Cryptography

From Free net encyclopedia

Image:SZ42-6-wheels.jpgCryptography or cryptology is a field of mathematics and computer science concerned with information security and related issues, particularly encryption and authentication.

Cryptography is an interdisciplinary subject, drawing from several fields. Older forms of cryptography were chiefly concerned with patterns in language. More recently, the emphasis has shifted, and cryptography makes extensive use of mathematics, particularly discrete mathematics, including topics from number theory, information theory, computational complexity, statistics and combinatorics. Cryptography is also considered a branch of engineering, but it is considered to be an unusual one as it deals with active, intelligent and malevolent opposition (see cryptographic engineering and security engineering). An active area of research studies the relationship between cryptographic problems and quantum physics (see quantum cryptography and quantum computing). And in the everyday world, cryptography is a tool used within computer and network security.

Template:Portal

1 Terminology
2 History of cryptography and cryptanalysis
3 Modern cryptography
4 Cryptography and Modern Society
5 See also
6 References
7 External links

[edit]

Terminology

The term "cryptography" ("secret writing," from the Greek kryptós, "hidden," and gráphein, "to write") is often used to refer to the field as a whole, as is "cryptology" ("the study of secret writing"). The study of how to circumvent the use of cryptography is called "cryptanalysis" or, loosely, "codebreaking."

Classically, "cryptography" referred almost exclusively to "encryption", the process of converting ordinary information ("plaintext") into an unreadable "ciphertext". "Decryption" is the reverse process, recovering the plaintext back from the ciphertext.

A "cipher" is a set of algorithms for encryption and decryption. The exact operation of a cipher is normally controlled by a key — a secret parameter for the cipher algorithms. Historically, ciphers were often used directly for encryption or decryption, but in modern techniques, a cipher is only one part of a "cryptosystem", a set of algorithms, protocols, and operating procedures for encryption and decryption that may use the cipher. The terms "encipherment" and "decipherment" are used to describe the cipher algorithms, to avoid confusion.

In colloquial parlance, the term "code" is often used synonymously with "cipher." In cryptography, however, "code" traditionally had a specific meaning. A "code" was a procedure which replaced a unit of plaintext, typically meaningful words or phrases, with a code word (for example, "apple pie" replaces "attack at dawn"). Codes are no longer used in serious cryptography, since the best ciphers are more practical and secure, and better suited to computers.

Today, while some practitioners use the terms cryptography and cryptology interchangeably, others make the distinction that cryptography refers to the use and practice of cryptographic techniques, while cryptology refers to the subject as a field of study (analogously with biology). The study of cryptography now encompasses not only traditional topics like encryption and authentication, but also new ones like zero-knowledge proofs and secure multiparty computation. As the noted cryptologist Ron Rivest summarized: cryptography is about communication in the presence of adversaries.<ref>Ronald Rivest, "Cryptography" From the Handbook of Theoretical Computer Science, edited by J. van Leeuwen, Elsevier Science Publishers B.V., 1990</ref>

[edit]

History of cryptography and cryptanalysis

Main article: History of cryptography Image:Skytala&EmptyStrip-Shaded.png

Historically, cryptography was concerned solely with encryption; that is, means of converting information from its normal, comprehensible form into an incomprehensible format, rendering it unreadable without secret knowledge. In recent decades, the field has expanded beyond secrecy to include techniques for authentication, signatures, interactive proofs, secure computation, steganography, and others.

