Luận Văn Các phương pháp tấn công rsa

TÓM TẮT NỘI DUNG


Hệ mật RSA được phát minh bởi Ron Rivest, Adi Shamir, và Len Adleman, công bố lần đầu vào tháng 8 năm 1977. Hệ mật sử dụng trong lĩnh vực đảm bảo tính riêng tư và cung cấp cơ chế xác thực của dữ liệu số. Ngày nay, RSA đã được phát triển ứng dụng rộng rãi trong thương mại điện tử và đặc biệt nó là hạt nhân của hệ thống thanh toán điện tử.

Ngay từ khi được công bố lần đầu, hệ RSA đã được phân tích hệ số an toàn bởi nhiều nhà nghiên cứu. Mặc dù đã trải qua nhiều năm nghiên cứu và đã có một số cuộc tấn công ấn tượng nhưng không mang lại kết quả là phá huỷ. Đa phần họ mới chỉ ra được những mối nguy hiểm tiềm ẩn của RSA mà khi sử dụng RSA người dùng cần cải thiện.

Thực tế vấn đề thám mã đối với hệ mật RSA hiện tại đang được các nhà nghiên cứu tập trung khai thác các sơ hở của RSA như: tấn công vào số mũ công khai hoặc số mũ bí mật thấp, tấn công vào các tham số nguyên tố p, q bé hoặc cách xa nhau lớn, hoặc tập trung vào việc phân tích nhân tử số n(modul của RSA).

Luận văn của em sẽ trình bày các phương pháp tấn công RSA trong vòng 20 năm trở lại đây và lựa chọn môt phương pháp tấn công phổ biến để demo.














Mục lục

MỞ ĐẦU 1

Chương 1. CÁC KHÁI NIỆM CƠ BẢN 2

1.1 Một số khái niệm toán học 2

1.1.1 Số nguyên tố và nguyên tố cùng nhau 2

1.1.2 Đồng dư thức 2

1.1.3 Không gian Zn và Zn* 3

1.1.4 Phần tử nghịch đảo 3

1.1.5 Khái niệm nhóm, nhóm con, nhóm Cyclic 4

1.1.6 Hàm Ф Euler 4

1.1.7 Các phép toán cơ bản trong không gian modulo 5

1.1.8 Độ phức tạp tính toán 5

1.1.9 Hàm một phía và hàm một phía có cửa sập 6

1.2 Vấn đề mã hóa 7

1.2.1 Giới thiệu về mã hóa 7

1.2.2 Hệ mã hóa 7

1.2.3 Những tính năng của hệ mã hóa 8

Chương 2. TỔNG QUAN VỀ MÃ HOÁ CÔNG KHAI MÃ THÁM 9

2.1 Mã hoá khoá công khai 9

2.1.1 Đặc điểm của Hệ mã khoá công khai 9

2.1.2 Nơi sử dụng Hệ mã hóa khoá công khai 10

2.2 Các bài toán liên quan đến hệ mã hoá khoá công khai 10

2.2.1 Bài toán phân tích số nguyên thành thừa số nguyên tố 11

2.2.2 Bài toán RSA (Rivest-Shamir-Adleman) 11

2.2.3 Bài toán thặng dư bậc hai 11

2.2.4 Bài toán tìm căn bậc hai mod n 12

2.2.5 Bài toán lôgarit rời rạc 13

2.2.6 Bài toán lôgarit rời rạc suy rộng 13

2.2.7 Bài toán Diffie-Hellman 13

2.2.8 Bài toán giải mã đối với mã tuyến tính 14

2.3 Vấn đề thám mã 16

Chương 3. TỔNG KẾT NHỮNG KẾT QUẢ TẤN CÔNG VÀO HỆ MẬT RSA TRONG NHỮNG NĂM QUA 19

3.1 Một số giả thiết ngầm định 19

3.2 Phân tích các số nguyên lớn 19

3.3 Các tấn công cơ bản 20

3.3.1 Modul chung 20

3.3.2 Mù (Blinding) 21

3.4 Số mũ riêng bé (Low Private Exponnent) 21

3.4.1 Độ lớn e 22

3.4.2 Sử dụng CRT 22

3.5 Số mũ công khai bé (Low public Exponent) 23

3.5.1 Hastad's Broadcast Attack. 23

3.5.2 Franklin-Reiter Related Message Attack. 24

3.6 Thành phần công khai bé 24

3.6.1 Coppersmith's Short Pad Attack. 25

3.6.2 Tấn công bằng khóa riêng. 25

3.7 Cài đặt các tấn công. 26

3.7.1 Tấn công dựa trên thời gian. 27

3.7.2 Tấn công dựa trên các lỗi ngẫu nhiên. 28

3.8 Một số tấn công bằng nhân tử hóa số N với số N lớn 29

3.8.1 Tìm nhân tử lớn nhất thứ nhất 29

3.8 2 Phân tích thứ hai. 30

3.8.3 Phân tích thứ ba 31

3.8.4 Thuật toán Pollard (p-1) 32

3.9 Kết luận 33

Chương 4. THƯ VIỆN TÍNH TOÁN SỐ LỚN 34

4.1 Biểu diễn số lớn. 34

4.2 Các phép toán trong số lớn 35

4.2.1 So sánh hai số 35

4.2.2 Cộng hai số lớn dương. 36

4.2.3 Trừ hai số lớn dương 36

4.2.4 Phép nhân hai số lớn. 37

4.2.5 Phép chia hai số lớn dương. 38

4.2.6 Lũy thừa 40

4.2.7 Ước chung lớn nhất 41

4.2.8 Phép nhân theo module p 42

4.2.9 Tìm phần từ nghịch đảo theo module p 42

4.2.10 Phép cộng có dấu 43

4.2.11 Phép trừ có dấu 44

4.3.12 Phép nhân có dấu 44

Chương 5. PHƯƠNG PHÁP TẤN CÔNG BẰNG 45

NHÂN TỬ HOÁ SỐ N SỬ DỤNG ĐỊNH LÝ FERMAT 45

5.1 Bổ đề 1 45

5.2 Định lý Fermat 45

KẾT LUẬN 48