Chuyên Đề BÁO CÁO CHUYÊN ĐỀ NGHIÊN CỨU KHOA HỌC TRONG SINH VIÊN NĂM 2009 Chuyên đề: Thám hệ mật RSA dựa vào ng

MỤC LỤC
Mục lục . Trang 2
Lời mở đầu 4
Phần 1: Hệ mật RSA . 5
1.1. Lịch sử phát triển . 5
1.2. Tổng quan . 6
1.3. Các biến thể RSA . 13
1.4. Mã thám . 17
1.4.1. Phân tích N . 18
1.4.2. Phương pháp vét cạn và tấn công “gặp nhau ở giữa”
lên d, d[SUB]p[/SUB], d[SUB]q[/SUB] . 18
1.4.3. Tấn công kênh kề . 18
1.4.4. Tấn công dựa theo thời gian . 20
1.4.5. Tấn công lựa chọn thích nghi bản mã . 20
Phần 2: Nghiệm nhỏ của đa thức . 21
2.1. Tổng quan về lưới 21
2.1.1. Định nghĩa về lưới 21
2.1.2. Lưới nguyên . 21
2.1.3. Bài toán quy hoạch lưới (giàn) LLL . 24
2.1.3.1. Lịch sử nghiên cứu giàn 24
2.1.3.2. Mô tả các chức năng của thuật toán thu gọn giàn 25
2.1.3.3. Hiệu suất của thuật toán LLL về lý thuyết . 26
2.1.3.4. Hiệu suất của thuật toán LLL trong thực tế . 27
2.1.3.5. Các kết quả đã được tính trong thực tế 28
2.2. Phương pháp Coppersmith 28
2.2.1. Nghiệm nhỏ của đa thức f[SUB]N[/SUB](x) 29
2.2.2. Nghiệm nhỏ của đa thức nhiều biến f[SUB]N[/SUB](x[SUB]1[/SUB],x[SUB]2[/SUB], ,x[SUB]N[/SUB]) . 30
2.3. Chiến lược tổng quát trong lựa chọn phương pháp 33
2.3.1. Nghiệm nhỏ của Modulo 33
2.3.2. Chiến lược cơ bản . 35
2.3.3. Chiến lược mở rộng 38
2.4. Độ phức tạp tính toán của phương pháp Coppersmith . 41
Kết luận . 43
Tài liệu tham khảo . 44
Nhận xét của giáo viên hướng dẫn 45























LỜI MỞ ĐẦU
Kỹ thuật mật mã (cryptology) là môn khoa học bao gồm hai lĩnh vực: mật mã(cryptography) và thám mã (crytoanalysis).
Mật mã là lĩnh vực khoa học về các phương pháp biến đổi thông tin nhằm mục đích bảo vệ thông tin khỏi sự truy cập của những người không có thẩm quyền.
Thám mã là lĩnh vực khoa học chuyên nghiên cứu,tìm kiếm yếu điểm của các hệ mật để từ đó đưa ra các phương pháp tấn công các hệ mật đó.
Mật mã và thám mã là hai lĩnh vực đối lập nhau nhưng gắn bó mật thiết với nhau.Không thể xây dựng một hệ mật tốt nếu không có hiểu biết sâu về thám mã.Thám mã chỉ ra yếu điểm của hệ mật.Yếu điểm đó có thể được sử dụng để cải tiến cho hệ mật tốt hơn.Nếu người xây dựng hệ mật không có hiểu biết rộng về mã thám,không kiểm tra độ an toàn của hệ mật trứoc các phương pháp tấn công thì hệ mật đó sẽ kém hiệu quả.Trong bài nghiên cứu này tôi xin đề cập đến cả hai vấn đề của kỹ thuật mật mã đó là tìm hiểu về Hệ mật RSA và Phương pháp thám RSA bằng phương pháp nghiệm nhỏ của đa thức mà ở đây là phương pháp Coppersmith
Trong bải này chúng tôi sẽ tiến hành tìm hiểu về các phần chính sau:
Phần 1:Hệ mật RSA.Phần này chúng tôi sẽ đưa ra những hiểu biết chính của mình về hệ mật RSA và những phương pháp thám RSA cơ bản và phổ biến.
Phần 2: Nghiệm nhỏ của đa thức.Phần này chúng tôi sẽ tìm hiểu về khái niệm nghiệm nhỏ của đa thức,tìm hiểu về giàn (lưới),và phương pháp Copper smith.
Phần 3: Tổng kết. Phần này đánh giá về phương pháp thám RSA bằng nghiệm nhỏ của đa thức.đưa ra ưu nhược điểm của phương pháp