This is a generalization of RSA (see Section 19.3) [217,212]. The modulus, n, is the product of two primes, p and q. However, instead of choosing e and d such that ed ≡ 1 mod ((p − 1)(q − 1)), choose t keys, Ki, such that
K1 * K2 * . . . * Kt ≡ 1 mod ((p − 1)(q − 1))
MK1 * K2 * . . . * Kt = M
this is a multiple-key scheme as described in Section 3.5.
If, for example, there are five keys, a message encrypted with K3 and K5 can be decrypted with K1, K2, and K4:
C = MK3 * K5 mod n
M = CK1 * K2 * K4 mod n
One use for this is multisignatures. Imagine a situation where both Alice and Bob have to sign a document for it to be valid. Use three keys: K1, K2, and K3. The first two are issued one each to Alice and Bob, and the third is made public.
M′ = MK1 mod n
M = M′K2 * K3 mod n
M″ = M′K2 mod n
M = M″K3 mod n
Note that a trusted party is needed to set this system up and distribute the keys to Alice and Bob. Another scheme with the same problem is . Yet a third scheme is [695,830,700], but the effort in verification is proportional to the number of signers. Newer schemes [220,1200] based on zero-knowledge identification schemes solve both shortcomings of the previous systems.