p q 选取不当

适用情况:

ppqq 选取不当时,例如 qq 选取了 pptt 倍的后几个素数,甚至 qq 就是 pp 的后几个素数,可以在较短时间内分解 nn

原理

不妨设:

q=tp+kq = tp + k

那么:

n=pq=p(tp+k)=tp2+pkn = pq = p(tp + k) = tp^2 + pk

即:

tp2+kpn=0tp^2 + kp - n = 0

则:

p=k+k2+4tn2tp = \frac{-k + \sqrt{k^2 + 4tn}}{2t}

由于 pp 是整数,所以 k2+4tn\sqrt{k^2 + 4tn} 是整数,即 k2+4tnk^2 + 4tn 开方后是整数。

寻找到符合条件的 kk,那么:

p=k+k2+4tn2tq=tp+k\begin{aligned} p & = \frac{-k + \sqrt{k^2 + 4tn}}{2t} \\ q & = tp + k \end{aligned}

如果 pq==npq == n,那么已成功分解。否则继续寻找 kk

代码

大数精确开方需要用到 gmpy2 库中的 iroot

1
2
3
4
5
6
7
8
9
10
11
12
def factor():
n_4t = n*4*t
for k in range(100000):
delta = k**2 + n_4t
if gmpy2.iroot(delta, 2)[1]:
print 'k =', k
p = (-k + gmpy2.iroot(delta, 2)[0]) / (2*t)
q = t*p + k
if p*q == n:
print 'p =', p
print 'q =', q
return p, q

例子

2018 柏鹭杯:simple RSA

题目:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from flag import flag
from Crypto.Util.number import *
import random
def next_prime(n):
num = n + 1
while True:
if isPrime(num):
return num
num += 1
p = random.randint(1<<3071,1<<3072)
p = next_prime(p)
q = next_prime(p*10)

N = p*q
e = 65537
c = pow(bytes_to_long(flag),e,N)
print N#247157208312655169175097941364280738161257111976460225724719907081110265510517450181419502794457206227461600647913804553439171851865273449559295717229024951735351965745325255241561391509015823198303928588939850683031392486366218841593013566932215141428061199015117025898704736991786081007198271335363347647516874679013119543722851148642512142186199102168074461255284546705588056994149297326331376082141145137980534967406372164077378650248545875219877244489040506317293082270408705203779841533080244655519849164084793887915122847280359452339072498784918027724621588636245527176960457003310429876627882173282069366037431766179722648353575718417895929519296072344510519198593252963273537190447967056699273665756186541135880261688073100218736960343554003491651502334045257343825793705434779809139021362473746587814528428007114308414633338220797896397738142172067161950968365434368211510967904096253326804711795198906393597153228365711080786247894858858419136771806150038968465644512536135428099037524022644906606239281576512245480765249280626544900781649017542649977530381598608436485399917576052247750573936190833224008929770080605906041913084656134359260509037195783858871830359437278131656343708211575987756873026171223324073191307367943843353573378426157170935012284820053625264544030714057464690450568057598110227083895395913850243271935830358181622027323185508807486853971929523201869477689585619024238113916052252320578711256593537267591407960305853736136636628575478996733430026632486500743561965770413140633948002705696925426367918545515713035754606128166993229587155817506068035187995926746472892280477401942441831391756895131543049750847590716935278314226902082626392655666615086297442052602217416486188297831289978272258543231414975069191549588547253936829655332588805672513945883351937495650167502066292697223592894483418517613405613285519159
print c#152721025887735064764471379084548069204525956728140596238274397757947415316727016281416993518884790524343567541799262176820909148208728616947040227306302164641933331109468512979068186962047716308015535717796123080303496277784765187481185086876434873226524784636408104495312136956587251145463229424950634548624036265557622592089071331292811066840281494102799063634204855779210798330603868025111521826209601342683209160845433746624786171189961029265101816540639855230011618388675527443511618729301028631422873421421991470450059414988968787693753741941765791793672069240992955177930884210118700416564364129283739917229225845073750451244070534919112957275948312337882004219145847493047815403283126471638320784008475284616178697542301935170768573588093196019976675846311280356987370969400610196847990069257614148181804915868273001764028563852238142447411811579695265293746037324400494199877368049162903819737962946786971556872009326814914717430484711885484790156341127433550909206551293806568904858726942820132521566970376839336895645431303013575622422180179687172859250687080526393904583834607514619581478966664406178290247731116920836372943133394640322159512633671870473674514938423231596849301615200001553851411828993918474534316510609878376462094608058640335426907349648369552864820322464995077358198844334320833893207364879282292959161203675080110629771237503657412087961891443054530286088807186134851425688726147108076040204500951624929585070273336203814962656253259257806100191430918121713005141607192112560560371475173081441671613602480052062955279287813475764285469835557663176529059039540417149792518941598550609678298901186032272305421028365295602810159191055078633881059737011784127699357480578433240110432805495328517379885306237631225477566136721077348329866885731002878563684349453668924250445128775992616650275173644658245397235667490402628

