Sơ đồ chữ ký số đặc biệt - Phạm Văn Hiệp

Công nghệ thông tin & Cơ sở toán học cho tin học P. V. Hiệp, H. V. Việt, “Sơ đồ chữ ký số đặc biệt.” 110 SƠ ĐỒ CHỮ KÝ SỐ ĐẶC BIỆT Phạm Văn Hiệp1* , Hoàng Văn Việt2 Tóm tắt:Bài báo đề xuất một sơ đồ chữ ký số đặc biệt nhằm giải quyết vấn đề trong giao thức thỏa thuận khóa giữa hai đối tượng cần giao dịch truyền thông báo cho nhau, khi đó, các thông tin về thỏa thuận khóa của mỗi người chỉ cần đến sự đảm bảo của chức năng xác thực người ký và bảo toàn văn bản được ký. Từ sơ đồ chữ ký đặc biệt được xây dựng, chúng tôi phân tích khả năng ứng dụng được của sơ đồ trong hai giao thức nhóm tiêu biểu đó là giao thức thỏa thuận khóa nhóm và giao thức tạo chữ ký số tập thể. Ngoài ra, bài báo còn đề cập đến một số vấn đề và có thể nghiên cứu tiếp từ sơ đồ chữ ký đặc biệt đã được xây dựng. Từ khoá: Sơ đồ; Chữ ký số đặc biệt (SDS). 1. MỞ ĐẦU Sơ đồ chữ ký số ra đời nhằm giải quyết các vấn đề cơ bản như: Xác thực người ký; Bảo toàn văn bản được ký; Chống sự chối bỏ trách nhiệm của người ký, ... Ngoài ra chúng luôn được thiết kế theo kiểu: Ai cũng kiểm tra được. Các sơ đồ chữ ký được đưa vào chuẩn của thế giới [1, 2, 3] đều đảm bảo đầy đủ các chức năng nêu trên, tuy nhiên, trong nhiều ứng dụng thực tế không nhất thiết cần đến quá nhiều sự đảm bảo như vậy, chẳng hạn, trong giao thức thỏa thuận khóa giữa hai đối tượng thì các thông tin về thỏa thuận khóa của mỗi người chỉ cần đến sự đảm bảo của hai chức năng đầu và cũng chỉ cần bản thân họ kiểm tra được chữ ký của người còn lại mà thôi. Để phục vụ được cho những nhu cầu đặc biệt trên, đương nhiên, chúng ta chỉ cần có những sơ đồ chữ ký với chức năng vừa đủ được gọi là “chữ ký số đặc biệt”. Trong bài viết này, chúng tôi đề xuất một sơ đồ chữ ký số đặc biệt, viết tắt là SDS (Special Digital Signature). Sơ đồ SDS được đưa ra cùng các phân tích về nó trong phần 2. Phần 3 dành để phân tích khả năng ứng dụng được sơ đồ SDS trong các giao dịch trong giao thức thỏa thuận khóa và trong giao thức tạo chữ ký số nhóm. Trong trường hợp ứng dụng được, chúng tôi phân tích sự hiệu quả của việc ứng dụng này. Phần 4 là các vấn đề cần và có thể nghiên cứu tiếp. 2. SƠ ĐỒ SDS 2.1. Sơ đồ SDS Sơ đồ SDS được thiết kế để phục vụ bài toán sau đây: Bài toán. (Hai đối tượng xác thực lẫn nhau) Cho hai đối tượng A và B cần thực hiện giao dịch truyền thông báo cho nhau đảm bảo được rằng: Người nhận có thể kiểm tra được thông báo đó có đúng là người còn lại gửi cho mình và có bị thay đổi hay không. 2.1.1. Thiết kế hệ thống Tham số hệ thống bao gồm một hàm f: K×M → S với K là tập các khóa, M là tập các thông báo và S là tập các chữ ký có các tính chất sau: Từ cặp (m,f(k,m)) với m ∈ M khó tìm được k. (1) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 49, 06 - 2017 111 Với mỗi k ∈ K, khó tìm được m và m’ thỏa mãn f(k,m) = f(k,m’). (2) Chú ý 1. Để thỏa mãn được điều kiện (1) thì tập K phải đủ lớn để chống lại việc tìm k theo phương pháp vét cạn k ∈ K. Điều kiện (2) là một điều kiện mà các hàm Hash an toàn luôn có. Mỗi cặp đối tượng (A,B) thỏa thuận chọn một khóa bí mật chung ,A Bk ∈ K. Khi này, thuật toán ký và kiểm tra chữ ký được thực hiện như sau: 2.1.2. Thuật toán ký Input: m ∈ M, thông báo cần ký. Output: s ∈ S, chữ ký lên thông báo m. 1. s ← f( ,A Bk ,m); 2. return s. 2.1.3. Thuật toán kiểm tra chữ ký Input: (m,s), m ∈ M là thông báo được ký bởi chữ ký s do người gửi thực hiện. Output: Accept∈ {0,1}, chấp nhận s là chữ ký lên văn bản M của người gửi. 1. s’ ← f( ,A Bk ,m); 2. Accept ← (s == s’); 3. return Accept. Dễ dàng nhận ra rằng, từ giả thiết ,A Bk là thông tin bí mật chung của A và B nên hai người này luôn luôn thực hiện ký và chữ ký luôn được chấp nhận trong thuật toán kiểm tra. Ngược lại, từ điều kiện thứ nhất đối với f nên với mọi đối tượng C khác do chỉ biết f và biến thứ hai là m nên không thể tạo ra chữ ký được A (và B) chấp nhận. Từ giả thiết f là hàm một chiều nên C cũng khó tìm được ,A Bk từ một chữ ký hợp lệ nào đó do A hoặc B đã thực hiện. Tóm lại ta có kết kết quả sau: Kết quả 1. Sơ đồ chữ ký SDS đảm bảo cho A (hoặc B) sau khi nhận được (m,s) và thực hiện việc kiểm tra cho kết quả 1 thì tin tưởng được hai điều sau: (m,s) là do chính B (tương tự A) gửi cho mình. m đã không bị thay đổi. Khả năng chống được tấn công giả mạo (hay độ an toàn của sơ đồ) đúng bằng độ khó tối thiểu trong hai tính chất cần có của hàm f. 2.2. Chức năng chống chối bỏ trách nhiệm có điều kiện của SDS Hiển nhiên SDS không cung cấp khả năng chống chối bỏ trách nhiệm trước văn bản đã được ký (m,s) vì cả A lẫn B đều có thể làm được điều này. Tuy nhiên, ta có kết quả sau Kết quả 2. Nếu tồn tại thông báo m được A ký theo SDS đối với B là (m,s) và A ký theo SDS đối với B’ ≠ B là (m,s’) thì chỉ có A làm được điều này. Chứng minh: Theo SDS thì chỉ có các đối tượng thuộc tập S = {A,B} là tạo được (m,s) hợp lệ và tương tự chỉ có các đối tượng thuộc tập S’ = {A,B’} là tạo được (m,s’) hợp lệ nên tập các đối tượng tạo được cả (m,s) và (m.s’) hợp lệ là S∩S’ = {A}. Công nghệ thông tin & Cơ sở toán học cho tin học P. V. Hiệp, H. V. Việt, “Sơ đồ chữ ký số đặc biệt.” 112 Chức năng nêu trên của SDS chúng tôi gọi là “chống chối bỏ trách nhiệm có điều kiện”. 2.3. Một SDS thiết kế từ các hàm Hash Trong mục này, chúng tôi giới thiệu một lớp các sơ đồ SDS có thể được thiết kế từ các hàm Hash như sau. Kết quả 3. Trong trường hợp K =  0,1 n , M = 0,1  và S =  0,1 h với n và h đủ lớn thì hàm f dùng để thiết kế cho sơ đồ SDS có thể xây dựng từ một hàm tóm lược an toàn Hash:  0,1  →  0,1 h theo công thức sau: f(k,m) = Hash(k||m) (3) Chứng minh: Nếu từ cặp (m, Hash(k||m)) với m ∈ M nào đó ta tính được k. Như vậy, ta đã tìm được nghịch ảnh của Hash(k||m) và điều này là mâu thuẫn với giả thiết Hash an toàn nên (1) được thỏa mãn. Điều kiện (2) là đương nhiên từ chú ý 1 nên kết quả đã được chứng minh. 3. KHẢ NĂNG ỨNG DỤNG CỦA SƠ ĐỒ SDS TRONG CÁC GIAO THỨC NHÓM Xuất phát sơ đồ SDS được đưa ra nhằm giải quyết vấn đề thỏa thuận khóa giữa hai đối tượng nên việc ứng dụng nó trong giao thức này là hiển nhiên. Trong phần này, chúng tôi giới thiệu thêm các dụng của SDS trong hai giao thức nhóm tiêu biểu đó là giao thức thỏa thuận khóa nhóm [4, 5] và giao thức tạo chữ ký tập thể [6, 7]. Trong hai loại giao thức kể trên luôn xuất hiện một cách phổ biến ba kiểu giao dịch đó là: Kiểu 1-1: Đối tượng U cần truyền một thông báo m cho đối tượng V. Kiểu 1-n: Đối tượng U cần truyền một thông báo m cho n đối tượng  1 2, ,...., nV V V , kiểu giao dịch này còn được gọi là “truyền quảng bá”. Kiểu n-1: n đối tượng  1 2, ,...., nU U U cần truyền n thông báo  1 2, ,...., nm m m (tương ứng iU truyền im ) cho  1 2, ,...., nV U U U , kiểu giao dịch này còn được gọi là “thu thập thông tin”. Tuy nhiên, tùy theo tính mục đích của giao thức mà các giao dịch nêu trên có những đòi hỏi không giống nhau, cụ thể: Trong giao thức thỏa thuận khóa nhóm thì người nhận (hoặc tập các người nhận) chỉ cần xác định thông tin m nhận được chỉ có thể là U và thông tin này không bị thay đổi. Những yêu cầu nêu trên nhằm mục đích chống lại các đối tượng ngoài nhóm thực hiện các kiểu tấn công xen giữa. Trong giao thức tạo chữ ký tập thể thì nếu thông tin m có liên quan đến trách nhiệm của U thì nó cần phải được đảm bảo thêm rằng U không thể chối bỏ trách nhiệm về thông tin đã truyền. Do SDS dùng cho hai đối tượng U và V chỉ cung cấp chức năng xác thực người gửi và sự bảo toàn thông tin được ký chứ không chống được sự chối bỏ trách nhiệm của người gửi cho nên các giao thức kiểu 1-1 loại sơ đồ SDS chỉ dùng cho giao thức thỏa thuận khóa và không dùng được cho giao thức tạo chữ ký tập thể. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 49, 06 - 2017 113 Như vậy, các giao dịch chúng sẽ đề cập ở đây ngoài việc truyền tin thông thường còn phải được các bên tham gia đảm bảo các điều kiện mật mã nào đó đối với người gửi (ký vào thông báo) và người nhận phải kiểm tra được các điều kiện được đảm bảo đó (kiểm tra chữ ký). Các giao dịch loại này người ta còn gọi là “giao dịch mật mã”. Hai mục 3.2 và 3.3 chúng tôi phân tích việc có thể sử dụng sơ đồ SDS trong hai kiểu giao dịch 1-n và n-1 loại mật mã. Trong trường hợp sử dụng được thì sẽ đưa ra đánh giá tính hiệu quả của việc thay thế GDS (General Digital Signature - chữ ký số tổng quát) bằng SDS và cơ sở cho việc đánh giá tính hiệu quả là thời gian thực hiện giao thức sẽ được trình bày trong mục 3.1. 3.1. Thời gian thực hiện một giao thức và việc so sánh tính hiệu quả giữa hai giao thức Trong mục này, chúng tôi bàn đến một thông số quan trọng dùng để đánh giá tính hiệu quả của giao thức đó là thời gian thực hiện của nó được định nghĩa như sau. Định nghĩa 1. Thời gian thực hiện một giao thức là khoảng thời gian bắt đầu từ lúc mọi thành viên tham gia đã sẵn sàng đến lúc kết thúc giao thức. Định nghĩa 2. Cho X và Y là hai giao thức cùng giải quyết một bài toán với thời gian thực hiện tương ứng là T(X) và T(Y). Khi này, ta nói X hiệu quả hơn Y nếu có bất đẳng thức sau: T(X) < T(Y) (4) Một giao dịch thực chất cũng là một giao thức nên ta cũng có thể dùng định nghĩa trên để xác định thời gian thực hiện của nó. Ví dụ. Giao dịch kiểu 1-1: Đối với loại thông thường thì thời gian thực hiện giao dịch này đúng bằng thời gian truyền thông báo m từ U đến V. Còn đối với loại mật mã thì ngoài thời gian truyền thông báo còn phải thêm vào thời gian tạo chữ ký của U và thời gian kiểm tra chữ ký của V. Cho X là một sơ đồ chữ ký, hý hiệu ( )signT X và er ( )vT X lần lượt là thời gian tạo chữ ký và thời gian kiểm tra chữ ký của X. Khi đó, với hai sơ đồ X và Y ta có thể nói “X là hiệu quả hơn Y” nếu có bất đẳng thức sau: ( )signT X + er ( )vT X < ( )signT Y + er ( )vT Y (5) Từ ví dụ trên, định nghĩa 2 chúng ta thu ngay được hệ quả sau: Hệ quả 1. Giao dịch mật mã kiểu 1-1 sử dụng sơ đồ chữ ký hiệu quả hơn thì sẽ hiệu quả hơn. Kết luận trên vẫn còn đúng đối với các giao dịch mật mã kiểu 1-n và kiểu n-1 giữa hai sơ đồ chữ ký cùng tính năng. Tuy nhiên, điều chúng ta cần quan tâm ở đây và việc thay sơ đồ GDS bằng một sơ đồ SDS (hiệu quả hơn) thì ra sao. Các vấn đề sẽ được giải quyết tại các mục sau. 3.2. Giao dịch kiểu 1-n Kết quả 2 cho thấy SDS có thêm tính năng chống chối bỏ trách nhiệm của người gửi trong trường hợp n > 1, như vậy, giao dịch mật mã kiểu 1-n đều giải được bởi sơ đồ chữ ký SDS. Kết quả 4. Cho GDS và SDS lần lượt là sơ đồ chữ ký tổng quát và sơ đồ chữ ký đặc biệt. Nếu Công nghệ thông tin & Cơ sở toán học cho tin học P. V. Hiệp, H. V. Việt, “Sơ đồ chữ ký số đặc biệt.” 114 ( ) . ( )sign signT GDS u T SDS (6) er er( ) . ( )v vT GDS v T SDS (7) Ký hiệu T(X: 1-n) là thời gian thực hiện giao dịch kiểu 1-n khi sử dụng sơ đồ X, ta có: T(SDS 1-n) = 1n u v   T(GDS 1-n) (8) Chứng minh: Theo định nghĩa về SDS ta có thể coi er( ) ( )sign vT SDS T SDS , ký hiệu T(SDS), nên việc sử dụng SDS trong giao dịch kiểu 1-n thì người gửi phải thực hiện n lần việc ký khác nhau và do mỗi người nhận chỉ cần kiểm tra 1 chữ ký nên tổng thời gian cho giao dịch này là: T(SDS 1-n) = (n+1).T(SDS) (9) Trong khi nếu dùng sơ đồ GDS thì người ký chỉ cần thực hiện ký đúng 1 lần còn n người kiểm tra do có thể thực hiện đồng thời nên từ (6) và (7) ta có tổng thời gian cho giao dịch này là: T(GDS 1-n) = ( )signT GDS + ( )verT GDS = (u+v).T(SDS) (10) Từ (9) và (10) suy ngay ra (8), vậy, kết quả đã được chứng minh. Chú ý. Với đẳng thức (8) trong kết quả thu được trên chúng ta thấy rằng việc thay SDS cho GDS không luôn luôn hiệu quả cho dù SDS là hiệu quả hơn GDS. Sự hiệu quả chỉ có nếu 1 1 n u v    tức là với số người nhận đủ nhỏ. 3.3. Giao dịch kiểu n-1 Vì SDS không cung cấp chức năng chống chối bỏ trách nhiệm nên sơ đồ này chỉ sử dụng được đối với giao dịch không cần đến yêu cầu trên. Cũng với những giả thiết về SDS và GDS theo (6) và (7) ta có: Kết quả 5. Ký hiệu T(X: n-1) là thời gian thực hiện giao dịch kiểu n-1 khi sử dụng sơ đồ X ta có: T(SDS 1-n) = 1 . n u n v   T(GDS 1-n) (11) Chứng minh: Đối với cả hai sơ đồ SDS và GDS thì giao dịch kiểu n-1 luôn tiến hành giống hệt nhau đó là cả n người gửi đồng thời tính chữ ký lên văn bản cần gửi của mình. Còn người nhận phải lần lượt kiểm tra đúng n chữ ký nêu trên, như vậy ta có: T(X: n-1) = ( ) . ( )sign verT X n T X (12) Dùng (12) cho GDS rồi thay (6) và (7) vào ta được: T(GDS: n-1) = ( ) . ( )sign verT GDS nT GDS = . ( ) .( . ( ))sign veru T SDS n v T SDS = (u+n.v).T(SDS) (13) Dùng (12) cho SDS ta được: Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 49, 06 - 2017 115 T(SDS: n-1) = er( ) . ( )sign vT SDS n T SDS = (n+1).T(SDS) (14) Từ (13) và (14) ta có ngay điều cần chứng minh. 4. MỘT SỐ VẤN ĐỀ CẦN NGHIÊN CỨU TIẾP Ngoài việc tìm thêm các sơ đồ SDS mới theo cách là tìm ra các hàm f thỏa mãn điều kiện nêu trong mục 2.1.1 chúng ta có thể giải quyết một số vấn đề sau: Vấn đề 1. Có thể nghiên cứu loại sơ đồ SDS nhưng dùng chung cho cả nhóm với khóa chung dài hạn cho giao thức thỏa thuận khóa phiên . Khi này, trong giao dịch kiểu 1- n, người gửi sẽ không cần phải thực hiện n lần ký theo SDS cho nên tử số của (8) chỉ là 2 và hiệu quả của việc dùng SDS sẽ tăng lên (u+v)/2 lần giống như trong giao dịch kiểu 1-1. Vấn đề 2. Các giao dịch kiểu n-1 có yêu cầu chống chối bỏ vốn không sử dụng được sơ đồ SDS. Ta có thể nghiên cứu việc thay kiểu giao dịch trên bằng kiểu giao dịch n-2 (khi này sẽ có đủ bằng chứng để chống chối bỏ). Khi này, số các lần tạo chữ ký SDS của mỗi người gửi sẽ phải tăng gấp đôi (do phải gửi cho 2 người) nhưng số lần kiểm tra chữ ký SDS vẫn không tăng vì do 2 người đảm nhiệm. Vấn đề 3. Vấn đề xác định (hay ước lượng) hai giá trị hai tham số u và v trong các công thức (6) và (7) đối với hai sơ đồ SDS và GDS cụ thể. Nói riêng là sơ đồ SDS được thiết kế từ hàm Hash vì với sơ đồ này cả hai tham số u và v đều lớn hơn 1 do mọi sơ đồ GDS hiện hữu như RSA, Elgamal, ECDS... đều có thực hiện việc tính hàm Hash trong cả hai công đoạn tạo và kiểm tra chữ ký. Muốn vậy, ta cần phải xác định thời gian thực hiện tính hàm Hash và tìm công thức so sánh với với thời gian tính các hàm dùng trong việc tạo ra chữ ký và kiểm tra chữ ký của các sơ đồ GDS. Lời cảm ơn: Nhóm tác giả gửi lời cảm ơn chân thành đến các Thầy giảng dạy tại Học viện Kỹ thuật Mật mã, Học viện Kỹ thuật quân sự đã có những chỉ dẫn và góp ý quan trọng hình thành nên bài viết này. Rất mong nhận được sự đóng góp và chia sẻ từ các đồng nghiệp. TÀI LIỆU THAM KHẢO [1]. National Institute of Standards and Technology, “Digital Signature Standard (DSS)”, NIST FIPS Publication 186-3, U.S. Department of Commerce, June 2009. [2]. GOST R 34.10-94. Russian Federation Standard. Information Technology. Cryptographic data Security. “Produce and check procedures of Electronic Digital Signature based on Asymmetric Cryptographic Algorithm”, Government Committee of the Russia for Standards, 1994 (in Russian). [3]. ElGamal T. (1985), “A public key cryptosystem and a signature scheme based on discrete logarithms”, IEEE Transactions on Information Theory, Vol. IT-31, No. 4, pp. 469 – 472. [4]. Diffie W, Hellman M. (1976), “New Directions in Cryptography”, IEEE Trans. On Info. Theory, IT-22(6), pp. 644-654. [5]. Keith Palmgren, “Diffie-Hellman Key Exchange: A Non-mathematician’s explanation”, ISSA Journal, 10-2006. [6]. Harn L. (1999), “Digital multisignature with distinguished signing authorities”, Electronics Letters, Vol. 35, pp. 294-295. Công nghệ thông tin & Cơ sở toán học cho tin học P. V. Hiệp, H. V. Việt, “Sơ đồ chữ ký số đặc biệt.” 116 [7]. Hakim Khali, MIEEE and Achene Farah, SIEEE. “DSA and ECDSA-based Multi- Signature Schemes”. IJCSNS International Jornal of Computer Science and Network Security, VOL. 7 No. 7, July 2007. ABSTRACT SPECIAL DIGITAL SIGNATURE SCHEME The article proposes a special digital signature scheme that addresses the problem in the key-agreement protocol between two entities that need to communicate to each other. Then the information about the key-agreement of each person only needs the guarantee of the signer authentication function and preserve the signed text. From the special signature scheme developed, we analyze the applicability of the diagrams in the two typical group protocols that are the group key agreement protocol and the collective digital signature protocol. In addition, the article addresses a number of issues and may proceed from the special signature scheme developed. Keywords: Schema; Special digital signature (SDS). Nhận bài ngày 18 tháng 5 năm 2017 Hoàn thiện ngày 13 tháng 6 năm 2017 Chấp nhận đăng ngày 20 tháng 6 năm 2017 Địa chỉ: 1ĐH Công nghiệp Hà Nội; 2Ban CNTT Binh chủng Thông tin-Liên lạc. *Email: hiephic@gmail.com