Cryptography

As mentioned above, a means for providing some of the important informa-tion integrity funcinforma-tions is cryptography. In general, there are two types of cryptography denotedsecret key cryptography andpublic key cryptography.

The crypto systems for performing secret key cryptography are also known as conventional crypto systems. Until 1976, when the concept of public key cryptography was introduced by Diffie and Hellman [DH76], all crypto sys-tems were secret key syssys-tems. The following brief description of both types of crypto systems gives the reader an introduction to the advantages, and the disadvantages, of the public key crypto systems. The description is based on

1.1. THE NEED FOR CRYPYOGRAPHY 5 [Nec92].

Secret Key Cryptography

A secret key system consists of two transformations: An encryption transfor-mationEK used for encryption of a messageM, and a decryption transforma-tion DK used for decryption of the encrypted message, i.e. DK(EK(M)) = M. The transformations are parameterised with a parameter K, denoted the key. By imposing certain requirements to the transformations, it is pos-sible to withstand some of the information integrity threats in Table 1.1.1.

Suppose two parties, say Alice and Bob, are communicating messages on a public communication channel. Furthermore, suppose that a third party, say Charlie, has access to the communication channel:

• To prevent Charlie from intercepting a message M send from Alice to Bob, Alice encrypts M using EK. Then, the resulting so-called cipher-text C = Ek(M) is sent to Bob. Finally, Bob decrypts C using DK. The key K, used as parameter in the encryption and the decryption, is kept secret from Charlie. Hence, by requiring that it is infeasible for Charlie to compute DK(C) without knowledge of the key value, Alice and Bob have achieved privacy in their communication.

• Furthermore, if it is infeasible for Charlie to compute EK(M) without knowledge of the key value, Charlie cannot pretend to be Alice in a communication where M is send to Bob.

The secret key crypto systems are mainly used for providing privacy in a communication between two parties. The Data Encryption Standard (DES) system is the most widely used secret key crypto system, see e.g. [SB92].

Public Key Cryptography

One of the reasons [Dif92] for proposing public key cryptography was the problem of key distribution: If two people, who have never met before, are to communicate privately using secret key cryptography, they must somehow agree in advance on a key that will be known to themselves and to no one else.

Another reason was the problems of signatures and of non-repudiation: A method was needed for providing the recipient of a purely digital electronic

message with a way of demonstrating to other people, that the message had come from a particular person. Hence, the signature should allow the recipient to hold the author to the contents of the message.

Public key systems differ from secret key systems in that there is no longer a single secret key shared by a pair of users. Rather, each user has each own key material. Furthermore, the key material of each user is di-vided into two portions, a private component and a public component. The public component generates a public transformationE, and the private com-ponent generates a private transformationD. Often,E andDis denoted the encryption transformation and the decryption transformation, respectively.

This is, however, an imprecise terminology: Depending on the actual sys-tem, it may be the case that D(E(M)) = M, E(D(M)) = M, or both. A common requirement to the public transformation E is that it must be a so-called trapdoor one-way function. “One-way” refers to the fact that E should be easy to compute from the public component of the key but hard to invert unless one possesses the corresponding private transformation D, or equivalently, the private component of the key. The private component thus yields a “trapdoor” which makes the problem of inverting E seem difficult from the point of view of all but the possessor ofD.

The following examples show how privacy, signatures, and non-repudiation may be provided by a public key crypto system. The transformations DA

and EA are those generated by Alice’s key, and the transformationsDB and EB are those generated by Bob’s key:

• To prevent Charlie from intercepting a message M send from Alice to Bob, Alice encrypts the message by means of Bob’s public avail-able transformation EB. Then, the ciphertext C = EB(M) is sent to Bob, who decrypts C by means of his own private transformation, M = DB(C)1. So, when the public key crypto system is used for obtaining privacy, only the transformations of the recipient are used.

The requirement to the transformations is that DB(EB(M)) = M. It should be emphasised, that Bob never needs to shareDB with Alice.

• To convince Bob that the messageM indeed originates from Alice and, hence, cannot have been generated by Charlie, Alice is able to sign the message: Alice transforms the message by means of her own private transformation. Then, the resulting signed messageS =DA(M) is sent to Bob. Finally, in order to verify the signature, Bob applies Alice’s

1.1. THE NEED FOR CRYPYOGRAPHY 7 public transformation to obtain M = EA(S). SinceDA is strictly pri-vate to Alice, Charlie could not possibly have generated the signed mes-sage. Note that only the transformations of Alice’s are used. In order to provide signatures, the transformations must obey EA(DA(M)) =M.

• The signed message, S =DA(M), could not even have been generated by Bob. Furthermore, the signature can be verified by every person who has access to Alice’s public transformation. Hence, Bob can prove to a third party that Alice indeed was the author of the signed message, and Alice cannot deny having signed the message.

To provide privacy, the transformations used in a public key systems must obey the conditionD(E(M)) =M, and to provide signatures they must obey E(D(M)) = M. According to [Nec92] there is only one major system, the Rivest-Shamir-Adleman (RSA) system, that satisfies both conditions. This system will be introduced below.

Compared to the secret key systems, the public key systems provide a wider range of information integrity functions. Furthermore, the key dis-tribution problem is significantly reduced: There is no longer a need for exchanging secret keys. Apart from the private transformation of a user, only the public available transformations of the other users are required in order to apply public key cryptography.

There are, however, a disadvantage of the public key systems: Compared to the secret key systems, they are based on very slow transformations, i.e.

the obtainable bandwidths associated with public key cryptography are lim-ited. A state-of-the-art dedicated hardware implementations of the DES secret key system is able to perform the transformations at a rate of up to 90 Mbit/set [Pij91]. This is close to 1000 times faster than the fastest known implementations of the RSA public key system. Indeed,the bandwidth prob-lem represents the most serious limitation on the practical applicability of public key systems.