Better to know some
... than all
The Basics of Cryptography
Cryptography is the study of mathematical techniques related to aspects of information security such as confidentiality, data integrity, entity authentication, and data origin authentication. Cryptography is not the only means of providing information security, but rather one set of techniques.
Of all the information security objectives, the following four form a framework upon which the others will be derived:
(1) privacy or confidentiality.
(2) data integrity.
1. Confidentiality is a service used to keep the content of information from all but those authorized to have it. Secrecy is a term synonymous with confidentiality and privacy. There are numerous approaches to providing confidentiality, ranging from physical protection to mathematical algorithms which render data unintelligible.
2. Data integrity is a service which addresses the unauthorized alteration of data. To assure data integrity, one must have the ability to detect data manipulation by unauthorized parties. Data manipulation includes such things as insertion, deletion, and substitution.
3. Authentication is a service related to identification. This function applies to both entities and information itself. Two parties entering into a communication should identify each other. Information delivered over a channel should be authenticated as to origin, date of origin, data content, time sent, etc. For these reasons this aspect of cryptography is usually subdivided into two major classes: entity authentication and data origin authentication. Data origin authentication implicitly provides data integrity.
4. Non-repudiation is a service which prevents an entity from denying previous commitments or actions. When disputes arise due to an entity denying that certain actions were taken, a means to resolve the situation is necessary. For example, one entity may authorize the purchase of property by another entity and later deny such authorization was granted. A procedure involving a trusted third party is needed to resolve the dispute.
A fundamental goal of cryptography is to adequately address these four areas in both theory and practice. Cryptography is about the prevention and detection of cheating and other malicious activities.
The number of basic cryptographic tools (primitives) used to provide information security These primitives should be evaluated with respect to various criteria such as:
1. Level of security. This is usually difficult to quantify. Often it is given in terms of the number of operations required (using the best methods currently known) to defeat the intended objective. Typically the level of security is defined by an upper bound on the amount of work necessary to defeat the objective. This is sometimes called the work factor.
2. Functionality. Primitives will need to be combined to meet various information security objectives. Which primitives are most effective for a given objective will be determined by the basic properties of the primitives.
3. Methods of Operation. Primitives, when applied in various ways and with various inputs, will typically exhibit different characteristics; thus, one primitive could provide very different functionality depending on its mode of operation or usage.
4. Performance. This refers to the efficiency of a primitive in a particular mode of operation.
5. Ease of Implementation. This refers to the difficulty of realizing the primitive in a practical instantiation. This might include the complexity of implementing the primitive in either a software or hardware environment.
The relative importance of various criteria is very much dependent on the application and resources available. For example, in an environment where computing power is limited one may have to trade off a very high level of security for better performance of the system as a whole.
Cryptography, over the ages, has been an art practiced by many who have devised ad hoc techniques to meet some of the information security requirements. The last twenty years have been a period of transition as the discipline moved from an art to a science. There are now several international scientific conferences devoted exclusively to cryptography and also an international scientific organization, the International Association for Cryptologic Research (IACR), aimed at fostering research in the area.
Basic terminology and concepts
The scientific study of any discipline must be built upon rigorous definitions arising from fundamental concepts. What follows is a list of terms and basic concepts used throughout this book. Where appropriate, rigor has been sacrificed for the sake of clarity.
Encryption domains and codomains
* A denotes a finite set called the alphabet of definition.
* M denotes a set called the message space. M consists of strings of symbols from an alphabet of definition. An element of M is called a plaintext message or simply a plaintext.
* C denotes a set called the ciphertext space. C consists of strings of symbols from an alphabet of definition, which may differ from the alphabet of definition for M. An element of C is called a ciphertext.
Encryption and decryption transformations
* K denotes a set called the key space. An element of K is called a key.
* Each element e 2 K uniquely determines a bijection fromMto C, denoted by Ee. Ee is called an encryption function or an encryption transformation. Note that Ee must be a bijection if the process is to be reversed and a unique plaintext message recovered for each distinct ciphertext.1
* For each d 2 K, Dd denotes a bijection from C toM(i.e., Dd : C ?!M). Dd is called a decryption function or decryption transformation.
* The process of applying the transformation Ee to a message m 2 Mis usually referred to as encrypting m or the encryption of m.
* The process of applying the transformationDd to a ciphertext c is usually referred to as decrypting c or the decryption of c. 1More generality is obtained if Ee is simply defined as a 1 ? 1 transformation fromMto C. That is to say, Ee is a bijection fromMto Im(Ee) where Im(Ee) is a subset of C.
* An encryption scheme consists of a set fEe : e 2 Kg of encryption transformations and a corresponding set fDd : d 2 Kg of decryption transformations with the property that for each e 2 K there is a unique key d 2 K such that Dd = E?1 e ; that is, Dd(Ee(m)) = m for all m 2 M. An encryption scheme is sometimes referred to as a cipher.
* The keys e and d in the preceding definition are referred to as a key pair and sometimes denoted by (e; d). Note that e and d could be the same.
* To construct an encryption scheme requires one to select a message spaceM, a ciphertext space C, a key space K, a set of encryption transformations fEe : e 2 Kg, and a corresponding set of decryption transformations fDd : d 2 Kg.
An encryption scheme may be used as follows for the purpose of achieving confidentiality. Two parties Alice and Bob first secretly choose or secretly exchange a key pair (e; d). At a subsequent point in time, if Alice wishes to send a message m2Mto Bob, she computes c = Ee(m) and transmits this to Bob. Upon receiving c, Bob computes Dd(c) = m and hence recovers the original message m.
The question arises as to why keys are necessary. (Why not just choose one encryption function and its corresponding decryption function?) Having transformations which are very similar but characterized by keys means that if some particular encryption/decryption transformation is revealed then one does not have to redesign the entire scheme but simply change the key. It is sound cryptographic practice to change the key (encryption/decryption transformation) frequently. As a physical analogue, consider an ordinary resettable combination lock. The structure of the lock is available to anyonewho wishes to purchase one but the combination is chosen and set by the owner. If the owner suspects that the combination has been revealed he can easily reset it without replacing the physical mechanism.
* An entity or party is someone or something which sends, receives, or manipulates information. Alice and Bob are entities. An entity may be a person, a computer terminal, etc.
* A sender is an entity in a two-party communicationwhich is the legitimate transmitter of information. The sender is Alice.
* A receiver is an entity in a two-party communication which is the intended recipient of information. The receiver is Bob.
* An adversary is an entity in a two-party communication which is neither the sender nor receiver, andwhich tries to defeat the information security service being provided between the sender and receiver. Various other names are synonymous with adversary such as enemy, attacker, opponent, tapper, eavesdropper, intruder, and interloper. An adversary will often attempt to play the role of either the legitimate sender or the legitimate receiver.
* A channel is a means of conveying information from one entity to another.
* A physically secure channel or secure channel is one which is not physically accessible to the adversary.
* An unsecured channel is one from which parties other than those for which the information is intended can reorder, delete, insert, or read.
* A secured channel is one fromwhich an adversary does not have the ability to reorder, delete, insert, or read.
One should note the subtle difference between a physically secure channel and a secured channel - a secured channelmay be secured by physical or cryptographic techniques, the latter being the topic of this book. Certain channels are assumed to be physically secure. These include trusted couriers, personal contact between communicating parties, and a dedicated communication link, to name a few.
A fundamental premise in cryptography is that the setsM; C;K; fEe : e 2 Kg, fDd : d 2 Kg are public knowledge. When two parties wish to communicate securely using an encryption scheme, the only thing that they keep secret is the particular key pair (e; d) which they are using, and which they must select. One can gain additional security by keeping the class of encryption and decryption transformations secret but one should not base the security of the entire scheme on this approach. History has shown that maintaining the secrecy of the transformations is very difficult indeed.
An encryption scheme is said to be breakable if a third party, without prior knowledge of the key pair (e; d), can systematically recover plaintext from corresponding ciphertext within some appropriate time frame.
An appropriate time frame will be a function of the useful lifespan of the data being protected. For example, an instruction to buy a certain stockmay only need to be kept secret for a few minutes whereas state secrets may need to remain confidential indefinitely.
An encryption scheme can be broken by trying all possible keys to see which one the communicating parties are using (assuming that the class of encryption functions is public knowledge). This is called an exhaustive search of the key space. It follows then that the number of keys (i.e., the size of the key space) should be large enough to make this approach computationally infeasible. It is the objective of a designer of an encryption scheme that this be the best approach to break the system.
Frequently cited in the literature are Kerckhoffs' desiderata, a set of requirements for cipher systems. They are given here essentially as Kerckhoffs originally stated them:
1. The system should be, if not theoretically unbreakable, unbreakable in practice.
2. Compromise of the system details should not inconvenience the correspondents.
3. The key should be rememberable without notes and easily changed.
4. The cryptogram should be transmissible by telegraph.
5. The encryption apparatus should be portable and operable by a single person.
6. The system should be easy, requiring neither the knowledge of a long list of rules nor mental strain.
This list of requirements was articulated in 1883 and, for the most part, remains useful today. Point 2 allows that the class of encryption transformations being used be publicly known and that the security of the system should reside only in the key chosen.
* Cryptanalysis is the study of mathematical techniques for attempting to defeat cryptographic techniques, and, more generally, information security services.
* A cryptanalyst is someone who engages in cryptanalysis.
* Cryptology is the study of cryptography and cryptanalysis.
* A cryptosystem is a general term referring to a set of cryptographic primitives used to provide information security services. Most often the term is used in conjunction with primitives providing confidentiality, i.e., encryption.
Cryptographic techniques are typically divided into two generic types: symmetric-key and public-key.