RSA算法中密钥对可交换使用的证明

【前言】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;(X>1)
    T==a2*X;(X>1)
由(D*E) % T == 1;    
==> (a1*X*E) % (a2*X) ==1;
==> a1*X*E == b*a2*X+1;
==> (a1*E-b*a2)*X==1;
==> X只能==1,且 a1*E-b*a2==1，如X==1，即反证失败。

证明完成