Let’s talk about your standard intro to cryptography course. For me this was CSE 5351 at OSU. It was a CSE major elective that I found a necessity. Like most intro to crypto courses, topics such as perfect-secrecy, block modes, signatures, MACs, and other essentials of crypto were discussed. Unfortunately, when there’s such a large amount of fundamentals, there’s little room for more than a mention of current events in cryptography. One thing that generally is discussed, is the public key or assymetric encryption scheme, RSA. RSA is one of the most popular public key encryption schemes in use today. So let’s go over the basics, in a simplified RSA crash course.

RSA - how it works

RSA has a public key, (publicExponent, modulus), that is visible to everybody and a private key, (privateExponent, modulus), that is visible only to the owner. Let’s take a look at how a key pair is generated:

  1. Choose two large primes, prime1 and prime2
  2. Find the product, prime1*prime2, which becomes the modulus
  3. Find the temp value, t, that is the least common multiple of (prime1-1) and (prime2-1).
  4. Choose publicExponent, such that it is less than t, and the greatest commond divisor between it and t is 1 (i.e. it is co-prime with t)
  5. Find the privateExponent as the modular multiplicative inverse of e, given modulo t (i.e. d*e mod t is 1)

Below we have three RSA keys. The first is a 512-bit RSA key generated by OpenSSL. While 512-bits is the weakest RSA key you can generate with OpenSSL, the numbers are a bit lofty, where only the public exponent can conveniently be expressed in decimal, 65537. As such, we have a readable in decimal-format 16-bit key. Finally we have a ridiculously small 6-bit key that we will work with in this blog post for easy calculations.

Private-Key: (512 bit)
modulus:
    00:d5:68:5f:05:e8:91:1e:c5:4f:0e:2a:2a:62:72:
    01:27:76:c3:e5:07:44:5e:41:53:14:0c:ee:f4:8e:
    7b:98:8f:6b:a9:bc:c9:ab:b8:5c:05:e9:44:d2:e4:
    92:b5:94:93:8f:92:c9:57:e4:44:25:8f:bd:d7:c6:
    55:15:04:7b:cd
publicExponent: 65537 (0x10001)
privateExponent:
    00:a4:f8:67:ec:83:5a:1b:b5:5f:65:8d:c6:f2:0f:
    3b:41:2c:98:46:a6:15:7d:df:75:bf:9c:37:e4:a9:
    78:75:f7:8e:4e:82:7c:cd:b4:1a:27:9a:c1:e0:36:
    cb:af:b3:be:fb:4a:ea:1a:3a:95:47:2e:c8:6c:56:
    14:a7:99:9f:81
prime1:
    00:fc:4d:bf:8e:a0:a7:f8:4e:60:c3:0d:a0:1d:c4:
    c1:2f:01:57:ea:5d:fe:0b:4f:33:65:8f:93:50:82:
    fe:e6:5d
prime2:
    00:d8:88:be:d9:3c:08:b8:39:f5:8b:96:c1:5c:18:
    e1:24:d4:ae:46:d4:ed:68:f6:d7:7b:0f:d8:38:03:
    35:b4:31
/* The exponents and coefficient below are for
 * making calculations faster. Let's ignore
 * these
 */
exponent1:
    00:f5:85:37:36:b5:52:1f:89:2e:12:41:cd:21:8a:
    d9:2f:43:d0:68:ca:64:b0:5e:b7:36:4a:bc:61:69:
    c8:61:25
exponent2:
    2d:12:b9:f7:6a:41:be:67:82:2f:5e:60:3d:95:88:
    38:2c:75:62:95:2c:1e:2f:53:c7:70:12:e8:05:f3:
    05:e1
coefficient:
    00:b0:2d:bb:2f:45:4b:08:9b:82:0f:6c:0d:78:12:
    89:e6:3f:d6:8c:ac:67:f2:e8:e2:f2:98:ac:65:c9:
    72:16:13
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MIIBPAIBAAJBANVoXwXokR7FTw4qKmJyASd2w+UHRF5BUxQM7vSOe5iPa6m8yau4
XAXpRNLkkrWUk4+SyVfkRCWPvdfGVRUEe80CAwEAAQJBAKT4Z+yDWhu1X2WNxvIP
O0EsmEamFX3fdb+cN+SpeHX3jk6CfM20GieaweA2y6+zvvtK6ho6lUcuyGxWFKeZ
n4ECIQD8Tb+OoKf4TmDDDaAdxMEvAVfqXf4LTzNlj5NQgv7mXQIhANiIvtk8CLg5
9YuWwVwY4STUrkbU7Wj213sP2DgDNbQxAiEA9YU3NrVSH4kuEkHNIYrZL0PQaMpk
sF63Nkq8YWnIYSUCIC0SufdqQb5ngi9eYD2ViDgsdWKVLB4vU8dwEugF8wXhAiEA
sC27L0VLCJuCD2wNeBKJ5j/WjKxn8uji8pisZclyFhM=
-----END RSA PRIVATE KEY-----

