tailieunhanh - Hệ Mật Mã Elgamal - Sinh Tham Số An Toàn phần 3

Thuật ngữ mật mã hóa khóa bất đối xứng thường được dùng đồng nghĩa với mật mã hóa khóa công khai mặc dù hai khái niệm không hoàn toàn tương đương. | CHƯƠNG I. VAI TRÒ CỦA số NGUyÊN TỐ DẠNG p 2q 1 TRONG MẬT MÂ. Từ giả thiết gcd t q 1 nên tồn tại t-1 mod q và do ó từ 1-5 ta có ngay x -st-1 mod q và ây là iều cần chứng minh. Kỹ thuật ể tìm cặp s t nêu trong kết quả ược thực hiện như sau. Chọn B là một số nguyên nào ó gọi là ngưỡng của cơ sở phân tích giả sử m là số các số nguyên tố không quá B sau ó tiến hành các bước sau Bước m 1 cặp số si9ti i 1 m 1 thoả mãn iều kiện m sSlatl mod p vin pỌịÌ J với 0 ai j q 1-6 . 7 1 Ký hiệu véc tơ Pi ai 1 ai 2 . a m với i 1 m 1 rõ ràng hệ m 1 véc tơ trong không gian m chiều nên phải phụ thuộc tuyến tính tức là tồn tại bộ m 1 số k1 k2 . km 1 không ồng thời bằng 0 với 0 ki q sao cho. k1P1 k2P2 . km 1Pm 1 e 0 0 . 0 . 1-7 . Bước 2. Tìm bộ k1 k2 . km 1 nói trên. Lấy s k1s1 k2s2 . km 1sm 1 và t k1t1 k2t2 . km 1tm 1 dễ dàng kiểm tra ược s t thoả mãn iều kiện 8sat wq mod p . Chú ý rằng bước 1 ược thực hiện theo cách Lấy-Kiểm tra cho ến khi tìm ược ầy ủ số cặp theo yêu cầu còn việc làm của bước 2 chính là giải một hệ phương trình ại số tuyến tính hệ số trên GF q mà hệ này luôn có nghiệm. Tóm lại ta luôn tìm ược cặp s t theo mong muốn tuy nhiên ể có thể ưa ra một dẫn giải tường minh về thời gian tính của thuật toán này là một iều không ơn giản. Chúng ta bằng lòng với kết quả ã ược công bố về thời gian tính của phương pháp sàng bậc q như sau xem Stinson . Kết quả . Thời gian tính tiệm cận của thuật toán sàng bậc q để tìm được logarit trên trường GF p là L p exp 1 O 1 ln2 q 1-8 . ở trên q là ước nguyên tố lớn nhất của p-1 còn O 1 là một vô cùng bé khi q X . ĐỀ TÀI SINH sô THAM số CHO HỆ MẬT ELGAMAL. 15 CHƯƠNG I. VAI TRÒ CỦA số NGUyÊN TỐ DẠNG p 2q 1 TRONG MẬT MÂ. Thuật toán sàng trường số Giống như ý tưởng của thuật thoán sàng bậc q phương pháp sàng trường số cũng thực hiện theo kiểu tìm cặp s t sao cho 8sat wq mod p sự khác biệt cơ bản là thay vì việc tìm các cặp s t trên trực tiếp trên GF p của sàng bậc q thì sàng trường số lại đi tìm chứng trong trường mở rông K