由题目可知,pp 是一个 3000 多位的素数,qq 是 10 倍 pp 的下一个素数。

直接可由上方法分解 n:

1
2
3
k = 1171
p = 4971490805710648894784063900603982138103528416416093113682856149525895474391965093292856360186270533203485404384261736770807923420477678768335595268260058770929420214670794184479653642688593773001265441972139034999789321709099375988424776953616924996952770970955016095518058970453801153351600603001621188113472370286189729979231943525793160692844078376540082324198649179890017101800683049489232021392715915700831833371902425005874555370189042455321691195416425399507551235346773377429357933240695935997956969841660473107352934178051894901298644110556291216221039424250078546978571086275993790666829060240691673857284132895978717935677825502362997789971900863003499701755174512295162461514926135376073693593713246781021035797102243028802222257489266812730745381990847604727619717567202686948267842932198278066304365500430012440700948799107940169074390644763691400614036677335457180241108468029814414775113509028739480597728319
q = 49714908057106488947840639006039821381035284164160931136828561495258954743919650932928563601862705332034854043842617367708079234204776787683355952682600587709294202146707941844796536426885937730012654419721390349997893217090993759884247769536169249969527709709550160955180589704538011533516006030016211881134723702861897299792319435257931606928440783765400823241986491798900171018006830494892320213927159157008318333719024250058745553701890424553216911954164253995075512353467733774293579332406959359979569698416604731073529341780518949012986441105562912162210394242500785469785710862759937906668290602406916738572841328959787179356778255023629977899719008630034997017551745122951624615149261353760736935937132467810210357971022430288022222574892668127307453819908476047276197175672026869482678429321982780663043655004300124407009487991079401690743906447636914006140366773354571802411084680298144147751135090287394805977284361

得到 flag:ISEC{simp13_crypt0}

模不互素

适用情况:
当存在两个公钥的 nn 不互素时,显然可以直接对这两个数求最大公因数,直接获得 ppqq

代码

1
2
3
4
5
6
7
8
9
def factor():
p = gmpy2.gcd(n1, n2)
q1 = n1 / p
q2 = n2 / p
assert p*q1 == n1
assert p*q2 == n2
print 'p =', p
print 'q1 =', q1
print 'q2 =', q2

例子

SCTF:RSA2

pcap 包中含有 n 和 e 的消息。其中有两个 n:

1
2
n1 = 20823369114556260762913588844471869725762985812215987993867783630051420241057912385055482788016327978468318067078233844052599750813155644341123314882762057524098732961382833215291266591824632392867716174967906544356144072051132659339140155889569810885013851467056048003672165059640408394953573072431523556848077958005971533618912219793914524077919058591586451716113637770245067687598931071827344740936982776112986104051191922613616045102859044234789636058568396611030966639561922036712001911238552391625658741659644888069244729729297927279384318252191421446283531524990762609975988147922688946591302181753813360518031
n2 = 19083821613736429958432024980074405375408953269276839696319265596855426189256865650651460460079819368923576109723079906759410116999053050999183058013281152153221170931725172009360565530214701693693990313074253430870625982998637645030077199119183041314493288940590060575521928665131467548955951797198132001987298869492894105525970519287000775477095816742582753228905458466705932162641076343490086247969277673809512472546919489077884464190676638450684714880196854445469562733561723325588433285405495368807600668761929378526978417102735864613562148766250350460118131749533517869691858933617013731291337496943174343464943

发现模数不互素:

