exchanged

exchanged.py

from Cryptodome.Util.number import *
from Cryptodome.Cipher import AES
from Cryptodome.Util.Padding import pad
from hashlib import sha256
from secrets import randbelow
from random import randint

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())

题目是用LCG来产生DH密钥交换的公钥(A,B)。我们要计算shared必须要解出a_priv或者b_priv。

$$f(s)=as+b\pmod{p}$$

$$\begin{aligned} f^{n}(s) &= a^ns+b\sum^{n}_{i=0}a^i \\ &=a^ns+b\frac{a^n-1}{a-1} \end{aligned} \\ f^n(s)(a-1)=a^ns(a-1)+b(a^n-1) \\ \frac{f^n(s)(a-1) + b}{as - s + b}=a^n $$

然后求对数就可以得到n

from sage.all import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from hashlib import sha256

p = 142031099029600410074857132245225995042133907174773113428619183542435280521982827908693709967174895346639746117298434598064909317599742674575275028013832939859778024440938714958561951083471842387497181706195805000375824824688304388119038321175358608957437054475286727321806430701729130544065757189542110211847
a = 118090659823726532118457015460393501353551257181901234830868805299366725758012165845638977878322282762929021570278435511082796994178870962500440332899721398426189888618654464380851733007647761349698218193871563040337609238025971961729401986114391957513108804134147523112841191971447906617102015540889276702905
b = 57950149871006152434673020146375196555892205626959676251724410016184935825712508121123309360222777559827093965468965268147720027647842492655071706063669328135127202250040935414836416360350924218462798003878266563205893267635176851677889275076622582116735064397099811275094311855310291134721254402338711815917
s = 35701581351111604654913348867007078339402691770410368133625030427202791057766853103510974089592411344065769957370802617378495161837442670157827768677411871042401500071366317439681461271483880858007469502453361706001973441902698612564888892738986839322028935932565866492285930239231621460094395437739108335763
A = 27055699502555282613679205402426727304359886337822675232856463708560598772666004663660052528328692282077165590259495090388216629240053397041429587052611133163886938471164829537589711598253115270161090086180001501227164925199272064309777701514693535680247097233110602308486009083412543129797852747444605837628
B = 132178320037112737009726468367471898242195923568158234871773607005424001152694338993978703689030147215843125095282272730052868843423659165019475476788785426513627877574198334376818205173785102362137159225281640301442638067549414775820844039938433118586793458501467811405967773962568614238426424346683176754273
ct = bytes.fromhex(
"e0364f9f55fc27fc46f3ab1dc9db48fa482eae28750eaba12f4f76091b099b01fdb64212f66caa6f366934c3b9929bad37997b3f9d071ce3c74d3e36acb26d6efc9caa2508ed023828583a236400d64e"
)

F = GF(p)
a_power_n = F((A*(a - 1) + b) / (a*s - s + b))
n = discrete_log(F(a_power_n), F(a))
shared = F(a)^n * B + b * F(F(a)^n - 1) / F(a - 1)
key = sha256(long_to_bytes(int(shared))).digest()[:16]
print(unpad(AES.new(key, AES.MODE_CBC, iv=ct[:16]).decrypt(ct[16:]), 16))
#corctf{th1s_lcg_3xch4ng3_1s_4_l1ttl3_1ns3cur3_f0r_n0w}

失败的尝试

一开始看到这种递归计算的时候是想用矩阵的

$$ f(s)= \begin{bmatrix} a & b \\ 0 & 1 \end{bmatrix} \begin{bmatrix} s \\ 1 \end{bmatrix} = \begin{bmatrix} as+b \\ 1 \end{bmatrix} \\ f^n(s) = \begin{bmatrix} a & b \\ 0 & 1 \end{bmatrix}^n \begin{bmatrix} s \\ 1 \end{bmatrix} $$

我们令

$$ A= \begin{bmatrix} A \\ 1 \end{bmatrix} \\ f^{n_2}(s)= \begin{bmatrix} a & b \\ 0 & 1 \end{bmatrix}^{n_2} \begin{bmatrix} s \\ 1 \end{bmatrix} = \begin{bmatrix}A \\ 1 \end{bmatrix} $$

from sage.all import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from hashlib import sha256

p = 142031099029600410074857132245225995042133907174773113428619183542435280521982827908693709967174895346639746117298434598064909317599742674575275028013832939859778024440938714958561951083471842387497181706195805000375824824688304388119038321175358608957437054475286727321806430701729130544065757189542110211847
a = 118090659823726532118457015460393501353551257181901234830868805299366725758012165845638977878322282762929021570278435511082796994178870962500440332899721398426189888618654464380851733007647761349698218193871563040337609238025971961729401986114391957513108804134147523112841191971447906617102015540889276702905
b = 57950149871006152434673020146375196555892205626959676251724410016184935825712508121123309360222777559827093965468965268147720027647842492655071706063669328135127202250040935414836416360350924218462798003878266563205893267635176851677889275076622582116735064397099811275094311855310291134721254402338711815917
s = 35701581351111604654913348867007078339402691770410368133625030427202791057766853103510974089592411344065769957370802617378495161837442670157827768677411871042401500071366317439681461271483880858007469502453361706001973441902698612564888892738986839322028935932565866492285930239231621460094395437739108335763
A = 27055699502555282613679205402426727304359886337822675232856463708560598772666004663660052528328692282077165590259495090388216629240053397041429587052611133163886938471164829537589711598253115270161090086180001501227164925199272064309777701514693535680247097233110602308486009083412543129797852747444605837628
B = 132178320037112737009726468367471898242195923568158234871773607005424001152694338993978703689030147215843125095282272730052868843423659165019475476788785426513627877574198334376818205173785102362137159225281640301442638067549414775820844039938433118586793458501467811405967773962568614238426424346683176754273
ct = bytes.fromhex(
"e0364f9f55fc27fc46f3ab1dc9db48fa482eae28750eaba12f4f76091b099b01fdb64212f66caa6f366934c3b9929bad37997b3f9d071ce3c74d3e36acb26d6efc9caa2508ed023828583a236400d64e"
)

