corCTF 2022

corCTF 2022, 写了两道简单的密码学

Crypto

tadpole

1
tadpoles only know the alphabet up to b... how will they ever know what p is?

题目是关于LCG的。给出了代码：

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 bytes_to_long, isPrime
from secrets import randbelow

p = bytes_to_long(open("flag.txt", "rb").read())
assert isPrime(p)

a = randbelow(p)
b = randbelow(p)

def f(s):
    return (a * s + b) % p

print("a = ", a)
print("b = ", b)
print("f(31337) = ", f(31337))
print("f(f(31337)) = ", f(f(31337)))

# a =  7904681699700731398014734140051852539595806699214201704996640156917030632322659247608208994194840235514587046537148300460058962186080655943804500265088604049870276334033409850015651340974377752209566343260236095126079946537115705967909011471361527517536608234561184232228641232031445095605905800675590040729
# b =  16276123569406561065481657801212560821090379741833362117064628294630146690975007397274564762071994252430611109538448562330994891595998956302505598671868738461167036849263008183930906881997588494441620076078667417828837239330797541019054284027314592321358909551790371565447129285494856611848340083448507929914
# f(31337) =  52926479498929750044944450970022719277159248911867759992013481774911823190312079157541825423250020665153531167070545276398175787563829542933394906173782217836783565154742242903537987641141610732290449825336292689379131350316072955262065808081711030055841841406454441280215520187695501682433223390854051207100
# f(f(31337)) =  65547980822717919074991147621216627925232640728803041128894527143789172030203362875900831296779973655308791371486165705460914922484808659375299900737148358509883361622225046840011907835671004704947767016613458301891561318029714351016012481309583866288472491239769813776978841785764693181622804797533665463949

LCG的标准格式为：

Ni+1=aNi+b mod pN_{i + 1} = aN_i + b \space mod \space p

也就是：

kp=aNi+b−Ni+1kp = aN_i + b - N_{i+1}

我们可以得到两个数字：k1pk_1p 和k2pk_2p。由于p是一个素数，所以这两个数的gcd即为p。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import libnum
from gmpy2 import gcd,is_prime

a = ...
b = ...
f = ... # f(31337)
ff = ... # f(f(31337))

k1 = a * 31337 + b - f
k2 = a * f + b - ff

p = gcd(k1, k2)
assert is_prime(p)

print(libnum.n2s(int(p)))

# b'corctf{1n_m4th3m4t1c5,_th3_3ucl1d14n_4lg0r1thm_1s_4n_3ff1c13nt_m3th0d_f0r_c0mput1ng_th3_GCD_0f_tw0_1nt3g3rs} <- this is flag adm'

luckyguess

1
i hope you're feeling lucky today

这题也是关于LCG的。

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
#!/usr/local/bin/python
from random import getrandbits

p = 2**521 - 1
a = getrandbits(521)
b = getrandbits(521)
print("a =", a)
print("b =", b)

try:
    x = int(input("enter your starting point: "))
    y = int(input("alright, what's your guess? "))
except:
    print("?")
    exit(-1)

r = getrandbits(20)

for _ in range(r):
    x = (x * a + b) % p


if x == y:
    print("wow, you are truly psychic! here, have a flag:", open("flag.txt").read())
else:
    print("sorry, you are not a true psychic... better luck next time")

可以看到LCG的三个参数已经给我们了。要求我们给出一个seed，并且给出r轮之后的LCG输出。

由于r是随机的，而且我们没有办法得到这个r。所以我们将目光放在一些特殊的值上面，比如，一个前后项相同的LCG序列。也就是Ni+1=NiN_{i+1}=N_i。

由此我们解一个模p剩余系的方程即可得到答案。

ax+b=a(ax+b)+b   mod pax + b = a(ax + b) + b \ \ \ mod \ p 

1
2
3
4
5
6
7
8
9
10
11
# sage

p = 2**521 - 1
a = ...
b = ...

R.<x> = Zmod(p)[]
f = (a*x + b) - (a*(a*x + b) + b)
print(f.roots()[0][0])

# wow, you are truly psychic! here, have a flag: corctf{r34l_psych1c5_d0nt_n33d_f1x3d_p01nt5_t0_tr1ck_th15_lcg!}

