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, *K _{i}*, such that

*K*_{1} * *K*_{2} * . . . * *K _{t}* ≡ 1 mod ((

Since

*M*^{K1 * 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 *K*_{3} and *K*_{5} can be decrypted with *K*_{1}, *K*_{2}, and *K*_{4}:

*C* = *M*^{K3 * K5} mod *n*

*M* = *C*^{K1 * 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: *K*_{1}, *K*_{2}, and *K*_{3}. The first two are issued one each to Alice and Bob, and the third is made public.

- (1) First Alice signs
*M*and sends it to Bob.*M*′ =*M*^{K1}mod*n* - (2) Bob can recover
*M*from*M*′.*M*=*M*′^{K2 * K3}mod*n* - (3) He can also add his signature.
*M″*=*M*′^{K2}mod*n* - (4) Anyone can verify the signature with
*K*_{3}, the public key.*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 [484]. 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.

Start Free Trial

No credit card required