RSA: The Complete Picture

INTRODUCTION: This paper is the first one in the series of papers that lead to the design of RSA Crypto Chip using VHDL and as such can be used to understand RSA Algorithm. The first part lays down the foundation of RSA cryptosystem , all of it’s mathematical intricacies have been investigated and elucidated in the easiest possible manner. I have provided "Mathematical insights" to the underlying principles of RSA so as to make the whole thing more understandable and a pleasant learning experience. BACKGROUND: RSA is a public-key cryptosystem developed by MIT professors: Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman in 1977 in an effort to help ensure internet security.This system is based on several mathematical principles in number theory. The basic technique was first discovered in 1973 by Clifford Cocks. A cryptosystem is an algorithm that can convert input data into something unrecognizable (encryption), and convert the unrecognizable data back to its original form (decryption). In a RSA cryptosystem, the sender encrypts a message with a private key. The sender's public key is posted (usually in a table). The recipient looks up the senders public key and uses it and her/his own private key to unlock the message. Private and public keys are associated by a function. In the RSA cryptosystem, the private and public keys are linked by the factorization of prime numbers The challenge of public-key cryptography is developing a system in which it is impossible to determine the private key. This is accomplished through the use of a one-way function. With a one-way function, it is relatively easy to compute a result given some input values. However, it is extremely difficult, nearly impossible, to determine the original values if you start with the result. In mathematical terms, given x, computing f(x) is easy, but given f(x), computing x is nearly impossible. The one-way function used in RSA is multiplication of prime numbers. It is easy to multiply two big prime numbers, but for most very large primes, it is extremely time-consuming to factor them. Public-key cryptography uses this function by building a cryptosystem which uses two large primes to build the private key and the product of those primes to build the public key. KEY GENERATION ALGORITHM 1 Generate two large random prime numbers say, p and q, of approximately equal size such that their product n(n is known as the modulus) = pq is of the required bit length, e.g. 1024 bits. 1.1 To generate the primes p and q, generate a random number of bit length b/2 where b is the required bit lengthof n 1.2 Set the low bit (this ensures the number is odd) and set the two highest bits (this ensures that the high bit of n is also set) 1.3 Check if prime (use the Rabin-Miller test); if not, increment the number by two and check again. This is p 1.4 Repeat for q starting with an integer of length b-b/2. 1.5 If p 3 Choose an integer e know as the public exponent or encryption exponent, 1 3.1 In practice, common choices for e are 3, 17 and 65537(2^16+1). These are Fermat primes and are chosen because they make the modular exponentiation operation faster. 3.2 Also, having chosen e, it is simpler to test whether gcd(e, p-1)=1 and gcd(e, q-1)=1 while generating and testing the primes in step 1. Values of p or q that fail this test can be rejected there and then 4 Compute the secret exponent or decryption exponent d, 1 . REFERENCE: 1 “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems". Communications of the ACM, 21 (2), pp. 120-126, February 1978. Author: I hold a B.Tech(Hons) degree in Electronics & Communication from National Institute Of Technology, Hamirpur India, and work as a research associate in High End Technologies Group, a consortium of freelancers working towards the common goal of providing technology solutions. If you have any suggestions, queries with regard to this paper then I can be contacted on abhishek_sood@rediffmail.com.