RaRCTF 2021 | snore

#rarctf2021

from Crypto.Util.number import long_to_bytes, bytes_to_long, isPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha224
from random import randrange
import os

p = 148982911401264734500617017580518449923542719532318121475997727602675813514863
g = 2
assert isPrime(p//2)  # safe prime

x = randrange(p)
y = pow(g, x, p)

def verify(s, e, msg):
    r_v = (pow(g, s, p) * pow(y, e, p)) % p
    return bytes_to_long(sha224(long_to_bytes(r_v) + msg).digest()) == e

def sign(msg, k):
    r = pow(g, k, p)
    e = bytes_to_long(sha224(long_to_bytes(r) + msg).digest()) % p
    s = (k - (x * e)) % (p - 1)
    return (s, e)

def xor(ba1,ba2):
    return bytes([_a ^ _b for _a, _b in zip(ba1, ba2)])

otp = os.urandom(32)

messages = [
    b"Never gonna give you up",
    b"Never gonna let you down",
    b"Never gonna run around and desert you",
    b"Never gonna make you cry",
    b"Never gonna say goodbye",
    b"Never gonna tell a lie and hurt you"
]

print("p = ", p)
print("g = ", g)
print("y = ", y)

for message in messages:
    k = bytes_to_long(xor(pad(message, 32)[::-1], otp))  # OTP secure
    s, e = sign(message, k % p)
    assert (verify(s, e, message))
    print(message, sign(message, k % p))

flag = open("flag.txt","rb").read()
key = sha224(long_to_bytes(x)).digest()[:16]
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(pad(flag, 16)).hex()
print("ct = ", ct)
print("iv = ", iv.hex())

DSA 。鍵が32バイトしかないかつ、#### 下位 12バイト程度が共通なので（メッセージの先頭が共通なので）Hidden Number Problemを解けばが求まる。苦戦した

from hashlib import sha224
import random

p =  148982911401264734500617017580518449923542719532318121475997727602675813514863
g =  2
y =  99943368625476277151400768907519717344447758596311103260066302523387843692499
n = (p - 1)

params = [
    [b'Never gonna give you up', (82164720827627951718117576622367372918842412631288684063666489980382312886875, 20555462814568596793812771425415543791560033744700837082533238767135)],
    [b'Never gonna let you down', (121728190859093179709167853051428045020048650314914045286511335302789797110644, 18832686601255134631820635660734300367214611070497673143677605724980)],
    # [b'Never gonna run around and desert you', (146082371876690961814167471199278995325899717136850705507399907858041424152875, 17280327447912166881602972638784747375738574870164428834607749483679)],
    [b'Never gonna make you cry', (70503066417308377066271947367911829721247208157460892633371511382189117698027, 18679076989831101699209257375687089051054511859966345809079812661627)],
    [b'Never gonna say goodbye', (129356717302185231616252962266443899346987025366769583013987552032290057284641, 2084781842220461075274126508657531826108703724816608320266110772897)],
    # [b'Never gonna tell a lie and hurt you', (12183293984655719933097345580162258768878646698567137931824149359927592074910, 15768525934046641405375930988120401106067516205761039338919748323087)],
]

ms = [
    params[i][0] for i in range(len(params))
]
ss = [
    params[i][1][0] for i in range(len(params))
]
es = [
    params[i][1][1] for i in range(len(params))
]
n = p // 2
r = inverse_mod(2**(12*8), n)
ds = [(ss[0] - ss[i]) *r for i in range(1, len(params))]
de = [(es[0] - es[i]) *r for i in range(1, len(params))]

# v = [t1, t2 , ..., x, 1]
N = len(ds)
M = matrix(QQ, N + 2, N + 2)
M.set_block(0, 0, matrix.identity(N) * n )
M.set_block(N, 0, matrix(QQ, 1, N, de))
M.set_block(N+1, 0, matrix(QQ, 1, N, ds))
M[N,N] = 2**(20 * 8) / n # 1 # 2**(256 - 12*8) / 2**256
M[N + 1,N + 1] = 2**(20 * 8) # 2**(256 - 12*8) # 2**20


L = M.LLL()

for row in L.rows():
    print([int(x).bit_length() for x in row])
    x = int(abs(row[-2] * n / 2**(20 * 8)))
    if pow(g, x, p) == y:
        print(x)

なるを見つけたと思っていが、復号できていなかった。に対しても式を満たすのでそちらも試す必要がある

from Crypto.Util.number import long_to_bytes, bytes_to_long, isPrime
from Crypto.Cipher import AES
from hashlib import sha224

p = 148982911401264734500617017580518449923542719532318121475997727602675813514863
g = 2
y = 99943368625476277151400768907519717344447758596311103260066302523387843692499

ct = bytes.fromhex("e426c232b20fc298fb4499a2fff2e248615a379c5bc1a7447531f8a66b13fb57e2cf334247a0589be816fc52d80c064b61fa60261e925beb34684655278955e0206709f95173ad292f5c60526363766061e37dd810ee69d1266cbe5124ae18978214e8b39089b31cad5fd91b9a99e344830b76d456bbf92b5585eebeaf85c990")
iv = bytes.fromhex("563391612e7c7d3e6bd03e1eaf76a0ba")
x = 37082803468215537180041083887500539438948496686358806412960293613018008099436
x += p // 2
assert pow(g, x, p) == y


key = sha224(long_to_bytes(x)).digest()[:16]
cipher = AES.new(key, mode=AES.MODE_CBC, iv=iv)
flag = cipher.decrypt(ct)
print(flag)