Generalized RSA (GRSA) Using 2k Prime Numbers with Secure Key Generation

Pierluigi Paganini September 29, 2016

In this blog, we introduce a generalized algorithm over RSA which is advanced, adaptable and scalable in using the number of primes.

Cryptography is used for secure communication since ancient days for providing confidentiality, integrity, and availability of the information. Public key cryptography is a classification of cryptography having a pair of keys for encryption and decryption. Public key cryptography provides security and authentication using several algorithms.

RSA algorithm is prominent since its inception and is widely used. Several modified schemes were introduced to increase security in RSA algorithm involving additional complexity. In this blog, we introduce a generalized algorithm over RSA which is advanced, adaptable and scalable in using the number of primes.

Our algorithm uses 2k prime numbers with secure key generation involving additional complexity making it computationally infeasible to determine decryption key. A user can use 4, 8, 16, 32,.…(2k) prime numbers for generating public and private components securely. In our algorithm, public key and private key components are generated by making use of N, where N is a function of 2k prime numbers. When an attacker gets public key component n out of {E, n} by using factorization techniques such as GNFS or ECM, he can only get two initial prime numbers (since, n is product of first two prime numbers).

However, finding remaining prime numbers is computationally infeasible as no relevant information is available to the attacker. Hence, it is difficult for the attacker to determine the private key component D out of {D, n} knowing public key component {E, n}. Thus, it is practically impossible to break our system using brute force attack.

When an attacker gets public key component n out of {E, n} by using factorization techniques such as GNFS or ECM, he can only get two initial prime numbers (since, n is product of first two prime numbers). However, finding remaining prime numbers is computationally infeasible as no relevant information is available to the attacker. Hence, it is difficult for the attacker to determine the private key component D out of {D, n} knowing public key component {E, n}. Thus, it is practically impossible to break our system using brute force attack.

            Generalized RSA-AA

In GRSA-AA algorithm, we have resolved the problem of guessing the other prime numbers by making use of 2k prime numbers and thus making it almost impossible for an attacker to recover the keys and break the system. GRSA-AA is presented and discussed in detail in the following subsections.

GRSA-AA Key Generation

GRSA-AA Key Generation For 8 Prime Numbers

GRSA-AA_KeyGen( )

INPUT:

Eight prime numbers: p1, p2, p3, p4, p5, p6, p7, p8.

OUTPUT:

Public key components {E, n}

Private key components {D, n}

PROCEDURE:

n ← p1 * p2

m ← p3 * p4

o ← p5 * p6

p ← p7 * p8

N1 ← n * m

N2 ← o * p

N ←N1* N2

/*Compute Euler phi values of n, m, o and p */

Φ(n) ← (p1-1) * (p2-1)

Φ(m) ← (p3-1) * (p4-1)

Φ(o) ← (p5-1) * (p5-1)

Φ(p) ← (p7-1) * (p8-1)

/*Compute Euler phi values of N */

Φ(N) ← Φ(n) * Φ(m) * Φ(o) * Φ(p)

Find a random number e1, satisfying 1 < e1 < Φ(n) and gcd (e1, Φ(n)) =1

Find a random number e2, satisfying 1 < e2 < Φ(m) and gcd (e2, Φ(m)) =1

Find a random number e3, satisfying 1 < e3 < Φ(o) and gcd (e3, Φ(o)) =1

Find a random number e4, satisfying 1 < e4 < Φ(p) and gcd (e4, Φ(p)) =1

Compute A1 ← e1e2 mod N1

Compute A2 ← e3e4 mod N2

Compute E’ ← A1A2 mod N

Find a random number E, satisfying 1 < E < Φ(n) * E’ and gcd (E, Φ(n) * E’) = 1

Compute a random number D, such that,

D ← E-1mod(Φ(N) * E’)

 

GRSA-AA Encryption and Decryption

Algorithm 2.3 GRSA-AA Encryption And Decryption

GRSA-AA_Encrypt( )

Input:

Plain text, Message (< n)

Public Key Components {E, n}

Output:

Cipher Text, C

Procedure:

C ← MEmod n

GRSA-AA_Decrypt( )

Input:

Cipher Text Message, C

