Introduction
Emerging technologies have globalized trading and communication systems. This has had an overwhelming effect on the world as most businesses re-align to implement e-commerce. These transactions and communication networks need protection against unauthorized access. In this regard, several methods have been established to safeguard online transactions as well as personal identification details. Most of these methods employ encryption to safeguard their online activities. Security is essential in protecting passwords, private communications, online payments as well as safe communications, among others. Cryptography, which refers to the science of writing using secret codes, originated in ancient Egypt as inscriptions. Its use has been considered a protective measure in modern technology where communications are transmitted through unsafe media. It has been employed for authentication, integrity, Non-repudiation, and private purposes. There are different types of cryptographic algorithms such as hash functions, private and public-key cryptography. This paper will explore the definition, structure, and the use of Rivest, Shamir, and Adleman’s (RSA) public key cryptographic algorithm (Rivest, Shamir & Adleman, 1978).
Definition
RSA which is derived from its inventor’s names Rivest, Shamir, and Adleman, emerged in 1977 and has since been used for security purposes. It was the first type of algorithm to be used in signatures. Its use has been far and wide and this enabled it to be patent-free since the year 2000. Since its invention, RSA has been tried in several security implementation including digital signatures and encryption, among others. It is structured to apply factorization as its security tool and this makes it comparatively easy to use and understand. For this reason, RSA is the most extensively used algorithmic method for online security purposes. Its use has also extended to IP data, e-mail, conferencing services, transport data and many more.
Theory
Prior to its invention in 1977 by the three MIT scholars Rivest, Shamir and Adleman, Clifford Cocks had tried to propose its implementation for the UK intelligence agency in 1973. However, this did not succeed as the computers required for this exercise were very expensive. When RSA was invented in 1977, and its implementation described in 1983 in MIT, the institution was granted a 17-year patent which was to expire in 2000, however, a public patent was declared by the RSA security that year. RSA employs the use of trap-door ciphers, where encoding and decoding of secret keys are done. This has made it easy to decode keys. The method allows those who have decoding keys to generate encoding ones and also restricts the generation of decoding keys from encoding, this way; it protects information. RSA encryption employs the Cipher method in its key generation (Rivest, Shamir & Adleman, 1978).
RSA algorithm involves the use of three stages or processes. These include key generation, then encryption, and finally decryption. RSA can use a public key or private key. The use of Public key is usually employed when dealing with encryption of messages while private decryption is for privacy and security purposes (Ireland, 2011, p. 1).
Key Generation
This method entails the use of a public key for encryption purposes. These are done as follows:
- Choosing 2 discrete prime numbers, for instance, p and q. These numbers are supposed to be chosen randomly to enhance security details; this is usually done using primality tests. Care should also be taken to ensure that these numbers have the same bit length.
- The second step involves the computation of numbers above for instance, from the above example, we shall introduce a new number, n = pq, where n is the modulus of the two numbers.
- This step involves further computation using Euler’s function as shown: (n) = (p – 1) (q – 1).
- The fourth step involves choosing an integer e, such that (n) < e < 1 and also the equations are co-prime, that is, their ((n), e) gcd is 1. In that case, e is released as the exponent of the public key. In most cases bit-length of e determines their security levels, for example, very short values such as 3 have proved to be less secure than the others.
- The next step involves finding the private key exponent, usually denoted as d; this is usually computed by use of an extended Euclidean algorithm. D is computed from e as follows: d = e-1 mod (n);
Therefore, to obtain the public key, one needs the public exponent e, and modulus n, while to obtain private key, private exponent d must be determined. The latter must be kept secret (RSA Security, 2011, p. 1).
Encryption stage
In this process the public key is transmitted while private key is kept secret. For instance, If George transmits a message X to Mary, and Mary transmits her encryption key say (n, e) and keeps the private key d, then George should change X into x, where x is an integer. x should be such that 0 < x < n using padding scheme that they have agreed on. George will then compute the cipher-text which corresponds to c = x e (mod n), using exponential squaring (Riikonen, 2002).
Decryption stage
This stage involves computing the result in encryption to obtain decryption exponent d. using the case above; the following method can be employed. X = c d (mod n) meaning that when x is provided, then Mary can obtain X by reversing the initially agreed padding scheme (Davis, 2003, p. 1).
Mathematics
RSA algorithm entails the use of several mathematical theorems like, Fermat’s little and extension theorems, as well as the Chinese remainder theorem. These theorems are used to enable key generation, encryption, decryption so as to ascertain the use of public key and private key. The following calculations are involved in RSA algorithm (Menez, et. al., 2002).
It starts by selecting random prime numbers, i.e. p and q in which confirmation can be made by p! = q. modulus n, is then computed as n = pq and (n) = (p – 1) (q – 1). Public exponent is given as e, such that (n) < e < 1 and gcd (e,(n)) = 1. These are used to compute d = e-1 mod (n);Thus giving public key as and private key as d. Encryption would therefore be c = m e mod n, while decryption would be m = c d mod n. For digital signatures s = H (m) d mod n while its verification is m’ = s e mod n, and is only correct when m’ = H (m), where H is a hash function (Coppersmith, 1997, p. 22).
For example, if p =47 and q = 71;
Then n = 3337;
(n) = 46 * 70 = 3220;
By letting e = 79, then d = 79 -1 mod 3220 = 1019
Therefore, from the formulae above, public key = n and e, while private key = d.
Also, by discarding p and q, we shall have;
Encrypt message m = 688, and hence c = 688 79 modulus 3337 = 1570.
Decrypt message shall be c = 1570. And m =1570 1019 modulus 3337 which gives m =688.
How it works
RSA uses factorization method to enhance its security; in addition it employs the use of RSAP, which is known as RSA problem. RSA problem ensures that RSA encryption is safeguarded. This ensures that only one number exists in the field. Factorization takes advantage of the fact that factoring large numbers is usually difficult in ensuring security. This can be done very fast, in fact quicker than brute forcing. Implementation of RSA involves the use of tools such as Arbitrary (multiple) precision arithmetic, prime number generator as well as the PRNG (Pseudo Random Number Generator).
The algorithm is based on three theorems, Fermat’s little and extension theories as well as the Chinese remainder theorem. These theories form the basis of RSA and are used to obtain decryption.
Fermat’s Little Theorem
This theory states that, if say p is a prime number, and m is an integer,
Then m p-1 =1(mod p). If (a, p) = 1.
Fermat’s Extension Theorem
In this method, if (a, p) = 1,
Then a (m) = 1(mod m),
Where (m) gives the digits less than m, and also prime to m
Chinese remainder theorem
In this theorem if say (p, q) = 1, and may not be prime numbers,
Then a = b (mod p);
And a = b (mod q),
Then a = b (mod pq).
Conclusion
In summary, the following processes are followed in RSA algorithm, Key generation, which involves selection of random prime numbers say, p and q in which confirmation can be made by p! = q. Modulus n, is then computed as n = pq and (n) = (p – 1) (q – 1). Public exponent is given as e, such that (n) < e < 1 and gcd (e, (n)) = 1
These are used to compute d = e-1 mod (n);Thus giving public key as and private key as d. Encryption would therefore be c = m e mod n, while decryption would be m = c d mod n. For digital signatures s = H (m) d mod n while its verification is m’ = s e mod n, and is only correct when m’ = H (m), where H is a hash function (Agrawal, et. al., (n.d)).
Reference List
Agrawal, M., et. al. (n.d). Primes is in P. Web.
Coppersmith, D. (1997). Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities. Journal of Cryptology, v. 10, n. 4.
Davis, T. (2003). RSA Encryption. Earthlink.net.
Ireland, D. (2011). RSA Algorithm. DI Management.
Menez, et. al. (2002). Hand book of Applied Cryptography.
Riikonen, P. (2002). RSA Algorithm. Web.
Rivest, R., Shamir, A. & Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Web.
RSA Security. (2011). PKCS#1 Standard. Web.