1
$\begingroup$

I have already done my research and found various sources that state that it is possible but there are also a lot of them that says it is not possible to recover $r$. This Q/A on this site for example even states the formula to get it. I don't know if it is wrong or I am missing something since I was not able to make a working implementation of it.

Some friends told me it is impossible to get $r$ back since it was raised during encryption to the $n$-th power and ended up in a smaller subgroup which results in a loss of information that renders it unable to be recovered.

I asked on reddit and got told the following:

$r$ is choosen to be between 0 and $n^2$. The plaintext can be between $0$ and $n$. The Ciphertext is however also between $0$ and $n^2$. Since the plaintext is fully preserved, the same is impossible for the randomness, as this would otherwise violate the theorem that lossless compression is impossible.

I would like to know whether it is possible to calculate $r$ and how it is computed given that I have:

  • $C \to$ ciphertext
  • $P \to$ plaintext
  • $N \to$ public key modulo $(p\cdot q)$

Also if it is not possible for all $r$ values to be recovered I would like to know if it would be possible to recover $r$ values smaller than $m$ bits (I know that reducing $r$ bit length makes the encryption less secure)

$\endgroup$
2
$\begingroup$

It is strange that Wikipedia propose to choose $r\mod N^2$ while $r^N\mod N^2$ depends on $r\mod N$ only: $$(r+tN)^N=r^N+r^{N-1}tN^2+\ldots\equiv r^N\pmod{ N^2}.$$ It means that you can recover only $r\mod N.$ In order to do it you can use the formula from the cited answer $$r\equiv (r^N)^M\pmod{ N}, $$ where $M = N^{-1}\bmod \phi(N)$.

$\endgroup$
  • $\begingroup$ So I have: $p = 56039$, $q = 58727$, $n = p·q = 3291002353$, $n^2 = 10830696487451536609$, $\phi(n) = (p-1)·(q-1) = 3290887588$, ciphertext $c$ of $m = 12$ using $r = 7$ $\to c = 6859599884662874753$ I do $P = decrypt(c) = 12$, $c' = c·(1-P·n)\>mod\>n^{2} = 685959988466287475 · (1-12·3291002353)\> mod\> 10830696487451536609 = 2421846566699018322,$ $M = n^{-1}\> mod \>\phi(n) = 3291002353^{-1}\> mod\> 3290887588 = 1169309581,$ $r = c'^M \>mod\> n = 2421846566699018322^{1169309581}\> mod \>3291002353 = 2648362593$ which is not $12$. Am I missing something? $\endgroup$ – Kranga Sep 29 at 16:52
  • $\begingroup$ @Kranga My calculations give $c=5368334944199256653$, $c'=4487862507998304930$ and $(c′)^M\mod n=7.$ Also here $c'=r^n\mod n^2$. $\endgroup$ – Alexey Ustinov Sep 30 at 1:50

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.