1. An RSA cipher has the public key pq = (5)(13) = 65 and e = 7 a) Encrypt this
ID: 3576439 • Letter: 1
Question
1. An RSA cipher has the public key pq = (5)(13) = 65 and e = 7
a) Encrypt this Plain Text Message M = J
b) Use the Extended Euclidean algorithm to find the greatest common divisor of e = 7 and (p-1)(q-1) = 48. Then find the intergers s,t such that Write the gcd (48, 7) = 7s +48t. Show your work.
c) Decrypt the Ciphertext C = 50 and translate the result into letters of the alphabet to discover the 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26Explanation / Answer
RSA Algorithm
Given, p=5, q=13 and e=7
therefore, n=p*q
=5*13=65
(n)=(p-1)*(q-1)
=4*12
=48
we have to choose e such that:
(1) 1<e<(n)
(2) e and n are co-prime
In this question e=7
So, our Public Key is (e,n)=(7,65)
(a) Given, Plain Text Message M = J
therefore from table J=10
So, Cipher Text Message C = (m)^e % n
= (10)^7 % 65
= 10
Hence C = 10
(b) gcd(48,7) = 7s + 48t
The gcd of two integers can be found by repeated application of the division algorithm, this is known as the Euclidean Algorithm. You repeatedly divide the divisor by the remainder until the remainder is 0. The gcd is the last non-zero remainder in this algorithm.
48 = 6*(7) + 6
7 = 1*(6) + 1
6 = 6*(1) + 0
So gcd(48,7) = 1
(c) Compute a value for d such that (d * e) % (n) = 1.
One solution is d = 7 since, .... [(7 * 7) % 48 = 1]
So, our Private Key is (d,n)=(7,65)
Cipher Text Message C = 50
therefore, M = (C)^d % n
= (50)^7 % 65
= 15
from given table O=15.
Hence required plain text message is O.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.