Tóm tắt Luận án Tiến sĩ Toán học: Nghiên cứu phát triển hệ mật mã khóa công khai dựa trên bài toán logarit rời rạc và phân tích số

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

Thêm vào BST

Báo xấu

3
lượt xem 0
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 hệ mật mã khóa công khai dựa trên bài toán logarit rời rạc và phân tích số" được nghiên cứu với mục tiêu: Nhằm đảm bảo an toàn, hiệu suất cao đề xuất phát triển mới 01 hệ mật; Các giao thức trao đổi khóa được đề xuất chỉ sử dụng mã hóa mà không sử dụng phương pháp ký rồi mã hóa (signature-then-encryption) hoặc ký và mã hóa đồng thời (signcryption) nhằm giảm độ phức tạp của giao thức và giảm kích thước của thông điệp ban đầu nhưng vẫn đảm bảo tính bảo mật của cả mã hóa và chữ ký số: bảo mật, toàn vẹn, không thể chỉnh sửa và chống chối từ.

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 hệ mật mã khóa công khai dựa trên bài toán logarit rời rạc và phân tích số

1 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Ự NGUYỄN VĨNH THÁI NGHIÊN CỨU PHÁT TRIỂN HỆ MẬT MÃ KHÓA CÔNG KHAI DỰA TRÊN BÀI TOÁN LOGARIT RỜI RẠC VÀ PHÂN TÍCH SỐ 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 - 2025
2 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: 1. PGS. TS Bạch Nhật Hồng 2. TS Lưu Hồng Dũng Phản biện 1: PGS. TS Đỗ Trung Tuấn Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Hà Nội Phản biện 2: PGS. TS Trần Cao Trưởng Học viện Kỹ thuật quân sự Phản biện 3: TS Thái Trung Kiên 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á 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 2025 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.
3 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ [CT1] Nguyễn Vĩnh Thái, Bạch Nhật Hồng, Lưu Hồng Dũng (12/2017), “Phát triển giao thức thiết lập khóa an toàn cho các hệ mã khóa bí mật”, Tạp chí Nghiên cứu khoa học và công nghệ quân sự, trang 193-202. Số đặc san CNTT 12/2017, ISSN 1859- 1043. [CT2] Nguyễn Vĩnh Thái, Lưu Hồng Dũng (12/2018), “Hệ mật khóa công khai dựa trên tính khó của việc giải đồng thời 2 bài toán phân tích số và logarithm rời rạc/khai căn”, Tạp chí Thông tin và Truyền thông: Một số vấn đề chọn lọc về an toàn an ninh thông tin 2018 - TP. Đà Nẵng, ngày 07/12/2018, pp.58-66, ISSN 1859-3550. [CT3] Nguyễn Vĩnh Thái, Lưu Hồng Dũng (4/2019), “Xây dựng giao thức trao đổi khóa an toàn dựa trên tính khó của việc giải đồng thời 2 bài toán logarithm rời rạc và phân tích số/khai căn cho các hệ mật khóa đối xứng”, Tạp chí Nghiên cứu khoa học và công nghệ quân sự, trang 8-15. Số đặc san CNTT 04/2019, ISSN 1859-1043. [CT4] Nguyễn Vĩnh Thái, Lưu Hồng Dũng, “Xây dựng các thuật toán mật mã khóa công khai dựa trên tính khó của việc giải đồng thời 2 bài toán logarithm rời rạc và phân tích số/khai căn”, Tạp chí Nghiên cứu khoa học và công nghệ quân sự, trang 24-32. Số đặc san CNTT 04/2019, ISSN 1859-1043. [CT5] Nguyễn Vĩnh Thái, Lưu Hồng Dũng (4/2019), “Một lược đồ chữ ký xây dựng trên tính khó của việc giải đồng thời 2 bài toán logarithm rời rạc và phân tích số”, Tạp chí Nghiên cứu khoa học và công nghệ quân sự, trang 57-64. Số đặc san CNTT 04/2019, ISSN 1859-1043. [CT6] Nguyễn Vĩnh Thái, Đỗ Anh Tuấn, Lưu Hồng Dũng, Đoàn Thị Bích Ngọc (12/2020), “Giao thức trao đổi khóa an toàn, hiệu quả cho các hệ mật khóa đối xứng”, Tạp chí Nghiên cứu khoa học và công nghệ quân sự, trang 80-86. Số đặc san CNTT 12/2020, ISSN 1859-1043. [CT7] Nguyen Vinh Thai, Đoan Thi Bich Ngoc, Luu Hong Dung (12/2021), “An encryption - authentication algorithms developed from the elgamal cryptosystem”, Journal of Military Science and Technology, pp61-70. Special Issue No.5 12/2021, ISSN 1859-1043.
1
1 MỞ ĐẦU 1. Tính cấp thiết của đề tài luận án Nội dung của khóa công khai không cần phải giữ bí mật như đối với khóa bí mật trong các phương pháp mã hóa khóa bí mật. Sử dụng khóa công khai có thể thiết lập một quy trình an toàn để trao đổi khóa bí mật được sử dụng trong hệ thống mã hóa bí mật. Mã hóa khóa công khai có thể được sử dụng để bảo mật, xác thực, hoặc cả hai. Việc nghiên cứu, xây dựng riêng những hệ mật mới đáp ứng được mục tiêu, yêu cầu về an toàn, bảo mật thông tin, liên thông các quốc gia và ứng dụng hiệu quả trong lĩnh vực quốc phòng an ninh trong tình hình mới là cần thiết và thực sự cấp thiết. 2. Mục tiêu nghiên cứu Luận án nghiên cứu, xây dựng hệ mật khóa công khai mới với mục tiêu sau: - Nhằm đảm bảo an toàn, hiệu suất cao đề xuất phát triển mới 01 hệ mật bao gồm: 01 lược đồ chữ ký số, 01 thuật toán mã hóa-xác thực, 01 giao thức trao đổi khóa từ cách hệ mật Elgamal và các thuật toán chữ ký số được xây dựng dựa trên tính khó của bài toán DLP. - Nhằm nâng cao độ an toàn của hệ mật đề xuất phát triển mới 01 hệ mật bao gồm: 01 lược đồ chữ ký số, 01 thuật toán mã hóa, 01 thuật toán mã hóa-xác thực và 01 giao thức trao đổi khóa. Đề xuất xây dựng dựa trên tính khó của việc giải đồng thời 2 bài toán khó bài toán logarit rời rạc và phân tích số. - Các giao thức trao đổi khóa được đề xuất chỉ sử dụng mã hóa mà không sử dụng phương pháp ký rồi mã hóa (signature-then-encryption) hoặc ký và mã hóa đồng thời (signcryption) nhằm giảm độ phức tạp của giao thức và giảm kích thước của thông điệp ban đầu nhưng vẫn đảm bảo tính bảo mật của cả mã hóa và chữ ký số: bảo mật, toàn vẹn, không thể chỉnh sửa và chống chối từ.
2 3. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của luận án gồm: a) Cơ sở toán học của hệ mật khóa công khai b) Nghiên cứu nguyên lý xây dựng hệ mật khoá công khai và một số hệ mật khoá công khai điển hình như: RSA, ElGamal. Phạm vi nghiên cứu của luận án gồm: cách thức hình thành tham số hệ thống và khóa; các chuẩn chữ ký số DSS của Mỹ và GOST của Nga; giao thức trao đổi khóa an toàn; cơ sở toán học của các bài toán khó như bài toán logarit rời rạc, phân tích một số nguyên lớn ra thừa số nguyên tố, bài toán khai căn. 4. Nội dung nghiên cứu • Phương pháp xây dựng tham số dùng chung cho hệ thống (𝑝, 𝑞, 𝑔), xây dựng khóa cho mỗi thực thể cuối gồm khóa bí mật và khóa công khai. • Các số lược đồ chữ ký số phổ biến như: DSA, KCDSA, GOST R 34.10-94, SDSA; Pointcheval/Vaudenay. • Các lược đồ chữ ký số RSA, Rabin, Schnorr. • Các họ giao thức trao đổi khóa có xác thực dựa trên phương pháp ký và mã đồng thời. 5. Phương pháp nghiên cứu • Phương pháp phân tích và tổng hợp lý thuyết. • Phương pháp toán học. • Phương pháp mô hình hóa. • 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 xây dựng hệ mật khóa công khai đạ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 (với hệ
3 mật xây dựng dựa trên tính khó của bài toán DLP), an ninh quốc phòng và hệ thống chính trị (với hệ mật xây dựng dựa trên tính khó của 02 bài toán DLP và IFP) thúc đẩy xây dựng Chính phủ điện tử. 7. Bố cục của luận án Luận án được bố cục bao gồm phần Mở đầu, 3 chương nội dung nghiên cứu chính và phần Kết luận. Chương 1 TỔNG QUAN VỀ VẤN HỆ MẬT KHÓA CÔNG KHAI 1.1 Hệ mật Trình bày hệ mật khóa bí mật và hệ mật khóa công khai. 1.2 Bài toán phân tích số, khai căn và hệ mật RSA 1.2.1 Bài toán phân tích số 1.2.2 Hệ mật RSA 1.2.3 Bài toán khai căn trên 𝒁 𝒏 1.2.4 Tấn công hệ mật RSA 1.3 Bài toán logarit rời rạc và hệ mật ElGamal 1.3.1 Bài toán logarit rời rạc trên ℤ 𝒑 - 𝑫𝑳𝑷(𝒑,𝒈) 1.3.2 Hệ mật ElGamal 1.4 Một số lược đồ chữ ký số 1.5 Giao thức trao đổi khóa 1.5.1 Một số khái niệm 1.5.2 Giao thức trao đổi khóa Diffie-Helman 1.5.3 Đánh giá độ an toàn của giao thức DHKE 1.5.4 Một số tính chất an toàn của giao thức trao đổi khóa 1.5.5 Điều kiện phát triển giao thức thiết lập khóa an toàn 1.6 Một số giao thức trao đổi khóa an toàn 1.6.1 Giao thức trao đổi khóa Arazi 1.6.2 Giao thức trao đổi khóa L. Harn 1.6.3 Giao thức trao đổi khóa Phan
4 1.6.4 Một số hướng phát triển giao thức trao đổi khóa 1.7 Đánh giá chung về hướng nghiên cứu 1.7.1 Các công trình liên quan đến lược đồ dựa trên 01 bài toán khó 1.7.2 Các công trình liên quan đến lược đồ dựa trên 02 bài toán khó 1.7.3 Các công trình liên quan đến phát triển giao thức trao đổi khóa 1.8 Yêu cầu hệ mật 1.9 Hướng nghiên cứu của đề tài luận án Hệ mật mới ngoài đề xuất thuật toán hình thành tham số hệ thống, khóa (TT-HT và TT-K) thì luận án đề xuất các thuật toán xây dựng các cấu phần hệ mật theo hai hướng: a) Đối với hướng hệ mật dựa trên bài toán DLP theo chuẩn ISO/IEC 14888-3, đề xuất phát triển hệ mật theo phương pháp của ElGamal, DSA, Schnorr, bao gồm: - Lược đồ chữ ký số (ký TT-K-01 và kiểm tra chữ ký TT-KT-01); - Mã hóa (TT-MH-01), giải mã - xác thực (TT-GM-01); - Giao thức trao đổi khóa (TT-TDK-01). b) Đối với hướng hệ mật dựa trên độ khó của kết hợp 02 bài toán DLP và IFP, đề xuất phát triển hệ mật nhằm nâng cao độ an toàn: - Lược đồ chữ ký số (ký TT-K-02 và kiểm tra chữ ký TT-KT-02); - Mã hóa (TT-MH-02), giải mã - xác thực (TT-GM-02); - Giao thức trao đổi khóa (TT-TDK-02). 1.10 Kết luận Chương 1
5 Chương 2 XÂY DỰNG HỆ MẬT KHÓA CÔNG KHAI DỰA TRÊN TÍNH KHÓ CỦA BÀI TOÁN LOGARIT RỜI RẠC 2.1 Thuật toán sinh tham số hệ thống Các tham số hệ thống 𝑝, 𝑞, 𝑔 thỏa mãn các điều kiện theo chuẩn FIPS PUB 186 - 5 và Special Publication 800-57 Part 1 Revision 5 của NIST về đề xuất cặp khóa sử dụng trong hệ mã logarit rời rạc. 2.2 Thuật toán hình thành khóa Sử dụng phương pháp sinh số nguyên tố ngẫu nhiên theo điều kiện (các số nguyên tố tất định). Các khóa 𝑛, 𝑥, 𝑑, 𝑒 thỏa mãn các điều kiện theo chuẩn FIPS PUB 186 - 5 và Special Publication 800-56B Revision 2 NIST về đề xuất cặp khóa sử dụng trong hệ mã RSA. 2.3 Xây dựng lược đồ chữ ký số 2.3.1 Qui trình ký 2.3.2 Qui trình kiểm tra chữ ký 2.3.3 Thuật toán sinh chữ ký TT-K-01 Theo hướng lược đồ chữ ký số kèm phụ lục thông điệp, đề xuất lược đồ chữ ký số gồm thuật toán sinh chữ ký TT-K-01 và kiểm tra chữ ký TT-KT-01. Lược đồ đã được công bố tại công trình [CT7] với khóa bí mật 𝑥 được chọn khoảng (1, 𝑞). Tính khóa công khai theo: −1 𝑦 = 𝑔−(𝑥) 𝑚𝑜𝑑 𝑝 (2.10) Thuật toán TT-K-01. Thuật toán sinh chữ ký Input: 𝑝, 𝑞, 𝑔, 𝑥, 𝑀 - thông điệp cần ký. Output: 𝐸, 𝑆 - chữ ký Bước 1. Chọn ngẫu nhiên giá trị 𝑘 trong khoảng (1, 𝑞) Bước 2. Tính giá trị:
6 𝑅 = 𝑔 𝑘 𝑚𝑜𝑑 𝑝 (2.11) Bước 3. Tính thành phần thứ nhất 𝐸 của chữ ký theo: 𝐸 = 𝐻(𝑀‖𝑅) 𝑚𝑜𝑑 𝑞 (2.12) Bước 4. Tính thành phần thứ hai 𝑆 của chữ ký theo: 𝑆 = 𝑥 × (𝐸 − 𝑘) 𝑚𝑜𝑑 𝑞 (2.13) Kiểm tra, nếu 𝐸 = 0 hoặc 𝑆 = 0 thì quay lại Bước 1 để tính một giá trị mới của 𝑘 và chữ ký phải được tính toán lại (nhưng rất khó để 𝐸 = 0 hoặc 𝑆 = 0 nếu chữ ký được tạo đúng). 2.3.4 Thuật toán kiểm tra chữ ký TT-KT-01 Thuật toán TT-KT-01. Thuật toán kiểm tra chữ ký Input: 𝑝, 𝑞, 𝑔, 𝑦, (𝐸, 𝑆) - chữ ký cần kiểm tra. Output: (𝐸, 𝑆) = true/false Bước 1. Tính giá trị: 𝑅 = (𝑦) 𝑆 × (𝑔) 𝐸 𝑚𝑜𝑑 𝑝 Bước 2. Tính giá trị: 𝐸 = 𝐻(𝑀‖𝑅) Bước 3. Nếu: 𝐸 = 𝐸 thì: (𝐸, 𝑆) = true, ngược lại: (𝐸, 𝑆) = false Người xác minh sẽ kiểm tra các điều kiện sau: - 0 < 𝑆 < 𝑞; - Nếu độ dài của giá trị 𝑙 𝐻 không lớn hơn 𝑙 𝑞 , độ dài bit của 𝐸 bằng độ dài bit đầu ra của hàm băm 𝑙 𝐻 được sử dụng; - Nếu độ dài của giá trị 𝑙 𝐻 lớn hơn 𝑙 𝑞 , độ dài bit của 𝐸 lớn bằng 𝑙 𝑞 . Nếu bất kỳ điều kiện nào ở trên không đúng, chữ ký sẽ bị từ chối. 2.3.5 Tính đúng đắn của lược đồ chữ ký số Chữ ký (𝐸, 𝑆) được sinh bởi Thuật toán TT-K-01, 𝐸 được tạo bởi Thuật toán TT-KT-01 thì điều cần chứng minh ở đây là: 𝐸 = 𝐸. Thật vậy, do: 𝑅 = (𝑦) 𝑆 × (𝑔) 𝐸 𝑚𝑜𝑑 𝑝 −1 𝑥×(𝐸−𝑘) 𝑚𝑜𝑑 𝑞 = (𝑔−(𝑥) 𝑚𝑜𝑑 𝑝) × (𝑔) 𝐸 𝑚𝑜𝑑 𝑝 𝑥×(𝐸−𝑘) −(𝑥)−1 = (𝑔 𝑚𝑜𝑑 𝑝) × (𝑔) 𝐸 𝑚𝑜𝑑 𝑝
7 −1 × = (𝑔)−(𝑥) 𝑥 ×(𝐸−𝑘) × (𝑔) 𝐸 𝑚𝑜𝑑 𝑝 = 𝑔 𝑘 𝑚𝑜𝑑 𝑝 = 𝑅 Suy ra điều cần chứng minh: 𝐸 = 𝐻(𝑀‖𝑅) = 𝐻(𝑀‖𝑅) = 𝐸. 2.3.6 Độ an toàn của lược đồ chữ ký số a) Tấn công khóa bí mật b) Tấn công giả mạo chữ ký c) Xác thực công khai 2.3.7 Hiệu quả thực hiện a) Kích thước chữ ký Bảng 2.3. So sánh độ dài khóa, chữ ký của các lược đồ Tính theo bits DSA GOST KCDSA Pointcheval/ SDSA Lược đồ R34- Vaudenay của 10.94 Luận án Độ Ký 𝑙𝑞 𝑙𝑞 𝑙𝑞 𝑙𝑞 𝑙𝑞 𝑙𝑞 dài Kiểm 𝑙𝑝 𝑙𝑝 𝑙𝑝 𝑙𝑝 𝑙𝑝 𝑙𝑝 khóa tra Độ dài chữ ký 2𝑙 𝑞 𝑙𝐻+ 𝑙𝑞 𝑙𝐻+ 𝑙𝑞 2𝑙 𝑞 𝑙𝐻 𝑙𝐻+ 𝑙𝑞 + 𝑙𝑞 Với cùng một bộ tham số (𝑝, 𝑞) thì kích thước chữ ký do lược đồ tạo ra ở đây với các chuẩn chữ ký số tạo ra là tương đương. b) Chi phí thực hiện Bảng 2.4. Chi phí thực hiện của các lược đồ chữ ký dựa trên DLP Texp Tmul Tinv Th K KT K KT K KT K KT DSA 1 2 2 3 1 1 1 1 GOST R34-10.94 1 3 3 2 0 0 1 1 KCDSA 1 2 2 1 0 0 1 1 Lược đồ đề xuất 1 2 1 1 0 0 1 1 Từ so sánh tại Bảng 2.4 cho thấy lược đồ đề xuất có chi phí thực hiện thấp nhất, thấp hơn cả lược đồ KCDSA.
8 2.4 Thuật toán mã hóa, giải mã - xác thực dựa trên bài toán logarit rời rạc 2.4.1 Thuật toán mã hóa TT-MH-01 Thuật toán TT-MH-01. Thuật toán mã hóa Input: 𝑝, 𝑞, 𝑔, 𝑥 𝐴 , 𝑦 𝐵 , 𝑀 - bản rõ. Output: (𝐶, 𝐸, 𝑆) - bản mã Bước 1. Chọn ngẫu nhiên giá trị k trong khoảng (1, 𝑞). Bước 2. Mã hóa thông điệp M theo: 𝐶 = 𝑀 × (𝑦 𝐵 ) 𝑘 𝑚𝑜𝑑 𝑝 Ở đó: (𝑥 𝐵 , 𝑦 𝐵 ) là khóa bí mật/công khai của người nhận B tính theo −1 (2.10): 𝑦 𝐵 = 𝑔−(𝑥 𝐵 ) 𝑚𝑜𝑑 𝑝. Bước 3. Tính giá trị 𝑅 theo: 𝑅 = 𝑔 𝑘 𝑚𝑜𝑑 𝑝 (2.15) Bước 4. Tính thành phần thứ nhất theo: 𝐸 = 𝐻(𝑀‖𝑅) 𝑚𝑜𝑑 𝑞 (2.16) Bước 4. Tính thành phần thứ hai theo: 𝑆 = 𝑥 𝐴 × (𝐸 − 𝑘) 𝑚𝑜𝑑 𝑞 (2.17) Bản mã gửi đi bao gồm (𝐶, 𝐸, 𝑆). 2.4.2 Thuật toán giải mã - xác thực TT-GM-01 Thuật toán TT-GM-01. Thuật toán giải mã - xác thực Input: 𝑝, 𝑞, 𝑔, 𝑥 𝐵 , 𝑦 𝐴 , (𝐶, 𝐸, 𝑆) Output: 𝑀 Bước 1. Tính giá trị: 𝑅 = (𝑦 𝐴 ) 𝑆 × (𝑔) 𝐸 𝑚𝑜𝑑 𝑝 Bước 2. Tính giá trị: 𝑤 = (𝑥 𝐵 )−1 𝑚𝑜𝑑 𝑞 Bước 3. Tính giá trị: 𝑈 = (𝑅) 𝑤 𝑚𝑜𝑑 𝑞 Bước 4. Giải mã theo: 𝑀 = 𝐶 × 𝑈 𝑚𝑜𝑑 𝑝 Bước 5: Tính giá trị: 𝐸 = 𝐻(𝑀‖𝑅) Bước 6. Nếu 𝐸 = 𝐸 thì 𝑀 = 𝑀 và do A gửi tới.
9 2.4.3 Tính đúng đắn của thuật toán TT-MH-01; TT-GM-01 Ta có: 𝑅 = (𝑦 𝐴 ) 𝑆 × (𝑔) 𝐸 𝑚𝑜𝑑 𝑝 −1 × = (𝑔)−(𝑥 𝐴 ) 𝑥 𝐴 ×(𝐸−𝑘) 𝑚𝑜𝑑 𝑞 × (𝑔) 𝐸 𝑚𝑜𝑑 𝑝 = 𝑔 𝑘 𝑚𝑜𝑑 𝑝 = 𝑅 Và: 𝑤 = (𝑥 𝐵 )−1 𝑚𝑜𝑑 𝑞 𝑤 (𝑥 𝐵 )−1 Nên 𝑈 = (𝑅) 𝑚𝑜𝑑 𝑞 = (𝑔 𝑘 𝑚𝑜𝑑 𝑝) 𝑚𝑜𝑑 𝑝 = 𝑘(𝑥 𝐵 )−1 = 𝑔 𝑚𝑜𝑑 𝑝 Mặt khác: −1 𝑘 𝐶 = 𝑀 × (𝑦 𝐵 ) 𝑘 𝑚𝑜𝑑 𝑝 = 𝑀 × (𝑔−(𝑥 𝐵 ) 𝑚𝑜𝑑 𝑝) 𝑚𝑜𝑑 𝑝 −1 = 𝑀 × 𝑔−𝑘.(𝑥 𝐵 ) 𝑚𝑜𝑑 𝑝 Suy ra điều cần chứng minh: −1 −1 𝑀 = 𝐶 × 𝑈 𝑚𝑜𝑑 𝑝 = 𝑀 × 𝑔−𝑘.(𝑥 𝐵 ) × 𝑔 𝑘(𝑥 𝐵 ) 𝑚𝑜𝑑 𝑝 = 𝑀. 2.4.4 Độ an toàn và hiệu quả a) Độ an toàn về khóa: tương tự RSA, GOST. b) Khả năng chống giả mạo. 2.5 Xây dựng giao thức trao đổi khóa Đề xuất xây dựng giao thức trao đổi khóa an toàn cho các hệ mật khóa đối xứng trên cơ sở phát triển giao thức DHKE nhưng đảm bảo xác thực giữa hai bên tham gia giao thức. 2.5.1 Giao thức trao đổi khóa TT-TDK-01 Giao thức TT-TDK-01 cũng như chứng minh tính đúng đắn, độ an toàn của giao thức đã được công bố tại các công trình [CT1], [CT6] như sau: Tham số hệ thống và khóa của A, B được hình thành theo TT-HT và TT-K, ở đó: 𝑦 𝐴 = 𝑔 𝑥 𝐴 𝑚𝑜𝑑 𝑝 (2.19) 𝑥𝐵 và: 𝑦𝐵 = 𝑔 𝑚𝑜𝑑 𝑝 (2.20)
10 Bảng 2.6 được sử dụng để mô tả trao đổi khóa bí mật chung/chia sẻ giữa A và B như sau: Bảng 2.6. Giao thức trao đổi khóa TT-TDK-01 A B Bước 1 - Chọn ngẫu nhiên một giá trị 𝑘 𝐴 : - Chọn ngẫu nhiên một giá trị 𝑘 𝐵 : 0 < 𝑘𝐴 < 𝑞 0< 𝑘𝐵 < 𝑞 - Tính: 𝑅 𝐴 = 𝑔 𝑘 𝐴 𝑚𝑜𝑑 𝑝 (2.21) - Tính: 𝑅 𝐵 = 𝑔 𝑘 𝐵 𝑚𝑜𝑑 𝑝 (2.22) - Tính: 𝑆 𝐴 = (𝑦 𝐵 ) 𝑥 𝐴 𝑚𝑜𝑑 𝑝 (2.23) - Tính: 𝑆 𝐵 = (𝑦 𝐴 ) 𝑥 𝐵 𝑚𝑜𝑑 𝑝 (2.24) - Tính: 𝐸 𝐴1 = 𝐻(𝑅 𝐴 ‖𝑆 𝐴 ) (2.25) - Tính: 𝐸 𝐵1 = 𝐻(𝑅 𝐵 ‖𝑆 𝐵 ) (2.26) 𝑅 𝐴 , 𝐸 𝐴1 𝑅 𝐵 , 𝐸 𝐵1 Bước 2 - Tính: ̅ 𝐵1 =𝐻(𝑅 𝐵 ‖𝑆 𝐴 ) 𝐸 (2.27) - Tính: ̅ 𝐴1 =𝐻(𝑅 𝐴 ‖𝑆 𝐵 ) 𝐸 (2.28) - Kiểm tra nếu ̅ 𝐵1 =𝐸 𝐵1 thì thực hiện 𝐸 - Kiểm tra nếu ̅ 𝐴1 =𝐸 𝐴1 thì thực hiện 𝐸 tiếp, nếu ̅ 𝐵1 ≠ 𝐸 𝐵1 thì hủy giao thức. 𝐸 tiếp, nếu ̅ 𝐴1 ≠ 𝐸 𝐴1 thì hủy giao thức. 𝐸 - Tính khóa bí mật chia sẻ với B: - Tính khóa bí mật chia sẻ với A: 𝐾 𝐴𝐵 = (𝑅 𝐵 ) 𝑘 𝐴 𝑚𝑜𝑑 𝑝 (2.29) 𝐾 𝐵𝐴 = (𝑅 𝐴 ) 𝑘 𝐵 𝑚𝑜𝑑 𝑝 (2.30) - Tính: 𝐸 𝐴2 = 𝐻(𝐾 𝐴𝐵 ‖𝑆 𝐴 ) (2.31) - Tính: 𝐸 𝐵2 = 𝐻(𝐾 𝐵𝐴 ‖𝑆 𝐵 ) (2.32) 𝐸 𝐴2 𝐸 𝐵2 Bước 3 - Kiểm tra nếu 𝐸 𝐵2 = 𝐸 𝐴2 thì A khẳng - Kiểm tra nếu 𝐸 𝐴2 = 𝐸 𝐵2 thì B khẳng định đối tượng tham gia trao đổi khóa định đối tượng tham gia trao đổi khóa là B và B đã thiết lập được khóa bí mật là A và A đã thiết lập được khóa bí mật chia sẻ với A. Giao thức thành công với chia sẻ với B. Giao thức thành công khóa chung là 𝐾 𝐴𝐵 ; nếu 𝐸 𝐵2 ≠ 𝐸 𝐴2 thì với khóa chung là 𝐾 𝐵𝐴 ; nếu 𝐸 𝐴2 ≠ 𝐸 𝐵2 A khẳng định đối tượng tham gia trao thì B khẳng định đối tượng tham gia đổi khóa là giả mạo và hủy khóa đã trao đổi khóa là giả mạo và hủy khóa được tạo ra. đã được tạo ra. 2.5.2 Tính đúng đắn của giao thức TT-TDK-01 Tính đúng đắn của giao thức TT-TDK-01 được chứng minh bằng mệnh đề sau: Cho 𝑝, 𝑞 là các số nguyên tố thỏa mãn: 𝑞|(𝑝 − 1), 𝑛 = 𝑝 × 𝑞, 𝑛 > 𝑝, 𝑝−1 𝛼 ∈ (1, 𝑝), 𝑔 = 𝛼 𝑞 𝑚𝑜𝑑 𝑝, 1 < 𝑥 𝐴 , 𝑥 𝐵 < 𝑞, 𝑦 𝐴 = 𝑔 𝑥 𝐴 𝑚𝑜𝑑 𝑝,
11 𝑦 𝐵 = 𝑔 𝑥 𝐵 𝑚𝑜𝑑 𝑝, 1 < 𝑘 𝐴 , 𝑘 𝐵 < 𝑞, 𝑅 𝐴 = 𝑔 𝑘 𝐴 𝑚𝑜𝑑 𝑝, 𝑅 𝐵 = 𝑔 𝑘 𝐵 𝑚𝑜𝑑 𝑝, 𝑆 𝐴 = (𝑦 𝐵 ) 𝑥 𝐴 𝑚𝑜𝑑 𝑝, 𝐸 𝐴1 = 𝐻(𝑅 𝐴 ‖𝑆 𝐴 ), 𝑆 𝐵 = (𝑦 𝐴 ) 𝑥 𝐵 𝑚𝑜𝑑 𝑝, 𝐸 𝐵1 = 𝐻(𝑅 𝐵 ‖𝑆 𝐵 ) Nếu: ̅ 𝐴1 = 𝐻(𝑅 𝐴 ‖𝑆 𝐵 ), ̅ 𝐵1 = 𝐻(𝑅 𝐵 ‖𝑆 𝐴 ), 𝐾 𝐴𝐵 = (𝑅 𝐵 ) 𝑘 𝐴 𝑚𝑜𝑑 𝑝, 𝐸 𝐸 𝑘𝐵 𝐾 𝐵𝐴 = (𝑅 𝐴 ) 𝑚𝑜𝑑 𝑝, 𝐸 𝐴2 = 𝐻(𝐾 𝐴𝐵 ‖𝑆 𝐴 ), 𝐸 𝐵2 = 𝐻(𝐾 𝐵𝐴 ‖𝑆 𝐵 ) thì: ̅ 𝐴1 = 𝐸 𝐴1 , ̅ 𝐵1 = 𝐸 𝐵1 , 𝐾 𝐴𝐵 =𝐾 𝐵𝐴 và 𝐸 𝐴2 = 𝐸 𝐵2 𝐸 𝐸 Chứng minh: Từ (2.20), (2.23) ta có: 𝑆 𝐴 = (𝑦 𝐵 ) 𝑥 𝐴 𝑚𝑜𝑑 𝑝 = (𝑔 𝑥 𝐵 𝑚𝑜𝑑 𝑝) 𝑥 𝐴 𝑚𝑜𝑑 𝑝 = 𝑔 𝑥 𝐴 .𝑥 𝐵 𝑚𝑜𝑑 𝑝 (2.33) Mặt khác, từ (2.19) và (2.24) ta lại có: 𝑆 𝐵 = (𝑦 𝐴 ) 𝑥 𝐵 𝑚𝑜𝑑 𝑝 = (𝑔 𝑥 𝐴 𝑚𝑜𝑑 𝑝) 𝑥 𝐵 𝑚𝑜𝑑 𝑝 = 𝑔 𝑥 𝐴 .𝑥 𝐵 𝑚𝑜𝑑 𝑝 (2.34) Từ (2.33) và (2.34) suy ra: 𝑆 𝐴 = 𝑆 𝐵 (2.35) Từ (2.25), (2.28) và (2.35) ta có: 𝐸 𝐴1 = 𝐻(𝑅 𝐴 ‖𝑆 𝐴 ) = 𝐻(𝑅 𝐴 ‖𝑆 𝐵 ) = ̅ 𝐴1 𝐸 (2.36) Tương tự, từ (2.26), (2.27) và (2.35) ta cũng có: 𝐸 𝐵1 = 𝐻(𝑅 𝐵 ‖𝑆 𝐵 ) = 𝐻(𝑅 𝐵 ‖𝑆 𝐴 ) = ̅ 𝐵1 𝐸 (2.37) Từ (2.29) và (2.22) ta có: 𝐾 𝐴𝐵 = (𝑅 𝐵 ) 𝑘 𝐴 𝑚𝑜𝑑 𝑝 = (𝑔 𝑘 𝐵 𝑚𝑜𝑑 𝑝) 𝑘 𝐴 𝑚𝑜𝑑 𝑝 = = 𝑔 𝑘 𝐵.𝑘 𝐴 𝑚𝑜𝑑 𝑝 (2.38) Từ (2.30) và (2.21) ta lại có: 𝐾 𝐵𝐴 = (𝑅 𝐴 ) 𝑘 𝐵 𝑚𝑜𝑑 𝑝 = (𝑔 𝑘 𝐴 𝑚𝑜𝑑 𝑝) 𝑘 𝐵 𝑚𝑜𝑑 𝑝 = = 𝑔 𝑘 𝐴 .𝑘 𝐵 𝑚𝑜𝑑 𝑝 (2.39) Từ (2.38) và (2.39) suy ra: 𝐾 𝐴𝐵 = 𝐾 𝐵𝐴 (2.40) Từ (2.31), (2.32), (2.35) và (2.40) suy ra: 𝐸 𝐴2 = 𝐻(𝐾 𝐴𝐵 ‖𝑆 𝐴 ) = 𝐻(𝐾 𝐵𝐴 ‖𝑆 𝐵 ) = 𝐸 𝐵2 (2.41) (2.36), (2.37), (2.40) và (2.41) là những điều cần chứng minh. Như vậy, mệnh đề đã được chứng minh.
12 2.5.3 Độ an toàn của giao thức TT-TDK-01 Giao thức mới đề xuất bảo đảm đầy đủ các tính chất an toàn của một giao thức trao đổi khóa: xác thực thực thể; xác thực khóa hiện; tính an toàn khóa đã biết; tính bí mật về phía trước; tính kháng tấn công UKS; tính kháng tấn công KCI. 2.5.4 Hiệu quả thực hiện của TT-TDK-01 Tổng hợp thời gian thực hiện của giao thức mới đề xuất và của các giao thức trao đổi khóa tích hợp chữ ký số được chỉ ra trong Bảng 2.7 như sau: Bảng 2.7. Thời gian thực hiện của các giao thức trên cơ sở DHKE TT Tên giao thức Tổng thời gian thực hiện 1 Arazi 8Texp + 4Th + 4Tinv + 10Tmul 2 Harn 14Texp + 4Th + 4Tinv + 16Tmul 3 Phan 12Texp + 4Th + 4Tinv + 12Tmul 4 MTA 16.6-01 8Texp + 4Th + 4Tinv + 4Tmul 5 MTA 16.6-02 5Texp + 2Th + 2Tinv + 2Tmul 6 MTA 17.5-03 8Texp + 4Th + 4Tinv + 4Tmul 7 MTA 17.5-04 6Texp + 6Th 8 TT-TDK-01 6Texp + 6Th 2.6 Kết luận Chương 2 Trong chương này, luận án đã trình bày các đề xuất chính liên quan đến thuật toán hình thành tham số hệ thống (TT-HT); hình thành khóa (TT-K); đề xuất hệ mật dựa trên tính khó bài toán logarit rời rạc bao gồm các thuật toán: sinh chữ ký (Thuật toán TT-K-01), kiểm tra chữ ký (Thuật toán TT-KT-01), mã hóa (Thuật toán TT-MH-01), giải mã - xác thực (Thuật toán TT-GM-01), đề xuất các lược đồ này đã được
13 công bố trong công trình [CT7]; trao đổi khóa (Thuật toán TT-TDK- 01) đề xuất này đã được công bố trong các công trình [CT1], [CT6]. Chứng minh tính đúng đắn, độ an toàn của lược đồ chữ ký số mới với các lược đồ DSA, KCDSA và GOST R34-10.94 là tương đương. Qua so sánh tính hiệu quả cho thấy lược đồ chữ ký số mới là tốt nhất. Chương 3 XÂY DỰNG HỆ MẬT KHÓA CÔNG KHAI DỰA TRÊN TÍNH KHÓ CỦA VIỆC GIẢI ĐỒNG THỜI 2 BÀI TOÁN 3.1 Phát triển lược đồ chữ ký số dựa trên hai bài toán khó 3.1.1 Lược đồ Rabin - Schnorr 3.1.2 Lược đồ RSA - Schnorr 3.1.3 Đánh giá 3.2 Xây dựng lược đồ chữ ký số Lược đồ chữ ký số đề xuất bao gồm thuật toán sinh chữ ký (Thuật toán TT-K-02) và kiểm tra chữ ký (Thuật toán TT-KT-02) được công bố tại công trình [CT5], với các tham số hệ thống cũng được hình thành theo TT-HT và khóa hình thành theo TT-K. Các tham số (𝑥1 , 𝑥2 /𝑦) được tính theo (3.1) sau: Chọn giá trị bí mật thứ nhất 𝑥1 trong khoảng (1, 𝑞) và tính 𝑦/𝑥2 : −1 𝑦 = (𝑔)(𝑥1 ) 𝑚𝑜𝑑 𝑝, 𝑥2 = 𝑦 −1 𝑚𝑜𝑑 𝜑(𝑛) (3.1) 3.2.1 Thuật toán sinh chữ ký TT-K-02 Thuật toán TT-K-02. Thuật toán sinh chữ ký Input: p, q, g, 𝜑(𝑛), 𝑥1 , 𝑥2 , 𝑀 - thông điệp cần ký. Output: 𝐸, 𝑆 - chữ ký Bước 1. Chọn ngẫu nhiên giá trị 𝑘 trong khoảng (1, 𝑞) Bước 2. Tính giá trị: 𝑅 = 𝑔 𝑘 𝑚𝑜𝑑 𝑝 (3.2) Bước 3. Tính thành phần thứ nhất 𝐸 của chữ ký theo:
14 𝐸 = 𝐻(𝑀‖𝑅) 𝑚𝑜𝑑 𝑞 (3.3) Bước 4. Tính thành phần thứ hai 𝑆 của chữ ký theo: 𝑆 = ((𝑥1 )−1 × (𝑘 + 𝐸)𝑚𝑜𝑑 𝑞) 𝑥2 𝑚𝑜𝑑 𝑛 (3.4) 3.2.2 Thuật toán kiểm tra chữ ký TT-KT-02 Thuật toán TT-KT-02. Thuật toán kiểm tra chữ ký Input: 𝑝, 𝑞, 𝑔, 𝑦, 𝑛, (𝐸, 𝑆) - chữ ký cần kiểm tra Output: (𝐸, 𝑆) = 𝑇𝑟𝑢𝑒/𝐹𝑎𝑙𝑠𝑒. Bước 1. Tính giá trị B sử dụng khóa bí mật thứ hai để tính 𝑅 theo: ̅ = ((𝑦)(𝑆) 𝑦 𝑚𝑜𝑑 𝑛 × (𝑔)−𝐸 ) 𝑚𝑜𝑑 𝑝 𝑅 (3.5) Bước 2. Tính giá trị: 𝐸 = 𝐻(𝑀‖𝑅) 𝑚𝑜𝑑 𝑞 (3.6) Bước 3. Nếu 𝐸 = 𝐸 thì (𝐸, 𝑆) = true; nếu 𝐸 ≠ 𝐸 thì (𝐸, 𝑆) = false 3.2.3 Tính đúng đắn của lược đồ chữ ký số Điều cần chứng minh đó là: Cho p, q , 𝑝1 , 𝑞1 là các số nguyên tố thỏa mãn: 𝑝−1 𝑞|(𝑝 − 1), 𝑛 = 𝑝1 × 𝑞1 , 𝑛 > 𝑝, 1 < 𝛼 < 𝑝, 𝑔 = 𝛼 𝑞 𝑚𝑜𝑑 𝑝, (𝑥1 )−1 𝜑(𝑛) = (𝑝1 − 1) × (𝑞1 − 1), 1 < 𝑥1 < 𝑞, 𝑦 = 𝑔 𝑚𝑜𝑑 𝑝, 𝑥2 = (𝑦)−1 𝑚𝑜𝑑 𝜑(𝑛), 1 < 𝑘 < 𝜑(𝑛), 𝑅 = 𝑔 𝑘 𝑚𝑜𝑑 𝑝, 𝐻: {0,1}∗ → 𝑍ℎ với 𝑞 < ℎ < 𝑝, 𝐸 = 𝐻(𝑀‖𝑆)𝑚𝑜𝑑 𝑞, 𝑆 = (𝑥1 × (𝑘 + 𝐸) 𝑚𝑜𝑑 𝑞) 𝑥2 𝑚𝑜𝑑 𝑛. 𝑦 Nếu: ̅ = ((𝑦)(𝑆) 𝑚𝑜𝑑 𝑛 × (𝑔)−𝐸 ) 𝑚𝑜𝑑 𝑝, ̅ = 𝐻(𝑀‖𝑅) 𝑚𝑜𝑑 𝑞 thì 𝑅 𝐸 ̅ ̅ = 𝐸. 𝐸 Chứng minh: Thật vậy, từ (3.1), (3.2), (3.4), (3.5) và (3.6) ta có: ̅ = ((𝑦)(𝑆) 𝑦 𝑅 𝑚𝑜𝑑 𝑛 × (𝑔)−𝐸 𝑚𝑜𝑑 𝑛) 𝑚𝑜𝑑 𝑝 −1 ((𝑥1 .(𝑘+𝐸) 𝑚𝑜𝑑 𝑞) 𝑥2 𝑚𝑜𝑑 𝑛) 𝑦 𝑚𝑜𝑑 𝑛 = (((𝑔)(𝑥1) 𝑚𝑜𝑑 𝑝) × (𝑔)−𝐸 ) 𝑚𝑜𝑑 𝑝(3.7) 𝑥1 .(𝑘+𝐸) (𝑥1 )−1 = (((𝑔) 𝑚𝑜𝑑 𝑝) × (𝑔)−𝐸 ) 𝑚𝑜𝑑 𝑝
15 −1 .𝑥 .(𝑘+𝐸) = ((𝑔)(𝑥1 ) 1 × (𝑔)−𝐸 ) 𝑚𝑜𝑑 𝑝 = ((𝑔)(𝑘+𝐸) × (𝑔)−𝐸 ) 𝑚𝑜𝑑 𝑝 = 𝑔 𝑘 𝑚𝑜𝑑 𝑝 = 𝑅 Từ (3.2), (3.6) và (3.7) suy ra điều phải chứng minh: ̅ = 𝐻(𝑀‖𝑅) 𝑚𝑜𝑑 𝑞 = 𝐻(𝑀‖𝑅) 𝑚𝑜𝑑 𝑞 = 𝐸 𝐸 ̅ 3.2.4 Độ an toàn của lược đồ chữ ký số a) Tấn công khóa bí mật b) Tấn công giả mạo chữ ký c) Xác thực công khai 3.2.5 Hiệu quả thực hiện Tính hiệu quả của lược đồ chữ ký có thể đánh giá qua chi phí thực hiện của các thuật toán ký, kiểm tra theo Bảng 3.1 sau: Bảng 3.1. Chi phí thực hiện của các lược đồ dựa trên DLP và IFP Lược đồ Texp Tmul Th Tsr K KT K KT K KT K KT Rabin - Schnorr 1 3 1 1 1 1 1 0 RSA – Schnorr 2 3 1 1 1 1 0 0 WR-Schnorr 2 2 2 1 1 1 0 0 Lược đồ đề xuất 1 1 2 1 1 1 0 0 3.3 Thuật toán mã hóa, giải mã - xác thực dựa trên hai bài toán khó Thuật toán mã hóa và chứng minh tính đúng đắn, độ an toàn của lược đồ đã được NCS công bố tại công trình [CT2], [CT3] như sau: Giả thiết người gửi/mã hóa là A, người nhận/giải mã là B có cặp khóa bí mật/công khai tương ứng là (𝑥1𝐴 , 𝑥2𝐴 /𝑦 𝐴 ) và (𝑥1𝐵 , 𝑥2𝐵 /𝑦 𝐵 ), trong đó: (𝑥1𝐴 , 𝑥1𝐵 ) được chọn ngẫu nhiên trong khoảng (1, 𝑞); (𝑥2𝐴 , 𝑦 𝐴 ) và (𝑥2𝐵 , 𝑦 𝐵 ) được tính theo (3.1) như sau: 𝑦 𝐴 = 𝑔−𝑥1𝐴 𝑚𝑜𝑑 𝑝, 𝑥2𝐴 = (𝑦 𝐴 )−1 𝑚𝑜𝑑 𝜑(𝑛 𝐴 ) (3.9) 𝑦 𝐵 = 𝑔−𝑥1𝐵 𝑚𝑜𝑑 𝑝, 𝑥2𝐵 = (𝑦 𝐵 )−1 𝑚𝑜𝑑 𝜑(𝑛 𝐵 )
16 3.3.1 Thuật toán mã hóa TT-MH-02 Thuật toán TT-MH-02. Thuật toán mã hóa Input: 𝑝, 𝑞 , 𝑔, 𝑥1𝐴 , 𝑥2𝐴 , 𝑛 𝐴 , 𝑛 𝐵 , M. Output: 𝐶, 𝐸, 𝑆. Bước 1. Biểu diễn thông điệp cần mã hóa M → 𝑚 trong khoảng [1, 𝑝 − 1], chọn ngẫu nhiên một giá trị 𝑘 trong khoảng (1, 𝑞) rồi tính thành phần thứ nhất của bản mã: 𝐶 = (𝑚 × (𝑦 𝐵 ) 𝑘 𝑚𝑜𝑑 𝑝) 𝑦 𝐵 𝑚𝑜𝑑 𝑛 𝐵 (3.10) Bước 2. Tính giá trị: 𝑅 = 𝑔 𝑘 𝑚𝑜𝑑 𝑝 (3.11) Bước 3. Tính thành phần thứ hai của bản mã: 𝐸 = 𝐻(𝑀‖𝑅) 𝑚𝑜𝑑 𝑞 (3.12) Bước 4. Tính thành phần thứ ba của bản mã: 𝑆 = ((𝑥1𝐴 )−1 × (𝑘 + 𝐸)𝑚𝑜𝑑 𝑞) 𝑥2𝐴 𝑚𝑜𝑑 𝑛 𝐴 (3.13) Bước 5. Gửi bản mã (𝐶, 𝐸, S) cho người nhận B. 3.3.2 Thuật toán giải mã - xác thực TT-GM-02 Thuật toán TT-GM-02. Thuật toán giải mã - xác thực Input: 𝑝, 𝑞, 𝑔, 𝑥1𝐵 , 𝑥2𝐵 , 𝑛 𝐴 , 𝑦 𝐴 , 𝑛 𝐵 , 𝑦 𝐵 , (𝐶, 𝐸, 𝑆) . Output: 𝑀, (𝐸, 𝑆) = 𝑇𝑟𝑢𝑒/𝐹𝑎𝑙𝑠𝑒. Bước 1. Người nhận sử dụng khóa bí mật thứ hai để tính 𝐶 theo: 𝐶 = (𝐶) 𝑥2𝐵 𝑚𝑜𝑑 𝑛 𝐵 (3.14) Bước 2. Tính giá trị: 𝑆 = (𝑆) 𝑦 𝐴 𝑚𝑜𝑑 𝑛 𝐴 (3.15) 𝑆 −𝐸 và 𝑅 = ((𝑦 𝐴 ) × (𝑔) ) 𝑚𝑜𝑑 𝑝 (3.16) Bước 3. Từ 𝐶, 𝑅 giải mã thông điệp nhận được: 𝑚 = 𝐶 × (𝑅)−𝑥1𝐵 𝑚𝑜𝑑 𝑝 (3.17) Bước 4. Chuyển giá trị 𝑚 thành thông điệp 𝑀 và tính: 𝐸 = 𝐻(𝑀‖𝑅) 𝑚𝑜𝑑 𝑞 (3.18)