COMP3334 Computer Systems Security 2021/22 Semester 2
Tutorial 3 Solutions Public-Key Cryptography Question 1 Extended Euclidean Algorithm
Suppose m and b are integers. If GCD(b, m) = 1, b has a multiplicative inverse modulo m. That is, (b * b-1) mod m = 1. Below is an algorithm, named Extended Euclidean Algorithm, for finding the inverse of b:
EXTENDED EUCLID(b, m)
Copyright By PowCoder代写 加微信 powcoder
1. (A1, A2, A3) = (1, 0, m); (B1, B2, B3) = (0, 1, b);
return A3 which is GCD(m, b) and there is no inverse;
return B3 which is GCD(m, b) and B2 which is the inverse of b;
4. Q=A3divB3;//Qisthequotient
5. (T1,T2,T3)=(A1–Q*B1,A2–Q*B2,A3–Q*B3);
6. (A1, A2, A3) = (B1, B2, B3);
7. (B1, B2, B3) = (T1, T2, T3);
8. goto 2;
Using the algorithm, calculate the inverse of 33 mod 35.
1 0 35 0 1 33 1 -1 2 0 1 33 1 -1 2 -16 17 1 1 -1 2 -16 17 1
Therefore, 17 is the inverse of 33.
COMP3334 Computer Systems Security
2021/22 Semester 2
Question 2 RSA Keys
Let p = 11 and q = 13. If the public key e = 7, what is the private key d?
n = pq = 143
(n) = 10 * 12 = 120
Calculate d = e-1 mod (n)
Using Extended Euclidean Algorithm,
1 0 120 0 1 7 1 -17 1 0 1 7 1 -17 1
The private key d = 103 (-17) Question 3 RSA Encryption
In a public-key system using RSA, you intercept the ciphertext C = 10 sent to a user whose public key is e = 5, n = 35. What is the plaintext M? Can you break it?
n = 5*7= p *q
p = 5 and q = 7
(n) = 4 * 6 = 24
e * d = 1 mod 24
Using Extended Euclidean Algorithm,
1 0 24 0 1 5 1 -4 4 0 1 5 1 -4 4 -1 5 1 1 -4 4 -1 5 1
M = Cd mod n = (10)5 mod 35 = 5
COMP3334 Computer Systems Security 2021/22 Semester 2
Question 4 RSA Security
In the RSA public-key encryption scheme, each user has a public key, e, and a private key, d. Suppose Bob leaks his private key d. Rather than generating a new modulus, he decides to generate a new public key and a new private key. Is this safe? Explain.
No. If n = p * q is not changed, for any new e’ e, adversary will be able to calculate the new corresponding d’ easily by the following steps:
1. Public key = (n, e) is known to adversary at any time.
2. After Bob leaks his secret key d, adversary will be able to obtain extra information
and calculate (n). The number of possible values of (n) is greatly reduced, i.e., for k a positive integer, (n) = (e*d – 1)/k and k < min{e, d}. By fixing e’, the possible values of d’ can be obtained. The adversary can simply check if m = (me’)d’ mod n to determine whether (n) and d’ is the correct one.
3. For any new public key e’, the property for e’ * d’ = 1 mod (n) still holds, since Bob used this to generate his new d’.
4. Since both (n) and e’ are known, adversary can derive the value of new secret key d’ easily by extended Euclidean algorithm.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com