RSA算法详解

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（概率签名方案）