Teknik Pemecahan Kunci Algoritma Rivest Shamir Adleman (RSA) dengan Metode Kraitchik

Abstract

Abstrak—Penelitian ini bertujuan memecahkan kunci privat algoritma RSA dengan memfaktorkan kunci publik n menggunakan metode Kraitchik dan melihat efisiensi waktu pemfaktorannya. Kriptanalisis dengan pemfaktoran (factoring) menggunakan kunci publik n yaitu n = p . q yang tidak dirahasiakan untuk memecahkan kunci privat RSA. Jika kunci publik n berhasil difaktorkan menjadi p dan q maka ɸ(n) = (p – 1)(q – 1) dapat dihitung dan dengan menggunakan kunci publik e, kunci privat d pun akan dapat terpecahkan. Metode Kraitchik yang mengawali munculnya algoritma pemfaktoran yang paling modern menyatakan bahwa untuk menemukan faktor x dan y dari bilangan bulat n sedemikian rupa sehingga x2 ≡ y2 (mod n). Hasil penelitian memperlihatkan bahwa efisiensi waktu pemfaktoran kunci publik n metode Kraitchik sangat dipengaruhi oleh selisih faktor kunci (p – q) yaitu semakin besar selisih antara p dan q maka semakin lama waktu pemfaktorannya. Pemfaktoran panjang kunci publik n sebesar 19 digit atau 152 bit dengan selisih faktor kunci (p – q) = 22641980 membutuhkan waktu selama 93,6002 ms lebih cepat jika dibandingkan dengan panjang kunci sebesar 15 digit atau 120 bit dengan selisih faktor kunci (p – q) = 23396206 yang membutuhkan waktu selama 5850,0103 ms. Faktor lainnya yang mempengaruhi efisiensi waktu pemfaktoran metode Kraitchik adalah Gcd (p – 1, q – 1), panjang kunci dan faktor prima (p – 1), (q – 1).

Kata kunci—RSA, Kriptanalisis, Pemfaktoran (Factoring), Metode Kraitchik.

GS Cited Analysis