In one of my recent blog posts, we explored the world of and more specifically, took a look at secret key cryptography and its applications. cryptography We took a closer look at the , which albeit simple, is one of the oldest methods of encryption in the history of cryptography. Also, I feel that the Caesar Cipher is a good entry point into understanding cryptography. Caesar Cipher In this blog I want to discuss the types of encryption methods and then take a look at a specific form of encryption known as RSA encryption. Encryption As per my other blog on cryptography, we discussed what encryption actually is. The basic idea behind encryption is that we want to or transform some or information into so that only the recipient can the the back into . encrypt plaintext ciphertext decrypt ciphertext plaintext There are two main types of encryption that we will discuss. The first is and the second is symmetric encryption asymmetric encryption. Symmetric Encryption symmetric encryption uses the same secret key for both encryption and decryption Symmetric encryption is the conventional method of encryption and is typically the more simple method of the two. In these cases, there is only one key that is used by both parties to both encrypt and decrypt information. So, the sender uses this key before sending this message and the recipient uses the same key before reading the message. Any party that somehow obtains the ciphertext won’t be able to decrypt the message without this key. The is actually an example of symmetric encryption since the same key used to encrypt a message can be used to decrypt a message. Caesar Cipher This form of encryption is generally used when sending large amounts of data since it does not take much time. Asymmetric Encryption this method uses a public key/private key combo Asymmetric encryption is a relatively new and more complex method over symmetric. The reason for its complexity is mainly due to the fact that we need two different keys for implementation. The first key is the which as the name suggests, is a key available for all to see. The however, is kept secret by the owner of the public key private key public key. If we were sending some information using asymmetric encryption, the first thing we have to do is use an encryption algorithm, along with the public key to get obtain our ciphertext. Now, the algorithm we utilize allows for decryption not with the public key, but the private key. What is interesting here is that you cannot decrypt the information with the same key used to encrypt it, which was the case for the . Caesar Cipher Can you imagine what these algorithms are like? Well, you won’t have to imagine for long as we move into… RSA Encryption RSA stands for Rivest Shamir and Adleman RSA encryption is an . It was created by these three geniuses, Ron Rivest, Adi Shamir and Len Adleman. asymmetric cryptosystem — a cryptographer and professor at MIT, he helped come up with the RSA encryption algorithm. He also invented several algorithms such as RC2, RC4, RC5. Ron Rivest symmetric key encryption — also had several contributions to computer science and cryptography such as scheme, the breaking of , and Along with the help of colleague, Eli Biham, he discovered It turned out that IBM and the NSA had already discovered this and kept it a secret. Adi Shamir Shamir secret sharing Merkle-Hellman knapsack cryptosystem TWIRL. differential cryptanalysis. — computer science professor at the University of Southern California. Aside from RSA encryption, he was known for the experimental use of DNA as a computational system. Len Adleman The system or algorithm itself works with very, very large prime numbers. A prime number is a whole number greater than 1, whose only two whole-number factors are 1 and itself. How do they find these large primes? Without popping a blood vessel on how this works, there are many ancient math algorithms out there that do things like find prime numbers. One such example is the Sieve of Eratosthenes. Sieve of Eratosthenes The algorithm is intended to find all prime numbers until any given limit, which in this case is 120. The way this works is by iteratively marking as composite the multiples of each prime starting with 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime and the difference between them is equal to that prime. Ok, back to RSA encryption. Before moving on however, I must apologize if some of this seems arcane. That actually is partially the point. As programmers, we must be very cautious when taking encryption into our own hands. The following slides were taken from a presentation I did on Cryptography. We’ll go over how the encryption/decryption keys work and then how these keys are formulated. Suppose we have an = (5, 14) and some which is the letter “B”. Oh man, what a big secret we must encrypt! encryption key plaintext Since we need to deal with numbers and not letters, let’s change the letter “B” into a character code of 2. In order to transform this into , we will use the following formula. ciphertext (p^e_a ) mod e_b (p^e_a ) mod e_b, where is plaintext(“B”), is encryption key A(5) and is encryption key B(14). You may or may not be familiar with the or operator. p e_a e_b mod modulo In computing, the operation finds the remainder after division of one number by another modulo Great, so now we have the number 4 which is equivalent to the letter “D”. The letter “D” is our ciphertext. So, in order for us to decipher this text. We will use the or = (11, 14). private key decryption key We can use the same formula above and as you can see from the slide above, we end up getting a character code 2, which is equivalent to our “B”. Eureka! It works! plaintext What’s really interesting is how you can obtain these keys. As I had mentioned before, the RSA encryption algorithm works with very large prime numbers, typically hundreds of digits long. For demonstration purposes we will work with small primes just so that we can conceptualize how we got those encryption and decryption key pairs. Remember that our was (5, 14) and our was (11, 14) NOTE: encryption key decryption key Let’s go over each step. Step 1 — We need to find two numbers and These two numbers must be prime, so let’s choose 2 and 7. p q. Step 2 — Next we need to come up with N. To find N we can use the formula p * q = N. Now we have N, which will be the and , which you can see is the same number, 14. encryption_b decryption_b Step 3 — That funny symbol in this step is the greek letter which represents Euler’s ‘totient’ function. We need to use this(don’t worry about Euler or the specifics on totient too much now) function on N, which just finds the number of for N. That number turns out to be 6. phi coprimes In number theory, two integers a and b are said to be , mutually prime, or (also spelled ) if the only positive integer that divides both of them is 1. That is, the only common positive factor of the two numbers is 1. This is equivalent to their greatest common divisor being 1. relatively prime coprime co-prime Step 4 — We need to find or . In order to do that we need to choose a number so that it is greater than 1, but less than the totient of N, which we found in Step 3, to be 6. So we choose 5 since it satisfies those conditions. Ok, so we can set = 5. e encryption_a encryption_a Step 5 — Now we need to find or The formula to figure this out is the following. d decryption_a. we can plug the values in here and get d * e(mod ( N)) = 1, φ d * 5(mod 6) = 1 d = 11 can actually be one of several numbers, but we can choose the number 11 since it satisfies all conditions. Now we have both and pairs(5, 14) and (11, 14). NOTE: d encryption decryption key And that, ladies and gentlemen, is a high-level view on how the RSA cryptosystem works!
![10 Best Object-Oriented Online Programming and Design Courses 2020 [Updated]](https://firebasestorage.googleapis.com/v0/b/hackernoon-app.appspot.com/o/images%2FMQzhgEvAeOXyPo3IjFRz4IZU3K83-r85m3uu7.jpeg?alt=media&token=52050782-8c47-4a38-85af-94636f190ad2&auto=format&fit=max&w=3840)
