首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. 密码应用
    3. 发新帖
[翻译]初学者向导—GGNFS和MSIEVE分解因数
发表于: 2012-9-20 20:42 62633

[翻译]初学者向导—GGNFS和MSIEVE分解因数

tihty 活跃值
2
2012-9-20 20:42
62633

记512位RSA破解

        最近，我用ggnfs破解出了512位RSA算法的私钥。感谢看雪论坛密码学小组，感谢，是这些前人的研究，带给了我指引和成功。所以，我想把这段经历分享给大家，希望更多的人懂得这件事情，将前人的研究成果发扬光大。

源起：
        公司的一个重要项目，需要知道某个协议中的RSA私钥，在同事们经历了几个月探寻之后，依然未果。能不能用一个工具，将RSA模数进行分解？这个大胆的念头开始在我心中萌发。

经过：
        我开始在网上寻找能够对大数做因式分解的工具，很快，我找到了看雪密码学小组的帖子，原来它就在我眼皮底下，『密码学』板块的头条置顶帖。
        经过仔细阅读，我发现有一套工具ggnfs能够对大数做因式分解。
        我开始按照帖子的内容布置工具环境，并尝试分解了一些256位的整数，我惊奇地发现，用这个工具分解256位整数只用4分钟。
        小有成效，我心里已经开始有些小小的欢喜，但是依然对分解512位整数怀有些许担心。
在隐隐的担忧下，我启动了对512位整数的分解。
        在接下来的35天里，我耐心地等待着，不时地祈祷。直到前几天，因数出来了：）

喜悦：
        原来真512位RSA真的像新闻上说的一样可以破解！

        既然是从看雪上学习而来，又是成功经验，所以我想，我应该把这个帖子翻译一遍，引起更多的人重视，方便大家学习研究。再说一遍，感谢看雪。

-------------------------------------------->8-------------------------------------------------------------
英文原链接：http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html


初学者向导—GGNFS和MSIEVE分解因数
作者 Jeff Gilchrist
译者 tihty
最近更新：2009.4.14

本文帮助初学者学习使用数域筛算法（NFS）分解大于100位（10进制位）的整数，它会教你如何使用GGNFS和MSIEVE工具完成因数分解。对于小于100位的整数，应该用MSEIVE或者YAFU工具进行二次筛法。

本文用分解下列121位的整数作为例子，进行讲解：
8996941959382577683409613171454174240738275788293429353288678806601664747011544951714674576925430397444054300751795281737

第1步 – 下载工具软件
获取GGNFS工具包
对于windows用户，你需要SVN 339或更高版本，预先编译好的GGNFS工具可以从这个网站获得
对于linux和unix用户，你需要下载源代码并自己进行编译，或者使用64位的linux版本

获取最新的MSIEVE，并覆盖GGNFS工具包中的文件
如果你是windows用户，预先编译好的MSIEVE程序可以从这个网站获得
如果你是linux或者unix用户，你需要下载源代码并自己进行编译。注意：为了启用高级多项式选择代码，你需要用’make GMP=1’或者’ECM=1’选项进行编译，否则将使用旧的多项式选择代码。

对于windows用户，你需要一个类unix环境来运行perl脚本，为此需要在系统上安装cygwin，cygwin安装包可以从这里下载。安装时在组件选择页面把”perl”选项设置为安装，确保perl组件被安装。安装完成之后，双击cygwin图标就可以进入shell环境。

注意：如果你无法完成第一步，那么请放弃，因为你可能没有能力完成剩下的步骤。

第2步 – 安装和配置软件
下载或编译好GGNFS程序集之后，将它们复制到一个目录下，例如/home/jeff/ggnfs
GGNFS工具包中含有一个旧版本的MSIEVE文件，你应该用最新版本来将这个文件覆盖

现在/home/jeff/ggnfs目录下应该包含下列文件（unix下可执行文件没有exe后缀名）：
def-nm-params.txt
def-par.txt
factLat.pl
factMsieve.pl
ggnfs-doc.pdf
gnfs-lasieve4I12e.exe
gnfs-lasieve4I13e.exe
gnfs-lasieve4I14e.exe
gnfs-lasieve4I15e.exe
gnfs-lasieve4I16e.exe
makefb.exe
matbuild.exe
matprune.exe
matsolve.exe
msieve.exe
pol51m0b.exe
pol51m0n.exe
pol51opt.exe
polyselect.exe
procrels.exe
sieve.exe
sqrt.exe

