RSA入门

RSA学习过程，对常见题型进行了整合

发表于2023年7月6日。于2024年7月15日进行更新，把以前三篇有关RSA的内容整合成一篇，添加了一些题目，并且去除了冗余的内容

一、RSA算法原理简介

1.密钥的产生

1. 选择两个保密的大素数$p$和$q$

2. 计算$n = p \times q,\phi(n) = (p-1)(q-1)$，其中$\phi(n)$是n的欧拉函数值

3. 选一整数$e$，满足$1 < e < \phi(n)$，且$gcd(\phi(n),e) = 1$

4. 计算$d$，满足$ed \equiv 1 \mod \phi(n)$。即$d$是e在模$\phi(n)$下的乘法逆元，因为$e$和$\phi(n)$互素，所以$d$必定存在

5. 以$(e,n)$为公开钥，$(d,n)$为秘密钥

2.加密

加密时，先把明文比特串分组，使得每个分组对应的十进制数$<n$，即分组长度小于$log_2n$。如然后对每个明文分组$m$，作加密运算:
$$
c \equiv m^e \mod n
$$

3.解密

对密文分组的解密运算:
$$
m \equiv c ^d \mod n
$$

4.证明解密的正确性

情况1:$m,n$互素。由欧拉定理:
$$
c^d \equiv m^{ed} \equiv m^{k\phi(n)+1} \equiv m\times (m^{\phi(n)})^k \equiv m \mod n
$$
即$c^d \equiv m \mod n$

情况2:$m,n$不互素。

因为$m,n$不互素，注意到$n = pq$，所以此时$m$是$p$或者$q$的倍数。假设$m$是$p$的倍数，即$m = tp$

此时$gcd(m,q) = 1$，否则$m$也是$q$的倍数，从而$m$是n的倍数，这与明文分组$m < n$矛盾。所以不可能

由$gcd(m,q) = 1$得
$$
m ^{\phi(q)} \equiv 1 \mod q
$$
所以
$$
m^{k\phi(p)\phi(q)} \equiv (m^{\phi(q)})^{k\phi(p)} \equiv 1\mod q
$$
即$m^{k\phi(n)} \equiv 1 \mod q$，也就是$m^{k\phi(n)} = kq + 1$

两边同时乘上$m = tp$，得$m^{k\phi(n)+1} \equiv ktpq + m = m+tkn$

也就是$m^{k\phi(n)+1} \equiv m \mod n$

二、基础工具

1.yafu

使用方法:进入yafu所在的文件夹，输入命令yafu-x64 factor(n)

2.网站分解

http://www.factordb.com/index.php

三、密钥生成和读取

密钥生成

通过Crypto.PublicKey.RSA中的construct函数可以生成公钥和私钥。

对于生成公钥，需要两个参数$n,e$，生成私钥需要$n,e,d$

需要配合exprot_Key使用

生成公钥

from Crypto.Util.number import *
from Crypto.PublicKey import RSA

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537

a = (n,e)
publickey = RSA.construct(a)
with open("publickey.pem","wb") as f:
    f.write(publickey.export_key())

生成私钥

必需参数是$n,e,d$，可添参数是$p,q$

from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import gmpy2

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
d = gmpy2.invert(e,(p-1)*(q-1))

a = (n,e)
b = (n,e,int(d))

publickey = RSA.construct(a)
privatekey = RSA.construct(b)

with open("publickey.pem","wb") as f:
    f.write(publickey.export_key())

with open("privatekey.pem","wb") as f2:
    f2.write(privatekey.export_key())

读取密钥

from Crypto.PublicKey import RSA

key = RSA.import_Key(文件)

key中有p,q,n,e,d五个属性，一般题目也就给了公钥，所以只有n,e是能读取的

例题1 泄露私钥

task

from Crypto.PublicKey import RSA
import libnum
import gmpy2
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
m = libnum.s2n(flag)

p = libnum.generate_prime(1024)
q = gmpy2.next_prime(p)
n = p * q
e = 65537
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = libnum.s2n(flag)
c = pow(m, e, n)
#
c1 = libnum.n2s(int(c))

with open("flag.pem", "wb") as f:
    f.write(c1)
# 生成公钥
rsa_components = (int(n), int(e), int(d))
keypair = RSA.construct(rsa_components)
with open('pubckey.pem', 'wb') as f:
    f.write(keypair.exportKey())

题目中把d也传入数据了，直接读取d解密即可

from Crypto.PublicKey import RSA
from Crypto.Util.number import *

c = bytes_to_long(open("flag.pem","rb").read())
key = RSA.import_key(open("publickey.pem","rb").read())
e = key.e
n = key.n
d = key.d

print(long_to_bytes(pow(c,d,n)))

# flag{947ce8a3-40ee-46c0-a00e-0026e583f8da}

例题2 OAEP

task.py

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import libnum
import gmpy2
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
flag = flag.encode()

p = libnum.generate_prime(1024)
q = gmpy2.next_prime(p)
n = p * q
e = 65537
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)

#
# 生成公钥
rsa_components = (int(n), int(e), int(d))
keypair = RSA.construct(rsa_components)
with open('prikey2.pem', 'wb') as f:
    f.write(keypair.exportKey())

rsa_components = (int(n), e,)
arsa = RSA.construct(rsa_components)
rsakey = RSA.importKey(arsa.exportKey())
rsakey = PKCS1_OAEP.new(rsakey)
c = rsakey.encrypt(flag)
with open("flag2.pem", "wb") as f:
    f.write(c)

了解了一下函数

PKCS1_OAEP.new(key, hashAlgo=None, mgfunc=None, label=b'')

参数含义如下：

key:RSA密钥，可以是公钥或私钥；

hashAlgo:哈希算法，默认为SHA-1；

myfunc:消息生成函数，默认为MGF1；

label:可选的附加数据，默认为空。

key是必需参数

使用PKCS1_OAEP.new初始化后，可以调用其实例方法encrypt和decrypt实现RSA-OAEP算法的加密和解密操作

exp.py

from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey.RSA import *

c = open("flag2.pem","rb").read()
key = import_key(open("prikey2.pem","rb").read())

newkey = PKCS1_OAEP.new(key)
m = newkey.decrypt(c)
print(m).

#flag{04bbaad0-9241-42a4-9fd4-7d6e0d8bc5f1}

攻防世界——cr4-poor-rsa

题目给了个无后缀的文件，拖到010发现里面有藏两个文件，于是把后缀改成了zip

打开后得到两个文件，分别是key.pub和flag.b64

key.pub

-----BEGIN PUBLIC KEY-----
ME0wDQYJKoZIhvcNAQEBBQADPAAwOQIyUqmeJJ7nzzwMv5Y6AJZhdyvJzfbh4/v8
bkSgel4PiURXqfgcOuEyrFaD01soulwyQkMCAwEAAQ==
-----END PUBLIC KEY-----

flag.b64

Ni45iH4UnXSttNuf0Oy80+G5J7tm8sBJuDNN7qfTIdEKJow4siF2cpSbP/qIWDjSi+w=

先试着读取公钥，发现n可以分解，于是就按常规流程做了

exp.py

import base64
from Crypto.PublicKey.RSA import *
from Crypto.Util.number import *
import gmpy2

c = base64.b64decode(open("flag.b64","rb").read())
c = bytes_to_long(c)
key = import_key(open("key.pub","rb").read())

p = 863653476616376575308866344984576466644942572246900013156919
q = 965445304326998194798282228842484732438457170595999523426901
n = p*q
e = 65537
d = gmpy2.invert(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

#XCTF{SMALL_PRIMES_ARE_BAD}

四、共模攻击

共模攻击：

在对同一明文的加密过程中使用相同的模数n，对同一明文，用不同的密钥e（两个密钥是互素的）进行加密

结果是得到两个不同的c

原理：
$$
c_1 \equiv m^{e_1} \mod n\\
c_2 \equiv m^{e_2} \mod n
$$
通过欧几里得扩展算法我们能得到$x,y$满足$e_1x+e_2y = 1$
$$
\therefore c_1^x \times c_2^y \equiv m^{e_1x + e_2y} \equiv m \mod n
$$

例题1

task.py

import libnum
import gmpy2
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)
p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
n1 = p * q
n2 = p * q
e1 = 2333
e2 = 23333
m = libnum.s2n(flag)
c1 = pow(m, e1, n1)
c2 = pow(m, e2, n2)
print("n1=", n1)
print("n2=", n2)
print("e1=", e1)
print("e2=", e2)
print("c1=", c1)
print("c2=", c2)

#n1 = 12023886737570921683430494088148056717464277480371493354080633886982376602419433228186314817561301719123238737516332784081267153425832030515178119047675516911098595227477026283152544604891747727831780305507300318674027062554009254728767714650522432836286987070040177863862115871377017779058128916872854380528430193235920536818893053943407063308419618772087299760070707222914961338101044775521373972076936552277418325268112523349134412986872504187930360266568935217397303420305220796347316727211659529079762169876950534044014924448371804442314283893083178368082712851107281302456671010073505430574108861981588149293779
n2 = 12023886737570921683430494088148056717464277480371493354080633886982376602419433228186314817561301719123238737516332784081267153425832030515178119047675516911098595227477026283152544604891747727831780305507300318674027062554009254728767714650522432836286987070040177863862115871377017779058128916872854380528430193235920536818893053943407063308419618772087299760070707222914961338101044775521373972076936552277418325268112523349134412986872504187930360266568935217397303420305220796347316727211659529079762169876950534044014924448371804442314283893083178368082712851107281302456671010073505430574108861981588149293779
e1 = 2333
e2 = 23333
c1 = 1316116662134770690879814362103839780623420120527248536043840592146479052480574077985474161623763978563721124073172820410730492348846200098142706235343164470686127445583938273863894304189618247054649514955176136464273395879832878841555224421879457659795562326746943199675846414637238040550327393009642569894024250271081839428945999237716296592560124669418322569188493036148885333003876760965512925618500360394774816066758106739359762817644284120811162065280330204951295150904138010974815308787047834776406610525102814356091515999954110712767658162496023213125548829820563945272374105274832862682574678195529192009516
c2 =6485241395763328009719746130709898541269729483150505308808259329749145687803066648274311801821624527910483266170666538736992203392620205417714840881369386852010836477498279266591695876758050686740322941452286584178315830797555697887040771666991377055060541491757349967338300117181859105577325308779010792879713808168285776399372981366988860647334022480774711504685240194804912592209253106123423232743785805952113875347267336118332317990496240807273787216894980604742600774512296661048914646776553393778079057461747246478299158814839681875752645552215714984659603917168300453505504140987829883479097467840565806608012

