Chương 1: Tổng quan về lược đồ chữ ký số EC-Schnorr. Trình bày tổng quan về lược đồ chữ ký số, các định nghĩa và khái niệm an toàn của lược đồ chữ ký số dựa trên đường cong elliptic trong trường hữu hạn; nghiên cứu một số yêu cầu đối với hàm Hash trong lược đồ chữ ký số Schnorr và độ an toàn tổng thể của kiểu lược đồ chữ ký số EC-Schnorr; đặt ra các vấn đề cần nghiên cứu, giải quyết. Chương 2: Nghiên cứu đề xuất một số giải pháp nâng cao độ an toàn cài đặt cho lược đồ chữ ký số EC-Schnorr Chương này trình bày về việc phân tích tấn công đối với lược đồ chữ ký khi khóa bí mật tức thời bị sử dụng lặp lại, đánh giá các giải pháp đã có, từ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 đó nghiên cứu đề xuất một lược đồ bổ sung thêm một phép tính hàm băm cho lược đồ chữ ký số EC-Schnorr gốc, gọi là lược đồ EC-Schnorr-M; đưa ra các đánh giá và chứng minh an toàn cho lược đồ chữ ký số EC-Schnorr-M trong mô hình bộ tiên tri ngẫu nhiên. Chương 3: Nghiên cứu đảm bảo an toàn cho khóa bí mật của lược đồ chữ ký số kiểu EC-Schnorr.
Chương này trình bày hai tấn công: tấn công thứ nhất được áp dụng khi khóa bí mật tức thời có các khoảng bit bị lặp; tấn công thứ hai xảy ra khi khóa bí mật tức thời và dài hạn của lược đồ chữ ký số đủ nhỏ hoặc đủ lớn so với cấp của nhóm. Trên cơ sở đó, đề xuất các tiêu chuẩn đảm bảo an toàn cho khóa bí mật của lược đồ chữ ký số kiểu EC-Schnorr. Danh mục các công trình đã công bố và tài liệu tham khảo. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 Chương này sẽ trình bày tổng quan về lược đồ chữ ký số, các định nghĩa và khái niệm an toàn của lược đồ chữ ký số dựa trên đường cong elliptic trong trường hữu hạn, phân tích, đánh giá một số nội dung liên quan đến độ an toàn của lược đồ chữ ký số EC-Schnorr.
Trên cơ sở đó đặt ra các vấn đề cần nghiên cứu, giải quyết. Tổng quan về lược đồ chữ ký số 1. Định nghĩa tổng quát về lược đồ chữ ký số Trong một lược đồ chữ ký số, mỗi người ký 𝐴 sở hữu một khóa công khai và một khóa bí mật. Những khóa này được sử dụng với mục đích: Khóa bí mật có nhiệm vụ chính là tạo chữ ký và chỉ có người sở hữu khóa này mới biết giá trị của nó.
Khóa công khai có nhiệm vụ giúp một người bất kỳ có thể kiểm tra tính hợp lệ của chữ ký trên một thông điệp nào đó. Do vậy, khóa này được công bố một cách công khai. Như vậy, khóa công khai của 𝐴 giúp cho chữ ký của anh ta trên một thông điệp nào đó có thể được xác minh tính hợp lệ một cách dễ dàng bởi một người bất kỳ. Trong khi đó, khóa bí mật của 𝐴 được sử dụng với mong muốn rằng bất cứ người nào không biết khóa này sẽ gặp khó khăn (hoặc không có khả năng) trong việc giả mạo một chữ ký hợp lệ của 𝐴 trên một thông điệp nào đó.
Tuy nhiên, khi thuật toán chữ ký được thiết kế không đủ tốt thì mong muốn đối với khóa bí mật thường không đạt được. Vì vậy, vấn đề này được xem là một thách thức khi thiết kế một lược đồ chữ ký số. Một định nghĩa hình thức cho lược đồ chữ ký số được xác định như sau: Định nghĩa 1. Một lược đồ chữ ký số được định nghĩa thông qua bộ-3 thuật toán (𝐾𝑒𝑦𝐺𝑒𝑛, 𝑆𝑖𝑔𝑛, 𝑉𝑒𝑟𝑖𝑓𝑦) như sau: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 14 Thuật toán sinh khóa 𝑲𝒆𝒚𝑮𝒆𝒏: Nhận đầu vào 1𝑘 , với 𝑘 là tham số an toàn, tạo ra một cặp khóa công khai và khóa bí mật thích hợp (𝑝𝑘, 𝑠𝑘).
Thuật toán sinh khóa phải là một thuật toán xác suất. Thuật toán ký 𝑺𝒊𝒈𝒏: Cho trước thông điệp 𝑚 và một cặp khóa công khai và bí mật thích hợp (𝑝𝑘, 𝑠𝑘), thuật toán Sign tạo ra một chữ ký 𝜎. Thuật toán sinh chữ ký có thể là thuật toán xác suất, và trong một vài lược đồ nó cũng có thể nhận thêm các đầu vào khác. Thuật toán xác minh 𝑽𝒆𝒓𝒊𝒇𝒚: Cho trước chữ ký 𝜎, một thông điệp 𝑚 và một khóa công khai 𝑝𝑘, thuật toán Verify kiểm tra 𝜎 là chữ ký hợp lệ của thông điệp 𝑚 tương ứng với khóa 𝑝𝑘 hay không.
Nói chung, thuật toán xác minh không nên là một thuật toán xác suất. Cho tới nay, các lược đồ chữ ký số phổ biến được chia ra thành hai lớp chính là các lược đồ chữ ký số dựa trên bài toán phân tích số và các lược đồ chữ ký dựa trên bài toán logarit rời rạc trên trường hữu hạn hay trên đường cong elliptic. Các khái niệm an toàn đối với lược đồ chữ ký số Theo [14], một lược đồ chữ ký số bị “phá vỡ” hay “không an toàn” trước một tấn công cụ thể nếu kẻ tấn công có thể thực hiện được những điều sau lên lược đồ chữ ký số với xác suất đáng kể: Phá vỡ hoàn toàn: Kẻ tấn công tìm ra được khóa bí mật của người ký. Giả mạo vạn năng: Kẻ tấn công có thể tìm ra một thuật toán sinh chữ ký hiệu quả có khả năng tương đương thuật toán sinh chữ ký của người ký.
Nghĩa là, có thể tạo ra chữ ký hợp lệ của người ký lên bất cứ thông điệp nào. Giả mạo tồn tại: Kẻ tấn công có thể đưa ra một cặp chữ ký - thông điệp mới và hợp lệ. Rõ ràng, nếu một lược đồ chữ ký số bị “phá vỡ hoàn toàn” hoặc bị “giả mạo vạn năng” trước một tấn công cụ thể thì lược đồ đó thực sự kém an toàn. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 15 Đối với “giả mạo tồn tại”, trong nhiều trường hợp, đây không thực sự là một mối đe dọa nguy hiểm đối với lược đồ chữ ký số, bởi vì thông điệp mà kẻ tấn công đưa ra nhiều khi không có ý nghĩa.
Tuy nhiên, nếu một lược đồ không bị “giả mạo tồn tại” trước một tấn công cụ thể, thì lược đồ này cũng có khả năng ngăn chặn mối đe dọa “phá vỡ hoàn toàn” và “giả mạo vạn năng”. Theo [14], độ an toàn đối với một lược đồ chữ ký số được đánh giá thông qua kịch bản tấn công lựa chọn thông điệp thích nghi. Ở đó, ngoài các thông tin công khai, kẻ tấn công có thể yêu cầu người ký tạo ra chữ ký trên bất kỳ thông điệp nào. Theo đó, kẻ tấn công có thể đưa ra yêu cầu tiếp theo đến người ký dựa trên những cặp thông điệp - chữ ký đã nhận được trước đó.
Lưu ý rằng, kẻ tấn công được xem xét ở đây là những máy thời gian đa thức xác suất, nghĩa là kẻ tấn công có năng lực tính toán hạn chế. Một lược đồ chữ ký số được gọi là an toàn nếu việc giả mạo tồn tại là không thể về mặt tính toán, ngay cả với một tấn công lựa chọn thông điệp thích nghi. Dưới đây, chúng ta sẽ phân tích một vài tình huống mà ở đó, các lược đồ chữ ký số không an toàn theo định nghĩa trên, hay nói cách khác chúng được xem là không an toàn về mặt lý thuyết. Lược đồ chữ ký số RSA nguyên thủy là không an toàn, bởi lược đồ này là đối tượng cho việc giả mạo tồn tại.
Nói cách khác, việc tạo ra một cặp chữ ký - thông điệp hợp lệ khác là dễ dàng, ngay cả khi không có bất cứ sự giúp đỡ nào từ người ký. Thật vậy, kẻ tấn công lựa chọn tùy ý chữ ký 𝜎 ∈ ℤ∗𝑁 , và sau đó tính thông điệp tương ứng là 𝑚 = 𝜎 𝑒 𝑚𝑜𝑑 𝑁. Khi đó, 𝑚 và 𝜎 là một cặp thông điệp, chữ ký hợp lệ, bởi chúng thỏa mãn điều kiện của thuật toán xác minh. Lược đồ chữ ký số ElGamal nguyên thủy là một ví dụ điển hình cho các lược đồ chữ ký số dựa trên bài toán logarit rời rạc không an toàn theo định nghĩa 1.
Lược đồ này được mô tả trong [19] như sau: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 16 - Thuật toán sinh khóa 𝐾𝑒𝑦𝐺𝑒𝑛: Chọn một số nguyên tố lớn cỡ 𝑛 và một phần tử sinh 𝑔 của ℤ∗𝑝 , cả hai đều công khai. Sau đó, với một khóa bí mật ngẫu nhiên 𝑥 ∈ ℤ𝑝−1 , thuật toán tính khóa công khai 𝑦 = 𝑔 𝑥 𝑚𝑜𝑑 𝑝. - Thuật toán ký 𝑆𝑖𝑔𝑛: Để ký lên thông điệp 𝑚, người ta tạo ra một cặp (𝑟, 𝑠) sao cho 𝑔𝑚 = 𝑦 𝑟 𝑟 𝑠 𝑚𝑜𝑑 𝑝. Để đạt được mục đích này, ta phải chọn một 𝑘 ∈ ℤ∗𝑝−1 ngẫu nhiên, tính toán lũy thừa 𝑟 = 𝑔𝑘 𝑚𝑜𝑑 𝑝 và giải 𝑠 theo phương trình tuyến tính 𝑚 = (𝑥𝑟 + 𝑘𝑠) 𝑚𝑜𝑑 (𝑝 − 1).
Thuật toán Sign đưa ra (𝑟, 𝑠). - Thuật toán xác minh 𝑉𝑒𝑟𝑖𝑓𝑦: Kiểm tra đẳng thức 𝑔𝑚 = 𝑦 𝑟 𝑟 𝑠 𝑚𝑜𝑑 𝑝. Lược đồ chữ ký số ElGamal là có thể giả mạo tồn tại (existentially forgeable). Chứng minh: Đây là một kết quả nổi tiếng, việc giả mạo trên lược đồ chữ ký số ElGamal có thể biểu diễn theo hai cách như sau: - Giả mạo dùng một tham số: Lấy ngẫu nhiên 𝑒 ∈ ℤ𝑝−1 , nếu chọn 𝑟 = 𝑔𝑒 𝑦 𝑚𝑜𝑑 𝑝 và 𝑠 = −𝑟 𝑚𝑜𝑑 (𝑝 − 1), dễ thấy rằng (𝑟, 𝑠) là một chữ ký hợp lệ đối với thông điệp 𝑚 = 𝑒𝑠 𝑚𝑜𝑑 (𝑝 − 1).
- Giả mạo dùng hai tham số: Lấy ngẫu nhiên 𝑒 ∈ ℤ𝑝−1 và 𝑣 ∈ ℤ𝑝∗ , nếu chọn 𝑟 = 𝑔𝑒 𝑦 𝑣 𝑚𝑜𝑑 𝑝 và 𝑠 = −𝑟𝑣 −1 𝑚𝑜𝑑 (𝑝 − 1), thì (𝑟, 𝑠) là một chữ ký hợp lệ đối với thông điệp 𝑚 = 𝑒𝑠 𝑚𝑜𝑑 (𝑝 − 1).■ Hai lược đồ chữ ký số ElGamal và RSA ở trên đều không an toàn theo kịch bản mà ở đó kẻ tấn công có thể chọn trước cặp chữ ký (𝑟, 𝑠) sau đó mới tính thông điệp 𝑚 cho phù hợp. Để tránh tấn công như vậy, một phương án có thể sử dụng là: thay vì ký trực tiếp lên thông điệp 𝑚, người ta sẽ băm thông điệp này bởi một hàm băm 𝐻 và sau đó thực hiện việc ký lên giá trị thu được. Do đó, nếu hàm băm được thiết kế đủ tốt thì kẻ tấn công như trên chỉ thu được giá trị băm 𝐻(𝑚) mà không thể đưa ra thông điệp 𝑚 phù hợp. Và đây là lý do tất cả các chuẩn chữ ký số (ECDSA, ECGDSA, GOST R 34.12- 2012,…) đều sử dụng hàm băm theo phương pháp trên.