June 1998

BY PHILIP C. DECK

The world continues to witness an explosion of technology designed to help people communicate faster and more easily. We carry powerful digital computers in our pockets, exchange digital information in addition to voice data with our mobile phones, and surf the Web with high-end pagers. In the near future, every type of electronic data channel will be used to exchange every type of electronic information. One of the great challenges of the ability to communicate digitally is securing the increased amount of electronic information now exchanged over the wire.

Commercial cryptography (encryption technology) has thus far been the answer to the wide range of issues that impact modern communication, including the assurance of privacy, the certainty of the transmitter or receiver's identity, and the integrity of the communication. However, traditional cryptographic algorithms (such as DSA and RSA), which were once considered effective, have become impractical in light of recent technological advances. These traditional approaches cannot support the new generation of digital communication and information access devices with their low power, small form factor, and high performance requirements.

The emerging breed of laptops, handhelds, cell phones, pagers, and wireless devices require a next-generation security technology. This article provides basic background on cryptography and describes the evolution of Elliptic Curve Cryptography -- security specifically designed to meet the requirements of the new generation of communications solutions.

MODERN CRYPTOGRAPHY BASICS
The term cryptography refers to a precise set of advanced mathematical techniques that have been developed primarily over the last two decades to secure digital information. Before the 1970s, cryptography was mainly used by government agencies, particularly the military. With the proliferation of digital computers, cryptography has emerged as an important science for the private sector, answering the complex security needs of the growing electronic commerce, enterprise networking, and consumer communications industries.

The mathematics of modern cryptography are based on highly sophisticated fields of knowledge such as number theory and group theory. Conceptually, all forms of cryptography are based on generating and managing one or more cryptographic "keys." A cryptographic key allows the unlocking of encrypted data. The advanced mathematics applied to the process of generating and protecting these keys is intended to make it virtually impossible to determine a specific key by someone trying to infiltrate the security system. In many cases, it would be more difficult, for example, than picking out a particular atom among all of the atoms in the universe.

Modern cryptography is generally classified in two broad categories: symmetric key cryptography and asymmetric, or public key, cryptography. Symmetric key cryptography, the earliest of the modern cryptographic techniques, is based on two or more parties sharing the same secret key for encrypting and decrypting the data to be exchanged amongst themselves. The best known example of a symmetric cryptosystem is the Data Encryption Standard (DES). Typical DES keys suitable for commercial applications are at least 56 bits in length.

Symmetric Cryptography
Symmetric cryptography has gained wide-spread acceptance due to its conceptual simplicity and, in real applications, very high efficiency. With a relatively small group of authorized parties, symmetric cryptography strikes an ideal balance between speed and manageability. However, with a very diverse network (i.e., different types of devices, users, information, etc.), the process of managing the secret keys becomes a major challenge.

Public Key Cryptography
Public key cryptography addresses the issue of key manageability. Public key systems use two types of keys: the private key (a non-shared secret key assigned to individual parties) and the public key (a freely exchanged key also assigned to individual parties). The public key is used for encryption and the private key is used for decryption. For example, if Andrew wishes to send a message to Betty, then Andrew would use Betty's public key to encrypt the data. Now, Betty's public key is also mathematically related to her individual private key (which no one else, including Andrew, knows). Betty then uses that private key to decrypt Andrew's message. The distinct advantage is that private keys (the decryption keys) are only known by rightful individuals, while everyone's public keys (the encryption keys) need not be kept secret at all. In practice, such a system greatly reduces the complexity of the key management even in the most diversified networks.

The Digital Identity
The other major impact that public key cryptography has had is to broaden the scope of cryptographic security from simply keeping unauthorized parties from accessing sensitive data (i.e., privacy) to include strong authentication of parties. With public key systems, it is much easier to identify with cryptographic certainty whether a party truly has authorization to access particular data. Especially for electronic commerce applications, the authentication capability is becoming more important than the privacy aspect of cryptography. In the past, individuals have been identified only with the use of passwords, a security tool that can be easily compromised. With public key cryptography, more sophisticated cryptographic tools such as tokens (e.g., smart cards), digital signatures, and certificates are used to provide the full scope of cryptographic security services.

CLASSIFICATIONS AND METHODOLOGIES
In practice, there are three fundamental classifications of public key cryptographic techniques.

Algorithms are the essential, low-level, mathematical formulations that prevent unauthorized access to private keys. Protocols are conceptual groupings of algorithms and related steps to achieve a certain user-level security functionality. The final classification is APIs, which is the developer-level programming interface to access protocols and algorithms in a convenient manner.

The best known and the most widely deployed methodology in software-only implementations is integer factorization. With this method, the factoring of a very large integer constitutes the basic mathematical challenge that an attacker must overcome in order to compromise security. Integer factorization algorithm is also known as the Rivest-Shamir-Adleman or RSA algorithm.

