2 minute refresher on RSA

RSA is a public key cryptosystem developed by Rivest, Shamir and Adleman in 1977. It is still the main primitive used by TLS (https), GPG, ssh, etc.

Public key crypto involves two keys: a public key and a private key. A user (Bob) publishes their public key and keeps the private key secure. Anyone can securely send messages to Bob by encrypting the contents using the public key. Only Bob who knows the private key can decrypt the messages.

RSA is based on the fact that it's easy to create and multiply two large prime numbers but it's hard to factorize the product. RSA also relies on modular exponentiation (a^e mod n) being a one-way function (given c ≡ a^e mod n, computing c is easy but finding a given c, e and n is hard).

The key generation algorithm boils down to:

1. choose two distinct prime numbers p and q. (Look up how this is actually done, it's interesting and has caused security flaws in the past).
2. compute n = p*q. The length of n (in bits) is going to be the key length.
3. compute φ = (p − 1)*(q − 1).
4. choose e, typically 3 or 65537.
5. compute d ≡ e^-1 mod φ (also look up how this is done).

• public key is the pair (n, e)
• private key is the pair (n, d)

Encryption is then performed using modular exponentiation. In this post, we ignore the fact that RSA encryption should always be combined with a secure encryption scheme (e.g. OAEP). Normally, you don't process plaintext with RSA but instead generate a fixed size random session key.

The RSA part of the encryption process boils down to:

• convert the message into a big integer.
• compute c ≡ m^e mod n

And decryption ends up being the same operation with a different exponent:

• c^d ≡ (m^e)^d ≡ m (mod n)

See Wikipedia's page on RSA for more info.

Cracking a weak RSA key

Let’s create a weak key and crack it. We’ll use openssl to create the key and encrypt a message. We’ll then use Ruby to factorize the public key and re-create the private key. Ruby makes handling bignums implicit (which is nice), but keep in mind that its handling of bignum is very slow (100 times slower than javascript and at least 3 orders of magnitude slower than native code).

Key generation

The first step is to create a weak key. We decided to go with a 64 bit RSA key because 64 bits ends up taking me a few minutes to break on my laptop. Feel free to try breaking larger keys, such as 128, 256 or 512 bit keys.

Notice how openssl doesn’t throw any warnings!

$ openssl genrsa 64 | tee small.pem
Generating RSA private key, 64 bit long modulus
....+++++++++++++++++++++++++++
...+++++++++++++++++++++++++++
e is 65537 (0x10001)
-----BEGIN RSA PRIVATE KEY-----
MD8CAQACCQDCX12/CM4MOQIDAQABAgh0j4YCTp0HdQIFAOq31rsCBQDT/wubAgUA
6YaGyQIEYIMgOQIFAM2FQT4=
-----END RSA PRIVATE KEY-----

To see what’s in the key, use openssl rsa -text:
$ openssl rsa -text -in small.pem
Private-Key: (64 bit)
modulus: 14006016441213389881 (0xc25f5dbf08ce0c39)
publicExponent: 65537 (0x10001)
privateExponent: 8399079174536234869 (0x748f86024e9d0775)
prime1: 3937916603 (0xeab7d6bb)
prime2: 3556707227 (0xd3ff0b9b)
exponent1: 3917907657 (0xe98686c9)
exponent2: 1619206201 (0x60832039)
coefficient: 3448062270 (0xcd85413e)
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MD8CAQACCQDCX12/CM4MOQIDAQABAgh0j4YCTp0HdQIFAOq31rsCBQDT/wubAgUA
6YaGyQIEYIMgOQIFAM2FQT4=
-----END RSA PRIVATE KEY-----

The key follows the following format:

    RSAPrivateKey ::= SEQUENCE {
        version           Version,
        modulus           INTEGER,  -- n
        publicExponent    INTEGER,  -- e
        privateExponent   INTEGER,  -- d
        prime1            INTEGER,  -- p
        prime2            INTEGER,  -- q
        exponent1         INTEGER,  -- d mod (p-1)
        exponent2         INTEGER,  -- d mod (q-1)
        coefficient       INTEGER,  -- (inverse of q) mod p
        otherPrimeInfos   OtherPrimeInfos OPTIONAL
    }

exponent1, exponent2 and coefficient are stored in the private key for optimizing purpose.

We want to throw away the private part of the key, so we extract the public key with -pubout:

$ openssl rsa -pubout -in small.pem | tee small_pub.pem; mv small_pub.pem small.pem
writing RSA key
-----BEGIN PUBLIC KEY-----
MCQwDQYJKoZIhvcNAQEBBQADEwAwEAIJAMJfXb8Izgw5AgMBAAE=
-----END PUBLIC KEY-----

Finally, let’s encrypt a message using the public key.

$ echo -n "new york" | openssl rsautl -encrypt -inkey small.pem -pubin -raw | base64 | tee cipher.txt
TKna/HwfcOI=

Factorization

To factorize small.pem, we simply iterate through all the numbers from 2 to the square root of n (we can stop at the square root r of n because if a number n is divisible by m with m>r, then n is also divisible by n/m and n/m<r).

As a micro optimization (makes the code run ~4x faster), we start by checking if n is divisible by 2, 3, 5 and we then go in chunks of 30 (30 comes from 2*3*5).

$ irb
> def factorize(n)
  if n%2==0 then return 2 end
  if n%3==0 then return 3 end
  if n%5==0 then return 5 end
  m = Math.sqrt(n)
  i=7
  while i<=m do
    if (n%i==0)      then return i end
    if (n%(i+4)==0)  then return i+4 end
    if (n%(i+6)==0)  then return i+6 end
    if (n%(i+10)==0) then return i+10 end
    if (n%(i+12)==0) then return i+12 end
    if (n%(i+16)==0) then return i+16 end
    if (n%(i+22)==0) then return i+22 end
    if (n%(i+24)==0) then return i+24 end
    i+=30
  end
end
> factorize(14006016441213389881)
> 3556707227

Re-creating the private key

Once we have factorized n, we can recreate the private key which allows us to decrypt cipher.txt.

> require 'openssl'
> require 'base64'
> a = OpenSSL::PKey::RSA::new
> a.e = 65537
> a.n = 14006016441213389881
> a.p = 3556707227
> a.q = a.n.to_i / a.p.to_i
> a.d = a.e.mod_inverse((a.p-1) * (a.q-1))
> a.dmp1 = a.d % (a.p-1)
> a.dmq1 = a.d % (a.q-1)
> a.iqmp = a.q.mod_inverse(a.p)
> File.write('small.pem', a)

$ cat cipher.txt| base64 -D | openssl rsautl -decrypt -inkey small.pem -raw
new york

Thankfully, keys are typically 2048 bits or longer, making this attack infeasible.

Cracking a weak RSA message

Encrypting a message involves computing m^e mod n. If e is a small value (e.g. 3) and m^e is less than n, the modulo does not do anything.

The original message is revealed by computing the eth root.

Message generation

$ openssl genrsa -3 128 | tee private.pem
Generating RSA private key, 128 bit long modulus
...+++++++++++++++++++++++++++
....+++++++++++++++++++++++++++
e is 3 (0x3)
-----BEGIN RSA PRIVATE KEY-----
MGECAQACEQCy/aCKGshlpPi2TFvQHvQDAgEDAhB3U8BcEdrubN1k06S5LCdLAgkA
4Kz0hhYYddkCCQDL8hpepERDOwIJAJXIowQOuvk7AgkAh/a8PxgtgicCCGHoV8yc
zeW8
-----END RSA PRIVATE KEY-----
$ echo -en "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00hello" | openssl rsautl -encrypt -inkey private.pem -raw  | base64
ABFcaHeP6CvK2nvQ2hKiTw==

Computing the nth root

We compute the nth root using Newton’s method. The code was easily found by Googling around.

$ irb
> require 'base64'
> def nthroot(n, a, precision = 1e-1024)
  x = a
  begin
    prev = x
    x = ((n - 1) * prev + a / (prev ** (n - 1))) / n
  end while (prev - x).abs > precision
 x
end
> a = Base64.decode64("ABFcaHeP6CvK2nvQ2hKiTw==")
> a = a.unpack('H*')[0].to_i(16)
> r = nthroot(3, a)
> puts [r.to_s(16)].pack('H*')
> hello

Notice how openssl doesn’t print any warnings.

In the case where we don't know the exponent's value, we can try a few different options.

When using RSA with random session keys, this case is unlikely to occur.

Same RSA message encrypted multiple times

If a message is encrypted e times, we can use the Chinese Remainder Theorem (see this post) to decrypt the ciphertext.

The theorem says that given:

• m^e mod A
• m^e mod B
• m^e mod C
• ...

It is possible to compute m^e (mod A*B*C*...).

This means we can convert three identical messages encrypted to three recipients into the weak message case above. This is possible because the message is going to be smaller than the product A*B*C.

$ openssl genrsa -3 128 | tee key1.pem
Generating RSA private key, 128 bit long modulus
..+++++++++++++++++++++++++++
.+++++++++++++++++++++++++++
e is 3 (0x3)
-----BEGIN RSA PRIVATE KEY-----
MGICAQACEQDSqVXh6LYTArm4OiIDupGVAgEDAhEAjHDj6/B5YgCbaxSUePbjKwIJ
AO33P5tsUQuxAgkA4qBbp+H3MSUCCQCepNUSSDYHywIJAJcVkm/r+iDDAggJ6hBR
5pRslA==
-----END RSA PRIVATE KEY-----
$ openssl genrsa -3 128 | tee key2.pem
Generating RSA private key, 128 bit long modulus
...+++++++++++++++++++++++++++
....+++++++++++++++++++++++++++
e is 3 (0x3)
-----BEGIN RSA PRIVATE KEY-----
MGICAQACEQDEtWSUEvnIiKUrAb9BqE7bAgEDAhEAgyOYYrdRMFnrimfrJUiquwIJ
APwgNlor+6pVAgkAx7svhF2/pG8CCQCoFXmRcqfG4wIJAIUndQLpKm2fAghyf0MX
IZWaZw==
-----END RSA PRIVATE KEY-----
$ openssl genrsa -3 128 | tee key3.pem
Generating RSA private key, 128 bit long modulus
.+++++++++++++++++++++++++++
.....+++++++++++++++++++++++++++
e is 3 (0x3)
-----BEGIN RSA PRIVATE KEY-----
MGICAQACEQDQOJ3STkxOKGWNp/GTCwS/AgEDAhEAitBpNt7diW8Phgt4Dlvp+wIJ
APICm09QDGXtAgkA3EH7bi10v9sCCQChVxI04AhD8wIJAJLWp57I+H/nAggXDoxS
56i64g==
-----END RSA PRIVATE KEY-----

$ echo -en 'hello world !!!!' | openssl rsautl -encrypt -inkey key1.pem -raw  | base64
pAvH0C8oeAF0PUX4ntQOJw==
$ echo -en 'hello world !!!!' | openssl rsautl -encrypt -inkey key2.pem -raw  | base64
p+XoMuN1JKzZI2L/EDF2xQ==
$ echo -en 'hello world !!!!' | openssl rsautl -encrypt -inkey key3.pem -raw  | base64
a+GgTrVXCGWWL9JO7CPhxA==

$ irb
> require 'base64'
> def nthroot(n, a, precision = 1e-1024)
  x = a
  begin
    prev = x
    x = ((n - 1) * prev + a / (prev ** (n - 1))) / n
  end while (prev - x).abs > precision
 x
end
> def extended_gcd(a, b)
  last_remainder, remainder = a.abs, b.abs
  x, last_x, y, last_y = 0, 1, 1, 0
  while remainder != 0
    last_remainder, (quotient, remainder) = remainder, last_remainder.divmod(remainder)
    x, last_x = last_x - quotient*x, x
    y, last_y = last_y - quotient*y, y
  end
  return last_remainder, last_x * (a < 0 ? -1 : 1)
end
> def invmod(e, et)
  g, x = extended_gcd(e, et)
  if g != 1
    raise 'Multiplicative inverse modulo does not exist!'
  end
  x % et
end
> def chinese_remainder(mods, remainders)
  max = mods.inject( :* )  # product of all moduli
  series = remainders.zip(mods).map{ |r,m| (r * max * invmod(max/m, m) / m) }
  series.inject( :+ ) % max
end
> n1 = '00d2a955e1e8b61302b9b83a2203ba9195'.to_i(16)
> c1 = Base64.decode64('pAvH0C8oeAF0PUX4ntQOJw==').unpack('H*')[0].to_i(16)
> n2 = '00c4b5649412f9c888a52b01bf41a84edb'.to_i(16)
> c2 = Base64.decode64('p+XoMuN1JKzZI2L/EDF2xQ==').unpack('H*')[0].to_i(16)
> n3 = '00d0389dd24e4c4e28658da7f1930b04bf'.to_i(16)
> c3 = Base64.decode64('a+GgTrVXCGWWL9JO7CPhxA==').unpack('H*')[0].to_i(16)
> crt = chinese_remainder([n1, n2, n3], [c1, c2, c3])
> r = nthroot(3, crt)
> puts [r.to_s(16)].pack('H*')
hello world !!!!

This is why RSA needs a randomized padding scheme.