Category:Definitions/RSA Algorithm

This category contains definitions related to RSA Algorithm.
Related results can be found in Category:RSA Algorithm.

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 = \paren {p - 1} \paren {q - 1}$.

$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 \paren {x^a}^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.