[CISCN 2024] Crypto部分复现

文章目录

- OvO
- ez_rsa
- checkin
- 浅记一下

迟来的文章

OvO

题目描述：

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

nbits = 512
p = getPrime(nbits)
q = getPrime(nbits)
n = p * q
phi = (p-1) * (q-1)
while True:
    kk = getPrime(128)
    rr = kk + 2
    e = 65537 + kk * p + rr * ((p+1) * (q+1)) + 1
    if 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_high
    f = 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 = 14999622534973796113769052025256345914577762432817016713135991450161695032250733213228587506601968633155119211807176051329626895125610484405486794783282214597165875393081405999090879096563311452831794796859427268724737377560053552626220191435015101496941337770496898383092414492348672126813183368337602023823

k = 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 flag

m = 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 flag

p = 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_bytes

N = 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793
c = 119279592136391518960778700178474826421062018379899342254406783670889432182616590099071219538938202395671695005539485982613862823970622126945808954842683496637377151180225469409261800869161467402364879561554585345399947589618235872378329510108345004513054262809629917083343715270605155751457391599728436117833
h = 115812446451372389307840774747986196103012628652193338630796109042038320397499948364970459686079508388755154855414919871257982157430015224489195284512204803276307238226421244647463550637321174259849701618681565567468929295822889537962306471780258801529979716298619553323655541002084406217484482271693997457806
p0 = 4055618

p_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_diff

p = 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 = 48

PR.<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 + dqlow
        q = 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 = 47794
    q0 = 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 // q
            d = 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位精确值，之后的可以舍弃，比如如果得到的解是无理数，那么用它可以得到一个确切的值，而不是一个无限长小数

~~其他题，等以后有空再来吧~~