Private Key Components: {D, n}

Output:

P ← CDmod n

2.4       Mathematical Proof of GRSA-AA

GRSA-AA is proved mathematically in the below subsection.

Proof:

Cipher Text is computed in the following way:

C = ME mod n                                                                       (1)

and plain text can be recovered in the following way:

M = CD mod n                                                                                       (2)

where n = p1*p2

Therefore, Public key = (E, n) and Private key = (D, n)

To retrieve plain text message M, from CD mod n

CD mod n = MED mod n                                                         (3)

From our Algorithm 3.1

D = E-1 mod (Φ(N)*E)                                                        (4)

E.D = 1 mod (Φ(N)*E)

= 1 mod ((p1-1)*(p2-1)*(p3-1)*….*(pi-1) * E’)

where, i=8, 16, 32… based on number primes

= 1+K ((p1-1)*(p2-1) (p3-1)*….*(pi-1)) * E’             (5)

where, K is any positive integer [4]

Substituting eq. (5) in eq. (4)

CD mod n=M1+K ((p1-1)*(p2-1) (p3-1)*….*(pi-1)) * E’ mod n

= M*M K ((p1-1)*(p2-1) (p3-1)*….*(pi-1)) * E’ mod n

= M*(M (p1-1))K(p2-1) (p3-1)*….*(pi-1)) * E’ mod n

since Mp1-1=1 mod p1                                 

(Using Fermat Little Theorem[5])

= M * 1 K(p2-1) (p3-1)*….*(pi-1)) * E’ mod n

= M mod n      (since M < n)

= M

 

GRSA- AA Numerical Example For 8 Prime Numbers

In this section, we discuss example problem using GRSA-AA for key generation, encryption and decryption using 8 prime numbers.

·         Take Eight large prime numbers p1= 101 p2=103, p3=107, p4=109, p5=113, p6=139, p7=131 and p8=127.

·         Compute

n ← p1 * p2

m ←p3 * p4

o ← p5 * p6

p ← p7 * p8

Thus,

n=10403, m =11663 o =15707 and p =16637

·          Compute N1 ← n * m, N2 ← o * p and N ← N1 * N2

Thus,

N1 =121330189, N2 =261317359 and N =31705684556450851

·         / * Compute Euler phi values of n, m, o and p * /

Φ(n) ← (a-1)  * (b-1)

Φ(m) ← (c-1)  * (d-1)

Φ(o) ← (e-1)  * (f-1)

Φ(p) ← (g-1)  * (h-1)

Thus,

Φ(n) =10200

Φ(m) =11448

Φ(o) =16380

Φ(p)=15456

·         / * Compute Euler phi values of N * /

Φ(N) ← Φ(n) * Φ(m) * Φ(o) * Φ(p)

Φ(N)= 29562475557888000

·         Find a random number e1, satisfying 1 < e1 < Φ(n) and gcd (e1, Φ(n)) =1

e1 =239

Find a random number e2, satisfying 1 < e2 < Φ(m) and gcd (e2, Φ(m)) =1

e2 =151

Find a random number e3, satisfying 1 <e3 < Φ(o) and gcd (e3, Φ(o)) =1

e3 =227

Find a random number e4, satisfying 1 < e4 < Φ(p) and gcd (e4, Φ(p)) =1

e4 =167

Compute A1 ← e1e2 mod N1

A1 =61150386

Compute A2 ← e3e4 mod N2

A2 =215986280

Compute E’ ← A1A2 mod N

 

E’ =1581954508210176

Find a random number E, satisfying 1 < E < Φ(n) * E’ and gcd (E, Φ(n) * E’) =1

Value of E =239

Compute a random number D, such that,

D ← E-1mod(Φ(N) * E’)

D =18393515478533395755916798406159

Input Message =786

Encryption, C ← MEmod n

C =9614

Decryption, P ← CDmod n

P = 786

Security Analysis

Original RSA is vulnerable to various attacks including timing attack as shown in [6] and factorization attack. The time to break RSA system is equivalent to the time for factorizing public key n. This simply requires finding prime factors of n. For this purpose, elliptic curve factorization (ECM) and General Number Field Sieve (GNFS).

