2021华为计算AI安全冬令营crypto writeup

crypto writeup

古典美

密钥:VklHRU5FUkU=

密文:

HHCKPDQEGUFXFCKHBZXXVQAAHZYHVDSYBQEHXRUHHCEXXSADBGEXZRCHBYEHTBAEH4GJEMFS

密钥用base64解码:VIGENERE,作为维吉尼亚的密钥。

解密密文得到:

MZWGCZZALMZTSYTDGRRTIMJWMRSDIZBUGIYDKNDDMUYTKOJZGYYTMNLDGQYDGXJAM4YDAZBB

只有A-Z和数字,因此采用base32解码: flag [39bc4c416dd4d42054ce15996165c403] g00d!

(忘记题目)

题目考察的点是在RSA中,如果已知公钥对(e, n)对应的私钥对(d, n),有办法分解出p, q的值。参考https://www.di-mgt.com.au/rsa_factorize_n.html

这道题首先第一部分用正常的d解密就好:

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
d1=0x7d12e57b1aa157038ebe5c45b56256270671e6984b0dcdf10a2ea07ce480143240c9a3e1c60870e499306a717073f157476aa88e99a7bdf1e2a4adf8ce21025cc6c05035c4a1d7e3b6f061464872e65118384999f0154f3c1761fa68d4685126b7fc98f4c2cdc41c98aa4e099a868a89099dd2170664647efca2c8d8e06a2e49
e1=0x10001
n1=0x96ed2727e4446e26c84552a9a19640c7d720c9b6e661cfcfec03463e92a9d0b228ddc9847c0daa137a19db67294626c535fe71c388f6ea3eb8cb5dbf09a84374eb021c9297a29394cf77da157c1b8be77b09a4fcbe54bf3dc93d33539e842766ad8e38369093ddc034ac32583a48e299a4d8b31b606b1729298ee136664b8b77
c1=0x6c435db37217bc4da3f225a8f1a0501e03a97d2cbc4fa249df051ed66c1559b68885f4fa181bdd9e98242441f463dbbc1c26d1eea2c5774a0a905b366c8775bce8e52182dc32a93647c9b8842b74abc434e5b84eeae679a3b19cb7a1ef6ae8f65d22ce6ab438a16119805eee83408a68207bbdfde5181a8bd8b4794c711d33c4
m1=pow(c1, d1, n1)
long_to_bytes(m1)

# 'flag part one is :2295b774c4467c9a'

再由e,d,n分解出p,q。

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
import java.math.BigInteger;
import java.util.Random;
import java.util.Scanner;

public class KnownEDN {
public static BigInteger[] attack(BigInteger e, BigInteger d, BigInteger n) {
BigInteger[] result = new BigInteger[2];
BigInteger k = d.multiply(e).subtract(BigInteger.ONE);
Random random = new Random();
while (true) {
BigInteger g = new BigInteger(n.bitLength(), random);
while (g.compareTo(BigInteger.ONE) <= 0 || g.compareTo(n) >= 0)
g = new BigInteger(n.bitLength(), random);
BigInteger k1 = k;
while (k1.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
k1 = k1.shiftRight(1);
BigInteger x = g.modPow(k1, n);
result[0] = x.subtract(BigInteger.ONE).gcd(n);
if (x.compareTo(BigInteger.ONE) > 0 && result[0].compareTo(BigInteger.ONE) > 0) {
result[1] = n.divide(result[0]);
return result;
}
}
}
}

public static void main(String[] args) {
BigInteger e = new BigInteger("65537");
BigInteger d = new
BigInteger("87829819124646652739812957863722412015634891260772294325995961099107534010712036077168547772778499478512604716421195336244466016654383871260966997679029170319388738640308348628385235411655710226519739834339519380578327359429189610559253693055613763347244887191660768249285720137254760097622936841830552710729");
BigInteger n = new
BigInteger("105984107381045601823003108385313761784328476156897016317924496005453968007586579300498888169700143991517014514556827875595249016469561521069948889302177015514105662236342493793950683120435606323771328483886206142440957804487985287339927632655132795619465387151256885471251176082064948939517064310791867173751");
BigInteger[] pq = attack(e, d, n);
System.out.println("p:\n" + pq[0] + "\nq:\n" + pq[1]);
}
}

从而得到p,q的值。

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

