RSA Encryption

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

$$n\equiv pq$$ (1)

for $p$ and $q$ Primes. Also define a private key $d$ and a public key $e$ such that

$$de\equiv 1\ \left({{\rm mod\ } {\phi(n)}}\right)$$ (2)

$$(e,\phi(n))=1,$$ (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

$$E = M^e {\rm\ (mod\ } n).$$ (4)

To decode, the receiver (who knows $d$) computes

$$E^d \equiv (M^e)^d \equiv M^{ed} \equiv M^{N\phi(n)+1} \equiv M {\rm\ (mod\ } n),$$ (5)

since $N$ is an Integer. In order to crack the code, $d$ must be found. But this requires factorization of $n$ since

$$\phi(n)=(p-1)(q-1).$$ (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

$$p = 2p_1+1$$ (7)

$$q = 2q_1+1,$$ (8)

where

$$p_1 = 2p_2+1$$ (9)

$$q_1 = 2q_2+1,$$ (10)

and $p$, $p_1$, $p_2$, $q$, $q_1$, and $q_2$ are all Primes. In this case,

$$\phi(n) = 4p_1q_1$$ (11)

$$\phi(\phi(n)) = 8p_2q_2.$$ (12)

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

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.