I am having a complete mental block understanding decryption with public and private keys. In my head, I am (apparently) falsely equating decryption to using a *Little Orphan Annie* decoder ring like in the movie *A Christmas Story*.
If a block of data was encrypted with a key, I can’t understand how a another key that is completely different is able to decrypt that data. I know there’s a fair bit of complex math involved, but if you multiple X by Y to get Z, then the only way to get X back from Z is to divide by Y.
* data->public key->encrypted->private key->data
* data->private key->encrypted->public key->data
* data->public key->encrypted->public key->error
* data->private key->encrypted->private key->error
In: 2
> if you multiply X by Y to get Z, then the only way to get X back from Z is to divide by Y
This is true in ℝ (real numbers, the numbers you learn about in school). However, cryptography schemes usually don’t use familiar numbers like ℝ (real numbers) or ℤ (real numbers).
If you use RSA cryptography (the oldest and simplest public key cryptography system), you use ℤ_n (integers modulo n). The elements of ℤ_n look like ordinary integers between 0 and n, but adding or multiplying them has an extra step: You divide by n and take the remainder.
For example if you work in ℤ_2173, you might pick a public key of 1776 and then calculate the private key as 2069. Normally (with the ordinary integers ℤ) you’d have 1776 x 2069 = 3674544, but in ℤ_2173 you have the extra step where you divide by 2173 and take the remainder. The remainder of 3674544 divided by 2173 is 1. So in ℤ_2173, it is actually a fact that 1776 x 2069 = 1.
You might have some questions:
– (1) Why did I pick 2173?
– (2) How did I know 2069 is the number that, when multiplied by 1776, gives 1?
And I have some answers:
– In the RSA cryptosystem, you pick the modulus n by picking two prime numbers p, q and multiplying them together. I picked p = 41 and q = 53, so 2173 = 41 x 53 (in ℤ).
– Calculate ϕ = (p-1)(q-1). In this case ϕ = 40 x 52 = 2080. [1]
– Raise 1776 to the ϕ-1th power. Divide by 2173 and take the remainder. [2]
– 1776^2079 is a huge number (6756 digits), but divide it by 2173 and take the remainder and you get 2069.
You then keep 2069 as your private key, and publish 1776 as your public key along with the modulus 2173. In principle a hacker could factor 2173 to get back 41 and 53, then do the same calculation themselves to calculate your private key and read your messages. In practice you’d use enormous numbers (think hundreds of digits), so the hacker would need unrealistic amounts of computing power to factor n (think millions of computers running for thousands of years).
[1] This calculation actually counts the number of elements of ℤ_2173 that aren’t divisible by 41 or 53. Counting these elements in ℤ_n is an important enough calculation that it is a named function (Euler’s totient function) and [has its own Wikipedia page](https://en.wikipedia.org/wiki/Euler%27s_totient_function).
[2] You can use the [exponentiation by squaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring) method. Also, you can divide by 2173 and take the remainder on intermediate steps without affecting the result. Optimize the computation.
Latest Answers