欧拉原理和RSA加解密过程的证明

ysr

欧拉定理和推论，统称为：欧拉原理。
RSA密码的原理就是利用的欧拉原理。

证明分三段：欧拉定理的证明，其推论的证明，RSA加解密过程的证明。（三个证明都是教科书上给出的，我只不过是择其简略的，复制黏贴，并整理在一起）

下面是欧拉定理的证明：
欧拉定理：a^φ(n)=1（mod n）
证明：
将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为合数。
当n为素数时原理仍然成立，但此时n不用分解了，不安全了，但我们改变了其功能，不再是加密程序，而是用来判断n是否为素数。明文要小，位数要短，因为我们要判断的整数n是做除数的，除数比明文短余数就更短，还原不回去明文了，原理失效，如明文用123，则对11位以上的都有效，成立，低于11位的可以用常规法判断。我已经据此原理编成程序，用于快速判断大素数，是确定性的方法。

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为素数也成立)
显然二者不同，不能同日而语。