2022DASTF十月赛

Crypto

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
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 *
from secret import flag

def encrypt1(n):
    n1 = hex(n>>200).encode()
    n2 = str(hex(n))[20:].encode()
    return n1,n2

def encrypt2(m , n_1):
    c_1 = pow(m,e_1,n_1)
    print('c_1 = '+str(c_1))

def encrypt3(m , n_2):
    c_2 = pow( m , e_2 , n_2)
    print('c_2 = '+str(c_2))

def encrypt4(m):
    k = getPrime(512)
    m = m % k
    c_3 = pow(m, e_2, n_3)
    print('c_3 = ' + str(c_3))
    print('m = ' + str(m))
    print('k = ' + str(k))

m1,m2 = encrypt1(flag)
m1 = bytes_to_long(m1)
m2 = bytes_to_long(m2)

print('n_2 = ' + str(n_2))
print('n_3 = ' + str(n_3))
print('e_1 = ' + str(e_1))
print('e_2 = ' + str(e_2))

encrypt2(m1,n_1)
encrypt3(n_1,n_2)
encrypt4(m2)

'''
n_2 = 675835056744450121024004008337170937331109883435712066354955474563267257037603081555653829598886559337325172694278764741403348512872239277008719548968016702852609803016353158454788807563316656327979897318887566108985783153878668451688372252234938716250621575338314779485058267785731636967957494369458211599823364746908763588582489400785865427060804408606617016267936273888743392372620816053927031794575978032607311497491069242347165424963308662091557862342478844612402720375931726316909635118113432836702120449010
n_3 = 91294511667572917673898699346231897684542006136956966126836916292947639514392684487940336406038086150289315439796780158189004157494824987037667065310517044311794725172075653186677331434123198117797575528982908532086038107428540586044471407073066169603930082133459486076777574046803264038780927350142555712567
e_1 = 65537
e_2 = 3
c_1 = 47029848959680138397125259006172340325269302342762903311733700258745280761154948381409328053449580957972265859283407071931484707002138926840483316880087281153554181290481533
c_2 = 332431
c_3 = 11951299411967534922967467740790967733301092706094553308467975774492025797106594440070380723007894861454249455013202734019215071856834943490096156048504952328784989777263664832098681831398770963056616417301705739505187754236801407014715780468333977293887519001724078504320344074325196167699818117367329779609
m = 9530454742891231590945778054072843874837824815724564463369259282490619049557772650832818763768769359762168560563265763313176741847581931364
k = 8139616873420730499092246564709331937498029453340099806219977060224838957080870950877930756958455278369862703151353509623205172658012437573652818022676431
'''

解m1要先求出n_1，n_1的加密为低指数加密，爆破可以得出n_1，yafu分解然后解密c_1。

m2部分根据代码有公式
$$
\begin{cases}
m_2 = m + t*k\\
c_3 = m^{e_2}\mod n_3
\end{cases}
==>c_3=(m_2-t*k)^{e_2}\mod n_3
$$
于是在模$n_3$的域上构造$f = (m_2-t*k)^{e_2} - c_3$ ，解出$t=0$，即$m_2=m$。

$m_1$，$m_2$解出来的有重叠部分，需去除。

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
from binascii import hexlify,unhexlify
from Crypto.Util.number import *
from gmpy2 import iroot,invert

#n_2是偶数
n_2 = 675835056744450121024004008337170937331109883435712066354955474563267257037603081555653829598886559337325172694278764741403348512872239277008719548968016702852609803016353158454788807563316656327979897318887566108985783153878668451688372252234938716250621575338314779485058267785731636967957494369458211599823364746908763588582489400785865427060804408606617016267936273888743392372620816053927031794575978032607311497491069242347165424963308662091557862342478844612402720375931726316909635118113432836702120449010
n_3 = 91294511667572917673898699346231897684542006136956966126836916292947639514392684487940336406038086150289315439796780158189004157494824987037667065310517044311794725172075653186677331434123198117797575528982908532086038107428540586044471407073066169603930082133459486076777574046803264038780927350142555712567
e_1 = 65537
e_2 = 3
c_1 = 47029848959680138397125259006172340325269302342762903311733700258745280761154948381409328053449580957972265859283407071931484707002138926840483316880087281153554181290481533
c_2 = 332431
c_3 = 11951299411967534922967467740790967733301092706094553308467975774492025797106594440070380723007894861454249455013202734019215071856834943490096156048504952328784989777263664832098681831398770963056616417301705739505187754236801407014715780468333977293887519001724078504320344074325196167699818117367329779609
m = 9530454742891231590945778054072843874837824815724564463369259282490619049557772650832818763768769359762168560563265763313176741847581931364
k = 8139616873420730499092246564709331937498029453340099806219977060224838957080870950877930756958455278369862703151353509623205172658012437573652818022676431

