Trang 1
S UTV>?JWDXE YZJ1J>? [ \M "!"#%$&$(')$(*U>^]`__aE+-,.,"/10123!547698&,":$(;(6< ,.=&8?>A@BDCFEHGIKJLK>NMOEQPRJ b(c1ZJU7J>&UKedfd3dhgUifjfikhg1lOjm3nhg1ofdOjmfpfkOqfr3rsgUifjRtnOj3i [ uM@ARf UK wvUJKWx7yyVz{Jv| AKTK}T~ O7J ~KyKTUJTwPKUQJ? M.K7UJ-^vQJW{UPHK>O J
JAKUJQyc KE O7JW R J`3KJWDD@JWZUJ vyFTK B|f^TVQ ^WJ vc y yTV Q @A3f>AKUJ5TK`Jv3TKQ BOJvIw URWTK B>7fJvKyKTQJT-T KPRyQ@ycTKJvT K{w KJ AKUJyUPRy^@BcU KUsz{c Uh AKU~UQJJ7z{UJv~Q [ MUKUE &OTKK <z{KUPHK1VUWWQ [ \M UKZ yK%KJ@BU OTK}T- O7J5@APH>1JhKyKTUJThPKUQJ WWTK BOvxJT FK@O3J@BJB7KQJ>hKyKTUJT7TVJTKy>hJQJBD F7B@AZK 3WcTKW&UJU~KWJQJBDQuTKycWJv RT BNJv>7TKU}y~Jv> JAKU~UQJJ7z{UJv~QWKTW JvQ>%@B5JBJQ7J1UvePRys1BO7>?z{ { c@yUKUE c~ U 7TJJQ [ Q~`J>NQTK`JvJz¡zef>N^yKEhX AKT}Te O7UJxc1{@OM {WR
J~3KJWx-T BNJvD
vJKUysW@cJ> @<JKWDJ7z{UJv~Q [ \M UKZUcTVT BNJvE ¢T ]__Q£@B [^ ¤M >¥¦JTE ThiNganHang.com
Trang 2
Chapter Overview of Cryptography Contents in Brief §?§N§?§?§?§&§?§?§?§&§?§?§&§?§?§?§&§?§?§?§N§?§?§&§?§?§?§&§ 1.1 Introduction §?§?§&§?§?§&§?§?§?§&§?§?§?§N§?§?§&§?§?§?§&§§?§&§?§?§?§N§?§?§&§?§?§?§&§ 1 1.2 Information security and cryptography 2 1.3 Background on functions §?§&§?§?§&§?§?§?§&§?§?§?§N§?§?§&§?§?§?§&§§?§?§&§?§?§?§&§?§?§?§N§?§?§&§?§?§?§&§ 6 1.4 Basic terminology and concepts 11 1.5 Symmetric-key encryption§?§?§&§?§?§?§&§?§?§&§?§?§?§&§?§?§?§N§?§?§&§?§?§?§&§§?§&§?§?§?§&§?§?§?§N§?§?§&§?§?§?§&§ 15 1.6 Digital signatures 22 1.7 Authentication and identification§?§?§?§&§?§?§?§&§?§?§&§?§?§?§&§?§?§?§N§?§?§&§?§?§?§&§§?§?§&§?§?§&§?§?§?§&§?§?§?§N§?§?§&§?§?§?§&§ 24 1.8 Public-key cryptography 25 1.9 Hash functions §?§&§?§?§&§?§?§?§&§?§?§?§N§?§?§&§?§?§?§&§§N§?§?§&§?§?§?§&§ 33 1.10 Protocols and mechanisms 33 1.11 Key establishment, management, and certification§?§?§&§?§?§?§N§?§?§&§?§?§?§&§§?§&§?§?§?§N§?§?§&§?§?§?§&§ 35 1.12 Pseudorandom numbers and sequences 39 1.13 Classes of attacks and security models§&§?§?§&§?§?§?§&§?§?§?§N§?§?§&§?§?§?§&§ 41 1.14 Notes and further references 45 1.1 Introduction Cryptography has a long and fascinating history. The most complete non-technical account of the subject is Kahn’s The Codebreakers. This book traces cryptography from its initial and limited use by the Egyptians some 4000 years ago, to the twentieth century where it played a crucial role in the outcome of both world wars. Completed in 1963, Kahn’s book covers those aspects of the history which were most significant (up to that time) to the devel- opment of the subject. The predominant practitioners of the art were those associated with the military, the diplomatic service and government in general. Cryptography was used as a tool to protect national secrets and strategies. The proliferation of computers and communications systems in the 1960s brought with it a demand from the private sector for means to protect information in digital form and to provide security services. Beginning with the work of Feistel at IBM in the early 1970s and culminating in 1977 with the adoption as a U.S. Federal Information Processing Standard for encrypting unclassified information, DES, the Data Encryption Standard, is the most well-known cryptographic mechanism in history. It remains the standard means for secur- ing electronic commerce for many financial institutions around the world. The most striking development in the history of cryptography came in 1976 when Diffie and Hellman publishedNew Directions in Cryptography. This paper introduced the revolu- tionary concept of public-key cryptography and also provided a new and ingenious method 1 ThiNganHang.com
Trang 3
2 Ch. 1 Overview of Cryptography for key exchange, the security of which is based on the intractability of the discrete loga- rithm problem. Although the authors had no practical realization of a public-key encryp- tion scheme at the time, the idea was clear and it generated extensive interest and activity in the cryptographic community. In 1978 Rivest, Shamir, and Adleman discovered the first practical public-key encryption and signature scheme, now referred to as RSA. The RSA scheme is based on another hard mathematical problem, the intractability of factoring large integers. This application of a hard mathematical problem to cryptography revitalized ef- forts to find more efficient methods to factor. The 1980s saw major advances in this area but none which rendered the RSA system insecure. Another class of powerful and practical public-key schemes was found by ElGamal in 1985. These are also based on the discrete logarithm problem. One of the most significant contributions provided by public-key cryptography is the digital signature. In 1991 the first international standard for digital signatures (ISO/IEC 9796) was adopted. It is based on the RSA public-key scheme. In 1994 the U.S. Govern- ment adopted the Digital Signature Standard, a mechanism based on the ElGamal public- key scheme. The search for new public-key schemes, improvements to existing cryptographic mec- hanisms, and proofs of security continues at a rapid pace. Various standards and infrastruc- tures involving cryptography are being put in place. Security products are being developed to address the security needs of an information intensive society. The purpose of this book is to give an up-to-date treatise of the principles, techniques, and algorithms of interest in cryptographic practice. Emphasis has been placed on those aspects which are most practical and applied. The reader will be made aware of the basic issues and pointed to specific related research in the literature where more indepth discus- sions can be found. Due to the volume of material which is covered, most results will be stated without proofs. This also serves the purpose of not obscuring the very applied nature of the subject. This book is intended for both implementers and researchers. It describes algorithms, systems, and their interactions. Chapter 1 is a tutorial on the many and various aspects of cryptography. It does not attempt to convey all of the details and subtleties inherent to the subject. Its purpose is to introduce the basic issues and principles and to point the reader to appropriate chapters in the book for more comprehensive treatments. Specific techniques are avoided in this chapter. 1.2 Information security and cryptography The concept of information will be taken to be an understood quantity. To introduce cryp- tography, an understanding of issues related to information security in general is necessary. Information security manifests itself in many ways according to the situation and require- ment. Regardless of who is involved, to one degree or another, all parties to a transaction must have confidence that certain objectives associated with information security have been met. Some of these objectives are listed in Table 1.1. Over the centuries, an elaborate set of protocols and mechanisms has been created to deal with information security issues when the information is conveyed by physical doc- uments. Often the objectives of information security cannot solely be achieved through mathematical algorithms and protocols alone, but require procedural techniques and abid- ance of laws to achieve the desired result. For example, privacy of letters is provided by sealed envelopes delivered by an accepted mail service. The physical security of the en- velope is, for practical necessity, limited and so laws are enacted which make it a criminal¨ c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter. ThiNganHang.com
Trang 4
© 1.2 Information security and cryptography 3 privacy keeping information secret from all but those who are autho- or confidentiality rized to see it. data integrity ensuring information has not been altered by unauthorized or unknown means. entity authentication corroboration of the identity of an entity (e.g., a person, a or identification computer terminal, a credit card, etc.). message corroborating the source of information; also known as data authentication origin authentication. signature a means to bind information to an entity. authorization conveyance, to another entity, of official sanction to do or be something. validation a means to provide timeliness of authorization to use or ma- nipulate information or resources. access control restricting access to resources to privileged entities. certification endorsement of information by a trusted entity. timestamping recording the time of creation or existence of information. witnessing verifying the creation or existence of information by an entity other than the creator. receipt acknowledgement that information has been received. confirmation acknowledgement that services have been provided. ownership a means to provide an entity with the legal right to use or transfer a resource to others. anonymity concealing the identity of an entity involved in some process. non-repudiation preventing the denial of previous commitments or actions. revocation retraction of certification or authorization. Table 1.1: Some information security objectives. offense to open mail for which one is not authorized. It is sometimes the case that security is achieved not through the information itself but through the physical document recording it. For example, paper currency requires special inks and material to prevent counterfeiting. Conceptually, the way information is recorded has not changed dramatically over time. Whereas information was typically stored and transmitted on paper, much of it now re- sides on magnetic media and is transmitted via telecommunications systems, some wire- less. What has changed dramatically is the ability to copy and alter information. One can make thousands of identical copies of a piece of information stored electronically and each is indistinguishable from the original. With information on paper, this is much more diffi- cult. What is needed then for a society where information is mostly stored and transmitted in electronic form is a means to ensure information security which is independent of the physical medium recording or conveying it and such that the objectives of information se- curity rely solely on digital information itself. One of the fundamental tools used in information security is the signature. It is a build- ing block for many other services such as non-repudiation, data origin authentication, iden- tification, and witnessing, to mention a few. Having learned the basics in writing, an indi- vidual is taught how to produce a handwritten signature for the purpose of identification. At contract age the signature evolves to take on a very integral part of the person’s identity. This signature is intended to be unique to the individual and serve as a means to identify, authorize, and validate. With electronic information the concept of a signature needs to be Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone. ThiNganHang.com
Trang 5
4 Ch. 1 Overview of Cryptography redressed; it cannot simply be something unique to the signer and independent of the in- formation signed. Electronic replication of it is so simple that appending a signature to a document not signed by the originator of the signature is almost a triviality. Analogues of the “paper protocols” currently in use are required. Hopefully these new electronic based protocols are at least as good as those they replace. There is a unique op- portunity for society to introduce new and more efficient ways of ensuring information se- curity. Much can be learned from the evolution of the paper based system, mimicking those aspects which have served us well and removing the inefficiencies. Achieving information security in an electronic society requires a vast array of techni- cal and legal skills. There is, however, no guarantee that all of the information security ob- jectives deemed necessary can be adequately met. The technical means is provided through cryptography. 1.1 Definition Cryptography is the study of mathematical techniques related to aspects of in- formation security such as confidentiality, data integrity, entity authentication, and data ori- gin authentication. Cryptography is not the only means of providing information security, but rather one set of techniques. Cryptographic goals framework upon which the others will be derived: (1) privacy or confidentiality (Of all the information security objectives listed in Table 1.1, the following four form aª ª ª ª1.5, ª1.8); (2) data integrity ( 1.9); (3) authentication ( 1.7); and (4) non-repudiation ( 1.6). 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 unau- thorized parties. Data manipulation includes such things as insertion, deletion, and substitution. 3. Authenticationis a service related to identification. This function applies to both enti- ties 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 cryptog- raphy is usually subdivided into two major classes: entity authentication and data origin authentication. Data origin authentication implicitly provides data integrity (for if a message is modified, the source has changed). 4. Non-repudiationis a service which prevents an entity from denying previous commit- ments 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 autho- rization 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. information security. Examples of primitives include encryption schemes (This book describes a number of basic cryptographic tools (primitives) used to provideª1.5 and ª1.8), ¨ c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter. ThiNganHang.com
Trang 6
© 1.2 Information security and cryptography 5 hash functions (ª1.9), and digital signature schemes (ª1.6). Figure 1.1 provides a schematic listing of the primitives considered and how they relate. Many of these will be briefly intro- duced in this chapter, with detailed discussion left to later chapters. These primitives should Arbitrary length hash functions Unkeyed One-way permutations Primitives Random sequences Block ciphers Symmetric-key ciphers Stream Arbitrary length ciphers hash functions (MACs) Security Symmetric-key Primitives Primitives Signatures Pseudorandom sequences Identification primitives Public-key ciphers Public-key Signatures Primitives Identification primitives Figure 1.1: A taxonomy of cryptographic primitives. 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 thework factor (see ª1.13.4). 2. functionality. Primitives will need to be combined to meet various information se- curity 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 in- puts, will typically exhibit different characteristics; thus, one primitive could provide Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone. ThiNganHang.com
Trang 7
6 Ch. 1 Overview of Cryptography 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 op- eration. (For example, an encryption algorithm may be rated by the number of bits per second which it can encrypt.) 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 prim- itive 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 practised 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 Crypto- logic Research (IACR), aimed at fostering research in the area. This book is about cryptography: the theory, the practice, and the standards. 1.3 Background on functions While this book is not a treatise on abstract mathematics, a familiarity with basic mathe- matical concepts will prove to be useful. One concept which is absolutely fundamental to cryptography is that of a function in the mathematical sense. A function is alternately re- ferred to as a mapping or a transformation. 1.3.1 Functions (1-1, one-way, trapdoor one-way) « Amight consist of the elementsset consists of distinct objects which are called¬ , , ®, and this is denotedelements«¤¯°±¬²²®³of the set. For example, a set. 1.2 Definition« A function is defined by two sets´ « and« ´ and a rule μ which assigns to each element inand ´ the codomain´ precisely one element in. If ¶ is an element ofμ . The set« (usually written¶ is called the¸ ¶·h«¶ domain) the imageof the function¸F¯μ¹º¶of ¶ is the» Standard notation for a functionelement in ¸ which the rule¶·«associates withμ from set « μ¹º¶R»A¯~¸to set; the image´ is μO¼«¾½f¿´of is denoted by. If ¸7·x´´, then a. preimagehave at least one preimage is called theof is an element for whichimage of μ , denoted. The set of all elements inÀÁ¹Âμ». which 1.3 Example« ´(function) Consider the setsμ¹Â¬K»¯Ç μ¹Ê¦»¯É«Ã¯Ä°±¬²²U®³μ¹Â®¦»"¯Æ, ´Ä¯Å°VÆK²Ç²È²ÉK³ , and the rule μ fromthe sets°VƲDzÉK³«to, ´ defined asand the function μ . The preimage of the element, , . Figure 1.2 shows a schematic ofÇ is ¬ . The image of μ Ëis . gramThinking of a function in terms of the schematic (sometimes called a) given in Figure 1.2, each element in the domain´ « has precisely one arrowed linefunctional dia- originating from it. Each element in the codomain can have any number of arrowed lines incident to it (including zero lines).¨ c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter. ThiNganHang.com
Trang 8
© 1.3 Background on functions 7 Ï Î 1 Ñ Í 2 Ð Ì 3 4 Ò Ó Ô Figure 1.2: A function from a set of three elements to a set of four elements. Often only the domainμ « and the rule μ are given and the codomain is assumed to be the image of . This point is illustrated with two examples. 1.4 Exampleμ¹º¶R»H¯×Ø (function×Ø) Take«\¯I°±Æ²ÇK²ÈK²ÕÕUÕ²Æ`Ö³¶QÙ and let μ be the rule that for eachÆÆ ¶ ·h« , , whereμ¹Æ»H¯|ÆÚμ¹Ç»H¯DÉis the remainder whenμ¹ÂÈ`»H¯DÛis divided byμ¹ÂÉ`»H¯|Ü . Explicitly thenμ¹Ü»H¯DÈ μ¹Ý»H¯|ÈÚμ¹Þ»H¯DÜ μ¹Âß`»H¯DÛ μ¹ÂÛ`»H¯|É μ¹Æ`Ö»¯|ÆKÕ The image of μ is the set ´I¯°VÆK²ÈK²É²Ü²ÛK³ . Ë 1.5 Example× Ø (function) Take¶Ù«\¯I°±Æ²Ç²ÈK²ÕUÕÕQ²Æ`ÖUàÂáK³ÆÖàÊá"âxÆ and let ¶-·μ be the rule« μ¹º¶ »(¯~× Ø , where to write downis the remainder whenμ explicitly as in Example 1.4, but nonetheless the function is completelyis divided by for all . Here it is not feasibleμ Ë specified by the domain and the mathematical description of the rule . (i) 1-1 functions Æ½Æ 1.6 Definitioncodomain ´ A function (or transformation) isis the image of at most one element in the domain(one-to-one)« . if each element in the 1.7 Definition A function (or transformation) is ãÊäæåã if each element in the codomainμN¼<«¾½f¿ç´´ is the image of at least one element in the domain. Equivalently, a functiononto if ÀÁ^¹Êμ»H¯´ . is 1.8 Definition If a function μN¼«è½f¿é´ is Æ3½ZÆ and ÀÁ¹Âμ»H¯I´ , then μ is called a bijection. 1.9 FactμO¼« If½æ¿é´μN¼æ« Æ"½~ƽf¿ ´ is «ÆZ½Æ then´ μA¼æ« ½f¿ ÀÁ¹Âμ» is a bijection. In particular, ifμ is , and and are finite sets of the same size, thenμ is a bijection.´ In terms of the schematic representation, if is a bijection, then each element in has exactly one arrowed line incident with it. The functions described in Examples 1.3 and1.4 are not bijections. In Example 1.3 the element È is not the image of any element in the domain. In Example 1.4 each element in the codomain has two preimages. 1.10 Definition´ « If μ is a bijection from¸
·{´« to ´ then it is a simple matter to define a bijection깺¸æ»H¯¶ ¶·« μ¹¶R»H¯¸ ê fromfunctiontoê obtained fromas follows: for eachμ is called the defineinverse functionwhereof μ and is denoted byand êZ¯|μ3ë3ì. This. Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone. ThiNganHang.com
Trang 9
8 Ch. 1 Overview of Cryptography Ï ï Î Î Í 1 1 Í Ñ Ì 2 Ð Ð 2 Ì Ñ í 3 3 í î 4 4 î 5 5 Ò ðñÒ<òó Figure 1.3: A bijection and its inverse . 1.11 Exampleμ (inverse function) Let «\¯°±¬²²U®²ôK²õV³ , andμ ´I¯°±Æ²Ç²ÈK²ÉK²ÜK³ , and considerê the ruleformed simply by reversing the arrows on the edges. The domain of« given by the arrowed edges in Figure 1.3. is a bijection and its inverseê is ´ and the codomainËis is . μ μ3ëfì Note that if is a bijection, then so is . In cryptography bijections are used as the tool for encrypting messages and the inverse transformations are used to decrypt. Thiswill be made clearer in ª1.4 when some basic terminology is introduced. Notice that if the transformations were not bijections then it would not be possible to always decrypt to a unique message. (ii) One-way functions There are certain types of functions which play significant roles in cryptography. At the expense of rigor, an intuitive definition of a one-way function is given. 1.12 Definition A function μ ¶-·{«from a set « to a set ´ is called a one-way function¸·ÀÁ¹Êμ» if μ¹º¶ » is “easy” to compute for allputationally infeasible” to find anybut for “essentially all” elements¶ ·h« such that μ¹º¶ »H¯~¸ . it is “com- 1.13 Note (clarification of terms in Definition 1.12) (i) A rigorous definition of the terms “easy” and “computationally infeasible” is neces- sary but would detract from the simple idea that is being conveyed. For the purpose (ii) The phrase “for essentially all elements inof this chapter, the intuitive meaning will suffice.¸e·´ ¶·«´ ” refers to the fact that there are a few¸e¯μ¹¶R» valuesone may computefor which it is easy to find an¸~¯öμ¹¶R» for a small number ofsuch that¶ values and then for these, the. For example, one-way function is the following: for a randominverse is known by table look-up. An alternate way to describe this property of a¶ ·Z« μ¹º¶R»A¯7¸ ¸·ÀÁ¹Âμ» it is computationally infeasible to find any such that . The concept of a one-way function is illustrated through the following examples. 1.14 Example¶ ·h« (one-way function×VØ ) Take «÷¯ø°VÆK²Ç²È²UÕÕÕQ²ÆÝK³È Ø ÆÞ and define μ¹¶R» ¯×Ø for all ¶ whereÆùÇ is the remainder whenÈ ÉÚÜ Ý Þ is divided byß ÛùÆÖÃÆÆÚÆ`ÇùÆ`ÈùÆÉÃÆÜùÆ`Ý. Explicitly, μ¹º¶ » ÈùÛÚÆÖÃÆÈùÜÃÆÜùÆ`ÆùÆ`ÝùÆ`É ß Þ ÉÚÆ`Ç Ç Ý Æ Given a number between Æ andÞ Æ`Ý , it is relatively easy to find the image of it under μ . How- ever, given a number such as¨ , without having the table in front of you, it is harder to find c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter. ThiNganHang.com
Trang 10
© 1.3 Background on functions 9 ¶ given that μ¹º¶ »H¯|Þ . Of course, if the number you are given is È then it is clear that¶w¯ÆË is what you need; but for most of the elements in the codomain it is not that easy. important point here is that there is a difference in the amount of work to computeOne must keep in mind that this is an example which uses very small numbers; the¶ μ¹º¶R» μ¹º¶R» μ¹º¶ » and the amount of work to find given . Even for very large numbers, can be computed efficiently using the repeated square-and-multiply algorithm (Algorithm 2.143),whereas the process of finding ¶ from μ¹º¶ » is much harder. 1.15 Exampleä¯üúQû¯éÇÝ`ÇÉ`Ý`ÜÈ`ÞÇ`Èonly positive integer divisors are 1 and itself. Select primes(one-way function) A prime number«ý¯ °±Æ²Ç²ÈK²ÕUÕÕQ²ä½Æ³is a positive integer greater than 1 whoseú
¯Éß`ÝÆ`Æ , û¯Ü`ÈÛ`ÛÈμ , form« by μ¹º¶ »¯×μ¹Ç`Éß`ÛÛ`Û`Æ»A¯)Æ`Û`ßÆ`ÈÛ`É`ÇÆ`ÉØ for each ¶·«, and let, where × Ø is the remainder whenÇ`É`ßÛ`ÛÛ`Æþ¯)Üß`ßÆ`Û`ÉÛ`ßÜ`ÛNÿäwâ-ÆÛ`ß`ÆÈ`ÛÉ`Ç`ÆÉ. Define a function¶þ is divided by ä on. For instance,Computing μ¹¶R» is a relatively simple thing to do, but to reverse the procedure is much moresince ¶ . difficult; that is, given a remainder to find the value which was originally cubed (raised with modulusto the third power). This procedure is referred to as the computation of a modular cube rootä . If the factors ofú û ä ä are unknown and large, this is a difficult problem; how- ever, if the factorsmodular cube roots. (Seeand ªof8.2.2(i) for details.)are known then there is an efficient algorithm for computingË Example 1.15 leads one to consider another type of function which will prove to be fundamental in later developments. (iii) Trapdoor one-way functions μA¼f« ½æ¿ ´ 1.16 Definition A trapdoor one-way function is a one-way function with the additional property that given some extra information (called thebecomes feasible to find for any given ¸·{ÀÁ¹Êμ», an ¶ ·Z« such thattrapdoor informationμ¹º¶ »(¯7¸ . ) it tional information of the factors ofExample 1.15 illustrates the concept of a trapdoor one-way function. With the addi-ä¯IÇ`ÝÇ`ÉÝ`Ü`ÈÞ`ÇÈ (namely, úZ¯IÉ`ßÝ`ÆÆ and û¯IÜ`È`ÛÛ`È , each of which is five decimal digits long) it becomes much easier to invert the function.The factors of Ç`ÝÇ`É`ÝÜ`ÈÞ`Ç`È are large enough that finding them by hand computation would be difficult. Of course, any reasonable computer program could find the factors relativelyquickly. If, on the other hand, one selects ú and û to be very large distinct prime numbers even with the most powerful computers, to deduce(each having about 100 decimal digits) then, by today’s standards, it is a difficult problem,ª ú and û simply fromä . This is the well- known integer factorization problem (see 3.2) and a source of many trapdoor one-way functions. It remains to be rigorously established whether there actually are any (true) one-way functions. That is to say, no one has yet definitively proved the existence of such func- tions under reasonable (and rigorous) definitions of “easy” and “computationally infeasi- ble”. Since the existence of one-way functions is still unknown, the existence of trapdoor one-way functions is also unknown. However, there are a number of good candidates for one-way and trapdoor one-way functions. Many of these are discussed in this book, with emphasis given to those which are practical. (discussed inOne-way and trapdoor one-way functions are the basis for public-key cryptographyª1.8). The importance of these concepts will become clearer when their appli- cation to cryptographic techniques is considered. It will be worthwhile to keep the abstract concepts of this section in mind as concrete methods are presented. Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone. ThiNganHang.com
Trang 11
10 Ch. 1 Overview of Cryptography 1.3.2 Permutations Permutations are functions which are often used in various cryptographic constructs. 1.17 Definition Let be a finite set of elements. AúO¼ x½f¿ permutation ú on is a bijection (Defini- tion 1.8) from to itself (i.e., ). 1.18 Example (permutation) Let x¯°VÆK²ÇK²È²É²ÜK³ . A permutation úA¼|½f¿ is defined as follows: úQ¹Æ`»¯È² úQ¹Ç`»¯Ü² úQ¹È`»H¯|ɲ úQ¹É`»H¯|Dz úQ¹Ü`»H¯|ÆÕ A permutation can be described in various ways. It can be displayed as above or as an array:ÆÚÇÃÈÚÉùÜ úh¯ ÈÚÜÃÉÚÇùÆ ² (1.1) mappingwhere the top row in the array is the domain and the bottom row is the image under theú . Of course, other representations are possible. Ë Since permutations are bijections, they have inverses. If a permutation is written as an array (see 1.1), its inverse is easily found by interchanging the rows in the array and reorder- ing the elements in the new top row if desired (the bottom row would have to be reorderedú ú ë3ì ¯ ÆùÇÚÈÃÉÚÜÜùÉÚÆÃÈÚÇ Õ correspondingly). The inverse of in Example 1.18 is 1.19 Example (permutation) Let « be the set of integersú û °±Ö²ÆK²ÇK²ÕÕUÕ²úQûN½7Ƴ where ú and û suppose that neitherare distinct large primes (for example,úH½Æ¶ þ nor û<½Æ is divisible by 3. Then the functionúQûand are each about 100 decimal digits long), andúQ¹º¶ »H¯~× Ø , where× Ø is the remainder whenthe inverse permutation is computationally infeasible by today’s standards unlessis divided by , can be shown to be a permutation. Determiningú andËû are known (cf. Example 1.15). 1.3.3 Involutions ª Another type of function which will be referred to in 1.5.3 is an involution. Involutions have the property that they are their own inverses. 1.20 Definition Letμ be a finite set and let μμI¯èμbe a bijection fromë3ì to (i.e., μN¼½æ¿ ). The functionμ¹Âμ¹º¶ »»(¯~¶ for allis called an¶ · . involution if . An equivalent way of stating this is 1.21 Exampleinvolution, note that if(involution) Figure 1.4 is an example of an involution. In the diagram of an is the image of then is the image of . Ë ¨ c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter. ThiNganHang.com
Trang 12
© 1.4 Basic terminology and concepts 11 1 1 2 2 3 3 4 4 5 5 Figure 1.4: An involution on a set of 5 elements. 1.4 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 (here in Chapter 1) for the sake of clarity. Encryption domains and codomains ¯°±Ö²ÆK³ denotes a finite set called the alphabet of definition. For example, , the binary alphabetcan be encoded in terms of the binary alphabet. For example, since there are, is a frequently used alphabet of definition. Note that any alphabetÈÇ binary strings of length five, each letter of the English alphabet can be assigned a unique binary string of length five. denotes a set called the message space. consists of strings of symbols from an alphabet of definition. An element of is called a plaintext message or simply a plaintext. For example, may consist of binary strings, English text, computer code, etc. denotes a set called the ciphertext space. consists of strings of symbols from an alphabet of definition, which may differ from the alphabet of definition for . An element of is called a ciphertext. Encryption and decryption transformations Each elementdenotes a set called theõ^· uniquely determines a bijection fromkey space. An element of is called a to key , denoted by. . is called an encryption function or an encryption transformation. Note that must be a bijection if the process is to be reversed and a unique plaintext messagerecovered for each distinct ciphertext.ôe· ì 3¼ ½f¿ For each , denotes a bijection from to (i.e., ). is called aThe process of applying the transformationdecryption function or decryption transformation to a message. · is usually re- ferred to as encrypting or the encryption of . ® The process of applying the transformation® ® to a ciphertext is usually referred to ó as decrypting or the decryption of . "$#&%'(*) "$#&%'(*) ! ! More generality is obtained if is simply defined as a transformation from to . That is to say, is a bijection from to where is a subset of . Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone. ThiNganHang.com
Trang 13
12 Ch. 1 Overview of Cryptography An encryption scheme consists of a set° f¼3ôh· ³ °+Q¼Rõ· ³ of encryption transformations and a corresponding setõ· +, of decryption transformations with the prop-ô· ,F¯- ë3ì erty that for each¹*¹.»Â»s¯/ there is a unique keyç· such that ; that is, for all . An encryption scheme is sometimes referred to as aThe keyscipherõ.and ô ¹Âõ²ô»in the preceding definition are referred to as aõ ô key pair and some- times denoted by . Note that and could be the same. ° Q¼Rõ· ³ To construct an encryption scheme requires one to select a message space+ , a ci- phertext spaceand a corresponding set of decryption transformations, a key space , a set of encryption transformations°0 ¼3ô· ³ . , Achieving confidentiality 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¤· ¹Êõ²Uô`». At a subsequent point in time, if Alice wishes to send a message® -¯ ¹.» ® to Bob, she computes ¹Â®¦»¯1 and transmits this to Bob. Upon receiving , Bob computes and hence recovers the original message . 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 combi- nation lock. The structure of the lock is available to anyone who 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. 1.22 Example (encryption schemeÈ %¯ÅÝ ) Let ¯ç°2 ì²3 Ù ²4 þ ³ and ¯¯ °VƲDzȲÉK²ÜK²ÝK³°±®ì²®Ù ²®þ ³ . There are precisely 65 bijections from to . The key space has six elements in it, each specifying one of the transformations. Figure 1.5 illustrates the sixencryption functions which are denoted by 87²Æ:9; (9DÝ . Alice and Bob agree on a trans- < ó Ì < > Ì < @ Ì = ó ó = ó ó = ó ó =?> ÌA> =?> ÌH> =?> ÌA> =?@ ÌA@ =?@ ÌH@ =?@ ÌA@ <CB Ì <ED Ì <GF Ì = ó ó = ó ó = ó ó =?> Ì > =?> Ì > =?> Ì > = @ Ì @ = @ Ì @ = @ Ì @ Figure 1.5: Schematic of a simple encryption scheme. formation, say® ì. To encrypt the message® ì, Alice computes ì¹I ì».¯®þ and sends þ to Bob. Bob decrypts® þ by reversing the arrows on the diagram for ì and observing that þ points to ì. ¨ c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter. ThiNganHang.com
Trang 14
© 1.4 Basic terminology and concepts 13 When is a small set, the functional diagram is a simple visual means to describe the mapping. In cryptography, the set is typically of astronomical proportions and, as such, the visual description is infeasible. What is required, in these cases, is some other simple means to describe the encryption and decryption transformations, such as mathematical al-gorithms. Ë Figure 1.6 provides a simple model of a two-party communication using encryption. Adversary Ì Ì Ì <encryption M=PO ñ JLKNMdecryptionHO ñ = = UNSECURED CHANNEL = plaintext destination source Alice Bob Figure 1.6: Schematic of a two-party communication using encryption. Communication participants Referring to Figure 1.6, the following terminology is defined. An entity or party is someone or something which sends, receives, or manipulates information. Alice and Bob are entities in Example 1.22. An entity may be a person, a computer terminal, etc. Asenderis an entity in a two-party communication which is the legitimate transmitter of information. In Figure 1.6, the sender is Alice. A receiver is an entity in a two-party communication which is the intended recipient of information. In Figure 1.6, the receiver is Bob. An adversary is an entity in a two-party communication which is neither the sender nor receiver, and which tries to defeat the information security service being provided between the sender and receiver. Various other names are synonymous with adver- sary 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. Channels 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 acces- sible to the adversary. An unsecured channel is one from which parties other than those for which the in- formation is intended can reorder, delete, insert, or read. Asecured channelis one from which an adversary does not have the ability to reorder, delete, insert, or read. Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone. ThiNganHang.com
Trang 15
14 Ch. 1 Overview of Cryptography One should note the subtle difference between a physically secure channel and a se- cured channel – a secured channel may 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 ded- icated communication link, to name a few. Security ² ² ²°0¼3õ%· ³ °0æ¼Rô^· A fundamental premise in cryptography is that the sets³ are public knowledge. When two parties wish to communicate securely using an en-¹Êõ²Uô`», cryption scheme, the only thing that they keep secret is the particular key pair 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 secu- rity of the entire scheme on this approach. History has shown that maintaining the secrecy of the transformations is very difficult indeed. 1.23 Definitionknowledge of the key pairAn encryption scheme is said to be¹Âõ²ô», can systematically recover plaintext from correspondingbreakable if a third party, without prior 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 stock may 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; and 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. Information security in general So far the terminology has been restricted to encryption and decryption with the goal of pri- vacy in mind. Information security is much broader, encompassing such things as authen- tication and data integrity. A few more general definitions, pertinent to discussions later in the book, are given next. An information security service is a method to provide some specific aspect of secu- rity. For example, integrity of transmitted data is a security objective, and a method to ensure this aspect is an information security service. ¨ c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter. ThiNganHang.com
Trang 16
© 1.5 Symmetric-key encryption 15 Breaking an information security service (which often involves more than simply en- cryption) implies defeating the objective of the intended service. A passive adversary is an adversary who is capable only of reading information from an unsecured channel. An active adversary is an adversary who may also transmit, alter, or delete informa- tion on an unsecured channel. Cryptology Cryptanalysis is the study of mathematical techniques for attempting to defeat cryp- tographic techniques, and, more generally, information security services. A cryptanalyst is someone who engages in cryptanalysis. Cryptology is the study of cryptography (Definition 1.1) 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. andª public-keyCryptographic techniques are typically divided into two generic types:. Encryption methods of these types will be discussed separately insymmetric-keyª1.5 and 1.8. Other definitions and terminology will be introduced as required. 1.5 Symmetric-key encryption ª1.5 considers symmetric-key encryption. Public-key encryption is the topic of ª1.8. 1.5.1 Overview of block ciphers and stream ciphers 1.24 Definitioncryption transformationsConsider an encryption scheme consisting of the sets of encryption and de-°0 ¼3õ· ³ and °0 ¼Rô· ³ , respectively, where is the key space. The encryption scheme is said to betion/decryption key pairõ ¹Êõ²ô»ô , it is computationally “easy” to determinesymmetric-key if for each associated encryp-ô knowing only õ, and to determineõ¯|ô from . Since in most practical symmetric-key encryption schemes, the term symmetric- key becomes appropriate. Other terms used in the literature arekey,Ù and conventional encryption. Example 1.25 illustrates the idea of symmetric-key en-single-key,one-key,private- cryption. 1.25 Example (symmetric-key encryption ) Let ¯ç°RQ²TS?²TU²UÕÕÕæ²WV.²3Xh²WYR³ be the Englishõ alphabet. Let and be the set of all strings of length five over . The key is chosen to be a permutation on . To encrypt, an English message is broken up into groups each having five letters (with appropriate padding if the length of the message is not a multipleof five) and a permutationô^¯õ ëfì õ is applied to each letter one at a time. To decrypt, the inverse permutationthe key õ is chosen to be the permutation which maps each letter to the one which is threeis applied to each letter of the ciphertext. For instance, suppose that positions to its right, as shown below õ¯ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z > D E F G H I J K L M N O P Q R S T U V W X Y Z A B CZ Private key is a term also used in quite a different context (see 1.8). The term will be reserved for the latter usage in this book. Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone. ThiNganHang.com
Trang 17
16 Ch. 1 Overview of Cryptography A message ¡¯ .À 7À À .À \[^] 3_U 3`8]Cab 3_U^abc[dQ 3eCf:XgeCh[^_iaU^jEbka is encrypted to®N¯ V¹»(¯ Õ Ë l I nmpofWqgrsfd_o]CjtfTqurv]CjmpwEfdxhyS(xbzm{q|]CrvVCjE] A two-party communication using symmetric-key encryption can be described by the block diagram of Figure 1.7, which is Figure 1.6 with the addition of the secure (both con- Adversary î key SECURE CHANNEL sourceî Ì Ì Ì <encryption M=PO ñ JuKWMdecryptionHO ñ = UNSECURED CHANNEL = = plaintext destination source Alice Bob Figure 1.7: Two-party communication using encryption, with a secure channel for key exchange.í î The decryption key can be efficiently computed from the encryption key . fidential and authentic) channel. One of the major issues with symmetric-key systems is to find an efficient method to agree upon and exchange keys securely. This problem is referred to as the key distribution problem (see Chapters 12 and 13). It is assumed that all parties know the set of encryption/decryption transformations (i.e., they all know the encryption scheme). As has been emphasized several times the only infor-mation which should be required to be kept secret is the keyõ ô . However, in symmetric-keyô encryption, this means that the keyõ. In Figure 1.7 the encryption key õ must also be kept secret, asis transported from one entity to the other with theô can be deduced from understanding that both can construct the decryption key . There are two classes of symmetric-key encryption schemes which are commonly dis- tinguished: block ciphers and stream ciphers. 1.26 Definitionsages to be transmitted into strings (calledA block cipher is an encryption scheme which breaks up the plaintext mes-blocks) of a fixed length å over an alphabet , and encrypts one block at a time. Most well-known symmetric-key encryption techniques are block ciphers. A number of examples of these are given in Chapter 7. Two important classes of block ciphers aresubstitution ciphers and transposition ciphers (ª1.5.2). Product ciphers (ª1.5.3) combine ¨ c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter. ThiNganHang.com
Trang 18
© 1.5 Symmetric-key encryption 17 these. Stream ciphers are considered inª ª1.5.4, while comments on the key space follow in 1.5.5. 1.5.2 Substitution ciphers and transposition ciphers Substitution ciphers are block ciphers which replace symbols (or groups of symbols) by other symbols or groups of symbols. Simple substitution ciphers û 1.27 Definitionå over . LetLet be the set of all permutations on the setbe an alphabet of symbols and be the set of all strings of length. Define for each õ7· an encryption transformation as: ¹I»(¯¹Âõ¹I ì»Êõ¹I Ù »ÿUÿÿõ¹.s}»»A¯|¹Ê®ì®Ù ÿÿÿ®~}»H¯®² where ¾¯¹ . ì Ù ÿUÿÿ3s}»^· . In other words, for each symbol in a å-tuple, replaceõ (substitute) it by another symbol from®O¯|¹Â®ì ®Ù ÿUÿÿ®~}» compute the inverse permutationaccording to some fixed permutationô ¯õ ëfì and . To decrypt ¹Â®¦»H¯¹Âô¹Â® ì»Êô`¹Ê®Ù »Qÿÿÿô`¹Ê®~}»»(¯¹I ì Ù ÿUÿÿ}»H¯cÕ is called a simple substitution cipher or a mono-alphabetic substitution cipher. The number of distinct substitution ciphers is ûA5 and is independent of the block size in the cipher. Example 1.25 is an example of a simple substitution cipher of block length five. Simple substitution ciphers over small block sizes provide inadequate security even ple 1.25, then the size of the key space iswhen the key space is extremely large. If the alphabet is the English alphabet as in Exam-ÇÝ+55ÉÆ`ÖÙ , yet the key being used can be determined quite easily by examining a modest amount of ciphertext. This follows from the simple observation that the distribution of letter frequencies is preserved in the ciphertext.a For example, the letter occurs more frequently than the other letters in ordinary English text. Hence the letter occurring most frequently in a sequence of ciphertext blocks is mosta likely to correspond to the letter in the plaintext. By observing a modest quantity of ci- phertext blocks, a cryptanalyst can determine the key. Homophonic substitution ciphers¬· w¹Â¬K»
å 1.28 Definitionthe restriction that the setsTo each symbol
¹Ê¬»
¬ , ¬h· , associate a set, be pairwise disjoint. Aof strings ofhomophonic substitutionsymbols, with fromcipher®&·
¹Ê¬»
¹Â¬K»
replaces each symbol. To decrypt a stringin a plaintext message block with a randomly chosen string® of å symbols, one must determine anw¹Â¬K» ¬~· such that
. The key for the cipher consists of the sets
. 1.29 Example
¹Â¦»H¯I°VÖƲÆÆK³(homophonic substitution cipher) Consider¬ ¯I°±¬²U³ ,
¹Ê¬»H¯°VÖÖ²Æ`ÖK³
Ö`ÖÖ`Æ, and Ö`Ö`ÆÆ
ÆÖ`Ö`Æ Æ`ÖÆ`Æ. The plaintext message block encrypts to one of the following: , , , . Observe that the codomain of the encryption function (for messages of length two) consists of the following pairwise disjoint sets of four-element bitstrings:¬¬ ½f¿ °±Ö`ÖÖ`Ö²Ö`ÖÆ`Ö²Æ`ÖÖ`Ö`²Æ`Ö±ÆÖ³ ¬K ½f¿ °±Ö`ÖÖ`ƲÖ`ÖÆ`ƲÆ`ÖÖ`Æ`²Æ`Ö±ÆƳ ¬ ½f¿ °±Ö`ÆÖ`Ö²Ö`ÆÆ`Ö²Æ`ÆÖ`Ö`²Æ`ƱÆÖ³ ½f¿ °±Ö`ÆÖ`ƲÖ`ÆÆ`ƲÆ`ÆÖ`Æ`²Æ`ƱÆƳ Any 4-bitstring uniquely identifies a codomain element, and hence a plaintext message. Ë Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone. ThiNganHang.com
Trang 19
18 Ch. 1 Overview of Cryptography Often the symbols do not occur with equal frequency in plaintext messages. With a simple substitution cipher this non-uniform frequency property is reflected in the ciphertext as illustrated in Example 1.25. A homophonic cipher can be used to make the frequency of occurrence of ciphertext symbols more uniform, at the expense of data expansion. Decryp- tion is not as easily performed as it is for simple substitution ciphers. Polyalphabetic substitution ciphers å 1.30 Definition A polyalphabetic substitution cipher is a block cipher with block length over an alphabet having the following properties: å ¹ú ì²1ú Ù ²ÕÕUÕæ²ú } » (i) the key spaceeach permutationconsists of all ordered sets ofú7 is defined on the set诹 ÿÿÿ; »permutations õs¯)¹ºú ²ú ²ÕUÕÕæ²1ú, where» (ii) encryption of the message¹.»A¯|¹ú ¹. »ºú .¹. ì»ÿÿUÿÙ ú}s}¹.s}»»under the key ì Ù } is given by ì ì Ù õ¯D¹úÙ ì ²ú Ù ²ÕUÕÕf²1ú; and} » ô ¯|¹ºú ìë3ì²1ú Ùëfì²ÕUÕÕf²1ú }ëfì» (iii) the decryption key associated with is . 1.31 Example¹ºú ²ú ²ú » (Vigen`ere cipherú ) Let ¯è°RQ²TS?²TU²UÕÕUÕæ²TV.²3XZ²TYR³ and å¯\È . Choose õ{¯ ú Ù ì Ù þ , where ì maps each letter to the letter three positions to its right in the alphabet,ú þ to the one seven positions to its right, and¡¯ "À ?À À ten positions to its right. If"À [^] _U `]Cab 3_:U^a8b[Q eEfHXeCh[n_a8UjCbCa then ®O¯ ¹»(¯ 9À Õ Ë l . m/h_kqg_:_hh{jE`UnrvfS?mp]E_:x_ xqgwqgfdVXuh Polyalphabetic ciphers have the advantage over simple substitution ciphers that symbol frequencies are not preserved. In the example above, the letter E is encrypted to both O and L. However, polyalphabetic ciphers are not significantly more difficult to cryptanalyze, theapproach being similar to the simple substitution cipher. In fact, once the block lengthå Æ -åå is determined, the ciphertext letters can be divided into groups (where groupú 7 , 9y &9 , consists of those ciphertext letters derived using permutation ), and a frequency analysis can be done on each group. Transposition ciphers Another class of symmetric-key ciphers is the simple transposition cipher, which simply permutes the symbols in a block. 1.32 Definition Consider a symmetric-key block encryption scheme with block length°VÆK²Ç²UÕÕUÕQ²1åU³ õ.· å. Let be the set of all permutations on the set . For each define the encryption function ¹»H¯¹ ÿUÿÿ » . I Tì TÙ 3 T} where 鯹 . ì Ù ÿUÿÿ3 } »?· , the message space. The set of all such transformationsõ is called apermutationsimple transposition cipher.ô%¯õ ë3ì. To decrypt ®N¯|¹Ê®The decryption key corresponding toì®Ù ÿÿÿ®~}», compute ¹Â®»H¯|¹Ê®Rì®Ris the inverseÙ ÿUÿÿ®R'}». A simple transposition cipher preserves the number of symbols of a given type within a block, and thus is easily cryptanalyzed. ¨ c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter. ThiNganHang.com
Trang 20
© 1.5 Symmetric-key encryption 19 1.5.3 Composition of ciphers In order to describe product ciphers, the concept of composition of functions is introduced. Compositions are a convenient way of constructing more complicated functions from sim- pler ones. Composition of functions μO¼½f¿ êN¼¡½æ¿ 1.33 Definitiontions. The compositionLet , , andof ê withbe finite sets and letμ , denoted¹ºêêμ&μ»Â¹º¶(or simply»(¯7ê¹Âμ¹¶R»»êæμand), is a function fromU¶· be func- to as illustrated in Figure 1.8 and defined by u s$6d6 . ¥ ¦ § ¥ § Î 1 ¡ Î ¡ Í 2 ¢ Í ¢ Ì Ï 3 £ Ì £ 4 ï ¤ ï Ï ¤ P¨ ðG©(Ò ð Ò Figure 1.8: The composition of functions and . ÕÕÕæ²UμComposition can be easily extended to more than two functions. For functionsμ 3ÿÿÿæμ æμ μ μ ì, μÙ , μW} W}, one can define W}6 ~ Ù ì, provided that the domain of W} equals the codomain of ëfì and so on. Compositions and involutionsª Involutions were introduced inerty: ª¹*ª¹¶R»Â»A¯7¶ for all¶ in the domain of1.3.3 as a simple class of functions with an interesting prop-ª ; that is, ª«8ª is the identity function. 1.34 Remark (composition of involutions) The composition of two involutions is not necessar- ily an involution, as illustrated in Figure 1.9. However, involutions may be composed to get somewhat more complicated functions whose inverses are easy to find. This is an importantfeature for decryption. For example if¯ ÿÿÿ ëfì ¯ ª+¬ ² ªR®ÿÿÿ²UÕÕÕ3²W ªA¯ are involutions then the inverse of ª ° ª+¬ ªR® W ªA¯ is ª ± ªA¯ ªA¯I²¬ W ª+¬ , the composition of the involutions in the reverse order. 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 Ï 4 4 ï 4 4 ïP¨ Ï 4 ðE©(Ò ð Ò Figure 1.9: The composition of involutions and is not an involution. Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone. ThiNganHang.com
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!