Tóm tắt Luận án Tiến sĩ Toán học: Nghiên cứu phát triển một số lược đồ chữ ký số và ứng dụng trong việc thiết kế giao thức trao đổi khóa

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST

Báo xấu

11
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tóm tắt Luận án Tiến sĩ Toán học "Nghiên cứu phát triển một số lược đồ chữ ký số và ứng dụng trong việc thiết kế giao thức trao đổi khóa" được nghiên cứu với mục tiêu là: Khái quát chung về chữ ký số và giao thức trao đổi khóa; Đề xuất lược đồ chữ ký số an toàn; Đề xuất giao thức trao đổi khóa an toàn dựa trên chữ ký số.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Toán học: Nghiên cứu phát triển một số lược đồ chữ ký số và ứng dụng trong việc thiết kế giao thức trao đổi khóa

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ TRIỆU QUANG PHONG NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ LƢỢC ĐỒ CHỮ KÝ SỐ VÀ ỨNG DỤNG TRONG VIỆC THIẾT KẾ GIAO THỨC TRAO ĐỔI KHÓA Ngành: Cơ sở toán học cho tin học Mã số: 9 46 01 10 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2023
CÔNG TRÌNH ĐƢỢC HOÀN THÀNH TẠI VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ - BỘ QUỐC PHÕNG Người hướng dẫn khoa học: TS. Trần Duy Lai TS. Vũ Quốc Thành Phản biện 1: PGS. TS Nguyễn Linh Giang Đại học Bách khoa Hà Nội Phản biện 2: PGS. TS Nguyễn Ngọc Hóa Trƣờng Đại học Công nghệ, Đại học Quốc gia Hà Nội Phản biện 3: TS Đỗ Việt Bình Viện Khoa học và Công nghệ Quân Sự Luận án được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp Viện, họp tại Viện KH-CNQS vào hồi……giờ….ngày.....tháng......năm 2023 Có thể tìm hiểu luận án tại: - Thư viện Viện Khoa học và Công nghệ quân sự - Thư viện Quốc gia Việt Nam
DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ [CT1]. Trieu Quang Phong, Nguyen Quoc Toan (2017). “Some Security Comparisons of GOST R 34.10-2012 and ECDSA Signature Schemes”, In Pre-proceedings of 6th Workshop on Current Trends in Cryptology (CTCrypt 2017), pp. 140-158. [CT2]. Triệu Quang Phong, Trần Duy Lai (2017). “Về một số lưu ý đối với lược đồ chữ ký số”, Tạp chí Nghiên cứu KH&CNQS, Số Đặc san CNTT, 12-2017, tr. 45-53. [CT3]. Triệu Quang Phong (2017). “Xem xét các thuộc tính an toàn của họ giao thức STS”, Chuyên san Nghiên cứu KH&CN trong lĩnh vực An toàn thông tin của Tạp chí An toàn thông tin – Ban Cơ yếu chính phủ, CS 05, tr. 52-60. [CT4]. Trieu Quang Phong (2019). “Considering two MAC under SIG variants of the basic SIGMA protocol”, Mathematical Aspects of Cryptography, Vol. 10(2), pp. 145-158. [CT5]. Triệu Quang Phong (2020). “Một số phân tích về mô hình an toàn cho giao thức trao đổi khóa”, Tạp chí Nghiên cứu KH&CNQS, Số Đặc san CNTT, 12 –2020, tr. 60-71. [CT6]. Trieu Quang Phong, Tran Duy Lai (2021). “Constructing efficient and secure batch signature schemes”, Journal of Military Science and Technology, No. CSCE5, pp. 49-60.
1 MỞ ĐẦU 1. Tính cấp thiết của đề tài luận án Việc trao đổi thông tin một cách bí mật và hiệu quả giữa các bên có thể được đảm bảo bởi các lược đồ mã hóa khóa đối xứng. Tuy nhiên, phương thức này lại yêu cầu các bên phải chia sẻ một khóa bí mật chung để thực hiện cả chức năng mã hóa lẫn giải mã. Đối với các bên cách xa nhau về mặt địa lý, việc thiết lập các khóa bí mật chung sẽ được thực hiện thông qua các giao thức trao đổi khóa (hay thỏa thuận khóa). Các giao thức trao đổi khóa hiện nay đa phần được thiết kế dựa trên một cơ chế khá nổi tiếng, đó là trao đổi khóa Diffie-Hellman. Tuy nhiên, để đảm bảo các giao thức trao đổi khóa hoạt động một cách an toàn với cơ chế này, chúng ta cần phải sử dụng các cơ chế xác thực cho chúng. Việc sử dụng chữ ký số được xem là một giải pháp có tính khả thi. 2. Mục tiêu nghiên cứu Trên cơ sở phân tích các kết quả đã công bố và những vấn đề còn hạn chế, mục tiêu chính của đề tài luận án là đề xuất lược đồ chữ ký số an toàn, hiệu quả và xây dựng giao thức trao đổi khóa có xác thực dựa trên chữ ký được đề xuất. 3. Đối tƣợng và phạm vi nghiên cứu Đối tượng nghiên cứu Luận án tập trung vào đối tượng là các lược đồ chữ ký số và giao thức trao đổi khóa dựa trên chữ ký số có độ an toàn chứng minh được trong các mô hình lý thuyết. Phạm vi nghiên cứu Luận án tập trung nghiên cứu các lược đồ chữ ký số ECDSA, GOST R 34.10-2012, TEGTSS, ECTEGTSS; các giao thức trao đổi khóa có xác thực dựa trên chữ ký STS, SIGMA; các phương pháp thiết kế và đáng giá độ an toàn chứng minh được cho lược đồ chữ ký số và giao thức trao đổi khóa trong các mô hình lý thuyết.
2 4. Nội dung nghiên cứu Luận án này tập trung vào nghiên cứu giải quyết 02 vấn đề chính: - Xây dựng, đề xuất các lược đồ chữ ký số có độ an toàn chứng minh được, - Xây dựng các giao thức trao đổi khóa có độ an toàn chứng minh được dựa trên lược đồ chữ ký được đề xuất 5.Phƣơng pháp nghiên cứu Nghiên cứu được tiến hành dựa trên các phương pháp sau: phương pháp phân tích và tổng hợp lý thuyết, phương pháp thu thập số liệu, phương pháp định tính, phương pháp thực nghiệm. 6. Ý nghĩa khoa học và thực tiễn - Ý nghĩa khoa học. Luận án góp phần đề xuất một số giải pháp ký số và trao đổi khóa đạt tính hiệu quả và độ an toàn chứng minh được. - Ý nghĩa thực tiễn. Kết quả của luận án có thể được ứng dụng trong thực tế nhằm đáp ứng nhu cầu trong các lĩnh vực kinh tế xã hội, an ninh quốc phòng, thúc đẩy xây dựng Chính phủ điện tử tại Việt nam. 7. Bố cục của luận án Luận án gồm 03 chương cùng với các phần mở đầu, kết luận, danh mục các công trình khoa học đã được công bố của tác giả và 01 Phụ lục. - Chương 1: Khái quát chung về chữ ký số và giao thức trao đổi khóa. - Chương 2: Đề xuất lược đồ chữ ký số an toàn. - Chương 3: Đề xuất giao thức trao đổi khóa an toàn dựa trên chữ ký số.
3 CHƢƠNG 1 KHÁI QUÁT CHUNG VỀ CHỮ KÝ SỐ VÀ GIAO THỨC TRAO ĐỔI KHÓA 1.1. Một số khái niệm cơ sở liên quan 1.1.1. Lược đồ chữ ký số tổng quát Một lược đồ chữ ký số được định nghĩa thông qua bộ-3 thuật toán: - Thuật toán sinh khóa : Nhận đầu vào , 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 . - 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 , tạo ra một chữ ký . - 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 , kiểm tra là chữ ký hợp lệ của tương ứng với khóa hay không. 1.1.2. Các khái niệm an toàn cho chữ ký số Mục này trình bày 02 kiểu tấn công (chỉ sử dụng khóa (công khai) và sử dụng thông điệp) và 04 nguy cơ giả mạo (phá vỡ hoàn toàn, giả mạo vạn năng, giả mạo lựa chọn, giả mạo tồn tại). Trong đó, độ an toàn kháng giả mạo tồn tại trước tấn công lựa chọn thông điệp thích nghi (thuộc tấn công sử dụng thông điệp), còn gọi là EUF-CMA, được sử dụng cho chữ ký số. Định nghĩa 1.2. 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. Độ an toàn EUF-CMA của một lược đồ chữ ký số sẽ có thể quy về độ an toàn EUF-NMA (tức là kháng giả mạo tồn tại trước tấn công chỉ sử dụng khóa công khai) nếu “bộ mô phỏng” của nó tồn tại. 1.1.3. Một số thuộc tính an toàn đáng mong đợi của giao thức thỏa thuận khóa Mục này trình bày một số thuộc tính an toàn cơ bản cho giao thức trao đổi khóa, bao gồm: xác thực khóa ẩn, chứng thực khóa hiện, an
4 toàn về phía trước (PFS), kháng tấn công mạo danh thỏa hiệp khóa (KCI), kháng tấn công chia sẻ khóa nhưng không rõ đối (UKS). 1.2. Đánh giá về vấn đề bƣớc lặp Mục này trình bày vấn đề bước lặp trong các lược đồ chữ ký ECDSA và GOST R 34.10-2012. 1.2.1. Lược đồ ECDSA Mục này trình bày phân tích vấn đề bước lặp cho ECDSA. 1.2.2. Lược đồ chữ ký GOST R 34.10-2012 Mục này trình bày phân tích vấn đề bước lặp cho lược đồ chữ ký số GOST R 34.10-2012. Bảng 1.1. Kết quả khảo sát bước lặp trên một số lược đồ chữ ký số. 1.3. Đánh giá về vấn đề chữ ký kép và tính dễ uốn 1.3.1. Chữ ký kép và tính dễ uốn đối với ECDSA Lược đồ chữ ký ECDSA được chỉ ra có hai lỗi sau: Lỗi chữ ký kép. Với là hai thông điệp bất kỳ, có thể tìm được khóa bí mật để tạo chữ ký chung cho .
5 Tính dễ uốn. Nếu là một chữ ký hợp lệ trên thông điệp đối với khóa công khai nào đó thì cũng là một chữ ký hợp lệ trên . Nguyên nhân: Do tính chất đối xứng của các điểm thuộc đường cong elliptic, tức là với thuộc đường cong ( ) thì . 1.3.2. Đánh giá vấn đề chữ ký kép và tính dễ uốn đối với GOST R 34.10-2012 Qua quá trình khảo sát và phân tích, luận án chỉ ra rằng GOST R 34.10-2012 có khả năng kháng lỗi chữ ký kép và tính dễ uốn. 1.4. Các mô hình an toàn cho lƣợc đồ chữ ký số 1.4.1. Mô hình bộ tiên tri ngẫu nhiên Trong mô hình này, hàm băm được lý tưởng hóa như một hàm ngẫu nhiên và được gọi là một “bộ tiên tri ngẫu nhiên”, mà hoạt động như sau. Với truy vấn được yêu cầu lần đầu, bộ tiên tri sẽ trả về một đầu ra ngẫu nhiên (thuộc tập đầu ra). Khi nó được yêu cầu từ lần thứ hai, bộ tiên tri tri sẽ trả về đầu ra mà trùng với câu trả lời cho yêu cầu trước đó. 1.4.2. Mô hình nhóm tổng quát 1.4.3. Mô hình với thiết bị bảo vệ 1.4.4. Mô hình bộ tiên tri ngẫu nhiên song ánh 1.5. Lƣợc đồ chữ ký số dạng TEGTSS Các lược đồ TEGTSS (bao gồm TEGTSS-II) được đề xuất bởi Pointcheval và cộng sự là an toàn EUF-CMA bằng cách chỉ ra độ an toàn EUF-NMA và sự tồn tại của bộ mô phỏng. Đây là tiền đề cho việc nghiên cứu lược đồ ECTEGTSS và các đề xuất ở Chương 2. Các lược đồ TEGTSS-II dựa trên sự tồn tại của bộ ba hàm , , . Trong đó, hàm phục vụ cho thuật toán tạo chữ ký, và sẽ dùng cho thuật toán xác minh. Ngoài ra, đối với TEGTSS-II, D. Pointcheval và cộng sự còn chỉ ra thêm điều kiện “1-1” đối với và . Trong quyển toàn văn, tác giả luận án đã chỉ ra sự không hợp lý của điều kiện “1-1” kể trên và đề xuất thay bằng điều kiện “gần 1-1”
6 trong Nhận xét 1.3, mà tương tự Nhận xét 2.1 cho ECTEGTSS ở Chương 2. 1.6. Khảo sát một số giao thức trao đổi khóa dựa trên chữ ký số Mục này trình bày một số lớp giao thức dựa trên cơ chế trao đổi khóa Diffie-Hellman mà dùng chữ ký để cung cấp tính xác thực. Cụ thể, quá trình này bắt đầu từ giao thức STS cơ bản đến họ giao thức SIGMA. 1.6.1. Giao thức STS cơ bản Giao thức STS cơ bản là phiên bản đầu tiên của họ STS. Do sử dụng cơ chế mã hóa để chứng nhận khóa, nên nó còn được gọi là STS- ENC (STS-ENCryption). Tuy nhiên, giao thức STS có thể bị tấn công tấn công UKS thay đổi khóa công khai. 1.6.2. Giao thức STS-MAC STS-MAC là một giao thức trong họ STS. Biến thể này cung cấp tính chứng nhận khóa bằng cách sử dụng hàm MAC (an toàn) thay vì sử dụng hàm mã hóa (an toàn) như STS cơ bản. Tuy nhiên, giao thức này cũng dễ dàng bị tổn thương trước tấn công UKS. Một số biến thể của STS-MAC đã được đưa ra để khắc phục điều này. Trong đó có, giao thức trong Hình 1.5. Hình 1.5. Biến thể 2 của STS-MAC Luận án đã mở rộng kết quả của J. Baek, K. Kim để đưa ra Mệnh đề 1.3, Mệnh đề 1.4 để chỉ ra nếu lược đồ chữ ký số được dùng là DSA, TEGTSS-II thì giao thức trong Hình 1.5 vẫn bị tấn công UKS. 1.6.3. Giao thức ISO-STS-MAC ISO-STS-MAC là một biến thể của họ STS xuất hiện trong chuẩn ISO/IEC 11770-3. Giao thức này dựa trên cơ chế “SIG-and-MAC”.
7 ISO-STS-MAC có khả năng kháng tấn công UKS và đạt một số thuộc tính khác (xem Bảng 1.2). Ngoài ra, giao thức này cũng an toàn trong mô hình CK. Tuy nhiên, nó không cung cấp tính “bảo vệ định danh”. Bảng 1.2. Các tính chất an toàn được xem xét trên họ giao thức STS. 1.6.4. Họ giao thức SIGMA Họ giao thức SIGMA cũng dựa trên cơ chế “SIG-and-MAC” giống ISO-STS-MAC nhưng lại cung cấp tính bảo vệ định danh. Ngoài ra, các giao thức SIGMA cũng đạt được các thuộc tính an toàn trong Bảng 1.2. Giao thức SIGMA cơ bản (Hình 1.7) là phiên bản đầu tiên trong họ SIGMA mà cung cấp tính bảo vệ định danh cho bên khởi tạo. Về mặt lý thuyết, giao thức này là an toàn trong mô hình CK với đối tác được định rõ sau. Một số giao thức khác trong họ này bao gồm: SIGMA-I, SIGMA-R và SIGMA đầy đủ. Hình 1.7. Giao thức SIGMA cơ bản
8 1.7.Mô hình an toàn cho giao thức trao đổi khóa Các mô hình đều được thiết lập để bảo vệ an toàn cho việc chia sẻ khóa chung giữa hai bên ̂ và ̂ trước sự đe dọa của bên đối kháng , mà được mô hình hóa để kiểm soát tất cả liên lạc giữa các bên cũng như kích hoạt các phiên và được phép thực hiện các truy vấn tới các bên để:  Khám phá các thông tin (bí mật) ngắn hạn;  Khám phá khóa phiên đối với các phiên đã hoàn tất,  Khám phá thông tin (dài hạn) của bên tham gia cụ thể. Nhiệm vụ của bên đối kháng (hay kẻ tấn công) là để phân biệt một khóa phiên của một phiên mục tiêu với một khóa ngẫu nhiên theo một cách “không tầm thường”. Cụm từ “không tầm thường” ở đây, được hiểu là bên đối kháng sẽ bị hạn chế các quyền ở trên đối với phiên mục tiêu và phiên có quan hệ “so khớp” với phiên mục tiêu (nếu tồn tại). 1.7.1. Mô hình với đối tác được định rõ trước Các mô hình an toàn được xem xét trong mục này gồm: CK, CKHMQV và mô hình với độ an toàn AKE. Đặc điểm chung trong các mô hình này là các bên có thể biết được định danh của bên đối tác của mình trước khi bắt đầu thực hiện giao thức. Hơn nữa quan hệ “so khớp” trong các mô hình này chỉ có thể được thiết lập với các phiên đã hoàn tất. Một kết quả thu được là độ an toàn trong mô hình và độ an toàn AKE không thể suy dẫn qua nhau. 1.7.2. Mô hình với đối tác được định rõ sau Mục này trình bày một biến thể của mô hình CK, có tên gọi là mô hình CK với đối tác được định rõ sau. Trong mô hình này, quan hệ “so khớp”có thể được thiết lập giữa các phiên chưa hoàn tất. Mô hình này là cơ sở cho việc đánh giá an toàn cho các đề xuất trong Chương 3. 1.8.Đánh giá chung về hƣớng nghiên cứu Dựa trên các việc đánh giá tổng quan, tác giả luận án thấy rằng hướng nghiên cứu về các lược đồ chữ ký số kiểu DSA, GOST, cũng như
9 các giao thức trao đổi khóa có xác thực dựa trên cơ chế Diffie-Hellman vẫn là những chủ đề đáng được quan tâm và còn chứa nhiều tính mới. 1.9. Kết Luận Chƣơng 1 Các kết quả thu được từ chương này gồm: - Trình bày kiến thức chung về một số lược đồ chữ ký số và giao thức trao đổi khóa, bao gồm ECDSA, GOST R 34.10-2012, STS, SIGMA, và một số khái niệm và mô hình an toàn lý thuyết. - Phân tích vấn đề bước lặp trong đối với ECDSA, GOST R 34.10- 2012 (Bảng 1.1). Kết quả này đã được công bố trong [CT2]. - Chỉ ra GOST R 34.10-2012 có khả năng kháng lỗi chữ ký kép và tính dễ uốn trên ECDSA. Kết quả này đã được công bố trong [CT1]. - Xem xét một số thuộc tính an toàn của các giao thức trong họ giao thức STS (xem Bảng 1.2). Những thuộc tính như vậy cũng đúng cho họ giao thức SIGMA. Bổ sung lý do cho việc các biến thể STS mà đưa chữ ký SIG vào trong MAC là thực sự không an toàn kháng tấn công UKS, mà đã được chỉ ra trong Mệnh đề 1.3 và Mệnh đề 1.4. Một số kết quả ở đây đã được công bố trong [CT3]. - Chỉ ra độ an toàn của mô hình và độ an toàn AKE không thể suy dẫn được thông qua nhau (công bố trong [CT5]). Hơn nữa, những kiến thức và kết quả thu được ở đây giúp tác giả đặt ra các hướng nghiên cứu mang lại đóng góp mới của luận án, bao gồm: - Xây dựng biến thể có độ an toàn chứng minh được và độ hiệu quả “tương đương” cho GOST R3 34.10-2012, thực hiện ở Chương 2. - Xây dựng biến thể của giao thức SIGMA theo hướng đưa MAC vào trong SIG để giúp tiết kiệm băng thông trao đổi, nhưng vẫn đảm bảo độ an toàn và hiệu quả so với giao thức ban đầu, thực hiện ở Chương 3.
10 CHƢƠNG 2 ĐỀ XUẤT LƢỢC ĐỒ CHỮ KÝ SỐ AN TOÀN 2.1. Lƣợc đồ chữ ký dạng ECTEGTSS Một lược đồ là ECTEGTSS nếu nó có các tính chất sau: (i) Nhóm cơ sở là đường cong elliptic ( ) có cấp bằng , với là số nguyên tố còn là thừa số nhỏ, một điểm ( ) có cấp . (ii) Lược đồ sử dụng hai hàm và , với miền giá trị tương ứng là và . Trong đó, được lập mô hình như một bộ tiên tri ngẫu nhiên và yêu cầu một số tính chất -kháng va chạm hoặc không có -va chạm, với số nguyên nào đó. (iii) Tồn tại ba hàm số: thỏa mãn với , (iv) Mỗi người có một khóa cá nhân và khóa công khai . (v) Để ký thông điệp , chọn , tính , , và . Đưa ra chữ ký . (vi) Để xác minh chữ ký có là hợp lệ với thông điệp hay không, tính và , tính . Cuối cùng kiểm tra và . (vii) Các hàm và phải thỏa mãn điều kiện “1 – 1” sau: cho trước , và , tồn tại duy nhất một cặp sao cho: . Hơn nữa, cặp này phải dễ tìm thấy. Nhận xét 2.1. Điều kiện (vii) đối với ECTEGTSS được phát biểu chưa đủ. Cụ thể, chúng ta sẽ cần điều kiện “gần” 1-1 như sau: ngoại trừ xác suất không đáng kể, thì với và cho trước chỉ tồn tại duy nhất một cặp sao cho và thay
11 vì điều kiện “1-1” ban đầu. Điều kiện này là có thể đạt được khi lựa chọn tham số. Dựa trên điều kiện gần “1-1” trong Nhận xét 2.1, luận án đã chứng minh chi tiết sự tồn tại của “bộ mô phỏng” đối với các lược đồ chữ ký dạng ECTEGTSS. Bổ đề 2.2. Giả sử là một hàm ngẫu nhiên lý tưởng với đầu ra nằm giữa 0 và . Khi đó tồn tại một bộ mô phỏng mà sinh ra các bộ hợp lệ sao cho sau bước, xác suất mà có thể bị phân biệt với một bộ ký ECTEGTSS với xác suất nhỏ hơn . 2.2. Đề xuất biến thể của lƣợc đồ chữ ký GOST R34.10-2012 Luận án đã kết hợp GOST R 34.10-2012 và ECTEGTSS để đưa ra hai đề xuất với tên gọi GOST-I và GOST-II mà đạt được độ an toàn EUF-CMA. Hơn nữa, những biến thể này vẫn kế thừa khả năng kháng lỗi chữ ký kép, tính dễ uốn và hiệu quả so với phiên bản gốc. 2.2.1. Lược đồ chữ ký số GOST-I  Thuật toán ký (của ̂ trên thông điệp ): 1. Chọn . 2. Tính , và , nếu quay về bước 1. 3. Tính . 4. Tính số nguyên mà có biểu diễn bit là , và . Nếu , thì gán . 5. Tính ; nếu , quay lại bước 1. 6. Trả về chữ ký .  Thuật toán xác minh: 1. Xác minh có thuộc hay không 2. Tính 3. Tính số nguyên mà có biểu diễn bit là , và . Nếu , thì gán 4. Tính
12 5. Tính và 6. Tính và tính 7. Chữ ký được xác minh chỉ khi Độ an toàn của GOST-I. Ở đây, luận án sẽ trình bày độ an toàn EUF- CMA của lược đồ chữ ký GOST-I. Mệnh đề 2.1. Lược đồ chữ ký GOST-I có dạng ECTEGTSS. Độ an toàn EUF-NMA của GOST-I được chỉ ra trong Mệnh đề sau. Mệnh đề 2.2. Giả sử rằng tồn tại một kẻ tấn công thành công trong việc giả mạo chữ ký của lược đồ GOST-I với xác suất thành công là sau truy vấn tới bộ tiên tri ngẫu nhiên , thì người ta có thể giải bài toán logarit rời rạc trong bằng cách sử dụng lần lặp của với xác suất lớn hơn . Sự tồn tại bộ mô phỏng cùng với độ an toàn EUF-NMA kéo theo độ an toàn EUF-CMA của GOST-I. Mệnh đề 2.3. Chúng ta xem xét một kẻ tấn công đối với một lược đồ chữ ký GOST-I, và cũng giả sử rằng có khả năng thực hiện môt giả mạo tồn tại dưới một tấn công lựa chọn thông điệp thích nghi với xác suất sau truy vấn tới hàm , thì người ta có thể giải bài toán logarit rời rạc trong bằng cách sử dụng lần lặp của với xác suất lớn hơn . 2.2.2. Lược đồ chữ ký số GOST-II  Thuật toán ký (của ̂ trên thông điệp ): 1. Chọn . 2. Tính , và , nếu quay về bước 1. 3. Tính .
13 4. Tính số nguyên mà có biểu diễn bit là , và xác định . Nếu , thì gán . 5. Tính ; nếu , quay lại bước 1. 6. Trả về chữ ký .  Thuật toán xác minh: 1. Xác minh có thuộc hay không. 2. Tính . 3. Tính số nguyên mà có biểu diễn bit là , và xác định . Nếu , thì gán . 4. Tính . 5. Tính và . 6. Tính và tính . 7. Chữ ký được xác minh chỉ khi . GOST-II cũng an toàn EUF-CMA với lập luận tương tự GOST-I. Mệnh đề 2.6. Chúng ta xem xét một kẻ tấn công đối với một lược đồ chữ ký GOST-II, và cũng giả sử rằng có khả năng thực hiện môt giả mạo tồn tại dưới một tấn công lựa chọn thông điệp thích nghi với xác suất sau truy vấn tới hàm , thì người ta có thể giải bài toán logarit rời rạc trong bằng cách sử dụng lần lặp của với xác suất lớn hơn . 2.2.3. Đánh giá hiệu năng của GOST-I và GOST-II Xét về mặt lý thuyết, các khía cạnh so sánh GOST-I và GOST-II so với GOST R34.10-2012 được thể hiện thông qua Bảng 2.1. Ở đó, ký hiệu và là thời gian tạo và xác minh chữ ký trong lược đồ GOST R 34.10-2012; là chênh lệch thời gian giữa các phép toán băm dạng và ; sẽ là thời gian chênh lệch giữa các phép toán dạng và phép toán . Vì những chênh lệch này trên thực tế là tương đối nhỏ nên có thể suy ra hiệu năng tương đương giữa các đề xuất so với GOST R34.10-2012.
14 Bảng 2.1. So sánh lý thuyết GOST-I, GOST-II với GOST R 34.10-2012. Bảng 2.2. Kết quả thực nghiệm GOST-I, GOST-II và GOST R 34.10-2012 Thời gian ký Thời gian xác minh (1000 thông điệp) (1000 cặp) 1,743 giây 1,870 giây GOST R 34.10-2012 (TB: 0.001743) (TB: 0.001870 giây) 1,776 giây 1,886 giây GOST-I (TB: 0.001776) (TB: 0.001886 giây) 1,748 giây 1,873 giây GOST-II (TB: 0.001748) (TB: 0.001873 giây) Xét về mặt thực nghiệm, tác giả luận án đã thực hiện cài đặt các lược đồ chữ ký số GOST R 34.10-2012, GOST-I, GOST-II, và thu được kết quả là thời gian chạy tương đương giữa chúng (xem Bảng 2.2). 2.3. Đề xuất lƣợc đồ chữ ký bó an toàn Đối với các giao thức trao đổi khóa được thiết lập giữa một máy chủ và nhiều máy khách nói chung, một yêu cầu quan trong đặt ra là máy chủ có thể thực hiện nhiều yêu cầu của khách cùng lúc. Do đó, đối với các giao thức trao đổi khóa có xác thực dựa trên chữ ký, để thực hiện mong muốn trên điều chúng ta có thể nghĩ tới là cải thiện khả năng
15 ký của máy chủ. Chữ ký bó dựa trên cây băm Merkle là một giải pháp như vậy. 2.3.1. Chữ ký bó dựa trên cây băm Merkle Vào năm 1999, Pavlovski và Boyd đã đề xuất một kỹ thuật chuyển đổi hiệu quả một lược đồ chữ ký khóa công khai bất kỳ thành một lược đồ chữ ký bó bằng cách sử dụng cây băm Merkle. Các chữ ký bó của họ tươn ứn với bó , ở đó với à chữ ký của ược đồ cho giá trị băm gốc của cây băm Merkle với các lá và một đường dẫn xác thực (chuỗi băm) nối tới . Quá trình xác minh chữ ký bao gồm hai bước: (1) tính lại đầu vào cho chữ ký thông thường nhờ thông điệp và đường dẫn , và (2) xác minh chữ ký đối với giá trị nhận được. A. Ansper và các cộng sự đã đề xuất ứng dụng lược đồ kể trên như một giải pháp ký số hiệu quả cho hệ thống X-Road, mà được sử dụng như trục liên thông dữ liệu ở Estonia. Bảng 2.3. So Sánh thực nghiệm giữa một số lược đồ chữ ký bó với phiên bản thường của chúng Thời gian ký Thời gian xác minh Tổng (1000 thông điệp) (1000 cặp) thời gian GOST-I 1,776 giây 1,886 giây 3,662 giây Chữ ký bó dựa 0,050 giây 1,938 giây 1,988 giây trên GOST-I GOST-II 1,748 giây 1,873 giây 3,621 giây Chữ ký bó dựa 0,055 giây 1,941 giây 1,996 giây trên GOST-II Độ hiệu quả. Xét về mặt thực nghiệm, lược đồ này đã được cài đặt với các lược đồ cơ sở GOST-I, GOST-II. Kết quả trong Bảng 2.3 cho thấy độ hiệu quả về thời gian chạy của nó so với các lược đồ thông thường. Hạn chế về độ an toàn. Nhược điểm của lược đồ này là nếu cho phép tạo một lượng tùy ý các chữ ký cùng lúc trong mỗi lần ký thì sẽ khiến
16 cho nó không đạt được độ an toàn EUF-CMA (theo Định nghĩa 1.2) ngay cả khi lược đồ chữ ký cơ sở đạt được độ an toàn đó. 2.3.2.Lược đồ chữ ký bó an toàn SBS-01 Với một đồ chữ ký thông thường chúng ta sẽ xây dựng lược đồ chữ ký bó dạng SBS-1 như sau: - Thuật toán sinh khóa: (1) Sử dụng thuật toán để sinh cặp khóa . (2) Thiết lập khóa bí mật và khóa công khai , với tham số là tham số biểu thị độ cao của cây băm mà người dùng cần xây dựng để xây dựng chữ ký bó. - Thuật toán sinh chữ ký: Với đầu vào là danh sách các thông điệp cần ký { }, với , chúng ta thực hiện: (1) Tính , với . (2) Xây dựng cây băm cho phần tử của danh sách { ⏟ }. Giả sử giá trị băm gốc thu được là . (3) Sử dụng thuật toán để tạo chữ ký cho , giả sử chữ ký thu được là . (4) Trích chuỗi băm cho lá đầu tiên trong cây băm , giả sử là . (5) Chữ ký trả về cho có dạng . - Thuật toán kiểm tra chữ ký: Với chữ ký , thông điệp , và khóa công khai , quá trình xác minh chữ ký diễn ra như sau: (1) Kiểm tra kích thước của bằng hay không, nếu khác nhau thì đưa ra chữ ký không hợp lệ. (2) Tính , và khôi phục giá trị từ và chuỗi băm . (3) Sử dụng thuật toán để kiểm tra tính hợp lệ của cặp thông điệp/chữ ký , nếu đúng thì đưa ra chữ ký hợp lệ, ngược lại trả về chữ ký không hợp lệ. Chúng ta sẽ gọi phép xây dựng từ sang ở trên là , nghĩa là .
17 Mệnh đề 2.7. Nếu một lược đồ chữ ký là an toàn EUF-CMA (theo Định nghĩa 1.2) và hàm băm được mô hình hóa như một bộ tiên tri ngẫu nhiên, thì lược đồ chữ ký bó cũng an toàn EUF-CMA (theo Định nghĩa 1.2). 2.3.3.Lược đồ chữ ký bó an toàn SBS-02 Nhược điểm của SBS-01 là kém linh động vì chỉ phù hợp cho những ứng dụng với số lượng yêu cầu đến là ổn định. Với một đồ chữ ký thông thường chúng ta sẽ xây dựng lược đồ chữ ký bó dạng SBS-02 như sau: - Thuật toán sinh khóa: (1) Sử dụng thuật toán để sinh cặp khóa . (2) Thiết lập khóa bí mật và khóa công khai . - Thuật toán sinh chữ ký: Với đầu vào là danh sách các thông điệp cần ký { }, chúng ta thực hiện: (1) Tính , với . (2) Xây dựng cây băm cho danh sách { }. Giả sử giá trị băm gốc của cây băm này là . (3) Tìm sao cho là số nguyên nhỏ nhất thỏa mãn . (4) Sử dụng thuật toán để tạo chữ ký cho thông điệp , giả sử chữ ký thu được là . (5) Trích chuỗi băm cho lá đầu tiên trong cây băm , giả sử là . (6) Chữ ký trả về cho có dạng . - Thuật toán kiểm tra chữ ký: Với chữ ký , thông điệp , và khóa công khai , quá trình xác minh chữ ký diễn ra như sau: (1) Tính kích thước của chuỗi băm , giả sử nó bằng . (2) Tính , và khôi phục giá trị từ và chuỗi băm . (3) Sử dụng thuật toán để kiểm tra tính hợp lệ của cặp thông điệp/chữ ký , nếu đúng thì đưa ra chữ ký hợp lệ, ngược lại trả về chữ ký không hợp lệ.