Cryptography has had a long and colourful history. Generally, the earliest forms of secret writing (now collectively termed classical cryptography) required little more than pen and paper. The two main categories of classical ciphers are transposition ciphers, which rearrange the order of letters in a message, and substitution ciphers, which systematically replace letters or groups of letters with other letters or groups of letters. One of the earliest and simplest substitution ciphers was the Caesar cipher, used by Julius Caesar during his military campaigns. Encryption was used to ensure secrecy in important communications, such as those of spies, military leaders, and diplomats, but it also had religious applications. Early Christians used cryptography to help guard their religious writings to preserve them in the face of persecution. Cryptography is also advocated in the Kama Sutra as a way for lovers to communicate without being discovered. In addition to encryption, steganography was also developed in the ancient times. While encryption attempts to render a message unreadable, steganography attempts to make a message undetectable. One example of such a technique, from Herodotus, was to write a message as a tattoo on a slave's head, concealed by regrown hair.<ref name="kahnbook">David Kahn, The Codebreakers, 1967, ISBN 0-684-83130--9.</ref>

Ciphertexts produced by these classical ciphers reveal statistical information about the plaintext, which is usable to break them. After the Arab discovery of frequency analysis (circa 1000), nearly all such ciphers were more or less readily readable by an informed attacker. Classical ciphers still enjoy popularity today, though mostly as puzzles (see cryptogram). Ciphers remained vulnerable to cryptanalysis by this technique until the invention of the polyalphabetic cipher by Leon Battista Alberti, in 1467, in which different parts of the message would be encrypted differently. In the polyalphabetic Vigenère cipher, for instance, encryption is performed by using a key word, and different letters are encoded differently depending on which letter of the key word it aligns with. Despite this improvement, polyalphabetic ciphers were still partially vulnerable to frequency analysis techniques.<ref name="kahnbook" />

Although frequency analysis was a very powerful technique, cryptography was still effective in practice, as in many cases, the holder of an enciphered message would be unaware of the technique used to create it. Although this may work, it was recognized in the 19th century that this was not the ideal state of affairs: in principle, a good cipher should still be secure if the adversary knows the cipher itself; the key should represent all the information unknown to the adversary. This is called Kerchoff's law.

Image:Nsa-enigma.jpg

Various physical devices and aids have been used for encryption in order to assist in the computation of the ciphers. One of the earliest may have been the scytale, a rod used in ancient Greece as an aid for a transposition cipher. In medieval times, other aids were invented such as the Cardan grille for steganography. With the invention of polyalphabetic ciphers came more sophisticated aids such as Alberti's cipher disk and Johannes Trithemius' tabula recta. Early in the 20th century, several mechanical devices were invented for performing encryption, including rotor machines — most famously the Enigma machine used by Germany in World War II. The ciphers these machines implemented brought about a substantial increase in cryptanalytic difficulty.<ref>James Gannon, Stealing Secrets, Telling Lies: How Spies and Codebreakers Helped Shape the Twentieth Century, Washington, D.C., Brassey's, 2001, ISBN 1-57488-367-4.</ref>

With the advent of digital computers and electronics, much more complex ciphers could be implemented. A characteristic of computer ciphers is that they operate on binary strings, unlike classical and mechanical schemes, which use more traditional alphabets. However, with these advantages came certain disadvantages, as computers could also be used for cryptanalysis. Nonetheless, modern ciphers have stayed ahead of cryptanalysis: it is usually the case that using a cipher is very efficient, while breaking it takes exponential effort.

Extensive academic research into modern cryptography is relatively recent — it began in the open community only as recently as the 1970s with the public release of the specifications for the Data Encryption Standard (DES) and the invention of RSA. Since then, cryptography has become a widely-used tool in communications, computer networks, and computer security generally. The security of many modern cryptographic techniques is based on the hardness of certain computational problems, such as the integer factorization problem or the discrete logarithm problem. In many cases, there are proofs that cryptographic techniques are secure if a certain computational problem cannot be solved efficiently. In this way, the security of many modern cryptographic techniques are tied to the P=NP problem.<ref name="goldreichbook">Oded Goldreich, Foundations of Cryptography, Volume 1: Basic Tools", Cambridge University Press, 2001, ISBN 0-521-79172-3</ref>

As well as noting lessons from its history, cryptographers must also be careful to consider the future. Moore's law is normally taken into account when specifying key lengths, and the potential effects of quantum computing are already being considered by good cryptographic system designers.<ref name="hac">A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography ISBN 0-849-38523-7.</ref>

