We’re rewarding the question askers & reputations are being recalculated! Read more.

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.

Filter by
Sorted by
Tagged with
0
votes
0answers
81 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 ...
0
votes
0answers
41 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 ...
5
votes
0answers
84 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 ...
-1
votes
1answer
46 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^*$?
2
votes
1answer
110 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 ...
-1
votes
1answer
114 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.
1
vote
1answer
161 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 ...
2
votes
1answer
171 views

Rabin cryptosystem - How many solutions?

If in Rabin cryptosystem we have $n = p \cdot q$ where $p$ and $q$ is prime we have four solutions (roots) - exist four solution of $x^2 \equiv b \pmod{n}$. However, when we have: $n = p \cdot q \...
-2
votes
1answer
326 views

rabin decryption [closed]

so in rabin decryption, we get 4 answers due to the square root and one of them is the correct one although I've seen the correct result multiple times sometimes i.e. 2 out of the 4 square roots. Is ...
5
votes
1answer
3k views

Decryption in Rabin

Recently I was working on the Rabin cryptosystem. But in the decryption part of the algorithm, there are two ways to decrypt the cipher. The first solution which has $p$ and $q$ equal to $3\pmod4$ ...
3
votes
1answer
92 views

Rabin encryption when M is not Disjoint to n

I need help with proving that the encryption going well when the message $M$ is not Disjoint to $n$ (public key). Encryption message $\ C= M^2 \bmod n$ Decryption message $\ C^{(p+1)/4} \equiv ±M \...
-1
votes
1answer
86 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 ...
0
votes
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 ...
4
votes
1answer
308 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 ...
1
vote
2answers
214 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 ...
-2
votes
1answer
182 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 ...
3
votes
1answer
533 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 ...
1
vote
2answers
244 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'...
1
vote
1answer
148 views

Proving property of Modified Rabin Signature

I'm trying to prove one of the properties of the “Modified Rabin Signature Scheme”: If $\gcd(x, n) = 1$, then $x^{\frac{(p−1)(q−1)}{2}} \equiv 1 \pmod n$ This is what I’ve got so far… Proof Let $...
1
vote
1answer
556 views

Chosen-Ciphertext Attack on Rabin: Factorize n

At the end of this Wikipedia section, you can see that $$\gcd(|r-s|,n)=q$$ or $$\gcd(|r-s|,n)=p$$ holds. I don't understand why.
2
votes
2answers
2k views

Can e = 2 be used in unpadded RSA?

I am wondering whether $e = 2$ can be used in unpadded RSA... It seems like it is not possible to use it: the value of e needs to be coprime with $tot(n)$. $tot(n) = (p - 1)(q - 1)$ where $p$ and $q$ ...
2
votes
1answer
999 views

How to use CRT to compute 4 square roots while decryption in Rabin Cryptosystem

I'm reading Rabin Cryptosystem which requires to compute 4 square roots $r, -r, s,- s$ while decryption of cipher text $c$ such that $$r = (y_p \times p \times m_q + y_q \times q \times m_p) \mod n $$...
4
votes
2answers
1k views

Why is Rabin encryption equivalent to factoring?

I don't understand the proof of equivalence I've read everywhere (e.g., in Rabin's paper or on Wikipedia). Here's my objection: let's say you have a Rabin decryption oracle that takes ...
2
votes
0answers
35 views

Are there UFDs where the factorization problem is difficult but finding irreducibles is cheap?

Factorization of integers is hard, but finding irreducibles is expensive. Is there a ring where factorization is assumed hard but finding irreducibles is much cheaper than over $\Bbb Z$? It could ...
3
votes
1answer
154 views

How to prove the hardness of Rabin's function?

I am unable to prove the following theorem: If for a $1/(\log(n))$ fraction of the quadratic residues $q\pmod n$ one could find a square root of $q$, then one could factor $n$ in random polynomial ...
8
votes
1answer
1k views

Why isn't Rabin-Williams cryptosystem widely used?

I think we all know RSA. And of course we also know DJB (a.k.a. Daniel J. Bernstein). Now some already have noticed that he has an opinion towards cryptographic questions. In his 2008 paper ("RSA ...
2
votes
1answer
81 views

Why does P1363 require RW signature with $0 ≤ s < n/2$?

I'm using an older copy of P1363 Public Key Cryptography was used below. It may (or may not) reflect the current state of affairs. P1363 has the following requirement in section 8.2.8 IFSP-RW, p. 45: ...
3
votes
0answers
96 views

Residue requirements of Rabin-Williams primes?

I'm trying to determine the residue requirements of Rabin-Williams. An older copy of P1363's Public Key Cryptography states the following in Section 8.1.3.2 RW key pairs: An RW public key consists ...
1
vote
1answer
199 views

Tweaked Square Roots and Rabin-Williams

I'm reading Bernstein's RSA signatures and Rabin–Williams signatures: the state of the art. In section 6, Bernstein states: Recall that Rabin’s system needed to try several values of r, on ...
2
votes
1answer
134 views

Rabin-Williams, blinding and size of Integer r?

I was reading the paper Breaking the Rabin-Williams digital signature system implementation in the Crypto++ library. The library uses blinding, but it was not enough to stop key recovery. But my ...
0
votes
0answers
425 views

Rabin cryptosystem with 1 mod 4

We have p and q which are distinct primes congruent to 1 mod 4. Then we have n = p*q. Do you know any algorith for calculating square roots for the decryption in this case? I'm asking for some ...
1
vote
1answer
289 views

How does knowing the factorization of N help to obtain the secret?

Assuming $x=a^2 \pmod n$ and knowing $x$, $p$, $q$ how is it possible to obtain $a$?
0
votes
1answer
820 views

Solving a quadratic equation for a variant of Rabin

My understanding of Rabin We have $p$ and $q$ which are distinct primes congruent to $3 \pmod 4$. Then we have $n = pq$. Encryption is done as $e(m) = m^2 \pmod n$, where $m$ is our message. ...
2
votes
1answer
681 views

Is Rabin's cryptosystem secure against known-plaintext attacks?

I've bee learning about Rabin's cryptosystem, and I already know that Rabin's cryptosystem is vulnerable to a chosen-ciphertext attack, but I was wondering, is it also vulnerable against known-...
1
vote
0answers
407 views

Rabin code same message sent with different $N$

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 ...
7
votes
2answers
202 views

Why is this authentication procedure using Rabin crypto not useful?

A friend asked me the following, pointing out that the method is not very useful (my problem is I do not see why it is not good): Consider a person A which chooses $n$ as the public key for the ...
2
votes
0answers
285 views

Rabin/RSA four possible messages?

Given this encryption method: $$f_{N,e} : Z^{*}_{N} \to QR(N)^{*};\quad f_{N,e}(x) = x ^{2e} \bmod N$$ I need to show that, for any $x_{0} \in Z^{*}_{N}$, there are four elements $x \in Z^{*}_{N}$ ...
3
votes
3answers
1k 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?
1
vote
1answer
231 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: ...