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 2^k 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,.…(2^k) 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 2^k 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 2^k 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 Encryption and Decryption

Algorithm 2.3 GRSA-AA Encryption And Decryption

2.4       Mathematical Proof of GRSA-AA

GRSA-AA is proved mathematically in the below subsection.

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.

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 p₁ and p₂ 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:

t_system = t_p1,p2 + t_bruteforce

t_system = Time taken to break the system

t_p1,p2 = Time taken to find p₁ and p₂ using GNFS or ECM

t_bruteforce = 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 2^k primes with secure key generation and named it GRSA-AA. GRSA-AA uses 2^k 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 p₁ and p₂, however, the value of D depends on N (not n) which is a product of 2^k 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

Author 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″]

References

[1] A. Lone, “Generalized RSA Using 2^k 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.