Using random search and brute force algorithm in factoring the RSA modulus
Journal Title: Data Science: Journal of Computing and Applied Informatics - Year 2018, Vol 2, Issue 1
Abstract
Abstract. The security of the RSA cryptosystem is directly proportional to the size of its modulus, n. The modulus n is a multiplication of two very large prime numbers, notated as p and q. Since modulus n is public, a cryptanalyst can use factorization algorithms such as Euler’s and Pollard’s algorithms to derive the private keys, p and q. Brute force is an algorithm that searches a solution to a problem by generating all the possible candidate solutions and testing those candidates one by one in order to get the most relevant solution. Random search is a numerical optimization algorithm that starts its search by generating one candidate solution randomly and iteratively compares it with other random candidate solution in order to get the most suitable solution. This work aims to compare the performance of brute force algorithm and random search in factoring the RSA modulus into its two prime factors by experimental means in Python programming language. The primality test is done by Fermat algorithm and the sieve of Eratosthenes.
Authors and Affiliations
Mohammad Budiman, Dian Rachmawati
Keywords
Related Articles
- EP ID EP435206
- DOI 10.32734/jocai.v2.i1-91
- Views 71
- Downloads 0
Time Series And Data Envelopment Analysis On The Performance Efficiency Of Dmmmsu-South La Union Campus
This study entitled “Time Series and Data Envelopment Analysis (DEA) on the Performance Efficiency of DMMMSU-South La Union Campus” determined the performance of the Don Mariano Marcos Memorial State University -South La...
Efficiency of Local Government Units in North Western Philippines as to the Attainment of the Millennium Development Goals
This study entitled “Efficiency of Local Government Units in Northwestern Philippines as to the Attainment of the Millennium Development Goals” determined the performance of the four provinces and eight cities in Region...
Subject Bias in Image Aesthetic Appeal Ratings
Automatic prediction of image aesthetic appeal is an important part of multimedia and computer vision research, as it contributes to providing better content quality to users. Various features and learning methods have b...
The Determining Gender Using Facial Recognition Based On Neural Network With Backpropagation
One area of science that can apply facial recognition applications is artificial intelligence. The algorithms used in facial recognition are quite numerous and varied, but they all have the same three basic stages, face...
On Factoring The RSA Modulus Using Tabu Search
It is intuitively clear that the security of RSA cryptosystem depends on the hardness of factoring a very large integer into its two prime factors. Numerous studies about integer factorization in the field of number theo...