Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
4  
You might consider reviewing the related question crypto.stackexchange.com/questions/6713/… –  poncho Jan 20 at 14:24
    
I edited my question so you can see how I use the Rabin cipher –  Alexander Jan 20 at 14:32
1  
@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 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 at 17:37
1  
@Alexander: RSA use odd public exponents, the minimum of which is 3. Rabin.. –  fgrieu Jan 20 at 17:54
show 4 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.