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

Tình trạng này giống như tình hình giữa bài toán thừa số nguyên và phép nhân các số nguyên. Chúng đều có thể dùng để xây dựng cấu trúc cho một hệ mật mã. | CHƯƠNG III. CHƯƠNG TRÌNH SINH số NGUyÊN TỐ MẠNH CHO HỆ MẬT ELGAMAL. VIỆC SINH CÁC số NGUyÊN Tố MẠNH VÀ GẦN MẠNH Khái niệm số nguyên tố mạnh và gần mạnh Mục đích của đề tài là tìm những số nguyên tố dạng p 2q 1 với q cũng là số nguyên tố những số nguyên tố này với tư cách là tham số modulo cho ĐỀ TÀI SINH sô THAM số CHO HỆ MẬT ELGAMAL. 40 CHƯƠNG III. CHƯƠNG TRÌNH SINH số NGUyÊN TỐ MẠNH CHO HỆ MẬT ELGAMAL. các hệ mật mà độ mật dựa vào tính khó giải của bài toán logarit trên trường GF p sẽ làm cho hệ mật đạt được tính an toàn cao nhất và cũng chính vì vậy mà chúng được gọi là các số nguyên tố mạnh. Cũng đạt được tính năng không thua kém mấy về độ an toàn là các số dạng p Rq 1 với R p cụ thể ở đây R logp cụ thể là nếu như bài toán logarit chỉ để lộ duy nhất 1 bit có ý nghĩa thấp nhất nếu dùng các số nguyên tố mạnh thì nó cũng sẽ chỉ để lộ logR bit thấp nhất nếu dùng các số dạng p Rq 1 cho nên việc sử dụng các số nguyên tố dạng này cũng có thể được chấp nhận trong các hệ mật nói trên. Định nghĩa dưới đây là một sự thống nhất trước về mặt khái niệm các đối tượng chúng ta quan tâm trong đề tài này. Định nghĩa . Số nguyên tốp Rq 1 với q cũng là nguyên tố được gọi là số nguyên tố gần mạnh nếu R ogq. trường hợp R 2 thì p được gọi là số nguyên tố mạnh. Số nguyên tố q nêu trong trên được gọi là nhân nguyên tố của số nguyên tốp. Việc kiểm tra tính gần mạnh của một số được dựa vào kết quả sau đây. Định lý . Cho p Rq 1 với q nguyên tố và Rđog q 3-6 . Khi đó p là nguyên tố khi và chỉ khi thoả mãn các điều kiện sau a . 2p-1 1 modp 3-7 . b . gcd 2R-1 p 1 3-8 . Chứng minh. Điều kiện cần là hiển nhiên. Ngược lại từ điều kiện 3-6 là R log q ta có 2 p-1 q 2R p vì vậy hiển nhiên 2 p-1 V1 mod p cùng với điều kiện 3-8 thì giá trị 2 chính là bằng chứng để p thoả mãn điều kiện của định lý Pocklington do đó p là số nguyên tố và theo định nghĩa nó là số nguyên tố gần mạnh. ĐỀ TÀI SINH sô THAM số CHO HỆ MẬT ELGAMAL. 41 CHƯƠNG III. CHƯƠNG TRÌNH SINH số NGUyÊN TỐ MẠNH CHO HỆ .