Xây dựng giao thức xác lập khóa cho các hệ mật mã khóa bí mật

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số x (2x), tháng x/201x XÂY DỰNG GIAO THỨC XÁC LẬP KHÓA CHO CÁC HỆ MẬT MÃ KHÓA BÍ MẬT CONSTRUCTION OF KEY ESTABLISHMENT PROTOCOL FOR SECRET KEY CRYPTOGRAPHY SYSTEMS Lưu Hồng Dũng Abstract: This paper proposed a key establishment protocol for secret key cryptography systems. This protocol has the capacity of key establishment and anthentication. The paper also offers analysis on the safety of the proposed protocol, has shown the ability to apply it in practice. Từ khóa: Key Establishment, Key Agreement Protocol, Key Transport Protocols, Secret Key Cryptography S ystem, Public Key Cryptography S ystem. I. ĐẶT VẤN ĐỀ Phương pháp xác lập khóa cho các hệ mật mã khóa bí mật được đề xuất đầu tiên bởi W. Diffie và M. Hellman vào năm 1976 và được gọi là giao thức trao thỏa thuận Diffie-Hellman (Diffie- Hellman Key Agreement Protocol) (gọi tắt là phương pháp Diffie-Hellman), sau đó đã mở ra một lĩnh vực mới về khoa học mật mã: mật mã khóa công khai. Hiện tại nó vẫn được sử dụng rất phổ biến với nhiều biến thể khác nhau. Nhược điểm cơ bản của phương pháp Diffie-Hellman là không có cơ chế xác thực các đối tượng tham gia truyền thông vì thế phương pháp này không có khả năng chống lại một số dạng tấn công giả mạo trong thực tế. Một số phương pháp đã được phát triển sau đó như ECDH (Elliptic Curve Diffie-Hellman Key Exchange), MQV (Menezes-Qu-Vanstone Protocol), ECMQV (Elliptic Curve Menezes-Qu- Vanstone Protocol)... đã được ứng dụng phổ biến trong thực tế. Tuy nhiên, việc phát triển các phương pháp mới để ứng dụng trong thực tế vẫn luôn là yêu cầu cần thiết được đặt ra. Bài báo đề xuất 2 phương pháp cho phép bảo đảm đồng thời việc thiết lập khóa cho các hệ mật mã khóa bí mật và xác thực các đối tượng tham gia truyền thông, vì thế sẽ chống được các kiểu tấn công giả mạo trong thực tế. II. XÂY DỰNG GIAO THỨC XÁC LẬP KHÓA Giao thức xác lập khóa được đề xuất ở đây bao gồm 2 thuật toán: thuật toán thỏa thuận khóa xây dựng trên cơ sở bài toán logarit rời rạc trong trường hữu hạn nguyên tố và thuật toán chuyển khóa, mà thực chất là một thuật toán mật mã khóa công khai được phát triển từ thuật toán thỏa thuận khóa thứ nhất. Cả 2 thuật toán này đều sử dụng chung một thuật toán hình thành các tham số hệ thống và khóa. 1. Thuật toán hình thành các tham số hệ thống và khóa công khai 1- Chọn một số nguyên tố lớn p và phần tử sinh g của nhóm sao cho bài toán logarit rời rạc trong là khó giải. * pZ * pZ 2- Chọn khóa riêng (x) là một số nguyên thỏa mãn: px <<1 . 3- Khóa công khai tương ứng (y) được tính theo công thức: Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số x (2x), tháng x/201x ( ) pgy x mod= 4- Chứng nhận và công khai y bởi một Cơ quan chứng thực – CA (Certificate Authority) đáng tin cậy. 2. Thuật toán thỏa thuận khóa 2.1 Mô tả thuật toán Các đối tượng tham gia trao đổi thông tin mật cùng thống nhất chọn các tham số p và g, chọn khóa riêng và tính khóa công khai của mình theo Thuật toán hình thành các tham số hệ thống và khóa công khai ở Mục 1. Giả sử đối tượng gửi/mã hóa thông tin ký hiệu là A có khóa riêng là xA, khóa công khai tương ứng của A là yA; Đối tượng nhận/giải mã thông tin ký hiệu là B có khóa riêng là xB và khóa công khai là yB. Các đối tượng A và B thống nhất sử dụng một thuật toán mật mã khóa bí mật (ví dụ: DES, AES,...) để mã hóa thông tin (bản tin, thông báo, tài liệu,...) cần trao đổi với nhau, khi đó phương pháp để thiết lập một khóa bí mật chung cho phép A mã hóa thông tin và B giải mã thông tin, bao gồm các bước thực hiện như sau: Bước 1: + Đối tượng A thực hiện các bước: 1- Chọn ngẫu nhiên một giá trị kA thỏa mãn: . pk A <<1 2- Hình thành thông tin thỏa thuận khóa RA theo công thức: ( ) pgR AkA mod= 3- Gửi giá trị RA cho đối tượng B. + Đối tượng B thực hiện các bước: 1- Chọn ngẫu nhiên một giá trị kB thỏa mãn: pkB <<1 . 2- Hình thành thông tin thỏa thuận khóa RB theo công thức: ( ) pgR BkB mod= 3- Gửi giá trị RB cho đối tượng A. Bước 2: 1- Đối tượng A hình thành khóa mã hóa theo công thức: ( ) ( ) pyRK AA xBkBA mod×= 2- Đối tượng B hình thành khóa giải mã theo công thức: ( ) ( ) pyRK BB xAkAB mod×= 2.2 Tính đúng đắn của thuật toán mới đề xuất Điều cần chứng minh ở đây là: cho p là số nguyên tố, g là phần tử sinh của nhóm , ∗pZ pxx BA << ,1 , , ( ) pgy AxA mod= ( ) pgy BxB mod= , pk A <<1 , ( ) pgR AkA mod= , pkB <<1 , ( ) pgR BkB mod= . Nếu: ( ) ( ) pyRK AA xBkBA mod×= , ( ) ( ) pyRK BB xAkAB mod×= thì: . BA KK = Chứng minh: Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/201x Thật vậy, do: = ( ) ( ) ( ) ( ) pgg ppgpg pyRK BABA ABAB AA xxkk xxkk x B k BA mod modmodmod mod .. ×= × ×= Mặt khác, do: ( ) ( ) ( ) ( ) pgg ppgpg pyRK BABA BABA BB xxkk xxkk x A k AB mod modmodmod mod .. ×= ×= ×= Từ đây suy ra: . BA KK = Đây là điều cần chứng minh. 2.3 Mức độ an toàn của thuật toán mới đề xuất Mức độ an toàn của thuật toán mới đề xuất được đánh giá qua các khả năng như sau: a) Chống tấn công làm lộ khóa bí mật Từ: ( ) ( ) pyRK AA xBkBA mod×= và: cho thấy, có thể tính được khóa bí mật dùng chung cho các bên tham gia truyền thông nếu biết được k ( ) ( ) pyRK BB xAkAB mod×= A và xA hoặc: kB và xB. Các giá trị này có thể tính được nhờ việc giải: (1) ( ) pgR AkA mod= và: (2) ( ) pgy AxA mod= Hoặc: (3) ( ) pgR BkB mod= và: ( ) pgy BxB mod= (4) Việc giải (1) và (2) hay (3) và (4) thực chất là giải bài toán logarit rời rạc trong trường hữu hạn nguyên tố . ∗pZ Như vậy, khả năng chống tấn công làm lộ khóa bí mật dùng chung của thuật toán mới đề xuất phụ thuộc vào mức độ khó của bài toán logarit rời rạc. b) Khả năng chống giả mạo về nguồn gốc khóa bí mật Để mạo danh A, kẻ giả mạo cần phải tính được khóa riêng (xA) của A. Việc tính xA có thể thực hiện bằng cách giải (2). Tương tự, cũng có thể mạo danh B nếu tính được xB nhờ việc giải (4). Như đã chỉ ra, việc giải (2) và (4) thực chất là giải bài toán logarit rời rạc. Những phân tích trên cho thấy khả năng chống giả mạo nguồn gốc của khóa bí mật dùng chung phụ thuộc vào mức độ khó của bài toán logarit rời rạc. c) Tính bí mật về phía trước đối với A Việc biết khóa riêng dài hạn của A sau một quá trình thỏa thuận khóa không cho phép kẻ tấn công tính lại được các khóa bí mật dùng chung do thuật toán tạo đã ra trước đó. d) Tính bí mật về phía trước riêng biệt đối với cả A và B Nếu biết khóa riêng dài hạn của A hoặc biết khóa riêng dài hạn của B sau một quá trình thỏa Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số x (2x), tháng x/201x thuận khóa, kẻ tấn công cũng không thể tính lại được các khóa bí mật dùng chung do thuật toán tạo đã ra trước đó. e) Tính bí mật về phía trước tương hỗ Khi biết cả khóa riêng dài hạn của A và B sau một quá trình thỏa thuận khóa thì kẻ tấn công cũng không thể tính lại được các khóa bí mật dùng chung do thuật toán tạo đã ra trước đó. 2.4 Thuật toán thỏa thuận khóa mở rộng Thuật toán thỏa thuận khóa mở rộng (thuật toán mở rộng) được đề xuất cho các trường hợp mà ở đó có số đối tượng tham gia thỏa thuận khóa lớn hơn 2. Xét trường hợp số đối tượng là 3, với các trường hợp có số đối tượng tham gia thỏa thuận khóa lớn hơn 3 cũng có thể thực hiện hoàn toàn tương tự giá sử các đối tượng cần thỏa thuận khóa bí mật chung là A, B và C, các đối tượng này có khóa riêng tương ứng là xA, xB, xC và các khóa công khai tương ứng là yA, yB, yC. Các đối tượng thỏa thuận một khóa bí mật chung qua các bước như sau: Bước 1: 1- A chọn một giá trị kA thỏa mãn: pk A <<1 và tính giá trị RA và SA theo công thức: và rồi gửi cho B. ( ) pgR AkA mod= ( ) pyS AxCA mod= 2- B chọn một giá trị kB thỏa mãn: pkB <<1 và tính giá trị RB và SB theo công thức: ( ) pgR BkB mod= và rồi gửi cho C. ( ) pyS AxBB mod= 3- C chọn một giá trị kC thỏa mãn: pkC <<1 và tính giá trị RC và SC theo công thức: ( ) pgR CkC mod= và rồi gửi cho A. ( ) pyS CxBC mod= Bước 2: 1- A tính giá trị RAC theo công thức: ( ) pRR AkCAC mod= , rồi gửi cho B. 2- B tính giá trị RB theo công thức: ( ) pRR BkAAB mod= , rồi gửi cho C. 3- C tính giá trị RBC theo công thức: ( ) pRR CkBBC mod= , rồi gửi cho A. Bước 3: 1- A tính khóa bí mật KA theo công thức: ( ) ( ) pSRK AA xCkBCA mod×= 2- B tính khóa bí mật KB theo công thức: ( ) ( ) pSRK BB xAkACB mod×= 3- C tính khóa bí mật KC theo công thức: ( ) ( ) pSRK CC xBkABC mod×= Tính đúng đắn của thuật toán thỏa thuận khóa mở rộng được đề xuất có thể chứng minh như sau: Điều cần chứng minh ở đây là: CBA KKK == . Thật vậy, ta có: Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/201x ( ) ( ) ( )( ) ( )( ) ( ) ( ) ( ) ( ) pgg ppgpg ppypR pSRK CBACBA CaBCAB ACAC AA xxxkkk xxxkkk xx B kk B x C k BCA mod modmodmod modmodmod mod .... .. ×= ×= ×= ×= Tương tự, ta cũng có: ( ) ( ) ( )( ) ( )( ) ( ) ( ) ( ) pg ppgpg ppypR pSRK CBA CBACBAC BABA BB kkk xxxxkkk xx C kk C x A k ACB mod modmodmod modmodmod mod .. ... = ×= ×= ×= Và: ( ) ( ) ( )( ) ( )( ) ( ) ( ) ( ) ( ) pgg ppgpg ppypR pSRK CBACBA CBACBA CBCB CC xxxkkk xxxkkk xx A kk A x B k ABC mod modmodmod modmodmod mod .... .. ×= ×= ×= ×= Từ đây suy ra: . CBA KKK == Mức độ an toàn của thuật toán mở rộng có thể phân tích đánh giá tương tự như với thuật toán thỏa thuận khóa đã đề xuất ở Mục 2.3. 3. Thuật toán chuyển khóa 3.1 Mô tả thuật toán Ở đây cũng giả thiết rằng, các đối tượng tham gia trao đổi thông tin A và B cùng thống nhất sử dụng một thuật toán mật mã khóa bí mật (ví dụ: DES, AES,...) để mã hóa thông tin (bản tin, thông báo, tài liệu,...) cần trao đổi với nhau. Các đối tượng A và B lựa chọn các tham số dùng chung p và g, chọn khóa riêng và tính khóa công khai của mình theo Thuật toán hình thành các tham số hệ thống và khóa công khai ở Mục 1. Giả sử đối tượng A có khóa riêng là xA, khóa công khai tương ứng của A là yA; Đối tượng B có khóa riêng là xB và khóa công khai là yB. Giả sử rằng, đối tượng A chọn khóa bí mật cho việc mã hóa và giải mã thông tin là K, với: pK <<1 và gửi cho đối tượng B, quá trình thực hiện bao gồm các bước như sau: Bước 1: Đối tượng B thực hiện: 1- Chọn ngẫu nhiên một giá trị kB thỏa mãn: pkB <<1 . 2- Tính giá tri RB theo công thức: ( ) pgR BkB mod= 3- Gửi giá trị RB cho đối tượng A. Bước 2: Đối tượng A thực hiện: 1- Chọn ngẫu nhiên một giá trị kA thỏa mãn: pk A <<1 . 2- Tính giá trị C theo công thức: ( ) ( ) pyRKC AA xBkB mod××= 3- Tính giá trị R theo công thức: ( ) pgR Ak mod= 4- Gửi bản mã (C,R) cho đối tượng B. Bước 3: Từ bản mã (C,R) nhận được, đối tượng B thực hiện việc giải mã (C,R) để nhận khóa bí mật (K) theo công thức sau: Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số x (2x), tháng x/201x ( ) ( ) pyRCK BB xAk mod−− ××= 3.2 Tính đúng đắn của thuật toán mới đề xuất Điều cần chứng minh ở đây là: cho p là số nguyên tố, g là phần tử sinh của nhóm , ∗pZ pxx BA << ,1 , , ( ) pgy AxA mod= ( ) pgy BxB mod= , pkk BA << ,1 , ( ) pgR BkB mod= , pK <<1 , ( ) ( ) pyRKC AA xBkB mod××= , ( ) pgR Ak mod= . Nếu: ( ) ( ) pyRCK BB xAk mod−− ××= thì: KK = . Chứng minh: Thật vậy, do: ( ) pgR Ak mod= Nên: ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( )( ) ( ) ( ) =×× ××= = ×××= ××= −− − − −− pgpg ppgpgK ppg pgpyRK pyRCK ABBA ABAB BA BAAA BB xxkk xxkk xx kkx B k B x A k modmod modmodmod modmod modmod mod .. × ( ) ( ) K pggggK ppgg pggK ABBABAAB ABBA BAAB xxkkxxkk xxkk xxkk = ××××= =×× ×××= −− −− mod modmod mod .... .. .. 3.3 Mức độ an toàn của thuật toán mới đề xuất Tương tự thuật toán thỏa thuận khóa ở Mục 2, mức độ an toàn của thuật toán chuyển khóa mới đề xuất cũng được đánh giá qua các khả năng như sau: a) Chống tấn công làm lộ khóa bí mật Từ: ( ) ( ) pyRKC AA xBkB mod××= và: ( ) ( ) pyRCK BB xAk mod−− ××= cho thấy, có thể tính được khóa bí mật dùng chung cho các bên tham gia truyền thông nếu biết được kA và xA hoặc kB và xB . Các giá trị này có thể tính được nhờ việc giải: ( ) pgy AxA mod= (5) và: ( ) pgR Ak mod= (6) Hoặc: ( ) pgy BxB mod= (7) và: ( ) pgR BkB mod= (8) Như đã chỉ ra ở Mục 2.3.a, khả năng chống tấn công làm lộ khóa bí mật dùng chung của thuật toán mới đề xuất ở đây cũng phụ thuộc vào mức độ khó của bài toán logarit rời rạc. b) Khả năng chống giả mạo về nguồn gốc khóa bí mật Để mạo danh A, kẻ giả mạo cần phải tính được khóa riêng (xA) của A. Việc tính xA có thể thực hiện bằng cách giải (5). Tương tự, cũng có thể mạo danh B nếu tính được xB nhờ việc giải (7). Như vậy, khả năng chống giả mạo nguồn gốc của khóa Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/201x bí mật dùng chung (K) cũng phụ thuộc vào mức độ khó của bài toán logarit rời rạc. 3.4 Thuật toán chuyển khóa mở rộng Thuật toán chuyển khóa mở rộng (thuật toán mở rộng) được đề xuất cho các trường hợp mà ở đó có số đối tượng lớn hơn 2. Xét trường hợp số đối tượng là 3, với các trường hợp có số đối tượng tham gia thỏa thuận khóa lớn hơn 3 cũng có thể thực hiện hoàn toàn tương tự. giá sử các đối tượng cần thỏa thuận khóa bí mật chung là A, B và C, có các khóa riêng là xA, xB, xC và các khóa công khai tương ứng là yA, yB, yC. Giả sử đối tượng A tạo trước một khóa bí mật dùng chung K với: và chuyển cho các đối tượng B và C, thuật toán bao gồm các bước như sau: pK <<1 Bước 1: 1- A chọn một giá trị kA thỏa mãn: pk A <<1 và tính giá trị RA và SA theo công thức: và rồi gửi cho B. ( ) pgR AkA mod= ( ) pyS AxCA mod= 2- B chọn một giá trị kB thỏa mãn: pkB <<1 và tính giá trị RB và SB theo công thức: và rồi gửi cho C. ( ) pgR BkB mod= ( ) pyS BxAB mod= 3- C chọn một giá trị kC thỏa mãn: pkC <<1 và tính giá trị RC và SC theo công thức: ( ) pgR CkC mod= và rồi gửi cho A. ( ) pyS CxBC mod= Bước 2: 1- A tính giá trị RAC theo công thức: ( ) pRR AkCAC mod= , rồi gửi cho B. 2- B tính giá trị RB theo công thức: ( ) pRR BkAAB mod= , rồi gửi cho C. 3- C tính giá trị RBC theo công thức: ( ) pRR CkBBC mod= , rồi gửi cho A. Bước 3: 1- A mã hóa khóa bí mật KA theo công thức: ( ) ( ) pSRKC AA xCkBCAK mod××= , rồi gửi cho B và C. 2- B giải mã CK để nhận khóa bí mật KA theo công thức: ( ) ( ) pSRCK BAB xkACKB mod−− ××= 3- C giải mã CK để nhận khóa bí mật KA theo công thức: ( ) ( ) pSRCK CC xBkABKC mod−− ××= Có thể dễ dàng thấy rằng: ACB KKK == Thật vậy, ta có: ( ) ( ) ( ) ( )( ) ( ) ( ) ( )( ) ( )( )( ) ( )( ) ( )( ) =×× ××= =× ×××= ××= −− − − −− BABA ACAC B BAA BB xx C kk C xx B kk BA x A k AC x C k BCA x A k ACKB pypR ppypRK pS RpSRK pSRCK modmod modmodmod mod mod mod Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số x (2x), tháng x/201x ( ) ( )( ) ( ) ( ) ( ) ( )( ( ) ( )( ) ( ) ( ) ( ) Axxxkkk xxxkkk A xxxkkk xxxkkk A xxxkkk xxxkkk A Kpg gK ppgg pggK ppgpg ppgpgK CBACBA CBACBA CBACBA CBACBA BACBAC CABCAB =× ××= ×× ×××= ×× ××= +− + −− −− mod modmod mod modmodmod modmodmod .... .... .... .... .. .. ) ) Tương tự, ta cũng có: ( ) ( ) ( ) ( )( ) ( ) ( ) ( )( ) ( )( )( ( )( ) ( )( ) ( ) ( )( ) ( ) ( ) ( )( )( ) ( ) ( )( ) ( )( ) ( ) ( ) Axxxkkk xxxkkk A xxxkkk xxxkkk A xxxkkk xxxkkk A xx A kk A xx B kk BA x B k AB x C k BCA x B k ABKC Kpg gK ppg pgK ppgpg ppgpgK ppypR ppypRK pS RpSRK pSRCK CBACBA CBACBA CBACBA CBACBA CBACBA CABCAB CBCB ACAC C CAA CC =× ××= × ××= =×× ××= =×× ××= =× ×××= ××= +− + +− + −− −− − − −− mod modmod mod modmodmod modmodmod modmodmod modmodmod mod mod mod .... .... .... .... .. .. Từ đây suy ra: . CBA KKK == Mức độ an toàn của thuật toán mở rộng có thể phân tích đánh giá tương tự như với thuật toán chuyển khóa đã đề xuất ở Mục 3.3. III. KẾT LUẬN Bài báo đề xuất giao thức xác lập khóa cho các hệ mật mã khóa bí mật, bao gồm một thuật toán thỏa thuận khóa và một thuật toán chuyển khóa. Các thuật toán mới đề xuất có những đặc điểm cơ bản như sau: - Mức độ an toàn của thuật toán phụ thuộc vào tính khó giải của bài toán logarit rời rạc trong trường hữu hạn nguyên tố. - Khóa mật dùng chung được xác thực về nguồn gốc, nên thuật toán mới đề xuất có khả năng chống lại các dạng tấn công giả mạo. - Khi bị lộ khóa riêng dài hạn (xA,xB) của các đối tượng tham gia thỏa thuận khóa (A,B) thì kẻ tấn công cũng không tính được khóa bí mật dùng chung (K) do thuật toán đã tạo ra trước đó. - Có thể mở rộng thuật toán cho các trường hợp có số lượng các đối tượng tham gia thỏa thuận khóa lớn hơn 2. Chứng minh về tính đúng đắn và những đánh giá về mức độ an toàn của thuật toán mới đề xuất đã cho thấy khả năng ứng dụng của nó trong thực tế. TÀI LIỆU THAM KHẢO. [1] W. Diffie & M. Hellman, New Directions in Cryptography, IEEE Trans. On Info. Theory, IT-22(6):644-654, 1976. [2] William Stallings, Cryptography and Network Security Principles and Practices, Fourth Edition, Prentice Hall PTR, p. 592, 2005. [3] D.R Stinson, Cryptography: Theory and Practice, CRC Press 1995 Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/201x _______________________________________ SƠ LƯỢC VỀ TÁC GIẢ LƯU HỒNG DŨNG. Sinh năm 1966. Tốt nghiệp đại học ngành Vô tuyến Điện tử tại Học viện Kỹ thuật Quân sự năm 1989. Hiện đang công tác tại khoa CNTT- Học viện KTQS. Hướng nghiên cứu: An toàn và bảo mật thông tin. Email: luuhongdung@gmail.com.