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 ♥-------------