0
$\begingroup$

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)?
$\endgroup$
4
  • $\begingroup$ 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$ $\endgroup$
    – kelalaka
    Commented Oct 26, 2021 at 6:02
  • $\begingroup$ Wikipedia 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? $\endgroup$
    – kelalaka
    Commented Oct 26, 2021 at 6:05
  • $\begingroup$ @kelalaka, what if I didn't divide my message? Is it critical mistake? $\endgroup$
    – DBenson
    Commented Oct 26, 2021 at 8:28
  • 1
    $\begingroup$ We want encryption schemes invertible, i.e. the decryption must(!) return what we encrypted. This is called the functionality of the encryption system. 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. $\endgroup$
    – kelalaka
    Commented Oct 26, 2021 at 8:33

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.