PKI applications (C2)

Basics and legal aspects

Pascal Steichen (MSSI-uni.lu) - 17/03/2007 (02)



Where it all started

For most of the history of cryptography, a key had to be kept absolutely secret and would be agreed upon beforehand using a secure, but non-cryptographic, method; for example, a face-to-face meeting or a trusted courier. There are a number of significant practical difficulties in this approach to distributing keys. Public-key cryptography was invented to address these drawbacks — with public-key cryptography, users can communicate securely over an insecure channel without having to agree upon a shared key beforehand.

In 1874, a book by William Stanley Jevons described the relationship of one-way functions to cryptography and went on to discuss specifically the factorization problem used to create the trapdoor function in the RSA system. In July 1996, one observer commented on the Jevons book in this way:

In his book The Principles of Science: A Treatise on Logic and Scientific Method, written and published in the 1890s , William S. Jevons observed that there are many situations where the 'direct' operation is relatively easy, but the 'inverse' operation is significantly more difficult. One example mentioned briefly is that enciphering (encryption) is easy while deciphering (decryption) is not. In the same section of Chapter 7: Introduction titled 'Induction an Inverse Operation', much more attention is devoted to the principle that multiplication of integers is easy, but finding the (prime) factors of the product is much harder. Thus, Jevons anticipated a key feature of the RSA Algorithm for public key cryptography, though he certainly did not invent the concept of public key cryptography.

The first invention of asymmetric key algorithms was by James H. Ellis, Clifford Cocks, and Malcolm Williamson at GCHQ in the UK in the early 1970s; these inventions were what later become known as Diffie-Hellman key exchange, and a special case of RSA. The GCHQ cryptographers referred to the technique as "non-secret encryption". These inventions were not publicly disclosed at the time, and the fact that they had been developed was kept secret until 1997.

An asymmetric-key cryptosystem was published in 1976 by Whitfield Diffie and Martin Hellman, who, influenced by Ralph Merkle's work on public-key distribution, disclosed a method of public-key agreement. This method of exponential-key exchange, which came to be known as Diffie-Hellman key exchange, was the first published practical method for establishing a shared secret-key over an unprotected communications channel without using a prior shared secret. Merkle's public-key-agreement technique became known as Merkle's Puzzles, and was published in 1978.

A generalisation of the Cocks method was reinvented in 1977 by Rivest, Shamir and Adleman, all then at MIT. The latter authors published their work in 1978, and the algorithm appropriately came to be known as RSA. RSA uses exponentiation modulo a product of two large primes to encrypt and decrypt, performing both public key encryption and public key digital signature, and its security is connected to the presumed difficulty of factoring large integers, a problem for which there is no known efficient (i.e., practicably fast) general technique.

Since the 1970s, a large number and variety of encryption, digital signature, key agreement, and other techniques have been developed in the field of public-key cryptography. The ElGamal cryptosystem (invented by Taher ElGamal then of Netscape) relies on the (similar, and related) difficulty of the discrete logarithm problem, as does the closely related DSA developed by the NSA and NIST. The introduction of elliptic curve cryptography by Neal Koblitz in the mid 1980s has yielded a new family of analogous public-key algorithms. Although mathematically more complex, elliptic curves appear to provide a more efficient way to leverage the discrete logarithm problem, particularly with respect to key size.

The problem with symmetric key crypto-systems:


© 1999 Department of Computer Science and Information Systems, The University of Hong Kong

1. PKI basics

Recap of the fundamentals and basic concepts:

Public key cryptography, also known as asymmetric cryptography, is a form of cryptography in which a user has a pair of cryptographic keys - a public key and a private key. The private key is kept secret, while the public key may be widely distributed. The keys are related mathematically, but the private key cannot be practically derived from the public key. A message encrypted with the public key can be decrypted only with the corresponding private key.

1.1. Data encryption using PKI

Public-key encryption uses a combination of a private key and a public key. The private key is known only to your computer, while the public key is given by your computer to any computer that wants to communicate securely with it. To decode an encrypted message, a computer must use the public key, provided by the originating computer, and its own private key.


© 1999 Department of Computer Science and Information Systems, The University of Hong Kong

