Public Key Cryptography Explained
by John Ridley

Most readers of SECURITY INTERNATIONAL will by now have heard about the growing importance of public key cryptography [PKC] and its relevance for government, commercial enterprises and the private citizen. Whilst details of the underlying mathematics are well beyond the grasp of most of us, the important thing is to understand the basics of how the technology can be applied, and what it means to the end user community. This article is intended to give a brief overview of PKC, and a new branch of PKC, which might find useful applications within the public sector.

THE RELEVANCE AND CONTEXT OF PKC

PKC is the enabling technology for all Internet security, and has an important role to play in e-commerce. Another facet of PKC is the increasing use of digital signatures, which are replacing traditional signatures in many contexts. The application of this technology will therefore impact on virtually all areas of society.

A BRIEF HISTORY OF PKC

In 1973, inspired by the pioneering work of James Ellis, Cliff Cocks of CESG invented the first practical method for what we now call public key cryptography (PKC), but the CESG breakthrough was not made public until 1997. The technology was subsequently rediscovered independently and developed into RSA. For those intrigued by abbreviations, it is derived from the names of its inventors, namely Rivest, Shamir and Adleman. RSA is a widely recognised standard familiar to all IT security professionals and is incorporated into many commercial products world-wide.

There has been a considerable amount of work in recent years on translating the concept of PKC into a practical architecture, namely a public key infrastructure [PKI] suitable for government use. This has involved CESG working closely with Government Departments as well as the IT industry, to explore how the architecture might be managed, and to help ensure that commercial PKC products meet agreed standards and are interoperable with each other.

It has to be said that there have been difficulties on the way to achieving this goal. Traditional PKC systems are not being implemented as widely or as quickly as initially anticipated. Some of the problems cited are the high cost of the infrastructure needed to manage and authenticate public keys, and the difficulties inherent in managing multiple communities of interest. This is where ID-PKC may prove to be a useful alternative application – whilst ID-PKC will not replace conventional PKIs, it offers an easier solution to some of these problems.

Shamir proposed the concept of identity-based public key cryptography (ID-PKC) in 1984. In ID-PKC all users’ public keys are predetermined by information that uniquely identifies them. For various reasons this would potentially make implementation of the technology much easier, as well as delivering some added Infosec benefits which are described below, such as the potential for cryptographic separation of different communities using the system. ID-PKC remained a purely theoretical concept until 1998 when Cliff Cocks proposed the first practical solution. CESG has now released information regarding his method into the public domain, and developed demonstrators proving that it offers a practical way ahead.

HOW DOES ID-PKC WORK?

To show the possible advantages of ID-PKC, it is worth explaining how the concept differs from traditional PKC. In a traditional PKC system, a user (call him Bob) creates a private key, and derives a public key from it. A central authority then certifies this public key and publishes it. If another user (Alice) wishes to communicate with Bob, she consults the PKI directory to find his public key, which is returned in a certificate.

Alice checks the certificate, and sends a message encrypted under Bob’s public key. In an ID-PKC system, by contrast, Alice has no need to consult any central authority, but simply derives Bob’s public key from his identity and uses it to encrypt a message. Bob then consults the central authority to obtain his private key, which is derived using some secret system information, and uses it to decrypt this and any future messages.

Because a public key can be derived without its owner first having to register with a central authority, Alice can send Bob an encrypted message without waiting for him to register and communicate his public key in advance. The onus is then on Bob to obtain his own private key in order to read this message, providing a positive motivation for him to begin using the system. ID-PKC has the potential for organic rather than stepped growth. There is no need for large up-front investment in infrastructure to get such a system off the ground. There is no need either for additional infrastructure to control how secret keys are generated in order to assure the security of this process.

Also it should be noted that the responsibility for determining whether a user is entitled to encrypt and read a received message resides not with the sender, as in traditional PKC systems, but with the authority, which makes the decision to release the private key or not. This is a quite fundamental paradigm shift. In a traditional system, sending a message implies that the recipient can read it, which has the potential for unwanted consequences. For example, if a confidential message is sent in error to the wrong ‘John Smith’ in an address book we can, by implication, read the message; this is not so in an ID-PKC system.

In the CESG system, cryptographic separation of communities is achieved by using different modulus. It is interesting to note that two American academics very recently discovered another ID-PKC method based on elliptical curves.

FOR THE MATHEMATICIANS

If the concepts of Quadratic Residuosity, public modulus, hashing, square roots and prime numbers are of interest to any reader, further information regarding the mathematics may be obtained from CESG. However, the technical details are probably of less significance to readers than the fact that such a method exists, and the potential benefits it offers.

THE PRACTICAL IMPLICATIONS

The problem of multiple communities of interest can also be addressed more easily in an ID-PKC system. In other words, a group of users who wish to share information between themselves only can do so. No private key relating to one community will decrypt messages encrypted with a public key relating to a different community. The designated authority can control this access.

On the face of it, a system authority seems an obvious single point of system trust (or compromise). An authority (or another party, if an authority’s secret were to be compromised) could masquerade as any given user of the system. However, CESG has developed a solution to this problem. It is possible to split the authority into two or more co-operating parties sharing the system secrets in a secure manner. Thereafter users will need to prove their identity to each authority, and each will return a part of the private key, which the user will be able to combine when the key is required for use. This procedure make it impossible for a single authority to generate a key alone, and if a system secret is split between an arbitrary number of authorities, then no smaller subset of them will be able to generate a key – all of them will have to co-operate. Also different communities of interest can have different authorities or combinations of authorities, possibly requiring different standards of proof of identity from users. Hence there is no single point of security failure.

Both traditional PKC and ID-PKC can be used for purposes of identification and authentication. systems. In the interactive case, for example accessing a web site, mutual strong authentication of the communicating parties is achieved trivially by a single protocol involving no third parties. However, in the non-interactive case [such as email], while ID-PKC implicitly authenticates the recipient, it says nothing about the sender. A signature scheme is required. Suggestions for ID-based signature schemes already exist, and CESG has developed a new scheme specifically for use with this ID-PKC method. In this scheme the identity signature is used as a ‘certificate’, which validates a traditional, possibly ephemeral, DSA (Digital Signature Algorithm ) signature for a message. This has the benefit of enabling compliance with the European Electronic Signatures Directive.

THE CURRENT STATE OF PLANNING

Work is still ongoing to define protocols and standards for implementation of ID-PKC. But it is already apparent that this technical breakthrough will present some real business opportunities and benefits for customers, not as a replacement for traditional PKI systems but as a complement to them, particularly in the e-Government arena. CESG is now approaching industry and potential Government customers to explain the opportunities presented by this technology and, according to market demand, to assist in the development of commercial ID-PKC products.

A series of briefing days have been planned for those interested in the potential application of ID-PKC which complement the concurrent discussions on ‘traditional’ PKC architectures, and sample ID-PKC code is also being distributed to interested parties within the UK.