Modified Miller-Rabin primality test algorithm to detect prime numbers for generating RSA keys
A prime number is a number that is only divisible by one and itself, which is essentially saying that it has no divisor. Prime numbers are important in the security field because many encryption algorithms are based on the fact that it is very easy to multiply two large prime numbers and get the...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2016
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/69356/1/FSKTM%202016%2021%20IR.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | A prime number is a number that is only divisible by one and itself, which is
essentially saying that it has no divisor. Prime numbers are important in the security
field because many encryption algorithms are based on the fact that it is very easy to
multiply two large prime numbers and get the result, while it is extremely computerintensive
to do the reverse. The Rivest-Shamir-Adleman algorithm (RSA) is one of the
most well-known and strongest public key cryptography algorithms. The security of
the RSA depends on the two prime numbers namely p and q and to generate them is
an extremely time consuming process (Fu and Zhu, 2008). An efficient method for
generating large random prime numbers within shortest time is thus a crucial
challenge for researchers (Bahadori et al., 2010; Saveetha and Arumugam, 2012).
The objective of this study is to reduce the time taken in finding prime numbers p
and q for RSA.
To achieve the objective, the Miller-Rabin primality test was modified by adding few
tests in the original Miller-Rabin. The prime numbers with the size of 256, 512, and
1024 bits are generated using the proposed modified algorithm. The performance of
the proposed modified Miller-Rabin was analysed in terms of the time taken to detect
the prime numbers and compare the time taken for generating the prime numbers
using original Miller-Rabin method. The comparison between the original Miller-
Rabin and the modified Miller-Rabin primality test methods show the difference of
time to generate prime numbers and the modified method shown the better results.
The study also reviewed previous works and the modified Miller-Rabin primality test
method has shown the better results in compared to them. |
|---|