In this note I want to discuss some ideas from modern cryptography..
Don't be intimidated by the size of the note...if you understand the ideas properly trust me it's worth it...you will learn about one of the most effective cipher systems still actively used today!!
In conventional cryptographic systems like the Caesar cipher,the sender and the receiver jointly have a secret key that is used for encryption and decryption.But in public-key cryptography two keys are used - an encryption key and a decryption key.Though these keys are related,there is no easy way to derive the decryption key from the encryption key.Thus the encryption key can be made public without compromising the decryption key.A major advantage of the public cryptosystem is that it is unnecessary for the senders and the receivers to exchange a key in advance of their decision to communicate with one another.
In 1977,Ronald Rivest,Adi Shamir and Leonhard Adleman proposed a public-key encryption system that uses elementary ideas from number theory.It's security depends on the assumption that in the current state of computer technology,factorization of composite numbers having large prime factors is so time consuming that it is almost unrealistic.
At first the user of the RS system chooses a pair of very large distinct primes.Then the two numbers are multiplied to form a number called the .The factorization of this product is beyond all computational abilities.Next,they need to select a positive integer such that called the .the pair is kept in a public profile(like a telephone directory) as the user's personal encryption key which allows anyone else to encrypt and send a message to this individual,but the primes and are unknown to everybody else.
First each alphabet of the message to be sent is converted into a 2-digit number.A standard procedure for executing this is using the following assignment:
It is aasumed that the message , where n is the enciphering modulus.Otherwise it is diffucult to distinguish M from any larger integer congruent to modulo n. If the message M is too long then it is broken into separate blocks of digits of appropriate size and each is coded separately.
After looking up the intended recipient's encryption key in the public directory,the sender disguises the plaintext into the ciphertext ,by raising M to the -th power and then taking modulo ,that is, . is selected such that
The authorized personnel deciphers the message by first determining the recovery exponent , for which
Since ,this linear congruence has a uniqee solution modulo .The Euclidean Algorithm produces as a solution to the equation . Note that the recovery exponent can only be obtained by someone who knows both and and hence both and .The knowledge of any unauthorized third party is limited to the public key .
Now if we calculate , we get, whenever .
In other words raising the plaintext number to the -th power and taking moduulo n recovers the plaintext.
It is to be noted that the assumption was used to use Euler's theorem.In case they are not relatively prime, we can prove by similar argument that Since , we have ,that is !!
Convert the digital representation to the alphabetic one.
Let us consider an unrealistically small example choosing 2 primes and .
The enciphering modulus is then and .
Since , we may choose to be the enciphering exponent.It can be calculated that in this case the recovery exponent will be .
Let the first block from the digital version of the plaintext be ,this encrypts to the ciphertext .But by using the recovery exponent , we can decrypt this to .
This is the original digital form of the plaintext !!!
Banks(1024-bit),Facebook(1024-bit),Twitter(1024-bit),Ebay(1024-bit) all use the RSA cipher to protect our internet secrets!!The numbers in the brackets denote the number of digits of the enciphering modulus. A 768 bit key has recently been broken.
Have fun encrypting :D ....i'll try to do a few more posts on modern ciphers next week
Introduction to Algorithms by Cormen,Leiserson,Rivest and Stein
Elementary Number Theory by David M.Burton(I took the example from here)
Encryption and huge numbers by NumberPhile (Video by Brady Haran and demonstrated by Dr.James Grime)