[原创]RSA公钥密码的破解

ysr

这个跟加解密过程不一样，不知道为啥。这里的公开模数直接用的是素数，实际用的是两个大素数的积。

ysr

这个跟加解密过程不一样，不知道为啥。这里的公开模数直接用的是素数，实际用的是两个大素数的积。

ysr

我说怎么不能把明文逆回去呢？原来模为n而不是φ（n），弄错了！
公式为:C=M^e MOD n，M=C^d MOD n，ed=1  MOD φ（n）
其中n为公开模数，C为密文，M为明文，e为公钥，d为私钥，明天再用数据验证吧！哈哈哈……

ysr

刚才算了一下，结果是这样的：明文123（这样明文就可以随便了，不用考虑是否与公开模数互质了，因为公开模数是很大的两个素数的积），则有：123^127 mod 8191=651，而651^2773 mod 8191=123，这样就对了，还原回去了。明天再试试！

ysr

昨天弄了个蒙哥马利快速幂模程序，速度确实快，大数值的也能很快出结果，实验了一下RSA加解密过程，验证了很多数据，都是正确的，终于搞明白了基本原理（过去我研究过，现在忘了，重新查了一下资料，基本原理用到了费马-欧拉定理，还有欧拉函数，由此及推论可推出前述两个公式），如下是一个验证结果，实际公开模数必须是两个大素数的积，这里只用了一个素数，这样不安全，仅是验证原理的，发一个供参考，有空慢慢看吧！

2^61-1=2305843009213693951是素数，而8191与2305843009213693950互质，8191模2305843009213693950的逆元为818347653251643061，演示RSA的加解密过程，加密：123456789^8191 MOD 2305843009213693951=608413768934359310，解密：608413768934359310^818347653251643061 MOD 2305843009213693951=123456789，逆回去了，过程正确。

ysr

这些程序可以用来破解RSA公钥密码的，分步做的，共有4个程序：大整数的分解，求两个大整数的公约数（判断是否互质），求大整数模的逆元，蒙哥马利快速幂模运算。
有感兴趣的我可以把程序和代码都传上来。
欢迎感兴趣的朋友沟通探讨切磋一下！

ysr

我想把我的程序发出来，最先发大数的分解程序，供参考试用。其他的简单，如求最大的公约数和模的逆元，就是辗转相除法，而蒙哥马利快速幂模，就是一句话：幂的模等于模的幂，然后再求模。我没有压缩软件，无法直接上传。
我的笔记本电脑昨天卡了和死机了一样，昨天扫描了病毒没有病毒，清理了垃圾，开机反应慢。不知道为啥？我关机是直接合上本子，不知道操作正确不？

ysr

若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，还原回去了，这就是过程。 这个公开模数长度小，不安全容易分解，这里就是演示一下。

ysr

RSA密码的基本原理就是前面的公式，文本长度大的情况下，明文要分段转化为密文，密文长度变大，密文长度是有公开模数的长度决定的，且每段密文的长度是不规矩的，要么加前导0变统一长度，要么加入分段符号，分开数段。可见虽然公开模数越大越难于破解，但密文也越长而浪费资源。

我有个加密程序，是用伪随机密码加密的，速度快，而且由于采用伪随机密码，相同的内容每次的密码也是不一样的，难于破解，但文本框容量小，每次最多加密10000字节的内容，超过长度必须分段加密，且在密文中要分段。

程序已经发在本论坛，感兴趣的朋友可以参考我过去发的文章。

ysr

这个原理方法的逆命题可以用来判断大整数是否是素数，原理是：设公开模数n为素数则n=p，φ（n）=p-1，用前述方法若能还原为明文则n为素数，否则为合数，明文采用小数值如123，由于123=3*41，所以先要试除3和41，不能整除再做判断。
经过实验，判断100为的将近1小时，所以用来判断几十位的还是不慢 ，可以的。因为我的乘除法效率低，若弄出了快速乘除法程序，就可以判断成千上万位的整数了，快速乘除法用到快速傅立叶变换，不会，还要研究学习。