Applications of Number Theory in Cryptography

Overview

Cryptography is a division of applied mathematics concerned with developing schemes and formulas to enhance the privacy of communications through the use of codes. Cryptography allows its users, whether governments, military, businesses, or individuals, to maintain privacy and confidentiality in their communications. The goal of every cryptographic scheme is to be "crack proof" (i.e, only able to be decoded and understood by authorized recipients). Cryptography is also a means to ensure the integrity and preservation of data from tampering. Modern cryptographic systems rely on functions associated with advanced mathematics, including a specialized branch of mathematics termed number theory that explores the properties of numbers and the relationships between numbers.

Background

Attempts to preserve the privacy of communications is an age-old quest. From the use of hidden text, disappearing inks, and code pads has evolved the modern science of cryptography. The word cryptography originally derives from the Greek, kryptos (to hide). In essence, cryptography is the study of procedures that allow messages or information to be encoded (obscured) in such a way that it is extremely difficult to read or understand the information without having a specific key (i.e., procedures to decode).

Encryption systems can involve the simplistic replacement of letters with numbers, or they can involve the use of highly secure "one-time pads" (also known as Vernam ciphers). Because one-time pads are based upon codes and keys that can only be used once, they offer the only "crack proof" method of cryptography known. The vast number of codes and keys required, however, makes one-time pads impractical for general use.

Many wars and diplomatic negotiations have turned on the ability of one combatant or country to read the supposedly secret messages of its enemies. In World War II, for example, the Allied Forces gained important strategic and tactical advantages from being able to intercept and read the secret messages of Nazi Germany that had been encoded with a cipher machine called Enigma. In addition, the United States gained a decided advantage over Japanese forces through the development of operation MAGIC, which cracked the codes used by Japan to protect its communications.

In step with the growth of computing technologies and the decline of paper and pen record keeping, the importance of cryptography rose during the later half of the twentieth century. Increasing amounts of data began to have permanent storage only in computer memory. Although the technological revolution and rise of the Internet presented unique security challenges, there were also challenges to the basic security of mounting levels of information stored and transmitted only in electronic form. This increasing reliance on electronic communication and data storage increased demand for advancements in cryptologic science. The use of cryptography broadened from its core diplomatic and military users to become of routine use by companies and individuals seeking privacy in their communications. Governments, companies and individuals, required more secure—and easier to use—cryptologic systems to secure their databases and email.

In addition to improvements made to cryptologic systems based on information made public from classified government research programs, international scientific research organizations devoted exclusively to the advancement of cryptography (e.g., the International Association for Cryptologic Research, or IACR), began to apply mathematical number theory to enhance privacy, confidentiality, and the security of data. Applications of number theory were used to develop increasingly involved algorithms (step-by-step procedures for solving a mathematical problem). In addition, as commercial and personal use of the Internet grew, it became increasingly important not only to keep information secret, but also to be able to verify the identity of message sender. Cryptographic use of certain types of algorithms called "keys" allow information to be restricted to a specific and limited audience, whose individual identities can be authenticated.

In some cryptologic systems, encryption is accomplished by choosing certain prime numbers and then products of those prime numbers as the basis for further mathematical operations. In addition to developing such mathematical keys, the data itself is divided into blocks of specific and limited length so that the information that can be obtained even from the form of the message is limited. Decryption is usually accomplished by following an elaborate reconstruction process that itself involves unique mathematical operations. In other cases, decryption is accomplished by performing the inverse mathematical operations performed during encryption.

Although it may have been developed earlier by government intelligence agencies, in August 1977 Ronald Rivest, Adi Shamir, and Leonard Adleman published an algorithm destined to become a major advancement in cryptology. The RSA algorithm underlying the system derives its security from the difficulty in factoring very large composite numbers. By the end of the twentieth century the RSA algorithm became the most commonly used encryption and authentication algorithm in the world. The RSA algorithm was used in the development of Internet web browsers, spreadsheets, data analysis, email, and word processing programs.