[edit]

Modern cryptography

The modern field of cryptography can be broken down into several areas of study. The following are the main ones, but they are not the only ones.

[edit]

Symmetric-key cryptography

Main article: Symmetric key algorithm

Symmetric-key cryptography refers to encryption methods in which both the sender and receiver share the same key (or in which their keys are different, but related in an easily computable way). Other terms include secret-key, private-key, one-key and single-key cryptography. This was the only kind of encryption publicly known for all of recorded history until 1976.<ref name="dh2">Whitfield Diffie and Martin Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, vol. IT-22, Nov. 1976, pp: 644-654.</ref>

Image:SAFER.png The study of modern symmetric-key cryptography relates mainly to the study of block ciphers and stream ciphers and their applications. A block cipher is the modern form of a polyalphabetic cipher: block ciphers take a block of plaintext data and a key, and output a block of ciphertext data of the same size. Block ciphers are not secure cryptosystems themselves (by modern standards, it is unacceptable for the encryption of a single plaintext to always be the same), but may be used in a mode of operation such as EAX mode to implement secure, authenticated encryption. DES and AES are block ciphers accepted as cryptography standards, but many others have been proposed; see Category:Block ciphers.<ref name="hac" /><ref name="schneierbook">Bruce Schneier, Applied Cryptography, 2nd edition, Wiley, 1996, ISBN 0471117099.</ref>

Stream ciphers, by contrast, operate on a continuous stream of plaintext, and produce an encrypted output stream based on an internal state that changes as the cipher operates. The state's evolution can be controlled by both the key and the plaintext stream, or it can derive from the key alone. RC4 is an example of a well-known stream cipher; see Category:Stream ciphers.<ref name="hac" />

Symmetric-key cryptography encompasses problems other than encryption, mainly those that can be accomplished with block ciphers. For instance:

Cryptographic hash functions take a long input (often a message) and output a short hash of it. Despite that infinitely many hash collisions must exist (pairs of inputs that lead to the same output), they should be difficult for any efficient algorithm to find. MD5 and SHA-1 are well-known examples of cryptographic hash functions; see Category:Cryptographic hash functions.<ref name="hac" />

Message authentication codes (MACs) are much like cryptographic hash functions, except that a secret key is needed to compute the value. As the name suggests, MACs can be used for message authentication.<ref name="hac" />

[edit]

Public-key cryptography

Main article: Public-key cryptography

Symmetric-key cryptosystems either use the same key for encryption and decryption, or the key used for decryption is easily calculated from the key used for encryption. The main drawback of symmetric ciphers is that the two communicating parties must share a secret key: it may be difficult to initially establish the secret. In a groundbreaking 1976 paper, Whitfield Diffie and Martin Hellman proposed the notion of public-key cryptography in which two different but related keys are used: one for encryption and one for decryption (public-key cryptography is also called asymmetric-key cryptography because of the difference between the keys).<ref>Whitfield Diffie and Martin Hellman, "Multi-user cryptographic techniques" [Diffie and Hellman, AFIPS Proceedings 45, pp109-112, June 8, 1976].</ref> In a public-key cryptosystem, the encryption key may be freely distributed, as long as the decryption key remains secret, hence, the encryption key is the public key and the decryption key is the private or secret key. Diffie and Hellman showed that public-key cryptography was possible by presenting the Diffie-Hellman key exchange protocol.<ref name="dh2" /> In 1978, Ronald Rivest, Adi Shamir, and Len Adleman invented RSA, the first public-key cipher.<ref>R. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Vol. 21 (2), pp.120–126. 1978. Previously released as an MIT "Technical Memo" in April 1977.</ref> However, in 1997, it became known that asymmetric cryptography was first invented secretly at GCHQ, a British intelligence organization, in the early 1970s, and that both Diffie-Hellman and RSA had been previously discovered in secret (by Malcolm J. Williamson and Clifford Cocks, respectively).Template:Fact

