Tiểu Luận tìm hiểu về RSA và Elliptic

MỤC LỤC TRANG
LỜI CẢM ƠN 3
Chương 1: AN TOÀN BẢO MẬT THÔNG TIN 4
1.1 Mật mã học. 4
1.2 Khái niệm hệ mã mật 5
Chương 2: KIẾN THỨC TOÁN HỌC 8
2. 1 Chia hết 8
2.2 MODULUS. 8
2.2.1 Định nghĩa : 8
2.2.2 Các phép toán. 9
2.3 ƯỚC CHUNG LỚN NHẤT - GCD (Greatest Common Divisor). 10
2.3.1 Thuật toán tìm ước chung lớn nhất của 2 số nguyên. 11
2.4 NGUYÊN TỐ 13
2.4.1 Số nguyên tố. 13
2.4.2 Lịch sử. 14
2.4.3 Nguyên tố cùng nhau : 14
2.4.4 Phi ơle. 14
2.5 PHẦN TỬ NGHỊCH ĐẢO 15
2.5.1 Thuật Toán Euclidian mở rộng : 15
2.5.2 Thuật toán lũy thừa nhanh. 17
2.6 GROUP , FIELD VÀ RING 18
2.6.1 Nhóm hữu hạn. 19
2.6.2 Nhóm vô hạn và nhóm abelian. 20
2.7 THUẬT TOÁN XÁC SUẤT SỐ NGUYÊN TỐ 27
2.7.1 ĐẶC ĐIỂM CỦA RABIN MILLER 28
2.7.2 THUẬT TOÁN 28
2.7.3 ÁP DỤNG THUẬT TOÁN VỚI SỐ NGUYÊN TỐ 28
2.7.4 ÁP DỤNG THUẬT TOÁN VỚI HỢP SỐ 29
2.7.5 PHỎNG ĐOÁN SỐ LƯỢNG CƠ SỞ KHÔNG CHẮC CHẮN CỦA N = P*Q 30
Chương 3: HỆ MẬT RSA 47
3.1 GIỚI THIỆU 47
3.2 LỰA CHỌN MODULO 48
3.3 CHỨNG MINH RSA 49
3.4 CÁC BƯỚC TẠO KHÓA RSA 50
Chương 4: HỆ MẬT ECC 52
4.1 ĐỊNH NGHĨA 52
4.2 MÔ TẢ HÌNH HỌC CỦA PHÉP CỘNG 54
4.4 ELLIPTIC TRÊN TRƯỜNG HỮU HẠN NGUYÊN TỐ 56
4.4.1 ĐỊNH NGHĨA 56
4.4.2 QUY TẮC CỘNG 56
TÀI LIỆU THAM KHẢO: 65



























LỜI CẢM ƠN Tôi xin cảm ơn thầy Nguyễn Văn Thắng đã giúp đỡ tôi thực hiện báo cáo tốt nghiệp
GIỚI THIỆU :
Ngày nay với sự bùng nổ của công nghệ thông tin thì vấn đề về bảo mật của những thông tin nhạy cảm càng được để ý tới như hệ thống bảo mật của ngân hàng, bản quyền phần mềm ,thông tin của chính phủ . Vì vậy có rất nhiều hệ mật được đưa ra cùng với những ưu điểm và đáp ứng như cầu hiện tại của con người.Đặc biệt là các hệ mật dựa trên các thuật toán mã hóa công khai như RSA và Elliptic mà chúng ta sẽ đề cập tới như là nội dung chính của báo cáo này. Hệ mật RSA và Elliptic là một trong những hệ mật được đánh giá là an toàn nhất tuy vậy tài liệu về hệ mật này ở Việt Nam còn hạn hẹp để nghiên cứu. với mục đích cho người đọc hiểu biết những kiến thức cơ bản nhất về hai hệ mật trên cùng với những kiến thức cơ sở về toán học, số học nhằm phục vụ cho những người muốn tìm hiểu về RSA và Elliptic.

