Information AboutCryptology |
|
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 . 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 Algorithm s 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 Proof s and Secure Multiparty Computation . As the noted cryptologist Ron Rivest summarized: ''cryptography is about communication in the presence of adversaries.''Ronald Rivest, "Cryptography" From the ''Handbook of Theoretical Computer Science'', edited by J. van Leeuwen, Elsevier Science Publishers B.V., 1990 HISTORY OF CRYPTOGRAPHY AND CRYPTANALYSIS ''Main article'': History Of Cryptography may have been one of the earliest devices used to implement a cipher.]] 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 , Signature s, Interactive Proof s, 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 Cipher s, which rearrange the order of letters in a message, and Substitution Cipher s, 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 Diplomat s, 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. David Kahn , The Codebreakers , 1967, ISBN 0-684-83130--9. 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 Puzzle s (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. 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 should represent all the information unknown to the adversary. This is called Kerchoff's Law . , used by Germany in World War II , implemented a complex Cipher to protect sensitive communications.]] 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 and Codebreakers Helped Shape the Twentieth Century '', Washington, D.C., Brassey's, 2001, ISBN 1-57488-367-4. 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. Oded Goldreich , ''Foundations of Cryptography, Volume 1: Basic Tools", Cambridge University Press, 2001, ISBN 0-521-79172-3 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 Length s, and the potential effects of Quantum Computing are already being considered by good cryptographic system designers.A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography ISBN 0-849-38523-7. 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. 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. Whitfield Diffie and Martin Hellman , "New Directions in Cryptography", IEEE Transactions on Information Theory, vol. IT-22, Nov. 1976, pp: 644-654. -K. Modern computer-implemented ciphers can be a lot more complex than those performed by hand or electromechanical machines.]] The study of modern symmetric-key cryptography relates mainly to the study of . Bruce Schneier , ''Applied Cryptography'', 2nd edition, Wiley, 1996, ISBN 0471117099. 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. . Symmetric-key cryptography encompasses problems other than encryption, mainly those that can be accomplished with block ciphers. For instance:
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, , 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). In addition to encryption, public-key cryptography encompasses 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 VPN s, etc). 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. 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 and Warren Weaver, "The Mathematical Theory of Communication", University of Illinois Press, 1963, ISBN 0-252-72548-4. 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. 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 255 operations, to try approximately half of the possible keys. However, one attack against DES requires 250 known plaintexts and 250 operations to recover the secret key. 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. While pure cryptanalysis uses weaknesses in the algorithms themselves, other attacks are based upon the Implementation , known as '' Side-channel Attack s''. 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 . Cryptographic primitives 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 . 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.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. Other cryptographic primitives include One-way Permutation s, Trapdoor Permutation s, and Oblivious Transfer protocols. 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 ), pp. 136-154, IEEE, 2001.. 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 decadesD. 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.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.D. Song, "Athena, an automatic checker for security protocol analysis", In ''Proceedings of the 12th IEEE Computer Security Foundations Workshop (CSFW)'', IEEE, 1999., 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 . 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 . 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 , 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. See Export Of Cryptography for more details. Another contentious issue in cryptography in the United States was the , 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. See Clipper Chip for more information. Cryptography is important in 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. SEE ALSO
REFERENCES EXTERNAL LINKS
|