现在切换到你的ggnfs目录下（cd /home/jeff），为分解任务建立一个工作目录（md example），这样我们就有了这样的目录结构/home/jeff/ggnfs/example

windows用户需要确保ggnfs/msieve在cygwin中设置成正确的执行许可，进入ggnfs目录运行下列命令：
chmod 755 *.exe *.pl

接下来用你最喜欢的编辑器编辑factMsieve.pl文件，windows用户可能会想用Notepad++或者Crimson Editor。你需要修改factMsieve.pl文件以对它进行配置，需要修改的地方有：

第3,4行从:
# The path where the binaries are:
$GGNFS_BIN_PATH="../../ggnfs/bin";
改成:
# The path where the binaries are:
$GGNFS_BIN_PATH="..";

第54行从:
$NUM_CPUS=1;
改成你想用来做因式分解的CPU数，在双核的系统上，可以选择1或者2, 四核系统上，可以选择1,2,3,4:
$NUM_CPUS=2;

如果你想让软件在低优先级下运行，以避免影响操作系统上运行的其他程序, 请把第89,90行从:
# Run the binaries at low priority?
# $NICE="nice -n 19 ";
改成:
# Run the binaries at low priority?
$NICE="nice -n 19 ";

保存对factMsieve.pl文件所作的修改，然后继续下面的步骤。

第3步 – 多项式选择
NFS算法分为3个阶段，首先是多项式选择，然后是筛选，最后是线性代数。开始分解因数之前，我们必须先选择一个多项式，获得多项式最简单的方法是让ggnfs工具帮你选择一个。对于少于140位的整数，用msieve选择的多项式比ggnfs选出的能够减少10-20%的筛选时间。关于msieve的用法，请看GNFS指南中的使用msieve做多项式选择。对于初学者，可能更加适合用ggnfs工具来选择多项式。

在命令行窗口中切换到你的工作目录（cd /home/jeff/ggnfs/example），在工作目录里，创建一个名叫example.n的文本文件，并在其中粘贴你要分解的整数。本文使用前面提到的121位整数，并在数字前加上”n:”，所以文件中的内容就是：

n:8996941959382577683409613171454174240738275788293429353288678806601664747011544951714674576925430397444054300751795281737

在工作目录中使用下列命令启动分解过程：
../factMsieve.pl example.n

这会调用pol51工具为example.n文件中的整数选择一个多项式，屏幕上的输出类似这个样子：

-> ___________________________________________________________
-> |        This is the factMsieve.pl script for GGNFS.       |
-> | This program is copyright 2004, Chris Monico, and subject|
-> | to the terms of the GNU General Public License version 2.|
-> |__________________________________________________________|
-> This is client 1 of 1
-> Using 2 threads
-> Working with NAME=example...
-> Error: Polynomial file example.poly does not exist!
-> Found n=899694195938257768340961317145417424073827578829342935328867880660166
4747011544951714674576925430397444054300751795281737.
-> Attempting to run polyselect...
-> Selected default polsel parameters for 121 digit level.
-> Selected default factorization parameters for 122 digit level.
-> Selected lattice siever: ../gnfs-lasieve4I13e.exe
-> Searching leading coefficients from 1 to 1000.
=> nice -n 19  "../pol51m0b.exe" -b example.polsel.machinename.2044 -v -v -p 4 -n 1.67E+018 -a 0 -A 1 > example.polsel.machinename.2044.log

对于本例中的数字，多项式选择这个步骤大约花费2个小时左右，这步完成之后，perl脚本将自动为你进入后面的步骤。

第4步 – 筛选和线性代数
这是NFS算法的最后两个步骤，它们也会由factMsieve.pl脚本来替你完成。在选定多项式之后，脚本将自动启动筛选过程。

筛选阶段的屏幕输出像这个样子：

