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

love-math · 发表于 2012-6-4 15:47

这种编码方法破解的难度主要在于运算量超大，目前的计算机水平无法实现。

技术员 · 发表于 2012-6-5 16:35

支持蜘蛛侠！请继续努力。开根大数算法有难度，如果你给我算法，我可以帮你试试。

ysr · 发表于 2012-6-6 13:30

谢谢各位朋友的支持！
“这种编码方法破解的难度主要在于运算量超大，目前的计算机水平无法实现。”
计算机的速度和容量是重要因素，但障碍可以用改变数学方法排除，由于大数开平方程序未编出来，原法难试，只好用+-*/及穷举迭代试代用版，不同于常规，是以余数波动周期为单位试，大副减少试除个数和时间，高手可以试，程序走完是否能成功破解，不知道！
“开根大数算法有难度，如果你给我算法，我可以帮你试试。”
是仿手工算法，看《（求助）求修改开平方程序》，前面部分是小位数的开平方可以22位的，无法调用大数的+-*/程序，数学原理参考《大整数开平方的数学原理》1文！谢谢！！

技术员 · 发表于 2012-6-6 19:18

下面引用由ysr在 2012/06/06 01:30pm 发表的内容：
谢谢各位朋友的支持！<BR>“这种编码方法破解的难度主要在于运算量超大，目前的计算机水平无法实现。”<BR>计算机的速度和容量是重要因素，但障碍可以用改变数学方法排除，由于大数开平方程序未编出来，原法难试 ...

给个链接或顶一下吧。

ysr · 发表于 2012-8-25 14:36

45楼的加法重新编辑了1下，原稿没有考虑最高位的进位，如999+1=000，是错的，修改后为999+1=1000，欢迎试用批评！

ysr · 发表于 2018-4-6 06:52

本帖最后由 ysr 于 2018-4-5 23:10 编辑

快速分解大整数:若M=Pq+r，令2B+1=(q-1)/(P-1)，(实际B=x/n，见前文所述)，要分解M，设其一个因子为P+F，则可得到经验方程:
(P+F)(2B+1)F=qF-r，整理得:
(2B+1)F^2-(q-(2B+1)P)F+r=0，由求根公式即可得到F。
例:分解M=14585113=？
解:令B=7.18，则由以往公式可得P=975，则有
   M=975*14959+88，由求根公式得
F=660/30=22，P+F=975+22=997，
   14585113=997*14629.
则实际B=6.843，与设定值7接近。

经验证当B的值非常接近实际的时候往往所得到的F值不稳定，而有的远离实际值，差距巨大。反而是当B的设定值远远大于实际值的时候，所得到的F值基本上稳定，接近于实际，这样我们就可以得到一个接近于实际的因子。再进一步从最高位开始逐步确定各位数字(如何确定？后面再讲，道理简单述叙繁琐，主楼方法有明白了也可以用)，得到十个可能的因子。

   实际上这些因子是概率值，既使概率仅0.01，对于巨大的数值来说也已经算大概率事件，故此法是有意义的，正如某论坛一位朋友在几年前所说的:不否认有碰巧能分解的时候。

故，此法可以编程一试，好在不会消耗太多时间，这一法仅分解特定类型合数，且是不完全分解法，两因子不一定都是素数，适用于B小于某个小数值如10000 0000.

主楼文章我现在看也觉得复杂，简单方便的方法肯定是有的，只要大家努力就会找到。感谢没有把我的文章当垃圾的认真阅读并参与讨论的各位朋友，欢迎朋友们关注和探讨！

求模的逆元的方法和公式推导参见下图，下图为陆教授给出的方法:
此法可以同时得到p模n的逆元，逆元为-C，可以用d-C得到正值，当|C丨>d，则C=MOD(C，d)。如下图中23模67的逆元为-32，67-32=35，(23*35-1)/67=804/67=12.

会大整数计算的不妨编程序试验一下。欢迎指出宝贵意见！

ysr · 发表于 2018-4-6 11:01

欢迎关注和讨论！欢迎批评！

ysr · 发表于 2018-4-12 19:00

注意上面例子中设定值的用法，其实还要乘以一个系数:7/7.18=0.97，故式中代入2B+1=7*2+1=15.
      还用上面那个数为例。
分解因数，求:M=14585113=？
解:令B=10，则2B+1=21，代入前一式得P=833，则有14585113=833*17509+116，乘以系数0.835重新定义2B+1=0.835*21=17.535，则由求根公式得
   F=165，则P+F=833+165=998，实际因子为997，经试除很快得14585113=997*14629.

故此法还得进一步研究。没有电脑仅用小数来验证没什么意义，系数也无法确定，是定值还是变化的函数？还要进一步研究，有电脑可以用电子表格的计算功能多验证一些数，推广到大数值。
      感兴趣的欢迎探讨和沟通！

ysr · 发表于 2020-1-2 19:33

这个方法的程序基本完成，是分步做的，不是统一的一个程序，而是多个程序，如分解因数，求逆元，蒙哥马利快速幂模等等。
没有可以破解的例子，只能是实验一些自己弄的数据，分步实验。

ysr · 发表于 2020-1-2 20:25

实验一下这个原理：由于2^13-1=8191是素数，所以可以当做公开模数，明文与模必须互质，不能有公约数，否则就逆不回去了，我们来求出密钥和公钥：由于127是素数与模数8190（8191内与其互质的数有8190个）是互质的，127模8190的逆元是2773，则私钥为127，公钥是2773，现在发个密文：由于127与8190互质，把127当做明文，则有：127^127mod 8190=3403，则3403为明文，但3403^2773mod8190=3403仍然是密文，所以是保密的，由于127和2773互为逆元，由2773模8190得到逆元是127，而3403^127mod8190=127，这就是明文，所以被破解，还原回明文。

		自动登录	找回密码
密码			注册

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