Chương 1: AN TOÀN BẢO MẬT THÔNG TIN Trải qua nhiều thế kỉ hàng loạt các giao thức và các cơ chế đã được tạo ra để đáp ứng nhu cầu an toàn bảo mật thông tin khi mà nó được truyền tải trên các phương tiện vật lý giấy báo, sách thường thì các mục tiêu của an toàn bảo mật thông tin không thể đạt được nếu chỉ đơn thuần dựa vào các thuật toán toán học và các giao thức , mà để đạt được điều này đòi hỏi cần có các kỹ thuật mang tính thủ tục và sự tôn trọng các điều luật . chẳng hạn sự bí mật của các bức thư hay do sự phát tán các lá thư đã có đóng dấu bởi một dịch vụ thư tín đã được chấp nhận. Tính an toàn về mặt vật lý của các lá thư là hạn chế nên đảm bảo bí mật của các bức thu pháp luật đã quy định việc xem thư mà không được sự đồng ý của chủ nhân hoặc người có thẩm quyền sẽ bị trừng phạt . Đôi khi mục địch của an toàn bảo mật thông tin lại đạt được nhờ chính phương tiện vật lý mang chúng , chẳng hạn như tiền giấy đòi hỏi phải được in bằng các loại mực và giấy tốt để không bị làm giả
Về mặt ý tưởng việc lưu trữ thông tin là không có nhiều thay đổi đáng kể qua thời gian. Ngày xưa thông tin thường được lưu giữ vận chuyển trên giấy tờ trong khi giờ đây chúng được lưu dưới dạng số hóa được vận chuyển bằng các hệ thống viễn thông hoặc hệ thống không dây .Tuy nhiên sự thay đổi đáng kể đến ở đây chính là khả năng sao chép và thay đổi thông tin . Người ta có thể tạo ra hàng ngàn mẩu tin giống nhau và không thể phân biệt nó với bản gốc và điều cần thiết đối với xã hội thông tin là hầu hết được lưu trữ và vận chuyển trên các phương tiện điện tử chính là các phương tiện đảm bảo an toàn bảo mật thông tin độc lập với các phương tiện lưu trữ và vận chuyển vật lý của nó .Phương tiện đó chính là mật mã học một ngành lịch sử lâu đời dựa trên nền tảng thuật toán toán học , số học xác suất và các môn khoa học khác.
1.1 Mật mã học Mật mã học gồm hai lĩnh vực mã hóa và thám mã trong đó
Mã hóa nghiên cứu các thuật toán và phương thức để đảm bảo tính bí mật và xác thực của thông tin . Các sản phẩm của lĩnh vực này là các hệ mã mật, các hàm băm các hệ chứ ký điện tử các cơ chế phân phối , quản lý và các giao thức mật mã.
Thám mã : nghiên cứu các phương pháp phá mã hoặc tạo mã giả . Sản phẩm của lĩnh vực này là các phương pháp thám mã, các phương pháp giả mạo chữ ký , các phương pháp tấn công các hàm băm và các giao thức mật mã .
Mã hóa : là một ngành khoa học của các phương pháp truyền tin bảo mật
Quy ước của mã hóa :
Người ta quy ước những từ , những ký tự của văn bản gốc có thể hiểu được là PlainText .Các từ, những ký tự trong một văn bản nào đó mà không thể hiểu được thì gọi là bản mã Ciphertext
Có 2 phương thức mã hóa cơ bản : thay thế và hoán vị
- Phương thức mã hóa thay thế là phương thức mã hóa mà từng ký tự gốc hay một nhóm ký tự của bản rõ được thay thế bởi các từ , các ký hiệu khác hay kết hợp với nhau cho phù hợp với một phương thức nhất định và khóa
- Phương thức mã hóa hoán vị là phương thức mã hóa mà các từ mã của bản rõ được săp xếp theo một phương thức nhất định
Các hệ mật thường sử dụng kết hợp cả 2 kỹ thuật này
1.2 Khái niệm hệ mã mật Một hệ mật mã là một bộ gồm 5 thành phần (P, C, K, E,D) thỏa mãn các điều kiện sau:
· P là không gian bản rõ : tập hợp hữu hạn các bản rõ có thể

· C là không gian bản mã : tập hữu hạn các bản mã có thể
· K là không gian khóa : là tập hữu hạn các khóa có thể
Với mỗi k thuộc K , có một quy tắc mã hóa e[SUB]k[/SUB] thuộc E và một quy tắc tương ứng d[SUB]k[/SUB] thuộc D với mỗi e[SUB]k[/SUB] : Pà Cvà d[SUB]k[/SUB] : Cà P là những hàm mà d[SUB]k[/SUB](e[SUB]k[/SUB](x)) = x cho mọi bản rõ x thuộc P . Hàm giải mã d[SUB]k[/SUB] chính là ánh xạ ngược của hàm mã hóa e[SUB]k[/SUB]