Skip to content
Practical TLS - October Sale
October is my birthday month, which makes for a good excuse to discount my most popular course: Practical TLS.

Use code OctBDAY2024b to get the course for $58 (originally $297).

Purchase here. Or, for more info on the top rated course on TLS, click here.

Code expires Oct 14, 2024.

RSA Example

    RSA Example

    The RSA algorithm is the most widely used Asymmetric Encryption algorithm deployed to date.

    The acronym is derived from the last names of the three mathematicians who created it in 1977:  Ron Rivest, Adi Shamir, Leonard Adleman.

    In order to understand the algorithm, there are a few terms we have to define:

    • Prime – A number is said to be Prime if it is only divisible by 1 and itself.  Such as: 2, 3, 5, 7, 11, 13, etc.
    • Factor – A factor is a number you can multiple to get another number.  For example, the factors of 12 are 1, 2, 3, 4, 6, and 12.
    • Semi-Prime – A number is Semi Prime if its only factors are prime (excluding 1 and itself). For example:
      12 is not semi-prime — one of its factors is 6, which is not prime.
      21 is semi-prime — the factors of 21 are 1, 3, 7, 21.  If we exclude 1 and 21, we are left with 3 and 7, both of which are Prime.
       (Hint: Anytime you multiply two Prime numbers, the result is always Semi Prime)
    • Modulos – This is a fancy way of simply asking for a remainder.  If presented with the problem 12 MOD 5, we simply are asking for the remainder when dividing 12 by 5, which results in 2.

    With that out of the way, we can get into the algorithm itself.

     

    RSA Key Generation

    The heart of Asymmetric Encryption lies in finding two mathematically linked values which can serve as our Public and Private keys.  As such, the bulk of the work lies in the generation of such keys.

    To acquire such keys, there are five steps:

    1. Select two Prime Numbers:  P and Q

    This really is as easy as it sounds.  Select two prime numbers to begin the key generation.  For the purpose of our example, we will use the numbers 7 and 19, and we will refer to them as P and Q.

    1. Calculate the Product: (P*Q)

    We then simply multiply our two prime numbers together to calculate the product:

    7 * 19 = 133

    We will refer to this number as N.  Bonus question: given the terminology we reviewed above, what kind of number is N?

    1. Calculate the Totient of N: (P-1)*(Q-1)

    There is a lot of clever math that goes into both defining and acquiring a Totient.  Most of which will be beyond the intended scope of this article.  So for now, we will simply accept that the formula to attain the Totient on a Semi Prime number is to calculate the product of one subtracted from each of its two prime factors. Or more simply stated, to calculate the Totient of a Semi-Prime number, calculate P-1 times Q-1.

    Applied to our example, we would calculate:

    (7-1)*(19-1) = 6 * 18 = 108

    We will refer to this as T moving forward.

    1. Select a Public Key

    The Public Key is a value which must match three requirements:

    • It must be Prime
    • It must be less than the Totient
    • It must NOT be a factor of the Totient

    Let us see if we can get by with the number 3:  3 is indeed Prime, 3 is indeed less than 108, but regrettably 3 is a factor of 108, so we can not use it.  Can you find another number that would work?  Here is a hint, there are multiple values that would satisfy all three requirements.

    For the sake of our example, we will select 29 as our Public Key, and we will refer to it as E going forward.

    1. Select a Private Key

    Finally, with what we have calculated so far, we can select our Private Key (which we will call D).The Private Key only has to match one requirement:  The Product of the Public Key and the Private Key when divided by the Totient, must result in a remainder of 1.  Or, to put it simply, the following formula must be true:

    (D*E) MOD T = 1

    There are a few values that would work for the Private Key as well.  But again, for the sake of our example, we will select 41.  To test it against our formula, we could calculate:

    (41*29) MOD 108

    We can use a calculator to validate the result is indeed 1. Which means 41 will work as our Private Key.

    And there you have it, we walked through each of these five steps and ended up with the following values:

    RSA Sample Values

    Now we simply pick a value to be used as our Plaintext message, and we can see if Asymmetric encryption really works the way they say it does.

    For our example, we will go ahead and use 99 as our Plaintext message.

    (the math gets pretty large at this point, if you are attempting to follow along, I suggest to use the Linux Bash Calculator utility)

    Message Encryption

    Using the keys we generated in the example above, we run through the Encryption process.  Recall, that with Asymmetric Encryption, we are encrypting with the Public Key, and decrypting with the Private Key.

    The formula to Encrypt with RSA keys is:  Cipher Text = M^E MOD N

    If we plug that into a calculator, we get:

    99^29 MOD 133 = 92

    The result of 92 is our Cipher Text.  This is the value that would get sent across the wire, which only the owner of the correlating Private Key would be able to decrypt and extract the original message.  Our key pair was 29 (public) and 41 (private).  So lets see if we really can extract the original message, using our Private Key:

    The formula to Decrypt with RSA keys is:  Original Message = M^D MOD N

    If we plug that into a calculator, we get:

    92^41 MOD 133 = 99

    As an experiment, go ahead and try plugging in the Public Key (29) into the Decryption formula and see if that gets you anything useful.  You’ll notice that, as was stated before, it is impossible to use the same key to both encrypt and decrypt.

    Message Signing

    But remember, that isn’t all we can do with a key pair.  We can also use same key pair in the opposite order in order to verify a message’s signature.

    To do this, we will use the same formulas as above, except this time we will revere the use of the Public and Private Key.  We’re going to encrypt with the Private Key and see if we can decrypt with the Public Key.

    We’ll use the same formula to encrypt, except this time we will use the Private Key:

    Signature = M^D MOD N

    If we plug that into a calculator, we get:

    99^41 MOD 133 = 36

    The result of 36 is the Signature of the message.  If we can use the correlating public key to decrypt this and extract the original message, then we know that only whoever had the original Private Key could have generated a signature of 36.

    Again, the same Decryption formula, except this time we will use the Public Key:

    Original Message = M^E MOD N

    If we plug that into a calculator, we get:

    36^29 MOD 133 = 99


     

    And there you have it.  A fully working example of RSA’s Key generation, Encryption, and Signing capabilities.

    It should be noted here that what you see above is what is regarded as “vanilla” RSA.  In production use of RSA encryption the numbers used are significantly larger. In fact, modern RSA best practice is to use a key size of 2048 bits.  This correlates to the N value in our calculation above.  The two primes used in modern RSA must result in a product that is 2048 bits.

    And just to give you an idea of how big 2048 bit number is. We saw earlier that a 128 bit number can be written in decimal with 39 digits. A 2048 bit key is exponentially longer – it would require approximately 617 digits to fully write out.


    Prefer video content to text? The majority of this article has been recorded and can be viewed on Youtube:

    Series NavigationAnti-Replay >>Diffie-Hellman Key Exchange >>
    4.9 7 votes
    Article Rating
    Subscribe
    Notify of

    10 Comments
    Oldest
    Newest Most Voted
    Inline Feedbacks
    View all comments

    Using rsa can’t we encrypt any text messege taking text as plain text. If yes then please help me with an example of encrypting any text(take “practicalnetworking” as example) with rsa. Thanking you

    you should to chinge it to binery

    Thank you for the clear explanation! Bringing it down to small numbers really helped to follow along.

    I love this. this is PRECISELY what I was looking for. sorry for posting on an old post.

    I have one question. In the example, how does the encryptor or decryptor know the value of “N” when they are decrypting or decrypting.

    At the time of encrypting I know:
    1) the message
    2) and the public Key

    which I can:

    M^E MOD ( unknown N? ) = cipher text?
    99^29 MOD? = 92

    This is the last piece of the puzzle for me ( in a long journey to understand how this works! )

    How the encryptor or decryptor knows the value of N:

    Encryption (using the public key):The value of N is included in the recipient’s public key, which is made public. Anyone who wants to send an encrypted message to the recipient can obtain the public key, including N, and use it to perform encryption.

    Decryption (using the private key):The recipient knows the value of N because it is a part of their private key. The private key is kept secret and is only known to the recipient. When someone sends an encrypted message, the recipient uses their private key, which includes N, to decrypt the message.In summary, the knowledge of N is distributed through the public and private key pairs, with N being included in the public key for encryption and in the private key for decryption.

    Last edited 10 months ago by MMG

    13 = m^23 mod 55
    please help me

    There are a few values that would work for the Private Key as well. But again, for the sake of our example, we will select 41

    So there is more private keys to one public key???

    Shouldn’t the formulas for decryption read “Original Message = C^D MOD N" and "Original Message = S^E MOD N" respectively?As they’re written in the article, you’re decrypting the original message instead of the cypher text.

    I have a public key (“E”) that also decrypts my cipher text. The numbers to generate E follow all the rules. This is what they are:

    P = 5 (must be prime number)
    Q = 7 (must be prime number)
    N = 35 = P*Q
    T = 24 = (P-1)*(Q-1)
    E = 11 (must be: 1. a prime number; 2. less than T; 3. not be a factor of T)

    If my original message is 10 (“M”), I encrypt it with the public key as follows:

    Cipher text = M^E MOD N
    = 10^11 MOD 35
    = 5

    Here’s the problem: I can decrypt this cipher text (“C”) with the public key as well:

    C^E MOD 35
    = 5^11 MOD 35
    = 10

    I have noticed that if I try a different value for the original message, then I cannot decrypt with the public key.

    e.g. if M = 59

    Cipher text (“C”) = 59^11 MOD 35
    = 19

    C^E MOD N
    = 19^11 MOD 35
    = 24 (not the original message, 59)