Smart Card Technical Issues Starter Kit
Chapter 5

Roger Clarke

Principal, Xamax Consultancy Pty Ltd, Canberra

Visiting Fellow, Department of Computer Science, Australian National University

Version of 8 April 1998

© Xamax Consultancy Pty Ltd, 1998

This document was prepared for Centrelink. Its purpose was to support the consultation process between Centrelink and privacy advocates, during a project that was intended to lay the foundations for a variety of projects for Centrelink's client agencies that it was anticipated would involve smart cards

This is chapter 5 of an 8-part document whose contents-page is at http://www.anu.edu.au/people/Roger.Clarke/DV/SCTISK.html

5. Public Key Cryptography

One of the most critical means whereby security is achieved in smart card based schemes is through the application of public key cryptography. This section provides a staged introduction to the technology.

This section comprises revised excerpts from:

Clarke R. (1996) 'Data Transmission Security (or 'Cryptography in Plain Text')' Privacy Law & Policy Reporter 3, 2 (May 1996), pp. 24-27

5.1 Cryptography Generally

Cryptography is an important element of any strategy to address data transmission security requirements. It is the practical art of converting messages or data into a different form, such that no-one can read them without having access to the 'key'. The message may be converted using a 'code' (in which case each character or group of characters is substituted by an alternative one), or a 'cypher' or 'cipher' (in which case the message as a whole is converted, rather than individual characters).

Cryptology is the science underlying cryptography. Cryptanalysis is the science of 'breaking' or 'cracking' encryption schemes, i.e. discovering the decryption key.

A 'strong encryption scheme' is one that cannot be cracked in a sufficiently short time that the security of the message is threatened, even using the most powerful computers available for the task.

With a 'weak encryption scheme', on the other hand, there is a significant risk that the key can be discovered by an organisation which has access to sufficient computing power. Discussions in this area generally relate to the computing power owned by the U.S. National Security Agency (NSA).

There are several aspects of a scheme that determine its strength. One of particular importance is the key-length needed to make it highly unlikely that a cracking attempt will be successful.

Cryptography comprises two distinct classes: symmetric and asymmetric.

5.2 Symmetric Cryptography

Symmetric cryptography involves a single, secret key, which both the message-sender and the message-recipient must have. It is used by the sender to encrypt the message, and by the recipient to decrypt it.

The NSA stated recently that a 40-bit length was acceptable to them (i.e. they can crack it sufficiently quickly). Increasing processor speeds, combined with loosely-coupled multi-processor configurations, are bringing the ability to crack such short keys within reach of much less well-funded organisations. To be 'strong', the key-length therefore needs to be at least 56 bits, and it was argued by an expert group in 1996 that 90 bits is a more appropriate length.

Symmetric cryptography provides a means of satisfying the requirement of message transmission security, because the content cannot be read without the secret key. There is a risk exposure, however, because neither party can be sure that the other party has not exposed the secret key to a third party (whether accidentally or intentionally).

Symmetric cryptography can also be used to address the integrity and authentication requirements. The sender creates a summary of the message, or 'message authentication code' (MAC), encrypts it with the secret key, and sends that with the message. The recipient then re-creates the MAC, decrypts the MAC that was sent, and compares the two. If they are identical, then the message that was received must have been identical with that which was sent.

The technique does not adequately address the non-repudiation requirement, however, because both parties have the same secret key, and hence each is exposed to fraudulent falsification of a message by the other.

A major difficulty with symmetric schemes is that the secret key has to be possessed by both parties, and hence has to be transmitted from whomever creates it to the other party. But if the key is compromised, all of the data transmission security measures are undermined. The steps taken to provide a secure mechanism for creating and passing on the secret key are referred to as 'key management'.

5.3 Asymmetric ('Public Key') Cryptography

Whereas symmetric cryptography has existed, at least in primitive forms, for 2,000 years, asymmetric approaches were only invented in the mid-1970s.

Asymmetric cryptography involves two related keys, referred to as a 'key-pair', one of which only the owner knows (the 'private key') and the other which anyone can know (the 'public key').

The advantages of asymmetric cryptography are that:

To crack a mere 40- or 56-bit asymmetric key would be trivially simple, because there are far fewer sets of keys (or, expressed more technically, the 'key-space' is relatively 'sparse'). It is currently conventional to regard a 1024-bit asymmetric key-length as being necessary to provide security.

5.4 Applied Public Key Cryptography

Public key cryptography can be applied as a means of addressing each of the requirements for data transmission security identified in the previous section.

* Public Key Cryptography and Message Transmission Security

The sender encrypts the message, not with their own key, but using the intended recipient's public key. The receiver decrypts using their private key.