1
print gmpy2.gcd(n1, n2)
1
122281872221091773923842091258531471948886120336284482555605167683829690073110898673260712865021244633908982705290201598907538975692920305239961645109897081011524485706755794882283892011824006117276162119331970728229108731696164377808170099285659797066904706924125871571157672409051718751812724929680249712137

那么可以直接由上述方法解密,得到 flag:sH1R3_PRlME_1N_rsA_iS_4ulnEra5le

多因子

适用情况:
nn 是由两个以上的素数相乘得到,会有些特殊。

原理

如果选取两个以上的素数,记为 p1,p2,p3...p_1, p_2, p_3...,它们相乘得到 nn,那么:

φ(n)=(p11)(p21)(p31)...\varphi (n) = (p_1 - 1)(p_2 - 1)(p_3 - 1)...

公钥、私钥、加解密都与一般 RSA 相同。

选取多因子,虽然会减少生成密钥的时间,但同样也更容易被破解。

例子

2018 picoctf:Super Safe RSA 3

每次 nc 连接可以获得不同的 ccnnee

例如一次连接中:

1
2
3
c: 236434294562852381842307785543347919217676481857496426677823656807506421759144963030501769311835411762026907848397529006599563288690089282702818198177368099766733506715831007535690273535741585530721389732916130816863687011754081219886436105201386044253051204304648556642980507914261370486658516914518976
n: 607623369882890591735782141073772197087735470451907161056918749085797298608061697204877318116530061370098150393008398852309935398612508655661345572182951783541048774456584255774063319762705994011630127672153887410829669163686086432067585460780467260542209687551454132414709631582428726568293866157915237
e: 65537

首先用 yafu 经过多次分解直到所有因子都为素数,可以得到 32 个素数因子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2209835647
3279221983
2203115203
3083863231
2624125561
4051923611
3870883097
3919135769
3746033843
2349626557
2911452569
2280078727
3772965367
2486744167
3816147749
2613884417
2657517431
2808514571
3516405091
3393739981
2965911017
2282964227
2794765357
2162896789
4177000211
2804308609
2549752151
2206071653
2336473199
2647948099
3656705023
2574736709

然后就可以直接求解:

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
import gmpy2

c = 236434294562852381842307785543347919217676481857496426677823656807506421759144963030501769311835411762026907848397529006599563288690089282702818198177368099766733506715831007535690273535741585530721389732916130816863687011754081219886436105201386044253051204304648556642980507914261370486658516914518976
n = 607623369882890591735782141073772197087735470451907161056918749085797298608061697204877318116530061370098150393008398852309935398612508655661345572182951783541048774456584255774063319762705994011630127672153887410829669163686086432067585460780467260542209687551454132414709631582428726568293866157915237
e = 65537
factors = [2209835647, 3279221983, 2203115203, 3083863231, 2624125561, 4051923611, 3870883097, 3919135769, 3746033843, 2349626557, 2911452569, 2280078727, 3772965367, 2486744167, 3816147749, 2613884417, 2657517431, 2808514571, 3516405091, 3393739981, 2965911017, 2282964227, 2794765357, 2162896789, 4177000211, 2804308609, 2549752151, 2206071653, 2336473199, 2647948099, 3656705023, 2574736709]
phi = 1
for x in factors:
phi *= (x-1)
d = gmpy2.invert(e, phi)
print long_to_bytes(pow(c, d, n))

得到 flag:picoCTF{p_&_q_n0_r_$_t!!_5146060}

共模攻击

适用情况:

当两个用户使用相同的模数、不同的私钥,加密同一明文消息时,即存在共模攻击。

原理

两用户私钥不同而模数相同,则两用户公钥必定不同。

设两用户的公钥分别为 e1e_1e2e_2,由于选取的 eeφ(n)\varphi (n) 互质,因此 e1e_1e2e_2 互质。明文为 mm,密文分别为:

c1=me1modnc2=me2modnc_1 = m^{e_1} \bmod n \\ c_2 = m^{e_2} \bmod n \\

当攻击者截获 c1c_1c2c_2 后,就可以恢复出明文。

用扩展欧几里得算法可求出 re1+se2=1modnre_1 + se_2 = 1 \bmod n 的两个整数 rrss,由此可得:

