Question

8.17. Considering the four examples from Problem 8.13, we see that the Elgamalscheme is nondeterministic: A given plaintext x has many valid ciphertexts, e.g., both x = 33 and x = 248 have the same ciphertext in the problem above.

1. Why is the Elgamal signature scheme nondeterministic?

2. How many valid ciphertexts exist for each message x (general expression)? How many are there for the system in Problem 8.13 (numerical answer)?

3. Is the RSA cryptosystem nondeterministic once the public key has been chosen?"

Answer 1

In this case, "non deterministic " means that the algorithm to generate the cipher text takes a random value as one of its inputs, and can generate many possible cipher texts based on the random value.

1. By choosing a different secret component i, the cipher text y of the same plain text x is different every time. Even if a pair of plain text/cipher text is compromised, such a pair will most likely not repeat a second time in a non deterministic encryption scheme.

2. In general, there are # (2,3, p - 2) = p - 3 different valid cipher texts for a single plain text i.e. we have 464 different possibilities for p = 467.

3. The plain RSA crypto system is deterministic. A specific plain text always yields the same cipher text assuming the same public parameters.