Hot answers tagged rabin-cryptosystem
A is acting as a square-root oracle in that protocol. We can use that oracle to factor $n$ and break the scheme. Suppose you are an attacker that wants to impersonate A. You: Pick a random $m$; Send $m^2$ to A; Compute $p = \gcd(m_1 - m, n)$, thus factoring $n$. This works with probability $1/2$ for each attempt.
The modulus 77 leads to a short period.
Because $r$ is not guaranteed to be a Quadratic Residue, so for random $r$ there wouldn't be $m_1$ such that $r \equiv m_1^2(\mod n)$, therefore authentication will be impossible in this case.
Nightcracker's method works fine. There also are deterministic solutions to select the correct ciphertext that require very few additional bits. One very useful ingredient is the use of the Jacobi symbol. For example, you might look at The Rabin cryptosystem revisited by M. Elia, M. Piva and D. Schipani (http://arxiv.org/pdf/1108.5935.pdf).
This is a solution that should work with very high probability, but possibly can fail. As a bonus it also resists tampering with the ciphertext. As encrypter generate a random key (say a 128-bit key for AES128-CTR) and encrypt the plaintext using that key. Then compute a MAC over the ciphertext (for example using HMAC-SHA1) using the same key. Finally you ...
Both Rabin and RSA rely on padding for security. Proper padding prevents chosen-ciphertext attacks since modified ciphertext has a negligible chance of producing valid padding. If you claim Rabin (or RSA) is vulnerable to CCA attacks, you should limit that to the unpadded/textbook variants. Most deployed implementations use padding, though some paddings ...
At first I want to cite Lindell and Katz book: A "plain Rabin" encryption scheme, constructed in a manner analogous to plain RSA encryption, is vulnerable to a chosen-ciphertext attack that enables an adversary to learn the entire private key. Although plain RSA is not CCA-secure either, known chosen-ciphertext attacks on plain RSA are less damaging ...
That practice of replacing the result of $y=x^d\bmod N$ (or $y=x^e\bmod N$) by $\hat y=\min(y,N-y)$ is also in ISO/IEC 9796-2:2010 (paywalled) and ancestors; I first met that in [INCITS/ANSI]/ISO/IEC 9796:1991, also given in the Handbook of Applied Cryptography, see in particular note 11.36. ISO/IEC 9796 was a broken and now withdrawn ...
An older copy of P1363 Public Key Cryptography was used below. In may (or may not) reflect the current state of affairs. It also uses Bernstein's RSA signatures and Rabin–Williams signatures: the state of the art. Do tweaked roots violate P1363? What I might be really asking is, does an exponent of 2 run afoul of P1363, but I'm not sure at the moment. ...
Blinding is usually applied on the whole modulus, and I see no incentive to do otherwise; random is cheap. In RSA, blinding is not always applied as described in the question and article, for efficiency and security reasons: the technique described requires computing $r^d\bmod N$, which is just as costly as the $m^d\bmod N$ operation being protected, and ...
The tricky point is that modulo a Blum integer (the product n = pq of two primes p and q that are equal to 3 modulo 4), in general, a quadratic residue (a value that is a square of something) has four square roots, not two. Consider the "normal" Rabin algorithm. Message m is encrypted into c = m2 mod n. To decrypt, you work modulo p and ...
Only top voted, non community-wiki answers of a minimum length are eligible