#低指数爆破
t = 0
tmp = c_2
while 1:
    if(iroot(tmp,3)[1]):
        n_1 = iroot(tmp,3)[0]
        print(f'n_1 = {n_1}')
        print(f't={t}')
        break
    tmp += n_2
    t += 1

#yafu n_1
p = 2224243981
q = 2732337821
r = 11585031296201346891716939633970482508158508580350404805965250133832632323150440185890235814142601827544669601048550999405490149435265122374459158586377571

phi = (p-1)*(q-1)*(r-1)
d = invert(e_1,phi)
m1 = pow(c_1,d,n_1)
# print(long_to_bytes(m1))
#0x666c61677b3230366538353964
mm = 0x666c61677b3230366538353964
flag1 = long_to_bytes(mm)
print(flag1)
'''sage
n_3 = 91294511667572917673898699346231897684542006136956966126836916292947639514392684487940336406038086150289315439796780158189004157494824987037667065310517044311794725172075653186677331434123198117797575528982908532086038107428540586044471407073066169603930082133459486076777574046803264038780927350142555712567
e_2 = 3
c_3 = 11951299411967534922967467740790967733301092706094553308467975774492025797106594440070380723007894861454249455013202734019215071856834943490096156048504952328784989777263664832098681831398770963056616417301705739505187754236801407014715780468333977293887519001724078504320344074325196167699818117367329779609
m = 9530454742891231590945778054072843874837824815724564463369259282490619049557772650832818763768769359762168560563265763313176741847581931364
k = 8139616873420730499092246564709331937498029453340099806219977060224838957080870950877930756958455278369862703151353509623205172658012437573652818022676431
p.<x> = PolynomialRing(Zmod(n_3))
f= (m+x*k)^3 - c_3
print(f.monic().small_roots())
# [0]
'''
assert m**3 % n_3 == c_3
flag2 = unhexlify(long_to_bytes(m))
print(flag2)
#有重复的字符
# flag{206e859d859d8e854c4f600cb12757bbf9f5}
# DASCTF{206e859d8e854c4f600cb12757bbf9f5}

Proof_Yourself

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
import gmpy2 as gy
import random
import functools
from datetime import datetime
from Crypto.Cipher import AES
import base64
import os

_N = gy.next_prime(2 ** 512)
_rand_int = functools.partial(random.SystemRandom().randint, 0)

class Encryptor():
    def __init__(self):
        self.pubKey = None
        self.priKey = None
        self.r = None

    def __gen_prime__(self, rs, n_bits):
        p = gy.mpz_urandomb(rs, n_bits)
        while not gy.is_prime(p):
            p += 1
        return p

    def __key_gen__(self, n_bits=512):
        while True:
            rs = gy.random_state(datetime.now().microsecond)
            p = self.__gen_prime__(rs, n_bits)
            q = self.__gen_prime__(rs, n_bits)
            n = p * q
            lmd = (p - 1) * (q - 1)
            if gy.gcd(n, lmd) == 1:
                break

        g = n + 1
        mu = gy.invert(lmd, n)
        self.pubKey = [n, g]
        self.priKey = [lmd, mu]
        return (self.pubKey, self.priKey)

    def encipher(self, plaintext):
        m = plaintext
        n, g = self.pubKey
        if self.r is None:
            r = gy.mpz_random(gy.random_state(datetime.now().microsecond), n)
            while gy.gcd(n, r) != 1:
                r += 1
            self.r = r
        else:
            r = self.r
        ciphertext = gy.powmod(g, m, n ** 2) * gy.powmod(r, n, n ** 2) % (n ** 2)#Paillier同态加密
        return ciphertext

    def decipher(self, ciphertext):
        # The decryption process is hidden
        return 0xffffffff


