Public Key Cryptography

Applications and Attacks

Lynn Margaret Batten

• Verlag: Wiley-IEEE Press
• Jahr: 2013
• ISBN:
  9781118482254
• Auflage: 1
• Thema: Informatique
• Thema: Cybersécurité

Complete coverage of the current major public key cryptosystems their underlying mathematics and the most common techniques used in attacking them Public Key Cryptography: Applications and Attacks introduces and explains the fundamentals of public key cryptography and explores its application in all major public key cryptosystems in current use, including ElGamal, RSA, Elliptic Curve, and digital signature schemes. It provides the underlying mathematics needed to build and study these schemes as needed, and examines attacks on said schemes via the mathematical problems on which they are based – such as the discrete logarithm problem and the difficulty of factoring integers. The book contains approximately ten examples with detailed solutions, while each chapter includes forty to fifty problems with full solutions for odd-numbered problems provided in the Appendix. Public Key Cryptography: •Explains fundamentals of public key cryptography •Offers numerous examples and exercises •Provides excellent study tools for those preparing to take the Certified Information Systems Security Professional (CISSP) exam •Provides solutions to the end-of-chapter problems

Public Key Cryptography provides a solid background for anyone who is employed by or seeking employment with a government organization, cloud service provider, or any large enterprise that uses public key systems to secure data.

1

Introduction

This book is designed for use as a university text for year three, four, or honors level students. It is intended as a first approach to public key cryptography—no background in cryptography is needed. However, a basic understanding of discrete mathematics and algorithms and of the concept of computational complexity is assumed.

The major public key systems are presented in detail, both from the point of view of their design and their levels of security. Since all are based on a computationally difficult mathematical problem, the mathematics needed to construct and to analyze them is developed as needed along the way.

Each concept presented in the book comes with examples and problems, some of which can be done with limited computational capacity (a calculator for example) and some of which need major computational resources such as a mathematics-based software package or some independently written algorithms. Mathematica, Matlab, Magma [64], and Maple [65] are examples of packaged software that can be used easily to perform the necessary computations. For those who prefer open source software, see [28] where Sage is used for algorithms and examples. The book can be used without additional software resources by avoiding those problems which require them.

The software used by the author for the computationally expensive examples in this book was Maple. The solutions are presented with sufficient detail to permit an easy translation to any other language or package. Full solutions are given to all odd-numbered problems. For those wishing to use the book at a Master's level, an emphasis on the computational complexity of the cryptographic systems and or the attacks on them would provide a solid basis for a good course including programme writing. Emphasis on the computational complexity of attacks on public key systems provides the user with a feel for the level of security provided.

1.1 The Meaning of the Word Cryptography

In this preliminary chapter, we present some of the history of cryptography and the reasons for the development of the systems that we see in use today. There are no exercises associated with this chapter, but the interested reader can follow up any of the references and links provided.

The words “cryptography,” “cryptology,” and “cryptanalysis” are commonly interchanged. However, each of them has a slightly different meaning. The common beginning “crytp” comes from the Greek κρυμμενoζ or kruptos for “hidden.” The ending “graphy” refers to writing and so the first word in the list means “hidden writing” and generally refers to the encryption part of establishing a system for transmitting secrets. We call such an encrypted string a “cipher” or “ciphertext.” Normally, when a cipher is constructed, the idea is that there will be some person or persons who can “legitimately” decipher it and so find the hidden text. In order to legitimately decipher, it is understood that a person will hold what is referred to as a “key,” a means of simply and efficiently determining the original text. On the other hand, without this key, it should not be simple to deduce the hidden text.

The last word, cryptanalysis, refers to an analysis of hidden things, or ciphers, to expose what is hidden; this word generally refers to the decryption or discovery component of the system when the analyst does not have a legitimate key with which to read a cipher.

Finally, the word cryptology is made up of the two components “hidden” and “study” and refers to the study of hidden writings or secrets. This word encompasses both the establishment of encryption methods and the analysis of a cipher in order to break it without the associated key. While “cryptology” would be the correct word for a discussion including both encryption techniques and analysis of these techniques with the intent of breaking them, many people use the word “cryptography” instead.

In the next section, we cover very briefly the introduction of, and changes to, symmetric key cryptography over thousands of years. This is followed by a brief introduction to public key cryptography. Recent applications of cryptography, in addition to simply hiding data, are mentioned in Section 1.5. Section 1.6 mentions current standards in the area of cryptography and their impact.

1.2 Symmetric Key Cryptography

The hiding of secrets in written and pictorial form with the intent of passing on a message to a select few has been documented over thousands of years, going far back in time to ancient Egypt [2, 36]. In many cases, it was used as a game so that the select few were able to have access to information not available to those excluded from the inner circle. However, it was also used in times of political tension and war to communicate securely, guarding secret information from the enemy.

Symmetric key systems are cryptographic systems in which decrypting is a simple method of reversing the encryption used. For example, if a message written in English is encrypted by replacing each letter with the one five places ahead in the alphabet (a is replaced by f, b by g, and so on), then to decrypt, the letters are simply moved five places back. A message written as a binary string may be encrypted by adding it to another, fixed, binary string. To decrypt, adding the fixed binary string again will produce the original message. Thus, to use a symmetric key cryptographic scheme, both the sender and the receiver use essentially the same key.

