Don't like this style? Click here to change it! blue.css

Welcome .... Click here to logout

Class 17: RSA day

Overview: RSA is the most famous modern encryption scheme. It has a great brand. I want to take a moment and demonstrate that key lengths must be dealt with more carefully in the public-key world.

We've just set up El Gamal and Diffie-Hellman where we can see that the secrecy entirely depends on the difficulty of a general solution to the discrete log problem.

Our next public-encryption scheme is also the most famous, RSA. It's secrecy depends on the difficulty of integer factorization. It is easy to multiply two large numbers (can be done in \(\mathbb{O}(\log{n})\) time) but expensive to reconstruct those factors given just the product ( \( \mathbb{O}(n) \) time (actually a bit better than this)) (here \(n\) is the size of the numbers NOT the number of digits).

Now a linear-time algorithm sounds fast to me. But we're talking about giant numbers, loop through every number from 1 to \(10^{600}\) and it'll eat up some CPU time. But something like AES is a far more complex process to start unraveling than just finding a factor.

I wanted to say this just to demonstrate that the security factor (block-length in AES and log of the modulus in RSA/DH) must be significantly larger when deploying public-key crypto vs symmetric crypto. Just remember this: 128-bits of security for AES is equivalent to 3,248-bits of security in RSA/DH.

Overview: Let's set up the math that we need to really pull off the RSA encryption scheme.

The world's most popular public-key encryption scheme is the RSA algorithm (named after the three authors which means that the NSA probably calls it something else in-house).

The idea is the following:

Now to encrypt use the public key \((n,e)\) and secret message \(m\) the cipher text is: \(C := m^{e} \mod{n}\).

The decryption of \(C\) is just \(C^{d} \mod{n} \equiv m^{e \cdot d} \mod{n} \equiv m \mod{n} \). This is because the size of the cyclic subgroup is \( \Phi(n) \) and \(e \cdot d = 1 + \Phi(n) \cdot k\) for some \(k\).

Trench Generation: Generate an RSA key pair using the command ssh-keygen -t rsa (it will ask you questions, the first question is where to save it, pick something in your current folder like rsa_key ).

Read the keys: Now use the command openssl rsa -text -noout -in rsa_key to see the various parameters in the private key file. There are 8 numbers stored there: the modulus \(n\), the public exponent \(e\), the private exponent \(d\), \(p\), \(q\), \(d \mod{p-1}\), \(d \mod{q-1}\), and \(q^{-1} \mod{p}\). Those last three are there to make the exponentiation faster by computing mod p-1, q-1 and using chinese remainder theorem to reconstruct the plaintext.

Confirm: confirm that \(n = p \cdot q\), \(e \cdot d \equiv 1 \mod{(p-1)\cdot (q-1)}\), and that \(p\) and \(q\) are prime.

You can now see the hard problem that an attacker must solve: given \(n, e, C\) find \(d\) or \(m\). The reason this is a factoring problem is that knowing \( \Phi(n) \) is enough to take an inverse for \(e\). Knowing \(Phi(n)\) is equivalent to knowing \(p\) or \(q\) just given \(n\).


Here is the fastest way to consume an RSA PEM key that I found. I was able to import rsa directly but probably some of you will have to pip install rsa or something like that:

Overview: Finally we'll both encrypt with RSA and break it (when the problem is small enough). This helps you really understand all of the mechanics and begin to appreciate some subtlety that we'll explore in the next module.

In public key encryption anyone that wants to receive a message must publish a public-key. Anyone that wants to send that person a message uses it to encrypt a message. RSA is a bit different than DH in this sense because the sender of the message doesn't need to create a public/private key-pair in order to participate.

Mini-Bletchley Contest

Let's have a three stage contest. Form 4-person teams, team A, team B, team C, etc. . On each team we will have two message senders and two message crackers. SenderA1, SenderA2, CrackerA1, CrackerA2, SenderB1, etc.

For this competition we will have a three stage race.

Some details you'll want:

Some "Common" RSA Attacks

CTF Flag

Check this one out: ctf.tar.gz