NepCTF 2022

signin

p,q极其近似，对n开根号取前后素数求出p,q

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

n = 19955580242010925349026385826277356862322608500430230515928936214328341334162349408990409245298441768036250429913772953915537485025323789254947881868366911379717813713406996010824562645958646441589124825897348626601466594149743648589703323284919806371555688798726766034226044561171215392728880842964598154362131942585577722616354074267803330013886538511795383890371097812191816934883393255463554256887559394146851379087386846398690114807642170885445050850978579391063585254346364297374019309370189128443081285875218288166996242359495992824824109894071316525623741755423467173894812627595135675814789191820979950786791
e = 65537
c_mod_p = 32087476819370469840242617415402189007173583393431940289526096277088796498999849060235750455260897143027010566292541554247738211165214410052782944239055659645055068913404216441100218886028415095562520911677409842046139862877354601487378542714918065194110094824176055917454013488494374453496445104680546085816
c_mod_q = 59525076096565721328350936302014853798695106815890830036017737946936659488345231377005951566231961079087016626410792549096788255680730275579842963019533111895111371299157077454009624496993522735647049730706272867590368692485377454608513865895352910757518148630781337674813729235453169946609851250274688614922
tmp = gmpy2.iroot(n,2)[0]
q = sympy.nextprime(tmp)
p = n // q
d = gmpy2.invert(e,(p-1)*(q-1))
'''m一般都不会很长，完全可以用p,q作为模数
m = pow(c_mod_p,gmpy2.invert(e,p-1),p)
print(long_to_bytes(m))
'''
invq = gmpy2.invert(q,p)
invp = gmpy2.invert(p,q)
c = (c_mod_p*invq*q + c_mod_q*invp*p)%n
m = pow(c,d,n)
print(long_to_bytes(m))

中学数学

已知$q=next_prime(p+(p>>500))$，则
$$
q=\lfloor (1+\frac{1}{2^{500}})p\rfloor+r
$$
其中r是满足q为素数的最小整数，
$$
n=pq=\lfloor (1+\dfrac{1}{2^{500}})p^2\rfloor+rp
$$
于是
$$
⌊(1+\dfrac{1}{2^{500}})n⌋=⌊(1+\dfrac{1}{2^{500}})p⌋^2+⌊(1+\dfrac{1}{2^{500}})rp⌋>⌊(1+\dfrac{1}{2^{500}})p⌋^2
$$
又有
$$
⌊(1+\dfrac{1}{2^{500}})n⌋=⌊(1+\dfrac{1}{2^{500}})p⌋^2+⌊(1+\dfrac{1}{2^{500}})rp⌋<⌊(1+\dfrac{1}{2^{500}})p⌋^2+2⌊(1+\dfrac{1}{2^{500}})rp⌋+r^2 = q^2
$$
所以
$$
⌊(1+\dfrac{1}{2^{500}})p⌋<\sqrt{\lfloor(1+\frac{1}{2^{500}})n\rfloor}<\lfloor(1+\frac{1}{2^{500}})p\rfloor+r
$$
即
$$
q−r<\sqrt{⌊(1+\dfrac{1}{2^{500}})n⌋}
$$
所以
$$
\lfloor(1+\frac{1}{2^{500}})p\rfloor<\sqrt{\lfloor(1+\frac{1}{2^{500}})n\rfloor}<\lfloor(1+\frac{1}{2^{500}})p\rfloor+r
$$
得到了无需爆破的形式。

但注意到next_prime算法的本质逻辑即是通过不断枚举奇数判断是否为素数，而这里n的分解保证了其必为素数，再判断素数的话属于是多此一举（浪费计算资源），所以我们可以根据素数分布公式或next_prime的方案向下枚举，得到唯一分解即可。

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

n= 13776679754786305830793674359562910178503525293501875259698297791987196248336062506951151345232816992904634767521007443634017633687862289928715870204388479258679577315915061740028494078672493226329115247979108035669870651598111762906959057540508657823948600824548819666985698501483261504641066030188603032714383272686110228221709062681957025702835354151145335986966796484545336983392388743498515384930244837403932600464428196236533563039992819408281355416477094656741439388971695931526610641826910750926961557362454734732247864647404836037293509009829775634926600458845832805085222154851310850740227722601054242115507
c= 6253975396639688013947622483271226838902346034187241970785550830715516801386404802832796746428068354515287579293520381463797045055114065533348514688044281004266071342722261719304097175009672596062130939189624163728328429608123325223000160428261082507446604698345173189268359115612698883860396660563679801383563588818099088505120717238037463747828729693649297904035253985982099474025883550074375828799938384533606092448272306356003096283602697757642323962299153853559914553690456801745940925602411053578841756504799815771173679267389055390097241148454899265156705442028845650177138185876173539754631720573266723359186
e = 0x10001

