Talk:Rabin cryptosystem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Cryptography / Computer science  (Rated Start-class, Top-importance)
WikiProject icon This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the quality scale.
 Top  This article has been rated as Top-importance on the importance scale.
Taskforce icon
This article is supported by WikiProject Computer science (marked as Top-importance).
 

Only the signature, not encryption is as secure as integer factorization[edit]

If the message m squared m*m is smaller than n, since m can be calculated as the square root (without remainder) independend of n, p and q. In such a case the encryption is not secure at all. 109.90.224.162 (talk) 15:04, 21 September 2015 (UTC)

Evaluation , a proposal[edit]

As discussed in other sections of this discussion page, it is not exactly clear, why a chosen ciphertext attack should break the Rabin Cryptosystem.
To shed some light on what Michael Rabin wrote in his original paper and what exactly the problem is, I propose to include a subsection under "Evaluation", which explains how finding square roots is connected to factoring the public key. I propose to use an example based on the two prime numbers "p=19","q=23","n=p*q=323". Rough outline:

  • Start with "k*k = s mod n", that means that "k" is one of the square roots of "s".
  • "n-k" is another square root of "s", because "(-k)*(-k) = s mod n". So "-k = n-k mod n" is the second square root of "s".
  • Now from Rabins paper we know, that there has to be another number "h", with "h != k mod n" and "h != -k mod n", so that "h*h = s mod n".
    This "h" is the third square root of "s".
  • "-h" is the fourth square root of "s".
  • Rabin shows that if you can find two square roots "k" and "h", with "h != k mod n" and "h != -k mod n", then you can very easily calculate "p" and "q", because:
    either "gcd(k-h,n) = p" or "gcd(k-h,n) = q". (gcd here means Greatest common divisor).
  • Example: "p=19,q=23,n=p*q=437". "s=233", "k=200, -k=237", "h=85, -h=352". (Simple check: "k*k mod n = 200*200 mod 437 = 233 = s")
    "k-h=200-85=115", "gcd(115,437) = 23 = q", voila we found one of the two prime factors.
  • Consequences:
    • Any attacker can create pairs of "k" and "s": Simply randomly generate a "k" and calculate "s = k*k mod n" ("n" is public).
    • If an attacker can additionally find "h" with "h != k mod n" and "h != -k mod n", the attacker is able to find "p" and "q".
      This is exactly what Rabin proves in his paper: Finding square roots "mod n" is as hard as factoring "n", because if you have the square roots you can efficiently calculate the prime factors of "n". Note: This of course applies to any cryptosystem, which relies on the assumption that factoring is hard (like for example this also applies to RSA).
    • What has to be avoided at all costs is, that the owner of the private key ("p" and "q") calculates such a "h" ("h*h = s mod n, h != k mod n, h != -k mod n") and sends it back to the attacker. If this should ever happen, the attacker can easily calculate "p" and "q" as shown before.
    • Possible threat: There exist "h" for which "h*h = s" with "1<=s<n" (important here, no "mod n"!). You can calculate "h" from "s" easily in this case (simple integer square root algorithm). When using Rabins Cryptosystem for signatures the signer should make sure that the signature "k", with "k*k = s mod n" does not produce a "s" which has an integer square root; of course the probability that this ever happens is minuscule and can be easily avoided completely. Again all this applies to any cryptosystem based on prime factors: An attacker can always create a huge amount of random "k*k = s mod n" pairs and check if "s" has an integer square root; this is just a randomized way to factor "n".

In my opinion the last two points are, why some people seem to say that Rabins Cryptosystem is vulnerable. But of course this is only true, if you construct the protocol in such a way, that the owner of the private key does send back the critical "h" square root. This can be easily avoided or at least I really cannot think of any scenario in which it cannot be avoided. Of course in a way this means that Rabins Cryptosystem is more "sensitive" (lack of a better word) in a manner than RSA:

  • Rabin: If you have a "ciphertext(s) <-> plaintext(k)" pair, then there exists an alternative "plaintext(h)" which MUST NOT be revealed by the owner of the private key. (Revealing a stand-alone "ciphertext(s) <-> plaintext(k)" pair DOES NOT break anything!).
  • RSA: There are only pairs of "ciphertext <-> plaintext" and no alternative "plaintext" exists. Revealing such a "ciphertext <-> plaintext" pair does not break anything.