m = pow(c1,x,n) * pow(c2,y,n) % n

exp.py

from Crypto.Util.number import *
import gmpy2

n = 12023886737570921683430494088148056717464277480371493354080633886982376602419433228186314817561301719123238737516332784081267153425832030515178119047675516911098595227477026283152544604891747727831780305507300318674027062554009254728767714650522432836286987070040177863862115871377017779058128916872854380528430193235920536818893053943407063308419618772087299760070707222914961338101044775521373972076936552277418325268112523349134412986872504187930360266568935217397303420305220796347316727211659529079762169876950534044014924448371804442314283893083178368082712851107281302456671010073505430574108861981588149293779
e1 = 2333
e2 = 23333
c1 =1316116662134770690879814362103839780623420120527248536043840592146479052480574077985474161623763978563721124073172820410730492348846200098142706235343164470686127445583938273863894304189618247054649514955176136464273395879832878841555224421879457659795562326746943199675846414637238040550327393009642569894024250271081839428945999237716296592560124669418322569188493036148885333003876760965512925618500360394774816066758106739359762817644284120811162065280330204951295150904138010974815308787047834776406610525102814356091515999954110712767658162496023213125548829820563945272374105274832862682574678195529192009516
c2 =6485241395763328009719746130709898541269729483150505308808259329749145687803066648274311801821624527910483266170666538736992203392620205417714840881369386852010836477498279266591695876758050686740322941452286584178315830797555697887040771666991377055060541491757349967338300117181859105577325308779010792879713808168285776399372981366988860647334022480774711504685240194804912592209253106123423232743785805952113875347267336118332317990496240807273787216894980604742600774512296661048914646776553393778079057461747246478299158814839681875752645552215714984659603917168300453505504140987829883479097467840565806608012

s,x,y = gmpy2.gcdext(e1,e2)
m = (pow(c1,x,n)*pow(c2,y,n))%n
print(long_to_bytes(m))

#flag{01d80670b01b654fe4831a3e81870734}

gcdext(e1,e2)返回3个元素

第一个元素是$Boolean$类型的数据，判断存不存在$x,y$使得$e_1x+e_2y = 1$

返回得第二个和第三个元素是$x,y$

例题2

这个例题的情况是$gcd(e_1,e_2)\ne 1$

task.py

from Crypto.Util.number import *
from random import getrandbits
import gmpy2
import uuid

while 1:
    flag = "flag{" + str(uuid.uuid4()) + "}"
    m = bytes_to_long(flag.encode())
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e1 = getrandbits(10)
    e2 = getrandbits(10)
    if e1 != e2 and gmpy2.gcd(e1,e2) != 1:
        break
    
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)
print("e1 =", e1)
print("e2 =", e2)
print("n =", n)
print("c1 =", c1)
print("c2 =", c2)

这种题目我们还是正常推导，设$t = gcd(e_1,e_2)$，通过扩展欧几里得算法，有
$$
e_1x + e_2y = t
$$
则
$$
c_1^x \times c_2^y \equiv m^{e_1x+e_2y} \equiv m^t \mod n
$$
根据t的大小再进行不同的处理，比如t=3，那么可以试着用低加密指数的思路进行处理。

如果t比较大，那么可以再次当作一次RSA进行求解。

本例t = 2，直接开根就行

exp.py

from Crypto.Util.number import *
import gmpy2

e1 = 578
e2 = 392
n = 21792499489446653209359648268647408248484077502636323240941263512972521642966446318685589383376089358615828479732487823375467576966410911798574546152698546172208644494120844910028661801069139412883722092087841337354582470102991346201250757430966278341015814968426027288609918021263801588485143246793300627932938615206724828284751003817198828431954277335825721403220979778254648036632075276172476930299390290573025768956364488376300510746252434716167769851984446036711610150897081622960442923737196929758209816434803424884970510663599653463189492521652184966337230394292288573277654840483815385709060428243829968709733
c1 = 1295899105546936416711955776176786556954959764395004520666273768220642845167647126115394711085928049897436984534359683209799926877399786065216458011526399070534983898250382591372240231327810785046739203554803467534631081973525005181861203752320250219830020069663762443152692331055158533035896110900630817135766754326408199206651276750278716441636585609321276880631239079781048185864263400051324827820941692502756433463495216541801444097560942509859140724554853380906157874504969878938634453309110942314571026225239704634981956565844426060346340677136929914119932647724346392582368980017754022031748246759437397697793
c2 = 6100251841868768392049795926373721745054594119167283623934416754665831830741776139556785242664295441966913393337547165974512844660057299278828165715333417692799802949938590574117892067491764731548261988101287152727657523152041485072722017224763458684855801781252103126948392647769522681887089175624603484575515518773338807587100984947122699045372679023951413797420560947466351031076552444459222063798664625809884979352261000568340687804017980769948161583294444251776973765636460565633962599948356942127522339715718463747197473475842874431177106692482361060930677857750098337273277996678196019443721319477484374253966

t = gmpy2.gcd(e1,e2)
s,x,y = gmpy2.gcdext(e1,e2)
m = gmpy2.iroot((pow(c1,x,n)*pow(c2,y,n))%n,t)
print(long_to_bytes(m[0]))

五、低加密指数攻击

原理：

加密指数e很小一般是3，导致出现两个情况

第一种情况：$m^e < n $则$c \equiv m^{e} \mod n \longrightarrow c = m^e$这种情况下对c开e次方就可以得到m的值

第二种情况：$m^e > n$(略大一点点)，则$m^e = k*n + c$这种情况需要爆破k

例题

task.py

import libnum
import gmpy2
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)
print(gmpy2.bit_length(m ** 3))
while True:
    p = libnum.generate_prime(504)
    q = libnum.generate_prime(504)
    n = p * q
    phi_n = (p - 1) * (q - 1)
    e = 3
    if gmpy2.gcd(e, phi_n) == 1 and  phi_n%e !=0:
        break

c = pow(m, e, n)
print("n=", n)
print("e=", e)
print("c=", c)

#c= 17567615026662297423639652671128685098763112348521263232850922784902991105809108670614334001294254886850775709702759646022208238160649099765454315761185950859820327234504422026634432251632399712621439201146
3091635444512796333373451321795475333496092463760390199602320265733668648810943598505902205569125
n = 1101676297168703265566511587913652821222614528632844563918598090813090976948138058144049294690727841463413972173051671908835164088465174349647584948964206244648736138253802417241570633968307801570794459668533128958442296813160786428069813867034205462528763830205245218089660432399549540588101288362866463
e = 3

exp.py

from Crypto.Util.number import *
import gmpy2

n = 1101676297168703265566511587913652821222614528632844563918598090813090976948138058144049294690727841463413972173051671908835164088465174349647584948964206244648736138253802417241570633968307801570794459668533128958442296813160786428069813867034205462528763830205245218089660432399549540588101288362866463
e = 3
c = 175676150266622974236396526711286850987631123485212632328509227849029911058091086706143340012942548868507757097027596460222082381606490997654543157611859508598203272345044220266344322516323997126214392011463091635444512796333373451321795475333496092463760390199602320265733668648810943598505902205569125
k = 0

t = gmpy2.iroot(c,e)
if t[1]:
    print(long_to_bytes(t[0]))
else:
    while 1:
        m = gmpy2.iroot(k*n+c,e)
        if m[1]:
            print(long_to_bytes(m[0]))
            break
        else:
            k += 1

六、广播攻击

原理：

明文$m$用相同的密钥$e$和不同的模$n$进行加密

一般会得到几组不同的$n$和$c$

第一种情况 多组n之间可能存在公因数

例题 BUUCTF-RSA5

task.txt

m = xxxxxxxx
e = 65537
========== n c ==========
n = 20474918894051778533305262345601880928088284471121823754049725354072477155873778848055073843345820697886641086842612486541250183965966001591342031562953561793332341641334302847996108417466360688139866505179689516589305636902137210185624650854906780037204412206309949199080005576922775773722438863762117750429327585792093447423980002401200613302943834212820909269713876683465817369158585822294675056978970612202885426436071950214538262921077409076160417436699836138801162621314845608796870206834704116707763169847387223307828908570944984416973019427529790029089766264949078038669523465243837675263858062854739083634207
c = 974463908243330865728978769213595400782053398596897741316275722596415018912929508637393850919224969271766388710025195039896961956062895570062146947736340342927974992616678893372744261954172873490878805483241196345881721164078651156067119957816422768524442025688079462656755605982104174001635345874022133045402344010045961111720151990412034477755851802769069309069018738541854130183692204758761427121279982002993939745343695671900015296790637464880337375511536424796890996526681200633086841036320395847725935744757993013352804650575068136129295591306569213300156333650910795946800820067494143364885842896291126137320

n = 20918819960648891349438263046954902210959146407860980742165930253781318759285692492511475263234242002509419079545644051755251311392635763412553499744506421566074721268822337321637265942226790343839856182100575539845358877493718334237585821263388181126545189723429262149630651289446553402190531135520836104217160268349688525168375213462570213612845898989694324269410202496871688649978370284661017399056903931840656757330859626183773396574056413017367606446540199973155630466239453637232936904063706551160650295031273385619470740593510267285957905801566362502262757750629162937373721291789527659531499435235261620309759
c = 15819636201971185538694880505120469332582151856714070824521803121848292387556864177196229718923770810072104155432038682511434979353089791861087415144087855679134383396897817458726543883093567600325204596156649305930352575274039425470836355002691145864435755333821133969266951545158052745938252574301327696822347115053614052423028835532509220641378760800693351542633860702225772638930501021571415907348128269681224178300248272689705308911282208685459668200507057183420662959113956077584781737983254788703048275698921427029884282557468334399677849962342196140864403989162117738206246183665814938783122909930082802031855

