Cryptography 101: Keep Your Hands off my Private Keys

You know that thing; you did in math class; when you were a kid; when you would took a number and broke it down into its prime factors? Example:

6 = 3 * 2
12 = 3 * 2 * 2
15 = 5 * 3

That’s called prime factorization and our whole society operates on the idea that it is hard; yet this theory hasn’t been proven. In theory it is possible that an algorithm exists for quickly calculating the prime factor of a large number. If someone were to discover that algorithm they would be able to decrypt all data. Credit card numbers would be stolen. Presidential communications would be tapped. Nothing stored on a computer would be a secret. We would be forced into a technological dark age.

Good thing mathematicians have been trying for centuries to find the prime factorization of a number to no prevail. For now the best method we have is no more complicated than just trying to divide a value by every number half its size.

Cryptography is a fascinated topic. It’s one of those rare subjects that is as profoundly boring as it is important. Our society depends on sending cryptographic messages every day. About half of all web traffic is encrypted and with about 2 billion smart phone users it’s safe to say cryptography is everywhere. Each time you Google “how many ounces in a cup,” for the umpteenth time, cryptography is making sure no one can know how terrible your memory is.

Cryptography is the study of techniques to secure communication. The word cryptography is greek for “hidden secret.” The earliest known practice of cryptography dates back to the Egyptians in 1900 BC. They would write strange looking hieroglyphic symbols in order to alter the appearance of the text.

The first known consistent usage of encryption in order to hide message wasn’t until 100 BC. Julius Caesar implemented what is now known as the caesar cypher. With the cypher he was able to send encrypted messages to his generals without fear of anyone intercepting. The caesar cypher is the canonical example of encryption. In order for it to work each party must agree on a number before hand. That number, called the key, is used to linearly shift all the letters. For example say we agree on the number 10. The alphabet would be shifted 10 spots to the left, transforming it like so:

from: abcdefghijklmnopqrstuvwxyz
to:   klmnopqrstuvwxyzabcdefghij

Then this transformation can be applied to any message. For example, with the key 10, “FullStackHacks” would be encrypted as so:

message:    FullStackHacks
encryption: PkvvCdkmuRkmui

This effectively renders the message unreadable without the key. The caesar cypher isn’t a secure form of encryption by todays standards. There are only 26 possible keys. All a computer would have to do is try each posible key until it produces a coherent statement. One of the most common and accepted methods of encryption is using PGP keys and the RSA algorithm.

RSA is an algorithm used to encrypt and decrypt messages in a cryptographically secure manner, so that even the NSA can’t see your data. It’s named after Ron Riest, Adi Shamir, and Leonard Adleman. Ron and Adi were computer scientist; they worked on implementing a one-way function that was difficult to invert (meaning: easy to encrypt difficult to decrypt). The two would propose a method and Leonard’s job was to find its flaws. As the legend goes, in 1977, after a Passover dinner Ron had a good deal to drink and returned home unable to sleep. In a stroke of genius Ron Riest stayed up all night formalizing the idea of what was to become the RSA algorithm. Funny enough, at the time computers were too expensive to implement his ideas so the RSA algorithm stayed dormant for about twenty years. Then in 1997 the algorithm was publicly released.

In order to understand RSA you need to understand a few simple mathematical concepts. The first is modular arithmetic. Modular is just a fancy word for the remainder. In modular arithmetic you work only with integers and a domain, n, is defined. The modulo of every value is then taken with respect to n. Therefore in mod 10 you have this:

4 = 14 = 24 = 34(mod 10)

What this means is that all values are limited to a finite domain, Z:

Z = {0, 1, 2, .... n - 1}

This has some interesting effects. Take the definition of an inverse value for example. An inverse value is the value that when multiplied by the inverse the results in 1. Which can be formally written as:

x * x^-1 = 1

In traditional arithmetic this would mean that the inverse of 3 is 1 /3, because 3 * 1 / 3 = 1. However, in modular arithmetic we only have integer values, but an inverse can still exists. For example, the inverse of 3 mod 5 is 2. This can easily be shown:

