eeee (480 pts)

Deskripsi

eeee?

nc 103.152.242.228 1021

Author : MockingJay

Pada soal ini kita diberikan sebuah service tapi tidak diberikan source code nya. Tampilannya adalah sebagai berikut.

Di awal kita diberikan nilai n dan e. Berikutnya, kita dibolehkan menginput sebuah nilai e. Server akan meng-output sebuah bilangan. Setelah menanyakan pada probset, rupanya ini adalah hasil dari inverse(e_user, phi). Dengan kata lain, ini adalah d dari e_user. Lalu setelah itu kita juga diberikan sebuah c untuk di-decrypt menjadi m. Jika salah, maka kita dibolehkan untuk menginput e lagi, begitu seterusnya. Btw walaupun boleh input e lagi, n dan e awal tetap sama.

Sekarang, katakanlah e awal itu e1, dan private key nya d1. Sementara itu, e user adalah e2 dan private key nya d2. Berdasarkan definisi dari e dan d dalam RSA, didapat:

e1*d1 ≡ 1 mod phi
e2*d2 ≡ 1 mod phi

Berikutnya, berdasarkan sifat-sifat modular arithmetic, didapat:

e1*d1*e2*d2 ≡ 1*1 mod phi
d1*(e1*e2*d2) ≡ 1 mod phi

Di sini nilai e1, e2, dan d2 diketahui. Nilai yang ingin kita cari adalah d1. Dengan begitu, untuk mendapatkan d1, kita tinggal perlu mengambil:

inverse(e1*e2*d2, phi)

Yang mana inverse([sesuatu], phi) itu telah disediakan oleh service. Oleh karena itu tinggal kita kalikan saja nilai e1, e2, dan d2 lalu masukkan ke service. Hasilnya adalah d1. Berikutnya, kita gunakan d1 untuk men-decrypt c yang diberikan server. Flag pun kita dapatkan.

Flag: slashroot7{meh_this_is_just_an_ez_crypto_wahahaha_welcome}