Review Questions
Review Questions
Review Questions
Ans
Ans:
In cryptography, a trapdoor is a secret with which Bob can use a feasible algorithm
To decrypt the cipher text. If Eve does not know the trapdoor, she needs to use an
Algorithm which is normally infeasible.
RSA uses two exponents, e and d, where e is public and d is private. Alice calculates C =
Pe mod n to create cipher text C from plaintext P; Bob uses P = Cd mod n to retrieve the
plaintext sent by Alice.
Ans
ElGamal is based on a discrete logarithm problem. The plaintext is masked with e1rd
to create the ciphertext. Part of the mask is created by Bob and becomes public; the other part is
created by Alice.
a. The one-way function is C = mask (P). Given P and the mask, it is easy to calculate the
C; given C is difficult to unmask P.
b. The trapdoor is the value of d that enables Bob to unmask C.
c. The public key is (e1, e2 and n). The private key is d.
d. The security of ElGamal depends on two points; p should be very large and Alice needs
to select a new r for each encryption.
5. Given the super increasing tuple b = [7, 11, 23, 43, 87, 173, 357], r = 41, and modulus
n = 1001, encrypt and decrypt the letter “a” using the knapsack cryptosystem. Use
[7 6 5 1 2 3 4] as the permutation table.
Ans
We use the 7-bit representation of character "a" as the plaintext.
Key Generation:
t = [287, 451, 943, 762, 564, 86, 623] → a = [623, 86, 564, 287, 451, 943, 762]
Encryption:
Plaintext: x = [1, 1, 0, 0, 0, 0, 1] → Cipher text: s = 1471
Decryption:
s’ = (41−1, 1471) mod 1001 = 293 × 1471 mod 1001 = 573
x’ = [0, 0, 0, 1, 0, 1, 1] → Plaintext x = [1, 1, 0, 0, 0, 0, 1]
6. To understand the security of the RSA algorithm, find d if you know that e = 17 and n =
187.
Ans
n = 187 = 17 × 11 → φ(n) = 17 × 11 = 160 → d = e−1mod φ(n) = 113. This proves that the
value of n in RSA must be very large. We could find d because we could factor n. The
modulus must be large enough to make the factorization infeasible.
7. In RSA, given e = 13 and n = 100 a. encrypt the message “HOW ARE YOU” using 00 to
25 for letters A to Z and 26 for the space. Use different blocks to make P < n.
Ans
In a real situation, the value of n is so large that Alice can't check if n and e are chosen
properly. In this toy problem, it is easy to see that n is not properly selected because n =
100 cannot be factored into two primes (n = p × q).
Although we can still encrypt the message using e = 13 and n = 100, the encrypted message
cannot be decrypted. The problem proves that Bob needs to first select p and q and be sure
that they are primes before calculating n = p × q. After the correct selection of n, then e
needs to be selected in such a way that φ(n) and e be co primes. This problem has no
solution.