Homework 3 – Aqila Dissanayake
My full name is = Aqila Nandaka Charith Dissanayake
AqilaNandakaCharithDissanayake
A = 65 Cumulative Total = 65
q = 113 Cumulative Total = 178
i = 105 Cumulative Total = 283
l = 108 Cumulative Total = 391
a = 97 Cumulative Total = 488
N = 78 Cumulative Total = 566
a = 97 Cumulative Total = 663
n = 110 Cumulative Total = 773
d = 100 Cumulative Total = 873
a = 97 Cumulative Total = 970
k = 107 Cumulative Total = 1077
a = 97 Cumulative Total = 1174
C = 67 Cumulative Total = 1241
h = 104 Cumulative Total = 1345
a = 97 Cumulative Total = 1442
r = 114 Cumulative Total = 1556
i = 105 Cumulative Total = 1661
t = 116 Cumulative Total = 1777
h = 104 Cumulative Total = 1881
D = 68 Cumulative Total = 1949
i = 105 Cumulative Total = 2054
s = 115 Cumulative Total = 2169
s = 115 Cumulative Total = 2284
a = 97 Cumulative Total = 2381
n = 110 Cumulative Total = 2491
a = 97 Cumulative Total = 2588
y = 121 Cumulative Total = 2709
a = 97 Cumulative Total = 2806
k = 107 Cumulative Total = 2913
e = 101 Cumulative Total = 3014
3014 mod 23 = 1
1 + 1 = 2
So, 2nd Question
9.2 / Perform encryption and decryption using the RSA algorithm, as in Figure 9.6, for the following:1. p = 3; q = 11, e = 7; M = 5
2. p = 5; q = 11, e = 3; M = 9
3. p = 7; q = 11, e = 17; M = 8
4. p = 11; q = 13, e = 11; M = 7
5. p = 17; q = 31, e = 7; M = 2. Hint: Decryption is not as hard as you think; use some finesse.
(1) p = 3; q = 11, e = 7; M = 5
Encryption
Ciphertext (C) = Memod n
C = 5^7 mod (p * q)
C = 5^7 mod (3 * 11) = 5^7 mod (33)
C = [ (5^4 mod 33) * (5 ^ 2 mod 33) * (5 ^ 1 mod 33) ] mod 33
C = [ (625 mod 33) * (25 mod 33) * (5 mod 33) ] mod 33
C = [ 31 * 25 * 5 ] mod 33
C = [ 3875] mod 33
C = 14
Decryption
Plaintext (M) = Cdmod n
Need to calculate d
e and d are multiplicative inverses mod f(n).
f(n) = (p – 1) (q – 1)
f(n).= (3 -1) (11 – 1) = 2 * 10 = 20
The multiplicative inverse of
e mod 20 = 7 mod 20 = 3
So, lets calculate Cdmod n
14 ^ 3 mod (n) = 14 ^ 3 mod (p * q) = 14 ^ 3 mod (33)
2744 mod 33 = 5
Therefore a successful decryption gets the original plaintext 5
(2) p = 5; q = 11, e = 3; M = 9
Encryption
Ciphertext (C) = Memod n
C = 9^3 mod (p * q)
C = 9^3 mod (5 * 11) = 729 mod (55)
C = 14
Decryption
Plaintext (M) = Cdmod n
Need to calculate d
e and d are multiplicative inverses mod f(n).
f(n) = (p – 1) (q – 1)
f(n).= (5 -1) (11 – 1) = 4 * 10 = 40
The multiplicative inverse of
e mod 40 = 3 mod 40 = -13
Therefore the positive multiplicative inverse of 3 mod 40 is = 27
So, lets calculate Cdmod n
14 ^ 27 mod (n) = 14 ^ 27 mod (p * q) = 14 ^ 27 mod (55)
[(14 ^ 16 mod 55) * (14 ^ 8 mod 55) * (14 ^2 mod 55) * (14 ^ 1 mod 55)] mod 55
[(14 ^ 8 mod 55) * (14 ^ 8 mod 55) * (14 ^ 8 mod 55) * (14 ^2 mod 55) * (14 ^ 1 mod 55)] mod 55
[(14 ^ 4 mod 55) * (14 ^ 4 mod 55) * (14 ^ 4 mod 55) * (14 ^ 4 mod 55) * (14 ^ 4 mod 55) * (14 ^ 4 mod 55) * (14 ^2 mod 55) * (14 ^ 1 mod 55)] mod 55
[(38416 mod 55) * (38416 mod 55) * (38416 mod 55) * (38416 mod 55) * (38416 mod 55) * (38416 mod 55) * (196 mod 55) * (14 mod 55)] mod 55
[26 * 26 * 26 * 26 * 26 * 26 * 31 * 14] mod 55 = 9
Therefore a successful decryption gets the original plaintext 9
(3) p = 7; q = 11, e = 17; M = 8
Encryption
Ciphertext (C) = Memod n
C = 8^17 mod (p * q)
C = 8^17 mod (7 * 11) = 8^17 mod (77)
C = [ (8^16 mod 77) * (8 ^ 1 mod 77) ] mod 77
C = [ (8^8 mod 77) * (8^8 mod 77) * (8 ^ 1 mod 77) ] mod 77
C = [(8^4 mod 77) * (8^4 mod 77) * (8^4 mod 77) * (8^4 mod 77) (8 ^ 1 mod 77) ] mod 77
C = [4096 mod 77 * 4096 mod 77 * 4096 mod 77 * 4096 mod 77 * 8] mod 77
C = [15 * 15 * 15 * 15 * 8] mod 77
C = [ 405000] mod 77
C = 57
Decryption
Plaintext (M) = Cdmod n
Need to calculate d
e and d are multiplicative inverses mod f(n).
f(n) = (p – 1) (q – 1)
f(n).= (7 -1) (11 – 1) = 6 * 10 = 60
The multiplicative inverse of
e mod 60 = 17 mod 60 = -7
Therefore the positive multiplicative inverse of 17 mod 60 is = 53
So, lets calculate Cdmod n
57 ^ 53 mod (n) = 57 ^ 53 mod (p * q) = 57 ^ 53 mod (77)
[(57^32 mod 77) * (57 ^16 mod 77) * (57 ^4 mod 77) * (57 ^ 1 mod 77)] mod 77
[(57 ^ 16 mod 77) * (57 ^ 16 mod 77) * (57 ^ 16 mod 77) * (57 * 4 mod 77) * (57 ^ 1 mod 77)] mod 77
57 ^ 4 mod 77 = 71
57 ^ 8 mod 77 = [(57 ^ 4 mod 77) * (57 ^ 4 mod 77)] mod 77
57 ^ 16 mod 77 = [ (57 ^8 mod 77) * (57 ^ 8 mod 77)] mod 77
Therefore,
57 ^ 8 mod 77 = [71 * 71] mod 77 = 36
Therefore,
57 ^ 16 mod 77 = [ 36 * 36] mod 77 = 64
So, we have
[64 * 64 * 64 * 71 * 57] mod 77
[262144 * 4047] mod 77 = 8
Therefore a successful decryption gets the original plaintext 8
(4) p = 11; q = 13, e = 11; M = 7
Encryption
Ciphertext (C) = Memod n
C = 7^11 mod (p * q)
C = 7^11 mod (11 * 13) = 7^11 mod (143)
C = [ (7^8 mod 143) * (7 ^ 2 mod 143) * (7 ^ 1 mod 143) ] mod 143
C = [ (7^4 mod 143) * (7^4 mod 143) * (7 ^ 2 mod 143) * (7 ^ 1 mod 143) ] mod 143
C = [ 113 * 113 * 49 * 7 ] mod 143
C = [ 4379767] mod 143
C = 106
Decryption
Plaintext (M) = Cdmod n
Need to calculate d
e and d are multiplicative inverses mod f(n).
f(n) = (p – 1) (q – 1)
f(n).= (11 -1) (13 – 1) = 10 * 12 = 120
The multiplicative inverse of
e mod 120 = 11 mod 120 = 11
So, lets calculate Cdmod n
106^ 11 mod (n) = 106 ^ 11 mod (p * q) = 106 ^ 11 mod (143)
[(106 ^ 8 mod 143) * (106 ^ 2 mod 143) * (106 ^ 1 mod 143)] mod 143
[(106 ^ 4 mod 143) * (106 ^ 4 mod 143) * (106 ^ 2 mod 143) * (106 ^ 1 mod 143)] mod 143
[3 * 3 * 82 * 106] mod 143
[78228] mod 143 = 7
Therefore a successful decryption gets the original plaintext 7
(5) p = 17; q = 31, e = 7; M = 2
Ciphertext (C) = Memod n
C = 2^7 mod (p * q)
C = 2^7 mod (17 * 31) = 128 mod (527)
C = 128
Decryption
Plaintext (M) = Cdmod n
Need to calculate d
e and d are multiplicative inverses mod f(n).
f(n) = (p – 1) (q – 1)
f(n).= (17 -1) (31 – 1) = 16 * 30 = 480
The multiplicative inverse of
e mod 480 = 7 mod 480 = -137
Therefore the positive multiplicative inverse of 7 mod 480 is = 343
So, lets calculate Cdmod n
128^ 343 mod (n) = 128 ^ 343 mod (p * q) = 128 ^ 343 mod (527)
Binary expansion of 343 = 2^8 + 2^6 + 2 ^ 4 + 2 ^ 2 + 2 ^ 1 + 2^0 = 101010111
So,
[(128 ^ 256 mod 527) * (128 ^ 64 mod 527) * (128 ^ 16 mod 527) * (128 ^ 4 mod 527) * (128 ^ 2 mod 527) * (128^1 mod 527)]mod 527
128 ^ 2 mod 527 = 47
Therefore,
128 ^ 4 mod 527 = [47 * 47] mod 527 = 101
Therefore,
128 ^ 16 mod 527 = [101* 101* 101* 101] mod 527 = 35
Therefore,
128^64 mod 527 = [35* 35* 35* 35] mod 527 = 256
Therefore,
128^256 mod 527 = [256* 256* 256* 256] mod 527 = 35
So,
[35 * 256 * 35 * 101 * 47 * 128] mod 527 = [35 * 35 * 47 * 101 * 128 * 256] mod 527
[1225 * 4747 * 32768] mod 527 = [5815075 * 32768] mod 527
[190548377600] mod 527 = 2
Therefore a successful decryption gets the original plaintext 2