首页
社区
课程
招聘
[原创]二次筛法研究学习笔记
2018-2-4 00:37 32906

[原创]二次筛法研究学习笔记

2018-2-4 00:37
32906

前因

       初来科锐学习,在某次看雪CTF赛中,遇到RSA算法加密,而RSATool无法快速的对上百位的大数进行分解,事后通过老师的指导,了解到看雪工具栏版块有分解大整数的工具PPSIQS,好奇其中原理,于是查阅相关资料,了解到这款工具利用的是二次筛法算法分解的大整数。特别感谢钱老师,姚老师的悉心教导,于是写下这篇笔记以记录心得。

 

       我们知道很多密码系统的安全性依赖于大整数因子分解问题的困难性。比如RSA加密算法,其破解的核心其实就是分解其中的大数,找到其两个质因子。
对于一般的数位位数较小的情况(几十bit的数量级),常用的分解整数的方法是试除法。而当数位达到百bit数量级时,试除法因为其效率低下,明显不适合大数分解。
解决较大的整数分解问题,有椭圆曲线算法、特殊数域筛法、二次筛法等,而二次筛法是500bit及以下整数分解时,已知的最快算法。

 

       我自己没有找到很好的介绍二次筛法中文资料。因此作文一篇,在此简单介绍下二次筛法。由于无法输入数学公式,部分内容以截图的形式呈现

1. 二次筛法思想简述

       了解二次筛法前,需要先了解下费马分解法,因为二次筛法是来源于费马分解法的。

1.1费马分解法

       在费马分解法发明之前的很长一段世间,人们只会使用试除法分解大数,而费马分解法的发明,使得分解大数效率大大提高。费马分解法的具体操作是怎样的呢?

 

       其实很简单,以分解大数N为例,在费马分解法中,我们并不直接去找N的质因子。而是试图先找一对具有以下关系的平方数:
图片描述

 

如果能找到以上关系的x、y,那我们可以继续变形得到:
图片描述

 

       这相当于说明(x+y)*(x-y)能够被N整除,那么(x-y)中一定有与N共有的公约数。通过欧几里得算法,可以很快地找到(x-y)与N的最大公约数,自然就是N的分解了。

 

       所以,在费马分解法的指导下,我们的问题转变了,我们只需要找到 x^2≡y^2 (mod N) 关系即可。然而,如果盲目去尝试,这样的x,y也是很不容易找到的……

 

       二次筛法的发明,就是帮助我们有步骤地、有效地找到满足以上条件的x、y关系。

1.2二次筛法中的二次函数

       在二次筛法中,我们先构造一个二次函数:
图片描述
       其中x是从0开始的任意整数。之所以构造一个这样的二次函数,是因为它天然地满足一些我们期待的要求(可以帮助我们进行N分解),理由如下:

 

图片描述

 

       以上式子的右边,已经是一个平方数了,所以,我们的问题进一步简化和明确,只需要Q(x)是一个(模N的)平方数,即可用费马分解法分解。

1.3二次筛法中的因子基(Factor Bae)

       如何比较高效地寻找Q(x),确保它是一个平方数呢?联想到所有的整数都可以分解成质数的幂的乘积形式。所谓平方数,其实就是所有质因子的幂是偶数的的情况(如400 = 2^4 * 5^2)。

 

       在二次筛法中,我们并不试图去直接找满足平方数要求的Q(x),而是先找一系列能够被某个质数集合完全分解的数,再由这些数,拼凑出Q(x)来。
而“某个质数集合”,称为“因子基”(Factor Base)。能够被因子基中的质数完全分解的数,我们称为其是“光滑的”(Smoothness)。

 

       比如,我们选在{2, 5}作为因子基,则400相对于这个因子基就是光滑的,而30相对于这个因子基就是不光滑的。

1.4利用Q(xi)构造Q(x)

图片描述
       这时,右边已经符合平方数,而左边,因为Q(xi)都是光滑的,我们只要选择适合的Q(xi)相乘,确保乘积结果的所有质因子的幂是偶数即可,这个过程本质上是解一个线性方程的过程。

2.算法简述

图片描述

3.举一个例子

        我们来简单看一下利用二次筛法分解N = 15347。

3.1 收集Q(xi)

图片描述
图片描述
图片描述

