by Neal R. Wagner
Copyright © 2002 by Neal R. Wagner. All rights reserved.
NOTE: This site is obsolete. See book draft (in PDF):
Michael Rabin discovered what I like to call a version of RSA, although it is more properly regarded as a public key cryptosystem in its own right. During its early history, this system was considered of theoretical, but not practical interest because of a ``fatal flaw'' (a quote from Donald Knuth) that made it vulnerable to a chosen plaintext attack. However, there is a way around the flaw, making this system a real competitor to RSA.
In the integers mod n, using both addition and mulitiplication mod n, if n in not a prime, then not every non-zero element has a multiplicative inverse. But also of interest here are elements that have a square root. The square root of an element a is an element b such that (b*b) % n = a. Some elements have several square roots, and some have none. In fact, number theorists have been interested in these matters for hundreds of years; they even have a special term for a number that has a square root: a quadratic residue. Thus this theory is not something new invented just for cryptography.
In elementary algebra, one learns that positive numbers have two square roots: one positive and one irrational. In the same way, for the integers modulo a prime, non-zero numbers that are squares each have two square roots. For example, if n = 11 then in Z11, 12 = 1, 22 = 4, 32 = 9, 42 = 5, 52 = 3, 62 = 3, 72 = 5, 82 = 9, 92 = 4, and 102 = 1. The following little table shows those numbers that have square roots:
| Numbers mod 11 | |
|---|---|
| Square | Square Roots |
| 1 | 1, 10 |
| 3 | 5, 6 |
| 4 | 2, 9 |
| 5 | 4, 7 |
| 9 | 3, 8 |
Notice that 1, 4, and 9 have their ``ordinary'' square roots of 1, 2, and 3, as well as an extra square root in each case, while 3 and 5 each also have two square roots, and 2, 6, 7, 8, and 10 each have no square roots at all.
Rabin's system uses n = p*q, where p and q are primes, just as with the RSA cryptosystem. It turns out that the formulas are particularly simple in case p % 4 = 3 and q % 4 = 3 (which is true for every other prime on the average), so the rest of this chapter makes that assumption about the primes used. The simplest such case has p = 3 and q = 7. In this case the table of square roots is the following:
| Numbers mod 21 = 3*7 | |
|---|---|
| Square | Square Roots |
| 1 | 1, 8, 13, 20 |
| 4 | 2, 5, 16, 19 |
| 7 | 7, 14 |
| 9 | 3, 18 |
| 15 | 6, 15 |
| 16 | 4, 10, 11, 17 |
| 18 | 9, 12 |
Here the ``normal'' situation is for a square to have four different square roots. However, certain squares and square roots have either p or q as a divisor. In this case, each square has two square roots (shown in red italic above). Of course, all the numbers not appearing in the left column don't have a square root. Here is a program that creates the above table: Square Roots mod n = p*q. This same section gives a table for p = 7 and q = 11, again satisfying the special Rabin property. In the table about, it looks as if there are a lot of red italic entries, but in fact there are (p+q)/2 - 1 = O(p+q) such squares with p or q as a factor, while there are (p*q + p + q - 3)/4 = O(p*q) squares altogether. An actual Rabin instance will use very large primes, so that only a vanishingly small number of them have the divisibility property, and the chances of this happening at random can be ignored.
Each user chooses two primes p and q each equal to 3 modulo 4, and forms the product n = p*q.
In the special case in which both primes when divided by 4 give remainder 3, there are simple formulas for the four roots:
Formulas for the four square roots of a square c. Calculate:
Now the four square roots are m1 = x, m2 = -x, m3 = y, and m4 = -y. In case m and hence c have p or q as a divisor, the formulas will only yield two square roots, each also with p or q as a factor. For the large primes used in an instance of Rabin, there is a vanishingly small chance of this happening. (Picture the chances that a 512-bit random prime number happens to divide evenly into a message!)
The complexity of Rabin's system (the difficulty of breaking it) is exactly equivalent to factoring the number n. Suppose one has a Rabin encryption/decryption machine that hides the two primes inside it. If one can factor n, then the system is broken immediately, since the above formulas allow the roots to be calculated. Thus in this case one could construct the Rabin machine. On the other hand, if one has access to a Rabin machine, then take any message m, calculate c = m2, and submit c to the Rabin machine. If the machine returns all four roots, then m and -m give no additional information, but either of the other two roots minus m will have one of p or q as a factor. (Take the GCD of it with n.)
The same proof that breaking Rabin is equivalent to factoring n provides what has been called a ``fatal flaw'' in Rabin's system. The above argument is just a chosen ciphertext attack. It is not wise to allow an opponent to mount such an attack, but one would also not want a cryptosystem vulnerable to the attack, which is the case with Rabin's system. (However, see the next section.)
In order to distinguish the true message from the other three square roots returned, it is necessary to put redundant information into the message, so that it can be identified except for an event of vanishingly small probability. The Handbook of Applied Cryptography suggests replicating the last 64 bits of any message. Or one could use 0s as the last 64 bits. In these or similar cases, the Rabin machine would be programmed to return only messages with the proper redundancy, and if 2-64 is not a small enough margin of error, then just choose more than 64 redundant bits. Then the attack described above doesn't work any more because the Rabin machine will only return a decrypted message (a square root) with the proper redundancy. Thus the Rabin machine returns at most one square root, and possibly none if someone is trying to cheat. (The probability of having two square roots with the given redundancy is again vanishingly small.) Breaking the new system is longer formally equivalent to factoring n, but it is hard to imagine any cryptanalysis that wouldn't also factor n.
Hugh Williams gave another variation of Rabin's cryptosystem that avoids the ``fatal flaw'' in a mathematically more elegant way.
Here is an example with tiny values for the primes. Of course a real example would use primes in the range from 512 to 1024 bits long, just as in the case of RSA.
Take p = 7, q = 11, and n = 77. Then (-3)*7 + 2*11 = 1, so that a = -3 and b = 2.
Suppose one uses 3-bit messages whose bits are then replicated to give 6 bits, up to the number 63. Messages must be in the range from 1 to 70, so this system of redundancy will work. Start with data bits 1012 or 510. The replication gives 1011012 or 4510. Then c = m2 mod 77 = 23. Continuing the calculations, r = 232 mod 7 = 4, and s = 233 mod 11 = 1. Finally, x = ((-3)*7*1 + 2*11*4) mod 77 = 67 and y = ((-3)*7*1 - 2*11*4) mod 77 = 45. These are two of the four square roots, and the remaining two are -x mod 77 = 10 and -y mod 77 = 32. In binary, the four square roots are 67 = 10000112, 45 = 1011012, 10 = 0010102, and 32 = 1000002. Only 45 has the required redundancy, so this is the only number that this modified Rabin machine will return.