n = 25033254625906757272369609119214202033162128625171246436639570615263949157363273213121556825878737923265290579551873824374870957467163989542063489416636713654642486717219231225074115269684119428086352535471683359486248203644461465935500517901513233739152882943010177276545128308412934555830087776128355125932914846459470221102007666912211992310538890654396487111705385730502843589727289829692152177134753098649781412247065660637826282055169991824099110916576856188876975621376606634258927784025787142263367152947108720757222446686415627479703666031871635656314282727051189190889008763055811680040315277078928068816491
c = 4185308529416874005831230781014092407198451385955677399668501833902623478395669279404883990725184332709152443372583701076198786635291739356770857286702107156730020004358955622511061410661058982622055199736820808203841446796305284394651714430918690389486920560834672316158146453183789412140939029029324756035358081754426645160033262924330248675216108270980157049705488620263485129480952814764002865280019185127662449318324279383277766416258142275143923532168798413011028271543085249029048997452212503111742302302065401051458066585395360468447460658672952851643547193822775218387853623453638025492389122204507555908862

n = 21206968097314131007183427944486801953583151151443627943113736996776787181111063957960698092696800555044199156765677935373149598221184792286812213294617749834607696302116136745662816658117055427803315230042700695125718401646810484873064775005221089174056824724922160855810527236751389605017579545235876864998419873065217294820244730785120525126565815560229001887622837549118168081685183371092395128598125004730268910276024806808565802081366898904032509920453785997056150497645234925528883879419642189109649009132381586673390027614766605038951015853086721168018787523459264932165046816881682774229243688581614306480751
c = 4521038011044758441891128468467233088493885750850588985708519911154778090597136126150289041893454126674468141393472662337350361712212694867311622970440707727941113263832357173141775855227973742571088974593476302084111770625764222838366277559560887042948859892138551472680654517814916609279748365580610712259856677740518477086531592233107175470068291903607505799432931989663707477017904611426213770238397005743730386080031955694158466558475599751940245039167629126576784024482348452868313417471542956778285567779435940267140679906686531862467627238401003459101637191297209422470388121802536569761414457618258343550613

n = 22822039733049388110936778173014765663663303811791283234361230649775805923902173438553927805407463106104699773994158375704033093471761387799852168337898526980521753614307899669015931387819927421875316304591521901592823814417756447695701045846773508629371397013053684553042185725059996791532391626429712416994990889693732805181947970071429309599614973772736556299404246424791660679253884940021728846906344198854779191951739719342908761330661910477119933428550774242910420952496929605686154799487839923424336353747442153571678064520763149793294360787821751703543288696726923909670396821551053048035619499706391118145067
c = 15406498580761780108625891878008526815145372096234083936681442225155097299264808624358826686906535594853622687379268969468433072388149786607395396424104318820879443743112358706546753935215756078345959375299650718555759698887852318017597503074317356745122514481807843745626429797861463012940172797612589031686718185390345389295851075279278516147076602270178540690147808314172798987497259330037810328523464851895621851859027823681655934104713689539848047163088666896473665500158179046196538210778897730209572708430067658411755959866033531700460551556380993982706171848970460224304996455600503982223448904878212849412357

n = 21574139855341432908474064784318462018475296809327285532337706940126942575349507668289214078026102682252713757703081553093108823214063791518482289846780197329821139507974763780260290309600884920811959842925540583967085670848765317877441480914852329276375776405689784571404635852204097622600656222714808541872252335877037561388406257181715278766652824786376262249274960467193961956690974853679795249158751078422296580367506219719738762159965958877806187461070689071290948181949561254144310776943334859775121650186245846031720507944987838489723127897223416802436021278671237227993686791944711422345000479751187704426369
c = 20366856150710305124583065375297661819795242238376485264951185336996083744604593418983336285185491197426018595031444652123288461491879021096028203694136683203441692987069563513026001861435722117985559909692670907347563594578265880806540396777223906955491026286843168637367593400342814725694366078337030937104035993569672959361347287894143027186846856772983058328919716702982222142848848117768499996617588305301483085428547267337070998767412540225911508196842253134355901263861121500650240296746702967594224401650220168780537141654489215019142122284308116284129004257364769474080721001708734051264841350424152506027932

n = 25360227412666612490102161131174584819240931803196448481224305250583841439581008528535930814167338381983764991296575637231916547647970573758269411168219302370541684789125112505021148506809643081950237623703181025696585998044695691322012183660424636496897073045557400768745943787342548267386564625462143150176113656264450210023925571945961405709276631990731602198104287528528055650050486159837612279600415259486306154947514005408907590083747758953115486124865486720633820559135063440942528031402951958557630833503775112010715604278114325528993771081233535247118481765852273252404963430792898948219539473312462979849137
c = 19892772524651452341027595619482734356243435671592398172680379981502759695784087900669089919987705675899945658648623800090272599154590123082189645021800958076861518397325439521139995652026377132368232502108620033400051346127757698623886142621793423225749240286511666556091787851683978017506983310073524398287279737680091787333547538239920607761080988243639547570818363788673249582783015475682109984715293163137324439862838574460108793714172603672477766831356411304446881998674779501188163600664488032943639694828698984739492200699684462748922883550002652913518229322945040819064133350314536378694523704793396169065179

n = 22726855244632356029159691753451822163331519237547639938779517751496498713174588935566576167329576494790219360727877166074136496129927296296996970048082870488804456564986667129388136556137013346228118981936899510687589585286517151323048293150257036847475424044378109168179412287889340596394755257704938006162677656581509375471102546261355748251869048003600520034656264521931808651038524134185732929570384705918563982065684145766427962502261522481994191989820110575981906998431553107525542001187655703534683231777988419268338249547641335718393312295800044734534761692799403469497954062897856299031257454735945867491191
c = 6040119795175856407541082360023532204614723858688636724822712717572759793960246341800308149739809871234313049629732934797569781053000686185666374833978403290525072598774001731350244744590772795701065129561898116576499984185920661271123665356132719193665474235596884239108030605882777868856122378222681140570519180321286976947154042272622411303981011302586225630859892731724640574658125478287115198406253847367979883768000812605395482952698689604477719478947595442185921480652637868335673233200662100621025061500895729605305665864693122952557361871523165300206070325660353095592778037767395360329231331322823610060006

n = 23297333791443053297363000786835336095252290818461950054542658327484507406594632785712767459958917943095522594228205423428207345128899745800927319147257669773812669542782839237744305180098276578841929496345963997512244219376701787616046235397139381894837435562662591060768476997333538748065294033141610502252325292801816812268934171361934399951548627267791401089703937389012586581080223313060159456238857080740699528666411303029934807011214953984169785844714159627792016926490955282697877141614638806397689306795328344778478692084754216753425842557818899467945102646776342655167655384224860504086083147841252232760941
c = 5418120301208378713115889465579964257871814114515046096090960159737859076829258516920361577853903925954198406843757303687557848302302200229295916902430205737843601806700738234756698575708612424928480440868739120075888681672062206529156566421276611107802917418993625029690627196813830326369874249777619239603300605876865967515719079797115910578653562787899019310139945904958024882417833736304894765433489476234575356755275147256577387022873348906900149634940747104513850154118106991137072643308620284663108283052245750945228995387803432128842152251549292698947407663643895853432650029352092018372834457054271102816934

n = 28873667904715682722987234293493200306976947898711255064125115933666968678742598858722431426218914462903521596341771131695619382266194233561677824357379805303885993804266436810606263022097900266975250431575654686915049693091467864820512767070713267708993899899011156106766178906700336111712803362113039613548672937053397875663144794018087017731949087794894903737682383916173267421403408140967713071026001874733487295007501068871044649170615709891451856792232315526696220161842742664778581287321318748202431466508948902745314372299799561625186955234673012098210919745879882268512656931714326782335211089576897310591491
c = 9919880463786836684987957979091527477471444996392375244075527841865509160181666543016317634963512437510324198702416322841377489417029572388474450075801462996825244657530286107428186354172836716502817609070590929769261932324275353289939302536440310628698349244872064005700644520223727670950787924296004296883032978941200883362653993351638545860207179022472492671256630427228461852668118035317021428675954874947015197745916918197725121122236369382741533983023462255913924692806249387449016629865823316402366017657844166919846683497851842388058283856219900535567427103603869955066193425501385255322097901531402103883869

n = 22324685947539653722499932469409607533065419157347813961958075689047690465266404384199483683908594787312445528159635527833904475801890381455653807265501217328757871352731293000303438205315816792663917579066674842307743845261771032363928568844669895768092515658328756229245837025261744260614860746997931503548788509983868038349720225305730985576293675269073709022350700836510054067641753713212999954307022524495885583361707378513742162566339010134354907863733205921845038918224463903789841881400814074587261720283879760122070901466517118265422863420376921536734845502100251460872499122236686832189549698020737176683019
c = 1491527050203294989882829248560395184804977277747126143103957219164624187528441047837351263580440686474767380464005540264627910126483129930668344095814547592115061057843470131498075060420395111008619027199037019925701236660166563068245683975787762804359520164701691690916482591026138582705558246869496162759780878437137960823000043988227303003876410503121370163303711603359430764539337597866862508451528158285103251810058741879687875218384160282506172706613359477657215420734816049393339593755489218588796607060261897905233453268671411610631047340459487937479511933450369462213795738933019001471803157607791738538467

n = 27646746423759020111007828653264027999257847645666129907789026054594393648800236117046769112762641778865620892443423100189619327585811384883515424918752749559627553637785037359639801125213256163008431942593727931931898199727552768626775618479833029101249692573716030706695702510982283555740851047022672485743432464647772882314215176114732257497240284164016914018689044557218920300262234652840632406067273375269301008409860193180822366735877288205783314326102263756503786736122321348320031950012144905869556204017430593656052867939493633163499580242224763404338807022510136217187779084917996171602737036564991036724299
c = 21991524128957260536043771284854920393105808126700128222125856775506885721971193109361315961129190814674647136464887087893990660894961612838205086401018885457667488911898654270235561980111174603323721280911197488286585269356849579263043456316319476495888696219344219866516861187654180509247881251251278919346267129904739277386289240394384575124331135655943513831009934023397457082184699737734388823763306805326430395849935770213817533387235486307008892410920611669932693018165569417445885810825749609388627231235840912644654685819620931663346297596334834498661789016450371769203650109994771872404185770230172934013971