This is a more secure approach than symmetric cryptography, because the decryption key need never be in the possession of anyone other than the owner. It is much slower, however, and hence symmetric cryptography is more commonly used for protecting the contents of the message from prying 'eyes'.

* Public Key Cryptography and Integrity, Authentication and Non-Repudiation

The technique can be used to address all of the integrity, authentication and non-repudiation requirements. Because the technique is somewhat complex, it is explained below in a succession of steps.

Note that this process uses a different key-pair from that used for message transmission security. The key-pair used for message-security is owned by the recipient, whereas the key-pair used in this process is owned by the sender.

The sender appends to a message a special, agreed segment within the message. He encrypts this segment with his private key. The recipient decrypts this segment using the sender's public key. If the decrypted segment is identical to what the two parties had previously agreed, then the recipient can be sure that the message has been sent by the purported sender, and that the sender cannot credibly deny having sent it. Hence the authentication and non-repudiation requirements are satisfied.

This technique can be taken a step further, to address the integrity requirement as well. The additional segment is not pre-agreed. Instead, a 'message digest' is created, by processing the actual message using a special, pre-agreed algorithm (in a similar way to the MAC'ing process used in symmetric cryptography). The sender encrypts this message digest with his private key, to produce what is called a 'digital signature' (because it performs much the same function as a written signature, although it is much harder to forge).

The recipient re-creates the message digest from the message that they receive, uses the sender's public key to decrypt the digital signature that they received appended to the message itself, and compares the two results. If they are identical, then:

* Would You Like That Run Past You Again?

Rest assured that most people do not grasp those ideas the first time that they read them.

Here is a second description of the process whereby all data transmission security risks can be addressed through the application of public key cryptography.

It involves:

The process is as follows:

Sender Actions Before Sending:
Message-in-Clear-Text * Hash-Function => Hash-Value
Hash-Value * Sender's-DigSig-Private-Key => Signature
Message-in-Clear-Text || Signature => Signed-Text
Signed-Text * Receiver's-Encryption-Public-Key => Encrypted-Signed-Text
Receiver Actions After Receiving:
Encrypted-Signed-Text / Receiver's-Encryption-Private-Key
	=> Message-in-Clear-Text || Signature
Message-in-Clear-Text * Hash-Function => Hash-Value
Signature / Sender's-DigSig-Public-Key => Hash-Value
Receiver Actions in Order to Test the Security of the Data Transmission:
IFF   	The Two Hash-Values Match
	THEN	Message Transmission Security is assured
	AND	Message Integrity is assured
	AND	Message Authentication is assured
	AND	Message Non-Repudiability is assured
	Something's Rotten in the State of Denmark

5.5 Public Key Cryptography and the Management of Secret Keys

Another way in which asymmetric cryptography can be used, is to underwrite the security of a symmetric encryption scheme.

This can be done by using it to support the secure transmission of a new secret key from the originator to the other party. Under this approach, the new secret key is encrypted using the recipient's public key, and then sent. Only the recipient has the recipient's private key, and hence only the recipient can decrypt the message and recover the new secret key. This technique is commonly used.

5.6 Additional Issues in Public Key Cryptography

Public key cryptography is relatively new, technically complex, and raises many public policy issues.

* The Generation of Pairs of Private and Public Keys

Because of the nature of the mathematics underlying asymmetric cryptography, the pairs of keys are created as part of the same process. Three main choices exist as to who performs key-generation:

This choice of who generates key-pairs is one of the issues at the heart of the cryptography debates of the last few years (Clarke 1996).

* Secure Deposit of Private Keys

If a person or organisation loses their private keys, they are unable to:

In order to address this risk, it is strongly advisable that every private key be placed into deposit in some location separate from that person's normal workstation. Because of the risks involved if the private key comes to be known by some other person, the deposit needs to be subject to an appropriately high set of security standards.

* Escrow of Private Keys

'Escrow' is an arrangement whereby something is placed on deposit with a trusted party, but may be accessed by third parties under certain conditions. It was originally used for title deeds for real property, and is used for source-code for software packages.

Escrow can also be used for private keys, in which case it is referred to as 'private key escrow', which is commonly shortened to 'key escrow'.

There are a number of conditions under which individuals or organisations may have a legitimate interest in gaining access to the private keys of other parties. These include:

If, however, security is to be sustained (and, indeed, if privacy is to be protected), any access to escrowed keys would need to be subject to very careful designed and implemented controls, e.g. a prior requirement of legal authority (such as a search warrant), granted by a senior member of the judiciary.

If key escrow is implemented, it might be:

and the function might be performed by:

These choices, and indeed the very question as to whether private key escrow should be implemented, lie at the heart of the cryptography debates of the last few years (Clarke 1996). It is important that the distinction be appreciated between secure deposit (for the benefit of the key-owner) be distinguished from escrow (for the benefit of a third party). This has become confused during the public debates.

* Access to, and Certification of, Public Keys

Asymmetric schemes depend on the public keys of people and organisations being publicly available. The most practicable methods of achieving this are:

Either of these approaches is subject to 'spoofing', i.e. an imposter can send a message which includes a public key, or store a public key in a directory, and thereby fool the other party into thinking the message came from a particular person or organisation.

To address this risk, the concepts have been created of:

If a party to a message-exchange wishes to acquire the public key of the other party, or to check that the public key they already have for the other party is valid and up-to-date, they use that party's identity to look up a certificate in a directory, and receive back a message containing that person's or organisation's public key. The message is signed and encrypted by the certification authority using its own private key, and the recipient decrypts it using the certification authority's public key.

In order to reduce the amount of network traffic involved, and hence the elapsed time of a transaction, it is feasible for certificates to be provided by the sender (in a manner analogous to a letter applying for a job being accompanied by a set of letters from referees attesting to the applicant's identity and good character).

An international standard for certificates of this kind has existed for several years, documented within the CCITT standard X.509. Services of this nature are being offered in the United States. In Australia, Telstra operates such a scheme for its own use and that of one or two major clients, and Australia Post has launched a scheme called KeyPost, which it intends to make generally available.

* Multi-Function Certification Authorities

The preceding paragraphs have endeavoured to present the complete set of concepts in a logical sequence of development. Unfortunately, the separation of ideas and functions has been considerably muddied in practice.

In particular, many of the proposals for public-key certification / authentication frameworks and certification authorities, including the Australian Standards document MP75 (PKAF 1996), envisage the authorities performing multiple functions, including:

Whether an organisation that performs the third and fourth functions should also perform the first and/or second functions is central to the current arguments between crypto-anarchists and crypto-authoritarians.

Introductory Materials

Clarke R. (1996) 'Data Transmission Security (or 'Cryptography in Plain Text')' Privacy Law & Policy Reporter 3, 2 (May 1996), pp. 24-27

Security Domain (1997) 'About public key cryptography'

Utah (1996) 'Digital Signature Tutorial'

Whittle R. (1996-) 'Public Key Authentication Framework: Tutorial'

Ylönen T. (1996-) 'Introduction to Cryptography'


Clarke R. (1996) 'Crypto-Confusion: Mutual Non-Comprehension Threatens Exploitation of the GII' Privacy Law & Policy Reporter 3, 2 (May 1996), pp. 24-27, 30-33

EPIC 'Cryptography Policy'

Garfinkel S. (1995) 'PGP: Pretty Good Privacy' O'Reilly & Associates, 1995, esp. Chapters 2-6 and the Glossary

Litterio F. (1995) 'Cryptography: The Study of Encryption'

Netscape (1996) 'Netscape Policy on Encryption Export'

OGIT (1998) 'Project Gatekeeper: Implementation of Public Key Technology by Commonwealth Agencies' Office of Government Information Technology, March 1998

OTA (1995) 'Issue Update on Information Security and Privacy in Network Environments', Chapter 2: Overview Of The 1994 OTA Report On Information Security And Privacy, June 1995, at: f ftp://otabbs.ota.gov/pub/infosec.update/07ch2.txt and ftp://otabbs.ota.gov/pub/pdf/infosec.update

and mirrored at:

http://www.anu.edu.au/people/Roger.Clarke/II/07ch2.txt and http://www.anu.edu.au/people/Roger.Clarke/II/03ch2.pdf

PKAF (1996) 'Strategies for the Implementation of a Public Key Authentication Framework (PKAF) in Australia' Standards Australia, MP75, 1996

RSA (1995) 'RSA's Frequently Asked Questions About Today's Cryptography'

Schneier B. (1996) 'Applied Cryptography' Wiley, 2nd Ed., 1996

SET (1996) 'Secure Electronic Transactions Specification', February 1996, at MasterCard and Visa

Wayner P. (1996) 'Don't Lose Your Crypto Keys' BYTE (May 1996) p.137

Whittle R. (1996-) 'Public Key Authentication Framework for Australia'

Ylönen T. (1996-) 'International Cryptography'


Go to Roger's Home Page.

Go to the contents-page for this segment.

Send an email to Roger

Created: 14 July 1998

Last Amended: 14 July 1998

These community service pages are a joint offering of the Australian National University (which provides the infrastructure), and Roger Clarke (who provides the content).
The Australian National University
Visiting Fellow, Faculty of
Engineering and Information Technology,
Information Sciences Building Room 211
Xamax Consultancy Pty Ltd, ACN: 002 360 456
78 Sidaway St
Chapman ACT 2611 AUSTRALIA
Tel: +61 2 6288 1472, 6288 6916