糖醋小鸡块的blog
0%

2023-羊城杯-wp-crypto

发表于 更新于 分类于 Valine：

随手记录一下~

Danger_RSA

题目描述:

1
看似简单的rsa

题目:

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

m = bytes_to_long(flag)


def get_key(a, nbit):
    assert a >= 2
    while True:
        X = getRandomInteger(nbit // a)
        s = getRandomRange(pow(2, a ** 2 - a + 4), pow(2, a ** 2 - a + 5))
        p = X ** a + s
        if isPrime(p):
            return (p, s)


p, s = get_key(a, 1024)
q, t = get_key(a, 1024)

N = p * q
e = s * t
c = pow(m, e, N)
print("N =", N)
print("e =", e)
print("c =", c)
# N = 20289788565671012003324307131062103060859990244423187333725116068731043744218295859587498278382150779775620675092152011336913225797849717782573829179765649320271927359983554162082141908877255319715400550981462988869084618816967398571437725114356308935833701495015311197958172878812521403732038749414005661189594761246154666465178024563227666440066723650451362032162000998737626370987794816660694178305939474922064726534186386488052827919792122844587807300048430756990391177266977583227470089929347969731703368720788359127837289988944365786283419724178187242169399457608505627145016468888402441344333481249304670223
# e = 11079917583
# c = 13354219204055754230025847310134936965811370208880054443449019813095522768684299807719787421318648141224402269593016895821181312342830493800652737679627324687428327297369122017160142465940412477792023917546122283870042482432790385644640286392037986185997262289003477817675380787176650410819568815448960281666117602590863047680652856789877783422272330706693947399620261349458556870056095723068536573904350085124198592111773470010262148170379730937529246069218004969402885134027857991552224816835834207152308645148250837667184968030600819179396545349582556181916861808402629154688779221034610013350165801919342549766

题目初看没有什么下手点，但其实get_key函数的这两行暴露了很多信息:

1
2
X = getRandomInteger(nbit // a)
s = getRandomRange(pow(2, a ** 2 - a + 4), pow(2, a ** 2 - a + 5))

也就是说，a可能的范围其实很小，粗略的范围都仅有[2,1024],这个时候再看生成的e，可以发现，e相对来说太小了，甚至可以得到他的全部素因子分解，即：

因此我们完全可以用下面这个方式来进一步确定a的取值范围:

1
2
3
for a in range(2,1024):
    if(pow(2, a ** 2 - a + 4)*pow(2, a ** 2 - a + 4) <= e and pow(2, a ** 2 - a + 5)*pow(2, a ** 2 - a + 5) >= e):
        print(a)

可以发现，a其实仅能取4；与此同时可以明白，对于刚才的e的因子分解，仅有两种可能的组合让两次生成的s均落在a规定的范围里：

此时再看n的生成过程：

s和t相较于X1、X2来说非常小，因此对n开4次方根就可以得到X1*X2，此时，就可以以以下方式分解n：

将所有量移动到同一侧：

左右同时乘$\; X1^4$，得:

此时，令$\;x = X1^4$，就得到下面的一元二次方程：

将可能的两组s、t，逐个代入解上述方程，就可以得到n的分解。

得到n的分解后，想要直接求解RSA解密却发现$\;gcd(e,phi_n)\;!=\;1$，发现是因为$\;3|(p-1)$且$\;7|(q-1)$，此时由于题目中并未说明对flag做过额外填充处理，而p、q两个因子均有接近1024比特，正常来说远大于明文比特位，因此可以转化到模p下求解，这是因为：

而

所以可以将$m^3$当作一个整体，进行RSA解密后在模p下开三次方根即可。


exp.ipynb:

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

N = 20289788565671012003324307131062103060859990244423187333725116068731043744218295859587498278382150779775620675092152011336913225797849717782573829179765649320271927359983554162082141908877255319715400550981462988869084618816967398571437725114356308935833701495015311197958172878812521403732038749414005661189594761246154666465178024563227666440066723650451362032162000998737626370987794816660694178305939474922064726534186386488052827919792122844587807300048430756990391177266977583227470089929347969731703368720788359127837289988944365786283419724178187242169399457608505627145016468888402441344333481249304670223
e = 11079917583
c = 13354219204055754230025847310134936965811370208880054443449019813095522768684299807719787421318648141224402269593016895821181312342830493800652737679627324687428327297369122017160142465940412477792023917546122283870042482432790385644640286392037986185997262289003477817675380787176650410819568815448960281666117602590863047680652856789877783422272330706693947399620261349458556870056095723068536573904350085124198592111773470010262148170379730937529246069218004969402885134027857991552224816835834207152308645148250837667184968030600819179396545349582556181916861808402629154688779221034610013350165801919342549766
elist = [3,7,7,19,691,5741]

a = 2
for i in range(2,10):
    if(pow(2, i ** 2 - i + 4)*pow(2, i ** 2 - i + 4) <= e and pow(2, i ** 2 - i + 5)*pow(2, i ** 2 - i + 5) >= e):
        a = i

s1 = 120561 
s2 = 91903

ab = iroot(N,4)[0] ** 4
b = -(N-ab-s1*s2)
a = s2
c1 = s1*ab
x = int((-b + iroot(b**2-4*a*c1,2)[0]) // (2*a))
p = x + s1
q = N//p

d = inverse(e//3,p-1)
m3 = int(pow(c,d,p))

PR.<x> = Zmod(p)[]
f = x^3 - m3
res = f.roots()
for i in res:
    temp = long_to_bytes(int(i[0]))
    if(b"DASCTF" in temp):
        print(temp)

得到flag：

DASCTF{C0nsTruct!n9_Techn1qUe2_f0r_RSA_Pr1me_EnC2ypt10N}


当然，这题还有一些值得思考的地方，如若明文的比特位超过了p，又该怎么办？

首先可以先将与p-1、q-1均不互素的素因子用普通RSA解密剔去，得到

然后就可以使用AMM算法，但是这时使用AMM算法又有一点特殊，这是因为虽然$7|q-1$，但是49却不整除于q-1，因此无法一次性在模q下开49次方根，而需要先开七次方根，再对7个开出的根再各开7次方根，最后再与模p下开出的3次方根作中国剩余定理求解：

exp.ipynb:

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
import random
from Crypto.Util.number import bytes_to_long,long_to_bytes,inverse


c = 3232774922192317186963877855543094060264001327534643963164572334193887491269409927593188017108306298404437170754762182875998691872041391981365074638343520234882604136837212457817534624895485767634112947143897465253262932526424371614372553023510973107043735041993637367122527503031768408492566328264574062328255875477737300307769891808134846813311720049466136337129654155946431766445576339564816809841942907193731423184669912783673012406488607834333191988772032942474663985054409518153017182678863504596312351140412943307416458908324209967299195302214349899874812717459558411734343869783905720910923365168671056618
p = 5213351003420231819415242686664610206224730148063270274863722096379841592931572096469136339538500817713355302889731144789372844731378975059329731297860686270736540109105854515590165681366189003405833252270606896051264517339339578167231093908235856718285980689179840159807651185918046198419707669304960745217
q = 3891889986375336330559716098591764128742918441309724777337583126578227827768865619689858547513951476952436981068109005313431255086775128227872912287517417948310766208005723508039484956447166240210962374423348694952997002274647622939970550008327647559433222317977926773242269276334110863262269534189811138319
n = p*q
e = 3*7*7

def onemod(e, q):
    p = random.randint(1, q-1)
    while(pow(p, (q-1)//e, q) == 1):  # (r,s)=1
        p = random.randint(1, q)
    return p

def AMM_rth(o, r, q):  # r|(q-1
    assert((q-1) % r == 0)
    p = onemod(r, q)

    t = 0
    s = q-1
    while(s % r == 0):
        s = s//r
        t += 1
    k = 1
    while((s*k+1) % r != 0):
        k += 1
    alp = (s*k+1)//r

    a = pow(p, r**(t-1)*s, q)
    b = pow(o, r*a-1, q)
    c = pow(p, s, q)
    h = 1

    for i in range(1, t-1):
        d = pow(int(b), r**(t-1-i), q)
        if d == 1:
            j = 0
        else:
            j = (-math.log(d, a)) % r
        b = (b*(c**(r*j))) % q
        h = (h*c**j) % q
        c = (c*r) % q
    result = (pow(o, alp, q)*h)
    return result

def ALL_Solution(m, q, rt, cq, e):
    mp = []
    for pr in rt:
        r = (pr*m) % q
        # assert(pow(r, e, q) == cq)
        mp.append(r)
    return mp

def calc(mp, mq, e, p, q):
    i = 1
    j = 1
    t1 = inverse(q, p)
    t2 = inverse(p, q)
    for mp1 in mp:
        for mq1 in mq:
            j += 1
            if j % 100000 == 0:
                print(j)
            ans = (mp1*t1*q+mq1*t2*p) % (p*q)
            if check(ans):
                return
    return


def check(m):
    try:
        a = long_to_bytes(m)
        if b'DASCTF' in a or b'flag' in a:
            print(a)
            return True
        else:
            return False
    except:
        return False


def ALL_ROOT2(r, q):  # use function set() and .add() ensure that the generated elements are not repeated
    li = set()
    while(len(li) < r):
        p = pow(random.randint(1, q-1), (q-1)//r, q)
        li.add(p)
    return li

cp = c % p
cq = c % q

mp = AMM_rth(cp, 3, p)
mq = AMM_rth(cq, 7, q)

rt1 = ALL_ROOT2(3, p)
rt2 = ALL_ROOT2(7, q)

amp = ALL_Solution(mp, p, rt1, cp, 3)
amq = ALL_Solution(mq, q, rt2, cq, 7)

#得到模q下所有根
mqs = []
for mq in amq:
    mqs.append(mq)
amq = mqs
dq = inverse(3, (q-1))
mmqs = []
for mq in amq:
    mmq = AMM_rth(mq, 7, q)

    rt3 = ALL_ROOT2(7, q)

    mamq = ALL_Solution(mmq, q, rt3, mq, 7)
    for t in mamq:
        mmqs.append(int(pow(t,dq,q)))
amq = mmqs

#得到模p下所有根
dp = inverse(49, (p-1))
mps = []
for mp in amp:
    mps.append(int(pow(mp, dp, p)))
amp = mps

calc(amp, amq, e, p, q)

而简便一点，直接解有限域下的方程也是可行的：

exp.ipynb:

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.Util.number import bytes_to_long,long_to_bytes,inverse
from sympy.ntheory.modular import crt
#使用如：M = crt(n,c)[0]

c = 3232774922192317186963877855543094060264001327534643963164572334193887491269409927593188017108306298404437170754762182875998691872041391981365074638343520234882604136837212457817534624895485767634112947143897465253262932526424371614372553023510973107043735041993637367122527503031768408492566328264574062328255875477737300307769891808134846813311720049466136337129654155946431766445576339564816809841942907193731423184669912783673012406488607834333191988772032942474663985054409518153017182678863504596312351140412943307416458908324209967299195302214349899874812717459558411734343869783905720910923365168671056618
p = 5213351003420231819415242686664610206224730148063270274863722096379841592931572096469136339538500817713355302889731144789372844731378975059329731297860686270736540109105854515590165681366189003405833252270606896051264517339339578167231093908235856718285980689179840159807651185918046198419707669304960745217
q = 3891889986375336330559716098591764128742918441309724777337583126578227827768865619689858547513951476952436981068109005313431255086775128227872912287517417948310766208005723508039484956447166240210962374423348694952997002274647622939970550008327647559433222317977926773242269276334110863262269534189811138319
n = p*q
e = 3*7*7

dp = inverse(49,p-1)
cp = pow(c,dp,p)
PR.<x> = Zmod(p)[]
f = x^3 - cp
resp = f.roots()

dq = inverse(3,q-1)
cq = pow(c,dq,q)
PR.<x> = Zmod(q)[]
f = x^49 - cq
resq = f.roots()

modlist = [p,q]
for i in resp:
    for j in resq:
        c = [int(i[0]),int(j[0])]
        m = crt(modlist,c)[0]
        temp = long_to_bytes(m)
        if(b"DASCTF" in temp):
            print(temp)

多种方法求解，也是为了能更灵活的思考问题，掌握更多求解方式，让自己一种方法卡住时，可以有路可走。




Easy_3L

题目描述：

1
无

题目：

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

m = bytes_to_long(flag)


def get_key():
    p = getPrime(1400)
    f = getRandomNBitInteger(1024)
    while True:
        q = getPrime(512)
        if gcd(f, q) != 1:
            continue
        else:
            break
    h = (invert(f, p) * q) % p
    return p, h


def encrypt1(m):
    a = getPrime(250)
    b = getRandomNBitInteger(240)
    n = getPrime(512)
    seed = m
    s = [0] * 6
    s[0] = seed
    for i in range(1, 6):
        s[i] = (s[i - 1] * a + b) % n
    return s


def encrypt2(msg, p, h):
    s = getRandomNBitInteger(512)
    c = (s * h + msg) % p
    return c


s = encrypt1(m)
print("S1 =", s[1])
print("S2 =", s[2])
print("S4 =", s[4])
print("S5 =", s[5])

p, h = get_key()
c = encrypt2(s[3], p, h)
print("p =", p)
print("h =", h)
print("c =", c)

# S1 = 28572152986082018877402362001567466234043851789360735202177142484311397443337910028526704343260845684960897697228636991096551426116049875141
# S2 = 1267231041216362976881495706209012999926322160351147349200659893781191687605978675590209327810284956626443266982499935032073788984220619657447889609681888
# S4 = 9739918644806242673966205531575183334306589742344399829232076845951304871478438938119813187502023845332528267974698273405630514228632721928260463654612997
# S5 = 9755668823764800147393276745829186812540710004256163127825800861195296361046987938775181398489372822667854079119037446327498475937494635853074634666112736
# p = 25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
# h = 2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
# c = 20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287

题目的3L显然指的是LLL算法，加密过程分为两层：

  • LCG加密种子flag
  • NTRU加密LCG的S3

那么解题思路也很清晰，先解决NTRU解出S3，进而恢复LCG的种子即可。

本题你会发现要规约出的向量(f,g)数量级好像差的有点多，很难规约出1024比特的f，但是不重要，f是否为原始值对于解密影响并不大，只需要检查S3的数量级正常即可。(正常来说，为使规约后的向量比特相近，应在第二列乘上2^512，使 f 与 (2^512)*g具有相同数量级，但本题中这是解不出来的，因此可以采用爆破手段，会发现有很多短向量f、g均可以用于解密，这也符合NTRU的密钥特性)

解出S3后是个简单的LCG问题，不再赘述。

exp.ipynb：

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

p = 25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
h = 2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
c = 20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287

def dec(S3):
    S1 = 28572152986082018877402362001567466234043851789360735202177142484311397443337910028526704343260845684960897697228636991096551426116049875141
    S2 = 1267231041216362976881495706209012999926322160351147349200659893781191687605978675590209327810284956626443266982499935032073788984220619657447889609681888
    S4 = 9739918644806242673966205531575183334306589742344399829232076845951304871478438938119813187502023845332528267974698273405630514228632721928260463654612997
    S5 = 9755668823764800147393276745829186812540710004256163127825800861195296361046987938775181398489372822667854079119037446327498475937494635853074634666112736

    x = [S1, S2, S3, S4, S5]
    t = []

    for i in range(1, len(x)):
        t.append(x[i] - x[i-1])

    m = 0
    for i in range(1, len(t)-1):
        m = GCD(t[i+1]*t[i-1] - t[i]*t[i], m)

    for p in sieve_base:
        while m % p == 0: m //= p
    assert isPrime(m)

    a = (S3 - S2) * inverse(S2 - S1, m)
    b = (S2 - a*S1) % m

    S1 = (S1-b)*inverse(a, m) % m
    flag = long_to_bytes(S1)
    if b'DASCTF' in flag:
        print(flag)


for e in range(1,1000):
    L = Matrix(ZZ, [[1, (2**e)*h],
                    [0, (2**e)*p]])
    f, g = L.LLL()[0]
    g = g  // (2**e)

    try:
        S3 = (f*c) % p % g * inverse(f, g) % g
        if(len(bin(S3)) == 514):
            dec(S3)
            break
    except:
        pass

得到flag：

DASCTF{NTRU_L0G_a6e_S1mpLe}




SigninCrypto

题目描述：

1
随机数真随机吗？如随！

题目：

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
from random import *
from Crypto.Util.number import *
from Crypto.Cipher import DES3
from flag import flag
from key import key
from iv import iv
import os
import hashlib
import secrets

K1= key
hint1 = os.urandom(2) * 8
xor =bytes_to_long(hint1)^bytes_to_long(K1)
print(xor)

def Rand():
    rseed = secrets.randbits(1024)
    List1 = []
    List2 = []
    seed(rseed)
    for i in range(624):
        rand16 = getrandbits(16)
        List1.append(rand16)
    seed(rseed)
    for i in range(312):
        rand64 = getrandbits(64)
        List2.append(rand64)
    with open("task.txt", "w") as file:
        for rand16 in List1:
            file.write(hex(rand16)+ "\n")
        for rand64 in List2:
            file.write(hex((rand64 & 0xffff) | ((rand64 >> 32) & 0xffff) << 16) + "\n")
Rand()

K2 = long_to_bytes(getrandbits(64))
K3 = flag[:8]

KEY = K1 + K2 + K3

IV=iv

IV1=IV[:len(IV)//2]
IV2=IV[len(IV)//2:]

digest1 = hashlib.sha512(IV1).digest().hex()
digest2 = hashlib.sha512(IV2).digest().hex()

digest=digest1+digest2
hint2=(bytes_to_long(IV)<<32)^bytes_to_long(os.urandom(8))
print(hex(bytes_to_long((digest.encode()))))
print(hint2)


mode = DES3.MODE_CBC
des3 = DES3.new(KEY, mode, IV)

pad_len = 8 - len(flag) % 8
padding = bytes([pad_len]) * pad_len
flag += padding

cipher = des3.encrypt(flag)

ciphertext=cipher.hex()
print(ciphertext)

# 334648638865560142973669981316964458403
# 0x62343937373634656339396239663236643437363738396663393438316230353665353733303939613830616662663633326463626431643139323130616333363363326631363235313661656632636265396134336361623833636165373964343533666537663934646239396462323666316236396232303539336438336234393737363465633939623966323664343736373839666339343831623035366535373330393961383061666266363332646362643164313932313061633336336332663136323531366165663263626539613433636162383363616537396434353366653766393464623939646232366631623639623230353933643833
# 22078953819177294945130027344
# a6546bd93bced0a8533a5039545a54d1fee647007df106612ba643ffae850e201e711f6e193f15d2124ab23b250bd6e1

可以发现，题目最终用3DES对flag进行了加密，因此目标就是还原3DES的key与iv即可。

其中，两个量分别分为了以下几部分：

  • KEY = K1 + K2 + K3 ,每个部分大小8字节
  • IV=iv，每个部分大小4字节

按照如下方式逐步还原每个部分：

K1

1
2
3
4
K1= key
hint1 = os.urandom(2) * 8
xor =bytes_to_long(hint1)^bytes_to_long(K1)
print(xor)

hint1为16字节量，而K1为8字节量，因此xor的高位即为hint1的高位，又因为hint1由重复字节构成，hint1高位与低位相等。得到完整hint1后与xor异或即得K1

K2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def Rand():
    rseed = secrets.randbits(1024)
    List1 = []
    List2 = []
    seed(rseed)
    for i in range(624):
        rand16 = getrandbits(16)
        List1.append(rand16)
    seed(rseed)
    for i in range(312):
        rand64 = getrandbits(64)
        List2.append(rand64)
    with open("task.txt", "w") as file:
        for rand16 in List1:
            file.write(hex(rand16)+ "\n")
        for rand64 in List2:
            file.write(hex((rand64 & 0xffff) | ((rand64 >> 32) & 0xffff) << 16) + "\n")
Rand()

K2 = long_to_bytes(getrandbits(64))

考察的是MT19937伪随机数生成，利用randcrack模块，提交624个32bit数，即可对之后的随机数进行精准预测。而注意到生成List1、List2之间重新调整了一次随机数种子，因此List1、List2是使用同一随机数种子生成的。

而注意到，List1仅有$62416$bit，List2却有$32464 = 624*32$bit，因此List2生成的位数是足够的，而最终task.txt文本中却只给了List2的部分字节，不需要深究原理也能明白：List1生成的字节恰好就是List2生成的随机数中缺失的字节。因此只需要每种补充方式均尝试一下即可得到K2。

K3

1
K3 = flag[:8]

很显然，因为flag一般以DASCTF{开头，因此只需要爆破一个可见字符即可得到正确K3。

IV1及IV2

1
2
3
4
5
6
7
8
9
10
IV1=IV[:len(IV)//2]
IV2=IV[len(IV)//2:]

digest1 = hashlib.sha512(IV1).digest().hex()
digest2 = hashlib.sha512(IV2).digest().hex()

digest=digest1+digest2
hint2=(bytes_to_long(IV)<<32)^bytes_to_long(os.urandom(8))
print(hex(bytes_to_long((digest.encode()))))
print(hint2)

首先明确IV一共8个字节，因此hint2的高位即为IV1，此时题目的几个哈希值貌似给了一个暗示：爆破求解IV2.可是需要爆破的量有4个字节，虽然不能说很大，却也需要很长时间。此时就需要注意到，digest=digest1+digest2这一行，并不是数值的相加，而是字符串的连接，而当你将digest解码后，你会发现：

1
digest1 = digest2

没错，太幽默了，所以IV2与IV1相同(基本无需考虑哈希碰撞)

此时所有量都得到了还原，解密3DES即可：

exp.py：

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
import hashlib
from random import *
from Crypto.Util.number import *
from Crypto.Cipher import DES3
from randcrack import RandCrack

rc = RandCrack()

cipher = int("a6546bd93bced0a8533a5039545a54d1fee647007df106612ba643ffae850e201e711f6e193f15d2124ab23b250bd6e1",16)

#获取iv
hint2 = 22078953819177294945130027344
IV1 = long_to_bytes(hint2 >> 64)
IV2 = IV1

#获取K2
list1 = []
list2 = []
with open("task.txt", "r") as f:
    for i in range(624):
        list1.append(int(f.readline(),16))
    for i in range(312):
        list2.append(int(f.readline(),16))
for i in range(312):
    t1 = (list2[i] & 0xffff)
    t2 = ((list2[i] >> 16) & 0xffff)
    rc.submit( (list1[2*i]<<16) | (list2[i] & 0xffff))
    rc.submit( (list1[2*i+1]<<16) | ((list2[i] >> 16) & 0xffff))
K2 = long_to_bytes(rc.predict_getrandbits(64),8)

#爆破k3
xor = 334648638865560142973669981316964458403
K1 = (xor ^ (xor>>64)) & 0xffffffffffffffff
K1 = long_to_bytes(K1)

temp = bytes_to_long(b"DASCTF{") << 8

for j in range(2**8):
    K3 = long_to_bytes(temp + j)
    KEY = K1 + K2 + K3
    IV = IV1 + IV2

    mode = DES3.MODE_CBC
    des3 = DES3.new(KEY, mode, IV)
    flag = str(des3.decrypt(long_to_bytes(cipher)))
    if("DASCTF" in flag):
        print(flag)
        break

得到flag：

DASCTF{8e5ee461-f4e1-4af2-8632-c9d62f4dc073}




esyRSA

题目描述：

1
好像这个RSA有点怪啊！私钥给你了！我的e呢？

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from gmpy2 import invert
from md5 import md5
from secret import p, q

e = ?????
n = p*q
phi = (p-1)*(q-1)
d = invert(e, phi)
ans = gcd(e,phi)

print n, e, d
print "Flag: DASCTF{%s}" %md5(str(p + q)).hexdigest()

"""
n = 8064259277274639864655809758868795854117113170423331934498023294296505063511386001711751916634810056911517464467899780578338013011453082479880809823762824723657495915284790349150975180933698827382368698861967973964030509129133021116919437755292590841218316278732797712538885232908975173746394816520256585937380642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913
"""

无力吐槽。。。这题附件锅了，n是两个重复的大整数拼起来的，因此要先取一半当作正确的n。之后的做法就多了，d过大可以考虑wiener或构造格，但是题目给了e为五位数的暗示，因此也只需要爆破一下e，当作已知e、d分解n即可。

exp.py:

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

n = "8064259277274639864655809758868795854117113170423331934498023294296505063511386001711751916634810056911517464467899780578338013011453082479880809823762824723657495915284790349150975180933698827382368698861967973964030509129133021116919437755292590841218316278732797712538885232908975173746394816520256585937380642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373"
n = 80642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913

for e in range(10000,100000):
    t = e*d - 1
    s = 0

    while t % 2 == 0:
        s += 1
        t //= 2

    found = False

    for i in range(1, s):
        c1 = pow(2, pow(2, i-1, n)*t, n)
        c2 = pow(2, pow(2, i, n)*t, n)
        if c1 != 1 and c1 != (-1 % n) and c2 == 1:
            p = GCD(c1 - 1, n)
            q = n // p
            print ("Flag: DASCTF{%s}" %hashlib.md5(str(p + q).encode()).hexdigest())
            exit()

得到flag：

DASCTF{4ae33bea90f030bfddb7ac4d9222ef8f}

(为什么主办方没有发现附件需要更新？/(ㄒoㄒ)/~~)




MCeorpkpleer

题目描述：

1
这数据都不全要怎么计算呢

题目：

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


def pubkey(list, m, w):
    pubkey_list = []
    for i in range(len(e_bin)):
        pubkey_list.append(w * list[i] % m)
    return pubkey_list


def e_cry(e, pubkey):
    pubkey_list = pubkey
    encode = 0
    for i in range(len(e)):
        encode += pubkey_list[i] * int(e[i]) % m
    return encode


p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = getPrime(64)
m = bytes_to_long(flag)
c = pow(m, e, n)

e_bin = (bin(e))[2:]
list = [pow(3, i) for i in range(len(e_bin))]
m = getPrime(len(bin(sum(list))) - 1)
w = getPrime(64)
pubkey = pubkey(list, m, w)
en_e = e_cry(e_bin, pubkey)

print('p = {}\n'
      'n = {}\n'
      'c = {}\n'
      'pubkey = {}\n'
      'en_e = {}'.format((p >> 435) << 435, n, c, pubkey, en_e))

观察题目，e_cry用于背包加密的就是e的二进制串本身，因此直接格基规约出e，再用coppersmith解已知p高位问题即可。

exp.ipynb：

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


#step1 已知p高位，恢复p、q
p4 = 139540788452365306201344680691061363403552933527922544113532931871057569249632300961012384092481349965600565669315386312075890938848151802133991344036696488204791984307057923179655351110456639347861739783538289295071556484465877192913103980697449775104351723521120185802327587352171892429135110880845830815744
n = 22687275367292715121023165106670108853938361902298846206862771935407158965874027802803638281495587478289987884478175402963651345721058971675312390474130344896656045501040131613951749912121302307319667377206302623735461295814304029815569792081676250351680394603150988291840152045153821466137945680377288968814340125983972875343193067740301088120701811835603840224481300390881804176310419837493233326574694092344562954466888826931087463507145512465506577802975542167456635224555763956520133324723112741833090389521889638959417580386320644108693480886579608925996338215190459826993010122431767343984393826487197759618771
pbits = 1024
kbits= 435
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits,beta=0.4)
if roots:
    p= p4 + int(roots[0])
    q = n//p

#step2 格基规约恢复e
b = [18143710780782459577, 54431132342347378731, 163293397027042136193, 489880191081126408579, 1469640573243379225737, 4408921719730137677211, 13226765159190413031633, 39680295477571239094899, 119040886432713717284697, 357122659298141151854091, 1071367977894423455562273, 3214103933683270366686819, 9642311801049811100060457, 28926935403149433300181371, 86780806209448299900544113, 260342418628344899701632339, 781027255885034699104897017, 2343081767655104097314691051, 7029245302965312291944073153, 21087735908895936875832219459, 63263207726687810627496658377, 189789623180063431882489975131, 569368869540190295647469925393, 1708106608620570886942409776179, 601827224419797931380408071500, 1805481673259393794141224214500, 893952418336266652976851386463, 2681857255008799958930554159389, 3523079163584485147344841221130, 1524252287869625983140881149316, 50264262166963219975822190911, 150792786500889659927466572733, 452378359502668979782399718199, 1357135078508006939347199154597, 4071405235524020818041597463791, 3169230503688232995231149877299, 462706308180869526799807117823, 1388118924542608580399421353469, 4164356773627825741198264060407, 3448085117999647764701149667147, 1299270151115113835209806487367, 3897810453345341505629419462101, 2648446157152195057994615872229, 3422845870014670444537026359650, 1223552407160181874717436564876, 3670657221480545624152309694628, 1966986461557807413563286569810, 1378466783231507511243038452393, 4135400349694522533729115357179, 3361215846199738142293703557463, 1038662335715384967987468158315, 3115987007146154903962404474945, 302975818554635252993570910761, 908927455663905758980712732283, 2726782366991717276942138196849, 3657854499533237101379593333510, 1928578295715881845245137486456, 1263242285705730806288591202331, 3789726857117192418865773606993, 2324195368467747797703678306905, 2450093503961328663664213663678, 2827787910442071261545819733997, 3960871129884299055190637944954, 2837628186769067706678271320788]
c = 31087054322877663244023458448558

n = len(b)
L = Matrix(ZZ, n+1, n+1)

for i in range(n):
    L[i,i] = 1
    L[i,-1] = b[i]
L[-1,-1] = -c

res = L.LLL()

for i in range(n + 1):
    M = res.row(i).list()
    flag = True
    for m in M:
        if m != 0 and m != 1:
            flag = False
            break
    if flag:
        e = M

#step3 RSA
c = 156879727064293983713540449709354153986555741467040286464656817265584766312996642691830194777204718013294370729900795379967954637233360644687807499775502507899321601376211142933572536311131955278039722631021587570212889988642265055045777870448827343999745781892044969377246509539272350727171791700388478710290244365826497917791913803035343900620641430005143841479362493138179077146820182826098057144121231954895739989984846588790277051812053349488382941698352320246217038444944941841831556417341663611407424355426767987304941762716818718024107781873815837487744195004393262412593608463400216124753724777502286239464
n = p*q
for i in range(len(e)):
    e[i] = str(e[i])
e = "".join(e)[:-1]
e = int(e,2)
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(int(pow(c,d,n))))

得到flag：

DASCTF{T81I_tPPS_6r7g_xlPi_OO3M_6vyV_Rkba}




XOR贯穿始终

题目描述：

1
一切都是有意义的，拿下它吧。

题目：

message.txt：

1
自由和谐和谐富强公正友善爱国公正法治法治文明和谐自由法治自由法治平等公正友善公正公正民主法治自由公正敬业和谐富强公正友善爱国和谐平等平等友善敬业法治敬业和谐富强法治平等平等友善敬业公正公正公正友善敬业法治平等平等诚信自由公正自由平等友善敬业公正友善法治和谐和谐

task.py：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from gmpy2 import gcd
from Crypto.Util.number import getPrime
from secret import enflag

p = getPrime(512)
q = getPrime(512)
n = q * p
phi = (p - 1) * (q - 1)
e = getPrime(17)
assert gcd(e, phi) == 1
# 以上信息生成了私钥文件,但文件被损坏了你能提取有用信息吗

c = pow(enflag, e, n)
print('c = ' + str(c))

'''
c = 91817924748361493215143897386603397612753451291462468066632608541316135642691873237492166541761504834463859351830616117238028454453831120079998631107520871612398404926417683282285787231775479511469825932022611941912754602165499500350038397852503264709127650106856760043956604644700201911063515109074933378818
'''

pri.pem：

1
2
3
4
5
6
7
8
9
10
11
12
-----BEGIN PRIVATE KEY-----
MIICdwIBADANBgkqhkiG9w0BAQEFAASCAmEwggJdAgEAAoGBALmtMy+2uH1ZtbIL
SuiAukFthyQRH5mp7UmLyzZQkdg9zEP9/5tgffikQ7ytx5kHySHnazgAO1sOzmYE
N4Axlev6uafiP8B1Eij97v5VkYJ1I9e3mtBNheTbXKoT8op+ASQ1fQaF4A8UzLuW
eZeZI8JTH/SH+bolAK3kiZXDFdkTAgMBAAECgYEAl067LaC7Cvs2A5cMPhfYsESv
IgcKN1CwW4Sd3u8dSphhgu7TgyzIuvwxbuo2g1BC6WwKhaI6vGN+csfw6nh98GEn
/p3D0huNroAYvf/DRRB9UnHdttX7wB+Mv3P0RBDWHgBiCDVvHFuFUV78cIs0tnbn
jxjU07aPV2XRC3AfA2ECQQDqWUNPVg3i6vTyHCL7EGkbeUheYpAAfcKCQrxjc5+5
X6A+XtgHAA1JHwykPlCpHUOmlA85DJF1ejuoImzlgRLJAkEAytTCnQF+MN2r1gaA
UETZyj5qMYT7Th8zKEVVVJjDawLnuX4usJ2FyRnjCkk86U75QSJhw5mMc0QnG25u
Gz3++w==
-----END PRIVATE KEY-----

第一层，解开社会主义核心价值观编码得到：

1
C0ngr4tulati0n5_y0u_fou^d_m3

第二层，恢复破损RSA私钥文件，base64解码后得到：

1
b'30820277020100300d06092a864886f70d0101010500048202613082025d02010002818100b9ad332fb6b87d59b5b20b4ae880ba416d8724111f99a9ed498bcb365091d83dcc43fdff9b607df8a443bcadc79907c921e76b38003b5b0ece660437803195ebfab9a7e23fc0751228fdeefe5591827523d7b79ad04d85e4db5caa13f28a7e0124357d0685e00f14ccbb9679979923c2531ff487f9ba2500ade48995c315d913020301000102818100974ebb2da0bb0afb3603970c3e17d8b044af22070a3750b05b849ddeef1d4a986182eed3832cc8bafc316eea36835042e96c0a85a23abc637e72c7f0ea787df06127fe9dc3d21b8dae8018bdffc345107d5271ddb6d5fbc01f8cbf73f44410d61e006208356f1c5b85515efc708b34b676e78f18d4d3b68f5765d10b701f0361024100ea59434f560de2eaf4f21c22fb10691b79485e6290007dc28242bc63739fb95fa03e5ed807000d491f0ca43e50a91d43a6940f390c91757a3ba8226ce58112c9024100cad4c29d017e30ddabd606805044d9ca3e6a3184fb4e1f332845555498c36b02e7b97e2eb09d85c919e30a493ce94ef9412261c3998c7344271b6e6e1b3dfefb'

按照RSA私钥格式还原，可以得到以下信息：

1
2
3
4
5
n 028181 00b9ad332fb6b87d59b5b20b4ae880ba416d8724111f99a9ed498bcb365091d83dcc43fdff9b607df8a443bcadc79907c921e76b38003b5b0ece660437803195ebfab9a7e23fc0751228fdeefe5591827523d7b79ad04d85e4db5caa13f28a7e0124357d0685e00f14ccbb9679979923c2531ff487f9ba2500ade48995c315d913
e 0203 010001
d 028181 00974ebb2da0bb0afb3603970c3e17d8b044af22070a3750b05b849ddeef1d4a986182eed3832cc8bafc316eea36835042e96c0a85a23abc637e72c7f0ea787df06127fe9dc3d21b8dae8018bdffc345107d5271ddb6d5fbc01f8cbf73f44410d61e006208356f1c5b85515efc708b34b676e78f18d4d3b68f5765d10b701f0361
p 0241 00ea59434f560de2eaf4f21c22fb10691b79485e6290007dc28242bc63739fb95fa03e5ed807000d491f0ca43e50a91d43a6940f390c91757a3ba8226ce58112c9
q 0241 00cad4c29d017e30ddabd606805044d9ca3e6a3184fb4e1f332845555498c36b02e7b97e2eb09d85c919e30a493ce94ef9412261c3998c7344271b6e6e1b3dfefb"

可以看到，私钥中的dp、dq以及inv(q,p)损坏了，但是剩下的值已经足够用于RSA解密，因此正常解密即可得到：

1
DASCTF{0e287wQ\x08R\x17\x00FGXYFZ\x07V\x03kIUCn\x02VDg\x01f\x0cN

发现题目描述XOR还没用上，将第一步社会主义核心价值观解密得到的串用于异或即可。

得到flag：

DASCTF{0e2874af5e422482378640e61d919e9a}




总结

总体难度确实不大，但是怎么说呢，题目有点坑，自己能力也还存在不足，下次加油吧。