Cryptography is study of ways to convert a plain text to some unintelligible gibberish which can be converted back to the original plain text by only those who have some kind of secret knowledge.
The classical analogy of cryptography goes as follows:
There are three people Alice, Bob and Eve. Alice and Bob wants to exchange secret messages but Eve is always eavesdropping and intercepting their messages. To prevent Eve from reading their texts Alice and Bob decided to meet and share amongst themselves two identical keys to a padlock. Alice and Bob keep their keys a secret. Now Alice writes a message, puts it into a box, locks the box with the padlock and sends it over to Bob. Eve intercepts the box, but cannot read the message inside the box because she don’t have a key to unlock it. So she forwards that box to Bob. Bob having the key to the padlock can unlock the box and can read the message. Using this setup Alice and Bob can share secret messages without Eve reading them.
This setup works perfectly as long as Alice and Bob can keep the key a secret.
But there is a major flaw in this setup. This setup relies on Alice and Bob being able to share a key in secret.
What if Alice and Bob cannot meet physically? They cannot send the key to any of them, because Eve can intercept the key and create a copy for herself and can unlock any box that is locked with that padlock. How would they share a key?
In cryptographic terminology, the above example can be reworded as follows: Alice has some key using which she encodes some plain text to some cipher text, which she sends over to Bob. Bob having the same key can decipher the cipher text into plaintext. This system uses a symmetric key, which can both encrypt and decrypt a message. The problem with symmetric key system is that you need to establish a shared key and be certain that it is a secret. Which is impossible to do over an open communication channel.
The idea of asymmetric key was born to resolve this problem. In asymmetric key systems you have two keys, one used to lock and another is user to unlock it. Alice can publish one key to public and keep the other one private. Anyone who wants to send her a message can encrypt the message using her public key and Alice having the private key can only decrypt the message. The key pairs are linked in a way that given one you can’t guess the other one, but the one can decrypt any message encrypted using the other key.
Mathematically, in asymmetric key, the encryption and decryption are inverse operations. Meaning:
Where, k1 is the key used to encrypt and k2 is key to decrypt.
Now the questions are:
a) What are functions D and E?
b) How is k1 and k2 related that one reverses the effect of the other, but you can’t guess k1 given k2 or vice versa?
Let’s explore the parts of this mathematical puzzle that makes this possible.
A function is called a one way function if calculating it in one direction is easy and calculating it in other direction is difficult. Meaning, you can calculate \(c = f(x)\) easily but you calculating \(f^{-1}(c)\) is very difficult.
A trapdoor function is a one way function, which is hard to reverse, unless you have some secret information. Meaning, you can calculate \(c = f(x)\) easily. But it is very difficult to calculate \(f^{-1}(c,t)\) if you don’t know the exact value of \(t\) that unlocks the trapdoor.
We are looking for such trapdoor to encrypt our messages with. Only does who knows the exact value of \(t\) can decrypt it.
Raise a number \(a\) to the power of \(e\) and divide it by \(n\) then the remainder of the division is \(c\). This operation is called modular exponentiation. Which is defined formally as follows:
Once you calculate \(c\), it is very difficult to calculate \(a\) given \(c\), \(e\), and \(n\). Best you can do to find a is to do brute force search of all numbers until you find the number \(a\). Moreover, since this is a congruence relationship there can be other values of a which will satisfy the relationship. So you can’t find the exact value of a that produces c.
So this is a one way function.
Now we need a trapdoor to be able to reverse it. Otherwise it will be a lock without a key, which will be pretty useless. We want something like:
Where \(d\) is the secret that reverses the one way function
Therefore our encryption function \(E\) will be, \(E(a)≡a^e (mod \space n)\) , and decryption \(D\) will be \(D(c)≡c^d (mod \space n)\)
Therefore we can say that,
\(D(E(a))≡ a (mod \space n)\)
\( \implies D(a^e) ≡a (mod \space n)\)
\(\implies (a^e )^d ≡a (mod \space n)\)
\(\implies a^{ed}≡a(mod \space n) \text{ ---------- (1)}\)
Now, For us to use modular exponentiation as our trapdoor function, we need to find a relationship between e, d, n such that e and d can reverse each other’s affects and this relationship between e and d has to be protected by some secret that cannot be deduced.
Prime factorization is an inherently difficult problem. Given a composite number, to find its prime factors you have to do brute force search to find a number that evenly divides the given number. If you select two prime numbers p and q which are hundreds of digits long it is easy to compute their product n. Now given n, you have to brute force search to find any of p or q. And since p and q are very large, it is computationally infeasible to do so.
Okay, But why do we care about this?
We care about this because if p and q are significantly large, given only their product we can be fairly sure that that p and q can never be found from n. If we keep the large prime factors of n a secret that only we know, we can be certain that it cannot be deduced by anyone else.
Now our task is to tie this idea of secret factors of a large number to the secret relationship of e, d and n.
Euler’s totient (\(\phi\)) of given number n is defined as the number of integer smaller than n which do not share any factor with \(n\). In other words, \(\phi(n)\) is number of co-primes that are less than n.
Eg. \(\phi(8)\) can be calculated as follows:
Factor of 8 are 2 x 2 x 2. All numbers less than 8 are 7,6,5,4,3,2,1. Amongst these, 6, 4 and 2 shares a factor of 2 with 8. Hence these are not co-primes of 8. The remain 4 numbers are 7,5,3 and 1. Which are co-prime to 8 (since 1 is every numbers factor, it is also counted). Therefore \(\phi(8) = 4\).
For any prime number n there will not be any number smaller than n which will share any factor with n. So \(\phi(n)\) will simply be number of all the integers less than n, which is \(n – 1\), i.e \(\phi(n) = n – 1\) if \(n\) is prime.
It states that, if \(n\) and a are positive integers and \(a\), \(n\) are coprime, then \(a^{\phi(n)}≡1 (mod\space n)\) , where \(\phi(n)\) is the Euler's totient function.
We can develop this further as follows:
\(a^{\phi(n)}≡1 (mod\space n) , \) where we can multiply a in both side to get
\(a^{\phi(n)+1}≡a (mod\space n) \text{ ---------- (2a)}\)
We can multiply \(a^{\phi(n)}\) in both side of (2a) to get
\(a^{2\phi(n)+1} ≡a^{\phi(n)+1} (mod \space n)\) , where we can substitute \(a^{\phi(n)+1}\) as a from (2a) to get
\(a^{2\phi(n)+1} ≡a(mod\space n) \text{ ---------- (2b)}\)
Therefore from (2b), we can say that, if we multiply (2a) with \(a^{\phi(n)}\) \(k\) times to get the following (by induction)
\(a^{k\phi(n)+1} ≡a (mod\space n) \text{ ---------- (2)}\)
Where and are coprime and is any positive integer.
A modular multiplicative inverse of an integer \(a\) is an integer \(x\) such that \(a*x\) is congruent to 1 modular some modulus \(n\). Formally,
\(a*x≡1 (mod \space n) \text{ ---------- (3)}\)
For any given a and n, a multiplicative inverse \(x\) exist if and only if \(a\) and \(n\) are coprime. In other words gcd(a,n) must be 1 for x to exist.
In (1) we got, \(a^{ed}≡a(mod \space n)\), where we need to establish a secret relationship between e and d.
In (2) we got, \(a^{k\phi(n)+1} ≡a (mod\space n)\), where a and n are coprime.
Therefore (1) and (2) implies,
\(ed=k\phi(n)+1 \text{ ---------- (4a)}\)
Which means,
\(ed≡1 (mod \space \phi(n)) \)
and from multiplicative inverse theorem (3) we know d exists if and only if e is a coprime to \(\phi(n)\)
Therefore the relationship between e and d is
\(ed=k\phi(n)+1 \text{ ---------- (4)}\)
where for e and φ(n) are coprime.
Equation (4) is a clear relationship between e and d. So where is the secret? We wanted it to be secret, right?
Yes. The secret lies in the \(\phi(n)\).
You see, Euler’s Totient has a multiplicative property. If p and q are prime factors of a number n, then
\(\phi(n)= \phi(p*q)=\phi(p)*\phi(q)=(p-1)*(q-1)\) ,since p and q are prime.
If n is significantly large, calculating \(\phi(n)\) in a brute force manner is impossible because amount of computation required. But if we know the secret, which is p and q that makes n, the calculation of \(\phi(n)\) is easy to compute.
That’s RSA!
Let’s write down the steps to get all this tied up together to get RSA working.
Step 1: Select two giant prime numbers p and q. Compute \(\phi(n)= \phi(p*q)=\phi(p)*\phi(q)=(p-1)*(q-1)\)
Step 2: Select value of e such that it is coprime with \(\phi(n)\), i.e. \(gcd(e,\phi(n))=1\).
Step 3: Calculate d for corresponding e using equation \(ed=k\phi(n)+1\). (We can discard the values of p, q and \(\phi(n)\) after we calculate our secret d, to make sure nobody else can find d)
Step 4: Encrypt using \(E(a)≡a^e (mod\space n)\)
Step 5: Decrypt using \(D(c)≡c^d (mod\space n)\)
Step 1: Select p = 31 and q = 83. We are selecting smaller prime number for the example.
Calculate n = p *q = 2573,
Calculate \(\phi(n)=(p-1)(q-1)=30*82=2460\)
Step 2: Select e, such that gcd(e,φ(n))=1.
For e = 7, gcd(7,2460) = 1
Step 3: Calculate d using \(d= {{kφ(n)+1}\over{e}}\)
Starting from 1 try values of k such that, ( kφ(n)+1) % e==0
For this example, k = 2 satisfies the above condition.
Therefore \(d= (2*2460+1)/7 = 703\)
Step 4: Encrypt using \(E(a)≡a^e (mod\space n)\)
Let’s say we want to encrypt a = 543
Therefore \(E(a)≡a^e (\mod n)= 543^7\mod 2573=1155\)
1155 is the encrypted value of our message.
Step 5: Decrypt cipher c using \(D(c)≡c^d (mod\space n)\)
\(D(c)≡c^d (mod n)=1155^{703} \mod 2573=543\)
Which is equal to our plain value a. Therefore RSA works.
Let’s implement this.
I have implemented RSA using C++. Following is an explanation of the decisions made to get this implementation working. Clone the Github repository to follow along different part of the code.
rtw_RSA: Implenemtation of RSA from Scratch
Disclaimer: This is a text book RSA. There are few vulnerabilities in this version, which is discussed in this post. So don't use this in your production application.
First, we need a way to store and use arbitrarily large numbers. I tried to implement a class for that purpose and gave up, because it was too much work. I ended up using the GMP library. How to setup GMP is mentioned in the readme of the github repository mentioned above.
The traditional algorithm of testing primality is try to divide the given number n by all the numbers starting from 2 to \(\sqrt{n}\) . This takes \(O(\sqrt{n})\) time. If n is hundreds of digits long \(\sqrt{n}\) will have half of the number of digits n has, which is still a very big number. So this primality test is not efficient enough for our use.
Instead we will use a probabilistic primality test called Miller-Rabin primality test. This primality test takes a number n and performs k number of tests. If all of these k test passes we can say that \(4^{-k}\)is the probability of n being composite. If any of these k test fails we can guarantee that n is composite.
If k is large enough, we can be fairly certain that a given number if prime if the test passes. The complexity of this algorithm is \(O(k \log^3n)\) which is really fast.
Since we are dealing with very large numbers. Raising such numbers to a big exponent a very expensive operation. And we don’t even need the result of the exponentiation, all we need is the remainder when we divide by some number n. There is a very fast algorithm to raise a number to a exponent called fast exponentiation. We will modify this algorithm a little bit considering the fact that we only care about modulo of the exponent. This algorithms runtime is \(O(\log N)\) where N is the exponent.
When you hear that an encryption is 1024 bit what does that mean? It means 1024 bits are used to store the public modulo n. If you use k bits, the maximum value that n can have is \(2^k-1\).
If p and q are two number each requiring at least x and y bits to represent them respectively, then their product will must require at least max(x,y) bits and at most x+y bits.
If n is a product of p and q and for n to be small enough to be represented by at most k bits, product of p and q can have at most k number of bits. Meaning
\(x+y≤k\)
Thus, we can select prime numbers p and q to be k/2 bits long, in which case n will be at most k bit long.
The encryption and decryption in RSA works on numbers only. So for us to encrypt a string we need a way to convert it to numbers.
The first idea that comes to mind is to use the ASCII values of each character and encrypting it. Let’s think about it. It requires 8 bits to represent a character in ASCII. If you feed that number into the encryption function, which is a^e (mod n), it will result in a number which is modulo n, so it will be at most k bits long. Therefore for every 8 bits of plain text you have k bit of cipher text. If k is large enough compared to 8 you are using quite a lot of extra space to store the cipher.
For example, If you have 10 characters (80 bits or 10 bytes) to encrypt in a 1024 bit encryption, you need 10 * (1024) bits which is 1280 bytes. That’s a lot of wastage of space.
Okay, that won’t work. But what if you take a bunch of characters from a string and combine their bits serially to make a number which is comparable in bit length with n. We will call such a combination of bits a block.
This is better idea. But how many characters can we combine? We need to remember that for RSA encryption to work the input must be less than n.
If n is a k bit number, the number representing the string will have to be less than k bit long. We will make the input a k-8 bits long number. We have to make sure that key generated is greater than \(2^{k-8}-1.\)
To encode a string of characters to number we will do as follows: Each byte will be arranged in a little endian fashion and every bit of every byte will be arranged in little endian fashion. Then this collection of bits considered as a number.
// From util.cpp
mpz_class RTW::FileIO::bytes_to_mpz(const char *buffer, size_t count)
{
mpz_t _t;
mpz_init(_t);
mpz_import(
_t , // where to load to
count, // How many words to read,
-1, // Least significant word first
sizeof(buffer[0]), // size of each words
-1, // Each word is little endien
0, // no nails
buffer // read from
);
mpz_class r(_t);
return r;
}
To decode, we pass number and a buffer to load the corresponding data. We will consider each byte representing the number to be little endian and we will consider the least significant bytes to be at the lowest index. And copy the data byte to the buffer.
// util.cpp
int RTW::FileIO::mpz_to_bytes(char *buffer, size_t size, mpz_t value)
{
size_t bytes_written;
mpz_export(
buffer, // where to write. Buffer must have enough space to accomodate the values
&bytes_written, // Will update how many bytes are written into the buffer from the number
-1 , // Least significant words first
sizeof(buffer[0]), // Size of each word
-1, // Each word are little endien
0, // no nails
value // where to read from
);
// If bytes_written < size, I can fill the remaining of the buffer as 0s, beacase numbers are little endian
// and 0s after most significant word are ignored
for(int i = bytes_written; i < size ; i++)
buffer[i] = 0;
return bytes_written;
}
We will create a buffer of length k-8 bits. Then try to read k-8 bit chucks from the file at a time. Then we convert this buffer to a number, using the encoding schema mentioned above, which we can feed to the encryption function to get a k bit number. We can convert this k bit number to a sequence of k bits and write to the output file.
For every k - 8 bit of plain text we are getting a k bit of cipher text.
// main.cpp
int encrypt_file(std::string path_puk, int key_size, std::string path_in, std::string path_out)
{
using namespace RTW;
// Try to open in/out files. Return -2,-3 on error
std::fstream in, out;
in.open(path_in,std::ios::binary|std::ios::in);
if(in.fail())
{
in.close();
return -2;
}
out.open(path_out,std::ios::binary|std::ios::out);
if(out.fail())
{
out.close();
return -3;
}
// Read key
mpz_class n;
if( FileIO::read_public_key(path_puk,n,key_size) < 0)
{
in.close();
out.close();
return -1;
}
RSA rsa(key_size);
int block_size = rsa.get_block_size();
char buffer[key_size/8];
mpz_class msg, cipher;
while(!in.eof())
{
in.read(buffer,block_size/8);
if( in.gcount() < 1)
continue;
msg = FileIO::bytes_to_mpz(buffer,in.gcount());
rsa.encrypt(msg,cipher,n);
// Cipher is always a key_size/8 byte long number, so if any number of bytes were read from
// input file, buffer will contain key_size/8 bytes representing cipher
FileIO::mpz_to_bytes(buffer,key_size/8,cipher.get_mpz_t());
out.write(buffer,key_size/8);
}
in.close();
out.close();
return 0;
}
We can read the cipher text in the same way. Read the private key from file then we can read k bit chunks from file convert it in the same way to numbers. And decrypt it. Once decrypt we can convert it to a string of characters. The decoding function will return the number of bits in the end decrypted result, and those many bits are written to output file.
// main.cpp
int decrypt_file(std::string path_prk, int key_size, std::string path_in, std::string path_out)
{
// This shit is slow, because of the giant values of d.
// Todo: Put multiple thread reading the file
using namespace RTW;
// Try to open in/out files. Return -2,-3 on error
std::fstream in, out;
in.open(path_in,std::ios::binary|std::ios::in);
if(in.fail())
{
in.close();
return -2;
}
out.open(path_out,std::ios::binary|std::ios::out);
if(out.fail())
{
out.close();
return -3;
}
mpz_class n,d;
if( FileIO::read_private_key(path_prk,n,d,key_size) < 0)
{
in.close();
out.close();
return -1;
}
RSA rsa(key_size);
int block_size = rsa.get_block_size();
char buffer[key_size/8];
mpz_class msg, cipher;
while(!in.eof())
{
in.read(buffer,key_size/8);
int count = in.gcount();
if(count < 1)
continue;
cipher = FileIO::bytes_to_mpz(buffer,key_size/8);
rsa.decrypt(cipher,msg,n,d);
count = FileIO::mpz_to_bytes(buffer,key_size/8,msg.get_mpz_t());
if(count > 0)
out.write(buffer,count);
else if ( msg == 0 )
out.write(buffer,in.gcount());
}
in.close();
out.close();
return 0;
}
I have added a command line interface to generate keys, encrypt and decrypt files. I will leave it for you read the code of how the keys are written and read. Try to build it and test it out.
Good luck and Thanks for reading.