2024HDCTF

发表于 分类于 阅读次数： Waline： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

记录2024HDCTF——Crypto题解

”燃烧“自己打满周末，接下来的时间该准备期末考了

CF

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import hashlib
from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flag

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
s = getPrime(512)
n = p * q * r * s
d = getRandomRange(1, int(n**0.127))
e = inverse(d, (p - 1) * (q - 1) * (r - 1) * (s - 1))
key = hashlib.md5(str(p + q + r + s).encode()).digest()
aes = AES.new(key, mode=AES.MODE_ECB)
print(n)
print(e)
print(aes.decrypt(flag))
# 12778528771742949806245151753869219326103790041631995252034948773711783128776305944498756929732298934720477166855071150429382343090525399073032692529779161146622028051975895639274962265063528372582516292055195313063685656963925420986244801150981084581230336100629998038062420895185391922920881754851005297105551156140379014123294775868179867798105218243424339964238809811837555910593108364135245826360599234594626605066012137694272914693621191616641820375665250179042481908961611154276842449520816511946371478115661488114557201063593848680402471689545509362224765613961509436533468849519328376263878041094637028661183
# 4446726708272678112679273197419446608921686581114971359716086776036464363243920846432708647591026040092182012898303795518854800856792372040517828716881858432476850992893751986128026419654358442725548028288396111453301336112088168230318117251893266136328216825852616643551255183048159254152784384133765153361821713529774101097531224729203104181285902533238977664673240372553695106609481661124179618839909468411817548602076934523684639875632950838463168454592213740967654900802801128243623511466324869786575827161573559009469945330622017702786149269513046331878690768979142927851424854919322854779975658914469657308779
# b'_\xf7\x16\x00S\x11\xd5\xec\x94+>\x98\x91\x8b\xaeC\xadV3\xf8\x07a\x95\xf6rr\x86\xd4\x1e\x1b\xe7\xf4H\xa0\xd9\x9b\xb5\x05.u\x08\x80\x04\x8d\xee\xec\x98\xf5'

这题做的有点非预期….感觉莫名其妙哈哈

四个素数，而且d蛮小的，估摸着是谋篇论文。用关键词Multi-prime RSA，small private exponent

找到一篇名叫On Some Attacks on Multi-prime RSA，3-540-36492-7_25.pdf (springer.com)

文章中提到r-prime modulus and $d < N^{\frac{1}{2r}} / \sqrt{2(2r-1)}$情况下的连分数展开，不巧的是这题的d并不满足条件。

继续往下看，文章提到了用boneh-durfee来攻击，然后自己改了改参数就出了

主要改的就是delta，m，Y

关键是这个Y，原本的板子是Y = floor(N^(1/2))，因为Y代表的是$n - \phi(n)$，所以这里改为$\frac{3}{4}$

然后一直把m改大就解出了d = 1602880683536635795876091613927500882436617854256464157042708767806743324582851

然后就是已知kphi和n，拿板子分解就行

exp.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
n = 12778528771742949806245151753869219326103790041631995252034948773711783128776305944498756929732298934720477166855071150429382343090525399073032692529779161146622028051975895639274962265063528372582516292055195313063685656963925420986244801150981084581230336100629998038062420895185391922920881754851005297105551156140379014123294775868179867798105218243424339964238809811837555910593108364135245826360599234594626605066012137694272914693621191616641820375665250179042481908961611154276842449520816511946371478115661488114557201063593848680402471689545509362224765613961509436533468849519328376263878041094637028661183
e = 4446726708272678112679273197419446608921686581114971359716086776036464363243920846432708647591026040092182012898303795518854800856792372040517828716881858432476850992893751986128026419654358442725548028288396111453301336112088168230318117251893266136328216825852616643551255183048159254152784384133765153361821713529774101097531224729203104181285902533238977664673240372553695106609481661124179618839909468411817548602076934523684639875632950838463168454592213740967654900802801128243623511466324869786575827161573559009469945330622017702786149269513046331878690768979142927851424854919322854779975658914469657308779
c = b'_\xf7\x16\x00S\x11\xd5\xec\x94+>\x98\x91\x8b\xaeC\xadV3\xf8\x07a\x95\xf6rr\x86\xd4\x1e\x1b\xe7\xf4H\xa0\xd9\x9b\xb5\x05.u\x08\x80\x04\x8d\xee\xec\x98\xf5'
d = 1602880683536635795876091613927500882436617854256464157042708767806743324582851

from math import gcd
from math import isqrt
from random import randrange
from gmpy2 import is_prime

