AAAAnnnnaaaallllyyyyssssiiiissss ooooffff tttthhhheeee DDDDEEEESSSS aaaannnndddd tttthhhheeee DDDDeeeessssiiiiggggnnnn ooooffff tttthhhheeee LLLLOOOOKKKKIIII EEEEnnnnccccrrrryyyyppppttttiiiioooonnnn SSSScccchhhheeeemmmmeeee unicrest here A THESIS SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY COLLEGE, UNIVERSITY OF NEW SOUTH WALES AUSTRALIAN DEFENCE FORCE ACADEMY FOR THE DEGREE OF DOCTOR OF PHILOSOPHY By Lawrence Peter Brown 1991 ii c Copyright 1991 by Lawrence Peter Brown CCCCeeeerrrrttttiiiiffffiiiiccccaaaatttteeee ooooffff OOOOrrrriiiiggggiiiinnnnaaaalllliiiittttyyyy I hereby declare that this submission is my own work and that, to the best of my knowledge and belief, it contains no material previously published or written by another person nor material which to a substantial extent has been accepted for the award of any other degree or diploma of a university or other institute of higher learning, except where due acknowledgement is made in the text. I also hereby declare that this thesis is written in accordance with the University's Policy with respect to the use of Project Reports and Higher Degree Theses. Lawrence Peter Brown iii iv AAAAbbbbssssttttrrrraaaacccctttt This thesis will analyse some existing encryption algorithms used to provide secrecy in communications and data storage, and will detail the development of a new private key algorithm. It starts with a brief survey of modern encyption algorithms and their uses. It then takes a closer look at the RSA public key algorithm, with particular reference to its practical implementation. It shows that whilst RSA has some very desirable properties for use in public networks in that keys need not be exchanged previously, limitations in implementation speeds mean that RSA alone is not sufficient. Consequently a hybrid scheme is required which combines a public key scheme for authentication and key exchange, with a private key scheme for privacy. At present the DES algorithm is the sole certified private key scheme. It has been extensively analysed for possible weaknesses since its adoption in 1977. It is generally agreed that whilst the structure is sound, its key size of 56-bits has become too small with the improvements in computational speed on modern computers. Whilst the DES algorithm is public, its design criteria are classified. This thesis examines the design of the DES data encryption algorithm and related schemes, particularly with reference to the fundamental avalanche and completeness properties. From this is developed some possible design criteria for such schemes. Using these criteria, along with insights based on generic substitution-permutation cipher construction, suggestions and support from the authors colleagues, and with some results on substitution box design by Pieprzyk and Seberry, a new group of private key schemes, the LOKI family, is designed and presented as the major achievement of this thesis. v vi FFFFoooorrrreeeewwwwoooorrrrdddd To my supervisors Jennifer Seberry, Ah Chung Tsoi, and David Anderson, for their help, advice, support and encouragement both directly on the thesis material, and indirectly though their help in supporting this research environment. To the current and former members of the Department of Computer Science, and particularly to Geoff Collins, George Gerrity, Andrzej Goscinski, Mike and Cathy Newberry, Josef Pieprzyk, Rei Safavi-Naini, and Chris Vance for their support, help and suggestions. Thankyou. This work could not have been completed without the support of ARC grant A48830241, ATERB, and Telecom Australia contract 7027. To all of those organisations, thankyou for your encouragement of this research. vii viii CCCCoooonnnntttteeeennnnttttssss Chapter 1. Some Introductory Words .................. 1 1 Genesis and Goals of the Thesis ................... 1 2 Content of the Thesis ............................. 5 2.1 Main Thesis ..................................... 5 2.2 Appendices ...................................... 8 3 Other Work by the Author .......................... 9 4 Definitions ....................................... 10 Chapter 2. Data Encryption - an Introduction and Overview ....................................... 13 1 Introduction ...................................... 13 2 Modern Private-Key Cryptography ................... 13 2.1 Introduction .................................... 13 2.2 Fundamental Concepts ............................ 14 2.3 Lucifer ......................................... 17 2.4 DES ............................................. 20 2.5 DES Variants .................................... 24 2.6 FEAL ............................................ 24 2.7 Khufu, Khafre and Snefru ........................ 25 2.8 LOKI ............................................ 27 3 Public-Key Cryptography ........................... 27 3.1 Introduction .................................... 27 3.2 Public-Key Distribution Systems (PKDS) .......... 29 3.2.1 Description ................................... 29 3.2.2 Implementation ................................ 31 3.3 The Rivest-Shamir-Adleman (RSA) PKC ............. 32 3.3.1 An Overview of RSA ............................ 32 3.3.2 RSA Weaknesses and Related Schemes ............ 34 3.3.3 Implementation ................................ 35 4 Further Reading ................................... 36 5 Conclusions ....................................... 37 Chapter 3. Techniques for Implementing the RSA Public Key Cryptosystem ........................ 39 1 Introduction ...................................... 39 2 RSA Encryption and Decryption ..................... 39 3 RSA Key Generation ................................ 46 4 RSA Implementation in Practice .................... 49 4.1 Software Implementations of RSA ................. 49 4.2 Hardware Implementations of RSA ................. 50 5 Conclusion ........................................ 51 Chapter 4. Design Rules for the DES ................. 53 1 Introduction ...................................... 53 ix x 2 Description of the DES ............................ 53 3 Known DES Design Criteria ......................... 54 3.1 S-box Design Criteria ........................... 54 3.2 P-box Design Criteria ........................... 56 3.2.1 IP and IP-1 ................................... 56 3.2.2 PC1 ........................................... 57 3.2.3 P and E ....................................... 57 3.2.4 PC2 ........................................... 59 3.3 Key Scheduling .................................. 60 4 Ciphertext Dependency Analysis .................... 61 4.1 Ciphertext Dependence of Plaintext Bits ......... 61 4.2 Ciphertext Dependence on Key Bits ............... 62 5 Design of new DES style Ciphers ................... 65 5.1 S-box Redesign .................................. 65 5.2 P-box Redesign .................................. 66 5.3 Key Scheduling Extension ........................ 67 5.4 Dependency Analysis of An Extended DES .......... 68 6 Conclusion ........................................ 68 Chapter 5. On the Design of Permutation P in Feistel Ciphers ................................ 71 1 Introduction ...................................... 71 2 Empirical P-box Design Criteria ................... 71 3 Further Analysis of the Design of Permutation P ................................................ 74 4 Analysis of the Best Latin-Square Permutations P ................................................ 75 5 A Regular Form for Permutation P .................. 77 6 A Further Criterion for Best Permutations ......... 78 7 Design Rules for Permutation P .................... 79 8 Regular Permutations P in Feistel Ciphers ......... 80 9 Conclusion ........................................ 81 Chapter 6. Key Scheduling in Feistel Ciphers ........ 83 1 Introduction ...................................... 83 2 The Key Schedule in DES ........................... 83 3 Empirical Key Schedule Design Criteria ............ 84 4 Ciphertext Dependence on Key Bits ................. 85 5 Alternatives for the Key Schedule ................. 85 6 Some Trials on New Key Schedules .................. 86 7 Design Criteria for New Key Schedules ............. 89 8 An Alternative Key Schedule Design ................ 90 9 Conclusion ........................................ 91 Chapter 7. LOKI - A Cryptographic Primitive for Authentication and Secrecy Applications ........ 93 1 Introduction ...................................... 93 1.1 Overview ........................................ 94 1.2 Encryption ...................................... 95 1.3 Decryption ...................................... 97 1.4 Function f ...................................... 97 xi 2 Design Philosophy ................................. 100 2.1 Overall LOKI Algorithm Design ................... 100 2.2 Overall Design, Permutation P, E, and the Key Schedule ....................................... 102 2.3 Key Representation and Choice ................... 105 2.4 LOKI S-boxes .................................... 106 2.5 Selection of Alternate Substitution Functions S .............................................. 109 3 Additional Modes of Use ........................... 112 3.1 Single Block Hash (SBH) Mode ................... 112 3.2 Double Block Hash (DBH) Mode .................... 113 4 Performance and Implementations ................... 114 4.1 Software Implementation ......................... 114 4.2 Hardware Implementation ......................... 115 5 Conclusion ........................................ 115 Chapter 8. Conclusion ............................... 118 1 Results Obtained in this Thesis ................... 118 2 Assumptions and Limitations of the Research ....... 121 3 Suggestions for Further Research .................. 122 Appendix A. Analysis of the LOKI Primitive .......... 123 1 LOKI Dependency Analysis .......................... 123 1.1 LOKI CPdep Analysis ............................. 125 1.2 LOKI CKdep Analysis ............................. 129 2 Analysis of the LOKI S-Boxes ...................... 133 Appendix B. Dependency Analysis Programs ............ 137 1 cp_dep.c .......................................... 137 2 ck_dep.c .......................................... 142 Appendix C. LOKI - Sample Implementation ............ 150 1 Overall Program Structure ......................... 150 2 Test Data ......................................... 151 3 Program Listings .................................. 154 Bibliography ........................................ 171 xii IIIInnnnddddeeeexxxx ooooffff FFFFiiiigggguuuurrrreeeessss Fig 1.1 - The Need for Privacy ...................... 1 Fig 1.2 - The Need for Authentication ............... 2 Fig 1.3 - Private-Key Cryptosystems ................. 3 Fig 1.4 - Public-Key Cryptosystems .................. 4 Fig 2.1 - Substitution Operation .................... 14 Fig 2.2 - Permutation Operation ..................... 15 Fig 2.3 - Sample S-P Network, with Avalanche Characteristic ................................. 16 Fig 2.4 - A Round of a Feistel Cipher ............... 17 Fig 2.5 - Lucifer ................................... 18 Fig 2.6 - Lucifer Function f ........................ 19 Fig 2.7 - DES Enciphering ........................... 20 Fig 2.8 - DES Function g ............................ 22 Fig 2.9 - DES Key Scheduling ........................ 23 Fig 5.1 - DES as a Mixing Function .................. 72 Fig 7.1 - LOKI Encryption Computation ............... 95 Fig 7.2 - LOKI Function _f Detail .................... 99 Fig 7.3 - LOKI S-Box Detail ......................... 100 Fig 7.4 - LOKI Single Block Hash (SBH) .............. 113 Fig 7.5 - LOKI Double Block Hash (DBH) .............. 114 xiii xiv IIIInnnnddddeeeexxxx ooooffff TTTTaaaabbbblllleeeessss Table 2.1 - Key Schedule for DES .................... 23 Table 3.1 - Complexity of Factorization and Exponentiation Operations Mod R ................ 40 Table 3.2 - Example of Long-hand Multiplication ..... 40 Table 3.3 - Number and Remainder (mod 517) .......... 42 Table 3.4 - Example of Modulo Reduction ............. 42 Table 4.1 - P.E Permutation ......................... 58 Table 4.2 - Worst Case DES P ........................ 61 Table 4.3 - Dependency of Ciphertext bits on Plaintext bits in DES .......................... 62 Table 4.4 - Dependency of Ciphertext bits on Key bits in DES with Current PC2 ................... 63 Table 4.5 - Dependency of Ciphertext bits on Key bits in DES with Worst Case PC2 ................ 64 Table 4.6 - Dependency of Ciphertext bits on Key bits in DES with Sample PC2 .................... 64 Table 4.7 - Sample DES PC2 .......................... 64 Table 4.8 - Sample Extended DES P ................... 66 Table 4.9 - Sample Extended DES PC2 ................. 67 Table 4.10 - Key Schedule for an Extended DES ....... 67 Table 4.11 - Dependency of Ciphertext bits on Plaintext bits in Extended (128-bit) DES with a Sample PC2 ................................... 68 Table 4.12 - Dependency of Ciphertext bits on Key bits in Extended (128-bit) DES with a Worst Case PC2 ....................................... 69 Table 4.13 - Dependency of Ciphertext bits on Key bits in Extended (128-bit) DES with a Sample Regular PC2 .................................... 69 Table 4.14 - Worst Case Extended DES P .............. 70 Table 4.15 - Worst Case Extended DES PC2 ............ 70 Table 5.1 - P.E Permutation ......................... 73 Table 5.2 - Worst Case DES P ........................ 74 Table 5.3 - Dependency of Ciphertext on Plaintext Bits for various DES permutations P by Round ................................................ 75 Table 5.4 - Fixed Columns in Sample Permutations P ................................................ 76 Table 5.5 - Best Latin-Square Permutations P ........ 77 Table 5.6 - Best Regular Form Permutations P ........ 78 Table 5.7 - Dependency of Ciphertext bits on Plaintext bits via Message, Autoclave and Both Inputs .................................... 78 Table 5.8 - Best Latin Square Permutations P by both Ciphertext-Plaintext and Ciphertext-Key xv xvi Dependence ..................................... 79 Table 5.9 - Best Regular Form Extended Permutations P ................................. 80 Table 5.10 - Dependency of Ciphertext bits on Plaintext bits in Extended (128-bit) DES ....... 80 Table 6.1 - Key Schedule for DES .................... 83 Table 6.2 - Current DES Permutation PC2 ............. 84 Table 6.3 - Form of generated Permutations PC2 ...... 86 Table 6.4 - Dependency of Ciphertext bits on Key bits Using Current DES Permutation P and Key Schedule ....................................... 87 Table 6.5 - Dependency of Ciphertext bits on Key bits Using Current DES Permutation P and Key Schedule by Both Message and Autoclave S-box Inputs ......................................... 88 Table 6.6 - Trial Key Schedules ..................... 89 Table 6.7 - Null and Local Permutations PC2 for Alternative Key Schedule ....................... 90 Table 6.8 - Alternative Constant Key Rotation Schedule ....................................... 90 Table 6.9 - Dependency of Ciphertext bits on Key bits Using Current DES Permutation P and the Alternative Key Schedule by Both Message and Autoclave S-box Inputs ......................... 91 Table 7.1 - LOKI Expansion Function E ............... 98 Table 7.2 - LOKI S-box .............................. 99 Table 7.3 - LOKI Permutation P ...................... 100 Table 7.4 - LOKI Key Schedule Overview .............. 104 Table 7.5 - Dependency of Ciphertext bits on Plaintext and Key bits by Both Message and Autoclave S-box Inputs ......................... 105 Table 7.6 - LOKI S-box Non-linearity for the Boolean function of all Input Bits to each Output bit ..................................... 109 Table 7.7 - LOKI - S-box Analysis ................... 109 Table 7.8 - Irreducible Polynomials for LOKI S- boxes .......................................... 110 Table 7.9 - Exponents Inverse Pairs Available for use in the LOKI S-boxes ........................ 111 0 CCCCHHHHAAAAPPPPTTTTEEEERRRR 1111 SSSSoooommmmeeee IIIInnnnttttrrrroooodddduuuuccccttttoooorrrryyyy WWWWoooorrrrddddssss _1. _G_e_n_e_s_i_s _a_n_d _G_o_a_l_s _o_f _t_h_e _T_h_e_s_i_s Cryptography, the study of secret writing, has a long his- tory which until recently has been primarily associated with military and government needs. Cryptography has two major purposes. The first is the provision of _p_r_i_v_a_c_y by concealing the contents of some message from _e_a_v_e_s_d_r_o_p_p_e_r_s who are not intended to be able to read it (Fig 1.1). This has been the traditional application of cryptography. FFFFiiiigggg 1111....1111 ---- TTTThhhheeee NNNNeeeeeeeedddd ffffoooorrrr PPPPrrrriiiivvvvaaaaccccyyyy However, with the increasing use of electronic media, there has been a developing need for an electronic equivalent of the written signature. This addresses the need for _a_u_t_h_e_n_t_i_c_a_t_i_o_n, of proving who has sent a given message, such as legal contracts, letters, etc. in a manner that they cannot subsequently repudiate (Fig 1.2). Both of these aspects are important in modern commercial cryptography. 1 2 FFFFiiiigggg 1111....2222 ---- TTTThhhheeee NNNNeeeeeeeedddd ffffoooorrrr AAAAuuuutttthhhheeeennnnttttiiiiccccaaaattttiiiioooonnnn Traditional cryptographic schemes have relied on a series of _s_u_b_s_t_i_t_u_t_i_o_n (where letters or words are replaced by others), and _t_r_a_n_s_p_o_s_i_t_i_o_n or _p_e_r_m_u_t_a_t_i_o_n (where the order of letters or words is changed) operations to conceal the message. The particular substitution or transposition used is controlled by a _k_e_y. This key is used by both the sender and the recipient of the concealed mesage, and hence has to be kept secret in order to protect the secrecy of the message. Such schemes are called _P_r_i_v_a_t_e- _K_e_y _C_r_y_p_t_o_s_y_s_t_e_m_s for this reason (Fig 1.3). The need to exchange keys via a trusted courier, and to keep them secret, was manageable whilst the communications channels were restricted to well defined miltary or diplomatic hierarchies. However the explosion of electronic communications media, the rise of Electronics Funds Transfer (EFT), and the need for secure communications in business and the public in electronic mail schemes, have all lead to a need for some alternative scheme where this previous exchange of keys is not needed. Since the number of keys which would need to be exchanged grows as the square of the number of partici- pants, this soon becomes infeasible. What is needed is the ability to be able to publish an encryption key (used either to conceal the message, or to verify a signature) in the equivalent of a telephone directory, without compromising the decryption key (used to restore the mes- sage or create a signature), and hence the security of the message. Such schemes are called _P_u_b_l_i_c-_K_e_y _C_r_y_p_t_o_s_y_s_- _t_e_m_s, or _T_w_o-_K_e_y _C_r_y_p_t_o_s_y_s_t_e_m_s (Fig 1.4). They were ori- ginally proposed in a pivotal paper by Diffie and Hellman Chapter 1 3 [DiH76], who developed these concepts, and proposed a pos- sible scheme; and also independently by Merkle [Mer78] who outlined the basic concepts, but did not propose a feasi- ble system. FFFFiiiigggg 1111....3333 ---- PPPPrrrriiiivvvvaaaatttteeee----KKKKeeeeyyyy CCCCrrrryyyyppppttttoooossssyyyysssstttteeeemmmmssss Ideally, public-key cryptosystems should be able to pro- vide all the features desired in a secure communications system. However, as shown in Chapter 3, limitations in the implementation speed of such schemes at present restrict their usefulness to authentication and key exchange (important though these are). Consequently there is a need for hybrid schemes which use a public-key cryptosys- tem to exchange session keys and to sign messages, and a private-key cryptosystem to efficiently encrypt the mes- sage for privacy. This implies a need for good modern private keys schemes, preferably a number of different schemes which may be employed in applications of varying sensitivity in the commercial and government confidential areas. Current schemes in use are either proprietry, or are felt to have key sizes which are too small. The remainder of this thesis details the development of a good new private key scheme, which is the major achievement of this thesis. Chapter 1 4 FFFFiiiigggg 1111....4444 ---- PPPPuuuubbbblllliiiicccc----KKKKeeeeyyyy CCCCrrrryyyyppppttttoooossssyyyysssstttteeeemmmmssss To achieve this, the Data Encryption Standard (DES) [NBS77] is analysed in detail as a source of insights to be used in the design of the new cipher. DES has achieved wide utilization, particularly in the banking and elec- tronic funds transfer areas, where it is now an Australian standard [ASA85]. At the time of its introduction there was a considerable amount of controversy, primarily with the choice of a 56-bit key [DiH77], [Hel79a]. This was on the grounds that such a key length was small enough to be exhaustively searched on machines which could be con- structed in the foreseeable future. With the march of computer technology, this risk appears to be rising. How- ever, on all other accounts DES appears to be an excellent cryptosystem. The DES has withstood a concerted analysis by the open research community, since its adoption in 1977. The most successful attack to date, that of Biham and Shamir [BiS90] still performs worse than an exhaustive key-space search on the DES with the full 16 rounds. With the current significant use of DES (especially in banking), there is interest in designing and building a DES-type cryptosystem with an extended key length, for several reasons. These include: +o Doubts about the ability of DES to withstand an attack based on exhaustive key-space searches on specialised hardware (cf. the decision of the US NBS to withdraw certification of DES for all but banking applications). This may be overcome by increasing Chapter 1 5 the key length. +o The difficulty in obtaining DES systems outside the US, due to export restrictions. +o The desire to develop a scheme for which all the design criteria used are known, and hence open to criticism. Given these reasons, and the confidence with which the DES is otherwise regarded, it was felt to be suitable for analysis to derive some design rules. Whilst the DES algorithm is public, its design criteria are classified. This thesis examines the design of the DES data encryption standard, and develops some possible design criteria for it in Chapters 4, 5 and 6. Using these criteria, along with insights based on generic substitution-permutation cipher construction, suggestions and support from the authors colleagues, and with some results on substitution box design by Pieprzyk and Seberry [PiF89], [Pie90], [Pie89], [PiS89], a new group of private key schemes, the LOKI family is designed. This development is detailed in Chapter 7. A preliminary analysis of one of the members of this family is then given. The appendices of this thesis present the detailed results from the analysis of one of the LOKI ciphers; the code used for the dependency analysis programs; and a sample LOKI cipher implementa- tion. _2. _C_o_n_t_e_n_t _o_f _t_h_e _T_h_e_s_i_s _2._1. _M_a_i_n _T_h_e_s_i_s The detailed contents of each chapter are as follows. Chapter 1 is this overview of the thesis. Chapter 2 surveys the field of cryptography, providing an overview of the modern private and public key cryptosys- tems used to provide privacy and authentication. It con- trasts their strengths and weaknesses, and briefly describes a number of schemes either in use, or proposed for use. These algorithms form the basis against which further algorithm development will be compared. Chapter 3 examines the RSA public key cryptosystem, which at present is generating considerable interest as a scheme with a wide range of potential uses. Indeed, it has already been adopted to provide authentication in EFT application in the UK. However, its practical use for providing secrecy has been limited because of the time Chapter 1 6 taken to perform its essential encryption and decryption functions. Whilst the times achieved to date are suffi- ciently short for key exchange and authentication schemes, they are not fast enough for encrypting data to provide privacy. Thus in the near term, practical schemes will very likely use hybrid systems. These use a public key algorithm to exchange session keys, and to provide authen- tication and non-repudiation of messages, and a fast private key scheme to provide privacy. This chapter con- cludes that whilst public key schemes would seem to be the obvious realm of research into cryptographic algorithms because of their advantages in public networks, present limitations indicate that good private key schemes are still required. This chapter includes material previously presented to the "Secure Data Communications Workshop", organized by the IEEE Communications Section, Victorian Branch, held at the Town House, Melbourne, on 31st July 1987 [Bro87]. Chapter 4 examines the Data Encryption Standard DES. This is the most widely used private key encryption system at present, especially in the financial industry. Though there were some initial doubts about the design of DES, it has withstood considerable analysis by the open research community since its adoption in 1977. The design of the DES is regarded as sound, though the size of key is thought to be too small. Whilst DES is a standard, the design criteria used in its development have been classi- fied by the US government. Because of this, and of increasing doubts about the ability of DES to withstand an attack based on an exhaustive key-space search using specialised hardware, there is considerable interest in developing an encryption scheme for which the design rules used are known, and hence open to analysis and criticism. This is the primary goal of this thesis. In order to achieve this, a detailed examination of the DES is done, since its design has withstood the test of time. This chapter reviews what is known about the design criteria for the S-boxes, P-boxes, and key scheduling in the current DES. It then presents some initial observations by the author on possible design rules for the permutations P, PC2, and the key rotation schedule KS in the DES. It then indicates how this information could be used to design new private key schemes with either full 64-bit keys (instead of the 56-bits used in the DES), or with double length keys of 128-bits. This chapter includes material previously presented to IFIP Sec'88, held on the Gold Coast, Australia, in May 1988, and subsequently pub- lished in [Bro89]. Chapter 1 7 The next two chapters examine two key components of the DES structure in more detail: the permutations P and PC2 and the key schedule KS. Chapter 5 develops some design criteria for the permuta- tion P in a DES style cryptosystem. This permutation pro- vides the diffusion component of a substitution- permutation network. Some empirical rules which seem to account for the derivation of the permutation used in the DES are first presented. The author then notes that these permutations may be regarded as latin-squares which link the outputs of S-boxes to their inputs at the next stage. A subset of these with a regular structure, and which per- form well in a dependency analysis are then presented. The author then generalises the design rules for permuta- tion P. These rules will be used later in Chapter 7 in the design of the LOKI algorithm. This chapter includes material previously presented to Eurocrypt '89 in Houthalen, Belgium, in April 1989, and published in [BrS90a]. Chapter 6 develops some design criteria for the key schedule in a DES style cryptosystem. The key schedule involves a Key Rotation component KS, and the permutation PC2. Together these provide for a diffusion of dependency of ciphertext bits on key bits. Some empirical rules which seem to account for the derivation of the key schedule used in the DES are first presented. A number of trials were run with various key schedules, and some further design rules were derived. An alternative form of key schedule was then tested. This used either a null PC2, or one in which permutations only occurred within the inputs to a given S-box, and a much larger rotation schedule than used in the DES. This was found to be as effective as the key schedule used in the current DES, and is proposed for use later in Chapter 7 in the design of the LOKI algorithm. This chapter includes material previ- ously presented to Auscrypt '90, in Sydney, Australia, in January 1990, and published in [BrS90b]. Chapter 7 presents the major achievement of this thesis. It provides an overview of the LOKI encryption algorithm which may be used to encrypt and decrypt a 64-bit block of data using a 64-bit key. It was developed by the author and his colleagues Professor Jennifer Seberry and Dr. Josef Pieprzyk. The structure of the LOKI encryption algorithm was designed by the author based on the general design principles developed in the previous chapters. The design principles for selecting S-boxes developed by Pieprzyk and Seberry [PiF89], [Pie90], [Pie89], [PiS89] were used in the design of the S-boxes used in LOKI. This Chapter 1 8 chapter completely details the proposed publicly standar- dised version of the LOKI cipher. It also describes how customised versions of the cipher may be constructed which are believed to have the same degree of security as the standard version of the cipher. The author then summar- ises the encouraging results from the initial testing of the LOKI cipher, details of which are given in Appendix 1. The LOKI cipher may be used in any mode of operation currently defined for DES, with which it is interface com- patible [AAA83]. In addition, the author has adapted two modes of operation of LOKI which compute a 64-bit or 128- bit Message Authentication Code (or hash values) respec- tively, from previous work by Davies and Price [DaP89], Winternitz [Win83], and Quisquater and Girault [QuG90]. These modes of operation may be used to provide authenti- cation of a communications session, or of data files. Finally the author presents some observations about the likely performance of the LOKI cipher in both software and hardware implementations, which show that it compares extremely favorably against the alternatives. This chapter includes material previously presented to Auscrypt '90, in Sydney, Australia, in January 1990, and published in [BrS90b]. Versions of this material have also been sup- plied to the European RIPE consortium [BPS89], to Stan- dards Australia, and to the Defence Signals Directorate, for evaluation. Chapter 8 summarises the results and achievements of this thesis, as described in the preceeding chapters. _2._2. _A_p_p_e_n_d_i_c_e_s The Appendices of this thesis comprise the detailed results from the analysis of the LOKI algorithm; the C program source for the DES dependency analysis programs; and the C program source for a sample implementation of the LOKI algorithm. Appendix 1 presents the detailed results from the depen- dency analysis and preliminary statistical analysis of LOKI cipher. Appendix 2 contains a listing of two programs ccccpppp____ddddeeeepppp and cccckkkk____ddddeeeepppp, which perform a dependency analysis of output bits on input and key bits for a DES like cipher. This analysis provides a measure of effectiveness of the permutations P, PC2, and the key schedule KS, in achieving the avalanche and completeness properties. This was used as a measure of effectiveness in evaluating variations of the permuta- tions P, PC2, and the key schedule KS in DES like schemes, and in LOKI, in the development of the design criteria. In Chapter 1 9 detail, the programs are: cp_dep.c builds a dependency matrix for each ciphertext bit, based on plaintext bits, for a given P. It assumes that the S-boxes provide an adequate degree of confu- sion sufficient to ensure that all outputs are depen- dent on all inputs, and that the S-Box outputs are all equivalent. It takes as input a permutation P to use in the cipher structure being analysed. ck_dep.c builds a dependency matrix for each ciphertext bit, based on keytext bits, for a given P, PC2 and key schedule. It assumes that the S-boxes provide an adequate degree of confusion sufficient to ensure that all outputs are dependent on all inputs, and that the S-Box outputs are all equivalent. It takes as input permutations P, and PC2, and a key schedule KS to use in the cipher structure being analysed. Appendix 3 contains a listing of a sample implementation of the LOKI cipher. These implement the first (small but slow) of the possible software implementations identified in Chapter 7. _3. _O_t_h_e_r _W_o_r_k _b_y _t_h_e _A_u_t_h_o_r During the period when the work detailed in this thesis was being developed, the author was engaged in a couple of other related projects which may be of interest. One discusses some alternative approaches to providing security in remote terminal sessions. Since remote termi- nal sessions mean that information is carried over a net- work that may not be trusted, there is a need for mechan- isms to protect the security of information exchanged dur- ing the session. The protocols implemented will need to address the issues of authentication of the parties, nego- tiation of a suitable cipher to use, and the exchange of keys for that cipher. This paper examines each of these issues, describes a prototype implementation incorporating some of these features in the sssseeeecccclllloooogggg program, and finishes with a description of work in progress on extending the widely used tttteeeellllnnnneeeetttt protocol to incorporate some of these security features. This material was presented to AUUGC'90, World Trade Centre, Melbourne, Victoria, Aus- tralia 26th - 28th September, 1990 [Bro90b], [Bro90]. The other project surveys the various alternatives avail- able for the provision of a Pay-TV service in Australia. Chapter 1 10 In particular, the technical alternatives available for the delivery, transmission, scrambling and key management components are presented. A selection of systems in, or proposed for use are then compared. This material was published in [Bro90a]. _4. _D_e_f_i_n_i_t_i_o_n_s Within this thesis, the following definitions apply: Algorithm a clearly specified mathematical process for computa- tion; a set of rules which, if followed, will give a prescribed result. Autoclave a process of incorporating information from the mes- sage input to an encryption algorithm into the key scheduling of that algorithm. Thus different message inputs result in different keying choices in the various stages of the algorithm. This is usually acomplished by using some message bits as inputs to both the key selection as well as the message substi- tution parts of the algorithm. Avalanche Property of a function implies that a change in an input bit should result in approximately half of the output bits changing [Fei73]. Bit Numbering bits within a 64-bit block b are numbered from 63 to 0, left to right, MSB to LSB, and denoted [b b ...b b ]. The bits within a 32-bit block are nu6m3be6r2ed l1ik0ewise from 31 to 0, ie the string 10010 represents the number eighteen. When used to represent a polynomial in a Galois field, a block is interpreted as having the left most bit being the most significant. ie the string 100011011 represents the polynomial x8+x4+x3+x+1. Ciphertext clear text that has been encrypted. Cleartext intelligible text or signals that have meaning and that can be read and used. Completeness Property of a function implies that each output bit must be a complex function of all input bits [KaD79]. Chapter 1 11 Concatenation of two blocks L and R of 32 bits, denoted L | R, will result in LR a 64-bit block consisting of the bits of L followed by the bits of R. Confusion a term coined by Shannon [Sha49] to describe a func- tion whose output is a complex function of its inputs (usually composed of a data block and a sub-key). Diffusion a term coined by Shannon [Sha49] to describe a linear function whose output is a permutation (or wire- crossing) of its inputs, and which distributes input bits so as to remove any local clustering. Data Encryption Algorithm (DEA) an algorithm designed to encrypt and decrypt blocks of data. Decryption the transformation of ciphertext into cleartext. Encryption the transformation of cleartext into ciphertext for the purpose of security or privacy. Encryption algorithm a set of mathematically expressed rules for rendering information unintelligible, by effecting a series of transformations to the normal representation of the information, through the use of variable elements controlled by the application of a key. Galois Field denoted GF(pn), is an extension of degree n of GF(p). In particular, this thesis refers to binary fields, eg GF(28). Initialization Vector a binary vector used in the initial input block in cipher block chaining mode of operation. Key a 64-bit quantity which is used for transformations between ciphertext and cleartext. LOKI the name of the DEA being developed in this thesis. Modulo 2 addition a mathematical operation equivalent to binary Chapter 1 12 addition without carry. Sometimes referred to as an 'exclusive OR' operation. Non-Linearity of a function f, belonging to the set F of all Boolean functions of n Boolean variablnes, is the minimum Hamming distance between f and the set of all linear Boolean functions L existing in F [Pie90], [Pie89]. n n Permutation a function that reorders a set of n input bits. It may be described by a table of size n. nb: this usage differs from that of Pieprzyk, for whom this term is a synonym for substitution. ROL(B,n) the operation of rotating a block B n places to the left, with wraparound from the MSB to LSB. ie; b becomes b , b becomes b etc. 0 n 1 n+1 ROR(B,n) the operation of rotating a block B n places to the right, with wraparound from the LSB to MSB. ie; b becomes b , b becomes b etc. n 0 n+1 1 Substitution a function mapping a set of m bit input words onto a set of n bit output words. It may be described by a table of size 2m. Chapter 1 CCCCHHHHAAAAPPPPTTTTEEEERRRR 2222 DDDDaaaattttaaaa EEEEnnnnccccrrrryyyyppppttttiiiioooonnnn ---- aaaannnn IIIInnnnttttrrrroooodddduuuuccccttttiiiioooonnnn aaaannnndddd OOOOvvvveeeerrrrvvvviiiieeeewwww _1. _I_n_t_r_o_d_u_c_t_i_o_n This chapter provides an overview of some modern encryp- tion algorithms, both private and public key. It will describe the general framework within which these schemes have been developed, briefly detail a number of algo- rithms, and then describe in detail two particular schemes: DES and RSA. These have been chosen as the two algorithms generating the most interest in the private and public-key realms respectively. The aim of this chapter is to establish the background against which the remainder of the thesis will be developed. In particular it intends to describe the theoretical framework, so far as is known, that has been used to design the DES and RSA algorithms. In the remainder of this thesis the author will be extending that analysis, ultimately using it to develop a new family of private key algorithms. As described earlier, encryption algorithms may be cata- gorised into two broad families. Private key (one-key) algorithms in which both sender and recipient share a com- mon secret key for both encryption and decryption; and public key (two-key) algorithms in which the sender uses a well known public encryption key, whilst the recipient uses a secret decryption key. These classes will be detailed separately. _2. _M_o_d_e_r_n _P_r_i_v_a_t_e-_K_e_y _C_r_y_p_t_o_g_r_a_p_h_y _2._1. _I_n_t_r_o_d_u_c_t_i_o_n With the advent of computers, data encryption schemes underwent a revolutionary change. The use of computers enabled the cracking of hitherto secure schemes, but also enabled the implementation of schemes which until then were too complex for use by a manual cipherclerk. Based on the work of Shannon [Sha49], a new family of cryptosys- tems, known as _S_u_b_s_t_i_t_u_t_i_o_n-_P_e_r_m_u_t_a_t_i_o_n _n_e_t_w_o_r_k_s were developed. These led to the development of a system known as LLLLuuuucccciiiiffffeeeerrrr, at the IBM Research Laboratories [Fei73], and subsequently to the DDDDaaaattttaaaa EEEEnnnnccccrrrryyyyppppttttiiiioooonnnn SSSSttttaaaannnnddddaaaarrrrdddd ((((DDDDEEEESSSS)))) 13 14 [NBS77]. DES has since achieved wide utilization, particu- larly in the banking and electronic funds transfer areas, where it is now a standard in a number of countries including the USA [NBS77], [Ins81], [AAA83], and Australia [ASA85]. _2._2. _F_u_n_d_a_m_e_n_t_a_l _C_o_n_c_e_p_t_s In designing cryptographic algorithms, there are two basic cryptographic primitives: _s_u_b_s_t_i_t_u_t_i_o_n and _t_r_a_n_s_p_o_s_i_t_i_o_n (or _p_e_r_m_u_t_a_t_i_o_n). In a substitution function, each char- acter is replaced by some other character (see example instance in Fig 2.1). FFFFiiiigggg 2222....1111 ---- SSSSuuuubbbbssssttttiiiittttuuuuttttiiiioooonnnn OOOOppppeeeerrrraaaattttiiiioooonnnn The particular substitution used is selected by some _k_e_y. If characters are represented by a small number of bits, then such a scheme may be defeated by enumerating all pos- sible cases to find the substitution used. If made suffi- ciently large and a suitably complex function is used, such a scheme is in practice unbreakable, since it would require the enumeration of all n! cases (where n is the number of possible characters). Unfortunately it is also unworkable, since the number of permutations, and hence keys, would be equally large. Traditionally, in a transposition function a set of char- acters were permuted (rearranged) into a new order, again with the particular rearrangement selected by some key. In modern implementations, this becomes a permutation of bits or a wire-crossing (see example instance in Fig 2.2). Chapter 2 15 FFFFiiiigggg 2222....2222 ---- PPPPeeeerrrrmmmmuuuuttttaaaattttiiiioooonnnn OOOOppppeeeerrrraaaattttiiiioooonnnn Since the complexity of such an operation is only linear in the number of bits used, it may be easily broken by testing each bit in turn to find its new location. It also implies that it is easy to build such a function for large numbers of bits. Because of these weaknesses in both the basic primitives, the concept of _p_r_o_d_u_c_t _c_i_p_h_e_r_s arose, whereby a series of substitution and transposition functions were combined to form a function which is much more secure than any of its components. Prior to the introduction of rotor machines, only simple product ciphers were possible. The develop- ment of rotor machines, and subsequently computers, changed this significantly. Shannon [Sha49], in a key paper, described a particular class of product ciphers which used a number of small (and hence implementable) substitution boxes, termed S-boxes, connected by large permutation boxes, termed P-boxes (see Fig 2.3). He termed these _m_i_x_i_n_g _t_r_a_n_s_f_o_r_m_a_t_i_o_n_s, whereby the S-boxes provided _c_o_n_f_u_s_i_o_n of the input, and the P- boxes provide _d_i_f_f_u_s_i_o_n of the S-box outputs across the inputs to the next stage. Such schemes are now termed _S_u_b_s_t_i_t_u_t_i_o_n-_P_e_r_m_u_t_a_t_i_o_n (_S-_P) _n_e_t_w_o_r_k_s. Chapter 2 16 FFFFiiiigggg 2222....3333 ---- SSSSaaaammmmpppplllleeee SSSS----PPPP NNNNeeeettttwwwwoooorrrrkkkk,,,, wwwwiiiitttthhhh AAAAvvvvaaaallllaaaannnncccchhhheeee CCCChhhhaaaarrrraaaacccctttteeeerrrriiiissssttttiiiicccc Two key properties of such S-P networks are the _a_v_a_l_a_n_c_h_e property, identified by Feistel [Fei73]; and the _c_o_m_p_l_e_t_e_- _n_e_s_s property, identified by Kam and Davida [KaD79]. The avalanche property states that changing one input bit should result in approximately half of the output bits changing. The completeness property states that each out- put bit must be a complex function of every input bit. These properties appear to be important criteria for pro- viding cryptographic strength in the resultant system. More formally, these are defined (see [WeT86]) as follows. A function f has a good _a_v_a_l_a_n_c_h_e effect if: m for each bit i, 0m_ +o and keeps secure the private key D = . Chapter 2 33 A sender can encrypt a message M (expressed as some large integer of a size less than the length of the modulus used in the system, and created by concatenating characters together to form a bit-string of the appropriate length) to form the ciphertext C using the public encryption key by calculating: C = Me (mod R), 0 _< C < R (Eq 2.8) The receiver can then decipher this using his private decryption key by calculating: M = Cd (mod R) (Eq 2.9) The system relies on the following well known number theoretic identity (Euler's generalization of Fermat's theorem): If GCD(X,R) = 1, (Eq 2.10) then XU(R) _= 1 (mod R) hence Cd = Med _= M1+nU(R) _= M1MnU(R) _= M1 _= M (mod R). RSA can also be used as a signature scheme since the encryption and decryption operations are commutative. That is, a sender can create a signature S for a message M using their private key (which only they have access to), by calculating: S = Md (mod R) (Eq 2.11) which may be verified by anyone using the sender's public key (obtained from the public directory), by calcu- lating: M = Se (mod R), (Eq 2.12) The signature can then be encrypted using the recipient's public key, in order to privately transfer it to the reci- pient. Chapter 2 34 _3._3._2. _R_S_A _W_e_a_k_n_e_s_s_e_s _a_n_d _R_e_l_a_t_e_d _S_c_h_e_m_e_s There is a minor problem known as the signature reblocking problem, which must be overcome when the same scheme is used for both secrecy and authentication. It occurs because each user has modulii R of different sizes, and hence a block of ciphertext in one user's field may not be a valid block in the other users field. This becomes a problem when user A signs a message for B, and then wishes to protect its privacy by encrypting with B's public key. If user A's field is larger than B's, and the signed mes- sage also turns out to be too large (ie R < S 24 bit 56 -> 48 bit 32 -> 24 bit 64 -> 48 bit Initially, a key schedule with the same form as the current DES was examined, in order that comparisons with the effectiveness of the current DES scheme could be made. Having obtained some guidelines from these trials, key schedules involving some of the alternatives were then tried. _6. _S_o_m_e _T_r_i_a_l_s _o_n _N_e_w _K_e_y _S_c_h_e_d_u_l_e_s In chapter 4, some empirical design criteria for permuta- tion PC2 and the Key Rotation Schedule were presented. The author has subsequently used these rules to generate a set of permutations PC2. Since all possible 28->24 bit permutations could not be tried, permutations with the form shown in Table 6.3 were tried (that is all arrange- ments of the 4 excluded bits in the fixed pattern of S- boxes, subject to the rules set, were found). This form was chosen in order to distribute key bits to each of the 4 S-boxes being fed by each half of the key schedule as quickly as possible, by the simple expediant of either sending each bit to the next S-box in turn or skipping it. This table lists which S-box each of the 28 bits in the C and D key halves is permuted to, if not skipped. A total of 7315 permutations were found. Chapter 6 87 ________________________________________________________________________________________ _|_________________T__TTTa__aaab__bbbl__llle__eee__6__666.__...3__333__-__---__F__FFFo__ooor__rrrm__mmm__o__ooof__fff__g__ggge__eeen__nnne__eeer__rrra__aaat__ttte__eeed__ddd__P__PPPe__eeer__rrrm__mmmu__uuut__ttta__aaat__ttti__iiio__ooon__nnns__sss__P__PPPC__CCC2__222_________________|_ |C: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 + X X X X | |D: 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8 + X X X X | _|_______________________________________________________________| Ciphertext-Key Dependences (CKdep) tests on these permuta- tions produced results shown in Table 6.4, column 4, with comparisons to the current and worst case PC2 supplied for comparison in columns 2 and 3. ____________________________________________________________________________________ | TTTTaaaabbbblllleeee 6666....4444 ---- DDDDeeeeppppeeeennnnddddeeeennnnccccyyyy ooooffff CCCCiiiipppphhhheeeerrrrtttteeeexxxxtttt bbbbiiiittttssss oooonnnn KKKKeeeeyyyy bbbbiiiittttssss | | UUUUssssiiiinnnngggg CCCCuuuurrrrrrrreeeennnntttt DDDDEEEESSSS PPPPeeeerrrrmmmmuuuuttttaaaattttiiiioooonnnn PPPP aaaannnndddd KKKKeeeeyyyy SSSScccchhhheeeedddduuuulllleeee | _|______________________________________________________________________________________________________________________________________________________________________|_ _|R_o_u_n_d__|__S_t_d__P_C_2__|__W_o_r_s_t__P_C_2__|__G_e_n_e_r_a_t_e_d__P_C_2__|__R_e_g_u_l_a_r__X__2__|___R_e_g_u_l_a_r__X__1_,__X__3_,__X__4__| | 1 | 5.36 | 5.36 | 5.36 | 5.36 | 5.36 | | 2 | 39.17 | 42.19 | 38.50-39.06 | 39.06 | 38.62 | | 3 | 82.25 | 81.47 | 80.25-82.37 | 82.37 | 81.47 | | 4 | 98.44 | 91.29 | 96.65-98.66 | 98.66 | 98.21 | | 5 | 100.00 | 96.21 | 99.55-100.00 | 100.00 | 100.00 | | 6 | 100.00 | 99.55 | 100.00 | 100.00 | 100.00 | | 7 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | | 8 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | _|______|__________|____________|________________|______________|_________________________| Some of these permutations performed better than the PC2 used in the current DES. The best of these were selected, 15 being found. These 15 permutations were all found to have a special form, namely that the excluded bits always fell between bits permuted to S-box 1 and S-box 2 (or 5 and 6 in the D-side). These will be termed the _R_e_g_u_l_a_r _X _62 permutations. There are exactly 15 of these, since 15 = C4 (ie the number of ways of placing the 4 excluded spots into the 6 occurences of the 1 2 3 4 regular patterns at the specified location (1 X 2 for example)). In order to investigate these permutations with a regular placing of the excluded bits, all 60 such permutations were gen- erated. A CKdep analysis of these permutations resulted in only two results, one for permutations with the excluded bit before a bit permuted to S-box 2 (Regular X 2), and one for the others (Regular X 1, X 3, X 4). These results are also shown in Table 6.4. The reason for this variation is unknown to the author at present, as is its signifi- cance, if any, from a cryptographic point of view. So far, we have used the first of the two criteria presented earlier, namely the growth of overall bit depen- dence of output bits on key bits. If we now consider the alternate measure, namely growth in dependence of output Chapter 6 88 bits on key bits by both message and autoclave S-box inputs, then the results become less clear. As shown in Table 6.5, whilst growth of overall dependence is greater with the regular PC2's, growth of both is worse. ___________________________________________________________________________________________________________________________ | TTTTaaaabbbblllleeee 6666....5555 ---- DDDDeeeeppppeeeennnnddddeeeennnnccccyyyy ooooffff CCCCiiiipppphhhheeeerrrrtttteeeexxxxtttt bbbbiiiittttssss oooonnnn KKKKeeeeyyyy bbbbiiiittttssss | | UUUUssssiiiinnnngggg CCCCuuuurrrrrrrreeeennnntttt DDDDEEEESSSS PPPPeeeerrrrmmmmuuuuttttaaaattttiiiioooonnnn PPPP aaaannnndddd KKKKeeeeyyyy SSSScccchhhheeeedddduuuulllleeee | _|_______________________________________________________________________________b__bbby__yyy__B__BBBo__ooot__ttth__hhh__M__MMMe__eees__ssss__sssa__aaag__ggge__eee__a__aaan__nnnd__ddd__A__AAAu__uuut__ttto__oooc__cccl__llla__aaav__vvve__eee__S__SSS-__---b__bbbo__ooox__xxx__I__IIIn__nnnp__pppu__uuut__ttts__sss_________________________________________________________________________________|_ |Round || 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | _|__________||______________|______________|______________|______________|______________|______________|______________|______________| _|C_K_d_e_p______||__B_o_t_h_,_E_i_t_h_e_r__|__B_o_t_h_,_E_i_t_h_e_r__|__B_o_t_h_,_E_i_t_h_e_r__|__B_o_t_h_,_E_i_t_h_e_r__|__B_o_t_h_,_E_i_t_h_e_r__|__B_o_t_h_,_E_i_t_h_e_r__|__B_o_t_h_,_E_i_t_h_e_r__|__B_o_t_h_,_E_i_t_h_e_r__| |PC2.std || 0.0,5.36 | 2.01,39.17 | 36.50,82.25| 81.03,98.44| 95.87,100.0| 99.33,100.0| 100.0,100.0| 100.0,100.0| |PC2.worst|| 0.0,5.36 | 0.0,42.19 | 33.71,81.47| 73.88,91.29| 84.38,96.21| 92.86,99.55| 98.66,100.0| 100.0,100.0| |PC2 X 1 || 0.0,5.36 | 0.22,38.62 | 29.91,81.47| 65.07,98.21| 73.66,100.0| 80.13,100.0| 87.28,100.0| 93.97,100.0| |PC2 X 2 || 0.0,5.36 | 0.45,39.06 | 30.36,82.37| 67.08,98.66| 77.01,100.0| 83.26,100.0| 90.18,100.0| 95.87,100.0| |PC2 X 3 || 0.0,5.36 | 0.45,39.06 | 30.13,81.92| 66.74,98.21| 76.79,100.0| 83.04,100.0| 89.96,100.0| 95.76,100.0| |PC2 X 4 || 0.0,5.36 | 0.45,39.06 | 30.13,81.92| 66.52,98.21| 75.67,100.0| 80.36,100.0| 86.38,100.0| 92.41,100.0| _|__________||______________|______________|______________|______________|______________|______________|______________|______________| A closer look at the structure of the regular permutations shows that the autoclave input bits are clustered, due to the method used to assign them to S-box inputs. By alter- ing the order of inputs within each S-box, a more regular arrangement of autoclave inputs was obtained. When these were tested, the growth of dependence on both was much greater, thus emphasizing the importance of this criterion on the design of PC2. To obtain an indication of the relative influences of each of the components in the key schedule, a series of 40 tri- als were run, in which each of the following three com- ponents were varied with the specified alternatives: P based on the results in [BrS90a], two permutations P were used: +o the current DES P and +o a strictly regular permutation generated by a difference function on the S-box number of [+1 - 2 +3 +4 +2 -1]. Because of its very regular struc- ture, the propagation of dependencies may be more easily calculated. PC2 from the above work, the 4 best performing regular PC2 were extracted. Then these were processed to provide three levels of clustering of the autoclave inputs. Chapter 6 89 KS the key variant in the key rotation schedule appears to be the distribution of shifts of 1 verses 2 places. A set of 5 key schedules with various numbers of shifts of 1 initially were derived as shown in Table 6.6. ________________________________________________ |________________T__TTTa__aaab__bbbl__llle__eee__6__666.__...6__666__-__---__T__TTTr__rrri__iiia__aaal__lll__K__KKKe__eeey__yyy__S__SSSc__ccch__hhhe__eeed__dddu__uuul__llle__eees__sss_________________|_ | Round|| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16| |_____________||__________________________________________________________________________________|_ | KS || 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 | | KS || 1 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 | | KS || 1 1 2 2 2 2 2 2 2 2 2 2 2 2 1 1 | | KS || 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 1 | ||_K_S_____||__1__1__1__1__2__2__2__2__2__2___2___2___2___2___2___2___|| When this test was run, the following conclusions were made: +o the current permutation P performed slightly better (though only in minor percentage values, not in the number of rounds needed to achieve full dependence) than the strictly regular permutation. This was pos- sibly because its less than regular structure assisted the distribution of dependencies between the autoclave and message inputs. +o the permutations PC2 with the best spread of auto- clave inputs, performed best as expected. +o a key schedule with as many shifts of 1 initially performed best. This again would appear to be a func- tion of the best method for spreading bits to as many S-box inputs as soon as possible. _7. _D_e_s_i_g_n _C_r_i_t_e_r_i_a _f_o_r _N_e_w _K_e_y _S_c_h_e_d_u_l_e_s From the above results, the design principles for design- ing key schedules can now be summarised as follows: The key schedule ensures that: +o KS1 each key bit is used as input to each S-box in turn +o KS2 no bit is used as autoclave inputs on successive rounds Chapter 6 90 +o KS3 no bit is excluded on successive rounds +o KS4 the final key register value is identical to the ori- ginal key register value (to enable easy reversal of the key schedule for decryption) _8. _A_n _A_l_t_e_r_n_a_t_i_v_e _K_e_y _S_c_h_e_d_u_l_e _D_e_s_i_g_n In the design of the DES, small key rotations were used, which required the use of permutation PC2 to provide a fan-out of key-bits across the S-box inputs, in order to satisfy the above principles (especially KS1). An alter- native design can be envisaged in which a large key rota- tion interval is used, along with a null PC2 (ie: so called worst case or straight through PC2), or a local PC2 which only permutes bits within each block of 6 S-box inputs. Two such PC2 permutations tested are shown in Table 6.7. The * in the table indicates a bit permuted to an autoclave input of an S-box, otherwise the bit is per- muted to a message input. The autoclave inputs are assumed to be bits 1 and 6 (as in the DES) of each S-box. The 4 excluded bits are left at the end. This causes no prob- lems, since the key rotation used of 7 places ensures that principle KS3 is satisfied. ____________________________________________________________________ | TTTTaaaabbbblllleeee 6666....7777 ---- NNNNuuuullllllll aaaannnndddd LLLLooooccccaaaallll PPPPeeeerrrrmmmmuuuuttttaaaattttiiiioooonnnnssss PPPPCCCC2222 | _|_______________________________________f__fffo__ooor__rrr__A__AAAl__lllt__ttte__eeer__rrrn__nnna__aaat__ttti__iiiv__vvve__eee__K__KKKe__eeey__yyy__S__SSSc__ccch__hhhe__eeed__dddu__uuul__llle__eee_______________________________________|_ |C: 1* 1 1 1 1 1* 2* 2 2 2 2 2* 3* 3 3 3 3 3* 4* 4 4 4 4 4* X X X X| |D: 5* 5 5 5 5 5* 6* 6 6 6 6 6* 7* 7 7 7 7 7* 8* 8 8 8 8 8* X X X X| _|___________________________________________________________________| |C: 1* 1 1 1 1 1* 2 2 2 2* 2* 2 3 3* 3* 3 3 3 4* 4 4 4 4 4* X X X X| _||D_:__5_*__5__5__5__5__5_*__6__6__6__6_*__6_*__6__7__7_*__7_*__7__7__7__8_*__8__8__8__8__8_*__X__X__X__X__|| For these tests, a constant key rotation of 7 bits was used, both because it is larger than the number of inputs to an S-box, and because after sixteen rounds, the key register contents are the same as the original value (since 7*16=112=4*28=2*56), for both split key registers or a single large key register. This key rotation schedule is shown in Table 6.8. ________________________________________________________ |__T__TTTa__aaab__bbbl__llle__eee__6__666.__...8__888__-__---__A__AAAl__lllt__ttte__eeer__rrrn__nnna__aaat__ttti__iiiv__vvve__eee__C__CCCo__ooon__nnns__ssst__ttta__aaan__nnnt__ttt__K__KKKe__eeey__yyy__R__RRRo__ooot__ttta__aaat__ttti__iiio__ooon__nnn__S__SSSc__ccch__hhhe__eeed__dddu__uuul__llle__eee_|_ | Round || 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16| |_______________||________________________________________________________________________________________________|_ ||_K_S______||_7___7__7___7__7___7__7___7__7___7____7___7____7___7____7___7___|| Chapter 6 91 The results obtained for these PC2 permutations and this key schedule, using both a split key rotation register, and a single key register, are shown in Table 6.9. _______________________________________________________________________________________________________________________ | TTTTaaaabbbblllleeee 6666....9999 ---- DDDDeeeeppppeeeennnnddddeeeennnnccccyyyy ooooffff CCCCiiiipppphhhheeeerrrrtttteeeexxxxtttt bbbbiiiittttssss oooonnnn KKKKeeeeyyyy bbbbiiiittttssss | | UUUUssssiiiinnnngggg CCCCuuuurrrrrrrreeeennnntttt DDDDEEEESSSS PPPPeeeerrrrmmmmuuuuttttaaaattttiiiioooonnnn PPPP aaaannnndddd tttthhhheeee AAAAlllltttteeeerrrrnnnnaaaattttiiiivvvveeee KKKKeeeeyyyy SSSScccchhhheeeedddduuuulllleeee | _|___________________________________________________________________________b__bbby__yyy__B__BBBo__ooot__ttth__hhh__M__MMMe__eees__ssss__sssa__aaag__ggge__eee__a__aaan__nnnd__ddd__A__AAAu__uuut__ttto__oooc__cccl__llla__aaav__vvve__eee__S__SSS-__---b__bbbo__ooox__xxx__I__IIIn__nnnp__pppu__uuut__ttts__sss_____________________________________________________________________________|_ |Round|| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | _|______||______________|______________|______________|______________|______________|______________|______________|______________| _|P_C_2___|_|__B_o_t_h_,_E_i_t_h_e_r_|___B_o_t_h_,_E_i_t_h_e_r_|___B_o_t_h_,_E_i_t_h_e_r_|___B_o_t_h_,_E_i_t_h_e_r_|___B_o_t_h_,_E_i_t_h_e_r_|___B_o_t_h_,_E_i_t_h_e_r_|___B_o_t_h_,_E_i_t_h_e_r_|___B_o_t_h_,_E_i_t_h_e_r__| | SSSSpppplllliiiitttt KKKKeeeeyyyy RRRReeeeggggiiiisssstttteeeerrrr UUUUsssseeeedddd | _|______________________________________________________________________________________________________________________| |null || 0.0,5.36 | 1.56,39.06 | 34.82,82.03| 76.56,98.33| 91.52,100.0| 98.21,100.0| 100.0,100.0| 100.0,100.0| _|l_o_c_a_l_|_|___0_._0_,_5_._3_6___|___2_._5_7_,_3_9_._0_6__|___3_8_._1_7_,_8_2_._0_3_|___8_3_._8_2_,_9_8_._3_3_|___9_8_._2_1_,_1_0_0_._0_|___1_0_0_._0_,_1_0_0_._0_|___1_0_0_._0_,_1_0_0_._0_|___1_0_0_._0_,_1_0_0_._0__| | SSSSiiiinnnngggglllleeee KKKKeeeeyyyy RRRReeeeggggiiiisssstttteeeerrrr UUUUsssseeeedddd | _|______________________________________________________________________________________________________________________| |null || 0.0,5.36 | 1.79,38.73 | 35.04,81.70| 76.56,98.33| 91.52,100.0| 98.21,100.0| 100.0,100.0| 100.0,100.0| _||l_o_c_a_l__||||___0_._0_,_5_._3_6____||__2_._7_9_,_3_8_._7_3___||__3_8_._3_9_,_8_1_._7_0__||__8_3_._8_2_,_9_8_._3_3__||__9_8_._2_1_,_1_0_0_._0__||__1_0_0_._0_,_1_0_0_._0__||__1_0_0_._0_,_1_0_0_._0__||__1_0_0_._0_,_1_0_0_._0__|| These results are very similar in performance to the key schedule used in the current DES (see Table 6.5). The null PC2 performs slightly worse in growth of dependencies via both autoclave and message inputs than the local PC2. Depending on the efficiency required, a tradeoff between best performance and ease of implementation can be made between these. There is very little difference in perfor- mance between the split and single key rotation registers, thus either could be chosen, depending on other con- straints. This may be explained by realising that depen- dencies grow both via the inputs from the key schedule, as well as via the message paths in the cipher. The single and split key schedules are identical for the first 4 rounds, and only differ from then on. However after 4 rounds nearly all output bits already have a dependency on most input bits, and hence the differing key schedules have little effect after that point in this analysis. _9. _C_o_n_c_l_u_s_i_o_n The key schedule in the current DES has been analysed, and some empirical principles which could have been used in its design derived. These were used to test a number of alternative key schedules, which led to the development of a new set of generalised principles to be used in the design of a new algorithm. An alternative key schedule which either eliminates permutation PC2, or uses a local PC2, was tried and found to be as effective as that used in the current DES. These generalised rules will be used Chapter 6 92 in the design of the LOKI family of ciphers, descibed in the next chapter. Chapter 6 CCCCHHHHAAAAPPPPTTTTEEEERRRR 7777 LLLLOOOOKKKKIIII ---- AAAA CCCCrrrryyyyppppttttooooggggrrrraaaapppphhhhiiiicccc PPPPrrrriiiimmmmiiiittttiiiivvvveeee ffffoooorrrr AAAAuuuutttthhhheeeennnnttttiiiiccccaaaattttiiiioooonnnn aaaannnndddd SSSSeeeeccccrrrreeeeccccyyyy AAAApppppppplllliiiiccccaaaattttiiiioooonnnnssss _1. _I_n_t_r_o_d_u_c_t_i_o_n This chapter provides an overview of the LOKI[1] encryp- tion primitive which may be used to encrypt and decrypt a 64-bit block of data using a 64-bit key. This is the main achievement of this thesis. Although some of the earlier work was directed toward the design of a cipher with 128- bit data and keys, in the short term there was consider- able interest in the design of ciphers which were compati- ble with the existing DES ciper. Thus a cipher with a full 64-bit key was the first to be designed using the principles identified. The author intends to extend this work to a cipher with 128-bit data and keys in the near future. The LOKI cipher is the first of an extensible family of encryption algorithms. These algorithms all share the same overall structure, but allow the substitu- tion and permutation functions, central to the security of the schemes, to be tailored to permit the design of private ciphers. The design of the LOKI primitive is based on the detailed analysis of the DES described in the previous chapters, and in [Bro89], [BrS90a], [BrS90b], and on the work of Pieprzyk on the design of good substitution functions with high non-linearity [PiF89], [Pie90], [Pie89], [PiS89]. Its overall structure has a broad resemblance to DES (see Fig 7.1), however the detailed structure has been designed to remove operations which impede analysis or hinder effi- cient implementation, but which do not add to the crypto- graphic security of the algorithm. ____________________ [1] LOKI - God of mischief and trickery in Scandinavian mythology. "He is handsome and well made, but of a very fickle mood and most evil disposition. He is of the giant race, but forced himself into the company of the gods, and seems to take pleasure in bringing them into difficulties, and in extracting them out of the danger by his cunning, wit and skill" [Bulfinch's Mythology, Avenel Books, NY 1978]. 93 94 The LOKI primitive may be used in any mode of operation currently defined for DES, with which it is interface com- patible [AAA83]. Also described are two modes of opera- tion of the LOKI primitive which compute a 64-bit, and 128-bit, Message Authentication Code (or hash value) respectively, from an arbitrary length of message input. The modes of use are modifications of those described in [DaP89], [Win83], and [QuG90]. These modes of operation may be used to provide authentication of a communications session, or of data files held on a computer system. The LOKI encryption primitive, and the above modes of use have been submitted to the European RIPE project [VCF90], Standards Australia, and the Defence Signals Directorate, for evaluation. This chapter will first present the LOKI cipher as currently specified, and will then examine the detailed design choices in its definition. _1._1. _O_v_e_r_v_i_e_w LOKI is a family of ciphers designed to encrypt and decrypt blocks of data consisting of 64 bits, under con- trol of a 64-bit key. This chapter defines a common vari- ant of the algorithm for use when compatibility between implementations is required. The same structure, but with alternate substitution functions may be used to build private variants of this algorithm. The same key is used for both encryption and decryption, but with the schedule of addressing the key bits altered so that the decryption process is the reverse of the encryption process. A block to be encrypted is added modulo 2 to the key, is then pro- cessed in 16 rounds of a key-dependent computation, and finally is added modulo 2 to the key again. The key- dependent computation can be defined in terms of a confusion-diffusion function f, and a key schedule KS. Descriptions of the encryption operation, the decryption operation, and the definition of the function f, are pro- vided in the following sections. The representation of the keys, key values to be avoided and guidelines for the con- struction of alternate private ciphers, and full results for the tests conducted to date on LOKI, are subsequently described. Chapter 7 95 FFFFiiiigggg 7777....1111 ---- LLLLOOOOKKKKIIII EEEEnnnnccccrrrryyyyppppttttiiiioooonnnn CCCCoooommmmppppuuuuttttaaaattttiiiioooonnnn _1._2. _E_n_c_r_y_p_t_i_o_n The encryption computation is illustrated in Fig 7.1. The 64 bits of the input block to be encrypted are added modulo 2 to the key, processed in 16 rounds of a complex Chapter 7 96 key-dependent computation, and finally added modulo 2 to the key again. In detail, the 64-bit input block X is partitioned into two 32-bit blocks XL and XR. Similarly, the 64-bit key is partitioned into two 32-bit blocks KL and KR. Correspond- ing halves are added together modulo 2, to form the ini- tial left and right halves for the following 16 rounds, thus: L = XL XOR KL KL = KL (Eq 7.1) 0 0 0 R = XR XOR KR KR = KR 0 0 0 The complex key-dependent computation consists (except for a final interchange of blocks) of 16 rounds (iterations) of a set of operations. Each iteration includes the cal- culation of the encryption function f. This is a concate- nation of a modulo 2 addition and three functions E, S, and P. Function f takes as input the 32-bit right data half R and the 32-bit left key half KL produced by the key sic-h1edule KS (denoted K below), andiwhich produces a 32-bit result which is addedimodulo 2 to the left data half L . The two data halves are then interchanged (exceptia-ft1er the last round). Each round may thus be characterised as: L = R i i-1 R = L XOR f(R , KL ) (Eq 7.2) i i-1 i-1 i f(R K ) = P(S(E(R XOR K ))) i-1, i i-1 i The component functions E, S, and P are described later. The key schedule KS is responsible for deriving the sub- keys K , and is defined as follows: the 64-bit key K is partitiioned into two 32-bit halves KL and KR. In each round i, the sub-key K is the current left half of the key KL . This half is tihen rotated 12 bits to the left, and tih-e1 key halves are interchanged. This may be defined thus: K = KL i i-1 KL = KR (Eq 7.3) i i-1 Chapter 7 97 KR = ROL(KL 12) i i-1, Finally after the 16 rounds, the other key halves are added modulo 2 to the data halves to form two output block halves YL and YR which are then concatenated together to form the output block Y. This is defined as follows (note the swap of data and key halves to undo the final inter- change in (Eq 7.2) and (Eq 7.3)): YL = R XOR KR 16 16 YR = L XOR KL (Eq 7.4) 16 16 Y = YL | YR _1._3. _D_e_c_r_y_p_t_i_o_n The decryption computation is identical to that used for encryption, save that the partial keys used as input to the function f in each round are calculated in reverse order, and the initial and final additions of key to data modulo 2 use the opposite halves of the key (interchange KL and KR in (Eq 7.1) and KL and KR in (Eq 7.3)). Th0e calculat0ion of the partial ke1y6s for 1d6ecryption con- sists of first exchanging key halves, then rotating the left half 12 bits to the right, and then using the left half as the partial key. This is defined as: KR = KL i i-1 KL = ROR(KR 12) (Eq 7.5) i i-1, K = KL i i _1._4. _F_u_n_c_t_i_o_n f The encryption function f is a concatenation of a modulo 2 addition and three functions E, S, and P, which takes as input the 32-bit right data half R and the 32-bit left key half KL , and produces a 32-bii-t1result which is added modulo 2 to ithe left data half L . This is shown in Fig 7.2, and is defined thus: i-1 f(R K ) = P(S(E(R XOR K ))) (Eq 7.6) i-1, i i-1 i Chapter 7 98 The modulo 2 addition of the key and data halves ensures that the output of f will be a complex function of both of these values. The expansion function E takes a 32-bit input and produces a 48-bit output block, composed of four 12-bit blocks which form the inputs to four S-boxes in function f. Func- tion E selects consecutive blocks of twelve bits as inputs to S-boxes S(4), S(3), S(2), and S(1) respectively, as follows: [b b ... b b b ... b ] [b3 2b ...0b 31] 30 24 [b27 b26 ... b16] [b19 b18 ... b8] 11 10 0 This is shown in Table 7.1 in full. ___________________________________________________________ | TTTTaaaabbbblllleeee 7777....1111 ---- LLLLOOOOKKKKIIII EEEExxxxppppaaaannnnssssiiiioooonnnn FFFFuuuunnnnccccttttiiiioooonnnn E | | | _|_____s__o__u__r__c__e____b__i__t____f__o__r____o__u__t__p__u__t____b__i__t__s____4__7____d__o__w__n____t__o____0____r__e__s__p__e__c__t__i__v__e__l__y_________|_ |3 2 1 0 31 30 29 28 27 26 25 24| |27 26 25 24 23 22 21 20 19 18 17 16| |19 18 17 16 15 14 13 12 11 10 9 8 | |11 10 9 8 7 6 5 4 3 2 1 0 | _|__________________________________________________________| FFFFiiiigggg 7777....2222 ---- LLLLOOOOKKKKIIII FFFFuuuunnnnccccttttiiiioooonnnn _f Detail Chapter 7 99 The substitution function S provides the confusion com- ponent in the LOKI cipher. It takes a 48-bit input and produces a 32-bit output. It is composed of four S-boxes, each of which takes a 12-bit input and produces an 8-bit output, which are concatenated together to form the 32-bit output of S. The 8-bit output from S(4) becomes the most significant byte (bits [31...24]), then the outputs from S(3) (bits[23...16]), S(2) (bits[15...8]), and S(1) (bits [7...0]). In this version, the four S-boxes are identi- cal. The form of each S-box is shown in Fig 7.3. The 12- bit input is partitioned into two segments: a 4-bit row value r formed from bits [b b b b ], and an 8-bit column value c formed from bit1s1 [1b0 b1 .0.. b b . The row value r is used to select one o9f 186 S-fun3cti2o]ns Sfn , which then take as input the column value c and produce ran 8-bit output value. This is defined as: er (E8q 7.7) Sfnr = (c XOR r) mod genr, in GF(2 ) 8 where genr is an irreducible polynomial in GF(2 ), and er is the exponent used in forming the rth S-box. The gen- erators and exponents to be used in the 16 S-functions Sfnr in the standard LOKI are specified in Table 7.2. ___________________________________________ | TTTTaaaabbbblllleeee 7777....2222 ---- LLLLOOOOKKKKIIII SSSS----bbbbooooxxxx | | IIIIrrrrrrrreeeedddduuuucccciiiibbbblllleeee PPPPoooollllyyyynnnnoooommmmiiiiaaaallllssss[[[[2222]]]] aaaannnndddd EEEExxxxppppoooonnnneeeennnnttttssss | | | |_____________________________________________________________________________________|_ |_______R_o_w_________||________g_e_n_r_________|__e_r__| | 0 || 375 | 31| | 1 || 379 | 31| | 2 || 391 | 31| | 3 || 395 | 31| | 4 || 397 | 31| | 5 || 415 | 31| | 6 || 419 | 31| | 7 || 425 | 31| | 8 || 433 | 31| | 9 || 445 | 31| | 10 || 451 | 31| | 11 || 463 | 31| | 12 || 471 | 31| | 13 || 477 | 31| | 14 || 487 | 31| | 15 || 499 | 31| |__________________||____________________|_____| Chapter 7 100 The permutation function P provides diffusion of the out- puts from the four S-boxes across the inputs of all S- boxes in the next round. It takes the 32-bit concatenated outputs from the S-boxes, and distributes them over all the inputs for the next round via a regular permutation which takes bits from the outputs of each S-box in turn, as defined in Table 7.3. ______________________________________________________ | TTTTaaaabbbblllleeee 7777....3333 ---- LLLLOOOOKKKKIIII PPPPeeeerrrrmmmmuuuuttttaaaattttiiiioooonnnn PPPP | | | |__s__o__u__r__c__e____b__i__t____f__o__r____o__u__t__p__u__t____b__i__t__s____3__1____d__o__w__n____t__o____0____r__e__s__p__e__c__t__i__v__e__l__y___|_ | 0 8 16 24 1 9 17 25| | 2 10 18 26 3 11 19 27| | 4 12 20 28 5 13 21 29| | 6 14 22 30 7 15 23 31| |______________________________________________________| FFFFiiiigggg 7777....3333 ---- LLLLOOOOKKKKIIII SSSS----BBBBooooxxxx DDDDeeeettttaaaaiiiillll _2. _D_e_s_i_g_n _P_h_i_l_o_s_o_p_h_y _2._1. _O_v_e_r_a_l_l _L_O_K_I _A_l_g_o_r_i_t_h_m _D_e_s_i_g_n The development of LOKI was motivated by the need to develop an alternative to DES for the provision of secrecy and authentication services in a range of applications, including electronic messaging, EDI, EFT, and others. ____________________ [2] The column genr is a decimal representation of the binar8y string which defines the generator polynomial in GF(2 ), the field used in the S-box function calculations. Chapter 7 101 A major requirement in the short term was for LOKI to be interface compatible with DES, so that it could be used as a replacement in services based on it. The same design principles are being used in the development of a future 128-bit version of the algorithm. LOKI is a Feistel type cipher [Fei73], a form of _S_u_b_s_t_i_t_u_t_i_o_n-_P_e_r_m_u_t_a_t_i_o_n (_S-_P) _n_e_t_w_o_r_k originally described by Shannon [Sha49]. This family of ciphers include Lucifer [Sor84], and of course ISO DEA-1 or DES [Ins81]. As stated previously in Chapter 2, two key properties of such S-P networks are the _a_v_a_l_a_n_c_h_e property [Fei73]; and the _c_o_m_p_l_e_t_e_n_e_s_s property [KaD79]. The _a_v_a_l_a_n_c_h_e _p_r_o_p_e_r_t_y states that changing one input bit should result in approximately half of the output bits changing. The _c_o_m_- _p_l_e_t_e_n_e_s_s _p_r_o_p_e_r_t_y states that each output bit must be a complex function of every input bit. These properties appear to be important criteria for providing crypto- graphic strength in the resultant system, and the provi- sion of them was the primary design criterion used in the design of LOKI. More formally, these properties may be defined [WeT86] [Llo90] as follows. A function f has a good _a_v_a_l_a_n_c_h_e effect if: for each bit i, 0_ 0 for all i, i_=16 chi^2 gaps 4070 2076 1022 520 261 134 58 18 17 7 0 1 0 0 7 1 13.51 blocks 4081 2063 1042 480 268 135 57 35 15 7 4 2 1 0 0 1 4.37 mean 4095 2048 1024 511 255 127 63 32 15 7 4 2 1 0 0 0 8184.00 Appendix A 135 Streamstat analysis on S-box for input bit 0 set true ss: 16384 0.000 0.018 3.453 0.000 0.000 6.621 4.730 Streamstat analysis on S-box for input bit 1 set true ss: 16384 0.000 0.045 2.028 0.000 0.000 15.636 9.738 Streamstat analysis on S-box for input bit 2 set true ss: 16384 0.562 -0.015 10.582 6.344 123.250 12.442 7.671 Streamstat analysis on S-box for input bit 3 set true ss: 16384 0.191 0.117 12.562 8.281 129.000 10.937 2.355 Streamstat analysis on S-box for input bit 4 set true ss: 16384 1.266 0.347 12.028 8.688 127.500 13.198 6.610 Streamstat analysis on S-box for input bit 5 set true ss: 16384 0.000 0.114 5.632 4.844 121.000 7.747 17.444 Streamstat analysis on S-box for input bit 6 set true ss: 16384 4.254 0.897 5.260 10.906 151.000 9.562 13.566 Streamstat analysis on S-box for input bit 7 set true ss: 16384 0.141 0.018 5.834 9.500 130.000 16.927 10.055 Streamstat analysis on S-box for input bit 8 set true ss: 16384 2.250 0.002 5.394 6.250 135.750 13.665 11.307 Streamstat analysis on S-box for input bit 9 set true ss: 16384 1.891 2.511 5.512 9.812 130.000 21.280 10.513 Streamstat analysis on S-box for input bit 10 set true ss: 16384 0.000 0.084 2.474 0.000 0.000 17.074 8.891 Streamstat analysis on S-box for input bit 11 set true ss: 16384 0.000 0.006 9.767 0.000 0.000 12.108 5.660 Streamstat analysis on S-box for output bit 0 over all inputs ss: 4096 0.000 1.166 3.418 14.344 294.000 5.097 8.305 Streamstat analysis on S-box for output bit 1 over all inputs ss: 4096 0.000 5.283 13.088 15.312 271.000 5.894 12.999 Streamstat analysis on S-box for output bit 2 over all inputs ss: 4096 0.000 0.912 5.512 5.281 251.000 13.358 12.166 Streamstat analysis on S-box for output bit 3 over all inputs ss: 4096 0.000 0.498 1.829 10.969 266.000 14.383 4.480 Streamstat analysis on S-box for output bit 4 over all inputs ss: 4096 0.000 0.638 2.924 14.625 240.000 3.034 3.506 Appendix A 136 Streamstat analysis on S-box for output bit 5 over all inputs ss: 4096 0.000 0.853 4.335 9.125 264.000 7.146 16.126 Streamstat analysis on S-box for output bit 6 over all inputs ss: 4096 0.000 0.044 5.606 12.406 208.000 6.077 18.239 Streamstat analysis on S-box for output bit 7 over all inputs ss: 4096 0.000 0.091 7.818 6.812 260.000 6.689 7.099 Appendix A AAAAPPPPPPPPEEEENNNNDDDDIIIIXXXX BBBB DDDDeeeeppppeeeennnnddddeeeennnnccccyyyy AAAAnnnnaaaallllyyyyssssiiiissss PPPPrrrrooooggggrrrraaaammmmssss _1. _c_p__d_e_p._c /* * _c_p _d_e_p._c - _b_u_i_l_d _d_e_p_e_n_d_e_n_c_y _m_a_t_r_i_x _f_o_r _e_a_c_h _c_i_p_h_e_r_t_e_x_t _b_i_t, _b_a_s_e_d _o_n * - _p_l_a_i_n_t_e_x_t _b_i_t_s, _f_o_r _a _g_i_v_e_n _P (_a_s_s_u_m_i_n_g _S-_b_o_x_e_s * _d_o _t_h_e_i_r _t_h_i_n_g, _a_n_d _t_h_a_t _t_h_e_i_r _o_u_t_p_u_t_s _a_r_e _e_q_u_i_v_a_l_e_n_t) * * _L_a_w_r_e_n_c_e _B_r_o_w_n <_l_p_b@_c_s._a_d_f_a._o_z> */ ####iiiinnnncccclllluuuuddddeeee ####ddddeeeeffffiiiinnnneeee HSIZE 32 ####ddddeeeeffffiiiinnnneeee FSIZE (2 * HSIZE) cccchhhhaaaarrrr *name = "cp dep"; /* _p_r_o_g_r_a_m _n_a_m_e */ cccchhhhaaaarrrr *depnam = "-CPdep"; /* _d_e_p_e_n_d_e_n_c_y _f_l_a_g _n_a_m_e _s_e_n_t _t_o _o_u_t_p_u_t _f_i_l_e */ cccchhhhaaaarrrr *usage = "[-vV] [-dD] [-rR rounds] [-P P values] "; /* _u_s_a_g_e _s_t_r_i_n_g */ - iiiinnnntttt P[HSIZE] = {{{{4, 2, 5, 6, 8, 3, 7, 5, 1, 4, 6, 7, 2, 5, 8, 3, 1, 2, 6, 4, 8, 7, 1, 3, 5, 4, 8, 2, 6, 3, 1, 7}}}}; /* _P_e_r_m_u_t_a_t_i_o_n _m_a_t_r_i_x _b_y _w_h_i_c_h _S-_b_o_x _i_n_p_u_t _b_i_t _i_s _f_r_o_m */ iiiinnnntttt G[FSIZE][FSIZE]; /* _d_e_p_e_n_d_e_n_c_y _m_a_t_r_i_x _G[_i][_j] _g_i_v_e_s _d_e_p _o_f _i _o_n _j */ iiiinnnntttt sp, /* _n_u_m_b_e_r _o_f _b_i_t_s _i_n _G _w_i_t_h _n_o _d_e_p_e_n_d_e_n_c_y */ me, /* _m_e_s_s_a_g_e _o_n_l_y _d_e_p_e_n_d_e_n_c_y */ ac, /* _a_u_t_o_c_l_a_v_e _o_n_l_y _d_e_p_e_n_d_e_n_c_y */ bt, /* _b_o_t_h _m_e_s_s_a_g_e & _a_u_t_o_c_l_a_v_e _d_e_p_e_n_d_e_n_c_y */ tot, /* _p_e_r_c_e_n_t_a_g_e _o_f _b_i_t_s _w_i_t_h _a _d_e_p_e_n_d_e_n_c_y */ err; /* _n_u_m_b_e_r _w_i_t_h _b_a_d _s_p_e_c_i_f_i_c_a_t_i_o_n */ iiiinnnntttt verbose = 0; /* _v_e_r_b_o_s_e _o_u_t_p_u_t _f_l_a_g */ 137 138 iiiinnnntttt dstat= 0; /* _p_r_i_n_t _d_e_t_a_i_l_e_d _s_t_a_t_s (_b_u_t _l_e_s_s _t_h_a_n _v_e_r_b_o_s_e) _f_l_a_g */ iiiinnnntttt pboth= 0; /* _p_r_i_n_t % _o_f _B_O_T_H _m_s_g+_a_u_t_o & _O_v_e_r_a_l_l _d_e_p_e_n_d_e_c_y */ iiiinnnntttt maxrounds = 8; /* _n_u_m_b_e_r _o_f _r_o_u_n_d_s _t_o _a_n_a_l_y_s_e */ cccchhhhaaaarrrr disp[4] = {{{{' ', 'x', '-', '*'}}}}; /* _d_i_s_p_l_a_y _c_h_a_r _f_o_r _e_a_c_h _c_l_a_s_s */ main(argc, argv) _m_a_i_n iiiinnnntttt argc; cccchhhhaaaarrrr **argv; {{{{ iiiinnnntttt i; init(argc, argv); prP(); G init(); iiii-ffff (verbose) printf("Round 1:"); eeeellllsssseeee printf("%s: ", depnam); scanG(); iiiiffff (verbose) prG(); ffffoooorrrr (i=2; i<=maxrounds; i++){{{{ nextG(); iiiiffff (verbose) printf("Round %d:", i); scanG(); iiiiffff (verbose) prG(); }}}} printf("\n"); }}}} G init() {{{{- iiiinnnntttt i, j, pbase; /* _c_l_e_a_r _G, _n_b _L_L _i_s _0 */ ffffoooorrrr (i=0; i 0 ) {{{{ iiiiffff ( (*argv)[0] == '-' ) sssswwwwiiiittttcccchhhh ( (*argv)[1] ) {{{{ ccccaaaasssseeee 'v': ccccaaaasssseeee 'V': verbose++; argv++; bbbbrrrreeeeaaaakkkk; ccccaaaasssseeee 'b': ccccaaaasssseeee 'B': pboth++; argv++; bbbbrrrreeeeaaaakkkk; ccccaaaasssseeee 'd': ccccaaaasssseeee 'D': dstat++; argv++; bbbbrrrreeeeaaaakkkk; ccccaaaasssseeee 'r': ccccaaaasssseeee 'R': argv++; maxrounds = atoi(*argv++); argc--; bbbbrrrreeeeaaaakkkk; ccccaaaasssseeee 'P': iiiiffff (argc < HSIZE) {{{{ fprintf(stderr, "Too few P values!!!\n"); exit(1); }}}} argv++; ffffoooorrrr (i=1; i<=HSIZE; i++) P[i-1] = atoi(*argv++); argc -= HSIZE; bbbbrrrreeeeaaaakkkk; ddddeeeeffffaaaauuuulllltttt: fprintf(stderr,"%s - usage: %s\n", name, usage); bbbbrrrreeeeaaaakkkk; }}}} eeeellllsssseeee fprintf(stderr, "Unknown argument %s\n", *argv); }}}} }}}} Appendix B 142 _2. _c_k__d_e_p._c /* * _c_k _d_e_p._c - _b_u_i_l_d _d_e_p_e_n_d_e_n_c_y _m_a_t_r_i_x _f_o_r _e_a_c_h _c_i_p_h_e_r_t_e_x_t _b_i_t, _b_a_s_e_d _o_n * - _k_e_y_t_e_x_t _b_i_t_s, _f_o_r _a _g_i_v_e_n _P, _P_C_2 & _k_e_y _s_c_h_e_d_u_l_e * (_a_s_s_u_m_i_n_g _S-_b_o_x_e_s _d_o _t_h_e_i_r _t_h_i_n_g, _a_n_d _t_h_a_t _t_h_e_i_r * _o_u_t_p_u_t_s _a_r_e _e_q_u_i_v_a_l_e_n_t) * * _L_a_w_r_e_n_c_e _B_r_o_w_n <_l_p_b@_c_s._a_d_f_a._o_z> _5/_8_8 */ ####iiiinnnncccclllluuuuddddeeee ####ddddeeeeffffiiiinnnneeee HSIZE 32 /* _s_i_z_e _o_f _i_n_p_u_t _d_a_t_a _b_l_o_c_k _h_a_l_f */ ####ddddeeeeffffiiiinnnneeee FSIZE (2 * HSIZE) /* _s_i_z_e _o_f _i_n_p_u_t _d_a_t_a _b_l_o_c_k */ ####ddddeeeeffffiiiinnnneeee USIZE 56 /* _s_i_z_e _o_f _k_e_y _v_e_c_t_o_r _u_s_e_d _i_n _k_e_y _s_c_h_e_d_u_l_e */ ####ddddeeeeffffiiiinnnneeee P2SIZE 48 /* _s_i_z_e _o_f _s_u_b_k_e_y _v_e_c_t_o_r _i_n_p_u_t _t_o _f */ ####ddddeeeeffffiiiinnnneeee ROTSIZE 28 /* _s_i_z_e _o_f _k_e_y _s_c_h_e_d_u_l_e _r_e_g_i_s_t_e_r (_k_e_y _h_a_l_f) */ ####ddddeeeeffffiiiinnnneeee ROUNDS 16 /* _N_u_m_b_e_r _o_f _D_E_S _r_o_u_n_d_s */ cccchhhhaaaarrrr *name = "ck dep"; /* _p_r_o_g_r_a_m _n_a_m_e */ cccchhhhaaaarrrr *depnam = "-CKdep"; /* _d_e_p_e_n_d_e_n_c_y _f_l_a_g _n_a_m_e _s_e_n_t _t_o _o_u_t_p_u_t _f_i_l_e */ cccchhhhaaaarrrr *usage = "[-vV] [-dD] [-rR rounds] [-P P values] [-C PC2 values] [-f] [-K key sched]"; /*-_u_s_a_g_e _s_t_r_i_n_g */- - iiiinnnntttt P[HSIZE] /* _P_e_r_m_u_t_a_t_i_o_n _m_a_t_r_i_x _P _o_f _w_h_i_c_h _S-_b_o_x _e_a_c_h _i_n_p_u_t _b_i_t _i_s _f_r_o_m */ = {{{{ 4, 2, 5, 6, 8, 3, 7, 5, 1, 4, 6, 7, 2, 5, 8, 3, 1, 2, 6, 4, 8, 7, 1, 3, 5, 4, 8, 2, 6, 3, 1, 7}}}}; cccchhhhaaaarrrr PC2[P2SIZE] /* _P_e_r_m_u_t_a_t_i_o_n _m_a_t_r_i_x _P_C_2 _o_f _k_e_y _s_c_h_e_d _b_i_t _p_e_r_m */ = {{{{ 14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10, 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2, 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48, 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32 }}}}; iiiinnnntttt keyrot[ROUNDS] /* _k_e_y _r_o_t_a_t_i_o_n _s_c_h_e_d_u_l_e */ = {{{{ 1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1 }}}}; Appendix B 143 iiiinnnntttt totrot[ROUNDS+1] /* _t_o_t_a_l _k_e_y _r_o_t_a_t_i_o_n _s_c_h_e_d */ = {{{{ 0,1,2,4,6,8,10,12,14,15,17,19,21,23,25,27,28 }}}}; iiiinnnntttt rotsize = ROTSIZE; /* _n_u_m_b_e_r _o_f _b_i_t_s _r_o_t_a_t_e_d _i_n _k_e_y _s_c_h_e_d */ iiiinnnntttt F[FSIZE][USIZE]; /* _d_e_p_e_n_d_e_n_c_y _m_a_t_r_i_x _F[_i][_j] _g_i_v_e_s _d_e_p_e_n_d_e_n_c_y */ /* _o_f _o_u_t_p_u_t _b_i_t _i _o_n _k_e_y _b_i_t _j _a_t _c_u_r_r_e_n_t _r_o_u_n_d */ iiiinnnntttt sp, /* _n_u_m_b_e_r _o_f _b_i_t_s _i_n _F _w_i_t_h _n_o _d_e_p_e_n_d_e_n_c_y */ me, /* _m_e_s_s_a_g_e _o_n_l_y _d_e_p_e_n_d_e_n_c_y */ ac, /* _a_u_t_o_c_l_a_v_e _o_n_l_y _d_e_p_e_n_d_e_n_c_y */ bt, /* _b_o_t_h _m_e_s_s_a_g_e & _a_u_t_o_c_l_a_v_e _d_e_p_e_n_d_e_n_c_y */ tot, /* _p_e_r_c_e_n_t_a_g_e _o_f _b_i_t_s _w_i_t_h _a _d_e_p_e_n_d_e_n_c_y */ err; /* _n_u_m_b_e_r _w_i_t_h _b_a_d _s_p_e_c_i_f_i_c_a_t_i_o_n */ iiiinnnntttt verbose = 0; /* _v_e_r_b_o_s_e _o_u_t_p_u_t _f_l_a_g */ iiiinnnntttt dstat= 0; /* _p_r_i_n_t _d_e_t_a_i_l_e_d _s_t_a_t_s (_b_u_t _l_e_s_s _t_h_a_n _v_e_r_b_o_s_e) _f_l_a_g */ iiiinnnntttt pboth= 0; /* _p_r_i_n_t % _o_f _B_O_T_H _m_s_g+_a_u_t_o & _O_v_e_r_a_l_l _d_e_p_e_n_d_e_c_y */ iiiinnnntttt maxrounds = 8; /* _n_u_m_b_e_r _o_f _r_o_u_n_d_s _t_o _a_n_a_l_y_s_e */ cccchhhhaaaarrrr disp[4] = {{{{' ', 'x', '-', '*'}}}}; /* _d_i_s_p_l_a_y _c_h_a_r _f_o_r _e_a_c_h _c_l_a_s_s */ main(argc, argv) _m_a_i_n iiiinnnntttt argc; cccchhhhaaaarrrr **argv; {{{{ iiiinnnntttt i; init(argc, argv); F init(); iiii-ffff (verbose) printf("Round 1:"); eeeellllsssseeee printf("%s: ", depnam); scanF(); iiiiffff (verbose) prF(); ffffoooorrrr (i=2; i<=maxrounds; i++){{{{ nextF(i); iiiiffff (verbose) printf("Round %2d:", i); scanF(); iiiiffff (verbose) prF(); }}}} printf("\n"); }}}} F init() {{{{- iiiinnnntttt i, j, kbase; Appendix B 144 /* _c_l_e_a_r _F, _n_b _F_L _i_s _0 */ ffffoooorrrr (i=0; i rotsize) x = (x + totrot[i-1] - 1) % rotsize + rotsize + 1; eeeellllsssseeee x = (x + totrot[i-1] - 1) % rotsize + 1; rrrreeeettttuuuurrrrnnnn(x); }}}} scanF() _s_c_a_n_F {{{{ Appendix B 146 iiiinnnntttt i, j; ffffllllooooaaaatttt ptot, both; sp = me = ac = bt = tot = err = 0; ffffoooorrrr (i=0; i 0 ) {{{{ iiiiffff ( (*argv)[0] == '-' ) sssswwwwiiiittttcccchhhh ( (*argv)[1] ) {{{{ ccccaaaasssseeee 'v': ccccaaaasssseeee 'V': verbose++; argv++; bbbbrrrreeeeaaaakkkk; ccccaaaasssseeee 'b': ccccaaaasssseeee 'B': pboth++; argv++; bbbbrrrreeeeaaaakkkk; ccccaaaasssseeee 'd': Appendix B 148 ccccaaaasssseeee 'D': dstat++; argv++; bbbbrrrreeeeaaaakkkk; ccccaaaasssseeee 'r': ccccaaaasssseeee 'R': argv++; maxrounds = atoi(*argv++); argc--; bbbbrrrreeeeaaaakkkk; ccccaaaasssseeee 'P': iiiiffff (argc < HSIZE) {{{{ fprintf(stderr, "Too few P values!!!\n"); exit(1); }}}} argv++; ffffoooorrrr (i=1; i<=HSIZE; i++) P[i-1] = atoi(*argv++); argc -= HSIZE; prP(); bbbbrrrreeeeaaaakkkk; ccccaaaasssseeee 'C': iiiiffff (argc < P2SIZE) {{{{ fprintf(stderr, "Too few PC2 values!!!\n"); exit(1); }}}} argv++; ffffoooorrrr (i=1; i<=P2SIZE; i++) PC2[i-1] = atoi(*argv++); argc -= P2SIZE; prPC2(); bbbbrrrreeeeaaaakkkk; ccccaaaasssseeee 'f': /* _u_s_e _f_u_l_l _s_i_z_e _k_e_y _r_o_t_a_t_i_o_n _r_e_g_i_s_t_e_r_s */ ccccaaaasssseeee 'F': rotsize = 2 * ROTSIZE; argv++; bbbbrrrreeeeaaaakkkk; ccccaaaasssseeee 'K': iiiiffff (argc < ROUNDS) {{{{ fprintf(stderr, "%d - Too few KeySched values!!!\n", argc); exit(1); }}}} argv++; ffffoooorrrr (i=1; i<=ROUNDS; i++) /* _r_e_a_d _k_e_y _r_o_t_a_t_i_o_n _s_c_h_e_d */ keyrot[i-1] = atoi(*argv++); ffffoooorrrr (i=1; i<=ROUNDS; i++) /* _c_a_l_c _t_o_t_a_l _r_o_t_a_t_i_o_n _s_c_h_e_d */ totrot[i] = totrot[i-1] + keyrot[i-1]; argc -= ROUNDS; prKS(); bbbbrrrreeeeaaaakkkk; ddddeeeeffffaaaauuuulllltttt: fprintf(stderr,"%s - usage: %s\n", name, usage); bbbbrrrreeeeaaaakkkk; }}}} eeeellllsssseeee fprintf(stderr, "Unknown argument %s\n", *argv); }}}} }}}} Appendix B 149 Appendix B AAAAPPPPPPPPEEEENNNNDDDDIIIIXXXX CCCC LLLLOOOOKKKKIIII ---- SSSSaaaammmmpppplllleeee IIIImmmmpppplllleeeemmmmeeeennnnttttaaaattttiiiioooonnnn _1. _O_v_e_r_a_l_l _P_r_o_g_r_a_m _S_t_r_u_c_t_u_r_e This appendix contains a listing of a sample implementa- tion of the LOKI cipher. These implement the first (small but slow) of the possible software implementations identi- fied previously. They modules are: loki.h function declarations and typedefs for the library routines to implement the LOKI cryptographic primi- tive lokimode.h declarations of the standard modes of operation using the LOKI primitive loki64.i specification of the public constants used in the library routines to implement the LOKI cryptographic primitive loki64.c the library routines to implement the LOKI crypto- graphic primitive lokimac.c a program using the loki64.c routines which reads a stream of data and computes the SBH message authenti- cation code for that stream. lokicert.c a program using the loki64.c routines which reads a file of (key,plaintext,ciphertext) triplets and cer- tifies that the loki64.c library routines are func- tioning correctly. gf8.c utility routines implementing arithmetic in $ GF( 2 sup 8 ) $. lokimode.c utility routines used in implementing the standard 150 151 modes of operation using the LOKI primitive test1, test2 files of (key,plaintext,ciphertext) triplets used by the lokicert.c program. cert.test1 trace of output from "lokicert test1" when "loki64.c" has been compiled with "TRACE=2" defined. Listings are provided for the following files: loki.h lokimode.h loki64.i loki64.c which form the core routines of the LOKI cryptographic primitive, and define macros for the standard modes of operation. The sources for the remaining routines, and for the test data and trace output, are available if required. _2. _T_e_s_t _D_a_t_a A single test triplet is listed below (being the contents of "test1"). # Single LOKI Certification triplet # data is saved as (key, plaintext, ciphertext) triplets # 5b5a57676a56676e 675a69675e5a6b5a 3c61fa7e2e99d048 A set of test triplets is listed below (being the contents of "test2"). # # LOKI Validation Data Suite Triples # data is saved as (key, plaintext, ciphertext) triplets # 0000000000000000 0000000000000000 0000000000000000 0000000000000000 355550b2150e2451 8e2a251b94704c69 0000000000000000 35a7bae825c0d73b 8ca64de9c1b123a7 0000000000000000 8ca64de9c1b123a7 35a7bae825c0d73b 0000000000000000 8e2a251b94704c69 355550b2150e2451 0000000000000000 ffffffffffffffff 61f38c55061e3161 Appendix C 152 0101010101010101 0123456789abcdef f60b54c240d7ed14 0101010101010101 617b3a0ce8f07100 38ae088ae853f7fb 0101010101010101 9b38f6ce85aab9c3 617b3a0ce8f07100 0113b970fd34f2ce 059b5e0851cf143a 88c37b8c809c6dcd 0113b970fd34f2ce 7514cdb961b6760d 86a560f10ec6d85b 0113b970fd34f2ce 86a560f10ec6d85b 23e9b229fdea123f 0123456789abcdef 0000000000000000 d853533a6c1beb30 0123456789abcdef 1111111111111111 c4d29774e5d5247c 0123456789abcdef 17668dfc7292532d cc9feed345a9f7a1 0123456789abcdef 23c086665917b8e1 17668dfc7292532d 0123456789abcdef d5d44ff720683d0d 13d2967efa3aa3c2 0123456789abcdef fce30226576320bd d5d44ff720683d0d 0131d9619dc1376e 5cd54ca83def57da c251a566d109cfc2 0131d9619dc1376e 65e160aed7b773a9 7a389d10354bd271 0131d9619dc1376e 7a389d10354bd271 94c33356f2ee1adf 0170f175468fb5e6 0756d8e0774761d2 49a480651f03b452 0170f175468fb5e6 0cd3da020021dc09 afec86ec719000ad 0170f175468fb5e6 914c1806fccbce33 0cd3da020021dc09 018310dc409b26d6 1d9d5c5018f728c2 87bd17440173768b 018310dc409b26d6 5a0bf934fd6009f8 5f4c038ed12b2e41 018310dc409b26d6 5f4c038ed12b2e41 773740aa56ef058e 025816164629b007 480d39006ee762f2 719ebffea9a16c35 025816164629b007 a1f9915541020b56 16f949d4011073b5 025816164629b007 ec92e65da168b46f a1f9915541020b56 04689104c2fd3b2f 26955f6835af609a 8139b3c65393ea37 04689104c2fd3b2f 5265227fe08a28ec 5c513c9c4886c088 04689104c2fd3b2f 5c513c9c4886c088 bfd4c8c383533bdb 04b915ba43feb5b6 42fd443059577fa2 e7244bf3b0e5715d 04b915ba43feb5b6 a483ea7ccf2e0e5a af37fb421f8c4095 04b915ba43feb5b6 af37fb421f8c4095 762bd5f9b296f82e 07a1133e4a0b2686 0248d43806f67172 dd02c943fb4537a3 07a1133e4a0b2686 624f2e2dfa008142 868ebb51cab4599a 07a1133e4a0b2686 868ebb51cab4599a 235c5997034a503d 07a7137045da2a16 28e686668c3bd6d9 dfd64a815caf1a0f 07a7137045da2a16 3bdd119049372802 3de59f157f8b6bf9 07a7137045da2a16 dfd64a815caf1a0f 00b3f10e6f1063ed 1111111111111111 0123456789abcdef b0c9897c2765e214 1111111111111111 1111111111111111 f0a12c83c4529223 1111111111111111 24900548c21a3567 f40379ab9e0ec533 1111111111111111 8a5ae1f81ab8f2dd a273d7cb7d390531 1111111111111111 a273d7cb7d390531 8a5ae1f81ab8f2dd 1111111111111111 f40379ab9e0ec533 24900548c21a3567 1c587f1c13924fef 305532286d6f295a 8b62933a45dcf71f 1c587f1c13924fef 63fac0d034d9f793 b061dff8054771a8 1c587f1c13924fef f63de067f58c38ed 63fac0d034d9f793 1f08260d1ac2465e 2c0a241eb9f05999 ef1bf03e5dfa575a 1f08260d1ac2465e 6b056e18759f5cca c07261a9596039c3 1f08260d1ac2465e ef1bf03e5dfa575a b8705cc3a19ae567 1f1f1f1f0e0e0e0e 0123456789abcdef 16be5183d694e578 1f1f1f1f0e0e0e0e 322f206b2d39d65d db958605f8c8c606 1f1f1f1f0e0e0e0e db958605f8c8c606 1c37794afacf9e4e Appendix C 153 3000000000000000 1000000000000001 85884d224ec9e63d 3000000000000000 958e6e627a05557b 389b4e8dc846c4aa 3000000000000000 d3c4539579b96231 958e6e627a05557b 37d06bb516cb7546 0a2aeeae3ff4ab77 45127fb1f43c5304 37d06bb516cb7546 164d5e404f275232 70f6cf2136677443 37d06bb516cb7546 19acae3136c0bc7c 0a2aeeae3ff4ab77 3849674c2602319e 126898d55e911500 7178876e01f19b2a 3849674c2602319e 51454b582ddf440a 57df30a9420a50ee 3849674c2602319e 7178876e01f19b2a 9ca72dbcd502b0ba 43297fad38e373fe 4c974f1caa59f5d4 ea676b2cb7db2b7a 43297fad38e373fe 762514b829bf486a 1d3eba477e45f553 43297fad38e373fe ea676b2cb7db2b7a 547018835947a9b3 49793ebc79b3258f 437540c8698f3cfa 7ce143bcd1108178 49793ebc79b3258f 6fbf1cafcffd0556 315e66ab98b26ded 49793ebc79b3258f a0cb2871752053f0 6fbf1cafcffd0556 49e95d6d4ca229bf 00b0024eaac70ae3 5a6b612cc26cce4a 49e95d6d4ca229bf 02fe55778117f12a 85028e1e6b858ec4 49e95d6d4ca229bf 5a6b612cc26cce4a 1b1789391a840fea 4fb05e1515ab73a7 072d43a077075292 cfeeb0bdeb67fef4 4fb05e1515ab73a7 2f22e49bab7ca1ac 237c628bb6892693 4fb05e1515ab73a7 ad87789bc00718c2 2f22e49bab7ca1ac 584023641aba6176 004bd6ef09176062 fcdebb14f3b2babb 584023641aba6176 88bf0db6d70dee56 d09730ee2f16f0d1 584023641aba6176 c7d2845ea6d01c70 88bf0db6d70dee56 5b5a57676a56676e 974affbf86022d1f 429941c32d5126e8 7ca110454a1a6e57 01a1d6d039776742 098c16c1e1f4a681 7ca110454a1a6e57 690f5b0d9a26939b c10935a58a249fbb 7ca110454a1a6e57 ecd1c2f929f33ced 690f5b0d9a26939b e0fee0fef1fef1fe 0123456789abcdef e29d11faf2d133ce e0fee0fef1fef1fe b7687facf9b1a656 edbfd1c66c29ccc7 e0fee0fef1fef1fe edbfd1c66c29ccc7 c0f43c83cce0e0df fedcba9876543210 0123456789abcdef cfee5c8eb79153d9 fedcba9876543210 2a2bb008df97c2f2 63f983b15c642726 fedcba9876543210 7f46aa73f7fcde02 2a2bb008df97c2f2 fedcba9876543210 c44c1b3668a0f2cf ed39d950fa74bcc4 fedcba9876543210 ed39d950fa74bcc4 7420eb3d2a7aa178 fedcba9876543210 ffffffffffffffff fce524b60ec5b3fc ffffffffffffffff 0000000000000000 0000000000000000 ffffffffffffffff 16b15028f06a5ab8 caaaaf4deaf1dbae ffffffffffffffff 3c7188775253884d 7359b2163e4edc58 ffffffffffffffff 7359b2163e4edc58 3c7188775253884d ffffffffffffffff caaaaf4deaf1dbae 16b15028f06a5ab8 ffffffffffffffff ffffffffffffffff 61f38c55061e3161 Appendix C 154 _3. _P_r_o_g_r_a_m _L_i_s_t_i_n_g_s /* * _l_o_k_i._h - _s_p_e_c_i_f_i_e_s _t_h_e _i_n_t_e_r_f_a_c_e _t_o _t_h_e _L_O_K_I _e_n_c_r_y_p_t_i_o_n _l_i_b_r_a_r_y. * _T_h_i_s _l_i_b_r_a_r_y _p_r_o_v_i_d_e_s _r_o_u_t_i_n_e_s _t_o _e_x_p_a_n_d _a _k_e_y, _e_n_c_r_y_p_t _a_n_d * _d_e_c_r_y_p_t _6_4-_b_i_t _d_a_t_a _b_l_o_c_k_s. _T_h_e _L_O_K_I _D_a_t_a _E_n_c_r_y_p_t_i_o_n _A_l_g_o_r_i_t_h_m * _i_s _a _b_l_o_c_k _c_i_p_h_e_r _w_h_i_c_h _e_n_s_u_r_e_s _t_h_a_t _i_t_s _o_u_t_p_u_t _i_s _a _c_o_m_p_l_e_x * _f_u_n_c_t_i_o_n _o_f _i_t_s _i_n_p_u_t _a_n_d _t_h_e _k_e_y. * * * _A_u_t_h_o_r: _L_a_w_r_e_n_c_e _B_r_o_w_n <_l_p_b@_c_s._a_d_f_a._o_z._a_u> _A_u_g _1_9_8_9 * _C_o_m_p_u_t_e_r _S_c_i_e_n_c_e, _U_C _U_N_S_W, _A_u_s_t_r_a_l_i_a_n _D_e_f_e_n_c_e _F_o_r_c_e _A_c_a_d_e_m_y, * _C_a_n_b_e_r_r_a, _A_C_T _2_6_0_0, _A_u_s_t_r_a_l_i_a. * * _V_e_r_s_i_o_n: * _v_1._0 - _o_f _l_o_k_i_6_4._o _i_s _c_u_r_r_e_n_t _7/_8_9 * * _C_o_p_y_r_i_g_h_t _1_9_8_9 _b_y _L_a_w_r_e_n_c_e _B_r_o_w_n _a_n_d _C_C_C_S_R _U_n_i _N_S_W. _A_l_l _r_i_g_h_t_s _r_e_s_e_r_v_e_d. * _T_h_i_s _p_r_o_g_r_a_m _m_a_y _n_o_t _b_e _s_o_l_d _o_r _u_s_e_d _a_s _i_n_d_u_c_e_m_e_n_t _t_o _b_u_y _a * _p_r_o_d_u_c_t _w_i_t_h_o_u_t _t_h_e _w_r_i_t_t_e_n _p_e_r_m_i_s_s_i_o_n _o_f _t_h_e _a_u_t_h_o_r. * * _D_e_s_c_r_i_p_t_i_o_n: * _T_h_e _r_o_u_t_i_n_e_s _p_r_o_v_i_d_e_d _b_y _t_h_e _l_i_b_r_a_r_y _a_r_e: * * _l_o_k_i_k_e_y(_k_e_y) - _e_x_p_a_n_d_s _a _k_e_y _i_n_t_o _s_u_b_k_e_y, _f_o_r _u_s_e _i_n * _c_h_a_r _k_e_y[_8]; _e_n_c_r_y_p_t_i_o_n _a_n_d _d_e_c_r_y_p_t_i_o_n _o_p_e_r_a_t_i_o_n_s. * * _e_n_l_o_k_i(_b) - _m_a_i_n _L_O_K_I _e_n_c_r_y_p_t_i_o_n _r_o_u_t_i_n_e, _t_h_i_s _r_o_u_t_i_n_e * _c_h_a_r _b[_8]; _e_n_c_r_y_p_t_s _o_n_e _6_4-_b_i_t _b_l_o_c_k _b _w_i_t_h _s_u_b_k_e_y * * _d_e_l_o_k_i(_b) - _m_a_i_n _L_O_K_I _d_e_c_r_y_p_t_i_o_n _r_o_u_t_i_n_e, _t_h_i_s _r_o_u_t_i_n_e * _c_h_a_r _b[_8]; _d_e_c_r_y_p_t_s _o_n_e _6_4-_b_i_t _b_l_o_c_k _b _w_i_t_h _s_u_b_k_e_y * * _T_h_e _6_4-_b_i_t _d_a_t_a & _k_e_y _b_l_o_c_k_s _u_s_e_d _i_n _t_h_e _a_l_g_o_r_i_t_h_m _a_r_e _s_p_e_c_i_f_i_e_d _a_s _e_i_g_h_t * _u_n_s_i_g_n_e_d _c_h_a_r_s. _F_o_r _t_h_e _p_u_r_p_o_s_e_s _o_f _i_m_p_l_e_m_e_n_t_i_n_g _t_h_e _L_O_K_I _a_l_g_o_r_i_t_h_m, * _t_h_e _b_i_t_s _a_r_e _n_u_m_b_e_r_e_d _a_s _f_o_l_l_o_w_s: * [_6_3.._5_6] [_5_5.._4_8] ... [_7.._0] * _i_n _b[_0] _b[_1] _b[_2] _b[_3] _b[_4] _b[_5] _b[_6] _b[_7] * */ ####ddddeeeeffffiiiinnnneeee LOKIBLK 8 /* _N_o _o_f _b_y_t_e_s _i_n _a _L_O_K_I _d_a_t_a-_b_l_o_c_k */ ####ddddeeeeffffiiiinnnneeee ROUNDS 16 /* _N_o _o_f _L_O_K_I _r_o_u_n_d_s */ ttttyyyyppppeeeeddddeeeeffff uuuunnnnssssiiiiggggnnnneeeedddd lllloooonnnngggg Long; /* _t_y_p_e _s_p_e_c_i_f_i_c_a_t_i_o_n _f_o_r _a_l_i_g_n_e_d _L_O_K_I _b_l_o_c_k_s */ eeeexxxxtttteeeerrrrnnnn Long lokikey[2]; /* _6_4-_b_i_t _k_e_y _u_s_e_d _b_y _L_O_K_I _r_o_u_t_i_n_e_s */ eeeexxxxtttteeeerrrrnnnn cccchhhhaaaarrrr *loki lib ver; /* _S_t_r_i_n_g _w_i_t_h _v_e_r_s_i_o_n _n_o. & _c_o_p_y_r_i_g_h_t */ - - Appendix C 155 ####iiiiffffddddeeeeffff ansi /* _d_e_c_l_a_r_e _p_r_o_t_o_t_y_p_e_s _f_o_r _l_i_b_r_a_r_y _f_u_n_c_t_i_o_n_s */ eeeexxxxtttteeeerrrrnnnn void enloki(cccchhhhaaaarrrr b[LOKIBLK]); eeeexxxxtttteeeerrrrnnnn void deloki(cccchhhhaaaarrrr b[LOKIBLK]); eeeexxxxtttteeeerrrrnnnn void setlokikey(cccchhhhaaaarrrr key[LOKIBLK]); ####eeeellllsssseeee /* _e_l_s_e _j_u_s_t _d_e_c_l_a_r_e _l_i_b_r_a_r_y _f_u_n_c_t_i_o_n_s _e_x_t_e_r_n */ eeeexxxxtttteeeerrrrnnnn void enloki(), deloki(), setlokikey(); ####eeeennnnddddiiiiffff ansi Appendix C 156 /* * * _l_o_k_i_m_o_d_e._h - _d_e_f_i_n_e _m_a_c_r_o_s _f_o_r _e_a_c_h _o_f _t_h_e _c_o_m_m_o_n _m_o_d_e_s _o_f _o_p_e_r_a_t_i_o_n * _o_f _t_h_e _L_O_K_I _e_n_c_r_y_p_t_i_o_n _p_r_i_m_i_t_i_v_e. * _D_e_t_a_i_l_s _o_f _t_h_e _m_o_d_e_s _m_a_y _b_e _f_o_u_n_d _i_n: * _A_N_S_I _S_t_a_n_d_a_r_d _X_3._1_0_6-_1_9_8_3 _D_E_A - _M_o_d_e_s _o_f _O_p_e_r_a_t_i_o_n * * _A_u_t_h_o_r: _L_a_w_r_e_n_c_e _B_r_o_w_n <_l_p_b@_c_s._a_d_f_a._o_z._a_u> _A_u_g _1_9_8_9 * _C_o_m_p_u_t_e_r _S_c_i_e_n_c_e, _U_C _U_N_S_W, _A_u_s_t_r_a_l_i_a_n _D_e_f_e_n_c_e _F_o_r_c_e _A_c_a_d_e_m_y, * _C_a_n_b_e_r_r_a, _A_C_T _2_6_0_0, _A_u_s_t_r_a_l_i_a. * * _C_o_p_y_r_i_g_h_t _1_9_8_9 _b_y _L_a_w_r_e_n_c_e _B_r_o_w_n _a_n_d _C_C_C_S_R _U_n_i _N_S_W. _A_l_l _r_i_g_h_t_s _r_e_s_e_r_v_e_d. * _T_h_i_s _p_r_o_g_r_a_m _m_a_y _n_o_t _b_e _s_o_l_d _o_r _u_s_e_d _a_s _i_n_d_u_c_e_m_e_n_t _t_o _b_u_y _a * _p_r_o_d_u_c_t _w_i_t_h_o_u_t _t_h_e _w_r_i_t_t_e_n _p_e_r_m_i_s_s_i_o_n _o_f _t_h_e _a_u_t_h_o_r. * */ /* * _d_e_f_i_n_e _v_a_l_i_d _f_l_a_g _v_a_l_u_e_s _f_o_r _t_h_e _r_e_q_u_i_r_e_d _m_o_d_e _a_n_d _o_p_e_r_a_t_i_o_n */ ####ddddeeeeffffiiiinnnneeee OP EN 0x01 /* _o_p _i_s _e_n_c_r_y_p_t_i_n_g */ ####ddddeeeeffffiiiinnnneeee OP-DE 0x02 /* _o_p _i_s _d_e_c_r_y_p_t_i_n_g */ - ####ddddeeeeffffiiiinnnneeee M ECB 0x10 /* _m_o_d_e _i_s _E_C_B */ ####ddddeeeeffffiiiinnnneeee M-CBC 0x20 /* _m_o_d_e _i_s _C_B_C */ ####ddddeeeeffffiiiinnnneeee M-CFB1 0x30 /* _m_o_d_e _i_s _C_F_B_1 _w_i_t_h _8-_b_i_t _f_e_e_d_b_a_c_k */ ####ddddeeeeffffiiiinnnneeee M-CFB8 0x40 /* _m_o_d_e _i_s _C_F_B_8 _w_i_t_h _6_4-_b_i_t _f_e_e_d_b_a_c_k */ ####ddddeeeeffffiiiinnnneeee M-OFB8 0x50 /* _m_o_d_e _i_s _O_F_B_8 _w_i_t_h _6_4-_b_i_t _f_e_e_d_b_a_c_k */ ####ddddeeeeffffiiiinnnneeee M-SBH 0x60 /* _m_o_d_e _i_s _S_B_H _s_i_n_g_l_e _b_l_o_c_k (_6_4-_b_i_t) _h_a_s_h */ ####ddddeeeeffffiiiinnnneeee M-DBH 0x70 /* _m_o_d_e _i_s _D_B_H _d_o_u_b_l_e _b_l_o_c_k (_1_2_8-_b_i_t) _h_a_s_h */ - eeeexxxxtttteeeerrrrnnnn Long dea IV[2]; /* _c_u_r_r_e_n_t _6_4-_b_i_t _I_V _v_e_c_t_o_r */ eeeexxxxtttteeeerrrrnnnn void set-IV(); /* _r_o_u_t_i_n_e _t_o _s_e_t _I_V _v_e_c_t_o_r */ /* * _d_e_f_i_n_e _m_a_c_r_o_s _f_o_r _e_a_c_h _o_f _t_h_e _c_o_m_m_o_n _m_o_d_e_s * _n_b: _i_n_p_u_t _b_l_o_c_k _m_u_s_t _b_e _t_y_p_e "_L_o_n_g _b[_2]" */ ####ddddeeeeffffiiiinnnneeee en ecb(b) enloki((cccchhhhaaaarrrr *)b) /* _E_n_c_r_y_p_t _i_n _E_C_B _m_o_d_e */ - ####ddddeeeeffffiiiinnnneeee de ecb(b) deloki((cccchhhhaaaarrrr *)b) /* _D_e_c_r_y_p_t _i_n _E_C_B _m_o_d_e */ - ####ddddeeeeffffiiiinnnneeee en cbc(b) {{{{ /* _E_n_c_r_y_p_t _i_n _C_B_C _m_o_d_e */ \ ((Long-*)b)[0] ^= dea IV[0]; /* _b = _b _X_O_R _I_V */ \ ((Long *)b)[1] ^= dea-IV[1]; \ enloki((cccchhhhaaaarrrr *)b); /-* _e_n_c_r_y_p_t _d_a_t_a _b_l_o_c_k */ \ dea IV[0] = ((Long *)b)[0]; /* _s_a_v_e _b _a_s _n_e_w _I_V _v_a_l_u_e */ \ dea-IV[1] = ((Long *)b)[1]; \ }}}} - Appendix C 157 ####ddddeeeeffffiiiinnnneeee de cbc(b) {{{{ /* _D_e_c_r_y_p_t _i_n _C_B_C _m_o_d_e */ \ rrrreeeeggggiiiisssstttt-eeeerrrr Long nextiv0, nextiv1; /* _t_o _s_a_v_e _e_a_c_h _b_l_o_c_k _a_s _n_e_x_t _i_v */ \ nextiv0 = ((Long *)b)[0]; /* _s_a_v_e _c_u_r_r_e_n_t _c_i_p_h_e_r_t_e_x_t _f_o_r _n_e_x_t _I_V */\ nextiv1 = ((Long *)b)[1]; \ deloki((cccchhhhaaaarrrr *)b); /* _d_e_c_r_y_p_t _d_a_t_a _b_l_o_c_k */ \ ((Long *)b)[0] ^= dea IV[0]; /* _b = _b _X_O_R _I_V */ \ ((Long *)b)[1] ^= dea-IV[1]; \ dea IV[0] = nextiv0; - /* & _m_o_v_e _n_e_x_t _I_V _t_o _c_u_r_r_e_n_t */ \ dea-IV[1] = nextiv1; \ }}}} - ####ddddeeeeffffiiiinnnneeee en cfb1(c) {{{{ /* _E_n_c_r_y_p_t _c_h_a_r _i_n _8-_b_i_t _C_F_B _m_o_d_e */ \ Long - work[2]; /* _w_o_r_k _s_t_o_r_e _f_o_r _b_l_o_c_k _t_o _e_n_c_r_y_p_t */ \ work[0] = dea IV[0]; work[1] = dea IV[1]; \ enloki((cccchhhhaaaarrrr -*)work); /* _e_n_c_r_y_p_t-_d_a_t_a _b_l_o_c_k */ \ c ^= (work[0] >> 24); /* _c = _c _X_O_R _M_S_B(_L_O_K_I(_I_V)) */ \ dea IV[0] = (dea IV[0] << 8) | (dea IV[1] >> 24); /* _I_V = (_I_V<<_8)|_c */ \ dea-IV[1] = (dea-IV[1] << 8) | c; \- }}}} - - ####ddddeeeeffffiiiinnnneeee en cfb8(b) {{{{ /* _E_n_c_r_y_p_t _b_l_o_c_k _i_n _6_4-_b_i_t _C_F_B _m_o_d_e */ \ enloki-((cccchhhhaaaarrrr *)dea IV); /* _e_n_c_r_y_p_t _d_a_t_a _b_l_o_c_k */ \ ((Long *)b)[0] ^= -dea IV[0]; /* _b = _b _X_O_R _I_V */ \ ((Long *)b)[1] ^= dea-IV[1]; \ dea IV[0] = ((Long *)-b)[0]; \ dea-IV[1] = ((Long *)b)[0]; \ }}}} - ####ddddeeeeffffiiiinnnneeee en ofb8(b) {{{{ /* _E_n_c_r_y_p_t _b_l_o_c_k _i_n _6_4-_b_i_t _O_F_B _m_o_d_e */ \ enloki-((cccchhhhaaaarrrr *)dea IV); /* _e_n_c_r_y_p_t _d_a_t_a _b_l_o_c_k */ \ ((Long *)b)[0] ^= -dea IV[0]; /* _b = _b _X_O_R _I_V */ \ ((Long *)b)[1] ^= dea-IV[1]; \ }}}} - ####ddddeeeeffffiiiinnnneeee en sbh(M) {{{{ /* _C_o_m_p_u_t_e _a _6_4-_b_i_t _M_A_C _u_s_i_n_g _S_B_H _m_o_d_e */ \ Long - work[2]; /* _w_o_r_k _s_t_o_r_e _f_o_r _b_l_o_c_k _t_o _e_n_c_r_y_p_t */ \ work[0] = ((Long *)M)[0] ^ dea IV[0]; /* _w_o_r_k _i_s _M _X_O_R _H */ \ work[1] = ((Long *)M)[1] ^ dea-IV[1]; \ setlokikey((cccchhhhaaaarrrr *)work); - /* _s_e_t _k_e_y _t_o _b_e _M _X_O_R _H */ \ work[0] = dea IV[0]; /* _w_o_r_k _i_s _H */ \ work[1] = dea-IV[1]; \ enloki((cccchhhhaaaarrrr -*)dea IV); /* _e_n_c_r_y_p_t _p_r_e_v_i_o_u_s _h_a_s_h _v_a_l_u_e */ \ dea IV[0] ^= work[-0]; /* _n_e_w _H _i_s _d_e_a _I_V _X_O_R _H */ \ dea-IV[1] ^= work[1]; \ - }}}} - Appendix C 158 /* * _l_o_k_i_6_4._i - _c_o_n_t_a_i_n_s _t_h_e _f_i_x_e_d _p_e_r_m_u_t_a_t_i_o_n _a_n_d _s_u_b_s_t_i_t_u_t_i_o_n _t_a_b_l_e_s * _f_o_r _a _6_4 _b_i_t _L_O_K_I _i_m_p_l_e_m_e_n_t_a_t_i_o_n * * _A_u_t_h_o_r: _L_a_w_r_e_n_c_e _B_r_o_w_n <_l_p_b@_c_s_a_d_f_a._o_z> _A_u_g _1_9_8_9 * _C_o_m_p_u_t_e_r _S_c_i_e_n_c_e, _U_C _U_N_S_W, _A_D_F_A, _C_a_n_b_e_r_r_a, _A_C_T _2_6_0_0, _A_u_s_t_r_a_l_i_a. * * _C_o_p_y_r_i_g_h_t _1_9_8_9 _b_y _L_a_w_r_e_n_c_e _B_r_o_w_n _a_n_d _C_C_C_S_R _U_n_i _N_S_W. _A_l_l _r_i_g_h_t_s _r_e_s_e_r_v_e_d. * _T_h_i_s _p_r_o_g_r_a_m _m_a_y _n_o_t _b_e _s_o_l_d _o_r _u_s_e_d _a_s _i_n_d_u_c_e_m_e_n_t _t_o _b_u_y _a * _p_r_o_d_u_c_t _w_i_t_h_o_u_t _t_h_e _w_r_i_t_t_e_n _p_e_r_m_i_s_s_i_o_n _o_f _t_h_e _a_u_t_h_o_r. */ /* _3_2-_b_i_t _p_e_r_m_u_t_a_t_i_o_n _f_u_n_c_t_i_o_n _P */ cccchhhhaaaarrrr P[32] = {{{{ 31, 23, 15, 7, 30, 22, 14, 6, 29, 21, 13, 5, 28, 20, 12, 4, 27, 19, 11, 3, 26, 18, 10, 2, 25, 17, 9, 1, 24, 16, 8, 0 }}}}; /* * _s_f_n _d_e_s_c - _a _d_e_s_r_i_p_t_o_r _t_a_b_l_e _s_p_e_c_i_f_y_i_n_g _w_h_i_c_h _i_r_r_e_d_u_c_i_b_l_e _p_o_l_y_n_o_m_i_a_l * - _a_n_d _e_x_p_o_n_e_n_t _i_s _t_o _b_e _u_s_e_d _f_o_r _e_a_c_h _o_f _t_h_e _1_6 _S _f_u_n_c_t_i_o_n_s _i_n * _t_h_e _L_o_k_i _S-_b_o_x */ ttttyyyyppppeeeeddddeeeeffff ssssttttrrrruuuucccctttt {{{{ sssshhhhoooorrrrtttt gen; /* _i_r_r_e_d_u_c_i_b_l_e _p_o_l_y_n_o_m_i_a_l _u_s_e_d _i_n _t_h_i_s _f_i_e_l_d */ sssshhhhoooorrrrtttt exp; /* _e_x_p_o_n_e_n_t _u_s_e_d _t_o _g_e_n_e_r_a_t_e _t_h_i_s _s _f_u_n_c_t_i_o_n */ }}}} sfn desc; - /* * _s_f_n - _t_h_e _t_a_b_l_e _s_p_e_c_i_f_y_i_n_g _t_h_e _i_r_r_e_d_u_c_i_b_l_e _p_o_l_y_s & _e_x_p_o_n_e_n_t_s _u_s_e_d * _i_n _t_h_e _L_o_k_i _S-_b_o_x_e_s _f_o_r _t_h_e _L_o_k_i _a_l_g_o_r_i_t_h_m * (_n_b: _t_h_e _f_i_r_s_t _1_6 _a_r_e _u_s_e_d _u_n_l_e_s_s _o_t_h_e_r_w_i_s_e _j_u_g_g_l_e_d) */ sfn desc sfn[] = {{{{ - {{{{ /* _1_0_1_1_1_0_1_1_1 */ 375, 31}}}}, {{{{ /* _1_0_1_1_1_1_0_1_1 */ 379, 31}}}}, {{{{ /* _1_1_0_0_0_0_1_1_1 */ 391, 31}}}}, {{{{ /* _1_1_0_0_0_1_0_1_1 */ 395, 31}}}}, {{{{ /* _1_1_0_0_0_1_1_0_1 */ 397, 31}}}}, {{{{ /* _1_1_0_0_1_1_1_1_1 */ 415, 31}}}}, {{{{ /* _1_1_0_1_0_0_0_1_1 */ 419, 31}}}}, {{{{ /* _1_1_0_1_0_1_0_0_1 */ 425, 31}}}}, {{{{ /* _1_1_0_1_1_0_0_0_1 */ 433, 31}}}}, {{{{ /* _1_1_0_1_1_1_1_0_1 */ 445, 31}}}}, {{{{ /* _1_1_1_0_0_0_0_1_1 */ 451, 31}}}}, {{{{ /* _1_1_1_0_0_1_1_1_1 */ 463, 31}}}}, Appendix C 159 {{{{ /* _1_1_1_0_1_0_1_1_1 */ 471, 31}}}}, {{{{ /* _1_1_1_0_1_1_1_0_1 */ 477, 31}}}}, {{{{ /* _1_1_1_1_0_0_1_1_1 */ 487, 31}}}}, {{{{ /* _1_1_1_1_1_0_0_1_1 */ 499, 31}}}}, ####iiiiffffddddeeeeffff ALLPOLYS /* _a_l_l _o_t_h_e_r _p_o_s_s_i_b_l_e _i_r_r_e_d_u_c_i_b_l_e _p_o_l_y_s _i_n _G_F(_2^_8) */ {{{{ /* _1_1_1_1_1_0_1_0_1 */ 501, 31}}}}, {{{{ /* _1_1_1_1_1_1_0_0_1 */ 505, 31}}}}, {{{{ /* _1_0_0_0_1_1_0_1_1 */ 283, 31}}}}, {{{{ /* _1_0_0_0_1_1_1_0_1 */ 285, 31}}}}, {{{{ /* _1_0_0_1_0_1_0_1_1 */ 299, 31}}}}, {{{{ /* _1_0_0_1_0_1_1_0_1 */ 301, 31}}}}, {{{{ /* _1_0_0_1_1_1_0_0_1 */ 313, 31}}}}, {{{{ /* _1_0_0_1_1_1_1_1_1 */ 319, 31}}}}, {{{{ /* _1_0_1_0_0_1_1_0_1 */ 333, 31}}}}, {{{{ /* _1_0_1_0_1_1_1_1_1 */ 351, 31}}}}, {{{{ /* _1_0_1_1_0_0_0_1_1 */ 355, 31}}}}, {{{{ /* _1_0_1_1_0_0_1_0_1 */ 357, 31}}}}, {{{{ /* _1_0_1_1_0_1_0_0_1 */ 361, 31}}}}, {{{{ /* _1_0_1_1_1_0_0_0_1 */ 369, 31}}}}, ####eeeennnnddddiiiiffff {{{{ 00, 00}}}} }}}}; Appendix C 160 /* * _l_o_k_i_6_4._c - _l_i_b_r_a_r_y _r_o_u_t_i_n_e_s _f_o_r _a _6_4 _b_i_t _L_O_K_I _i_m_p_l_e_m_e_n_t_a_t_i_o_n * * _A_u_t_h_o_r: _L_a_w_r_e_n_c_e _B_r_o_w_n <_l_p_b@_c_s_a_d_f_a._o_z> _A_u_g _1_9_8_9 * _C_o_m_p_u_t_e_r _S_c_i_e_n_c_e, _U_C _U_N_S_W, _A_D_F_A, _C_a_n_b_e_r_r_a, _A_C_T _2_6_0_0, _A_u_s_t_r_a_l_i_a. * * _M_o_d_i_f_i_c_a_t_i_o_n_s: * _v_1._0 - _o_r_i_g_i_n_a_l _s_e_t _o_f _c_o_d_e (_b_a_s_e_d _o_n _l_o_k_i_6_4._c _v_4._0) _9/_8_9 _l_p_b * * * _C_o_p_y_r_i_g_h_t _1_9_8_9 _b_y _L_a_w_r_e_n_c_e _B_r_o_w_n _a_n_d _C_C_C_S_R _U_n_i _N_S_W. _A_l_l _r_i_g_h_t_s _r_e_s_e_r_v_e_d. * _T_h_i_s _p_r_o_g_r_a_m _m_a_y _n_o_t _b_e _s_o_l_d _o_r _u_s_e_d _a_s _i_n_d_u_c_e_m_e_n_t _t_o _b_u_y _a * _p_r_o_d_u_c_t _w_i_t_h_o_u_t _t_h_e _w_r_i_t_t_e_n _p_e_r_m_i_s_s_i_o_n _o_f _t_h_e _a_u_t_h_o_r. * * _n_b: _i_f _t_h_i_s _p_r_o_g_r_a_m _i_s _c_o_m_p_i_l_e_d _o_n _a _l_i_t_t_l_e-_e_n_d_i_a_n _m_a_c_h_i_n_e (_e_g _V_a_x) * #_d_e_f_i_n_e _L_I_T_T_L_E _E_N_D_I_A_N * _i_n _o_r_d_e_r _t_o _e_n-a__b_l_e _t_h_e _b_y_t_e _s_w_a_p_p_i_n_g _r_o_u_t_i_n_e_s * * _i_f _a _d_e_t_a_i_l_e_d _t_r_a_c_e _o_f _L_O_K_I _f_u_n_c_t_i_o_n _f _i_s _r_e_q_u_i_r_e_d _f_o_r _d_e_b_u_g_g_i_n_g * #_d_e_f_i_n_e _T_R_A_C_E * * _t_h_e_s_e _r_o_u_t_i_n_e_s _a_s_s_u_m_e _t_h_a_t _t_h_e _8-_b_y_t_e _c_h_a_r _a_r_r_a_y_s _u_s_e_d _t_o _p_a_s_s * _t_h_e _6_4-_b_i_t _b_l_o_c_k_s _f_a_l_l _o_n _a _w_o_r_d _b_o_u_n_d_a_r_y, _s_o _t_h_a_t _t_h_e _b_l_o_c_k_s * _m_a_y _b_e _r_e_a_d _a_s _l_o_n_g_w_o_r_d_s _f_o_r _e_f_f_i_c_i_e_n_c_y _r_e_a_s_o_n_s. _I_f _t_h_i_s _i_s * _n_o_t _t_r_u_e, _t_h_e _l_o_a_d & _s_a_v_e _o_f _t_h_e _p_a_r_a_m_e_t_e_r_s _w_i_l_l _n_e_e_d _c_h_a_n_g_i_n_g. */ ####iiiinnnncccclllluuuuddddeeee ####iiiinnnncccclllluuuuddddeeee "loki.h" /* _i_n_c_l_u_d_e _I_n_t_e_r_f_a_c_e _S_p_e_c_i_f_i_c_a_t_i_o_n _h_e_a_d_e_r _f_i_l_e */ ####iiiinnnncccclllluuuuddddeeee "loki64.i" /* _i_n_c_l_u_d_e _L_O_K_I _P_e_r_m_u_t_a_t_i_o_n, _S_u_b_s_t_i_t_u_t_i_o_n & _K_e_y _t_a_b_l_e_s*/ Appendix C 161 /* * _l_o_k_i_k_e_y - _t_h_e _6_4-_b_i_t _k_e_y _f_o_r _t_h_e _L_O_K_I _l_i_b_r_a_r_y _r_o_u_t_i_n_e_s */ Long lokikey[2] = {{{{0, 0}}}}; /* * _s_t_r_i_n_g _s_p_e_c_i_f_y_i_n_g _v_e_r_s_i_o_n _a_n_d _c_o_p_y_r_i_g_h_t _m_e_s_s_a_g_e */ cccchhhhaaaarrrr *loki lib ver = "64-bit LOKI library v1.0, Copyright (C) 1989 - - Lawrence Brown & CCCSR Uni NSW"; Long f(); /* _d_e_c_l_a_r_e _L_O_K_I _f_u_n_c_t_i_o_n _f */ sssshhhhoooorrrrtttt s(); /* _d_e_c_l_a_r_e _L_O_K_I _s-_b_o_x _r_o_u_t_i_n_e (_f_o_r _s_m_a_l_l _v_e_r) */ eeeexxxxtttteeeerrrrnnnn sssshhhhoooorrrrtttt exp8(); /* _e_x_p_o_n_e_n_t_i_a_t_i_o_n _r_o_u_t_i_n_e _f_o_r _G_F(_2^_8) */ /* * _R_O_L_1_2(_b) - _m_a_c_r_o _t_o _r_o_t_a_t_e _3_2-_b_i_t _b_l_o_c_k _b _l_e_f_t _b_y _1_2 _b_i_t_s * _R_O_R_1_2(_b) - _m_a_c_r_o _t_o _r_o_t_a_t_e _3_2-_b_i_t _b_l_o_c_k _b _r_i_g_h_t _b_y _1_2 _b_i_t_s */ ####ddddeeeeffffiiiinnnneeee ROL12(b) b = ((b << 12) | (b >> 20)); ####ddddeeeeffffiiiinnnneeee ROR12(b) b = ((b >> 12) | (b << 20)); /* * _b_s_w_a_p(_b) - _e_x_c_h_a_n_g_e_d _b_y_t_e_s _i_n _e_a_c_h _l_o_n_g_w_o_r_d _o_f _a _6_4-_b_i_t _d_a_t_a _b_l_o_c_k * _o_n _l_i_t_t_l_e-_e_n_d_i_a_n _m_a_c_h_i_n_e_s _w_h_e_r_e _b_y_t_e _o_r_d_e_r _i_s _r_e_v_e_r_s_e_d */ ####iiiiffffddddeeeeffff LITTLE ENDIAN ####ddddeeeeffffiiiinnnneeee bswap(-cb) {{{{ \ rrrreeeeggggiiiisssstttteeeerrrr cccchhhhaaaarrrr c; \ c = cb[0]; cb[0] = cb[3]; cb[3] = c; \ c = cb[1]; cb[1] = cb[2]; cb[2] = c; \ c = cb[4]; cb[4] = cb[7]; cb[7] = c; \ c = cb[5]; cb[5] = cb[6]; cb[6] = c; \ }}}} ####eeeennnnddddiiiiffff Appendix C 162 /* * _s_e_t_l_o_k_i_k_e_y(_k_e_y) - _s_a_v_e _6_4-_b_i_t _k_e_y _f_o_r _u_s_e _i_n _e_n_c_r_y_p_t_i_o_n_s & _d_e_c_r_y_p_t_i_o_n_s */ void setlokikey(key) _s_e_t_l_o_k_i_k_e_y cccchhhhaaaarrrr key[LOKIBLK]; /* _K_e_y _t_o _u_s_e, _s_t_o_r_e_d _a_s _a_n _a_r_r_a_y _o_f _L_o_n_g_s */ {{{{ lokikey[0] = ((Long *)key)[0]; lokikey[1] = ((Long *)key)[1]; ####iiiiffffddddeeeeffff LITTLE ENDIAN bswap(lok-ikey); /* _s_w_a_p _b_y_t_e_s _r_o_u_n_d _i_f _l_i_t_t_l_e-_e_n_d_i_a_n */ ####eeeennnnddddiiiiffff ####iiiiffff TRACE >= 1 fprintf(stderr," keyinit(%08lx, %08lx)\n", lokikey[0], lokikey[1]); ####eeeennnnddddiiiiffff }}}} Appendix C 163 /* * _e_n_l_o_k_i(_b) - _m_a_i_n _L_O_K_I _e_n_c_r_y_p_t_i_o_n _r_o_u_t_i_n_e, _t_h_i_s _r_o_u_t_i_n_e _e_n_c_r_y_p_t_s _o_n_e * _6_4-_b_i_t _b_l_o_c_k _b _u_s_i_n_g _t_h_e _L_O_K_I _a_l_g_o_r_i_t_h_m _w_i_t_h _l_o_k_i_k_e_y * * _T_h_e _e_n_c_r_y_p_t_i_o_n _o_p_e_r_a_t_i_o_n _i_n_v_o_l_v_e_s _X_O_R'_i_n_g _t_h_e _i_n_p_u_t _b_l_o_c_k _w_i_t_h * _t_h_e _k_e_y, _a_p_p_l_y_i_n_g _a _L_O_K_I _r_o_u_n_d _s_i_x_t_e_e_n _t_i_m_e_s * (_w_h_i_c_h _e_n_s_u_r_e_s _t_h_e _o_u_t_p_u_t _i_s _a _c_o_m_p_l_e_x _f_u_n_c_t_i_o_n _o_f _t_h_e _i_n_p_u_t, * _a_n_d _t_h_e _k_e_y), _a_n_d _f_i_n_a_l_l_y _X_O_R'_i_n_g _t_h_e _i_n_p_u_t _b_l_o_c_k _w_i_t_h _t_h_e _k_e_y * * _E_a_c_h _r_o_u_n_d _p_e_r_f_o_r_m_s _t_h_e _f_o_l_l_o_w_i_n_g _c_a_l_c_u_l_a_t_i_o_n _u_s_i_n_g _a _4_8-_b_i_t * _s_u_b_k_e_y_s: * _L(_i) = _R(_i-_1) * _R(_i) = _L(_i-_1) _X_O_R _f(_R(_i-_1), _K(_i)) * * _T_o _s_a_v_e _s_w_a_p_p_i_n_g, _a_l_t_e_r_n_a_t_e _c_a_l_l_s _t_o _f _u_s_e _L & _R _r_e_s_p_e_c_t_i_v_e_l_y * * _n_b: _T_h_e _6_4-_b_i_t _b_l_o_c_k _i_s _p_a_s_s_e_d _a_s _t_w_o _l_o_n_g_w_o_r_d_s. _F_o_r _t_h_e * _p_u_r_p_o_s_e_s _o_f _t_h_e _L_O_K_I _a_l_g_o_r_i_t_h_m, _t_h_e _b_i_t_s _a_r_e _n_u_m_b_e_r_e_d: * [_6_3 _6_2 .. _3_3 _3_2] [_3_1 _3_0 ... _1 _0] * _T_h_e _L (_l_e_f_t) _h_a_l_f _i_s _b[_0], _t_h_e _R (_r_i_g_h_t) _h_a_l_f _i_s _b[_1] * */ void enloki(b) _e_n_l_o_k_i cccchhhhaaaarrrr b[LOKIBLK]; {{{{ rrrreeeeggggiiiisssstttteeeerrrr Long L, R; /* _l_e_f_t & _r_i_g_h_t _d_a_t_a _h_a_l_v_e_s */ rrrreeeeggggiiiisssstttteeeerrrr Long KL, KR; /* _l_e_f_t & _r_i_g_h_t _k_e_y _h_a_l_v_e_s */ ####iiiiffffddddeeeeffff LITTLE ENDIAN bswap(b);- /* _s_w_a_p _b_y_t_e_s _r_o_u_n_d _i_f _l_i_t_t_l_e-_e_n_d_i_a_n */ ####eeeennnnddddiiiiffff ####iiiiffff TRACE >= 1 fprintf(stderr," enloki(%08lx, %08lx)\n", ((Long *)b)[0], ((Long *)b)[1]); ####eeeennnnddddiiiiffff KL = lokikey[0]; /* _l_o_a_d _k_e_y_s _i_n _r_e_g_i_s_t_e_r _v_a_r_s */ KR = lokikey[1]; L = ((Long *)b)[0] ^ KL; /* _L_R = _X _X_O_R _K */ R = ((Long *)b)[1] ^ KR; /* _P_e_r_f_o_r_m _t_h_e _1_6 _r_o_u_n_d_s _u_s_i_n_g _s_u_b-_k_e_y_s _i_n _u_s_u_a_l _o_r_d_e_r */ L ^= f(R, KL); ROL12(KL); R ^= f(L, KR); ROL12(KR); L ^= f(R, KL); ROL12(KL); R ^= f(L, KR); ROL12(KR); L ^= f(R, KL); ROL12(KL); R ^= f(L, KR); ROL12(KR); L ^= f(R, KL); ROL12(KL); Appendix C 164 R ^= f(L, KR); ROL12(KR); L ^= f(R, KL); ROL12(KL); R ^= f(L, KR); ROL12(KR); L ^= f(R, KL); ROL12(KL); R ^= f(L, KR); ROL12(KR); L ^= f(R, KL); ROL12(KL); R ^= f(L, KR); ROL12(KR); L ^= f(R, KL); ROL12(KL); R ^= f(L, KR); ROL12(KR); ((Long *)b)[0] = R ^ KR; /* _Y = _s_w_a_p(_L_R) _X_O_R _K */ ((Long *)b)[1] = L ^ KL; ####iiiiffff TRACE >= 1 fprintf(stderr," enloki returns %08lx, %08lx\n", ((Long *)b)[0], ((Long *)b)[1]); ####eeeennnnddddiiiiffff ####iiiiffffddddeeeeffff LITTLE ENDIAN bswap(b);- /* _s_w_a_p _b_y_t_e_s _r_o_u_n_d _i_f _l_i_t_t_l_e-_e_n_d_i_a_n */ ####eeeennnnddddiiiiffff }}}} Appendix C 165 /* * _d_e_l_o_k_i(_b) - _m_a_i_n _L_O_K_I _d_e_c_r_y_p_t_i_o_n _r_o_u_t_i_n_e, _t_h_i_s _r_o_u_t_i_n_e _d_e_c_r_y_p_t_s _o_n_e * _6_4-_b_i_t _b_l_o_c_k _b _u_s_i_n_g _t_h_e _L_O_K_I _a_l_g_o_r_i_t_h_m _w_i_t_h _l_o_k_i_k_e_y * * _D_e_c_r_y_p_t_i_o_n _u_s_e_s _t_h_e _s_a_m_e _a_l_g_o_r_i_t_h_m _a_s _e_n_c_r_y_p_t_i_o_n, _e_x_c_e_p_t _t_h_a_t * _t_h_e _s_u_b_k_e_y_s _a_r_e _u_s_e_d _i_n _r_e_v_e_r_s_e _o_r_d_e_r. */ void deloki(b) _d_e_l_o_k_i cccchhhhaaaarrrr b[LOKIBLK]; {{{{ rrrreeeeggggiiiisssstttteeeerrrr Long L, R; /* _l_e_f_t & _r_i_g_h_t _d_a_t_a _h_a_l_v_e_s */ rrrreeeeggggiiiisssstttteeeerrrr Long KL, KR; /* _l_e_f_t & _r_i_g_h_t _k_e_y _h_a_l_v_e_s */ ####iiiiffffddddeeeeffff LITTLE ENDIAN bswap(b);- /* _s_w_a_p _b_y_t_e_s _r_o_u_n_d _i_f _l_i_t_t_l_e-_e_n_d_i_a_n */ ####eeeennnnddddiiiiffff ####iiiiffff TRACE >= 1 fprintf(stderr," deloki(%08lx, %08lx)\n", ((Long *)b)[0], ((Long *)b)[1]); ####eeeennnnddddiiiiffff KL = lokikey[0]; /* _l_o_a_d _k_e_y_s _i_n _r_e_g_i_s_t_e_r _v_a_r_s */ KR = lokikey[1]; L = ((Long *)b)[0] ^ KR; /* _L_R = _X _X_O_R _K */ R = ((Long *)b)[1] ^ KL; /* _P_e_r_f_o_r_m _t_h_e _1_6 _r_o_u_n_d_s _u_s_i_n_g _s_u_b-_k_e_y_s _i_n _u_s_u_a_l _o_r_d_e_r */ ROR12(KR); L ^= f(R, KR); ROR12(KL); R ^= f(L, KL); ROR12(KR); L ^= f(R, KR); ROR12(KL); R ^= f(L, KL); ROR12(KR); L ^= f(R, KR); ROR12(KL); R ^= f(L, KL); ROR12(KR); L ^= f(R, KR); ROR12(KL); R ^= f(L, KL); ROR12(KR); L ^= f(R, KR); ROR12(KL); R ^= f(L, KL); ROR12(KR); L ^= f(R, KR); ROR12(KL); R ^= f(L, KL); ROR12(KR); L ^= f(R, KR); ROR12(KL); R ^= f(L, KL); ROR12(KR); L ^= f(R, KR); ROR12(KL); R ^= f(L, KL); ((Long *)b)[0] = R ^ KL; /* _Y = _L_R _X_O_R _K */ ((Long *)b)[1] = L ^ KR; ####iiiiffff TRACE >= 1 fprintf(stderr," deloki returns %08lx, %08lx\n", ((Long *)b)[0], ((Long *)b)[1]); Appendix C 166 ####eeeennnnddddiiiiffff ####iiiiffffddddeeeeffff LITTLE ENDIAN bswap(b);- /* _s_w_a_p _b_y_t_e_s _r_o_u_n_d _i_f _l_i_t_t_l_e-_e_n_d_i_a_n */ ####eeeennnnddddiiiiffff }}}} Appendix C 167 /* * _f(_r, _k) - _i_s _t_h_e _c_o_m_p_l_e_x _n_o_n-_l_i_n_e_a_r _L_O_K_I _f_u_n_c_t_i_o_n, _w_h_o_s_e _o_u_t_p_u_t * _i_s _a _c_o_m_p_l_e_x _f_u_n_c_t_i_o_n _o_f _b_o_t_h _i_n_p_u_t _d_a_t_a _a_n_d _s_u_b-_k_e_y. * _T_h_e _i_n_p_u_t _d_a_t_a _R(_i-_1) _i_s: * _a_d_d_e_d _m_o_d_u_l_o _2 _t_o _t_h_e _k_e_y _K(_i) * _e_x_p_a_n_d_e_d _t_o _4_8-_b_i_t_s _v_i_a _e_x_p_a_n_s_i_o_n _f_n _E * _s_u_b_s_t_i_t_u_t_e_d _i_n_t_o _t_h_e _S-_b_o_x_e_s * _p_e_r_m_u_t_e_d _b_y _P. * _i_e _t_h_e _c_a_l_c_u_l_a_t_i_o_n _i_s: * _A = _E(_R(_i-_1) _X_O_R _K(_i)) (_a _4_8-_b_i_t _v_a_l_u_e) * _B = _S(_A) (_a _3_2-_b_i_t _v_a_l_u_e) * _f = _P(_B) (_a _3_2-_b_i_t _v_a_l_u_e) * * _n_b: _t_h_e _1_2-_b_i_t _S-_b_o_x _i_n_p_u_t _v_a_l_u_e [_x _x _x _x _1_1 _1_0 _9 ... _3 _2 _1 _0] * _i_s _i_n_t_e_r_p_r_e_t_e_d _a_s: * _b_i_t_s [_1_1 _1_0 _1 _0] _s_e_l_e_c_t _1 _o_f _1_6 _r_o_w_s _w_i_t_h_i_n _e_a_c_h _b_o_x, * _b_i_t_s [_9 _8 ... _3 _2] _t_h_e_n _s_e_l_e_c_t _a _c_o_l_u_m_n _w_i_t_h_i_n _t_h_a_t _r_o_w */ ####ddddeeeeffffiiiinnnneeee MASK12 0x0fff /* _1_2 _b_i_t _m_a_s_k _f_o_r _e_x_p_a_n_s_i_o_n _E */ ssssttttaaaattttiiiicccc Long f(r, k) _f rrrreeeeggggiiiisssstttteeeerrrr Long r; /* _D_a_t_a _v_a_l_u_e _R(_i-_1) */ Long k; /* _K_e_y _K(_i) */ {{{{ Long a, b, c; /* _3_2 _b_i_t _S-_b_o_x _o_u_t_p_u_t, & _P _o_u_t_p_u_t */ a = r ^ k; /* _A = _R(_i-_1) _X_O_R _K(_i) */ b = ((Long)s((a & MASK12)) ) | /* _B = _S(_E(_R(_i-_1)) _X_O_R _K(_i)) */ ((Long)s(((a >> 8) & MASK12)) << 8) | ((Long)s(((a >> 16) & MASK12)) << 16) | ((Long)s((((a >> 24) | (a << 8)) & MASK12)) << 24); perm32(&c, &b, P); /* _C = _P(_S( _E(_R(_i-_1)) _X_O_R _K(_i))) */ ####iiiiffff TRACE >= 2 /* _I_f _T_r_a_c_i_n_g, _d_u_m_p _A, _K(_i), _a_n_d _f(_R(_i-_1),_K(_i)) */ fprintf(stderr," f(%08lx, %08lx) = P.S(%08lx) = P(%08lx) = %08lx\n", r, k, a, b, c); ####eeeennnnddddiiiiffff rrrreeeettttuuuurrrrnnnn(c); /* _f _r_e_t_u_r_n_s _t_h_e _r_e_s_u_l_t _C */ }}}} Appendix C 168 /* * _s(_i) - _r_e_t_u_r_n _S-_b_o_x _v_a_l_u_e _f_o_r _i_n_p_u_t _i */ ssssttttaaaattttiiiicccc sssshhhhoooorrrrtttt s(i) rrrreeeeggggiiiisssstttteeeerrrr Long i; /* _r_e_t_u_r_n _S-_b_o_x _v_a_l_u_e _f_o_r _i_n_p_u_t _i */ {{{{ rrrreeeeggggiiiisssstttteeeerrrr sssshhhhoooorrrrtttt r, c, v, t; r = ((i>>8) & 0xc) | (i & 0x3); /* _r_o_w _v_a_l_u_e */ c = (i>>2) & 0xff; /* _c_o_l_u_m_n _v_a_l_u_e */ t = c ^ r; /* _b_a_s_e _v_a_l_u_e _f_o_r _S_f_n */ v = exp8(t, sfn[r].exp, sfn[r].gen); /* _S_f_n[_r] = _t ^ _e_x_p _m_o_d _g_e_n */ ####iiiiffff TRACE >= 2 fprintf(stderr, " s(%lx=[%d,%d]) = %x sup %d mod %d = %x\n", i, r, c, t, sfn[r].exp, sfn[r].gen, v); ####eeeennnnddddiiiiffff rrrreeeettttuuuurrrrnnnn(v); }}}} /* * _p_e_r_m_3_2(_o_u_t, _i_n, _p_e_r_m) _i_s _t_h_e _g_e_n_e_r_a_l _p_e_r_m_u_t_a_t_i_o_n _o_f _a _3_2-_b_i_t _i_n_p_u_t * _b_l_o_c_k _t_o _a _3_2-_b_i_t _o_u_t_p_u_t _b_l_o_c_k, _u_n_d_e_r _t_h_e _c_o_n_t_r_o_l _o_f _a * _p_e_r_m_u_t_a_t_i_o_n _a_r_r_a_y _p_e_r_m. _E_a_c_h _e_l_e_m_e_n_t _o_f _p_e_r_m _s_p_e_c_i_f_i_e_s _w_h_i_c_h * _i_n_p_u_t _b_i_t _i_s _t_o _b_e _p_e_r_m_u_t_e_d _t_o _t_h_e _o_u_t_p_u_t _b_i_t _w_i_t_h _t_h_e _s_a_m_e * _i_n_d_e_x _a_s _t_h_e _a_r_r_a_y _e_l_e_m_e_n_t. * * _n_b: _t_o _s_e_t _b_i_t_s _i_n _t_h_e _o_u_t_p_u_t _w_o_r_d, _a_s _m_a_s_k _w_i_t_h _a _s_i_n_g_l_e _1 _i_n _i_t _i_s * _u_s_e_d. _O_n _e_a_c_h _s_t_e_p, _t_h_e _1 _i_s _s_h_i_f_t_e_d _i_n_t_o _t_h_e _n_e_x_t _l_o_c_a_t_i_o_n */ ####ddddeeeeffffiiiinnnneeee MSB 0x80000000L /* _M_S_B _o_f _3_2-_b_i_t _w_o_r_d */ perm32(out, in , perm) _p_e_r_m_3_2 Long *out; /* _O_u_t_p_u_t _3_2-_b_i_t _b_l_o_c_k _t_o _b_e _p_e_r_m_u_t_e_d */ Long *in; /* _I_n_p_u_t _3_2-_b_i_t _b_l_o_c_k _a_f_t_e_r _p_e_r_m_u_t_a_t_i_o_n */ cccchhhhaaaarrrr perm[32]; /* _P_e_r_m_u_t_a_t_i_o_n _a_r_r_a_y */ {{{{ Long mask = MSB; /* _m_a_s_k _u_s_e_d _t_o _s_e_t _b_i_t _i_n _o_u_t_p_u_t */ rrrreeeeggggiiiisssstttteeeerrrr iiiinnnntttt i, o, b; /* _i_n_p_u_t _b_i_t _n_o, _o_u_t_p_u_t _b_i_t _n_o, _v_a_l_u_e */ rrrreeeeggggiiiisssstttteeeerrrr cccchhhhaaaarrrr *p = perm; /* _p_t_r _t_o _p_e_r_m_u_t_a_t_i_o_n _a_r_r_a_y */ *out = 0; /* _c_l_e_a_r _o_u_t_p_u_t _b_l_o_c_k */ ffffoooorrrr (o=0; o<32; o++) {{{{ /* _F_o_r _e_a_c_h _o_u_t_p_u_t _b_i_t _p_o_s_i_t_i_o_n _o */ i =(iiiinnnntttt)*p++; /* _g_e_t _i_n_p_u_t _b_i_t _p_e_r_m_u_t_e_d _t_o _o_u_t_p_u_t _o */ b = (*in >> i) & 01; /* _v_a_l_u_e _o_f _i_n_p_u_t _b_i_t _i */ iiiiffff (b) /* _I_f _t_h_e _i_n_p_u_t _b_i_t _i _i_s _s_e_t */ *out |= mask; /* _O_R _i_n _m_a_s_k _t_o _o_u_t_p_u_t _i */ mask >>= 1; /* _S_h_i_f_t _m_a_s_k _t_o _n_e_x_t _b_i_t */ }}}} }}}} Appendix C 169 Appendix C 170 Appendix C BBBBiiiibbbblllliiiiooooggggrrrraaaapppphhhhyyyy [ASA85] ASA, "_E_l_e_c_t_r_o_n_i_c_s _F_u_n_d_s _T_r_a_n_s_f_e_r - _R_e_q_u_i_r_e_m_e_n_t_s _f_o_r _I_n_t_e_r_f_a_c_e_s, _P_a_r_t _5, _D_a_t_a _E_n_c_r_y_p_t_i_o_n _A_l_g_o_r_i_t_h_m," AS2805.5-1985, Standards Association of Australia, Sydney, Australia, 1985. [AdS82] W. Adams and D. Shanks, "Strong Primality Tests That Are Not Sufficient," _M_a_t_h_e_m_a_t_i_c_s _o_f _C_o_m_p_u_t_a_t_i_o_n, vol. 39, no. 159, pp. 255-300, |July| 1982. [AdT90] C. Adams and S. Tavares, "Good S-boxes are easy to find," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _C_R_Y_P_T_O'_8_9, Lecture Notes in Computer Science, no. 435, G. Brassard (editor), pp. 612-615, |Springer Verlag|, Berlin, 1990. [APR83] L. M. Adleman, C. Pomerance and R. S. Rumlely, "On Distinguishing Prime Numbers from Composite Numbers," _A_n_n_a_l_s _o_f _M_a_t_h_e_m_a_t_i_c_s, vol. 117, pp. 173-206, 1983. [AHU74] A. V. Aho, J. E. Hopcroft and J. D. Ullman, _T_h_e _D_e_s_i_g_n _a_n_d _A_n_a_l_y_s_i_s _o_f _C_o_m_p_u_t_e_r _A_l_g_o_r_i_t_h_m_s, |Addison Wesley, Reading, Mass., 1974. [AAA83] "_I_n_f_o_r_m_a_t_i_o_n _I_n_t_e_r_c_h_a_n_g_e - _D_a_t_a _E_n_c_r_y_p_t_i_o_n _A_l_g_o_r_i_t_h_m - _M_o_d_e_s _o_f _O_p_e_r_a_t_i_o_n," American National Standards Institute X3.106-1983, American National Standards Institute, New York, 1983. [AnR82] D. Andelman and J. Reeds, "On the Cryptanalysis of Rotor Machines and Substitution-Permutation Networks," |_I_E_E_E _T_r_a_n_s. _I_n_f. _T_h_e_o_r_y|, vol. IT- 28, no. 4, pp. 578-584, |July| 1982. [Aru85] A. A. Aruliah, "_P_a_s_c_a_l _I_m_p_l_e_m_e_n_t_a_t_i_o_n _o_f _t_h_e _R_S_A _A_l_g_o_r_i_t_h_m," NPL-DITC-66/85, National Physical Lab., Div. of Information Technology and Computing, Teddington (England), |September.| 1985. 171 172 [BeP82] H. Beker and F. Piper, _C_i_p_h_e_r _S_y_s_t_e_m_s: _T_h_e _P_r_o_t_e_c_t_i_o_n _o_f _C_o_m_m_u_n_i_c_a_t_i_o_n_s, Northwood Books, London, 1982. [Bek84] H. J. Beker, "A Survey of Encryption Algorithms," in |_P_r_o_c.| _1_9_8_4 |_I_n_t.| |_C_o_n_f.| _o_n _S_e_c_u_r_e _C_o_m_m_u_n_i_c_a_t_i_o_n_s _S_y_s_t_e_m_s, pp. 14-19, IEE, London, 22-23 |February.| 1984. [BKS79] S. Berkovits, J. Kowalchuk and B. Schanning, "Implementing Public Key Scheme," _I_E_E_E _C_o_m_m_u_n_i_c_a_t_i_o_n_s _M_a_g_a_z_i_n_e, vol. 17, pp. 2-3, |May| 1979. [Ber82] T. A. Berson, "Long Key Variants of DES," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - |_P_r_o_c.| _o_f _C_r_y_p_t_o _8_2, D. Chaum, R. L. Rivest and A. T. Sherman (editors), pp. 311-313, Plenum Press, New York, |August.| 23-25, 1982. [BiS90] E. Biham and A. Shamir, "_D_i_f_f_e_r_e_n_t_i_a_l _C_r_y_p_t_a_n_a_l_y_s_i_s _o_f _D_E_S-_l_i_k_e _C_r_y_p_t_o_s_y_s_t_e_m_s," Technical Report, Weizmann Institute of Science, Rehovot, Israel, 19 July 1990. [Bla83] G. R. Blakley, "A Computer Algorithm for Calculating the Product AB Modulo M," _I_E_E_E |_T_r_a_n_s.| _o_n _C_o_m_p_u_t_e_r_s, vol. C-32, no. 5, pp. 497-500, |May| 1983. [Boe89] B. D. Boer, "Cryptanalysis of F.E.A.L," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _E_u_r_o_c_r_y_p_t'_8_8, Lecture Notes in Computer Science, no. 330, C. G. Gunther (editor), pp. 293-300, |Springer Verlag|, Berlin, 1989. [BoB86] A. W. Bojanczyk and R. P. Brent, "A Systolic Algorithm for Extended GCD Computation," in |_P_r_o_c.| _9_t_h _A_u_s_t_r_a_l_i_a_n _C_o_m_p_u_t_e_r _S_c_i_e_n_c_e |_C_o_n_f.|, pp. 129-137, ANU, Canberra, Australia, |January.| 29-31, 1986. [Bon84] D. J. Bond, "Practical Primality Testing," in |_P_r_o_c.| _o_f |_I_n_t.| |_C_o_n_f.| _o_n _S_e_c_u_r_e _C_o_m_m_u_n_i_c_a_t_i_o_n _S_y_s_t_e_m_s, pp. 50-53, IEE, 22-23 |February.| 1984. [BGK77] D. K. Branstead, J. Gait and S. Katzke, "_R_e_p_o_r_t _o_f _t_h_e _W_o_r_k_s_h_o_p _o_n _C_r_y_p_t_o_g_r_a_p_h_y _i_n _S_u_p_p_o_r_t _o_f _C_o_m_p_u_t_e_r _S_e_c_u_r_i_t_y," NBSIR 77-1291, National Bureau of Standards, |September.| 1977. Bibliography 173 [Bra79] G. Brassard, "A Note on the Complexity of Cryptography," |_I_E_E_E _T_r_a_n_s. _I_n_f. _T_h_e_o_r_y|, vol. IT-25, no. 2, pp. 232-233, |March.| 1979. [Bre86] R. P. Brent, "Some Integer Factorization Algorithms using Elliptic Curves," in |_P_r_o_c.| _9_t_h _A_u_s_t_r_a_l_i_a_n _C_o_m_p_u_t_e_r _S_c_i_e_n_c_e |_C_o_n_f.|, pp. 149-163, ANU, Canberra, Australia, |January.| 29-31, 1986. [Bri82] E. F. Brickell, "A Fast Modular Multiplication Algorithm with Application to Two Key Cryptography," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - |_P_r_o_c.| _o_f _C_r_y_p_t_o _8_2, D. Chaum, R. L. Rivest and A. T. Sherman (editors), pp. 51-60, Plenum Press, New York, |August.| 23-25, 1982. [BMP87] E. F. Brickell, J. H. Moore and M. R. Purtill, _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - |_P_r_o_c.| _o_f _C_R_Y_P_T_O'_8_6, Lecture Notes in Computer Science, no. 263, pp. 3-8, |Springer Verlag|, Berlin, 1987. [Bri90] E. F. Brickell, "A survey of hardware implementations of RSA," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _C_R_Y_P_T_O'_8_9, Lecture Notes in Computer Science, no. 435, G. Brassard (editor), pp. 368-370, |Springer Verlag|, Berlin, 1990. [BBB86] "_A_d_v_a_n_c_e _I_n_f_o_r_m_a_t_i_o_n _o_n _t_h_e _M_e_t_e_o_r _V_L_S_I _P_u_b_l_i_c _K_e_y _D_e_v_i_c_e," TA10.1.2, British Telecom, Ipswich UK, |April.| 1986. [Bro87] L. P. Brown, "Implementation of RSA ," in _S_e_c_u_r_e _D_a_t_a _C_o_m_m_u_n_i_c_a_t_i_o_n_s _W_o_r_k_s_h_o_p - _D_i_g_e_s_t _o_f _P_a_p_e_r_s, J. Snare (editor), IEEE, Melbourne, Australia, 31 |July| 1987. [BPS89] L. Brown, J. Pieprzyk and J. Seberry, "_L_O_K_I - _A _C_r_y_p_t_o_g_r_a_p_h_i_c _P_r_i_m_i_t_i_v_e _f_o_r _A_u_t_h_e_n_t_i_c_a_t_i_o_n _a_n_d _S_e_c_r_e_c_y _A_p_p_l_i_c_a_t_i_o_n_s," RIPE Submission Annex, CCSR, Canberra, Australia, |September.| 1989. [Bro89] L. Brown, "A Proposed Design for an Extended DES," in _C_o_m_p_u_t_e_r _S_e_c_u_r_i_t_y _i_n _t_h_e _A_g_e _o_f _I_n_f_o_r_m_a_t_i_o_n, W. J. Caelli (editor), North- Holland, Amsterdam, 1989. [Bro90a] L. Brown, "Technical Options for Implementing Pay-TV in an Australian Context," _A_u_s_t_r_a_l_i_a_n _T_e_l_e_c_o_m_m_u_n_i_c_a_t_i_o_n_s _R_e_v_i_e_w , |November.| 1990. Bibliography 174 [Bro90b] L. Brown, "SECLOG - A Secure Remote Login Frontend and Shell," _A_u_s_t_r_a_l_i_a_n _U_n_i_x _U_s_e_r_s _G_r_o_u_p _N_e_w_s_l_e_t_t_e_r, vol. 11, no. 2, pp. 18-26, |April.| 1990. [BrS90a] L. Brown and J. Seberry, "On the Design of Permutation P in DES Type Cryptosystems," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _E_u_r_o_c_r_y_p_t'_8_9, Lecture Notes in Computer Science, no. 434, J. J. Quisquater and J. Vanderwalle (editors), pp. 696-705, |Springer Verlag|, Berlin, 1990. [BrS90b] L. Brown and J. Seberry, "Key Scheduling in DES Type Cryptosystems," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y: _A_u_s_c_r_y_p_t '_9_0, Lecture Notes in Computer Science, no. 453, pp. 221-228, |Springer Verlag|, Berlin, 1990. [Bro90] L. Brown, "Secure Remote Login - the SECLOG option," in _A_U_U_G _9_0 _C_o_n_f_e_r_e_n_c_e _P_r_o_c_e_e_d_i_n_g_s, pp. 309-320, Australian UNIX Systems Users Group, Sydney, NSW, Australia, |September.| 1990. [Bur84] C. E. Burton, "RSA: A Public Key Cryptosystem, Parts 1 and 2," _D_o_c_t_o_r _D_o_b_b_s _J_o_u_r_n_a_l, vol. 9, no. 3,4, pp. 16-43, 32-59, March - April 1984. [Chi84] H. R. Chivers, "A Practical Fast Exponentiation Algorithm for Public-Key," in |_P_r_o_c.| _o_f |_I_n_t.| |_C_o_n_f.| _o_n _S_e_c_u_r_e _C_o_m_m_u_n_i_c_a_t_i_o_n _S_y_s_t_e_m_s, pp. 54-58, IEE, 22-23 |February.| 1984. [CoL84] H. Cohen and H. W. Lenstra, "Primality Testing and Jacobi Sums," _M_a_t_h_e_m_a_t_i_c_s _o_f _C_o_m_p_u_t_a_t_i_o_n, vol. 42, no. 165, pp. 297-330, |January.| 1984. [Coo83] S. A. Cook, "An Overview of Computational Complexity," |_C_o_m_m. _o_f _t_h_e _A_C_M|, vol. 26, no. 6, pp. 401-408, |June| 1983. [CoQ82] C. Couvreur and J. J. Quisquater, "An Introduction to Fast Generation of Large Prime Numbers," _P_h_i_l_i_p_s _J. _R_e_s_e_a_r_c_h, vol. 37, no. 5- 6, pp. 231-264, Philips Research Labs, Brussels, Belgium, 1982. [Cox58] D. R. Cox, _P_l_a_n_n_i_n_g _o_f _E_x_p_e_r_i_m_e_n_t_s, Wiley Series in Probability and Mathematical Statistics, |John Wiley & Sons, New York, 1958. Bibliography 175 [Coy85] M. Coyne, "_A_n _I_m_p_l_e_m_e_n_t_a_t_i_o_n _o_f _a _P_u_b_l_i_c _K_e_y _C_r_y_p_t_o_s_y_s_t_e_m," Honours Thesis, Basser Department of Computer Science, University of Sydney, Australia, |November.| 13, 1985. [Dav82] D. W. Davies, "Some Regular Properties of the Data Encryption Standard," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - |_P_r_o_c.| _o_f _C_r_y_p_t_o _8_2, D. Chaum, R. L. Rivest and A. T. Sherman (editors), pp. 89- 96, Plenum Press, New York, |August.| 23-25, 1982. [Dav83] D. W. Davies, "Applying the RSA Digital Signature to Electronic Mail," |_I_E_E_E _C_o_m_p_u_t_e_r_s|, vol. C-16, no. 2, pp. 55-62, |February.| 1983. [DHS84] J. A. Davies, D. B. Holdridge and G. J. Simmons, "Status Report on Factoring (At the Sandia National Laboratories)," in _A_d_v_a_n_c_e_s _I_n _C_r_y_p_t_o_l_o_g_y: |_P_r_o_c.| _o_f _E_u_r_o_c_r_y_p_t _8_4, Lecture Notes in Computer Science, no. 209, T. Beth, N. Cot and I. Ingemarsson (editors), pp. 183-215, |Springer Verlag|, Berlin, |April.| 1984. [DaP89] D. W. Davies and W. L. Price, _S_e_c_u_r_i_t_y _f_o_r _C_o_m_p_u_t_e_r _N_e_t_w_o_r_k_s, John Wiley and Sons, New York, 1989. (2nd edn). [DDF83] M. Davio, Y. Desmedt, M. Fosseprez, R. Govaerts, J. Hulsbosch, P. Neutjens, P. Piret, J. Quisquater, J. Vanderwalle and P. Wouters, "Analytical Characteristics of the DES," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - |_P_r_o_c.| _o_f _C_r_y_p_t_o _8_3, D. Chaum, R. L. Rivest and A. T. Sherman (editors), pp. 171-202, Plenum Press, New York, |August.| 22-24, 1983. [Dem89] N. Demytko, "Generating Multiprecision Integers with Guaranteed Primality," in _C_o_m_p_u_t_e_r _S_e_c_u_r_i_t_y _i_n _t_h_e _A_g_e _o_f _I_n_f_o_r_m_a_t_i_o_n, W. J. Caelli (editor), North-Holland, Amsterdam, 1989. [DeK74] J. Denes and A. D. Keedwell, _L_a_t_i_n _S_q_u_a_r_e_s _a_n_d _t_h_e_i_r _A_p_p_l_i_c_a_t_i_o_n_s, English Universities Press Limited, London UK, 1974. [Den82] D. E. Denning, _C_r_y_p_t_o_g_r_a_p_h_y _a_n_d _D_a_t_a _S_e_c_u_r_i_t_y, Addison-Wesley, 1982. Bibliography 176 [Den83] D. E. Denning, "Protecting Public Keys and Signature Keys," |_I_E_E_E _C_o_m_p_u_t_e_r_s|, vol. C-16, no. 2, pp. 27-35, |February.| 1983. [Den84] D. E. Denning, "Digital Signatures with RSA and Other Public-Key Cryptosystems," |_C_o_m_m. _o_f _t_h_e _A_C_M|, vol. 27, no. 4, pp. 388-392, |April.| 1984. [Des84] Y. Desmedt, "_A_n_a_l_y_s_i_s _o_f _t_h_e _S_e_c_u_r_i_t_y _a_n_d _N_e_w _A_l_g_o_r_i_t_h_m_s _f_o_r _M_o_d_e_r_n _I_n_d_u_s_t_r_i_a_l _C_r_y_p_t_o_g_r_a_p_h_y," PhD Disertation, Department Elektrorechniek, Faculteit der Toegepaste Wetenschappen, Katholieke Universiteit, Leuven, |October.| 1984. [DiH76] W. Diffie and M. E. Hellman, "New Directions In Cryptography," _I_E_E_E |_T_r_a_n_s.| _o_n _I_n_f_o_r_m_a_t_i_o_n _T_h_e_o_r_y, vol. IT-22, no. 6, pp. 644-654, |November.| 1976. [DiH77] W. Diffie and M. E. Hellman, "Exhaustive Cryptanalysis of the NBS Data Encryption Standard," _C_o_m_p_u_t_e_r, vol. 10, no. 6, pp. 74-84, |June| 1977. [DiH79] W. Diffie and M. E. Hellman, "Privacy and Authentication: An Introduction to Cryptography," _P_r_o_c _I_E_E_E, vol. 67, no. 3, pp. 397-427, |March.| 1979. [Dus91] S. Dusse, "A Cryptographic Library for the Motorola DSP 56000," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _E_u_r_o_c_r_y_p_t'_9_0, Lecture Notes in Computer Science, no. 473, I. B. Damgard (editor), pp. 230-244, |Springer Verlag|, Berlin, 1991. [ElG85] T. ElGamal, "A Public Key Cryptosystem and a Signature System Based in Discrete Logarithms," _I_E_E_E |_T_r_a_n_s.| _o_n _I_n_f_o_r_m_a_t_i_o_n _T_h_e_o_r_y, vol. IT-31, no. 4, pp. 469-472, |July| 1985. [Fam82] B. W. Fam, "A Parallel/Pipeline Processor For Fast Exponentiation," |_P_r_o_c.| _1_9_8_2 |_I_n_t.| |_C_o_n_f.| _o_n _P_a_r_a_l_l_e_l _P_r_o_c_e_s_s_i_n_g , pp. 316-318, 1982. [Fei73] H. Feistel, "Cryptography and Computer Privacy," _S_c_i_e_n_t_i_f_i_c _A_m_e_r_i_c_a_n, vol. 228, no. 5, pp. 15- 23, |May| 1973. Bibliography 177 [FNS75] H. Feistel, W. A. Notz and J. L. Smith, "Some Cryptographic Techniques for Machine-to-Machine Data Communications," |_P_r_o_c.| _I_E_E_E, vol. 63, no. 11, pp. 1545-1554, |November.| 1975. [Gai79] J. Gait, "Can the Mitre Public Key System Be Short-Cycled?," _I_E_E_E _C_o_m_m_u_n_i_c_a_t_i_o_n_s _M_a_g_a_z_i_n_e, vol. 17, pp. 2-3, |November.| 1979. [Gir71] M. B. Girsdansky, "Data Privacy - Cryptology and the Computer at IBM Research," _I_B_M _R_e_s_e_a_r_c_h _R_e_p_o_r_t_s, vol. 7, no. 4, pp. 1-12, IBM Research, Yorktown Heights, New York, 1971. [Gol82] S. Golomb, _S_h_i_f_t _R_e_g_i_s_t_e_r _S_e_q_u_e_n_c_e_s, Aegean Park Press, 1982. [Gor84] J. Gordon, "Strong RSA keys," _E_l_e_c_t_r_o_n_i_c_s _L_e_t_t_e_r_s, vol. 20, no. 12, pp. 514-516, |June| 1984. [GrT78] E. K. Grossman and B. Tuckerman, "Analysis of a Weakened Feistel-Like Cipher," in |_P_r_o_c.| _1_9_7_8 _I_E_E_E |_C_o_n_f.| _O_n _C_o_m_m_u_n_i_c_a_t_i_o_n_s, pp. 46.3.1-5, IEEE, 1978. [Hel79a] M. E. Hellman, "DES will be totally insecure within ten years," _S_P_E_C_T_R_U_M, vol. 16, no. 7, pp. 31-41, |July| 1979. With rebuttals from George I. Davida, Walter Tuchman, and Dennis Branstad. [Hel79b] M. E. Hellman, "The Mathematics of Public-Key Cryptography," _S_c_i_e_n_t_i_f_i_c _A_m_e_r_i_c_a_n, vol. 241, pp. 146-157, 1979. [Hen81] P. S. Henry, "Fast Decryption Algorithm for the Knapsack Cryptographic System," _B_e_l_l _S_y_s_t_e_m _T_e_c_h_n_i_c_a_l _J_o_u_r_n_a_l, vol. 60, no. 5, pp. 767-773, Bell Labs, May-June 1981. [Her78] T. E. Herlestam, "Critical Remarks on Some Public Key Cryptosystems," _B_i_t, vol. 18, no. 4, pp. 493-496, 1978. [HeJ81] T. Herlestam and R. Johannesson, "On Computing Logarithms Over GF(2^p), or an Attempt to Swindle Mitre Corporation," in _1_9_8_1 _I_E_E_E |_I_n_t.| _S_y_m_p_o_s_i_u_m _o_n _I_n_f_o_r_m_a_t_i_o_n _T_h_e_o_r_y - _A_b_s_t_r_a_c_t_s _o_f _P_a_p_e_r_s , p. 47, 1981. Bibliography 178 [Her80] J. E. Hershey, "Implementation of Mitre Public Key Cryptographic System," _E_l_e_c_t_r_o_n_i_c_s _L_e_t_t_e_r_s, vol. 16, no. 24, pp. 930-931, |November.| 1980. [HGD84] F. Hoornaert, J. Goubert and Y. Desmedt, "Efficient Hardware Implementation of the DES," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y: |_P_r_o_c.| _o_f _C_r_y_p_t_o _8_4, Lecture Notes in Computer Science, no. 196, G. R. Blakley and D. Chaum (editors), pp. 147-173, |Springer Verlag|, Berlin, |August.| 1984. [HDV89] F. Hoornaert, M. Decroos, J. Vanderwalle and R. Govaerts, "Fast RSA Hardware: Dream or Reality?," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _E_u_r_o_c_r_y_p_t'_8_8, Lecture Notes in Computer Science, no. 330, C. G. Gunther (editor), pp. 257-266, |Springer Verlag|, Berlin, 1989. [Ins81] "" A. N. S. Institute, ed., "_D_a_t_a _E_n_c_r_y_p_t_i_o_n _A_l_g_o_r_i_t_h_m," American National Standards Institute X3.92-1981, American National Standards Institute, New York, 1981. [JMN84] A. M. Jackson, N. A. McEvoy and B. B. Newman, "The Project Universe Experiment," in |_P_r_o_c.| _1_9_8_4 |_I_n_t.| |_C_o_n_f.| _o_n _S_e_c_u_r_e _C_o_m_m_u_n_i_c_a_t_i_o_n_s _S_y_s_t_e_m_s, pp. 14-19, IEE, London, 22-23 |February.| 1984. [Jan87] A. Janiak, "_E_D_S_P-_2_4_7 _E_n_c_r_y_p_t_i_o_n _C_h_i_p_s_e_t," Product Info, Kencomp - A Division of Janiak Holdings Pty. Ltd., 2 Regina Street, Kilsyth, Vic 3137, Australia, 1987. [KaD79] J. B. Kam and G. I. Davida, "Structured Design of Substitution-Permutation Encryption Networks," |_I_E_E_E _T_r_a_n_s. _o_n _C_o_m_p_u_t_e_r_s|, vol. C- 28, no. 10, pp. 747-753, |October.| 1979. [KBS86a] D. Khoo, D. J. Bird and J. Seberry, "_E_n_c_r_y_p_t_i_o_n _e_x_p_o_n_e_n_t_s _3 _a_n_d _t_h_e _s_e_c_u_r_i_t_y _o_f _R_S_A," Tech. Rep. 275, Basser Dept. of Computer Science, Uni. of Sydney, 1986. [KBS86b] D. Khoo, D. J. Bird and J. Seberry, "Encryption Exponent 3 and the Security of RSA," _E_u_r_o_c_r_y_p_t _8_6 - _A_b_s_t_r_a_c_t_s _o_f _P_a_p_e_r_s , Linkoping, Sweden, 20-22 May 1986. also Journal Cryptology (to appear). Bibliography 179 [Knu81] D. E. Knuth, _S_e_m_i_n_u_m_e_r_i_c_a_l _A_l_g_o_r_i_t_h_m_s, The Art of Computer Programming, no. 2, |Addison Wesley, London, 1981. [Koh78] L. M. Kohnfelder, "On the Signature Reblocking Problem in Public-Key Cryptosystems," |_C_o_m_m. _o_f _t_h_e _A_C_M|, vol. 21, no. 2, p. 179, |February.| 1978. [Kon86] A. G. Konheim, _C_r_y_p_t_o_g_r_a_p_h_y, Seminars of Excellence, ORSYS Institute, Amsterdam, |June| 9-11, 1986. notes from a seminar series. [KrR82a] D. W. Kravitz and I. S. Reed, "Extension of RSA Crypto-Structure: A Galois Approach," _E_l_e_c_t_r_o_n_i_c_s _L_e_t_t_e_r_s, vol. 18, no. 6, pp. 255- 256, |March.| 1982. [KrR82b] D. W. Kravitz and I. S. Reed, "Comment: on Extension of RSA Cryptostructure: A Galois Approach," _E_l_e_c_t_r_o_n_i_c_s _L_e_t_t_e_r_s, vol. 18, no. 13, pp. 582-583, |June| 1982. [Lem79] A. Lempel, "Cryptology In Transition," |_C_o_m_p_u_t_i_n_g _S_u_r_v_e_y_s|, vol. 11, no. 4, pp. 285- 303, |December.| 1979. [Llo90] S. Lloyd, "Counting Functions Satisfying a Higher Order Strict Avalanche Criterion," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _E_u_r_o_c_r_y_p_t'_8_9, Lecture Notes in Computer Science, no. 434, J. J. Quisquater and J. Vanderwalle (editors), pp. 63-74, |Springer Verlag|, Berlin, 1990. [MTI86] T. Matsumoto, Y. Takashima and H. Imai, "On Seeking Smart Public-Key-Distribution Systems," |_T_r_a_n_s.| _I_E_C_E _o_f _J_a_p_a_n, vol. E69, no. 2, pp. 99-106, IECE, |February.| 1986. [Mau90] U. M. Maurer, "Fast generation of secure RSA- products with almost maximal diversity," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _E_u_r_o_c_r_y_p_t'_8_9, Lecture Notes in Computer Science, no. 434, J. J. Quisquater and J. Vanderwalle (editors), pp. 636-647, |Springer Verlag|, Berlin, 1990. [Mer78] R. C. Merkle, "Secure Communications Over Insecure Channels," |_C_o_m_m. _o_f _t_h_e _A_C_M|, vol. 21, no. 4, pp. 294-299, |April.| 1978. Bibliography 180 [Mer89] R. C. Merkle, "_A _S_o_f_t_w_a_r_e _E_n_c_r_y_p_t_i_o_n _F_u_n_c_t_i_o_n," Technical Report, Xerox PARC, Pala Alto, CA, 1989. on 13 July 1989"" also released as USEnet news article in "sci.crypt" on 13 July 1989. [Mey78] C. H. Meyer, "Ciphertext/plaintext and ciphertext/key dependence vs number of rounds for the data encryption standard," in _A_F_I_P_S |_C_o_n_f.| |_P_r_o_c.| _4_7, pp. 1119-1126, AFIPS Press, Montvale NJ, USA, |June| 1978. [MeM82] C. H. Meyer and S. M. Matyas, _C_r_y_p_t_o_g_r_a_p_h_y: _A _N_e_w _D_i_m_e_n_s_i_o_n _i_n _D_a_t_a _S_e_c_u_r_i_t_y, |John Wiley & Sons, New York, 1982. [Miy88] S. Miyaguchi, "FEAL-8 LSI chip with the speed of 12Mbyte/s," _N_i_k_k_e_i _E_l_e_c_t_r_o_n_i_c_s , 8 |February.| 1988. [Miy90] S. Miyaguchi, "The FEAL-8 cryptosystem and a call for attack," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _C_R_Y_P_T_O'_8_9, Lecture Notes in Computer Science, no. 435, G. Brassard (editor), pp. 624-627, |Springer Verlag|, Berlin, 1990. [MoA85] S. B. Mohan and B. S. Adiga, "Fast Algorithms for Implementing RSA Public Key Cryptosystem," _E_l_e_c_t_r_o_n_i_c_s _L_e_t_t_e_r_s, vol. 21, no. 17, p. 761, |August.| 1985. [Mon76] D. C. Montgomery, _D_e_s_i_g_n _a_n_d _A_n_a_l_y_s_i_s _o_f _E_x_p_e_r_i_m_e_n_t_s, |John Wiley & Sons, New York, 1976. [MoT86] T. E. Moore and S. E. Tavares, "A Layered Approach to the Design of Private Key Crypto systems," in _P_r_o_c_e_e_d_i_n_g_s _o_f _C_r_y_p_t_o _8_5, Lecture Notes in Computer Science, no. 218, pp. 227-245, Springer-Verlag, 1986. [MoS86] J. H. Moore and G. J. Simmons, "Cycle Structure of the Weak and Semi-Weak DES Keys," _E_u_r_o_c_r_y_p_t _8_6 - _A_b_s_t_r_a_c_t_s _o_f _P_a_p_e_r_s , p. 2.1, Linkoping, Sweden, 20-22 |May| 1986. [MoS87] J. H. Moore and G. J. Simmons, _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - |_P_r_o_c.| _o_f _C_R_Y_P_T_O'_8_6, Lecture Notes in Computer Science, no. 263, pp. 9-32, |Springer Verlag|, Berlin, 1987. [Mor86] T. M. Morris-Yates, "_A_n _n_M_O_S _V_L_S_I _I_m_p_l_e_m_e_n_t_a_t_i_o_n _o_f _a _D_a_t_a _E_n_c_r_y_p_t_i_o_n _A_l_g_o_r_i_t_h_m," BEng Honours Bibliography 181 Thesis, School of Electrical Engineering, Uni. Sydney, |November.| 1986. [Mor83] D. R. Morrison, "Subtractive Encryptors- Alternatives to the DES," |_S_I_G_A_C_T _N_e_w_s|, vol. 15, no. 1, pp. 67-77, SPRING 1983. [Mul83] C. Muller-Schloer, "A Microprocessor-based Cryptoprocessor," _I_E_E_E _M_i_c_r_o , pp. 5-15, |October.| 1983. [MNW84] R. Mullin, E. Nemeth and N. Weidenhofer, "Will Public Key Cryptosystems Live up to Their Expectations?," in |_P_r_o_c.| _1_9_8_4 |_I_n_t.| _J_o_i_n_t |_C_o_n_f.| _o_n _P_a_r_a_l_l_e_l _P_r_o_c_e_s_s_i_n_g, pp. 193-196, 1984. [NBS77] NBS, "_D_a_t_a _E_n_c_r_y_p_t_i_o_n _S_t_a_n_d_a_r_d (_D_E_S)," FIPS PUB 46, US National Bureau of Standards, Washington, DC, |January.| 1977. [Odl84] A. M. Odlyzko, "Discrete Logarithms in Finite Fields and their Cryptographic Significance," in _A_d_v_a_n_c_e_s _I_n _C_r_y_p_t_o_l_o_g_y: |_P_r_o_c.| _o_f _E_u_r_o_c_r_y_p_t _8_4, Lecture Notes in Computer Science, no. 209, T. Beth, N. Cot and I. Ingemarsson (editors), pp. 224-316, |Springer Verlag|, Berlin, |April.| 1984. [Oor91] P. C. Oorschot, "A Comparison of Practical Public-Key Cryptosystems based on Integer Factorization and Discrete Logarithms," _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _C_r_y_p_t_o'_9_0, vol. 537, pp. 576-581, |Springer Verlag|, Berlin, 1991. [ORS87] G. A. Orton, M. P. Roy, P. A. Scott, L. E. Peppard and S. E. Tavares, _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _C_R_Y_P_T_O'_8_6, Lecture Notes in Computer Science, no. 263, pp. 277-301, |Springer Verlag|, Berlin, 1987. [Out86] R. Outerbridge, "Some Design Criteria for Feistel-Cipher Key Schedules," _C_r_y_p_t_o_l_o_g_i_a, vol. 10, no. 3, pp. 142-156, |July| 1986. [Out89] R. Outerbridge, "_A _1_2_8-_b_i_t _K_e_y _S_c_h_e_d_u_l_e _f_o_r _t_h_e "_D_a_t_a _E_n_c_r_y_p_t_i_o_n _S_t_a_n_d_a_r_d" _A_l_g_o_r_i_t_h_m," (private communication), Toronto, Canada, |January.| 15, 1989. Bibliography 182 [PiS89] J. Pieprzyk and J. Seberry, "_R_e_m_a_r_k_s _o_n _E_x_t_e_n_s_i_o_n _o_f _D_E_S - _W_h_i_c_h _W_a_y _t_o _G_o?," Tech. Rep. CS89/4, |Dept. of Computer Science, UC UNSW, Australian Defence Force Academy|, Canberra, Australia, |February.| 1989. [PiF89] J. Pieprzyk and G. Finkelstein, "Permutations that Maximize Non-Linearity and Their Cryptographic Significance," in _C_o_m_p_u_t_e_r _S_e_c_u_r_i_t_y _i_n _t_h_e _A_g_e _o_f _I_n_f_o_r_m_a_t_i_o_n, W. J. Caelli (editor), North-Holland, Amsterdam, 1989. [Pie89] J. Pieprzyk, "Error Propagation Property and Application in Cryptography," _I_E_E _P_r_o_c_e_e_d_i_n_g_s- _E, _C_o_m_p_u_t_e_r_s _a_n_d _D_i_g_i_t_a_l _T_e_c_h_n_i_q_u_e_s, vol. 136, no. 4, pp. 262-270, |July| 1989. [Pie90] J. Pieprzyk, "Non-Linearity of Exponent Permutations," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _E_u_r_o_c_r_y_p_t'_8_9, Lecture Notes in Computer Science, no. 434, J. J. Quisquater and J. Vanderwalle (editors), pp. 80-92, |Springer Verlag|, Berlin, 1990. [Pom81] C. Pomerance, "Recent Developments in Primality Testing," _T_h_e _M_a_t_h_e_m_a_t_i_c_a_l _I_n_t_e_l_l_i_g_e_n_c_e_r, vol. 3, no. 3, pp. 97-105, 1981. [PoK79] G. J. Popek and C. S. Kline, "Encryption and Secure Computer Networks," |_C_o_m_p_u_t_i_n_g _S_u_r_v_e_y_s|, vol. 11, no. 4, pp. 331-356, |December.| 1979. [Pur83] G. B. Purdy, "A Carry-Free Algorithm for Finding the Greatest Common Divisor of Two Integers," _C_o_m_p_u_t_e_r_s _a_n_d _M_a_t_h_e_m_a_t_i_c_s _w_i_t_h _A_p_p_l_i_c_a_t_i_o_n_s, vol. 9, no. 2, pp. 311-316, 1983. [QuC82] J. J. Quisquater and C. Couvreur, "Fast Decipherment Algorithm for RSA Public-Key Cryptosystem," _E_l_e_c_t_r_o_n_i_c_s _L_e_t_t_e_r_s, vol. 18, no. 21, pp. 905-907, |October.| 1982. [QDD86] J. Quisquater, Y. Desmedt and M. Davio, "The Importance of Good Key Scheduling Schemes (How to make a Secure DES scheme with <= 48 bit keys)," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _C_r_y_p_t_o _8_5, Lecture Notes in Computer Science, no. 218, H. C. Williams (editor), pp. 537-542, |Springer Verlag|, Berlin, 1986. Bibliography 183 [QuG90] J. Quisquater and M. Girault, "2n-Bit Hash Functions Using n-Bit Symmetric Block Cipher Algorithms," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _E_u_r_o_c_r_y_p_t'_8_9, Lecture Notes in Computer Science, no. 434, J. J. Quisquater and J. Vanderwalle (editors), pp. 102-109, |Springer Verlag|, Berlin, 1990. [Rab79] M. O. Rabin, "_D_i_g_i_t_a_l_i_z_e_d _S_i_g_n_a_t_u_r_e_s _a_n_d _P_u_b_l_i_c-_K_e_y _F_u_n_c_t_i_o_n_s _a_s _I_n_t_r_a_c_t_a_b_l_e _a_s _F_a_c_t_o_r_i_z_a_t_i_o_n," MIT/LCS/Tech. Rep.-212, MIT Lab. Computer Science,, Cambridge, Mass., |January.| 1979. [RSW82] R. F. Rieden, J. B. Snyder, R. J. Widman and W. J. Barnard, "_A _T_w_o-_C_h_i_p _I_m_p_l_e_m_e_n_t_a_t_i_o_n _o_f _t_h_e _R_S_A _P_u_b_l_i_c-_K_e_y _E_n_c_r_y_p_t_i_o_n _A_l_g_o_r_i_t_h_m," SAND82- 0994, Sandia National Labs, Albuquerque, NM 87185, 1982. [RSA78] R. L. Rivest, A. Shamir and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," |_C_o_m_m. _o_f _t_h_e _A_C_M|, vol. 21, no. 2, pp. 120-126, |February.| 1978. [Riv78] R. L. Rivest, "Remarks on a Proposed Cryptanalytic Attack on the MIT Cryptosystem," _C_r_y_p_t_o_l_o_g_i_a, vol. 2, no. 1, pp. 62-65, |January.| 1978. [Riv79] R. L. Rivest, "Critical Remarks on Critical Remarks on Some Public-Key Cryptosystems," _B_i_t, vol. 19, no. 2, pp. 274-275, 1979. [Riv80] R. L. Rivest, "A Description of a Single-Chip Implementation of the RSA cipher," _L_a_m_b_d_a, vol. 1, no. 3, pp. 14-18, 1980. [Riv84] R. L. Rivest, "RSA Chips (Past/Present/Future)," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y: |_P_r_o_c.| _o_f _E_u_r_o_c_r_y_p_t _8_4, Lecture Notes In Computer Science, no. 209, T. Beth (editor), pp. 159-165, |Springer Verlag|, Berlin, |April.| 1984. [ScA83] G. C. Schaller and J. F. Arnold, "Microprocessor Based Implementation of the Public Key Encryption System," in _1_9_t_h |_I_n_t.| _E_l_e_c_t_r_o_n_i_c_s _C_o_n_v_e_n_t_i_o_n _a_n_d _E_x_h_i_b_i_t_i_o_n. _D_i_g_e_s_t _o_f _P_a_p_e_r_s., pp. 300-302, IREE, 1983. Bibliography 184 [Sch82] I. Schaumuller-Bichl, "Cryptanalysis of the Data Encryption Standard by the Method of Formal Coding," in _C_r_y_p_t_o_g_r_a_p_h_y: |_P_r_o_c.| _o_f _t_h_e _w_o_r_k_s_h_o_p _o_n _C_r_y_p_t_o_g_r_a_p_h_y (_E_u_r_o_c_r_y_p_t _8_2), Lecture Notes in Computer Science, no. 149, T. Beth (editor), pp. 235-255, |Springer Verlag|, Berlin, |March.| 29 - |April.| 2, 1982. [Sch84] M. R. Schroeder, _N_u_m_b_e_r _T_h_e_o_r_y _i_n _S_c_i_e_n_c_e _a_n_d _C_o_m_m_u_n_i_c_a_t_i_o_n, Springer-Verlag, 1984. [Sch85] M. R. Schroeder, "Number theory and the Real World," _T_h_e _M_a_t_h_e_m_a_t_i_c_a_l _I_n_t_e_l_l_i_g_e_n_c_e_r, vol. 7, no. 4, pp. 18-26, 1985. [SeP89] J. Seberry and J. Pieprzyk, _C_r_y_p_t_o_g_r_a_p_h_y: _A_n _I_n_t_r_o_d_u_c_t_i_o_n _t_o _C_o_m_p_u_t_e_r _S_e_c_u_r_i_t_y, |Prentice Hall, Englewood Cliffs, NJ|, 1989. [SBC84] S. C. Serpell, C. B. Brookson and B. L. Clark, "A Prototype Encryption System Using Public Key," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y: |_P_r_o_c.| _o_f _C_r_y_p_t_o _8_4, Lecture Notes in Computer Science, no. 196, G. R. Blakley and D. Chaum (editors), pp. 3-9, |Springer Verlag|, Berlin, |August.| 1984. [Sha86] A. Shamir, "On the Security of DES," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _C_r_y_p_t_o _8_5, Lecture Notes in Computer Science, no. 218, H. C. Williams (editor), pp. 280-281, |Springer Verlag|, Berlin, 1986. [Sha49] C. E. Shannon, "Communication Theory of Secrecy Systems," _B_e_l_l _S_y_s_t_e_m _T_e_c_h_n_i_c_a_l _J_o_u_r_n_a_l, vol. 28, no. 10, pp. 656-715, |October.| 1949. [ShM88] A. Shimizu and S. Miyaguchi, "Fast Data Encipherment Algorithm FEAL," _E_u_r_o_c_r_y_p_t _8_7 _A_b_s_t_r_a_c_t_s , pp. 11-14, 1988. [SiN77] G. J. Simmons and J. J. Norris, "Preliminary Remarks on the MIT Cryptosystem," _C_r_y_p_t_o_l_o_g_i_a, vol. 1, no. 4, pp. 406-414, 1977. [Sim79a] G. J. Simmons, "Symmetric and Asymmetric Encryption," |_C_o_m_p_u_t_i_n_g _S_u_r_v_e_y_s|, vol. 11, no. 4, pp. 305-330, |December.| 1979. [Sim79b] G. J. Simmons, "Cryptology: The Mathematics of Secure Communication," _T_h_e _M_a_t_h_e_m_a_t_i_c_a_l Bibliography 185 _I_n_t_e_l_l_i_g_e_n_c_e_r, vol. 1, no. 4, pp. 233-246, 1979. [Sim82] G. J. Simmons, ed., _S_e_c_u_r_e _C_o_m_m_u_n_i_c_a_t_i_o_n_s _a_n_d _A_s_y_m_m_e_t_r_i_c _C_r_y_p_t_o_s_y_s_t_e_m_s, AAAS Selected Symposium, no. 69, Westview Press, 1982. [SNO72] J. L. Smith, W. A. Notz and P. R. Osseck, "An Experimental Application of Cryptography to a Remotely Accessed Data System," in |_P_r_o_c.| _A_C_M |_C_o_n_f.|, p. 282 297, 1972. [SoS77] R. Solovay and V. Strassen, "A Fast Monte Carlo Test for Primality," _S_i_a_m _J_o_u_r_n_a_l _o_n _C_o_m_p_u_t_i_n_g, vol. 6, no. 1, pp. 84-85, |March.| 1977. [Sor84] A. Sorkin, "Lucifer, a Cryptographic Algorithm," _C_r_y_p_t_o_l_o_g_i_a, vol. 8, no. 1, pp. 22-41, |January.| 1984. [VCF90] J. Vandewalle, D. Chaum, W. Fumy, C. Janssen, P. Landrock and G. Roelofsen, "A European Call for Cryptographic Algorithms: RIPE RACE Integrity Primitives Evaluation," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _E_u_r_o_c_r_y_p_t'_8_9, Lecture Notes in Computer Science, no. 434, J. J. Quisquater and J. Vanderwalle (editors), pp. 267-271, |Springer Verlag|, Berlin, 1990. [WeT86] A. F. Webster and S. E. Tavares, "On the design of S-Boxes," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _C_r_y_p_t_o _8_5, Lecture Notes in Computer Science, no. 218, H. C. Williams (editor), pp. 523-534, |Springer Verlag|, Berlin, 1986. [Wei90] M. J. Weiner, "Cryptanalysis of short RSA secret exponents," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _E_u_r_o_c_r_y_p_t'_8_9, Lecture Notes in Computer Science, no. 434, J. J. Quisquater and J. Vanderwalle (editors), p. 372, |Springer Verlag|, Berlin, 1990. full paper in IEEE-IT, IT-36(3), pp 553- 558. [WiS79] H. C. Williams and B. Schmid, "Some Remarks Concerning the MIT Public Key Cryptosystem," _B_i_t, vol. 19, no. 4, pp. 525-538, 1979. [Wil80] H. C. Williams, "A Modification of the RSA Public-Key Encryption Procedure," _I_E_E_E |_T_r_a_n_s.| _o_n _I_n_f_o_r_m_a_t_i_o_n _T_h_e_o_r_y, vol. IT-26, no. 6, pp. 726-729, |November.| 1980. Bibliography 186 [Wil82] H. C. Williams, "Computationally Hard Problems as a Source for Cryptosystems," in _S_e_c_u_r_e _C_o_m_m_u_n_i_c_a_t_i_o_n_s _a_n_d _A_s_y_m_m_e_t_r_i_c _C_r_y_p_t_o_s_y_s_t_e_m_s, AAAS Selected Symposia Series, no. 69, G. J. Simmons (editor), pp. 11-39, Westview Press, 1982. [Wil84] H. C. Williams, "Some Public-Key Crypto- Functions as Intractable as Factorization," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y: |_P_r_o_c.| _o_f _C_r_y_p_t_o _8_4, Lecture Notes in Computer Science, no. 196, G. R. Blakley and D. Chaum (editors), pp. 66-70, |Springer Verlag|, Berlin, |August.| 1984. [Wil86] H. C. Williams, "An M^3 Public-Key Encryption Scheme," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _C_r_y_p_t_o _8_5, Lecture Notes in Computer Science, no. 218, H. C. Williams (editor), pp. 358-368, |Springer Verlag|, Berlin, 1986. [WiC81] R. Willoner and I. Chen, "An Algorithm for Modular Exponentiation," in |_P_r_o_c.| _5_t_h _S_y_m_p_o_s_i_u_m _o_n _C_o_m_p_u_t_e_r _A_r_i_t_h_m_e_t_i_c, _1_9_8_1., pp. 135-138, 1981. [Win83] R. S. Winternitz, "Producing a One-Way Hash Function from DES," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - |_P_r_o_c.| _o_f _C_r_y_p_t_o _8_3, D. Chaum, R. L. Rivest and A. T. Sherman (editors), pp. 203-207, Plenum Press, New York, |August.| 22-24, 1983. [Yac91] Y. Yacobi, "Exponentiating faster with addition chains," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y - _E_u_r_o_c_r_y_p_t'_9_0, Lecture Notes in Computer Science, no. 473, I. B. Damgard (editor), pp. 222-229, |Springer Verlag|, Berlin, 1991. [Yao82] A. C. Yao, "Theory and Applications of Trapdoor Functions," in |_P_r_o_c.| _A_n_n_u_a_l _S_y_m_p_o_s_i_u_m _O_n _F_o_u_n_d_a_t_i_o_n_s _o_f _C_o_m_p_u_t_e_r _S_c_i_e_n_c_e, pp. 80-91, IEEE, 1982. [YiP82] K. Yiu and K. Peterson, "A Single-Chip VLSI Implementation of the Discrete Exponential Public-Key Distribution System," in _G_l_o_b_e_c_o_m '_8_2. _I_E_E_E _G_l_o_b_a_l _T_e_l_e_c_o_m_m_u_n_i_c_a_t_i_o_n_s |_C_o_n_f.|, _V_o_l. _1, pp. 173-179, 1982. [Zim86] P. Zimmermann, "A Proposed Standard Format for RSA Cryptosystems," _C_o_m_p_u_t_e_r, vol. 19, no. 9, pp. 21-34, |September.| 1986. Bibliography 187 Bibliography