three_friends

题目

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

flag = b"***********"

L = len(flag)
m1 = bytes_to_long(flag[:L//3])
m2 = bytes_to_long(flag[L//3:2*L//3])
m3 = bytes_to_long(flag[2*L//3:])

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)

e = 65537

n1 = p * q
n2 = q * r
n3 = p * r

c1 = pow(m1, e, n1)
c2 = pow(m2, e, n2)
c3 = pow(m3, e, n3)

print(f"n1 = {n1}")
print(f"n2 = {n2}")
print(f"n3 = {n3}")
print(f"e = {e}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"c3 = {c3}")

"""
n1 = 110479112338979326841231465480900311437095583241804968504367003268478785311645575853029227541889465070127417880290972698509502098875302777600751062235679028180932171554996023850242418398546147652141811910224228666917788640895453721648601609529326886128507435254380985821439510394329605362511800619781782498829
n2 = 95225891725804035729098697183853172993650305271540351260130976375990969994680256179992972429701670943885218431291657615581872984046365977866046911929212400122026478512046580419614160900113488336302811792780327677539930592604198331529856760869923384410189400614767668529075682332352478496830621674767765967989
n3 = 111603865467493745511917065096450766019551858630764507502030413922630178420561431122201021143404521026218410173550594126191240832822627851633700772093095150654117699219949636045712687320990198957564564857885138504872560550777788915442814980338401072475446362026076893466520135409327492048388030114969050367401
e = 65537
c1 = 83456548767677952158133165776385438048214812740470347872014544040241661979735585698444752238351578159480247608435786172021153411975720140472715451216442036398970558532828923787921375318802867775369825882219621531795085442575971814645729572790836415339290407608988460626504016819536559945368010686567075802413
c2 = 55598291653542627898994967211126815679185160762475277667203320398466974811147081936849639204784572327753766773503264941715352990434513737784771805183050575481575095545922660276426069697449001567347723946016416649932633528235458091960122921036028416845355866656581114844470311590282808396786169332755296721792
c3 = 99617304265145206462280689337024202287720390645940568836285315412577937662785727570612881726190729195621460858194592258472873348744392240254689998279616123901037173010035977506212880680604466077172284894508163086916852071659627506881093976971048133795462670278664801263633610021626528113016267024450025017002
"""

思路
n1 = p * q
n2 = q * r
n3 = p * r
通过求公因数分别获得p,q,r
得到phi1，phi2，phi3
进行求解

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

n1 = 110479112338979326841231465480900311437095583241804968504367003268478785311645575853029227541889465070127417880290972698509502098875302777600751062235679028180932171554996023850242418398546147652141811910224228666917788640895453721648601609529326886128507435254380985821439510394329605362511800619781782498829
n2 = 95225891725804035729098697183853172993650305271540351260130976375990969994680256179992972429701670943885218431291657615581872984046365977866046911929212400122026478512046580419614160900113488336302811792780327677539930592604198331529856760869923384410189400614767668529075682332352478496830621674767765967989
n3 = 111603865467493745511917065096450766019551858630764507502030413922630178420561431122201021143404521026218410173550594126191240832822627851633700772093095150654117699219949636045712687320990198957564564857885138504872560550777788915442814980338401072475446362026076893466520135409327492048388030114969050367401
e = 65537
c1 = 83456548767677952158133165776385438048214812740470347872014544040241661979735585698444752238351578159480247608435786172021153411975720140472715451216442036398970558532828923787921375318802867775369825882219621531795085442575971814645729572790836415339290407608988460626504016819536559945368010686567075802413
c2 = 55598291653542627898994967211126815679185160762475277667203320398466974811147081936849639204784572327753766773503264941715352990434513737784771805183050575481575095545922660276426069697449001567347723946016416649932633528235458091960122921036028416845355866656581114844470311590282808396786169332755296721792
c3 = 99617304265145206462280689337024202287720390645940568836285315412577937662785727570612881726190729195621460858194592258472873348744392240254689998279616123901037173010035977506212880680604466077172284894508163086916852071659627506881093976971048133795462670278664801263633610021626528113016267024450025017002
p=gmpy2.gcd(n1, n3)
q=gmpy2.gcd(n1, n2)
r=gmpy2.gcd(n2, n3)
phi1=(p-1)*(q-1)
phi2=(q-1)*(r-1)
phi3=(p-1)*(r-1)
d1=gmpy2.invert(e, phi1)
d2=gmpy2.invert(e, phi2)
d3=gmpy2.invert(e, phi3)
m1=pow(c1,d1,n1)
m2=pow(c2,d2,n2)
m3=pow(c3,d3,n3)
flag=long_to_bytes(m1)+long_to_bytes(m2)+long_to_bytes(m3)
print(flag)

DASCTF{thr33_fri3nds_sh@r3_pr1m3s!!}

lattice_oracle

题目

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
from Crypto.Cipher import AES
import hashlib, os, json, random

flag = b"?"

n = 6
q = 97
m = 30

s = [random.randint(0, 3) for _ in range(n)]

A = []
b = []
for _ in range(m):
    a_i = [random.randint(0, q - 1) for _ in range(n)]
    e_i = random.randint(-1, 1)
    b_i = (sum(x * y for x, y in zip(a_i, s)) + e_i) % q
    A.append(a_i)
    b.append(b_i)

key = hashlib.sha256(str(s).encode()).digest()[:16]
iv = os.urandom(16)
pad_len = 16 - len(flag) % 16
enc = AES.new(key, AES.MODE_CBC, iv).encrypt(flag + bytes([pad_len]) * pad_len)

print(f"n = {n}")
print(f"q = {q}")
print(f"m = {m}")
print(f"A = {A}")
print(f"b = {b}")
print(f"iv = '{iv.hex()}'")
print(f"enc = '{enc.hex()}'")

"""
n = 6
q = 97
m = 30
A = [[94, 13, 86, 94, 69, 11], [54, 4, 3, 11, 27, 29], [77, 3, 71, 25, 91, 83], [69, 53, 28, 57, 75, 35], [20, 89, 54, 43, 35, 19], [43, 13, 11, 48, 12, 45], [77, 33, 5, 93, 58, 68], [48, 10, 70, 37, 80, 79], [73, 24, 90, 8, 5, 84], [37, 10, 29, 12, 48, 35], [81, 46, 20, 47, 45, 26], [34, 89, 87, 82, 9, 77], [21, 68, 93, 31, 20, 59], [34, 81, 88, 71, 28, 87], [77, 29, 4, 40, 51, 34], [27, 72, 91, 40, 27, 83], [50, 82, 58, 18, 33, 17], [95, 71, 68, 33, 95, 74], [74, 51, 46, 28, 17, 65], [11, 96, 6, 14, 19, 80], [87, 54, 76, 8, 49, 48], [59, 67, 32, 70, 1, 87], [14, 87, 68, 96, 34, 82], [14, 37, 55, 20, 58, 0], [92, 33, 64, 22, 64, 13], [38, 81, 64, 77, 25, 19], [20, 69, 67, 0, 76, 41], [2, 14, 46, 39, 30, 7], [72, 10, 10, 93, 62, 8], [16, 16, 84, 60, 70, 21]]
b = [56, 74, 51, 28, 10, 30, 34, 45, 82, 56, 62, 52, 5, 71, 35, 41, 86, 47, 8, 27, 64, 29, 57, 92, 34, 55, 57, 70, 87, 28]
iv = 'bcdad772f7a0ec967887f7b8f36234c8'
enc = '00ac1bac207e84d91c6243c4aead3576a20f996a5420eea7bfa0df3b61d68c83f283bd31f1fedf7465b6445d7a58dcdc'
"""

思路

1
2
n=6
s = [random.randint(0, 3) for _ in range(n)]

随机生成6维向量s

1
2
3
4
5
6
7
8
9
A = []
b = []
for _ in range(m):
    a_i = [random.randint(0, q - 1) for _ in range(n)]
    e_i = random.randint(-1, 1)
    b_i = (sum(x * y for x, y in zip(a_i, s)) + e_i) % q
    A.append(a_i)
    b.append(b_i)

生成6维的向量a_i,和s进行点积加上误差e_i，然后取模q

暴力枚举 4096 种 s 的原理
s 有 6 个位置，每个位置只能取 0、1、2、3（第 10 行）：
s = [random.randint(0, 3) for _ in range(n)]
所以总组合数 = 4 × 4 × 4 × 4 × 4 × 4 = 4⁶ = 4096。
直接枚举并通过检验误差diff判断s是否满足条件
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
32
33
34
35
36
37
38
39
from Crypto.Cipher import AES
import itertools
import hashlib

n = 6
q = 97
m = 30
A = [[94, 13, 86, 94, 69, 11], [54, 4, 3, 11, 27, 29], [77, 3, 71, 25, 91, 83], [69, 53, 28, 57, 75, 35], [20, 89, 54, 43, 35, 19], [43, 13, 11, 48, 12, 45], [77, 33, 5, 93, 58, 68], [48, 10, 70, 37, 80, 79], [73, 24, 90, 8, 5, 84], [37, 10, 29, 12, 48, 35], [81, 46, 20, 47, 45, 26], [34, 89, 87, 82, 9, 77], [21, 68, 93, 31, 20, 59], [34, 81, 88, 71, 28, 87], [77, 29, 4, 40, 51, 34], [27, 72, 91, 40, 27, 83], [50, 82, 58, 18, 33, 17], [95, 71, 68, 33, 95, 74], [74, 51, 46, 28, 17, 65], [11, 96, 6, 14, 19, 80], [87, 54, 76, 8, 49, 48], [59, 67, 32, 70, 1, 87], [14, 87, 68, 96, 34, 82], [14, 37, 55, 20, 58, 0], [92, 33, 64, 22, 64, 13], [38, 81, 64, 77, 25, 19], [20, 69, 67, 0, 76, 41], [2, 14, 46, 39, 30, 7], [72, 10, 10, 93, 62, 8], [16, 16, 84, 60, 70, 21]]
b = [56, 74, 51, 28, 10, 30, 34, 45, 82, 56, 62, 52, 5, 71, 35, 41, 86, 47, 8, 27, 64, 29, 57, 92, 34, 55, 57, 70, 87, 28]
iv = 'bcdad772f7a0ec967887f7b8f36234c8'
enc = '00ac1bac207e84d91c6243c4aead3576a20f996a5420eea7bfa0df3b61d68c83f283bd31f1fedf7465b6445d7a58dcdc'

candidates = []  # 存放所有通过验证的 s

for s_tuple in itertools.product(range(4), repeat=6):
    s = list(s_tuple)
    ok=True
    for i in range(m):
        a_i=A[i]
        b_i=b[i]
        inner=0
        for j in range(6):
            inner+=a_i[j]*s[j]
        inner=inner%q
        #防止出现负数
        diff=(b_i-inner)%q
        if diff>1 and diff<q-1:
            ok=False
            break
    if  ok:
        candidates.append(s)

iv_bytes = bytes.fromhex(iv)
enc_bytes = bytes.fromhex(enc)

for s in candidates:
    key = hashlib.sha256(str(s).encode()).digest()[:16]
    plain = AES.new(key, AES.MODE_CBC, iv_bytes).decrypt(enc_bytes)
    print(f"解密结果: {plain}")

DASCTF{LWE_l4tt1c3_r3duct10n_i5_p0w3rful!}