预期解法 Pollard's p-1 method

题目

from 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)] # 循环2次,出来2个数
n = p * q
c = pow(m, e, n)

其中primes是Crypto.Util.number模块中定义的前10000个质数

len(primes)=10000

for i in primes:
    print(i)

输出

2
3
5
7
11
13
...
104683
104693
104701
104707
104711
104717
104723

这些数是固定的

再看getPrime()函数，它用choice()函数从primes中随机取出一个质数，

然后累乘进n中。如果n的二进制位数大于等于2048就不乘了.

ps: 0b01二进制位数就是1，0b11的二进制位数就是2

然后判断n+1是不是质数，

如果是就返回n+1，这样getPrime()函数的功能就完成了，成功获取到质数。

ps: 如果不是呢? 好像就g了

所以出来的数 = 2 * m2 * m7 * m8 * ... + 1 (假设是这么多)

ps: m2,m7,m8 模拟的是随机数的某些数

如何解题?

数据库有差不多10000个随机数,我们把这些数的乘积设为∏

∏ = 2 * 3 * 5 * 7 * 11 * ... * 104723 * 104729

已知 n=p * q

然后假设 p = 2 * m2 * m7 * m8 + 1

那么 p - 1 = 2 * m2 * m7 * m8 *

然后 ∏ = 2 * 3 * 5 * 7 * 11 * ... * 104723 * 104729

所以,我么可以说 ∏ 一定是 p - 1 的倍数(仔细看看)

那么 令 ∏ = k * (p - 1)

引入欧拉定理: a和m互质,那么 a^φ(m) ≡ 1 % m

那么(a^φ(m)-1)是m的倍数

拓展一下，又有 (a^kφ(m) - 1) 是m的倍数，系数k为正整数

为什么是成立的?

因为: a^φ(m) ≡ 1 % m

所以: a^φ(m) - 1 = k₁m

其中: a^φ(m) = 1 + k₁m

于是:

a^φ(m) * a^φ(m) - 1 = a^2φ(m) - 1

同时:

a^φ(m) * a^φ(m) - 1

= a^φ(m) * (1 + k₁m) - 1

= a^φ(m) - 1 + a^φ(m) - 1

其中a^φ(m) - 1本来就是m的倍数,然后a^φ(m) - 1也是m的倍数

所以会有(a^2φ(m) - 1) 是m的倍数

推广到(a^kφ(m) - 1) 是m的倍数呢?

a^φ(m) * (a^φ(m) * ... * a^φ(m)) - 1

= a^φ(m) * (1 + k₁m)ⁿ - 1

= a^φ(m) * [ 1 + (k₁m)ⁿ + k₁m的相关项) ] -1

= a^φ(m) - 1 + (k₁m)ⁿ + k₁m的相关项

其中a^φ(m) - 1本来就是m的倍数,然后 (k₁m)ⁿ + k₁m的相关项 也是m的倍数

所以说 (a^kφ(m) - 1) 是m的倍数

然后,回来继续做题

∏ = k * (p - 1) = k * φ(p)

令字母a=2,2和p应该是互质的,引入欧拉定理

2^φ(p) ≡ 1 % p

所以 2^φ(p) - 1 是p的倍数

那么 2^kφ(p) - 1 也是p的倍数

所以 2^kφ(p)-1 = 2^∏-1 是p的倍数

所以 2^∏-1 = k₂p

同时 n = pq

所以2^∏-1 和 n的一定存在公约数p或者q是我们需要的数据

我们需要求出2^∏-1 和 n的公约数

2^∏-1 和 n是已知的,或者说可以直接结算出来

于是假设p=gcd(2^∏-1,n)

但是,∏是一万个数字的乘积,很大,2^∏也很大

所以我们要优化一下

因为: 2^∏-1 = k₂p ① (前面说过)

所以: 2^∏ = k₂p + 1

假设 2^∏ / n = k₃ + u

那么 2^∏ % n = 2^∏ - k3n = 2^∏ - k3pq

等式两边同时 % p，

有 2^∏ % n % p = (2^∏ - k3pq)%p

即: 2^∏ % n % p = 2^∏ % p ②

因为: 2^∏-1 = k₂p

所以: (2^∏-1)%p = 0

对于新的多项式: (2^∏ % n - 1 )%p

= (2^∏ % n % p - 1%p )%p