解的值是整个序列的值，以这个值为seed会导出一个所有导出数字都为seed的序列。所以这个值既是我们的起始值也是我们的猜测值。

但其实好像也不需要这么麻烦。

我们的目标是找到一个seed是的LCG输出的值不变。那么其实约束可以变为以下形式：

x=a∗x+b mod px = a*x + b \space mod \space p

其实也就变成了:

x=b1−a mod px = \frac{b}{1-a} \space mod \space p 

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

p = 2**521 - 1

sh = remote("be.ax", 31800)
sh.recvuntil(b"a = ")
a = int(sh.recvline().strip())
sh.recvuntil(b"b = ")
b = int(sh.recvline().strip())

x = b*inverse(1-a, p) % p

sh.sendline(str(x).encode("utf-8"))
sh.sendline(str(x).encode("utf-8"))
print(sh.recvline())

sh.close()
# b"enter your starting point: alright, what's your guess? wow, you are truly psychic! here, have a flag: corctf{r34l_psych1c5_d0nt_n33d_f1x3d_p01nt5_t0_tr1ck_th15_lcg!}\n"

hidE

1
This RSA encryption service is so secure we're not even going to tell you how we encrypted it

RSA相关，涉及为随机数和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
49
50
#!/usr/local/bin/python
import random
import time
import math
import binascii
from Crypto.Util.number import *


p, q = getPrime(512), getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)

flag = open('./flag.txt').read().encode()

random.seed(int(time.time()))

def encrypt(msg):
    e = random.randint(1, n)
    while math.gcd(e, phi) != 1:
        e = random.randint(1, n)
    pt = bytes_to_long(msg)
    ct = pow(pt, e, n)
    return binascii.hexlify(long_to_bytes(ct)).decode()


def main():
    print('Secure Encryption Service')
    print('Your modulus is:', n)
    while True:
        print('Options')
        print('-------')
        print('(1) Encrypt flag')
        print('(2) Encrypt message')
        print('(3) Quit')
        x = input('Choose an option: ')
        if x not in '123':
            print('Unrecognized option.')
            exit()
        elif x == '1':
            print('Here is your encrypted flag:', encrypt(flag))
        elif x == '2':
            msg = input('Enter your message in hex: ')
            print('Here is your encrypted message:', encrypt(binascii.unhexlify(msg)))
        elif x == '3':
            print('Bye')
            exit()

if __name__ == '__main__':
    main()

从运行脚本中我们可以看到，加密使用的所有e都是随机生成的。而且我们可以加密自己的数据，并且没有次数的限制。

1
2
3
flag = open('./flag.txt').read().encode()

random.seed(int(time.time()))

脚本中使用了时间作为随机数生成的seed。所以我们第一步就可以获得这个seed。方法很简单，我们能够得到对应明文的密文，那么我们只需要输入一个seed然后这个seed输出的e作为加密参数加密出来的结果和服务器提供的一致即可。所以在我们连接服务器之前，以本地时间得到seed即可得到一个开始值。

1
2
3
4
5
6
7
8
9
10
# sh -> pwn.remote
sh.sendline(b"2")
sh.sendline(b"41") # "A“
sh.recvuntil(b"Here is your encrypted message: ")
cipher = sh.recvline().strip().decode()
while True:
    random.seed(seed)
    if encrypt(binascii.unhexlify(b"41")) == cipher: break
    else : seed += 1
print(f"seed = {seed}")

这里有一个问题就是，这个encrypt函数需要使用phi。但是我们的本地是没有的。所以需要队encrypt函数稍做修改。我们知道phi一定一个偶数，因为 phi=(p−1)∗(q−1)phi = (p-1)*(q-1)而p和q都是素数也就是(p-1)和(q-1)都是偶数。

那么e要和phi互素就要求e要是奇数。

1
2
3
4
5
6
7
def encrypt(msg):
    e = random.randint(1, n)
    while e % 2 == 0 :   # an odd and an even number likely co-prime
        e = random.randint(1, n)
    pt = bytes_to_long(msg)
    ct = pow(pt, e, n)
    return binascii.hexlify(long_to_bytes(ct)).decode()

