RSA密码体制加解密的演示：

若n=pq，且p丶q均为素数，则φ（n）=(p-1)(q-1)，由于6958000001674999998647为两个11位的素数的积，则可以当公开模数，做密码，这个位数少容易分解，

不安全，只是演示RSA密码的原理。

则φ（n）=(p-1)(q-1)=6958000001505999998640，选公钥，

公钥的选择在1~φ（n）之间，公钥必须与φ（n）互质

根据互质数的性质:

(1):小数与大质数互质，

(2):小质数与不含有它的倍数的大合数互质，

由于122333221和6958000001505999998640 最大公约数为：1，所以122333221可以做公钥，而122333221模6958000001505999998640 的逆元

4415860875509221693741，这个逆元就是私钥，私钥比公钥长，演示加密：明文123456789^122333221 MOD 6958000001674999998647=2920527367305698772708， 解密是这样：密文2920527367305698772708^4415860875509221693741 MOD 6958000001674999998647=123456789，还原回去了，这就是过程。

6958000001674999998647=71000000041*97999999967为两个11位的素数的积，则可以当公开模数，做密码，这个位数少容易分解，不安全，只是演示RSA密码的原理

原理的证明分三段：欧拉定理的证明，其推论的证明，RSA加解密过程的证明。下面是欧拉定理的证明：

欧拉定理：a^φ(n)=1（modn）

证明：

将1~n中与n互质的数按顺序排布：x1,x2……xφ(n) （显然，共有φ(n)个数）

我们考虑这么一些数：

m1=a*x1;m2=a*x2;m3=a*x3……mφ(n)=a*xφ(n)

数m1,m2,m3……mφ(n)（如果将其次序重新排列）必须相应地同余于x1,x2,x3……xφ(n).

故得出：m1*m2*m3……mφ(n)≡x1*x2*x3……xφ(n) (mod n)

或者说a^[φ(n)]*(x1*x2*x3……xφ(n))≡x1*x2*x3……xφ(n)(mod n)

或者为了方便：K{a^[φ(n)]-1}≡0 ( mod n ) 这里K=x1*x2*x3……xφ(n)。

可知K{a^[φ(n)]-1}被n整除。但K中的因子x1,x2……都与n互质，所以K与n互质。那么a^[φ(n)]-1必须能被n整除，即a^[φ(n)]-1≡0 （mod n），即a^[φ(n)]≡1 （mod n），得证。 

当n为素数时就得到费马小定理：

费马小定理：对于质数p，任意整数a，均满足：a^p≡a（mod p）

而RSA密码的加解密过程不同于费马小定理。 

欧拉定理的推论：

　　若正整数a，n互质，那么对于任意正整数b，有a^b≡a^(b mod φ（n）)（mod n）

证明如下：（类似费马小定理的证明）

　　把目标式做一简单变形：a^(b - b mod φ（n）)* a^(b mod φ（n）)≡ a^(b mod φ（n）)（mod n），所以接下来只需要证明a^(b - b mod φ（n)）≡ 1 （mod n），又因为：

（ b - b mod φ（n））| φ（n），不妨设：（ b - b mod φ（n））= q*φ（n）（q为自然数），则有a^(q*φ（n）)== （a^q）^φ（n），因为a，n互质，那么（a^q）与n也互质，

那么就转换到了欧拉定理：（a^q）^φ（n）≡ 1 （mod n），成立。所以我们这个推论成立。

 b mod φ（n）是求模就是求余数的关系不是乘法，不等于b*φ（n），所以解释一下这一步：设b=q∗φ(n)+r,其中0≤r<φ(n),即r=b mod φ(n).于是：

（ b - b mod φ（n））| φ（n），

所以前面的成立。

RSA公钥密码解密过程的证明：

也就是证明下面的式子：c^d=m(mod n).

因为根据加密规则：m^e=c(mod n).

于是c可以写成：c=m^e-kn。

将c代入要我们证明的解密规则：

（m^e-kn）^d=m（mod n）。

它等同于求证：m^（ed）=m（mod n）。

这个容易证明：

等式m^（ed）=m（mod n）可以用欧拉定理的推论简单证明的，证明如下：

证明：根据欧拉定理的推论，

若正整数a，n互质，那么对于任意正整数b，有a^b≡a^(b mod φ（n）)（mod n）。

令b=ed，则m^(ed)=m^b，由于ed=1（mod φ（n）），所以m^(b mod φ（n）)=m （mod n）。

证毕！ 

当n为素数时照样成立，此时φ（n）=n-1.

所以，不同于费马小定理的，我们采用n为素数，当 φ（n）不等于n-1时，还原不回去明文m，就可以确定n为合数。 

RSA公钥密码体制是上世纪70年代～80年代好像是，由3个数学家弄出来的，RSA分别是3位数学家的名字的开首字母。

这个原理就是前面证明过程中的衡等式：m^（ed）=m（mod n）。

数学家居然把它拆开成两个等式，两个过程，没有反例，不会出错。

比较这两个公式：a^p≡a（mod p）（费马小定理），m^（ed）=m（mod n）（欧拉原理）(其中ed=1（mod φ（n）），n为素数也成立)

显然二者不同，不能同日而语。 

当n为素数时原理仍然成立，但此时n不用分解了，不安全了，但我们改变了其功能，不再是加密程序，而是用来判断n是否为素数。明文要

小位数要短，因为我们要判断的整数n是做除数的，除数比明文短余数就更短，还原不回去明文了，原理失效，如明文用123，

则对5位以上的都有效，成立，低于5位的可以用常规法判断。我已经据此原理编成程序，