RSA, in addition to being the first known example of a public-key cryptosystem, is also one of the most popular. Other popular public-key cryptosystems include the Cramer-Shoup cryptosystem and various elliptic curve techniques. See Category:Asymmetric-key cryptosystems

In addition to encryption, public-key cryptography encompasses digital signatures. A digital signature is meant to be digital version of a signature, which should be easy for the correct user to produce, but difficult for anyone else to forge. However, digital signatures surpass this notion by incorporating the message to be signed in the computation of a signature: thus, digital signatures cannot simply be moved from one document to another. In a digital signature scheme, there are two algorithms: one for signing, in which the secret key is combined with the message, and one for verification, in which the public key is used to compare the digital signature to the message. RSA can also be used for digital signatures, and some schemes such as DSA and ElGamal signatures are designed especially for signatures. Digital signatures are central to the operation of public key infrastructure and many network security schemes (e.g., Kerberos, most VPNs, etc).<ref name="schneierbook" />

Public-key algorithms are most often based on the computational complexity of number theory problems. Because of this, most public-key algorithms involve operations like modular multiplication and exponentiation, which are much more expensive than the techniques used to create block ciphers. As such, public-key cryptosystems are usually used in a hybrid system, in which fast symmetric encryption is used for the bulk of the message, while the symmetric key used is sent with the message, encrypted using the public-key scheme. Similarly, hybrid signature schemes are often used, in which a cryptographic hash function is computed, and only the resulting hash is digitally signed.<ref name="hac" />

[edit]

Cryptanalysis

Main article: Cryptanalysis

The goal of cryptanalysis is to find some weaknesses or insecurity in a cryptographic scheme. Cryptanalysis might be undertaken by a hostile attacker, attempting to subvert a system; or by the system's designer (or others) wishing to evaluate whether a system is secure. In modern practice, however, cryptographic techniques usually come with proofs that establish security of the system (at least, under clear and hopefully reasonable assumptions).

It's a common fallacy that every encryption method can be broken by someone, even if we include intelligence agencies such as the NSA. For instance, Claude Shannon proved that the one-time pad cipher is unbreakable, provided the key material is truly random, never reused, kept secret from all possible attackers, and of equal or greater length than the message<ref>"Shannon": Claude Shannon and Warren Weaver, "The Mathematical Theory of Communication", University of Illinois Press, 1963, ISBN 0-252-72548-4</ref>. Apart from the one-time pad, most encryption can be broken with enough computational effort, but the amount of effort needed to break a cipher may be exponential compared to the amount of effort needed to use the cipher. In such cases, security can still be achieved if the parameters (such as key length) are large enough that the exponential effort is beyond the estimated ability of the adversary.

There are a wide variety of cryptanalytic attacks, and they can be classified in several ways. One distinction concerns what an attacker can know and do in order to learn secret information. In a ciphertext-only attack, the cryptanalyst has access only to the ciphertext (modern cryptosystems are usually immune to ciphertext-only attacks). In a known-plaintext attack, the cryptanalyst has access to a ciphertext and its corresponding plaintext (or many such pairs). In a chosen-plaintext attack, the cryptanalyst may chose a plaintext and learn its corresponding ciphertext (perhaps many times). Finally, in a chosen-ciphertext attack, the cryptanalyst may choose ciphertexts and learn their corresponding plaintexts.<ref name="hac" />

Cryptanalysis of symmetric-key techniques typically involves looking for attacks against block ciphers or stream ciphers that are better than should exist for a perfect cipher. For example, a brute force attack against DES would take one known plaintext and 2⁵⁵ operations, to try approximately half of the possible keys. However, one attack against DES requires 2⁵⁰ known plaintexts and 2⁵⁰ operations to recover the secret key.Template:Fact Differential cryptanalysis and linear cryptanalysis are some recent important techniques in the cryptanalysis of block ciphers.