n = 20545487405816928731738988374475012686827933709789784391855706835136270270933401203019329136937650878386117187776530639342572123237188053978622697282521473917978282830432161153221216194169879669541998840691383025487220850872075436064308499924958517979727954402965612196081404341651517326364041519250125036424822634354268773895465698920883439222996581226358595873993976604699830613932320720554130011671297944433515047180565484495191003887599891289037982010216357831078328159028953222056918189365840711588671093333013117454034313622855082795813122338562446223041211192277089225078324682108033843023903550172891959673551
c = 14227439188191029461250476692790539654619199888487319429114414557975376308688908028140817157205579804059783807641305577385724758530138514972962209062230576107406142402603484375626077345190883094097636019771377866339531511965136650567412363889183159616188449263752475328663245311059988337996047359263288837436305588848044572937759424466586870280512424336807064729894515840552404756879590698797046333336445465120445087587621743906624279621779634772378802959109714400516183718323267273824736540168545946444437586299214110424738159957388350785999348535171553569373088251552712391288365295267665691357719616011613628772175

n = 27359727711584277234897157724055852794019216845229798938655814269460046384353568138598567755392559653460949444557879120040796798142218939251844762461270251672399546774067275348291003962551964648742053215424620256999345448398805278592777049668281558312871773979931343097806878701114056030041506690476954254006592555275342579529625231194321357904668512121539514880704046969974898412095675082585315458267591016734924646294357666924293908418345508902112711075232047998775303603175363964055048589769318562104883659754974955561725694779754279606726358588862479198815999276839234952142017210593887371950645418417355912567987
c = 3788529784248255027081674540877016372807848222776887920453488878247137930578296797437647922494510483767651150492933356093288965943741570268943861987024276610712717409139946409513963043114463933146088430004237747163422802959250296602570649363016151581364006795894226599584708072582696996740518887606785460775851029814280359385763091078902301957226484620428513604630585131511167015763190591225884202772840456563643159507805711004113901417503751181050823638207803533111429510911616160851391754754434764819568054850823810901159821297849790005646102129354035735350124476838786661542089045509656910348676742844957008857457

n = 27545937603751737248785220891735796468973329738076209144079921449967292572349424539010502287564030116831261268197384650511043068738911429169730640135947800885987171539267214611907687570587001933829208655100828045651391618089603288456570334500533178695238407684702251252671579371018651675054368606282524673369983034682330578308769886456335818733827237294570476853673552685361689144261552895758266522393004116017849397346259119221063821663280935820440671825601452417487330105280889520007917979115568067161590058277418371493228631232457972494285014767469893647892888681433965857496916110704944758070268626897045014782837
c = 14069112970608895732417039977542732665796601893762401500878786871680645798754783315693511261740059725171342404186571066972546332813667711135661176659424619936101038903439144294886379322591635766682645179888058617577572409307484708171144488708410543462972008179994594087473935638026612679389759756811490524127195628741262871304427908481214992471182859308828778119005750928935764927967212343526503410515793717201360360437981322576798056276657140363332700714732224848346808963992302409037706094588964170239521193589470070839790404597252990818583717869140229811712295005710540476356743378906642267045723633874011649259842

n = 25746162075697911560263181791216433062574178572424600336856278176112733054431463253903433128232709054141607100891177804285813783247735063753406524678030561284491481221681954564804141454666928657549670266775659862814924386584148785453647316864935942772919140563506305666207816897601862713092809234429096584753263707828899780979223118181009293655563146526792388913462557306433664296966331469906428665127438829399703002867800269947855869262036714256550075520193125987011945192273531732276641728008406855871598678936585324782438668746810516660152018244253008092470066555687277138937298747951929576231036251316270602513451
c = 17344284860275489477491525819922855326792275128719709401292545608122859829827462088390044612234967551682879954301458425842831995513832410355328065562098763660326163262033200347338773439095709944202252494552172589503915965931524326523663289777583152664722241920800537867331030623906674081852296232306336271542832728410803631170229642717524942332390842467035143631504401140727083270732464237443915263865880580308776111219718961746378842924644142127243573824972533819479079381023103585862099063382129757560124074676150622288706094110075567706403442920696472627797607697962873026112240527498308535903232663939028587036724

n = 23288486934117120315036919418588136227028485494137930196323715336208849327833965693894670567217971727921243839129969128783853015760155446770590696037582684845937132790047363216362087277861336964760890214059732779383020349204803205725870225429985939570141508220041286857810048164696707018663758416807708910671477407366098883430811861933014973409390179948577712579749352299440310543689035651465399867908428885541237776143404376333442949397063249223702355051571790555151203866821867908531733788784978667478707672984539512431549558672467752712004519300318999208102076732501412589104904734983789895358753664077486894529499
c = 10738254418114076548071448844964046468141621740603214384986354189105236977071001429271560636428075970459890958274941762528116445171161040040833357876134689749846940052619392750394683504816081193432350669452446113285638982551762586656329109007214019944975816434827768882704630460001209452239162896576191876324662333153835533956600295255158377025198426950944040643235430211011063586032467724329735785947372051759042138171054165854842472990583800899984893232549092766400510300083585513014171220423103452292891496141806956300396540682381668367564569427813092064053993103537635994311143010708814851867239706492577203899024

n = 19591441383958529435598729113936346657001352578357909347657257239777540424811749817783061233235817916560689138344041497732749011519736303038986277394036718790971374656832741054547056417771501234494768509780369075443550907847298246275717420562375114406055733620258777905222169702036494045086017381084272496162770259955811174440490126514747876661317750649488774992348005044389081101686016446219264069971370646319546429782904810063020324704138495608761532563310699753322444871060383693044481932265801505819646998535192083036872551683405766123968487907648980900712118052346174533513978009131757167547595857552370586353973
c = 3834917098887202931981968704659119341624432294759361919553937551053499607440333234018189141970246302299385742548278589896033282894981200353270637127213483172182529890495903425649116755901631101665876301799865612717750360089085179142750664603454193642053016384714515855868368723508922271767190285521137785688075622832924829248362774476456232826885801046969384519549385428259591566716890844604696258783639390854153039329480726205147199247183621535172450825979047132495439603840806501254997167051142427157381799890725323765558803808030109468048682252028720241357478614704610089120810367192414352034177484688502364022887

n = 19254242571588430171308191757871261075358521158624745702744057556054652332495961196795369630484782930292003238730267396462491733557715379956969694238267908985251699834707734400775311452868924330866502429576951934279223234676654749272932769107390976321208605516299532560054081301829440688796904635446986081691156842271268059970762004259219036753174909942343204432795076377432107630203621754552804124408792358220071862369443201584155711893388877350138023238624566616551246804054720492816226651467017802504094070614892556444425915920269485861799532473383304622064493223627552558344088839860178294589481899206318863310603
c = 6790553533991297205804561991225493105312398825187682250780197510784765226429663284220400480563039341938599783346724051076211265663468643826430109013245014035811178295081939958687087477312867720289964506097819762095244479129359998867671811819738196687884696680463458661374310994610760009474264115750204920875527434486437536623589684519411519100170291423367424938566820315486507444202022408003879118465761273916755290898112991525546114191064022991329724370064632569903856189236177894007766690782630247443895358893983735822824243487181851098787271270256780891094405121947631088729917398317652320497765101790132679171889

n = 26809700251171279102974962949184411136459372267620535198421449833298448092580497485301953796619185339316064387798092220298630428207556482805739803420279056191194360049651767412572609187680508073074653291350998253938793269214230457117194434853888765303403385824786231859450351212449404870776320297419712486574804794325602760347306432927281716160368830187944940128907971027838510079519466846176106565164730963988892400240063089397720414921398936399927948235195085202171264728816184532651138221862240969655185596628285814057082448321749567943946273776184657698104465062749244327092588237927996419620170254423837876806659
c = 386213556608434013769864727123879412041991271528990528548507451210692618986652870424632219424601677524265011043146748309774067894985069288067952546139416819404039688454756044862784630882833496090822568580572859029800646671301748901528132153712913301179254879877441322285914544974519727307311002330350534857867516466612474769753577858660075830592891403551867246057397839688329172530177187042229028685862036140779065771061933528137423019407311473581832405899089709251747002788032002094495379614686544672969073249309703482556386024622814731015767810042969813752548617464974915714425595351940266077021672409858645427346

思路

每两个n求一次公约数，看看是否有不为1的一组n，如果有的话，p就是这个公约数，之后就可以求其他量了

exp.py

from Crypto.Util.number import *
import gmpy2

e = 65537

n = [n0,n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,n13,n14,n15,n16,n17,n18,n19]
c = [c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19]

for i in range(len(n)):
    for j in range(len(n)):
        if (i!=j):
            t = gmpy2.gcd(n[i],n[j])
            if t != 1:
                p = t
                q = n[i] // p
                d = gmpy2.invert(e,(p-1)*(q-1))
                m = pow(c[i],d,n[i])
                print(long_to_bytes(m))
                
#flag{abdcbe5fd94e23b3de429223ab9c2fdf}

第二种情况 用中国剩余定理

简要说明中国剩余定理的作用就是把一个同余式组变成一个同余式,eg:
$$
c_1 \equiv m^e \mod n_1
$$

$$
c_2 \equiv m ^e \mod n_2
$$

$$
c_3 \equiv m ^e \mod n_3
$$

转换为一个$C \equiv m ^ e \mod N$，$N = lcm(n_1,n_2,n_3)$

例题1

task.py

import libnum
import gmpy2
import random
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)

p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
n1 = p * q
p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
n2 = p * q
p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
n3 = p * q
while 1:
    e = random.randint(10, 20)
    print(e)
    if gmpy2.is_prime(e):
        break
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)
c3 = pow(m, e, n3)

print("n1=", n1)
print("n2=", n2)
print("n3=", n3)

print("c1=", c1)
print("c2=", c2)
print("c3=", c3)

先根据中国剩余定理求出$m^e$，这题的e只给范围，要爆破一下

exp.py

from Crypto.Util.number import long_to_bytes
import gmpy2

