Xây dựng sơ đồ chữ ký số trên hệ mật mã dựa trên mã sử dụng phương pháp giải mã theo chuẩn Syndrome

Kỹ thuật điều khiển & Điện tử Lê Văn Thái, “Xây dựng sơ đồ chữ ký số phương pháp giải mã theo chuẩn syndrome.” 88 XÂY DỰNG SƠ ĐỒ CHỮ KÝ SỐ TRÊN HỆ MẬT MÃ DỰA TRÊN MÃ SỬ DỤNG PHƯƠNG PHÁP GIẢI MÃ THEO CHUẨN SYNDROME Lê Văn Thái* Tóm tắt: Nội dung bài báo đề xuất sơ đồ chữ ký số dựa trên hệ mật Niederreiter, biến thể của hệ mật McEliece. Để khắc phục nhược điểm kích thước khóa lớn của đề xuất gốc và hạn chế về khả năng ký một văn bản bất kỳ, tác giả đã sử dụng giải pháp ghép các mã BCH thành phần và sử dụng phương pháp giải mã theo chuẩn syndrome. Kết quả thử nghiệm sơ đồ đề xuất trên máy tính Corei5-2.3GHz, 8Gb Ram: thời gian ký nhỏ hơn 20ms, thời gian xác nhận chữ ký nhỏ hơn 1ms đồng thời cho phép giảm kích thước khóa 65 lần so với chữ ký CFS (m=15, t=12) trong cùng mức bảo mật. Từ khóa: Hệ mật Niederreiter; Hệ mật McEliece; Sơ đồ chữ ký số; Hệ mật dựa trên mã, Chuẩn syndrome. 1. ĐẶT VẤN ĐỀ Hiện nay, vấn đề đảm bảo an toàn, bảo mật thông tin trên hạ tầng mạng là nhiệm vụ quan trọng, cấp thiết, đặc biệt là trong xu hướng hội nhập, toàn cầu hóa cùng với sự tiến bộ của khoa học công nghệ trong lĩnh vực mật mã, xử lý thông tin và truyền thông. Chữ ký số dựa trên nền tảng hệ mật khóa công khai là công nghệ cho phép nâng cao tính bảo mật, đảm bảo toàn vẹn dữ liệu, đảm bảo tính xác thực, chống chối bỏ trách nhiệm. Thuật toán lượng tử trong thời gian đa thức của Shor công bố năm 1994 và thuật toán tìm kiếm trên dữ liệu không có cấu trúc của Grover năm 1996 đã cảnh báo các sơ đồ chữ ký số RSA, DSA, ECDSA đang được sử dụng trong thực tế hiện nay sẽ không an toàn khi chế tạo thành công máy tính lượng tử đủ lớn [1, 2]. Do đó, việc xây dựng sơ đồ chữ ký mới trên cơ sở các hệ mật có khả năng chống lại tấn công từ máy tính hiện đại và máy tính lượng tử là nội dung đang được nhiều nhà khoa học nghiên cứu. Mật mã dựa trên mã là một trong những hệ thống mật mã kháng lượng tử và được coi là ứng cử tiềm năng trong thế giới lượng tử thay thế các hệ mật đang được sử dụng hiện nay [3]. An ninh của hệ mật dựa trên độ khó của bài toán giải mã syndrome đã được chứng minh là NP-đầy đủ [4]. Hệ mật McEliece khi mới đề xuất không thể trực tiếp áp dụng để xây dựng chữ ký số do ràng buộc về khả năng sửa lỗi của mã nên không thể ký được một văn bản tùy ý và kích thước khóa còn lớn. Những năm gần đây đã có nhiều công bố là biến thể mới của hệ mật McEliece, có nhiều đề xuất xây dựng sơ đồ chữ ký số trên hệ mật này thông qua việc nghiên cứu, cải tiến và sử dụng các họ mã khác nhau thay thế cho mã Goppa trong hệ mật gốc [5], [6]. Trong đó, hai đề xuất chính của sơ đồ chữ ký số dựa trên mã là sơ đồ chữ ký Kabatianskii-Krouk-Smeets (KKS) [7] và sơ đồ chữ ký Courtois- Finiasz-Sendrier (CFS) [8]. Sơ đồ chữ ký số KKS được đề xuất năm 1997, sử dụng hai mã với chiều dài khác nhau, một mã được lựa chọn là mã con của mã kia và sử dụng phương pháp giải mã đầy đủ. Tuy nhiên, sơ đồ KKS có thể bị tấn công khôi phục khóa trong 277 phép tính nhị phân với khoảng tối đa 20 chữ ký [9]. Năm 2001, sơ đồ chữ ký số dựa trên mã được Courtois, Finiasz, và Sendrier xây dựng trên hệ mật Niederreiter và được gọi là sơ đồ CFS. Giải pháp của sơ đồ chữ ký số CFS để đảm bảo ký được mọi văn bản là sử dụng phương pháp giải mã đầy đủ (sơ đồ CFS được trình bày chi tiết trong mục 2.2). Hạn chế của phương pháp này là số lần lặp thực hiện lớn, trung bình khoảng t! lần [8]. Mặt khác, cuộc tấn công của D.Bleichenbacher đưa ra được Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 61, 6 - 2019 89 mô tả bởi Finiasz trong [10] đã chỉ ra điểm yếu để giả mạo thành công chữ ký CFS hợp lệ đối với các tham số trong đề xuất gốc dựa trên thuật toán ngày sinh nhật tổng quát [11]. Giải pháp khác để khắc phục điểm hạn chế trên của hệ mật là nghiên cứu xây dựng một cấu trúc mã và thuật toán giải mã hiệu quả để đạt được một tỷ lệ tối ưu giữa số syndrome giải mã được và tổng số syndrome có thể có. Để hiện thực hóa giải pháp trên, tác giả đề xuất lựa chọn giải pháp ghép các mã BCH thành phần, đảm bảo tính bảo mật với các tấn công giải mã và tấn công cấu trúc, giảm được kích thước khóa, đồng thời cho phép tăng số syndrome có thể giải mã được. Phần còn lại của bài báo được tổ chức như sau: Trong phần 2 nghiên cứu về hệ mật mã dựa trên mã và sơ đồ chữ ký số CFS, phần 3 đề xuất xây dựng sơ đồ chữ ký số mới trên hệ mật Niederreiter sử dụng phương pháp ghép mã BCH thành phần, phần 4 đánh giá độ phức tạp và độ bảo mật của sơ đồ đề xuất. 2. HỆ MẬT MÃ DỰA TRÊN MÃ VÀ SƠ ĐỒ CHỮ KÝ SỐ CFS 2.1. Hệ mật Niederreiter Hệ mật mã dựa trên mã McEliece là một trong những hệ mật mã đầu tiên sử dụng tính ngẫu nhiên trong mã hóa. Để mô tả khóa bí mật, một mã sửa lỗi được lựa chọn với thuật toán giải mã hiệu quả lựa chọn trước. Hệ mật gốc sử dụng mã nhị phân Goppa và thuật toán giải mã Petterson. Khóa công khai thu được từ khóa bí mật bằng cách xáo trộn ma trận sinh G của mã nhị phân thông qua hai ma trận khả nghịch ngẫu nhiên. Hệ mật Niederreiter là một biến thể của hệ mật McEliece. Hệ mật Niederreiter sử dụng ma trận kiểm tra H để làm khóa và sử dụng vector lỗi để giải mã. Sơ đồ hệ mật mã khóa công khai Niederreiter được thể hiện trong hình 1. Hình 1. Sơ đồ hệ mật mã khóa công khai Niederreiter. Các thuật toán của hệ mật Niederreiter được thực hiện như sau [12]: a) Tạo khóa • Chọn mã Goppa (n,k) có khả năng sửa t lỗi, có ma trận kiểm tra H[n-k,n] • Chọn ma trận khả nghịch Q[(n-k, n-k)]. • Chọn ma trận chuyển vị P[n, n]. • Tính H’ = Q.H.P. • Khóa công khai là (H’, t). • Khóa mật là (Q, H, P). b) Mã hóa Sử dụng khóa công khai (H’, t), bản tin M cho dưới dạng chuỗi nhị phân dài n bit có trọng số nhỏ hơn hoặc bằng t, bên gửi sẽ thực hiện tính bản mã: c = H’.MT. c) Giải mã Bên nhận sở hữu khóa mật tiến hành thực hiện giải mã: Alice Bob H H’ Q -1 P -1 H’ = QHP Kênh truyền c = H’. MT Giải mã goppa Khóa công khai: H’, t MT M c c Khóa bí mật: Q,H,P Kỹ thuật điều khiển & Điện tử Lê Văn Thái, “Xây dựng sơ đồ chữ ký số phương pháp giải mã theo chuẩn syndrome.” 90 • Tính c’ = Q-1c = Q-1H’.MT = Q-1.Q.H.P.MT = H.P.MT; c’ là một trong các syndrome của mã Goppa được sử dụng. • Sử dụng thuật toán giải mã theo chuẩn syndrome cho mã (n,k) ta tìm được M’ = P.MT. Tính : MT = M’.P-1 và thực hiện khôi phục bản tin gốc M. Hạn chế của hệ mật này trong việc sử dụng để mã hóa là yêu cầu bản tin phải có trọng số nhỏ hơn hoặc bằng t. Trong thực tế, các bản tin có chiều dài ngẫu nhiên, số syndrome thỏa mãn được điều kiện này là nhỏ. Do đó, để sử dụng được hệ mật này thì đòi hỏi phải có thuật toán để chuyển đổi bản tin về dạng có trọng số nhỏ hơn hoặc bằng t. Niederreiter đề xuất thực hiện chuyển đổi bản tin thành vector lỗi có trọng số nhỏ hơn hoặc bằng t sử dụng hàm n,t : {0,1} wn,t , trong đó  = log2|wn,t| và wn,t = {e 2 nF |wt(e)=t}. Thuật toán được trình bày trong hình 2 [13]: Thuật toán chuyển đổi một số [0, ]tnC thành vector có trọng số  t Input: [0, ]ty nI C Output: vector trọng số t với 1 20 ..... ti i i n     . j t While 0j  do _ ( , )j yi invert binomial I j j j y y iI I C  ; 1j j  Trong đó _ ( , )yinvert binomial I j trả về số nguyên i thỏa mãn 1 t t i y iC I C   Hình 2. Thuật toán chuyển đổi bản tin thành vector có trọng số t, chiều dài n. 2.2. Sơ đồ chữ ký số CFS Hệ mật Niederreiter và các hệ mật mã dựa trên các mã sửa lỗi không có khả năng ký một bản tin bất kỳ. Bởi vì chỉ có một số vector nhị phân có chiều dài n có trọng số w≤ t (t là khả năng sửa lỗi của mã). Xét một mã C(n,k), với n = 2m, tổng số vector lỗi có thể sửa, được xác định theo công thức: 1 ! t t t giaima ni n T C t   khi n đủ lớn (1) và tổng số syndrome có thể có là: 2 2n k mt ttongT n    (2) Trong đó, Tgiaima là số syndrome có khả năng giải mã được, Ttong là số syndrome có thể có. Về lý thuyết Tgiaima ≤ Ttong, dấu bằng chỉ xẩy ra khi C(n,k) là một mã hoàn thiện. Xác suất giải mã thành công (Pgiaima) được xác định theo công thức: 1 ! giaima giaima tong T P T t   (3) Từ công thức (3) ta nhận thấy xác suất này không phụ thuộc vào n mà chỉ phụ thuộc vào t. Mặt khác, thời gian ký sẽ không thay đổi nhiều khi n thay đổi, trong khi đó độ an toàn của hệ mật tăng nhanh khi n tăng. Xác suất giải mã (Pgiaima) giảm nhanh khi tăng t, qua khảo sát, xác suất giải mã thành công chỉ có thể chấp nhận được khi t ≤ 10. Do đó, các nghiên cứu tập trung vào việc nâng cao khả năng sửa lỗi của mã để khắc phục điểm hạn chế này. Để nâng cao hiệu quả sửa lỗi của mã, sơ đồ chữ ký CFS dựa trên hệ mật Niederreiter sử dụng phương pháp giải mã đầy đủ (complete decoding). Giải pháp được đề Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 61, 6 - 2019 91 xuất là sử dụng phương pháp giải mã ngoài giới hạn khoảng cách mã, dựa trên việc tìm một từ mã gần nhất với một từ mã trong không gian mã. Một giải pháp thực hiện giải mã đầy đủ là tiến hành sửa các lỗi cố định được thêm vào. Để giải mã một syndrome tương ứng với một lỗi có trọng số  = t+, có thể cộng  cột tùy ý của ma trận kiểm tra vào syndrome và tiến hành giải mã syndrome mới nhận được. Nếu tất cả  cột của tương ứng với một số vị trí lỗi thì syndrome mới sẽ tương ứng với một từ mã có trọng số t và có thể giải mã được. Nếu không, tiến hành thử lại với  cột khác cho tới khi giải mã được syndrome. Như vậy, có thể giải mã bất kỳ một syndrome nào tương ứng với một lỗi có trọng số nhỏ hơn hoặc bằng t+ [8]. Nếu  đủ lớn thì có thể thực hiện giải mã được syndrome bất kì. Tuy nhiên, khi  lớn sẽ dẫn đến xác suất giải mã thành công cho mỗi lần chọn  cột là giảm. Do đó, cần phải chọn các tham số mã để có  đủ nhỏ và đồng thời đảm bảo độ an toàn cho hệ mật. Thuật toán ký phải lặp lại quá trình giải mã cho đến khi giải mã thành công. Một giải pháp khác là lấy một syndrome ngẫu nhiên bất kỳ nhận được thông qua hàm băm và thực hiện giải mã, trường hợp nếu không giải mã được thì xáo trộn lại bản tin và băm lại một lần nữa; thực hiện lại các bước này cho tới khi tất cả các syndrome được giải mã thành công [8, 14]. Điểm hạn chế của sơ đồ chữ ký số CFS khi sử dụng phương pháp giải mã đầy đủ là thuật toán ký phải lặp lại trung bình t! lần. Vì vậy, đây là thuật toán ký chậm, khó được áp dụng trong thực tiễn. Nội dung tiếp theo bài báo đề xuất một giải pháp mới là sử dụng giải pháp ghép các mã BCH thành phần thành mã tổng thay thế cho mã Goppa trong đề xuất gốc. Nâng cao khả năng sửa của các mã thành phần này bằng cách sử dụng phương pháp giải mã thế dựa theo chuẩn syndrome. Từ đó, tăng tỷ lệ số các syndrome giải mã được trên tổng số syndomre. 3. XÂY DỰNG SƠ ĐỒ CHỮ KÝ SỐ TRÊN HỆ MẬT NIEDERREITER 3.1. Phương pháp giải mã thế dựa theo chuẩn syndrome Các phương pháp đại số giải mã BCH yêu cầu phải giải phương trình khóa bậc cao trên trường Galoa như thuật toán Berlekamp Massey (BMA), thuật toán Euclid (EA). Các thuật toán giải mã lặp BMA, EA có độ trễ xử lý lớn khi n và t tăng. Điều đó, hạn chế việc ứng dụng mã BCH vào các hệ thống thông tin thời gian thực. Qua việc nghiên cứu cấu trúc của mã BCH và các biến thể của nó, xây dựng một tham số mới là chuẩn syndrome. Chuẩn syndrome là bất biến với tác động của nhóm các dịch vòng và syndrome của các nhóm khác nhau thì khác nhau. Khi sử dụng chuẩn syndrome, các lỗi ngẫu nhiên và lỗi cụm có thể được sửa đồng thời do chuẩn syndrome của các vector lỗi ngẫu nhiên và một số cấu hình lỗi cụm độ dài nhỏ, lỗi cụm đồng pha không trùng nhau khi chọn đa thức sinh của trường một cách thích hợp. Đặc biệt khi kết hợp phương pháp chuẩn syndrome với phép thế cyctotomic cho phép giảm số lượng chuẩn syndrome cần xử lý nên có thể nâng cao chất lượng giải mã khi sửa lỗi bội cao [15], [16]. Thuật toán giải mã theo phương pháp chuẩn syndrome được thực hiện theo các bước như sau: + Tính syndrome S(e)=(s1,s1,,st) với si là phần tử của trường Galoa GF(2 m). + Tính bậc của chuẩn syndrome N. Tính degsj, degsi là bậc thành phần sj , si của syndrome S(e)=(s1,s1,si,sj,,st)với 1  j ≤ j  t. Tính chuẩn syndrome của S(e) và xác định bậc của nó degNij. + Từ degNij xác định vector sinh và bậc i0 của thành phần syndrome đầu tiên s 0 1 ứng với vector sinh. + Tính số thứ tự bit lỗi đầu tiên bằng Li = (degsi – degs 0 i) mod n. Kỹ thuật điều khiển & Điện tử Lê Văn Thái, “Xây dựng sơ đồ chữ ký số phương pháp giải mã theo chuẩn syndrome.” 92 + Tìm vector lỗi e bằng cách dịch vòng vector sinh đi Li nhịp. + Sửa tín hiệu nhận được: Cộng tín hiệu nhận được với vector lỗi tìm được. Phương pháp chuẩn syndrome giải mã mã BCH đã nâng cao được hiệu quả sửa lỗi của mã và có thể áp dụng mã BCH để thực hiện xây dựng được sơ đồ chữ ký số trên hệ mật Neiderreiter, khắc phục được các nhược điểm cơ bản của chữ ký số CFS dựa trên hệ mật Neiderreiter. 3.2. Đề xuất sơ đồ chữ ký số sử dụng mã ghép BCH Một sơ đồ chữ ký số ngoài việc đảm bảo các yêu cầu chặt chẽ về an ninh thì cần phải thỏa mãn hai điều kiện đó là: thuật toán tạo chữ ký số phải áp dụng ký được cho một bản tin bất kỳ và thuật toán xác nhận phải đủ nhanh. Các thuật toán của sơ đồ chữ ký số dựa trên mã ghép BCH được thực hiện như sau: a) Tạo khóa - Ma trận kiểm tra H của chuỗi mã được hình thành từ các ma trận kiểm tra của  mã thành phần có dạng:   1 ... ... ( ) ... ... ... ... i H H N K N H H            (4) - Chọn ma trận hoán vị P[N,N], ma trận khả nghịch Q[(N-K),(N-K)] trong trường GF(2). - Tính khóa mật H’ = Q.H.P. - Khóa công khai là (H’,t) và một hàm băm có đầu ra có kích thước N-K bit. b) Thuật toán ký Thuật toán tạo chữ ký số dựa trên chuỗi mã BCH thể hiện trên hình 3.      1 2|| || ... ||e e e e       1 2|| || ... ||s s s s  1 2 0{ , ,... , } Ty i i i i 1.T Ty P e1. Ts Q  ( || )h M j  1 2 0, ,... , )Sg i i i i  1j j  ( ) 1 i decs M i     Hình 3. Lưu đồ thuật toán ký sử dụng mã ghép BCH. - Bản tin cần ký M được cho dưới dạng chuỗi nhị phân. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 61, 6 - 2019 93 - Sử dụng một hàm băm để tiến hành băm bản tin, kết quả thu được một chuỗi nhị phân có độ dài N-K bit: =h(M). - Tính syndrome: Thực hiện nhân nghịch đảo của ma trận Q với chuỗi băm T để thu được một syndrome (độ dài N – K bit) s = Q-1.T. Từ số lượng mã BCH thành phần sử dụng (gồm mã), chia syndrome thu được thành các syndrome thành phần s(i) sắp xếp tương ứng với mỗi mã. - Tính chuẩn syndrome cho mỗi mã thành phần, giải mã các mã thành phần theo phương pháp thế dựa trên chuẩn syndrome: Nếu s(i) là một syndrome trong tập giải mã được (Mdec) ta tiến hành xác định vector lỗi e (i) theo phương pháp chuẩn syndrome tương ứng với mã thứ i. Ngược lại, ta ghép bản tin đầu vào với một biến đếm j và thực hiện quá trình lặp từ j=0 tăng dần một đơn vị cho đến khi giải mã thành công các syndrome thành phần s(i). Xác định và lưu giá trị i0 là giá trị của biến j nhỏ nhất mà tại đó tất cả các s (i) đều thực hiện giải mã được. - Hợp nhất các vector lỗi thành phần đã giải mã được thành vector lỗi tổng (chiều dài n bit) ta thu được e = e(1)||e(2)||||e(i)||||e(l). - Tính: yT = P-1.eT và xác định các tọa độ khác 0 của yT ta nhận được giá trị các vị trí lỗi của yT:{i1,i2,,it}. - Chữ ký thu được là (i1,i2,,it,i0) dưới dạng nhị phân. c) Thuật toán xác nhận chữ ký Sau khi văn bản và chữ ký được gửi đến bên nhận, phía nhận sẽ tiến hành việc xác nhận chữ ký. Lưu đồ thuật toán xác nhận chữ ký được trình bày trên hình 4. Hình 4. Lưu đồ thuật toán xác nhận chữ ký sử dụng mã ghép BCH. Trong bước xác nhận chữ ký, bên nhận có bản tin M và chữ ký Sg(i1,i2,,it,i0). Tách chữ ký Sg thành 2 thành phần, thành phần i0 và thành phần các tọa độ khác không {i1,i2,,it} của y T. - Tính giá trị băm ρ: Bên nhận sử dụng hàm băm cho trước để tiến hành băm văn bản sau khi đã ghép bản tin với thành phần i0 và thu được chuỗi giá trị băm ρ=h(M||i0). - Từ các tọa độ {i1,i2,,it} tiến hành khôi phục vector y T. - Tính ’T bằng cách nhân ma trận khóa công khai H’với yT:’T=H’.yT. Kỹ thuật điều khiển & Điện tử Lê Văn Thái, “Xây dựng sơ đồ chữ ký số phương pháp giải mã theo chuẩn syndrome.” 94 - Xác nhận: So sánh chuỗi giá trị băm ρ và ρ’ nếu hai chuỗi này trùng nhau thì chữ ký hợp lệ và được xác nhận, ngược lại chữ ký không được xác nhận. d) Lựa chọn tham số mã sử dụng trong sơ đồ chữ ký đề xuất Như đã thảo luận mục 2, điểm hạn chế cơ bản của sơ đồ chữ ký số xây dựng trên hệ mật McEliece hoặc Niederreiter là không ký được văn bản bất kỳ. Vì xác suất giải mã thành công đối với một syndrome bất kỳ là 1/t!, nếu tăng khả năng sửa lỗi t thì xác suất giải mã thành công giảm. Do đó, để xây dựng sơ đồ chữ ký số dựa trên hệ mật này cần tăng tỷ lệ số syndrome có thể giải mã được trên tổng số syndrome có thể có. Để thực hiện được điều đó, bài báo đề xuất giải pháp xây dựng sơ đồ chữ ký số sử dụng ghép các mã BCH thành phần. Mã BCH tổng với các mã thành phần có khoảng cách mã không lớn, sử dụng phương pháp giải mã thế theo chuẩn syndrome nhằm mở rộng khả năng sửa lỗi của mã. Thông qua khảo sát sự phụ thuộc của mức bảo mật vào chiều dài mã N khi sử dụng thuật toán tấn công của Canteaut-Chabaud [17] và thuật toán tấn công ngày sinh nhật [18] với mức an ninh ~ 80 bit, bộ tham số lựa chọn cho sơ đồ chữ ký số sử dụng mã ghép BCH như sau: Lựa chọn hàm băm SHA-1, chiều dài giá trị băm 160 bit. Số mã BCH thành phần lựa chọn 10 mã (  =10) gồm: Một mã C5(31,21) và mã thuận nghịch mở rộng C6(32,21), ba mã C7(31,16), một mã C8(32,16), hai mã C7(63,45) trên trường GF(26), hai mã C7(127,106), mỗi mã nói trên cho phép mở rộng khả năng sửa thêm 1 lỗi, ngoại trừ mã C7(31,16) có khả năng sửa đến 5 lỗi. Mô hình thuật toán đề xuất được thể hiện trên hình 5. Hình 5. Thuật toán mã hóa và giải mã sơ đồ mã ghép BCH. Khi đó, các tham số của mã tổng được xác định như sau: Khả năng sửa lỗi t=timax (i = 110, tmax là số bội lỗi tối đa mà mã thành phần có thể sửa được); tổng chiều dài mã hóa N=ni và K=ki (i = 110). Việc lựa chọn sử dụng các tham số của mã thành phần thành mã ghép tổng phải đảm bảo sao cho r =160, để tương ứng với bản tin đầu ra của hàm băm SHA-1 có độ dài chính bằng 160 bit và đây là giá trị được sử dụng làm syndrome. Thực hiện chia các giá trị băm này thành các syndrome tương ứng với mã thành phần để áp dụng phương pháp giải mã thế theo chuẩn syndrome trên từng mã thành phần. Độ dài của syndrome thành phần chính bằng số bit kiểm tra của mã đó. 10 1 11 1 15 3 16 1 18 2 21 2 160r N K               Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 61, 6 - 2019 95 Như vậy, khi lựa chọn bộ mã gồm 10 mã BCH thành phần trên, ta được mã tổng với các tham số mã: N = 568, K = 408, r = 160 và khả năng sửa lỗi t = 41. Chiều dài chữ ký được xác định như sau: Trong trường hợp tất cả các mã đều sửa tối đa số bội có thể tmax = 41; mỗi giá trị này được lưu dưới dạng chuỗi nhị phân 10 bit và cần thêm 10 bit để lưu trữ chỉ số ký lại phục vụ cho việc xác nhận. Do vậy, độ dài của chữ ký là 420 bit. Để khôi phục bản tin gốc: thực hiện tách 10 bit cuối, chuyển sang số thập phân ta nhận được số lần ký lặp lại. Số bit còn lại (410 bit), chia thành các chuỗi 10 bit và đổi sang thập phân. Nếu kết quả bằng 0 thì không có giá trị hay không thuộc vị trí nào, nếu lớn hơn 0 thì lưu lại vị trí trọng số vào mảng. Khôi phục lại vector chữ ký dài 568 bít có trọng số ở các vị trí tương ứng với các giá trị đã lưu trong mảng. 4. ĐÁNH GIÁ ĐỘ PHỨC TẠP VÀ ĐỘ BẢO MẬT SƠ ĐỒ CHỮ KÝ SỐ 4.1. Độ phức tạp của sơ đồ chữ ký số Độ phức tạp của chữ ký số phụ thuộc vào độ phức tạp của việc giải mã mã BCH. Hoạt động giải mã được thực hiện theo từng khối mã thành phần, bao gồm việc kiểm tra một đoạn n - ki bit có là syndrome hay không. Dựa trên phương pháp chuẩn syndrome cho phép mở rộng khả năng sửa lỗi của mã lên đến t+1 lỗi, khảo sát tỷ lệ số syndrome có thể giải mã được trên tổng số syndrome có thể được thể hiện trong bảng 1. Bảng 1. Tỷ lệ syndrome có thể giải mã được. STT Số mã thành phần Mã thành phần Tỷ lệ syndrome có thể giải mã được 1 1 C5(31,21) 100% 2 1 C6(32,21) 72,7% 3 3 C7(31,16) 89,9% 4 2 C7(63,45) 77,2% 5 2 C7(127,106) 97,8% 6 1 C8(32,16) 34,3% Tỷ lệ trung bình các syndrome có thể giải mã được xác định theo công thức: 1 10,3%diP    (5) Do đó, thuật toán đề xuất cần phải thực hiện băm lại văn bản trung bình 10 lần. Bỏ qua độ phức tạp của các mã khoảng cách nhỏ ni≤32, độ phức tạp của sơ đồ chữ ký xác định theo công thức (6) và có giá trị 225,7.   3 3 2 2 63 2 127 21 1 1 2. .log 63 2. .log (127) 2 ( ) 2i iDS i iW C C N N K            (6) Độ phức tạp của việc xác nhận chữ ký: Đó là độ phức tạp của việc quyết định syndrome từ vector lỗi, thực hiện nhân ma trận N×(N-K) với vector độ dài N. Với thuật toán đề xuất, việc xác nhận yêu cầu N×(N-K)/2 phép tính nhị phân tương đương độ phức tạp 15,52 . Đây là độ phức tạp chấp nhận được và có thể thực hiện được trong thực tế. 4.2. Đánh giá khả năng bảo mật của sơ đồ chữ ký số đề xuất a) Tấn công giải mã Sơ đồ chữ ký số sử dụng mã ghép BCH với các tham số đề xuất ở trên đảm bảo được độ bảo mật khi áp dụng các thuật toán tấn công vào sơ đồ. Độ an toàn của sơ đồ Kỹ thuật điều khiển & Điện tử Lê Văn Thái, “Xây dựng sơ đồ chữ ký số phương pháp giải mã theo chuẩn syndrome.” 96 chữ ký số khi sử dụng thuật toán tấn công của Canteaut-Chabaud [17] là 284,2 và 2127 khi sử dụng thuật toán tấn công ngày sinh nhật [18]. b) Tấn công cấu trúc Trường hợp sử dụng thuật toán tấn công, cho phép xác định được ma trận H và Q, khi đó sẽ tính toán và tìm được ma trận P. Sau đó, với mỗi khóa bí mật, thuật toán phải thực hiện kiểm tra cho tới khi khóa này là khóa đúng. Đối với sơ đồ chữ ký đề xuất, độ phức tạp của phương pháp tấn công này sẽ tăng theo độ phức tạp của các mã BCH thành phần. Vì các mã BCH, mã BCH mở rộng, mã thuận nghịch có độ dài khác nhau với các đa thức sinh khác nhau. Ngoài ra còn áp dụng hoán vị với các mã BCH thành phần để tăng thêm độ phức tạp tấn công cấu trúc. Để tấn công cấu trúc trong trường hợp thuận lợi nhất là xác định được tham số ni, ki của mã thành phần. Từ đó, tính toán xác định việc sử dụng các mã thành phần còn lại. Giả sử thay đổi tham số b để bí mật ma trận mã BCH thành phần (có khoảng cách cấu trúc d = 5, 7), cho công khai các đa thức sinh của trường GF(2m), m = 5, 6, 7. Trong đề xuất cho phép sử dụng mã BCH mở rộng, mã thuận nghịch và mở rộng của nó nên số lượng mã có thể chọn sẽ tăng đột biến. Mặt khác tương ứng có 6; 6; 14 đa thức nguyên thủy bậc 5, 6, 7. Các mã được sắp xếp thành chuỗi theo một thứ tự ngẫu nhiên. Do đó, số lượng mã thành phần khác nhau là 10668 mã và độ phức tạp xác định cấu trúc 10 mã thành phần khoảng 2137. Với các giá trị của độ phức tạp tấn công giải mã và tấn công cấu trúc vào sơ đồ đề xuất ở trên, đã khẳng định độ an toàn bảo mật của sơ đồ đề xuất trước các tấn công phổ biến vào sơ đồ. Kết quả thử nghiệm sơ đồ chữ ký số sử dụng mã ghép BCH trên máy tính core-i5 2.3 GHz, RAM 8GB: - Số lần ký lại trung bình khoảng 10 lần, - Thời gian ký trung bình nhỏ hơn 20 ms, - Thời gian xác nhận chữ ký nhỏ hơn 1ms. Bảng 2. So sánh sơ đồ chữ ký dựa trên mã ghép BCH và sơ đồ chữ ký CFS. TT Sơ đồ chữ ký Sơ đồ chữ ký CFS (m = 15, t = 12) Sơ đồ chữ ký dựa trên mã ghép BCH 1 Độ dài chữ ký (bit ) 180 420 2 Kích thước khóa (Kbyte) 720 11 3 Độ phức tạp của chữ ký 247,7 225,7 4 Độ phức tạp của xác nhận 221,5 215,5 5 Tấn công giải mã ISD 288 284,2 6 Tấn công cấu trúc 2119 2137 Qua bảng so sánh trên, sơ đồ chữ ký số sử dụng mã ghép BCH đề xuất cho phép giảm kích thước khóa 65 lần trong cùng mức an ninh. Cho phép tăng độ bảo mật lên nhiều lần do khó thực hiện tấn công thông thường với sơ đồ trên. Đặc biệt, độ phức tạp thực hiện của chữ ký giảm nhiều lần thông qua việc giảm độ dài của các mã thành phần và sử dụng phương pháp giải mã thế dựa trên chuẩn syndrome. Phương pháp giải mã này cho phép mở rộng khả năng sửa lỗi của mã, đồng thời tăng số lượng các syndrome có thể giải mã được nên khắc phục nhược điểm cơ bản của hệ mật mã dựa trên mã trong đề xuất gốc. 5. KẾT LUẬN Bài báo đề xuất sơ đồ chữ ký số mới dựa trên cấu trúc mã ghép BCH. Phương pháp giải mã thế dựa trên chuẩn syndrome để giải mã các mã thành phần đã cho phép mở rộng được Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 61, 6 - 2019 97 khả năng sửa lỗi của mã đồng thời làm tăng độ phức tạp của tấn công cấu trúc và tấn công giải mã. Sơ đồ đề xuất mới cũng đã khảo sát các dạng tấn công điển hình vào sơ đồ. Kết quả khảo sát cho thấy sơ đồ chữ ký số đề xuất cho phép giảm kích thước khóa 65 lần so với sơ đồ chữ ký số CFS (m =15, t = 12) trong cùng mức an ninh và giảm được độ phức tạp của quá trình ký và xác nhận. Kết quả thử nghiệm chương trình phần mềm sơ đồ chữ ký số đề xuất trên máy tính core-i5 6200U 2.3 GHz, RAM 8 GB: số lần ký lại trung bình khoảng 10 lần, thời gian ký trung bình nhỏ hơn 20 ms, thời gian xác nhận nhỏ hơn 1ms. Với những kết quả đạt được, sơ đồ chữ ký đề xuất có thể đáp ứng được yêu cầu của các hệ thống bảo mật trong thực tế. TÀI LIỆU THAM KHẢO [1]. Grover L. K. (1996), "A fast quantum mechanical algorithm for database search", STOC, pp: 212-219. [2]. Shor P. W. (1997), "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", SIAM Journal on Computing, 25(5), pp: 1484- 1509. [3]. L. Chen S. J., Y.K. Liu, D. Moody, R. Peralta, R. Perlner, D. S. Tone. (2016), "Report on Post-Quantum Cryptography". The National Institute of Standards and Technology Internal Report 8105, U.S. Department of Commerce. [4]. Berlekamp E., McEliece R., and Tilborg H. v. (1978), "On the Inherent Intractability of Certain Coding Problems", IEEE Transactions on Information Theory, 24(3), pp: 384-386 [5]. Cayrel P. L., Gaborit P., Giraul M. (2007). Identity-based identification and signature schemes using correcting codes, International Workshop on Coding and Cryptography 2007, pp: 69-78. [6]. Finiasz M., and Sendrier N. (2011), "Digital Signature Scheme Based on McEliece", in : Henk C.A. van Tilborg and Sushil Jajodia (editors), Encyclopedia of Cryptography and Security (2nd edition), Springer., pp: 342-343. [7]. Kabatianskii G., Krouk E., and Smeets B. (1997). A digital signature scheme based on random error correcting codes, The 6th IMA International Conference on Cryptography and Coding, London, UK, 1997, pp: 161-167. [8]. Courtois N., Finiasz M., and Sendrier N. (2001). How to achieve a mceliece based digital signature scheme, Lecture Notes in Computer Science, pp: 157-174. [9]. Otmani A., and Tillich J. P. (2011). An Efficient Attack on All Concrete KKS Proposals, International Workshop on Post-Quantum Cryptography, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, Vol 7071, pp: 98-116. [10]. Finiasz M., and Sendrier N. (2009). Security Bounds for the Design of Code-Based Cryptosystems, Advances in Cryptology ASIACRYPT 2009, Lecture Notes in Computer Science, pp: 88-105. [11]. Wagner D. (2002). A Generalized Birthday Problem, Annual International Cryptology Conference: Advances in Cryptology - CRYPTO 2002, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, pp: 288-304. [12]. Niederreiter H. (1986), "Knapsack-type Cryptosystems and Algebraic Coding Theory", Problems of Control and Information Theory, 15(2), pp: 159-166. [13]. Bernstein D. J., Buchmann J., and Dahmen E. (2009), Post-quantum cryptography, Springer-Verlag Berlin Heidelberg, pp: 95-145. Kỹ thuật điều khiển & Điện tử Lê Văn Thái, “Xây dựng sơ đồ chữ ký số phương pháp giải mã theo chuẩn syndrome.” 98 [14]. Hamdi O., Harari S., and Bouallegue A. (2006), "Secure and fast digital signatures using BCH codes", IJCSNS International Journal of Computer Sience and Network Security, 6(10), pp: 220-226. [15]. Thai L.V, and Hoan P.K. (2017), A novel method of decoding the BCH code based on norm syndrome to improve the error correction efficiency, RTTR 2017. The 2nd Workshop on Recent Trends in Telecommunications Research, TNE Research Group, Massey University. [16]. Hoan P.K, Thai L.V, and Ha V.S. (2013), Simultaneous correction of random and burst errors using norm syndrome for BCH codes, National Conference on Electronics and Communications (REV2013-KC01) [17]. Finiasz M., and Sendrier N. (2009). Security Bounds for the Design of Code-Based Cryptosystems, Advances in Cryptology ASIACRYPT 2009, Lecture Notes in Computer Science, pp: 88-105 [18]. Bernstein D. J., Lange T., and Peters C. (2008). Attacking and defending the McEliece cryptosystem, Post-Quantum Cryptography, Second International Workshop, PQCrypto2008, Cincinnati, OH, USA, October 17-19, 2008, pp: 31-46. ABSTRACT CONSTRUCTION OF CODE BASED CRYPTOSYSTEM DIGITAL SIGNATURE SCHEME USING NORM SYNDROME FOR BCH CODES The content of the paper proposes a digital signature scheme based on the Niederreiter cryptosystem, this is variant of the McEliece cryptosystem. To overcome the major key size drawback in the original proposal and limit the ability to sign any document, the paper used a component BCH concatenation solution and used the norm-syndrome based decoding method for BCH code. Test results of proposed scheme on Corei5-2.3GHz, 8Gb Ram computers: signing time is less than 20ms, signature confirmation time is less than 1ms and allows to reduce the size of the key 65 times compared to the CFS signature (m = 15, t = 12) in the same security level. At the same time, the proposed digital signature scheme guarantees security against structural attacks and decryption attacks. Keywords: Niederreiter cryptosystem; McEliece cryptosystem; Digital signature scheme; Code-based cryptosystem; Norm syndrome. Nhận bài ngày 20 tháng 3 năm 2019 Hoàn thiện ngày 16 tháng 4 năm 2019 Chấp nhận đăng ngày 17 tháng 6 năm 2019 Địa chỉ: Khoa Điện tử, Trường Đại học Công nghiệp Hà Nội. *Email: thailv@haui.edu.vn.