Defintion: x * x^-1 = 1
3 * 2 = 6 (mod 5)
6 mod 5 = 1

There’s also an interesting property with modular arithmetic: if the greatest common divisor of any number > 0 and n is 1 then an inverse value exist. In our example the greatest common divisor between 3 and 5 is 1, hence we know the inverse exists. If we were in say mod 6, the greatest common divisor between 3 and 6 is 2. 2 does not equal 1 and therefore 3 mod 6 doesn’t have an inverse value. This means if n is a prime number we can prove that every number, in its domain and > 0, has an inverse. Since n is a prime number then the greatest common divisor with all values less than n and > 0 will be 1 and therefore have an inverse value. Take the prime number 5, we can easily show the inverse value for every value from 1 to 4:

mod 5:
1^-1 = 1
2^-1 = 3
3^-1 = 2
4^-1 = 4

The final concept that needs to be understood is Euler’s totient, ϕ. Euler’s totient is defined as “the number of elements that have a multiplicative inverse in a set of modulo integers.” Example:

ϕ(5) = 4

In mod 5: 1, 2, 3, and 4 all have inverse values. That’s 4 distinct values hence ϕ(5) = 4. It can be shown that for any prime number, p:

ϕ(p) = p - 1

Another useful theorem is that for any value n:

ϕ(n) = ϕ(p * q) = ϕ(p) * ϕ(q)

Alright, now we have all the tools we need to fight the NSA and stop them from stealing our data. I’ve explained modular arithmetic, inverse numbers, and Euler’s totient, and now we can finally explain how the RSA algorithm works. First we need 2 very large prime numbers. Typically, these prime numbers can be as large as 2²⁰⁴⁸. This is where PGP (pretty good privacy) key generation comes into play.

PGP key generation is done by generating a random value and then using the Miller-Rabin primality test to determine within a high degree of certainty if the number is prime. If the value is not prime we simply increment the value until it is. We’ll generate one random prime number: p and a second prime number: q. Next, the modulus is generated. Our modulus, n, equals p * q. From now on most our math will be modular arithmetic in mod n. Since p and q are prime numbers we know.

ϕ(p) = p - 1
ϕ(q) = q - 1

Therefore:

ϕ(n) = (p - 1) * (q - 1)

With this information we can generate our public key. Our public key will be used later on to encrypt a message. First we define is a random prime number, e, between 65537 and ϕ(n). The reason 65537 is chosen as the lower bound is because if the public key is too small there can be security flaws. Now we can expose two values (e and n). These two values will be combined to create our public PGP key.

Next we will generate a private PGP key. We need a value d that is the inverse of our public key in “mod ϕ(n)”. Meaning:

e * d = 1 mod ϕ(n)

This can be easily calculated using the Extended Euclidean Algorithm. d and n will then be combined to produce our private key.

Note: prime factorization is hard therefore, when only given n, for big enough values p and q are impossible to find in a finite amount of time. Therefore ϕ(n) is also impossible to find. Hence, our public/private keys cannot be forged.

Now that we’ve successfully generated a public and private key we can encrypt our messages. In order to do this each party exposes their public key containing e and n. From there any value m can be encrypted like so:

m ^ e = encrypted_message (mod n)

Then in order to decrypt the message all you have to do is:

encrypted_message ^ d = m (mod n)

This is cool and all, but if you’re anything like me you’re probably asking why does this work? First you need Fermat’s little theorem; It states for any prime number p:

a^p = a (mod p)
AND
a^(p - 1) = 1 (mod p)

Well remember how d and e were inverse values in ϕ(n), therefore:

d * e = 1 (mod ϕ(n))

This can then be converted to:

d * e = 1 (mod ((p - 1)*(q - 1)))

Which means:

e * d = 1 (mod (p - 1))
AND
e * d = 1 (mod (q - 1))

If we apply Fermat’s little theorem we can then show that:

