# Tag Info

7

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.

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

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

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 $$... 5 The modulus 77 leads to a short period. 5 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 ... 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 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 ... 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 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 ... 3 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 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. 2 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 (... 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} \... 1 Consider two numbers a and b that square to the same value modulo n and don't just differ by the sign.$$a^2 \equiv b^2 \pmod n2(a-b)(a+b) \equiv 0 \pmod n Neither of the factors on the left is 0 (or equivalently a multiple of $n$), thus each of them must contain one of the prime factors of $n$. Thus you can use $\operatorname{GCD}(a-b, n)$ ...

1

Let $\mathcal A$ be the hypothetical algorithm in the question, with input $(n,q)$, output $r$, such that $r^2\equiv q\pmod n$ for a $1/(\log(n))$ fraction of the quadratic residues $q\pmod n$, running in random polynomial time w.r.t. $\log(n)$, restricting to $n$ product of two large distinct primes. Let $\mathcal F$ be the following algorithm with input $... 1 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 ... 1 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. ... 1 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 ...

1

Your question is related to the well known RABIN Cryptosystem which is similar to RSA, except the public exponent is 2. As fgrieu mentioned, decipherment can be easily processed by the CRT algorithm, but some precautions must beforehand be observed during the key generation. In fact the solution of the equation gives 4 roots, which means that the solution ...

1

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