Given a big number $x$(1024 bits) and a large prime $N$($N>x$), I want to encrypt it with a smaller number $y$(128 bits).

$$Enc(x) = xy \mod{N}.$$

Is it safe? If not, how do I evaluate its leakage?


The most basic security is "Indistinguishability in the presence of an eavesdropper". This is based on a simple experiment. An adversary $A$ sends two messages $m_0$, $m_1$ to a challenger $C$. The challenger encrypts one of the messages (randomly chosen, say $C$ chooses $b \in \{0,1\}$ uniform random and encrypts $c_b = Enc(m_b)$). The ciphertext is then send to $A$. The adversary now has to find out, which message was encrypted and sends $b'=0$ or $b'=1$ to $C$. If $b = b'$ we say $A$ wins.

Now we look at your Encryption: $A$ knows $Enc(x)$ and $x$. With the extended euclidean algorithm $A$ can compute $y$ and therefore can distinguish $c_b$. So $A$ wins the experiment and the Encryption system does not even provide the most basic concept of security.

  • $\begingroup$ $A$ knows $\operatorname{Enc}(x)$, but no justification is given that $A$ knows $x$. $A$ knows $x\in\{m_0,m_1\}$, but it is not told how it is determined whether $x=m_0$ or $x=m_1$. In some cases, there is no possible advantage, e.g. with $m_0=1$, $m_1=2$, and it happens that the key $y=3-x$: for both $b$, $\operatorname{Enc}(x)=2$. $\endgroup$ – fgrieu Apr 13 at 9:16
  • $\begingroup$ When $Enc(x)$ and $x$ are given, $y$ can be computed. However, gettng $Enc(m_b)$, using $m_0$ and $m_1$ respectively, you can compute different $y_1$ and $y_2$. How do you know which one is right? $\endgroup$ – Wanyu Apr 13 at 9:22
  • $\begingroup$ @Wanyu: that's where the "128-bit" part of the problem statement comes into play. $\endgroup$ – fgrieu Apr 13 at 9:24
  • 2
    $\begingroup$ I think what @fgrieu is getting at is if any one of them requires y to be something larger than 128 bits then, we can tell which one was encrypted. If you get x and y to be of equal size, it becomes same as one time pad, hence indistinguishability is inevitable but it makes the encryption scheme practically useless. $\endgroup$ – Manish Adhikari Apr 13 at 10:24
  • 2
    $\begingroup$ But remember that even in this case, indistinguishability only exists upto a point of one round of game. It does not allow key reuse and since encryption oracle cannot be applied here as a single round reveals the key entirely. Thus the scheme is still not CPA-secure $\endgroup$ – Manish Adhikari Apr 13 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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