Kita diberikan source code dan outputnya sebagai berikut.
chall.py
import random
from Crypto.Util.number import *
flag="XXXXXXXXXXXXXXXXXXXXXXXXX"
class lcg:
def __init__(self,a,b,n):
self.seed=random.getrandbits(32)
self.a=(a-(a&1))
self.b=b
self.n=(n-(n&1))
def next(self):
self.seed=(self.a*self.seed+self.b)%self.n
return self.seed
a1,a2,b1,b2,n1,n2=[random.getrandbits(32) for _ in range(6)]
if((b1^b2)&1==0):
b1-=1
lcg1=lcg(a1,b1,n1)
lcg2=lcg(a2,b2,n2)
s1=lcg1.next()
s2=lcg2.next()
enc=[]
flag=''.join(['{:08b}'.format(ord(i)) for i in flag])
for i in flag:
if i=='0':
enc.append(s1)
s1=lcg1.next()
else:
enc.append(s2)
s2=lcg2.next()
print(f"enc: {enc}")
Oke jadi intinya, soal ini adalah soal tentang LCG, di mana LCG itu adalah sebuah pseudo-random number generator. Saya belajar sedikit konsep tentang LCG dari video ini: https://youtu.be/PtEivGPxwAI
Nah yang membedakan LCG pada soal ini dengan LCG pada umumnya bisa kita lihat pada definisi LCG yang dibuat.
Di sini, nilai a dan n nya di-modif terlebih dahulu.
self.a=(a-(a&1))
self.n=(n-(n&1))
Operasi k = (k-(k&1)) adalah untuk mengubah sebuah bilangan yang paritasnya tidak diketahui, menjadi bilangan genap. Cara kerjanya:
k & 1 mengekstrak bit terakhir, 0 atau 1, kalau 0 berarti genap, kalau 1 berarti ganjil
k - (k&1) mengurangi bilangan dengan hasil di atas, yang artinya kalau ganjil berarti dikurang 1, kalau genap dikurang 0
Oke, lanjut. Jadi sekarang kita tahu bahwa untuk lcg1 dan lcg2 pada soal, itu a dan n nya pasti genap. Di samping itu, dari line dibawah ini, kita tahu bahwa b1 dan b2 paritasnya pasti berbeda.
if((b1^b2)&1==0):
b1-=1
Penjelasannya sebagai berikut:
dilakukan b1 ^ b2 dulu untuk memastikan kalau digit terakhir dari kedua bilangan beda. Andaikan paritasnya sama, maka digit terakhirnya akan jadi 0. Misal 1 ^ 1 = 0 atau 0 ^ 0 = 0
& 1 di sini hanya sekedar untuk meng-ekstrak digit terakhir tadi
kalau digit tersebut sama dengan 0 (paritas sama), maka b1 -= 1 supaya b1 berubah paritasnya
Maka dari itu, paritas dari lcg1 dan lcg2 sepenuhnya ditentukan oleh b1 dan b2.
BAGUS!!! Ini berarti, untuk mendapatkan flag, kita tinggal perlu mengecek paritas dari setiap bilangan dari enc. Kita buat empty string lalu append "0" setiap kali bilangannya ganjil, dan "1" setiap kali bilangannya genap*.
*) Untuk urutan 0 dan 1 nya ini ada dua kemungkinan, tapi bisa ditemukan dengan trial and error.