2023DASCTF暑期挑战赛——Crypto

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

复现2023DASCTF暑期挑战赛Crypto方向赛题（没做完）

EzDHKE

题目

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import randbytes, getrandbits
from flag import flag
def diffie_hellman(g, p, flag):
    alice = getrandbits(1024)
    bob = getrandbits(1024)
    alice_c = pow(g, alice, p)
    bob_c = pow(g, bob, p)
    print(alice_c , bob_c)
    key = sha256(long_to_bytes(pow(bob_c, alice, p))).digest()
    iv = b"dasctfdasctfdasc"
    aes = AES.new(key, AES.MODE_CBC, iv)
    enc = aes.encrypt(flag)
    print(enc)

def getp():
    p = int(input("P = "))
    assert isPrime(p)
    assert p.bit_length() >= 1024 and p.bit_length() <= 2048
    g = 2
    diffie_hellman(g, p, flag)

getp()

flag被ECB加密，已经给出了iv，我们的目的是求key

而key是关于DH加密的一个值

getp()要求我们传一个1024bit——2048bit的素数p，之后会返回DH加密后的密文

既然模数p是由我们决定的，那我们传一个很光滑的素数p使得下式可以很快解出来
$$
g^{Alice} = Alice_c \mod p
$$
exp:

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
from Crypto.Util.number import *
import gmpy2
from sympy.ntheory import discrete_log
from hashlib import *
from Crypto.Cipher import AES

# 构造一个很光滑的p，即p可以分解成许多小素数之积
p = 1
i = 2
while  isPrime(p+1) ==False or p.bit_length()<1024 :
    p *= i
    i = gmpy2.next_prime(i)

# print(p+1)

# 接下来就是解Alice的私钥a
g = 2
p = p+1
A = 6497613672285956425201511287597625030386480108672286755480826112363203245642148151212994725377254666591461004877010242830011793120730597548153751505160757772485565892716879723968695533469583944347775896608532625158303921475557511270608379047178615651278485591942635948967376062201899549648208278357029126731213145007749394102828405131490762093895807059008547765574826356405482971857911257856639902792877504986919307035949726
B = 6892121088985539176550813556605471863390995273766116635861764749041016271848611822954736310722897673081939505093515966422841748844230466887689109451140120941395556326881049077033545866417480327268932777262530024548392468111847291103142479432094000792091679519431359554583970331286677886683961473976144527513383303092681236504569767664611631709120184944129897975070357015740122424467791475504388327118892471415926469637241282

enc = b'`<\xad\x93e\xeez\x8e\x1b\xe2B\xe9\xc7\x166\xc92$\x1a\xda\x86\x12m\x07\xb2\xa5d\x0b.\x13\xee\xa7.y(1\xd0\xf8\xc5\xffL\xf1\xb6_m840'
iv = b"dasctfdasctfdasc"
a = discrete_log(p,A,g)

key = sha256(long_to_bytes(pow(B, a, p))).digest()
# print(a)

aes = AES.new(key, AES.MODE_CBC, iv)
flag = aes.decrypt(enc)
print(flag)

EzRSA

题目:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from secret import secret, flag
def encrypt(m):
    return pow(m, e, n)
assert flag == b"dasctf{" + secret + b"}"
e = 11
p = getPrime(512)
q = getPrime(512)
n = p * q
P = getPrime(512)
Q = getPrime(512)
N = P * Q
gift = P ^ (Q >> 16)

print(N, gift, pow(n, e, N))
print(encrypt(bytes_to_long(secret)),
    encrypt(bytes_to_long(flag)))

N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034
pow(n,e,N) = 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
pow(secret,e,n) = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
pow(flag,e,n) = 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991

首先注意到flag和secret在转成long型之后是有一定差值的，所以想到了相关消息攻击，但是相关消息攻击需要n

已知给了N,P^(Q>>16),pow(n,e,N)的值，想到把P求出来再解pow(n,e,N)