class Proof():
    def __init__(self):
        self.pubKey = None
        self.proof_param = None
        self.pre_param = None
        self.d = None

    def setup(self, pk, c1, c2, c3, m1, m2, r1, r2, r3):
        self.pubKey = pk
        self.proof_param = [c1, c2, c3, m1, m2, r1, r2, r3]

    def pre_work_verify(self):
        c1, c2, c3, m1, m2, r1, r2, r3 = self.proof_param
        m4 = gy.mpz_random(gy.random_state(datetime.now().microsecond), self.pubKey[0])
        pai = Encryptor()
        pai.pubKey = self.pubKey
        c4 = pai.encipher(m4)
        r4 = pai.r
        pai.r = None #然后会重新生成r

        c5 = pai.encipher(m2 * m4)
        r5 = pai.r
        pai.r = None

        self.pre_param = [c4, m4, r4, c5, r5]
        return c4, c5

    def set_d(self, d):
        self.d = d

    def verify(self):
        n_2q = self.pubKey[0] ** 2
        c1, c2, c3, m1, m2, r1, r2, r3 = self.proof_param
        c4, m4, r4, c5, r5 = self.pre_param
        d = self.d

        e = d * m1 + m4
        a1 = pow(r1, d, n_2q) * r4 % n_2q
        b1 = r5 * pow(r3, d, n_2q) % n_2q
        a2 = pow(r2, e, n_2q) * gy.invert(b1, n_2q) % n_2q
        b2 = pow(c3, d, n_2q) * c5 % n_2q

        enc = Encryptor()
        enc.pubKey = self.pubKey
        enc.r = pow(r1, d, n_2q) * r4 % n_2q
        if pow(c1, d, n_2q) * c4 % n_2q != enc.encipher(d * m1 + m4): # 这里要 ==
            return False
        enc.r = a2
        return pow(c2, e, n_2q) * gy.invert(b2, n_2q) % n_2q == enc.encipher(0) #必须从这里返回，且为True

class MProof():
    def __init__(self):
        self.pubKey = None
        self.priKey = None
        self.cs = None
        self.rs = None
        self.k = None
        self.t = 9

    def generate_param(self, pk, cs, rs, k):
        self.pubKey = pk[0]
        self.priKey = pk[1]
        self.cs = cs
        self.rs = rs
        self.k = k

    def verify(self, d):
        enc = Encryptor()
        enc.pubKey = self.pubKey
        enc.priKey = self.priKey
        cs = self.cs
        rs = self.rs
        k = self.k
        t = self.t
        assert k == enc.decipher(cs[0])
        for i in range(1, t - 1):
            c1 = cs[0]
            c2 = cs[i - 1]
            c3 = cs[i]
            m2 = enc.decipher(cs[i - 1])
            r1 = rs[0]
            r2 = rs[i - 1]
            r3 = rs[i]

            proof = Proof()
            proof.setup(self.pubKey, c1, c2, c3, k, m2, r1, r2, r3)

            proof.pre_work_verify()
            proof.set_d(d)

            if not proof.verify(): # 这里要返回True
                return False
        return True

def main():
    flag = os.environ["flag for GFCTF2022-Crypto Proof Yourself"]
    k = _rand_int(_N - 1)
    print("k: ", k)
    d = _rand_int(_N - 1)
    print("d: ", d)
    param = eval(input("please proof yourself: "))

    cs = param['cs']
    rs = param['rs']
    pk = param['pk']

    print(pk[0])
    print(rs)
    mp = MProof()
    mp.generate_param(pk, cs, rs, k)
    if mp.verify(d):
        s = 1
        for i in cs:
            s *= i
            s %= _N
        aes = AES.new(str(s)[:32].encode(), AES.MODE_ECB)
        flag = flag.encode()
        while len(flag) % AES.block_size != 0:
            flag += b'\x00'
        c = aes.encrypt(flag)
        c = base64.b64encode(c)
        print(c)
    else:
        print("you're not yourself!")

