Category:Definitions/RSA Algorithm

From ProofWiki
Jump to navigation Jump to search

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.

Pages in category "Definitions/RSA Algorithm"

The following 4 pages are in this category, out of 4 total.