= (2^∏ % p - 1%p )%p

= (2^∏ - 1 )%p

= 0

所以(2^∏ % n - 1 ) 也是 p 的倍数

所以gcd(2^∏,1) == gcd(2^∏%n,1) 于是就优化了

于是,已知e,n,c, 然后p可求

然后q就出来了,然后求d,然后结果就出来了

import gmpy2
from Crypto.Util.number import isPrime, sieve_base as primes

e = 0x10001
n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
#primes为前10000个素数的列表
#计算mul_all_prime = ∏ primes
mul_all_prime = 1
for i in primes:
    mul_all_prime *= i #计算所有的素数之积
p = gmpy2.gcd(gmpy2.powmod(2,mul_all_prime,n) - 1,n)#优化的式子求p
q = n // p
phi_n=(p-1)*(q-1)
d = gmpy2.powmod(e,-1,phi_n)	#计算私钥d
m = gmpy2.powmod(c, d, n)    #解密
print(bytes.fromhex(hex(m)[2:]))

暴力的yafu

test.txt的内容是n的数值,最后要换行一下

PS E:\Crypto\yafu-1.34> .\yafu-x64.exe "factor(@)" -batchfile test.txt


=== Starting work on batchfile expression ===
factor(32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513 )
=============================================
fac: factoring 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C1241
rho: x^2 + 2, starting 1000 iterations on C1241
rho: x^2 + 1, starting 1000 iterations on C1241
pm1: starting B1 = 150K, B2 = gmp-ecm default on C1241
Total factoring time = 2.0339 seconds


***factors found***

PRP621 = 178449493212694205742332078583256205058672290603652616240227340638730811945224947826121772642204629335108873832781921390308501763661154638696935732709724016546955977529088135995838497476350749621442719690722226913635772410880516639651363626821442456779009699333452616953193799328647446968707045304702547915799734431818800374360377292309248361548868909066895474518333089446581763425755389837072166970684877011663234978631869703859541876049132713490090720408351108387971577438951727337962368478059295446047962510687695047494480605473377173021467764495541590394732685140829152761532035790187269724703444386838656193674253139
PRP621 = 184084121540115307597161367011014142898823526027674354555037785878481711602257307508985022577801782788769786800015984410443717799994642236194840684557538917849420967360121509675348296203886340264385224150964642958965438801864306187503790100281099130863977710204660546799128755418521327290719635075221585824217487386227004673527292281536221958961760681032293340099395863194031788435142296085219594866635192464353365034089592414809332183882423461536123972873871477755949082223830049594561329457349537703926325152949582123419049073013144325689632055433283354999265193117288252918515308767016885678802217366700376654365502867

ans = 1

eof; done processing batchfile

这样就求得了p,q

于是,已知e,n,c,p,q

然后就不多说了

import gmpy2
p=178449493212694205742332078583256205058672290603652616240227340638730811945224947826121772642204629335108873832781921390308501763661154638696935732709724016546955977529088135995838497476350749621442719690722226913635772410880516639651363626821442456779009699333452616953193799328647446968707045304702547915799734431818800374360377292309248361548868909066895474518333089446581763425755389837072166970684877011663234978631869703859541876049132713490090720408351108387971577438951727337962368478059295446047962510687695047494480605473377173021467764495541590394732685140829152761532035790187269724703444386838656193674253139
q=184084121540115307597161367011014142898823526027674354555037785878481711602257307508985022577801782788769786800015984410443717799994642236194840684557538917849420967360121509675348296203886340264385224150964642958965438801864306187503790100281099130863977710204660546799128755418521327290719635075221585824217487386227004673527292281536221958961760681032293340099395863194031788435142296085219594866635192464353365034089592414809332183882423461536123972873871477755949082223830049594561329457349537703926325152949582123419049073013144325689632055433283354999265193117288252918515308767016885678802217366700376654365502867
e=0x10001
c=26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
n=p*q
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
m=pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))

x % k₁a % a == x % a (我么要证明的等式,k₁a是a的倍数)

令x = k₁a * k₂ + m (一定存在这样的等式,k2>=0,且m<k₁a)

那么

x % k₁a % a

= ( k₁a * k₂ + m) % k₁a % a

= m % a

x % a

= (k₁a * k₂ + m)%a

= a % m

所以x % k₁a % a == x % a