m^(e * d) = m (mod p)
AND
m^(e * d) = m (mod q)

Then we can apply Chinese remainder theorem:

m^(e * d) = m (mod p * q)

Substitute n back in:

m^(e * d) = m (mod n)

Remember our encrypted message:

encrypted_message = m ^ e (mod n)

In order to decrypt that message we simply did:

encrypted_message ^ d = m (mod n)

Combining both operations gives us:

(m ^ e) ^ d (mod n)

That’s equivalent to:

(m ^ e * d) (mod n)

Which we showed above equals:

m^(e * d) = m (mod n)

Hence our message was unaltered. Amazing, right!? This simple algorithm is responsible for a large portion of all encryption on the web. As long as someone has access to my public key they can send me a message and I’ll be the only one who can decrypt it. This algorithm also allows anyone to digitally sign messages. Mathematically there’s no difference between private and public keys. The only difference is the way a user exposes them. A digital signature is just the inverse action of encryption. Encryption is sending data that can only be decrypted by me. A signature is sending data that could have only been encrypted by me. So, if we encrypt a piece of data with our private key. Then anyone with our public key will be able to decrypt it knowing we were the only ones who could have encrypted the data! If this doesn’t get you excited about cryptography I don’t know what will.

The RSA algorithm allows us to secure all sorts of messages and its what makes sending encrypted emails or even an https connections possible. One interesting parts about the RSA algorithm is there’s still a need for trust when it comes to the public key. For example say an hacker is able to give someone a fake public key. They could then trick a user into encrypting the data so that only the hacker can read it. In order to combat this there are some interesting projects. MIT allows you to publicly host your public keys on their PGP server. Users can also host pubic keys on the global PGP directory. My favorite public key storage method is Keybase, which is a social network for public keys. Keybase may be to the nerdiest project on the web, but isn’t it awesome? There’s even such a thing as key signing parties where people will meet in person and digitally sign each other’s public keys. It’s impossible to forge in person meetings; so this allows a trusted network of verified public keys to be formed. Oh, also Facebook now allows people to host the PGP keys.

Welcome to the beautiful world of cryptography.

Interesting links

• If you’re still confused this is a great write up of how RSA encryption works. It also includes some simple math examples.
• A brief history of encryption
• Keybase.io
• PGP global directory
• MIT PGP key server

Digitally signature

In the spirit of this article I’ve decide to digitally sign it using my Keybase public key that can be shown below (scroll all the way to the bottom to see my signature).

My Keybase PGP public key

— — -BEGIN PGP PUBLIC KEY BLOCK — — -
Comment: https://keybase.io/download
Version: Keybase Go 1.0.21 (darwin)