def Get_Mi(m_list,m):               #求衍数
    M_list = []
    for mi in m_list:
        M_list.append(m // mi)
    return M_list

def Get_resMi(M_list,m_list):       #求乘率
    resM_list = []
    for i in range(len(M_list)):
        resM_list.append(gmpy2.invert(M_list[i],m_list[i]))
    return resM_list

def Get_result(a_list):
    M_list = Get_Mi(m_list,m)
    resM_list = Get_resMi(M_list,m_list)
    result = 0
    for i in range(len(M_list)):
        result += M_list[i]*resM_list[i]*a_list[i]
    result %= m
    return result

n1 = 16655230929893303490818415854457831426545038662809855283873228642358207995734291242944120042612699642460820594813654718158395826755230956722936107927889550129166619245152453353908373751380196656611349200623414836128383308653618062999595622747482867683840133843768870236300348203389275090871132570173650238774275209757683812077533989960172822335488251744796657926473009279723460304257252876756936524918018903158795894385111046938638194925881670388700872760201130485273663156422785999102754192840209476417602399017445296045070405343876349687582470436774316410697773759057621576657298096301937899052773787116133124199739
n2 = 17197151926745749646602149115445210421300330711044282276861045275221683290586877554048509794473112203880585601275129330843554946888863132721219683639579200702355880529569042889789589005950061966309684759066705732225014741164779016525568884409690021988879475589545329149547046975086877521757237117008484775731784935960191717287332176327498377273179740487245459081737196777751408106728622513560888261855065717079007065635401835089216224111969668029246916986663313301660909538148574652809266532053889578734157117390082522831069594417637550812101652367765364077901612478983024721669687150628356918237152414368862535409859
n3 = 18719461901666732419189610536735130974364055134601694187780706398369536769336080321122034942831217438281120989017698755904233940669427542442488330152862658754609065361849067002424120904308655036927580582916373684567047102601602588472175947665724244201887952599804681827419266055359412641159981152796138695901074514583606207162167385730873921563442166111892785482387108299191119048884993267729877797586421940344366636285656854837470348603688925980178978612114344024951042846249621559376348599687263736342957456838732355009637030035658212442442824658869094581324944034490700706979663405137522294780606800571433058912041

c1 = 3530761236149189046680124371485374220252032991305088864647979778627799354583229731576585900490173357726425570018182390597284149666834264690795437972634538596441103368165128688664787322126097802985602065455316693754513332761284857157982201975554297034291092099307950246864758375115838291339394148547902128382917596947095456178572561422004708150053706114994560773293625641699691472764190426577272488084620105693964419578988589192873196530900413833531923536786853211065167782657153004342018675666293830194703777994380600060782651326623229047839109994778831432598543154184891096335217588164509636922274833553782288823349
c2 = 7557835478962501903223351987016911891266554255050134264644805724502475848487138948948076311894495847429608136390014902405718084026208891531815323418707377349405409096779206918831458396991602033494429461919844309109113047361743133772636443322195238900874786548606687215969337920658068807801603115402783849082788527952834594443136756890747461628705174983562847145588532659589787532039981477468881131005056101092222499397893730056830156407331988257383965698358904379729558105489119604343081747549319382873235286788453435066434264212954607441597606413293491628299838317713381567250093086011058119721189087729804152444980
c3 =8471234074077377509408346140986116360421840978074779990698043926601850838824365885362094731657766299393262223086536737448516669969503891677808275285733096884405583100485903641986516527279324847718603091709062689898441711907846902050004165404073776422495381050861998133576074526490209080137421773440295749900582039873013319584167081936219517593826232230971430937112005615502869367413205660317010303160932970748420125111225082886082306332340892549579826854620461821084886193470846195356695313518639669516456574134135244251956477677377976434266541164893562226872334598362396368708087248848222008201970781942468960022694

m_list= [n1,n2,n3]
a_list= [c1,c2,c3]

m = 1
for i in m_list:
    m *= i

result = Get_result(a_list)
for e in range(10,20):
    m = gmpy2.iroot(result,e)
    if m[1]:
        print(long_to_bytes(m[0]))

例题2 鹤城杯2021——Crazy_Tech_RSA

task.py

from Crypto.Util.number import *
from Crypto.Util.Padding import *

FLAG = bytes_to_long(pad(b"flag{??????}",64))
def init_key():
    p, q = getPrime(512), getPrime(512)
    n = p*q
    e = 9
    while(GCD((p-1)*(q-1),e)!=1):
        p, q = getPrime(512), getPrime(512)
        n = p*q
    d = inverse(e,(p-1)*(q-1))
    return n,e,d

n_list=list()
c_list=list()
for i in range(9):
    N,e,d=init_key()
    n_list.append(N)
    c=pow(FLAG,e,N)
    c_list.append(pow(FLAG,e,N))
    assert(pow(c,d,N)==FLAG)
print("n_list:",n_list)
print("c_list:",c_list)

先用中国剩余定理解出$m^e$

再开根号

这道题的e是给出，如果e没有给出的话，需要爆破e

exp.py

from Crypto.Util.number import long_to_bytes
import gmpy2

def Get_Mi(m_list,m):               #求衍数
    M_list = []
    for mi in m_list:
        M_list.append(m // mi)
    return M_list

def Get_resMi(M_list,m_list):       #求乘率
    resM_list = []
    for i in range(len(M_list)):
        resM_list.append(gmpy2.invert(M_list[i],m_list[i]))
    return resM_list

def Get_result(a_list):
    M_list = Get_Mi(m_list,m)
    resM_list = Get_resMi(M_list,m_list)
    result = 0
    for i in range(len(M_list)):
        result += M_list[i]*resM_list[i]*a_list[i]
    result %= m
    return result
m_list=[71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799, 92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949, 100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919, 59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377, 72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281, 69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951, 76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
a_list=[62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585, 46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900, 85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198, 14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981, 16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376, 31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996, 25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]

m = 1
for i in m_list:
    m *= i

result = Get_result(a_list)
e = 9
m = gmpy2.iroot(result,e)
if m[1]:
print(long_to_bytes(m[0]))

七、维纳攻击

攻击条件:$d < \frac{1}{3}N^{0.25}$

原理:
$$
ed \equiv 1 \mod \phi(n)
$$
有
$$
ed = k\phi(n) + 1
$$
因为$\phi(n) \approx n$
$$
\therefore ed \approx kn + 1
$$
两边同除$dn$有
$$
\frac{e}{n} \approx \frac{k}{d} + \frac{1}{dn}
$$
则
$$
\frac{e}{n} - \frac{k}{d} \approx \frac{1}{dn}
$$
满足勒让德定理(这个定理网上可以搜得到，根据这个定理，不同形式的n是不一样的，比如说这个例子需要$n=p\times q$才可使用)，因此$\frac{e}{n}$可以作为$\frac{k}{d}$的收敛子

连分数展开即可

例题

task.py

import libnum
import random
import gmpy2

# 生成随机素数
p = libnum.generate_prime(512)
q = libnum.generate_prime(512)
m = "flag{20d6e2da95dcc1fa5f5432a436c4be18}"
# 字符串转数字
m = libnum.s2n(m)
n = p * q
phi_n = (p - 1) * (q - 1)

# 计算d
while True:
    nbits = 1024
    d = random.getrandbits(nbits // 4)
    if (libnum.gcd(d, phi_n) == 1 and 36 * pow(d, 4) < n):
        break
# 计算e
e = libnum.invmod(d, phi_n)

c = pow(m, e, n)

print("n=", n)
print("e=", e)
print("c=", c)

exp.py

import gmpy2
import libnum


def continuedFra(x, y):
    """计算连分数
    :param x: 分子
    :param y: 分母
    :return: 连分数列表
    """
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf


def gradualFra(cf):
    """计算传入列表最后的渐进分数
    :param cf: 连分数列表
    :return: 该列表最后的渐近分数
    """
    numerator = 0
    denominator = 1
    for x in cf[::-1]:
        # 这里的渐进分数分子分母要分开
        numerator, denominator = denominator, x * denominator + numerator
    return numerator, denominator


def solve_pq(a, b, c):
    """使用韦达定理解出pq，x^2−(p+q)∗x+pq=0
    :param a:x^2的系数
    :param b:x的系数
    :param c:pq
    :return:p，q
    """
    par = gmpy2.isqrt(b * b - 4 * a * c)
    return (-b + par) // (2 * a), (-b - par) // (2 * a)


def getGradualFra(cf):
    """计算列表所有的渐近分数
    :param cf: 连分数列表
    :return: 该列表所有的渐近分数
    """
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf


def wienerAttack(e, n):
    """
    :param e:
    :param n:
    :return: 私钥d
    """
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    for d, k in gf:
        if k == 0: continue
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        p, q = solve_pq(1, n - phi + 1, n)
        if p * q == n:
            return d


n = 113881698992379349039968368927979997900777221951663104697020683691495129639829918739755194174063944178083527489820939138302751895652076620380510013941997706327553964127612610209509889011613768847759318892303231846117914554931459295347697888260576901354448014917692680573408654658384481284699735788978230690197
e = 39068960413447607023613035707248214114819409621234801785480423979473767995171860917209502861408393208940683687475760366491413173744775811644295874981290403938714121977201901942939425294427737703229098649131737380098596135730392902019429964095866394165971291108245774407908011073271822915371753470010435225545
c = 32897925577913728659288168937025744709859960639901500169867896018406263110205704273203287172003057450591000201857719871686024077615520906540631374442504017489026298422189715372129838501090730593164075113452055617571409044743698645392909829425374093273187125709095368164744188182156849031225036001381531504057

d = wienerAttack(e, n)
print(d)
m = pow(c, d, n)
print(libnum.n2s(m).decode())

exp也可以用sagemath写，这里就不展示了

多因子的维纳攻击

例题来源：2023NKCTF——complex_matrix

task.py

from Crypto.Util.number import *
import gmpy2 as gy
flag = ''

k = 400
p, q = getPrime(741), getPrime(741)
N = p * q
phi = (p-1) * (q-1)
_flag = bytes_to_long(flag)
p, q = getPrime(1024), getPrime(1024)
d_array = [getPrime(k) for _ in range(4)] 
e_array = [inverse(i, phi) for i in d_array]
c = pow(_flag, 65537, N)
print('N:',N)
print('e:',e_array)
print('c:',c)

#N: 71841248095369087024928175623295380241516644434969868335504061065977014103487197287619667598363486210886674500469383623511906399909335989202774281795855975972913438448899231650449810696539722877903606541112937729384851506921675290984316325565141178015123381439392534417225128922398194700511937668809140024838070124095703585627058463137549632965723304713166804084673075651182998654091113119667582720831809458721072371364839503563819080226784026253
#e: [65128799196671634905309494529154568614228788035735808211836905142007976099865571126946706559109393187772126407982007858423859147772762638898854472065889939549916077695303157760259717113616428849798058080633047516455513870697383339784816006154279428812359241282979297285283850338964993773227397528608557211742425548651971558377656644211835094019462699301650412862894391885325969143805924684662849869947172175608502179438901337558870349697233790535, 58756559706647121529575085912021603170286163639572075337348109911506627489265537716060463072086480156516641723700802217411122982693536541892986623158818442274840863016647800896033363360822503445344748132842451806511693779600370832206455202293028402486647422212959763287987847280322100701242139127654031151565924132562837893975505159702015125483479126108892709063135006366792197127007229210558758401679638300464111782814561428899998471531067163715, 34828685390969672139784723764579499920301439564705391196519314224159563070870933754477650614819514127121146216049444888554338415587165719098661141454627820126445291802801256297252654045398330613075575527685542980264993711077876535643646746742646371967302159565887123638001580042027272379341650995728849759541960087953160211696369079708787543303742132161742979856720539914370868829868891655221361545648778590685232034703220732697083024449894197969, 26717968456600556973167180286909817773394160817933525240720067057464671317174201540556176814203780603153696663101158205367554829261808020426363683474848952397963507069306452835776851274959389849223566030857588019845781623271395012194869024566879791449466064832273531795430185178486425688475688634844530106740480643866537205900809400383304665727460014210405339697947582657505028211149470787536144302545259243549176816653560626044921521516818788487]
#c: 39297018404565022956251803918747154798377576057123078716166221329195959669756819453426741569480551313085435037629493881038383709458043802420338889323233368852331387845200216275712388921820794980987541224782392553528127093154957890356084331463340193478391679540506421250562554424770350351514435220782124981277580072039637811543914983033300225131364246910828188727043248991987332274929827173923543187017105236008487756190002204169623313222748976369

存个脚本，来源文章列表 | NSSCTF

exp.py

import gmpy2
import libnum
isdigit = lambda x: ord('0') <= ord(x) <= ord('9')

def my_permutations(g, n):
    sub = []
    res = []
    def dfs(s, prev):
        if len(s) == n:
            res.append(s[::])
        for i in g:
            if i in s or i < prev:
                continue
            s.append(i)
            dfs(s, max(prev, i))
            s.remove(i)
    dfs(sub, 0)
    return res

class X3NNY(object):
    def __init__(self, exp1, exp2):
        self.exp1 = exp1
        self.exp2 = exp2
    
    def __mul__(self, b):
        return X3NNY(self.exp1 * b.exp1, self.exp2 * b.exp2)

    def __repr__(self):
        return '%s = %s' % (self.exp1.expand().collect_common_factors(), self.exp2)

class X_Complex(object):
    def __init__(self, exp):
        i = 0
        s = '%s' % exp
        while i < len(s):
            if isdigit(s[i]):
                num = 0
                while i < len(s) and isdigit(s[i]):
                    num = num*10 + int(s[i])
                    i += 1
                if i >= len(s):
                    self.b = num
                elif s[i] == '*':
                    self.a = num
                    i += 2
                elif s[i] == '/':
                    i += 1
                    r = 0
                    while i < len(s) and isdigit(s[i]):
                        r = r*10 + int(s[i])
                        i += 1
                    self.b = num/r
            else:
                i += 1
        if not hasattr(self, 'a'):
            self.a = 1
        if not hasattr(self, 'b'):
            self.b = 0

def WW(e, d, k, g, N, s):
    return X3NNY(e*d*g-k*N, g+k*s)
def GG(e1, e2, d1, d2, k1, k2):
    return X3NNY(e1*d1*k2- e2*d2*k1, k2 - k1)

def W(i):
    e = eval("e%d" % i)
    d = eval("d%d" % i)
    k = eval("k%d" % i)
    return WW(e, d, k, g, N, s)

def G(i, j):
    e1 = eval("e%d" % i)
    d1 = eval("d%d" % i)
    k1 = eval("k%d" % i)
    
    e2 = eval("e%d" % j)
    d2 = eval("d%d" % j)
    k2 = eval("k%d" % j)
    
    return GG(e1, e2, d1, d2, k1, k2)

def R(e, sn): # min u max v
    ret = X3NNY(1, 1)
    n = max(e)
    nn = len(e)
    l = set(i for i in range(1, n+1))
    debug = ''
    u, v = 0, 0
    for i in e:
        if i == 1:
            ret *= W(1)
            debug += 'W(%d)' % i
            nn -= 1
            l.remove(1)
            u += 1
        elif i > min(l) and len(l) >= 2*nn:
            ret *= G(min(l), i)
            nn -= 1
            debug += 'G(%d, %d)' % (min(l), i)
            l.remove(min(l))
            l.remove(i)
            v += 1
        else:
            ret *= W(i)
            l.remove(i)
            debug += 'W(%d)' % i
            nn -= 1
            u += 1
    # print(debug, end = ' ')
    return ret, u/2 + (sn - v) * a

def H(n):
    if n == 0:
        return [0]
    if n == 2:
        return [(), (1,), (2,), (1, 2)]
    ret = []
    for i in range(3, n+1):
        ret.append((i,))
        for j in range(1, i):
            for k in my_permutations(range(1, i), j):
                ret.append(tuple(k + [i]))
    return H(2) + ret
    
def CC(exp, n):
    cols = [0 for i in range(1<<n)]
    
    # split exp
    texps = ('%s' % exp.exp1.expand()).strip().split(' - ')
    ops = []
    exps = []
    for i in range(len(texps)):
        if texps[i].find(' + ') != -1:
            tmp = texps[i].split(' + ')
            ops.append(0)
            exps.append(tmp[0])
            for i in range(1, len(tmp)):
                ops.append(1)
                exps.append(tmp[i])
        else:
            ops.append(0)
            exps.append(texps[i])
    if exps[0][0] == '-':
        for i in range(len(exps)):
            ops[i] = 1-ops[i]
        exps[0] = exps[0][1:]
    else:
        ops[0] = 1
    # find e and N
    l = []
    for i in range(len(exps)):
        tmp = 1 if ops[i] else -1
        en = []
        j = 0
        while j < len(exps[i]):
            if exps[i][j] == 'e':
                num = 0
                j += 1
                while isdigit(exps[i][j]):
                    num = num*10 + int(exps[i][j])
                    j += 1
                tmp *= eval('e%d' % num)
                en.append(num)
            elif exps[i][j] == 'N':
                j += 1
                num = 0
                if exps[i][j] == '^':
                    j += 1
                    while isdigit(exps[i][j]):
                        num = num*10 + int(exps[i][j])
                        j += 1
                if num == 0:
                    num = 1
                tmp *= eval('N**%d' % num)
            else:
                j += 1
        if tmp == 1 or tmp == -1:
            l.append((0, ()))
        else:
            l.append((tmp, tuple(sorted(en))))
    
    # construct h
    mp = H(n)
    for val, en in l:
        cols[mp.index(en)] = val
    # print(cols)
    return cols

def EWA(n, elist, NN, alpha):
    mp = H(n)
    var('a')
    S = [X_Complex(n*a)]
    cols = [[1 if i == 0 else 0 for i in range(2^n)]]
    for i in mp[1:]:
        eL, s = R(i, n)
        cols.append(CC(eL, n))
        S.append(X_Complex(s))
    
    alphaA,alphaB = 0, 0
    for i in S:
        alphaA = max(i.a, alphaA)
        alphaB = max(i.b, alphaB)
    # print(alphaA, alphaB)
    D = []
    for i in range(len(S)):
        # print((alphaA-S[i].a), (alphaB - S[i].b))
        D.append(
            int(NN^((alphaA-S[i].a)*alpha + (alphaB - S[i].b)))
        )
    kw = {'N': NN}
    for i in range(len(elist)):
        kw['e%d' % (i+1)] = elist[i]

    B = Matrix(ZZ, Matrix(cols).T(**kw)) * diagonal_matrix(ZZ, D)
    L = B.LLL(0.5)
    v = Matrix(ZZ, L[0])
    x = v * B**(-1)
    phi = int(x[0,1]/x[0,0]*elist[0])
    return phi

def attack(NN, elist, alpha):
    phi = EWA(len(elist), elist, NN, alpha)
    print(phi)
    return phi


NN = 71841248095369087024928175623295380241516644434969868335504061065977014103487197287619667598363486210886674500469383623511906399909335989202774281795855975972913438448899231650449810696539722877903606541112937729384851506921675290984316325565141178015123381439392534417225128922398194700511937668809140024838070124095703585627058463137549632965723304713166804084673075651182998654091113119667582720831809458721072371364839503563819080226784026253
elist = [65128799196671634905309494529154568614228788035735808211836905142007976099865571126946706559109393187772126407982007858423859147772762638898854472065889939549916077695303157760259717113616428849798058080633047516455513870697383339784816006154279428812359241282979297285283850338964993773227397528608557211742425548651971558377656644211835094019462699301650412862894391885325969143805924684662849869947172175608502179438901337558870349697233790535, 58756559706647121529575085912021603170286163639572075337348109911506627489265537716060463072086480156516641723700802217411122982693536541892986623158818442274840863016647800896033363360822503445344748132842451806511693779600370832206455202293028402486647422212959763287987847280322100701242139127654031151565924132562837893975505159702015125483479126108892709063135006366792197127007229210558758401679638300464111782814561428899998471531067163715, 34828685390969672139784723764579499920301439564705391196519314224159563070870933754477650614819514127121146216049444888554338415587165719098661141454627820126445291802801256297252654045398330613075575527685542980264993711077876535643646746742646371967302159565887123638001580042027272379341650995728849759541960087953160211696369079708787543303742132161742979856720539914370868829868891655221361545648778590685232034703220732697083024449894197969, 26717968456600556973167180286909817773394160817933525240720067057464671317174201540556176814203780603153696663101158205367554829261808020426363683474848952397963507069306452835776851274959389849223566030857588019845781623271395012194869024566879791449466064832273531795430185178486425688475688634844530106740480643866537205900809400383304665727460014210405339697947582657505028211149470787536144302545259243549176816653560626044921521516818788487]
c = 39297018404565022956251803918747154798377576057123078716166221329195959669756819453426741569480551313085435037629493881038383709458043802420338889323233368852331387845200216275712388921820794980987541224782392553528127093154957890356084331463340193478391679540506421250562554424770350351514435220782124981277580072039637811543914983033300225131364246910828188727043248991987332274929827173923543187017105236008487756190002204169623313222748976369
alpha = 400 / int(NN).bit_length()				#400指的是d的比特
for i in range(1, len(elist)+1):
    var("e%d" % i)
    var("d%d" % i)
    var("k%d" % i)
g, N, s = var('g'), var('N'), var('s')

for i in range(len(elist)):
    elist[i] = Integer(elist[i])
phi = attack(NN, elist, alpha)

d = gmpy2.invert(65537, phi)
m = int(pow(c, d, NN))
print(libnum.n2s(m))
# NKCTF{F10w3r_Hav3_r3start_Day_N0_Man_iS_Y0ung_Aga1n}

八、共享素数

两个n有相同的因子，直接求公因数就好了

例题

task.py

import gmpy2
import libnum
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)
p = libnum.generate_prime(1024)
q1 = libnum.generate_prime(1024)
q2 = libnum.generate_prime(1024)
n1 = p * q1
n2 = p * q2
e = 65537
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)
print("n1=", n1)
print("n2=", n2)
print("c1=", c1)
print("c2=", c2)

exp.py

from Crypto.Util.number import long_to_bytes
import gmpy2

n1 =22036096414750333101406538757625812613248444424049684758772058140377463618250795867832853117902163257003301132932490853355450673043991381637053778653821758783435921283322439267628837074056789021611782010444749024512216306961829453158759193969454712080047205883631153040900193575534288719429526169135614695862857156639195562501217424283401364740789214390377624598500939079307163832197534297642842744345373413423859103414676878739674227554029537817890874031594311152843060524913028526429344172693584167398664817727426767686424415189580527939256633114120720308173788544194669684834369132677253418971615644691719536820433
n2 =17251653165250011947306159769694143433212298910745609670733920118632739529605426957617875166211610794383631191273183964010346725508667657137931394653419082978603166138439632713627832321960586938891805262605225424775586397813147240201440036009395991700175612039074317131837185920131565272816639771739150718839592250080325774556601865770352479323350280393818365902570673799584200153846520860657815432981116910233453207519365604533077996449249223280685559491369393277114405166293011856168173778428700718404816038991911974902005969923746846815798515831172402122367026339135245751136695128279659872423027539333024854133659
c1 =1408937404754902028814920445701404613476983383738408959873219805755187459225302977012340464647741276263048769176603562703588286152102079561897286480939341184453940846603761664643956274520695676061184610702912592321357240109665885587701906369214592438887065694062151546241739122722790261888290706296747328780758965559093085406877315628139811554345214347799361309288949307776501119359571116522001853935560023530705364795364624152061166945046882418058831567088890277747158775876953662285842999920594778445526224560016361787941610542255000514402493843548068271595134879195073239601085319795505131267697387692179944010772
c2 =12175155463891225370775786368564999885751076529394005420368968241428058465831204925081389807872272508968531564921996276054143112205083003561546962102395368677755381589762565680900651699885381615975236663522025080384481537727180649424984636506390139648492522347366656322729441290553251505232488994951243521740296115895651926783520321289129993169836271218322014443396220481361007479796234525990954874013729001502984583162486353287639655447340498584591591009224750835072707121652727119580764546240945763088815277130694950594020142961659318737857067755125666395542079926757603295535345281657293981259718286213812909191174
e = 65537

t = gmpy2.gcd(n1,n2)
if t != 1:
    p = t
    q = n1 // p
    d = gmpy2.invert(e,(p-1)*(q-1))
    print(long_to_bytes(pow(c1,d,n1)))

九、dp泄露

原理推导

$$
\because d_p \equiv d \mod (p-1)
$$

左右同乘e得

$$
d_p\times e \equiv d\times e \mod (p-1)
$$
即
$$
d\times e = k_1(p-1) +d_p\times e
$$

$$
\because d\times e \equiv 1 \mod \phi(n)
$$

$$
\therefore d\times e = k_2(p-1)(q-1)+1
$$

$$
\therefore k_1(p-1)+dp×e = k_2(p-1)(q-1)+1
$$

化简得

$$
d_p\times e = (p-1)[k_2(q-1)-k_1] + 1
$$

$$
\because d_p < p-1
$$

$$
\therefore 0< k_2(q-1)-k_1
$$

遍历$i \in (0,e)$的所有值，如果$d_p\times e-1$能够整除$i$则，我们就可以求得$p-1$

例题1

task.py

import gmpy2
import libnum
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
m = libnum.s2n(flag)
p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
e = 65537
n = p * q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
print("d=",d)
dp = d % (p - 1)
c = pow(m, e, n)
print("n=", n)
print("e=", e)
print("c=", c)
print("dp=", dp)

exp.py

from Crypto.Util.number import long_to_bytes
import gmpy2

n = 17954000555185130679232377513216924086370205717680723426279833171815673097846434355592747466782173529597978954062272371758852339605432963940809244445748900431763988392120156128524694217746804744076348205536430811607694098089294013508111154514184079159181563040241302764793111632189829652065825442796716027051750043654503172469553222784393034067341575558782690547449884992414106322578261286526556856377419622164651917718772498388922129465042492616904419638034789576380038341882418547113136903862482397767904921157094396562770484669239932933837196899640811033424030302285885080504355934919967693498648701839252087380477
c = 1808490145328726635638705291306162339133116115672167390186563455429486046847680827004544020052978814401354685508506555963361065725012891622174617670820924531959433674273579973778657669162210657120785539629874456938159379512635932223403818177582242406964621317531188027900758868453176575753681627336133481701182056262584118645398172089436811174776978418919803975809158758707062473122656821152108292060156091196577573172937093806159669057467094718771367509856968694209472630329096814023864642219783061245777457366202879949123915168571990229277326042767587009623951348541055835347386485900505749475571895673653225741649
dp =114993440308125678369350484461242628405806013372930792337329972720600942891053460367721272956155528263465552939386621554396883112994907299126303463171544968629898544811159986442249990975328659373544491636958873255689808151391606942912468529923159009459712396428051292828093059494024457367637991626193487727331
e =65537

for i in range(1,e):
    t = (dp * e - 1) % i        #这是p-1前面的系数
    if t == 0:
        p = (dp * e - 1) // i + 1
        if n % p == 0:
            q = n // p
            d = gmpy2.invert(e,(p-1)*(q-1))
            print(long_to_bytes(pow(c,d,n)))

例题2 e很大

task.py

import gmpy2
import libnum
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)
p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
e = libnum.generate_prime(128)
n = p * q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)