当然这样改是有点问题的，但是可以通过多次的尝试来解决。如果一段时间没有出结果，我们需要重启攻击脚本。

得到seed之后，也就相当于e我们得到了。n是无法分解的，这里我们能够得到flag的不同e的加密输出。所以这里可以选择使用共模攻击。

但是共模攻击有一个要求，gcd(e1,e2)=1gcd(e_1,e_2) = 1也就是要求我们前后两次的加密指数e要是互质的。

由于服务器对我们请求的加密的次数没有限制所以我们可以很轻松的找到一组满足要求的密文和加密指数。

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
import time
from pwn import *
import random
from Crypto.Util.number import *
from gmpy2 import invert, gcd

def encrypt(msg):
    e = random.randint(1, n)
    while e % 2 == 0 :   # an odd and an even number likely co-prime
        e = random.randint(1, n)
    pt = bytes_to_long(msg)
    ct = pow(pt, e, n)
    return binascii.hexlify(long_to_bytes(ct)).decode()

def CMA(n, c1, c2, e1, e2):
    def egcd(a, b):
        if b == 0:
            return a, 0
        else:
            x, y = egcd(b, a % b)
            return y, x - (a // b) * y
    s = egcd(e1, e2)
    s1 = s[0]
    s2 = s[1]

    if s1 < 0:
        s1 = - s1
        c1 = invert(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = invert(c2, n)
    m = pow(c1, s1, n) * pow(c2, s2, n) % n
    return m

seed = int(time.time())
sh = remote("be.ax", 31124)

sh.recvuntil(b"Your modulus is: ")
n = int(sh.recvline().strip())
print(f"n = {n}")

# if you run many seconds and the seed wasnt printed, you need retry this script
sh.sendline(b"2")
sh.sendline(b"41") # "A“
sh.recvuntil(b"Here is your encrypted message: ")
cipher = sh.recvline().strip().decode()
while True:
    random.seed(seed)
    if encrypt(binascii.unhexlify(b"41")) == cipher: break
    else : seed += 1
print(f"seed = {seed}")

sh.sendline(b"1")
sh.recvuntil(b"Here is your encrypted flag: ")
flag1 = int(b"0x" + sh.recvline().strip(), 16)
e1 = random.randint(1, n)
while e1 % 2 == 0:
    e1 = random.randint(1, n)

while True:
    sh.sendline(b"1")
    sh.recvuntil(b"Here is your encrypted flag: ")
    flag2 = int(b"0x" + sh.recvline().strip(), 16)
    e2 = random.randint(1, n)
    while e2 % 2 == 0:
        e2 = random.randint(1, n)

    if gcd(e1, e2) == 1:
        break

m = CMA(n, flag1, flag2, e1, e2)

print(long_to_bytes(int(m)))

# b'corctf{y34h_th4t_w4snt_v3ry_h1dd3n_tbh_l0l}\n'

exchanged

于2022-08-09新增

当时做题推导的时候公式写错了，麻了。现在来补上。

对了我的latex渲染挂掉了，这几篇博客的公式都没渲染出来，之后再处理这个事。

1
you could make an exchange out of this

给了源代码：

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
from secrets import randbelow

p = 142031099029600410074857132245225995042133907174773113428619183542435280521982827908693709967174895346639746117298434598064909317599742674575275028013832939859778024440938714958561951083471842387497181706195805000375824824688304388119038321175358608957437054475286727321806430701729130544065757189542110211847
a = randbelow(p)
b = randbelow(p)
s = randbelow(p)

print("p =", p)
print("a =", a)
print("b =", b)
print("s =", s)

a_priv = randbelow(p)
b_priv = randbelow(p)

def f(s):
    return (a * s + b) % p

def mult(s, n):
    for _ in range(n):
        s = f(s)
    return s

A = mult(s, a_priv)
B = mult(s, b_priv)

print("A =", A)
print("B =", B)

shared = mult(A, b_priv)
assert mult(B, a_priv) == shared

flag = open("flag.txt", "rb").read()
key = sha256(long_to_bytes(shared)).digest()[:16]
iv = long_to_bytes(randint(0, 2**128))
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
print(iv.hex() + cipher.encrypt(pad(flag, 16)).hex())


# p = 142031099029600410074857132245225995042133907174773113428619183542435280521982827908693709967174895346639746117298434598064909317599742674575275028013832939859778024440938714958561951083471842387497181706195805000375824824688304388119038321175358608957437054475286727321806430701729130544065757189542110211847
# a = 118090659823726532118457015460393501353551257181901234830868805299366725758012165845638977878322282762929021570278435511082796994178870962500440332899721398426189888618654464380851733007647761349698218193871563040337609238025971961729401986114391957513108804134147523112841191971447906617102015540889276702905
# b = 57950149871006152434673020146375196555892205626959676251724410016184935825712508121123309360222777559827093965468965268147720027647842492655071706063669328135127202250040935414836416360350924218462798003878266563205893267635176851677889275076622582116735064397099811275094311855310291134721254402338711815917
# s = 35701581351111604654913348867007078339402691770410368133625030427202791057766853103510974089592411344065769957370802617378495161837442670157827768677411871042401500071366317439681461271483880858007469502453361706001973441902698612564888892738986839322028935932565866492285930239231621460094395437739108335763
# A = 27055699502555282613679205402426727304359886337822675232856463708560598772666004663660052528328692282077165590259495090388216629240053397041429587052611133163886938471164829537589711598253115270161090086180001501227164925199272064309777701514693535680247097233110602308486009083412543129797852747444605837628
# B = 132178320037112737009726468367471898242195923568158234871773607005424001152694338993978703689030147215843125095282272730052868843423659165019475476788785426513627877574198334376818205173785102362137159225281640301442638067549414775820844039938433118586793458501467811405967773962568614238426424346683176754273
# e0364f9f55fc27fc46f3ab1dc9db48fa482eae28750eaba12f4f76091b099b01fdb64212f66caa6f366934c3b9929bad37997b3f9d071ce3c74d3e36acb26d6efc9caa2508ed023828583a236400d64e

可以看到关键是找到shared的值。求shared值要求我们得到a_private和b_private。对于LCG数列有：

A(0)=sA(1)=as+bA(2)=a(as+b)+b=a2s+ab+b...A(n)=ans+an−1b+an−2b+...+bA(0) = s \\ A(1) = as + b \\ A(2) = a(as + b) + b = a^2s + ab + b \\ ... \\ A(n) = a^ns + a^{n-1}b + a^{n-2}b + ...+b

于是推得LCG数列的第n项为：

A(n)=ans+b1−an1−a mod pA(n) = a^ns + b\frac{1-a^n}{1-a} \space mod \space p

由于我们知道A(n)的值，所以我们能求n，这样我们就得到了a_private，同理可得b_private。

代码如下：

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
from gmpy2 import invert as inverse
from sympy import discrete_log
from hashlib import sha256
from Crypto.Util.number import *
from Crypto.Cipher import AES

invert = lambda x,p: int(inverse(x,p))

p = ...
a = ...
b = ...
s = ...
A = ...
B = ...
cipher = "e0364f9f55fc27fc46f3ab1dc9db48fa482eae28750eaba12f4f76091b099b01fdb64212f66caa6f366934c3b9929bad37997b3f9d071ce3c74d3e36acb26d6efc9caa2508ed023828583a236400d64e"

a_k = (A*(1-a) - b)*invert(s - s*a -b, p) % p
b_k = (B*(1-a) - b)*invert(s - s*a -b, p) % p
a_private = discrete_log(p, a_k, a)
b_private = discrete_log(p, b_k, a)

print(f"key_a = {a_private}")
print(f"key_b = {b_private}")

key_shared = a_private + b_private

shared = ( pow(a, key_shared, p)*s + b*(1-pow(a, key_shared, p))*invert(1-a, p) ) % p

key = sha256(long_to_bytes(shared)).digest()[:16]
iv = bytes.fromhex(cipher[:32])
c = bytes.fromhex(cipher[32:])

decoder = AES.new(key, AES.MODE_CBC, iv=iv)
print(decoder.decrypt(c))

# b'corctf{th1s_lcg_3xch4ng3_1s_4_l1ttl3_1ns3cur3_f0r_n0w}\n\n\n\n\n\n\n\n\n\n'
CTF writeup Crypto

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！