Thang Nguyen > Project >

#### Generate large prime numbers for RSA encryption algorithm

Prime-numbers, Large-prime, Prime-generator

### Overview

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.

##### Github: PrGlib

#GENERATE STRONG PRIMES FOR RSA

[email protected]

ThangLong University

#### I. GENERATION OF STRONG PRIMES

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.

##### 1. Generate random integers

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.

##### 2. PRETREATMENT

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.

##### 4. RABIN-MILLER- TEST

we’ll check 64 numbers, include of 20 the first primes and 44 random numbers.

##### 5. GORDON’S ALGORITHM FOR FINDING STRONG PRIMES

Gordon’s algorithm is as follows:

1. Find p– and p+ as large random primes.
2. Compute p- as the least prime of the form p-=a–*p– +1, for some integer a–.
3. Let po=((p+)^(p- -1)- (p-)^(p+ -1))mod (p-*p+).
4. Compute p as the least prime of the from p=po+ap-p+, for some integer a
##### 6. RUNTIME OF ALGORITHM

OS: ubuntu

Language program C++

Use library: NTL and GMP

=> Generate prime numbers: 0→ 2s.

=> Generate strong prime numbers: 1→ 3s.

#### II. RSA ALGORITHM

##### 1. GENERATE KEY

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)

##### 2. ENCRYPT

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.

##### 3. DECRYPT

Decryption process do the opposite encryption with M = C ^ d mode n

#### References

[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

http://thangdn.com/posts/Generate-large-prime-numbers-for-RSA-encryption-algorithm.html