if __name__ == '__main__':
    main()

  • MProof类中的verify()部分

    1
    2
    k == enc.decipher(cs[0])
    m2 = enc.decipher(cs[i - 1])

    说明 $k(m_1)$ 与 $c_1(cs[0])$是一组明密文，$m_2$ 与 $c_2(cs[i-1])$是一组明密文。

    1
    proof.pre_work_verify()

    说明$c_4,m_4,r_4$是一组，$c_5,m_2*m_4$是一组。

  • Proof类中的verify()部分

    就是一堆公式然后不断化简。

    首先我们要明确verify返回的值必须是True，也就是从最后一个return返回，所以以下两个等式成立

    1
    2
    ① pow(c1, d, n_2q) * c4 % n_2q == enc.encipher(d * m1 + m4)
    ② pow(c2, e, n_2q) * gy.invert(b2, n_2q) % n_2q == enc.encipher(0)

    根据代码有以下公式
    $$
    \begin{cases}
    \quad e = d*m_1+m_4\\
    \quad a_1 = r_1^d*r_4 \% n^2\\
    \quad b_1 = r_5*r_3^d \% n^2\\
    \quad a_2 = r_2^e*b_1^{-1} \% n^2\\
    \quad b_2 = c_3^d*c_5 \% n^2\\
    \quad r = r_1^d*r_4 \% n^2(在①中)\\
    \quad r = r_2^e*b_1^{-1} \% n^2(在②中)
    \end{cases}
    $$
    对①进行化简，有
    $$
    \begin{align}
    c_1^d*c_4 &≡ g^{d*m_1+m_4}*r^n \mod n^2\\
    c_1^d*c_4 &≡ g^{d*m_1}*g^{m_4}*r_1^{d*n}*r_4^n \mod n^2\\
    c_1^d &≡ g^{d*m_1}*r_1^{d*n} \mod n^2\\
    c_1 &≡ g^{m_1}*r_1^n \mod n^2\
    \end{align}
    $$
    因为不可能从这里返回False，所以$c_1,m_1,r_1$是一组。

    对②进行化简，有
    $$
    \begin{align}
    c_2^e*b_2^{-1}&≡r^n \mod n^2\\
    c_2^e*b_2^{-1} &≡ r_2^{e*n}*b_1^{-n} \mod n^2\\
    c_2^{e}*b_1^n&≡r_2^{e*n}*b_2 \mod n^2\\
    c_2^{e}*r_5^n*r_3^{d*n}&≡r_2^{e*n}*c_3^d*c_5 \mod n^2\\
    c_2^e*(g^{m_2*m_4}*r_5^n)*r_3^{d*n} &≡ r_2^{e*n}*c_3^d*c_5*g^{m_2*m_4} \mod n^2\\
    c_2^e*r_3^{d*n} &≡ r_2^{e*n}*c_3^d*g^{m_2*m_4} \mod n^2\\
    g^{e*m_2}*(c_2^e)*(g^{m_3*d}*r_3^{d*n})&≡(g^{e*m_2}*r_2^{e*n})*(c_3^d)*g^{m_3*d}*g^{m_2*m_4} \mod n^2\\
    g^{e*m_2}*(c_2^e)*(g^{m_3}*r_3^n)^d&≡(g^{m_2}*r_2^n)^e*(c_3^d)*g^{m_3*d+m_2*m_4}\mod n^2
    \end{align}
    $$
    因为是Paillier同态加密，要使得②成立，极有可能是$m_2,c_2,r_2$和$m_3,c_3,r_3$分别为一组。故
    $$
    \begin{align}
    g^{e*m_2}&≡g^{m_3*d+m_2*m_4}\mod n^2\\
    e*m_2 &≡ m_3*d+m_2*m_4\mod φ(n^2)\\
    m_1*m_2&≡m_3\mod φ(n^2)
    \end{align}
    $$
    因为我们要求$c_i(即cs[i])$，所以将上述等式转换为
    $$
    \begin{align}
    m_1*m_2&≡m_3\mod φ(n^2)\\
    g^{m_1*m_2} &≡ g^{m_3} \mod n^2\\
    c_3 &≡ g^{m_1*m_2}*r_3^n \mod n^2\\
    cs_i &≡ g^{m_0*m_{i-1}}*r_i^n \mod n^2 \quad,i∈[1,t-1](转换成跟cs_i对应的下标)
    \end{align}
    $$
    前面的等式①的推导已经得到了$cs_0$的加密公式为
    $$
    cs_0 ≡ g^{m_0}*r_0^n\mod n^2
    $$
    然后根据MProof.verify()中的for循环，有
    $$
    \begin{align}
    i=1时,有m_1&=m_0*m_0=k^2\\
    i=2时,有m_2&=m_0*m_1=k^3\\…
    \end{align}
    $$
    而$m_0 = k$，故$m_i = k^{(i+1)}$，$i∈[0,t-1]$。故求$cs_i和cs_0$的公式可合并为
    $$
    cs_i ≡ g^{k^{(i+1)}}*r_i^n \mod n^2 \quad,i∈[0,t-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
import base64
from Crypto.Cipher import AES
import gmpy2

t = 9
k = 11279504534075664648994853756208309836888259081316987836068134565254532996039360827546417609514423428910384542842117375028420780633866653159695275393368525
d = 10221665185656075870670995630062725196664430105025904882602057721789662854574978018794504264934209067929011475979200882531626936657436063908347321906634698
n, g = pk = [48818225666351727287207574448645102762537417687444983843100304919285725062598967011116889972414214836241381602471131430626879759533369143920487299838261148460925610689261484965443528954172944323770181595455493018560585886136460076911284321702606299935385905187490733877700172236929823996030434548431963845417, 48818225666351727287207574448645102762537417687444983843100304919285725062598967011116889972414214836241381602471131430626879759533369143920487299838261148460925610689261484965443528954172944323770181595455493018560585886136460076911284321702606299935385905187490733877700172236929823996030434548431963845418]
rs = [7017835444643249654271082822123622319668823350427792339866057586668389112104752762656197513200543360993520983724957230042201508973227162755834455588213955577427129770220944523362675094151087610149577572745132843096125306714661937578722687485657829513505193501779196974947234280267216675125252078851200384511, 11926419785881734844311665235521692826579887231998046623960612782040667947241499738956574205257924912658501445776452678070116549164041547529876699253294424780763676555577471679864402445858336882095147665188840642566915806261768356998922735189200720213585973193760859762565499482788728104626011895319246070666, 42849056994192303821377400100288133996583852078950720125488290595760149056455393645072193770289570081775019724341661792638180771853532605128714550478335577195726229688940314874397525687446284173037582151644404387768530054222357908795147990398041926171515316417608763369700129500666902309717940977358807727525, 569456034348887900543839220414996643340590767934767190156995758515165897120739581783360541347732807472270912131379832279120488198273011491688831841399829273608264595546111772893429063435258947915507670361144515456182164834954215193382047579447153761545329658264080907041640135001986168270265476743567482692, 3882702856238247498776796661311784006527802920550510293689922477675526354665322642479849874736259591551374176143098918760791897417239069537473431992448934909453262242143947844529634470612342500819944459175262578570970986439077317400529787443727039336276584314877540411569781766947088676007567558786204756622, 34782235652997768305926510863494232383450368915240504241174297907018847182768375070693257841105403770877838315164696945795337955510221866283665914601590428884905858716454103802020812133141150426745257298797890891272342044576267512614330845263269719988690131903885166576787904418689220619969803389055644879283, 41592967491176047854989428284345162501007190601227408901070248204262133730525966700579489348638677097892234799114781714483501047161590906530561145043956218048476973681993844049727301616425300184917461748554561251157129032137452031152035104390819324726028213814331358281835310137578997975640720667608761964678, 2578609445428238934369429276761562264275224240462388961086309951471476260768389780485799474959219453117497280460546287104687546269870223859389440049894002336889078632572487931627548008400365190508858547984095575105551066221392543458691134989381950316158817283668533035090342510306180189918351739923749743570]
#len(rs) = 8
_N = gmpy2.next_prime(2 ** 512)
c = b'Oq5bkAPCCT6W3CskX+2uqtY5wrhs+2DqupzjIJ0u/Yl0m/Ig1/uvrSWdezrqLxHG'

cs = [0 for _ in range(len(rs))]
n_2 = n**2
# cs[0] = pow(g, k, n_2)*pow(rs[0], n, n_2) % n_2
m_list = [k**(i+1) for i in range(len(rs))]
for i in range(len(rs)):
    cs[i] = pow(g, m_list[i], n_2)*pow(rs[i], n, n_2) % n_2

s = 1
for i in cs:
    s *= i
    s %= _N
aes = AES.new(str(s)[:32].encode(), AES.MODE_ECB)
c = base64.b64decode(c)
flag = aes.decrypt(c)
print(flag)

Recover_Secret

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
128
129
130
import gmpy2 as gy
import random
import functools
import libnum
from Crypto.Util import number
from datetime import datetime
import os
import sys

of = open('output','w')
sys.stdout = of
_N = gy.next_prime(2 ** 512)
_rand_int = functools.partial(random.SystemRandom().randint, 0)

class Encryptor():
    def __init__(self):
        self.pubKey = None
        self.priKey = None

    def __gen_prime__(self, rs, n_bits):
        p = gy.mpz_urandomb(rs, n_bits)
        while not gy.is_prime(p):
            p += 1
        return p

    def __key_gen__(self, n_bits=512):
        while True:
            rs = gy.random_state(datetime.now().microsecond)
            p = self.__gen_prime__(rs, n_bits)
            q = self.__gen_prime__(rs, n_bits)
            n = p * q
            lmd = (p - 1) * (q - 1)
            if gy.gcd(n, lmd) == 1:
                break

        g = n + 1
        mu = gy.invert(lmd, n)
        self.pubKey = [n, g]
        self.priKey = [lmd, mu]
        return (self.pubKey, self.priKey)

    def encipher(self, plaintext):
        m = plaintext
        n, g = self.pubKey
        r = gy.mpz_random(gy.random_state(datetime.now().microsecond), n)
        while gy.gcd(n, r) != 1:
            r += 1
        ciphertext = gy.powmod(g, m, n ** 2) * gy.powmod(r, n, n ** 2) % (n ** 2) #Paillier同态加密
        return ciphertext

class Commit:
    def __init__(self):
        self.param = None

    def __key_gen__(self, n): # 参数n相同，则产生的q,g,h相同
        p = n
        r = 1
        while True:
            q = r * p + 1
            if gy.is_prime(q):
                break
            r += 1
        x = q - 1
        while True:
            g = x ** r % q
            if g != 1:
                break
            x -= 1
        while True:
            h = x ** r % q
            if(g != h and h != 1):
                break
            x -= 1
        self.param = q, g, h

    def commit(self, m):
        q, g, h = self.param
        r = number.getRandomRange(1, q - 1)
        c = (pow(g, m, q) * pow(h, r, q)) % q #Benaloh加密
        return c, r

def shuffle(X, Y, x):
    res = []
    for i in range(len(X)):
        res.append([i, X[i], Y[i]])
        for j in range(x):
            res.append([i, X[i] + random.randint(-X[i], X[i]), Y[i] + random.randint(-Y[i], Y[i])])
    random.shuffle(res) #随机排序
    return res

def main():
    k = 6
    sk = []
    flag = os.environ["flag for GFCTF2022-Crypto Recover Secret"]
    secret = libnum.s2n(flag)
    assert len(bin(secret)) < 514
    enc = Encryptor()
    sk = [enc.__key_gen__() for i in range(k)]
    print(sk)

    s = [_rand_int(_N - 1) for i in range(k)]
    s[0] = secret

    v = Commit()
    v.__key_gen__(_N)
    print(v.param)
    cr = [v.commit(s[i]) for i in range(k)]
    c = [i[0] for i in cr]
    print(c)

    X = []
    Y = []
    for i in range(1, k + 1):
        xs = 1
        enc.pubKey = sk[i - 1][0]  # [n_i,g_i]
        n_2q = enc.pubKey[0] ** 2  # n_i^2
        for j in range(k):
            xs *= pow(enc.encipher(i ** j), cr[j][1], n_2q)
        X.append(xs)

        ys = 1
        for j in range(k):
            ys *= pow(enc.encipher(i ** j), s[j], n_2q)
        Y.append(ys)

    X_Y = shuffle(X, Y, 51)
    print(X_Y)

if __name__ == '__main__':
    main()

类Encryptor是Paillier同态加密，类Commit貌似是Benaloh加密。

重点在X、Y的生成以及shuffle混淆，先看X、Y的生成，他们的生成公式类似，为
$$
xs_i = E(i^0,r_0)^{cr_0}*E(i^1,r_1)^{cr_1}*…*E(i^5,r_5)^{cr_5}\mod n_i^2 \tag{1}
$$

$$
ys_i = E(i^0,r_0)^{s_0}*E(i^1,r_1)^{s_1}*…*E(i^5,r_5)^{s_5}\mod n_i^2 \tag{2}
$$

（这里的$cr$指$cr$中的$r$。）

根据Paillier同态加密的特点，有
$$
D(E(m_1,r_1),E(m_2,r_2)\mod n^2) = m_1+m_2\mod n
$$

$$
D(E(m_1,r_1)^k\mod n^2)=k*m\mod n
$$

于是公式(1)(2)的解密公式为
$$
D(xs_i) = cr_0*i^0+…+cr_5*i^5 \mod n_i
$$

$$
D(ys_i) = s_0*i^0+…+s_5*i^5 \mod n_i
$$

因为$xs,ys$都有6个，而系数已知，所以可以构建矩阵方程解出$cr_i,s_i$。

但是$X,Y$被打乱了顺序。

根据commit()函数，有
$$
c_i = g^{s_i}*h^{cr_i}
$$
进行如下转换
$$
c_0 = g^{s_0}*h^{cr_0}，c_1^i = g^{s_1*i}*h^{cr_1*i},c_2^{i^2} = g^{s_2*i^2}*h^{cr_2*i^2},…\
$$
于是有
$$
\begin{align}
c_0*c_1^i*c_2^{i^2}*…*c_5^{i^5}
&= g^{s_0+s_1*i+s_2*i^2+…+s_5*i^5}*h^{cr_0+c_r1*i+cr_2*i^2+…+cr_5*i^5}\\
&=g^{D(ys_i)}*h^{D(xs_i)}\mod q
\end{align}
$$
因此通过此等式可得到正确的$X,Y$。

求出$Y$后，因为有六个未知数和六个方程，所以建个矩阵求解
$$
{\left[
\matrix{
s_0 & s_1 & … & s_5
}
\right]}
*
\left[
\matrix{
1^0 & 2^0 & … & 5^0\\
1^1 & 2^1 & … & 5^1\\
…\\
1^6 & 2^6 & … & 5^6
}
\right]
=\left[
\matrix{
dec\_y_0 & dec\_y_1 & … & dec\_y_5
}
\right]
$$

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

class Encryptor():
    def __init__(self):
        self.pubKey = None
        self.priKey = None

    def decipher(self, ciphertext):
        n, g = self.pubKey
        lmd, mu = self.priKey
        plaintext = (pow(ciphertext, lmd, n**2) - 1)*mu//n % n # Paillier同态解密
        # plaintext = (pow(ciphertext, lmd, n ** 2) - 1) // n  * mu % n
        return plaintext


_N = next_prime(2 ** 512)
with open(r'output', 'rb') as f:
    sk = eval(f.readline().decode())
    vparam = eval(f.readline().decode())
    c = eval(f.readline().decode())
    X_Y = eval(f.readline().decode())

X_Y = sorted(X_Y, key=lambda x: x[0])
k = 6
q, g, h = vparam


m_cs = []
for i in range(1, k + 1):
    cs = 1
    for j in range(k):
        cs = cs * pow(c[j], i**j, q) % q #错误操作-> cs *= pow(c[j], i**j, q) % q 取余在相乘
    m_cs.append(cs)


real_XY = []
enc = Encryptor()
for each in X_Y:
    i = each[0]
    enc.pubKey = sk[i][0]
    enc.priKey = sk[i][1]
    de_xs = enc.decipher(each[1])
    de_ys = enc.decipher(each[2])
    gh = pow(g, de_ys, q)*pow(h, de_xs, q) % q
    if gh == m_cs[i]:
        real_XY.append([i, de_xs, de_ys])

# print(real_XY)
k = 6
Y = [int(each[2]) for each in real_XY]
Y = Matrix(Y)

A = []
for j in range(k):
    v = [i**j for i in range(1,k+1)]
    A.append(v)
A = Matrix(A)

S = A.solve_left(Y)
print(S)
print(long_to_bytes(int(S[0][0])))

参考：

DASCTF X GFCTF 2022 ｜十月赛官方Write Up (qq.com)

其他加密算法 | Lazzaro (lazzzaro.github.io)

Crypto
#低指数爆破 #Paillier
2022DASTF十月赛
http://example.com/2022/10/26/CTF/2022DASTF十月赛/
作者
gla2xy
发布于
2022年10月26日
许可协议