Home Page
Archive > Posts > Tags > RSA
Search:

The math behind the RSA encryption algorithm

I’ve always thought that the RSA and Diffie–Hellman public key encryption algorithm systems are beautiful in their complex simplicity. While there are countless articles out there explaining how to implement them, I have never really found one that I think describes the math behind then in a simple way, so I thought I’d give a crack at it.

Both algorithms are derived from 3 math axioms:
  1. This is called Modular exponentiation (hereby referred to as modexp). In the following, x is a prime numbers and p is an integer less than x.
    1. p^(x  ) mod x = p (e.x. 12^(17  ) mod 17 = 12)
    2. p^(x-1) mod x = 1 (e.x. 12^(17-1) mod 17 = 1 )
  2. A further derivation from the above formulas shows that we can combine primes and they work in the same manner. In the following, x and y are prime numbers and p is an integer less than x*y.
    1. p^((x-1)*(y-1)  ) mod (x*y) = 1 (e.x. 12^((13-1)*(17-1)  ) mod (13*17) = 1 )
      Note: This formula is not used in RSA but it helps demonstrate how the formulas from part 1 becomes formula 2b.
      Due to how modexp works with primes, values of p that are multiples of x or y do not work with 2a.
    2. p^((x-1)*(y-1)+1) mod (x*y) = p (e.x. 12^((13-1)*(17-1)+1) mod (13*17) = 12)
  3. The final axiom is how modexp can be split apart the same way as in algebra where (x^a)^b === x^(a*b). For any integers p, x, y, and m:
    (p^(x*y) mod m) === ((p^x mod m)^y mod m)

With these 3 axioms we have everything we need to explain how RSA works. To execute an RSA exchange, encrypted from Bob and decrypted by Alice, the following things are needed.

The variable Variable name Who has it Who uses it Description
Prime Numbers 1 and 2 Prime1, Prime2 Alice Alice Alice will use these to derive variables PubKey, PrivKey, and Modulo. In our examples we use small numbers, but in reality, very large primes will be used, generally of at least 256 bit size.
Public key PubKey Alice, Bob Bob Alice sends this to Bob so he can encrypt data to her. Bob uses it as an exponent in a modexp.
Private key PrivKey Alice Alice Alice uses this to decrypt what Bob sends her. Alice uses it as an exponent in a modexp.
Modulo Modulo Bob, Alice Bob, Alice Alice sends this to Bob. They both use it as a modulo in a modexp
Payload Data Payload The data bob starts with and turns into EncryptedPayload. Alice derives Payload back from EncryptedPayload

Now, let’s start with axiom 2b:
Payload^((Prime1-1)*(Prime2-1)+1) mod (Prime1*Prime2) = Payload

Let’s change this up so the exponent is just 2 multiplications so we can use axiom 3 on it. We need to find 2 integers to become PubKey and PrivKey such that:
PubKey*PrivKey=(Prime1-1)*(Prime2-1)+1

And Modulo is Prime1*Prime2.
So we now have:
Payload^(PubKey*PrivKey) mod Modulo = Payload

Now, using axiom 3, we can turn it into this:
(Payload^PubKey mod Modulo)^PrivKey mod Modulo = Payload

Now, we can split this up into:
Bob calculates and sends to Alice: Payload^PubKey mod Modulo=EncryptedPayload
Alice uses the received EncryptedPayload and performs: EncryptedPayload^PrivKey mod Modulo = Payload

And the process is complete!


However, there is 1 caveat that I didn’t cover which makes the encryption that what we currently have weak. The calculation of PubKey and PrivKey from Prime1 and Prime2 needs to follow some rather specific complex rules to make the keys strong. Without this, an attacker may be able to figure out Prime1 and Prime2 from the Modulo and PubKey, and could then easily derive PrivKey from it. I generally see the PubKey as 65535, or another power of 2 minus 1.


OpenSSH RSA Authentication public key file format
Curiosity as always

There are two primary authentication methods for logging onto an SSH server as a user. The first is password based authentication, and the second is public key authentication. The public/private RSA key pair for public key authentication can be created using OpenSSH’s “ssh-keygen” application.

I’m not going to go into the exact method on accomplishing this because instructions can be found on countless other places on the internet. However, I was curious yesterday as to what exactly was in the public key (.pub) files created by ssh-keygen, as the data payload was larger than I expected (2232 bits for a 2048 bit key). I couldn’t find documentation on this ANYWHERE on the internet, so I downloaded the OpenSSH source code and looked at the generation code of the files. The format of the files is as follows:

  • The public key files are ASCII based text files with each public key taking up exactly one line.
  • Each line is formatted with 2 pieces of data as follows:
    KEY_TYPE DATA_PAYLOAD
  • KEY_TYPE is the type of public key, which in our case (and most cases nowadays) is “ssh-rsa”.
  • DATA_PAYLOAD contains the actual public key information encoded in base64 with the following format:
TypeByte lengthNameDescriptionDefault Value
unsigned int4KEY_TYPE_LENGTHLength of the next entry7
StringSee previousKEY_TYPESee abovessh-rsa
unsigned int4E_LENGTHLength of the next entry3
BigIntSee previousethis is the public key exponent in RSA65537
unsigned int4N_LENGTHLength of the next entryKEY_BIT_SIZE/8 (optional +1)
BigIntSee previousnthis is the “modulus for both the public and private keys” in RSAKey dependent

I also checked putty public key authentication files and they seemed to contain the exact same DATA_PAYLOAD.