Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 +-c^k \mod p$

share|improve this question
You might consider reviewing the related question… – poncho Jan 20 '14 at 14:24
I edited my question so you can see how I use the Rabin cipher – Alexander Jan 20 '14 at 14:32
@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. – fgrieu Jan 20 '14 at 17:25
Thanks for the link, but in RSA attack we always need at least three messages, in my case I only have two – Alexander Jan 20 '14 at 17:37
@Alexander: RSA use odd public exponents, the minimum of which is 3. Rabin.. – fgrieu Jan 20 '14 at 17:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.