-> ___________________________________________________________
-> |        This is the factMsieve.pl script for GGNFS.       |
-> | This program is copyright 2004, Chris Monico, and subject|
-> | to the terms of the GNU General Public License version 2.|
-> |__________________________________________________________|
-> This is client 1 of 1
-> Using 1 threads
-> Working with NAME=example...
-> Selected default factorization parameters for 122 digit level.
-> Selected lattice siever: ../gnfs-lasieve4I13e
-> Creating param file to detect parameter changes...
-> Q0=2500000, QSTEP=60000.
-> makeJobFile(): q0=2500000, q1=2560000.
-> makeJobFile(): Adjusted to q0=2500000, q1=2560000.
-> Lattice sieving algebraic q-values from q=2500000 to 2560000.
=> "../gnfs-lasieve4I13e" -k -o spairs.out -v -n0 -a example.job
FBsize 182730+0 (deg 5), 348512+0 (deg 1)
total yield: 181, q=2500049 (0.03459 sec/rel)

如果你想在任务完成之前停止筛选，可以按下CTRL-C等待筛选器结束。停止之后，在工作目录再次运行类似前面的命令，也可以继续启动筛选。为了安全，最好在重新启动之前备份你的ggnfs/example目录下的文件。要从停止的地方继续执行分解任务，运行：
../factMsieve.pl example.poly

在生成的关系式达到预期的最小数量之后，脚本会运行msieve看是否有足够的关系式能够执行线性代数阶段。如果关系式的数量不够，就继续执行筛选过程。在某个时间，最终会产生足够的关系式，这时脚本将自动调用msieve执行最后的线性代数阶段。一旦完成这个最后阶段，因数就会显示出来。对于本例中的整数，大约需要850万个关系式。在主频3GHz的奔腾4处理器上，产生这些关系式大约需要4天时间。请确保你拥有足够的磁盘空间，因为这些关系式会使用很多空间。本例中，850万个关系式和中间文件使用了约1.2GB磁盘空间。最后，msieve程序执行线性代数阶段，这个过程大约花费几个小时，然后结果就会显示出来，类似这样：

<some data snipped>
.
.
commencing square root phase
reading relations for dependency 1
read 353299 cycles
cycles contain 1407657 unique relations
read 1407657 relations
multiplying 1151656 relations
multiply complete, coefficients have about 51.48 million bits
initial square root is modulo 24600791
reading relations for dependency 2
read 352893 cycles
cycles contain 1406530 unique relations
read 1406530 relations
multiplying 1149570 relations
multiply complete, coefficients have about 51.38 million bits
initial square root is modulo 23829469
prp58 factor: 7113268608388826628041175633889105572982840043845203074777
prp64 factor: 1264811221773952923237987117254409784246941529158530073219882481
elapsed time 00:29:35
-> Computing time scale for this machine...
sumName = g121-C121_104_57.txt
-> Factorization summary written to g121-example.txt.

正如你在输出中看到的，本例中的整数有2个可能的质因数，一个是58位整数（7113268608388826628041175633889105572982840043845203074777），另一个是64位整数（1264811221773952923237987117254409784246941529158530073219882481），你可以将它们两相乘，以检查结果是否等于你想要分解的整数。

第5步 – 享受质因数
祝贺你，你已经完成了大整数的因式分解，尽情地享受这份快乐吧。记住，分解更大的整数需要花更多的时间来做选择多项式和筛选，同时也会消耗更多金钱。在一台4核机器上用gnfs分解一个155位整数需要几个月的时间。


