Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Assume there is a public-key encryption scheme $(KeyGen, Enc, Dec)$ with perfect correctness (i.e., for all messages M and valid key-pairs (PK,SK), we have $Dec_{SK}(Enc_{PK}(M))=M$).
Will there always be a function $A$ such that for all messages M and valid public-keys PK, $A_{PK}(Enc_{PK}(M))=M$?
In other words, can a computationally unbounded adversary decrypt the message, having only the public key?
Yes, a computationally unbounded attacker can break any public key system.
One easy way to see this is to consider the KeyGen algorithm, which takes takes as input a value R (which in normal use is the output of some random number generator), and outputs a public key PK and a private key SK.
Now, what a computationally unbounded adversary can do is consider all possible inputs R, and see which one produces the public key that he has been given. We know that there is at least one such input R (the one that was used when the public key was created); we can then use the corresponding private key to decrypt the message.
The obvious objection to this is "what if there are multiple such R's which generate the same public key, but different private keys?". Actually, it turns out that this is not a problem; because each such private key SK was generated correctly by the key generation function and corresponds to the public key under attack, it must still satisfy the formula:
$Dec_{SK}(Enc_{PK}(M)) = M$
Hence, it must correctly decrypt the message, even if it was not the exact private key that the legitimate user had.
I believe that the whole point of developing secure encryption schemes is to prevent such scenarios from occurring. With respect to the ElGamal encryption scheme, though, the above scenario is possible if the same random number (called the commitment) is used to encrypt two or more messages. The cryptanalyst can use this information to recover the private key.
To answer this question thoroughly, though, one needs to explain how set up and encrypt messages using the ElGamal coding scheme. Choosing the keys requires selecting a large prime number $p$. For security reasons, $p$ needs to be a number of at least 2000 bits, or 600 decimal digits.
First, select a primitive root $a \pmod{p}$. Note that finding a primitive root will be similar to finding a primitive element for cyclic groups. Also, select a number $b$ with $1 \leq b < p - 1$. This will be our private key. Calculate $c \equiv a^{b} \pmod{p}$ as a least residue modulo $p$. Note that $c \not\equiv 0, 1 \pmod{p}$. Publish $p$, $a$ and $c$ as the public key, and keep $b$ secret as the private key.
To encode a message, we must first translate the text into a numerical string using the ASCII collating sequence, or another agreed method (e.g. EBCDIC). Break this numerical string into blocks, each a number $x$ with $0 \leq x < p$. For each block $x$, choose a random number $r$ (called the commitment) with $1 \leq r < p - 1$. This number should be different for each block, for reasons that are explained below. Compute $y_{1}$ and $y_{2}$, with $0 < y_{1}$, $y_{2} < p$ by assigning $y_{1} \equiv a^{r} \pmod{p}$ and $y_{2} \equiv x \cdotp c^{r} \pmod{p}$. Finally, transmit $y_{1}$ and $y_{2}$, in that order.
To decode a message, we must first calculate $x$ with $0 \leq x < p$ by assigning $x \equiv y_{2}(y_{1}^{b})^{-1} \pmod{p}$, and then collect the decoded blocks into a numerical string which is translated to text by the agreed method.
As an example, to encode the message HELLO, we first translate the text into a numerical string using the ASCII collating sequence. This becomes the numerical string 72 69 76 76 79. For simplicity, we choose $p = 97$, $a = 10$ and $b = 2$, and calculate $c \equiv a^{b} \equiv 10^{2} \equiv 100 \equiv 3 \pmod{97}$. We then publish $p = 97$, $a = 10$ and $c = 3$, and keep $b = 2$ private.
Next, we split the numeric strings into blocks of two digits; that is, one letter in each block. For block $x = 72$, we choose $r = 2$, which results in $(y_{1}, y_{2}) = (3,66)$. Similarly, for block $x = 69$, we choose $r = 3$, which results in $(y_{1}, y_{2}) = (30,20)$. For blocks $x = 76$, we choose $r = 4$ and $r = 5$, respectively, and for block $x = 79$, we choose $r = 6$. Collectively, this results in the following message being transmitted:
(3,66), (30,20), (9,45), (90,38), (27,70)
If one were to use the same random number (or commitment), say $r = 2$, to encode different blocks, this would result in the following message being transmitted:
(3,66), (3,39), (3,5), (3,5), (3,32)
Notice that $y_{1}$ is repeated for each block, and that there is no entropy or dispersion of characters in the message that is encoded, meaning that if an intruder or cryptanalyst were to know (or guess) the message of the first (or any consecutive) block, he/she would be able to use it to find the multiplicative inverse of $(y_{1}^{b})^{-1}$, without the knowledge of the private key, and therefore use it to decode the rest of the message in the remaining blocks.
Remember, to decode a message, we use $x \equiv y_{2}(y_{1}^{b})^{-1} \pmod{p}$. So, if we were to know that $(3, 66)$ decodes to $72$, we can use this information to determine that $(y_{1}^{b})^{-1} = 54$, using the Euclidean algorithm for solving linear congruences. We can then use this to decode the message in the remaining blocks. Hence, $(3,39)$ translates to $69$, $(3,5)$ translates to $76$, and $(3,32)$ translates to $79$.
Note that this is a very simplistic example, and typically measures will be taken to prevent such a cryptanalysis of the message. Other methods of cryptanalysis typically involve dictionary attacks on the passphrase, or brute force attacks on the private key.