首页
社区
课程
招聘
[原创]商业级RSA算法解密的似乎可行的一种算法
2021-12-22 13:24 28855

[原创]商业级RSA算法解密的似乎可行的一种算法

2021-12-22 13:24
28855

上周,我开始找RSA加密的可行解法,然后就开始研究素数......之后嘛,就画了一张似乎并没有什么用的平面坐标系解析图(以(x,x)原数轴,(x,kx)为k数轴,(x,k∈N+)当k为定值时,y=k上只有一个与k之内的数轴的交点的对应的k数轴就对应为素数)这个图并没有多么神奇,它只是告诉我们若一个数不是比它小的所有数的整数倍数那么它就是素数,并且由一个自然数直接求它后面的第二个素数是不可能的.接下来,我就按这种方法展开成筛选集得到一个:求任意正整数的下一个素数的算法,并一步一步优化它,并把它融入到一下的这种启发式解RSA的算法当中.(整体来看会比较像实时训练五个朝不同方向大跨度遍历的查找器)

核心:求任意正整数的下一个素数的算法(求素模块)(我们不妨在整体分析时把求素数看做是求一个由一个振源产生的无限大的离散度扩大的波动的间隙或织布机,当进入下一个数时,波动时间递变1),//~~但若是忽略循环而直接看作求余化简后等价直接上素数筛法,相当于没啥用了。尴尬。。。。但其实模型还是可以用来解析的,小的空间循环完全可以用复数方程表示,可以把某一时刻的所有空间解析成一个大的复数方程,之后再把所有时刻的复数方程联立成更大的复数方程,之后对时刻+小空间的筛进行解析。整个方程当做曲线来看的话,素数就相当于洞。整体来看,更接近于由自然数由时间差步构造的复杂体系。

