As you have read in the previous article on cryptography, encryption algorithms are like complicated mathematical equations that you can solve only if you know the variable X, which represents the password. But if you have ever used a program like PGP, which uses public and private keys, you may be wondering how it is possible to encrypt something with one password and decrypt it with another. Well, the concept is similar, and I’ll explain to you how this works in a moment.
To start with, let’s define some terms. There are two most common types of cryptographic algorithms in the world: those who encrypt and decrypt with the same key are called “symmetric algorithms,” and those who encrypt with one key and decrypt with another are called “public key algorithms.” Another thing that makes them different is their speed: symmetric algorithms can be up to 100 times faster than public keys algorithms. That’s why in real world applications public key algorithms are never used for encrypting data. They are only used to encrypt the key for the symmetric algorithm which encrypts the data.
I’ll show you how a public key algorithm works on an example of one of my favorite algorithms: RSA. RSA was invented in 1971 by Ron Rivest, Adi Shamir and Leonard Adelman (thus RSA.) Below we’ll encrypt and decrypt a simple string using RSA. Hope you’ll stay with me. 
Let’s choose two random prime numbers a and b, for example:
a=47, b=71.
Now we come up with another prime number n by multiplying a and b:
n=47*71=3337
The number n (3337), will be the first part of our public key. The second part will be a random number e of our choice. It can be any prime number. Let’s say it will be 79. So e=79.
Numbers n and e are our public key. Simple, isn’t it? We will now calculate our secret keys using this formula:
s=e^-1(mod((a-1)*(b-1)))
which in our case will be
s= 79^-1(mod((47-1)*(71-1))) = 79^-1(mod(46*70)) = 79^-1(mod 3220) = 1019
So here we have our public key (n=3337, e=79), and our secret key (s=1019). The original prime numbers a and b, should be permanently erased. The important concept to understand at this point is that the public key can only be used to encrypt messages. It cannot decrypt anything. The private key can only decrypt messages but it cannot encrypt them.
Now let’s encrypt and decrypt the text “SC TEAM”. First we convert it to numbers. As you may know, every letter has it’s numeric ASCII representation, for example “S” would be 83, “C” would be 67, a space would be 32 etc.
If we write SC_TEAM as numbers here’s how our text will look:
83 67 32 84 69 65 77
Now we divide it to modules of, let’s say, 3 digits:
x1=863
x2=732
x3=846
x4=965
x5=77
and we perform the encrypting operation using the formula shown below and the public key, which is composed of the numbers e and n:
x=i^e(mod n)
In our case:
x1=863^79 (mod 3337)=1299
x2=732^79 (mod 3337)=1964
x3=846^79 (mod 3337)=0315
x4=965^79 (mod 3337)=1313
x5=77^79 (mod 3337)=3123
Thus we come up with an encrypted string of digits:
129 919 640 315 131 331 23
which can later be converted to characters using the ASCII numeric table (since there are only 256 ASCII characters, we use modulus 256):
129=ü,
919=ù (919(mod 256)
128=Ç (640(mod 256))
059=; (315(mod 256))
132=ä
075=K (331(mod 256))
023=-
So our text “SC TEAM” after encrypting will look like this:
üùÇ;äK-
The public key (e and n) can be sent out all over the world, and anybody can encrypt a message to us, but they cannot decrypt it, because they do not have the secret key, which is the number s (1019). Once they send their message to us, we can decrypt it using the same formula as above, but instead of e, we use s:
x=i^s(mod n)
And so:
x1=1299^1019 (mod 3337)=863
x2=1964^1019 (mod 3337)=732
x2=0315^1019 (mod 3337)=846
x2=1313^1019 (mod 3337)=965
x2=3123^1019 (mod 3337)=77
which makes 83673284696577 = ASCII for “SC TEAM”.
The safety of this algorithm depends on the length of the key, because the only known mathematical way to break it is to try finding the original numbers a and b, which enabled us to generate the secret key. The process of figuring out what two prime numbers were multiplied to create the third prime number is called factorizing. There are several effective methods of factorizing prime numbers, the fastest of them has been discovered only recently, and is called Number Field Sieve (NFS).
In our example we used a very short, 16 bit key (4 digits — 3337). This is not difficult to factorize. But modern encryption programs usually work with much longer keys (1024 to 4096 bits).
Here’s how long it would take to factorize a 1024 bit key if we used the NFS method and a network of one million computers, each one being able to take one million factorizing steps per second: about 10,000,000,000 years. To show you how long the 1024 bit prime number is I typed an example below:
i=4254980451654210406548456540570891958405046848641201546548798465461
56543151549764754657849875654315248765245732100540084708424540578145
94254980451654210406548456540570891958405046848641201546548798465461
56543151549764754657849875654315248765245732100540084708424540578145
94254980451654210406548456540570891958405046848641201546548798465461
56543151549764754657849875654315248765245732100540084708424540578145
95784354651
What do you think were the two prime numbers a and b, that were multiplied, and created the number typed above?
But both match and technology keeps progressing and soon it will be possible to factorize even such large numbers within a reasonable amount of time. Of course by then the keys used by encryption programs will be much longer as well.
Hope you enjoyed this short introduction to public key algorithms!
