Public-key Cryptography Explained- 13 mins
Public-key cryptography is one of the most used cryptosystems today. It refers to any system that uses a key pair, one for encrypting data and another one for decrypting data. If data encrypted using a key, other key is used to decrypt it. This seems pretty magical at first, but in the end of blog post you will understand how this works. In this blog post I’ll start with an analogy to understand what is the purpose of using two key pairs. Then I’ll explain the mathematical concepts behind the algorithm. Then I’ll implement a toy algorithm to understand it further (But never design your own crypto algorithms). Next I’ll explain some
openssl commands to generate RSA public and private keys which you can use in real world applications.
Let’s start with an analogy
Suppose you are at home and need to send your passbook to the bank. You have to send this by a bad courier service, in fact they always try to inspect and spy what’s inside every package. So you buy a locker box with two identical keys. You keep one to yourself and send other one to the bank. You can’t send the key with the package because the courier service will open the locker box and inspect. You can’t send it separately because this bad courier always make copies of the keys they deliver in hopes of trying them out on future deliveries. So you walk in to the bank yourself to deliver the key to the bank. Now you go home and put the passbook inside the locker box and lock it with your identical key and send it via the bad courier. They deliver the box hopelessly without being able to see what’s inside. It was inefficient, you had to visit yourself to the bank first. But can we do better?
This time the bank buy a new kind of locker for this purpose. The new locker box has two keys, one for locking the box (public key), another one for unlocking (private key). The key used to lock can’t be used to unlock the box. The key used to unlock can’t be used to lock the box. Bank send over the locker box to you along with the locking key (public key). As usual the bad courier makes a copy of the key in hopes of future endeavors. Now you put the passbook inside the box and lock it with your locking key (public key). You keep the key and send the box. Courier tries to unlock the box using the key the have had copied, but no luck. It can only unlock using the unlocking key (private key) only owned by the bank.
Modern Internet is like the bad courier, filled with hackers inspecting unencrypted packets. We need something similar to the second paragraph to secure the Internet communication.
The first paragraph is an analogy of symmetric encryption. Second paragraph discuss asymmetric encryption, which is the category public encryption belongs. But how could we design such a lock digitally?
The Underlying Mathematics
We can write our encryption function as where is the message we want to encrypt, is the function that does the encryption and is the encrypted message. Decryption is . Let’s define our functions.
and are public and private keys respectively. is a large number which is a multiple of two large prime numbers. means the modulo operation. Most programming languages represent this by
% symbol. Given two positive numbers and result of is the reminder when divides by . For example because when divides by remainder is . We could write above equations in another way using modular arithmetic syntax.
If then and has a congruence relationship. That means is dividable by and and both has the same reminder.
Now we can write the following congruence relation. This relationship must be true for encryption and decryption to work properly. must always return original back.
Now we need to find a relationship between and in such that holds true. To move forward we need another equation. For that we are going to start with Fermat’s little theorem from number theory. Theorem state the follows
If is a prime number and is any integer number is an integer multiple of . We can also write this as
Removing from both sides we get
Now let’s look at a function called Euler’s totient function. In number theory Euler’s totient function counts number of positive integers given integer that are relatively prime to . Relative primes are numbers that don’t have divisors other than . If and are relatively prime then we can write that greatest common divisor is . We usually write this as . For example and are relatively prime because . Now to the totient function, notice that if is a prime all the postive integers less than are relatively prime to . We can write this as
So what does it have to do with our previous equations? Now we can write something like this using Euler’s totient function.
Now we are going to prepare above equations to match which is similar to with some reordering. As the first step of the preparation take the power on both sides
Now Let’s multiply both sides by
Now we also have the following equation
Did you notice the similarity in the right side of the two equations? Now we can write
Now this is exactly the following by the definition of modular arithmetic syntax.
We can expand further because is a multiple of two prime numbers.
So we can write
Now choose a random private key such that and (Which means they need to be relatively prime). Now we can find using modular inverse algorithm.
Now that we have found keys and we can use them to encrypt and decrypt messages. In the next section I will give a numeric example which will clear up most of the details.
Let’s choose two prime numbers . We choose small values to make calculations easier but in practice RSA algorithm use very large prime numbers.
And let’s calculate the Euler’s totient function
Now we choose such that it’s relatively prime to . Let’s say
Now compute such that
If then satisfies the equation.
Now private key is and public key is . Now let’s encrypt some number using public key. Of course if you need to encrypt chars you must convert them to integers first.
Now let’s decrypt using private key.
It works :). I’ve implemented this as a toy algorithm using python. Never implement your own cryptography algorithms though, to use in production environments.
from __future__ import division from Crypto.Util import number import os from fractions import gcd
from Crypto.Util import number for generating random primes.
class RSA: p = q = n = d = e = pi_n = 0 def __init__(self): self.generate() def generate(self): self.p = number.getPrime(10, os.urandom) self.q = number.getPrime(10, os.urandom) self.n = self.p * self.q self.pi_n = (self.p - 1) * (self.q - 1) self.d = self.choose_d() self.e = self.choose_e() def choose_d(self): self.d = self.find_a_coprime(self.pi_n) return self.d def find_a_coprime(self, a): for i in range(2, a): if gcd(i, a) == 1: return i def choose_e(self): for i in range(self.n): if (i * self.d) % self.pi_n == 1: return i def public_key(self): return (self.e, self.n) def private_key(self): return (self.d, self.n) def encrypt(self, m, key): return pow(m, key) % key def decrypt(self, c, key): return pow(c, key) % key
Now we can create
rsa = RSA()
Following should output
99 if our algorithm works and it does :)
rsa.decrypt(rsa.encrypt(99, rsa.public_key()), rsa.private_key())
How is it secure
Whole security of public key encryption depends on that given a public key no one should be able to generate private key from that public key. Remember ? So, to calculate d from e attacker needs to know . But only way to calculate that is . Only key generator knows and . When are large enough no one can calculate (Yet!) , from . The whole cryotosystem depends on this assumption.
Public key cryptography is used everywhere. HTTPS run on public key cryptography (Not only RSA but it plays a huge role). If you need to use public key cryptography for your own application you can use openssl. openssl is a full featured toolkit which can generate RSA keys among lot of other things. To generate a key pair type following in command line (Assuming you are on UNIX based system)
openssl genpkey -algorithm RSA -out private_key.pem -pkeyopt rsa_keygen_bits:2048
You will generate
private_key.pem file from above command. In this key there are lot of information encoded that it can be used to extract public key.
openssl rsa -pubout -in private_key.pem -out public_key.pem
public_key.pem only contain details to encrypt or decrypt something so it can be shared. But you should never share your
Now let’s encrypt some data using public key.
echo "reqviescat in constantia, ergo, repræsentatio cvpidi avctoris religionis" > key.bin
openssl rsautl -encrypt -inkey public_key.pem -pubin -in key.bin -out key.bin.enc
Encrypted data is written to
key.bin.enc. Now let’s decrypt it again
openssl rsautl -decrypt -inkey private_key.pem -in key.bin.enc -out key.bin
If you open
key.bin file you can see that same data is there.
Toy RSA Algorithm - Github
Original RSA Paper - A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
Modular Arithmetic - Wikipedia
Fermat’s Little Theorem - Wikipedia
Coprime integers - Wikipedia
Euler’s totient function - Wikipedia
Modular multiplicative inverse - Wikipedia