Public-key techniques are all based on the difficulty of various computational problems. The most famous of these is the problem of integer factorization (the RSA cryptosystem is based on a problem related to factoring), but the discrete logarithm problem is also especially important. Much of the important public-key cryptanalysis concerns numerical algorithms for solving these computational problems efficiently. For instance, the best algorithms for solving the elliptic curve-based version of discrete logarithm are much worse than the best known algorithms for factoring. Therefore, to achieve an equivalent strength, factoring-based techniques need to use larger keys than elliptic curve techniques. For this reason, public-key cryptosystems based on elliptic curves have become popular since the early 1990s.Template:Fact

While pure cryptanalysis uses weaknesses in the algorithms themselves, other attacks are based upon the implementation, known as side-channel attacks. If a cryptanalyst has access to, say, the amount of time the algorithm took to encrypt a number of plaintexts, he may be able to use a timing attack to break a cipher that is otherwise resistant to analysis. An attacker also might consider studying the pattern and length of messages to derive valuable information; this is known as traffic analysis.Template:Fact

[edit]

Cryptographic primitives

Template:Unsolved Much of the theoretical work in cryptography concerns cryptographic primitives — algorithms that have basic cryptographic properties — and their relationship to other cryptographic problems. For example, a one-way function is a function that is easy to compute but hard to invert. In order for any cryptographic application to be secure (if based on computational assumptions), one-way functions must exist. However, if one-way functions exist, it implies that P ǂ NP.<ref name="goldreichbook" /> Since the P versus NP problem is unsolved, we don't know if one-way functions exist. If they do, however, we can build other cryptographic tools from them. For instance, if one-way functions exist, then pseudorandom generators and pseudorandom functions exist.<ref>J. Hastad, R. Imagliazzo, L.A. Levin, and M. Luby, "A Pseudorandom Generator From Any One-Way Function", SIAM J. Computing, vol. 28 num. 4, pp 1364–1396, 1999.</ref>

Other cryptographic primitives include one-way permutations, trapdoor permutations, and oblivious transfer protocols.

[edit]

Cryptographic protocols

In some cases, cryptographic techniques involve back and forth communication among two or more parties. The term cryptographic protocol captures this general idea. Cryptographic protocols exist for a wide range of problems, including relatively simple ones like interactive proofs<ref>László Babai. "Trading group theory for randomness". Proceedings of the Seventeenth Annual Symposium on the Theory of Computing, ACM, 1985.</ref>, secret sharing<ref>G. Blakley. "Safeguarding cryptographic keys." In Proceedings of AFIPS 1979, volume 48, pp. 313-317, June 1979.</ref><ref>A. Shamir. "How to share a secret." In Communications of the ACM, volume 22, pp. 612-613, ACM, 1979.</ref>, and zero-knowledge<ref>S. Goldwasser, S. Micali, and C. Rackoff, "The Knowledge Complexity of Interactive Proof Systems", SIAM J. Computing, vol. 18, num. 1, pp. 186-208, 1989.</ref>, and much more complex ones like electronic cash<ref>S. Brands, "Untraceable Off-line Cash in Wallets with Observers", In Advances in Cryptology -- Proceedings of CRYPTO, Springer-Verlag, 1994.</ref> and secure multiparty computation<ref>R. Canetti, "Universally composable security: a new paradigm for cryptographic protocols", In Proceedings of the 42nd annual Symposium on the Foundations of Computer Science (FOCS), pp. 136-154, IEEE, 2001.</ref>.

