Nội dung

Kỹ thuật điều khiển & Điện tử DLP OVER POLYNOMIAL RINGS WITH TWO CYCLOTOMIC COSETS Nguyen Le Cuong1*, Le Danh Cuong2, Nguyen Binh2 Abstract: One of the classical problems in public key cryptography systems and public key exchange protocols is the Discrete Logarithm Problem (DLP) over a finite field Zp, here p is a large prime. In this paper, this DLP is studied in the case of polynomial rings with two cyclotomic cosets. By mathematical analysis and illustrations, this paper points out that decrete logarithm problem over polynomial rings with two cyclotomic cosets can be used efficiently in public-key cryptography. Key words: Discrete Logarithm Problem (DLP), Cryptography, Polynomial rings, Cyclotomic coset. 1. INTRODUCTION Nowadays, most commonly used public key cryptography systems (PKC) and public key exchange protocols are based on number theory. The theoretical strength depends on the structure of Abelian groups. Their robustness is based on the difficulty of solving certain problems over finite commutative algebraic structures. One of these problems is the Integer Factorization Problem over the ring Zn, here n is the product of two large prime numbers; for example, the well-known cryptosystem RSA [18] is based on this problem. The second classical problem is the Discrete Logarithm Problem (DLP) over a finite field Zp, here p is a large prime; the ElGamal protocol and all its variants are based on this problem [9,10]. The discrete logarithm problem (DLP) in a finite cyclic group G is an algorithmic question to find for any given pair of elements g,h  G a number n  N satisfying gn = h. This problem is extremely important due to its relation to cryptography [11]. The main idea of this work is the using of polynomial rings with two cyclomic cosets for DLP, in particular the rings of quasi-isomorphism to Zp where p is a prime number. This is what makes this ring very interesting for cryptographic applications. 2. PRELIMINARY 2.1. DLP in polynomial field (PF) Consider PF Z2 [x]/f(x), with f(x) – irreducible polynomial with degree m. In this case, all the polynomials (included zero polynomial) with degrees the smaller m are constructed as a field. Non-zero polynomials are in a cyclic multiplicative group with order 2m – 1. Example: [ ] Cyclic multiplicative group with order 15 is constructed as following: A = {1, x, x2,x3,1+x, x+x2,x2+x3,1+x+x3, 1+x2,x+x3, 1+x+x2, x+x2+x3, 1+x+x2+x3, 1+x3 } We have: log(1+x)(x+x2) = 5, log(1+x)(1+x2+x3) = 7 Number of primitive elements of this multiplicative group is: (15) = 8 They are the following polynomials {x,x2,(1+x),(1+x+x3),(1+x2),(x+x2+x3),(1+x2+x3),(1+x3)} DLP in Z2 [x]/f(x) Problem instance: 86 N. L. Cuong, L. D. Cuong, N. Binh, “DLP over polynominal rings … cyclotomic cosets.” Nghiên cứu khoa học công nghệ I = (m, (x), (x)) deg((x)), deg((x))  m – 1 (x) – primitive element of multiplicative group {Z2 [x]/f(x)}\{0} Objective: Find the unique integer a: 0  a  2m – 1, such that a(x)  (x) mod f(x) We will denote this integer a by log(x)(x) Remark: This DLP is hard if 2m – 1 is sufficient large. 2.2. Polynomial rings with two cyclotomic cosets Definition 1: PR with 2 cyclotomic cosets are PR satisfying the following condition: + 1 = ( + 1) ∑ (1) Here, (1 + ) and ∑ are irreducible polynomials. Lemma 1: PR with two cyclotomic cosets can be decomposited as following: ̅ ( ) ̅ Here: = { ( ), = 1,2,…2 }, = { ( ), = 1,2, … , 2 } ( ) = ( ) + ( ) is called symmetric polynomial of ( ). ( ) – swallowing idempotent, ( ) = ∑ A – cyclic multipicative group with maximal order. n-2 3. DLP OVER POLYNOMIAL RINGS WITH TWO CYCLOTOMIC COSETS Problem instance: I = (m, (x), (x)) deg((x)), deg((x))  m – 1 (x) – primitive element of CMG with maximal order in PR with 2 cyclotomic cosets [ ] + 1 = (1 + ) ∑ With (1+x) and ∑ are irreducible polynomials. Here, Objective: Find the unique integer a, 0  a  2n-1-1, such as a(x)  (x) mod xn + 1 We will denote this integer a by log(x), (x). Notice: If: w((x)) – odd then w((x)) – odd w((x)) – even then w((x)) – even Remark: - This DLP is hard if 2 − 1 is sufficient large. - Over these rings we can construct crypto-systems similarly as Massey or ElGamal systems Example: n = 5 In this ring, except ( ), all the non-zero polynomials belong to 2 CMG with maximal order & ̅ = {(024), (034), (1), (013), (014), (2), (124), (012), (3), (023), (123), (4), (134), (234), (0)} ̅ = {(13), (12), (0234), (24), (23), (0134), (03), (34), (0124), (14), (04), (0123), (02), (01), (1234)} We have: log(034)(012) = 4 log(12)(34) = 4 Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 87 Kỹ thuật điều khiển & Điện tử Notice: (024)  1 + x2 + x4 Generally, DLP in PR with 2 cyclotomic cosets is easier than DLP in GF(p) i = log ( ) a (x) = log ( ) a (x) K = log x ; K ∈ {1,2, … , n − 1} since n|(2 − 1) Easy problem: Z [x]/(x + 1) – PR with two cyclotomic cosets; 2n-1 – Mersenne prime; a(x) ∈ Z∗ [x]/(x + 1). Compute ai(x) (according to the repeated square and multiply algorithm for exponentiation [3]). Hard problem: Compute i = loga(x)b(x). 4. DISCUSSION AND FUTURE WORK In this paper, we have shown that polynomial rings with two cyclotomic cosets can be used in public key cryptography systems. This DLP’s hard problem is hard enough if the Mersenne prime is sufficient large. DLP in PR with 2 cyclotomic cosets is easier to solve the easy problem than DLP in GF(p). Over these rings we can construct crypto-systems similarly as Massey or ElGamal systems. REFERENCES [1]. R. L. Rivest, A. Shamir and L. Adleman. “A method for obtaining digital signatures and public-key cryptosystems”. Communications of the ACM, 21(2): 120-126 (1978). [2]. R. Alvarez, L. Tortosa, J. Vicent and A. Zamora. “A non-abelian group based on block upper triangular matrices with cryptographic applications”. In M. BrasAmoros and T. Hoholdt (editors), Applied Algebra, Algebraic Algorithms, and ErrorCorrecting Codes, volume 5527 of Lecture Notes in Computer Science, pages 117126. Springer-Verlag, Berlin, 2009. [3]. J.-J. Climent, P. R. Navarro and L. Tortosa. “Key exchange protocols over noncommutative rings”. The case End(Zp ×Zp2 ). In J. Vigo Aguiar (editor), Proceedings of the 11th International Conference on Computational and Mathematical Methods in Science and Engineering (CMMSE 2011), pages 357-364. 2011. [4]. W. D. Diffie and M. E. Hellman. “New directions in cryptography”. IEEE Transactions on Information Theory, 22(6): 644{654 (1976). [5]. A. J. Menezes, P. C. van Oorschot and S. A. Vanstone. “Handbook of Applied Cryptography”. CRC Press, Boca Raton, FL, 1996. [6]. B. Schneider. “Applied Cryptography”. John Wiley & Sons, New York, NY, second edition, 1996. [7]. D. R. Stinson. “Cryptography. Theory and Practice”. CRC Press, Boca Raton, FL, 1995. [8]. D. Boneh and R. J. Lipton, “Quantum cryptanalysis of hidden linear functions”. In D. Coppersmith (editor), Advances in Cryptology, CRYPT0 '95, volume 963 of Lecture Notes in Computer Science, pages 424-437. Springer-Verlag, Berlin, 1995. [9]. T. ElGamal. “A public key cryptosystem and a signature scheme based on discrete logarithms”. IEEE Transactions on Information Theory, 31(4), 469-472 (1985). [10]. P. W. Shor. “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”. SIAM Journal on Computing, 26(5): 1484-1509 (1997). 88 N. L. Cuong, L. D. Cuong, N. Binh, “DLP over polynominal rings … cyclotomic cosets.” Nghiên cứu khoa học công nghệ [11]. Nguyen Trung Hieu, Nguyen Van Tung, Nguyen Binh, “A classification of Linear Codes based on Algebraic Structures and LCC”, Proceeding of ATC 2014. TÓM TẮT BÀI TOÁN LOGARITHM RỜI RẠC TRÊN CÁC VÀNH ĐA THỨC CÓ HAI LỚP KỀ CYCLIC Một trong những bài toán kinh điển trong các giao thức trao đổi khóa trong hệ mật mã khóa công khai là bài toán logarithm rời rạc (DLP) trên trường hữu hạn Zp với p là số nguyên tố lớn. Trong bài báo này, bài toán DLP trên các vành đa thức có hai lớp kề cyclic sẽ được nghiên cứu. Thông qua các phân tích toán học và các ví dụ minh họa, bài báo chỉ ra rằng rằng bài toán logarithm rời rạc trên vành đa thức có hai lớp kề cyclic có thể được sử dụng hiệu quả trong hệ mật mã khóa công khai. Từ khóa: Bài toán logarithm rời rạc (DLP), Mật mã, Vành đa thức, Lớp kề cyclic. Received date, 24th May, 2017 Revised manuscript, 6th July, 2017 Published, 18th August, 2017 Author affiliations: 1 Electric Power University, 235 – Hoang Quoc Viet, Hanoi, Vietnam; 2 Posts and Telecommunications Institute of Technology, 122 –Hoang Quoc Viet, Hanoi, Vietnam. * Corresponding author: cuongnl@epu.edu.vn. Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 89