F = GF(p)
m = matrix(F, 2, 2, [[a, b], [0, 1]])
s = matrix(F, 2, 1, [[s], [1]])
A = matrix(F, 2, 1, [[A], [1]])

d = s / A
d = d.jordan_form(subdivide=False)
print(d)
n = discrete_log(d, m)
print(ZZ(n))

'ZeroDivisionError: input matrix must be nonsingular'

我没能构造出一个可逆矩阵来求解这个对数问题。

hidE

main.py

#!/usr/local/bin/python
import random
import time
import math
import binascii
from Cryptodome.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是由random.randint(1, n)生成的,random的seed是由time.time()决定的。就可以在产生交互的时候用time.time()来同步。然后连续生成多个额e来爆破。最后用共模攻击。

#!/usr/bin/sage
from pwn import *
from Crypto.Util.number import *
from time import time
from random import Random

#io = process(["python3", "main.py"])
io = remote("be.ax", 31124)
io.recvuntil(b"Your modulus is: ")
n = int(io.recvline())

def getflag():
    io.sendlineafter(b"option: ", b"1")
    io.recvuntil(b"flag: ")
    return bytes_to_long(bytes.fromhex(io.recvlineS().strip()))

start = int(time())
c1, c2 = getflag(), getflag()

def attack(c1, c2, e1, e2):
    g, a, b = xgcd(e1, e2)
    if g != 1:
        return
    return power_mod(c1, a, n) * power_mod(c2, b, n) % n

for t in range(start - 10, start + 5):
    rng = Random(t)
    es = [rng.randint(1, n) for _ in range(10)]
    for i in range(len(es)):
        for j in range(i, len(es)):
            m = attack(c1, c2, es[i], es[j])
            if m is not None and b"corctf{" in long_to_bytes(m):
                print(long_to_bytes(m))
                exit()
io.interactive()

"""
[x] Opening connection to be.ax on port 31124
[x] Opening connection to be.ax on port 31124: Trying 34.138.3.129
[+] Opening connection to be.ax on port 31124: Done
b'corctf{y34h_th4t_w4snt_v3ry_h1dd3n_tbh_l0l}\n'
[*] Closed connection to be.ax port 31124
"""

generous

generous.py

#!/usr/local/bin/python
from Crypto.Util.number import getPrime, inverse, bytes_to_long
from random import randrange

with open("flag.txt", "rb") as f:
    flag = f.read().strip()

def gen_keypair():
    p, q = getPrime(512), getPrime(512)
    n = (p**2) * q
    while True:
        g = randrange(2, n)
        if pow(g, p-1, p**2) != 1:
            break
    h = pow(g, n, n)
    return (n, g, h), (g, p, q)

def encrypt(pubkey, m):
    n, g, h = pubkey
    r = randrange(1, n)
    c = pow(g, m, n) * pow(h, r, n) % n
    return c

def decrypt(privkey, c):
    g, p, q = privkey
    a = (pow(c, p-1, p**2) - 1) // p
    b = (pow(g, p-1, p**2) - 1) // p
    m = a * inverse(b, p) % p
    return m

def oracle(privkey, c):
    m = decrypt(privkey, c)
    return m % 2

pub, priv = gen_keypair()
n, g, h = pub
print(f"Public Key:\n{n = }\n{g = }\n{h = }")
print(f"Encrypted Flag: {encrypt(pub, bytes_to_long(flag))}")
while True:
    inp = int(input("Enter ciphertext> "))
    print(f"Oracle result: {oracle(priv, inp)}")

根据decrypt和oracle很容易想到LSB oracle攻击。看了corCTF 2022 - Crypto | joseph’s blog (jsur.in)这篇文章,没想到这已经是一个现实的公钥密码系统。Okamoto–Uchiyama cryptosystem。虽然一直说是RSA LSB Oracle Attack,但这道题目足以说明,LSB Oracle Attack可以更多的适用于在整数模n乘法群($\mathbb{Z}/n\mathbb{Z}$)上的密钥系统,来恢复一些我们想要的数据。

corCTF 2022 - Crypto | joseph’s blog (jsur.in)这篇文章是利用LSB Oracle Attack来恢复p,进而解密。

具体exp就不贴了。这里还有一篇文章是直接恢复flag,涉及同态,再研究研究。

corCTF 2022 WriteUps