s
Section 5.6 The Mighty Mod Function
433
example 54
Using RSA encryption/decryption, let p = 17 and q = 13. Then n = 221 and
w(n) = 16 # 12 = 192. Pick e = 11; e and w(n), 11 and 192, are relatively prime.
Using the Euclidean algorithm, with 11 and 192,
192 = 17 # 11 + 5
or
5 = 192 − 17 # 11
11 = 2 # 5 + 1
or
1 = 11 − 2 # 5
5 = 5 # 1 + 0
from which
1 = 11 − 2 # 5 = 11 − 2 3192 − 17 # 11 4 = 35 # 11 − 2 # 192
which gives a value for d of 35. If the integer T = 8, then 8 is encoded as follows,
where the tedious modulo arithmetic can be broken down using Equation (1). The
encoding key is (n, e) and both values are used in the computation.
8
11
mod 221 = 8
3 # 8
3 # 8
3 # 8
2
mod 221
= 512 # 512 # 512 # 64 mod 221
= 70 # 70 # 70 # 64 mod 221
= 4900 # 4480 mod 221
= 38 # 60 mod 221
= 2280 mod 221
= 70
To decode the encrypted value 70, compute
70
35
mod 221 = (70
2
)
17 # 70 mod 221 = (4900)
17 # 70 mod 221
= 38
17 # 70 mod 221 = (38
2
)
8 # 38 # 70 mod 221
= (1444)
8 # 38 # 70 mod 221 = (118)
8 # 38 # 70 mod 221
= 3(118)
2
4
4 # 38 # 70 mod 221 = (13924)
4 # 38 # 70 mod 221
= 1
4 # 38 # 70 mod 221 = 2660 mod 221 = 8
which was the original encoded integer
This is not a realistic example because p and q (and n) are relatively small.
But even here the computations are quite tedious. Again, a spreadsheet and its mod
function will be helpful.
■
PRaCtiCe 47 Assume you receive a ciphertext message of 166 that was encoded using your public key
(n, e) from Example 54. Decode the message to obtain the original integer T.
Hashing for Password Encryption
The user of a computer system typically has to enter a user ID and password to
authenticate him or her as a legitimate user, a person entitled to use these computing resources. The list of user IDs and corresponding passwords must be stored