# Questions tagged [rabin-cryptosystem]

A public-key cryptosystem based on squaring modulo the product of two primes, introduced in 1979 by Michael O. Rabin and proven to have security reducible to the hardness of integer factorization. It is similar to RSA but uses e=2.

43 questions
Filter by
Sorted by
Tagged with
0answers
5 views

### Tonelli-Shank vales are incorrect when trying to get back to c value for Rabin

I'm working (banging head against wall) on a Rabin encryption as part of a challenge. I thought I was making progress as several algorithms had given em the same values for the mod sqrt but it seems ...
0answers
17 views

### How to decrypt Rabin message when p=q and you have the roots from Tonelli-Shanks

I've been trying to decrypt a message encrypted with Rabin as a challenge. I'm very new to cryptography and these challenges so much of this is new. I've factorised n and determined that p=q which I ...
1answer
104 views

### Forging Rabin signature

What is the chances to forge a signature for the system implementing Rabin signature with total message recovery, if attacker posses the public key and have some message pairs? The last byte of ...
2answers
189 views

### Identify the cryptosystem where $\ m = c^2 \bmod n$?

I came across with cryptosystem whose decryption method is: $\ m = c^2 \bmod n$. It's exact opposite of Rabin's, where's the same formula is used for encryption. What is the name of this ...
0answers
130 views

### Encoding function for ISO 9796-2

I try to reproduce the analysis conducted in this presentation by R. Lifchitz. Namely, data signed by an 1024-bit key $n$ (Rabin scheme) and following ISO/IEC 9796-2. From what I understand, for a ...
0answers
73 views

### 1-out-of-2 Oblivious Transfer Security

Just started reading Oblivious Transfer. I am searching for a proof of security based on RSA implementation but I can't find anything simple to understand. Can someone direct/show me to an easy to ...
0answers
96 views

### Why did Rabin use $x(x + b)$ instead of just $x^2$ in the original paper?

Encryption in the original Rabin scheme took a message $x$ and computed $x(x + b) \bmod n$, where $0 \le b \lt n$ and $n$ is the product of two secret primes $p$ and $q$. The private key is defined as ...
1answer
51 views

### Why is the Rabin mapping not a permutation over $\mathbb{Z}_N^*$

Why is the Rabin mapping: $f_i(x_i)=x_i^2 \bmod N_i$ not a Permutation over $\mathbb{Z}_N^*$?
1answer
148 views

### Estimate Security level of the Rabin Signature

I'm trying to figure out how long the modulus $n$ has to be in the Rabin Signature scheme, to provide 128 bit security. We assume that the used hash function is "secure enough". Then the naive ...
1answer
183 views

### Rabin Encryption is not CCA secure

Why is Rabin Encryption is considered as not CCA secure and how can I prove it? Any example would be helpful.
1answer
249 views

### Rabin: how discover P and Q?

I'm really lost. I'm creating a classroom lesson about Rabin encryption and I had understood the encryption process, the creation of public-key (N = p*q) and the steps I need to find the 4 values ...
1answer
213 views

1answer
101 views

### Finding greatest integer m satisfying modular relation

I solved (c). I want to know (a) and (b) For (a), what i have done is that p-1=t2^s(t is odd) = 2^s (mod 2^m) And for m=1,2,...s, both sides are 0. So, m is s or more than s. For m= s+1, s+2,... what ...
2answers
1k views

### Rabin cryptosystem decryption when p=q

I'm currently trying to implement the Rabin Cryptosystem when I realized something when gave p and q the same value: So my values are as follows: Original message = 20 p=11 q=11 Encrypted message ...
1answer
313 views

### Is this a good choice of a digital signature scheme?

This is a concrete instantiation of Rabin-Williams signatures. Specifically: The private key is 2 primes $p, q$. The public key is their product $N = pq$ and is approximately 3072 bits long. the ...
2answers
289 views

### Get $a$ such that quadratic residue has a solution (Rabin)

My task is to implement Rabin signature. I have trouble with choosing padding a such that $$x^2 \equiv a \pmod n$$ has a solution. In that context, $n=p\cdot q$ is composite, where $p$ and $q$ are ...
1answer
196 views

### Decrypting an RSA message given $a^2 \equiv 1 \pmod n$

I need help with a practice problem for an upcoming test. I've learned the answer to the problem is "well done", but don't know how to get there. Any help is greatly appreciated. Suppose that the ...
1answer
697 views

### How do I attack an RSA setup where e is even?

As a challenge, we were shown an RSA setup where we have a big $n$ (617 decimal digits), $e=4$, and asked to recover three messages. (However, the messages are padded to the same length as the key ...
2answers
303 views

### Breaking hashless variant of the Rabin Signature system with chosen message attack

I heard that we can break the Rabin Signature system using chosen-message attack. For a message $M$ that is a quadratic residue modulo $N$, the signature is $x$ such that $x^2 \equiv M \pmod N$. I can'...
1answer
169 views

3answers
2k views

### Identification of correct plaintext after decryption in Rabin cryptosystem

In the Rabin cryptosystem, decrypting a message can produce four different outputs, of which only one is the correct plaintext. How can one know which of the outputs is the correct one?
1answer
263 views

### Pseudo Random Generator (PRG) from Rabin function

I'm trying to make a PRG using the Rabin function. The code (in Java) I wrote to implement the function is: ...