dp = d % (p - 1)
c = pow(m, e, n)
print("n=", n)
print("e=", e)
print("c=", c)
print("dp=", dp)

在e很大的情况下，我们爆破$(0,e)$的值就显得不现实。需要用其他方法
$$
\because d_p \times e = k(p-1)+1
$$

$$
\therefore dp ×e \equiv 1 \mod (p-1)
$$

取一个与$p$互素的常数$a$，则有

$$
a^{d_p\times e} \equiv a^{k(p-1)+1} \equiv a \mod p
$$

$$
\therefore a^{dp×e}-a =kp
$$

然后与n求公因数即可得到p

exp.py

from Crypto.Util.number import getPrime,long_to_bytes
import gmpy2

n= 18150086749964030204952772593650655354407282168407543480518017821905322058792108409169209539752974177937328703466169798097779231540410352308736251888449285307132274903811942187361234788236374036493935354342502760429195828731474432692281516115002087485890105917067613983079156790015275611914738187418424730456416770000646598861170179898016595068557049151791620868027603590052357726580431487083778514163249201637184318559165989454489485258667170883129099757366657203826319909509544670881866298317938263281638296241860739828567999093491297970389142395080780768892194380031018324855383292685388767246393785705551231780899
e= 278817530653170259039233683650169866189
c= 10813189255953686674328168562592345253502176950586624384555229875947895107088800774325110599057171743065073092283651992594106863499561887773348061509184951920329015539552207920010924284253109754443530283215130327152416667309504455641730629770856098336299767661535526880065006664806270833698497579073641076473649621250873969544362062393319711114090739414415757921473984666129110213417578310035188480139392986280529932137364474426391469019554935239234968517869914506321750458197587849623935306068749435995413807906558975073047215241796461878288003366415184144140612947217041288538376514085070670565572628317388808356563
dp= 25015362092988139281045705051525732988903355826221062953430054346210238749256645995431509510448988062597830708438496723137288693056422683942336451600173722142331077900759633024803467824277121463213906905346623305038031660927650043841899168305106293747254814365869018331032172781810238397508103692878400636333