q = iroot((n + (n >> 500)),2)[0]
print(isPrime(q))#False
while True:
    q = next_prime(q)
    if n % q == 0:
        p = n//q
        d = invert(e, (p-1)*(q-1))
        m = pow(c, d, n)
        flag = long_to_bytes(m)
        if b'flag' in flag or b'NepCTF' in flag:
            print(flag)
            break

bd_key

767.pdf (iacr.org)

Dual EC (asecuritysite.com)

比赛时思路:

分析代码发现，do_schnorr_identification()能影响（或有作用）的是challenge()，分析getRandomNBytes()，发现给出的c = __Dual_EC_DRBG(0) 。

在忽略s_i等其他变量的，通过getRandomNBytes()分析key和c的获取：

1
2
c = __Dual_EC_DRBG(self.h_adin)
key = __Dual_EC_DRBG(self.h_adin) >> 128

虽然看上去可以通过c求key，但是在执行上面两个函数时会影响s_i,进而影响到key。

于是乎大致思路就是通过c来求出r_i之前的s_i，然后走一遍流程就可以得到key。

分析__Dual_EC_DRBG()，得出以下公式

1
2
s_i = (s_i*P)[0]
c = r_i = (s_i*Q)[0]

我们知道P,Q,c，利用P,Q和生成的点都在椭圆曲线上，兴许可以联立方程求出s_i？

利用椭圆曲线方程，已知x求y，求出生成点，然后利用ECDLP求解s_i（好像跑不出来）

注意类名，放网上一搜就有相关内容！！！

Dual_EC_DBRG问题，有兴趣的可以搜一搜其背后的故事，真有点魔幻。

整合一下上面的分析，生成c的过程有方程如下：

1
2
3
(1)s_i = (s_i*P)[0]
(2)c = r_i = (s_i*Q)[0]
(3)s_i = (s_i*P)[0]

我们知道d，这就相当于给了个后门。

假设横坐标为c的点为R = (c,y)，根据上面的(1)(2)(3)公式以及$P=d*Q$，有
$$
d*R = d*(s_i*Q) = s_i*(d*Q) = s_i*P
$$
于是可以直接得到(3)的$s_i$ ，再走一遍流程就可以得到key。

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
# sagemath

from Crypto.Util.number import *
from Crypto.Cipher import AES

p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
E = EllipticCurve(GF(p), [-3, b])
Qx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
Qy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
Q = E(Qx, Qy)
d = 66604141534275704476445937214374130642068729921454877238730830814793201802544
P = d * Q
c = 59100197418944667413449341413044666843726352095054393072750502893110293231642
ct = 25645992443585671366815910836517434170297823176311632150463962979581372384075859802765045877741181123347569267185176

def dec_flag(ct, key):
    cipher = AES.new(key, AES.MODE_ECB)
    ct = long_to_bytes(ct)
    flag = cipher.decrypt(ct)
    print(flag)

assert E.is_x_coord(c)#检测c是否是x坐标，即存在点，x坐标为c
s1_Q = E.lift_x(c)#找点
s2 = (d * s1_Q)[0].lift()
s3 = (s2 * P)[0].lift()
r3 = (s3 * Q)[0].lift()
k = r3 >> ((32 - 16) * 8)
key = long_to_bytes(k)
dec_flag(ct, key)

P or S

分析enc()函数：

1
2
3
4
5
6
7
8
def enc(v):
    t = v
    for i in keys:
        q = []
        for j in Pbox:
            q.append(sum([t[k] for k in j]) % 2)
        t = [int(q[j]) ^ int(i[j]) for j in range(32)]
    return t

细心点可以发现 $q$ 的生成可以看成 $GF(2)$ 上的矩阵运算（行乘列，很像吧），假设 $Pbox$ 的矩阵为 $P$ (32×32)，传入的明文的矩阵为 $M$ (32×1)，则中间生成矩阵为 $T=P*M$ ，$t$ 这一步就是额外加一个矩阵 $K_i$(32×1)，于是6次循环有如下公式
$$
c = P*(P*(P*(P*(P*(P*M+K_1)+K_2)+K_3)+K_4)+K_5)+K_6 = P^6*M+\sum_{i=0}^{n=6}P^{6-i}K_i
$$
通过已知一组明密文可以计算出对应的$\sum_{i=0}^{n=6}P^{6-i}K_i$ 。

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

