Published: March 1997
The Elliptic Curve Cryptosystem (ECC) provides the highest strength-per-bit of any cryptosystem known today. This paper is the first in a series of ECC whitepapers aimed at providing an overview of information security and public-key cryptosystems for readers with little background in data security.
Contents
1. Information Security and Cryptographic Systems
"Information Security" is rapidly becoming a "buzz-word" of the 1990s. Governments, commercial businesses, and individuals are all storing information in electronic form. This medium allows a number of advantages over previous physical storage: storage is more compact, transfer is almost instantaneous, and accessing via databases is facilitated. The ability to use information more efficiently has resulted in a rapid increase in the value of information. Businesses in a number of commercial arenas today recognize information as their most valuable asset.
However, with the electronic revolution, information faces new and potentially
more damaging security threats. Unlike information printed on paper, information
in electronic form can potentially be stolen from a remote location. It
is much easier to intercept and alter electronic communication than its
paper-based predecessors.
1.1 What is Information Security?
Simply put, information security describes all measures taken to prevent unauthorized use of electronic data - whether this unauthorized use takes the form of disclosure, alteration, substitution, or destruction of the data concerned.
Only today are the full requirements of securely maintaining electronic information being understood. Information Security is classified as the provision of the following three services:
Cryptographic systems are controlled by the use of a key to determine the transformation performed. The key itself also takes the form of an electronic string. Of course, transforming data using a cryptographic system is not the only concern of information security. The owner of the cryptographic key must continue to ensure the security of the information by guarding the key itself. Security of the key, assignment of liability and responsibility for the key, and audit of access to the key are all ongoing issues that must be addressed.
That said, there is no doubt that a cryptographic system, correctly
managed and implemented, offers the highest security level for electronic
information available today.
1.2 What Services do Cryptographic Systems Provide?
Cryptographic systems (or cryptosystems) potentially provide all three objectives of information security: confidentiality, integrity, and availability. In order to clarify and demonstrate how cryptosystems are employed, confidentiality and integrity are further sub-classified into five services that can be thought of as the building blocks of a secure system:
While this whitepaper focuses on the security services of confidentiality and integrity, availability is an issue which remains crucial when implementing security. This is particularly true in the commercial arena. For example, an extremely secure electronic payment system is virtually useless if it is not able to operate fast enough to handle consumers' needs, or if it restricts the volume of trade so that merchants are forced to turn customers away. Thus when addressing the issues of information security, a business does not only face the question: "what security services do I need a cryptosystem to provide?", but also "which cryptosystem will best ensure that I can continue to use my information as efficiently as possible?".
So, while this whitepaper focuses on the services of confidentiality and integrity, bear in mind that availability will be crucial in many applications. When employing a cryptosystem, this availability translates into the speed of operation of the cryptosystem, its reliability, and its ease of use.
2. Types of Cryptographic Systems
Historically cryptographic systems have provided only confidentiality. Preparing a message for a secure, private transfer involves the process of encryption. Encryption transforms data in user or machine readable form, called the plaintext, to an illegible version, called the ciphertext. The conversion of plaintext to ciphertext is controlled by an electronic key k. The key is simply a binary string which determines the effect of the encryption function. The reverse process of transforming the ciphertext back into plaintext is called decryption, and is controlled by a related key l.
There are two broad classes of cryptosystems, known as symmetric-key cryptosystems and public-key cryptosystems. The relationship between k and l differentiates the two.
In a symmetric-key cryptosystem, the same key is used for both encryption and decryption. Figure 1 illustrates the mechanical analogy of a symmetric-key cryptosystem. Since the keys are the same, two users wishing to communicate in confidence must agree and maintain a common secret key. Each entity must trust the other not to divulge the key. In applications where a limited number of users exist, symmetric-key cryptography is effective. However, in large networks with users distributed over a wide area, key distribution becomes a problem. Each individual in a network should have a distinct key to communicate with each other person. To set this up, a tremendous number of keys must be established and stored securely. For example, a system with 1000 users would require approximately 500,000 keys to be exchanged and maintained securely. Exchanging and managing such a large number of keys is at best an arduous task and at worst impossible.
Symmetric-key cryptosystems have been used to provide confidentiality for thousands of years. One of the first recorded systems was used by Julius Caesar. Known as the Caesar Cipher, it involves shifting the letters of the alphabet a predetermined number of characters. The number of character shifts is the encryption key, and, of course, shifting back the same number of characters reverses this process to decrypt. Today, symmetric-key cryptosystems are controlled by keys that are based on complex mathematical algorithms.
On the other hand, public-key cryptosystems are a contemporary technology, introduced as recently as 1976 by two Stanford researchers, Whitfield Diffie and Martin Hellman. In a public-key cryptosystem, the abilities to perform encryption and decryption are separated. The encryption rule employs a public key E (that is k = E), while the decryption rule requires a different (but mathematically related) private key D (that is l = D). Knowledge of the public key allows encryption of plaintext but does not allow decryption of the ciphertext. If a person selects and publishes their public key, then everyone can use that one public key to encrypt messages for that person. The private key is kept secret so that only the intended individual can decrypt the ciphertext. In a network of 1000 users, there is only a need for one public key and one private key for each user. This requires a total of 2000 keys instead of the 500,000 keys required for a symmetric-key cryptosystem. Figure 2 shows the mechanical analogy of a public-key cryptosystem.
There are many examples of commonly used symmetric-key and public-key systems including:
| Public-Key Cryptosystems | Symmetric-Key Cryptosystems |
|
|
3. Security Services using Public-Key Cryptosystems
Public-key cryptosystems are capable of fulfilling all of the main objectives
of information security. This section outlines how each of these services
can be provided by the correct implementation of a public-key cryptosystem.
For illustrative purposes, each service is discussed in the context of
a hypothetical communication between two users, Alice and Bob. Bob's private
key will be denoted by Dbob and his public key by Ebob.
The adversary, trying to subvert secure communication, is Eve.
| 3.1 Public-Key Encryption | Confidentiality |
to show that C is the result of transforming M using Ebob. Finally Alice sends C to Bob. Bob retrieves M by transforming C using Dbob.
Alice and Bob are now assured that no-one else can decipher C, since only Bob knows his private key Dbob. Therefore Bob alone can compute:
and recover M from C. Thus the service of confidentiality is provided by performing public-key encryption in this way. Figure 3 illustrates the procedure Alice and Bob undergo during public-key encryption.
Notice, however, that anyone could have encrypted any message and sent it to Bob. While the message is confidential, there is no assurance that the message came from Alice. A method for achieving the extra service of data origin authentication is described in the next section.
| 3.2 Digital Signatures | Data Origin Authentication
Data Integrity Non-repudiation |
To avoid compromise in this way, digital signatures are performed in a more complex manner using a public-key cryptosystem. The essential difference between the use of a public-key cryptosystem for signing and its use for encrypting is that the order in which the keys are used is reversed. In data encryption, first Alice applied Ebob to M, then Bob decrypted using Dbob. In digital signatures, first Bob applies Dbob to compute his signature, then Alice checks, or verifies, the signature using Ebob.
Figure 4 illustrates this "reversal" of the application of the private key and public key. The details of forming a digital signature are more complex, but keep in mind that it is this change that fundamentally determines the whole process.
Suppose now that Bob wishes to sign a message M. Bob first transforms M using a hash function. The output of the hash function is a value which is specific to the content of the message itself. This output, which is denoted h(M), is called a message digest and can be thought of as a "fingerprint" of the message.
Bob signs M by transforming h(M) using Dbob, to obtain:
Here S rather than C denotes the output of the transformation in order to distinguish that S forms part of the signature process as opposed to the encryption process. Bob now sends M and S to Alice as his signature on M.
If Alice wants to verify Bob's signature on M, she first retrieves Ebob. Then she recomputes the message digest, h(M), from M using the publicly available hash function. Finally Alice transforms S using Ebob and compares the result with h(M). If Alice finds that:
then she accepts Bob's signature as valid. On the other hand, if:
h(M)Alice concludes that S is not Bob's signature for message and that M has been modified. Figure 5 shows Alice and Bob carrying out this process.
Why does this signature process provide the services of data origin authentication, data integrity, and non-repudiation? First of all, Alice is assured that only Bob could have computed the signature, since only Bob knows Dbob, and therefore only Bob could have transformed h(M) to S. Thus data origin authentication is provided. Secondly, once Bob has signed M, the message cannot be altered, since changing M would change h(M), so that S would no longer represent a valid signature on the new message. Thus data integrity is upheld. Finally, non-repudiation is provided because once Bob has signed a message, he cannot later deny signing it. All Alice has to do to be assured of non-repudiation is save Bob's signature on M so that if Bob later denies signing M, the pair of M and S will demonstrate that he is lying.
| 3.3 Signed Challenges | User Authentication |
What is the difficulty with providing user authentication? Consider the following scenario. Alice wants user authentication to assure her that she is involved in a real-time communication with Bob. Suppose Bob attempted to provide this assurance by simply signing the message "this is Bob". Certainly Alice is assured that the message originated from Bob at some stage, because, as seen in the last subsection, digital signatures provide data origin authentication. The problem comes with the phrase "real-time". Once Bob has signed "this is Bob", Eve can save this signature and use it to authenticate herself as Bob at any later time.
So a simple digital signature alone does not provide Alice with user authentication. To attain this service, the interaction between Alice and Bob is modified as follows. When Alice enters a real-time communication with Bob and desires user authentication, she first generates an unpredictable random number, Ralice, and sends it to Bob. Ralice is called a challenge in this context. Now, instead of signing just "this is Bob", Bob signs "this is Bob, and you just sent me Ralice". Provided this signature is valid, and the signed value Ralice is the same as the challenge Alice generated, then Alice is assured that she is communicating with Bob in "real-time". Thus the combination of a digital signature together with the unpredictability of Alice's random challenge provides user authentication.
This is a simple example of a cryptographic protocol. A protocol
is a sequence of messages and responses passed between Alice and Bob that
provide one or both parties with some service. Cryptographic protocols
are widely used by computer networks. For example, a more complex protocol
would be required to provide both Alice and Bob with user authentication
- a service known as mutual user authentication.
3.4 Certification Authorities
By this stage it has been shown how public-key cryptosystems can be used to provide the five "building blocks" for system security. In Section 1, we briefly discussed issues of key management for cryptosystems - the need to store keys securely, audit access to keys, and so on. Therefore implementing a secure system is more complex than simply programming routines to implement a public-key cryptosystem and choosing a key. Many other procedures must be in place, for example the assignment of liabilities and responsibilities for the maintenance of the keys. This is particularly true in applications in which digital signatures are recognized to have the same legal status as handwritten signatures.
As an example of some of the subtleties involved, consider the following scenario. During the procedures for encryption and signing, Bob began by placing his public key in some kind of "electronic phone book" so that the other users could later retrieve it. In fact, the set-up of this "phone book" is crucial to security. Suppose that Eve is also able to place a public key of her choice into this public directory, claiming that the key belongs to Bob. When Alice now encrypts confidential information and sends it to Bob, Eve intercepts the ciphertext and decrypts the information herself. So confidentiality is not upheld. This demonstrates that all users need to have confidence that the public keys they retrieve are authentic and belong to the specified user.
This requirement amounts to the need for some information binding Bob to his public key. This binding is usually provided by a certificate. Certificates are issued by a Certification Authority (CA). A Certification Authority is a third party trusted by all users.
A CA creates, distributes, revokes, and generally manages certificates. To generate Bob's certificate, the CA checks Bob's identity and that Ebob really is Bob's public key. The CA then signs with its own private key, DCA, a message comprised of Bob's identification (information such as name, address, and email address), Bob's public key and any other useful information, such as expiration date of the certificate and user privileges.
Now, when Alice wants to obtain Bob's public key, she retrieves Bob's certificate from a public directory, and verifies the CA's signature on the certificate itself. Provided this signature verifies correctly, she has assurance from the trusted CA that Ebob really is Bob's public key. Alice can now go ahead and use Bob's public key to encrypt confidential information to send to Bob or to verify Bob's signatures, protected by the assurance of the certificate.
Of course, each user must obtain an authentic copy of the CA's public key, but since this only requires the distribution of one key, it is practical to carry out this distribution by hand, possibly at the same time as each user certifies their own public key in person with the CA.
Provided subtleties such as this are correctly addressed, public-key cryptosystems can ensure the integrity of large computing networks and allow businesses to reap the benefits of the coming electronic era, protected from the heightened threats and security concerns of such an environment.
4. Applications
In Section 3, public-key cryptosystems were demonstrated to provide each of the major security services: confidentiality, user authentication, data origin authentication, data integrity, and non-repudiation. In this section, we describe some current applications of cryptosystems, together with some new applications that are already in the prototype stage. These applications typically require a number of the main security services simultaneously to provide overall security. To solve these problems, the various "modes of operation" for public-key cryptosystems are combined to build a complete security solution.
While readers may be unfamiliar with cryptographic systems, this technology has in fact been a part of society for a number of years. The chances are that most people employ a cryptographic system every day. When using an Automatic Teller Machine (ATM), communicating by cellular phone, or watching premium television services, cryptographic systems are in the background providing security that is taken for granted. The list of "everyday uses" for cryptographic systems goes on. The fact that these systems are almost totally transparent to the user attests to the efficiency, sophistication, and integrability of modern cryptographic techniques.
This point will be further illustrated by investigating the security
services provided by cryptographic systems in some of the technologies
we all use daily, and by exploring the requirements of other exciting technologies
soon to reach the mass market.
4.1 Automatic Teller Machines
The first example of cryptographic systems in widespread use that comes
to mind is the operation of ATMs (or ABMs - Automatic Banking Machines).
Cryptosystems in this context are used to provide a number of services
both to the customer and to the bank that issues the card. Firstly, it
is impractical to store every user's PIN number at every ATM, so the PIN
entered at the ATM must be transmitted over a network to the bank's head
office to be checked. Confidentiality of this PIN is certainly required
while it is in transit. Secondly, when an amount of money is requested,
that information requires data integrity. Otherwise the amount requested
could be altered, and money siphoned from accounts. These are two of the
services provided by cryptosystems in this environment.
4.2 Phone Cards
The use of "stored value" phone cards is widespread throughout North
America and Europe. In this instance information encoding the amount of
money left on the card is stored in electronic form on the card. Suppose
that the integrity of this information was not protected. Then anyone could
alter the stored information, so that the amount stored on the card was
replenished, thereby gaining free access to the telephone network. Here
data integrity is provided by a cryptosystem to protect the telephone network
operator from fraudulent use of the network.
4.3 Cellular Phone Networks
Another area of telephone communications that is vulnerable to fraud
is the use of cellular phones. This is an issue that is only now being
addressed by service providers. The next generation of cellular phones
will employ cryptosystems to prevent fraud. It is easy to see why network
providers want to add security to cellular phones - the Cellular Telecommunications
Industry Association estimates that the current generation of cellular
phones, without security, enables fraudulent use at the cost of between
$1.5 and $2.5 billion each year.
4.4 Remote System Access
An increasing trend in business is the use of remote computing facilities. Many employees work from home or mobile offices and communicate through a computer with a remote connection. Company personnel retrieve pricing and inventory information, access training manuals, electronic mail and financial records, and review internal job postings. In such situations, there are several risks: the information exchanged could be intercepted and used against the company, a system perpetrator could gain access to the system and steal proprietary information, or the operation of the computer system could be sabotaged by destroying files or planting viruses. Thus in such an environment, the services commonly afforded by a public-key system include: user authentication of all users requesting access to prevent sabotage, confidentiality to hide sensitive data from competitors, and data integrity to protect pricing and inventory information.
The four examples above illustrate current "real-world" applications of public-key cryptosystems. What does the future hold for public-key cryptosystems, and what services can we expect to see it enable in the future?
One exciting avenue that is currently becoming dominant is the use of
smart cards (also referred as chip cards). These are cards
the same size as standard credit cards, but contain a small microprocessor.
As public-key technology advances, it is now possible to install a public-key
system on these cards at little expense. Potentially smart cards enable
the added security provided by a public-key cryptosystem to be utilized
on a device small enough to fit into your purse or wallet. Some of the
applications that such a technology enables are discussed below, together
with other exciting applications for public-key systems that are currently
at the prototype stage.
4.5 Credit Cards
Major credit card companies are currently planning the transition from the use of the familiar magnetic-stripe cards to smart cards. With magnetic-stripe cards, no security services can be placed on the card itself, so transaction security is only provided between the point-of-sale terminal and the card issuer. This means that customers and card issuers must place trust in the point-of-sale terminal. The use of smart cards would remove the need for this trust. A public-key cryptosystem on the smart card would provide confidentiality for the card number, together with data origin authentication, data integrity, and non-repudiation through digital signatures for the transaction information.
Another application of public-key cryptography to the credit card industry
will be to supply security for Internet shopping. Visa and Mastercard have
already developed the Secure Electronic Transaction (SET) protocol as a
standardized method to secure card payments over open networks. The SET
protocol employs public-key technology.
4.6 Electronic Cash
The technology to allow electronic cash is currently in the prototype
stage. Proposed solutions employ public-key cryptosystems to provide security.
A secure system has been developed that allows the notes and coins in your
wallet to be replaced by a smart card containing a stored value of money.
This advance removes the need for individuals and businesses to carry physical
cash, therefore reducing crime. One fringe benefit is to prevent incorrect
change being given. Furthermore, access to your bank account via ordinary
telephone lines allows cash to be withdrawn by a simple telephone call
rather than by a time-consuming visit to the ATM.
4.7 Medical Records
One of the most promising applications for smart cards is in the health care industry. Patients will carry a smart card on which their medical records are stored. Doctors can then access these records almost instantaneously. This ability will enable faster treatment and improved diagnosis, in some cases helping lives to be saved. Of course, medical records contain sensitive information, so storing records on a card is only conceivable provided security is provided on the card by a public-key cryptosystem. The services required include confidentiality and data integrity of patient information.
5. Conclusions
Through the use of public-key cryptosystems, the area of information security has tremendous potential to assist commercial success, provide peace of mind, and improve the quality of life. This document scratches the surface of this exciting field by outlining how security services are provided by public-key systems. The possible applications for this technology are endless.
6. Further Reading
This whitepaper sets out to give a brief introduction to the subject of Information Security. The following expositions of the subject are recommended to the interested reader.