[CISCN 2024] Crypto部分復現

文章目錄

- OvO
- ez_rsa
- checkin
- 淺記一下

遲來的文章

OvO

題目描述：

from Crypto.Util.number import *
from secret import flagnbits = 512
p = getPrime(nbits)
q = getPrime(nbits)
n = p * q
phi = (p-1) * (q-1)
while True:kk = getPrime(128)rr = kk + 2e = 65537 + kk * p + rr * ((p+1) * (q+1)) + 1if gcd(e, phi) == 1:break
m = bytes_to_long(flag)
c = pow(m, e, n)e = e >> 200 << 200
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')"""
n = 111922722351752356094117957341697336848130397712588425954225300832977768690114834703654895285440684751636198779555891692340301590396539921700125219784729325979197290342352480495970455903120265334661588516182848933843212275742914269686197484648288073599387074325226321407600351615258973610780463417788580083967
e = 37059679294843322451875129178470872595128216054082068877693632035071251762179299783152435312052608685562859680569924924133175684413544051218945466380415013172416093939670064185752780945383069447693745538721548393982857225386614608359109463927663728739248286686902750649766277564516226052064304547032760477638585302695605907950461140971727150383104
c = 14999622534973796113769052025256345914577762432817016713135991450161695032250733213228587506601968633155119211807176051329626895125610484405486794783282214597165875393081405999090879096563311452831794796859427268724737377560053552626220191435015101496941337770496898383092414492348672126813183368337602023823
"""

題目分析：
$1\\e = (k + 2)n + (2k + 2)p + (k + 2)q + (k + 65540)\\ \Rightarrow k + 2 = e // n，k = e // n - 2\\ 令e中已知的項都為a，即a = (k + 2)n + k + 65540\\e = (2k + 2)p + (k + 2)q + a\\e p = (2k + 2)p^2 + (k + 2)n + ap\\目前是e的低200位未知，等式又已知\\ 那么具體解法可以參考d的高位攻擊，很快便能出結果的$
exp:

# sagemath
from Crypto.Util.number import *def get_full_p(p_high, n, bits):PR.<x> = PolynomialRing(Zmod(n))    f = x + p_highf = f.monic()roots = f.small_roots(X=2^(bits + 10), beta=0.4)  if roots:x0 = roots[0]p = gcd(x0 + p_high, n)return ZZ(p)n = 111922722351752356094117957341697336848130397712588425954225300832977768690114834703654895285440684751636198779555891692340301590396539921700125219784729325979197290342352480495970455903120265334661588516182848933843212275742914269686197484648288073599387074325226321407600351615258973610780463417788580083967
e = 37059679294843322451875129178470872595128216054082068877693632035071251762179299783152435312052608685562859680569924924133175684413544051218945466380415013172416093939670064185752780945383069447693745538721548393982857225386614608359109463927663728739248286686902750649766277564516226052064304547032760477638585302695605907950461140971727150383104
c = 14999622534973796113769052025256345914577762432817016713135991450161695032250733213228587506601968633155119211807176051329626895125610484405486794783282214597165875393081405999090879096563311452831794796859427268724737377560053552626220191435015101496941337770496898383092414492348672126813183368337602023823k = e // n - 2
a = 65537 + (k + 2) * n + (k + 2) + 1
P.<x> = PolynomialRing(RealField(1024))
f = e * x - ((2 * k + 2) * x ^ 2 + (k + 2) * n + a * x)
res = f.roots()if res:for y in res:p_high = int(y[0])p = get_full_p(p_high, n, 200)if p:print(p)   # python
from Crypto.Util.number import *
n = 111922722351752356094117957341697336848130397712588425954225300832977768690114834703654895285440684751636198779555891692340301590396539921700125219784729325979197290342352480495970455903120265334661588516182848933843212275742914269686197484648288073599387074325226321407600351615258973610780463417788580083967
e = 37059679294843322451875129178470872595128216054082068877693632035071251762179299783152435312052608685562859680569924924133175684413544051218945466380415013172416093939670064185752780945383069447693745538721548393982857225386614608359109463927663728739248286686902750649766277564516226052064304547032760477638585302695605907950461140971727150383104
c = 14999622534973796113769052025256345914577762432817016713135991450161695032250733213228587506601968633155119211807176051329626895125610484405486794783282214597165875393081405999090879096563311452831794796859427268724737377560053552626220191435015101496941337770496898383092414492348672126813183368337602023823
k = e // n - 2
p = 9915449532466780441980882114644132757469503045317741049786571327753160105973102603393585703801838713884852201325856459312958617061522496169870935934745091
q = n // p
print(n % p)
e = 65537 + k * p + (k + 2) * ((p+1) * (q+1)) + 1
phi = (p - 1) * (q - 1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))

ez_rsa

題目描述：
ezrsa.py:

from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import random
from secret import flagm = bytes_to_long(flag)
key = RSA.generate(1000)
passphrase = str(random.randint(0,999999)).zfill(6).encode()
output = key.export_key(passphrase=passphrase).split(b'\n')
for i in range(7, 15):output[i] = b'*' * 64
with open("priv.pem", 'wb') as f:for line in output:f.write(line + b'\n')
with open("enc.txt", 'w') as f:f.write(str(key._encrypt(m)))

enc.txt:

55149764057291700808946379593274733093556529902852874590948688362865310469901900909075397929997623185589518643636792828743516623112272635512151466304164301360740002369759704802706396320622342771513106879732891498365431042081036698760861996177532930798842690295051476263556258192509634233232717503575429327989

priv.pem:

題目分析：
第一部分先略過吧，不想看
直接跳到后面階段
得到的數據有：

n = 0x00a18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c81
e = 0x10001
inv = 0x5f152c429871a7acdd28be1b643b4652800b88a3d23cc57477d75dd5555b635167616ef5c609d69ce3c2aedcb03b62f929bbcd891cadc0ba031ae6fec8a2116d
dqlow = 0x8f2363b340e5

看這里之前我覺得可以先來看看下面這題

checkin

題目描述：

from Crypto.Util.number import *
from secret import flagp = getPrime(512)
q = getPrime(512)
n = p*q
x = 2021*p+1120*q
h = (inverse(x,n)+x)%n
e = 65537
c = pow(bytes_to_long(flag), e, n)print('n =', n)
print('c =', c)
print('h =', h)
print('p0 =', p >> 490)# n = 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793
# c = 119279592136391518960778700178474826421062018379899342254406783670889432182616590099071219538938202395671695005539485982613862823970622126945808954842683496637377151180225469409261800869161467402364879561554585345399947589618235872378329510108345004513054262809629917083343715270605155751457391599728436117833
# h = 115812446451372389307840774747986196103012628652193338630796109042038320397499948364970459686079508388755154855414919871257982157430015224489195284512204803276307238226421244647463550637321174259849701618681565567468929295822889537962306471780258801529979716298619553323655541002084406217484482271693997457806
# p0 = 4055618

題目分析：
已知：
$\begin{align*} & x = 2021p + 1120q\\ & h \equiv x + \frac{1}{x} \pmod n\\ & p0 = p的高22位\\ & 目前知道了n,c,h,p0\\ \end{align*}\\$
$x^2 + 1 - hx \equiv 0 \pmod n ①\\ 借助p0計算出x的一個近似估計x0\\ x0= 2021 * (p_0 << 490) + 1120 * (\frac{N}{p_0 << 490})\\ x和x0之間的誤差x\_diff最多是501位，大概500位左右的樣子\\ 所以我們將x\_diff當作一個新的未知量通過①式來構造等式，之后使用copper求出\\ f(x\_diff) = (x0 + x\_diff) ^ 2 + 1 - h * (x0 + x\_diff)$

現在的重點是small_roots()里面的參數要怎么設置
先來點前置知識（怕自己又忘了）：

X:所求根的上界

beta $(\beta)$ :限定因子，滿足 $N^{\beta}$ ，默認值為1 (所以此情況下b = N)。（找到 f(x)
= 0 的一個解，使它在模 n 的某個因子時成立，此時這里說的某個因子即為b，在rsa中n = p * q，只有兩個因子，故此時的b即p或q。一般我們遇到的題中p,q位數都是相等的，故beta可取0.5，但更多情況下我們并不知道p,q哪個大，所以保險起見beta通常取0.4)

epsilon $(\epsilon)$ :限定因子，默認值為 $\beta / 8$

d:f(x)的度，高位攻擊中d = 1

在方程F(x)，模數N確認的情況下，我們可以通過增加 $\beta$ 的取值或減小 $\epsilon$ 的取值，使得X取到更優的上界。

我們知道上界 $ceil(\frac{1}{2} * N^{\frac{\beta^2}{d} - \epsilon})$ (向上取整)
現在，已知d = 2，beta = 1，X有500位未知，我們取epsilon = 0.01是完成能夠得到結果的，但我們也知道epsilon越小，耗時越長，我們試著把epsilon調大一點，讓epsilon = 0.02，看看能否出結果。經過測試也是能出結果的，那么就用它啦
把x_diff求出來了，后面就簡單了，這也就不多說了

from Crypto.Util.number import long_to_bytesN = 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793
c = 119279592136391518960778700178474826421062018379899342254406783670889432182616590099071219538938202395671695005539485982613862823970622126945808954842683496637377151180225469409261800869161467402364879561554585345399947589618235872378329510108345004513054262809629917083343715270605155751457391599728436117833
h = 115812446451372389307840774747986196103012628652193338630796109042038320397499948364970459686079508388755154855414919871257982157430015224489195284512204803276307238226421244647463550637321174259849701618681565567468929295822889537962306471780258801529979716298619553323655541002084406217484482271693997457806
p0 = 4055618p_high = p0 << 490
x0 = 2021 * p_high + 1120 * (N // p_high)P.<x_diff> = PolynomialRing(Zmod(N))
f = (x0 + x_diff)^2 + 1 - h * (x0 + x_diff)res = f.small_roots(X = 2^500, epsilon = 0.02)
x_diff = Integer(res[0])x = x0 + x_diffp = var('p')
q = var('q')
res = solve([x == 2021 * p + 1120 * q, N == p * q], p, q)
print(res)
p = Integer(res[0][0].rhs()) # 提取等號右邊部分
q = Integer(res[0][1].rhs())d = inverse_mod(65537, (p - 1) * (q - 1))
print(long_to_bytes(int(pow(c,d,N))))

進入主題
國賽ez_rsa
題目描述：
(就截取這么一點點了）

n = 0x00a18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c81
e = 65537
inv = 0x5f152c429871a7acdd28be1b643b4652800b88a3d23cc57477d75dd5555b635167616ef5c609d69ce3c2aedcb03b62f929bbcd891cadc0ba031ae6fec8a2116d
dqlow = 0x8f2363b340e5

題目分析：

方式1
$\begin{align*} & dq \equiv d \pmod{q - 1} \\ & dq \cdot e \equiv d \cdot e \equiv 1 \pmod{q - 1} \\ & dq \cdot e - 1 = k \cdot (q - 1) \\ & dq \cdot e + k - 1 = kq \\ & 我們目前已知的有dq的低48位和inv（其中inv \cdot q \equiv1 \pmod p）\\ & 又知道:\\ & inv \cdot q - 1 = k_1 \cdot p\\ & 想的是乘個q，得到：inv\cdot q\cdot q - q = k_1 \cdot n\\ & 然后inv \cdot q^2 - q \equiv 0 \pmod n，之后解方程\\ & 不過后面發現運行不出結果\\ & 被指出了問題：只有kq，并沒有q，確實，是我分析沒有到位\\ & 所以換一個：\\ & inv \cdot kq \equiv k \pmod p\\ & inv \cdot kq - k = k_2 \cdot p\\ & inv \cdot (kq)^2 - k \cdot kq = k \cdot k_2\cdot n \equiv 0 \pmod n\\ & 令f = inv \cdot (kq)^2 - k \cdot kq \ 之后去解方程 \end{align*}$
解方程的過程和上題的思路應該來說是一樣的
這里也是d = 2，beta = 1，所以關鍵部分還是落在了epsilon 的取值上，這個就自己去生成數據測一測，從0.05往上加，發現到0.09以后解集為空，那么設置成0.09就行

exp:

from Crypto.Util.number import *
from tqdm import *n = 0x00a18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c81
e = 0x010001
dqlow = 0x8f2363b340e5
inv = 0x5f152c429871a7acdd28be1b643b4652800b88a3d23cc57477d75dd5555b635167616ef5c609d69ce3c2aedcb03b62f929bbcd891cadc0ba031ae6fec8a2116d
c = 55149764057291700808946379593274733093556529902852874590948688362865310469901900909075397929997623185589518643636792828743516623112272635512151466304164301360740002369759704802706396320622342771513106879732891498365431042081036698760861996177532930798842690295051476263556258192509634233232717503575429327989
bits = 48PR.<x> = PolynomialRing(Zmod(n))
dq = (2 ^ bits * x) + dqlow
# k = 47794
for k in trange(e,1,-1):f = inv * (e * (2 ^ bits * x + dqlow) - 1 + k) ^ 2 - k * (e * (2 ^ T * x + dqlow) - 1 + k)f = f.monic()root = f.small_roots(X=2 ^ (512 - bits), epsilon = 0.09)if root:dq = int(root[0]) * 2 ** bits + dqlowq = int((e * dq - 1) // k + 1)p = int(n // q)phi = (p - 1) * (q - 1)d = inverse_mod(e,phi)print(long_to_bytes(int(pow(c,d,n))))break

方式2
回到解法1里面說的那句" $想的是乘個q，得到：inv\cdot q\cdot q - q = k_1 \cdot n \equiv 0 \pmod n$ "
既然如此，那我們就來求q，我們知道了dq的低48位，那么我們可以通過 $dq \cdot e + k - 1 = kq$ 該式子求得q的低48位
之后令 $f = inv * (2 ^{bits} * x + q\_low) ^ 2 - (2 ^{bits} * x + q\_low)$
解方程后即可得到flag

是的這里的epsilon最大也是0.09

from tqdm import *
from Crypto.Util.number import *
n = 0x00a18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c81
inv = 0x5f152c429871a7acdd28be1b643b4652800b88a3d23cc57477d75dd5555b635167616ef5c609d69ce3c2aedcb03b62f929bbcd891cadc0ba031ae6fec8a2116d
c = 55149764057291700808946379593274733093556529902852874590948688362865310469901900909075397929997623185589518643636792828743516623112272635512151466304164301360740002369759704802706396320622342771513106879732891498365431042081036698760861996177532930798842690295051476263556258192509634233232717503575429327989
dq_low = 0x8f2363b340e5
q_low = []
bits = 48
e = 65537
qq = var('qq')PR.<x> = PolynomialRing(Zmod(n))
# k = 47794
for k in trange(e,1,-1):k = 47794q0 = solve_mod([e * dq_low == k * qq - k + 1], 2^bits)for i in q0:f = inv * (2 ^ bits * x + int(i[0])) ^ 2 - (2 ^ bits * x + int(i[0]))f = f.monic()root = f.small_roots(X = 2^(512-bits), epsilon = 0.09)if root:q = 2^bits * int(root[0]) + int(i[0])p = n // qd = inverse_mod(e,(p - 1) * (q - 1))print(long_to_bytes(int(pow(c,d,n))))break# flag{df4a4054-23eb-4ba4-be5e-15b247d7b819}

這種方式更費時（不過多開幾個在比賽過程中也是能出的）開始確實是這種想法來著，后面beta又寫了個0.4，導致最終沒出結果，該死啊。
應該就是這個原因，導致又對它重溫了一遍。
現在應該可以這樣說，之前對coppersmith的理解是1/3，這次之后變成了2/3
所以說數據測試真的是很重要啊！

淺記一下

OvO這題，有人問為什么不能用ZZ，要用RealField
細想一下就是用ZZ無解，為什么會無解，因為它的解是小數，而不是整數，故不能用ZZ。
RealField(1000)創建一個精度為1000位的實數環，即可以得到小數點后1000位精確值，之后的可以舍棄，比如如果得到的解是無理數，那么用它可以得到一個確切的值，而不是一個無限長小數

~~其他題，等以后有空再來吧~~