这里通过爆破的方法求P

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
import sys
from tqdm import *
sys.setrecursionlimit(3000)
gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034
N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377

# 低位往高位爆

def findp(p,q):
    if len(p) == 512:
        pp = int(p,2)
        if N % pp == 0:
            print("p = ",pp)
            print("q = ",N // pp)
            
    else:
        l = len(p)
        pp = int(p,2)
        qq = int(q,2)
        if (pp ^ (qq>>16)) % (2 ** l) == gift %(2**l) and pp * qq %(2 ** l) == N % (2**l):
            findp('1' + p,'1' + q)
            findp('1' + p,'0' + q)
            findp('0' + p,'1' + q)
            findp('0' + p,'0' + q)
            
for i in trange(2**17,2**16,-1):
    findp('1',bin(i)[2:])

因为不知道Q的低16位是什么，只能爆破一下Q。

得到

P=8006847171912577069085166877758626954304824756138758266557706391662987806065132448544117840031499707938227955094109779732609035310252723066470330862622641

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

N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034
c = 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
secret_c = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
flag_c = 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991
e = 11

P = 8006847171912577069085166877758626954304824756138758266557706391662987806065132448544117840031499707938227955094109779732609035310252723066470330862622641
Q = N // P
d = gmpy2.invert(e,(P-1)*(Q-1))
n0 = pow(c,d,N)
print(n0)
print(n0.bit_length())

解得

n=8410363083727227985204019150296233995423906412694890252698371563789022268553444336554986979907257458547381598181369620318848637391220240378808211998052306324620364339595355706922325759625785590466818309839146408927226283350419069859849879835884942537531811470537915106995685907400782213608736735862576031042

检查一下n的位数发现只有1020bit，理论上n应该是1024bit，所以我们手动加上N

然后就是相关消息攻击解flag

exp:

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

def GCD(a,b):
    if b == 0:
        return a.monic()
    else:
        return GCD(b,a%b)
    
n = 83410392685813224685786027640778560521035854332627839979281105731457044069408118952629284089869335506983096270269822559619624906180108256504440296527471536363057103101146262613593336072556587341466840510200003498265457285439149541137127199088938421905041387224795918868443175561632999479925818053898100117419
secret_c = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
flag_c = 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991
e = 11

R.<x> = PolynomialRing(Zmod(n))

for i in range(100):
    f1 = (bytes_to_long(b'dasctf{' + b'\x00'*i + b'}') + 256*x)^e - flag_c
    f2 = x^e - secret_c
    if (GCD(f1,f2).coefficients()[0] != 1):
        print(b'dasctf{' + long_to_bytes(int(n - GCD(f1,f2).coefficients()[0]))+b'}')

解释部分代码：

  1. f1 = (bytes_to_long(b"dasctf{" + b"\x00"*i + b"}") + 256*x)^11 - flag_c

因为dasctf{在高位，所以要补上一些x代表secret的值，因为bytes_to_long()之后是256进制，所以乘上256

判断条件为：

  1. if (N-GCD(f1,f2).coefficients()[0]) != N-1:是因为如果填充的i个数不对GCD(f1,f2)返回的是1，则

coefficients()返回的也是1了

值得注意的是

coefficients()这个函数返回的值是多项式中每项的系数，但是是从低次幂往高次幂

eg:

1
2
f = x**3 + 2*x**2 + 6*x + 6
f.coefficients() = [6,6,2,1]
  1. print(long_to_bytes(int(N-GCD(f1,f2).coefficients()[0])))

为什么返回值要在前面加上N-

翻阅大佬博客：

密码学学习笔记 之 Coppersmith’s Method | Van1sh的小屋 (jayxv.github.io)

自己弄了一些简单的数进行测试，我的理解是：

假设

GCD(f1,f2).coefficients()[0]返回的是tmp，而我们要求的 x 和 tmp 满足

x + tmp = n

-------------已经到底啦！-------------