RSA算法详解

欧拉定理

$n$和$a$为正整数，且$a和n$互素，即$gcd(a,n)=1$，则：

$$ a^{\phi(n)} \equiv 1(modn) $$

费马小定理

对于任意素数$p$和正整数$a$，且$a$不是$p$的倍数，则：

$$ a^{p-1} \equiv 1(mod {,}n) $$

RSA算法密钥产生

  • 选择$p,q$ $p和q$都是素数，其中$p \neq q$
  • 计算$n=p \times q$
  • 计算$\phi(n)=(p-1)(q-1)$
  • 选择整数$e$ $gcd(\phi(n),e)=1;1<e<\phi(n)$
  • 计算$d$ $d \equiv e^{-1}(mod{,}{\phi(n)})$
  • 公钥 $PU={e,n}$
  • 私钥 $PR={d,n}$

简写

  • OAEP= Optimal Asymmetric Encryption Padding（最优非对称加密填充）
  • PSS = Probabilistic Signature Scheme（概率签名方案）