O'Reilly logo

Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition by Bruce Schneier

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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, Ki, such that

images

Since

images

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:

images

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.

  1. (1) First Alice signs M and sends it to Bob.

    images

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

    images

  3. (3) He can also add his signature.

    images

  4. (4) Anyone can verify the signature with K3, the public key. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required