Tài liệu Phát triển và xây dựng tham số an toàn cho hệ chữ kí số trên bài toán logarit rời rạc theo modul hợp số

i LỜI CAM ĐOAN Tôi xin cam đoan rằng luận án tiến sĩ là công trình khoa học của riêng tôi. Kết quả nghiên cứu là trung thực, khách quan và chưa từng được công bố trong bất kỳ công trình khoa học nào của người khác. Tôi xin cam đoan rằng mọi thông tin, luận cứ, luận chứng mà luận án đã trích dẫn đều được chỉ rõ địa chỉ nguồn gốc. Hà Nội, ngày 10 tháng 10 năm 2019 Tác giả Lê Văn Tuấn ii LỜI CẢM ƠN Trong quá trình thực hiện luận án “Phát triển và xây dựng tham số an toàn cho hệ chữ ký số trên bài toán logarit rời rạc theo modul hợp số” tôi đã nhận được sự giúp đỡ của Đảng ủy, ban Giám đốc Học viện Kỹ thuật Quân sự; sự quan tâm, giúp đỡ của Đảng ủy, ban Giám đốc Học viện Khoa học Quân sự; sự giúp đỡ của tập thể cùng ban lãnh đạo Phòng Sau Đại học Học viện Kỹ thuật Quân sự; sự giúp đỡ của tập thể giảng viên Khoa CNTT Học viện Kỹ thuật Quân sự, nơi tôi sinh hoạt học thuật. Tôi xin chân thành cảm ơn sự giúp đỡ quý báu đó. Tôi xin chân thành cảm ơn TS. Lều Đức Tân và TS. Bùi Thế Truyền, đã hướng dẫn tôi về chuyên môn và phương pháp nghiên cứu trong suốt quá trình thực hiện đề tài luận án. Tôi xin chân thành cảm ơn sự giúp đỡ của các bạn bè, đồng nghiệp đang học tập và công tác tại Học viện Khoa học Quân sự và Học viện Kỹ thuật Quân sự; đặc biệt là sự động viên, giúp đỡ của gia đình, người thân để tôi hoàn thành luận án này. Tác giả iii MỤC LỤC LỜI CAM ĐOAN ............................................................................................. i LỜI CẢM ƠN .................................................................................................. ii MỤC LỤC ....................................................................................................... iii DANH MỤC CÁC KÝ HIỆU......................................................................... v BẢNG CHỮ VIẾT TẮT ................................................................................ vi DANH MỤC CÁC BẢNG ............................................................................ vii DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ..................................................... viii MỞ ĐẦU .......................................................................................................... 9 CHƯƠNG 1. TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨU VÀ CƠ SỞ LÝ THUYẾT CỦA LUẬN ÁN ........................................................................... 18 1.1. Tổng quan và vấn đề nghiên cứu của luận án. ................................. 18 1.1.1. Tổng quan. ...................................................................................... 18 1.1.2 Một số lược đồ chữ ký số trên trường ℤp. ....................................... 19 1.1.3. Một số lược đồ chữ ký số trên vành ℤn. ......................................... 20 1.1.4. Vấn đề nghiên cứu của luận án. ...................................................... 22 1.2. Cơ sở lý thuyết liên quan đến luận án............................................... 24 1.2.1. Một số định nghĩa và định lý quan trọng ........................................ 24 1.2.2. Thuật toán và độ phức tạp của thuật toán. ...................................... 26 1.2.3. Lược đồ chữ ký số khóa công khai. ................................................ 32 1.2.4. Lược đồ chữ ký số trên trường ℤp .................................................. 36 1.2.5. Lược đồ chữ ký số trên vành ℤn. .................................................... 43 1.2.6. Ngưỡng an toàn và chuẩn tham số an toàn. .................................... 47 1.3. Kết luận ................................................................................................ 50 CHƯƠNG 2. PHÁT TRIỂN LƯỢC ĐỒ CHỮ KÝ SỐ TRÊN VÀNH .... 51 2.1. Mở đầu ................................................................................................. 51 2.2. Một số kiến thức bổ trợ ...................................................................... 51 2.3. Xây dựng lược đồ chữ ký số cơ sở ..................................................... 55 2.3.1. Đặt vấn đề ....................................................................................... 55 2.3.2. Xây dựng công thức tổng quát ........................................................ 56 2.4. Đề xuất lược đồ chữ ký số trên vành ℤn ........................................... 65 2.4.1. Lược đồ chữ ký số dạng 1............................................................... 65 2.4.2. Lược đồ chữ ký số dạng 2............................................................... 68 2.4.3. Phân tích các lược đồ chữ ký đề xuất ............................................. 70 2.4.4. Một số so sánh và điều kiện an toàn cho lược đồ đề xuất .............. 75 2.5. Xây dựng hệ tham số cho lược đồ...................................................... 79 2.5.1. Số Modulo....................................................................................... 80 2.5.2. Xác định phần tử sinh ..................................................................... 80 2.5.3. Xác định thành phần bí mật và công khai ...................................... 85 2.5.4. Hệ tham số của lược đồ .................................................................. 85 iv 2.6. Thử nghiệm và đánh giá kết quả ....................................................... 85 2.6.1. Chuẩn bị thử nghiệm....................................................................... 85 2.6.2. Tiến hành thử nghiệm ..................................................................... 87 2.6.3. Đánh giá kết quả ............................................................................. 91 2.7. Kết luận ................................................................................................ 93 CHƯƠNG 3. XÂY DỰNG THAM SỐ AN TOÀN CHO CÁC LƯỢC ĐỒ CHỮ KÝ SỐ ĐỀ XUẤT ............................................................................... 94 3.1. Mở đầu ................................................................................................. 94 3.2. Ngưỡng an toàn ................................................................................... 95 3.2.1. Ngưỡng an toàn của Lenstra và Verheul ........................................ 95 3.2.2. Ngưỡng an toàn của lược đồ chữ ký số đề xuất ............................. 97 3.3. Xây dựng hệ tiêu chuẩn tham số an toàn........................................ 102 3.3.1. Ý tưởng ......................................................................................... 102 3.3.2. Xây dựng hệ tiêu chuẩn cho tham số ............................................ 103 3.4. Sinh tham số cho các lược đồ chữ ký số đề xuất ............................ 108 3.4.1. Thuật toán ..................................................................................... 108 3.4.2. Chương trình ................................................................................. 122 3.5. Thử nghiệm và đánh giá kết quả ..................................................... 123 3.5.1. Thử nghiệm ................................................................................... 123 3.5.2. Đánh giá kết quả ........................................................................... 134 3.6. Kết luận .............................................................................................. 136 KẾT LUẬN VÀ ĐỀ XUẤT ........................................................................ 137 I. KẾT LUẬN ........................................................................................... 137 1. Về lý thuyết ........................................................................................... 137 2. Về thực nghiệm..................................................................................... 138 II. ĐỀ XUẤT VÀ HƯỚNG NGHIÊN CỨU .......................................... 138 1. Đề xuất: ................................................................................................. 138 2. Hướng nghiên cứu: .............................................................................. 139 DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ ................................ 140 TÀI LIỆU THAM KHẢO .......................................................................... 141 PHỤ LỤC ..................................................................................................... 146 v DANH MỤC CÁC KÝ HIỆU Các tập hợp số: ℕ tập số tự nhiên. ℤ Tập số nguyên. R Tập số thực. P Tập các số nguyên tố. Ký hiệu lấy phần nguyên: Cho số thực 𝑥: ⌈x⌉: số nguyên m nhỏ nhất sao cho m ≥ x. ⌊x⌋: số nguyên m lớn nhất sao cho m ≤ x. Ký hiệu liên quan đến lý thuyết chia hết: a.b: số a nhân với số b. a|b: a là ước của b, ngược lại b là bội của a. GCD(a, b): ước số chung lớn nhất của a và b. LMC(a, b): bội số chung nhỏ nhất của a và b. Số nguyên tố bổ trợ: Cho 𝑝, 𝑞 là số nguyên tố. p1 : ước nguyên tố lớn nhất của p – 1 p2 : ước nguyên tố lớn nhất của p + 1 q1 : ước nguyên tố lớn nhất của q − 1 q2 : ước nguyên tố lớn nhất của q + 1 Một số ký hiệu khác: DLPp : Bài toán logarit rời rạc trên trường ℤp DLPn : Bài toán logarit rời rạc trên vành ℤn k∈R X: Lẫy ngẫu nhiên phần tử k thuộc tập X x || y: Ký kiệu nối chuỗi x với chuỗi y. Secure_strength: Ký hiệu ngưỡng an toàn cho một hệ mật L(a): Kích thước của số nguyên a tính theo đơn vị bít Ordn (g): Cấp của g trong vành ℤn TLKTTB : Thực lực kinh tế của tổ chức tình báo TLTTSMT : Thực lực tính toán của siêu máy tính vi BẢNG CHỮ VIẾT TẮT Các chữ viết tắt Ý nghĩa AN-QP Quốc phòng - An ninh CPLT Chi phí lý thuyết CPTT Chi phí thực tế KT-XH Kinh tế - Xã hội SMT Siêu máy tính TCVN Tiêu chuẩn Việt Nam TLTT Thực lực tính toán AL Attack Class. BO Bit Operator CRT Chinese Remainder Theorem DLP Dicrete Logarithms Problem DP Dificult Problem DSA Digital Signature Algorithm ECM Elliptic Curve Method FIPS Federal Information Processing Standards FP Factorization Problem GCD Great Common Division HP Hard Problem IMY Infeasible number of Mips Years LCM Least comom Multiple NFS Number Field Sieve NIST National Institute of Standards and Technology RSA Ron Rivest, Adi Shamir và Len Adleman vii DANH MỤC CÁC BẢNG Bảng 1.1. Thống kê độ phức tạp một số phép toán .................................... 28 Bảng 1.2. Kết quả chi phí tính toán ............................................................. 43 Bảng 1.3. Độ dài số modulo n và thời gian sống. ........................................ 49 Bảng 1.4. Một số tiêu chuẩn tham số an toàn trong FIPS ......................... 49 Bảng 1.5. Tiêu chuẩn tham số lược đồ TCVN 7635-2007. ........................ 50 Bảng 2.1. Bảng thống kê kết quả phân tích lược đồ đề xuất ..................... 73 Bảng 2.2. Thời gian sinh chữ ký và xác nhận chữ ký ................................ 91 Bảng 3.1. Ngân quỹ dành cho một số tổ chức tình báo của Mỹ................ 98 Bảng 3.2. Một số tiêu chuẩn cập nhật năm 2019 ...................................... 107 Bảng 3.3. Ngưỡng an toàn tính theo Lenstra và Verheul ........................ 125 Bảng 3.4. Ngưỡng an toàn trong môi trường KT-XH ............................. 126 Bảng 3.5. Ngưỡng an toàn trong lĩnh vưc AN-QP ................................... 127 Bảng 3.6. Thời gian sinh tham số............................................................... 134 viii DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 2.1. Biểu đồ kết quả thử nghiệm sinh chữ ký .................................... 92 Hình 2.2. Biểu đồ kết quả thử nghiệm xác nhận chữ ký ........................... 92 Hình 3.1. Đồ thị so sánh ngưỡng an toàn .................................................. 128 Hình 3.2. Biểu đồ ngưỡng an toàn ............................................................. 128 9 MỞ ĐẦU 1. Lý do chọn đề tài Lịch sử nhân loại đang chứng kiến cuộc cách mạng công nghiệp lần thứ tư (còn gọi là cuộc cách mạng công nghệ 4.0), cuộc cách mạng này đã và đang tạo ra những khả năng hoàn toàn mới, tác động sâu sắc đến mọi mặt, mọi lĩnh vực của đời sống xã hội. Ở Việt nam, cuộc cách mạng công nghệ 4.0 đã mang đến vô số cơ hội, đồng thời cũng phải đối mặt không ít thách thức, khó khăn, đặc biệt là vấn đề an toàn và bảo mật thông tin trên không gian mạng. Nhờ đặc tính xử lý nhanh, chính xác, phạm vi rộng và khả năng lưu trữ lớn, nên các dịch vụ điện tử mang lại những lợi ích to lớn, góp phần không nhỏ vào sự phát triển xã hội loài người trong vài thập niên qua. Tuy nhiên, bên cạnh những mặt tích cực của các dịch vụ điện tử đem lại, nguy cơ mất an toàn thông tin là rất cao. Minh chứng bằng những cuộc tấn công mạng từng xuất hiện trong thời gian gần đây, đó là vụ tấn công mạng bởi mã độc NotPetya vào sáng 27/6/2017[54] và nhiều cuộc tấn công khác vào các webside hàng loạt các tập đoàn kinh tế hàng đầu của Mỹ trong năm 2018 đã gây thiệt hại hàng tỷ USD. Ở Việt nam, những vụ mất an toàn thông tin nghiêm trọng đã xảy ra trong thời gian qua, tiêu biểu là vụ tấn công mạng của hãng Hàng không Quốc gia Việt nam vào ngày 29/7/2016[55] và nhiều cuộc tấn công mạng khác [55], [56], [58]. Theo thông tin từ [56], tính riêng năm 2018, thiệt hại do virus máy tính gây ra đối với người dùng Việt Nam đã lên mức kỷ lục 14.900 tỷ đồng, tương đương 642 triệu USD, nhiều hơn 21% so với mức thiệt hại của năm 2017. Vậy an toàn thông tin cho các dịch vụ điện tử không còn là vấn đề riêng của mỗi tổ chức, quốc gia mà đã trở thành vấn đề chung của toàn thế giới. Trước bối cảnh đó, đã có nhiều giải pháp là kết quả nghiên cứu của các nhà khoa học được ứng dụng trong lĩnh vững an toàn và bảo mật thông tin, tiêu biểu là sự phát minh ra mật mã khóa công khai của hai tác giả W. Diffie và M. Hellman đã tạo bước ngoặt lớn trong ngành mật mã nói chung và trong lĩnh 10 vực an toàn và bảo mật thông tin nói riêng. Nhờ sự phát minh vĩ đại này của W. Diffie và M. Hellman, hàng loạt các dịch vụ an toàn, bảo mật thông tin được ra đời, tiêu biểu là các dịch vụ xác thực sử dụng chữ ký số. Chữ ký số là một dạng chữ ký điện tử, có chức năng xác thực, đảm bảo tính toàn vẹn và tính không thể chối bỏ của các bên gửi, nhận tin. Sự ra đời của chữ ký số góp phần xây dựng thành công Chính phủ Điện tử, Thương mại Điện tử và là cơ sở cho sự ra đời của hàng loạt dịch vụ an toàn thông tin khác trên mạng Internet. Những lược đồ chữ ký số tiêu biểu được kể đến, đó là lược đồ chữ ký số RSA[20] có độ an toàn dựa trên tính khó giải của bài toán phân tích số, được ứng dụng rộng rãi trên thế giới trong đó có Việt Nam; lược đồ chữ ký số ElGamal cùng các biến thể có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên trường hữu hạn ℤp được đề cập trong các kết quả nghiên cứu [13], [17], [18], [27-29], [32],[33], [38], [44], [46-52]. Điểm tồn tại chung của lược đồ chữ ký số trên trường hữu hạn ℤp (lược đồ Elgamal và các biến thể của nó) đều công khai cấp của phần tử sinh (chính xác hơn là không thể che giấu cấp phần tử sinh), chính đặc điểm này khiến cho các lược đồ chữ ký này phải đối mặt với hai nguy cơ: nguy cơ thứ nhất là mất an toàn trong tình huống trùng khóa phiên hoặc lộ khóa phiên; nguy cơ thứ hai có khả năng bị tấn công bởi các thuật toán giải bài toán logarit rời rạc dựa vào cấp của phần tử sinh 𝑔 khi tham số của lược đồ chữ ký không đạt tiêu chuẩn an toàn, chẳng hạn tấn công sử dụng thuật toán Rho của Pollard, thuật toán Pohlig Hellman và thuật toán Index calculate. Hơn nữa, tốc độ sinh chữ ký của lược đồ chữ ký trên trường ℤp chậm hơn nhiều tốc độ sinh chữ ký của các lược đồ chữ ký cùng loại trên vành ℤn , do các phép toán có chi phí lớn trong các lược đồ chữ ký là phép lũy thừa, phép tính phần tử nghịch đảo trên vành ℤn sẽ có chi phí nhỏ hơn nhiều trên trường ℤp nhờ áp dụng định lý CRT (được chứng minh trong bổ đề 2.3 của luận án, n = p. q và L(p) =L(q), điều này còn được đề cập trong [10] khi áp dụng định lý CRT cho 11 lược đồ chữ ký RSA). Hơn nữa, các lược đồ chữ ký cùng loại được xây dựng trên cấu trúc vành ℤn tránh được hai nguy cơ tấn công nêu trên nhờ tính chất che giấu cấp phần tử sinh. Trước sự phát triển như vũ bão cuộc cách mạng công nghiệp lần thứ tư, đặc biệt là sự ra đời của các máy tính lượng tử có khả năng tính toán nhanh gấp nhiều lần so với các loại máy tính truyền thống trong tương lai, việc nghiên cứu phát triển các lược đồ chữ ký số trên cấu trúc vành ℤn an toàn và hiệu quả hơn có ý nghĩa khoa học và thực tiễn và nhiều lược đồ chữ ký số được xây dựng trên cấu trúc vành ℤn , được đề xuất bởi các nhà khoa học trong nước và trên thế giới [1], [3], [21], [39], [41]. Kết quả khảo sát một số lược đồ chữ ký số trên vành ℤn đã công bố cho thấy các nhà khoa học mới dừng lại ở việc đề xuất lược đồ chữ ký số mới, chứng minh tính đúng đắn và kết luận tính an toàn của lược đồ dựa trên một hoặc hai bài toán khó nào đó. Khoảng trống về học thuật là chưa xây dựng cơ sở toán học và hệ tiêu chuẩn cho tham số; đa số các lược đồ chữ ký chưa được khuyến cáo cho người sử dụng nên sử dụng hệ tiêu chuẩn tham số đã có của thế giới; một số lược đồ chữ ký định lượng độ lớn cấp của phần tử sinh là số 256 bit mà không đưa ra lý giải tại sao, hơn nữa với độ lớn của cấp 256 bit, các lược đồ chữ ký này không thể sử dụng được hàm băm SHA 512, dẫn đến độ an toàn của nó bị hạn chế; cấp của phần tử sinh trong một số lược đồ chữ ký được định lượng về độ lớn xấp xỉ với độ lớn của số modulo [39] dẫn đến chi phí tính toán cao. Hơn nữa, lược đồ chữ ký trong [39] chọn số modulo 𝑛 được cấu tạo bởi số nguyên tố 𝑝, 𝑞 siêu mạnh (n = p. q), điều này sẽ không thực tế với các lược đồ chữ ký số trên vành ℤn đều đòi hỏi tham số phân biệt với từng người sử dụng(chống tấn công sử dụng số modulo chung), trên thực tế mật độ số nguyên tố siêu mạnh rất thưa. Có thể nói rằng những tồn tại nêu trên các lược đồ đã công bố là khoảng trống về học thuật cần giải quyết trong luận án này. Chính vì thế, NCS đã chọn đề tài “Phát triển và xây dựng tham số an toàn cho hệ chữ ký số trên bài toán logarit rời rạc theo modul hợp số” làm luận án tiến sĩ của 12 mình với mong muốn đóng góp một phần nhỏ vào sự phát triển Khoa học Công nghệ trong lĩnh vực an toàn và bảo mật thông tin nói chung và trong phát triển các lược đồ chữ ký số nói riêng. Kết quả nghiên cứu đã đề xuất được bốn lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên vành hữu hạn ℤn , đồng thời luận án đã định lượng được các tham số của lược đồ thông qua hệ tiêu chuẩn tham số và đề xuất hai môi trường ứng dụng là môi trường TK-XH và lĩnh vực AN-QP làm cơ sở tham khảo cho các tổ chức hoặc cá nhân khi đánh giá độ an toàn hoặc có ý định ứng dụng các lược đồ chữ ký số này vào thực tiễn. 2. Mục tiêu nghiên cứu - Nghiên cứu, phát triển lược đồ chữ ký số mới có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên vành hữu hạn ℤn an toàn và hiệu quả hơn một số lược đồ chữ ký số cùng loại được công bố trước đó. - Nghiên cứu xây dựng công thức tính ngưỡng an toàn, hệ tiêu chuẩn tham số an toàn và đề xuất môi trường ứng dụng cho các lược đồ chữ ký đề xuất; - Xây dựng công cụ thử nghiệm sinh tham số, sinh chữ ký và xác nhận chữ ký cho các lược đồ đề xuất thỏa mãn hệ tiêu chuẩn đã đưa ra. 3. Đối tượng nghiên cứu Đối tượng nghiên cứu của luận án gồm: - Lược đồ chữ ký số. - Tham số của lược đồ chữ ký số. - Ngưỡng an toàn và hệ tiêu chuẩn tham số an toàn cho lược đồ chữ ký số. 4. Phạm vi nghiên cứu 4.1. Về lý thuyết - Nghiên cứu lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên trường hữu hạn ℤp , trong đó tập trung vào nghiên 13 cứu kỹ thuật thiết kế lược đồ chữ ký số mà các lược đồ Elgamal và lược đồ DSA đã sử dụng; phân tích, chỉ ra một số điểm tồn tại trên các lược đồ chữ ký số này. - Nghiên cứu lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên vành hữu hạn ℤn với 𝑛 là tích của hai số nguyên tố phân biệt, trong đó tập trung vào nghiên cứu kỹ thuật thiết kế mà các lược đồ chữ ký đã sử dụng; phân tích, chỉ ra những điểm tồn tại trên các lược đồ chữ ký số này. - Nghiên cứu xây dựng lược đồ cơ sở và các lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên vành hữu hạn ℤn che giấu cấp của phần tử sinh. - Nghiên cứu ngưỡng an toàn và hệ tiêu chuẩn tham số an toàn cho lược đồ chữ ký số đề xuất và đề xuất môi trường sử dụng cho nó. - Nghiên cứu, xây dựng thuật toán và chương trình sinh tham số theo hệ tiêu chuẩn cho các lược đồ đề xuất. 4.2. Về thực nghiệm - Kiểm chứng tính đúng đắn, tính đầy đủ, tính hiệu quả của các lược đồ chữ ký số đề xuất; so sánh chi phí tính toán của lược đồ chữ ký đề xuất với lược đồ chữ ký số Elgama và lược đồ DSA. - Kiểm tra tính đúng đắn kết quả tính ngưỡng an toàn theo công thức đã xây dựng. - Kiểm tra tham số được sinh ra theo từng tiêu chuẩn trong hệ tiêu chuẩn. 5. Nội dung nghiên cứu Nội dung nghiên cứu của luận án gồm: - Nghiên cứu kỹ thuật thiết kế lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên trường hữu hạn ℤ𝑝 của các nhà khoa học trong nước và trên thế giới liên quan đến luận án. 14 - Nghiên cứu kỹ thuật thiết kế lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên vành hữu hạn ℤ𝑛 của các nhà khoa học trong nước và trên thế giới liên quan đến luận án. - Chỉ ra những điểm tồn tại trên các lược đồ chữ ký số đã khảo sát và xác định những khoảng trống về học thuật và xác định vấn đề nghiên cứu của luận án; trình bày cơ sở lý thuyết liên quan đến vấn đề nghiên cứu của luận án. - Nghiên cứu xây dựng lược đồ chữ ký số cơ sở có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên vành hữu hạn ℤn , dựa trên các lược đồ cơ sở này nghiên cứu sinh đã phát triển bốn lược đồ chữ ký số trên vành hữu hạn ℤ𝑛 . - Khảo sát phương pháp tính ngưỡng an toàn của thế giới[12] và của một số nhà khoa học Việt Nam[8], [9], từ đó nghiên cứu, xây dựng công thức tính ngưỡng an toàn cho các lược đồ chữ ký số đề xuất. - Khảo sát một số chuẩn tham số của thế giới và của Việt Nam liên quan đến tham số lược đồ chữ ký số trên bài toán phân tích số, bài toán logarit rời rạc; xây dựng hệ tiêu chuẩn tham số cho lược đồ chữ ký số đề xuất có kế thừa một số chuẩn đã có của Việt Nam và phát triển thêm một số tiêu chuẩn riêng cho lược đồ chữ ký số đề xuất. - Nghiên cứu, xây dựng thuật toán sinh tham số theo hệ tiêu chuẩn đã chỉ ra cho các lược đồ chữ ký số đề xuất. - Nghiên cứu, xây dựng chương trình để thử nghiệm việc xác định ngưỡng an toàn, sinh chữ ký, xác nhận chữ ký và sinh tham số cho lược đồ chữ ký số đề xuất theo hệ tiêu chuẩn đã đưa ra. - Thử nghiệm và đánh giá kết quả nghiên cứu. 6. Phương pháp nghiên cứu Các phương pháp nghiên cứu sau đã được kết hợp sử dụng trong quá trình thực hiện đề tài luận án: 15 - Phương pháp lý thuyết: Tiến hành khảo sát, phân tích, tổng hợp và phát triển các kết quả nghiên cứu trong nước và trên thế giới về thiết kế lược đồ chữ ký số hình thành nên lược đồ chữ ký số cơ sở[CT9]; Nghiên cứu cách tiếp cận tính ngưỡng an toàn [8], [9], [12] và hệ tiêu chuẩn tham số an toàn để xây dựng hệ tiêu chuẩn tham số an toàn cho lược đồ chữ ký số đề xuất. - Phương pháp chuyên gia: Xin ý kiến chuyên gia đầu ngành trong lĩnh vực toán học và trong lĩnh vực an toàn thông tin trong thiết kế và xây dựng tiêu chuẩn tham số an toàn cho lược đồ chữ ký số. - Phương pháp thực nghiệm: NCS đã xây dựng công cụ thử nghiệm là phần mềm tin học, sử dụng công cụ đó để kiểm nghiệm các kết quả nghiên cứu lý thuyết; xác định đối tượng, phạm vi, điều kiện và quy trình thử nghiệm. Sau mỗi nội dung thử nghiệm đều tiến hành đánh giá kết quả thử nghiệm, đối chiếu kết quả thử nghiệm với kết quả nghiên cứu lý thuyết. 7. Tính mới trong khoa học của luận án Những đóng góp mới của luận án gồm: - Phát triển được bốn lược đồ chữ ký số mới có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên vành hữu hạn ℤn . - Đề xuất hệ tiêu chuẩn tham số an toàn cho các lược đồ đề xuất; sinh thành công các tham số thỏa mãn hệ tiêu chuẩn; đề xuất hai môi trường KT-XH và AN-QP làm môi trường ứng dụng lược đồ chữ ký số đề xuất. 8. Ý nghĩa khoa học và thực tiễn 8.1. Ý nghĩa khoa học Xây dựng thành công hai lược đồ chữ ký số cơ sở và đề xuất bốn lược đồ chữ ký số mới trên lược đồ cơ sở có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên vành hữu hạn ℤn là một đóng góp mới có ý nghĩa về khoa học, cụ thể là: 16 - Kết quả nghiên cứu đã khẳng định việc phát triển các lược đồ chữ ký số trên vành hữu hạn ℤn là có cơ sở khoa học, đảm bảo tính đúng đắn, tính đầy đủ, tính hiệu quả và an toàn hơn các lược đồ chữ ký số cùng loại trên trường ℤp . - Kết quả nghiên cứu sẽ góp phần bổ sung làm giàu thêm cơ sở khoa học để phát triển lược đồ chữ ký số, đồng thời bổ sung thêm giải pháp nâng cao độ an toàn cho các lược đồ chữ ký số trên vành ℤn . 8.2. Ý nghĩa thực tiễn Kết quả nghiên cứu của luận án có ý nghĩa thực tiễn, vì: - Thứ nhất, vấn đề nghiên cứu được xuất phát việc giải quyết khoảng trống về học thuật trên thực tế, cụ thể là: giải quyết nguy cơ mất an toàn xảy ra trong tình huống trùng khóa phiên hoặc lộ khóa phiên; giải quyết vấn đề nâng cao hiệu quả cho các lược đồ chữ ký... - Thứ hai, bốn lược đồ chữ ký số đề xuất đã cài đặt thành công trên ngôn ngữ cấp cao, chạy trên các máy tính có cấu hình vừa phải được cài hệ điều hành Window, kích thước tham số sát với thực tế. - Thứ ba, luận án đã định lượng được tham số mà tiền đề là ngưỡng an toàn và sau đó là hệ tiêu chuẩn tham số an toàn. - Thứ tư, đề xuất hai môi trường ứng dụng các lược đồ chữ ký số đề xuất đó là môi trường KT-XH và lĩnh vực AN-QP, làm cơ sở cho các tổ chức hoặc cá nhân tham khảo, đánh giá độ an toàn khi có ý định ứng dụng các lược đồ chữ ký số này vào thực tế, đây là điểm khác biệt so với các luận án tiến sĩ cùng hướng nghiên cứu trong thời gian qua. - Thứ năm, đã sinh thành công các tham số, mỗi bộ tham số sinh ra được kiểm tra từng tiêu chuẩn và đều thỏa mãn. - Thứ sáu, hàm băm SHA 512 [26] đã được sử dụng trong các lược đồ chữ ký đề xuất, đây là hàm băm đang được ứng dụng rộng rãi trên thế giới. 17 9. Bố cục của luận án Ngoài phần mở đầu, kết luận, danh mục các công trình công bố, tài liệu tham khảo và phần phụ lục, luận án được cấu trúc thành ba chương sau: Chương 1. Tổng quan vấn đề nghiên cứu và cơ sở lý thuyết của luận án. Nội dung khái quát lại một số kết quả khảo sát lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên vành và trên trường hữu hạn; xác định vấn đề cần giải quyết trong luận án và trình bày một số kiến thức cơ sở liên quan đến các nội dung nghiên cứu và được sử dụng xuyên suốt trong luận án. Chương 2. Phát triển lược đồ chữ ký số trên vành. Nội dung nghiên cứu, xây dựng hai lược đồ chữ ký số cơ sở và bốn lược đồ chữ ký số cụ thể trên vành hữu hạn ℤn , đánh giá mức độ an toàn trên phương diện lý thuyết, đánh giá tính đầy đủ, tính đúng đắn và tính hiệu quả của lược đồ chữ ký số đề xuất trên cả phương diện lý thuyết và thực nghiệm. Chương 3. Xây dựng tham số an toàn cho các lược đồ chữ ký số đề xuất Nội dung nghiên cứu, xây dựng công thức tính ngưỡng an toàn cho của lược đồ chữ ký đề xuất; dựa trên một số hệ tiêu chuẩn của thế giới và Việt Nam, kế thừa và xây dựng thêm một số tiêu chuẩn tham số an toàn cho lược đồ chữ ký đề xuất; sinh thành công tham số theo hệ tiêu chuẩn đã đề xuất áp dụng cho năm 2018 và các năm tiếp theo. 18 CHƯƠNG 1. TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨU VÀ CƠ SỞ LÝ THUYẾT CỦA LUẬN ÁN Nhiệm vụ của chương là tiến hành khảo sát một số lược đồ chữ ký số trên trường hữu hạn ℤp và trên vành hữu hạn ℤn , chỉ ra một số điểm tồn tại trên các lược đồ đã khảo sát như là khoảng trống về học thuật, đồng thời xác định vấn đề nghiên cứu giải quyết những khoảng trống đã chỉ ra. Nội dung phần còn lại của chương trình bày một số cơ sở lý thuyết liên quan đến vấn đề nghiên cứu được đặt ra trong luận án và được sử dụng trong nội dung nghiên cứu các chương sau của luận án. 1.1. Tổng quan và vấn đề nghiên cứu của luận án 1.1.1. Tổng quan Trong lý thuyết số, khái niệm lớp các bài toán được cho là khó, bao gồm bài toán phân tích số, ký hiệu là FP, bài toán logarit rời rạc trên trường hữu hạn ℤp ký hiệu là DLPp , bài toán logarit rời rạc trên trên vành hữu hạn ℤn , ký hiệu DLP𝑛 , bài toán khai căn theo Modulo hợp số… Hiện nay, đa số các lược đồ chữ ký số đều có độ an toàn dựa trên tính khó giải của một hoặc hai trong số bài toán khó kể trên(gọi là bài toán cơ sở). Trong một lược đồ chữ ký số thì “độ khó” của việc giả mạo chữ ký được gọi là “độ an toàn” của nó. Như vậy nếu việc giả mạo chữ ký cần đến việc giải một bài toán khó nào đó thì lược đồ này được gọi là “có độ an toàn dựa trên tính khó giải của bài toán đó”, chẳng hạn lược đồ chữ ký số RSA có độ an toàn dựa trên tính khó giải của bài toán phân tích số 𝑛 và lược đồ DSA có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên trường ℤp . Luận án chủ yếu đề cập đến lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên trường hữu hạn ℤp , được đề cập trong các tài liệu tham khảo [13], [17], [18], [27-29], [32], [33], [38], [44], [46-52] và lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc 19 trên vành ℤn đã được công bố trong các tài liệu tham khảo [1-6], [11], [14-16], [21], [36], [39], [40-42], [45]. 1.1.2 Một số lược đồ chữ ký số trên trường ℤp Nội dung phần này NCS sẽ khảo sát một số lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên trường ℤ𝐩 , chỉ ra một số điểm còn tồn tại trên các lược đồ chữ ký này. Khảo sát đầu tiên được thực hiện với lược đồ ElGamal và một số biến thể của nó trên trường hữu hạn ℤp . Vào năm 1985, tác giả ElGamal đã đề xuất lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toàn logarít rời rạc trên trường ℤp (còn gọi là lược đồ chữ ký số ElGamal). Kể từ khi lược đồ chữ ký số ElGamal ra đời, nhiều lược đồ chữ ký số được phát triển dựa trên lược đồ này (gọi là các biến thể của lược đồ ElGamal), tiêu biểu là lược đồ chữ ký số Schnorr năm 1990 [17], [46]; lược đồ chữ ký số DSA năm 1994 [13], [29], [49], [50], [52]; lược đồ chữ ký số GOST R34.10-94 [27] của Liên bang Nga. Điểm tồn tại chung cho lược đồ chữ ký số ElGamal cùng các biến thể có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên trường ℤ𝑝 có chi phí tính toán để sinh chữ ký cao hơn các lược đồ cùng loại trên vành ℤ𝑛 , điều này được chứng minh trong bổ đề 2.3 (khi L(p) = L(q) và phép lũy thừa và phép nghịch đảo trên vành ℤ𝒏 với n=p.q có chi phí chỉ bằng 1/3 chi phí trên trường ℤ𝑝 với L(p)=L(n)); điểm tồn tại thứ hai là lược đồ chữ ký số ElGamal cùng các biến thể của nó được xây dựng trên trường ℤp phải đối mặt với nguy cơ tấn công bằng các thuật toán giải bài toán logarit rời rạc dựa vào cấp của phần tử sinh [20] khi mà hệ tham số của các lược đồ này không đạt tiêu chuẩn an toàn, chẳng hạn thuật toán Pohlig Hellman, thuật toán Rho của Pollard và thuật toán Index calculate; điểm thức ba là cấu trúc trường hữu hạn ℤp không che giấu được cấp của phần tử sinh, điều này dẫn đến nguy cơ mất an toàn trong những tính huống lộ khóa phiên hoặc trùng khóa phiên, khẳng định này được tham khảo trên các kết quả nghiên cứu liên quan được đề cập 20 trong tài liệu tham khảo[21], [33], [48-52]. Để khắc phục những điểm tồn tại đã chỉ ra, các nhà khoa học đã nghiên cứu, cải tiến các lược đồ chữ ký số ElGamal cùng các biến thể của nó với nhiều mục đích khác nhau, cụ thể là mục đích nâng cao độ an toàn được thể hiện trong các kết quả nghiên cứu [48-52]; nâng cao tốc độ sinh chữ ký và xác nhận chữ ký trong một số kết quả nghiên cứu trong [18], [29]. Năm 2013, nhóm tác giả H. Zhang, R. Li, L. Li và Y. Dong đã đề xuất một giải pháp cải tiến tốc độ cho lược đồ DSA [29]. Một kết quả nghiên cứu khác được công bố năm 2015, các tác giả H. Morita, J. C. Schuldt, T. Matsuda, G. Hamaoka, T. Iwata đã cải tiến lược đồ DSA và lược đồ Schnorr chống lại sự mất an toàn trong tình huống dùng trùng khóa phiên [28]; năm 2010 nhóm tác giả Li Xiao-fei, Shen Xuan-jing và Chen Hai-peng đã đề xuất một lược đồ sửa đổi lược đồ nguyên thủy ElGamal bằng cách thêm vào thành phần ngẫu nhiên trong mỗi phiên truyền nhằm tăng thêm tính bảo mật cho lược đồ; trong kết quả nghiên cứu của mình tác giả bài báo [13], B. Yang đã đề xuất phương pháp chống tấn công "IP Prefix Hijacking" liên quan đến lộ hoặc trùng khóa phiên; hoặc trong kết quả nghiên cứu của ba tác giả Z. Ping, K. Yingzhan và J. Keke công bố năm 2012 [49] và kết quả nghiên cứu của nhóm tác giả Z. Ping, W. Tao và C. Hao công bố năm 2015 [50], chỉ ra lược đồ chữ ký DSA không an toàn với phương pháp tấn công "L3 cache time attack" là một kiểu tấn công kênh kề (Side chanel attack) được đề cập trong [5]. Cho đến nay, đã có nhiều công trình khoa học trong nước và trên thế giới được công bố nhằm cải tiến lược đồ ElGamal cùng các biến thể của nó, tuy nhiên cho đến nay chưa có kết quả nghiên cứu nào có thể thể khắc phục được triệt để những tồn tại trên các lược đồ chữ ký số này, đặc biệt là khắc phục vấn đề không thể che giấu cấp của phần tử sinh trên cấu trúc trường ℤp . 1.1.3. Một số lược đồ chữ ký số trên vành ℤn Vấn đề nghiên cứu đã đặt ra cho các nhà khoa học trong thiết kế lược đồ chữ ký là phải chọn một cấu trúc đại số phù hợp hơn cấu trúc trường ℤp , đảm