RSA算法中密钥对可交换使用的证明
3582 点击·0 回帖
灯火互联
楼主
 |  | |
 | 【前言】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，即反证失败。 证明完成 作者“张宇(数据恢复)” | |
 |  |