Fword CTF 2020 | Randomness - crypto-writeup-public

from Crypto.Util.number import *
from random import *

flag="TODO"
p=getPrime(64)
a=getrandbits(64)
b=getrandbits(64)
X=[]
X.append((a*getrandbits(64)+b)%p)
c=0
while c<len(flag):
    X.append((a*X[c]+b)%p)
    c+=1

output=[]

for i in range(len(flag)):
    output.append(ord(flag[i])^X[i])

print (output)

#output:[6680465291011788243L, 5100570103593250421L, 5906808313299165060L, 1965917782737693358L, 9056785591048864624L, 1829758495155458576L, 6790868899161600055L, 1596515234863242823L, 1542626304251881891L, 8104506805098882719L, 1007224930233032567L, 3734079115803760073L, 7849173324645439452L, 8732100672289854567L, 5175836768003400781L, 1424151033239111460L, 1199105222454059911L, 1664215650827157105L, 9008386209424299800L, 484211781780518254L, 2512932525834758909L, 270126439443651096L, 3183206577049996011L, 3279047721488346724L, 3454276445316959481L, 2818682432513461896L, 1198230090827197024L, 6998819122186572678L, 9203565046169681246L, 2238598386754583423L, 467098371562174956L, 5653529053698720276L, 2015452976526330232L, 2551998512666399199L, 7069788985925185031L, 5960242873564733830L, 8674335448210427234L, 8831855692621741517L, 6943582577462564728L, 2159276184039111694L, 8688468346396385461L, 440650407436900405L, 6995840816131325250L, 4637034747767556143L, 3074066864500201630L, 3089580429060692934L, 2636919931902761401L, 5048459994558771200L, 6575450200614822046L, 666932631675155892L, 3355067815387388102L, 3494943856508019168L, 3208598838604422062L, 1651654978658074504L, 1031697828323732832L, 3522460087077276636L, 6871524519121580258L, 6523448658792083486L, 127306226106122213L, 147467006327822722L, 3241736541061054362L, 8781435214433157730L, 7267936298215752831L, 3411059229428517472L, 6597995245035183751L, 1256684894889830824L, 6272257692365676430L, 303437276610446361L, 8730871523914292433L, 6472487383860532571L, 5022165523149187811L, 4462701447753878703L, 1590013093628585660L, 4874224067795612706L]

$X_0 = aX + b \mod p$

$X_i+1 = aX_i + b \mod p$

という漸化式を建てておいて、 $C_i = X_i \oplus M_i$

フラグはFword{から始まりそうなので

$X_0, X_1, X_2, X_3, X_4$ あたりが得られる。

$d_0 = X_1 - X_0$

$d_1 = X_2 - X_1 = (aX_1 + b) - (aX_0 + b) = a(X_1 - X_0) = ad_0 \mod p$

$d_2 = X_3 - X_2 = ad_1 \mod p$

$d_3 = X_4 - X_3 = ad_2 \mod p$

として次を計算してみる

$d_2d_0 - d_1d_1 = ad_1d_0 - ad_0ad_0 = a(ad_0)d_0 - a^2d_0^2 = a^2d_0^2 - a^2d_0^2 = 0 \mod p$

$d_3d_1 - d_2d_2 = ad_2d_1 - a^2d_1^2 = a^2d_1^2 - a^2d_1^2 = 0 \mod p$

2式はそれぞれ $p$ の倍数（0でなければ）。ということでGCDをとることで、 $p$ が求まる。不安ならさらにもう少し式を足せば良い。これって二項間漸化式の何かかな

$p$ が求まったのであとはそんなに難しくない。

$d_0 = X_1 - X_0, d_1 = a(X_1 - X_0) \mod p$ なのだから $d_1d_0^{-1} \equiv a \mod p$

$a$ が求まれば $b$ を求めるのは何でもなくて、 $X_1 = aX_0 + b \mod p$ なんだから $(X_1 - aX_0) \mod p = b$

$p, a, b$ を求めれば任意の $X_i$ 計算できるのでXORして終わり。なるほどなぁ

from Crypto.Util.number import *
from random import *

output = [6680465291011788243, 5100570103593250421, 5906808313299165060, 1965917782737693358, 9056785591048864624, 1829758495155458576, 6790868899161600055, 1596515234863242823, 1542626304251881891, 8104506805098882719, 1007224930233032567, 3734079115803760073, 7849173324645439452, 8732100672289854567, 5175836768003400781, 1424151033239111460, 1199105222454059911, 1664215650827157105, 9008386209424299800, 484211781780518254, 2512932525834758909, 270126439443651096, 3183206577049996011, 3279047721488346724, 3454276445316959481, 2818682432513461896, 1198230090827197024, 6998819122186572678, 9203565046169681246, 2238598386754583423, 467098371562174956, 5653529053698720276, 2015452976526330232, 2551998512666399199, 7069788985925185031, 5960242873564733830, 8674335448210427234, 8831855692621741517, 6943582577462564728, 2159276184039111694, 8688468346396385461, 440650407436900405, 6995840816131325250, 4637034747767556143, 3074066864500201630, 3089580429060692934, 2636919931902761401, 5048459994558771200, 6575450200614822046, 666932631675155892, 3355067815387388102, 3494943856508019168, 3208598838604422062, 1651654978658074504, 1031697828323732832, 3522460087077276636, 6871524519121580258, 6523448658792083486, 127306226106122213, 147467006327822722, 3241736541061054362, 8781435214433157730, 7267936298215752831, 3411059229428517472, 6597995245035183751, 1256684894889830824, 6272257692365676430, 303437276610446361, 8730871523914292433, 6472487383860532571, 5022165523149187811, 4462701447753878703, 1590013093628585660, 4874224067795612706]

flag = "Fword{"

X = [ord(flag[i])^output[i] for i in range(len(flag))]

d0 = X[1] - X[0]
d1 = X[2] - X[1]
d2 = X[3] - X[2]
d3 = X[4] - X[3]

a = d2*d0 - d1*d1
b = d3*d1 - d2*d2

p = GCD(a, b)
assert isPrime(p)

a = d1 * inverse(d0, p) % p
b = (X[1] - a*X[0]) % p

Y = [0 for _ in range(len(output))]
Y[0] = X[0]
for i in range(1, len(output)):
    Y[i] = (a * Y[i-1] + b) % p

flag = ""
for i in range(len(output)):
    flag += chr( Y[i] ^ output[i] ) 

print(flag)