RSA 加密体制及其安全性分析

一.RSA 的原理

密钥生成：我们要选择两个大素数p pp和q qq，计算N = p ⋅ q N=p \cdot qN=p⋅q。公钥p k = ( N , e ) pk=(N, e)pk=(N,e)，私钥s k = ( p , q , d ) sk=(p, q, d)sk=(p,q,d)
同余关系：e ee和d dd必须满足e ⋅ d ≡ 1 ( m o d ( p − 1 ) ( q − 1 ) ) e \cdot d \equiv 1 \pmod{(p-1)(q-1)}e⋅d≡1(mod(p−1)(q−1))
加密：c = m e ( m o d N ) c = m^e \pmod Nc=me(modN)
解密：m = c d ( m o d N ) m = c^d \pmod Nm=cd(modN)
正确性验证：c d ≡ ( m e ) d ≡ m e d ≡ m ( m o d N ) c^d \equiv (m^e)^d \equiv m^{ed} \equiv m \pmod Ncd≡(me)d≡med≡m(modN)。

二.优化算法

计算x n ( m o d N ) x^n \pmod Nxn(modN)，当n nn是个 1024 位的数时，宇宙毁灭了都算不完。

1.平方-乘算法

口诀：从最高位开始扫描，遇到每一个比特都先平方；如果该比特是 1，则再乘底数 。
例子 (Page 18)：计算x 7 x^7x