def factorize(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method only works for a modulus consisting of 2 primes!
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors, or None if the factors were not found
    """
    s = N + 1 - phi
    d = s ** 2 - 4 * N
    p = int(s - isqrt(d)) // 2
    q = int(s + isqrt(d)) // 2
    return p, q


def factorize_multi_prime(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method works for a modulus consisting of any number of primes, but is considerably be slower than factorize.
    More information: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3)
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors
    """
    prime_factors = set()
    factors = [N]
    while len(factors) > 0:
        # Element to factorize.
        N = factors[0]

        w = randrange(2, N - 1)
        i = 1
        while phi % (2 ** i) == 0:
            sqrt_1 = pow(w, phi // (2 ** i), N)
            if sqrt_1 > 1 and sqrt_1 != N - 1:
                # We can remove the element to factorize now, because we have a factorization.
                factors = factors[1:]

                p = gcd(N, sqrt_1 + 1)
                q = N // p

                if is_prime(p):
                    prime_factors.add(p)
                elif p > 1:
                    factors.append(p)

                if is_prime(q):
                    prime_factors.add(q)
                elif q > 1:
                    factors.append(q)

                # Continue in the outer loop
                break

            i += 1

    return tuple(prime_factors)

factors = factorize_multi_prime(n,e*d-1)
p,q,r,s = factors

from Crypto.Cipher import AES
import hashlib
key = hashlib.md5(str(p + q + r + s).encode()).digest()
aes = AES.new(key, mode=AES.MODE_ECB)
flag = aes.encrypt(c)
print(flag)
# DASCTF{d4d0b2c4-b41d-4ce1-871a-b08325900b30}

ezrsa

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
import random
import hashlib
from secret import flag


gen1 = lambda bits=1024, rand=lambda n: bytes(random.getrandbits(1) for _ in range(n)): (getPrime(bits//2, randfunc=rand), getPrime(bits//2, randfunc=rand))

gen2 = lambda alpha=512, K=500, T=getPrime(506): next(((p, q, T) for q, r in [(getPrime(alpha), getPrime(alpha))] for k in range(2, K+1) if (isPrime(p := r + (k * q - r) % T))), None)

p1,q1=gen1()
p2, q2, T = gen2()
assert flag == "DASCTF{" + hashlib.md5(str(p1 + p2 + q1 + q2).encode()).hexdigest() + "}"
print(p1*q1)
print((p2*q2,T))
# 44945076854246685060397710825960160082061127479194994041436997195972585701097443198954359213635892234058786065342178389181538153413878118039445271277476379366294977408981257175008890470376094381644530106799352839565803317977637572325347776636285703517680754624094985374606187797141657688145287340444623176193
# (57784854392324291351358704449756491526369373648574288191576366413179694041729248864428194536249209588548791706980878177790271653262097539281383559433402738548851606776347237650302071287124974607439996041713554182180186588308614458904981542909792071322939678815174962366963098166320441995961513884899917498099, 150514823288951667574011681197229106951781617714873679347685702558528178681176081082658953342482323349796111911103531429615442550000291753989779754337491)

先理解这两个很长的lambda。

gen1()

gen1()，关键就是把getPrime(bits,randfunc=None)改成了getPrime(bits,randfunc=rand)

我不太清楚randfunc起到什么作用，自己打印几组数据发现，gen1生成的素数每8bit只有2个情况，分别是

00000000 00000001

而高8位必定是10000000

通过这个性质，再利用p * q % 2**l == n % 2**l，写一个剪枝就可以爆出来

gen2()

审计代码可以知道
$$
p_2 = (kq_2-r)\mod T + r
$$

自己可以验证一下，上式和下式在mod T下是等价的
$$
p_2 \equiv kq_2 \mod T
$$
两边同乘$q_2$
$$
n_2 \equiv kq_2^2 \mod T
$$
解这个同余方程，相当于得到$q_{low} \equiv q \mod T$

再对$q_{low}$加上若干个(范围在64以内)T即可求得

exp.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from tqdm import *

n1 = 44945076854246685060397710825960160082061127479194994041436997195972585701097443198954359213635892234058786065342178389181538153413878118039445271277476379366294977408981257175008890470376094381644530106799352839565803317977637572325347776636285703517680754624094985374606187797141657688145287340444623176193
n2,T = (57784854392324291351358704449756491526369373648574288191576366413179694041729248864428194536249209588548791706980878177790271653262097539281383559433402738548851606776347237650302071287124974607439996041713554182180186588308614458904981542909792071322939678815174962366963098166320441995961513884899917498099, 150514823288951667574011681197229106951781617714873679347685702558528178681176081082658953342482323349796111911103531429615442550000291753989779754337491)

def find(p,q,l):
    if l == 504:
        pp = int("10000000"+ p,2)
        qq = int("10000000"+ q,2)
        if n1 % pp == 0:
            print(f"p1 = {pp}")
            print(f"q1 = {qq}")
            return 
    else:
        pp = int(p,2)
        qq = int(q,2)
        if pp * qq % 2**l == n1 % 2**l:
            find("00000001" + p,"00000001" + q,l+8)
            find("00000001" + p,"00000000" + q,l+8)
            find("00000000" + p,"00000001" + q,l+8)
            find("00000000" + p,"00000000" + q,l+8)

def decrypt2():
    for k in trange(2,501):
        R.<x> = PolynomialRing(Zmod(T)) 
        f = k*x^2 - n2
        res = f.roots()
        if res:
            for root in res:
                for i in range(64):
                    low = int(root[0])
                    q = low + i*T
                    if n2 % q == 0:
                        p = n2 // q
                        print(f"p2 = {p}")
                        print(f"q2 = {q}")
                        return
                    
# find("00000001","00000001",8)
# decrypt2()

p1 = 6704109351064115455893295955648034742490075153469647652626278891915863408109665863057399099944508436950445216168956861863970048266975514429634433698038017
q1 = 6704108555018235126044943757232820606509394092422982568570889193755927961059256373509251540968761510597955349467469602569838971815245810437719445704016129
p2 = 8604143985568971357221106163518321547782942525630490158067993880524661927741225574307260111628133976467492901704516592869940382055272648214920231756723373
q2 = 6715932984064668444342570644774156271984002289395510283696469320418962556390690901906940107908954287013902962625382543926197508086756331581472941654687263

import hashlib

flag = "DASCTF{" + hashlib.md5(str(p1 + p2 + q1 + q2).encode()).hexdigest() + "}"
print(flag)
# DASCTF{354ed97c5a3d9d16f49ad93fc30e1c6f}
-------------已经到底啦！-------------