3.2 处理Q(xi)

       通过上表我们不难看出很明显Q(3)直接满足条件。那么我们就有:
图片描述

 

       一般运气没那么好,并不能直接得到Q(x),而是构造来的,比如,我们剔除掉Q(3),用剩余几个Q(x_i)来构造。剩余几个Q(x_i)的指数矩阵S:

 

图片描述

 

       我们想要找到矩阵R:

 

图片描述

 

       解以上线性方程得到:

 

图片描述

 

       则我们知道:

 

图片描述

 

       显然 149 * 103 = 15347 。我们也成功分解了整数15347。

4.程序

       按照算法思路,我简单按流程实现一个DEMO,在寻找合适的矩阵步骤上,没有想到效率更高的算法,采用了穷举,导致循环次数呈指数增长,部分算法也没有做优化,导致只能是一个参考Demo...

 

图片描述

最后是广告:要毕业了,帮科锐宣传下,科锐30期正在招生中(https://bbs.pediy.com/thread-51839.htm)


[培训]《安卓高级研修班(网课)》月薪三万计划

上传的附件:
收藏
点赞8
打赏
分享
最新回复 (13)
雪    币: 22975
活跃值: (3312)
能力值: (RANK:648 )
在线值:
发帖
回帖
粉丝
KevinsBobo 8 2018-2-4 09:40
2
0
赞!
雪    币: 48
活跃值: (25)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
想要养只猫 2018-2-4 22:44
3
0
( ̄∀ ̄)板凳
雪    币: 23
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
mb_tfcmlgee 2020-5-6 06:08
4
0
很棒
雪    币: 1255
活跃值: (147)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Yilisah 2020-5-17 10:49
5
0
很不错,值得学习。
雪    币: 5568
活跃值: (2931)
能力值: ( LV12,RANK:394 )
在线值:
发帖
回帖
粉丝
htg 4 2023-4-6 14:32
6
0
内容不错,由浅入深
雪    币: 5568
活跃值: (2931)
能力值: ( LV12,RANK:394 )
在线值:
发帖
回帖
粉丝
htg 4 2023-4-23 09:16
7
0
有没有继续在深入讲解数域筛法,SNFS或GNFS,感觉太难理解了。
雪    币: 18614
活跃值: (27889)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
秋狝 2023-4-23 09:30
8
1
感谢分享
雪    币: 6
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
tao.hong 2023-12-11 16:09
9
0
二次筛法,本来是可以一直雄踞榜首的,无奈二次筛法首创者,没有完全弄明白扩展平方剩余理论,寻找你所谓的“因子基”是有强壮的理论支撑的,与x²-N大小无关,甚至可以y²+N方向筛选,还可以x和y双向筛(两面约去奇次方即可),但规模还是需要大量统计支撑的,减少无用功,
雪    币: 6
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
tao.hong 2023-12-11 16:20
10
0
我发现的二次剩余筛法,300位以下,无需“二次筛法”,直接遍历即可,就像暴力试除法的(当然是扩展版)最高接近7倍,只不过暴力试除法筛的是N=pq的p或q,而二次剩余筛法筛的是x²-y²=N的x或y,但是倍数却是千亿倍量级(每交叉一个小质数,跳距增加2倍)!
雪    币: 76
活跃值: (1467)
能力值: ( LV2,RANK:15 )
在线值:
发帖
回帖
粉丝
mb_wjynirwq 2023-12-11 17:36
11
0
tao.hong 我发现的二次剩余筛法,300位以下,无需“二次筛法”,直接遍历即可,就像暴力试除法的(当然是扩展版)最高接近7倍,只不过暴力试除法筛的是N=pq的p或q,而二次剩余筛法筛的是x²-y²=N的x或y,但 ...
有文章吗,大佬
雪    币: 6
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
tao.hong 2023-12-13 07:19
12
0
没文章,寻求合作中!
雪    币: 6
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
tao.hong 2023-12-13 11:37
13
0
有对二次筛法源码熟悉的,可以联系我,可以推出升级版!我十分想证实,是否不同的“因子基”,会有多个爆点?如果可以,那就应该多大的数都能在有限时间内分解!
雪    币:
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
mb_sjkhdbvk 2023-12-28 18:26
14
0
这个代码跑不了,有没有大佬救救我
游客
登录 | 注册 方可回帖
返回