RSA Explained

23 mins

This page is based on an email I had with a teacher

I had missed a question on a test where the test was incorrect and I wrote the email to get the point back. Surprisingly it worked.

I've shared the email enough that I figured it would be better to just make a post about it.

The Basics

RSA is conceptually simple. There are two keys, a public and a private key. The public key can be given out freely but the private key should be protected and never given out to anyone.

Say Alice wants to talk to Bob but they are communicating over a monitored line, meaning anything they send will be received by a third party. If they don't want to have that third party knowing what they are saying they can send each other their public key over that monitored line.

After they send their public keys over that line they can then encrypt their messages using the other's public key. So for example if Alice wants to send a message to Bob she would encrypt the message using Bob's public key and send it over the monitored line. Bob would then decrypt the message using his private key.

The third party would only be able to see that encrypted message and assuming Alice and Bob are using good encryption with a large enough key length the third party wouldn't be able to decrypt the message with only the public key.

RSA Algorithm

There are three parts of the algorithm: key generation, encryption, and decryption.

The easy part is encryption and decryption so we'll start with that.

The encryption algorithm is:

c is the resulting ciphertext
≡ basically means its equal (this is a simplification but it's ok for now)
m is the padded plaintext message (padding is just adding some extra bits for a couple different reasons, padding could be its own page so I won't get too deep into it)
e is the public key exponent of the person you're sending the message to
n is the product of that person's two prime factors, this is sent with the public key

So to put it together the ciphertext is calculated using the message to the power of the public key of the person you're sending it to then modulo that by the product of that person's two prime numbers.

The decryption algorithm is:

This looks complicated but it's basically just ciphertext to the power of the private key exponent. The rest of that algorithm is just showing work.

Now for the comparatively complicated part: Key Generation.

The first thing that needs to be generated are two large prime numbers, these are known as p and q.
From there you generate n which is n = pq. This is your key length.
You need to compute lambda(n) where "lambda" is Carmichael's totient function. This is expressed as lambda(n) = lcm(p - 1, q - 1)
Then we need to choose an integer e where 2 < e < lambda(n) AND gcd(e, lambda(n)) = 1. Essentially we need to make sure "e" and "lambda(n)" are coprime. This is your public key exponent.
Finally we need to calculate d where d ≡ e⁻¹(mod lambda(n)) or for the math nerds, "d" needs to be the modular multiplicative inverse of "e modulo lambda(n)" This is your private key exponent.

Putting it into practice

OpenSSL Baseline

Man that's a lot of math talk, if you're anything like me you need examples. Before we get into the nitty-gritty with python lets get a baseline with the standard Openssl tool.

First lets generate the private key with a key length of 2048: openssl genrsa 2048. This will output the key to stdout to put this in a file you can either use shell redirects or the -out flag.

Here is the key I generated. (Please note this key was generated for the purposes of explanation. I don't use this key and you shouldn't either.)

To find what numbers were used in this keys generation you can run openssl rsa -in private.pem -text -noout. This will give all the numbers used to generate both private and public keys in hex. To convert this to decimal we can do some bashfu. The modulus is the easy part because there is a -modulus flag we can use to output the modulus in hex without anything else or any colons: openssl rsa -in private.pem -modulus -noout | sed -e 's/Modulus=/ibase=16; /' | bc

Original Modulus output: Modulus=C9BF0AFE1A15A83A8CD68D12C11CB6A944EBF38D62A33F84B179052E875F1F57441A85F932BBB67EB03A59ABC93D35E9DB5B69476BFBAD9F7F13704C1FBB9CE2BE5B0F065653DAA8B21A25858AA2B7225BCE31F81216E71DCF410ADA5A838B6E60DE49DA632A68D0BB9BC1D0D63CEB27AAAB8DCE7193E772CCF93CA6E0387948381A2786BD42397AB15B247C2FDBB050C6B0BBDBD2ADE1803064BE845382738B2BF2232DEB2EFE56077A4A00CDC693D0F65DC6DAC002F2EEC455D23B53D5162103F7FD43AE02D98FC41DF288DE060AF5AAE669337C7B8A01EFEC70FDE9BFCE3B36798307E697041D9289291F601C14F336C0B7888D2F312ABCBEE7163B88C9CF
Bashfu oneliner output: 25468106082921794971929409506903775758728045423753973170996959875345803013722474541045565883815682177434955104383906639041388567454940137687663026589323306165475698385730572512046618474721376990576162384898600637901272248576695044354175677353663993053604053214742119796047637103645642070127143302862228807476663080956490039342214965817463705457380197342311783922066124952133161913392372304617410084643208670689823597752814889511157649686062558985502814811733665601943693667553357863982055267040184966104535775272478573916097964350996183228704435845314131797767367898143161396024687771146955440326737475094160322644431

e is already in decimal. To get it we can run: openssl rsa -in private.pem -text -noout | grep publicExponent | cut -d' ' -f2 The output of which would be: 65537 This is actually the most common value for e, some implementations even hardcode this value for e.

It's much more complicated to get the rest of the numbers into decimal. You have to use this arcane tomfoolery. openssl rsa -in private.pem -text -noout | awk '/prime1/{f=1;next} /prime2/{f=0} f' | sed -z 's/\n//g' | tr '[:lower:]' '[:upper:]' | sed -e 's/ /ibase=16; /' | sed -e 's/ //g' | sed -e 's/://g' | echo $(</dev/stdin) | bc If I knew more awk this oneliner would probably be shorter. Honestly if your oneliner is this long you should look into making a script.

Here is what this oneliner is doing:

openssl rsa -in private.pem -text -noout This prints out all the numbers we need in a way that needs a lot of post processing.
awk '/prime1/{f=1;next} /prime2/{f=0} f' cuts out and prints only what is inbetween the strings "exponent1" and "exponent2", this is our hex that we have to process a bit more.
sed -z 's/\n//g' This removes all the break lines.
tr '[:lower:]' '[:upper:]' This converts all the lowercase characters to uppercase, this is important because bc requires hex to be uppercase.
sed -e 's/ /ibase=16; /' This replaces the first soft-tab (four spaces) with the string "ibase=16; " (that space is important). This is to tell bc what the incoming number's base is.
sed -e 's/ //g' This removes the rest of the soft-tabs.
sed -e 's/://g' This removes all of the colons.
echo $(</dev/stdin) This takes everything its given and echos it back. The reason for this is because bc requires the file its given to be breakline terminated and when we removed all the breaklines we made it NULL byte terminated and echo will automatically breakline terminate what it's given.
bc This is a calculator it takes the string we gave it and since we told it the input is base16 and didn't tell it to do anything else it will just output it in it's default base which just happens to be base10.

Here is the output, this would be p in the algorithm: 155914412676434675314820481330982951827486100759784364030252893898688913090630372157763542261719781624233993313959510526992259203526385534804748738559933412515374992441436966925006082075153066647463756075095883082749743200243171265715537247653604857193825438674261300552713707139224336927994866325867294412357

To get q we simply change the awk command to be awk '/prime2/{f=1;next} /exponent1/{f=0} f'. The output of which would be: 163346708272410490172882278503333820513575790750437110978123060377446751068976433661783430090185519420190349809551840135224191547707060554245081804237066395852443481289521744551767634302275175142839715462228814818980848446348299322499179342179183207006986673200678816332938667830000104560034958148053831668483

To get d we change the awk command to be awk '/privateExponent/{f=1;next} /prime1/{f=0} f'. The output of which would be: 1405395511678695569159142308645765064489372053572886216532805978137358997194368512102953888930213689895685111234942068756476215789566062040487561769081400380661959857973276400961542269463507024832059619222512309183666495063515535161921911853602176341278347474725954441649850917578382662413824461827688946430843606274855955090103821457312917652310054371695742108881766776794023764138582730768916367023231131060661708719759467907398810533710873045608163596267901366288770505797621290798104135495549989982489603223494880641560639079992670449735738127888799908638531653890764335505230961293265852225463268359370966848837

Python

Since RSA requires you to bring your own p and q I'm just going to use the values generated from OpenSSL.

 #!/bin/env python3

# Supply "p" and "q"
p =
q =

# Calculating "n"
n = p*q

# To calculate lambda(n) we can use the extended euclidean algorithm
# This is a recursive implementation
# return (g, x, y) such that a*x + b*y = g = gcd(a, b)
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    g, y, x = egcd(b%a,a)
    return (g, x - (b//a) *y, y)

# Takes the absolute value of p-1 times q-1 and floor divides it 
# (to make sure it's an int) by the greatest common denominator 
# between the two.  
# The slice function at the end makes this function a regular gcd 
# instead of an extended gcd.
lambda_n = abs(p-1*q-1)//egcd(p-1,q-1)[0]

# Now we need "e", I'm going to use 65537 since it's the most common
# To run a sanity check we can make sure the gcm of "e" and "lambda_n" is 1
e = 65537
if egcd(e, lambda_n)[0] == 1:
    print("Valid int for 'e'")

# Finally to get 'd' we need to calculate the modular inverse
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('No modular inverse')
    return x%m
    
d = modinv(e, lambda_n)

# From here we can construct a key
# I'm going to be using a library to build the key using the numbers generated
# this library is part of the 'pycrypto' package, it basically handles formatting
from Crypto.PublicKey import RSA as rsa
key = rsa.construct((n, e, d, p, q))
print(key.exportKey().decode("utf-8"))

My output is :

Fun Stuff

This section is mainly what the email was about

If you remember back to the beginning of this writeup I stated that as long as Alice and Bob used a long enough key their messages couldn't be decoded with only the public key. But what if they weren't using a long enough key? How would you generate a private key from a public key?

To start I generated a new 64bit key using a patched version of OpenSSL to remove the minimum key length requirements.

-----BEGIN PUBLIC KEY----- MCQwDQYJKoZIhvcNAQEBBQADEwAwEAIJAKMLz3XANvA3AgMBAAE= -----END PUBLIC KEY-----

It's values are:

n: 11748712157569019959
e: 65537

The public key gives us n and e. That leaves p, q, and d for us to solve.

To get p we need to factorize n since both p and q are prime. Then to get q all we need to do is divide n by p.

 #!/bin/env python3
from math import sqrt

# This isn't the most efficient way of doing things but it's fairly readable
# First it tests the low hanging fruit
def factorize(n):
        if n%2 == 0:
                return 2
        if n%3 == 0:
                return 3
        if n%5 == 0:
                return 5

# Then it takes the squareroot of "n" and sees if it can be modded by "i"
# It moves in chunks of 30 until it finds a factor
        m = sqrt(n)
        i = 7

        while i <= m:
                if n%i == 0:
                        return i
                if n%(i+4) == 0:
                        return i+4
                if n%(i+6) == 0:
                        return i+6
                if n%(i+10) == 0:
                        return i+10
                if n%(i+12) == 0:
                        return i+12
                if n%(i+16) == 0:
                        return i+16
                if n%(i+22) == 0:
                        return i+22
                if n%(i+24) == 0:
                        return i+24
                i+=30
                
print(factorize(11748712157569019959))

This gives me: p = 3221634953 and took about 2 minutes.

Plugging these numbers into the key generation script from earlier:

 #!/bin/env python3
# Almost verbatim the script I made originally for generating keys
from Crypto.PublicKey import RSA as rsa

n = 11748712157569019959
e = 65537
p = 3221634953
q = n//p

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    g, y, x = egcd(b%a,a)
    return (g, x - (b//a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('No modular inverse')
    return x%m

d = modinv(e, (p-1)*(q-1))
print("d = {0}".format(d))

key = rsa.construct((n, e, d, p, q))
print(key.exportKey().decode("utf-8"))

And we get: d = 699863775216061441 and the full key:

-----BEGIN RSA PRIVATE KEY----- MD8CAQACCQCjC891wDbwNwIDAQABAggJtmplQOrMAQIFAMAGP4kCBQDZXgG/AgUA k6b6SQIEcei5sQIFALlribw= -----END RSA PRIVATE KEY-----

Now to test to make sure this key works. Say Alice sends "Hi World" (NULL terminated) using the weak public key. openssl pkeyutl -encrypt -inkey weak_key.pub -pubin -pkeyopt rsa_padding_mode:none -in plain.txt -out cipher.txt

Since Bob sent his public key over the line we are monitoring we have a copy of that key and we just generated a private key from it. Testing to see if it works: openssl pkeyutl -decrypt -inkey cracked_key.pem -pkeyopt rsa_padding_mode:none -in cipher.txt -out clear.txt

We now have a file called "clear.txt" that shows "Hi World" (Null terminated of course).

Updated:

Created: 2023-07-14