Note under the "Security" section it says that: "(This assumes that the plaintext was not created with a specific structure to ease decoding.)". If you read what I wrote above, this quote is nonsense: ANY plaintext "k" (regardless of structure) produces a ciphertext "s" with "s = k*k mod n". If an attacker can find the an alternative plaintext "h", so that "h != k mod n" and "h != -k mod n", the cipher has been broken; this is true for ALL plaintexts "k", so why has that anything to do with the structure of the plaintext ? Lundril (talk) 13:26, 14 September 2011 (UTC)

Rabin for signatures, and Blum-Williams modification[edit]

Rabin cryptosystem is not a permutation, so there may be issues when used for pubkey encryption, but there should not when used in signature schemes. Can somebody write something about this?

answering to myself... Ok, Rabin is totally insecure as a signature scheme under CCA. —Preceding unsigned comment added by 85.124.63.18 (talk) 23:03, 21 January 2009 (UTC)

Also, Blum and Williams have suggested to use primes p and q which are both equivalent to 3 mod 4, in which case the solution is unique, i.e. the scheme becomes a permutation. Can somebody write something about this as well?

Thanks, 141.201.123.144 (talk) 14:44, 19 January 2009 (UTC)

Security[edit]

The security stuff on this page is definitely wrong -- appropriate padding makes Rabin stronger, not less strong. I'll try and fix it when I have time ciphergoth 10:26, 2004 Nov 16 (UTC)

It's been fixed, I think. —Lowellian (reply) 01:50, 15 March 2006 (UTC)

From the page:

By adding redundancies, for example, the repetition of the last 64 bits, the system can be made to produce a single root. This thwarts the chosen-ciphertext attack, since the decoding algorithm then only produces the root that the attacker already knows. If this technique is applied, the proof of the equivalence with the factorization problem fails, so it is uncertain as of 2004 if this system is secure.

This is not followed by a reference and I think it is simply not true ? As far as I understand the proof of the equivalence with the factorization problem (I read the original paper), the equivalence simply means: If someone is able to compute FOUR square-roots from only a single number, then from these FOUR square-roots, you can factorize "n". Now "n" is public; so an attacker ALWAYS will know "n". So how would an attacker break the system by Chosen Ciphertext Attack: He would repeatedly give the decryption oracle a ciphertext which was simply created by choosing a random number X and then calculating "X*X mod n".So the attacker already knows two square roots of "X*X" (X itself and N-X), if the decryption oracle gives him a third square root Y (so that Y*Y=X*X mod n), then the attacker knows all four square-roots and thus can factor "n".

I do not see at all why putting redundancies in "X" (the number from which the cipher text X*X mod n is created) does have anything to do with the equivalence to factorization. It simply means an attacker will always get back X instead of Y. The equivalence to factorization is not touched by that fact. It also means that an attacker cannot chose X arbitrarily any more, so it puts constraints on the attacker. I completely fail to see why this should weaken the cipher.

I also find it strange that people seem to have some bad feelings about putting redundancy in X. If you use RSA with 2048 to encrypt a message, the message (in current crypto systems) usually is a symmetric key comprised of something like 256 bits. For encrypting this key, first a number with 2048 bits is produced by padding the 256 bits with something like Optimal Asymmetric Encryption Padding. So RSA also uses padding, so why does it seems to be a problem for Miller Rabin encryption to use some padding in X to introduce some redundancies ?

