CHƯƠNG 1: GIỚI THIỆU MẬT MÃ VÀ HỆ MÃ HÓA CÔNG KHAI RSA 1.1 Giới thiệu về mật mã và hệ mật mã 1.1 Khái quát về mật mã và hệ thống mã hóa Mật mã (Cryptogaraphy) là một ngành khoa học nghiên cứu các giải pháp mã hóa, biến đổi thông tin thành một dạng khác với mục đích che dấu thông tin và ý nghĩa thông tin cần mã hóa. Đây là một ngành quan trọng có nhiều ứng dụng trong cuộc sống xã hội. Cùng với sự phát triển của khoa học máy tính và Internet, các nghiên cứu và ứng dụng của khoa học mật mã càng ngày trở nên đa dạng hơn, ứng dụng của khoa học mật mã không chỉ đơn thuần là mã hóa và giải mã thông tin mà còn bao gồm nhiều vấn đề cần được nghiên cứu: Chứng thực nguồn gốc thông tin đó là chữ ký điện tử, chứng nhận tính xác thực về người sở hữu mã khóa, các quy trình giúp trao đổi thông tin và thực hiện giao dịch điện tử an toàn. Một hệ mật mã (Cryptosystem) là một bộ năm (P, C, K, E, D) thỏa mãn các điều kiện: - P là một tập hữu hạn các bản rõ (chứa thông tin cần mã hóa).
- C là tập hữu hạn các bản mã (chứa thông tin đã được mã hóa từ bản rõ). - K là tập hữu hạn các khóa. - E và D lần lược là quá trình mã hóa và giải mã: Với mỗi khóa k K tồn tại luật mã hóa ek E và luật giải mã dk D tương ứng. Luật mã hóa ek: P → C và luật giải mã ek: C → P là hai ánh xạ thỏa mãn dk(ek(x)) = x , x P.
Hệ thống mã hóa khóa bí mật [2][5], là hệ thống mã hóa trong đó quá trình mã hóa và giải mã đều sử dụng chung một khóa gọi là khóa bí mật (Secret key). Việc bảo mật thông tin phụ thuộc vào việc bảo mật khóa. Trong hệ thống mã hóa bí mật, thông điệp nguồn (bản tin rõ) được mã hóa với khóa k được thống nhất giữa người gửi A và người nhận B. Người A sẽ sử dụng 4 khóa k và để mã hóa thông điệp M thành thông điệp c (bản mã) và gửi c cho B, người B sẽ sử dụng khóa k để giải mã thông điệp c này, vấn đề an toàn bảo mật thông tin được mã hóa phụ thuộc vào việc giữ bí mật nội dung khóa k.
Khóa bí mật Kênh bí mật Bản tin rõ Bản mã Bản tin rõ Mã hoá Giải mã Hình 1.1 Mô hình hệ mã khoá bí mật 1.2 Phân loại hệ mã hóa - Mã theo chuỗi bit (Stream Cipher) Trong dạng mã này thông điệp là các bit và khoá được phát sinh bởi bộ phát sinh ngẫu nhiên. Chuỗi bit khoá được trộn với bản rõ, thường theo phép XOR để sinh bản mã. Việc giải mã được thực hiện bằng cách tính XOR bản mã với khoá k. - Mã theo chữ Các hệ mã ban đầu thường dựa trên cơ sở phép biến đổi một chữ cái trong bản rõ thành một chữ cái trong bản mã.
Kỹ thuật mã hoá này còn được gọi là mã thay thế. Để thực hiện phương pháp này, trước hết cần định nghĩa một bản mã (như bảng ASCII) để số hoá bản rõ, vì các phép toán sẽ làm việc trên các số thay vì các ký tự. Dạng mã này có độ bảo mật không cao vì một ký tự luôn được mã hoá bằng một ký tự khác trong bản mã mà với sự tiến bộ của máy tính hiện nay thì sẽ không khó khăn để giải mã một bản mã được mã hoá bằng phương pháp thay thế như trên. - Mã khối (Block Cipher) Rõ ràng, hệ mã theo chữ có độ an toàn không cao, vì thế một cách để tăng độ an toàn là dùng phương pháp mã khối.
Trong mã khối, bản rõ và bản mã được chia thành từng khối ký tự trước khi thực hiện việc mã hoá hay giải mã. Kỹ thuật mã khối được mô tả như sau [1]: 5 • Chia văn bản M thành nhiều khối: M = M1M2 … Mj, mỗi khối Mi với 1≤ i ≤ j là một khối n ký tự. • Chuyển các ký tự thành các số tương đương và xây dựng bản mã: Ci = AMi + B (mod n), i = 1, 2, …, j Trong đó (A, B) là khoá, A là một ma trận khả nghịch cấp n với gcd(det(A), n) = 1, B = (B1, B2,…, Bn)T , C = (C1, C2,…, Cn) và Mi = (m1, m2, …, mn)T Để giải mã, thực hiện phép toán: Mi = A-1 (Ci – B)(mod n) Trong đó A-1 là ma trận nghịch đảo của A. - Mã mũ Mã mũ, do Pohlig và Hellman giới thiệu năm 1976 [2][5], được mô tả như sau: Chọn p là một số nguyên tố, M là một số tương ứng của bản rõ, với mỗi ký tự trong bản rõ được thay thế bằng mã tương ứng Bảng 1.1 Bản mã ASCII A B C D E F G H I J K L M 01 02 03 04 05 06 07 08 09 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25 26 Chia M thành các khối Mi, 0 < Mi < p.
Gọi k là một số nguyên thoả 0 < k < p và gcd(k, p-1) = 1 • Mã hoá khối Mi thành Ci = E(k, Mi) ≡ M ik (mod p). • Giải mã Ci theo công thức: Mi = D(v,Ci) ≡ Cik ≡ ( M ik )v ≡ Mi (mod p).3 Phân tích các ưu nhược điểm của các hệ mật mã - Ưu điểm Tốc độ thực hiện nhanh vì các quá trình mã hoá và giải mã sử dụng các phép toán trên dãy bit nhị phân như: OR, AND, XOR, … là những phép toán gần với lệnh máy. - Nhược điểm Cả người gửi và người nhận đều phải biết khoá nên phát sinh vấn đề an toàn khi truyền khoá. Nếu khoá bị đánh cắp thì thông tin được mã hoá bằng khoá đó không còn được an toàn.
Hạn chế về khả năng quản lý khoá: Đối với mỗi người để liên lạc được với nhau phải có một khoá riêng, do đó đối với hệ thống lớn có nhiều đối tác giao tiếp với nhau thì mỗi người phải lưu giữ một số lượng khoá bí mật rất lớn dẫn đến vấn đề khó khăn trong quản lý và bảo mật khoá. Đối với phương pháp mã hoá bằng khoá bí mật có thể không xác nhận được chủ nhân của thông tin, tức nguồn gốc thông tin nhận được. Nên phương pháp mã hoá bí mật khó ứng dụng vào lĩnh vực cần xác định được nguồn gốc của thông tin như lĩnh vực chữ ký điện tử. * Ứng dụng của mã hoá khoá bí mật Loại mật mã này thường được dùng trong quân sự, ngoại giao, tức là khi cần trao đổi thông tin với nhau khá ít, hơn nữa cùng chung quyền lợi nên sẵn sàng bảo vệ bí mật cho nhau.
Do tốc độ mã hoá nhanh nên các hệ mã khóa bí mật thường được dùng mã hoá khối lượng dữ liệu lớn (mã hóa các cơ sở dữ liệu). Ngày nay sự phát triển của xã hội dẫn đến mật mã được dùng hầu hết trong mọi hoạt động của đời sống như: trong quân sự, ngoại giao, kinh tế, thương mại, … số lượng người dùng ngày càng lớn. Với mật mã khoá bí mật đòi hỏi số khoá mà mỗi thành viên cần phải giữ quá nhiều hơn nữa những người dùng cùng một chìa khoá trong hệ thống hệ mã khoá bí mật đều phải biết khoá của nhau. Do đó nên phải 7 có một hệ mã mới ra đời đó là hệ mật mã khoá công khai (hệ mã bất đối xứng) để khắc phục những nhược điểm của hệ mật mã khoá bí mật.2 Hệ mã hóa công khai RSA 1.1 Trình bày các khái niệm liên quan Hệ mã khóa công khai RSA là hệ thống mật mã do các giáo sư Ronald Rivest, Adi Sharmir và Leonard Adleman phát minh năm 1978 tại học viện Công nghệ Massachusetts (MIT).
Thuật toán RSA là thuật toán đầu tiên phù hợp với việc tạo chữ ký điện tử đồng thời với việc mã hóa và giải mã. Nó đánh dấu một sự tiến bộ vượt bậc của lĩnh vực mật mã học trong việc sử dụng hệ mật mã khóa công khai. RSA đang được sử dụng phổ biến trong thương mại điện tử và đảm bảo an toàn với điều kiện độ dài khóa đủ lớn. Hệ mã RSA được xây dựng trên cơ sở mã khối trong đó khóa mã hóa là cặp (e, n) gồm số mũ e modulo n.
Với n là tích số của 2 số nguyên tố rất lớn nào đó, n = p*q còn (e, φ(n)) = 1, với φ(n) là giá trị hàm Euler của n, trong trường hợp này φ(n) = (p-1)*(q -1). Như vậy, thuật toán RSA được thiết kế dựa trên độ khó của bài toán phân tích ra thừa số nguyên tố trên tập số nguyên Zn. Cụ thể là số nguyên dương n = p*q với p, q là 2 số nguyên tố. Nếu biết n, muốn tìm p, q phải giải bài toán phân tích một số ra thừa số nguyên tố và nếu n, p, q đủ lớn thì đòi hỏi phải thực hiện số lượng các phép tính vô cùng lớn.
Trong điều kiện hiện nay thì điều này không khả thi, tuy nhiên trong tương lai với sự phát triển của máy tính thì bài toán phân tích ra thừa số nguyên tố vẫn có thể giải được. Khóa công khai của B khóa bí mật của B đoạn tin Giải thuật mật mã Giải thuật đoạn tin User B User A mã hóa giải mã Hình 1.2: quá trình mã hóa khóa công khai 8 Bảng 1.2: Tóm tắt giải thuật RSA Tạo khóa Độ phức tạp Tạo 2 số nguyên tố lớn p và q Tính n = p*q, 0(n) = (p-1)*(q-1) 0((logn)2) Chọn 1 số ngẫu nhiên 1<e<0(n): gcd(0(n), e) = 1 0((log(0(n))2) Tính d: d = e-1 mod 0(n) (giải thuật Extended 0((logn)3) Euclidean) Khóa công khai KU = [e, n] Khóa bí mật KR = [d, n] Mã hóa Đoạn tin: M < n Mã hóa: C = Me mod n Giải mã Đoạn tin mã: C Giải mã: M = Cd mod n + Mỗi hệ thống cuối trong mạng tạo ra một cặp khóa để dùng cho mã hóa và giải mã đoạn tin mà nó sẽ nhận. + Mỗi hệ thống công bố rộng rãi khóa mã hóa bằng cách đặt khóa vào một thanh ghi hay một file công khai. Đây là khóa công khai, khóa còn lại được giữ riêng.
+ Nếu A muốn gửi một đoạn tin tới B thì A mã hóa đoạn tin bằng khóa công khai của B. + Khi B nhận đoạn tin mã hóa, nó giải mã bằng khóa bí mật của mình.