RSA密码体制的原理和大素数的快速判断

ysr

RSA密码体制的原理和大素数的快速判断

原理方法和公式：
公式:C=M^e MOD n，M=C^d MOD n，ed=1  MOD φ（n）
其中n为公开模数，C为密文，M为明文，e为私钥，d为公钥。

流程演示：
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&#8727;φ(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位的可以用常规法判断。我已经据此原理编成程序，
但不会大整数的快速乘法除法，因此，速度很慢，寻求合作，希望感兴趣会大整数快速乘法除法程序的与我们联系！

这种大素数的快速判断可能是我的首发，没见别人这样用过，原理是现成的改变功能，变量改变了。原来明文密文是变量公开模数是固定的已知量，现在公开模数是待判定的变量明文是已知量，如123由程序员给定编在程序中，密文是程序自动产生的中间量，公钥和密钥由程序自动产生已经不需要输入，只输入公开模数，输出判定结果是否是素数。

欢迎合作，欢迎感兴趣的朋友与我沟通和联系！

ysr

这种方法是确定性的，用于判定位数多于明文位数的大素数，小于等于明文的可以用常规法。
速度还有很大的提升空间，会了快速乘法除法程序大大加快。
我有某数内的最大素数的估算公式，二者结合起来就快捷方便，可以得到需要的任意位数的大素数。公式暂时不发了。欢迎讨论和沟通！

ysr

这个是确定性的算法，没有反例，速度够快，足以满足需要得到需要的大素数，咋没人看？这就是数学中国的现状？

lusishun

您对万哲先教授的密码学，研究的很深啊！

ysr

啊？万哲先是谁？哈哈哈！我只对RSA密码研究过一点。

lusishun

中科院院士，华罗庚的学生。

ysr

谢谢！祝福前辈数学大师！祝愿数学中国人才辈出！

ysr

汉奸卖国贼洋奴才是不会支持我们的，他们恨不得把我们踩死拍死，以便用他们的稀牛屎忽悠中国人的钱，比如数学研发论坛的老板郭先强，是不会展示他的技术和原代码的，只会用他的破玩意忽悠中国人的钱，甚至可能暗中破坏中国人的网络安全密码体制。

那些洋奴才，舔人家稀牛屎能吃饱肚子？能不传染病毒？当你的主子觉得你没有利用价值踢你出门时候，那你还能吃饱肚子吗？你就成了鲁迅先生笔下的“丧家的资本家的乏走狗”。

方舟子，汪方之流，就是这样的汉奸叛徒卖国贼！必须处理，不能让这些疯狂的东西危害祖国和人民，不能让它们再嚣张下去了！！

ysr

也没有人看，顶起来，备自己查阅。欢迎朋友沟通和参考！

ysr

这么重要的文章没有人浏览，知识点也不高，容易明白，也不看，可见当今社会对科学知识尤其基础理论何等不重视？这已经是普遍现象，尤其中科院，不具有科学精神，不配科学二字！
民科弄出来的许多基本定理，是非常重要的，不仅在理论上重要，实际中也是有重要用途的，可惜没有人重视，根本不予以关注，更别说评审承认和推广普及！
其实差定理比和定理(就是哥德巴赫猜想)重要得多，有用的多。
差定理：任意两个奇素数的差(包括自身相减)可以表示全体偶数。且差为2，4，6，……，2n的素数对都有无穷多。
差定理的证明：
比如如下数列：
2n+1：3，5，7，……
2n+2m+1：3+2m，5+2m，7+2m，……
对应项差为2m，可以严格证明（我可以用多种方法证明，比如用欧几里得反证法）这两个数列中含有无穷多对素数对，而2m为全体偶数，m可以等于0，这就是差定理。2m就是所有，就是全体偶数。
从而由差定理推导和证明和定理（就是哥德巴赫猜想）：任意两个素数的和可以表示大于等于4的全体偶数。
证明：设p3>=p2>=p1>=3，由差定理知p2-p1=0，2，4，……，则有p2=p1+0，2，4，……（等式含义不解释）。由于p1，p2，p3各自集合无区别，则有p2+p3=2p1+0，2，4，……，又因为2p1>=6，4=2+2.故，命题成立。

证毕！
这样，这个定理就把小素数和巨大的素数建立了关连性，小的素数非常容易找到，而大素数很难找，如何快速得到呢？而且，我实际用到的大素数是具有密码学特征的，就是其中的数字排列不规则，且其中用到的数字字码比较全，这样的素数才是具有密码学特征的。
由于差为2，4，6，……，2n的素数对都有无穷多，n为任意值，就是该偶数没有任何限制条件，这样就方便了，通过小素数与巨大素数的差值的关连性找到需要的大素数。
任意位的具有密码学特征的偶数容易找到，一个小素数加上该偶数就是巨大的具有密码学特征的大素数。这样，找到大素数的概率就增加了，对密码的方便性和加强保密性都有重要作用。