If I do encryption and decryption like this:

Encryption: $\text{E}(m) = (r \times p_1+m) \bmod N$

Decryption: $\text{D}(\text{E}(m)) = ((r \times p_1 + m) \bmod N) \bmod p_1 = m$


$r$ = random number

$p_1$ = random large prime

$m$ = plain text (int)

$N$ = product of two large primes $p1 \times p2$

So, my question is if $\text{E}_1(m)$ and $\text{E}_2(m)$, two different ciphers for the same integer are known, what could be done to break the algorithm?

This question is for my assignment but I do not have a clue where to start. A little clue will be appreciated.


  • 3
    $\begingroup$ That's not the cipher from Fully Homomorphic Encryption Over The Integers. There's no noise/error term attached for starters, which makes a big difference. Anyways: What if $m = 0$? $\endgroup$
    – Ella Rose
    Mar 27 '19 at 2:17
  • $\begingroup$ @EllaRose: actually, there is an 'error' term; the value $r$, which is a random value for every encryption. $\endgroup$
    – poncho
    Mar 27 '19 at 12:27
  • $\begingroup$ However, the 'what if $m = 0$?' question is a pretty good hint. Could you figure out how to break it if you were given an encryption of 0? If so, could you figure out how to obtain the encryption of 0 given two different encryptions of the same value? $\endgroup$
    – poncho
    Mar 27 '19 at 12:29
  • $\begingroup$ Thanks for the comment. @ Ella Rose, yes this is not the actual encryption. It has a flaw and my question was knowing the two cipher of the same integer what can I do to break this algorithm or what could be done with the known information. And for m, let's say that m will not be 0. $\endgroup$
    – randomUser
    Mar 28 '19 at 16:21
  • $\begingroup$ @poncho, I think there is nothing wrong with the r as this is a nondeterministic algorithm. so it is expected that the value of r to be different in every encryption. And that's how we get different cipher for the same m. Please correct me if I'm wrong. $\endgroup$
    – randomUser
    Mar 28 '19 at 16:42

Your Answer

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

Browse other questions tagged or ask your own question.