tailieunhanh - Lý thuyết mật mã - Chương 4

Kiểm tra tính nguyên tố xác suất Để thiết lập hệ mật RSA, ta phải tạo ra các số nguyên tố ngẫu nhiên lớn (chẳng hạn có 80 chữ số). Trong thực tế, ph-ơng cách thực hiện điều này là: tr-ớc hết phải tạo ra các số ngẩu nhiên lớn, sau đó kiểm tra tính nguyên thuỷ của chúng bằng cách dùng thuật toán xác suất Monte- Carlo thời gian đa thức (chẳng hạn nh- thuật toán Miller- Rabin hoặc là thuật toán Solovay- Strasen). Cả hai thuật toán trên đều đ-ợc trình bày trong phần này. Chúng là các. | Vietebooks Nguyễn Hoàng Cương CHƯƠNG 4 KIỂM TRA TÍNH NGUyÊN Tố XÁC SUẤT Để thiết lập hệ mật RSA ta phải tạo ra các số nguyên tố ngẫu nhiên lớn chẳng hạn có 80 chữ số . Trong thực tế phương cách thực hiện điều này là trước hết phải tạo ra các số ngẩu nhiên lớn sau đó kiểm tra tính nguyên thuỷ của chúng bằng cách dùng thuật toán xác suất Monte- Carlo thời gian đa thức chẳng hạn như thuật toán Miller- Rabin hoặc là thuật toán Solovay- Strasen . Cả hai thuật toán trên đều được trình bày trong phần này. Chúng là các thuật toán nhanh tức là một số nguyên n được kiểm tra trong thời đa thức theo log2n là số các bít trong biểu diện nhị phân của n . Tuy nhiên vẫn có khả năng là thuận toán cho rằng n là số nguyên tố trong khi thực tế n là hợp lệ số. Bởi vậy bằng cách thay đổi thuật toán nhiều lần có thể giảm xác suất sai số dưới một mức ngưỡng cho phép sau này sẽ thảo luận kỹ hơn một chút về vấn đề này . Một vấn đề quan trọng khác là cần phải kiểm tra bao nhiêu số nguyên ngẫu nhiên với kích thươc xác định cho tới khi tìm được một số nguyên tố. Một kết quả nỗi tiếng trong lý thuyết số được gọi là định lý số nguyên tố phát biểu rằng số các số nguyên tố không lớn hơn N xấp xỉ bằng N ln N. Bởi vậy nếu p được chọn ngẫu nhiên thì xác suất p là một số nguyên tố sẽ vào khoảng 1 ln p. Với một mođun 512 bít ta có 1 ln p 1 77. Điều này có nghĩa là tính trung bình cư 177 số nguyên ngẫu nhiên p với kích thước tương ứng sẽ có một số là số nguyên tố. Dĩ nhiên nếu chĩ hạn chế xét các số nguyên lẻ thì xác suất sẽ tăng gấp đôi tới khoảng 2 177 . Bỡi vậy trên thực tế hoàn toàn có khả năng tạo được các nguyên tố đủ lớn và do đó về mặt thực thể ta có thể thiết lập được một hệ mật RSA. Sau đây sẽ tiếp tục xem xét điều này được thực hiên như thế nào. Một bài toán quyết định là một bài toán toán trong đó một câu hỏi cần được trả lời có hoặc không . Một thuật toán xác suất là một thuật toán bất kỳ có sử dụng các số ngẫu nhiên ngược lại thuật toán không sử dụng các số ngẫu nhiên sẽ được gọi là một .

• An ninh - Bảo mật
• Lý thuyết thông tin
• hệ mật
• khoa học mật mã
• an ninh máy tính
• bảo mật dữ liệu
• Bài giảng Lý thuyết thông tin
• Môn học lý thuyết thông tin
• Giới thiệu môn học lý thuyết thông tin
• Lịch sử môn Lý thuyết thông tin
• Vai trò lý thuyết thông tin
• Nôi dung lý thuyết thông tin
• hệ thống thông tin
• giáo trình Lý thuyết thông tin
• tài liệu Lý thuyết thông tin
• đề cương Lý thuyết thông tin
• bài tập Lý thuyết thông tin
• Độ do lượng tin
• sinh mã tách được
• kênh thông tin rời rạc không nhớ
• sửa lỗi kênh truyền
• Xử lý tín hiệu
• Lý thuyết thông tin thống kê
• Đô lượng thông tin
• Entropy có điều kiện
• tài liệu học đại học
• Lý thuyết hệ thống thông tin
• Mô hình hệ thống thông tin
• Thông tin có giá trị
• Các dạng thông tin
• Bài giảng Hệ thống thông tin quản lý
• Hệ thống thông tin quản lý
• Thông tin quản lý
• Chiến lược thông tin
• Thông tin xử lý giao dịch
• Lý thuyết hệ thống
• Phân loại hệ thống thông tin
• bài giảng về lý thuyết thông tin
• kỹ thuật thông tin liên lạc
• bài giảng về công nghệ viễn thông
• Đề thi môn Lý thuyết thông tin
• Trắc nghiệm Lý thuyết thông tin
• Công nghệ thông tin
• Kỹ thuật viễn thông
• Thành phần của hệ thống thông tin
• Xử lý thông tin
• Nguồn lực phần mềm
• Nguồn rời rạc
• Nghiên cứu lý thuyết thông tin
• Lượng tin xác suất
• Lượng tin có điều kiện
• Mã hóa thông tin
• Phương pháp mã hóa
• Giải mã thông tin
• Mật mã thông tin
• Hệ liên tục