1.1.1. Example: SSL/TLS

A popular implementation of public-key encryption is the Secure Sockets Layer (SSL). Originally developed by Netscape, SSL is an Internet security protocol used by Internet browsers and Web servers to transmit sensitive information. SSL has become part of an overall security protocol (from the IETF) known as Transport Layer Security (TLS).

Look for the "s" after "http" in the address whenever you are about to enter sensitive information, such as a credit-card number, into a form on a Web site. In your browser, you can tell when you are using a secure protocol, such as TLS, in a couple of different ways. You will notice that the "http" in the address line is replaced with "https," and you should see a small padlock in the status bar of the browser window. The padlock symbol lets you know that you are using encryption.

Public-key encryption takes a lot of computing, so most systems use a combination of public-key and symmetry. When two computers initiate a secure session, one computer creates a symmetric key and sends it to the other computer using public-key encryption. The two computers can then communicate using symmetric-key encryption. Once the session is finished, each computer discards the symmetric key used for that session. Any additional sessions require that a new symmetric key be created, and the process is repeated.

1.2. Digital signature using PKI (1)


© 1999 Department of Computer Science and Information Systems, The University of Hong Kong

Digital signature using PKI (2)


© 2006 Bart Van den Bosch

1.3. Key management in PKI (1)

We are going to study the data encryption example in more details. This illustrates the key management issues for Public Key Crypto-Systems. Suppose Thomas wants to send a secret message to Peter.


© 1999 Department of Computer Science and Information Systems, The University of Hong Kong

He needs to ask Miss C.A., the public-keys keeper, for Peter's public key. Miss C.A. will give out Peter's public key.


© 1999 Department of Computer Science and Information Systems, The University of Hong Kong

Key management in PKI (2)

Then Thomas encrypts the message with Peter's public key. Note that this encrypted message can ONLY be decrypted by Peter's private key. Thomas then sends the encrypted message via the Internet.


© 1999 Department of Computer Science and Information Systems, The University of Hong Kong

After Peter receives the encrypted message from the Internet, he uses his own private key to decrypt it. The same public key can be used by others to send secret messages to Peter.


© 1999 Department of Computer Science and Information Systems, The University of Hong Kong

Note that for the whole system to work, there are two important key management issues:

1.4. CA and certificates

A public key certificate (or identity certificate) is a certificate which uses a digital signature to bind together a public key with an identity — information such as the name of a person or an organization, their address, and so forth. The certificate can be used to verify that a public key belongs to an individual. In a typical public key infrastructure (PKI) scheme, the signature will be of a certificate authority (CA).


© 1999 Department of Computer Science and Information Systems, The University of Hong Kong

A certificate authority or certification authority (CA) is an entity which issues digital certificates for use by other parties. It is an example of a trusted third party. CAs are characteristic of many public key infrastructure (PKI) schemes.

1.4.1. Example certificate (1)

Example certificate

Example certificate (2)

2. Ten risks of PKI


© 2000 Computer Security Journal • Volume XVI, Number 1, Bruce Schneier

3. Trust models

or PKI vs PGP

Web of trust

3.1. PKI trust models/architectures

4. Legal aspects

4.1. Electronic signature directive (1999/93/EC) (1)

The electronic signature directive (1999/93/EC) establishes a harmonized electronic signature similar to the handwritten signature.

The key definitions from the directive are:

Electronic signature directive (1999/93/EC) (2)

Electronic signature directive (1999/93/EC) (3)

Electronic signature directive (1999/93/EC) (4)

Electronic signature directive (1999/93/EC) (5)

Electronic signature directive (1999/93/EC) (6)

Electronic signature directive (1999/93/EC) (7)

4.2. LU legal framework (1)

LU legal framework (2)

LU legal framework (3)

LU legal framework (4)

4.3. CSP supervision/accreditation legal framework (1)

CSP supervision/accreditation legal framework (2)

CSP supervision/accreditation legal framework (3)

CSP supervision/accreditation legal framework (4)

CSP supervision/accreditation legal framework (5)

4.4. CSP accreditation scheme

4.5. CSP supervision scheme

5. Bibliographic references