c1rc2s=mre1mse2modn=m(re1+se2)modn=(mmodn)(re1+se2)modn=(mmodn)1modnmodn=mmodn\begin{aligned} c_{1}^{r}c_{2}^{s} &= m^{re_1}m^{se_2}\bmod n \\ &= m^{(re_1+se_2)} \bmod n \\ &= (m\bmod n)^{(re_1+se_2)} \bmod n\\ &= (m\bmod n)^{1 \bmod n} \bmod n\\ &= m \bmod n \end{aligned}

代码

1
2
3
4
5
6
7
8
9
10
11
def get_m(c1, c2, e1, e2, n):
gcd, r, s = gmpy2.gcdext(e1, e2)
assert gmpy2.gcd(e1, e2) == 1
if r < 0:
r = -r
c1 = gmpy2.invert(c1, n)
if s < 0:
s = -s
c2 = gmpy2.invert(c2, n)
m = pow(c1, r, n) * pow(c2, s, n) % n
print 'm =', m

例子

XMan 一期夏令营课堂练习

1
2
3
4
{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,773}
{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,839}
message1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
message2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535

可以发现两个公钥模数 nn 相同,由上述方法可以得到 mm

1
m = 1021089710312311910410111011910111610410511010710511610511511211111511510598108101125

直接 long_to_bytes 得到的都是乱码,这里应该不是通常的将明文逐个字符转 16 进制 ascii 码再字符串相加最后转 10 进制。通过观察应该是每两个或三个数字是 10 进制的 ascii 码。所以:

1
2
3
4
5
6
7
8
9
10
11
i = 0
flag = ""
m = str(m)
while i < len(m):
if m[i] == '1':
flag += chr(int(m[i: i+3]))
i += 3
else:
flag += chr(int(m[i: i+2]))
i += 2
print flag

得到 flag:flag{whenwethinkitispossible}

p-1 光滑

原理

光滑数(Smooth Number)指可以分解为小素数乘积的正整数。

ppNN 的因数,并且 p1p-1 是光滑数,可能可以使用 Pollard’s p − 1 算法来分解 NN

首先根据费马小定理:

如果 pp 是一个质数,而整数 aa 不是 pp 的倍数,则有 ap11modpa^{p-1} \equiv 1 \bmod p

则:

at(p1)1t1modpa^{t(p-1)} \equiv 1^t \equiv 1 \bmod p

可改为等式:

at(p1)1=kpa^{t(p-1)} - 1 = k * p

at(p1)1a^{t(p-1)} - 1pp 的倍数 。

然后根据 Pollard’s p - 1 算法:

如果 p1p-1 是一些很小质数的乘积,那么 n!n! 就能被 p1p-1 整除。即 n!=t(p1)n! = t(p-1)

对于每一个 n=2,3,4,...n = 2, 3, 4, ...,任意选择一个底数 aa(事实上,可以简单地选择为 2),并计算:

gcd(an!1,N)gcd(a^{n!} - 1, N)

如果结果不为 1 或 NN,那么就已成功分解 NN

但当 nn 较大时,直接计算 n!n! 将会很消耗资源。在遍历 nn 时,可以简化运算。

因为:

an!modN=(amodN)n!modNa^{n!} \bmod N = (a \bmod N) ^ {n!} \bmod N

所以:

an!modN={(amodN)2modNn = 2(a(n1)!modN)nmodNn >= 3a^{n!} \bmod N = \begin{cases} (a \bmod N) ^ 2 \bmod N & \text{n = 2} \\ (a^{(n-1)!} \bmod N) ^ n \bmod N & \text{n >= 3} \end{cases}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2

def Pollards_p_1(N):
a = 2
n = 2
while True:
a = pow(a, n, N)
res = gmpy2.gcd(a-1, N)
if res != 1 and res != N:
print 'n =', n
print 'p =', res
return res
n += 1

例子

[NCTF2019] childRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)]
n = p * q
c = pow(m, e, n)
# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
# c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

可以发现 ppqq 是由前 10000 个随机的许多小质数乘积加 1 得到, 即 p1p-1 为许多小质数的乘积。那么可以利用 Pollard’s p − 1 算法来分解 N。

1
2
3
4
5
6
7
8
9
10
e = 0x10001
n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

p = pollards_p_1(n)
q = n // p
assert p*q == n
d = gmpy2.invert(e, (p-1)*(q-1))
m = pow(c, d, n)
print long_to_bytes(m)

参考文章

https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_module_attack/

https://frenchfries.net/paul/factoring/theory/pollard.p-1.html