The RSA Encryption Algorithm is a mathematical method of generating two encryption keys. You then encrypt a message with one key, and decrypt it using the other key.

This allows you to keep one key private, and publish the other key to the entire world.

Then there are two ways you can use these keys:

- You
look up the public key of your friend, and encrypt a message using
key. You have guaranteed that no-one can read the message**their public**your friend.**except**

- You
encrypt a message using
key. Everyone can read it, but no-one else**your private**could have**but you****sent it.**

__, and__

**keep secrets**__Cool.__

**prove identity.**So how can you get two keys that encrypt and decrypt like this?

It turns out that it's possible using the simple mathematical fact that it's easy to multiply numbers together, but much harder to break a number down into its factor.

First we need to find two primes (p and q). RSA generates random numbers and uses the Fermat Primality Test to find these primes. Well there's actually more to it than this – RSA doesn't generate the random numbers in a

__random fashion – it does some extra checks to ensure that the resultant keys are hard to factor, but the concept is the same.__

**purely**Then we multiply the primes together to get a modulo, n. Because we know what the two primes were, it is easy for us to calculate the totient of n $\varphi(n) = (p – 1)(q – 1)$. (There are p – 1 numbers coprime to p, and q – 1 numbers coprime to q. The total number of coprime values are just the multiple of these.)

Then we look (randomly) for a number e that is coprime to $\varphi(n)$. This can be tested by using the Euclidean Algorithm. Once we've found this, the number pair e and n become one of our encryption keys.

If e and n are coprime, we can use the Extended Euclidean Algorithm to find:

$x
\cdot e + y \cdot \varphi(n) = gcd(n,e)$

$d
\cdot e + y \cdot \varphi(n) = 1$

$d
\cdot e = 1 + y \cdot \varphi(n)$

$d
\cdot e = 1 \text{ mod } \varphi(n)$

d
in this case represents the inverse of e mod $\varphi(n)$.Why do we do this? Because we already know from the Euler-Fermat Theory, that raising any message m (that is coprime to n) to the power of $\varphi(n)$, we end up at 1.

We could try to factor $\varphi(n) + 1$ into two values $e \times d = \varphi(n)$ so that $(m^{e})^{d} = m^{\varphi(n)+1} = 1 \times m$. But the whole point is that we want to avoid factoring numbers if at all possible.

By finding the multiplicative inverse of e (mod $\varphi(n)$), we are instead using $(m^{e})^{e^{-1}} = m^1 = m$. The

__reason this approach works, is because we wrap around every $\varphi(n)$.__

**only**Here's an example using the two primes p = 21 and p = 19.

$n
= 21 \times 19$

$n
= 399$

$\varphi(n)
= (p – 1) (q – 1) $

$\varphi(n)
= 20 \times 18 $

$\varphi(n)
= 180$

I
used python to select a random Integer e
= 31
that is coprime to 180. (Verified by the Euclidean Algorithm).Then using the Extended Euclidean Algorithm to find the inverse of 31 mod 180.

q | r | x | y |
---|---|---|---|

180 | 1 | 0 | |

31 | 0 | 1 | |

5 | 25 | 1 – 5 * 0 = 1 | 0 – 5* 1 = -5 |

1 | 6 | 0 – 1* 1 = – 1 | 1 – 1 * – 5 = 6 |

4 | 1 | 1 – 4 * – 1 = 5 | -5 – 4 *6 = – 29 |

4 | 0 |

$
180 \times 5 + 31 \times – 29 = 1$

So:
$31^{-1}
= – 29 \text{ mod } 180$

$31^{-1}
= 151$

Checking:
$31
\times 151 = 4681 = 26 \times 180 + 1 = 1 \text{ mod } 180$

Finally, lets test this by encoding a message. We have to ensure that the message is in a numerical format, and that it is coprime to n. We'll pretend that we've already converted a message into the number 14 (One of my favourite numbers).

To encode the message, we want to calculate:

$14^{31} \text{ mod } 399$

Sagemath
has a power_mod method that efficiently calculates this value as:
power_mod(14,31,399)
= 287

$
287^{151} \text{ mod } 399$

power_mod(287,151,399)
= 14.

using
only the message and the published key (151, 399).There's a lot more to the RSA Algorithm that ensures it is secure. For example, we've used a message that is a pretty small value. If all our messages are this small (say the 17 most commonly used letters of the alphabet represented by the numbers 1 to 17), it may be possible to guess the private key. Using a hash ensures that the possible message is spread out across a lot of possibilities. Also, the bigger the primes, the more secure the encryption will be.

## No comments:

## Post a Comment