# 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.

41 questions
Filter by
Sorted by
Tagged with
97 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 ...
186 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 ...
106 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 ...
67 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 ...
93 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 ...
49 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^*$?
146 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 ...
171 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.
232 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 ...
205 views

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 ...
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 ...
312 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 ...
262 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 ...
194 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 ...
640 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 ...
299 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'...
167 views