Chapter 5 - Thủ tục mật mã

- 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.
- 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 Z p , p là số nguyên tố ( hình 5.1.
- 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.
- 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-.
- 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ì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ố,.
- Ta sẽ xác định số nguyên a bằng log α β.
- Cho p là số nguyên tố sao cho bài toán logarithm rời rạc trong Zp là khó giải.
- Bob -ngời biết số mũ bí mật a có thể tính đợc β k từ α k .
- 5.1.1.Các thuật toán cho bài toán logarithm rời rạc..
- Khi đó bài toán logarithm rời rạc có thể đợc phát biểu dới dạng sau:.
- 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ằ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ó lu ý đế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.
- Thuật toán Shanks cho bài toán DL..
- 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).
- Ngợc lại, đối với β bất kì ta có thể viết.
- 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.
- 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.
- Bây giờ ta có thể tính.
- Có thể kiểm tra thấy rằng quả thực mod 809)..
- Giả sử.
- p i là số nguyên tố đặc biệt.
- Ta có thể biểu diễn x theo cơ số q nh sau:.
- Cũng có thể biểu diễn nh sau:.
- a = x + q c s với s là một số nguyên nào đó..
- Trong thuật toán này, α là phần tử nguyên thuỷ theo modulo p, q là số nguyên tố.
- Cần để ý rằng, các đồng d này có thể viết tơng đơng nh sau:.
- 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ử..
- c B log α p B ( mod p-1) Vì mọi giá trị đều đả biết trừ giá trị log α β nên có thể dễ dàng tìm.
- Bản chất của bài toán: I = (p, α , β , i) trong đó p là số nguyên tố , α∈ Z p * là phần tử nguyên thuỷ, β ∈ Z p * và i là một số nguyên sao cho 1 ≤ i.
- 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..
- 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ả.
- Khi đó có thể chỉ ra rằng, dễ dàng tính đợc L i ( β ) nếu 1 ≤ s.
- 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.
- Giả sử α a ≡ β (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ì.
- 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á.
- 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 L 2 đợc tính theo thuật toán giả định).
- Bởi vậy, log ta có thể dễ dàng kiểm tra đợc giá.
- 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.
- Có thể chứng minh bằng phơng pháp quy nạp rằng:.
- 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.
- 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.
- 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..
- 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.
- Bài toán logarithm rời rạc trong (G,0).
- Đặc trng của bài toán: I = (G, α , β.
- Bây giờ ta sẽ trở lại bài toán DL tổng quát hoá .
- 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.
- 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.
- 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..
- 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.
- đó có thể giải để tìm a và nhận đợc.
- Giả sử α ∈ G là một phần tử sao cho bài toán DL trong H là khó.
- ở 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ố .
- 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.
- 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..
- 1là số nguyên.
- Giả sử p là số nguyên tố.
- Giả sử f(x), g(x), h(x.
- Điều này có thể thực hiện theo cách chia các đa thức thông thờng..
- Cần nhớ lại rằng, Z m là một trờng khi và chỉ khi m là số nguyên tố và các phần tử nghịch đảo nhân có thể tìm đợc qua thuật toán Euclide.
- 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..
- Đ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].
- 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ử.
- 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 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.
- Cuối cùng, có thể chỉ ra rằng, không tồn tại một trờng hữu 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)..
- Nhóm này sẽ cho các ví dụ về các nhóm cyclic trong đó bài toán DL có thể.
- Phơng pháp tính toán chỉ số có thể sửa.
- 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".
- [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 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ó.
- Cho p >3 là số nguyên tố.
- 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.
- Để làm điều đó, xét mỗi giá trị có thể x ∈ Z 11 , tính x 3 +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.
- Khi đó ta có thể tính các "luỹ thừa".
- 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:.
- 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ó..
- Cho E là một đờng cong elliptic trên Z p , p là số nguyên tố >.
- 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..
- 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 cha 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..
- 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ã).
- 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 = Z p * ì Z p.
- Bài toán tổng các tập con.
- Đặc trng của bài toán: I = (s 1 , s 2

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt