A method of buiding a crypto system based on unbalanced feistel network and its application in hash functions - Ngo Duc Thien

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 34, 12 - 2014 41 A METHOD OF BUIDING A CRYPTO SYSTEM BASED ON UNBALANCED FEISTEL NETWORK AND ITS APPLICATION IN HASH FUNCTIONS NGO DUC THIEN, DANG HOAI BAC Abstract: This paper proposes a block crypto system that uses cyclic geometric progressions over polynomial rings as encryption function, and its encryption diagram is based on unbalanced Feistel network with four branches. All the sub keys in encryption steps are also elements in cyclic geometric progressions over polynomial ring with two cyclotomic cosets. By using this crypto system, we apply to a hash function with 512 bits output length. Some diffusion simulations of the proposed crypto system and hash function are also presented. Keywords: Block crypto system; Feistel network; Hash function; Polynomial ring; Cyclic geometric progression. 1. INTRODUCTION In recent years, there are noticeable researches of cyclic geometric progressions (CGP) over polynomial rings (PR) applied in error control codes [2] with some advantages such as: easy to set up encoders and decoders; a lot of optimum codes found... Following these researches, only polynomial rings Z2[] + 1⁄ with is odd or = 2 ( is odd) can be used to construct error correcting codes. On the other hands, = 2 are special cases and is not considered. However, when using the CGPs over these PRs Z2[]/ 2 + 1, we have interesting applications in cryptography. This paper proposes a block crypto system with 128 bits output. It uses CGPs as encryption function, and the encryption diagram is built according to unbalance Feistel network with four branches. The secret keys for this crypto system are also the elements of the CGPs on PRs with two cyclotomic cosets. With this crypto system, we applied to a specific modification detection code (MDC) hash function with 512 bits output length. Some diffusion simulations of the proposed crypto system and hash function are also presented. 2. BLOCK CRYPTO SYSTEM BASED ON UNBALANCE FEISTEL NETWORK WITH FOUR BRANCHES 2.1. Cyclic multiplicative group over polynomial ring Definition 1: Set of polynomials () in a polynomial ring Z2[] + 1⁄ with multiplicative operation creates a multiplicative group G [3]. 〈();∗〉 = (1) If (), () ∈ then () ∗ () = () ∈ . Existing unit element () ∈ with () ∗ () = (). Lemma 1: Consider PR Z2[] + 1⁄ with = 2, set of polynomials that its weight is odd creates a multiplicative group modulo with + 1 [3]. Kỹ thuật điện tử & Khoa học máy tính N. D. Thien, D. H. Bac, “A method of building a crypto system hash functions” 42 Definition 2: Let PR Z2[] + 1⁄ , a cyclic multiplicative group (CMG) A in this PR is defined as follow [2]. = {(), = 1,2, } (2) where, () ∈ Z[] + 1\⁄ {0} is called generator element (or generator polynomial). The number of elements in is order of (), ( () = ||), and also is order of . The number of polynomials with order equal to is 2−2 [3]. Therefore, we also have 2−2 CMGs with order is (include identity multiplicative group ). Example 1: With = 8, we have 26 = 64 CMGs with order is 8 and the form of these CMGs as follow: = {(), (), , (), () = 1} (3) 2.2. Cyclic Geometric Progressions If we multiply all the elements in a CMG with an element () ∈ of PR we will have a CGP as following form: = ()(), = 1,2,3, (4) Where, () - initial element; () - generator element. Lemma 2: Let PR ℤ2[]/ + 1 with = 2, the number of CGPs with order equal to in group is calculated as follow [3]. = 2.2 (5) The example can be seen in Table 1. Table 1. Number of CGPs with some values Number of CGPs Number of CGPs = 8 = 2 = 8192 = 32 = 2 = 16 = 2 = 64 = 2 2.3. Descriptions of crypto system The proposed crypto system is describes in Fig. 1. It is based on unbalanced Feistel network with four branches, and on each encryption loop it performs the following algorithm: ⎩ ⎪ ⎨ ⎪ ⎧ = − 1 = − 1 = − 1 = − 1 = ⊕ ⊕ (, , , ) (6) In Fig. 1, the encryption function block has four inputs; three of them are data inputs (b, c and d) and one key input. The length of all inputs and outputs is 32 bits. The encryption is performed by CGPs in PR ℤ2[] + 1⁄ with = 2 = 32. The structure of CGP that is used in encoder as follow: = (); = 0,1,2, ,31 (7) where, () = is initial polynomial and also is sub key in the step encryption. Essentially this is a special converter which is specifically by a matrix as follows [3]: Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 34, 12 - 2014 43 = () () () = ⋮ ⋮ ⋮ (8) where, ∈ {0,1}. Remark: The rows of matrix correlate with polynomials. The elements in a row of are the factors of monomials in corresponding polynomial. For example, if the row 1 of A is polynomial () = 1 + + then the factors of this row are = 1 with = 0,3,4 and = 0 with all others . And similar with all rows of . If we chose () ∈ , then exist inverse matrix −1. When using matrix to encryption, we can decrypt by using matrix −1 [3]. The inverse matrix −1can be calculated as follow: −1 = −1 (9) Because the order of CGP is so = or = , where I is identity matrix [3]. According to lemma 1, we just select a polynomial () with odd weight, then it will belong to and we will have inverse polynomial () = () and also inverse matrix −1. Example 2:Consider PR ℤ2[]/ 32 + 1, select () = 1 + + ↔ (0.3.4) as initial element of encryption matrix (remark: (0.3.4) is the power form of ()), then inverse matrix −1 = 31 can be performed from inverse polynomial () as follow: () = (1.2.3.4.8.11.12.14.16.17.18.19.23.26.27.29.31) And −1 = {(), = 0,1,2, ,31}. In step of encryption scheme, function performs the following equations: = ⊕ ⊕ _ = (10) where, is transposed matrix of , and is calculated as (8) but substitutes () = . Fig. 2 is an example of encryption circuit with key polynomial = 1 + 3 + 4. The inputs , , are fed to an OR gate and then 32 bits output from this OR gate are loaded to a shift register. After that, it performs modulo 2 addition bits in shift register corresponding to the factors of key polynomial , and after 32 shift steps we have output value. Fig. 1. Encryption scheme a (32 bits) f b (32 bits) c (32 bits) d (32 bits) f f f a’ (32bits) b’ (32bits) c’ (32bits) d’ (32bits) k1 k2 k15 k16 Plaintext (128 bits) Cipher text (128 bits) Kỹ thuật điện tử & Khoa học máy tính N. D. Thien, D. H. Bac, “A method of building a crypto system hash functions” 44 Fig.2. Encryption circuit with key ki = 1 + x + x 4(0.3.4). All sub keys in Fig.1 are also created from CGPs over PRs with two cyclotomic cosets [4]. Because the sub keys are the initial polynomials () of , therefore all are odd weight. Definition 3: PR ℤ[] + 1⁄ is called PR with two cyclotomic cosets if: + 1 = (1 + )∑ (11) where, 1 + and ∑ are irreducible polynomials [4]. If we select sub keys in PRs with two cyclotomic cosets, it is because the polynomials in these PRs have maximum order: max () = 2 − 1 [4], therefore, we can create CGPs with a large number of elements (or number of sub keys). If the PR with two cyclotomic cosets ℤ[]/ + 1 is selected, then 16 keys for encryption loops are the first 16 elements of a CGP as following description: ≡ + 1; ( = 1,2, ,16) (12) where, ∈ + 1 is initial polynomial; (generator element) is a primitive element of multiplicative group with = 2 − 1. All and must be odd weight to ensure is odd weight. Since PR + 1 with two cyclotomic cosets having smaller and approximate to 32, so PR + 1 should be selected to generate keys. In the encryption scheme as shown in Fig. 1, there is a difference to the original unbalanced four branches of Feistel network, that means in step the data in block is added to key (only adding first 29 bits of to ). This avoids the case, that if plaintext input data includes all bit "0" or "1" then the cipher text data will be all bits "0" or "1", respectively, since that the encryption function has not any substitute operations. To calculate the diffusion property of crypto system with changed plaintext data, the keys must be fixed and selected as follows: Generator element: = 1 + + ; Initial element: = 1 + + . The plaintext includes 128 bits and described in hexa form as follows: = (13) Some calculating results of Hamming distance (or diffusion property) of crypto system are described in Table 2 [1]. Remark: in Table 2, 3 and 5 the hexa characters in bold contain changed bit. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 34, 12 - 2014 45 Table 2. Some Hamming distances . Plaintext Cipher text (,) 0 0123456789ABCDEF0123456789ABCDEF D3D720E98643F04FE175EE121F5103FA 0 1 1123456789ABCDEF0123456789ABCDEF DE0D0F18E351B9399697DCC148AE8774 69 2 2123456789ABCDEF0123456789ABCDEF 7A073EF374EE9F5C94FB4A8C5AD22E93 64 64 0123456789ABCDE70123456789ABCDEF 0C0C0702BCD5C0D735CCA2FDD6997536 71 65 0123456789ABCDEF1123456789ABCDEF AEFA8E9A547F3C467EC2A0EA2B7FCC96 72 127 0123456789ABCDEF0123456789ABCDEB 3348DDF7729EF847F7B90454CE93EBEE 61 128 0123456789ABCDEF0123456789ABCDE7 1BE86A980A1DE01428DBA8418F8A4366 59 Change each single bit from 1st to 128th of plaintext we have the average Hamming distance of 128 calculating steps as follow: () = 1 128 (, ) = 64.14 (14) To calculate the diffusion property of crypto system with changed keys. The plaintext must be fixed and selected as (13). The key generator element is still = 1 + + , the first initial polynomial is selected as (15). We use 8 characters to describe 29 bits of . The first 7 characters are hexa number and the last character is binary. This last bit ensures the weight of is odd, that means if the sum of 28 bits beginning of is even then 29 th bit of is "1" and vice versa. ka(Bin) = 1000.0100.1100.0010.1010.0110.1110. 1 ka(Hex) = 1 . 2 . 3 . 4 . 5 . 6 . 7 . 1 29th bit (check bit) Remark: the position of bit "1" in corresponds to the power of in polynomial . = 127.1 ↔ 1000.01001110.1 ↔ 1 + +⋯+ + + (15) All bits from 1st to 28th in are replaced each to next one, therefore 29 th bit always is "0", so the Hamming distance of couples of cipher text will be discribed as d(C, C) after replacing step. Some calculated Hamming distance of crypto system with key’s changing are described in Table 3 [1]. Table 3. Some Hamming distance between couples of cipher text when change key () Cipher text (, ) 0 12345671 7E4E4B27958D0AFC11831E81F4B3F44E 0 1 02345670 E5DC803F2AB48FD256993E4ADF55B8BA 63 2 32345670 111A88DD76E1B7EDCC4C1A268DD78B8D 73 14 12365670 64E030BF3EA25E4282A3304B0694B670 65 27 12345630 362C4BE56959804C4EDFFF25620D8C5D 58 28 123456F0 3C0A9C422692514581AFFA6AF0002C7F 62 The average Hamming distance is calculated as follows: () = ∑ (, ) = 63.68 bits (16) Kỹ thuật điện tử & Khoa học máy tính N. D. Thien, D. H. Bac, “A method of building a crypto system hash functions” 46 From (14) and (16) we can see that the average Hamming distance approximates the half of cipher text length, that means the crypto system has good diffusion property. 3. THE APPLICATION OF PROPOSED CRYPTO SYSTEM IN A HASH FUNCTION In this section, we apply proposed crypto system to introduce a MDC hash function. The hash scheme including of four branches, which is based on Matyas - Meyer - Oseas scheme, is described in Fig. 3. (1) i x (2) i x (3)ix (4) i x (1) 1i H  (2) 1i H  (3) 1i H  (4) 1i H  Fig.3. Hash function scheme. In Fig. 3, the encryption block E is proposed crypto system with 128 bits output. Block g in each branch will create key with 29 bits for the current hash step . It selects 28 bits from corresponding hash value in step − 1, starting from 1st bit of and continue with four bits distance (bits 1 st ,5th ,9th ,...); and the last 29th bit is check bit. Carry out the diffusion simulation of hash function with input changed hash data. The key generator element is still = 1 + + . The keys and must be fixed on all simulation steps. All four branches in Fig. 3 use the same initial polynomial () = = 1234567.1 and it is fed directly to block E. The first plaintext data () or the hash data input contains 5120 bits (10 blocks x 512 bits /1 block) and it is random generated. On each simulation steps we only change randomly one bit of plaintext. Table 4 are diffusion property simulation results of some hash values when plaintext difference from the first plaintext is one bit [1], where, () = () = 1234567.1, and the key generator is still = 1 + + . Carrying out random change plaintext a hundred times, we have the average Hamming distance of hash values as follows: () = ∑ , = 257.36 (17) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 34, 12 - 2014 47 Table 4. Some Hamming distance (,) when change one bit of plaintext input Position of changed bit Hash value (,) 0 Not changed F6A3FB5D6CC40BD9A7078EDA0773FFAA5043DB834A3174171ACDB614F27BF70B BF1CFE764A57727701BB029D0B2F1C00D0E68EE56B6445A24A13924DCB298B31 0 1 2779 1F8F391D7D7B0694ED057F2E1218D6D3916A29275D5357B8C63EA1BA6BB08974 862FE65D881DB269ECB659F1B94804C8D66C120FF69BD9BBB0C1CDA6CA19007B 254 2 616 29DA6B85607B360DFC8ABE725891A1155F4E476A43BD175E9E0773FA0C89B772 6E9D88C94D3BDC17C94443A931E541D3269F2B96135AE922A23218FDE0D3FD2E 266 50 945 D01C97F23CDB2CAAF24495225A847394BCBAA30A533063303EF0DA2561D22290 A752032DE24493D1332251CA365A6E8401DAFBB1C59AA2E9CFFDBFE661BDB4D1 270 51 2518 D188D7BD2AB4C4F433F1040B9915A7C91C38B36D5652FE59B30FEC622CB88A9B A30CD51AFCF8BB689353EFC36828F4010CBAC6D7F4BA5773AE4EC636BDCF8A05 254 99 3198 5ED2A7B21112595E3E7845E5EA19A3A90C00CAE1B5F27F89D3488B27DF453F6E CDCF30571607B06800C575558F4A9BC0C1DD9DAE401B5EAF5C115DBDB984F837 258 100 157 CB45347A184000EBA2BE4EFA17C6F61DDBD3A32C63D5C20976A1BC6CA24756F5 C0F4117C1FB76A4C0655787AD38A82D9FA85F12A9B90294218513129B9D2C464 258 Table 5 presents Hamming distance of some hash values with changing of the initial polynomial . On each simulation steps, the initial polynomial () and first initial key () difference is one bit (in range 1 st to 28th bits). The 29th bit will be "0" that ensure the weight of is odd. The plaintext input includes 10 blocks, which contains 512 bits and randomly generated. On all simulation steps the plaintext is fixed. The average Hamming distance of hash codes of 28 times with changing of the key is calculated as follows: () = ∑ , = 260.43 (18) According to (17) and (18) we can see that the diffusion property of hash function is 257.36 bits, and 260.43 bits. These two values are approximately half of the hash value length (256 bits). Table 5.Some Hamming distance (, ) with changing of key () Hash value (,) 0 12345671 606FFF021720878021E32ABD3310B0625000AFEC6577EFE760C1DEF44BAFB3CE EF760038FC0021DB9689FC2BD45CA72DABA758EDCF81B8A13AB5E65BEC7F7B4A 0 1 02345670 864CF8486A0EFD35EF6C0F739ED8C8ABE96298361F377B4FC3A6AFFA9DFB92B3 DF6E45C0F4B36CD8652A1C67E06BE38D58B778663118A1DCC626E97970733FA8 242 2 32345670 27E0D91CB664150E09CBD8D0087C8DC120A9BE96B3E2AB0B763E3CBE3C909FEB 141C63DE11C86302E3B9F3DA5D04F44ECDD1C1D5878FA90F6858977DDE48BAAF 252 14 12365670 BB30EECBD594B48DFF728D008202688A7EE5048536875952B2F1E093EF3A5C1C AD3FEC67DE2C5EA0C7952302D5679F62975ABB12A3A06FB3FB414E11992F4DA5 270 27 12345630 723E753B5656859E2F3129C24D33299A9C4832A342F1F4FDB86B3274D5F89283 2EC71B6FED5D15CFA5A145D9A9093CB0DE7873903B6DE1E502B0165A1182E232 252 28 123456F0 C9CC96EF585CBCB153BD3CE860FBB2F9321540A6C7A0ECD0C0D8B1F0C2AC6970 336E9E6DF3D95CE94B4605DDECE16A7D3A2DDB0D190163E006D3A86E0288547F 266 4. CONCLUSION In this paper, a ideal to build the block crypto system is presented. There are advantages of this crypto system as: i) Easy to set up encryption circuit, which is suitable for hash function; ii) A large number of keys can be created from CGPs of PR, which is convenient to generate sub keys in encryption schemes; iii) The crypto system and the hash function have good diffusion property with changing of Kỹ thuật điện tử & Khoa học máy tính N. D. Thien, D. H. Bac, “A method of building a crypto system hash functions” 48 the plaintext or key. To get more estimations, it is necessary to more calculate properties of this hash function, such as the pre-image resistant, second pre-image resistant, and collision resistant... REFERENCES [1]. Jean-Yves Chouinard, "Secure Communications and Data Encryption, School of Information Technology and Engineering", University of Ottawa, April 2002. [2]. Nguyen Binh, “Cyclic and Local Cyclic Codes over Polynomial Ring”, Journal of Science and Technology, Vietnam, Vol. 50(2012), pp. 735-749, ISSN 0866 708X. [3]. Ho Quang Buu, Ngo Duc Thien, Tran Duc Su, "Constructing a Crypto system based on Cyclic Geometric Progressions in Polynomial Rings", Jounal of Science and Technology, Vietnam Academy of Science and Technology, Vol. 50 - 2A, (2012) pp. 109-119, ISSN 0866 708X. [4]. Nguyen Trung Hieu, Ngo Duc Thien, Tran Duc Su, "On Constructing Cyclic Multiplicative Groups with Maximum Order over Polynomial Rings with Two Cyclotomic Cosets", Jounal of Scientific research and Military technology, Vol. 17, (2012) pp. 133-140, ISSN 1859-1043. TÓM TẮT MỘT PHƯƠNG PHÁP XÂY DỰNG HỆ MẬT DỰA TRÊN SƠ ĐỒ FEISTEL KHÔNG CÂN BẰNG VÀ ỨNG DỤNG TRONG HÀM BĂM Bài báo này đề xuất một hệ mật mã khối sử dụng các cấp số nhân cyclic trên vành đa thức làm hàm mã hóa, sơ đồ mã hóa của hệ mật dựa theo sơ đồ Feistel bốn nhánh không cân bằng. Các khóa con trong các bước mã hóa cũng được xây dựng trên các cấp số nhân của vành đa thức có hai lớp kề cyclic. Sau đó, hệ mật đề xuất này được ứng dụng vào một hàm băm mật mã với độ dài mã băm 512 bit. Một số mô phỏng đánh giá tính khuếch tán của hệ mật và hàm băm đề xuất cũng đã thực hiện và bình luận. Từ khóa: Mật mã khối, sơ đồ Feistel; Hàm băm; Cấp số nhân cyclic; Vành đa thức. Nhận bài ngày 19 tháng 08 năm 2014 Hoàn thiện ngày 10 tháng 10 năm 2014 Chấp nhận đăng ngày 04 tháng 12 năm 2014 Địa chỉ: Học viện Công nghệ Bưu chính Viễn thông. Email:thienptit@gmail.com; bacdanghoai@gmail.com Di động: 0912.928.928