Programming Praxis

The RSA encryption algorithm, which we studied in a previous exercise, relies on the difficulty of factoring large integers for its security. Another cryptosystem was developed by Michael Rabin about the same time that Rivest, Shamir and Adelman were developing RSA, and is also based on the difficulty of factoring large integers. Although it is theoretically stronger than RSA, Rabin’s cryptosystem never became popular because in practice RSA is about equally strong, because RSA was first by about a year, and because Rabin’s cryptosystem requires additional work to disambiguate the decryption.

Rabin’s cryptosystem is based on two integers p and q each congruent to 3 modulo 4 which form the private key; their product, n = p × q, is the public key. Then to encrypt the message m, the ciphertext is c = m² mod n. The plaintext is recovered by finding the four square roots of c modulo m, and choosing the correct message from the four possibilities. Note that a text message is converted to a number m in the same way as RSA.

The four square roots of the ciphertext c are calculated as follows. First determine a and b satisfying the equation a × p + b × q = 1 using the extended euclidean algorithm of a prior exercise. Compute r = c^(p+1)/4 mod p. Compute s = c^(q+1)/4 mod q. Compute x = (a × p × s + b × q × r) mod n. Compute y = (a × p × s − b × q × r) mod n. Then the four square roots are m₁ = x, m₂ = −x, m₃ = y, and m₄ = −y.

The problem with Rabin’s cryptosystem is the decryption into four possible messages. The solution is to pad the message in such a way that only one of the four possible messages fits the padding. This is done by replicating the bits of the last portion of the message, adding them to the end of the message; only the correct decryption will have the trailing bits duplicated.

An example makes this clear. Consider p = 7, q = 11, and n = 77. By the euclidean algorithm, (−3)×7 + 2×11 = 1, so a = −3 and b = 2. Now we send the message 5₁₀ = 101₂, padded to the message m = 101101₂ = 45₁₀. The ciphertext is c = 45² mod 77 = 23. Decryption first computes r = 23² mod 7 = 4 and s = 23² mod 11 = 1. Then x = (−3)×7×1 + 2×11×4 mod 77 = 67 and y = (−3)×7×1 − 2×11×4 mod 77 = 45. Thus two of the square roots are 67 and 45, and the other two are 77 − 67 = 10 and 77 − 45 = 32. Now 10₁₀ = 001010₂, 32₁₀ = 100000₂, 45₁₀ = 101101₂ and 67₁₀ = 1000011₂, so only 101101₂ has the required redundancy and the payload is 101₂ = 5₁₀.

In normal usage, the Rabin cryptosystem is generally based on blocks of 512 bits, or 1024 bits, or 2048 bits, of which the last 64 bits consist of padding, giving a payload of 448, 960 or 1984 bits (56, 120 or 248 bytes), respectively; sometimes a padding of 128 bits is used, if there is some concern about the (very unlikely) possibility of a false duplicate. Another method that is sometimes used pads the message with 64 0-bits (or 128 bits instead of 64 bits, or 1-bits instead of 0-bits, or some other known pattern), so that only the square root with the desired pattern is used. The message is split into blocks of the needed size, and is extended by adding a 1-bit followed by as many 0-bits as are needed to make the message a multiple of the block length.

Your task is to write functions that generate keys and encrypt and decrypt messages using the Rabin cryptosystem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2