Faktorisasi Modulus RSA secara Metaheuristik dan Eksak

Abstract

Sejak dipublikasikan pada tahun 1978, algoritma RSA (Rivest-Shamir-Adleman) menjadi salah satu algoritma kriptografi kunci publik pertama yang menerapkan konsep kriptografi asimetrik Diffie-Hellman yang masih digunakan hingga saat ini. Tingkat keamanan RSA berbanding lurus dengan seberapa sukar memfaktorkan modulus RSA, yaitu n, sebuah bilangan bulat positif yang sangat besar menjadi dua buah faktor primanya, yaitu p dan q. Metode metaheuristik selama ini dikenal untuk menyelesaikan masalah-masalah kontinu, dan jarang sekali digunakan untuk menyelesaikan masalah-masalah diskrit, seperti pemfaktoran. Sementara itu, metode pemfaktoran eksak yang ada di dalam ranah teori bilangan adalah metode pemfaktoran eksak yang bersifat umum: dapat digunakan untuk memfaktorkan sembarang bilangan bulat dan tidak memperhitungkan apakah bilangan bulat tersebut memiliki kriteria tertentu seperti modulus RSA yang memiliki keterkaitan erat dengan nilai totient-nya. Penelitian ini mengukur seberapa baik kinerja metode metaheuristik dibandingkan dengan metode eksak di dalam memfaktorkan modulus RSA. Kemudian, penelitian ini mencoba mengembangkan sebuah algoritma pemfaktoran baru yang secara khusus ditujukan untuk modulus RSA. Lima buah metode metaheuristik, yakni random search, iterated local search, random-restart hill climbing, steepest ascent hill climbing, dan tabu search akan diukur kinerja real-time-nya dalam memfaktorkan modulus RSA, dan dipilih yang paling efisien. Kemudian, lima buah metode eksak, yakni Fermat difference of squares, Euler factorization, Brent factorization, Pollard, dan Pollard rho juga search akan diukur kinerja real-time-nya dalam memfaktorkan modulus RSA, dan dipilih yang paling efisien. Kemudian, dengan menggunakan melihat hubungan antara nilai n, Φ(n), p, dan q, serta dengan memperhatikan batas Fang-Liu, sebuah algoritma pemfaktoran baru yang khusus untuk memfaktorkan modulus RSA yang lebih efisien daripada kesepuluh metode dari ranah metaheuristik dan eksak tadi pun dikembangkan.