Week 4 Tutorial Sheet
Public Key Encryption: Part 1
1. What are the essential ingredients of an asymmetric / public-key cipher?
• Plaintext: This is the readable message or data that is fed into the algorithm as input.
Copyright By PowCoder代写 加微信 powcoder
• Encryption algorithm: The encryption algorithm performs various transformations on the plaintext.
• Public and private key: This is a pair of keys that have been selected so that if one is used for encryption, the other is used for decryption. The exact transformations performed by the encryption algorithm depend on the public or private key that is provided as input
• Ciphertext: This is the scrambled message produced as output. It depends on the plaintext and the key. For a given message, two different keys will produce two different ciphertexts.
• Decryption algorithm: This algorithm accepts the ciphertext and the matching key and produces the original plaintext.
2. What is the difference between the public key and the private key? Why the public-key cryptosystem is still secure even after giving the public key to the attacker?
The public key is used for the encryption, while the private key (secret key) is used for the decryption. The public key is different from the secret or private key (but related to it).
It is infeasible for an attacker to deduce the secret key from the public key and the plaintext/ciphertext.
3. Write the following composite numbers as a multiplication of their prime factors.
(a) 12 (b) 78 (c) 99
(a) 12=2×2×3=22×3 (b) 78=2×3×13
(c) 99=3×3×11=32×11
(d) 128=2×2×2×2×2×2×2=27
4. Complete the following modular arithmetic operations and determine the result:
(a) (12+8) mod 6 (b) (2×12) mod 6
(c) (20 + 125) mod 5 (d) (20 − 35) mod 5 (e) 104 mod 3
(f) 10−1 mod 31 (g) 13−1 mod 19
(a) (12+8)mod6=2 (b) (2×12)mod6=0
Week 4 Tutorial Sheet
(c) (d) (e)
(a) 7156 mod 11
(b) 5866 mod 31
(a) StartwithMSbit𝑏5=1of𝑒=5610=1110002andsince71=5mod11 Set 𝑧 = 𝑎 = 5 and 𝑛 = 11
𝑖=4:bit𝑏4=1→− square&multiply:z=az2mod𝑛=5∗25mod11=4 𝑖=3:bit𝑏3=1→− square&multiply:z=az2mod𝑛=5∗42mod11=3 𝑖=2:bit𝑏2=0→− 𝑠𝑞𝑢𝑎𝑟𝑒∶z=z2mod𝑛=32mod11=9 𝑖=1:bit𝑏1=0→− 𝑠𝑞𝑢𝑎𝑟𝑒∶z=z2mod𝑛=92mod11=4 𝑖=0:bit𝑏0=0→− 𝑠𝑞𝑢𝑎𝑟𝑒∶z=z2mod𝑛=42mod11=5
The answer is 5.
(b) StartwithMSbit𝑏6=1of𝑒=6610=10000102andsince58=27mod31 Set 𝑧 = 𝑎 = 27 and 𝑛 = 31
𝑖=5:bit𝑏5=0→− 𝑠𝑞𝑢𝑎𝑟𝑒∶z=z2mod𝑛=272mod31=16 𝑖=4:bit𝑏4=0→− 𝑠𝑞𝑢𝑎𝑟𝑒∶z=z2mod𝑛=162mod31=8 𝑖=3:bit𝑏3=0→− 𝑠𝑞𝑢𝑎𝑟𝑒∶z=z2mod𝑛=82mod31=2 𝑖=2:bit𝑏2=0→− 𝑠𝑞𝑢𝑎𝑟𝑒∶z=z2mod𝑛=22mod31=4 𝑖=1:bit𝑏1=1→− square&multiply:z=az2mod𝑛=27∗42mod31=29 𝑖=0:bit𝑏0=0→− 𝑠𝑞𝑢𝑎𝑟𝑒∶z=z2mod𝑛=292mod31=4
The answer is 4.
(20+125)mod5=0 (20−35)mod5=0
104 mod3=(10mod3)4 mod3=14 mod3=1alternatively104 mod3= (9999+1) mod 3 = 1
Since GCD of 31 and 10 is 1 that multiplicative inverse exists. Since 31 = 10 ∗ 3 + 1 so 1 = 31 + 10(−3). By taking modulus at both sides, 1 = 10 ∗ (−3) mod 31. The inverse is −3 mod 31 i.e. 28 mod 31.
13 ∗ 3 mod 19 = 39 mod 19 = 1, thus the multiplicative inverse of 13 is 3.
5. Using the “Square and Multiply” modular exponentiation algorithm calculate the following:
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com