[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！

最后于 2020-5-1 21:22 被kanxue编辑 ，原因：
上传的附件：
收藏
免费 ・8
支持
分享
最新回复 (21)
tihty
雪    币： 27
活跃值： (127)
能力值： ( LV8，RANK：120 )
在线值：
发帖
回帖
粉丝
私信
2 楼
编辑帖子技巧不行，弄得不好看，希望大家喜欢：）
2012-9-20 20:49
0
kanxue
雪    币： 47147
活跃值： (20445)
能力值： (RANK：350 )
在线值：
发帖
回帖
粉丝
私信
3 楼
记事本里排好版，直接复制粘贴上来。显示出来就是记事本里面的格式。
2012-9-20 22:02
0
chengkang
雪    币： 94
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
4 楼
高手呀 谢谢分享 了解！
2012-9-20 22:11
0
kxzjchen
雪    币： 190
活跃值： (40)
能力值： ( LV3，RANK：20 )
在线值：
发帖
回帖
粉丝
私信
5 楼
右键摊主！！鸡冻啊
2012-9-20 23:51
0
missdiog
雪    币： 364
活跃值： (61)
能力值： ( LV3，RANK：30 )
在线值：
发帖
回帖
粉丝
私信
6 楼
Good，用GPU跑
2012-9-21 09:56
0
hellok
雪    币： 227
活跃值： (120)
能力值： ( LV10，RANK：160 )
在线值：
发帖
回帖
粉丝
私信
7 楼
顶
很好奇LZ机器什么配置，
35天.NB啊
2012-9-21 12:25
0
yxgbo
雪    币： 34
活跃值： (11)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
8 楼
mark一下，
2012-9-21 19:25
0
YwdxY
雪    币： 347
活跃值： (25)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
9 楼
感谢分享~
支持
2012-9-27 13:08
0
outlooker
雪    币： 187
活跃值： (18)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
10 楼
我用了25天分解了512位的大数，配置为Xeon 3460 4核8线乘,4GB, ESXi，Windows 2003 虚拟机 4GB, 4 Virtual CPUs, 40GB 硬盘;另外还有3个虚拟机在运行。
2013-4-16 01:44
0
jianghaha
雪    币： 1
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
11 楼
请教下。。我也是用Windows 2003 ，我现在单台是可以计算的。但是多台进行并行运算还没弄。你是怎么并行运算的。。坐等回答
2013-7-19 16:36
0
outlooker
雪    币： 187
活跃值： (18)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
12 楼
我没有并行计算，其他的虚拟机再运行其他云端服务
2013-7-26 05:11
0
Love Or Dream
雪    币： 3
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
13 楼
tihty 编辑帖子技巧不行，弄得不好看，希望大家喜欢：）
我想问一下，为什么我下的GNFS没有.pl文件啊
2018-6-16 00:09
0
satadriver
雪    币： 13
活跃值： (215)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
14 楼
求问Jeff Gilchrist帖子源地址，像拜读一下
2019-8-17 12:29
0
mb_abgypohf
雪    币：
能力值： ( LV1，RANK：0 )
在线值：
发帖
回帖
粉丝
私信
15 楼
outlooker 我用了25天分解了512位的大数，配置为Xeon 3460 4核8线乘,4GB, ESXi，Windows 2003 虚拟机 4GB, 4 Virtual CPUs, 40GB 硬盘;另外还有3个虚拟 ...
你好 可以告诉下怎么实现的吗  可以有偿的
2020-4-24 11:59
0
shark凯
雪    币： 6
活跃值： (113)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
16 楼
楼主工具可以发下不，网站已经无法下载了
2020-9-28 18:06
0
SnowFox
雪    币： 8107
活跃值： (1955)
能力值： ( LV8，RANK：122 )
在线值：
发帖
回帖
粉丝
私信
17 楼
shark凯 楼主工具可以发下不，网站已经无法下载了
找到个镜像站, 这里有下载
https://download.mersenne.ca/GGNFS
2020-11-6 16:46
0
shark凯
雪    币： 6
活跃值： (113)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
18 楼
SnowFox 找到个镜像站, 这里有下载 https://download.mersenne.ca/GGNFS
感谢兄弟
2020-12-7 10:54
0
莽莽s
雪    币： 239
活跃值： (58)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
19 楼
大佬，这个工具 只能用来分解 rsa数吗？分解任意一个60位的整数，用什么工具好啊？谢谢
2023-4-1 13:54
0
于恬
雪    币： 0
能力值： ( LV1，RANK：0 )
在线值：
发帖
回帖
粉丝
私信
20 楼
莽莽s 大佬，这个工具 只能用来分解 rsa数吗？分解任意一个60位的整数，用什么工具好啊？谢谢
这个可以分解任意的数，不一定是RSA！如果只是分解60位的整数，可以在这个网站分解即可哈https://zh.numberempire.com/numberfactorizer-394392480923
2023-6-5 15:48
0
秋狝
雪    币： 3059
活跃值： (30876)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
21 楼
mark
2023-6-6 09:18
1
dryzh
雪    币： 864
活跃值： (2355)
能力值： ( LV3，RANK：20 )
在线值：
发帖
回帖
粉丝
私信
22 楼
于恬 这个可以分解任意的数，不一定是RSA！如果只是分解60位的整数，可以在这个网站分解即可哈https://zh.numberempire.com/numberfactorizer-39439248092 ...

数字 (358971360037089496616230686115552284659215418104349240980871493191722094160398620549217504736246162)
您输入的表达式太长
最大长度为 70 字符

使用范围太小，不实用，没什么价值

最后于 2024-5-6 16:00 被dryzh编辑 ，原因：
2024-5-6 15:59
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//