Review Questions

Download as pdf or txt
Download as pdf or txt
You are on page 1of 9

Review Questions

1. Distinguish between symmetric-key and asymmetric-key cryptosystems.

Ans

Symmetric-key cryptography is based on sharing secrecy; asymmetric-key cryptography


is based on personal secret.
2. Define a trapdoor one-way function and explain its use in asymmetric-key
cryptography.

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.

3. Briefly explain the idea behind the RSA cryptosystem.

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.

a. What is the one-way function in this system?


Ans:
The one-way function is the C = Pe mod n. Given P and e, it is easy to calculate C;
given C and e, it is difficult to calculate P if n is very large.

b. What is the trapdoor in this system?


Ans
The trapdoor in this system is the value of d, which enables Bob to use P = Cd mod n.

c. Define the public and private keys in this system.


Ans:
The public key is the tuple (e, n). The private key is d.

d. Describe the security of this system.

4. Briefly explain the idea behind the ElGamal cryptosystem.


a. What is the one-way function in this system?
b. What is the trapdoor in this system?
c. Define the public and private keys in this system.
d. Describe the security of this system.

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.

You might also like