Pages Menu
Categories Menu




Posted by on Aug 17, 2016 in Event, Hacking, Tutorial, Write-up | 0 comments

[Write-Up : RSA Factorization] Gemastik 2016

[Write-Up : RSA Factorization] Gemastik 2016

rsa

Seorang intelijen menantang Anda untuk memecahkan enkripsi RSA yang ia punya. Tidak butuh super quantum computer untuk melakukannya karena ternyata ada kelemahan pada kunci yang digunakan.

Anda diberikan Public Key (tanpa Private Key) beserta teks yang telah dienkripsi menggunakan Public Key. Pecahkan enkripsinya dan dekripsikan teks yang diberikan.

sebelummnya saya aka menjelaskan apa itu enkripsi RSA,

Algoritma RSA merupakan salah satu algoritma public key yang populer dipakai dan bahkan masih dipakai hingga saat ini. Kekuatan algoritma ini terletak pada proses eksponensial, dan pemfaktoran bilangan menjadi 2 bilangan prima yang hingga kini perlu waktu yang lama untuk melakukan pemfaktorannya (sumber).

Untuk pembangkitan pasangan kunci RSA, digunakan algoritma sebagai berikut (rujukan) :

  1. Pilih dua buah bilangan prima sembarang yang besar, p dan q. Nilai p dan q harus dirahasiakan.
  2. Hitung nilai n dari rumus, n = p x q. Besaran n tidak perlu dirahasiakan.
  3. Hitung nilai m menggunakan teorema euler dengan rumus,m = (p – 1)(q – 1)
  4. Pilih sebuah bilangan bulat sebagai kunci publik (e), yang relatif prima terhadap m. e relatif prima terhadap m artinya faktor pembagi terbesar keduanya adalah 1, secara matematis disebut gcd (e,m) = 1. Untuk mencarinya dapat digunakan algoritma Euclid
  5. Hitung kunci privat yang disebut d sedemikian hingga agar (d * e) mod m = 1. Untuk mencari nilai d yang sesuai dapat juga digunakan algoritma Extended Euclid.Maka hasil dari algoritma tersebut diperoleh :

kunci publik adalah pasangan (e,n)

kunci privat adalah pasangan (d,n)

Nilai dari n bersifat publik, dan diperlukan pada perhitungan enkripsi/dekripsi.

Fungsi enkripsi dan dekripsinya dijabarkan dalam fungsi berikut :

C = Me mod n ( fungsi enkripsi )

M = Cd mod n (fungsi dekripsi)

Keterangan :

C      =     Cipherteks                         d      =          kunci privat

M     =     Message / Plainteks           n       =          modulo pembagi

e       =     kunci publik

Kedua pihak harus mengetahui nilai e dan nilai n ini, dan salah satu pihak harus memilki d untuk melakukan dekripsi terhadap hasil enkripsi dengan menggunakan public key e.

Syarat nilai e dan dadalah gcd(d,e)=1.

Contoh tahapan perhitungan pembangkit kunci pada RSA :

  1. Pilih 2 bilangan prima, misalnya p = 17 dan q = 11.
  2. Hitung n = p*q = 17 × 11 = 187.
  3. Hitung Φ(n) = (p – 1)(q – 1) = 16 × 10 = 160.
  4. Pilih nilai e sedemikian sehingga relatif prima terhadap Φ(n) = 160 dan kurang dari Φ(n); contoh pilih nilai e = 7.
  5. Hitung d sedemikian sehingga de≡ 1 (mod 160) dan d< 160.Nilai yang didapatkan d= 23,karena  23 × 7 = 161 = (1 × 160) + 1; d dapat dihitung dengan Extended Euclidean Algorithm.

Nilai edisebut Public Key dan ddisebut sebagai dan Private Key.

Sehingga Pasangan yang didapatkan adalah :

Kunci Publik                =(e, n) = {7,187}

Kunci Privatnya           = (d, n) = {23, 187}

Selanjutnya kunci diatas dapat digunakan untuk melakukan enkripsi.

Contoh :

Lakukan enkripsi angka 88 maka M = 88. Untuk proses enkripsi, kita akan menghitung dengan rumus

      C     = M e mod n

= 887 mod 187

= 11

Maka didapatkan C atau hasil enkripsi =11. Selanjutnya, nilai C inilah yang akan dikirimkan kepada penerima untuk didekripsi dengan kunci privat miliknya.

      M    = C d mod n

=1123mod 187

= 88

dengan mendapatkan nilai p dankita bisa generate private key dari enkripsi ini, kita bisa menggunakan tools RSA Tool
bagi yg belum ada tools ini bisa mendownloadnya terlebih dahulu,
command :
$ git clone https://github.com/ius/rsatool.git
command generate key :
python2.7 rsatool.py -p 3532461934402770121272604978198464368671197400197625023649303468776121253679423200058547956528088349 -q 7925869954478333033347085841480059687737975857364219960734330341455767872818152135381409304740185467 -o private.key
rsa2
priv
setelah private key sudah di dapat maka kita tinggal decrypt file yg di encrypt yg di beri panitia,
command :
openssl rsautl -in encrypted.enc -out decrypt.txt -inkey private.key -decrypt
note :
encrypted.enc = file yang di enkrip
decrypt.txt =  tempat menyimpan plaintext dari hasil decrpyt
private.key = file private key dari enkripsi di atas
fix
flag : GEMASTIK{no_need_for_quantum_computer_r8?}
johan Wahyudi on Facebook
johan Wahyudi
Linux and Network Security Enthusiast

Post a Reply

Your email address will not be published. Required fields are marked *