Example of RSA encryption and decryption
1. choose two distinct prime numbers ( we will use
small numbers - to keep it simple - the actual
RSA algorithm would use far bigger numbers)
p = 13 and q = 19
2. Compute n = pq
so n = 13 * 19 = 247
3. compute φ(n) = (p-1)(q-1) which is
φ(247) = (13-1)(19-1) = 216
4. Now we have to pick a number e such that
1 < e < 216 and is coprime to 216
by choosing a prime number for e we only have to make
sure that it is not a divisor of 216
let e = 11
5. Compute d, the modular multiplicative inverse of 1/e(mod (φ(n))
which is:
d = 59
Getting the modular inverse is not a trivial problem - so I used a Math Cad
program called "scientific notebook" and here is the calculation:
(1/11)mod216= 59
Thus, we have :
public key is (n=247, e=11) and the private key is (n=247, d=59)
Let's look at our message "ATTACK"
The letter "A" is represented by decimal 65 so let's encrypt "A"
by using the public key. The private key is held by the recipient
let's call her Mary. So Bill who wants to send Mary a message
uses her public key and encrypts the message - then Mary
would use her private key to decrypt it.
ie, c = me ( mod n) : where m is the decimal value of "A".
(the first letter of Bill's message)
or
c = 6511 ( mod 247) = 221 so Bill's message would start off with
221 ..............( + other encrypted letters ) .....
Mary wants to decrypt the message: ie, calculate
m = cd (mod 247) : where c is the first letter
of the message.
or
m = 22159 ( mod 247) = 65 which is the decimal equivalent of "A"
Mary's decrypted message is :
"A" ...... + the other letters ...... OR "ATTACK"
You can use the microsoft calculator ( in scientific mode ) to
do the other letters and have your friends try to break the coded message.
Remember it is not a simple key as explained on the pc technician home
page where Encryption basics are explained.
|