Private-Key: (16 bit)
modulus:
    43027
publicExponent: 17 (0x11)
privateExponent: 14873 (0x3A19)
prime1: 173
prime2: 211 

Private-Key: (6 bit)
modulus:
    55
publicExponent: 3
privateExponent: 7
prime1: 5
prime2: 11

So how would we use this to encrypt a message? Well, we won’t go into detail of how a message is turned into a number that can be encrypted. If you want to know more about this, then you can take some time to rersearch padding schemes such as PKCS#1. We won’t look at an actual message being encrypted, but to understand the principle, let’s encrypt the value 3 with the private key and decrypt the encrypted value with the public key, and vice-versa.

Attacking RSA

So, now that we have a crash course into how RSA works, how do we figure out the whole keypair with just the public key, (publicExponent, modulus). The obvious attack is trying to factor the modulus, and run through the key generation steps, already knowing the publicExponent from step 4. Let’s take a second though and talk about the publicExponent.

You might ask if the publicExponent can be the starting point of the attack. publicExponent means nothing without the modulus, or more specifically the two primes which are used to find (prime1-1)*(prime2-1) or our temp value which helps to decide the privateExponent. In fact, the value 65537 is the standard publicExponent. Most implementations of RSA are optimized to work with this value.

Back to attacking RSA. The only way to directly attack it is to figure out the two prime factors of the modulus. Unfortunately this isn’t an easy thing to do, and in fact there is no polynomial solution to integer factorization… on standard computers. There is a quantum attack called Shor’s algorithm that can do integer factorization in polynomial time. This isn’t a problem currently as the largest value factored with Shor’s algorithm is 21 in 2012. A different quantum algorithm though has factored 56153, and as quantum computers become more advanced, RSA will become unviable for encryption.

Quantum computers and modern cryptography

RSA isn’t the only encryption scheme susceptible to quantum attacks. There are three principles that are used in a large number of modern encryption schemes: integer factorization, discrete logarithms, and elliptical curve discrete logarithms. All three of these problems can be solved with Shor’s algorithm. So as the age of modern cryptography comes to an end, you might start to ask what comes next? The obvious answer you’ll find when you google it will be “quantum cryptography”. Quantum cryptography requires quantum computers to work. Normal users won’t have quantum computers for a long time. So, what happens in the interim when only state-level actors and big corporations have quantum computers? Is there no way to protect our data?

The answer to this is simple and confusing. The name for algorithms that can be used by normal computers, but that are secure against quantum attackers is “post-quantum cryptography”. This is because it protects against quantum attackers as compared to modern cryptographic or as it is sometimes termed “pre-quantum” cryptography. Additionally quantum cryptography isn’t based on strong mathematics, but quantum physics. Algorithms and schemes are the weapons of pre and post quantum cryptography, whereas physics rules the area inbetween. The basis for the post-quantum encryption schemes currently are lattice-based, code-based, multivariate, hash-based, supersingular elliptic curve isogeny (I have no idea what this one means), and using a symmetric key that is quantum resistant based on both size and algorithm.

Some older pre-quantum schemes are in fact still secure against quantum attackers (e.g. AES). The only thing that needs to change, is the notion of how strong is strong enough. This has been changing with Moore’s Law, but quantum computers will lead to an essential change in how big a key needs to be. Wikipedia has a table containing the bit-size needed to equal a 128-bit post-quantum security level. This difference becomes especially apparent when you consider how Grover’s algorithm can be used against symmetric cryptographic keys such as AES to brute force a key much faster than is currently possible.

I’m still learning about post-quantum crypto schemes myself, but I figured I’d end this with a brief listing of SOME schemes in modern cryptography, post-quantum cryptography, and quantum cryptography. If you’d like to look into post-quantum crypto, check out the Open Quantum Safe project.

Modern cryptography

These schemes use modern computers and provide protection against modern attackers. MOST do not provide protection against quantum computers, but have been proven to be reasonably safe to this point.

Algorithm Type base problem
RSA public key scheme integer factorization
ElGamal public key scheme discrete logarithms
DSA public key scheme discrete logarithms
ECDSA public key scheme elliptical curves
DHE public key exchange ??
ECDHE public key exchange elliptical curves
AES symmetric encryption ??

Post-Quantum Cryptography

These schemes use modern computers and provide protection against both modern and quantum attackers. They don’t have the same amount of time to have been attacked as heavily as modern cryptography schemes, and as such have less confidence from the cryptographic community.

Algorithm Type base problem
NTRU public key scheme lattice-based
McEliece(1978) public key scheme code-based
SIDH public key exchange supersingular elliptic curve isogeny
AES symmetric encryption ??

Quantum Cryptography

Using quantum computers to deal with cryptography. Still a long time out from popular use, and will have time to be proven against attacks by the time quantum computers become an everyday thing. The methods in this category are less of mathematical schemes, and more of a reliance on quantum physics. If Eve intercepts a communication between Alice and Bob, the fact is quite clear as the communication between Alice and Bob will come out garbled from its intended state.