When the security of a cryptographic system fails, it is rare that a weakness in the cryptographic primitives is the weakness which was exploited. Many cryptographic protocols are designed and analyzed using ad hoc methods. Weaknesses are often mistakes in the protocol design and analysis (usually due to the error-prone process), the implementation (a program bug), a failure of the assumptions needed for security, or some other human error. Methods for formally analyzing the security of protocols, based on techniques from mathematical logic (see for example BAN logic), and more recently from concrete security principles, have been the subject of research for the past few decades<ref>D. Dolev and A. Yao, "On the security of public key protocols", IEEE transactions on information theory, vol. 29 num. 2, pp. 198-208, IEEE, 1983.</ref><ref>M. Abadi and P. Rogaway, "Reconciling two views of cryptography (the computational soundness of formal encryption)." In IFIP International Conference on Theoretical Computer Science (IFIP TCS 2000), Springer-Verlag, 2000.</ref><ref>D. Song, "Athena, an automatic checker for security protocol analysis", In Proceedings of the 12th IEEE Computer Security Foundations Workshop (CSFW), IEEE, 1999.</ref>, but the tools available are still cumbersome and not yet widely used for complex designs.

The study of how best to implement and integrate cryptography for deployment in applications is a field in itself, see: cryptographic engineering and security engineering.

[edit]

Cryptography and Modern Society

Because of its potential to disrupt national intelligence-gathering and law enforcement, and because of its impact on privacy, there has been a history of controversial legal issues surrounding cryptography ever since the advent of computers, particularly in the United States.

One particularly important issue has been the export of cryptography and cryptographic software and hardware. Because of the importance of cryptanalysis in World War II, many western governments have strictly regulated the export of cryptography because of national security concerns. For instance, after World War II in the US, it was illegal to sell or freely distribute encryption technology overseas; in fact, encryption was classified as a munition.Template:Fact Until the advent of the personal computer and the internet, this was not especially problematic. However, as the internet grew, most standard encryption techniques became well-known globally, and these export restrictions became an impediment to research.

In the 1990s, several challenges were launched against export regulations of cryptography. Philip Zimmermann's Pretty Good Privacy encryption program was released in open source form and found its way onto the Internet in 1991.<ref name="levybook">Steven Levy, Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age, 2001, ISBN 0-670-85950-8</ref> Daniel Bernstein, a graduate student at UC Berkeley, brought a lawsuit against the government challenging the restrictions on free speech grounds in the 1995 case Bernstein v. United States. Cryptography exports from the US (and in much of the rest of the developed world) are less strictly regulated now than in the past, though encryption is still defined as a munition.Template:Fact See Export of cryptography for more details.

Another contentious issue in cryptography in the United States was the National Security Agency and its involvement in the high quality cipher development. The NSA was involved with the design of DES during its development and its consideration as a possible Federal Standard for cryptography.Template:Fact DES was built to be secure against differential cryptanalysis, a cryptanalytic technique that was known to NSA, and rediscovered by IBM researchers during DES development, but was not publicly known until the late 1980s<ref>E. Biham and A. Shamir, "Differential cryptanalysis of DES-like cryptosystems", Journal of Cryptology, vol. 4 num. 1, pp. 3-72, Springer-Verlag, 1991.</ref>. Another instance was the NSA's advocacy of the Clipper chip in 1993, an encryption microchip intended to be part of the Capstone cryptography-control initiative. Clipper was criticized for two reasons: the cipher was classified (the cipher, called Skipjack, was declassified in 1998 after the Clipper initiative failed). This led to concerns that the NSA had made the cipher weak on purpose in order to assist its intelligence efforts, and also to criticism of the initiative based on Kerchoff's law. Second, the chip included a special escrow key held by the government for use in wiretaps.<ref name="levybook" /> See Clipper chip for more information.

Cryptography is important in digital rights management (DRM), a technological way of enforcing copyrights. In 1998, Bill Clinton signed the Digital Millennium Copyright Act (DMCA), which criminalized the production and dissemination of certain cryptanalytic techniques and technology; specifically, those that could be used to circumvent DRM technology.Template:Fact This had a very serious potential impact on the cryptography community: after all, an argument could be made that virtually any cryptanalytic research violated the DMCA. The FBI has not enforced the DMCA as rigorously as had been feared by some, but nonetheless, this law remains a contentious issue in the cryptography community.

The Electronic Frontier Foundation is often involved in legal challenges relating to cryptography.

[edit]