[zer0pts CTF 2020] ROR

chall.py, chall.txt가 주어진다.

ROR.zip

0.08MB

import random
from secret import flag

ror = lambda x, l, b: (x >> l) | ((x & ((1<<l)-1)) << (b-l))

N = 1
for base in [2, 3, 7]:
    N *= pow(base, random.randint(123, 456))
e = random.randint(271828, 314159)

m = int.from_bytes(flag, byteorder='big')
assert m.bit_length() < N.bit_length()

for i in range(m.bit_length()):
    print(pow(ror(m, i, m.bit_length()), e, N))

m.bit_length()가 367 임을 알 수 있다.

ror은 i가 하나씩 증가할 때마다 m을 이진수로 표현하여 오른쪽으로 하나씩 shift 한다. 예를 들어, m이 1011010이고 i가 3이면, 0101011이 된다.

N이 짝수이기 때문에, m의 MSB가 0이라면 출력되는 값이 짝수이고, 1이라면 홀수이다. 이런 식으로 한 비트씩 알아낼 수 있다.

 

Exploit Code

from fractions import gcd
from Crypto.Util.number import *

f = open('chall.txt', 'r')

data = []
while True:
    s = f.readline()
    if not s:
        break
    data.append(int(s))

m = 0
for i in range(0, len(data)):
    data[i] = data[i] % 2
    m += data[i] * pow(2, i)

print long_to_bytes(m)

 

Capture the Flag

---