Pada tahun ini, terdapat ±30 soal pada babak penyisihan yang dibuat oleh 10 problem setter, dimana saya membuat 4 soal yang terdiri dari 3 crypto dan 1 misc.
Untuk menambah inovasi dan membakar semangat peserta, saya mencoba membuat First Blood Bot pada server discord HackToday 2021, bernama BotToday. Meskipun bot tersebut benar-benar baru dibuat sejak H-4 babak penyisihan, namun bot bekerja dengan baik dan tidak memiliki kendala apapun saat di hari H babak penyisihan.
Pada tulisan ini, saya akan membahas solusi dari beberapa challenge berikut:
- crypto🍞 (465 points, 6 solves): Custom Random Number Generator (RNG)
- PKX (500 points, 1 solve): Small subgroup attack pada Diffie-Hellman
- bookmove (500 points, 0 solves): Dependent primes pada RSA
Catatan:
- Angka solves yang ditampilkan di bawah ini merupakan jumlah solves pada frozen leaderboard.
- Hint yang terdapat pada deskripsi soal dirilis ketika soal belum diselesaikan oleh salah satu tim.
crypto🍞 (465 points, 6 solves)
Please rate our 🍞. Thank you!
Author: deomkicer#3362
#!/usr/bin/env python3
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import getRandomNBitInteger
FLAG = open('flag.png', 'rb').read()
class Bread:
def __init__(self, state, switch=True):
assert state.bit_length() <= 64
self.state = state
self.switch = switch
self.mask32 = (1 << 32) - 1
self.mask64 = (1 << 64) - 1
def encrypt(self, message):
key = b''.join([int.to_bytes(self.next(), 4, 'big') for _ in range(4)])
iv = b''.join([int.to_bytes(self.next(), 4, 'big') for _ in range(4)])
cipher = AES.new(key, AES.MODE_CBC, iv)
return iv + cipher.encrypt(pad(message, 16))
def next(self):
self.state = ((self.state << 43) | (self.state >> (64 - 43))) & self.mask64
self.state = self.state ^ int.from_bytes('🍞'.encode(), 'big')
self.switch = not self.switch
return (self.state >> 32) & self.mask32 if self.switch else self.state & self.mask32
def main():
seed = getRandomNBitInteger(64)
bread = Bread(seed)
enc = bread.encrypt(FLAG)
with open('flag.enc', 'wb') as f:
f.write(enc)
f.close()
if __name__ == '__main__':
main()
Solution
RNG diinisialisasi dengan random 64-bit seed. Setiap kali pemanggilan self.next, nilai self.state berubah dikarenakan adanya bits rotation dan xor dengan 🍞. Nilai yang dikembalikan self.next pun juga berubah-ubah antara 32-bit pertama dan 32-bit terakhir dari self.state secara bergantian.
def encrypt(self, message):
key = b''.join([int.to_bytes(self.next(), 4, 'big') for _ in range(4)])
iv = b''.join([int.to_bytes(self.next(), 4, 'big') for _ in range(4)])
cipher = AES.new(key, AES.MODE_CBC, iv)
return iv + cipher.encrypt(pad(message, 16))
Dari potongan kode diatas, terlihat self.next dipanggil sebanyak 8 kali (4 untuk key, 4 untuk IV). Fungsi self.encrypt juga menyisipkan IV di depan ketika me-return encrypted flag. Hal ini menandakan kita mempunyai 4 nilai half-state (32-bit state ke-5 hingga ke-8) yang dihasilkan oleh RNG tersebut. Dimana ide utama dari challenge ini adalah kita perlu menemukan 4 nilai half-state sebelumnya (32-bit state ke-1 hingga ke-4) yang merupakan kunci pada AES-CBC.
Catatan: Penulis menyebutkan half-state karena self.next hanya me-return 32-bit dari self.state yang aslinya bernilai 64-bit.
Langkah pertama, mari kita ambil terlebih dahulu 4 nilai half-state pada IV.
enc = open('flag.enc', 'rb').read()
iv, enc = enc[:16], enc[16:]
print(f'iv: {iv.hex()}')
states = [int.from_bytes(iv[x:x+4], 'big') for x in range(0, len(iv), 4)]
for state in states:
print(bin(state)[2:].zfill(32))
iv: a5717f138bf89aa2344a9eb054f58146
10100101011100010111111100010011
10001011111110001001101010100010
00110100010010101001111010110000
01010100111101011000000101000110
Pada pemanggilan self.next pertama, nilai self.switch diubah menjadi False, sehingga dapat disimpulkan untuk half-state ke-1, 3, 5, dan 7 merupakan 32-bit terakhir dari full-state. Sementara half-state ke-2, 4, 6, dan 8 merupakan 32-bit pertama dari full-state. Mari kita coba susun secara manual bit full-state ke-1 hingga ke-8. Bit yang tidak diketahui akan ditandai dengan karakter strip.
state 1: ----------------------------------------------------------------
state 2: ----------------------------------------------------------------
state 3: ----------------------------------------------------------------
state 4: ----------------------------------------------------------------
state 5: --------------------------------10100101011100010111111100010011
state 6: 10001011111110001001101010100010--------------------------------
state 7: --------------------------------00110100010010101001111010110000
state 8: 01010100111101011000000101000110--------------------------------
Terlihat bahwa 21-bit pertama pada state ke-6 sama dengan 21-bit terakhir pada state ke-5. Hal ini terjadi karena adanya bits rotation yang dilakukan ketika pemanggilan self.next. Dengan demikian, bit ke-21 hingga bit ke-32 di state ke-6 bisa dipastikan sama persis dengan 11-bit pertama di state ke-5. Hal ini juga berlaku pada pasangan state ke-7 dan ke-8.
state 1: ----------------------------------------------------------------
state 2: ----------------------------------------------------------------
state 3: ----------------------------------------------------------------
state 4: ----------------------------------------------------------------
state 5: 01010100010---------------------10100101011100010111111100010011
state 6: 10001011111110001001101010100010--------------------------------
state 7: 00101000110---------------------00110100010010101001111010110000
state 8: 01010100111101011000000101000110--------------------------------
Pada tahap ini, kita sudah me-recover 11-bit tambahan di state ke-5, sehingga hanya tersisa 21-bit yang tidak diketahui. Karena hanya tersisa 21-bit saja, kita bisa brute-force full-state ke-5 tersebut. Caranya dengan menjadikan full-state ke-5 sebagai initial state RNG di tiap iterasi, lalu generate half-state sebanyak 3 kali, kemudian bandingan half-state tersebut dengan half-state yang ada (half-state ke-6, 7, dan 8).
state_5_hole = states[0] | ((states[1] & ((1 << 11) - 1)) << (64 - 11))
print(f'bin_state_5_hole: {bin(state_5_hole)[2:].zfill(64)}')
for i in range(2**21):
state_5_test = state_5_hole | (i << 32)
a = Bread(state_5_test, False)
b = [a.next() for _ in range(3)]
if b == states[1:]:
state_5 = state_5_test
break
print(f'state_5: {state_5}')
print(f'bin_state_5_full: {bin(state_5)[2:].zfill(64)}')
bin_state_5_hole: 0101010001000000000000000000000010100101011100010111111100010011
state_5: 6076107218727567123
bin_state_5_full: 0101010001010010101010110101001010100101011100010111111100010011
state 1: ----------------------------------------------------------------
state 2: ----------------------------------------------------------------
state 3: ----------------------------------------------------------------
state 4: ----------------------------------------------------------------
state 5: 0101010001010010101010110101001010100101011100010111111100010011
state 6: 10001011111110001001101010100010--------------------------------
state 7: 00101000110---------------------00110100010010101001111010110000
state 8: 01010100111101011000000101000110--------------------------------
Setelah berhasil menemukan full-state ke-5 secara menyeluruh, kita perlu me-reverse proses bits rotation dan xor, yang mana tentunya hal ini cukup sederhana untuk diimplementasikan. Hal ini kita lakukan sebanyak 5 kali hingga kita benar-benar mendapatkan initial state asli yang digunakan program untuk mengenkripsi flag.
seed = state_5
for _ in range(5):
seed = seed ^ int.from_bytes('🍞'.encode(), 'big')
seed = ((seed << 21) | (seed >> (64 - 21))) % (1 << 64)
print(f'seed: {seed}')
Implementation
#!/usr/bin/env python3
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from chall import Bread
enc = open('flag.enc', 'rb').read()
iv, enc = enc[:16], enc[16:]
print(f'iv: {iv.hex()}')
states = [int.from_bytes(iv[x:x+4], 'big') for x in range(0, len(iv), 4)]
print(states)
state_5_hole = states[0] | ((states[1] & ((1 << 11) - 1)) << (64 - 11))
print(f'bin_state_5_hole: {bin(state_5_hole)[2:].zfill(64)}')
for i in range(2**21):
state_5_test = state_5_hole | (i << 32)
a = Bread(state_5_test, False)
b = [a.next() for _ in range(3)]
if b == states[1:]:
state_5 = state_5_test
break
print(f'state_5: {state_5}')
print(f'bin_state_5_full: {bin(state_5)[2:].zfill(64)}')
seed = state_5
for _ in range(5):
seed = seed ^ int.from_bytes('🍞'.encode(), 'big')
seed = ((seed << 21) | (seed >> (64 - 21))) % (1 << 64)
print(f'seed: {seed}')
a = Bread(seed)
calc_key = b''.join([int.to_bytes(a.next(), 4, 'big') for _ in range(4)])
calc_iv = b''.join([int.to_bytes(a.next(), 4, 'big') for _ in range(4)])
assert calc_iv == iv
print(f'key: {calc_key.hex()}')
cipher = AES.new(calc_key, AES.MODE_CBC, calc_iv)
res = unpad(cipher.decrypt(enc), 16)
with open('result.png', 'wb') as f:
f.write(res)
f.close()
$ python3 solve.py
iv: a5717f138bf89aa2344a9eb054f58146
[2775678739, 2348325538, 877305520, 1425375558]
bin_state_5_hole: 0101010001000000000000000000000010100101011100010111111100010011
state_5: 6076107218727567123
bin_state_5_full: 0101010001010010101010110101001010100101011100010111111100010011
seed: 11800126609623179686
key: e35a8027d4013e58f96d49576a4abdde
Flag
hacktoday{we_baked_bread_you_cant_refuse}
PKX (500 points, 1 solve)
Sebuah percakapan antara sepasang anak muda di tanah sunda. Karena maraknya penyadapan komunikasi terjadi, mereka pun mengenkripsi percakapan mereka menggunakan metode Punten Key eXchange (PKX).
nc 103.41.207.206 11005
Author: deomkicer#3362
#!/usr/bin/env python3
from Crypto.Cipher import AES
from Crypto.Hash import SHA1
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
import math
import sys
class Unbuffered(object):
def __init__(self, stream):
self.stream = stream
def write(self, data):
self.stream.write(data)
self.stream.flush()
def writelines(self, datas):
self.stream.writelines(datas)
self.stream.flush()
def __getattr__(self, attr):
return getattr(self.stream, attr)
sys.stdout = Unbuffered(sys.stdout)
FLAG = open('flag.txt', 'rb').read()
class PKX:
def __init__(self, p):
self.g = 0x24e6e064ca1d3dac
self.p = p
assert self.g < self.p
self.private = getRandomRange(2, self.p - 2)
self.secret = None
def getPublicKey(self):
return pow(self.g, self.private, self.p)
def getSharedSecret(self, x):
assert x > 1 and x < self.p - 1
self.secret = pow(x, self.private, self.p)
def getFingerprint(self):
return SHA1.new(long_to_bytes(self.secret)).hexdigest()
def checkFingerprint(self, fingerprint):
return fingerprint == self.getFingerprint()
def encrypt(self, msg):
iv = AES.get_random_bytes(AES.block_size)
key = SHA1.new(long_to_bytes(self.secret)).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
return iv.hex() + cipher.encrypt(pad(msg, 16)).hex()
def check(p, k):
for _ in range(k):
if not isPrime(p):
return False
d = int(math.log10(p))
p = p - p // pow(10, d) * pow(10, d)
return True
def user_input(s):
inp = input(s).strip()
assert len(inp) <= 64, 'You may send up to 64 digits for PKX prime.'
return inp
def main():
print('+' + '-'*60)
print('| Welcome to Punten Key eXchange (PKX)!')
print('| We ensure only Alice and Bob can read or listen to what is sent, and nobody in between, not even us.')
print('+' + '-'*60)
p = int(user_input('| Please enter a PKX prime: '))
print('+' + '-'*60)
if not check(p, 20) or p < 0:
print('| That\'s not a PKX prime.')
print('+' + '-'*60)
return
Alice = PKX(p)
Bob = PKX(p)
A = Alice.getPublicKey()
B = Bob.getPublicKey()
print('| Alice\'s public key: ' + chr(42)*10 + hex(A)[2:].zfill(len(hex(p)[2:]))[10:])
print('| Bob\'s public key: ' + chr(42)*10 + hex(B)[2:].zfill(len(hex(p)[2:]))[10:])
print('+' + '-'*60)
Alice.getSharedSecret(B)
Bob.getSharedSecret(A)
if Bob.checkFingerprint(Alice.getFingerprint()):
print('| Bob: ' + Bob.encrypt(b'Hey Alice, can you give me the flag?'))
print('| Alice: ' + Alice.encrypt(b'Sure, Bob. Here is the flag: ' + FLAG))
print('| Bob: ' + Bob.encrypt(b'Hatur nuhun teh Alis.'))
print('| Alice: ' + Alice.encrypt(b'Sami-sami kang Bobi.'))
else:
print('| Fingerprint mismatch.')
print('+' + '-'*60)
if __name__ == '__main__':
main()
Solution
Diberikan source code server.py dan servis ke 103.41.207.206 11005. Pada source code yang diberikan, komunikasi Alice dan Bob dienkripsi menggunakan AES-CBC, dan Diffie-Hellman key exchange terlibat dalam proses pertukaran kunci mereka.
Pada challenge ini, parameter $ p $ pada Diffie-Hellman ditentukan oleh user input, sedangkan parameter $ g $ pada Diffie-Hellman bersifat konstan pada source code, yang nilainya terbilang ‘tidak biasa’, yaitu $ \mathrm{0x24e6e064ca1d3dac} $. Sebelum terjun lebih jauh mengenai hubungan parameter $ g $ dan $ p $ pada Diffie-Hellman, mari kita coba cari nilai $ p $ yang memenuhi pada saat pengecekan.
def check(p, k):
for _ in range(k):
if not isPrime(p):
return False
d = int(math.log10(p))
p = p - p // pow(10, d) * pow(10, d)
return True
if not check(p, 20) or p < 0:
print('| That\'s not a PKX prime.')
print('+' + '-'*60)
return
Jika diperhatikan, fungsi check melakukan pengecekan apakah nilai $ p $ bilangan prima atau bukan pada setiap iterasi. Jika benar merupakan bilangan prima, nilai $ p $ akan dipotong digit paling depannya, lalu masuk ke iterasi berikutnya. Jika bukan bilangan prima, fungsi check langsung mengembalikan nilai False. Penjelasan tersebut membuktikan bahwa fungsi check akan melihat apakah nilai $ p $ merupakan 20 left-truncatable prime atau bukan. Untuk meng-generate truncatable prime sendiri cukup sederhana diimplementasikan pada python ataupun sage. Berikut kodenya.
pkx = []
res = ['']
while True:
tmp = []
for i in res:
for j in '123456789':
if is_prime(int(j+i)):
tmp.append(j+i)
res = tmp
if not res: break
if len(res[0]) >= 20: pkx += res
pkx = list(map(int, pkx))
print(pkx, len(pkx))
[36484957213536676883, 67986315421273233617, 86312646216567629137, 18918997653319693967, 15396334245663786197, 66276812967623946997, 367986315421273233617, 686312646216567629137, 918918997653319693967, 315396334245663786197, 666276812967623946997, 6686312646216567629137, 7686312646216567629137, 5918918997653319693967, 9918918997653319693967, 96686312646216567629137, 57686312646216567629137, 95918918997653319693967, 357686312646216567629137] 19
Terdapat 19 (atau lebih?) kemungkinan angka yang mengembalikan nilai True pada fungsi check. Kode program diatas meng-generate truncatable prime dengan panjang 20-digit atau lebih, karena 21-digit truncatable prime pun akan tetap bernilai True ketika dicek menggunakan fungsi check (sesuai Hint 1), dan berlaku seterusnya.
In [3]: def check(p, k):
...: for _ in range(k):
...: if not isPrime(p):
...: return False
...: d = int(math.log10(p))
...: p = p - p // pow(10, d) * pow(10, d)
...: return True
...:
In [4]: check(36484957213536676883, 20)
Out[4]: True
In [5]: check(357686312646216567629137, 20)
Out[5]: True
Sesuai Hint 2, dari 19 angka tersebut, angka mana yang bisa memudahkan kita untuk mencari nilai shared secret? Karena public key dari Alice dan Bob tidak diperoleh secara menyeluruh, hal ini tidak bisa kita manfaatkan untuk mendapatkan private key mereka dengan menghitung discrete-log nya. Dengan kondisi public key tidak diketahui dan nilai parameter $ p $ dapat kita kontrol, hal yang bisa kita lakukan adalah dengan mengimplementasikan small subgroup attack antara parameter $ g $ dan $ p $.
Kita dapat memanfaatkan module discrete-log di sage untuk menghitung ukuran subgroup yang terbentuk antara $ g $ dan $ p $ dengan cepat (namun saya yakin cara ini bukan cara yang optimal). Berikut kodenya.
sage: ps = [36484957213536676883, 67986315421273233617, 86312646216567629137, 18918997653319693967, 153963342456637861
....: 97, 66276812967623946997, 367986315421273233617, 686312646216567629137, 918918997653319693967, 31539633424566378
....: 6197, 666276812967623946997, 6686312646216567629137, 7686312646216567629137, 5918918997653319693967, 99189189976
....: 53319693967, 96686312646216567629137, 57686312646216567629137, 95918918997653319693967, 357686312646216567629137
....: ]
sage: g = 0x24e6e064ca1d3dac
sage: for p in ps:
....: P = GF(p)
....: subgroup_size = (P(g)^-1).log(P(g))
....: print(p, subgroup_size)
....:
36484957213536676883 36484957213536676881
67986315421273233617 67986315421273233615
86312646216567629137 28770882072189209711
18918997653319693967 18918997653319693965
15396334245663786197 7698167122831893097
66276812967623946997 33138406483811973497
367986315421273233617 22999144713829577100
686312646216567629137 42894540388535476820
918918997653319693967 918918997653319693965
315396334245663786197 315396334245663786195
666276812967623946997 666276812967623946995
6686312646216567629137 1671578161554141907283
7686312646216567629137 3843156323108283814567
5918918997653319693967 2959459498826659846982
9918918997653319693967 4959459498826659846982
96686312646216567629137 52500
57686312646216567629137 3204795147012031534951
95918918997653319693967 15986486499608886615660
357686312646216567629137 44710789080777070953641
Terlihat bahwa pasangan nilai $ g $ dengan angka prima $ 96686312646216567629137 $ menghasilkan subgroup yang ukurannya jauh lebih kecil dibanding angka prima lainnya, sehingga kita akan gunakan angka prima tersebut sebagai nilai $ p $ ke servis yang tersedia.
Karena ukuran subgroup hanya 52500 (lebih tepatnya 52501 karena angka 1 di dalam group tetap dihitung) dan rentang tersebut sangat brute-forcible untuk dilakukan, maka langsung saja kita brute-force shared secret antara Alice dan Bob menggunakan nilai parameter $ g = \mathrm{0x24e6e064ca1d3dac} $ dan $ p = 96686312646216567629137 $. Berikut kodenya.
Implementation
#!/usr/bin/sage
from Crypto.Cipher import AES
from Crypto.Hash import SHA1
from Crypto.Util.number import long_to_bytes
from pwn import *
import time
start = time.time()
pkx = []
res = ['']
while True:
tmp = []
for i in res:
for j in '123456789':
if is_prime(int(j+i)):
tmp.append(j+i)
res = tmp
if not res: break
if len(res[0]) >= 20: pkx += res
pkx = list(map(int, pkx))
print(pkx, len(pkx))
g = 0x24e6e064ca1d3dac
min_s = 2^64
for p in pkx:
P = GF(p)
s = (P(g)^-1).log(P(g)) # bukan cara yang paling optimal
if s < min_s:
min_p = p
min_s = s
assert min_s < 2^16
p = min_p
print(f'{p = }')
s = min_s
print(f'{s = }')
# r = process('./server.py')
# r = remote('localhost', 11005)
r = remote('103.41.207.206', 11005)
r.sendlineafter(b'Please enter a PKX prime: ', str(p).encode())
r.recvuntil(b'Bob: ')
r.recvuntil(b'Alice: ')
enc = bytes.fromhex(r.recvline(0).decode())
iv, ct = enc[:16], enc[16:]
r.close()
for x in range(s):
y = pow(g, x, p)
key = SHA1.new(long_to_bytes(y)).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
pt = cipher.decrypt(ct)
if b'flag' in pt:
flag = pt[pt.index(b'hacktoday{'):pt.index(b'}')+1]
print(f'flag = {flag.decode()}')
break
end = time.time()
print(f'time = {end-start} seconds')
$ sage solve.sage
[36484957213536676883, 67986315421273233617, 86312646216567629137, 18918997653319693967, 15396334245663786197, 66276812967623946997, 367986315421273233617, 686312646216567629137, 918918997653319693967, 315396334245663786197, 666276812967623946997, 6686312646216567629137, 7686312646216567629137, 5918918997653319693967, 9918918997653319693967, 96686312646216567629137, 57686312646216567629137, 95918918997653319693967, 357686312646216567629137] 19
p = 96686312646216567629137
s = 52500
[x] Opening connection to 103.41.207.206 on port 11005
[x] Opening connection to 103.41.207.206 on port 11005: Trying 103.41.207.206
[+] Opening connection to 103.41.207.206 on port 11005: Done
[*] Closed connection to 103.41.207.206 port 11005
flag = hacktoday{all_your_conversation_are_belong_to_us}
time = 8.173951625823975 seconds
Flag
hacktoday{all_your_conversation_are_belong_to_us}
bookmove (500 points, 0 solves)
Definitely the conventional moves.
Author: deomkicer#3362
#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, isPrime, getPrime
from libnum import grey_code
FLAG = open('flag.txt', 'rb').read()
def bookmove(nbit):
while True:
p = getPrime(nbit // 3)
if p % 8 == 1:
q = grey_code(p)
r = grey_code(q)
if isPrime(q) and isPrime(r):
return p * q * r
m = bytes_to_long(FLAG)
e = 65537
n = bookmove(1536)
c = pow(m, e, n)
print(f'{e = }')
print(f'{n = }')
print(f'{c = }')
e = 65537
n = 1337019719866013134311502867665167638966695743292894716327343862274121579466869813594221725755438050073939953340753287213906421339262574483387468763195012360339971640277270196638499163755345814097026097936673955162469055482078476651059809508489652783985615153221495580490730931660705593609939955424611697354621729662929558565499366483826261600300167171392762299060817265964348661751639430527513341508915893730214795480676247679224372484041466733871469573310022179
c = 308013715706893096316943745042644246712394567314503581147341487424999022679742698959777178713510471886312316680638653501601294983972427880095230642174257809555165327207166272407873917975855381008065455831026725087298871408371006858974416002264387201821745372781658202601775263720561069642128144635638590920742252564219016677475961650093872263358830241576866286716368280154739111992549611084155614682637575573462749366166200569569916981088019443740751232359060185
Solution
Diberikan source code chall.py dan file output.txt. Program mengenkripsi flag menggunakan RSA dengan nilai modulus $ n $ merupakan hasil perkalian antara 3 bilangan prima $ p, q, $ dan $ r $.
Pertama, mari kita pahami dulu source code dari fungsi grey_code pada salah satu repository milik the one and only crypto god, hellman. Fungsi grey_code sangatlah sederhana, dimana $ n $ akan di-xor dengan $ n $ yang sudah digeser sebanyak 1 bit ke kanan.
def grey_code(n):
return n ^ (n >> 1)
Secara sederhana, \(\mathrm{bit}_i\) akan didapat dari hasil xor antara \(\mathrm{bit}_{i+1}\) dan \(\mathrm{bit}_{i}\) (urutan bit dari kanan ke kiri). Berikut ilustrasinya ketika $ p = 17 $ ($ p $ harus memenuhi kondisi $ p = 1\pmod{8} $ agar nilai $ q $ dan $ r $ merupakan angka ganjil).
In [1]: from libnum import *
In [2]: p = 17
In [3]: q = grey_code(p); q
Out[3]: 25
In [4]: r = grey_code(q); r
Out[4]: 21
Ingat! Jika $ A \times B = C $, maka $ (A \pmod{n} \times B \pmod{n}) \pmod{n} = C \pmod{n} $. Berikut contohnya.
Catatan:
- Tak hanya di basis 10 (desimal), aturan ini juga berlaku untuk perkalian di basis lainnya, termasuk basis 2 (biner).
- Fungsi mask merepresentasikan $ \pmod{n} $
mask = lambda a, x: a & ((1 << x) - 1)
Sesuai dengan hint yang ada, kita bisa brute-force nilai $ p $ secara bit per bit (bisa juga per sekian bit), lalu generate nilai $ q $ dan $ r $ berdasarkan nilai $ p $ di setiap iterasi, kemudian kalikan ketiga angka tersebut dengan mask bit tertentu, dan bandingkan dengan $n$. Namun hal ini menjadi sedikit tricky karena pada additional bit $ p $ dan $ q $ tidak pasti bernilai 0. Hal ini dikarenakan faktanya $ p $ memiliki bit lanjutan yang tidak dapat dipastikan antara 0 atau 1. Karena MSB $ r $ bergantung pada additional bit $ q $, dan additional bit $ q $ bergantung pada 2 additional bit $ p $, maka kita juga perlu brute-force 2 additional bit $ p $ sekaligus agar nilai $ p, q, $ dan $ r $ bisa ditemukan.
Implementation
#!/usr/bin/python
from libnum import *
exec(open('output.txt').read())
mask = lambda a, x: a & ((1 << x) - 1)
grey = lambda p: p ^ (p >> 1)
def cari(curr_p, x):
for i in range(1024): # 2^8, plus 2 additional bits
test_p = int(bin(i)[2:].zfill(10) + curr_p, 2)
test_q = grey(test_p)
test_r = grey(test_q)
if mask(test_p * test_q * test_r, x) == mask(n, x):
res = []
res.append(bin(mask(test_p, x))[2:].zfill(x))
res.append(bin(mask(test_q, x))[2:].zfill(x))
res.append(bin(mask(test_r, x))[2:].zfill(x))
return res
x = 8
curr_p = ''
curr_q = ''
curr_r = ''
while True:
res = cari(curr_p, x)
curr_p = res[0]
curr_q = res[1]
curr_r = res[2]
print '>', x
print 'curr_p =', int(curr_p, 2)
print 'curr_q =', int(curr_q, 2)
print 'curr_r =', int(curr_r, 2)
print
x += 8
if int(curr_p, 2) * int(curr_q, 2) * int(curr_r, 2) == n:
break
print '> found'
p = int(curr_p, 2)
q = int(curr_q, 2)
r = int(curr_r, 2)
d = invmod(e, (p-1) * (q-1) * (r-1))
print n2s(pow(c, d, n))
$ python solve.py
> 8
curr_p = 89
curr_q = 245
curr_r = 143
> 16
curr_p = 25433
curr_q = 21237
curr_r = 31631
> 24
curr_p = 549721
curr_q = 9196277
curr_r = 13269903
> 32
curr_p = 1393058649
curr_q = 4203500277
curr_r = 130710415
...
> 488
curr_p = 554054447595710955666362614793081391948235276695164364263933630596038736909443490751734691988505547874267136360512740792657926409305152129285514073
curr_q = 729792514060899554983983679451720106970684641220561153869779206263317824732325887619762106197450825811608408555272166998460027403137846098139042549
curr_r = 490574122930329477293669224898904798318425476956172102596126144965021805701429369739763706555878213410841983672525957931725488750641845007934978959
> 496
curr_p = 163584250739298089247338896343511398543363024679230617746732546690071452425032883235914600618376310249725068787244852214884533008284456563964983665497
curr_q = 34294832927058448026798917094187844226379611871154330967907434836155314760522445835153293326336116499722067571972636176370316661906845489711371014901
curr_r = 50838134742426652185016069347003090977431816321856826823652609589803017209386609291040060536763876724276530728798571971989510440506203310427782937487
> 504
curr_p = 40876379936447562597536385750636775854237848472339848936945168937385735545208172659596586373921809264813878202623773235392024161297734032664738545558361
curr_q = 33586548563862512615661993309577079154446960583812568423171643957821526727908436633388671739666853727296310579879463364020847196257232124286328778806005
curr_r = 50379218731145607903637807658071340056308303274233977965129257394067860136931257890621317730047540292919159299190034663738704829833494121505353894624143
> 512
curr_p = 11563211319730866945043964118583785791656817850543927907918130784635776698889662605848707311361104442435935006331635223187836767202814317580381155660161881
curr_q = 9356202999852074558413226249874579464667443507714461088871585460295610578888421568940941894683841893293021586975170545598271593838938831540165975353348853
curr_r = 12358327904420639039153231067729844152390882396396157586422304801435530934618507584251716864875447171180253091618815901658395589442362572002020617630677903
> found
hacktoday{your_book_move_reached_the_512_bit_depth}
Flag
hacktoday{your_book_move_reached_the_512_bit_depth}