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