a = getPrime(10)

p = gmpy2.gcd(pow(a,dp*e,n)-a,n)    #pow(a,dp*e,n)-a 就是kp
m = pow(c,dp,p)
print(long_to_bytes(m))

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

关于m = pow(c,dp,p)的证明

很多题目会出现在mod p下求解的情况，需要注意的是前提条件为$m < p$，证明如下
$$
\because c \equiv m^e \mod n
$$

$$
ed \equiv 1 \mod \phi(n)
$$

$$
d_p \equiv d \mod p-1
$$

所以有
$$
e \times d_p \equiv 1 \mod p-1
$$
即
$$
e\times d_p = k \times (p-1) + 1
$$

$$
\therefore c ^{d_p} \equiv m ^{e\times d_p} \equiv m ^{k(p-1)+1} \equiv m \mod p
$$

例题3 dp高位泄露

e不是很大

$$
\because ed_p \equiv 1 \mod p-1
$$

$$
\therefore e(d_{phigh} + x) \equiv 1 \mod p-1
$$

$$
\therefore e(d_{phigh} + x) = k(p-1) + 1
$$

$$
\therefore e(d_{phigh}+x) + k - 1\equiv 0 \mod p
$$

如果e不大的话，直接爆破k解这个方程即可

e很大

task.py

from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p * q
e = getPrime(64)
d = inverse(e,(p-1)*(q-1))

