RSA public-key cryptosystem (named after its inventors: Ron Rivest, Adi Shamir and Leonard Adleman) is most used asymmetric public-private key cryptosystem.
Let's start with some theory.
Prime numbers are the numbers which has no divisors except itself and 1. This can be represented graphically.
Let's take 9 balls or some other objects. 9 balls can be arranged into rectangle:
ooo ooo ooo
So is 12 balls:
oooo oooo oooo
Or:
ooo ooo ooo ooo
So 9 and 12 are not prime numbers. 7 is prime number:
ooooooo
Or:
o o o o o o o
It's not possible to form a rectangle using 7 balls, or 11 balls or any other prime number.
The fact that balls can be arranged into rectangle shows that the number can be divided by the number which is represented by height and width of rectangle. Balls of prime number can be arranged vertically or horizontally, meaning, there are only two divisors: 1 and the prime number itself.
Natural number can be either prime or composite number. Composite number is a number which can be breaked up by product of prime numbers. Let's take 100. It's not prime.
By the fundamental theorem of arithmetic, any number can be represented as product of prime numbers, in only one single way.
So the composite number phrase means that the number is composed of prime numbers.
Let's factor 100 in Wolfram Mathematica:
In[]:= FactorInteger[100]
Out[]= {{2, 2}, {5, 2}}
This mean that 100 can be constructed using 2 and 5 prime numbers ($2^2 \cdot 5^2$):
In[]:= 2^2*5^2 Out[]= 100
Even more than that, it's possible to encode some information in prime numbers using factoring. Let's say, we would encode "Hello" text string. First, let's find ASCII codes of each character in the string:
In[]:= ToCharacterCode["Hello"]
Out[]= {72, 101, 108, 108, 111}
Let's find first 5 prime numbers, each number for each character:
In[]:= Map[Prime[#] &, Range[5]]
Out[]= {2, 3, 5, 7, 11}
Build a huge number using prime numbers as bases and ASCII codes as exponents, then get a product of all them ($2^{72} \cdot 3^{101} \cdot 5^{108} \cdot 7^{108} \cdot 11^{111}$):
In[]:= tmp = 2^72*3^101*5^108*7^108*11^111 Out[]= \ 1649465578065933994718255257642275679479006861206428830641826551739434\ 9344066214616222018844835866267141943107823334187149334898562231349428\ 5708281252457614466981636618940129599457183300076472809826225406689893\ 5837524252859632074600687844523389231265776082000229507684707641601562\ 5000000000000000000000000000000000000000000000000000000000000000000000\ 000
It's a big number, but Wolfram Mathematica is able to factor it back:
In[]:= FactorInteger[tmp]
Out[]= {{2, 72}, {3, 101}, {5, 108}, {7, 108}, {11, 111}}
First number in each pair is prime number and the second is exponent. Get the text string back:
In[]:= FromCharacterCode[Map[#[[2]] &, tmp]] Out[]= "Hello"
That allows to have some fun. Let's add exclamation point to the end of string by manipulating only the big number. ASCII code of exlamation point is 33. The next prime number after 11 is 13. So add it (by multiplying by $13^{33}$):
In[]:= tmp = tmp*13^33 Out[]= \ 9494539005656577744061615691556750598033024729435332190254469113536733\ 9032823543118405499931761589928052797992206631285822671397023217541663\ 5920521812548793623881568510051214975599793760307837993570818136014139\ 9497958680836430182400405525832564875875193876694267121604212637095253\ 0725145452728611417114734649658203125000000000000000000000000000000000\ 000000000000000000000000000000000000000
So we got new number. Let's factor it back and decode:
In[]:= factored = FactorInteger[tmp]
Out[]= {{2, 72}, {3, 101}, {5, 108}, {7, 108}, {11, 111}, {13, 33}}
In[]:= FromCharacterCode[Map[#[[2]] &, factored]]
Out[]= "Hello!"
Wow, that works. Will it be possible to remove one 'l' character from the string at the third position? 'l' has ASCII code of 108 and it is exponent for two prime numbers in our expression: 5 (first 'l') and 7 (second 'l').
To knock out the character, we divide the big number by the corresponding prime number with the exponent of 108 (divide by $5^{108}$):
In[]:= tmp = tmp/5^108
Out[]= \
3081154065769189664244341216329094565621009415122099836376732969546063\
1079164051611808432546107410277501678916823138724630810880390384343750\
1196528030610615786507542545262118293483878711112407171889948257893463\
8494741216231004109210436295299274515484540190050751059821909485854359\
9630924207126074604240892753608704
In[]:= factored = FactorInteger[tmp]
Out[]= {{2, 72}, {3, 101}, {7, 108}, {11, 111}, {13, 33}}
In[]:= FromCharacterCode[Map[#[[2]] &, factored]]
Out[]= "Helo!"
Let's say, the initial container number is 1. Let's increment the number at the second position within it by multiplicating by the first prime number (3):
In[]:= tmp = 1*3 Out[]= 3
Then let's set the number at fourth posistion to 123. The fourth prime number is 7 (the percent sign in Mathematica denotes the last result):
In[]:= tmp = tmp*7^123 Out[]= 26557071110804040505330743411815438275701018334410643480070773\ 5780279761186999642944265644421128096489029
Then let's set the number at fifth position to 456. The fifth prime number is 11:
In[]:= tmp = tmp*11^456 Out[]= 19917948660639605307938425372554395433764512138284060223646519\ 1257621966825293455339751080188144910510813322192288287162176499976800\ 9147068591160798243308591883294649069355015558472564457422829073938118\ 4396204999051856879940101934339913600942451006747982291524910653185084\ 4057972896537894301213735252418639782974592077393028390193060138936503\ 0125465578958567377627063815620261557939484036628536230966158222960762\ 8509899641574477547658142457598168497006309608599830554758951672484533\ 9216105863754463712957143732563375990198901073698626584903164027850451\ 8825659837114080589573087269
Then let's decrement the number at fourth position, the fourth prime number is 7:
In[]:= tmp = tmp/7 Out[]= 28454212372342293297054893389363422048235017340405800319495027\ 3225174238321847793342501543125921300729733317417554695945966428538287\ 0210097987372568919012274118992355813364307940675092082032612962768740\ 6280292855788366971343002763342733715632072866782831845035586647407263\ 4368532709339849001733907503455199689963702967704326271704371627052147\ 1607807969940810539467234022314659368484977195183623187094511747086804\ 0728428059392110782368774939425954995723299440856900792512788103549334\ 1737294091077805304224491046519108557427001533855180835575948611214931\ 260808548159154369939012467
Let's factor the composite number and get all the numbers we set inside container (1, 122, 456):
In[]:= FactorInteger[tmp]
Out[]= {{3, 1}, {7, 122}, {11, 456}}
So the resulting number has $3 \cdot 7^{122} \cdot 11^{456}$ form at the end.
This is somewhat wasteful way to store the numbers, but out of curiosity: since there are infinite number of prime numbers and so any number of infinitely big numbers can be stored within one (although huge) composite number.
Coprime numbers are the 2 or more numbers which don't have any common divisors. In mathematical lingo, GCD (greatest common divisor) of all coprime numbers is 1.
3 and 5 are coprimes. So are 7 and 10. So are 4, 5 and 9.
Coprime numbers are the numerator and denominator in fraction which cannot be reduced further (irreducible fraction). For example, $\frac{130}{14}$ is $\frac{65}{7}$ after reduction (or simplification), 65 and 7 are coprime to each other, but 130 and 14 are not (they has 2 as common divisor).
One application of coprime numbers in engineering is to make number of cogs on cogwheel and number of chain elements on chain to be coprimes. Let's imagine bike cogwheels and chain:
If you choose 5 as number of cogs on one of cogwhell and you have 10 or 15 or 20 chain elements, each cog on cogwheel will meet some set of the same chain elements. For example, if there are 5 cogs on cogwheel and 20 chain elements, each cog will meet only 4 chain elements and vice versa: each chain element has its own cog on cogwheel. This is bad because both cogwheel and chain will run out slightly faster than if each cog would interlock every chain elements at some point. To reach this, number of cogs and chain elements could be coprime numbers, like 5 and 11, or 5 and 23. That will make each chain element interlock each cog evenly, which is better.
... are also used in RSA in its core.
Semiprime is a product of two prime numbers.
An interesting property of semiprime:
In 1974 the Arecibo message was sent with a radio signal aimed at a star cluster. It consisted of 1679 binary digits intended to be interpreted as a 23×73 bitmap image. The number 1679 = 23×73 was chosen because it is a semiprime and therefore can only be broken down into 23 rows and 73 columns, or 73 rows and 23 columns.
( Wikipedia )
... is also used in RSA in its core.
I've written the article about it. The only difference is that I used CPU reigsters in the article which leads to modulo base like $2^{32}$ or $2^{64}$, while modulo bases in RSA are very large semiprimes.
Fermat little theorem states that if $p$ is prime, this congruence is valid for any $a$ in the environment of modulo artihemtic of base $p$:
There are proofs, which are, perhaps, too tricky for this article which is intended for beginners. So far, you can just take it as granted.
This theorem may be used to sieve prime numbers. So you take, for example, 10 and test it. Let's take some random $a$ value (123) (Wolfram Mathematica):
In[]:= Mod[123^(10 - 1), 10] Out[]= 3
We've got 3, which is not 1, indicating the 10 is not prime. On the other hand, 11 is prime:
In[]:= Mod[123^(11 - 1), 11] Out[]= 1
This method is not perfect (some composite p numbers can lead to 1, for example p=1105), but can be used as a method to sieve vast amount of prime numbers candidates.
... also used in RSA. Wikipedia link.
It is a number of coprime numbers under some n. Denoted as φ(n) or ϕ(n), pronounced as "phi".
For the sake of simplification, you may just keep in mind that if $n=pq$ (i.e., product of two prime numbers), $\varphi (pq)=(p-1)(q-1)$. This is true for RSA environment.
Euler’s theorem is generalization of Fermat little theorem. It states:
But again, for the sake of simplification, we may keep in mind that Euler's theorem in the RSA environment is this:
... where $n=pq$ and both $p$ and $q$ are prime numbers.
This theorem is central to RSA algorithm.
There are The Sender and The Receiver. The Receiver generates two big prime numbers ($p$ and $q$) and publishes its product ($n=pq$). Both $p$ and $q$ are kept secret.
For the illustration, let's randomly pick p and q among the first 50 prime numbers in Wolfram Mathematica:
In[]:= p = Prime[RandomInteger[50]] Out[]= 89 In[]:= q = Prime[RandomInteger[50]] Out[]= 43 In[]:= n = p*q Out[]= 3827
3827 is published as public key, named "public key modulus" or "modulo". It is semiprime. There is also public key exponent $e$, which is not secret, is often 65537, but we will use 17 to keep all results tiny.
Now The Sender wants to send a message (123 number) to The Receiver and he/she uses one-way function:
In[]:= e = 17 Out[]= 17 In[]:= encrypted = Mod[123^e, n] Out[]= 3060
3060 is encrypted message, which can be decrypted only using $p$ and $q$ values separately. This is one-way function, because only part of exponentiation result is left. One and important consequence is that even The Sender can't decrypt it. This is why you can encrypt a piece of text in PGP/GnuPG to someone using his/her public key, but can't decrypt it. Perhaps, that's how CryptoLockers works, making impossible to decrypt the files.
To recover message (123), $p$ and $q$ values must be known.
First, we get the result of Euler's totient function $(p-1)(q-1)$ (this is the point where $p$ and $q$ values are needed):
In[]:= totient = (p - 1)*(q - 1) Out[]= 3696
Now we calculating decrypting exponent using multiplicative modulo inverse (multiplicative inverse was also described in my previous article) ($e^{-1} \pmod{totient=(p-q)(q-1)}$):
In[]:= d = PowerMod[e, -1, totient] Out[]= 2609
Now decrypt the message:
In[18]:= Mod[encrypted^d, n] Out[18]= 123
So the $d$ exponent forms another one-way function, restoring the work of what was done during encryption.
It works, because $e$ and $d$ exponents are reciprocal to each other by modulo $totient=(p-1)(q-1)$:
In[]:= Mod[e*d, totient] (* check *) Out[]= 1
This allows...
In[]:= Mod[123^(e*d), n] Out[]= 123
So the encryption process is $m^{e} \pmod{n}$, decryption is $(m^{e})^{d}=m \pmod{n}$.
To prove congruence (1), we first should prove the following congruence:
... using modular arithmetic rules, it can be rewritten as:
$h$ is some unknown number which is present here because it's not known how many times the final result was rounded while exponentiation (this is modulo arithmetic after all).
So $m^{ed}=m \pmod{n}$ can be rewritten as:
...and then to:
The last expression can be simplified using Euler's theorem (stating that $a^{(p-1)(q-1)} \equiv 1 \pmod{n}$). The result is:
... or just:
We can try to factor $n$ semiprime (or RSA modulus) in Mathematica:
In[]:= FactorInteger[n]
Out[]= {{43, 1}, {89, 1}}
And we getting correct $p$ and $q$, but this is possible only for small values. When you use some big ones, factorizing is extremely slow, making RSA unbreakable, if implemented correctly.
The bigger $p$, $q$ and $n$ numbers, the harder to factorize $n$, so the bigger keys in bits are, the harder it to break.
In my example, public key is $n=pq$ (product) and secret key are $p$ and $q$ values stored separately. This is not very efficient, to calculate totient and decrypting exponent each time. So in practice, a public key is $n$ and $e$, and a secret key is at least $n$ and $d$, and $d$ is stored in secret key precomputed.
For example, here is my PGP public key:
dennis@...:~$ gpg --export-options export-reset-subkey-passwd --export-secret-subkeys 0x3B262349\! | pgpdump
Old: Secret Key Packet(tag 5)(533 bytes)
Ver 4 - new
Public key creation time - Tue Jun 30 02:08:38 EEST 2015
Pub alg - RSA Encrypt or Sign(pub 1)
RSA n(4096 bits) - ...
RSA e(17 bits) - ...
...
... so there are available openly big (4096 bits) $n$ and $e$ (17 bits).
And here is my PGP secret key: