糖醋小鸡块的blog
0%

2023-春秋杯网络安全联赛冬季赛-wp-crypto

发表于 更新于 分类于 Valine：

简单写一写题目wp。

not_wiener

题目：

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
from Crypto.Util.number import *
from gmpy2 import *
import random, os
from hashlib import sha1
from random import randrange
flag=b''
x = bytes_to_long(flag)

def gen_key():
    while True:
        q = getPrime(160)
        p = 2 * getPrime(1024-160) * q+1
        if isPrime(p):
            break
    h = random.randint(1, p - 1)
    g = powmod(h,(p-1)//q, p)
    y=pow(g,x,p)
    return p,q,g,y
def cry():
    a =
    p = getPrime(512)
    q = getPrime(512)
    d = getPrime(280)
    n = p * q
    e = inverse(d, (p - 1) * (q - 1))
    c = pow(a, e, n)
    return n,e,c

p,q,g,y=gen_key()
k1 = random.randint(1, q-1)
h1 = bytes_to_long(sha1(os.urandom(20)).digest())
r1 = pow(g, k1, p) % q
s1 = ((h1 + x*r1) * invert(k1, q))% q

n,e,c= cry()

a=
b= 17474742587088593627
k2 = a*k1 + b
h2 = bytes_to_long(sha1(os.urandom(20)).digest())
r2 = pow(g, k2, p) % q
s2 = ((h2 + x*r2) * invert(k2, q)) % q
print(n,e,c)
print(p,q,g,y)
print("h1:%s r1:%s s1:%s"%(h1,r1,s1))
print("h2:%s r2:%s s2:%s"%(h2,r2,s2))

题目看上去不算短，但其实对DSA比较熟悉的话，马上就可以看出这道题目的主体其实是一个线性k的DSA攻击，只是两个k的线性关系中，a被隐去了，所以就需要通过cry()函数提供的信息来解出。

而关于a的信息就是一个RSA加密结果，而在这个RSA加密中由于d较小，所以可以用boneh and durfee攻击得到d，然后就可以解密出a了。题目名字的not wiener也就用在这里，因为d的界大概是0.273，超过了wiener要求的$ \frac{1}{3}n^{\frac{1}{4}}$，但是却又小于boneh and durfee要求的理论上界0.292，而且并不极限所以不怎么需要调参数就能跑出来。

得到a过后就是个DSA的线性k攻击，主要思路就是用两次签名的式子消元解出私钥x，也就是题目中的flag。这一部分网上的资料很多并且我之前的博客也有讲过，其大概思路写下来也就是如下。因为有：

由于k是线性关系，所以选择消去k或者x都可以也都很方便，这里就选择消去x为例。首先把逆元乘过去：

为了消去x，再进行移项，并且配系数使两个等式可以作差：

现在作差就可以消去x了，得到一个如下形式的等式：

现在已经可以直接求这个方程得到k了，不过也可以合并同类项，然后直接得到k的表达式来计算：

得到k过后随便带入一个式子就能得到x也就是flag。

exp：

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

#part1 get a(boneh and durfee)
a = bytes_to_long(b"6d70e71d06e29c742b86a6da0108238e")

#part2 DSA's linear k attack
p= 161310487790785086482919800040790794252181955976860261806376528825054571226885460699399582301663712128659872558133023114896223014064381772944582265101778076462675402208451386747128794418362648706087358197370036248544508513485401475977401111270352593919906650855268709958151310928767086591887892397722958234379
q= 1115861146902610160756777713087325311747309309771
g= 61073566757714587321114447684333928353300944355112378054603585955730395524359123615359185275743626350773632555967063692889668342544616165017003197599818881844811647270423070958521148291118914198811187731689123176313367399492561288350530256722898205674043032421874788802819858438796795768177550638273020791962
y= 23678147495254433946472657196764372220306841739888385605070426528738230369489739339976134564575544246606937803367113623097260181789372915552172469427842482448570540429192377881186772226796452797182435452490307834205012154495575570994963829345053331967442452842152258650027916313982835119514473311305158299360
(h1, r1, s1) = 535874494834828755542711401117152397489711233142, 117859946800380767356190121030392492081340616512, 26966646740134065096660259687229179143947213779
(h2, r2, s2) = 236574518096866758760287021848258048065293279716, 863199000523521111517835459866422731857447792677, 517924607931342012033031470185302567344725962419

b = 17474742587088593627

k = (h1*r2-h2*r1 + b*s2*r1)*inverse(s1*r2-a*s2*r1,q) % q
x = (k*s1 - h1)*inverse(r1,q) % q
print(long_to_bytes(x))

#flag{l1near_k1s_unsafe}



ez_ECC

题目描述：

1
ECDSA算法确实是一种奇妙的算法，它已经在现实世界中得到了广泛的应用。但由于操作问题，我不小心在我的签名中泄露了太多的数据。即使我泄露了这么多数据，也应该是安全的吧？

题目：

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
from sage.all import *
import itertools
from hashlib import *
from Crypto.Util.number import *
from random import randint
import ecdsa
from math import ceil
from secret import secret,hint,flag,my_own_prime

assert flag.startwith(b'flag{')
assert bytes_to_long(secret).bit_length() == 384

curves = ecdsa.curves
NIST256p = curves.NIST256p
NIST384p = curves.NIST384p

class Random_EC():
    def __init__(self,state = None,Gen_Curve = True):
        if state == None:
            self.state = getRandomNBitInteger(512)
        else:
            self.state = state
        if Gen_Curve:
            self.int_curve()

    def int_curve(self,CURVE = None):
        if CURVE == None:
            self.Curve = NIST256p
            self.g = self.Curve.generator * self.state
            num1 = getRandomNBitInteger(256)
            num2 = getRandomNBitInteger(256)
            self.P = num2*self.g
            self.Q = num1*self.g

        # get the confirmed curve
        else:
            Curve, P, Q = CURVE
            self.Curve = Curve
            self.g = Curve.gen(0)
            self.P = P
            self.Q = Q

    def int_getkey(self):
        # To get the right random key
        t = int((self.state * self.Q).x())
        self.int_updade()
        return t%(2**250)

    def RSA_reinforce(self,key: int):
        p = my_own_prime(512)
        q = my_own_prime(512)
        n = p * q
        leak = p + q
        e = 16542764952
        c = pow(key, e, n)
        return (c, n, leak)

    def int_updade(self):
        self.state = int((self.state * self.P).x())

    def Random_key(self, n:int):
        out = 0
        number = ceil(n/250)
        for i in range(number):
            out = (out<<250) + self.int_getkey()
        return out % (2^n)


class ECDSA():
    def __init__(self):
        self.Random = Random_EC()
        self.Curve_length = 384
        self.curve = NIST384p
        self.gen = self.curve.generator
        self.pri_key = self.Random.Random_key((self.Curve_length*125)//192)
        self.pub_key = self.pri_key * self.gen
        self.order = self.curve.order

    def set_curve(self, curve) -> None:
        self.Random = Random_EC()
        self.Curve_length = 384
        self.curve = curve
        self.gen = curve.generator
        self.order = self.curve.order

    def set_pri_key(self, d: int) -> None:
        self.pri_key = d
        self.pub_key = d * self.gen

    def sign(self, msg: bytes, K_time:int) -> tuple:

        if K_time == 0:
            K = long_to_bytes(self.Random.Random_key(self.Curve_length))
            k = int(sha256(K).hexdigest(), 16)
        else:
            k = K_time

        P = k * self.gen
        r = int(P.x())
        k_v = int(inverse(k, self.order))
        e = int(sha256(msg).hexdigest(), 16)
        s = (e + self.pri_key * r) * k_v % self.order
        # print('k = ',k)
        return r, s, k

    def verify(self, msg: bytes, signature: tuple) -> bool:
        r, s = signature

        assert  0 < r < self.order
        assert 0 < s < self.order

        e = int(sha256(msg).hexdigest(), 16)
        w = int(inverse(s, self.order))
        u1 = e * w % self.order
        u2 = r * w % self.order
        P = u1 * self.gen + u2 * self.pub_key
        return int(r) == int(P.x())

    def into_secret(self, msg: int) -> tuple:
        # sage
        E = EllipticCurve(GF(int(NIST384p.curve.p())),[int(NIST384p.curve.a()), int(NIST384p.curve.b())])
        Point = E.lift_x(msg)
        Key = self.Random.Random_key(self.Curve_length)
        return int(Key)*Point


if __name__ == '__main__':
    hint = b"****************************************************"
    flag = bytes_to_long(flag)
    hint = bytes_to_long(hint)
    secret = bytes_to_long(secret)

    for i in range(250):
        SIGN = ECDSA()

        Hint = SIGN.Random.RSA_reinforce(hint)
        m1 = b'A typical Dual ec prng vulnerability applied to NSA, you can find its source in past papers.'
        m2 = b'Hope you have learned a good foundation of ECDSA, it can help you better answer and understand this problem.'
        C = flag^^secret
        into_secret = SIGN.into_secret(secret)
        sign1 = SIGN.sign(m1,0)
        sign2 = SIGN.sign(m2,sign1[2])

        print(f'C = {C}')
        print(f'Hint = {Hint}')
        print(f'pub_key = {SIGN.pub_key.x(),SIGN.pub_key.y()}')
        print(f'P = {int(SIGN.Random.P.x()),int(SIGN.Random.P.y())}')
        print(f'Q = {int(SIGN.Random.Q.x()),int(SIGN.Random.Q.y())}')
        print(f'sign1 = {sign1[:2]}')
        print(f'sign2 = {sign2[:2]}')
        print(f'into_secret = {into_secret}')
        print(f'-------------------------------------------------------------------')

Dual EC

这个题目就更长了，不过m1，m2中给了提示说题目与Dual EC伪随机数发生器相关，然后想到之前在Zima师傅的博客上好像有看到过一个有关的题目：

第七届蓝帽杯全国大学生网络安全技能大赛 - ZimaB1ue - 博客园 (cnblogs.com)

两个题目确实是有不少相似之处，但是为了彻底弄明白整个题目，还是要把整个Dual EC的加密过程与后门搞清楚，然后也找到了一篇很好的材料：

密码学后门系列Ⅰ: Dual EC | tl2cents blog

如果各位师傅对整个过程还不太清楚的话，学习一下上面这篇博客之后再来看题目，帮助会更大。

简单总结一下，Dual EC其实就是一个伪随机数发生器，他选取E=NIST256p作为用于产生伪随机数的椭圆曲线，其产生随机数的步骤是：

  • 选取E上的两个随机点P、Q
  • 初始化一个起始状态state(256bit)
  • 每次要获取一个随机数时，就计算当前的stateQ的横坐标，并按要求截取对应比特，当作本次产生的伪随机数；产生伪随机数后，更新state为stateP的横坐标

就是这么简洁，然后他的后门也很易懂，如果攻击者掌握了一个d值，这个d值满足：

那么对于任意一个产生的随机数，攻击者相当于知道了对应的stateQ点，那么又因为他知道d，所以他就有state*dQ点，也就是stateP点。也就是说，攻击者就能获取以后的所有伪随机数，这就是Dual EC的后门。

题解

首先就会发现这个hint其实很容易就能解，因为其实就是用leak和n去构造一个关于p和q的方程就能解出p、q。但是出题人还非要绕一下，e和phi是不互素的，还需要有限域开根或者AMM才能解出hint。总之解出来hint是：

1
Anything greater than 2^15 is really that's too big

当然现在是肯定完全不知道这句话是什么意思的，那就接着分析题目。接下来可以发现的一点是：所有签名的r值都相同。

这一点看代码也能看出，对m2的签名用的是签名m1时的k，所以存在一个k复用的问题。而签名的流程是：

而k相同会导致r相同，所以两式只需要简单作差消去k，就能求出pri的值：

既然能求出pri的值，而pri是250bit数量级，是一个state*Q的坐标的低250位，因此只需要爆破6位就可以得到这个点的完整坐标。而根据Dual EC的后门可以知道，如果我们有P=dQ的d这个值，就可以完全掌控后面所有的state，也就可以拿到之后用于加密secret的key值。那么问题就在于如何求出这个d。

而P、Q点的生成过程是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def __init__(self,state = None,Gen_Curve = True):
    if state == None:
        self.state = getRandomNBitInteger(512)
    else:
        self.state = state
    if Gen_Curve:
        self.int_curve()

def int_curve(self,CURVE = None):
    if CURVE == None:
        self.Curve = NIST256p
        self.g = self.Curve.generator * self.state
        num1 = getRandomNBitInteger(256)
        num2 = getRandomNBitInteger(256)
        self.P = num2*self.g
        self.Q = num1*self.g

蓝帽杯那个题目中，是由于num1和num2较小，所以可以用bsgs来碰撞出d值。但这个题目里很显然根本就没有任何方法可以利用。虽然说他给了很多组数据没错，但是这些数据之间其实可以说是完全独立的，没有什么联系。我也就卡在这一步了。

这个时候突然想起来貌似还有个hint没有用，他说的是：

1
Anything greater than 2^15 is really that's too big

然后就冒出一个比较大胆的猜想，这个意思难道是在说这么多组数据之中，存在一个小于2^15的d值？一旦有了这个想法，马上就能找到一个证明这个思路的依据：

  • 一共只有232组数据，和题目循环的250次不一样，显然动了手脚

。。。。。。那么题目给这么多组明明就没有关系的数据也就说得通了。但是感觉其实就和前面的AMM一样，其实没有多大必要在这里设一道坎的，多少还是有点脑洞。

那么接下来要做的是就是对每一组依次试一下看存不存在小于2^15的d满足P=dQ，然后用存在的那一组解密即可。这里也有一点小的优化技巧，就是不要这样写：

1
2
3
for i in range(2^15):
	if(i*Q == P):
		print(i)

这样是很自然的写法，但是会做很多多余的点加法计算，就比如你计算9Q的时候，其实在前面计算8Q时已经算过8Q的值，只需要用那个8Q的值求8Q+Q就能得到9Q了。所以更好的方式是写成：

1
2
3
4
5
6
7
8
P = NIST_256_CURVE(P)
Q = NIST_256_CURVE(Q)
q0 = Q
for i in range(2^15):
	if(q0 == P):
		print(j,i)
		print(P)
	q0 += Q

这样会减少很多时间，本来爆破完所有数据可能要两小时，但这样五六分钟就可以搞定。

求出d过后就是控制Dual EC生成我们需要的伪随机数key，然后求逆并作点乘得到secret，并与C异或就得出flag了。

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
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
from Crypto.Util.number import *
from gmpy2 import iroot
from hashlib import sha256
from tqdm import *
from math import ceil

#part1 get hint
if(0):
    c,n,leak = (12351774260625362799610458605055557349668978169954248709224197283033722650641969191523420968152180626844781310599988085824706330561484553939064653937267598659731237154241515349280967639128615784193195725170343153328247947729351564102666060302013802359410482179324719156651832539747622404434096773119440083329, 122908984806235457892414635852036332676574434804833208576141668077475917235411535511069143359388659946159724740722593181625712110278669227640297497485641848470391938438894136564046632275052354217712453952532772368082733299695485759213723305738760035793602060420638500827652832664161031815519780589765520132973, 22333858470427703056488469739724305644350178024239032705153649807913901449803887198889611591209527103787726531081225700412575986297091811550954958064297166)
    e = 16542764952
    p_q = iroot(leak^2-4*n,2)[0]
    p = (leak + p_q) // 2
    q = n // p
    cq = pow(c,inverse(e//24,q-1),q)
    PR.<x> = Zmod(q)[]
    f = x^24 - cq
    resq = f.roots()
    for i in resq:
        print(long_to_bytes(int(i[0])))
    #hint: Anything greater than 2^15 is really that's too big


#part2 get d
# NIST P-256
NIST_256_P = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
NIST_256_K = GF(NIST_256_P)
NIST_256_A = NIST_256_K(0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc)
NIST_256_B = NIST_256_K(0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b)
NIST_256_CURVE = EllipticCurve(NIST_256_K, (NIST_256_A, NIST_256_B))
NIST_256_GEN = NIST_256_CURVE(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
NIST_256_ORDER = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 * 0x1

# NIST P-384
NIST_384_P = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff
NIST_384_K = GF(NIST_384_P)
NIST_384_A = NIST_384_K(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000fffffffc)
NIST_384_B = NIST_384_K(0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef)
NIST_384_CURVE = EllipticCurve(NIST_384_K, (NIST_384_A, NIST_384_B))
NIST_384_GEN = NIST_384_CURVE(0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7, 0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f)
NIST_384_ORDER = 0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973 * 0x1


#结合hint在2^15内爆破，发现第201组数据有异常：32309*Q = P
if(0):
    with open(r"E:\vscode\py\crypto\春秋杯冬季赛 2023\ez_ECCc_output.txt","r") as f:
        for j in trange(250):
            for t in range(6):
                exec(f.readline())
            f.readline()
            P = NIST_256_CURVE(P)
            Q = NIST_256_CURVE(Q)
            q0 = Q
            for i in range(2^15):
                if(q0 == P):
                    print(j,i)
                    print(P)
                q0 += Q


#part3 get pri
C = 28370462154406144789913243909256020527531135264361458510233553021695306448248185548876492600895007348961847185821989
pub_key = (23063531651133054044852146745751828065565652508316078757465526964945889829041322577333868291426745685755660447945768 , 38213774544479557349161813523787259744626407961805163166366401345392394160489749007540120063131112167181615738936602)
P = (99376526638506705902714648195970871631891150648967956889439656483745513799077, 49286347987713888387330453808791204691290920954467279402308313223992253330920)
Q = (95979043517822469787247449840043678535429394578371796773017425344169131078878, 94108817998367868965643129518919867199519351407755146103464278196693149407197)
r1,s1 = (32594514971850903210957109229029032596013744664454613348001968983388557886022626485537652491952756966982681985873826, 33822531453262141722363336331985371357432586409495680846477948429687072595338746861106767975593900234281162130620713)
r2,s2 = (32594514971850903210957109229029032596013744664454613348001968983388557886022626485537652491952756966982681985873826, 30963116078493244587396392437563800584802728459796510243236725881496588593849796130551914519859427419450232539678279)
into_secret = (12219467168510963191933866108724307399115854676119007622103880230537250338471252977689989738440080704914043187805666 , 15140655916234412794356873631237108843402057349206472869810848889771783263614142207164313273971781373595696054566462)
e1 = int(sha256(b"A typical Dual ec prng vulnerability applied to NSA, you can find its source in past papers.").hexdigest(), 16)
e2 = int(sha256(b"Hope you have learned a good foundation of ECDSA, it can help you better answer and understand this problem.").hexdigest(), 16)
P = NIST_256_CURVE(P)
Q = NIST_256_CURVE(Q)
into_secret = NIST_384_CURVE(into_secret)

#shared-k attack
r = r1 = r2
o = NIST_384_ORDER
pri = (e2*s1-e1*s2)*inverse(r1*s2-r2*s1,o) % o

d = 32309
assert d*Q==P


#part4 Dual_EC backdoor
def int_getkey(state):
    # To get the right random key
    t = int((state * Q)[0])
    return t%(2**250)

def Random_key(n,state):
    temp = state
    out = 0
    number = ceil(n/250)
    for i in range(number):
        out = (out<<250) + int_getkey(temp)
        temp = int((temp*P)[0])
    return out % (2^n)

for i in range(2^6):
    r = i*2^250 + pri
    try:
        R = NIST_256_CURVE.lift_x(r)
        S = d*R
        state = int(S[0])
        key = Random_key(384,state)
        secret = int((inverse(key,o)*into_secret)[0])
        flag = long_to_bytes(int(secret^^C))
        if(b"flag" in flag):
            print(flag)
    except:
        pass

#flag{EC_PRNG_DUAL_NSA_18saL_0dh1_fh2ass0j_happy}

然后里面的ez_ECCc_output.txt这个文件，就是用一些全局替换对题目的output简单做了下处理，具体来说长下面这个样子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
pub_key = (7027198281618631109486546289418606436971306672049130948012540052979334787960281672746337056539439605928657120238948 , 30133540967149613975580795321921856644836168481028610007698327788048304814516517723608956804180632040981935542511437)
P = (17823116086876603269147060388719138662933817343024907156946194895842434214281, 80495309605411726002105878653283056375715403786488100338817913553121489831495)
Q = (46211125703713341292250779219515629306817624623159126615353410671209836378592, 94299460316426215202488880100669252287366820173365904372956288139806594541521)
sign1 = (6024266653924965558891017862145460120918687496468619682171279074596829568579614877691814275653589570598579410112071, 38177481088058121800207400725752708499346593588334743367566585331125114008356717480483226246659297274051563633828949)
sign2 = (6024266653924965558891017862145460120918687496468619682171279074596829568579614877691814275653589570598579410112071, 16369791614659331230610038275555078273062830812174831682189450495008185190975437959806536731511751926751061875511021)
into_secret = (18008353077466326893639562184181541471523657777178523896116425154484047074966064804018839658773729302151970933329800 , 9571770927641786375764966028815494982061521034302464222216678194218397272826459066078547700439904198852732709652236)

pub_key = (30952652464090154765700322426668773032420938414283809417202553773567574652233791704091301132956488800404306789683929 , 24434565373866540175538188663428739461189279984830219306744288993496065112238042640140414987229292993385061168991884)
P = (61503409678425616256814824706718701705285717980372750579649622220042379199063, 41978512646631377264391570171154885686312333682242627154032473621923333680935)
Q = (240014305523009712905368281643270225420175458523341650798225304665234408613, 32766026654026451889850025426197960803468793975163659845047322191441149171379)
sign1 = (5416210854653151719049022358066744158998560461940033379429156268115331437487444739683004920113952381284779550518474, 22015555679435957137370999648019545701879994735584708151177942763291571402267659885807969927530527596907814361814246)
sign2 = (5416210854653151719049022358066744158998560461940033379429156268115331437487444739683004920113952381284779550518474, 15040404282504296230825332673502390022066437191583605036725522476133316703777454934819829899317477856672211592302446)
into_secret = (193136219101302929403672002025568011182508516205015861233115071685682648716347978711510614153126503990830819166256328501117112004986822861149334210295759079734086379886321520537693689496869032983739365453033379003922594948804120874)

pub_key = (23099020203147370343025197263073676926643140376101288717875201483840703687544603053757488654765255677440760503713978 , 26114249417289088514441684945637228515176439146920836168796260800127107191830660494115786187518579103520377733967178)
P = (6394847313094066355092535870187127774709946937855744188908275981082478504869, 56646403494945610009636754829164685972045972046301795829835579362095319435811)
Q = (97716080684931874033397760667927007063270415118850496815451515445344135191822, 46519598120320390474773553046006013660088676744621584568185607341933322917054)
sign1 = (27086927550243061987095547909650882234082407878322873658240459376060724598083272966571400355987231527195299846018892, 23221862721323106146595388755440981055812829114828942824860327140563072790559259290097252303296557453898991310926722)
sign2 = (27086927550243061987095547909650882234082407878322873658240459376060724598083272966571400355987231527195299846018892, 22128212158572530213694047212096680763835792912115914158076280586875413266424638696597440583653147615519266382640505)
into_secret = (47049653917189265002689432956249150485391814948071645079435344313874379858788979536210104320058718078602413781801140430800896683283278287099214154956784204330473641487578641830520258749807353305263187416294227562859499072189690180)

......



CF is Crypto Faker

题目描述：

1
学过AI的都知道，这题不是“纯密码”，密码假面人要披上AI的战衣，但他永远不会卸下密码的假面。

题目(文件有六七个，这里只放对解题有用的几个文件)：

README.txt：

1
2
3
4
Please firstly pay attention to the file named as "task.py".
The real flag is a little strange.
However, there is no need to be messy in your mind just because of the "appearance" of the flag.
Just be self-confident!

task.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
from Crypto.Util.number import *
import initialize
import train
import valid
import test
import rec
from secret import message, flag_point

flag = b"flag{" + long_to_bytes(message) + long_to_bytes(flag_point) + b".}"

p = getPrime(512)
q = getPrime(512)
n = p * q
print("The significant parameter n: %s" % hex(n))
phi0 = (p - 1) * (q - 1)
r = rec.rec(p, q)
print("The unique parameter r: %s" % hex(r))

parameters = initialize.initialize(p, q)
wild_phi = parameters[0]
wild_e = parameters[1]
print("------")

print("Parameters are initialized to: \n  phi:%s\n" % hex(wild_phi), " e:%s" % hex(wild_e))
print("But they are wild and crazy!")
print("We have to give them a lesson!")
print("------")

parameters = train.train(wild_phi, wild_e, n, r, phi0)
trained_phi = parameters[0]
trained_e = parameters[1]
print("Parameters are trained to: \n  phi:%s\n" % hex(trained_phi), " e:%s" % hex(trained_e))
print("After training, the two naughty parameters are more and more normal.")
print("It's closer to your target!")
print("------")

parameters = valid.valid(trained_phi, trained_e, n)
y_valid = parameters[0]
print("The encrypted output in validation set is %s" % hex(y_valid))
print("After validation, the model is more and more stable.")
print("To test the real flag!")
print("------")

parameters = test.test(trained_phi, trained_e, n)
y_hat_cipher1 = parameters[0]
y_hat_cipher2 = parameters[1]
print("The final output is \n%s" % hex(y_hat_cipher1), "\n%s" % hex(y_hat_cipher2))
print("------")

output.txt：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
The significant parameter n: 0x81c5f040bfaea676120cd62c36ba7afb303561504bbf8609afa3da60fb6202ca875b0bd2a06143ebcd16fa615557ff159d97909160d68e1938b3ecaf57709b3d2698476b6dd203811b6a2ec6a6e2a7e213ab719bcd3ab49bb864b10e9c78ea3f501c0e2213dfe431043bb6f0cc2e8d77bfb43869b843af1a99ae81b87811e101
The unique parameter r: 0x4f37fe985d13ffde9867fa0063f68dea79196408b1404eadf03ea59297d629c2183a4a6a6647b6c4c99dd43bae8c4fa4691a608d20170fd42b18aef7efb3ae01cd3
------
Parameters are initialized to:
  phi:0x81c5f040bfaea676120cd62c36ba7afb303561504bbf8609afa3da60fb6202ca875b0bd2a06143ebcd16fa615557ff159d97909160d68e1938b3ecaf57709648d78eb17edb46dda768a97d57e6bd1c48657393b7c0d9c574c38cc0a3545ce7d209ade33b8ac6b31a41fe9f4ed62b4ddd7b99859b74915f2031dd2f5f0499a2f8
  e:0x2ebad696da6dda845bf03fdf34ee73d4849800de9267a5baa3c068e2d33a74727d00002fbfea775e5233087a9039d267130aa924a4f7fed3576f6ff7b8e1b2e8
But they are wild and crazy!
We have to give them a lesson!
------
The loss is -0x5144bdad7cc24f5348c5752dda0ff5fa7d72e36370d5af55eb6f590ac0764b843a06ee1a4651b8f3a6c878df56f1678454e58eaf0ede9a1eb0503dce6a1303b69e33bbaad112abb051a28d51a9fee629e89400a338bd02998568d044852f11e05572fc4a0ddacdf7342048295a4025394e77e973621a77ea5bbdb06af2cb72b2f8298e2cd16736454fd066d3d96a4f77cd094cd783ead17024de981df7ade84aa8c282b1ec6f8ec6ec4752727387ef637ba2a4eed8f83c77d5db14d297de8098
Parameters are trained to:
  phi:0x81c5f040bfaea676120cd62c36ba7afb303561504bbf8609afa3da60fb6202ca875b0bd2a06143ebcd16fa615557ff159d97909160d68e1938b3ecaf57709b3bb712fdcba325655f111918472d4353a66854ccda50b63a1047278c15a4b39cde898d054db87092958c7c05f8fa566dcd969b1ff4b7d1935c375a4af3bfc341b0
  e:0x2c22193ad9abcca2f67552fc76dd07b3ef883f3d755c95119cdf82bb6a07c970fd37e582bb49250d8efaa29b8a59c82059165c654206a9d7261f6b45a90dc69
After training, the two naughty parameters are more and more normal.
It's closer to your target!
------
The encrypted output in validation set is 0x775cbee546e7579f0a69645b59f72f5c8ff0c538dd9a6e755969dee2ffb8748073c089557801dfb8bfae15baba9a909f3addac142ad928ac7cc453c72166dda235128de12965df4308997416e054ab1ab9af55c60533c7374096aa2d05339900b3e14f7148930bf083eb1eb9fa22b9a997f85b39501d3a9bdfa08e3389b8f2fe
After validation, the model is more and more stable.
To test the real flag!
------
The final output is
0x29289e3d9275147b885b5061637564cbee3e4d9f48e52694e594f020e49da9b24d9246b2437fb2221fa86ca1a277f3fdd7ab5cad4738a02b66d47703ef816844a84c6c209c8251e8961c9ba2c791649e022627f86932d9700c3b1dc086e8b2747d0a5604955387a935464d3866dd4100b2f3d57603c728761d1d8ef7fdbdcbee
0x2b0059f88454e0e36269c809b5d5b6b28e5bab3c87b20f9e55635239331100a0a582241e7a385034698b61ebf24b519e868617ff67974cc907cc61be38755737f9a6dbeb7890ff55550b1af1ecf635112fcaaa8b07a3972b3c6728cbcf2a3973a4d7bd92affec7e065e0ae83cd36858e6d983785a3668a8b82709d78a69796af
------

这个题确实不知道是什么情况，因为trained_phi、e以及n全部都给了，所以直接解密最后的密文然后拼起来就得到flag。

开始觉得估计是题目失误多给了数据，但是想了下怎么也说不太通。比如要说是多给了n，所以需要联立方程求n的话，由于题目剩下几个文件里，rec.py中是整除，所以基本等于把q给你，而后面的train中无论如何phi也不会变(毕竟随便乱变的话解密也不正确了)，只是会修改e的值而已，所以可以直接根据phi和q得到n。而要是多给了phi的话，由于有q也可以直接解出phi。而e又不可能不给，所以很奇怪。

也许就是出题人好心送一波分数也说不定？

exp：

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 *

n = 0x81c5f040bfaea676120cd62c36ba7afb303561504bbf8609afa3da60fb6202ca875b0bd2a06143ebcd16fa615557ff159d97909160d68e1938b3ecaf57709b3d2698476b6dd203811b6a2ec6a6e2a7e213ab719bcd3ab49bb864b10e9c78ea3f501c0e2213dfe431043bb6f0cc2e8d77bfb43869b843af1a99ae81b87811e101
r = 0x4f37fe985d13ffde9867fa0063f68dea79196408b1404eadf03ea59297d629c2183a4a6a6647b6c4c99dd43bae8c4fa4691a608d20170fd42b18aef7efb3ae01cd3

#part1 get p,q
q = GCD(n,r)
p = n //q
print(p)

#part2 好像根本不需要上一个步骤。。
trained_phi = 0x81c5f040bfaea676120cd62c36ba7afb303561504bbf8609afa3da60fb6202ca875b0bd2a06143ebcd16fa615557ff159d97909160d68e1938b3ecaf57709b3bb712fdcba325655f111918472d4353a66854ccda50b63a1047278c15a4b39cde898d054db87092958c7c05f8fa566dcd969b1ff4b7d1935c375a4af3bfc341b0
trained_e = 0x2c22193ad9abcca2f67552fc76dd07b3ef883f3d755c95119cdf82bb6a07c970fd37e582bb49250d8efaa29b8a59c82059165c654206a9d7261f6b45a90dc69
c1 = 0x29289e3d9275147b885b5061637564cbee3e4d9f48e52694e594f020e49da9b24d9246b2437fb2221fa86ca1a277f3fdd7ab5cad4738a02b66d47703ef816844a84c6c209c8251e8961c9ba2c791649e022627f86932d9700c3b1dc086e8b2747d0a5604955387a935464d3866dd4100b2f3d57603c728761d1d8ef7fdbdcbee
c2 = 0x2b0059f88454e0e36269c809b5d5b6b28e5bab3c87b20f9e55635239331100a0a582241e7a385034698b61ebf24b519e868617ff67974cc907cc61be38755737f9a6dbeb7890ff55550b1af1ecf635112fcaaa8b07a3972b3c6728cbcf2a3973a4d7bd92affec7e065e0ae83cd36858e6d983785a3668a8b82709d78a69796af

d = inverse(trained_e, trained_phi)
m1 = pow(c1,d,n)
m2 = pow(c2,d,n)
print(long_to_bytes(m1))
print(long_to_bytes(m2))

#flag{With the method of machine learning, it is available for Crypto-er to develop the modern cryptography.Don't give up learning crypto.}