dp = d % (p-1)
leak = dp >> 64 << 64
c = pow(m,e,n)
print(f"n = {n}")
print(f"c = {c}")
print(f"e = {e}")
print(f"leak = {leak}")
"""
n = 108867023585283899312601516631596145998654767437612286040742902945694826711187570537876759789643259431350352590412655898964386234903475482280911808566497936037152171435317938413515356868240854632004961172899360272761406519077380255802700944002126599829184693692273637230349297388495886988988512631044494610227
c = 55610391226438079690691299914193010897347055835338032942001645697966587672596937470425142446679815934940962159432814479063990621696064239924347523289515556844359094065042974221093712989000153444928594999529082105262409273370242062803004814801742763253605838374098344711160380314529928211369000469059015996052
e = 14257237624892167181
leak = 2451130625204471881762267484243564297625381377098677997721378436579042927693972537775392209546509688501306219327699327137859174235486735043842710630825984
"""

$$
\because ed_p \equiv 1 \mod p-1
$$

$$
\therefore e(d_{phigh} + x) \equiv 1 \mod p-1
$$

$$
\therefore e(d_{phigh} + x) = k(p-1) + 1
$$

$$
\therefore e(d_{phigh}+x) + k - 1\equiv 0 \mod p
$$

k和x都是64bit的值，用二元copper即可

exp

from Crypto.Util.number import *
import gmpy2
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
        print(d)
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

n = 108867023585283899312601516631596145998654767437612286040742902945694826711187570537876759789643259431350352590412655898964386234903475482280911808566497936037152171435317938413515356868240854632004961172899360272761406519077380255802700944002126599829184693692273637230349297388495886988988512631044494610227
c = 55610391226438079690691299914193010897347055835338032942001645697966587672596937470425142446679815934940962159432814479063990621696064239924347523289515556844359094065042974221093712989000153444928594999529082105262409273370242062803004814801742763253605838374098344711160380314529928211369000469059015996052
e = 14257237624892167181
leak = 2451130625204471881762267484243564297625381377098677997721378436579042927693972537775392209546509688501306219327699327137859174235486735043842710630825984

R.<x,y> = PolynomialRing(Zmod(n))
f = e * (leak + x) + (y - 1)
res = small_roots(f,(2^64,2^64),m=1,d=3)
for root in res:
    dp_low = root[0]
    dp = leak + dp_low
    tmp = pow(2,e*dp,n) - 2
    p = gmpy2.gcd(tmp,n)
    q = n // p
    d = inverse(e,(p-1)*(q-1))
    m = pow(c,d,n)
    print(long_to_bytes(m))

十、dp,dq泄露

如果题目给出$p,q,d_p,d_q$，那么直接在模p和模q下求解即可，如果模不够大，再用中国剩余定理即可

例题1

task.py

import gmpy2
import libnum
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
m = libnum.s2n(flag)
p = libnum.generate_prime(256)
q = libnum.generate_prime(256)
e = 65537
n = p * q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
print("d=", d)
dp = d % (p - 1)
dq = d % (q - 1)
c = pow(m, e, n)

print("p=", p)
print("q=", q)
print("c=", c)
print("dp=", dp)
print("dq=", dq)

exp.sage

import gmpy2
from Crypto.Util.number import *

p = 112454994630978850005784651276022327545786198205744597431888680937657203192943
q = 111081771780978300442208201256251933100607227308819156491182881723714968913833
c = 7847140580627012782899798457736961376953768684667159008470556786390887805253326211691923724846808704462396746105331991924048819814322540306282164012066426
dp = 99016059099144522019375365089687785694029213535292918424815544402513220169503
dq = 79504900574184798493105575420403885224379864982754477219462523963780735261625
n = p*q

mp = pow(c,dp,p)
mq = pow(c,dq,q)
print(long_to_bytes(mp))
print(long_to_bytes(mq))

m = crt([mp,mq],[p,q])
print(long_to_bytes(m))

十一、考察欧拉函数计算

欧拉函数计算方法:

1. $n = 1$，则$\phi(n)= 1$

2. $n$是素数，则$\phi(n) = n - 1$

3. $n = p^r$($p$为素数，$r$为大于等于1的整数)，则$\phi(n) = p^{r-1}(p-1)$

4. $n = \prod_{i=1}^kp_i$，则$\phi(n) = \prod_{i=1}^{k}(p_i-1)$

例题1

task.py

import gmpy2
import libnum
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
m = libnum.s2n(flag)
p = libnum.generate_prime(512)
n = p ** 5
e = 65537
c = pow(m, e, n)
print("n=", n)
print("e=", e)
print("c=", c)

本题考查$n = p^r$

exp.py

from Crypto.Util.number import *
import gmpy2

n = 109671394618534156590716540772306636060550711465455829526382945168271125218007503161807386153286648328529071790130095763349089936429151343426469415497138306284842512691195220650548494501337831207724397925027651025644976364368511262187227825083865690186591571250267479440100917127211656877566179258870510690665025580200477574123634259670039152125607834855408269848826938902407472374892693266119859709658788565014195766992713646832624001067898323913639712284673673557898135411273837250194079399384826384835709060797351332323930309379071015140548478132323474993964925055399350661600068568602468295748573856804293659942047543032878436316918991716636681116631322082919386178460096115355963882313682994343822128626370850455024905542367255179074441679461101331332093019368492643
e = 65537
c = 83166081100602571613112201467626632459949037182633475449066025299006894059443612622701975752551708249083077180755342065457682925338233793688583913228361068561515321097016501900442865692643652803949920987493441500744743553498018003210308290969303190355756775977367324120441564693220728163622472865572357639056734898022442794130514936425334924283145153496702507951466618177405870656868713199816223765264228006032228439676574053839549440372521050502986043855511540855864034336902304414848547480112182226920285820386643015671106933140105835060319823245206934565859078021518312305243997612804935774414840491355098017977514736057368000596388974956265042651277403519473262257945986199408278855335170546242641727930526697102351648388874227840119205560199015181257296591985205818
p = 10186351850605898834333098258639828910824016865517013383611935945131883947448223014077315468253377357594775340263769153442019216205089695821439736926082483

phi = p**5-p**4
d = gmpy2.invert(e,phi)
print(long_to_bytes(pow(c,d,n)))

例题2

task.py

import gmpy2
import libnum
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)
p = libnum.generate_prime(512)
q = libnum.generate_prime(512)
n = p ** 3 * q
e = 65537
c = pow(m, e, n)
print("q=", q)
print("n=", n)
print("e=", e)
print("c=", c)

$\because n = p^{3}×q$

$\therefore \phi(n) = (p^{3}-p^{2})×(q-1)$

exp.py

from Crypto.Util.number import long_to_bytes
import gmpy2

q = 13345672330679418443866848695749753384841350112452462690350565885192764753702964893062035116023096943358384379827500462723016224486435032522188166109529147
n = 4663711063632671446966617442890809468548735750386480905820144168615122369358088158709822723959108989276525102755551604204514586528122441075489492157644479194671784485228731421500391142158401889177506319977349707503678947872777602384171260874359045585814189677748712566088220734735479518470883541166059233676170283938881683675790979128058243582825012415020019043126740915522571217495119060031729061070896580899732991209113679151755713858497630999746612658308778711613697038750661479517187094033129979714688161348844542070263109259258937863241431480105798790363889436471998002323269704182369356300287043940743500087239
e = 65537
c = 4050303218893912343776312253598257474375000778822229482734626960955864773175090306426885201033332266573903303684635688485414725284644108123459136702775991157244389086147955395682206311752151842740679445903864544823592773331496589661187968392779340028173948172003460012051289357755574536619241969492822938688821287700132262703677149526846356206143053559703859606442209340834979412336031660590507709503830013770022485005101363701272279629510056964018618212014677531338026866748075406283893942248599825641124694672878533987994699411744521757385858889763503705242690212615083634186373933214686193717950163215308138805348

p = n // q 
phi = (p**3-p**2)*(q-1)
d = gmpy2.invert(e,phi)
print(long_to_bytes(pow(c,d,n)))

例题3

task.py

import gmpy2
import libnum
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)
p = libnum.generate_prime(512)
q = gmpy2.next_prime(p)
r = libnum.generate_prime(512)
n = p * q * r
e = 65537
c = pow(m, e, n)
print("r=", r)
print("n=", n)
print("e=", e)
print("c=", c)

r = 12328943069972158868300333965019293732240349172933398867374450193780676916633106046545397891902123683693837126404908611670219604587587151306224914062663729
n = 928445951911850156618541782850215900925329423880533465612155142015978599609287623859912813317551629221695490535012732781489396534420011145723987610606038091488823086647363964394753700158320900867101659445170118179077194271099520502633316318889163873291574934282498061117736456183503867870294570083013883365868242889035609602940685335912371326827533418614992221705810476710807373254363162373986374486325350746366851935451369892949745302442034805629514003196071631
e = 65537
c = 327716655224470059950709685055600963837116578216483343492948888372401723689223347212508532985781828794786448842515029515358422017875793926582832247025212149474404973170422295165602666360784347416812528617973764432916955654602356835327769633635513894485943553309743509322858937973710628023758816806471875016815994664897320150855163109437521642800230902661034555151514311149333258071668655344069451897282357234220538922127548822361859943829665459953651351620958628

$$
\because n = p\times q \times r
$$

$$
\therefore \phi(n)=(p-1)×(q-1)×(r-1)
$$

exp.py

from Crypto.Util.number import long_to_bytes
import gmpy2

r = 12328943069972158868300333965019293732240349172933398867374450193780676916633106046545397891902123683693837126404908611670219604587587151306224914062663729
n = 928445951911850156618541782850215900925329423880533465612155142015978599609287623859912813317551629221695490535012732781489396534420011145723987610606038091488823086647363964394753700158320900867101659445170118179077194271099520502633316318889163873291574934282498061117736456183503867870294570083013883365868242889035609602940685335912371326827533418614992221705810476710807373254363162373986374486325350746366851935451369892949745302442034805629514003196071631
e = 65537
c = 327716655224470059950709685055600963837116578216483343492948888372401723689223347212508532985781828794786448842515029515358422017875793926582832247025212149474404973170422295165602666360784347416812528617973764432916955654602356835327769633635513894485943553309743509322858937973710628023758816806471875016815994664897320150855163109437521642800230902661034555151514311149333258071668655344069451897282357234220538922127548822361859943829665459953651351620958628

t = gmpy2.iroot(n//r,2)[0]
p = gmpy2.next_prime(t)
q = n // p // r

phi = (p-1)*(q-1)*(r-1)
d = gmpy2.invert(e,phi)
print(long_to_bytes(pow(c,d,n)))