p = 7989817345872802916258824633068986429227729563110196898659568255235293257271203068952971618219681106634429039565231866429796385557747877260629666332312643
q = 13264897405419718100411551025228233248810511685104073408647554593159408298020238756835088759200259612491893289998541138751171701279712972233358298687021757
c2 = 0x8cb5d8861e5838f41910d6eaf142a8d47b92e0c6b1b1e9e25896f7169644bbb726ccfdc82ba50932fbc45f00c53dda42f8efc358a5108cde8aaa9f38b493aa3417c9522924f06847ba4a3dd26f005a610f7633877fbe89e090df5cb3a7a5ebae0fbe72eabb339b21fa2ddd33844a5cb53e39491fc472721ed676ae07b33c8d6e
phi = (p - 1) * (q - 1)
e = 0x3f1
d = gmpy2.invert(e, phi)
m = pow(c2, d, p*q)
print(long_to_bytes(m))

# flag part two is :ca5c600783b9bde0

两部分连接起来就是flag的值。

RSA_upgrade

题目代码:

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
import random
from sympy import nextprime
from Crypto.Util.number import *
from gmpy2 import *
from typing import *
flag = b'DASCTF{********************************}'

def lcg(seed,params):
(m,c,n)=params
s = seed % n
while True:
s = (m * s + c) % n
yield s


seed = getPrime(128)
m = getPrime(128)
c = getPrime(128)
n = getPrime(129)


key_stream = lcg(seed,(m,c,n))
num=[]
for _ in range(6):
num.append(next(key_stream))

secret = next(key_stream)

e = nextprime(secret)
p = getPrime(1024)
q = getPrime(1024)
r = getPrime(1024)


flag = bytes_to_long(flag)
flag ^= flag >> 10
print(p)
print(p*q*r)
print(pow(flag,e,p*q*r))


num = [58605992502479537155943965904595921273, 525605798656979919420608964379033982804, 607738431135489138748992347244318940466, 631747898536603358381419028993140907216, 13450658701001781564543219325486287717, 407826262741495712819054543462943222370]
p = 138092450043978032187397495330379791355629274237204650898232878263413301988536751004632087169676028049236253598677819980191406826529664613957150122788435561338344715937422320958238628877093605040078776555586363593650646481242888908171897232624141894446324625781720275455534977357099473212936612966142541689717
newN = 3373500409784821814490131118443028295231446638918191872866826078664586857545499510115664725311697632345156866795088640886074708893049896293408277232121045205172588091316164743124173177747110069553394872128870505076277498830601152723565030932360665298864122468812389923295873644041292977470736981439616767671752225297169001703767163460419431015014012924743881828753765788455996503018031103917461875346904941302752301152097427368052588291798732671143344833211267818507324812463058368199324367285019651028003000765054679485233317767201747568717493732406861626561470103436488978595267326521876995116542475030869904228103019888619123275263009931569375612626796485751453790231029224398879558668919940829341599982045260085645733137064910612640851525128951165660322666651603943749615559507563880191545144231282875004494643666234781231448702811026047613232622993307630737999918058511598922102840862761604680588858313364100914751476403
c = 40522976224675404992818282038409183193065303107530049168092540620105120083552580372904554927069109321998620410524986748598618388761467715127564839742806614159382512978830563949967053562802375030363283879451081474764301602860367140250483857874335594802704634427276762179861996608105102610424633434334897307449739846880323406404392707133580686043181007091235341464802410874449708870610192494627811013526751435468963111672237058189288520084494533786573065843704621915085789731723587760910378534773137633519620193203450046994466154848079413319979993890764583887936777316159487010002407093187269512820453207591173395762513970799972839858119501585885277954258269483363133460240339866272358522431904252286259542327658731232568465990008278265227086114042064326334937705758042097987623388556184022737180944807660792992413039097516526454455063218161704505837882378018400687043158628503465274374703624257222504948612055237771581019005

典型的m,c,n未知时候的LCG。首先求出m,c,n及seed的值,有多个可能的值,代回原来的lcg函数比对生成的6个值。具体公式推导见 https://blog.csdn.net/superprintf/article/details/108964563 (写的真不错)

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
from Crypto.Util.number import *

def gcd(a,b):
if(b == 0):
return a
else:
return gcd(b,a % b)

s = [58605992502479537155943965904595921273, 525605798656979919420608964379033982804, 607738431135489138748992347244318940466, 631747898536603358381419028993140907216, 13450658701001781564543219325486287717, 407826262741495712819054543462943222370]
t = []
all_n = []
for i in range(6):
t.append(s[i] - s[i - 1])

