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.

learn more… | top users | synonyms

5
votes
2answers
128 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 ...
4
votes
1answer
57 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 ...
3
votes
2answers
173 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 ...
3
votes
1answer
129 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 ...
3
votes
1answer
84 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 ...
2
votes
2answers
238 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
3answers
715 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?
2
votes
1answer
142 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 $$...
2
votes
1answer
288 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
66 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
62 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 ...
2
votes
0answers
26 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 ...
2
votes
0answers
33 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 ...
2
votes
0answers
162 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}$ ...
1
vote
1answer
140 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: ...
1
vote
1answer
86 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.
1
vote
1answer
323 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
1answer
33 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: ...
1
vote
1answer
96 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 ...
1
vote
1answer
75 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 ...
1
vote
1answer
233 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$?
1
vote
0answers
227 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 ...
0
votes
1answer
50 views

Breaking the Rabin Signature system with chosen message attack

I heard that we can break the Rabin Signature system using chosen-message attack. I can't find a message to ask for its signature in order to spoof my message M. Any suggestions?
0
votes
1answer
315 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. ...
0
votes
0answers
43 views

Why does Rabin cryptosystem split the message into key blocks?

Why does Rabin cryptosystem split the message into key blocks and not into plain text blocks like in Merkle Damgard Construction? Is it because it acts in a way similar to IV? Probably not, it doesn'...
0
votes
0answers
118 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 ...
-2
votes
1answer
86 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 ...