Chapter Summary

All the material studied in earlier chapters culminates in this relatively short chapter which describes some popular cryptographic algorithms. We address most of the problems relevant in cryptography, namely, encryption, key agreement, digital signatures and entity authentication. Against each algorithm we mention the (provable or alleged) source of security of the algorithm.

Encryption algorithms are treated first. We start with the seemingly most popular RSA algorithm. This algorithm derives its security from the RSA key inversion problem and the RSA problem. The key inversion problem is probabilistic polynomial-time equivalent to the integer factorization problem. The intractability of the RSA problem is unknown. At present no algorithm other than factoring the RSA modulus is known for solving the RSA problem. We subsequently describe Rabin encryption (based on the square root problem), Goldwasser–Micali encryption (based on the quadratic residuosity problem), Blum–Goldwasser encryption (based on the square root problem), ElGamal encryption (based on the Diffie–Hellman problem) and Chor–Rivest encryption (based on a variant of the subset sum problem). The XTR encryption algorithm is essentially an efficient implementation of ElGamal encryption and is based on a tricky representation of elements in certain finite fields. The last encryption algorithm we discuss is the NTRU algorithm. It derives its security from a mixing system that uses the algebra . Attacks on NTRU based on the shortest vector problem are also known.

The basic key-agreement scheme is the Diffie–Hellman scheme. In order to prevent small-subgroup attacks on this scheme, one employs a technique known as cofactor expansion. We then explain unknown key-share attacks against key-agreement schemes. These attacks necessitate the use of authenticated key agreement schemes. The MQV algorithm is presented as an example of an authenticated key-agreement scheme.

Next come digital signature algorithms. Digital signatures may be classified in two broad categories: signature schemes with appendix and signature schemes with message recovery. In this book, we study only the signature schemes with appendix. As specific examples of signature schemes, we first explain RSA and Rabin signatures. Then, we present several variants of discrete-log-based signature schemes: ElGamal signatures, Schnorr signatures, Nyberg–Rueppel signatures, the digital signature algorithm (DSA) and its elliptic curve variant ECDSA. All the discrete-log (over finite fields)-based signature schemes have efficient XTR implementations. The NTRUSign algorithm is the last general-purpose signature scheme discussed in this section.

We then present a treatment of some special signature schemes. Blind signatures are created on messages unknown to the signer. Three blind signature schemes are described: Chaum, Schnorr and Okamoto–Schnorr schemes. An undeniable signature, on the other hand, requires an active participation of the signer at the time of verification and comes with a denial protocol that prevents a signer from denying a valid signature at a later time. The Chaum–Van Antwerpen undeniable signature scheme is based on the discrete-log problem, whereas the GKR scheme is based on the RSA problem.

A way to guarantee both authentication and confidentiality of a message is to sign the message and then encrypt the signed message. This involves two basic operations (signature generation and encryption). Zheng’s signcryption scheme combines these two primitives with a view to reducing both running time and message expansion.

The final topic we discuss in this chapter is entity authentication, a mechanism by means of which an entity can prove its identity to another. Here identity of an entity is considered synonymous with the possession of some secret information by the entity. Passwords are called weak authentication schemes, since the claimant has to disclose the secret straightaway to the verifier. A strong authentication scheme (also called a challenge–response scheme) does not reveal the secret to the verifier. We describe two strong authentication schemes; the first is based on encryption and the second on digital signatures. A way to establish mutual authentication between two entities is also presented. Challenge–response algorithms may be vulnerable to some attacks mounted by the verifier. A zero-knowledge protocol comes with a proof that during the authentication conversation no information is leaked to the verifier. Three zero-knowledge protocols are discussed: the Feige–Fiat–Shamir protocol, the Guillou–Quisquater protocol, and the Schnorr protocol.