Score:0

ElGamal, message > p

in flag

Assume that we have:

p = 89
g = 5
public key: 17
private key: 73

If we try to encrypt message M = 53 (M < p), then we get (c1, c2) == (55, 67) and further message decrypts well.

However, if we try to encrypt message M = 91 (M > p), then we get (c1, c2) == (44, 57) and further message decrypts failed (got "2" as the result).

There are 3 questions:

  • Why does it happen?
  • Is it possible to recover original message M if we know the fact that (m > p) used, p, g, public key and have (c1, c2)?
  • Is it possible to recover original message M if we know the fact that (m > p) used, p, g, public key and have several encrypted messages (c1, c2)?
kelalaka avatar
in flag
This is very well-known if you know how modulus works; modulus rounds up. You need to divide your messages into blocks where each part should be $ < p$
kelalaka avatar
in flag
[Wikipedia](https://en.wikipedia.org/wiki/ElGamal_encryption) states this _Map the message $M$ to an element $m$ of $G$ using a reversible mapping function._. Can you recover your message if you really using modulus correctly?
DBenson avatar
in flag
@kelalaka, what if I didn't divide my message? Is it critical mistake?
kelalaka avatar
in flag
We want encryption schemes invertible, i.e. the decryption must(!) return what we encrypted. This is called the [functionality of the encryption system](https://crypto.stackexchange.com/a/88339/18298). Modular operations work in the modulus. The libraries automatically make the reduction and the information is lost. You should learn some modular arithmetic, CPU arithmetic, and their connection.
Score:3
ng flag

Why does it happen?

This happens because, in terms of arithmetic mod 89, the numbers $2$ and $91$ are equivalent: $91 \bmod 89 = 2$. You'll usually see this denoted as $91 \equiv 2 \pmod{89}$.

If you're new to modular arithmetic - this is just as how the hours $0$ and $12$ on a traditional clock are equivalent - it "wraps around".

Is it possible to recover original message M if we know the fact that (m > p) used, p, g, public key and have (c1, c2)?

Not in general, while still allowing decrypting messages $m < p$.

In a specific case, where you had a ciphertext and knew that the original message had been in e.g. $[2p, 3p - 1]$, you could recover it by simply adding the appropriate offset after decryption.

In practice this is not particularly useful, so as mentioned in comments above, one splits the message $m$ into $m_1, \ldots, m_n$ such that $m_i < p$. Each partial message is then encrypted individually.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.