# Definition:RSA Algorithm

## Definition

The **RSA algorithm** is a technique of encoding a message such that the method of encoding can be made public without compromising the security.

Let Alice be sending a message to Bob.

Alice and Bob both agree on two large primes $p$ and $q$, each having at least $100$ digits.

Let $M = p q$.

$M$ can be made public if they so wish.

Let $K = \left({p - 1}\right) \left({q - 1}\right)$.

$K$ is to be kept secret.

Let Alice choose some number $a$ such that $a \perp K$.

$a$ is made known to Bob, and may even be made public.

Alice represents her message in a series of numbers in the range $0$ to $M$.

Let $x$ be one such number.

Alice calculates $y \equiv x^a \pmod M$.

The sequence of numbers $y$ is sent to Bob as the coded message.

Bob needs to know a number $b$ such that $a b \equiv 1 \pmod K$.

This number needs to be kept secret.

To decode $y$, Bob computes $y^b \pmod M$.

This works because of Fermat's Little Theorem:

- $y^b \equiv \left({x^a}\right)^b \equiv x^1 = x \pmod M$

The method works because:

- $(1): \quad$ There are efficient tests to find large primes

- $(2): \quad$ There are no known methods for finding the prime factors of large numbers efficiently.

So making $p q$ public does not help $p$ and $q$ be found, and without those it is impossible to work out what $b$ is.

## Source of Name

This entry was named for Ronald Linn Rivest, Adi Shamir and Leonard Max Adleman.

## Sources

- 1986: David Wells:
*Curious and Interesting Numbers*... (previous) ... (next): '$..........$' - 1997: David Wells:
*Curious and Interesting Numbers*(2nd ed.) ... (previous) ... (next): '$..........$' - 2008: Ian Stewart:
*Taming the Infinite*... (previous) ... (next): Chapter $7$: Patterns in Numbers: Gauss