参考官方wp:http://soreatu.com/ctf/writeups/Writeup%20for%20Crypto%20problems%20in%20NCTF%202019.html#childrsa
以及：https://blog.csdn.net/weixin_44017838/article/details/104907559
题目中官方wp中的和另外的wp有点区别，主要是n和c，不过问题不大，思路都差不多，本文章是在官方wp的基础上加了点工，补充了自己在理解官方wp中某些地方的思考
题目：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flag
def getPrime(bits):
while True:
n = 2
while n.bit_length() < bits:
n *= choice(primes)
if isPrime(n + 1):
return n + 1
e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)
# n = 32849718197337581823002243717057659218502519004386...........
# c = 26308018356739853895382240109968894175166731283702...........
首先，p,q由getPrime函数生成：1
2
3
4
5
6
7def getPrime(bits):
while True:
n = 2
while n.bit_length() < bits:
n *= choice(primes)
if isPrime(n + 1):
return n + 1
其中primes是Crypto.Util.number模块中定义的前10000个质数，最大的第10000个为104729
一般来说，我们寻找大质数都是随机生成一个大数，然后将其经过素性测试，能够通过的就返回。
常见的就是Crypto.Util.number模块中的getPrime函数，直接返回一个指定位数的素数，但是这道题自定义了一个函数用于生成p和q。
可以看到，本题getPrime生成的质数，是由前10000个质数随机抽取若干个累乘起来然后再加1生成的。
这就使得生成的质数p，将其减一后，其结果（也就是这个质数的欧拉函数p-1）能够被分解为许多个相对来说很小的质数。这在数学上有一个专门的术语，叫做B-smooth。很显然，p是104729-smooth的。
光滑数（smooth number）是一个可以约数分解为小素数乘积的正整数，若一正整数的素因数均不大于B，此整数即为B-光滑数。例如1620的约数分解为2^2 × 3^4 × 5，素因数均不大于5，因此1620是5-光滑数。
光滑数有什么坏处呢？
我们先来看一个叫做费马小定理的东西：
其中p为素数，a为任意正整数
也就是说，指数那边每增加p-1，其结果仍然不变。指数以p-1为一个循环
将其变型一下：
此时$a^{p-1}-1$同余0，也就是说$a^{p-1}-1$是p的倍数
将同余式改成等式，
其中$t，k$是两个正整数
如果指数$exp$是p-1的倍数，那么$a^{exp}-1$就是p的倍数
上面的p指某一素数
如果我们能够找到一个指数L，使得对于某一个底数a，$a^L-1$ 是p的倍数，但不是q的倍数，这时只要去计算
得到的结果，就是p，因而分解了N
那么，怎么去找到这个L呢？
Pollard的厉害之处就在于此，他发现，如果$p-1$正好是一些很小的质数的乘积，那么$p-1$就能整除$n!$，其中$n$是一个不太大的数。
假设
$p-1$等于这些质数的乘积，其中最大的质数是pk。那么，显然
肯定包括了p1, p2, …, pk这些质数的乘积，即$pk！$肯定是$p-1$的倍数。
也就是说，当$n>pk$的时候，$n！$很大概率上就能被$p-1$整除。（考虑到p1, p2, …,pk中可能有重复的情况）
这导致了Pollard’ p-1 method：
对于每一个$n=2,3,4…$，我们任意选择一个底数$a$（事实上，我们可以简单地选择为2），并计算
如果结果落在1和N中间，那么我们就成功了。
这个公式是我对官方wp的修正之一，另外的，对于此题的情况，我觉得就是完全不考虑p1, p2, …,pk中可能有重复的情况，不然要算更久。
我们假设
其中p4和p5是相邻的两个素数
若我们进一步假设p5=104729 p4=104723
那么当$n$只有大于104729时，$n!$才有可能被$p-1$整除，因为$n=104729$时
不可以约掉这个$p4$，只有当$n=2*p4=209446$时才可以约掉，此时$n!$才能被$p-1$整除
可见如果题目中choice函数出来的素数有重复且较大的话，运算时间将会指数处的阶乘放大（瞎bb这个名字，不会用时间复杂度描述）
实际操作中，这个算法有很多可以优化的地方。
例如，我们并不需要算出$a^{n!}-1$的确切值，当$n>100$时，$n!$本身就已经很大了，整体结果肯定巨大无比。我们每一次只需要算出$(a^{n!}-1)\ mod\ N$的值即可，可以将运算结果限制在模N的范围内。
这里也可以简单的用公式解释一下
我们的目的是求
而$(a^{n!}-1)\ mod\ N$的值
即$(a^{n!}-1)\ -\ kN$
若存在p且满足$gcd((a^{n!}-1)\ mod\ N,N)$
显然p是$(a^{n!}-1)\ -\ kN$这两项的因子
所以想求
也就可以求
这一题，实际上我们已经知道了最大的质数为104729，我们大概只需要算到$n=104729$就可以了（不考虑p-1的构成中有几个重复的比较大的质数）。
另外并不需要每一个都去算一遍，每隔一个恰当的间隔去算就可以了。
这里也可以简单解释一下
当我们的选取的n大于理想的刚好求出p的值时，此时$n!$必然是$p-1$的倍数，因为素数都可以同时约掉，所以无论我们的n值只要大过那个临界的n，都可以求出$gcd(a^{n!}-1,N)$
官方wp的脚本：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18from Crypto.Util.number import *
def Pollard_p_1(N):
a = 2
while True:
f = a
# precompute
for n in range(1, 80000):
f = pow(f, n, N)
for n in range(80000, 104729+1):
f = pow(f, n, N)
if n % 15 == 0: #这个就是一个间隔，没有每个值都去算gcd
d = GCD(f-1, N)
if 1 < d < N:
return d
print(a)
a += 1
n = 1592519204764870135...
print( Pollard_p_1(n) )
大概需要跑个十几分钟（由于这个N太大了，十万次左右的快速幂还是需要点时间的），能分解出来
另外的有一篇wp，方法是类似的，但是运算时间只用十几秒1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25from Crypto.Util.number import *
from Crypto.Util.number import sieve_base as primes
import gmpy2
n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
t=pow(2,2048)
e = 0x10001
k=2
for i in range(10000):
k=pow(k,primes[i],n)
if(k>t):
if(i%15==0):
if(gmpy2.gcd(k-1,n)!=1):
print(gmpy2.gcd(k-1,n))
#178449493212694205742332078583256205058672290603652616240227340638730811945224947826121772642204629335108873832781921390308501763661154638696935732709724016546955977529088135995838497476350749621442719690722226913635772410880516639651363626821442456779009699333452616953193799328647446968707045304702547915799734431818800374360377292309248361548868909066895474518333089446581763425755389837072166970684877011663234978631869703859541876049132713490090720408351108387971577438951727337962368478059295446047962510687695047494480605473377173021467764495541590394732685140829152761532035790187269724703444386838656193674253139
break
p=178449493212694205742332078583256205058672290603652616240227340638730811945224947826121772642204629335108873832781921390308501763661154638696935732709724016546955977529088135995838497476350749621442719690722226913635772410880516639651363626821442456779009699333452616953193799328647446968707045304702547915799734431818800374360377292309248361548868909066895474518333089446581763425755389837072166970684877011663234978631869703859541876049132713490090720408351108387971577438951727337962368478059295446047962510687695047494480605473377173021467764495541590394732685140829152761532035790187269724703444386838656193674253139
#p=gmpy2.gcd(k-1,n)
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
flag=long_to_bytes(m)
#flag=hex(m)[2:].decode('hex') #py2
print(flag)
这里巧妙地利用了t=pow(2,2048)，这个相当于p的最大值，$k=2^{p1·p2·p3…pk}\ mod \ n$让$k$和$t$比较，我们知道只有当$k$大于$t$时，才可能存在对应的gcd，才能求出p
同样的这也是在choice函数选择出来的素数均不同的前提才能实现