# Tag Info

9

Since n = pq, then when an integer modulo n is a square, then it has (in general) four square roots. This can be seen by reasoning modulo p and modulo q: a square has two roots modulo p, and two roots modulo q, which makes for four combinations. More precisely, modulo a prime p, if y has a square root x, it also has another square root which is -x. The same ...

9

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.

8

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

7

Unless they did something wrong (either accidentally, or deliberately to make it easy), there is no practical way. It's well known that, if you're able to compute the squareroot of an arbitrary number modulo a composite, you can efficiently factor that composite. And, solving $e=4$ is equivalent for solving the RSA problem twice with $e=2$. Now, it's ...

6

Adding some more information to fkraiem's answer: The encryption in the Rabin cryptsystem is basically textbook RSA with an exponent of $2$. 1) Neither p nor q are equal to 2. This means they are odd. The product of (p−1)(q−1) would be even i.e. not coprime with 2. Well, yes. That is one of the basic problems in Rabin's cryptosystem. If we want that $$c=... 5 Rabin-Williams signature verification with 3072 bit keys is much faster than EdDSA signature verification of comparable security (when done in software). How much depends on care of coding, hardware, EdDSA parameters. Two data points: in the eBATS benchmarks for a skylake CPU, ronald3072 signature verification (RSA with e=3 as an OpenSSL wrapper, by ... 5 Note: It is assumed familiarity with finite ring \mathbb Z_w, polynomial ring, and standard notation; see final section. Decrypting in the Rabin cryptosystem of the question involves solving for m the equation m^2\equiv a\pmod{p\,q} . This is performed by solving m^2\equiv a\pmod p and m^2\equiv a\pmod q (each yielding two solutions in most cases),... 5 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 ... 5 The modulus 77 leads to a short period. 4 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. 4 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). 4 After another 5 minutes of thought, I think I solved my own problem. Choose an arbitrary message m, compute c=m^2 % n and submit c and n to the Rabin oracle. If you repeat this enough times (by which I mean probably within 2 iterations) you will choose m in such a way that the oracle gives you ± the other root, which you can then use to factor n. 3 The definition of the Rabin cryptosystem in the question likely is similar to: Setup: choose p and q large distinct primes with p\equiv q\equiv 3\pmod 4 ; compute and publish public modulus n=p\;q, and publish it as the public key; the private key is p,q . Encryption of message (representative) M with 0\le M<n : compute ciphertext C=M^2\... 3 As first step to compute the four square roots of c \pmod N one can compute the two square roots \mod p and the two square roots \mod q and then using the Chinese Reminder Theorem combine them to the four square roots \mod N where N = p \cdot q. Let's start computing the square root of ciphertext c \mod p. Usually p \equiv q \equiv 3 \pmod 4. ... 3 You heard incorrectly. Rabin signatures as proposed in his 1979 paper include (randomized) hashing of the message, which completely prevents the attack given reasonable choices of hash function. The scheme without message hashing was never proposed, and should be called something like "oversimplified Rabin-like signatures" to avoid confusion. I recommend ... 3 Here's how the attack works: Select a random value y Compute a = y^2 \bmod n Ask for the signature of a, that is x with x^2 = a If x \ne y and x + y \ne n, then \gcd(n, x+y) is a proper factor of n The last step will succeed with probability \approx 0.5. You can make it probability 1 if you select a y with Jacobi symbol -1. 3 In short words: when you compute things modulo n = pq, you are really computing things simultaneously modulo p and modulo q. That's the gist of the Chinese Remainder Theorem. So to prove that a = b \pmod n, you just have to prove that a = b \pmod p and a = b \pmod q. Modulo p, for any x that is not a multiple of p, x^{p-1} = 1 \pmod p (... 3 Why is the Rabin mapping: f_i(x_i)=x_i^2 \bmod N_i not a Permutation over \mathbb{Z}_N^*? Because it maps distinct inputs to the same output. For example, f_i(1) = f_i(N_i - 1), with both being 1 3 I doubt this is an encryption scheme, except in the limited sense of that in code obfuscation. If indeed this is the decryption part of an encryption scheme, that's a very weak one: it is a symmetric encryption scheme which decryption key is n, and two distinct plaintext/ciphertext pairs are typically enough to recover that key. Often n=\gcd({c_0}^2-m_0,{... 3 Would [f_N(x)=x^2\bmod N] lose the one-way property if N is prime and not a product of two primes? Yes, thanks to the Tonelli-Shanks algorithm (special cases here). [Is] Rabin function still one-way if factorization of N=pq is known? No, because the main ("only") information advantage the private key holder has in the Rabin cryptosystem ... 2 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 ... 2 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 ... 2 By following the above advice (taking the equations for r and s given in the article and writing r-s) you will notice that q is a divisor, therefore GCD(|r-s|,n) cannot be 1. There are only two options left since n is only divisible by q and p. 2 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 are ... 2 RSA with e = 2 is Rabin, it works a bit differently and is slightly more mathematically involved, but it is a valid cryptosystem. 2 The equation a = x^2 \bmod N has at most 4 solutions x. There are solutions if a is a square modulo both p and q. This can be checked by computing the Legendre of symbol of x modulo p and modulo q. Assuming that the two Legendre symbols are +1, when p \equiv 3 \pmod 4, a square-root of a modulo p is given by x_p = a^{(p+1)/4} \... 2 How much will we have solutions? Assuming: p, q, r, ..., z are distinct odd primes b is relatively prime to n There exists at least one solution Then, yes, there will be precisely 2^k solutions. This is straight-forward to show; as we know there exists a solution x_0 such that x_0^2 = b \pmod n, then this implies that:$$x_0^2 = b \pmod p ...

2

The intended users know, in fact choose $p,q.$ The attackers aren't supposed to know. Once you know $p,q,$ you use the Chinese Remainder Theorem for efficient computations.

2

With proper choice of key and padding, the most efficient purely cryptographic known attack on Rabin signature and RSA (encryption and signature) is the same: factoring the public modulus. Therefore, size recommendations for the public modulus are the same. If 3072-bit RSA achieves 128-bit security by some criteria, Rabin does. Beware that there can be ...

2

We are given $n>4$ and ciphertext $c\in(0,n)$ for textbook Rabin encryption. We want to solve for $x\in[0,n)$ the equation $x^2\bmod n=c$. We found that $n$ is a square, computed $p=\sqrt n$, found that it is prime, solved $y^2\bmod p=c\bmod p$ yielding two roots $y_0\in(0,p/2)$ and $y_1=p-y_0$, and now want the solutions for the original equation. Every ...

Only top voted, non community-wiki answers of a minimum length are eligible