xsFNBFjyW6YBEAC2WWvu3whKuaVuWt82qDkgUzeWSP7RQsDr2eu/9cfKfd0ppH3k
E+o00kWf6NIy7rcSG5g+PxAiWdp0lejNVpa9Z5/TXYc4i5izwAfFXtR8HL3N0Cb+
gmUELzVDRbqOW34ZU5erHoBUooNCe0ZpBXf8M3GajbqtPBIv7ZVVN8aS0+p3PUWI
jEuxaWQRNNUaG52tH0X0ER2OdGsyummpLXvTeE+U5/1awTS1ARC4vY4M7swzg8t/
XneWajkITtLeRP5tPJ6FspiJApj7H9BZ8nk7Q6hyLtZro20LFbbKdlEEbFXdR+G3
3W/qBtzGyV/zxJP0kVRU0rk81zK3YE367MPCxzZUwBLc9He6qkkiGxlIKmSb7Czb
JcEL4mG/ZmNtgbhDqcqCiLojnTh/IgH5m8ZbAyW8RQfVMGcyHDLDlCeSJUc2MwLF
5cdqiOgdVBnHQiWsQB6xEVSqGVjpJShwiOY0/eiuLrco9rA2wzUFbVCwEqsOb9wQ
2jmTEJlQNMnqvSsE/uTjFLcgFDu8W0bJcUt1Yofdsv/sHovE2ake5kOISJ00UatU
CXAkqHmFXV82xwnhZ16HixJv3S1ULzCIHzOmFSvKv7/RlgrHIiwR54yA28yW8sMf
XCJJvL7f88AcDrdiAaFHQb4pqDcCFPk30RCd4WyJel/VTfOSfyO3IS1NYwARAQAB
zR9BZGFtIENvbGxpbnMgPGFkYzYxM0BnbWFpbC5jb20+wsF4BBMBCAAsBQJY8lum
CRBfedYkhRG3gQIbAwUJHhM4AAIZAQQLBwkDBRUICgIDBBYAAQIAAEnjEABTdZf8
sIG9uIwRnFxkqS6M64RfTWYKD3e7ot18RFkd+m3zWPRmKDNRYajDHTHdTn5Qaq83
KqEOxlKlcrmLdXUdE1InscXQscl6mKs0f2Y6Nx9FbaUP/Shsch/qBy0eHH7diHXG
Xr81TEEJmYRgU1nLmD8FAdTDhOBepy9Ejs+GuWnioPl4AMiFwwXJouZXg7vN5l6d
E6esu2n2njonPtoygHEuitfR/5dX7h4ImAgPep26f65Lke36WI4qEE/1f9qr2M91
rAKEny127Zw8HFj+MWqq5VSXOkWu8A3cpDLbNffE9ZvlkrxQLlWw34ipPYqRldGZ
KyQEx9z/KIvafnn7rfLYLp6CUgk9us6n2EPuqM0RZOG5QIfXX+l18fpL+akcKcHx
jAjGxeb5CmTL8cPCQ9d6XSrdnBIUowOi5aRqUYK+th07++9TPQFVoLjeT/rk4q2p
GlebBEuP7qqdsC6SpPxg4WB7TbL8tgizXv+V2/id14kCriEk1NJvnXbOUULZRwR9
D5vQJ4QJyZAv2+nu3nATJvq+TC1ZXSMrVqDimjx1yHUMsqJsUAUzH8Haex9zSILv
QxgxTPkAvcyq+JGSEj6XyHR7aCXniUSETSsHclyz7h9ax4DxNyAQj5lDsVWOTGpD
9NKDP96K1OZYE2CnZMkGQ1oHKN8nlQDuE+O+P87BTQRY8lumARAAsJTokiie5QR8
jDnBgFq5gr7fFQe6idqp7M9XIeYNQ5bKQK+m7R8ceRQjdWqbO1a8jaE+hToByQv/
O+3pCmNx00czTgqym2bBfuYxqZRbLoFCqq5Mh65egHA0fbKjKBQKrvqKwy2PYJtk
b9B/oNVmnCeXmvd6IYpaKM6eNNU1dNVjhBluHw6HTjADqnDFErFzu28BC1fk5lZ9
BJTE583+g/u9KmBplDem3gI7+VFKv17kKK49gVjG937nukXAaQqeflDjtHRkhO+H
yn/TPxP8K6MhJ6FxPhvLazSxkMOpd49CNwd7FDmy+5GVMKLrBSuqxqAWRBvvYW71
tGZDZFRPXpQ6cNV36VNnrUeq+dDK98fIw2hIJFKyC9N3GnG/ZrMGp05u/8dodh90
U4ZsfEET4T77hAfv3RQc/14w6LEpzJiMKdDsuHu3armd6dPwaTP4h2SxqNFQWxUu
YDi8PEPFG+nCUVkTcDn0KUI3rhMV9lxAoWzO3ZuQ7SHUlcRi00E9+22DvHvmbE/Z
1T9+6Gjxc8BNgHH9q/xGl/o7EkmLr5Z3YU7a3FlAvj5+uqSn0W9oDOA9YK/vLdJp
9sAo01qDMJjifH3f7WZDD5ZytfWmq/QA0Jvv6KiKqARX1qyVZWwOPSrQfvDQMX7X
P/k8bcvP0x89+WXTl0LECwd4Tq9mz28AEQEAAcLBdQQYAQgAKQUCWPJbpgkQX3nW
JIURt4ECGwwFCR4TOAAECwcJAwUVCAoCAwQWAAECAACvjxAAF2bj2qxrnQTZPscf
mxrTjc6vzKIssy5rSuCTaCXWmgeP7G0Ox1y+gFBxU0UxFhYlyIoZu8M+iwhkisdK
oGvNzulmbNEcCbIXhzmS0HfDjSXPdx2ZEXxOX+t66SAlH5EDXbSUVAJq1rVIVZUq
NY75QtIwLgf9ZbqRCexpLw9anmyqzTCkFCeHzyryHuitmYBSp/8MecjOsPYF+bD6
KL6AX2FMcZxKVBxbnoXN/E0fF5mrhejcq8rwu8GE33tNPYweH7tgbLKa5ns/89aw
YWEfmD4cQjLTcJErvPZEU8+WCf73ES3BnphnAKauuh4jnwsirh3rESVTW4i3degF
h5/3V+B2JyJtHaE+x4ZxvatgclOWQgmZ5pc3d/prYnWKhLwz7GXDuKPNYipSo2wc
mCI7Kt8j7vrQfC1WQGNAITsYpwW865Z7jFhmp7e91d/8UNpEI/yYiGXlwywvgjsu
TmJYWg+YiU5RZmtuOu3ncF1xxwRFsR69gx+IiJyz3jS6Y5jCTIIqqON8uUJ0DHPy
f5+CdffUxGc6EZAETtjb2YoPbcDg8DfRgHihhk3EHgaX87Mdk/MIwu+BhPkjMnPp
pzocvWNu9LNhtKWyuwiu5IBEPGa3JAPWgdEt3ir6V6o6+yCg9hpFgUD5maEUYzzF
WudlSZPChjzFGHUZBzoDumJNwt8=
=FPw0
— — -END PGP PUBLIC KEY BLOCK — — -

