数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
楼主: ysr

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

[复制链接]
发表于 2012-6-4 15:47 | 显示全部楼层

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

这种编码方法破解的难度主要在于运算量超大,目前的计算机水平无法实现。
发表于 2012-6-5 16:35 | 显示全部楼层

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

支持蜘蛛侠!请继续努力。开根大数算法有难度,如果你给我算法,我可以帮你试试。
 楼主| 发表于 2012-6-6 13:30 | 显示全部楼层

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

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

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

下面引用由ysr2012/06/06 01:30pm 发表的内容:
谢谢各位朋友的支持!<BR>“这种编码方法破解的难度主要在于运算量超大,目前的计算机水平无法实现。”<BR>计算机的速度和容量是重要因素,但障碍可以用改变数学方法排除,由于大数开平方程序未编出来,原法难试 ...
给个链接或顶一下吧。
 楼主| 发表于 2012-8-25 14:36 | 显示全部楼层

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

45楼的加法重新编辑了1下,原稿没有考虑最高位的进位,如999+1=000,是错的,修改后为999+1=1000,欢迎试用批评!
 楼主| 发表于 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.

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

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
 楼主| 发表于 2018-4-6 11:01 | 显示全部楼层
欢迎关注和讨论!欢迎批评!
 楼主| 发表于 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.

故此法还得进一步研究。没有电脑仅用小数来验证没什么意义,系数也无法确定,是定值还是变化的函数?还要进一步研究,有电脑可以用电子表格的计算功能多验证一些数,推广到大数值。
        感兴趣的欢迎探讨和沟通!
 楼主| 发表于 2020-1-2 19:33 | 显示全部楼层
这个方法的程序基本完成,是分步做的,不是统一的一个程序,而是多个程序,如分解因数,求逆元,蒙哥马利快速幂模等等。
没有可以破解的例子,只能是实验一些自己弄的数据,分步实验。
回复 支持 反对

使用道具 举报

 楼主| 发表于 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,这就是明文,所以被破解,还原回明文。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-6-15 06:38 , Processed in 0.078125 second(s), 14 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表