RSA算法详解

RSA算法详解

欧拉定理

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

费马小定理

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

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