RSA加密

RSA算法

明文和密文均是0至n-1之间的证书，n的大小通常为1024位的2进制，或309位的十进制。

生成RSA密钥

每个用户生成一个私钥/公钥对，通过：

随机选择两个大素数p,q;【保密的，选定的】
计算系统的模量：N=pq 【公开的，计算得到的】
- 注意有 $\phi(N)$ =(p-1)(q-1)【比N小又与N互素的数的个数】
随机选择e,满足gcd( $\phi(N),e$ )=1；1<e< $\phi(N)$ 【公开的，选定的】
解出d,d满足 $d\equiv e^{-1}(\mod \phi(N))$ 【保密的，计算得出的(扩展欧几里得算法?)】

即 ed=1mod $\phi(N)$ 且1<d< $\phi(N)$ 【ed互为模 $\phi(N)$ 的乘法逆】
公布公钥{e,N}；保存私钥{d,N}

【乘法幂回顾】

如果a和b互素，则b有模a的乘法逆元。【注意：互素是前提】

即如果gcd(a,b)=1,那么b有模a的乘法逆元。对于b<a,存在 $b^{-1}<a$ ，使 $bb^{-1}=1\mod a$

RSA的使用

明文分组M和密文分组C:

$C=M^e \mod n；(0\leq M<N) \\ M=C^d \mod n =(M^e \mod n)^d \mod n =M^{ed} \mod n (0\leq C<N)$

因此，有 $M^{ed} \mod n =M$

另一种: $C^d = (M^e)^d = M^{1+k.ø(N)} = M^1.(M^{ø(N)})^{k} = M^1.(1)^k = M1 = M mod N =M$

RSA浅析

【欧拉定理】数论中的欧拉定理（费马-欧拉定理），表明，若n,a为正整数，且n,a互质，则 $a^{\phi(n)}\equiv 1 \mod n$

在RSA中，N=pq, $\phi(N)=(p-1)(q-1)$ 选择mod N互逆的ed,得到 $ed=1+k\phi(N)$

RSA证明

$M^{ed} \mod n =M$

1.M和p不互素，p可以整除M。则M mod p=0， $M^{ed}\mod p=0$

2.M和p互素，根据欧拉公式， $M^{\phi(p)} \mod p=1$

$M^{ed}\mod p=M^{1+k\phi(p)}\mod p\\=(M\mod p)\times ((M^{(p-1)})^{k(q-1)}\mod p)\\=(M\mod p)\times ((M^{\phi(p)})^{k(q-1)}\mod p)\\=(M\mod p)\times 1^{k(q-1)}=M\mod p$