Applied Cryptography: Protocols, Algorithms and Source Code in C, 20th Anniversary Edition

CHAPTER 23

Special Algorithms for Protocols

23.1 MULTIPLE-KEY PUBLIC-KEY CRYPTOGRAPHY

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₁ * K₂ * . . . * K_t ≡ 1 mod ((p − 1)(q − 1))

Since

M^{K₁ * K₂ * . . . * K_t} = 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₃ and K₅ can be decrypted with K₁, K₂, and K₄:

C = M^{K₃ * K₅} mod n

M = C^{K₁ * K₂ * K₄} 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₁, K₂, and K₃. 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^K₁ mod n

• (2) Bob can recover M from M′.

  M = M′^{K₂ * K₃} mod n

• (3) He can also add his signature.

  M″ = M′^K₂ mod n

• (4) Anyone can verify the signature with K₃, the public key.

  M = M″^K₃ 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.

23.2 SECRET-SHARING ALGORITHMS ...