RESIDUE CIPHERS

Frank Rubin

December 4, 1994

In a recent article in this journal Shepherd, Sanders and Stockel (SSS) compare the quadratic residue cipher (QRC) to the well-known Rivest-Shamir-Adleman public key cipher (RSA). They indicate several areas in which the QRC falls short of expectations. In particular, they did not know of any method whereby the QRC could be used to authenticate a message. Such authentication is often called a "digital signature".

In this paper I will show how the QRC can be used to authenticate messages. I will also discuss several other aspects of using the QRC, such as speed and storage requirements, with the goal of showing that the QRC can be extremely competitive with the RSA for practical use. Then I introduce a double QRC which is faster and more secure than either the QRC or the RSA.

In the RSA algorithm, a user R who wishes to receive messages chooses a large number N as a modulus, and a number E as an enciphering exponent. N must be the product of two large primes. The two numbers N and E are published, or made publicly available. A sender S who wishes to send a message to R expresses the message as an integer M. The integer M is then raised to the power E modulo N, and the residue M' is sent to R as the enciphered message. If the message is long, it is broken into separate blocks, each of which is enciphered in this manner. Since R knows the factorization of N, R can determine the inverse exponent D to be used for deciphering. R then raises M' to the power D modulo N, thereby recovering the message M. The modulus N and the enciphering exponent E are called the public keys, and the deciphering exponent D is called the secret key.

The quadratic residue cipher was initially proposed by Blum, Blum and Shub in (BBS). In the QRC, each recipient R again chooses a modulus N which is the product of 2 large primes. To encipher a message, the sender S chooses an initial seed x

The low order b bits of each residue are XORed with the next b bits of the message. It has been shown that b = log

Notice that the security of RSA and QRC both rest on the known difficulty of factoring large numbers. Since it has been shown that general numbers as large as 129 decimal digits can be factored, in practice the modulus N should be chosen larger than 10

With the RSA, a sender can authenticate a message in the following way: Suppose S wishes to send a message to a receiver, R, so that R knows for certain that it was sent by S, and not by some third party. S creates an authenticating block, which might contain the sender's ID, the receiver's ID, a time/date stamp, and a secure checksum for the message. S then enciphers this block using S's secret deciphering key D, which is the inverse of S's public enciphering key E. This "digital signature" is then appended to the message, and the entire message is enciphered using R's public key. When R receives the message, the enciphered authenticating block is then deciphered with S's public key E. This produces the plaintext of the block. Since only S knows D, only S could have sent the message.

The same result can be accomplished using the QRC, but with a slightly more complex protocol. Suppose again that S wishes to authenticate a message to R. S begins by sending a message to R requesting an authenticating key. This message may be sent in clear. R produces this key by choosing a number K in the range 1 to N-1, where N is S's public modulus. (K cannot be chosen too near 1 or N-1, say less than N

Now S recovers K from K' and appends it to the message. In general there are four numbers which can be squared modulo N to produce K'. Including 80 bits of K along with K' makes it possible for S to choose K, and not any of the other square roots. The message is then sent to R using R's public modulus. When R deciphers the message, the presence of K verifies that S was the sender. Note that any user of the system can generate K and K' pairs at will. This would not allow that person to pose as S, however, since the value of K is chosen by the recipient, not the sender. Conversely, knowing 80 bits of K would not be enough to allow an eavesdropper to determine K from K' since N is at least 430 bits, and reducing the search size from 2

This protocol is very different from the protocol of a secret key cipher system. In a secret key system, keys must be securely protected when they are being transmitted. In this protocol the message requesting an authentication key and the key itself can be sent in clear, since an eavesdropper could not use the key to pose as the legitimate sender.

A second disadvantage which Shepherd, Sanders and Stockel cite for the QRC versus RSA is that in RSA the enciphered message will be the same length as the plaintext, while in QRC the enciphered message is longer by the addition of a delimiter and the final quadratic residue. This comparison exaggerates the advantage of the RSA.

The RSA enciphers a message in fixed-sized blocks. If the RSA modulus has B bits, then at most B-1 bits of the plaintext can be enciphered in each block. You cannot encipher B bits, because the numeric value of B bits of plaintext could be greater than the modulus. However, each transmitted block must be B bits long, since the result of the exponentiation in the RSA could be that long. Therefore the RSA has an inherent expansion factor of B/(B-1). (Actually, each ciphertext block could be kept to B-1 bits by repeatedly enciphering until that length was achieved, however this involves about a 50% increase in enciphering and deciphering time just to achieve perhaps a 0.3% decrease in message length.) Moreover, since the RSA requires a fixed block size, the last block of the plaintext will have, on average, only B/2 bits, assuming the lengths are uniformly distributed, while the ciphertext block will be B bits long. So the length will be increased by about B/2 bits per message.

