一种基于随机漫游的RSA公钥密码破解方法及系统

一种基于随机漫游的rsa公钥密码破解方法及系统
技术领域
1.本发明涉及整数分解技术领域，尤其涉及一种基于随机漫游的rsa公钥密码破解方法及系统。


背景技术：

2.对公钥密码的研究是研究整数分解最主要的动力，试除法是目前已知的最早的整数分解方法。rsa公钥密码体制主要建立在rsa模数分解或解算困难的基础上。分解或解算rsa模数的本质是寻找分解任意整数的方法。为增强安全性，rsa模数越来越大，其分解难度也愈发增加。各国网络安全和密码研究人员都在积极寻找新的分解或解算rsa模数的方法以证实或证伪rsa公钥密码体制的安全性。


技术实现要素：

3.有鉴于此，为了解决rsa公钥密码破解方法中整数分解难度较大的技术问题，本发明提出一种基于随机漫游的rsa公钥密码破解方法，所述方法包括以下步骤：
4.获取rsa公钥密码的模数，记为n；
5.预估n的小因数上界，记为pb；
6.设定密集因子g，步长δ
x
和δy；
7.计算总起点
8.设置本轮漫游起点(x0，y0)＝(c
x
，cy)
9.初始化随机变量(x，y)＝(x0，y0)；
10.定义区域中任意元素ω的表达式；
11.计算ω与n的最大公因数f；
12.在所述区域循环随机移步，计算漫游所到处的ω和f，直至f大于1，输出f。
13.其中，pb预估值系随机预估，一般情况，可选择在附近。
14.在一些实施例中，还包括：
15.当计步器的数值大于预设计步阈值，跳出循环。
16.通过该优选步骤，通过预设计步阈值b，设定第二跳出循环的条件，防止循环无法终止。
17.在一些实施例中，还包括：
18.随机漫游区域可描述为：
19.1≤x≤n-p
b-1；
20.1≤y≤(x-1)g+1；
21.其三条边界分别为：
22.y＝1；
23.x＝n-p
b-1；
24.y＝(x-1)g+1。
25.通过该优选步骤，将含有大整数因数的宿主数汇集在一个可计算的三角形区域，进而给出了该区域边界、内点的计算方法。
26.在一些实施例中，区域中任意元素ω的表达式如下：
[0027][0028]
在一些实施例中，在所述区域循环随机移步，计算漫游所到处的ω和f，直至f大于1，输出f：
[0029]
生成随机数；
[0030]
根据随机数的值，结合步长，移动x和y；
[0031]
计算ω；
[0032]
计算ω与n的最大公因数f；
[0033]
判定x和y是否越界，若越界，则重返起点附近，得到本轮起点；
[0034]
其中，重返起点附近可以是最原始起点附近、前一轮迭代的起点附近和本轮迭代的起点附近，根据选择的起点不同，计算最终结果所花费的时间也会有所差异，在本实施例，优选地，选择返回前一轮迭代的起点附近；另外，由于是随机漫游方法，对于起点的附近点不作具体限定。
[0035]
循环直至f大于1，输出f。
[0036]
在一些实施例中，x和y是否越界的判定规则如下：
[0037]
若x≤1，则判定为越界；
[0038]
若x≥n-p
b-1，则判定为越界；
[0039]
若y≤1，则判定为越界；
[0040]
若y≥(x-1)g+1，则判定为越界。
[0041]
该步骤中，设定越界条件，在判断到越界，强制返回起点附近。
[0042]
在一些实施例中，所述根据随机数的值，结合步长，移动x和y这一步骤，其具体包括：
[0043]
若随机数的值为1，则x从当前位置向上移动δ
x
；
[0044]
若随机数的值为2，则x从当前位置向下移动δ
x
；
[0045]
若随机数的值为3，则y从当前位置向左移动δy；
[0046]
若随机数的值为4，则y从当前位置向右移动δy。
[0047]
其中，二维随机移步的1～4代表上下左右4个方向，每一步都随机选择下一步的方向，按照设置的步伐移动。因为x、y的范围不一样，所以步伐长度可设置得不同。
[0048]
在一些实施例中，所述重返起点附近，其具体包括：
[0049]
生成第二随机数；
[0050]
若第二随机数为1，则x从本轮起点(x0，y0)向上移动δ；
[0051]
若第二随机数为2，则x从本轮起点(x0，y0)向下移动δ；
[0052]
若第二随机数为3，则y从本轮起点(x0，y0)向左移动δ；
[0053]
若第二随机数为4，则y从本轮起点(x0，y0)向右移动δ。
[0054]
本发明还提出了一种基于随机漫游的rsa公钥密码破解系统，所述系统包括：
[0055]
至少一个处理器；
[0056]
至少一个存储器，用于存储至少一个程序；
[0057]
当所述至少一个程序被所述至少一个处理器执行，使得所述至少一个处理器实现如上所述一种基于随机漫游的rsa公钥密码破解方法。
[0058]
基于上述方案，本发明提供了一种基于随机漫游的rsa公钥密码破解方法及系统，是将含有大整数因数的整数(后称“宿主数”)汇集在一个平面区域并经随机漫游去寻找这些宿主数的方法，通过集合的笛卡尔差运算将含有大整数因数的宿主数汇集在一个可计算的三角形区域，给出了该区域边界、内点的计算方法；利用计算机随机漫游在该区域搜索含这些宿主数以便分解大整数。汇集后的宿主数在所述区域的密度提高使得搜索的成功率提高，克服了整数分解难度较大的技术问题。
附图说明
[0059]
图1是本发明一种基于随机漫游的rsa公钥密码破解方法的步骤流程图；
[0060]
图2是本发明具体实施例随机漫游分解整数的流程示意图；
[0061]
图3是本发明具体实施例里面的p-带和pq-三角形。
具体实施方式
[0062]
本发明沿用集合、元素和集合运算，诸于空集集合并∪、集合差-以及属于关系∈。特别地a-b表示从集合a中剔除所有同时在集合b中的元素。记号表示从a推导出b。记号和分布是地板函数和天花板函数，这些在一般计算机教科书中可见。
[0063]
记号x＝a mod b表示x是整数a除以整数b的余数,或者说a＝kb+x,这里a,b,k,和x都是整数。
[0064]
另外，还存在一些记号定义：
[0065]
设s是一个集合，e∈s是s的一个元素；e在s里重复出现的次数称为e的重复度记为me。例如，集合s＝{1,2,2,3}里有m1＝1,m2＝2以及m3＝1。记号e
∨m
表示将m个重复出现的元素不计顺序地置于一起，即,以此记号集合s＝{1,2,3,2}可表为{1
∨1
,2
∨2
,3
∨1
}。设x＝{x1,x2,...,xn}是一个包含n＞0个元素的有限集合，记号xk表示
[0066][0067]
这里k＞0为整数。
[0068]
设a＝{a1,a2,...,an}是包含n个整数的有限集合，则-a＝{-a1,-a2,...,-an}；记号b＝a(mod x)表示b＝{a1mod x,a
2 mod x,...,anmod x},这里x≠0是一个整数。若b＝{b1,b2,...,bn}是包含n个整数的有限集合，b≡a(mod x)表示bi≡ai(mod x)，i＝1,2,...,n。
[0069]
本发明所称整数区间[a,b]是从a开始到b结束的全部整数集合。例如[5,9]＝{5,6,7,8,9}。本发明所称奇数区间[a,b]指从a开始到b结束的全部奇数集合。例如，奇数区间[5,9]＝{5,7,9}。如果一个区间包含整数x,则该区间称作x的宿主区间。
[0070]
定义1.设x＝{x1,x2,...,xn}是一个有限集合，这里n为正整数；若x的全部元素均为0，即则称x为零集合并用记号x＝0表示。
[0071]
定义2.设a＝{a1,a2,...,as}、b＝{b1,b2,...,b
t
}是两个有限集合,这里s、t均为正整数；则b与a的笛卡尔差定义为：
[0072][0073]
为方便起见，可简记为：
[0074][0075]
显而易见,且即使是b＝a。
[0076]
定义3.设a＝{a1,a2,...,an}是有限集合,这里n是正整数。由a中所有不相同元素组成的集合称为a的核。例如
[0077]
定义4.如果d是合数n的因数，则n称为d的宿主数。
[0078]
下面将结合本技术实施例中的附图，对本技术实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本技术一部分实施例，而不是全部的实施例。基于本技术中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本技术保护的范围。
[0079]
需要说明的是，为了便于描述，附图中仅示出了与有关发明相关的部分。在不冲突的情况下，本技术中的实施例及实施例中的特征可以相互组合。
[0080]
应当理解，本技术中使用的“系统”、“装置”、“单元”和/或“模块”是用于区分不同级别的不同组件、元件、部件、部分或装配的一种方法。然而，如果其他词语可实现相同的目的，则可通过其他表达来替换该词语。
[0081]
如本技术和权利要求书中所示，除非上下文明确提示例外情形，“一”、“一个”、“一种”和/或“该”等词并非特指单数，也可包括复数。一般说来，术语“包括”与“包含”仅提示包括已明确标识的步骤和元素，而这些步骤和元素不构成一个排它性的罗列，方法或者设备也可能包含其它的步骤或元素。由语句“包括一个
……”
限定的要素，并不排除在包括要素的过程、方法、商品或者设备中还存在另外的相同要素。
[0082]
在本技术实施例的描述中，“多个”是指两个或多于两个。以下术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者更多个该特征。
[0083]
另外，本技术中使用了流程图用来说明根据本技术的实施例的系统所执行的操作。应当理解的是，前面或后面操作不一定按照顺序来精确地执行。相反，可以按照倒序或同时处理各个步骤。同时，也可以将其他操作添加到这些过程中，或从这些过程移除某一步或数步操作。
[0084]
主要引用的数学原理有：
[0085]
基于前述定义的笛卡尔差运算本发明首先证明了多个数学结论，然后衍生出整数分解的新方法。这些数学原理包括引理、定理和推论。
[0086]
引理1.设a＝{a},b＝{b},c＝{c1,c2,...,cn},这里n＞0为整数；记则
[0087]
ca∪cb＝{c
i-xj|,ci∈c,xj∈a∪b}
[0088]
或者
[0089][0090]
证明：直接按照定义2展开得
[0091][0092]
令x＝{c
i-xj|,ci∈c,xj∈a∪b}，则有
[0093]
x＝{c
1-a,c
2-a,...,c
n-a,c
1-b,c
2-b,...,c
n-b}
[0094]
从而，ca∪cb＝x
[0095]
引理2.设a1＝{a1},a2＝{a2}a＝{a1,a2}＝a1∪a2,b＝{b1,b2,...,bn},这里n＞0为整数。
[0096]
若
[0097]
且
[0098]
则c＝c1∪c2[0099]
或者
[0100]
证明.该引理是引理1的另一种说法。仿照引理1的证明可证明之。
[0101]
引理.设a＝a1∪a2、b＝b1∪b2,这里a1,a2,b1,b2均非空；则
[0102][0103]
更一般地,若a＝a1∪a2∪...∪ak、b＝b1∪b2∪...∪b
l
，则
[0104][0105]
这里k和l均为正整数,1≤i≤l,1≤j≤k，
[0106]
证明.不失一般性，设a1＝{a
11
,a
12
,...,a
1s
},a2＝{a
21
,a
22
,...,a
2t
},b1＝{b
11
,b
12
,...,b
1u
}及b2＝{b
21
,b
22
,...,b
2v
},这里s、t、u、v均为正整数。令则由定义2直接展开得：
[0107]
由于
[0108][0109][0110][0111][0112]
可知类似地可证明一般情况下的结论。
[0113]
引理4.设a＝{a}、b＝{a,a}、c＝{c1,c2,...,cn},这里n＞0为整数。若
[0114]
则或者更一般地，a＝{a}、可得或者
[0115]
证明.直接计算得
[0116]
[0117]
由b＝a2得
[0118][0119]
因为x＝ak,所以
[0120][0121]
引理4*.设a＝{a}、b＝{a,a}、c＝{c1,c2,...,cn},这里n＞0为整数。若
[0122]
则或者更一般地，a＝{a}、可得或者
[0123]
证明.直接计算得
[0124][0125]
从而
[0126][0127]
由x＝ak得
[0128][0129]
引理5.设a＝{a}、b＝{b1,b2,...,bn},这里n＞0为整数。则有：
[0130][0131]
这里k》0为整数。
[0132]
证明.比较引理4和4*的证明即得本引理的证明。
[0133]
引理6.设a＝{a}、b＝{b}、c＝{c}；则有这里g是一个正整数。
[0134]
证明.由于直接计算得：
[0135][0136]
引理7.设这里p、q都是正整数。若
[0137]
则c＝{(b-a)
∨pq
}
[0138]
证明.直接计算即得：
[0139]
定理与推论：
[0140]
定理1.设k、l是两个正整数,α＝min(k,l)、β＝max(k,l)。再设a＝{a1,a2,...,ak}、b＝{b1,b2,...,b
l
}是两个连续整数形成的集合且b
1-ak＝ω≥0；若c是笛卡尔差
[0141]
则有(1)c的元素c
ij
之计算公式为：
[0142]cij
＝b
i-aj＝ω+(i-1)+(k-j),i＝1,2,...,l；j＝1,2,...,k.
ꢀꢀꢀꢀ
(1)
[0143]
从而c包含kl个元素，其中最小的是ω、最大的是ω+(l-1)+(k-1)。
[0144]
(2)集合c包含k+l-1个不同的元素，它们是ω、ω+1、
…
、和ω+(l-1)+(k-1)。因此一些元素会重复出现。这些重复出现元素的重复度为
[0145][0146]
也就是说，在c中k+l-1个不同元素中，有β-α+1个的重复度为α、2个的重复度为α-1、2个的重复度为α-2，依此下去，2个的重复度为1。
[0147]
证明.由于a和b都是连续正整数形成的集合，故有bi＝b1+i-1、aj＝a1+j-1＝a
k-k+j。
[0148]
从而b
i-aj＝b1+i-1-(a
k-k+j)＝b
1-ak+(i-1)+k-j＝ω+(i-1)+(k-j)
[0149]
此即为(1)所述。
[0150]
将c写成行列的形式得：
[0151][0152]
若k＝l得
[0153][0154]
若k＜l则有：
[0155][0156]
而k＞l时得：
[0157][0158]
式子(3)、(4)、(5)即知c包含kl个元素，其中ω是最小的、ω+(l-1)+(k-1)是最大的，同时也证明了(2)所述的结论。
[0159]
根据(3)、(4)、(5)，若不考虑元素的顺序，在k≠l时c可以表示为：
[0160]
c＝{ω
∨1
,(ω+1)
∨2
,...,(ω+α-2)
∨(α-1)
,(ω+α-1)
∨α
,(ω+α)
∨α
,...,(ω+β-1)
∨α
,(ω+β)
∨(α-1)
,...,(ω+β+α-3)
∨2
,(ω+β+α-2)
∨1
}
[0161]
而在k＝l时有c＝{ω
∨1
,(ω+1)
∨2
,...,(ω+α-2)
∨(α-1)
,(ω+α-1)
∨α
,(ω+α)
∨(α-1)
,...,(ω+2α-3)
∨2
,(ω+2α-2)
∨1
}
[0162]
例子1.设a＝{1,2,3,4}、b＝{5,6,7,8}；则k＝4、l＝4、ω＝1,且有
[0163]
c＝{4,3,2,1,5,4,3,2,6,5,4,3,7,6,5,4}＝{1
∨1
,2
∨2
,3
∨3
,4
∨4
,5
∨3
,6
∨2
,7
∨1
}
[0164]
可知4重复了4次、3重复了3次、2重复了2次。
[0165]
更具体地：m1＝1,m2＝2,m3＝3,m4＝4,m5＝3,m6＝2,m1＝7。
[0166]
推论1.设k、l、a、b、c如定理1所述。若a＝b则有
[0167]
(1)c的行列表示式为：
[0168][0169]
或
[0170]
c＝{(1-k)
∨1
,(2-k)
∨2
,...,-1
∨(k-1)
,0
∨k
,1
∨(k-1)
,2
∨(k-2)
,...,(k-2)
∨2
,(k-1)
∨1
} (7)
[0171]
即有：m
1-k
＝1,m
2-k
＝2,...,m-p
＝k-p,...,,m-2
＝k-2,m-1
＝k-1,m0＝k,m1＝k-1,m2＝k-2,...,m
p
＝k-p,...,m
k-2
＝2，m
k-1
＝1。
[0172]
(2)在c中任意两个重复元素之间有k个其它元素。
[0173]
证明.由a＝b得知ω＝1-k。由此及(3)即刻得到(6)和(7)。从(6)中可以看出结论(2)。
[0174]
设是不考虑c中元素的符号形成的集合即这里则
[0175][0176]
推论2.设α、β、ω、a、b为定理1所述,是不考虑c中元素的符号形成的集合
[0177]
即
[0178]
则中有k2个元素，其中有2(k-s)个取值s,这里s是满足0＜s≤k-1的整数。
[0179]
证明.记则当b＝a时由定理1知c包含k2个元素。从而含有k2个元素。另外一个结论可直接从(8)得到。
[0180]
例子.设a＝{1,2,3,4}、b＝{1,2,3,4}；则
[0181][0182]
推论3.设a＝[a+1,a+j]、b＝[a+j+1,a+j+k]、c＝[a+j+k+1,a+j+k+l]是整数区间，s＝a∪b∪c，这里a为整数、j≥1、k≥1、l≥1。则
[0183][0184]
若记则
[0185][0186]
证明.所述结论直接从(7)和(8)得到。
[0187]
注记1.在推论3里面取a＝0得到a＝[1,j]、b＝[j+1,j+k]、c＝[j+k+1,j+k+l]和s＝[1,j+k+l]。可以看出k和l越大，或中源于[1,j-1]和[j,j+k]的元素之重复度越大。
[0188]
例子.设a＝{1,2,3,4}、b＝{5,6,7}、c＝{8,9,10,11}；则a＝0、j＝4、k＝3、l＝4和s＝{1,2,3,4,5,6,7,8,9,10,11}。从而
[0189][0190]
推论4.设a为整数；取a＝{a}、b＝{a+1,...,a+k}、c＝{a+k+1,a+k+2,...,a+k+l}及s＝a∪b∪c，则
[0191][0192]
若则
[0193][0194]
定理2.设a、b定理1所述；则对任意正整数g都有
[0195][0196][0197]
证明.记ai＝{ai}(i＝1,2,...,k)、bj＝{bj}(j＝1,2,...,l)。则且由于由引理2、3、4和6得
[0198][0199]
同理得
[0200][0201]
例子.设a＝{1,2,3,4}、则k＝4、l＝4、g＝2。
[0202]
直接计算得：
[0203][0204]
推论6.设a＝{a1,a2,...,ak}是一个连续整数组成的集合，则
[0205][0206]
这里k和g都是正整数。
[0207]
证明.设以及
[0208][0209]
则和分别为：
[0210][0211][0212]
记
[0213][0214][0215]
则由引理3得
[0216][0217]
再由引理7,1≤i,j≤k。从而
[0218][0219]
与此同时，由即刻得到
[0220][0221]
例子.设a＝{1,2,3,4}则
[0222][0223]
由(7)知，故有：
[0224]
推论7.设k、a如定理1所述；则
[0225][0226]
若集合定义为这里则
[0227][0228]
这里s是满足1≤s≤k-1的整数。
[0229]
证明.由推论6,参考(7)和(8)知(9)、(10)成立。
[0230]
推论8.设a如定理1所述；则
[0231][0232]
证明.参考本发明定义的新记号及推论1，即得本证明。
[0233]
注记2.将写成行列的形式有
[0234][0235]
借助矩阵运算的转置符号t知
[0236][0237]
定理3.给定整数a、g》0、n》0，假设a＝{a+1,a+2,...,a+n}、b＝{a+1,a+2,...,a+gn}；
[0238]
若不考虑集合的元素顺序，有：
[0239][0240]
证明.由推论8,集合
[0241][0242]
共含有gn个元素。对其每个元素取模n的余数得知
[0243][0244]
再由推论1
[0245][0246]
设为任意非零元素即eb≠0，那么它比为eb＝i
±
gn的性质，这里1≤i≤n-1。
[0247]
注意到，对于j＝1,2,...,g有
[0248]
ebmod n＝i
±
gn mod n＝i,1≤i≤n-1
[0249]
从而
[0250][0251]
对比即知定理获证。
[0252]
分解整数的方法：
[0253]
因为rsa数为殆素数，这里考虑n＝pq是因数p和q生成的殆素数，1＜p＜q。假设p和q宿主区间为i
p
＝[ps,pb]、iq＝[qs,qb]，这里ps、pb、qs、qb都是奇整数满足和在i
p
里找出p或者在iq里找出q即分解了n。为此设a
p
＝[1,p
s-1]、b
p
＝i
p
、c
p
＝[pb+1,pe]和s
p
＝a
p
∪b
p
∪c
p
,这里pe＞pb+1为整数。那么有
[0254][0255]
由前述注记1知，b
p
里的元素会重复出现在里面，且pe越大重复的次数越多。为达到分解的目的，先考虑pe＝n的情形，再考虑pe＝gn的情形，这里g≥1为整数。
[0256]
pe＝n的情形分析
[0257]
从pe＝n得出
[0258][0259]
或者
[0260][0261]
从而在里面，p的宿主数满足：
[0262]mp
＝2(n-p
s-p),m
2p
＝2(n-p
s-2p),...,m
αp
＝2(n-p
s-αp),...,m
(q-1)p
＝2(n-p
s-(q-1)p)
[0263]
这里α为满足1≤α≤q-1的整数。
[0264]
由前述推论1知，中p的宿主数每隔p个其它元素出现一次，离散地分布着，其总数为：
[0265]np
＝2(n-p
s-p)+2(n-p
s-2p)+...+2(n-p
s-αp)+...+2(n-p
s-(q-1)p)＝(q-1)n
[0266]
由于pe＝n意味着也包含q、2q、3q、...、(p-1)q，它们每隔q个其它元素出现一次，总数为
[0267]
nq＝(p-1)n
[0268]
因此，包含的n之因数的宿主数总数为
[0269]
nd＝n
p
+nq＝(p+q-2)n
[0270]
例如，取n＝35直接计算之中有60个5、50个10、40个15、30个20、20个25和10个30,共计210个元素包含因数5；还同时包含56个7,42个14,28个21和14个28,共计140个元素包含因数7。
[0271]
在表达式(11)里，对角线上的0将整个集合分为上下两个三角形,它们每个都包含同样数量n的因数。在下面的三角形中可以看到，有一个从ps到pb的带，如图3所示，这个带里面每列都包含一个p。故称此带为p-带。另外注意到，p-带之下的三角形包含全部p宿主数αp(这里整数α＞1)和q的宿主数βq(这里整数β≥1)，故称此三角形为pq-三角形。
[0272]
p-带中包含元素总数量为：
[0273][0274]
pq-三角形包含元素的总数量为：
[0275][0276]
二者包含元素的总量为：
[0277][0278]
注意到，p-带中重复之p的个数为：
[0279][0280]
因此pq-三角形中含有n之因数的宿主数总量为：
[0281][0282]
若记
[0283]
pq-总＝p带∪pq-三角形
[0284]
则在p-带、pq-三角形以及pq-总中含有n之因数的宿主数之密度分别为：
[0285][0286][0287]
以及
[0288][0289]
经计算得到
[0290][0291]
和
[0292][0293]
由于
[0294][0295]
以及
[0296][0297]
可知(13)满足
[0298][0299]
式子(14)和(12)表明pq-三角形中n之因数的宿主数分布密度最大。
[0300]
pe＝gn的情形分析
[0301]
记ξ＝[1,gn]则有
[0302]
该集合共包含(q-1)gn个p的宿主数和(p-1)gn个q的宿主数。因此g称为密集因子。
由于中除0之外的任意元素都能表示成i
±
jn，这里1≤i≤n-1，0≤j≤g。用行和列的方式表示，为：
[0303][0304]
同样可知，包含n之因数的宿主数稀疏地分布在集合中。现在考虑其密化方法。根据定理3考虑有
[0305][0306]
因此pe＝gn的情形转换为pe＝n情形的重叠，即的情形。从而有
[0307][0308]
显而易见，pe＝gn的情形是pe＝n密化后的结果。上述集合中同样存在p
g-带,(pq)
g-三角形和(pq)
g-总，其中(pq)
g-三角形包含最高密度n之因数的宿主数。
[0309]
参照图1和图2，在(pq)
g-三角形上的随机漫游分解方法
[0310]
(pq)
g-三角形里汇集了最大数量的n之因数的宿主数，在此区域搜索到其中任何一个元素譬如e，那么e和n之间的最大公因数d＝gcd(e,n)就是n的一个因数。以下给出通过随机漫游搜索的方法。为方便起见，将(pq)
g-三角形记为那么
[0311][0312]
采用行列的形式为
[0313]
[0314]
由于元素pb+1在边界上重复了(n-p
b-1)g次，因此每行只取一个作为边界。那么可以得到一个随机漫游的区域：
[0315]
第1行:d
1,1
＝pb+1；
[0316]
第2行:
[0317]
第3行:
[0318]
第4行:
[0319]
第k行:
[0320][0321]
这里1≤k≤n-p
b-1、1≤j≤k-1。
[0322]
采用随机变量x和y,随机漫游的区域可描述为：
[0323]
1≤x≤n-p
b-1、1≤y≤(x-1)g+1
[0324]
其三条边界为
[0325]
线l1：y＝1,线l2：x＝n-p
b-1,线l3:y＝(x-1)g+1.
[0326]
区域中的任意元素ω可用x、y和g表示为：
[0327][0328]
确定了随机漫游的区域后，漫游的首起点(总起点)、每轮漫游起点、步伐及其越界后的处理成为关键。由于是p和q的自然分界数，首起点(c
x
,cy)可以选择为由于y向漫游的位移平均近似是x向的g倍，选择较大的y向步距能提高效率。本发明视从起点开始至出界而未找到目标数的漫游为一轮，设定每轮起点为(x0,y0)，采用arandstep(x,y,δ
x
,δy)来计算从当前点(x,y)迈一步后的位置，这里δ
x
、δy分别是x方向与y方向的步距。漫游每到一处则以当前的(x,y)按照(15)计算此处的ω值并计算ω与n的最大公因数f＝gcd(n,ω)。如果f》1则n的因数找到，漫游终止；否则继续漫游。当漫游越过边界后，需要通过returnstart(x0,y0δ)强迫返回到起点(x0,y0)附近一个距离为δ的范围内重启一轮漫游。本发明设定outofborder(x,y)来判定x、y是否越界。为避免长时间漫游而未搜索到目标，设定一个计步器并给予一个阀值b。当计步器的总步数超过该阀值时，强制漫游终止，重启下一轮漫游。
[0329]
所述随机移步arandstep(x,y,δ
x
,δy)、强制返回起点附近returnstart(x0,y0,δ)和判定是否出界outofborder(x,y)以及本发明的总体算法如下：
[0330]
1.随机移步arandstep(x,y,δ
x
,δy)的实现方法：
[0331]
随机产生1到4的整数；
[0332]
若前述随机数为1，则x从当前位置向上移动δ
x
；
[0333]
若前述随机数为2，则x从当前位置向下移动δ
x
；
[0334]
若前述随机数为3，则y从当前位置向左移动δy；
[0335]
若前述随机数为4，则y从当前位置向右移动δy。
[0336]
2.强制返回起点附近returnstart(x0,y0,δ)的实现方法：
[0337]
随机产生1到4的整数；
[0338]
若前述随机数为1，则x从本轮起点(x0，y0)向上移动δ；
[0339]
若前述随机数为2，则x从本轮起点(x0，y0)向下移动δ；
[0340]
若前述随机数为3，则y从本轮起点(x0，y0)向左移动δ；
[0341]
若前述随机数为4，则y从本轮起点(x0，y0)向右移动δ；
[0342]
需要注意的是，在本实施例，优选地，选择返回前一轮迭代的起点附近。
[0343]
3.判定是否出界outofborder(x,y)的实现方法：
[0344]
如果x≤1或者x≥n-p
b-1或者y≤1或者y≥(x-1)g+1；则判定出界。
[0345]
总体算法：
[0346]
获取rsa公钥密码的模数，记为n；
[0347]
设定密集因子g和pb，步长δ
x
和δy；
[0348]
计算总起点
[0349]
设置本轮漫游起点(x0，y0)＝(c
x
，cy)
[0350]
初始化随机变量(x，y)＝(x0，y0)；
[0351]
定义随机漫游区域以及区域中任意元素ω的表达式；
[0352]
计算ω与n的最大公因数f；
[0353]
在所述区域循环随机移步，计算漫游所到处的ω和f，直至f大于1，输出f。
[0354]
另外，本发明还公开了另一实施例，一种基于随机漫游的rsa公钥密码破解系统，包括：
[0355]
至少一个处理器；
[0356]
至少一个存储器，用于存储至少一个程序；
[0357]
当所述至少一个程序被所述至少一个处理器执行，使得所述至少一个处理器实现如上所述一种基于随机漫游的rsa公钥密码破解方法。
[0358]
上述方法实施例中的内容均适用于本系统实施例中，本系统实施例所具体实现的功能与上述方法实施例相同，并且达到的有益效果与上述方法实施例所达到的有益效果也相同。
[0359]
以上是对本发明的较佳实施进行了具体说明，但本发明创造并不限于所述实施例，熟悉本领域的技术人员在不违背本发明精神的前提下还可做作出种种的等同变形或替换，这些等同的变形或替换均包含在本技术权利要求所限定的范围内。

