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.
51 questions
11
votes
1
answer
1k
views
Why aren't RSA public keys and signatures compressed in practice?
According to Bernstein[1], it is possible to compress RSA/Rabin public keys by a factor of 2 and 3. And compress signatures by a factor of 2. Apparently, by using Coppersmith's lattice methods.
I wasn'...
- 113
2
votes
0
answers
44
views
If rabin signature uses a hash function then why cant we use that hash function to sign a message?
About Rabin Signature link
According to this paper, the person who wants to sign a message M first appends a random byte string U.
=> M_new = MU
Then uses a compression function to get c = ...
- 21
0
votes
0
answers
299
views
CTF question with hint "Quadratic method to solve ifp problem"
I totally have no idea about this Rabin decrypt problem.
source code:
https://github.com/shanzhuer/myctf/blob/main/crypto/rabin.py
Inside there were $2^{21}$ times of encryption and decryption of ...
1
vote
0
answers
126
views
Clarification for CCA security (or - why is the following not a Rabin CCA attack?)
In three different, highly reputable sources (e.g. "Introduction to Modern Cryptography" by Katz and Lindell, 2007), the definition of CCA attack doesn't allow the adversary to decrypt the ...
- 413
1
vote
1
answer
252
views
Clarification regarding Rabin Cryptosystem being CPA (Chosen Plaintext Attack) secure
Do I understand correctly that the textbook Rabin encryption scheme, where there is no random padding (as is also required in RSA for it to be CPA secure), is not CPA secure? (it is deterministic ...
- 413
0
votes
1
answer
1k
views
Rabin Cryptosystem: Chosen-Ciphertext Attack
I read in literature that Rabin Cryptosystem can be broken using chosen-ciphertext attack. It is described that after chosen ciphertext is decrypted attacker can factorize public key $n$ by using ...
1
vote
1
answer
94
views
Is digital signature without schema possible?
In my application I want to use Rabin crypto system with short keys (like 128 bits) and MD5 for hashing. I found that schema like PKCS1-V1_5 or PPS does not allow you to have such small keys and ...
- 111
7
votes
2
answers
482
views
Rabin-Williams signature and it's reduction to factorization
Rabin signature is rightly celebrated as a signature scheme with provable reduction to factorization. How do we show that for Rabin-Williams signature as standardized, under the common and realistic ...
- 151k
2
votes
1
answer
235
views
Does Rabin function lose its one-way property if squaring mod a prime?
I am looking into various one way functions and I stumbled upon a Rabin function, which is squaring modulo an RSA modulus $N=pq$, where $p,q$ are prime: $R_N(x) = x^2 \mod N$.
Would it lose the one-...
- 207
1
vote
1
answer
208
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 ...
- 113
0
votes
1
answer
231
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 ...
- 25
1
vote
2
answers
246
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 ...
- 25
0
votes
0
answers
359
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 ...
- 9
0
votes
0
answers
181
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 ...
- 19
7
votes
0
answers
258
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 ...
- 16.2k