Before getting in RSA, we would briefly discuss a very important maths topic, on which the RSA greatly depends, Modular arithmetics.
Modular Arithmetics
In general, we can consider numbers modulo n, where n is any positive integer. This means that we divide a number by n, and just look at the remainder. The quotient is discarded. Each remainder has to be a whole number r such that 0 ≤ r < n.
For example,
23 ≡ 1 (mod 11).
This is read as ‘23 is congruent to 1 modulo 11’.
Here are some other examples:
80 ≡ 8 (mod 9), 40 ≡ 2 (mod 19), 20 ≡ 2 (mod 3).
The idea can be extended to the negative integers. For example, we divide
−50 by 6
as follows:
−50 = −9×6+4.
Here the remainder has to be a whole number r
such that 0 ≤ r < 6. We can write
−50 ≡ 4 (mod 6).
Congruence modulo n
The integers 18 and 58 are both congruent to 2 modulo 8, so we say they are congruent to each other:
58 ≡ 18 (mod 8).
We could have checked this directly by subtracting 18 from 58:
we have 58 − 18 = 40,
which is a multiple of 8.
we would use the following modular exponentiation rules for solving RSA problems:
Example:
1. 2468 ≡ a (mod 7)
2468 / 7 = 352 remainder 4
We have 2468 = 352×7+4.
Hence, 2468 ≡ 4 (mod 7),
and therefore a = 4.
2. 2242 ≡ a (mod 3)
We have 2242 = (22 )121 ≡ 1121 (mod 3)
since 22 ≡1 (mod 3).
Therefore a = 1.
3. 3245 ≡ a (mod 5)
We have 3245 = 34×61+1
≡ (34x61)×3 (mod 5) ≡161×3 (mod 5) ≡ 3 (mod 5).
since 34 ≡ 1 (mod 5)
Therefore a = 3.
4. 6545 ≡ a (mod 12).
We have 654 ≡ 6 (mod 12) then.
We have 6542 ≡ 62 (mod 12) then.
We have 6542 ≡ 36 (mod 12) ≡ 0 (mod 12) then.
We have 6545 ≡ (6542) 2 + 1 (mod 12)
We have 6545 ≡ (0) 2 + 1 (mod 12)
and so a = 0.
A first look at RSA:
In 1978, Ron Rivest, Adi Shamir, and Leonard Adleman introduced a cryptographic algorithm, RSA which was essentially to replace the less secure National Bureau of Standards (NBS) algorithm. Most importantly, RSA implements a public-key cryptosystem, as well as digital signatures. RSA is motivated by the published works of Diffie and Hellman from several years before, who described the idea of such an algorithm, but never truly developed it.
The RSA public-key/two-key/asymmetric cryptography involves the use of two keys:
– a public-key, which may be known by anybody, and can be used to encrypt messages, and verify signatures
– a private-key, known only to the recipient, used to decrypt Public-Key Cryptography
The public-key for encrypting a message may be made public, without compromising the secrecy of the method of decryption. This is also called public-key encryption. It is usually referred to as asymmetric because – those who encrypt messages or verify signatures cannot decrypt messages or create signatures but if the Private key is disclosed communications are compromised
Take a number, raise it to some exponent, divide by the modulus and output the remainder. This can be used to encrypt a message as follows.
Imagine Bob(Participant A) has a message which is converted into a number m. He then multiplies his number by itself, e times where e is a public exponent. Then he divides the result by a random number n and outputs the remainder of the division,
me mod n = c -----eqn1
This results in some numbers c also referred to the cipher text or encrypted message. However, given only c, e and n, it is much more difficult to determine which m was used, because we'd have to resort to some form of trial and error. So this is our one way function that we can apply to m, easy to perform but difficult to reverse, it is our mathematical lock.
Now, what about the key.
The key or private key is some piece of information that makes it easy to reverse the encrypted message c. To decrypt the message, We need to raise the encrypted message c to some other exponent, say d, which will undo the initial operation applied to m, and return the original message m.
Ce mod n = m ---eqn2
So both operations of encryption and decryption together is the same as m to the power of e all raise to the power of d, which is the same as m to the power of e times d. e is the encryption, d is the decryption.
Med mod n = m ---eqn3
Therefore, we need a way for Alice(participant B) to construct e and d, which makes it difficult for anyone else to find d. This requires a second one way function which is used for generating d.
Prime Factorization
Over 2000 years ago Euclid showed every number has exactly one prime factorization, which we can think of as a secret key. It turns out that prime factorization is a fundamentally hard problem.
Each natural number greater than 1 can be factorised as a product of powers of primes. Moreover, if we ignore the order of the prime powers, then there is only one way to do this. For example, we can write
60 = 22 ×3×5.
There are infinitely many prime numbers. Using a computer, it is relatively easy to find lots of large prime numbers. At present, however, it is very difficult to find the prime factorisation of a very large number. This is what makes RSA encryption so hard to crack.
If someone told you to find the prime factorization of 589, you will notice the problem, feels harder. No matter what your strategy, it will require some trial and error until you find a number which evenly divides 589 After some struggle, you will find 19 times 31 is the prime factorization.
If you were told to find the prime factorization of 437,231, you probably give up and get a computer to help you. This works fine for small numbers, though if we try to get a computer to factor in larger and larger numbers, there is a runaway effect. The time needed to perform the calculations increases rapidly as there are more steps involved as the numbers grow the computer needs minutes then hours and eventually it will require hundreds or 1000s of years to factor huge numbers. We therefore say it is a hard problem.
Due to this growth rate of time needed to solve it. So factorization is what was used to build the trapdoor solution step one.
Imagine Alice randomly generated a prime number over 150 digits long call this P1, then a second random prime number roughly the same size, call this P2. She then multiplies, these two primes together to get a composite number n, which is over 300 digits long. This multiplication step would take less than a second, we could even do it in a web browser. Then she takes the factorization of n = P2 * P2 and hides it.
Now if she gave, n to anyone else. They would have to have a computer running for years to find the solution.
Then, we need to find a function which depends on knowing the factorization of n. For this we looked back to work done in 1760 by Swiss mathematician, Leonard Euler. Euler continue to investigate properties of numbers, specifically, the distribution of prime numbers. One important function he defined is called the Phi function(ᶲ).
Phi function(ᶲ). It measures the break ability of a number. So, given a number say n, it outputs, how many integers are less than or equal to n, that do not share any common factor with n. For example, if we want to find the PHI of eight (ᶲ8), we look at all values from one to eight,1,2, 3, 4, 5, 6, 7, 8.
then we count how many integers, eight does not share a factor greater than one with, notice six is not counted because it shares a factor of two. 1, 3, 5, 7 are all counted because they only share a factor of one. Therefore, ᶲ8 equals four. What's interesting is that calculating the ᶲ function is hard, except in one case, Since prime numbers have no factors greater than one, the phi of any prime number P is simply P – 1.
To calculate ᶲ7 a prime number, we count all integers except seven Since none of them share a factor with 7. ᶲ7 equals six. So if you're asked to find ᶲ of 21,377 A prime number, you would only need to subtract one to get the solution 21,376. ᶲ of any prime is easy to compute. This leads to an interesting result based on the fact that the phi function is also multiplicative that is ᶲ( A*B) equals ᶲA times ᶲB.
ᶲ[A*B] = ᶲ[A] * ᶲ[B]
e.g ᶲ[3*4] = ᶲ[3] * ᶲ[4]
note: ᶲ[12] = 4 = 1, 3, 5, 7…..
ᶲ[3] = 2 = 1, 2……
ᶲ[4] = 2 = 1, 3
= ᶲ[12] = 2 * 2
4 = 4
If we know some number n is the product of two primes P1 and P2, then ᶲ of n is just the value of ᶲ for each prime multiplied together.
ᶲ [n] = (P1-1) * (P2-1)
We now have a trapdoor for solving ᶲ, if you know the factorization for n, then finding ᶲ[n] is easy. For example,
the prime factorization of 77 is equal to 7 x 11.
So ᶲ[77] = (7-1) x (11-1).
ᶲ[77] = 6 x 10 = 60.
So next step is how do we connect this ᶲ function to modular arithmetics used in RSA.
For this he turned to Eulers theorem, which is a relationship between the ᶲ function and modular exponentiation as follows, m to the power of ᶲn is congruent to 1 mod n.
Mᶲ(n) = 1 mod n
This means you could pick any two numbers such that they do not share a common factor, let's call them, m and n say m equals five, and n equals eight. Now when you raise, m to the power of ᶲn, or 4, and divide by n, you will always be left with 1.
5ᶲ(8)=4 ≡ I mod n
625 ≡ 1 mod 8
Given m=5, n≡8
Now we just need to modify this equation using two simple rules. First, if you raise the number one to any exponent K, you always get 1
1k =1 ------rule 1
in the same way we can multiply the exponent ᶲn by any number k, and the solution is still one
mk * ᶲ(n) ≡ 1 mod n ---------eqn 3
second, if you multiply one by any numbers say m. It always equals n.
1 x m = m------------rule 2
In the same way we can multiply the left side by n to get m on the right hand side. Eqn 3 becomes
M x mk * ᶲ(n) ≡ m mod n ----- 4
And this can be simplified as m to the power of k times ᶲn + 1.
Mk * ₽ᶲ(n) + 1 ≡ m mod n -----5
This is the breakthrough. We now have an equation for finding e x d, which depends on phi, and therefore, it's easy to calculate d, only if the factorization of n is known, by comparing eqn5 to eqn 2
mk * ᶲ(n) + 1 = me x d ≡ m mod n
e x d = k * ᶲ(n) + 1 ----------6
d = (k * ᶲ(n) + 1 )/e ----------------7
meaning d should be Alice's private key is the trapdoor which will allow her to undo the effect of e. Let's do a simple example to see all of this in action.
We start with another example to refresh our memories of the process. We again use small numbers to make the example easier to read, but of course this is not secure.
Step 1. Choose two primes p and q. Example: p = 5 and q = 13.
Step 2. Let n = pq. Example: n = 5×13 = 65.
Step 3. Let A=₽ᶲ(n) = (p −1)(q −1). Example: A = 4×12 = 48.
Step 4. Choose an integer E with 1 < E < A such that E and A are relatively prime. That is they both share no common factor i.e gcd(E, A)=1.
Example: Choose E = 11.
Step 5. Let D be the multiplicative inverse of E modulo A. That is, find the unique integer D with 1 < D < A such that D ×E −1 is a multiple of A.
Example: As (35×11)−1 = 384 = 8×48, we have D = 35.
Encryption steps:
To encrypt a number, we first raise it to the power E = 11,
and then find its remainder when we divide by n = 65.
For example, to encrypt 3, we find 3 11 = 177, 147.
Since 177, 147 = 2725×65+22, the remainder is 22.
So 3 encrypts as 22.
We can write 3 11 ≡ 22 (mod 65).
Decryption
We take 22 to the power D = 35, and find its remainder when we divide by n = 65.
We can use some of the properties of modular arithmetic which we developed earlier to help with this. We will break up 35 as 24+10+1.
We have 222 ≡ 29 (mod 65) and,
conveniently, 296 ≡ 1 (mod 65).
So 2212 ≡ 1 (mod 65)
and therefore 2224 ≡ 1 (mod 65).
Since 222 ≡ 29 (mod 65) and 295 ≡ 9 (mod 65),
we have 2210 ≡ 9 (mod 65).
Finally, we obtain 2235 = 2224 ×2210 ×22 ≡ 1×9×22 (mod 65) ≡ 3 (mod 65).
Another Example
Step 1. Choose two primes p and q. Example: p = 3 and q = 11. Step 2. Let n = p × q. Example: n = 3×11 = 33. Step 3. Let A = (p −1)(q −1). Example: A = 2×10 = 20. Step 4. Choose an integer E with 1 < E < A such that E and A have no common factors other than 1. Example: Choose E = 7. Step 5. Find the integer D with 1 < D < A such that D ×E −1 is a multiple of A. Example: As (3×7)−1 = 20, we have D = 3.
The numbers n and E are the public key, they can be shared with anyone. The number D is the private key, it must be kept secret.
How do we use it?
Lily wants to be able to receive a secret message from Frank. She sends him the values of n and E. It doesn’t matter if this message is intercepted; the values of n and E can be made public. Only Lily knows the value of D.
When data is sent securely over the internet, it is protected by a system like this. Anyone can encrypt, but only the authorised recipient can decrypt. Let us see how to employ it.
Before a message can be encrypted, it must be converted into a number (or a sequence of numbers). The number must be less than n. Since n is so small in our example, we will assign distinct numbers (each less than n) to the letters of the alphabet, and encrypt our message one letter at a time.
Suppose the message is ‘HELP’. For simplicity, we suppose that the letters H, E, L and P were assigned the numbers 2, 3, 4 and 5, respectively.
H E L P
2 3 4 5
The next step is to raise each of these numbers to the power E = 7.
128 2187 16384 78125
Then find the remainders when each of these numbers is divided by n = 33. For example, we have 128 = 3×33+29, and so 128 gives a remainder of 29.
29 9 16 14
The encrypted message to be sent is 29 9 16 14.
The method for decryption is similar, but we use D instead of E. Start with the encrypted message.
29 9 16 14
Raise each number to the power D = 3.
24,389 729 4096 2744
Find the remainders when each number is divided by n = 33.
2 3 4 5
This is the original message.
Some security issues
There are two very big problems with this example. The first problem is the size of the primes. The number n = 33 is public. It is clear that our two primes must be 3 and 11, and so A = 20. Since E = 7 is also public, is it easy to work out the decryption key D.
This problem is overcome by using much larger primes. The two primes p and q should be chosen to have roughly the same size; in practice, they would each have over 150 decimal digits.
The second problem is that we have encrypted one letter at a time. This means, of course, that each letter will always have the same value once encrypted. This immediately makes the cipher easy to break by using a simple frequency count.
This problem is overcome by grouping letters together, and encrypting each group as a single number. For example, the ASCII codes for the letters H, E, L and P are 72, 69, 76 and 80, respectively. So, if n were large enough, we could convert the word ‘HELP’ into the single number 72 697 680.