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

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 cscodehelp代写 加微信 cscodehelp

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代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com