Sơ đồ chữ ký đồng thời an toàn dựa trên mã bch ghép tầng - Phạm Khắc Hoan

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 55 SƠ ĐỒ CHỮ KÝ ĐỒNG THỜI AN TOÀN DỰA TRÊN MÃ BCH GHÉP TẦNG Phạm Khắc Hoan1*, Nguyễn Văn Hải1, Vũ Sơn Hà2 Tóm tắt: Chữ ký đồng thời là sơ đồ chữ ký có tính chất đặc biệt cho phép trao đổi thông tin giữa hai thực thể một cách ngang hàng mà vẫn đảm bảo tính riêng tư của mỗi bên. Bài báo đề xuất một sơ đồ chữ ký số kháng lượng tử dựa trên mã BCH ghép tầng cho phép rút gọn kích thước khóa và đảm bảo các yêu cầu an ninh của chữ ký đồng thời. Từ khóa: Chữ ký dựa trên mã hóa; Chữ ký đồng thời; Mã BCH ghép tầng. 1. ĐẶT VẤN ĐỀ Các sơ đồ chữ ký số hiện nay chủ yếu sử dụng hệ mật khóa công khai dựa trên bài toán phân tích thừa số hay logarit rời rạc và có thể bị phá vỡ bởi máy tính lượng tử nhờ sử dụng thuật toán của Shor [1]. Trước những nguy cơ đó, cần xây dựng các hệ mật khóa công khai mới có thể chống lại các cuộc tấn công của máy tính lượng tử và máy tính cổ điển, được gọi là hệ mật kháng lượng tử (post- quantum cryptosystem). Mật mã dựa trên mã hóa (Code-based cryptography) là một trong những hướng nghiên cứu tiềm năng cho mật mã kháng lượng tử. Hệ mật này có ưu điểm cơ bản so với các hệ mật mã khóa công khai khác là quá trình thực hiện mã hóa và giải mã nhanh hơn và với việc tăng kích thước khóa giúp tăng tính bảo mật một cách nhanh chóng. Tuy nhiên điểm yếu cơ bản của hệ mật dựa trên mã hóa là kích thước ma trận khóa công khai và khóa bí mật khá lớn [2]. Trong các ứng dụng thực tế xuất hiện yêu cầu chữ ký có tính chất đặc biệt như chữ ký tập thể, chữ ký mù, chữ ký đồng thời...Trong sơ đồ chữ ký số đồng thời (concurrent signature) người ký gốc và người ký kết hợp có thể trao đổi thông tin mà không cần thực thể tin cậy thứ ba. Ví dụ khi thực hiện bỏ thầu điện tử B có hợp đồng và A, C muốn đề xuất giá bỏ thầu, khi đó A gửi giá đề xuất của mình kết hợp với một khóa chủ bí mật, B gửi một sơ đồ chữ ký đồng thời khác cho A để xác nhận rằng B chấp nhận đề xuất của A. B không thể cung cấp cho C giá bỏ thầu của A vì chữ ký của A là mờ và C không thể nhận biết được A hay B đề xuất giá thầu. Một số sơ đồ chữ ký đồng thời đã đề xuất dựa trên bài toán khó của lý thuyết số, tuy nhiên có rất ít sơ đồ chữ ký đồng thời có khả năng chống lại tấn công từ máy tính lượng tử [3, 4]. Mặt khác sơ đồ chữ ký đồng thời dựa trên mã hóa vẫn chưa đạt được thành tựu đáng kể do vẫn có nhược điểm cơ bản là thuật toán ký phải lặp lại quá trình giải mã khoảng t! lần cho đến khi giải mã thành công [5]. Bài báo đề xuất một sơ đồ chữ ký đồng thời dựa trên mã BCH ghép tầng đảm bảo an toàn với các tấn công giải mã và tấn công cấu trúc trên máy tính cổ điển và máy tính lượng tử, giảm kích thước khóa đồng thời giảm độ phức tạp của quá trình ký và xác nhận. Công nghệ thông tin P. K. Hoan, N. V. Hải, V. S. Hà, “Sơ đồ chữ ký đồng thời dựa trên mã BCH ghép tầng.” 56 Phần còn lại của bài báo được tổ chức như sau. Trong phần 2 xem xét hệ mật dựa trên mã BCH ghép tầng, phần 3 đề xuất phương pháp xây dựng sơ đồ chữ ký đồng thời dựa trên hệ mật mới, trong phần 4 tiến hành phân tích, đánh giá độ an toàn và độ phức tạp của sơ đồ chữ ký được đề xuất. 2. HỆ MẬT DỰA TRÊN MÃ BCH GHÉP TẦNG Giả sử kết hợp các mã thành phần, ma trận kiểm tra của mã được sử dụng trong hệ mật có dạng [6]: . 0 X Y H Z        (1) Trong đó: X là ma trận kiểm tra của mã BCH và các biến thể với khoảng cách mã dx (sau đây để thuận tiện ta gọi là mã X), Y là ma trận kiểm tra của một mã BCH mở rộng với khoảng cách mã dy, Z là ma trận kiểm tra của mã ghép tầng có ghép xen (interleaved concatenated code) được cấu trúc từ các mã thành phần là các mã BCH, BCH mở rộng C1, C2 với ma trận hoán vị П. Kích thước của các mã thành phần được chọn sao cho ny = nz, rx = ry (có thể sử dụng độn bit để đảm bảo điều kiện này). Ma trận kiểm tra của mã BCH ghép tầng có ghép xen có dạng: 1 2 1 2 . . . .. . . . H H Z H H                                 (2) Số lượng ma trận 2H trên đường chéo chính bằng 1n , còn số ma trận 1H trên đường chéo chính được chọn bằng 2r , các phần tử còn lại bằng 0. Vì vậy các tham số của mã Z thỏa mãn: 1 2.Zn n n , 1 2.zr r r . Mã kết hợp có chiều dài x zn n n  ; số bit kiểm tra x zr r r  . Ma trận Π kích thước  1 2 1 2n r n r . Hệ mật dựa trên mã BCH ghép tầng gồm các thủ tục sau. Tạo khóa Chọn ma trận các khả nghịch Q ((N –K) (N –K)), ma trận P(N N). Trong đó ma trận P có dạng ... , ... x z P P P        với xP , zP là các ma trận hoán vị cấp ,x zn n tương ứng. Xây dựng ma trận kiểm tra H của mã ghép tầng như mô tả trên. Tính H’ = Q.H.P. Khóa công khai là (H’, t). Khóa bí mật (Q, P, X, Y, П, H1, H2). Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 57 Mã hóa: Để mã hóa bản rõ cho trước, biểu diễn bản tin x zM M M sao cho bản tin xM có độ dài xn , trọng số không quá xt ; bản tin zM có độ dài zn , trọng số không quá zt sử dụng thuật toán bổ sung, người gửi tính: c = H’.m T. Giải mã: Để giải mã bản mã c, sử dụng thuật toán giải mã Dg dựa trên phương pháp chuẩn syndrome giải mã BCH [6, 7]. Tính 1' Tc Q c HPm  ; Tìm m’=P.mT từ c’ khi áp dụng thuật toán giải mã Dg. Tìm: 1.Tm P m  3. SƠ ĐỒ CHỮ KÝ ĐỒNG THỜI DỰA TRÊN MÃ BCH GHÉP TẦNG Trong phần tiếp theo, đề xuất phương pháp tạo chữ ký đồng thời dựa trên hệ mật sử dụng mã BCH ghép tầng. *Setup: - Chọn hai mã BCH ghép tầng có ghép xen C (N, K, t), ma trận kiểm tra của mã C xác định theo công thức (2) là ,A BH H  . - Hàm hàm băm đầu ra có N-K bit g: {0,1}*→ {0,1}N-K. - Chọn h là hàm tạo chuỗi giả ngẫu nhiên N bit từ N – K bit. - Khóa công khai Para ={N, K, ,A BH H  , t, g} * KGen: - Chọn ngẫu nhiên vector nhị phân κ độ dài N trọng số không quá t, là khóa chủ bí mật (keystone) Khóa chủ cố định (keystone fix): '( . ).TAx h H  *ASign Tạo chữ ký mờ: - Người ký A chọn số ngẫu nhiên r dài N – K bit, với bản tin cần ký M, tính ( , , , ) ;TA B Bg r M H H H x     1( ). .A Ay Dec Q P  (3) Nếu không giải mã được thì chọn r khác và lặp lại thủ tục ký. Chữ ký của M là θ = (r, x, y). *AVer Xác nhận chữ ký Cho Para, AH  , BH  chữ ký θ là hợp lệ khi và chỉ khi ' ( , , , )T TA B A BH y H x g r M H H    với trọng số của x và y không quá t. Người ký phối hợp B nhận được chữ ký θ = (r, x, y) là hợp lệ hay không nhờ thuật toán AVer. Công nghệ thông tin P. K. Hoan, N. V. Hải, V. S. Hà, “Sơ đồ chữ ký đồng thời dựa trên mã BCH ghép tầng.” 58 *Xác nhận chữ ký đồng thời Cho chữ ký θ = (r, x, y) và khóa chủ κ chữ ký đồng thời hợp lệ khi '( . ) ,TAh H x  ' ( , , , )T TA B A BH y H x g r M H H    với trọng số của x và y không quá t. 4. PHÂN TÍCH AN NINH CỦA SƠ ĐỒ CHỮ KÝ ĐỒNG THỜI ĐÃ ĐỀ XUẤT 4.1. Tính đúng đắn của sơ đồ chữ ký Tính đúng đắn của sơ đồ ký được đảm bảo vì     ' 1 ' 1 ' 1 ' ' ' . . . ( ). . . . . ( ) . ( , , , ) ( , , , ) T T T T A B A A A A A B T T T A A A A A B T A A B T T A B B B A B H y H x Q H P Dec Q P H x Q H P P Dec Q H x Q Q H x g r M H H H x H x g r M H H                     Nếu θ = (r, x, y) là chữ ký hợp lệ của thông điệp M thì quan hệ sau thỏa mãn: ' ( , , , )T TA B A BH y H x g r M H H    . Nếu chữ ký được tạo ra bởi người ký B tính đúng đắn cũng đảm bảo một cách hoàn toàn tương tự. 4.2. Phân tích các yêu cầu bảo mật của sơ đồ chữ ký đồng thời Các yêu cầu bảo mật cơ bản của chữ ký đồng thời gồm: không thể giả mạo, tính làm mờ và tính công bằng. Không thể giả mạo chữ ký: Không ai có thể tạo ra khóa chủ cố định hợp lệ trừ người ký ban đầu do không biết khóa chủ bí mật κ và khóa riêng của A là ma trận HA theo bài toán giải mã syndome. Khi chọn N-K đủ lớn không thể tạo ra chữ ký giả mạo θ’. Tính chất mờ của chữ ký: Rõ ràng với thực thể C nào đó với chữ ký θ = (r, x, y) không thể xác định được chữ ký do A hay B tạo ra. Với các tham số , , ,A Br M H H  đã cho trước, người ký i chọn ri ngẫu nhiên thuộc [1, 2 N-K] tạo ra chữ ký (ri, x, yi). Xác suất để người ký i tạo ra chữ ký mờ bằng 2 K-N, người ký j cũng có cùng xác suất như vậy. Vì vậy xác suất mà C phán đoán chữ ký được tạo ra bởi người ký i hoàn toàn giống như xác suất chữ ký tạo ra bởi người ký j, nghĩa là C phán đoán người ký thực của chữ ký mờ với xác suất bằng 1/2. Tính công bằng của chữ ký: Trước hết chỉ người có khóa chủ bí mật κ mới có thể tạo ra chữ ký. Giả sử địch thủ C tạo ra chữ ký θ* = (r*, x*, y*) của bản tin M* với khóa chủ κ*. Theo thuật toán xác nhận chữ ký Ver điều đó tương đương với '( . ).TAx h H    Xác suất địch Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 59 thủ C có thể tạo ra cặp (κ*, x*) sao cho '( . )TAh H x   không quá 2K-N là có thể bỏ qua khi N- K đủ lớn. Mặt khác mỗi chữ ký mờ được tạo ra bởi cùng khóa chủ cố định x sẽ được kết nối lại để tạo ra chỉ một chữ ký đồng thời θ = (r, x, y). Giả sử C tạo ra chữ ký θ’ = (r’, x*, y’) là một chữ ký hợp lệ khác của bản tin M’ với khóa công khai ,A BH H  . Khi đó θ’ thỏa mãn thuật toán Aver trong khi θ’ không thỏa mãn thuật toán xác nhận Ver với đầu vào (κ*, θ*). Vì θ* là chữ ký hợp lệ nên nó phải thỏa mãn thuật toán Aver, theo thuật toán này rút ra '( . ).TAx h H    Điều này mâu thuẫn với giả thiết θ’ ≠ θ*. 4.3. Đánh giá chất lượng của sơ đồ chữ ký đã đề xuất An ninh của hệ mật và sơ đồ chữ ký đã đề xuất dựa trên bài toán giải mã theo syndrome. Bài toán giải mã syndrome về bản chất là tìm vector lỗi theo syndrome khi cấu trúc của ma trận kiểm tra đã được làm ngẫu nhiên không theo cấu trúc đại số của mã. Bài toán này đã được chứng minh là NP-đầy đủ. Các tấn công phổ biến và hiệu quả nhất vào các hệ mật mã dựa trên mã hóa là tấn công giải mã ISD và tấn công cấu trúc [8]. Tấn công vét cạn không hiệu quả bởi vì từ khóa công khai là ma trận H’để tìm được khóa bí mật là ma trận H cần duyệt tất cả các ma trận hoán vị P và ma trận Q. Số lượng ma trận P có thể có là ! !x zn n , số lượng ma trận Q có thể có là 22(N-K), với xn ≥ 1000, N-K≥160, tấn công vét cạn phức tạp hơn nhiều lần so với tấn công giải mã ISD. Xét ảnh hưởng của thuật toán lượng tử đến hệ mật sử dụng mã BCH ghép tầng. Khi sử dụng giải mã ISD lượng tử với thuật toán Grover, độ phức tạp giải mã được xác định theo công thức sau [11].   0,29 K N Q decode inv itK N t C WF c c c C     (4) Trong đó : 2 2log ( )decodec N N : Chi phí giải mã các qubit đầu vào. 3 21 ( ) 2 invc K N K K   : Chi phí tính toán thực hiện việc nghịch đảo các cột của ma trận. itc K : Số lượng các phép toán bit cần thiết để thực hiện một lần lặp của thuật toán giải mã. Để minh họa các tham số của hệ mật dựa trên mã BCH ghép tầng được chọn như sau: Công nghệ thông tin P. K. Hoan, N. V. Hải, V. S. Hà, “Sơ đồ chữ ký đồng thời dựa trên mã BCH ghép tầng.” 60 Mã Z: 1(16,7,8)C , 2 (128,106,8)C , 1 2. 9.22 198zr r r   ; X mã BCH  127,85,13 , Y mã BCH mở rộng  2048,2003,10 , 42, 45x yr r  . Để phối hợp kích thước, ma trận X được bổ sung thêm ba hàng gồm toàn bit 0. Do đó tham số của mã ghép tầng 2175x yN n n   , 243y zr r r   , 1932,K  30t  độ phức tạp tấn công giải mã từ máy tính thông thường vào hệ mật 992 . Khi sử dụng thuật toán giải mã ISD kết hợp với thuật toán Grover trên máy tính lượng tử theo công thức (4) độ phức tạp tấn công ISD từ máy tính lượng tử đạt 281,6. Dưới đây đánh giá độ an toàn của sơ đồ chữ ký đồng thời đã đề xuất. Trong sơ đồ này cả 2 người ký đều chọn bộ tham số của mã ghép tầng như trên nhưng các mã thành phần có ma trận kiểm tra khác nhau (có thể đạt được bằng thay đổi đa thức sinh hoặc thay đổi trường hữu hạn). Hàm một chiều g là hàm băm, ví dụ SHA-3. ( , , , ) ( )A B A Bg r M H H g r M H H    , trong đó các ma trận ,A BH H  được biểu diễn việc ghép bởi các vector hàng của chúng. Giả sử hàm băm được dùng là SHA-3 có độ dài giá trị băm là 256 bit. Để đảm bảo tương thích với kích thước ma trận, giá trị băm được cắt bỏ đi 13 bit, tức là một cách hình thức hàm băm trong sơ đồ trên có độ dài giá trị băm 243 bit. Mặc dù chưa thể đánh giá hết ảnh hưởng của tấn công từ máy tính lượng tử đến hàm băm, có thể tìm được giới hạn của độ dài giá trị băm. Với tấn công ngày sinh nhật tổng quát trên máy tính thông thường, để tìm được một xung đột, thời gian yêu cầu xấp xỉ /22r . Với máy tính lượng tử có thể tìm được một xung đột trong thời gian /32 .r Với sơ đồ chữ ký số dựa trên mã BCH ghép tầng được đề xuất đảm bảo mức an ninh 81 bit với tấn công vào hàm băm từ máy tính lượng tử. Chú ý rằng thuật toán giải mã hai giai đoạn cho phép giải mã được mọi cấu hình lỗi trong khả năng sửa, nên ở bước tạo chữ ký chỉ ký lại khi mã X không giải mã được, tỷ lệ các vector lỗi trong khả năng sửa lỗi của mã X khoảng 1/6!. Chữ ký gồm 3 thành phần x, y và r, trong đó x, y là các vector dài N bit có trọng số không quá t nên mỗi thành phần này cần 2log t NC    223 bit, còn r có thể mã hóa bằng N – K bit Trong bảng 1 trình bày kết quả so sánh chữ ký được đề xuất với sơ đồ được đề xuất trong [10]. Trong sơ đồ chữ ký đồng thời sử dụng mã Goppa để đảm bảo an ninh của hệ mật chống tấn công ngày sinh nhật tổng quát cần chọn N = 222, t = 9 [8]. Như vậy với cùng mức an ninh số lần ký lặp lại giảm 576 lần, sơ đồ đề xuất cho phép rút gọn kích thước khóa 1470 lần. Độ dài chữ ký tăng khoảng 24% do số lỗi sửa được tăng lên, số cấu hình lỗi có thể có tăng lên. Sơ đồ đề xuất tạo ra chữ ký đồng thời an toàn với tấn công từ máy tính thông thường và máy tính lượng tử. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 61 Bảng 1. So sánh sơ đồ đề xuất với sơ đồ chữ ký đồng thời dựa trên mã Goppa. Số lần ký lặp lại Kích thước khóa (KB) Độ dài chữ ký (bit) Sơ đồ chữ ký dựa trên mã Goppa 9! 101376 557 Sơ đồ đề xuất 6! 69 689 5. KẾT LUẬN Bài báo đề xuất sơ đồ chữ ký đồng thời sử dụng cấu trúc kết hợp mã BCH mở rộng với mã BCH ghép tầng. Sơ đồ chữ ký được đề xuất đảm bảo các yêu cầu bảo mật đặc trưng của chữ ký đồng thời và an toàn với các phương pháp tấn công giải mã, tấn công cấu trúc mới được nghiên cứu gần đây. Mặt khác sơ đồ chữ ký đồng thời dựa trên mã BCH ghép tầng cho phép giảm kích thước khóa và độ phức tạp nhiều lần do chiều dài mã giảm đi khoảng 2000 lần nên thời gian ký và xác nhận đều giảm đi đáng kể và áp dụng giải mã hai giai đoạn cho mã BCH ghép tầng. TÀI LIỆU THAM KHẢO [1]. P.W.Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26:1484– 1509, 1997. [2]. McEliece, R.J. A Public-Key Cryptosystem Based on Algebraic Coding Theory, The Deep Space Network Progress Report, DSN PR 42–44, pp. 114- 116, 1978. [3]. D. J. Bernstein, J. Buchmann, E. Dahmen. Post-quantum cryptography, Springer-Verlag Berlin Heidelberg, 2009. [4]. Z. Huang, K. Chen, X. Len, R. Huang. Analysis and improvements of two identity based perfect concurrent signature schemes. Informatica, Vol. 18, No. 3, pp 375-394, 2007. [5]. K. Morozov, P. Roy, R. Steinwandt, R. Xu. On the sceurity of Courtois- Finiasz-Senderier signature. Open math , pp 161-167, 2018. [6]. Pham Khac Hoan, Le Van Thai, Pham Duy Trung: A secure McEliece cryptosystem’s variant based on interleaved concatenated BCH codes, 2016 International Conference on Advanced Technologies for Communications (ATC 2016), pp 513-518. [7]. Phạm Khắc Hoan, Lê Văn Thái, Nguyễn Anh Tuấn. Xây dựng sơ đồ chữ ký số dựa trên hệ mật sử dụng mã BCH ghép tầng. Hội thảo quốc gia REV-EICT, 2016. Công nghệ thông tin P. K. Hoan, N. V. Hải, V. S. Hà, “Sơ đồ chữ ký đồng thời dựa trên mã BCH ghép tầng.” 62 [8]. M. Finiasz, N. Sendrier. Security Bounds for the Design of Code-Based Cryptosystems, Advances in Cryptology ASIACRYPT 2009, Volume 5912 of the series Lecture Notes in Computer Science pp 88-105. [9]. Becker, A., Joux, A., May, A., and Meurer, A. Decoding random binary linear codes in 2n/20: How 1 + 1 = 0 improves information set decoding. In Advances in Cryptology - EUROCRYPT 2012, Lecture Notes in Comput. Sci., Springer, 2012. [10]. M. R. Asaar, M. Salmasizadeh, M. A. Aref. A Provably secure code-based concurrent signature scheme. [11]. Vries S. D. Achieving 128-bit security against quantum attacks in OpenVPN, Master’s thesis, August 2016. ABSTRACT A SECURE CONCURRENT SIGNATURE BASED ON CONCATENATED BCH CODES A concurrent signature scheme allows the exchange of information between two entities fairly while ensuring the privacy. In this paper, a post- quantum signature scheme based on concatenated BCH codes is proposed. For the proposed scheme, the key size is reduced dramatically while the security requirements of the concurrent signature are complied with. Keywords: Code-based signature; Concurrent signature; Concatenated BCH codes. Nhận bài ngày 29 tháng 06 năm 2018 Hoàn thiện ngày 09 tháng 10 năm 2018 Chấp nhận đăng ngày 05 tháng 11 năm 2018 Địa chỉ: 1Khoa VTĐT - Học viện KTQS; 2Viện CNTT - Viện KHCN quân sự. *Email: hoanpk2012@gmail.com.