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

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

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.

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

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

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

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

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

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.

1

RSA with $e = 2$ is Rabin, it works a bit differently and is slightly more mathematically involved, but it is a valid cryptosystem.

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