Luận Văn Chữ kí số Elgamal

Lời mở đầu

Một sơ đồ chữ kí số thường chứa hai thành phần : Thuật toán kí và thuật toán xác minh . Người A có thể kí bức điện x dùng thuật toán kí an toàn . Chữ kí Sig(x) nhận được có thể kiểm tra bằng thuật toán xác minh công khai Ver . Khi cho trước cặp (x,y) thuật toán xác minh cho giá trị TRUE hay FALSE tuỳ thuộc vào việc chữ kí được xác thực như thế nào

Nghiên cứu một số loại tấn công chữ ký số

GIỚI THIỆU
Con người luôn có nhu cầu trao đổi thông tin với nhau. Nhu cầu đó tăng cao khi các công nghệ mới ra đời đáp ứng cho việc trao đổi thông tin ngày càng nhanh. Chúng ta vẫn không quên việc chiếc máy điện thoại ra đời đã là bước tiến vượt bậc trong việc rút ngắn khoảng cách đáng kể cả về thời gian và không gian giữa hai bên muốn trao đổi thông tin. Những bức thư hay điện tín được gửi đi nhanh hơn khi các phương tiện truyền thông phát triển. Đặc biệt hơn là từ khi Internet xuất hiện, dường như yêu cầu trao đổi thông tin của chúng ta được đáp ứng ngay khi ấn phím “send”. Sẽ còn rất nhiều tiện ích mà các công nghệ mới đã đem lại cho chúng ta trong mọi lĩnh vực Kinh tế-Văn hóa-Giáo dục-Y tế .
Ích lợi của Internet mang lại đối với xã hội là vô cùng, nhưng cũng không thể không kể đến những mặt trái của nó khi con người sử dụng nó với mục đích không tốt. Vì vậy mà đối với những thông tin quan trọng khi truyền trên mạng như những bản hợp đồng ký kết, các văn kiện mang tính bảo mật . thì vấn đề quan tâm nhất đó là có truyền được an toàn hay không?
Do vậy để chống lại sự tấn công hay giả mạo, thì nảy sinh yêu cầu là cần phải làm thế nào cho văn bản khi được gửi đi sẽ “không được nhìn thấy”, hoặc không thể giả mạo văn bản, dù có xâm nhập được vào văn bản. Nhu cầu đó ngày nay đã được đáp ứng khi công nghệ mã hóa và chữ ký số ra đời. Với công nghệ này, thì đã trợ giúp con người giải quyết được bài toán nan giải về bảo mật khi trao đổi thông tin.
Cùng với sự phát triển của mật mã khóa công khai, người ta đã nghiên cứu và đưa ra nhiều phương pháp, nhiều kỹ thuật ký bằng chữ ký số ứng dụng trong các hoạt động kinh tế, xã hội. Chẳng hạn như các ứng dụng trong thương mại điện tử, các giao dịch của các chủ tài khoản trong ngân hàng, các ứng dụng trong chính phủ điện tử đòi hỏi việc xác nhận danh tính phải được đảm bảo.
Ngày nay chữ ký số được sử dụng trong nhiều lĩnh vực như trong kinh tế với việc trao đổi các hợp đồng giữa các đối tác kinh doanh, trong xã hội là các cuộc bỏ phiếu kín khi tiến hành bầu cử từ xa, hay trong các cuộc thi phạm vi rộng lớn.
Một số chữ ký đã được xây dựng là: chữ ký RSA, chữ ký ELGAMAL, chữ ký DSS, chữ ký RABIN . Mặc dù các chữ ký số còn nhiều hạn chế như là về kích thước chữ ký, hay khả năng chống giả mạo chưa cao . nhưng những khả năng mà nó đem lại là rất hữu ích.
RSA (Rivest-Shamir-Adleman): năm 1977, R.1. Rivest, A. Shamir và L.M. Adleman đề xuất một hệ mật mã khóa công khai mà độ an toàn của hệ dựa vào bài toán khó “phân tích số nguyên thành thừa số nguyên tố”, hệ này trở thành một hệ nổi tiếng và mang tên là hệ RSA.
ELGAMAL: hệ mật mã ElGamal được T. ElGamal đề xuất năm 1985, độ an toàn của hệ dựa vào độ phức tạp của bài toán tính logarit rời rạc.
DSS (Digital Signature Standard) được đề xuất từ năm 1991 và được chấp nhận vào cuối năm 1994 để sử dụng trong một số lĩnh vực giao dịch điện tử tại Hoa Kỳ. DSS dựa vào sơ đồ chữ ký ElGamal với một vài sửa đổi.
RABIN: hệ mã hóa khóa công khai được M.O. Rabin đề xuất năm 1977, độ an toàn của hệ dựa vào bài toán khó “phân tích số nguyên thành thừa số nguyên tố”.
Khi nói đến chữ ký điện tử, chúng ta luôn lấy mục tiêu an toàn lên hàng đầu. Một chữ ký điện tử chỉ thực sự được áp dụng trong thực tế nếu như nó được chứng minh là không thể giả mạo. Mục tiêu lớn nhất của kẻ tấn công các sơ đồ chữ ký chính là giả mạo chữ ký, điều này có nghĩa kẻ tấn công sẽ sinh ra được chữ ký của người ký lên thông điệp, mà chữ ký này sẽ được chấp nhận bởi người xác nhận. Trong thực tế các hành vi tấn công chữ ký điện tử là hết sức đa dạng. Đó cũng là vấn đề chính được nghiên cứu trong luận văn “Nghiên cứu một số loại tấn công chữ ký số”. Nội dung chính của luận văn này bao gồm 2 chương:
Chương 1: Một số khái niệm cơ bản .
Chương 2: Tấn công chữ ký số.

