Encryption as explained earlier1 is simply substitution of letters with numbers and then using complex mathematical functions to alter the pattern of numbers. This article is about understanding Asymmetric Cryptography, Public Key, Private Key and the RSA Algorithm.
Encryption has been there from a long time and symmetric key or secret key cryptography had a monopoly over all communications. Symmetric key meant using the same key to encrypt or decrypt a message. You can read this short article to understand basics of encryption in under ten minutes: Encryption and Symmetric Cryptography – How is data secured electronically?
Asymmetric Cryptography or Public Key Cryptography
Till the end of World War II humanity was suffering this problem where secure communication between nations could be established only by physically sharing encryption keys and risking adverse situations. It was impossible to hold fully wireless communication. Spies and agents were the sole key exchange mechanism.
The concept of modern Asymmetric Cryptography or Public Key Cryptography (“PKC”) was published in a Mathematics paper titled, “New directions in cryptography” by a Stanford University professor Martin Hellman and a graduate student Whitfield Diffie in 1976. 2
They described the mechanism as a two-key cryptosystem in which two parties could engage in a secure communication over a non-secure communications channel without having to physically share a secret key chart.
In this method two different keys are used, one for encrypting the message, another for decrypting the message. The key used to encrypt a message is called a public key, while the one used to decrypt it is called a private key. The values of these keys are mathematically linked. It is impossible to carry out encryption and decryption without this functional link.
Every recipient has to generate this set of two keys. The encryption key or the public key would be made available publicly. And the decryption key or the private key would be privately stored.
Therefore only the intended recipient can decrypt the message. However, the sender may not decide to reveal his identity.
There are multiple asymmetric cryptography algorithms.
- Elliptic curve cryptography
- Diffie-Hellman key exchange
- Key Serialization
- Signature Interfaces
- Asymmetric Utilities
We will discuss RSA asymmetric algorithm. The RSA algorithm is the most widely used encryption algorithm in the world.
RSA algorithm (Rivest-Shamir-Adleman)
Soon after the publication of Hellman and Diffie on asymmetric key exchange mechanism, three scientists at the MIT Lab. for Computer Science and Department of Mathematics, Ron Rivest, Adi Shamir and Leonard Adleman published another paper titled:
A Method for Obtaining Digital Signatures and Public-Key Cryptosystems3
The algorithm was made popular by the company of the same name – RSA Security. The company was owned by Ron, Adie and Leonard and it jointly held the US Patent No. US 4405829 A.4
Clifford Cocks, an English mathematician working at the English intelligence agency GCHQ, had developed an equivalent system in 1973, but it was not declassified until 1997.
The mathematics behind RSA algorithm
This algorithm uses a set of complex mathematics rules to find out the encryption and decryption key. The required mathematics for this include: prime factorisation, Euler totient function, Euclidean algorithm (for finding GCD) and modulus. The strength of the algorithm relies on the time difficulty required to solve prime factorisation of very large numbers.
While it takes not even a fraction of a second to multiply two large prime numbers, it takes an awfully long time to find the prime factors from the product.
For e.g. if I were asked to find the prime factors of the number 143, it would take me at least 5 seconds to guess that it is divisible by 13 and returns the whole number 11. The time would be required to try dividing the number 143 by every number starting from 1 until 11 is found as a perfect divisor. In comparison it would not take even a split second to calculate 13*11=143.
It gets more difficult to factor higher prime numbers, say, 1431431431 (17123, 83597). Similarly, if the number to be factored is 100 digits long, even the fastest computers would take more than 30 years. And a 200 digit long number would require at least 8 million years for the latest binary computers.5
In comparison multiplication of two 100 digit prime numbers would only take 56 seconds.
This one way difficulty in mathematical calculation is exploited by the RSA Algorithm to create a one-way encryption method. Decrypting the cipher would require guessing the prime factors of a very long number.
Formula and Calculation
m^e mod n = c
means, if m^e is divided by n it would leave remainder cencrypt: m^e mod n = c
decrypt: c^d mod n = m
Where m is the message;
(e,n) is the the encryption key;
c is the cipher;
d is the decryption key;
n is the RSA modulus
The public key used to encrypt a message is the combination (e,n). While the private key used to decrypt the message is (d).
The relation between the numbers e, n and d are very critical to maintain the data integrity. The calculation of e, n, d therefore is more complex. To keep it simple we will take a very small message and small keys.
Step 1. Select two, large, random, prime numbers, p and q. Calculating the RSA modulus n by multiplying p and q.
So for p I pick 11
and for q I pick 5.
Therefore n is 55.
Step 2. Calculate the totient t of the modulus n.
The totient function, also called Euler’s totient function, is defined as the number of positive integers, that do not have any common factor with n other than 1.
Totient is multiplicative. Therefore totient of n is the multiplication of the totient of p and q. Also, the totient of any prime number is the number itself minus one.
t(n) = (p-1)*(q-1)
totient of n = (11-1)*(5-1) = 40
Step 3. Select number e (relatively prime to and less than t)
One number is relatively prime to another when they do not share any factors except for 1.
So e can be 3, 7, 9, 11, 13, 17, …
I will take e as 7
Step 4. We have to find d which is the Modular Multiplicative Inverse of integer e with respect to modulo t.
In other words, e*d mod t = 1
We have 7*d mod 40 = 1,
we have to solve for d.
In mathematics, the Euclidean algorithm, is a clean way for finding out the GCD of two numbers. I will request you to watch this video on Euclidean algorithm and I would take the liberty of not explaining it. ‘7d mod 40 = 1’ means that if 7d is divided by 40 it would leave remainder 1.
In other words we have to first find the greatest common divisor (GCD) of 40 and 7. And we would be using the Extended Euclidean Algorithm to do that.
The GCD of 40 and 7 is 1. A modular inverse is possible only when the GCD is 1.
And the Modular Multiplicative Inverse of 40 and 7 is 23.6
Finally, d is found to be 23.
Encryption and Decryption
We now have the public key e,n (7,55). The private key d (23). Let’s take ‘*’ the asterisk as the message.
The ‘*’ in ASCII convention is ’42’7
encrypt: m^e mod n = c
Let’s encrypt the message ’42’ using RSA Algorithm:
42^7 mod 55 = 488
We can now publish or broadcast the message 48 publicly, only the person with the private key can decipher it.
decrypt: c^d mod n = c
Let’s now decrypt the cipher ’48’:
48^23 mod 55 = 429
Once the private and public keys are created by the recipient, the recipient will publish the public key globally. The recipient may now ask the sender to broadcast the encrypted messages. These can be received by anyone but can be decrypted only by the recipient’s private key.
Asymmetric cryptography being a more complex mathematical function than symmetric cryptography causes computation to take more time.
It is therefore hardly ever used to encrypt stored data and mostly used for electronic communication. It proves useful in technologies where verifying and ascertaining identity is required among multiple peers in a common network.
For e.g.: HTTPS protocol for online transactions, BitCoins, Chatrooms, etc.
You might have seen banking websites advertising 128/256 bit encryption transactions.
What do they actually mean? Is it enough? How long would it take a hacker to crack the network?
A 256 bit key can hold a 32 digit long modulus. Which would take around 3 minutes to crack open (factorised to its prime factors).10 A 512 bit key would take about 12 days. While the RSA Security website itself instructs to use a minimum of 1024 bits.
Unauthorised decryption by hackers
Anyone who is using the same wifi connection as you do, can listen to the radio signals sent out by your wifi module of your computer. The numerical messages broadcasted by your wifi module can be intercepted.
Based on the public key anyone can find out the private key by factorising the modulus of the public key. The only difficulty is the prime factorisation of the modulus. Smaller modulus of 32 digits as present in 256 bit encryption can be factorised in under 3 minutes. Once the private key is derived from the factors of the modulus, the numerical messages you broadcasted can be read. Someone may also decide to forge your identity.
The need is not to drop the RSA Security standard but to use it with all the available guidelines. Encryptions need to be at the least of 1024 bits.
Our security systems are quite outdated, and regulators are oblivious to the dangers. The more you learn and know about these intricacies the better are my chances of getting better security.
- Encryption and Symmetric Cryptography – How is data secured electronically?
- Diffie, W.; Hellman, M. (1976).“New directions in cryptography” (PDF).
- Rivest, R. L., A. Shamir, and L. Adleman. “A Method for Obtaining Digital Signatures and Public-Key.” Communications of the ACM 21.2 (1978): 120-26. (download PDF)
- Cryptographic communications system and method US 4405829 A
- Calculating Time Complexity
- Modular Multiplicative Inverse
- ASCII Table
- Calculate on WolframAlpha
- Calculate on WolframAlpha
- Calculating Time Complexity