Hey guys , I wanted to write a little bit about cryptosystem . RSA is an system , which means that a key pair will be generated (we will see how soon) , a key and a key , obviously you keep your private key secure and pass around the public one. RSA asymmetric public private The algorithm was published in the 70’s by Ron ivest, Adi hamir, and Leonard dleman, hence RSA , and it sort of implement’s a trapdoor function such as Diffie’s one. R S A is rather slow so it’s hardly used to encrypt data , more frequently it is used to encrypt and pass around keys which can actually deal with encryption at a speed. RSA symmetric faster How does it work? As in D-H I’m gonna be using rather small numbers, but keep in mind that the real value of most of based algorithms happens when huge primary numbers are used. mod(p) The first part i’ll show how the trapdoor function works , and then i’ll explain why it works , so bare with me. Essentials We’ve got a message (“HELLO”) , and we’ve picked two tuples with two numbers each ( I will explain how these came about later). Obviously there’s no arithmetic operation we can perform with strings , so the message has to be convert it to something , so let’s say “HELLO” converts using some conversion algo to “ ” 2 Normally , in production , a lot of different techniques are used to encode the message and padding is also used Ok Fantastic we have everything we need , let’s run the message through the functions that will in theory encrypt this for us: mini rsa So there we have the basics of the RSA algorithm , and how the trapped function is laid out. The interesting bit is how we come about those numbers , and how (5,14) is related to (11,14), and this is the interesting part i believe , let’s start: The details of the Decryption/Encryption pair: Pick two prime numbers , I will pick and lets call them p and q 2 7 , = 2 and = 7 P Q 2. Multiply and , and that becomes the modulus P Q = P * Q = N 14 3. Make a list between and 14 and remove the common factors: 1 Now there’s an easy way to get this and that is: ( - 1 ) * ( - 1) = Q P L (7 - 1 ) * ( 2 -1 ) = 6 Great let’s save this number , let’s call it “ ” L 4. Now we get to pick the encryption key , in the example was ( ) , we know is the modulus. 5,14 14 So for the encryption key there’s a few rules: it’s got to be between and 1 L [2,3,4,5] Coprime with (6) and the (14) , the answer is there’s no other possibility . L Modulus 5 , So there we came to a conclusion of why we picked ( ) 5,14 5. The Decryption part , In the example we’ve picked ( ) , again 14 is the modulus but where does 11 come from?? , from now on let’s call it let’s find out why is 11: 11,14 D , D D has to follow one rule and this is it: So the Decryptor(11) multiplied by the Encryptor(5) modulus the length of the non coMmon factor with the modulus(14) has to be equals to 1. * % (N) = 11 * 5 % 6 = 1 D E LNCF 1 So we know if we multiply D * E and E is 5 , D will need to be a common factor of 5 , so: So I’ve made a list of numbers from 1 to and , filtered the ones that when multiplied by E and by (N) are equals 1 , so let’s see if those can decrypt the message :) , Remember the encrypted message is “ ”,and the decrypted message is “ ” so the function should be something like: 50 moduled LNCF 4 2 4 ** D % 14 = 2 <---Decrypted message So let’s do a little list comprehension to see if the rule works: Great ! it worked , you see how applying the function to all the Decryption keys that follow the rule ( * % (N) = decrypted the message successfully . D E LNCF 1) , I hope this didn’t get too complex , it certainly felt a bit complex but i tried to keep it as simple as possible .