若n为正整数,使n+△n为素数(△n不能使之为n之前的所有数的倍数)
1.整体分析.(以下的全是关于△n,相当于进入筛时间不同,随后按自己的步调循环的质点)
经过简单推导可以得到△n的筛(原理是加上△n后不为该位数的倍数):n,n-2,n-4(开始的段很大,这些段在同一个循环节中,之后也会有很多这样的大段,都满足规律递减,称之为高位循环段,递减的差值随进入的循环深度而改变)......(n-m)-((n-m)%m),(n-(m-1)-((n-(m-1))%(m-1))(m为正整数,这些段的循环节很小,可以不讨论其共性,直接求该数减它的对n的余数,称之为低位循环段)......(直到除数为2)
2.开始由每个数来讨论.
(所有的数不会消失,只是陷入了不同依次差1的时间步 的循环中).
比如:
2=2121212121......,3=321321321321321......4=4321432143214321.....依次类推.
但由于多有重复,所以产生有效过滤的却仅是少数.这是因为可以认为在1.中说的高位循环段优先产生过滤效果,
由于高位循环段的规律一致,易于统计,并且在计算高位循环段的分组的同时,低位循环段也可以得到充分的计算.所以应优先计算高位循环段.
这个算法的实现.(简述)
输入:查找数w,查找单次上限a,查找总数上限b(这两个数的选取至关重要,因由训练器动态生成)
1.初始化:c=0,e=2.
之后q=e-(w%e),r=w+q,k=r//e,得到一个e的筛q,k作为筛集参数
筛集是一个逐级递减的等差数列,只需要记(k,e)即可(首项和项数自己推一下,是根据进入当前上面说的高位循环段决定的).(需注意的是只有e=2时,(k,e)可以有足够的项数一筛到底.这也决定了b越大,高位循环段的有效的筛越多)(相当于把高位循环段当成依次的的等差数列)
之后e+=1,并重复以上行为直到e=a.
2.合并所有q和(k,e)后得到总筛集,取总筛集中由小到大排布的第一个空缺数记为m.并对(m+w)进行常规的素数检验.
c+=1,
为素则输出.
不为素则在总筛集中添加m并接着上一次继续进行一遍a次求筛.
若发生c=b则输出错误并终止求素模块,并提供给训练器参数.(该正整数与下一个素数相距过远也算作查找器找到的是一个坏数)
(如果不限制b的情况下,最坏的情况是求到e与k交错时,针对高位RSA基本上就不可解了,幸好可以通过限制b来规避这种现象,b不能太小,若高位循环与低位数交错太少则会导致过滤效果太低.)

查找器(i,j),由初始值(受训练器改变)大跨度向四周遍历寻找p,q附近的正整数.(只谈思路,实现灵活)

需要实现两种模式:(主要是为了尽量少的调用上述的求素模块)
1.遍历模式(先基于二分,之后把控制权转交给训练器,详见运行流程)
2.收敛模式(基于训练器,开始减少跨度,使更接近下一个素数组)

 

需要五个查找器,分别为(+,+)(-,-)(+,-)(+,0)(-,0)...注:0表示不变化
在设计时,由于不同方向参数具有独立性,可以把一个方向的+或-设计为一个类,之后通过混合类派生.

训练器,用于解决求素模块与查找器的联系,每个查找器都应拥有自己私有的训练器(只谈思路,实现灵活)

应包含的方法如下:
1:更改查找器遍历的跨度参数
2:更改查找器的模式参数
3:更改每个查找器私有的求素模块的参数
4.接收来自求素模块和查找器返回的参数

运行的流程(简述,这里只叙述单个查找器的,每个查找器的线程是一样的,并且在运行后很快就只会剩查找器(+,-))

1.初始化:(初始时i=j),使i*j近似等于素积(应是偏小的,因为是下一个素数,求素后都会更大,若偏大的近似会超出素积),传递(i,j)初始化查找器和求素模块求素,之后求素模块传递参数给(a,b)并检验a*b==素积.否,则传递参数给训练器.训练器训练后(训练的主要思路是使求素后的a*b逼近素积,由于大素数存在积近似相等的情况的数密度很低,并且即使相近相差也比较大.所以可以通过大跨度查找素积近似等于素积的数(通过改训练器和查找器(遍历模式)实现),)传递参数给查找器改变(i,j),并按查找器得到新的(i,j)(i和j也应满足积近似为素积(收敛模式),这样便于求素模块求素).(单方向则只改i)
2.之后:按此次的(i,j)重复上述操作.直到a*b==素积,或出现来回波动的情况(以及开始就超范围的),此时则终止此查找器.
(当然,如果所有查找器都被近乎于步进查找了,则训练器或查找器的设计不合理)


[培训]科锐软件逆向50期预科班报名即将截止,速来!!! 50期正式班报名火爆招生中!!!

最后于 2022-2-19 22:56 被whereslow编辑 ,原因:
收藏
免费 0
打赏
分享
最新回复 (6)
雪    币: 152
活跃值: (1051)
能力值: ( LV3,RANK:33 )
在线值:
发帖
回帖
粉丝
whereslow 2021-12-25 18:18
2
1
这种方法的思路是很简单的(按照素数的定义来的),可行的原因是好优化。别沉了啊。。。。。
雪    币: 250
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
mb_bnceljza 2022-1-8 21:44
3
0
思路错了
雪    币: 152
活跃值: (1051)
能力值: ( LV3,RANK:33 )
在线值:
发帖
回帖
粉丝
whereslow 2022-1-10 22:50
4
0
mb_bnceljza 思路错了
RSA的安全性就是源于正确的思路都无法在足够大时有效求解。我这个思路是奇葩了点,但你估摸一下效果,基本上可以做到求解的复杂度与数大小无关。(只是实现上,尤其是使查找器估计的数积逼近得通过概率,还得不漏,实现困难。但其实这些都是浮云,最重要的是可以对一个自然数筛掉大量的非素数的Δn(并不会选择筛完),至于其他的部分,本就是该自由发挥的)
雪    币: 152
活跃值: (1051)
能力值: ( LV3,RANK:33 )
在线值:
发帖
回帖
粉丝
whereslow 2022-2-13 12:02
5
0

把自己的原型当结论用了,尴尬,唉。。。。。效率还不如直接筛选,还是错了。。。

最后于 2022-2-13 12:17 被whereslow编辑 ,原因:
雪    币: 0
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
mb_qksofjjn 2022-3-31 06:33
6
0
呵呵,我已经在高兴和失落之间反复横跳多次了。事实上,能意识到自己思路错了是件天大的好事。
雪    币: 1243
活跃值: (1815)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
库尔 2022-3-31 14:49
7
0
挺好,黎曼猜想还没那么容易破掉。
游客
登录 | 注册 方可回帖
返回