›
›

Giáo trình Lý thuyết mật mã - Chương 5: Các hệ mật khoá công khai khác

pdf 42 trang ngocly 180
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Lý thuyết mật mã - Chương 5: Các hệ mật khoá công khai khác", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_ly_thuyet_mat_ma_chuong_5_cac_he_mat_khoa_cong_kh.pdf

Nội dung text: Giáo trình Lý thuyết mật mã - Chương 5: Các hệ mật khoá công khai khác

  1. 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 logarithm 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 Z p đ−ợ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õ.
  2. 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) Ta sẽ xác định số nguyên a bằng log α β 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 ∈ Z p-1, ta xác định: ek (x,k) = (y1 ,y 2 ) trong đó k y1 = α mod p k y2 = x β mod p * với y1 ,y 2 ∈ Zp ta xác định: a -1 dk(y1 ,y 2 ) = y2 (y1 ) mod p Sau đây sẽ mô tả sơ l−ợc cách làm việc của hệ mật Elgamal .Bản rõ x k k đ−ợc "che dấu" bằng cách nhân nó với β để tạo y 2 . Giá trị α 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 k k β từ α . Sau đó anh ta sẽ "tháo mặt nạ" bằng cách chia y 2 cho β để thu đ−ợc x. Ví dụ 5.1
  3. Cho p = 2579, α = 2, a = 765. Khi đó β = 2 765 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 853 y 1 = 2 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 ì (435 765 )-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 a * nhất, 0 ≤ a ≤ p-2 sao cho α ≡β (mod p), với β ∈ Z p 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
  4. 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 L 1 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 L 2 5. Tìm một cặp (j,y) ∈ L 1 và một cặp (i,y) ∈ L 2 ( 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) ∈ L 1 và (i,y) ∈ L 2 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 L 1 và L 2. Sau đây là một ví dụ nhỏ để minh hoạ. Ví dụ 5.2. Giả sử p = 809 và ta phải tìm log 3525. Ta có α = 3, β = 525 và m = √808  = 29. Khi đó:
  5. α29 mod 809 = 99 Tr−ớc tiên tính các cặp đ−ợc sắp (j,99 j mod 809) với 0 ≤ j ≤28. Ta nhận đ−ợc danh sách sau: (0,1) (1,99) (2,93) (3,308) (4,559) (5,329) (6,211) (7,664) (8,207) (9,268) (10,644) (11,654) (12,26) (13,147) (14,800) (15,727) (16,781) (17,464) (18,314) (19,275) (20,582) (21,496) (22,564) (23,15) (24,676) (25,586) (26,575) (27,295) (28,81) Danh sách này sẽ đ−ợc sắp xếp để tạo L 1. Danh sách thứ hai chứa các cặp đ−ợc sắp (i,525 ì(3 i)-1 mod 809), với 0 ≤ i ≤ 28. Danh sách này gồm: (0,525) (1,175) (2,328) (3,379) (4,396) (5,132) (6,44) (7,554) (8,724) (9,511) (10,440) (11,686) (12,768) (13,256) (14,,355) (15,388) (16,399) (17,133) (18,314) (19,644) (20,754) (21,496) (22,564) (23,15) (24,676) (25,356) (26,658) (27,489) (28,163) Sau khi sắp xếp danh sách này, ta có L 2 . Bây giờ nếu xử lý đồng thời qua cả hai danh sách, ta sẽ tìm đ−ợc ( 10,644) trong L 1 và (19,644) trong L 2. Bây giờ ta có thể tính log 3525 = 29 ì10+19 = 309 Có thể kiểm tra thấy rằng quả thực 3 309 ≡ 525 (mod 809). Thuật toán Pohlig - Hellman. Thuật toán tiếp theo mà ta nghiên cứu là thuật toán Pohlig - Hellman. Giả sử pi là số nguyên tố đặc biệt. Giá trị a = log αβ đ−ợc xác định một cách duy ci nhất theo modulo p-1. Tr−ớc hết nhận xét rằng, nếu có thể tính a mod p i với
  6. mỗi i, 1 ≤ i ≤ k, thì có thể tính a mod (p-1) theo định lý phần d− China. Để thực hiện diều đó ta giả sử rằng q là số nguyên tố. p-1 ≡ 0 (mod q c) p-1 ≡ 0 (mod q c+1 ) Ta sẽ chỉ ra cách tính giá trị x = a mod q c 0 ≤ x ≤ q c-1. Ta có thể biểu diễn x theo cơ số q nh− sau: trong đó 0 ≤ a i ≤ q-1 với 0 ≤ i ≤ c-1. Cũng có thể biểu diễn nh− sau: a = x + q cs với s là một số nguyên nào đó. B−ớc đầu tiên của thuật toán tính a 0. Kết quả chính ở đây là: β(p-1)/q ≡ α(p-1)a0/q (mod p) Để thấy rõ điều đó cần chú ý rằng: Điều này đủ để cho thấy: Kết quả này đúng khi và chỉ khi: Tuy nhiên
  7. Đó chính là điều cần chứng minh. Do đó ta sẽ bắt đầu bằng việc tính β(p-1)/q mod p. Nếu β(p-1)/q ≡ 1 (mod p) thì a 0=0. Ng−ợc lại chúng ta sẽ tính liên tiếp các giá trị: γ = α(p-1)/q mod p, γ2 mod p,. . ., cho tới γi ≡ β(p-1)/q (mod p). với một giá trị i nào đó. Khi điều này xảy ra ta có a 0 =i. Bây giờ nếu c = 1 thì ta đ. thực hiện xong. Ng−ợc lại, nếu c > 1 thì phải tiếp tục xác định a 1. Để làm điều đó ta phải xác định -ao β1 = β α và kí hiệu c x1 = log αβ1 mod q Dễ dàng thấy rằng Vì thế dẫn đến (p-1)/ q2 Nh− vậy ta sẽ tính β1 mod p và rồi tìm i sao cho Khi đó a 1 = i. Nếu c =2 thì công việc kết thúc; nếu không, phải lặp lại công việc này c-2 lần nữa để tìm a 2,. . .,a c-1. Hình 5.4 là mô tả giải m. của thuật toán Pohlig - Hellman. Trong thuật toán này, α là phần tử nguyên thuỷ theo modulo p, q là số nguyên tố . p-1 ≡ 0 (mod q c) và p-1 ≡ 0 (mod q c+1 )
  8. Thuật toán tính các giá trị a 0, . . ., a c-1 trong đó log αβ mod qc c Hình 5.4. Thuật toán Pohlig - Hellman để tính log αααβββ mod q . 1. Tính γ = α(p-1)/q mod p với 0 ≤ i ≤ q-1 2. Đặt j = 0 và βj = β 3. While j ≤ c-1 do (p-1)/ q j+1 4. Tính δ = βj mod p 5. Tìm i sao cho δ = γi 6. a j = i -aj qj 7. βj+1 = βj α mod p 8. j = j +1 Chúng ta minh hoạ thuật toán Pohlig - Hellman (P - H) qua một ví dụ nhỏ. Ví dụ 5.3 Giả sử p=29; khi đó n = p-1 = 28 = 2 2.7 1 Giả sử α = 2 và β = 18. Ta phải xác định a = log 218. Tr−ớc tiên tính a mod 4 rồi tính a mod 7. Ta sẽ bắt đầu bằng việc đặt q = 2, c = 2. Tr−ớc hết γ0 = 1 28/2 và γ1 = α mod 29 = 2 14 mod 29 = 28 Tiếp theo δ = β28/2 mod 29 = 18 14 mod 29 = 28 Vì a 0 = 1. Tiếp theo ta tính: -1 β1 = β0α mod 29 = 9 và 28/4 7 β1 mod 29 = 9 mod 29 = 28
  9. Vì γ1 ≡ 28 mod 29 Ta có a 1 = 1. Bởi vậy a ≡ 3 ( mod 4). Tiếp theo đặt q = 7 và c = 1, ta có β28/7 mod 29 = 18 4 mod 29 = 25 28/7 và γ1 = α mod 29 = 2 4 mod 29 = 16. Sau đó tính: γ2 = 24 γ3 = 7 γ4 = 25 Bởi vậy a 0 = 4 và a ≡ 4 ( mod 7) Cuối cùng giải hệ ph−ơng trình a ≡ 3 ( mod 4) a ≡ 4 ( mod 7) bằng định lý phần d− China, ta nhận đ−ợc a ≡ 11( mod 28). Điều này có nghĩa là đ. tính đ−ợc log 218 trong Z 29 là 11. Ph−ơng pháp tính toán chỉ số. Ph−ơng pháp tính chỉ số khá giống với nhiều thuật toán phân tích thừa số tốt nhất. Trong phần này sẽ xét tóm tắt về ph−ơng pháp. Ph−ơng pháp này chỉ dùng một cơ sở nhân tử là tập B chứa các số nguyên tố nhỏ. Giả sử B = {p 1,p 2,. . ., p B}. B−ớc đầu tiên ( b−ớc tiền xử lý) là tìm các logarithm của B số nguyên tố trong cơ sở nhân tử. B−ớc thứ hai là tính các logarithm rời rạc của phần tử β bằng cách dùng các hiểu biết về các log của các phần tử trong cơ sở. Trong quá trình tiền xử lý, ta sẽ xây dựng C = B +10 đồng d− thức theo modulo p nh− sau: xj a1j a2j aBj α ≡ p 1 p2 . . . p B (mod p) 1 ≤ j ≤ C. Cần để ý rằng, các đồng d− này có thể viết t−ơng đ−ơng nh− sau: xj ≡ a 1j log αp1+ . . . + a Bj log αpB (mod p-1) 1 ≤ j ≤ C. C đồng d− thức đ−ợc cho theo B giá trị log αpi (1 ≤ i ≤ B) ch−a biết. Ta hy vọng rằng, có một nghiệm duy nhất theo modulo p-1. Nếu đúng nh− vậy thì có thể tính các logarithm của các phần tử theo cơ sở nhân tử.
  10. Làm thế nào để tạo các đồng d− thức có dạng mong muốn?. Một ph−ơng pháp sơ đẳng là chọn một số ngẫu nhiên x, tính αx mod p và xác định xem liệu αx mod p có tất cả các thừa số của nó trong B hay không. (Ví dụ bằng cách chia thử). Bây giờ giả sử rằng đ. thực hiện xong b−ớc tiên tính toán, ta sẽ tính giá trị mong muốn log αβ bằng thuật toán xác suất kiểu Las Vegas. Chọn một số ngẫu nhiên s ( 1 ≤ s ≤ p-2) và tính : γ = β αs mod p Bây giờ thử phân tích γ theo cơ sở B. Nếu làm đ−ợc điều này thì ta tính đ−ợc đồng d− thức dạng: s c1 c2 cB βα = p 1 p2 . . . p B (mod p) Điều đó t−ơng đ−ơng với log αβ + s ≡ c 1log αp1+ . . . + c Blog αpB ( mod p-1) Vì mọi giá trị đều đả biết trừ giá trị log αβ nên có thể dễ dàng tìm đ−ợc log αβ. Sau đây là một ví dụ minh hoạ 2 b−ớc của thuật toán. Ví dụ 5.4. Giả sử p =10007 và α = 5 là một phần tử nguyên thuỷ đ−ợc dùnglàm cơ sở của các logarithm theo modulo p. Giả sử lấy B = {2, 3, 5, 7} làm cơ sở. Hiển nhiên là log 55 = 1 nên chỉ có 3 giá trị log của các phần tử trong cơ sở cần phải xác định. Để làm ví dụ, chọn một vài số mũ "may mắn" sau: 4063, 5136 và 985. Với x = 4063, ta tính 54063 mod 10007 = 2 ì3ì7 ứng với đồng d− thức log 52 + log 53 + log 57 ≡ 4063 ( mod 10006). T−ơng tự, vì 55136 mod 10007 = 54 = 2 ì33 và 59865 mod 10007 = 189 = 3 3ì7 ta tìm đ−ợc hai đồng d− thức nữa: log 52 + 3log 53 ≡ 5136 ( mod 10006) 3log 53 + log 57 ≡ 9865 ( mod 10006)
  11. Bây giờ ta có 3 đồng d− thức theo 3 giá trị log ch−a biết. Giải các ph−ơng trình đồng d− này, ta có log 52 = 6578, log 53 = 6190, log 57 = 1301. Bây giờ giả sử ta cần tìm log 59451, ta chọn số mũ "ngẫu nhiên" s=7736 và tính: 9451 ì57736 mod 10007 = 8400 Vì 8400 = 2 4315271 các thừa số trong B nên ta nhận đ−ợc: log 59451 = 4log 52 + log 53 + log 55 + log 57 - s mod 10006 = 4 ì6578 + 6190 + 2 ì1 + 1310 - 7736 mod 10006 = 6057. Kiểm tra lại ta thấy rằng 5 6057 ≡ 9451 ( mod 10007). Đ. có nhiều nghiên cứu phân tích mò mẫm nhiều kiểu thuật toán khác nhau. Với giả thiết hợp lý, Thời gian chạy tiệm cận của giai đoạn tiền tính toán này cỡ và thời gian để tính một giá trị logarithm rời rạc riêng là khoảng Hình 5.5. Bít thứ i của logarithm rời rạc. Bản chất của bài toán: I = (p, α, β, i) trong đó p là số nguyên tố , * * α∈Zp là phần tử nguyên thuỷ, β ∈ Z p và i là một số nguyên sao cho 1 ≤ i ≤ log 2(p-1) . Mục tiêu: Tính L i(β) là bít thấp nhất thứ i của log αβ. (với α và p cho tr−ớc) 5.1.2. Độ bảo mật từng bít của các logarithm rời rạc. Bây giờ ta xem xét vấn đề về thông tin bộ phận của các logarithm rời rạc và thử xem việc tính các bít riêng của các logarithm rời rạc là khó hay dễ. Cụ thể , xét bài toán trình bày trên hình 5.5. Bài toán này đ−ợc gọi là bài toán về bít thứ i.
  12. Tr−ớc tiên, ta sẽ chỉ ra rằng, bít thấp nhất của các logarithm rời rạc rất dễ tính toán. Nói cách khác, nếu i = 1 thì bài toán về bít thứ i có thể giải đ−ợc một cách hiệu quả. Điều này rút ra từ tiêu chuẩn Euler liên quan đến thặng d− bình ph−ơng theo modulo p, với p là số nguyên tố . * * Xét ánh xạ f: Z p Zp đ−ợc định nghĩa nh− sau: f(x) = x 2 mod p Nếu kí hiệu QR(p) là tập các thặng d− bình ph−ơng theo modulo p thì 2 * QR(p) = { x mod p : x ∈ Z p } Tr−ớc tiên ta thấy rằng, f(x) = f(p-x). Tiếp theo xét thấy: w2 ≡ x 2 mod p khi và chỉ khi p | (w-x)(w+x) điều này sẽ xảy ra khi và chỉ khi w ≡ ± x mod p. Từ đây rút ra: | f -1(y) | = 2 với mọi y ∈ QR(p) và bởi vậy: | QR(p) = (p-1)/2 * Điều đó có nghĩa là có đúng một nữa các thặng d− trong Z p là các thặng d− bình ph−ơng và một nữa không phải. * Bây giở giả sử rằng, α là một phần tử nguyên thuỷ của Z p . Khi đó a 0 2 p-3 α ∈QR(p) nếu a chẵn. Vì (p-1)/2 phần tử α mod p, α mod p,. . ., α mod p đều là các phần tử khác nhau nên: QR(p) = { α2i mod p: 0 ≤ i ≤ (p-3)/2} Bởi vậy, β là thặng d− bình ph−ơng khi và chỉ khi log αβ là chẵn, tức khi và chỉ khi L 1(β) = 0. Tuy nhiên theo tiêu chuẩn Euler β là thặng d− bình ph−ơng khi và chỉ khi β(p-1)/2 ≡ 1 (mod p)
  13. Nh− vậy, ta đ. có công thức hữu hiệu sau để tính L 1(β): 0 nếu β(p-1)/2 ≡ 1( mod p) L1(β)= 1 trong các tr−ờng hợp còn lại Bây giờ xét việc tính L i(β) với i > 1. Giả sử p-1 = 2 s t trong đó t là số lẻ. Khi đó có thể chỉ ra rằng, dễ dàng tính đ−ợc L i(β) nếu 1≤s. Mặt khác, việc tính L s+1 (β) chắc chắn là khó nếu dùng thuật toán giả định bất kì cho việc tính L s+1 (β) để tính các logarithm rời rạc trong Z p. Ta sẽ chứng minh kết quả này trong tr−ờng hợp s = 1. Chính xác hơn, nếu p ≡ 3 (mod 4)là số nguyên tố thì ta sẽ chỉ ra cách sử dụng một thuật toán giả định bất kì tính L 2(β) để giải bài toán logarithm rời rạc trong Z p. Nếu β là một thặng d− bình ph−ơng trong Z p và p ≡ 3 ( mod 4) thì ±β(p+1)/2 mod p là hai giá trị căn bậc hai của modulo p. Một chú ý cũng quan trọng là với bất kì β ≠ 0: L1(β) ≠ L 1(p-β). nếu p ≡ 3 (mod 4). Ta sẽ thấy điều đó nh− sau. Giả sử αa ≡ β (mod p) thì αa+(p-1)/2 ≡ -β (mod p) Vì p ≡ 3 (mod 4) nên số nguyên (p-1)/2 là một số lẻ. Từ đây rút ra kết quả. Bây giờ giả sử β = αa với số mũ chẵn a (ch−a biết) nào đó. Khi đó hoặc: β(p+1)/4 ≡ αa/2 (mod p) hoặc -β(p+1)/4 ≡ αa/2 (mod p) Ta có thể xác định giá trị nào trong hai giá trị có thể này là đúng nếu biết giá trị L 2(β), vì a/2 L2(β) = L 1(α ) Điều này đ−ợc khai thác trong thuật toán đ−ợc mô tả trong hình 5.6. ở cuối thuật toán, các giá trị x i là các bít biểu diễn nhị phân của log αβ, nghĩa là:
  14. D−ới đây là một ví dụ nhỏ để minh hoạ. Ví dụ 5.5. Giả sử p =19, α = 2 và β = 6. Vì trong ví dụ này, các giá trị quá nhỏ * nên có thể lập bảng các giá trị của L 1(γ) và L 2(γ) với mọi mọi giá trị γ∈Z19 .( Nói chung L 1 có thể tính đ−ợc một cách hiệu quả bằng tiêu chuẩn Euler, còn L2 đ−ợc tính theo thuật toán giả định). Các giá trị này đ−ợc cho trên bảng 5.1. Thuật toán đ−ợc tiến hành nh− trên hình 5.7. Bởi vậy, log 26 = 1110 2 = 14, ta có thể dễ dàng kiểm tra đ−ợc giá trị này. Hình 5.6. Tính các logarithm rời rạc trong Z p với p ≡≡≡ 3 ( mod 4) khi biết tr−ớc thuật toán giả định L 2(βββ). 1. x0 = L 1(β) 2. β = β/αx0 mod p 3. i =1 4. While β ≠ 1 do 5. x i = L 2(β) 6. γ = β(p+1)/4 (mod p) if then 7. L 1(γ) = x i 8. β = γ 9. else 10. β = p -γ 11. β = β/αxi mod p 12. i = i+1 Bảng 5.1. Các giá trị của L 1 và L 2 với p =19, α = 2 γ L1(γ) L2(γ) γ L1(γ) L2(γ) γ L1(γ) L2(γ) 1 0 0 7 0 1 13 1 0 2 1 0 8 1 1 14 1 1 3 1 0 9 0 0 15 1 1 4 0 1 10 1 0 16 0 0 5 0 0 11 0 0 17 0 1 6 0 1 12 0 0 18 1 0
  15. Có thể đ−a ra một chứng minh hình thức cho tính đúng đắn của thuật toán bằng ph−ơng pháp quy nạp. Kí hiệu Với i ≥ 0, ta định nghĩa: i+1 Yi = x/2  Hình 5.7 Tính log 26 trong Z 19 1. x 0 = 0 2. β =6 3. i =1 5. x 1 = L 2(6) = 1 6. γ = 5 7. L 1(5) = 0 ≠ x 1 10. β =14 11. i =2 12. i =2 5. x 2 = L 2(7) =1 6. γ = 11 7. L 1(11) = 0 ≠ x 2 10. β =8 11. β =4 12. i = 3 5. x 3 = L 2(4) = 1 6. γ =17 7. L 1(17) = 0 ≠ x 3 10. β = 2 11. β =1 12. i = 4 4. DONE Cũng vậy ta xác định β0 là giá trị của β ở b−ớc 2 trong thuật toán; và với i ≥1, While ta xác định βi là giá trị của β ở b−ớc 11 trong b−ớc lặp thứ i của vòng . Có thể chứng minh bằng ph−ơng pháp quy nạp rằng: βi ≡ α2Y i (mod p) với mọi i ≥0. Bây giờ để ý rằng: 2Y i = Y i-1 - x i
  16. điều này kéo theo xi+1 = L 2(βi) , i ≥0 Vì rằng x i+1 = L 2(β) nên thuật toán là đúng. Các chi tiết dành cho độc giả xem xét. 5.2. Tr−ờng hữu hạn và các hệ thống đ−ờng cong elliptic. Chúng ta đ. dành thời gian đáng kể để xét bài toán logarithm rời rạc (DL) vào việc phân tích số. Ta sẽ còn trở lại hai bài toán này trong các loại hệ mật và các giao thức m. khác nhau. Bài toán DL đ. đ−ợc nghiên cứu trong tr−ờng hữu hạn Z p, tuy nhiên việc xét bài toán này theo các thiết lập khác nhau cũng rất có ích và là chủ đề của phần này. Hệ mật Elgamal có thể đ−ợc áp dụng trong một nhóm bất kì mà bài * toán DL là khó giải. Ta đ. dùng nhóm nhân Z p tuy nhiên các nhóm khác cũng là những ứng cử viên thích hợp. Tr−ớc hết ta phát biểu bài toán DL trong một nhóm hữu hạn nói chung G (hữu hạn) và ở đó kí hiệu phép lấy nhóm là dấu " ο". Dạng bài toán tổng quát hoá nh− vậy trình bài trên hình 5.8. Dễ dàng xác định một hệ mật Elgamal trong nhóm con H theo cách * t−ơng tự đ. mô tả trong Z p và đ−ợc trình bày trên hình 5.9. Chú ý rằng phép m. hoá yêu cầu dùng số nguyên k ngẫu nhiên sao cho 0 ≤ k ≤ | H | - 1. Tuy nhiên, nếu Alice không biết cấp của nhóm con H thì cô ta có thể tạo một số nguyên k thoả m.n 0 ≤ k ≤ | G | -1, khi đó sẽ không có bất kì sự thay đổi nào trong quá trình m. và giải m Cũng cần chú ý là nhóm G không phải là nhóm Aben (Tuy H vẫn là nhóm Aben vì nó là nhóm cyclic).
  17. Hình 5.8. Bài toán logarithm rời rạc trong (G,0) Đặc tr−ng của bài toán: I = (G, α, β), trong đó G là một nhóm hữu hạn với phép lấy nhóm o , α ∈ G và β ∈ H, trong đó H = { αi : i ≥ 0} là một nhóm con sinh bởi α. Mục tiêu: Tìm một số nguyên duy nhất a sao cho 0 ≤ a ≤ | H | -1 và a a α = β, với kí hiệu α có nghĩa là α o . . . o α (a lần) Ta sẽ kí hiệu số nguyên a này bằng log αβ Bây giờ ta sẽ trở lại bài toán DL tổng quát hoá . Nhóm con H đ−ợc sinh bởi phần tử α tuỳ ý ∈ G dĩ nhiên phải là nhóm con cyclic cấp | H |. Bởi vậy, dạng bất kì của bài toán theo một nghĩa nào đó đều t−ơng đ−ơng với bài toán DL trong một nhóm cyclic. Tuy nhiên, độ khó của bài toán DL d−ờng nh− phụ thuộc vào cách biểu diễn nhóm đ−ợc dùng. Xét một ví dụ về cách biểu diễn mà với nó, bài toán logarithm rời rạc rất dễ giải. Xét nhóm cộng cyclic Z n và giả sử UCLN( α,n) = 1, bởi vậy α là phần tử sinh của Z n. Vì phép toán trong nhóm là cộng theo modulo n nên phép lấy mũ sẽ là nhân với a theo modulo n. Vì thế trong cách xây dựng này, bài toán logarithm rời rạc sẽ là tìm số nguyên a sao cho. αa ≡ β (mod n) Vì UCLN( α,n) = 1 nên α có phần tử nghịch đảo nhân theo modulo n và ta có thể dễ dàng tính α-1 mod n bằng thuật toán Euclide. Sau đó có thể giải để tìm a và nhận đ−ợc -1 log αβ = β α mod n
  18. Hình 5.9. Hệ mật khoá công khai Elgamal tổng quát Giả sử G là một nhóm hữu hạn có phép lấy nhóm o. Giả sử α ∈ G là một phần tử sao cho bài toán DL trong H là khó; ở đây H = { αi, i ≥ 0} là một nhóm con sinh bởi α. Đặt P = G, C = G ìG và định nghĩa: K = {(G, α, a, β) : β = αa} Các giá trị α, β công khai, còn a đ−ợc giữ kín. Với K = (G, α, a, β) và với một số ngẫu nhiên bí mật k ∈ Z |H| ta xác định: eK(x,k) = (y 1,y 2) k trong đó y 1 = α k và y 2 = (x o β ) Với bản m. y = (y1,y 2) ta xác định: a -1 dK(y) = y 2 o (y 1 ) * ở phần trên ta đ. nghiên cứu bài toán DL trong nhóm nhân Z p vơi p là là số nguyên tố . Nhóm này là nhóm cyclic cấp p-1 và bởi vậy nó đẳng cấu với nhóm cộng Z p-1. Theo thảo luận ở trên, ta đ. biết cách tinh các logarithm rời rạc một cách hiệu quả trong nhóm cộng này. Điều đó gợi ý khả năng giải * bài toán DL trong Z p bằng cách quy nó về bài toán giải đ−ợc dễ dàng trong Zp-1. Ta h.y xem xét điều này đ−ợc thực hiện nh− thế nào?. Khi nói rằng, * (Z p , ì) là đẳng cấu với (Z p-1, +) có nghĩa là có một song ánh : * φ : Z p  Z p-1 sao cho φ(xy mod p) = ( φ(x) + φ(y)) mod (p-1) Điều đó kéo theo: φ(αa mod p) = a φ(α) mod (p-1) Bởi vậy β ≡ αa mod p ⇔ a φ(α) ≡ φ(β) (mod p-1) Do đó nếu tìm a theo mô tả ở trên, ta có: -1 log αβ = φ(β) ( φ(α)) mod (p-1) Bây giờ, nếu có một ph−ơng pháp hữu hiệu để tính phép đẳng cấu φ thì * ta sẽ có một thuật toán hữu hiệu để tính các logarithm rời rạc trong Z p . Khó khăn ở đây là không có một ph−ơng pháp chung đ. biết nào để tính hiệu quả phép đẳng cấu φ với số nguyên tố tuỳ ý. Ngay cả khi đ. biết hai nhóm là
  19. đẳng cấu thì vẫn không thể biết một thuật toán hiệu quả để mo tả t−ơng minh phép đẳng cấu. Ph−ơng pháp này có thể áp dụng cho bài toán DL trong một nhóm G tuỳ ý. Nếu có một ph−ơng pháp hiệu quả tính phép đẳng cấu giữa H và Z |H| thì bài toán DL trong G mô tả ở trên có thể giải đ−ợc một cách hữu hiệu. Ng−ợc lại, dễ dàng thấy rằng, một ph−ơng pháp tính các logarithm rời rạc có hiệu quả sẽ tạo ra ph−ơng pháp hiệu quả tính phép đẳng cấu giữa hai nhóm. Thảo luận ở trên chỉ ra rằng, bài toán DL có thể dễ hoặc khó (xétbề ngoài) tuỳ thuộc vào biểu diễn của nhóm cyclic đ−ợc dùng. Nh− vậy, sẽ tốt hơn nếu xem xét các nhóm khác với hy vọng tìm đ−ợc các thiết lập khác nhau để bài toán DL có vẻ khó. Có hai lớp nhóm nh− vậy. 1. Nhóm nhân của tr−ờng Galois GF(p n) 2. Nhóm của một đ−ờng cong elliptic xác định trên một tr−ơng hữu hạn. Ta h.y xem xét hai lớp nhóm này ở phần sau. 5.1.2. Tr−ờng Galois Ta đ. biết rằng, nếu p là số nguyên tố thì Zp sẽ là một tr−ờng. Tuy nhiên có nhiều tr−ờng hữu hạn khác không có dạng trên. Thực tế có các tr−ờng hữu hạn q phần tử nếu q = p n, trong đó p là số nguyên tố , n ≥ 1là số nguyên. Bây giờ ta sẽ mô tả ngắn gọn cách xây dựng một tr−ờng nh− vậy. Tr−ớc tiên ta sẽ đ−a ra một vài định nghĩa. Định nghĩa 5.1 Giả sử p là số nguyên tố. Gọi Z p[x] là tập tất cả các đa thức biến x. Bằng cách xây dựng phép cộng và nhân đa thức theo quy tắc thông th−ờng ( và rút gọn hệ số theo modulo p) ta sẽ tạo nên một vành. Với f(x), g(x) ∈ Z p[x], ta nói rằng, f(x) chia hết cho g(x) ( kí hiệu f(x) | g(x)) nếu tồn tại q(x) ∈ Z p[x] sao cho: g(x) = q(x)f(x) Với f(x) ∈ Z p[x], ta xác định bậc của f ( kí hiệu là deg(f)) là số mũ cao nhất có trong các số hạng của f. Giả sử f(x), g(x), h(x) ∈ Z p[x] và deg(f) = n ≥ 1, ta định nghĩa: g(x) ≡ h(x) (mod f(x)) nếu f(x) | (g(x) - h(x)).
  20. Chú ý sự t−ơng tự giữa định nghĩa về đồng d− của các đa thức với định nghĩa về đồng d− của các số nguyên. Bây giờ ta sẽ định nghĩa vành các đa thức theo modulo f(x). (ta kí hiệu vành này là Z p[x]/f(x)). Việc xây dựng Z p[x]/f(x) từ Z p[x] dựa trên khái niệm về các đồng d− thức theo modulo f(x) và nó t−ơng tự nh− việc xây dựng Z m từ Z. Giả sử deg(f) = n. Nếu chia g(x) cho f(x), ta thu đ−ợc th−ơng q(x) và phần d− r(x), trong đó: g(x) = q(x)f(x) + r(x) và deg(r) 0 và deg(f 2) > 0. Một thực tế rất quan trọng là Z p[x]/(f(x)) là một tr−ờng khi và chỉ khi f(x) bất khả quy. Hơn nữa, các phần tử nghịch đảo nhân trong Z p[x]/(f(x)) có thể tính đ−ợc bằng cách dùng thuật toán Euclide mở rộng có biến đổi đôi chút. Sau đây là một ví dụ minh hoạ cho vấn đề nêu ra. Ví dụ 5.6
  21. Xây dựng một tr−ờng 8 phần tử. Điều này có thể thực hiện bằng cách tìm một đa thức bất khả quy bậc 3 trong Z 2[x]. Ta chỉ cần xem xét các đa thức có thành phần hằng số bằng 1 vì một đa thức bất kì có thành phần hằng số bằng 0 sẽ chia hết cho x và bởi vậy nó là một đa thức bất khả quy . Có tất cả 4 đa thức nh− vậy. 3 f1(x) = x + 1 3 f2(x) = x + x + 1 3 2 f3(x) = x + x + 1 3 2 f4(x) = x + x + x + 1 Xét thấy f 1(x) là khả quy vì: x3 +1 = (x+1)(x 2+x+1) (cần để ý là tất cả các hệ số đ−ợc rút gọn theo modulo 2). T−ơng tự, f 4(x) cũng khả quy vì: x3+x 2+x+1 = (x+1)(x 2+1) Tuy nhiên cả hai đa thức f 2(x) va f 3(x) lại đều là đa thức bất khả quy và có thể dùng hai đa thức này để xây dựng tr−ờng 8 phần tử . 3 Giả sử dùng f 2(x) để xây dựng tr−ờng Z 2[x]/(x +x+1). 8 phần tử của tr−ờng là 8 đa thức : 0, 1, x, x+1, x 2, x 2+1, x 2+x, x 2+x+1 Để tính tích của hai phần tử của tr−ờng, nhân hai đa thức với nhau và rút gọn theo modulo x 3+x+1 (tức chia cho (x 3+x+1) và tìm đa thức d−). Vì ta chia một đa thức bậc 3 nên đa thức d− có bậc nhiều nhất là 2 và vì thế nó là một phần tử của tr−ờng. 2 2 3 Ví dụ, ta h.y tính (x +1)(x +x+1) trong Z 2[x]/(x +x+1). Tr−ớc hết tính 4 3 3 tích trong Z 2[x] là x +x +x+1. Khi chia cho x +x+1, ta nhận đ−ợc biểu thức sau: x4+x 3+x+1 = (x+1)(x 3+x+1) +x 2+x 3 Bởi vậy, trong tr−ờng Z 2[x]/(x +x+1) ta có : (x 2+1)(x 2+x+1) = x 2+x
  22. D−ới đây sẽ đ−a ra bảng dầy đủ cho cá phần tử khác 0 của tr−ờng. Để đơn 2 giản, ta viết đa thức : a 2x +a 1x+a 0 theo bộ ba đ−ợc sắp a 2a1a0. 001 010 011 100 101 110 111 001 001 010 011 100 101 110 111 010 010 100 110 011 001 111 101 011 011 110 101 111 100 001 010 100 100 011 111 110 010 101 001 101 101 001 100 010 111 011 110 110 110 111 001 101 011 010 100 111 111 101 010 001 110 100 011 Việc tính các phần tử nghịch đảo đ−ợc tực hiện theo thuật toán Euclide mở rộng có biến đổi đôi chút. Cuối cùng, ta thâý rằng nhóm nhân của các đa thức khác 0 trong tr−ờng là một nhóm cyclic cấp 7. Vì 7 là số nguyên tố nên suy ra mọi phần tử khác 0 của tr−ờng đều là phần tử sinh của nhóm này (tức là phần tử nguyên thuỷ). Ví dụ, nếu tính các luỹ thừa của x, ta có: x1 = x x2 =x 2 x3 = x+1 x4 = x 2+1 x5 = x 2+ x+1 x6 = x 2+1 x7 = 1 sẽ bao gồm tất cả các phần tử khác 0 của tr−ờng. Vấn đề còn lại là sự tồn tại và tính duy nhất của các tr−ờng dạng này. Có thể chỉ ra rằng, có ít nhất một đa thức bất khả quy bậc bất kì n ≥1 trong Zp[x]. Bởi vậy, sẽ có một tr−ờng hữu hạn p n phần tử đối với mọi nguyên tố p và mọi số nguyên n ≥1. Thông th−ơng có khá nhiều đa thức bất khả quy bậc n trong Z p[x]. Tuy nhiên, những tr−ờng hữu hạn đ−ợc xây dựng từ hai đa thức bất khả quy bất kì bậc n đều có thể chứng tỏ đ−ợc chúng là đaửng cấu với nhau. Bởi vậy, chỉ có một tr−ơng hữu hạn duy nhất cấp p n tuỳ ý (p - số nguyên tố, n ≥ 1) là tr−ờng GF(p n). Trong tr−ờng hợp n = 1, tr−ơng GF(p) cũng chính là Z p. Cuối cùng, có thể chỉ ra rằng, không tồn tại một tr−ờng hữu
  23. hạn r phần tử trừ phi r = p n với p là số nguyên tố , n là số nguyên nào đó (n ≥1). * Ta đ. nhận thấy là nhóm nhân Z p (p - số nguyên tố) là một nhóm cyclic cấp p-1. Thực tế, nhóm nhân của tr−ờng hữu hạn bất kì đều là nhóm cyclic: GF(p n)\{0} là một nhóm cyclic cấp p n-1. Nhóm này sẽ cho các ví dụ về các nhóm cyclic trong đó bài toán DL có thể đ−ợc nghiên cứu. Thực tế các tr−ờng hữu hạn GF(2 n) đ. đ−ợc nghiên cứu khá kĩ. Cả hai thuật toán logarithm rời rạc Shanks và Pohlig-Hellman đều làm việc trên các tr−ờng GF(2 n). Ph−ơng pháp tính toán chỉ số có thể sửa đổi để làm việc trên các tr−ơng này. Thời gian tiền tính toán của thuật toán tính toán chỉ số khoảng còn thời gian để tìm một giá trị logarithm rời rạc riêng khoảng Tuy nhiên, với các giá trị n lớn (n > 800), bài toán DL trong GF(2 n) đ−ợc coi là khó cỡ 2 n phải có ít nhất một thừa số nguyên tố "lớn" ( để gây khó khăn cho cách tấn công Pohlig - Hellman). 5.2.2. Các đ−ơng cong Elliptic Ta bắt đầu bằng việc định nghĩa khái niệm đ−ờng cong elliptic. Định nghĩa 5.3 2 3 Cho p >3 là số nguyên tố. Đ−ờng cong elliptic y = x +ax+b trên Z p là một tập các cặp (x,y) ∈ZpìZp thoả mWn đồng d− thức y2 ≡ x 3+ax+b (mod p) (5.1) trong đó a, b ∈Zp là các hằng số sao cho 4a3+27b2 ≡ 0 ( mod p) cùng với một điểm đặc biệt O đ−ợc gọi là điểm vô cực. [Ph−ơng trình (5.1) có thể dùng để xác định một đ−ờng cong elliptic trên một tr−ờng bất kì GF(p n) với p - là số nguyên tố lớn hơn 3. Đ−ờng cong elliptic trên GF(2 n) hoặc GF(3 n) đ−ợc xác định bằng một ph−ơng trình khác đôi chút)]. Đ−ờng cong elliptic E có thể tạo thành một nhóm Aben bằng cách xác định một phép toán thích hợp trên các điểm của nó. Phép toán này là phép cộng và đ−ợc xác định nh− sau ( ở đây mọi phép toán số học đ−ợc thực hiện trên Z p).
  24. Giả sử P = (x 1,y 1) và Q = (x 2,y 2) là các điểm trên E. Nếu x 2=x 1 và y 2=-y1 thì P+Q = O; ng−ợc lại P+Q = (x 3,y 3) trong đó: 2 x3 = λ -x1-x2 y3 = λ(x 1-x3)-y1 và (y 2-y1)/(x 2-x1) nếu P ≠ Q λ = 2 (3x 1 +a)/2y 1 nếu P = Q Cuối cùng ta xác định P+O = O+P = P đối với mọi P ∈ E. Với định nghĩa phép cộng nh− vậy, có thể chỉ ra rằng, E là một nhóm Aben với phần tử đơn vị O. ( phần lớn các phép kiểm tra đều khá đơn giản song việc chứng minh tính kết hợp lại rất khó). Cần để ý là các phần tử ng−ợc (nghịch đảo) rất dễ tính toán. Phần tử nghịch đảo của (x,y) là (x,-y) với mọi (x,y) ∈ E ( ta kí hiệu phần tử này là - (x,y) do phép nhóm là phép cộng) Xét ví dụ sau. Ví dụ 5.7 2 3 Giả sử E là một đ−ờng cong elliptic y = x +x+6 trên Z 11 . Tr−ớc tiên ta xác định các điểm trên E. Để làm điều đó, xét mỗi giá trị có thể x ∈ Z 11 , tính x3+x+6 mod 11 và thử giải ph−ơng trình (5.1) đối với y. Với giá trị x cho tr−ớc, ta có thể kiểm tra xem liệu z = x 3+x+6 mod 11 có phải là một thặng d− bình ph−ơng hay không bằng cách áp dụng tiêu chuẩn Euler. Ta đ. có một công thức t−ờng minh để tính các căn bậc hai của các thặng d− bình ph−ơng theo modulo p với các số nguyên tố p ≡ 3 (mod 4). áp dụng công thức này, ta có các căn bậc hai của một thặng d− bình ph−ơng z là: z(11+1)/4 mod 11 = z 3 mod 11 Kết quả của các phép tính này đ−ợc nêu trên bảng 5.2 Nh− vậy, E có tất cả 13 điểm. Với một nhóm bất kì cấp nguyên tố đều là nhóm cyclic nên dẫn đến E đẳng cấu với Z 13 và một điểm bất kì ( không phải điểm vô cực) đều là phần tử sinh của nhóm E. Giả sử ta lấy phần tử sinh là (2,7) = α. Khi đó ta có thể tính các "luỹ thừa" của α ( chính là các bội của α vì phép nhóm là phép cộng). Để tính 2 α = (2,7) + (2,7), tr−ớc hết ta tính:
  25. λ = (3 ì22+1)(2 ì7) -1 mod 11 = 2 ì3-1 mod 11 = 2 ì4 mod 11 = 8 2 Sau đó ta có: x3 = 8 -2-2 mod 11 = 5 và y3 = (8(2-5)-7) mod 11 = 2 Bởi vậy 2 α = (5,2) 2 3 Bảng 5.2 Các điểm trên đ−ờng cong elliptic y = x +x+6 trên Z 11 x x3+x+6 mod 11 Có trong QR(11)? y 0 6 Không 1 8 Không 2 5 Có 4,7 3 3 Có 5,6 4 8 Không 5 4 Có 2,9 6 8 Không 7 4 Có 2,9 8 9 Có 3,8 9 7 Không 10 4 Có 2,9 Bội tiếp theo là 3 α = 2 α+α = (5,2) + (2,7). Ta lại bắt đầu bằng viẹc tính λ. λ = (7-2)(2-5) -1 mod 11 = 5 ì8-1 mod 11 = 5 ì7 mod 11 = 2 2 Khi đó ta có x 3 = 2 -5-2 mod 11 = 8 và y3 = 2(5-8) - 2 mod 11 = 3 Bởi vậy 3 α = (8,3)
  26. Tiếp tục theo cách t−ơng tự, có thể tính đ−ợc các bội còn lại nh− sau: α = (2,7) 2 α = (5,2) 3 α = (8,3) 4α = (10,2) 5 α = (3,6) 6 α = (7,9) 7α = (7,2) 8 α = (3,5) 9 α = (10,9) 10 α = (8,8) 11 α = (5,9) 12 α = (2,4) Do đó α = (2,7) thực sự là phần tử nguyên thuỷ. Một đ−ờng cong elliptic xác định trên Z p (p là số nguyên tố >3) sẽ có khoảng p điểm. Chính xác hơn, theo một định lý nổi tiếng của Hasse, số các điểm trên E ( kí hiệu là #E) thảo m.n bất đẳng thức sau: Việc tính toán chính xác giá trị của #E có khó hơn nh−ng đ. có một thuật toán hữu hiệu do Schoof đ−a ra giúp tính toán dễ dàn hơn.( Nghĩa hữu hiệu ở đây đ−ợc hiểu là thời gian chạy của thuật toán là thời gian đa thức theo log p. Thuật toán Schoof có thời gian chạy khoảng O((log p) 8) phép tính trên bít và có thể thực hiện đối với các số nguyên tố p có vài trăm chữ số). Bây giờ giả sử có thể tính đ−ợc #E. Vấn đề tiếp theo là phải tìm một nhóm con cyclic trong E sao cho bài toán DL trong nó là khó. Bởi vậy ta phải biết một vài điều về cấu trúc của nhóm E. Định lý sau đây cung cấp một thông tin đáng kể về cấu trúc nhóm của E. Định lý 5.1 Cho E là một đ−ờng cong elliptic trên Z p, p là số nguyên tố > 3. Khi đó, tồn tại các số nguyên n 1 và n 2 sao cho E là đẳng cấu với Z n1 ìZn2 . Ngoài ra n 2 | n 1 và n 2 | (p-1). Bởi vậy nếu có thể tính đ−ợc các số n 1 và n 2 thì ta sẽ biết rằng E có một nhóm con cyclic đẳng cấu với Z n1 và có thể dùng E để thiết lập một hẹe mật Elgamal. Chú ý là nếu n 2 = 1 thì E là một nhóm cyclic. Cũng vậy, nếu #E là một số nguyên tố hoặc là tích của các số nguyên tố khác nhau thì E là nhóm cyclic có chỉ số nhóm cyclic.
  27. Các thuật toán Shanks và Pohlig - Hellman có thể áp dụng cho bài toán rời rạc trên đ−ờng cong Elliptic song tới nay vẫn ch−a có một thuật toán thích hợp cho ph−ơng pháp tính chỉ số đối với các đ−ờng cong Elliptic.Tuy nhiên, đ. có một ph−ơng pháp khai thác đẳng cấu một cách t−ờng minh giữa các đ−ờng cong Elliptic trong tr−ờng hữu hạn. Ph−ơng pháp này dẫn đến các thuật toán hữu hiệu đối với một số lớp các đ−ờng cong Elliptic. Kỹ thuật này do Menezes, Okamoto và Vanstone đ−a ra và có thể áp dụng cho một số tr−ờng hợp riêng trong một lớp đặc biệt các đ−ờng cong Elliptic (đ−ợc gọi là các đ−ờng cong siêu biến, chúng đ. đ−ợc kiến nghị sử dụng trong các hệ thống mật m.). Tuy nhiên, nếu tránh các đ−ờng cong siêu biến thì lại xuất hiện một đ−ờng cong Elliptic có một nhóm con cyclic cỡ 2 160 , đ−ờng cong này sẽ cho phép thiết lập an toàn một hệ mật miễn là bậc của nhóm con phải là bội của ít nhất một thừa số nguyên tố lớn ( nhằm bảo vệ hệ mật khỏi ph−ơng pháp tấn công của Pohlig - Hellman). Xét một ví dụ về phép m. Elgamal sử dụng đ−ờng cong elliptic nêu trên ví dụ 5.7. Ví dụ 5.8. Giả sử α = (2,7) và số mũ mật của Bob là a = 7. Bởi vậy: β = 7 α = (7,2) Phép m. hoá thực hiện nh− sau eK(x,k) = (k(2,7),x+k(7,2)) trong đó x ∈E và 0 ≤ k ≤ 12 còn phép giải m. thực hiện nh− sau: dK(y 1,y 2) = y 2-7y 1 Giả sử Alice muốn m. bản tin x = (10,9) ( là một điểm trên E). Nếu cô chọn giá trị ngẫu nhiên k=3 thì cô tính y1 = 3(2,7) = (8,3) và y2 = (10,9) + 3(7,2) = (10,9) + (3,5) = (10,2) Bởi vậy, y = ((8,3),(10,2)). Bây giờ nếu Bob nhận đ−ợc bản m. y thì anh ta giải m. nh− sau: x = (10,2) - 7(8,3) = (10,2) - (3,5) = (10,2) + (3,6) = (10,9) Đây chính là bản rõ đúng.
  28. Trên thực tế có một số khó khăn khi áp dụng hệ mật Elgamal trên đ−ờng cong Elliptic. Hệ thống này đ−ợc áp dụng trong Z p ( hoặc trong GF(p n) với n > 1) sẽ có hệ số mở rộng bản tin là 2. Việc áp dụng đ−ờng cong Elliptic sẽ có thừa số mở rộng khoảng 4 lần. Điều này là do có xấp xỉ p bản rõ, nh−ng mỗi bản m. lại gổm bốn phần tử của tr−ờng. Một trở ngại là không gian bản rõ chứa các điểm trên đ−ờng cong E và không có ph−ơng pháp nào xác định t−ờng minh các điểm trên E Menezes và Vanstone đ. tìm ra một ph−ơng án hiệu quả hơn. theo ph−ơng án này đ−ờng cong Elliptic dùng để "che dấu", còn các bản rõ và bản m. hợp lệ là các cặp đ−ợc sắp tùy ý các phần tử khác không của tr−ờng( tức là chúng không đòi hỏi phải là các điểm trên E). Điều này sẽ tạo hệ số mở rộng bản tin là 2 giống nh− trong hệ mật Elgamal ban đầu. Hệ mật Menezes - Vanstone đ−ợc mô tả trên hình 5.10. 2 3 Nếu trở lại đ−ờng cong y = x + x + 6 trên Z 11 ta sẽ thấy rằng hệ mật Menezes - Vanstone có 10 ì10 = 100 bản rõ, trong khi đó hệ mật ban đầu chỉ có 13 bản rõ. Ta sẽ minh hoạ phép m. và giải m. trong hệ mật này bằng cách sử dụng đ−ờng cong trên. Hình 3.6 Hệ mật trên đ−ờng cong Elliptic của Menezes - Vanstone Giả sử E là một đ−ờng cong Elliptic trên Zp (p là số nguyên tố > 3) sao cho E chứa một nhóm con cyclic H, trong đó bài toán DL là bài toán khó. * * * * Giả sử P = Zp ì Z p , C = E ì Z p ì Z p ,ta định nghĩa: K = { (E, α,a, β) : β = a α } trong đó α∈E. Các giá trị α và β đ−ợc công khai, còn a đ−ợc giữ kín. Đối với K = (E, α,a, β), với số ngẫu nhiên bí mật k ∈ Z | H | * * và x = (x 1,x 2) ∈ Z p ì Z p , ta xác định: eK (x,k) = (y 0,y 1,y 2) y0 = k α (c 1,c2) = k β y1 = c1x1 mod p và y2 = c 2y2 mod p Với bản m. y = (y 0,y 1,y 2), ta định nghĩa -1 -1 dK (y) = (y 1c1 mod p, y 2c2 mod p) trong đó a y 0 = (c 1,c 2)
  29. Ví dụ 5.9 Cũng nh− ví dụ tr−ớc, giả sử α = (2,7) và số mũ mật của Bob là 7. Khi đó β = 7 α = (7,2) Giả sử Alice muốn m. hoá bản rõ sau: x = (x 1,x 2) = (9,1) (Cần chú ý là x không phải là một điểm trên E) và cô chọn giá trị ngẫu nhiên k = 6. Đầu tiên cô tính: y0 = k α = 6(2,7) = (7,9) và kβ = 6(7,2) = (8,3) Nh− vậy, c 1 = 8 còn c 2 = 3. Tiếp theo Alice tính: y1 = c 1x1 mod p = 8 ì9 mod 11 = 6 và y2 = c 2x2 mod p = 3 ì1 mod 11 = 3 Bản m. mà cô giửi cho Bob là: y = (y 0,y 1,y 2) = ((7,9), 6, 3) Khi Bob nhận đ−ợc bản m. này, Tr−ớc tiên anh ta tính: (c 1,c 2) = (a y 0) = 7(7,9) = (8,3) và sau đó tính: -1 -1 x = (y 1c1 mod p, y 2c2 mod p) = ((6 ì8-1 mod 11, 3 ì3-1 mod 11) = (6 ì7 mod 11, 3 ì4 mod 11) = (9,1). Hình 5.11. Bài toán tổng các tập con Đặc tr−ng của bài toán: I = (s 1, s 2, . . . ,s n, T) trong đó s 1, . . ., s n và T là các số nguyên d−ơng. Các s i đ−ợc gọi là các cỡ, T đ−ợc gọi là tổng đích. Vấn đề : Liệu có một véc tơ nhị phân x = (x 1, . . . , x n) sao cho: n ∑x i si =T ? i =0
  30. Đây chính là bản rõ đúng. 5.3. Hệ mật xêp ba lô merkle - Hellman Hệ mật xếp ba lô Merkle – Hellman nổi tiếng lần đầu tiên đ−ợc Merkle – Hellman mô tả vào năm 1978. Mặc dù hệ mật này có một vàI biến thể của nó đ. bị phá vào đầu những năm 1980 nh−ng nó vẫn là một cống hiến có giá trị do sự tinh tế về kháI niện và kỹ thuật thiết kế có tính nần tảng của mình. Thuật ngữ ba lô (knapsack) thực tế là một thuật ngữ dùng sai. Trên thực tế hệ thống này xây dựng trên cơ sở bàI toán tổng tập con ( nêu trên hình 5.11) BàI toán tổng các tập con là bàI toán quyết định ( tức là chỉ cần câu trả lời “có” hay “không” ). Nếu diễn đạt lạI bài toán một cách nhẹ nhàng sao cho với một số đặc tr−ng bất kì , câu trả lời luôn luôn là “có” thì phảI tìm đ−ợc véc tơ quyết định x (vec to này có thể không duy nhất). Khi đó ta có một bàI toán tìm kiếm. Bài toán toán quyết định tổng các tập con là một bài toán NP đầy đủ. ĐIũu này có nghĩa là trong số các thuật nghữ khác nhau, không có một thuật toán thời gian đa thức nào tìm đ−ợc quyết định lựa chọn phù hợp. ĐIều này cũng đúng với bài toán tổng các tập con. Song ngay cả khi một bài toán không có thuật giảI với thời gian đa thức nói chung thì vẫn có những trừng hợp nhất định có thể giảI với thời gian đa thức. ĐIều này cũng đúng với bàI toán tổng các tập con. Ta định nghĩa một danh sách các cỡ (s 1,s 2, , s n) là một d.y siêu tăng nếu: với 2 ≤ j ≤ n. Nếu danh sách các cỡ là một d.y siêu tăng thì dạng tìm kiếm của bài toán tổng các tập con có thể giảI đ−ợc với thời gian O(n) và giảI pháp
  31. x ( nếu tồn tạI ) phảI là giảI pháp duy nhất. Thuật toán này đ−ợc mô tả ở hình 5.12. Giả sử s = (s 1, ,s n) là một d.y siêu tăng, xét hàm hàm này đ−ợc xác định nh− sau: PhảI chăng có thể dùng e s nh− một quy tắc m. hoá?. Vì s là một d.y siêu tăng nên e s là một đơn ánh và thuật toán đ−ợc mô tả ở hình 5.12 sẽ là thuật toán giảI m. t−ơng ứng. Tuy nhiên một hệ thống nh− vậy sẽ hoàn toàn mất an toàn và bất kì ai cũng có thể giảI m. một bản tin m. theo cách trên. Hình 5.12. Thuật toán để giảI tr−ờng hợp siêu tăng của bàI toán tổng các tập con. 1. for i = n down to 1 do 2. if T > s then i 3. T = T - s i 4. x = 1 i 5. else 6. x i = 0 n 7. if ∑ x is i = T then i=1 8. X = (x 1 , x, n ) là giả i pháp cần tim 9. else 10. Không có giả i pháp Bởi vậy chiến thuật ở đây là biến đổi danh sách các cỡ theo cách sao cho nó không còn là d.y siêu tăng nữa. Bob sẽ không thể áp dụng phép biến đổi ng−ợc để khôI phục lai danh sách siêu tăng các cỡ. Mặt khác, Oscar ( không biết phép biến đổi đ−ợc dùng ) phảI đối mặt với bài toán tổng quát ( là
  32. một bài toán khó của bài toán tổng các tập con) khi anh ta cố gắng giải m. một bản m Một kiểu biến đổi thích hợp là phép biến đổi theo modun. Modun p nguyên tố đ−ợc chọn sao cho: Ta chọn thừa số a thảo m.n 1 ≤ a ≤ p-1. Sau đó xác định: ti = a s i mod p 1 ≤ i ≤ n. Danh sách các cỡ t = (t 1, , t n) là khoá công khai đ−ợc dùng để m. hoá. Các giá trị a, p đ−ợc dùng để xác định phép biến đổi theo modun sẽ đ−ợc giữ kín. Mô tả đầy đủ hệ mật xếp ba lô Merkle – Hellman cho ở hình 5.13. nh− sau: ????????????????? Ví dụ nhỏ sau đây sẽ minh hoạ quá trình m. và giải m. trong hệ mật Merklre – Hellman. Ví dụ 5.10 Giả sử s = (2, 5, 9, 21, 45, 103, 215, 450, 946) là một danh sách siêu tăng bí mật. Giả sử p = 2003, a = 1289. Khi đó danh sách công khai của các cỡ là: t = (575, 436, 1586, 1030, 1921, 569, 721, 1183, 1570) Bây giờ Alice muốn m. bản rõ x = (1, 0, 1, 1, 0, 0, 1, 1, 1) cô ta phảI tính: y = 575 +1586 +1030 +721 + 1183 +1570 = 6665 Khi Bob nhận đ−ợc bản m. y, đầu tiên anh ta tính: z = a -1y mod p = 317 ì6665 mod 2003 = 1643 Sau đó Bob sẽ giảI tr−ờng hợp I = (s,z) của bàI toán tổng các tập con bằng thuật giảI mô tả trên hình 5.12. Cuối cùng Bob sẽ thu đ−ợc bản rõ (1, 0, 1, 1, 0, 0, 1, 1, 1).
  33. Vào đầu những năm 80, hệ mật xếp ba lô Merkle – Hellman đ. bị Shamir phá. Shamir đ. sử dụng thuật toán quy hoạch nguyên của Lenstra để phá hệ thống. ĐIều này cho phép m. thám Oscar phá đ−ợc cửa sập của Bob ( hoặc một cửa sập t−ơng đ−ơng). Sau đó Oscar có thể giải m. các bản tin giống nh− Bob. 5.3. Hê mật m celiece Hệ mật McEliece sử dụng nguyên lý t−ơng tự nh− hệ mật Merkle – Hellman: Phép giải m. là một tr−ờng hợp đặc biệt của bài toán NP đầy đủ nh−ng nó đ−ợc ngụi trang giống nh− tr−ờng hợp chung của bài toán. Trong hệ thống này, bài toán NP đ−ợc áp dụng ở đây là bài toán giải m. cho một m. sửa sai ( nhị phân ) tuyến tính nói chung. Tuy nhiên, đối với nhiều lớp m. đặc biệt đều tồn tạI các thuật toán giải m. với thời gian đa thức. Một trong những lớp m. này là m. Goppa, Chúng đ−ợc dùng làm cơ sở cho hệ mật McEliece. Ta bắt đầu bằng một định nghĩa cơ bản. Định nghĩa 5.4 Giả sử k, n là các số nguyên d−ơng, k ≤ n. MW C[n, k] là một không n gian k chiều của (Z 2) ( không gian vecto của tất cả các vecto nhị phân n chiều). Ma trận sinh của mW C[n,k] là một ma trận nhị phân k ìn, các hàng của ma trận này tạo nên cơ sở của C. n Giả sử x, y ∈ (Z 2) , trong đó x = (x 1, , x n) và y = (y 1, , y n). Ta xác định khoảng cách Hamming: d(x,y) = | {i : 1 ≤ i ≤ n , x i ≠ y i} | tức là số các tạo độ mà ở đó x và y khác nhau. Khoảng cách mW C đ−ợc định nghĩa nh− sau: d(C) = min { d(x,y) : x,y ∈ C, x ≠y} MW [n, k] có khoảng cách d đ−ợc kí hiệu là mW [n,k,d]. M. sửa sai đ−ợc dùng để sửa các sai ngẫu nhiên xảy ra khi truyền số liệu (nhị phân) qua kênh có nhiễu. ĐIều đó đ−ợc thực hiện nh− sau. Giả sử G là một ma trận sinh đối với m. [n,k,d], x là véc tơ nhị phân k chiều cần truyền đi. Ng−ời gửi Alice sẽ m. hoá x thành một vec to n chiều y = xG rồi truyền y qua kênh.
  34. Giả sử Bob nhận đ−ợc vecto n chiều r không giống y. Bob sẽ giải m. r bằng chiến thuật giải m. “ng−ời láng giềng gần nhất”. Theo chiến thuật này, Bob sẽ tìm m. từ y’ có khoảng cách tới r nhỏ nhất. Sau đó anh ta giải m. r thành y’, rồi xác định vecto k chiều x’ sao cho y’= x’G. Bob hy vọng y’= y và bởi vậy x’= x( tức là Bob tin rằng các sai số trên đ−ờng truyền đ. đ−ợc sửa). Dễ dàng thấy rằng, nếu sai số trên đ−ờng truyền nhiều nhất là (d-1)/2 thì trên thực tế, chiến thuật này sẽ sửa đ−ợc tất cả các sai. Ta xét trên thực tế, thuật toán giải m. này đ−ợc thực hiện nh− thế nào?. Vì | C | = 2 k nên Bob so sánh r với mỗi từ m., anh ta sẽ phảI kiểm tra 2 k vecto – là một số lớn theo hàm mũ so với k. Nói cách khác, thuật toán này không phảI là thuật toán chạy trong thời gian đa thức. Một biện pháp khác ( tạo cơ sở cho nhiều thuật toán giải m. thực tế) dựa trên kháI niệm về syndrom. Ma trận kiểm tra tính chẵn lẻ của m. C[n,k,d] ( có ma trận sinh G) là một ma trận nhị phân ( n-k) ìn chiều ( kí hiệu là H). Các hàng của H sẽ tạo cơ sở cho các phần bù trực giao của C ( kí hiệu là C -) và đ−ợc gọi là m. đối ngẫu với C. Nói cách khác, các hàng của H là những vevto độc lập tuyến tính, còn GH T là một ma trận không cấp k ì(n- k). n T T Cho véc tơ r ∈ (Z 2) , ta xác định syndrom của r là H r . Syndrom H r là một véc tơ cột có ( n-k) thành phần. Các kết quả cơ bản sau rút ra từ đạI số tuyến tính. Định lý 5.2 Giả sử C là một mW [n,k] có ma trận sinh G và ma trận kiểm tra tính n chẵn lẻ H. Khi đó x ∈ (Z 2) là một từ mW khi và chỉ khi:
  35. n Hơn nữa nếu x ∈ C, e ∈ (Z 2) và r = x + e thì H r T = H e T Ta coi e là véc tơ sai xuất hiện trong quá trình truyền từ m. x. Khi đó r biểu diễn vec tơ thu đ−ợc. Định lý trên phát biểu rằng syndrom chỉ phụ thuộc vào các sai số mà không phụ thuộc vào từ m. cụ thể nào đ−ợc truyền đi. Điều này gợi ý tới một cách giải m. đ−ợc gọi là giải mW theo syndrom : tr−ớc tiên tính s = H r T. Nếu s là một véc tơ không thì ta giải m. r thành r. Nếu không thì ta sẽ lần l−ợt tạo tất cả các vec tơ sai có trọng số 1. Với mỗi véc tơ e này, ta tính H e T. Nếu có một véc tơ e nào đó thảo m.n H e T = s thì ta giảI m. r thành r-e. Ng−ợc lại, lạI tiếp tục tạo các véc tơ sai có trọng số 2,3, , (d-1)/2 . Nếu ở một thời đIúm nào đó H e T = s thì ta giảI m. r thành r-e rồi thoát khỏi quá trình giải m Nếu ph−ơng trình trên không thảo m.n với mọi véc tơ sai có trọng số ≤ (d-1)/2  thì ta có thể kết luận rằng số sai số xuất hiện trên đ−ờng truyền lớn hơn (d-1)/2 . Theo thuật toán này, có thể giải m. cho một véc tơ nhận đ−ơc trong nhiều nhất là n  n   1+   + +  d −1 1       2  b−ớc. Ph−ơng pháp này làm việc trên một m. tuyến tính bất kì. Đối với một số loạI m. đặc biệt, thủ tục giải m. có thể nhanh chóng hơn. Tuy nhiên, trên thực tế, cách giảI quyết này cho chiến thuật giảI m. “ng−ời láng giềng gần nhất” vẫn là một bài toán NP đầy đủ. Nh− vậy, vẫn ch−a có một thuật toán giải trong thời gian đa thức đ. biết nào cho bài toán giảI m. theo “ng−ời láng giềng gần nhất “ tổng quát. ( Khi số các sai số không bị giới hạn bởi (d-1)/2 . Cũng giống nh− bài toán tổng tập con, có thể chỉ ra một tr−ờng hợp đặc biệt “dễ”, sau đó ngụi trang sao cho nó giống với bài toán chung “khó”. Để đ−a ra lý thuyết rất dàI dòng, bởi vậy, ta sẽ chỉ tóm l−ợc các kết quả ở
  36. đây. Một tr−ờng hợp riêng khá dễ đ−ợc McEliece đề nghị là dùng một m. trong lớp các m. Goppa. Trên thực tế , các m. này có một thuật toán giải m. hữu hiệu. Hơn nữa các m. này rất dễ tạo và có một số l−ợng lớn các m. Goppa t−ơng đ−ơng có cùng tham số. Các tham số của m. Goppa có dạng n = 2 m, d = 2t+1 và k = n-mt. Để áp dụng trong thực tế cho một hệ mật khoá công khai, McEliece đề nghị chọn m = 10 và t = 50. ĐIều này ứng với m. Goppa [1024,524,101]. Mỗi bản rõ là một véc tơ nhị phân cấp 524 và mỗi bản m. là một véc tơ nhị phân cấp 1024. Khóa công khai là một ma trận nhị phân cấp 524 ì1024. Hình 5.14 sẽ mô tả hệ mật McEliece. Hình 5.14. Hệ mật McEliece. Cho G là một ma trận sinh của một m. Goppa C[n,k,d], trong đó n = 2m, d = 2t + 1 và k = n - mt. Cho s là một ma trận khả nghịch cấp k ìk trên k Z2. Giả sử P là một ma trận hoán vị cấp n ìn, ta đặt G’ = S G P. Cho P = (Z 2) , n C = (Z 2) và kí hiệu: K = {( G, S, P, G’)} Trong đó G, S, P đ−ợc xây dựng nh− mô tả ở trên và đ−ợc giữ kín, còn G’ đ−ợc công khai. Với K = ( G, S, P, G’), ta định nghĩa: e K(x,e) = xG’ + e n ở đây e ∈ (Z 2) là một véc tơ ngẫu nhiên có trọng số t. n Bob giải m. bản m. y ∈ (Z 2) theo các b−ớc nh− sau: -1 1. Tính y 1 = yP 2. Giải m. (decode) y 1, Bob tìm đ−ợc y 1 = x 1+e 1, x 1 ∈ C. k 3. Tính x 0 ∈ (Z 2) sao cho x 0G = x 1 -1 4. Tính x = x 0S
  37. Để minh hoạ cho các thủ tục m. và giảI m. ( code and decode ), xét ví dụ sau: Ví dụ 5.11. Ma trận 1 0 0 0 1 1 0   0 1 0 0 1 0 1  G = 0 0 1 0 0 1 1      0 0 0 1 1 1 1  là ma trận sinh của m. Hamming [7,4,3]. Giả sử Bob chọn ma trận S và ma trận P nh− sau: 1 1 0 1   1 0 0 1 S = 0 1 1 1      1 1 0 0  0 1 0 0 0 0 0   0 0 0 1 0 0 0   0 0 0 0 0 0 1 và P = 1 0 0 0 0 0 0   0 0 1 0 0 0 0 0 0 0 0 0 1 0   0 0 0 0 1 0 0 Khi đó ma trận sinh công khai là: 1 1 1 1 0 0 0    1 1 0 0 1 0 0 G'=   1 0 0 1 1 0 1    0 1 0 1 1 1 0  Bây giờ giả sử Alice m. hoá bản rõ x = ( 1, 1, 0, 1) bằng cách dùng một véc tơ sai ngẫu nhiên trọng số 1 có dạng: e = (0, 0, 0, 0, 1, 0, 0). Bản m. tính đ−ợc là: y1 = x G’ + e
  38. 1 1 1 1 0 0 0    1 1 0 0 1 0 0 = (1, 1, 0, 1)   + ()0, 0, 0, 0, 1, 0, 0 1 0 0 1 1 0 1    0 1 0 1 1 1 0  = ()()0, 1, 1, 0, 0, 1, 0 + 0, 0, 0, 0, 1, 0, 0 = (0, 1 , 1, 0, 1, 1, 0) Khi Bob nhận đ−ợc bản m. y, tr−ớc hết anh ta tính: -1 y1 = y P 0 0 0 1 0 0 0   1 0 0 0 0 0 0   0 0 0 0 1 0 0 = ()0, 1, 1, 0, 1, 1, 0 0 1 0 0 0 0 0   0 0 0 0 0 0 1 0 0 0 0 0 1 0   0 0 1 0 0 0 0 = ()1, 0, 0, 0, 1, 1, 1 . Tiếp theo Bob giảI m. y 1 để nhận đ−ợc x 1 = (1, 0, 0, 0, 1, 1, 0) ( Cần -1 để ý là e 1 ≠ e do phép nhân với P ). Sau đó anh ta lập x 0 = (1, 0, 0, 0) ( bốn thành phần đầu tiên của x 1). Cuối cùng Bob tính: -1 x x = S 0 1 1 0 1    1 1 0 0 =  ()1, 0, 0, 0 0 1 1 1    1 0 0 1 = ()1, 1, 0, 1 Đây chính là bản rõ mà Alice đ. m 5.4. Các chú giảI và tàI liệu dẫn. Hệ mật Elgamal đ. đ−ợc mô tả trong [EL 85]. Thuật toán Pohlig- Hellman đ−ợc công bố trong [PH 78], còn các vấn đề liên quan đến các bít
  39. riêng của bàI toán logarithm rời rạc đ−ợc nêu trong tàI liêụ của Perelta [PE 86]. Thông tin thêm về bàI toán logarithm rời rạc có thể tham khảo trong các bàI báo của La Macchima, Odlyzko [LO 91] và của Mc Curley [Mc 90]. Sách tham khảo chính về các tr−ờng hữu hạn của Lidl và Niederreiter [LN 83]. Về chủ đề này, cuốn sách của McEliece [Mc 87]cũng là một giáo trình tốt, còn một chuyên khảo về các nghiên cứu mới nhất trong lĩnh vực áp dụng các tr−ờng hữu hạn là cuốn của Menezes và các tác giả khác [MBGMVY 93]. BàI báo mới nhất về bàI toán logarithm rời rạc trong GF(2 n) là của Gordon và McCurley [GM 93]. ý đồ sử dụng các đ−ờng cong elliptic cho các hệ mật khoá công khai do Kobliz [Ko 87A] và Miller [Mi 86] đ−a ra. Quyển sách của Menezes [ME 93] là một chuyên khảo về hệ mật đ−ờng cong elliptic. Cũng có thể xem bàI báo của Menezes và Vanstone [MV 93] và ch−ơng 6 trong sách của Kobliz [KO 87]. Các đề cập sơ cấp về đ−ờng cong elliptic nên xem trong cuốn của Sileverman và Tate [ST 92]. Ph−ơng pháp suy biến của các logarithm rời rạc của Menezes – Okamoto – Vanstone từ các đ−ờng cong elliptic sang các tr−ờng hữu hạn đ−ợc cho trong [MO 94] ( cũng có thể xem trong [ME 93]). Hệ mật Merkle-Hellman đ−ợc trình bày trong [MH 78]. Hệ mật này đ. bị phá bởi Shamir và một dạng có lặp của hệ thống bị phá bởi Brickell [Br85]. Một hệ thống loạI xếp ba lô khác của Chor và Riverst [CR 88] vẫn ch−a bị phá. Chi tiết hơn có thể xem trong bàI báo tổng quan của Brickell- Olyzko [BO 92]. Sách tham khảo quan trọng nhất về lý thuyết code là cuốn [MS 77] của Mac William và Sloane. Có nhiều giáo trình tốt về lý thuyết code, chẳng hạn của Hoffman và các tác giả khác [HLLPRW 91], của Vanstone, Van Oorchot [VV 89]. Hệ mật McEliece lần đầu tiên đ−ợc mô tả trong [Mc 78]. Một bàI báo gần đây thảo luận về độ mật của hệ thống này đ−ợc trình bày bởi Chabaud [CH 95].
  40. BàI tập 5.1. áp dụng thuật toán Shanks để tìm các logarithm rời rạc trong Z p với p là một số nguyên tố, α là một phần tử nguyên thuỷ. H.y dùng ch−ơng trình của bạn để tìm log 106 12375 trong Z 24691 và log 6 248388 trong Z 458009 . 5.2. á p dụng thuật toán Pohlig-Hellman để tìm các logarithm rời rạc trong Zp, p là số nguyên tố, α là phần tử nguyên thuỷ. H.y dùng ch−ơng trình của bạn tìm log 5 8563 trong Z 28703 và log 10 12611 trong Z 31153 . 5.3. H.y tìm log 5 896 trong Z 1163 bằng cách dùng thuật toán đ−ợc nêu trên hình 5.6. Giả sử rằng, L 2(β)=1 với β = 25, 219 và 841 và L 2(β) = 0 với β = 163, 532,625 và 656. 5.4. H.y giảI m. bản m. Elgamal cho trên bảng 5.3. các tham số của hệ thống là p = 31847, α = 5, a = 7899 và β = 18074. Một phần tử của Z n biểu thị 3 kí tự nh− trong bàI tập 4.6. Bảng 5.3. Bản mW Elgamal (3781,14409) (31552,3930) (27214,15442) (5809,30274) (5400,31486) (19936,721) (27765,29284) (29820,7710) (31590,26470) (3781,14409) (15898,30844) (19048,12914) (16160,3129) (301,17252) (24689,7776) (28856,15720) (30555,24611) (20501,2922) (13659,5015) (5740,31233) (1616,14170) (4294,2307) (2320,29174) (3036,20132) (14130,22010) (25910,19663) (19557,10145) (18899,27609) (26004,25056) (5400,31486) (9526,3019) (12962,15189) (29538,5408) (3149,7400) (9396,3058) (27149,20535) (1777,8737) (26117,14251) (7129,18195) (25302,10248) (23258,3468) (26052,20545) (21958,5713) (346,31194) (8836,25898) (8794,17358) (1777,8737) (25038,12483) (10422,5552) (1777,8737) (3780,16360) (11685,133) (25115,10840) (14130,22010) (16081,16414) (28580,20845) (23418,22058) (24139,9580) (173,17075) (2016,18131) (19886,22344) (21600,25505) (27119,19921) (23312,16906) (21563,7891) (28250,21321) (28327,19237) (15313,28649) (24271,8480) (26592,25457) (9660,7939) (10267,20623) (30499,14423) (5839,24179) (12846,6589) (9284,27858) (24875,17641) (1777,8737) (18825,19671) (31306,11929) (3576,4630) (26664,27572) (27011,29164) (22763,8992) (3149,7400) (8951,29435) (2059,3977) (16258,30341) (21541,19004) (5865,29526) (10536,6941) (1777,8737 ) (17561,11884) (2209,6107) (10422,5552) (19371,21005) (26521,5803) (14884,14280) (4328,8635) (28250,21321) (28327,19237) (15313,28649)
  41. 5.5. H.y xác định đa thức nào trong các đa thức sau là bất khả quy trên Z2[x]: x5 +x 4 +1 x5 +x 3 +1 x5 + x 4 + x 2 +1 5 5 2 5.6. Tr−ờng GF(2 ) có thể đ−ợc xây dựng theo Z 2[x]/(x +x +1). H.y thực hiện các phép tính sau trên các tr−ờng này: a). Tính (x 4 + x 2)ì(x 3 +x +1) b). Sử dụng thuật toán Euclide mở rộng để tính (x 3 +x 2)-1 c). Sử dụng thuật toán bình ph−ơng và nhân để tính x 25 . 5.7. Đây là một ví dụ về hệ mật Elgamal áp dụng trong GF(3 3). Đa thức 3 2 3 2 x +2x +1 là một đa thức bất khả quy trên Z 3[x] và bởi vậy Z 3[x]/(x +2x +1) chính là GF(3 3). Ta có thể gắn 26 chữ cáI của bảng chữ cáI với 26 phần tử khác 0 của tr−ờng và nh− vậy có thể m. hoá một văn bản thông th−ờng theo cách truyền thống. Ta sẽ dùng thứ tự theo từ đIún của các đa thức khác 0 để thiết lập sự t−ơng ứng. A ↔ 1 B ↔ 2 C ↔ x D ↔ x+1 E ↔ x+2 F ↔ 2x G ↔ 2x+1 H ↔ 2x+2 I ↔ x 2 J ↔ x 2+1 K ↔ x 2+2 L ↔ x 2+x M ↔ x 2+x+1 N ↔ x 2+x+2 O ↔ x 2+2x P ↔ x 2+2x+1 Q ↔ x 2+2x+2 R ↔ 2x 2 S ↔ 2x 2+1 T ↔ 2x 2+2 U ↔ 2x 2+x V ↔ 2x 2+2x+1 W ↔ 2x 2+2x+2 X ↔ 2x 2+2x Y ↔ 2x x+2x+1 Z ↔ 2x x+2x+2 Giả sử Bob dùng α = x, a = 11 trong hệ mật Elgamal. Khi đó β = x+2. H.y chỉ ra cách Bob giảI m. bản m. sau ra sao: (K,H) (P,X) (N,K) (H,R) (T,F) (V,Y) (E,H) (F,A) (T,W) (J,D) (U,T) 2 3 5.8. Giả sử E là đ−ờng cong elliptic y = x + x + 28 xác định trên Z 71 a) H.y xác định số các đIểm trên E b) H.y chứng tỏ rằng E không phảI là nhóm cyclic. c) Cấp lớn nhất của một phần tử trong E là bao nhiêu?. H.y tìm một phần tử có cấp này
  42. 2 3 5.9. Cho E là một đ−ờng cong elliptic y = x + x +13 xác định trên Z 31 . Đ. biết rằng #E = 34 và (9,10) là một phần tử cấp 34 trên E. Hệ mật Menezes- * * Vanstone đ−ợc xác định trên E sẽ có không gian bản rõ là Z 34 ì Z 34 . Giả sử số mũ bí mật của Bob là α = 25. a) H.y tính β = a α b) H.y giảI m. bản m. sau: ((4,9),28,7), ((19,28),9,13), ((5,22),20,17), ((25,16),12,27) c) Giả sử rằng mỗi bản rõ biểu thị hai kí tự trong bảng chữ cái. H.y biến đổi bản rõ thành một từ tiếng Anh (ở đây sử dụng phép t−ơng ứng sau: A ↔ 1,. . ., Z ↔ 26 vì 0 không đ−ợc phép có trong một cặp đ−ợc sắp của bản rõ). 5.10. Giả sử hệ mật Merkle-Hellman có một danh sách công khai các cỡ là một véc tơ xếp ba lô sau: t = (1394, 1256, 1508, 1987, 439, 650, 724, 339, 2303, 810). Giả sử thám m. Oscar đ. phát hiện đ−ợc p = 2503. a) Bằng phép thử và sai số h.y xác định giá trị α sao cho danh sách a-1t mod p là một hoán vị của một danh sách siêu tăng. b) H.y chỉ rõ cách giảI m. bản m. 5746. 5.11. Có thể chứng tỏ rằng, ma trận H đ−ợc nêu d−ới đây là một ma trận kiểm tra tính chẵn lẻ của m. (code) BCH [15, 7, 5] 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1    0 1 0 0 1 1 0 1 0 1 1 1 1 0 0    0 0 1 0 0 1 1 0 1 0 1 1 1 1 0  0 0 0 1 0 0 1 1 0 1 0 1 1 1 1  H =   1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1   0 0 1 0 1 0 0 1 0 1 0 0 1 0 1   0 1 1 1 1 0 1 1 1 1 0 1 1 1 1  H.y giảI m. (decode) nếu có thể. Mỗi véc tơ r nhận đ−ợc sau đây bằng ph−ơng pháp giảI m. theo syndrom: a) r = (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) b) r = (1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0) c) r = (1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0)