A comment about costs: It is claimed that because the decryption algorithm needs to calculate four square roots that decryption introduces additional costs. Well yes, but these "costs" are completely marginal when compared to the costs you need to find the square roots "mod p" and "mod q" or compared to calculating the logarithm "mod n" for RSA: Generating the four square roots takes 4 additions/subtractions "mod n", speaking of "additional costs" gives the impression that these costs are high and this is simply wrong... 92.194.229.8 (talk) 11:14, 6 June 2009 (UTC)

I can only totally agree to that analysis. I really would like to see that paper that says that rabin cryptosystem is insecure against chosen ciphertext attacks. This really only applies if you implement it in a fairly dumb manner (oracle which for a given ciphertext produces the four square roots and then RANDOMLY selects one of the square roots and sends it back to the attacker). For non-signature applications (like exchange of a symmetric key for setup of a secure communcation channel) this really is NO problem at all, because the sender (the one which encrypts by using the public key) simply can be forced to additionally send proof of the secret (like for example a hash key of the secret) and the decrypting entity will simply check which square root was used by checking the proof.
For signature applications the problem is more complicated, because in this case the decrypter needs to proof that it is able to generate square roots by providing one for a cipher text which is generated out of the data which should be signed. But still it is not clear how an attacker could use that: In the signature scenario the decrypter has TONS of freedom how exactly it proofs that it can calculate square roots. The DECRYPTER (and not the attacker) has full control over the signature process, so it is completely unclear how an attacker should be able to lure the decrypter into providing useful information...
You really get the feeling that rabin cryptosystem is dismissed for completely different reasons (marketing; RSA is patented and probably some people pay license fees.) — Preceding unsigned comment added by 92.194.141.107 (talk) 01:01, 14 September 2011 (UTC)
I disagree. Section 7.2.4 of the lecture notes by Goldwasser and Bellare confirms the quote from the article. There Goldwasser and Bellare explain that adding sufficient redundacy to the plaintext before encrypting it, has the consequence that proof of equivalence of the cryptosystem and factoring no longer works. Concretely, the section concludes with
"Therefore, either Rabin's scheme is not equivalent to factoring, which is the case when inverting on a sparse message space, or (when M is not sparse) it is insecure before a chosen ciphertext adversary."
First of all is there any way to point a reader of the article to this section ?
I just read the section and I think it would help if the argument would be repeated in a more readable fashion in the article:
Let me try to explain: Rabin proved that if you can calculate the four square roots of a single arbitrary number "c" (the ciphertext == encrypted message), then you can factorize n (the public key). Now if you limit the message space (by enforcing certain patterns in the message), then it might be that for this particular message space an adversary can decrypt ciphertext, but is still not able to factor the public key; so if you limit the message space, then decrypting might not be as hard as factoring. A trivial example: We have an N (public key) with 1024 bit and we limit the message space to numbers "0 .. 2^400-1" (so numbers with a length of 400 bit maximum). The ciphertext "c = m*m mod n" will have at most 800 bit (since m is at most a 400 bit number) meaning that you never actually did any modulo operation. An adversary has to find the integer square root of your 800 bit ciphertext. Calculating integer square roots is easy, so an adversary can easily reverse the encryption and will still not be able to factorize "N". Conclusion: If you enforce certain patterns on the message to be encrypted, then it is not clear that decrypting is as hard as factoring.
My problem with this whole argument: There is a much better way. Instead of enforcing a pattern on the message, enforce that the encrypter additionally has to send a cryptographic hash of the message along with the ciphertext. With this approach decrypting is as hard as factoring and you defeat chosen ciphertext attacks. Lundril (talk) 18:20, 15 September 2011 (UTC)
Of course, the chosen ciphertext attack can be prevented by chosing an appropriate padding scheme, though like RSA this is not completely trivial. E.g. the proposal above to append a hash of the encrypted message loses semantic security and thus is not appropriate. Claims what constitutes a good padding scheme should therefore come with a citation, this discussion page is not the right place to argue that a certain padding is not susceptible to an attack. 62.202.80.11 (talk) 00:55, 15 September 2011 (UTC)
I did not mean padding. I meant encrypt your message (without padding), and additionally to the ciphertext you must send a cryptographic hash of your unencrypted message (cleartext). This kind of step is not necessary with RSA, because RSA is a 1-to-1 mapping whereas Rabin is a 4-to-1 mapping. The chosen ciphertext attack against Rabin as far as I can tell works like this:
  1. You enforce a certain pattern on the message to be encrypted to make sure, that the decrypter can pick the right square root.
  2. A lot of messages have to fit that pattern (otherwise it is not clear that decryption is equivalent to factoring).
  3. You have an oracle to which you can send ciphertext and it will return the decrypted message (provided there is a decrypted message, which fits the enforced pattern).
  4. An attacker randomly produces ciphertext, by picking a message which does NOT fit the pattern and encrypting it (c=m*m mod n).
  5. The oracle tries to decrypt the ciphertext.
  6. Since there ar many messages which fit the enforced pattern, after a reasonable amount of time the attacker will find a ciphertext for which the oracle produces the decrypted answer.
  7. With this decrypted answer (second pair of square roots), the attacker is able to reproduce the private key (p,q).