ELLIPTIC CURVE CRYPTOGRAPHY
However, as mentioned earlier, traditional cryptographic algorithms are not particularly efficient in small form factor, low-power, "resource constrained" devices, as they require a co-processor to complete the calculations in a timely manner. Adding a co-processor significantly raises the cost of manufacture, rendering many devices impractical. The cost of producing a smart card, for example, is increased by as much as 400 percent when an additional processor is required. For embedded systems or telecommunications applications characterized by extremely high volumes and a wide variety of devices, many of which have limited computing resources, the trend has been towards alternate algorithms.

One technology in particular, called Elliptic Curve Cryptography (ECC), has become the cryptography of choice for mobile computing and communications devices due to its size and efficiency benefits. ECC is based on the mathematical process of guessing random points and complex point trajectories within sophisticated algebraic constructs called elliptic curves (see sidebar entitled The Math Behind ECC). Because of the increased difficulty of the essential math problem, the key needed to secure an ECC application is dramatically shorter than that of equivalent RSA applications.

Smaller key sizes result in lower bandwidth requirements for the system. For mobile devices, power consumption is also reduced. With commercial-grade implementations of ECC, developers should also expect to see an overall speed increase introduced by computational optimizations.

Cryptographic Protocols
Although the right algorithm provides the fundamental security, improper management of the algorithms can lead to insecure applications. The prevention of such mishaps often lies in well-defined cryptographic protocols.

Perhaps the most famous protocol in public key cryptography is the Diffie-Hellman (DH) key exchange protocol. This protocol introduced the public key concept to the world in 1976, and has remained a very popular protocol for strong authentication of entities. More recently, driven by the needs of the embedded systems world, DH analogs have been introduced for ECC.

Pure DH or ECC DH applications are, however, susceptible to impersonation or "man in the middle" attack, whereby an adversary establishes digital facades between two parties in order to obtain private information. Advanced key exchange protocols such as the Menezes-Qu-Vanstone (MQV) introduce mutual strong authentication which allows both parties to confidently identify each other before exchanging sensitive information. MQV is currently deployed through ECC systems.

ECC STANDARDIZATION AND CURRENT USE
In addition to strength and efficiency, the interoperability of public key technology is a critical consideration. Smart cards, wireless devices, and software and hardware for desktop computing must all interoperate reliably and seamlessly in the growing digital infrastructure. Various accredited standards bodies around the world are currently drafting standards for ECC. By June of 1998, the American National Standards Institute (ANSI) Financial Services committee is expected to publish ANSI X9.62, The Elliptic Curve Digital Signature Algorithm (ECDSA). ANSI X9.63, Elliptic Curve Key Agreement and Transport Protocols, is now in progress. Elliptic curves are also covered by the IEEE P1363 draft standard (Standard for Public Key Cryptography), which includes encryption, signature, and key agreement mechanisms.

As the draft standards for ECC near completion, a growing number of companies have already licensed and begun integrating ECC into their products, including 3Com/Palm Computing, Motorola, VeriFone, Atalla Corp. (A Tandem Company), and Sterling Commerce. The future of secure, low-cost wireless and other digital communications depends heavily on strong, efficient cryptography. The availability of efficient ECC implementations has revolutionized public key cryptography, enabling its use in and accelerating the deployment of advanced wireless technologies.

The Math Behind ECC

The security of ECC rests on the difficulty of the elliptic curve discrete logarithm problem. Although this example is simplified, the following provides an introduction to this mathematical problem.

An elliptic curve, defined modulo a prime p, is the set of solutions (x,y) to an equation of the form

y2 = x3 + ax + b (mod p)

for two numbers a and b. If (x,y) satisfies the above equation then P=(x,y) is a point on the elliptic curve.

The most efficient and preferred method to implement elliptic curves is over the finite field consisting of 2m elements. Such a representation can offer maximum efficiency benefits in the operation of ECC.

It is possible to define the "addition" of two points on the elliptic curve. Suppose P and Q are both points on the curve, then

P + Q

will always be another point on the curve. The elliptic curve discrete logarithm problem can be stated as follows. For a point p, on an elliptic curve, xP represents the point P added to itself x times. Suppose Q is a multiple of P, so that

Q = xP

for some x. Then the elliptic curve discrete logarithm problem is to determine x given P and Q.

While this may look simple at first, in reality it is an extremely difficult problem to solve, due to the complex nature of the elliptic curve.

Philip C. Deck is President and CEO of Certicom, Corp. Deck has focused Certicom's business operations on the development, standardization, and marketing of OEM cryptographic implementations. Certicom is a leading provider of cryptographic technologies for computing and communications companies. Vendors of electronic commerce and digital communications products are integrating and deploying Certicom's technology across a wide range of operating environments and devices to build the strongest, most efficient security into software, smart card, and wireless applications. As information security architects, Certicom's teams of cryptographers, engineers, and developers provide comprehensive OEM solutions, from advanced cryptographic implementations to consulting for systems integration and development support. Certicom's cryptographic re-search and product development is based in Toronto, Canada, with worldwide sales and marketing operations in San Mateo, CA. Certicom shares are traded on the Toronto Stock Exchange under the symbol "CIC." For more information, please visit Certicom's Web site at www.certicom.com, or contact Certicom at 1-800-561-6100.