for i in range(4):
all_n.append(gcd((t[i + 1] * t[i - 1] - t[i] * t[i]), (t[i + 2] * t[i] - t[i + 1] * t[i + 1])))

MMI = lambda A, n, s=1, t=0, N=0: (n < 2 and t % N or MMI(n, A % n, t, s - A // n * t, N or n), -1)[n < 1]
for n in all_n:
n = abs(n)
if n == 1:
continue
m = (s[2] - s[1]) * MMI((s[1] - s[0]), n) % n
ani = MMI(m,n)
c = (s[1] - m * s[0]) % n
seed = (ani * (s[0] - c)) % n
print("n = ",n)
print("m = ",m)
print("c = ",c)
print("seed = ",seed)

# n = 658483278832814360413959491304994965751
# m = 304895213771629215412875483024241040557
# c = 332633353219222389093389121471714482887
# seed = 233122372118782757817692638408531340431

e是lcg的第7个值的下一质数,这样就能得出e。

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
import random
from sympy import nextprime
from Crypto.Util.number import *
from gmpy2 import *

n = 658483278832814360413959491304994965751
m = 304895213771629215412875483024241040557
c = 332633353219222389093389121471714482887
seed = 233122372118782757817692638408531340431

def lcg(seed,params):
(m,c,n)=params
s = seed % n
while True:
s = (m * s + c) % n
yield s

key_stream = lcg(seed,(m,c,n))
num=[]
for _ in range(6):
num.append(next(key_stream))

secret = next(key_stream)
e = nextprime(secret)

# e = 176683449265430137948016253982177600477

发现是三质数的RSA。这里有个坑,跟BMZCTF2020里一样。因为p,q,r两两互素,所以不需要知道q,r的值,利用phi(p)=p-1就可以得到d的值。

1
2
3
4
5
6
7
8
9
import gmpy2
p = 138092450043978032187397495330379791355629274237204650898232878263413301988536751004632087169676028049236253598677819980191406826529664613957150122788435561338344715937422320958238628877093605040078776555586363593650646481242888908171897232624141894446324625781720275455534977357099473212936612966142541689717
c = 40522976224675404992818282038409183193065303107530049168092540620105120083552580372904554927069109321998620410524986748598618388761467715127564839742806614159382512978830563949967053562802375030363283879451081474764301602860367140250483857874335594802704634427276762179861996608105102610424633434334897307449739846880323406404392707133580686043181007091235341464802410874449708870610192494627811013526751435468963111672237058189288520084494533786573065843704621915085789731723587760910378534773137633519620193203450046994466154848079413319979993890764583887936777316159487010002407093187269512820453207591173395762513970799972839858119501585885277954258269483363133460240339866272358522431904252286259542327658731232568465990008278265227086114042064326334937705758042097987623388556184022737180944807660792992413039097516526454455063218161704505837882378018400687043158628503465274374703624257222504948612055237771581019005
phi = p - 1
e = 176683449265430137948016253982177600477
d = gmpy2.invert(e, phi)
m = pow(c, d, p)

# 569987504250336203008383799281952855095298052417061158522700484233183317916824291767569080757872

有了明文,但并不是真正的flag。明文是flag异或上flag >> 10的值,flag头部’DASCTF{‘,但只移动了10bits,因此理论上每10bit一组交替异或,可以逆推出flag的值。

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 *

m = 569987504250336203008383799281952855095298052417061158522700484233183317916824291767569080757872
flag = list(bin(m)[2:])
part = bin(bytes_to_long(b'DASCTF{'))[2:][:10]
result = [part]
str1 = []
str2 = ['0000000000', part]

for i in range(0, len(flag), 10):
t = ''.join(str(j) for j in flag[i:i+10])
str1.append(t)

for i in range(1, len(str1)):
L = len(str1[i])
tmp = str2[i][:L]
t = bin(int(str1[i], 2) ^ int(tmp, 2))[2:].zfill(L)
result.append(t)
str2.append(t)

print(long_to_bytes(int(''.join(result), 2)))

# DASCTF{b19998fb5acd197e441029b37bc246d7}

rsa4

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
from Crypto.Util.number import *
import binascii
import gmpy2
flag = 'flag is :********************************'
hex_flag=int(flag.encode("hex"),16)

p=getPrime(256)
q=getPrime(256)
n=p*q

e=0x3

c=pow(hex_flag,e,n)

m=((hex_flag>>120)<<120)

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

'''
('n=', '0x8bc8479ebf10dc1a4c24d6dfd6effd0437969eebf67654bc5c495bf2577f15226c15b9793ce9363c5986c485c2932fc7e7e6daac8dc108cca6d1b3850353fa2fL')
('e=', '0x3')
('c=', '0x87c05b7868cf54a58e19fe7a969a0213101f045e2afbf7547534564e918b62caa8187c773a8168ff464b20c28ce0e33383a600351883bb0938b2ecf0c45d59f3L')
('m=', '0x666c6167206973203a3739306666373532653338393838613532000000000000000000000000000000L')
'''

m是由flag向右移120后再向左移120位得到,m高位泄露,低位的120比特未知。加上e = 3,可以联想到coopersmith的高位攻击。以前的coopersmith定理的题目一般是已知p的高位,爆破出完整的p来分解n。 sage里面的small_roots实现了LLL算法求解非线性低维度多项式方程小根的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
n = 0x8bc8479ebf10dc1a4c24d6dfd6effd0437969eebf67654bc5c495bf2577f15226c15b9793ce9363c5986c485c2932fc7e7e6daac8dc108cca6d1b3850353fa2f
e = 0x3
c = 0x87c05b7868cf54a58e19fe7a969a0213101f045e2afbf7547534564e918b62caa8187c773a8168ff464b20c28ce0e33383a600351883bb0938b2ecf0c45d59f3
m_part = 0x666c6167206973203a3739306666373532653338393838613532000000000000000000000000000000

kbits = 120
PR.<x> = PolynomialRing(Zmod(n))
f = (m_part + x) ^ e - c
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
m = m_part + x0
print(long_to_bytes(m))

# flag is :790ff752e38988a521c73837942b1414

MEET

题目代码:

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
from Crypto.Cipher import DES
import random
import base64
from secret import flag

class _2DES:
def __init__(self):
pass

def Get_key(self):
k1="".join([random.choice('0123456789abcdef') for i in range(8)])
return (k1[:4]*2,k1[4:]*2)

def Enc(self,msg,key1,key2):
k1,k2=key1,key2
e1=DES.new(k1.encode(),DES.MODE_CBC,bytes(8))
e2=DES.new(k2.encode(),DES.MODE_CBC,bytes(8))
c=e2.decrypt(e1.encrypt(msg))
return base64.b64encode(c)

if __name__ == "__main__":
_2des=_2DES()
k1,k2=_2des.Get_key()
c=_2des.Enc(b'12345678',k1,k2)
print(c)
c=_2des.Enc(flag,k1,k2)
print(c)

#b'D4meWwYAUE4='
#b'qMMGe3wORmFJePnQnM2ZeA=='

2DES的中间相遇攻击。已知一组明密文[12345678, D4meWwYAUE4=],能够爆破出k1k2的值。满足:

1
2
c = e2.decrypt(e1.encrypt(msg))
e2.encrypt(c) = e1.encrypt(msg)

因此先遍历k1加密明文后的值放入一个数组1,再遍历k2加密密文c后的值放入数组2,比较数组1和数组2找相同的中间值,根据中间值计算对应的k1和k2。

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
from Crypto.Cipher import DES
import base64
import itertools as its
from Crypto.Util.number import *

def enc(msg,k):
e=DES.new(k.encode(),DES.MODE_CBC,bytes(8))
c = e.encrypt(msg)
return c

def dec(c, key1, key2):
k1, k2 = key1, key2
e1 = DES.new(k1.encode(), DES.MODE_CBC, bytes(8))
e2 = DES.new(k2.encode(), DES.MODE_CBC, bytes(8))
m = e1.decrypt(e2.encrypt(c))
return m

if __name__ == "__main__":
words = '0123456789abcdef'
c_1 = base64.b64decode('D4meWwYAUE4=')
c_2 = base64.b64decode('qMMGe3wORmFJePnQnM2ZeA==')
words = its.product(words,repeat=4)
mid_1 = []
mid_2 = []
key = []
k1 = ''
k2 = ''

for i in words:
key.append(''.join(i))

for i in key:
m = enc(b'12345678', i * 2)
mid_1.append(m)

for i in key:
m = enc(c_1, i * 2)
mid_2.append(m)

for i in mid_1:
for j in mid_2:
if i == j:
mid = i
break

for i in key:
if enc(b'12345678', i * 2) == mid:
k1 = i * 2

for i in key:
if enc(c_1, i * 2) == mid:
k2 = i * 2

print(dec(c_2, k1, k2))

# b'_Meet_in_Middle_'
-------------end ♥-------------