代写代考 COMP3334 Computer Systems Security 2021/22 Semester 2

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