— — -BEGIN PGP SIGNATURE — — -
Version: Keybase OpenPGP v2.0.68
Comment: https://keybase.io/crypto

wsFcBAABCgAGBQJY9OcbAAoJEF951iSFEbeBduYP/1WrLOoNuCW3ediB53xOzw84
Hx1lXL8GDvuWs4tulT9Be+HKk1jMVjUw5wbNVkMt2XaMsDomjXnRX//18REA+pBS
N49TqNRrJP8DZCXR9takF3tjmhIeAw6AV9cfzFRYXHkVGYOzYErWVxhJFT2LxG+S
VoJC4N6Mxc670JjdVVfDTPdrnV2HWbkRmJoTvl6uEM9TNtDQF0bPB075GZAOXadf
V7YUoHjCc4zqKFgVYDhECc6ma11Syv+0AbqLjBbQjzJHbzt5K+3vYWJYQXFwkpeh
yM2wMubitbaoRIJKNjQYouRgkdmqGBzcCnd13uxJU+SGEgYZwPqcLcNQTW6bgByo
6cAoLD5WecIcP5aM2Gs/49fLqodu7BvAdykibj2vBNdnjPF0o72XJthbO+cOc657
SQ0MHAO27MkJqRk7C/AJcaS/p9GS5o09prEcP8Y1yRVOGA4iramQedKGXMUlqmUB
mbe10gewEG/HNaflScEMzo8UmHfd+T+DbZXxGfKIw69JK69Ky3LAw2I4LhbYEqfb
89OEVDB2SieAryG2NhbEuY9eUnTdWMl/ig2qfZOVI2c02C+DjuOfiKm3ClXk/vm5
dmktdCQA//QnM7b2BoLtY5Epqxp3nUMX5uJTOcSkdq7U/MrRXOFf8J1JTnkcKvuB
Zn2QqLBkZO4/9sGdGw20
=DQfX
— — -END PGP SIGNATURE — — -