info prev up next book cdrom email home

RSA Encryption

A Public-Key Cryptography Algorithm which uses Prime Factorization as the Trapdoor Function. Define

\begin{displaymath}
n\equiv pq
\end{displaymath} (1)

for $p$ and $q$ Primes. Also define a private key $d$ and a public key $e$ such that
\begin{displaymath}
de\equiv 1\ \left({{\rm mod\ } {\phi(n)}}\right)
\end{displaymath} (2)


\begin{displaymath}
(e,\phi(n))=1,
\end{displaymath} (3)

where $\phi(n)$ is the Totient Function.


Let the message be converted to a number $M$. The sender then makes $n$ and $e$ public and sends

\begin{displaymath}
E = M^e {\rm\ (mod\ } n).
\end{displaymath} (4)

To decode, the receiver (who knows $d$) computes
\begin{displaymath}
E^d \equiv (M^e)^d \equiv M^{ed} \equiv M^{N\phi(n)+1} \equiv M {\rm\ (mod\ } n),
\end{displaymath} (5)

since $N$ is an Integer. In order to crack the code, $d$ must be found. But this requires factorization of $n$ since
\begin{displaymath}
\phi(n)=(p-1)(q-1).
\end{displaymath} (6)

Both $p$ and $q$ should be picked so that $p\pm 1$ and $q\pm 1$ are divisible by large Primes, since otherwise the Pollard p-1 Factorization Method or Williams p+1 Factorization Method potentially factor $n$ easily. It is also desirable to have $\phi(\phi(pq))$ large and divisible by large Primes.


It is possible to break the cryptosystem by repeated encryption if a unit of $\Bbb{Z}/\phi(n)\Bbb{Z}$ has small Order (Simmons and Norris 1977, Meijer 1996), where $\Bbb{Z}/s\Bbb{Z}$ is the Ring of Integers between 0 and $s-1$ under addition and multiplication (mod $s$). Meijer (1996) shows that ``almost'' every encryption exponent $e$ is safe from breaking using repeated encryption for factors of the form

$\displaystyle p$ $\textstyle =$ $\displaystyle 2p_1+1$ (7)
$\displaystyle q$ $\textstyle =$ $\displaystyle 2q_1+1,$ (8)

where
$\displaystyle p_1$ $\textstyle =$ $\displaystyle 2p_2+1$ (9)
$\displaystyle q_1$ $\textstyle =$ $\displaystyle 2q_2+1,$ (10)

and $p$, $p_1$, $p_2$, $q$, $q_1$, and $q_2$ are all Primes. In this case,
$\displaystyle \phi(n)$ $\textstyle =$ $\displaystyle 4p_1q_1$ (11)
$\displaystyle \phi(\phi(n))$ $\textstyle =$ $\displaystyle 8p_2q_2.$ (12)

Meijer (1996) also suggests that $p_2$ and $q_2$ should be of order 1075.


Using the RSA system, the identity of the sender can be identified as genuine without revealing his private code.

See also Public-Key Cryptography


References

Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 166-173, 1985.

Meijer, A. R. ``Groups, Factoring, and Cryptography.'' Math. Mag. 69, 103-109, 1996.

Rivest, R. L. ``Remarks on a Proposed Cryptanalytic Attack on the MIT Public-Key Cryptosystem.'' Cryptologia 2, 62-65, 1978.

Rivest, R.; Shamir, A.; and Adleman, L. ``A Method for Obtaining Digital Signatures and Public Key Cryptosystems.'' Comm. ACM 21, 120-126, 1978.

RSA Data Security. ${}^{\scriptstyle\circledRsymbol}$ A Security Dynamics Company. http://www.rsa.com.

Simmons, G. J. and Norris, M. J. ``Preliminary Comments on the MIT Public-Key Cryptosystem.'' Cryptologia 1, 406-414, 1977.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-25