More than simply publishing a mathematical algorithm, however, Rivest, Shamir, and Adleman developed the first public key cryptologic system widely available to commercial and private users. The most important of the modern cryptographic systems to be based on the RSA algorithm (and its modifications and derivations) are termed "public key" systems. These systems are considered to be among the most secure of cryptographic techniques. Encoding and decoding is accomplished using two keys—mathematical procedures to lock (code) and unlock (decode) messages. In such "two-key" cryptologic systems, those wishing to use the public key system distribute the "public" key to those intended to have the capability to encode messages. The sender uses the recipient's public key to encode the message, but the message can only be decoded with the recipient's private key. This assures that only the holder of the private key can decode an encoded message. Beginning in 1991 the public key method was used to enhance Internet security through a freely distributed package called Pretty Good Privacy (PGP).

Impact

Applications of number theory allow the development of mathematical algorithms that can make information (data) unintelligible to everyone except for intended users. In addition, mathematical algorithms can provide real physical security to data—allowing only authorized users to delete or update data. One of the problems in developing tools to crack encryption codes involves finding ways to factor very large numbers. Advances in applications of number theory, along with significant improvements in the power of computers, have made factoring large numbers less daunting.

In general, the larger the key size used in PGP-based RSA public-key cryptology systems, the longer it will take computers to factor the composite numbers used in the keys. Accordingly, RSA cryptology systems derive their reliability from the fact that there are an infinite number of prime numbers—and from the difficulties encountered in factoring large composite numbers composed of prime numbers.

Specialized mathematical derivations of number theory such as theory and equations dealing with elliptical curves are also making an increasing impact on cryptology. Although, in general, larger keys provide increasing security, applications of number theory and elliptical curves to cryptological algorithms allow the use of easier-to-use smaller keys without any loss of security.

Another ramification related to applications of number theory is the development of "nonreputable" transactions. Non-reputable means that parties cannot later deny involvement in authorizing certain transactions (e.g., entering into a contract or agreement). Many cryptologists and communication specialists assert that a global electronic economy is dependent on the development of verifiable and non-reputable transactions that carry the legal weight of paper contracts. Legal courts around the world are increasingly being faced with cases based on disputes regarding electronic communications.

Advancements in number theory have been equally applied, however, in an attempt to crack important cryptologic systems. In RSA composite number-based, two-key cryptologic systems, there are public keys and private keys. Trying to crack the codes (the encryption procedures) requires use of advanced number theories that allow, for instance, an unauthorized user to determine the product of the prime numbers used to start the encryption process. Factoring this product is a difficult and tedious procedure to determine the underlying prime numbers. An unsophisticated approach might be simply to attempt to try all prime numbers. The time to accomplish this task, however, can defeat all but the most determined of unauthorized users. Other more exotic attempts involve algorithms termed quadratic sieves, a method of factoring integers developed by Carl Pomerance that is used to attack smaller numbers, and field sieves algorithms, which are used in attempts to determine larger integers.

Within the last two decades of the twentieth century, advances in number theory allowed factoring of large numbers that by hand might take billions of years to procedures that with the use of advanced computing might be accomplished in a matter of months. Further advances in number theory may lead to the discovery of a polynomial time factoring algorithm that can accomplish in hours what now takes months or years of computer time.

Advances in factoring techniques and the expanding availability of computing hardware (both in terms of speed and low cost) make the security of the algorithms underlying cryptologic systems increasingly vulnerable. These threats to the security of cryptologic systems are, in some regard, offset by continuing advances in the design of powerful computers that have the ability to generate larger keys by multiplying very large primes. Despite the advances in number theory, it remains easier to generate larger composite numbers than it is to factor those numbers.

The National Institute of Standards and Technology (NIST) oversees the development of many cryptography standards. One such standard, developed by commercial entities and the United States National Security Agency (NSA) in the 1970s, was termed the Data Encryption Standard (DES). In anticipation of increasing security needs, late in the twentieth century NIST began to work toward the implementation of the Advanced Encryption Standard (AES) to replace DES. Although there were efforts to liberalize trade policies, at the end of the twentieth century security algorithms used in PGP-type programs were classified as munitions by the United States government. As such, they remained subject to severe export control and restrictions that inhibited their widespread distribution and use.

K. LEE LERNER