In the QRC, the delimiter that (SSS) proposes between the end of the message and the final residue can be eliminated simply by making the residue fixed length. In this way, if the modulus has B bits, then the last B bits of the enciphered message will be the final residue. The QRC also enciphers using fixed sized blocks, and the last block will generally be padded. However, the block size in QRC is only log

Consequently, for short messages of less than B/2 blocks or B²/2 bits, the QRC ciphertext will be longer on average, by up to B/2 bits. For messages longer than B/2 blocks, the RSA ciphertext will usually be longer, and the amount is not limited.

The Shepherd, Sanders and Stockel article describes their implementation of QRC. They mention that for a 32K bit message 3640 quadratic residues are needed, and using an 800-bit modulus this takes about 338K of storage. This is easily handled in a current PC.

Actually, since they are using only 9 bits from each residue, only these 9 bits need to be saved, so the storage needed is only 32K, the same size as the message, plus the final residue, so 32K + 800 bits altogether. Further, if the message is transmitted as it is enciphered, then the only storage needed by the sender is for the enciphering program itself.

There is a disadvantage with long messages that the entire message must be received and stored before the final residue is reached. This residue is required before deciphering can begin. For very long messages, this could be a serious problem. One way around this would be for the sender to calculate the final residue beforehand, and append it at the start of the message. If the key, or initial residue is K, and the message consists of b blocks, then the final residue is K^(2

The article (SSS) compares the number of modulo multiplication steps that must be performed for RSA versus QRC. They go out of their way to be fair to RSA by assuming that the enciphering exponent for RSA is the prime 2

It is true that the process needed to decipher a message in QRC also takes a large number of multiplications to recover the key, however this is done only once per message, not once per block as for the RSA.

Having said this, let us try a numerical example. Suppose that we wish to encipher and then decipher a message of 10K bits using both RSA and QRC with a 512-bit modulus. With RSA we will need 20.04 blocks. Call it 20. To encipher and decipher each block takes about 768+18 or 786 modulo multiplications, making 15720 multiplications altogether.

To encipher and decipher the same message with QRC we break the message into 1138 blocks of 9 bits each. We need one multiplication per block for enciphering, and one for deciphering, or 2276 altogether. In addition, the receiver must determine the seed, which requires two large exponentiations, the first taking about 1.5(log

There is a way to make the speed comparison even more lopsided. Suppose that instead of one initial key x

I will demonstrate the problem with the high-order bits by using an example in decimal. Suppose that we had a sequence of true random numbers modulo 115, and we were using this to generate 3-digit enciphering keys. In the high-order digit position out of each 115 keys we will have, on average, the digit zero 100 times, the digit one 15 times, and the other digits would not occur at all. Obviously the high-order digit position is nowhere near uniformly distributed. In the second digit position we would have a zero 20 times (from 000 to 009 and from 100 to 109), a one 15 times, and all other digits 10 times each. This is closer to uniform, but not adequate for secure encryption. In the third position we would get the digits zero to four 12 times each, and the other digits 11 times each. This is even closer to a uniform distribution. In general, the further you go from the high-order digit, the better the distribution gets.

In the case of binary numbers, I would exclude the high-order 20 bits from the encipherment. (If we were using a single key sequence, I would exclude 40 bits, but the XOR evens the distribution by a square factor, so 20 bits is sufficient.) In multiplicative pseudo-random number generators, the low-order bits are typically the least random, that is, they may have a short period, while the magnitude of the number is the most random. Based on this observation, it may be better to XOR the 20 high-order bits to the 20 low-order bits, rather than merely to discard them. The ultra-conservative might fold the residue to 256 bits by XORing the high- and low-order halves.

For a 512-bit modulus, excluding the high-order 20 bits still leaves 492 bits for use. In the last block of the message, the number of bits used from each residue will match the block length. There is no need to pad the last block, as is done with the RSA, and no need for delimiter sequences, as proposed by (SSS).

With this double QRC, the above message would take 21 blocks of 492 bits each, with 4 multiplications to encipher and decipher each. The receiver takes 768+6 multiplications to determine each of the 2 seeds. The total is 1632 modulo multiplications altogether. This is now about 9.6 times as fast as RSA. (If we took the ultra-conservative approach and used only 256 bits from each residue, then we would need 40 blocks, and take 1708 multiplications, which is still 9.2 times as fast as RSA.) As before, the comparison to RSA becomes even more advantageous as the length of the message and the size of the modulus increase. The only disadvantage is that the message now requires two final residues to be appended, rather than one.

An additional advantage of the double QRC is that it will be resistant to a chosen ciphertext attack, since choosing the ciphertext and receiving the corresponding plaintext will reveal the XOR of the two key sequences, which cannot be separated. If the two key sequences are calculated with two independent moduli having the same bit length, then the period is longer by a square factor, and the security is enhanced to the same degree.

The sequence of quadratic residues beginning with a particular seed form a sequence of strong pseudorandom numbers. Here,

Suppose that the modulus N is of the form pq where p = 2p'+1, p' = 2p"+1, q = 2q'+1, and q' = 2q"+1 with p, p', p", q, q' and q" all prime. We will call a modulus N chosen in this manner a

The article (SSS) indicates that the process of choosing seeds for the enciphering sequence is intractable for the sender of the message since the sender does not know the factorization of the modulus. There seems to be no way for the sender to know whether the seed will have a long or short period, except to generate as many terms of the sequence as the message requires, and then to verify that the sequence has not repeated.

In fact the situation is far worse than they suspect! Even if the period were longer than the message, the eavesdropper could continuously square the final residue until it recurred. Then the entire sequence of residues would be known, and the eavesdropper could determine the initial residue from the message length. Therefore, it would appear

The true situation appears to be slightly less rosy than (BBS) claims, but far less glum than (SSS). I have tested every possible Blum modulus up to 46,340 and generated the full period for every possible seed. (The limit of 46,340 is due to the 31-bit word size of my PC. Any larger number would overflow when squared.) The results of this examination are summarized below.

Call a seed x

In practice, p and q are chosen to be at least 50 decimal digits each. p" and q" are about p/4 and q/4, respectively, so they are similarly large. The periods just given suggest that for all but the 9 doubly trivial seeds, the period will always be large enough for any conceivable message.

I will summarize the status of the QRC to RSA comparison by presenting a chart similar to Table 1 in (SSS), updated with the conclusions from the preceding sections.

RSA - Disadvantage. Requires many multiplications due to large exponents.

QRC - Advantage. Requires moderate number of multiplications due to small block size.

DQRC - Big advantage. Requires few multiplications due to large block size and small exponent.

RSA - Similar. Slight expansion per block. Last block padded.

QRC - Similar. No block expansion. No block padding. Requires appending final residue. Shorter than RSA for messages longer than B/2 blocks.

DQRC - Disadvantage. No block expansion. No block padding. Requires appending 2 final residues. Shorter than RSA for messages longer than 3B/2 blocks.

RSA - Advantage. Digital signature is easy to achieve.

QRC - Disadvantage. Digital signature requires a preliminary exchange of messages.

DQRC - Disadvantage. Digital signature requires a preliminary exchange of messages.

RSA - Disadvantage. May be solvable even if factorization is difficult.

QRC - Advantage. Proved as hard as factorization.

DQRC - Advantage. Proved as hard as factorization.

RSA - Balanced. Resistant to a chosen ciphertext attack. Eavesdropper can easily verify suspected plaintext.

QRC - Balanced. Vulnerable to a chosen ciphertext attack. Eavesdropper cannot verify suspected plaintext.

DQRC - Big advantage. Resistant to a chosen ciphertext attack. Eavesdropper cannot verify suspected plaintext.

RSA - Similar. Uses modulo multiplication of large numbers.

QRC - Similar. Uses modulo multiplication of large numbers.

DQRC - Similar. Uses modulo multiplication of large numbers.

RSA - Similar. No practical limit.

QRC - Similar. No practical limit.

DQRC - Similar. No practical limit.

(BBS) | L. Blum, M. Blum and M. Shub 1986. A Simple Unpredictable Pseudorandom Number Generator. SIAM Journal on Computing 15(2): 364-383. | ||||||||||||||

(RSA) | R. L. Rivest, A. Shamir and L. Adleman. A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Comm. ACM 21: 120-126. | ||||||||||||||

(SSS) | S. J. Shepherd, P. W. Sanders and C. T. Stockel. The Quadratic Residue Cipher and Some Notes on Implementation. Cryptologia 17(3): 264-282. |