This paper describes and implements the classical method to generate random strong primes used in cryptography. Specifically, the Rabin-Miller and Gordon algorithmsare presented in detail.
#GENERATE STRONG PRIMES FOR RSA
ThangLong University
According to primes number, the average distance of two large prime numbers (n bit) is n * ln2. And We prove the existence of primes in this distance.
We need to generate large random integer about 3072bit. Due to use in cryptography so a good random integer if it satisfies the following condition: it’s a large integer. the values between numbers have to far apart.
In this PrGlib library, it was used RandomBits (NTL library) to goal generate random integers.
We’ll consider 2nln2 numbers [n,n+2nln) by Rabin-miller Algorithm. But we can improve this algorithm as follows:
- Generate a list 1000 the first prime numbers.
- Generate a array S with size = 2nln2. default is zero
- Let r=n%p (p is 1000 the first primes). And compute S[p*k-r]=1
we prove n+i always be divisible for p if S[i]=1.
After finish, we just consider n+i if S[i]=0.
so this improve algorithm, it eliminates more than 93% composite.
we’ll check 64 numbers, include of 20 the first primes and 44 random numbers.
Gordon’s algorithm is as follows:
- Find p– and p+ as large random primes.
- Compute p- as the least prime of the form p-=a–*p– +1, for some integer a–.
- Let po=((p+)^(p- -1)- (p-)^(p+ -1))mod (p-*p+).
- Compute p as the least prime of the from p=po+ap-p+, for some integer a
OS: ubuntu
Language program C++
Use library: NTL and GMP
=> Generate prime numbers: 0→ 2s.
=> Generate strong prime numbers: 1→ 3s.
Generate p and q as strong primes about 3072bit.
Compute n=pq and phi(n)=(p-1)(q-1)
Choose e, such as gcd(e,phi(n))=1.
Let e*d=1 mod phi(n).
Private key (n,d) Public key (n,e)
we’ll encrypt a KEY{128,192,256}.
Generate a array bits with size = 2048. And use 16 headbit and KEY{128,192,256}, so we have to random 2032-KEY.
Encrypt array bits: C=M^e mod n
we should store C format base64.
Decryption process do the opposite encryption with M = C ^ d mode n
[1]. Are `Strong’ Primes Needed for RSA?,Ronald L. Rivest #,Robert D. Silverman y November 22, 1999
[2]. Strong primes are easy to find, John Gordon, Cybermation L t d