I use Rabin code with modulus $N$. Now assume that Alice sends me a message $m$ $(1\le m\le N)$ encoded by Rabin code. Unfortunately after Alice sent me the text I lose the information about the factorization of $N$ and therefore I cant decipher the message. I take new primes and construct a $\bar{N}>N$ and tell Alice to encode it again with $\bar{N}$.

An enemy finds both messages (the one encoded with $N$ and the one encoded with $\bar{N}$). My question now is how can he finds out the message $m$?

EDIT: According to the comment, here my method for the Rabin cipher:

The primes $p,q$ are of the form $p=4k-1, q=4m-1, N=pq$. Public key is $N$ and the encrypting fuction is $m\rightarrow m^2 \mod N$ $gcd(m,N)=1$. I also know that if $c\equiv m^2 \mod p$ then $m\equiv \pm c^k \mod p$

  • 4
    $\begingroup$ You might consider reviewing the related question crypto.stackexchange.com/questions/6713/… $\endgroup$
    – poncho
    Jan 20 '14 at 14:24
  • $\begingroup$ I edited my question so you can see how I use the Rabin cipher $\endgroup$
    – Alexander
    Jan 20 '14 at 14:32
  • 1
    $\begingroup$ @Alexander: your enciphering method is to Rabin what naked (or textbook) RSA is to RSA. Some of the attacks that apply to naked RSA can be adapted to naked Rabin, including the one pointed by poncho. You may also want to read the introduction of section 4.2 of Twenty Years of Attacks on the RSA Cryptosystem and adapt from that. $\endgroup$
    – fgrieu
    Jan 20 '14 at 17:25
  • $\begingroup$ Thanks for the link, but in RSA attack we always need at least three messages, in my case I only have two $\endgroup$
    – Alexander
    Jan 20 '14 at 17:37
  • 1
    $\begingroup$ @Alexander: RSA use odd public exponents, the minimum of which is 3. Rabin.. $\endgroup$
    – fgrieu
    Jan 20 '14 at 17:54

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.