Batch RSA invented by Amos Fiat Described in Crypto 89 and J Cryptology 1997. RSA works as follows. The key owner chooses two secret primes p and q, and forms their product n = p*q. He then chooses a public exponent e relatively prime to p-1 and q-1. His public key is (n, e). To encrypt a message m into cyphertext c, m is raised to the power e, mod n: c = m^e mod n. To decrypt the message, the key holder calculates d as the multiplicative inverse of e mod (p-1)(q-1): d = 1/e mod (p-1)(q-1). He recovers m from m = c^d mod n. For simplicity, below we will write this as m = c^(1/e) mod n, where it is understood that the 1/e is done mod (p-1)(q-1). An RSA signature s on a message m is calculated as for a decryption: s = m^(1/e) mod n. The signature is verified by m ?=? s^e mod n. The time consuming part of an RSA decryption or signature is this exponentiation step. e can be chosen to be small, so encryption and verification is fast, but 1/e will generally be about the same size as n, so many multiplications must be done to raise a number to that power. Amos Fiat describes a method whereby multiple messages can be decrypted or signed using only one full-sized exponentiation. The "catch" is that the messages must all use different exponents with the same n. Here is a concrete example. You want to decrypt or sign two messages, M1 and M2, raising M1 to the 1/3 power and M2 to the 1/5 power. Perform the following steps: M12 = M1^5 * M2^3 I12 = M12 ^ (1/15) This is the only full-sized exponentiation needed. This gives: I12 = M1^(1/3) * M2^(1/5). This is the product of the two values that we want. Fiat uses a trick to disentangle the two values. He raises I12 to the 6th power. The number 6 is chosen so that it is a multiple of one of the two exponents, 3, and is 1 more than a multiple of the other exponent, 5: I12^6 = M1^2 * M2 * M2^(1/5) Therefore: M2^(1/5) = I12^6 / (M1^2 * M2) which is one of the values we need. Since I12 is the product of the two values we want, we can recover the other value just by dividing this into I12: M1^(1/3) = I12 / M2^(1/5) Here is another example. Suppose we want M3^(1/7) and M4^(1/11). (Note that we are using prime numbers for the exponents; the reason will be explained below.) We calculate: M34 = M3^11 * M4^7 I34 = M34 ^ (1/77) This gives us: I34 = M3^(1/7) * M4^(1/11) Again this is the product of the two values we want. As before we will raise this to a power which is 1 more than a multiple of one of the two exponents (7 and 11) and is a multiple of the other one. The smallest such power is 22. I34^22 = M3^3 * M3^(1/7) * M4^2 So we can divide to get M3^(1/7): M3^(1/7) = I34^22 / (M3^3 * M4^2) And we can divide to get the other value needed: M4^(1/11) = I34 / M3^(1/7) This illustrates how to derive two RSA roots using only one full sized exponentiation. A few small exponentiations are also needed, as well as two divisions, but these are much faster than doing the full exponentiation (raising to the 1/15 or 1/77 powers above). Fiat's idea can then be applied recursively. Note that in the examples above we had to take two full-sized exponentiation, M12 to the 1/15 power and M34 to the 1/77 power. We can combine both of these exponentiations into one just as was done above: M14 = M12^77 * M34^15 I14 = M14 ^ (1/1155) Now: I14 = M12^(1/15) * M34^(1/77) the product of the two values we want. We need an exponent which is 1 more than a multiple of 15 while being a multiple of 77, giving 615, or vice versa, giving 540. Choosing the latter since it is smaller we have: I14^540 = M12^36 * M34^7 * M34^(1/77) so: M34^(1/77) = I14^540 / (M12^36 * M34^7) and dividing gives the other factor: M12^(1/15) = I14 / M34^(1/77) These values can then be fed into the expressions above to recover M1^(1/3) and the other three values, all with only one full-sized exponentiation for the four messages. In general, finding the exponent for Ixx can be handled by the Chinese Remainder Theorem. However it requires that the two values be relatively prime. That is why the exponents used in Batch RSA must all be relatively prime, so that there is a solution to the value of the exponent for Ixx. As the number of values in the batch increases, the "small" exponents needed to recover the values increase as well. We saw above that the exponents went from 6 and 22 for the size-two batches to 540 for the size-four batch. This means that you reach a point of diminishing returns where increasing the batch size no longer provides much benefit. Fiat suggests a batch size of n/(log^2 n) messages, where n is the length of the full-sized exponentiation (e.g. 1000 for a 1000 bit modulus). This would correspond to about a 10 message batch for a 1024 bit key. Fiat describes a few situations where it may be appropriate to use different exponents for multiple RSA operations. In the case of a server issuing multiple RSA signatures it could define its public key to be (n, e1, e2, e3,...) and specify that the signature was valid for any exponent in the list. Then it could batch up signatures and use a different exponent for each one. Another case is "pure RSA" encryption, where the message itself is broken into blocks and each one is RSA encrypted. In that case the blocks could use successive exponents from the list, and the receiver could decrypt a batch of blocks using one large exponentiation. There is another case of interest to us, related to the task of searching through messages from a message pool, possibly steganographically hidden. That will be described in another message.