Using random search and brute force algorithm in factoring the RSA modulus

Data Science: Journal of Computing and Applied Informatics

View Publication Info
 
 
Field Value
 
Title Using random search and brute force algorithm in factoring the RSA modulus
 
Creator Budiman, Mohammad Andri
Rachmawati, Dian
 
Description 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.
 
Publisher Talenta Publisher
 
Date 2018-02-01
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
Peer-reviewed Article
 
Format application/pdf
 
Identifier https://talenta.usu.ac.id/index.php/JoCAI/article/view/91
10.32734/jocai.v2.i1-91
 
Source Data Science: Journal of Computing and Applied Informatics; Vol 2 No 1 (2018): Data Science: Journal of Computing and Applied Informatics (JoCAI); 45-52
2580-829X
2580-6769
 
Language eng
 
Relation https://talenta.usu.ac.id/index.php/JoCAI/article/view/91/78
 
Rights Copyright (c) 2018 Journal of Computing and Applied Informatics
 

Contact Us

The PKP Index is an initiative of the Public Knowledge Project.

For PKP Publishing Services please use the PKP|PS contact form.

For support with PKP software we encourage users to consult our wiki for documentation and search our support forums.

For any other correspondence feel free to contact us using the PKP contact form.

Find Us

Twitter

Copyright © 2015-2018 Simon Fraser University Library