Chương 5: Các hệ mật khoá công khai khác

Trong chương này ta sẽ xem xét một số hệ mật khoá công khai khác. Hệ mật Elgamal dựa trên bài toán logarithm rời rạc là bài toán được dùng nhiều trong nhiều thủ tục mật mã. Bởi vậy ta sẽ dành nhiều thời gian để thảo luận về bài toán quan trọng này. ở các phần sau sẽ xem xét sơ lược một số hệ mật khoá công khai quan trọng khác bao gồm các hệ thoóng loại Elgamal dựa trên các trường hữu hạn và các đường cong elliptic, hệ mật xếp ba lô Merkle-Helman và hệ mật McElice....
Nội dung trích xuất từ tài liệu:
Chương 5: Các hệ mật khoá công khai khác Chương 5 Các hệ mật khoá công khai khác Trong chương này ta sẽ xem xét một số hệ mật khoá công khai khác. Hệ mật Elgamal dựa trên bài toán logarithm rời rạc là bài toán được dùng nhiều trong nhiều thủ tục mật mã. Bởi vậy ta sẽ dành nhiều thời gian để thảo luận về bài toán quan trọng này. ở các phần sau sẽ xem xét sơ lược một số hệ mật khoá công khai quan trọng khác bao gồm các hệ thoóng loại Elgamal dựa trên các trường hữu hạn và các đường cong elliptic, hệ mật xếp ba lô Merkle-Helman và hệ mật McElice. 5.1. Hệ mật Elgamal và các logarithm rời rạc. Hệ mật Elgamal được xây dựng trên bài toán logảithm rời rạc . Chúng ta sẽ bắt đầu băng việc mô tả bài toán bài khi thiết lập môi trường hữu hạn Zp, p là số nguyên tố ( hình 5.1) ( Nhớ lại rằng nhóm nhân Z p* là nhóm cyclic và phần tử sinh của Zp* được gọi là phần tử nguyên thuỷ). Bài toán logarithm rời rạc trong Zp là đối tượng trong nhiều công trình nghiên cứu và được xem là bài toán khó nếu p được chọn cẩn thận. Cụ thể không có một thuật toán thời gian đa thức nào cho bài toán logarithm rời rạc. Để gây khó khăn cho các phương pháp tấn công đã biết p phải có ít nhất 150 chữ số và (p-1) phải có ít nhất một thừa số nguyên tố lớn. Lợi thế của bài toán logarithm rời rạc trong xây dượng hệ mật là khó tìm được các logarithm rời rạc ,song bài toán ngược lấy luỹ thừa lại có thể tính toán hiệu quả theo thuật toán bình phương và nhân. Nói cách khác , luỹ thừa theo modulo p là hàm một chiều với các số nguyên tố p thích hợp. Elgamal đã phát triển một hệ mật khoá công khai dựa trên bài toán logarithm rời rạc. Hệ thống này được trình bày trên hình 5.2. Hệ mật này là một hệ không tất định vì bản mã phụ thuộc vào cả bản rõ x lẫn giá trị ngẫu nhiên k do Alice chọn. Bởi vậy, sẽ có nhiều bản mã được mã từ cùng bản rõ. Hình 2.6 Bài toán logarithm rời rạc trong Zp Đặc trương của bài toán: I = (p,α,β) trong đó p là số nguyên tố, α ∈ Zp là phần tử nguyên thuỷ , β ∈ Zp* Mục tiêu:Hãy tìm một số nguyên duy nhất a, 0 ≤ a ≤ p-2 sao cho: α a ≡ β (mod p) Hình 2.7 Hệ mật khoá công khai Elgamal trong Zp* Cho p là số nguyên tố sao cho bài toán logarithm rời rạc trong Zp là khó giải. Cho α ∈ Zp* là phần tử nguyên thuỷ.Giả sử P = Zp* , C = Zp* × Zp* . Ta định nghĩa: K = {(p, α,a,β): β ≡ α a (mod p)} Các giá trị p, α,β được công khai, còn a giữ kín Với K = (p, α,a,β) và một số ngẫu nhiên bí mật k ∈ Zp-1, ta xác định: ek (x,k) = (y1 ,y2 ) trong đó y1 = αk mod p y2 = xβ k mod p Sau đây sẽ nmô tả sơ lược cách làm việc của hệ mật Elgamal .Bản rõ x được che dấu bằng cách nhân nó với β k để tạo y2 . Giá trị α k cũng được gửi đi như một phần của bản mã. Bob -người biết số mũ bí mật a có thể tính được β k từ α k . Sau đó anh ta sẽ tháo mặt nạ bằng cách chia y2 cho β k để thu được x. Ví dụ 5.1 Cho p = 2579, α = 2, a = 765. Khi đó β = 2765 mod 2579 = 949 Bây giờ ta giả sử Alice muốn gửi thông báo x = 1299 tới Bob. Giả sử số ngẫu nhiên k mà cô chọn là k = 853. Sau đó cô ta tính y1 = 2853 mod 2579 = 435 y2 = 1299 × 949853 mod 2579 = 2396 Khi đó Bob thu được bản mã y = (435,2396), anh ta tính x = 2396 × (435765)-1 mod 2579 = 1299 Đó chính là bản rõ mà Alice đã mã hoá. 5.1.1. Các thuật toán cho bài toán logarithm rời rạc. Trong phần này ta xem rằng p là số nguyên tố, α là phần tử nguyên thuỷ theo modulo p. Ta thấy rằng p và α là các số cố định. Khi đó bài toán logarithm rời rạc có thể được phát biểu dưới dạng sau: tìm một số mũ a duy nhất, 0 ≤ a ≤ p-2 sao cho αa ≡β (mod p), với β ∈ Zp* cho trước. Rõ ràng là bài toán logarithm rời rạc (DL) có thể giải bằng một phép tìm kiếm vét cạn với thời gian cỡ O(p) và không gian cỡ O(1) ( bỏ qua các thừa số logarithm). Bằng cách tính toán tất cả các giá trị αa có thể và sắp xếp các cặp có thứ tự (a, αa mod p) có lưu ý đến các tạo độ thứ hai của chúng, ta có thể giải bài toán DL với thời gian cỡ O(1) bằng O(p) phép tính toán trước và O(p) bộ nhớ ( vẫn bỏ qua các thừa số logarithm). Thuật toán không tầm thường đầu tiên mà chúng ta sẽ mô tả là thuật toán tối ưu hoá thời gian - bộ nhớ của Shanks. Thuật toán Shanks Hình 5.3. Thuật toán Shanks cho bài toán DL. 1.Tính α mj mod p, 0 ≤ j ≤ m-1 2.Sắp xếp m cặp thứ tự ( j,αmj mod p) có lưu ý tới các tạo độ thứ hai của các cặp này, ta sẽ thu được một danh sách L1 3.Tính βα -i mod p, 0 ≤ i ≤ m-1 4.Sắp xếp m cặp thứ tự (i, βα -i mod p) có lưu ý tới các toạ độ thứ hai của các cặp được sắp này, ta sẽ thu được một danh sách L2 5.Tìm một cặp (j,y) ∈ L1 và một cặp (i,y) ∈ L2 ( tức là một cặp có tạo độ thứ hai như nhau). 6.Xác định logαβ = mj + i mod (p-1) 7. - Nếu cần, các bước 1 và 2 có thể tính toán trước ( tuy nhiên, điều này không ảnh hưởng tới thời gian chạy tiệm cận) - Tiếp theo cần để ý là nếu (j,y) ∈ L1 và (i,y) ∈ L2 thì αmj = y = βα -i Bởi vậy α mj+i = β như mong muốn. Ngược lại, đối với β bất kì ta có thể viết logαβ = mj+i trong đó 0 ≤ j,i ≤ m-1. Vì thế phép tìm kiếm ở bước 5 chắc chắn thành công. Có thể áp dụng thuật toán này chạy với thời gian O(m) và với bộ nhớ cỡ O(m) ( bỏ qua các thừa số logarithm). Chú ý là bước 5 có thể thực hiện một cách ( đồng thời ) qua từng danh sách L1 và L2. Sau đây là một ví dụ nhỏ để minh hoạ. Ví dụ 5.2. Giả sử p = 809 và ta phải tìm log3525. Ta có α = 3, β = 525 và m = √808 ...