WOLFRAM|DEMONSTRATIONS PROJECT

RSA Encryption and Decryption

​
message
compose
send
decrypt
public key
three
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
letter
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
message
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Alice
3149 17
plaintext: XYZ

Bob
893
ciphertext:
082112311242
message: XYZ
The RSA algorithm for public-key encryption was originated by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT in 1977. Several similar methods had been proposed by earlier workers. The algorithm is based on the fact that it is far more difficult to factor a product of two primes than it is to multiply the two primes. Even the most powerful modern supercomputers would require more time than the age of the universe to factor a 400-digit number. (This might change if quantum computers ever become operational.)
In this Demonstration, the RSA algorithm is simulated using much smaller randomly chosen prime numbers,
p
and
q,
both less than 100. The public key, which is made freely available to Alice and all other users, consists of the two numbers
N=pq
and an exponent
E
, which is an odd integer relatively prime to
ϕ(N)
between 1 and
ϕ(N)=(p-1)(q-1)
. (Here
ϕ(N)
is Euler's totient function, the number of positive integers less than
N
and relatively prime to
N
.) For simplicity, take
E=17
and also limit messages to three letters, such as XYZ. This constitutes the plaintext and is converted into an integer
M
using, for example, ASCII codes. The corresponding ciphertext
C
is computed using
C=
E
M
(modN)
.
Only the recipient Bob has access to the private key, which is an integer exponent
D
, a modular inverse to
E
such that
DE=1(mod
ϕ(N))
. To determine
D
, a codebreaker would need to find the prime factors of
N
, which, as noted earlier, is hopefully impossible. The plaintext is recovered using
M=
D
C
(modN)
. The method works since
M=
ED
M
(mod
N
), with application of Fermat's little theorem. The public and private keys can periodically be changed according to some prearranged schedule.
By inputting the public key
(N,E)
and the three-part ciphertext
C
, Bob can recover the plaintext message.