Pbox = [
    [0, 3, 6, 9, 10, 11, 13, 16, 18, 19, 20, 24, 25, 27, 28, 29, 30, 31],
    [0, 1, 3, 8, 9, 11, 12, 14, 16, 18, 19, 23, 24, 25, 26, 28, 29],
    [0, 1, 2, 3, 9, 10, 11, 13, 19, 20, 22, 25, 27, 28, 29, 31],
    [0, 2, 3, 5, 6, 7, 8, 13, 16, 19, 21, 25, 26, 27, 28],
    [2, 4, 6, 7, 9, 11, 12, 13, 16, 17, 20, 21, 22, 23, 24, 25, 27, 31],
    [2, 10, 13, 15, 16, 17, 21, 22, 23, 24, 29, 31],
    [1, 2, 8, 11, 12, 13, 16, 17, 19, 21, 22, 24, 25, 26, 27, 28, 30, 31],
    [0, 3, 6, 13, 14, 17, 19, 21, 22, 23, 26, 27, 28],
    [1, 5, 7, 8, 11, 12, 14, 15, 19, 23, 25, 27, 31],
    [0, 2, 3, 6, 7, 8, 9, 10, 11, 12, 16, 18, 19, 22, 23, 24, 25, 26, 27, 28],
    [0, 1, 6, 7, 10, 15, 16, 21, 24, 25, 29, 30],
    [1, 4, 5, 6, 7, 12, 13, 15, 18, 19, 20, 22, 26, 27, 29, 31],
    [0, 3, 5, 8, 9, 17, 21, 22, 24, 25, 26, 27, 30],
    [0, 2, 3, 4, 5, 6, 7, 8, 11, 17, 19, 20, 24, 25, 26, 27, 30],
    [2, 6, 7, 8, 11, 12, 14, 16, 20, 21, 22, 24, 29, 30, 31],
    [0, 2, 5, 6, 7, 8, 9, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
    [0, 1, 2, 3, 4, 5, 8, 10, 11, 12, 13, 16, 17, 18, 20, 21, 22, 23, 25, 26, 28, 29, 30],
    [3, 5, 6, 8, 10, 13, 14, 17, 19, 20, 21, 22, 24, 26, 27, 29, 30],
    [1, 3, 6, 12, 14, 15, 16, 17, 18, 21, 24, 25, 26, 27, 28],
    [0, 1, 2, 3, 5, 6, 7, 8, 9, 12, 13, 19, 20, 23, 26, 29, 30],
    [3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 20, 21, 22, 25, 26, 27, 28, 29, 30],
    [0, 1, 2, 4, 6, 7, 9, 10, 11, 13, 15, 16, 18, 19, 20, 21, 25, 31],
    [0, 2, 7, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
    [1, 2, 3, 5, 7, 8, 18, 19, 21, 22, 23, 25, 31],
    [3, 4, 7, 8, 10, 11, 13, 14, 17, 18, 19, 21, 22, 23, 24, 28, 29],
    [0, 2, 6, 7, 8, 10, 11, 12, 13, 16, 18, 19, 21, 23, 31],
    [0, 1, 3, 4, 8, 13, 14, 16, 18, 19, 21, 26, 27, 30, 31],
    [5, 6, 7, 9, 13, 14, 15, 18, 19, 20, 21, 24, 25, 28],
    [1, 3, 4, 5, 6, 7, 11, 14, 16, 17, 19, 20, 21, 22, 23, 25, 30, 31],
    [2, 3, 4, 6, 7, 11, 13, 17, 18, 19, 20, 23, 24, 25, 26, 28, 29, 30, 31],
    [0, 1, 2, 3, 4, 7, 9, 10, 13, 15, 16, 19, 22, 23, 24, 25, 27],
    [0, 1, 3, 4, 12, 16, 18, 19, 26, 30]
]

#get Matrix P
P = []
for i in range(32):
    t = [0]*32
    for j in range(len(Pbox[i])):
        t[Pbox[i][j]] = 1
    P.append(t)
P = Matrix(GF(2),P)
P6 = P^6
inv_P6 = P6^(-1)

#get sum of key_i*P^j
def getsum(data,cipher):
    A = [[int(i)] for i in data]#A = matrix(32,1,A)
    A = Matrix(GF(2),A)
    C = [[int(i)] for i in cipher]
    C = Matrix(GF(2),C)
    sum = C - P6*A
    return sum

#to decrypto
def solve(B,C):#B is key_sum,C is cipher
    C = Matrix(GF(2),C)
    f = inv_P6*(C-B)
    return f.list()


ciphertext = '0111110000100101000001101011110111101100000010110011101111000101111110111111100100100010001011000101000110110011111101000001001000000101111000001110001111001001100100111000011011101111111101001011100000100100110011111101100111001100111111110001111011101100'
format = bin(bytes_to_long(b'flag'))[2:].zfill(32)
sum = getsum(format,ciphertext[:32])

fb = ''
for i in range(0, len(ciphertext), 32):
    t = solve(sum,[[int(j)] for j in ciphertext[i:i + 32]])
    fb += "".join(str(j) for j in t)

flag = long_to_bytes(int(fb,2))
print(flag)

参考：

NepCTF 2022 (wolai.com)

Crypto
#Dual_EC
NepCTF 2022
http://example.com/2022/07/21/CTF/NepCTF 2022/
作者
gla2xy
发布于
2022年7月21日
许可协议