技术特征：
1.一种基于随机漫游的rsa公钥密码破解方法，其特征在于，包括以下步骤：获取rsa公钥密码的模数，记为n；预估n的小因数上界，记为p
b
；设定密集因子g，步长δ
x
和δ
y
；计算总起点设置本轮起点(x0，y0)＝(c
x
，c
y
)初始化随机变量(x，y)＝(x0，y0)；定义随机漫游区域以及区域中任意元素ω的表达式；计算ω与n的最大公因数f；在所述区域循环随机移步，计算漫游所到处的ω和f，直至f大于1，输出f。2.根据权利要求1所述一种基于随机漫游的rsa公钥密码破解方法，其特征在于，还包括：当计步器的数值大于预设计步阈值，跳出循环。3.根据权利要求2所述一种基于随机漫游的rsa公钥密码破解方法，其特征在于：随机漫游区域可描述为：1≤x≤n-p
b-1；1≤y≤(x-1)g+1；其三条边界分别为：y＝1；x＝n-p
b-1；y＝(x-1)g+1。4.根据权利要求3所述一种基于随机漫游的rsa公钥密码破解方法，其特征在于，区域中任意元素ω的表达式如下：5.根据权利要求4所述一种基于随机漫游的rsa公钥密码破解方法，其特征在于，在所述区域循环随机移步，计算漫游所到处的ω和f，直至f大于1，输出f这一步骤，其具体包括：生成随机数；根据随机数的值，结合步长，移动x和y；计算ω；计算ω与n的最大公因数f；判定x和y是否越界，若越界，则重返起点附近，得到下轮起点，仍记为(x0，y0)；循环直至f大于1，输出f。6.根据权利要求5所述一种基于随机漫游的rsa公钥密码破解方法，其特征在于，x和y是否越界的判定规则如下：若x≤1，则判定为越界；若x≥n-p
b-1，则判定为越界；若y≤1，则判定为越界；
若y≥(x-1)g+1，则判定为越界。7.根据权利要求6所述一种基于随机漫游的rsa公钥密码破解方法，其特征在于，所述根据随机数的值，结合步长，移动x和y这一步骤，其具体包括：若随机数的值为1，则x从当前位置向上移动δ
x
；若随机数的值为2，则x从当前位置向下移动δ
x
；若随机数的值为3，则y从当前位置向左移动δ
y
；若随机数的值为4，则y从当前位置向右移动δ
y
。8.根据权利要求7所述一种基于随机漫游的rsa公钥密码破解方法，其特征在于，所述重返起点附近，其具体包括：生成第二随机数；若第二随机数为1，则x从本轮起点(x0，y0)向上移动δ；若第二随机数为2，则x从本轮起点(x0，y0)向下移动δ；若第二随机数为3，则y从本轮起点(x0，y0)向左移动δ；若第二随机数为4，则y从本轮起点(x0，y0)向右移动δ。9.一种基于随机漫游的rsa公钥密码破解系统，其特征在于，包括：至少一个处理器；至少一个存储器，用于存储至少一个程序；当所述至少一个程序被所述至少一个处理器执行，使得所述至少一个处理器实现如权利要求1-8任一项所述的基于随机漫游的rsa公钥密码破解方法。

技术总结
本发明公开了一种基于随机漫游的RSA公钥密码破解方法及系统，该方法包括：获取RSA公钥密码的模数；设定密集因子和步长；计算起点以及初始化漫游点；定义随机漫游区域以及区域中任意元素的表达式；计算区域中元素与模数的最大公因数；循环随机移步并输出最大公因数。该系统包括包括存储器以及用于执行上述基于随机漫游的RSA公钥密码破解方法的处理器。通过使用本发明，能够克服RSA公钥密码破解方法中整数分解难度较大的技术问题。本发明可广泛应用于整数分解技术领域。用于整数分解技术领域。用于整数分解技术领域。


技术研发人员：王兴波
受保护的技术使用者：佛山科学技术学院
技术研发日：2023.07.18
技术公布日：2023/9/14