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 66
- 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...
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...
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...
Data Analysis as a Method to gather Data to study the Relation between Fundamental Rights and Rule of Law
The research described here involves the relation between fundamental rights and the rule of law. In the end we want to find out what meaning is attributed to ‘rule of law’ by the European Court of Human Rights. In this...
Improving Data Collection on Article Clustering by Using Distributed Focused Crawler
Collecting or harvesting data from the Internet is often done by using web crawler. General web crawler is developed to be more focus on certain topic. The type of this web crawler called focused crawler. To improve the...