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

K1 * K2 * . . . * Kt ≡ 1 mod ((p − 1)(q − 1))

Since

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.

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

    M′ = MK1 mod n

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

    M = MK2 * K3 mod n

  • (3) He can also add his signature.

    M″ = MK2 mod n

  • (4) Anyone can verify the signature with K3, 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.

23.2 SECRET-SHARING ALGORITHMS ...

Get Applied Cryptography: Protocols, Algorithms and Source Code in C, 20th Anniversary Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.