|
RESIDUE CIPHERS Frank Rubin December 4, 1994 Abstract: In a recent Cryptologia article Shepherd, Sanders and Stockel compare the quadratic residue cipher (QRC) to the Rivest-Shamir-Adleman (RSA) public key cipher. They discuss a number of advantages of the QRC over the RSA, but also indicate a number of shortcomings. In this paper I attempt to redress some of those supposed shortfalls. I introduce the double quadratic residue cipher, which is both faster and more secure than either the QRC or the RSA. Keywords: public key, cryptography, digital signature, prime number, factorization, quadratic residue, double quadratic cipher. INTRODUCTION 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 x0 in the range 2 to N-2. Subsequent terms in the sequence are calculated by taking quadratic residues, namely xi+1 = xi² mod N. The low order b bits of each residue are XORed with the next b bits of the message. It has been shown that b = log2log2N bits can be used from each residue. The final residue is appended to the message and the resulting bit string is transmitted to the receiver. (This is not the residue used for enciphering the last block, of course, but the succeeding residue.) Since R chose the modulus and knows its factors, R can determine the initial seed directly from the final residue, and from that the entire sequence of residues. A third party who does not know the factors of N cannot determine the seed with any less work than would be needed to factor N. 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 10129. MESSAGE AUTHENTICATION 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 N2/3 or greater than N-N2/3, or else it will be easy for an opponent to obtain the desired square root modulo N. If K is chosen at random in the range 1 to N-1, the probability of such a choice is negligible.) R takes the quadratic residue K' of K and sends K' and the low-order 80 bits of K back to S. Again, this may be sent in clear, since nobody except S can recover K from K', and since K will be used only once. 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 2430 to 2350 is still infeasible. 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. MESSAGE EXPANSION 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 log2B bits, so on average only (log2B)/2 bits will be added to the message. 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. STORAGE 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^(2b) mod N. Here ^ indicates exponentiation. With a B-bit modulus this will take about (3/2)(B + log2b) modulo multiplications, and needs to be done only once per message. SPEED 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 216+1, which requires only 18 modulo multiplications for enciphering each block. This ignores the deciphering exponent. If the enciphering exponent has been specifically chosen to require as few multiplications as possible, then the deciphering exponent must require a large number of multiplications. There is no way to select the two exponents so that both are small and consist mostly of 0 bits. (This is apparent when you consider that the product of the two exponents must be at least on the order of the modulus, and therefore together they must have at least as many bits.) A randomly chosen B-bit exponent will require, on average, about 3B/2 multiplications to raise a number to that exponent. On that basis, with an 512-bit modulus the 768 or so multiplications per block needed for deciphering overwhelms the 18 multiplications for enciphering. 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(log21138) = 15.2 multiplications, and the second taking about 786 multiplications in the worst case. So the total for QRC is 3077. For this example, then, QRC is about 5.1 times as fast as RSA, and the comparison will become even more favorable to QRC as the message length and the modulus size increase. DOUBLE QUADRATIC RESIDUE CIPHER There is a way to make the speed comparison even more lopsided. Suppose that instead of one initial key x0 you have two independent keys x0 and y0, and generate two sequences xi and yi. The message is then enciphered by XORing with both sequences. We will call this a double QRC or DQRC. You may then use the entire residue, except for some high-order bits. 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. GENERATING SEEDS The sequence of quadratic residues beginning with a particular seed form a sequence of strong pseudorandom numbers. Here, strong indicates that the sequence appears to be truly random and unpredictable. This property makes the sequence cryptographically secure, provided that the sequence is longer than the message. If the sequence repeats, however, then this can be detected by an eavesdropper, and used to read the message. Therefore choosing a seed with a long period is essential to the security of the cipher. 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 Blum modulus. It is known that the maximum period that can be achieved divides 2p"q". Blum, Blum and Shub have "proved" the converse, namely that under these conditions 2p"q" also divides the maximum period, and therefore the maximum period is 2p"q". The authors give a condition for the seed which guarantees this period, but the condition requires knowledge of p and q. I put "proved" in quotes before because I have found that the foregoing is not entirely true. 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 a priori that the sender would need to carry the sequence forward further than any enemy would ever attempt in order to assure security. This is clearly infeasible. 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 x0 p-trivial if x0 mod p is either 0, 1, or p-1. Likewise, call the seed x0 q-trivial if x0 mod q is either 0, 1, or q-1. For the 9 degenerate seeds which are both p-trivial and q-trivial the period is either 1 or 2. For the 3(q-3) seeds which are p-trivial but not q-trivial, the period is either q" or 2q". For the 3(p-3) seeds which are q-trivial but not p-trivial, the period is either p" or 2p". For the (p-3)(q-3) seeds which are neither p-trivial nor q-trivial the period is either p"q" or 2p"q". (BBS) "proved" this period is always 2p"q", but for the modulus N = 47×719 = 33793 the period is actually p"q". For a given modulus, all of the seeds in each of the preceding 3 classes have the same period. 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. SUMMARY 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. Speed: 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. Message length expansion: 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. Possibility of a digital signature: 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. Formal proof of security: RSA - Disadvantage. May be solvable even if factorization is difficult. QRC - Advantage. Proved as hard as factorization. DQRC - Advantage. Proved as hard as factorization. Resistance to attack: 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. Algorithm complexity: RSA - Similar. Uses modulo multiplication of large numbers. QRC - Similar. Uses modulo multiplication of large numbers. DQRC - Similar. Uses modulo multiplication of large numbers. Message length limit: RSA - Similar. No practical limit. QRC - Similar. No practical limit. DQRC - Similar. No practical limit. REFERENCES
| ||||||||||||||||||||||||||||||||||||||||||||||||