By enforcing that a sender must additionally send a cryptographic hash of the unencrypted message, this attack is thwarted and you do not need to put any constraints on the message (which would prevent equivalency to factorization). To reproduce the private key, an attacker would have to
  1. pick a number "x", generate ciphertext "c = x*x mod n"
  2. generate a cryptographic hash "h", which fits to the unknown alternative square root "y".
  3. Ask the oracle to decrypt "c"
  4. The oracle produces "y" and answers because "h" fits "y".
  5. The attacker can now reproduce the public key (p,q)
The question is how should an attacker be able to produce the cryptographic hash "h" ?
The whole chosen ciphertext against Rabin stuff only works under the assumption that an oracle will produce answers to a given ciphertext with high probability. And yes: It is pretty easy to prevent this. BTW: If anybody suddenly suggests this scheme of adding a cryptographic hash of the unencrypted message: I proposed it first :-). Lundril (talk) 18:55, 15 September 2011 (UTC)

Duplicate[edit]

It appears that this article is duplicated on the Rabin-Williams encryption page. I suggest that the best parts of each of the explanations be taken to form a single article and a redirect be made from the redundant page. Which page becomes the redundant page depends on which name is most appropriate. Does anyone know how this scheme came to be known under two names?

Worked Example[edit]

In the example given on the page, mq = 9. By my calculations, mq = 2.

mq2 (congruent to) c mod 11
mq2 (congruent to) 15 mod 11
mq2 = 4
mq = 2

Apologies for poor formatting.

--Newheroicideal 15:07, 25 March 2007 (UTC)

No-one seems to object, so I changed it myself. --Newheroicideal 15:18, 2 April 2007 (UTC)

In the article square roots are computed using . Thus is the correct result. But, notice that . Hence 2 is the other square root of modulo 11, just not the one computed with described method. 85.2.2.33 20:33, 2 April 2007 (UTC)

Legendre Symbol[edit]

From follows that c is a quadratic residue. Hence

Why is this so? Doesn't seem to be correct to me after reading an article on Jacobi symbol... —Ram3ai (talk) 21:25, 17 January 2008 (UTC)

If then for some integer n. So . reetep (talk) 11:27, 18 January 2008 (UTC)

What is 'r'[edit]

In decryption section a variable 'r' appears "out of the blue", then proabably reused by a possible solution. This proabably comes from different editors not keeping consistency. Even knowing what a Rabin scheme is, it introduces much confusion. —Preceding unsigned comment added by Janislaw (talkcontribs) 14:48, 14 January 2009 (UTC)

1 or 6?[edit]

From the article:

In our example we get and .

Since we took p=7, m=20, the first remainder must equal 6 and not 1 (unless any other possible input is considered). Isn't it the case? --Microcell (talk) 19:38, 18 November 2012 (UTC)