WU3 - Baby Time Capsule
Bill Elim, Jayson Adrian S
Diberikan sebuah script seperti berikut
Mari kita bedah satu per satu
Pertama apabila kita mengetik Y, maka program tersebut akan memanggil fungsi get_new_time_capsule() dan kita bisa melihat isinya
Disini terdapat skema RSA yang mengenkripsi msg dimana msg itu adalah flagnya
Disini terdapat generasi public key biasa, tetapi perlu diperhatikan e yang di initialize adalah 5 sehingga termasuk kecil
Baiklah, sebelum kita mulai ngesolve pertama kita harus belajar mtk dikit.
Chinese Remainder Theorem (CRT)
Bayangin kita punya sebuah angka dan beberapa modulus
Nah CRT ini bilang kita bisa merecover 23 bila hanya diberikan hasil modulusnya saja
Apabila hanya diberikan sperti ini, maka memungkinkan bagi kita untuk merecover x.
Note:
kalau masih bingung sama notasinya 23=2 (mod 3) itu sama aja dengan 23 % 3=2, kalau di internet
juga kadang ditulis pakai simbol congruence ≡232 (mod 3), yang sebenarnya gaada bedanya.
CRT on RSA Equation
Nah kalau diperhatikan sebenarnya RSA itu sebenarnya bisa ditulis ulang dalam bentuk yang sama untuk dibikinkan CRT. (kalau belum tahu RSA bisa baca di WU pertama CSC saya ygy)
Bayangin kalau sebuah message m di encrypt beberapa kali dengan e yang sama tetapi N yang berbeda-beda.
Yap, jadi ketika kita CRT maka kita akan mendapatkan me, kemudian tinggal diakar pangkat e aja untuk mendapatkan m kembali.
“Lah jadi semua message yang di encrypt 2 kali vulnerable dong?”
Hmmmm sebenarnya ada batasannya, jadi agar CRT ini bisa bekerja jumlah ciphertext yang didapat itu harus >= e, kalau ngga maka gabakal bisa because math
Nah karena di soal e = 5, maka kita tinggal ambil 5 ciphertext aja agar CRT nya bisa bekerja
Flag: HTB{t3h_FuTUr3_15_bR1ghT_1_H0p3_y0uR3_W34r1nG_5h4d35!}