Perbandingan Algoritma Brute Force Dan Kraitchik Dalam Kriptanalisis Algoritma Kunci Publik Enhanced AAβ

Abstract

This study examines the comparison between the Brute Force and Kraitchik algorithms in the cryptanalysis of the Enhanced AAβ public key algorithm, implemented and tested on Android devices using the Dart programming language on the Flutter platform. The analysis reveals that both algorithms can factorize the public keys A1 and A2 to produce the factors p, q, and d. However, the Kraitchik algorithm demonstrates lower efficiency than Brute Force for larger key lengths k. Kraitchik performs faster in factorizing A2 when p is smaller than q, especially when p and q are close in value. This efficiency is due to the smaller quadratic difference (x2- kn), which accelerates the factorization process. Nevertheless, Kraitchik experiences a sharper increase in execution time compared to Brute Force, particularly for k ≥ 9. For smaller key lengths (k=3), both algorithms exhibit relatively fast execution times. However, as key length increases, Kraitchik becomes less efficient compared to Brute Force.