MỤC LỤC
GIỚI THIỆU 4
Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN . 6
1.1. CÁC KHÁI NIỆM TRONG TOÁN HỌC 6
1.1.1. Một số khái niệm trong số học 6
1.1.1.1. Số nguyên tố 6
1.1.1.2. Ước số và bội số . 7
1.1.1.3. Ước số chung và bội số chung . 7
1.1.1.4. Số nguyên tố cùng nhau 8
1.1.1.5. Khái niệm Đồng dư 8
1.1.2. Một số khái niệm trong đại số . 8
1.1.2.1. Nhóm 8
1.1.2.2. Nhóm con của nhóm (G, *) . 9
1.1.2.3. Nhóm Cyclic 9
1.1.2.4. Tập thặng dư thu gọn theo modulo . 10
1.1.2.5. Phần tử nghịch đảo đối với phép nhân 10
1.1.3. Độ phức tạp của thuật toán 11
1.1.3.1. Khái niệm bài toán . 11
1.1.3.2. Khái niệm thuật toán . 11
1.1.3.3. Khái niệm Độ phức tạp của thuật toán . 11
1.1.3.4. Khái niệm “dẫn về được” . 13
1.1.3.5. Khái niệm khó tương đương . 13
1.1.3.6. Lớp bài toán P, NP . 13
1.1.3.7. Lớp bài toán NP-hard . 14
1.1.3.8. Lớp bài toán NP-Complete . 14
1.1.3.9. Hàm một phía và hàm cửa sập một phía . 14

1.2. VẤN ĐỀ MÃ HÓA DỮ LIỆU 15
1.2.1. Khái niệm Mã hóa 15
1.2.2. Phân loại mã hóa 16
1.2.2.1. Hệ mã hóa khóa đối xứng 16
1.2.2.2. Hệ mã hóa khóa công khai 17
1.3. VẤN ĐỀ CHỮ KÝ SỐ . 19
1.3.1. Khái niệm “chữ ký số” 19
1.3.1.1. Giới thiệu “chữ ký số” 19
1.3.1.2. Sơ đồ “chữ ký số” 20
1.3.2. Phân loại “chữ ký số” . 21
1.3.2.1. Phân loại chữ ký theo đặc trưng kiểm tra chữ ký 21
1.3.2.2. Phân loại chữ ký theo mức an toàn 21
1.3.2.3. Phân loại chữ ký theo ứng dụng đặc trưng . 21
1.4. MỘT SỐ BÀI TOÁN QUAN TRỌNG TRONG MẬT MÃ . 22
1.4.1. Bài toán kiểm tra số nguyên tố lớn . 22
1.4.2. Bài toán phân tích thành thừa số nguyên tố . 27
1.4.3. Bài toán tính logarit rời rạc theo modulo . 30

Chương 2. TẤN CÔNG CHỮ KÝ SỐ 32
2.1. TẤN CÔNG CHỮ KÝ RSA 32
2.1.1. Chữ ký RSA . 32
2.1.1.1. Sơ đồ chữ ký 32
2.1.1.2. Ví dụ . 32
2.1.2. Các dạng tấn công vào chữ ký RSA . 33
2.1.2.1. Tấn công dạng 1: Tìm cách xác định khóa bí mật . 33
2.1.2.2. Tấn công dạng 2: Giả mạo chữ ký (không tính trực tiếp khóa bí mật) 42
2.2. TẤN CÔNG CHỮ KÝ ELGAMAL 44
2.2.1. Chữ ký Elgamal 44
2.2.1.1. Sơ đồ chữ ký 44
2.2.1.2. Ví dụ . 45
2.2.2. Các dạng tấn công vào chữ .