 |
【前言】RSA算法研究中的一点随笔
RSA算法简述(类C风格描述)：
设P、Q为2个大素数；
N=P*Q；
T=(P-1)*(Q-1)；
找到某数E,使其满足E与T互素(E与T的公约数只有1)；
找到某数D,使其满足(E*D) % T == 1;
则：(D、N)与(E、N)即为可互换的加密(解密)密钥对。
设加密明文为 M, 加密后的密文为C。下面过程假设(E、N)为加密用的公钥，(D、N)为解密用的私钥。
加密：C= (M的E次幂) % N；
解密：M= (C的E次幂) % N；
证明(D、N)与(E、N)即为可互换的加密(解密)密钥对：
如(D、N)与(E、N)可互换，需满足如下2个条件：
1、(D*E) % T == 1;
证明：((E*D) % T ) == ((D*E) % T)；
2、需满足D也与T互素
证明：假证D与T不互素，则可描述：
D==a1*X;
T==a2*X;
由(D*E) % T == 1;
==> (a1*X*E) % (a2*X) ==1;
==> a1*X*E == b*a2*X+1;
==> (a1*E-b*a2)*E==1;
==> E只能==1,且 a1*E-b*a2==1，如E==1，即反证失败。
证明完成
作者“张宇(数据恢复)”
| |
