A median-size company with 400 employees’ security policy requires ensuring secret communi- cation for every possible pair of employees. How many secret keys are needed if a symmetric-key cipher, e.g., AES, is used? How about if an asymmetric-key cipher, e.g., RSA, is used?Question 3
Bob created his RSA encryption system with a public modulus
n
=
p q
and a public key
e. After some time, Bob decides that it is the time to refresh the keys. He generates a new modulus
n
l
=
p q
l
with only one new prime
q
l
generated at random from an appropriate range. To save time and effort, he reuses the prime
p. Are there any security implications of the shortcut taken by Bob? Justify your answer.Question 4 Let
p
= 3,
q
= 11,
e
= 5. Encrypt plaintext
M
= 10 to get the ciphertext. You need to do the calculation by hand. (
Hint: You need to first figure out the modulo number
n
and then apply the encryption algorithm of RSA.)
( 3809ICT/7809ICT - 2021 T1 Workshop 4: Public-Key Encryption and RSA Lecturer: Qinyi Li Scribe: Qinyi Li ) Question 1 1. What are the principal elements of a public-key encryption system? 2. What are the roles of the public and private key in a public-key encryption system? 3. What are three broad categories of applications of public-key cryptosystems? 4. Why in public-key encryption systems, it should be infeasible to obtain private keys from the public keys. 5. Explain the encryption process and the decryption process of hybrid encryption? Question 2 A median-size company with 400 employees’ security policy requires ensuring secret communi- cation for every possible pair of employees. How many secret keys are needed if a symmetric-key cipher, e.g., AES, is used? How about if an asymmetric-key cipher, e.g., RSA, is used? Question 3 ( × ) ( × )Bob created his RSA encryption system with a public modulus n = p q and a public key e. After some time, Bob decides that it is the time to refresh the keys. He generates a new modulus nl = p ql with only one new prime ql generated at random from an appropriate range. To save time and effort, he reuses the prime p. Are there any security implications of the shortcut taken by Bob? Justify your answer. Question 4 Let p = 3, q = 11, e = 5. Encrypt plaintext M = 10 to get the ciphertext. You need to do the calculation by hand. (Hint: You need to first figure out the modulo number n and then apply the encryption algorithm of RSA.) ( 1 ) Question 5 We learned the working of the RSA encryption system and have seen two examples from the lecture slides. However, no proof is given showing the decryption process is correct in general. Such a proof uses the Euler’s phi function and its property given in the slides. Suppose the public key is (n, e) and the private decryption key is d. To encrypt plaintext M , we do C = Me mod n To decrypt, we do Cd mod n Assume gcd(M, n) = 1 and M < n. expand the decryption formula to show it gives m . ( ≡ )(hint: the first step would be replaced c by me mod n. you will need to use the property of exponential function, and the euler’s theorem, i.e., if gcd(m, n) = 1 then mφ(n) 1 (mod n) or mφ(n) mod n = 1.) question 6 bob somehow generates his rsa public key as (n = 143, e = 5) and private decryption key d = 3. is this a correct pair of rsa key? (hint: e, d, φ(n) should satisfy certain mathematical relation.) n.="" expand="" the="" decryption="" formula="" to="" show="" it="" gives="" m="" .="" (="" ≡="" )(hint:="" the="" first="" step="" would="" be="" replaced="" c="" by="" me="" mod="" n.="" you="" will="" need="" to="" use="" the="" property="" of="" exponential="" function,="" and="" the="" euler’s="" theorem,="" i.e.,="" if="" gcd(m,="" n)="1" then="" mφ(n)="" 1="" (mod="" n)="" or="" mφ(n)="" mod="" n="1.)" question="" 6="" bob="" somehow="" generates="" his="" rsa="" public="" key="" as="" (n="143," e="5)" and="" private="" decryption="" key="" d="3." is="" this="" a="" correct="" pair="" of="" rsa="" key?="" (hint:="" e,="" d,="" φ(n)="" should="" satisfy="" certain="" mathematical="">