=========================preview======================
(COMP170)Midterm2_2007_review.pdf
Back to COMP170 Login to download
======================================================
COMP 170 C Fall 2007
Midterm 2 Solution

Q1. Recall the RSA public key cryptography scheme.

Bob posts a public key P =(n, e) and keeps a secret key S =(n, d).
When Alice wants to send a message 0 <M<n to Bob, she calculates M. = Me mod n and sends M. to Bob.
Bob then decrypts this by calculating (M.)d mod n.

In class we learnt that in order for this scheme to work, n, e, d must have special properties.
(Note: In real life, to ensure a high level of security, n, e, d have to be very large numbers. For simplicity, however, we do not consider that fact here and use small numbers in this question.)
For each of the three Public/Secret (P/S) key pairs listed below:
(i)
say whether it is a valid set of RSA Public/Secret key pairs and


(ii)
justify your answer.


(a)
P = (91, 25), S = (91, 51)

(b)
P = (91, 25), S = (91, 49)

(c)
P = (84, 25), S = (84, 37)


Solution:
Recall that the conditions for a pair to be correct is that (i)n = pq where p and q are prime numbers and
(ii) e d mod T =1 where T =(p . 1)(q . 1).
Solution:
Recall that the conditions for a pair to be correct is that (i)n = pq where p and q are prime numbers and
(ii) e d mod T =1 where T =(p . 1)(q . 1).
(a)P = (91, 25), S = (91, 51)
This is not a valid key pair.
It is true that n =7 13 so p, q are prime.
But T = 72 and 25 51 mod 72 .

=1.

It is true that 25 51mod91 = 1 but that is not the RSA condition.
Solution:
Recall that the conditions for a pair to be correct is that

(i)n = pq where p and q are prime numbers and

(ii)
e d mod T =1 where T =(p . 1)(q . 1).


(b)
P = (91, 25), S = (91, 49)


This is a valid key pair since n =7 13 and 25 49 mod 72 = 1.
Solution:
Recall that the conditions for a pair to be correct is that (i)n = pq where p and q are prime numbers and
(ii) e d mod T =1 where T =(p . 1)(q . 1).
(c) P = (84, 25), S = (84, 37)
This is not a valid key pair since n =7 12 and12 is not prime.

Solution:
Recall that the conditions for a pair to be correct is that (i)n = pq where p and q are prime numbers and
(ii) e d mod T =1 where T =(p . 1)(q . 1).
(c) P = (84, 25), S = (84, 37)
This is not a valid key pair since n =7 12 and12 is not prime.

Note. It is true that e d mod n =1 and e d mod (6 11) = 1 but this doesnt mean anything.
Q2. Calculate the value of

31032 mod 50.

Show the steps to obtain the result.

Solution: Use repeated squaring to calculate

31 mod 50 32 mod 50 34 mod 50 38 mod 50 316 mod 50 332 mod 50 364 mod 50 3128 mod 50 3256 mod 50 3512 mod 50 31024 mod 50
=3 =9 =92 mod 50 = 31 = 312 mod 50 = 11 = 112 mod 50 = 21 = 212 mod 50 = 41 = 412 mod 50 = 31 = 312 mod 50 = 11 = 112 mod 50 = 21 = 212 mod 50 = 41 = 412 mod 50 = 31

Solution: Use repeated squaring to calculate
31 mod50 = 3 32 mod50 = 9 34 mod50 = 92 mod 50 = 31 38 mod50 = 312 mod 50 = 11
316 mod50 = 112 mod 50 = 21 332 mod50 = 212 m