GNFS and ECM are the first and third fastest factoring methods respectively. ECM is commonly is used for small number factoring whereas GNFS is capable of factoring larger than 100 bits. However, the beauty of GRSA-AA lies in the fact that even if ECM or GNFS can be used to factor public key n, but this parameter is not sufficient to recover private key D (which is a function of N not only n) to break the system. The above factoring methods can be used to find prime numbers namely p

The above factoring methods can be used to find prime numbers namely p1 and p2 but other prime numbers (remaining 6 in the case of GRSA-AA using 8 primes and remaining 14 primes in the case of GRSA-AA 16) can be found only a brute force attack which is computationally infeasible for large prime numbers. Thus, time required to break the system is defined as:

tsystem = tp1,p2 + tbruteforce

tsystem = Time taken to break the system

tp1,p2 = Time taken to find p1 and p2 using GNFS or ECM

tbruteforce = Time taken for brute-force attack

Practically launching a brute force attack would be a difficult task with large prime numbers of 1024 bits or greater, so it is almost practically impossible to launch a brute force attack against such a system, and giving an unbreakable cryptographic system to its users.

Conclusion

In this blog post, we presented a novel approach towards Generalized RSA scheme using 2k primes with secure key generation and named it GRSA-AA. GRSA-AA uses 2k large prime numbers thereby increasing the time required to find the private key components (D, n) in which D is a function of N. An attacker factorize the n to determine p1 and p2, however, the value of D depends on N (not n) which is a product of 2k prime numbers. We have presented an algorithm and mathematical proof of GRSA-AA in earlier sections. Examples are presented using 8 prime numbers and 16 prime numbers. Public key component E of (E, n) in GRSA-AA is computed using multiple iterative modular and Euler functions complying Fermat Little Theorem. Hence, it is computationally infeasible to determine the value of D based on the known factorization of n. Key generation time in GRSA-AA is comparatively higher than earlier related schemes which is, therefore more secure (computationally infeasible to determine D) and thus making GRSA-AA stronger than earlier related schemes. Processing complexity, including encryption and decryption time, depend on the key length and remains nearly same as in the earlier related scheme, hence, not burdening the system by processing overhead. It is computationally infeasible to determine all the prime numbers involved in the generation of N, the attacker using brute force cannot determine private key component D. Based on our results, and conclusion, GRSA-AA is best suited in security employing in a distributed computing environment. In today’s changing world, distributed computing is available everywhere, however, security is compromised for the processing and transmission capability. Our research can also become useful in providing stronger security in distributed computing environment.

About the Author: Auqib Hamid Lone

auqibAuthor Bio :   I have done Bachelors in Information Technology and Engineering with distinction, post my B. Tech my interest and passion towards information security took me into master’s and I completed M. Tech in Information Security & Cyber Forensics from Jamia Hamdard University, New Delhi with Gold Medal. As a part of my thesis, I worked on RSA algorithm and generalize it to remove the factorization Problem. My areas of interest are Cryptography, Network Security, Web Application Security and Digital Forensics

[adrotate banner=”9″]

(Security Affairs – RSA, Secure Key Generation)

References

[1] A. Lone, “Generalized RSA Using 2k Prime Numbers with Secure Key Generation”, M. Tech, Jamia Hamdard (Hamdard University), 2016.

[2] Stallings W. Cryptography and Network Security: Principles and Practice, 5th ed. Pearson Education, 2011.

[3] Diffie, W.; Hellman, M. New directions in cryptography. IEEE Transactions on Information Theory 22, 1976, pp. 644–654.

[4] Rivest RL, Shamir A, Adleman LA. Method for obtaining digital signatures and public-key cryptosystems. Communincation ACM, 21(2), 1978, pp. 120-126.

[5] Vanstone Menezes, Handbook of Applied Cryptography. pp. 286-287.

[6] Ribenboim P. In: The New Book of Prime Number Records. 3rd ed., Vol. 49. Springer-Verlag, 1995, pp. 22-25.

[7] Carl PA. Tale of two sieves. Notices American Mathematical Society, 43(12), 1996, pp. 1473-85.



you might also like

leave a comment