The simplicity of using the same key both to encrypt and to decrypt is off set by the difficulty of ensuring that all parties have the needed keys in a tense situation, and also when people may be widely dispersed geographically. In time of war, keys have to be physically delivered to personnel even in the remotest and most dangerous locations. In the late 1800s, the idea of a “code book” which listed which keys to be used on which dates was born. Both the transmitter and the receiver needed a copy of the same code book for this to work, but several months of communications could be based on the delivery of a single code book. (Serious users of encryption recognized the need for constantly changing the key!)

1.2.1 Impact of Technology

Despite its history of about 4000 years, cryptography only came of age in the 1800s with the invention of technologies such as the telegraph (for rapid communication over great distances) and manual rotary machines, followed in the early 1900s by electrical rotary machines [2]. David Khan, in his book The Code Breakers [22] explains that the electro mechanical rotary machine for cryptographic purposes was invented almost simultaneously around 1917–1919 by four different people in four different countries. None of these people became rich. One of them, the Swede Arvid Damm, died in 1927 and his company was taken over by another Swede, Boris Hagelin (1892–1983). Despite Hagelin's death, the company, Crypto AG (http://www.crypto.ch/), still operates in Zug, Switzerland. Figure 1.1 shows a machine sold by the company.

Figure 1.1 The M-209 encryption machine sold by Hagelin (from Wikipedia).

1.2.2 Confusion and Diffusion

As cryptography became less of an art form and more of a science in the 1900s, it was inevitable that at some point, someone would try to formalize the principal aims of a cryptographic system. Claude Shannon was one of the first to do so [48]. He argued that a cryptosystem designer should assume that the system may be attacked by someone who has access to it, as was indeed the case during the two world wars when machines were stolen and reverse engineered. He argued that the only point of secrecy should be the key, but that the system design should assist the security by incorporating “confusion” and “diffusion.” “Confusion is intended to make the relationship between the key and the ciphertext as complex as possible. Diffusion refers to rearranging or spreading out the bits in the message so that any redundancy in the plaintext is spread out over the ciphertext” [29]. In most symmetric key cryptosystems, confusion is provided by means of a substitution of some letters or symbols for others, whereas diffusion is provided by a permutation of the letters or symbols.

1.2.3 DES and AES

Horst Feistel (1919–1990) is believed to have been the first person to use the idea of a cipher with input broken into two parts of equal size, and iterated through several rounds in which functions and keys are applied, and right and left sides interchanged [29]. The concept is the basis for many symmetric ciphers in use today including the Data Encryption Standard (DES).

DES was the first commercially driven cryptographic product in history. By the mid-1900s, the effectiveness of cryptography for use by companies wishing to communicate in private led the U.S. government to work with IBM to develop the first fully specified cryptographic system on the open market. In 1976, the U.S. National Bureau of Standards declared it an official Federal Information Processing Standard.

In 1997, it was decided that the parameters of DES were now too small to provide the kind of protection needed, and a public, world-wide call for submissions for a new cryptosystem standard was made by the U.S. National Institute of Standards and Technology (NIST). After several years of analysis of submissions, much done by academics around the world, in 2002 a new standard, known as AES (for Advanced Encryption Standard), was chosen by NIST. While the AES does not incorporate a Feistel-type structure, such as DES, it uses substitutions and permutations along with several rounds. More details on both DES and AES can be found in [52].

Further Reading

F.L. Bauer [2]; D. Khan [22]; S. Pincock [36]; C.E. Shannon [48].

1.3 Public Key (Asymmetric) Cryptography

The one major problem that held back a general uptake of cryptography for use in business circles was that of exchanging keys. While for many years, governments had established methods of managing keys, business people were not interested in employing circumspect, and perhaps even dangerous, methods of exchanging keys. In the 1960s, this became known as the “key management” problem and it was to be another decade before a viable solution was found.

1.3.1 Diffie–Hellman Key Exchange

In 1976, Whit Diffie and Martin Hellman published a paper [13] describing a method of establishing a common key in a secure manner over an insecure channel. The method is based on exponentiation and the fact that exponents can be multiplied in any order with the same result. The method is described in detail in Section 2.3. However, this scheme was useful only for establishing keys and did not actually encrypt data. The search was still on for an encryption scheme that allowed anyone to send an enciphered message to any other person, without pre-establishing keys, such that only the targeted recipient could decrypt the message.

In retrospect, the solution is amazingly simple and the first example appears to have been developed independently from two sources.

Basically, the idea is for each person to have two keys, one to encrypt and one to decrypt. The two keys would have to be bound together in some fundamental way in order for them to “invert” each other, but it should be impossible for an attacker to derive one from the other. The encryption key would be published, as in a telephone book. Only the recipient would know his/her decryption key; it would not be revealed to anyone else. This idea entirely solved the problem of exchanging keys, except for the fact that, initially, no one actually had a real way of setting up such a scheme.

1.3.2 RSA

In 1978, the first actual method for implementing such a scheme was published by Ron Rivest et al. [46] and is now widely known by the first letter of each of the authors' names as RSA. An RSA patent was filed in the United States on December 14, 1977, and approved as #4,405,829 titled “Cryptographic Communications System and Method” to the Massachusett's Institute of Technology, Rivest, Shamir, and Adelman. However, since the work had been published before the patent application, it could not be patented under European and Japanese law. (The RSA United States patent expired in 2000.) The company, RSA Data Security, was formed shortly thereafter and was granted an exclusive license on the RSA patent. In 2006, EMC Corporation (www.emc.com), a global information management and storage company, bought RSA which continues to operate as EMC's security division.

RSA security was based on the difficulty of factoring large numbers. At the time...