PENNY PLAIN
CRYPTOSYSTEM ALGORITHM
Have you ever wondered which one of the cryptography techniques has a penny plain algorithm?
Yes! penny plain i.e. plain and simple algorithm.
It’s the RSA Cryptography Algorithm, that was built in 1977 by Ron Rivest, Adi Shamir, Leonard Adleman.
— — — — — — — — — — — Popularly known as Rivest-Shamir-Adleman ( RSA ) algorithm, it was built after Whitefied Diffie, Martin Helman and Ralph Merkle introduced public key cryptography in 1976. RSA is an asymmetric cryptography popularly known as public key cryptography.
— — — — — — — — — — —
Let’s go down the memory lane for a while -
Some Important Terms -
- Plain Text — It is information that can be directly read by humans or a machine (this article is an example of plaintext).
- Cipher Text — When the plaintext is encrypted using a key it becomes a garbled text (unreadable text) which is called as the cipher text.
- Encryption — The process of converting plaintext to ciphertext.
- Decryption — The process of converting ciphertext to plaintext.
Why the need of Asymmetric Cryptography ?
When using symmetric cryptography communicating parties (Harry Potter and Luna Lovegood. P.S.- I was bored with Alice and Bob) have the same capabilities, since they possess the same key.
“Symmetric Cryptography is a type of cryptography where only one key (a secret key) is used to both encrypt and decrypt electronic information. The keys should be exchanged before hand so that it can be used in the decryption process.“
As a consequence, symmetric cryptography cannot be used for applications where we would like to prevent cheating by the communicating parties (either Harry or Luna).
For instance, in e-commerce applications it is often important to prove that communicating Parties (Harry or Luna) actually sent a certain message, say, an online order for a flat screen TV. If we only use symmetric cryptography and Luna changes her mind later, she can always claim that Harry, the vendor ( not the wizard ! ), has falsely generated the electronic purchase order.
Preventing this is called nonrepudiation and can be achieved with asymmetric cryptography.
“ The sender of a message can not deny the creation of the message. “
“Asymmetric cryptography is a branch of cryptography where a secret key have two parts, a public key and a private key. The public key can be given to anyone, trusted or not, while the private key must be kept secret.“
So if we look at the scenario explained above (between Luna and Harry) if Luna orders a flat TV screen and changes her mind later (She spent all her money on shopping). If the communication parties are using Asymmetric cryptography then even if she wants to deny buying the TV she can’t as when the order is made she encrypts it with her own private key and Harry decrypts it with the public key made available by Luna.
As only Luna could have encrypted the message by her private key (secret key) so she can’t deny that she ordered a flat screen TV.
“Encryption and Decryption can be done via public key as well as private key”
Coming back from our memories -
Why is it called a penny plain algorithm ?
Looking at the RSA algorithm you must be convinced that it is easy, simple and short. The steps given in Figure 1 are the main instructions to be followed to calculate the keys and to encrypt and decrypt the data.
Unlike the other Symmetric and Asymmetric Algorithm where you have to learn tedious algorithms just to encrypt the data, RSA is a unique little algorithm standing straight in the pool of other complex algorithms.
Easy and simple doesn’t mean it’s not strong. The Mathematics behind this algorithm is pretty strong as till this date we use RSA in many cryptosystems and also in Digital Signatures and Digital Certificates.
If you look at the certificate for google.com you will find RSA there as well.
For learning RSA our prerequisites are -
1. Prime numbers
2. Euler’s Totient
3. Greatest Common Divisor
4. Extended Euclidean Algorithm
5. Modular Arithmetic (Clock Arithmetic)
Basically Number Theory
Encryption involves calculating the CipherText ( C ) which is Plain Text ( M ) raised to the power public key ( e ) of the intended receiver modulo the product of two prime numbers ( n ).
P.S. The best thing about the public key cryptography is that anyone can encrypt them but only the intended user can decrypt them.
Decryption involves calculating the Plain Text ( M ) which is Cipher text ( C ) (Encrypted Text) raised to the power private key ( d ) of the receiver modulo the product of two prime numbers ( n ).
First of all, we need to choose two large prime numbers around 1024 bits long which is a secret (Shhhh!). For choosing such numbers we can make use of the Primality Test ( A Primality Test is an algorithm for determining whether an input number is prime ) such as Miller’s Rabin, Fermat’s Primality test etc. Multiply the two numbers and get ‘n’.
After choosing adequate prime numbers, we need to find the Euler’s Totient.
“ The totient function ϕ(n) also called Euler’s totient function, is defined as the number of positive integers ≤ n that are relatively prime to (i.e., do not contain any factor in common with) n “
( P.S.— 1 is counted as being relatively prime to all numbers )
After getting the Euler’s Totient we need to choose a public key ‘e’ which should be relatively prime to the euler’s totient. The public key ‘e’ helps to get a private key ‘d’. Calculate the private key ‘d’ with the help of the extended Euclidean algorithm.
YOU ARE DONE.
“ But simple does not mean it’s not strong enough. “
To find out how strong RSA is we need to see how difficult it is to factor ‘n’ (which is the product of 1024 bits of data making it 2048 bits of n or 512 bits of data making it 1024 bits of ‘n’) which is called the integer factorization problem.
“ The underlying one-way function of RSA is the integer factorization problem.”
Multiplying 2 large prime numbers is easy ( Experts can do it in their mind and others can do it on paper and pencil ) but factoring, it is difficult.
Also if a little part of the data is already known as the cipher text and the product of two prime numbers the difficulty is to find Plain Text ‘M’ which is raised to the power the public key ‘e’ which makes it a RSA problem ( Given an RSA public key (n,e) and a cipher-text ‘C’, use C = M^e(mod n), to compute ‘M’).
Relation between Problems
Integer factorisation and RSA problem goes hand in hand.
The RSA assumption is that the RSA Problem is hard to solve when the modulus n is sufficiently large and randomly generated and the plain- text M (and hence the ciphertext C) is a random integer between 0 and n − 1. So to solve the RSA problem we need to factorise the sufficiently large n which actually is the integer factorisation problem, you can compute ϕ(n) and thus d i.e. — the private key ‘d’ .
Any C can then be decrypted with the private key d to get M (Plain Text).
“ RSA is the prime example for a public-key algorithm that is computationally intensive. “
For large RSA key sizes (in excess of 1024 bits), no efficient method for solving this problem is known, if an efficient method is ever developed, it would threaten the current or eventual security of RSA-based cryptosystems.
“ RSA function is a trapdoor one-way function (‘d’ private key is the trapdoor). “
If we are able to find d we can find M easily —
So, C^d mod n = M. (By above proof)
“Having C, d and n I am pretty sure we can find M”
RSA encryption is not meant to replace symmetric ciphers because it is several times slower than those. In practice RSA is often used together with a symmetric cipher such as AES, where symmetric cipher does the actual bulk data encryption.
