The RSA Algorithm
The following is an adaptation from Section 4.6.5 of your textbook. Let \(n = p \times q\) be the product of two
primes \(p\) and \(q\). Let
- \(e \in [3\ldots n)\) be co-prime to \((p-1)\times(q-1)\), and let
- \(d = e^{-1} \pmod{(p-1)\times(q-1)}\). This exists by Bézout's theorem.
We'll only encrypt short messages in this demo comprising uppercase letters only. The
encoding is very similar to the one described in your textbook. We'll first encode the
message into a number by
converting every letter to two digits ranging from \(01\ldots26\). Thus, the message "A" is encoded
as 01, "AB" is encoded as 0102, and so on. The word "STOP" for example is encoded as
\(19{\color{red}20}15{\color{red}16}\).
To encrypt a message \(m\)—a number actually, you compute \(m^e \pmod{n}\), and to decrypt an
encrypted message, you raise the cyphertext \(c\) (also a number) to the power \(d\), i.e.,
\(c^d \pmod{n}\). To uniquely decrypt an encryption, the message must be \(< n\). In other words,
\(m^e\) is a bijection from \([0\ldots n) \rightarrow [0\ldots n)\).
The demo will generate random RSA parameters, encode the message, encrypt it, and then decrypt it
for sanity checking.
Type a short message consisting only of uppercase letters, for e.g., ATTACK, PARIS, ARREST.