Cryptology and Number Theory

█ K. LEE LERNER

Cryptography is a division of applied mathematics concerned with developing schemes and formula to enhance the privacy of communications through the use of codes. More specifically, 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 encoded information without having a specific key (i.e., procedures to decode) that can be used to reverse the encoding procedure.

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, number theory that explores the properties of numbers and the relationships between numbers.

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 in the ability of one combatant or country to read the supposedly secret messages of its enemies. The use of cryptography has 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 systems to protect 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 (IACR)), began to apply applications of mathematical number theory to enhance privacy, confidentiality, and the security of data. Applications of number theory were used to develop increasingly involved algorithms (i.e., step-by-step procedures for solving a mathematical problems). 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 audiences whose identities can be authenticated.

Mathematical Operations

In some cryptologic systems, encryption is accomplished, for example, by choosing certain prime numbers and then products of those prime numbers as a 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.

In the late 1970s, government intelligence agencies and Ronald Rivest, Adi Shamir, and Leonard Adleman published an algorithm (the RSA 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. The RSA algorithm was the mathematical foundation for the development of a public two-key cryptographic system called Pretty Good Privacy (PGP).

Applications of number theory allow the development of mathematical algorithms which 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 a system systems, the longer it will take computers to factor the composite numbers used in the keys.

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 smaller keys with any loss of security.

Advancements in number theory are also used to crack important cryptologic systems. Attempting to crack encryoption codes (the encryption procedures) often 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, at best, a time consuming process to determine the underlying prime numbers. An unsophisticated approach, for example, might be to simply attempt or apply all prime numbers. Other more elegant 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 that are used in attempts to determine larger integers. Advances in number theory allowed factoring of large numbers to move from procedures that, by manual manipulation, could take billions of years, to procedures that—with the use of advanced computing—can be accomplished in weeks or months. Further advances in numbertheory 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 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.

Other improvements related to applications of number theory involve the development of "non-reputable" transactions. Non-reputable means that parties can not 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 faced with cases based on disputes regarding electronic communications.

█ FURTHER READING:

BOOKS:

Burn R. P. A Pathway into Number Theory, 2nd. ed. New York: Cambridge University Press, 1997.

Niederreiter, Harald. Mathematical Foundations of Coding and Cryptology. Singapore: World Scientific Press, 2003.

Wagstaff, Samuel S., Jr., Cryptanalysis of Number Theoretic Cyphers Boca Raton, FL: CRC Press, 2002.

SEE ALSO

Cryptology, History
Cryptonym