登录后更精彩...O(∩_∩)O...
您需要 登录 才可以下载或查看，没有账号？立即注册
×
记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位整数需要几个月的时间。
2012.9.20
南宁
| 
发表于 2022-9-18 18:52:48
