Bài giảng Chương 4 : các phương pháp mã hoá hiện đại

Giảng viên : Nguyễn Minh Thành E-mail : thanhnm.itc@itc.edu.vn Chương 4 : CÁC PHƯƠNG PHÁP MÃ HOÁ HIỆN ĐẠI Mục Lục I. Các loại hệ thống mã hoá II. Chuẩn mã hoá dữ liệu DES và các biến thể 1. DES 2. Các mode của DES 3. Các biến thể III. Chuẩn mã hoá cấp cao AES IV. Hệ thống mã hoá công khai RSA V. Chữ ký số (Digital Signature) 2 I. Các Loại Hệ Thống Mã Hoá  Có hai hệ thống mã hoá dựa vào khoá :  Hệ thống mã hoá đối xứng (Symmetric cryptosystem) : sử dụng một khoá (khoá bí mật) duy nhất để mã hoá và giải mã dữ liệu.  Hệ thống mã hoá bất đối xứng (Asymmetric cryptosystem) : sử dụng hai khoá, một khoá công khai để mã hoá (giải mã) và một khoá bí mật để giải mã (mã hoá) dữ liệu. 3 I. Các Loại Hệ Thống Mã Hoá (tt)  Đối với hệ mã hoá đối xứng  Người gửi và người nhận phải thoả thuận trước khoá bí mật khi muốn trao đổi thông tin với nhau.  Tính an tòan của thuật tóan đều nằm trong khóa, để lộ ra khóa có nghĩa là người nào đó có thể mã hóa và giải mã thông điệp. Quá trình mã hóa và giải mã với thuật tóan đối xứng có thể được biểu diễn như sau:  EK(M)=C  DK(C)=M4 I. Các Loại Hệ Thống Mã Hoá (tt)  Đối với hệ mã hoá đối xứng  Các hệ mã hoá cơ bản cũng thuộc vào hệ mã hoá này.  Thuật toán mã hoá có thể chia làm 2 loại :  Loại họat động dựa trên từng bit đơn hay từng byte gọi là stream algorithms hay stream ciphers.  Lọai thứ hai dựa trên plaintext là những nhóm bit, những nhóm bit này gọi là những block, cho nên thuật tóan được gọi là block algorithm hay block cipher.  Đối với thuật tóan máy tính hiện đại, một block điển hình là từ 64 bit, kích thước này đủ lớn để ngăn chận quá trình phân tích và đủ nhỏ để thuật tóan có thể họat động được. 5 I. Các Loại Hệ Thống Mã Hoá (tt)  Đối với hệ mã hoá bất đối xứng  Người gửi và người nhận tự chọn một cặp khoá bí mật và công khai riêng cho mình. Khoá bí mật sẽ được giữ kín và khoá công khai sẽ được cho mọi người biết.  Cả 2 key này đều có thể được dùng để mã hóa và giải mã, nếu dữ liệu được mã hóa bằng key này thì phải được giải mã bằng key còn lại. 6 II. Chuẩn Mã Hoá Dữ Liệu DES 7  Vào cuối thập niên 60, Horsr Feistel đã đưa ra hệ mã Lucifer. Hệ mã này gắn liền với hãng IBM.  Uỷ ban Tiêu Chuẩn Hoa Kỳ đã dàn xếp với IBM và đựa hệ mã này thành tiêu chuẩn mã hoá dữ liệu (Data Encryption Standard) và miễn phí.  DES là hệ mã hoá đối xứng dùng khoá bí mật. II.1 DES (Data Encryption Standard) 8  Vào cuối thập niên 60, Horsr Feistel đã đưa ra hệ mã Lucifer. Hệ mã này gắn liền với hãng IBM.  Uỷ ban Tiêu Chuẩn Hoa Kỳ đã dàn xếp với IBM và đựa hệ mã này thành tiêu chuẩn mã hoá dữ liệu (Data Encryption Standard) và miễn phí.  DES là hệ mã hoá đối xứng dùng khoá bí mật.  Vấn đề chính trong phương pháp này là bên gửi và bên nhận phải trao đổi khóa một cách an tòan. II.1 DES (Data Encryption Standard) 9  Mô tả tổng quan  DES là thuật toán mã hoá với input là khối 64bit, output cũng là khối 64bit.  DES sử dụng khóa 64 bit trong đó 56 bit làm key thực sự, còn 8 bit còn lại dùng để kiểm tra parity (bit kiểm tra tính chẵn lẻ). II.1 DES (Data Encryption Standard) 10  Sự tạo khoá  DES thực hiện 16 vòng lặp với các phép tính và những hàm có chức năng đặc biệt để tạo ra khối mã hóa Cipher.  16 vòng lặp chạy cùng thuật toáng nhưng mỗi vòng lặp sử dụng một khoá riêng biệt 48bit. Các khoá này được tạo ra từ khối khoá 56bit (đã bỏ đi các bit parity), hoán chuyển các bit và trích ra 48bit làm khoá cho từng vòng.  Trong quá trình giải mã, các khoá sẽ được đảo ngược. II.1 DES (Data Encryption Standard) 11  Sự tạo khoá (tt)  Mô tả thuật toán sinh khoá chi tiết như sau Bước 1: Từ khóa key được hoán vị qua ma trận hoán vị PC-1 (Permuted Choice -1) •Từ khóa key được đưa vào khối hoán vị PC-1, thực chất khối này chỉ tác động lên 56 bit dữ liệu và loại bỏ 8 bit parity dùng để kiểm tra không mang tính bảo mật thông tin, sau khối hoán vi này sẽ tạo 56 bit ngõ ra và được chia thành 2 nhóm: 28 bit trái và 28 bit phải của khóa. • 28 bit đầu tiên (bên trái) được đặt vào ma trận C0 (Ci ,Di được xem là số vòng lặp có trong thuật toán) •28 bit sau được đặt vào ma trận D0. II.1 DES (Data Encryption Standard) 12  Sự tạo khoá (tt)  Mô tả thuật toán sinh khoá chi tiết như sau Bước 2: Dịch xoay vòng sang trái thứ tự bit của ma trận Ci và Di trong một vòng lặp. Việc tính toán Ci và Di phụ thuộc vào Ci-1 và Di-1 và quá trình dịch chuyển từng bit của 2 nhóm sang trái theo quy tắc sau: Bước 3: Hoán vị Ci và Di qua ma trận nén PC-2 tạo từ khóa 48bit Thứ tự vòng i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Số bit dịch vòng 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 II.1 DES (Data Encryption Standard) 13  Sự tạo khoá (tt)  Sơ đồ tạo khoá II.1 DES (Data Encryption Standard) 14  Quá trình mã hoá  Thuật toán thực hiện 16 vòng, từ khoá K (64bit), sẽ tạo ra 16 khoá con (48bit) cho mỗi vòng.  Đầu tiên khối dữ liệu 64 bit sẽ được đưa vào khối hoán vị khởi tạo IP (Initial Permutation). Sau đó, khối dữ liệu sẽ được chia làm 2 nửa và đưa vào 2 khối L0 và R0(Li và Ri là thứ tự của mỗi vòng lặp). II.1 DES (Data Encryption Standard) 15  Quá trình mã hoá  Tại mỗi vòng lặp, input của vòng lặp này được tính từ output của vòng trước.  Nửa phải của vòng i-1 sẽ là nửa trái của vòng i, và nửa phải của vòng i-1 cùng với khoá ki sẽ đi qua một hàm f tạo ra 32bit, 32 bit này sẽ được xor với nửa trái của vòng i-1 để tạo ra nửa phải của vòng i. II.1 DES (Data Encryption Standard) 16  Quá trình mã hoá  Hàm f cung cấp sức mạnh cho hệ mã hoá DES.  Hoạt động của hàm f :  Nửa phải (32bit) của vòng i-1 sẽ được mở rộng thanh 48bit và được xor với khoá ki, kết quả tạo ra 48bit và được chia thành 8 tập 6bit. Mỗi tập là một bảng thay thế gọi là S-box. S-box sẽ thay thế một số bit trong đó và tạo ra 4bit ở mỗi s-box. Kết hợp các bit đó ta được một chuỗi 32bit và là đầu ra cho hàm f. II.1 DES (Data Encryption Standard) 17  Quá trình mã hoá  Hoạt động của hàm f : II.1 DES (Data Encryption Standard) 18  Quá trình mã hoá  Sau khi chạy qua hết 16 vòng, ở bước cuối cùng chuỗi 64bit sẽ được đưa vào chuỗi hoán vị ngược so với chuỗi hoán vị khởi tạo IP-1 trước khi trở thành chuỗi mã hoá. II.1 DES (Data Encryption Standard) 19  Quá trình mã hoá II.2 Các Mode của DES 20  Khi lần đầu tiên được công bố, nó đã được thông báo là quá yếu do chiều dài 56bit của khoá là quá ngắn.  Do đó, DES đã được phát triển thêm nhiều Mode hoạt động khác nhau để tăng tính bảo mật. II.2 Các Mode của DES 21  Mode 1- Electronic Code Book (ECB)  Mode ECB là kiểu hoạt động sử dụng cùng 1 key cho quá trình mã hóa và giải mã cho nhiều khối dữ liệu của một file. Các khối dữ liệu (64 bit) được mã hóa độc lập với nhau với cùng 1 từ khóa. Kiểu hoạt động này kém tính bảo mật nếu có nhiều khối truyền giống nhau. II.2 Các Mode của DES 22  Mode 2 – Cipher Block Chainning (CBC)  Hoạt động dùng thêm 1 cổng XOR để thực hiện XOR 64 bit của vector khởi tạo (initialization Vector – IV) với 64 bit dữ liệu của khối plaintext đầu tiên trước khi đưa vào mã hóa tạo ra ciphertext đầu tiên, khối plaintext thứ 2 trước khi được mã hóa được XOR với khối ciphertext đầu tiên, tương tự cho các khối plaintext tiếp theo …IV cần được khởi tạo và được thống nhất giữa người gửi và người nhận. Mode này có tính bảo mật tốt hơn mode hoạt động ECB, tuy nhiên cần phải bảo mật thêm phần IV. II.2 Các Mode của DES 23  Mode 3 – Cipher FeedBack (CFB)  Nguyên lý hoạt động của mode này hoàn toàn khác với 2 mode ECB cà CBC. Đối với 2 mode đầu thì quá trình mã hóa dữ liệu được thực hiện trên từng khối dữ liệu 64 bit cố định. Trong khi mode hoạt động CFB thì mã hóa và giải mã không dựa vào từng khối dữ liệu 64 bit, mà khối dữ liệu có thể thay đổi từ 8 bit, 16 bit, 24 bit, 32 bit, 40 bit, 48 bit, 56 bit, 64 bit. II.2 Các Mode của DES 24  Mode 3 – Cipher FeedBack (CFB) Quá trình mã hóa:  Chọn số bit cho khối dữ liệu mã hóa: R bit.  Lần mã hóa đầu tiên cho dữ liệu đầu vào là khối vector IV (64 bit), sau khi mã hóa xong lấy R bit bên trái của khối cipher này XOR với R bit của dữ liệu cần mã hóa để tạo thành ciphertext cho dữ liệu.  R bit cipher sẽ được thay thế vào bên phải của chuỗi IV sau khi dịch trái IV R bit.  Quá trình mã hóa sẽ tiếp tục như vậy cho đến khi kết thúc data cần mã hóa.  Quá trình giải mã được thực hiện tương tự như mã hóa. II.2 Các Mode của DES 25  Mode 4 – Output FeedBack (OFB):  Mode này mã hóa tương tự như CFB. Tuy nhiên, ở mode này toàn bộ ngõ ra của thuật toán mã hóa DES được sử dụng như ngõ vào của lần mã kế tiếp. II.3 Các Biến Thể của DES 26  Mã DES còn có các biến thể như: 3DES (triple DES), Chained 3DES, FEAL (Fast Encryption Algorithm),…  3DES: khối mã hóa dài 64 bit, sử dụng 3 lần mã hóa DES và 3 key 56 bit khác nhau. Chống bẻ khóa khá mạnh.  Chained 3DES: cũng là 3DES nhưng theo một số cơ cấu hồi tiếp như CBC, OFB hoặc CFB. Chống bẻ khóa rất tốt.  FEAL: mã hóa khối, tốc độ khá nhanh nhưng đã bị bẻ khóa. III. Chuẩn Mã Hoá Cấp Cao AES 27  6/1977, Diffie and Hellman đã thông báo về chiều dài của khoá 56bit là quá ngắn và đã thiết kế một bộ máy giải mã chuẩn DES chỉ trong một vài ngày.  2/1/1997, NIST đã thông báo một giải thuật mã hoá đối xứng mới thay thế cho chuẩn DES, và được gọi là AES (Advanced Encryption Standard) III. Chuẩn Mã Hoá Cấp Cao AES 28  AES có tên là Rijndael (Do hai nhà mật mã học người Bỉ là Joan Daemen và Vincent Rijmen đưa ra) cho phép xử lý các khối dữ liệu input có kích thước 128 bit sử dụng các khóa có độ dài 128, 192 hoặc 256 bit. III. Chuẩn Mã Hoá Cấp Cao AES 29  Thuật toán mã hoá của AES (tham khảo) IV. Hệ Thống Mã Hoá Công Khai RSA 30  Các hệ mã được trình bày trong các chương trước được gọi là các hệ mã khóa bí mật, khóa đối xứng, hay các hệ mã truyền thống.  Các hệ mã này có các điểm yếu sau đây:  Nếu số lượng người sử dụng lớn thì số khóa sẽ tăng rất nhanh, chẳng hạn với n người sử dụng thì số khóa sẽ là n*(n-1)/2 do đó rất khó quản lý, phức tạp và không an toàn.  Dựa trên các hệ mã này không thể xây dựng các khái niệm và dịch vụ như chữ ký điện tử, dịch vụ xác thực hóa người dùng cho các ứng dụng thương mại điện tử. IV. Hệ Thống Mã Hoá Công Khai RSA 31  Vào năm 1975 Diffie và Hellman trong một công trình của mình (một bài báo) đã đề xuất ra các ý tưởng cho phép xây dựng lên các hệ mã hoạt động theo các nguyên tắc mới gắn liền với các bên truyền tin chứ không gắn với các cặp truyền tin.  Nguyên tắc hoạt động của các hệ mã là mỗi bên tham gia truyền tin sẽ có 2 khóa, một khóa gọi là khóa bí mật và một khóa được gọi là khóa công khai.  Khóa bí mật là khóa dùng để giải mã và được giữ bí mật (KS), khóa công khai là khóa dùng để sinh mã được công khai hóa để bất cứ ai cũng có thể sử dụng khóa này gửi tin cho người chủ của hệ mã (KP). IV. Hệ Thống Mã Hoá Công Khai RSA 32  Ngày nay chúng ta có thể thấy rất rõ nguyên tắc này trong việc gửi email, mọi người đều có thể gửi email tới một địa chỉ email nào đó, nhưng chỉ có người chủ sở hữu của địa chỉ email đó mới có thể đọc được nội dung của bức thư, còn những người khác thì không. Với các hệ mã khóa công khai việc phân phối khóa sẽ trở nên dễ dàng hơn qua các kênh cung cấp khóa công cộng, số lượng khóa hệ thống quản lý cũng sẽ ít hơn (là n cặp khóa cho n người dùng). Các dịch vụ mới như chữ ký điện tử, thỏa thuận khóa cũng được xây dựng dựa trên các hệ mã này. IV. Hệ Thống Mã Hoá Công Khai RSA 33  Hai mô hình sử dụng hệ mã hoá công khai IV. Hệ Thống Mã Hoá Công Khai RSA 34  Hệ mã RSA được đặt tên dựa theo các chữ cái đầu của 3 tác giả của hệ mã là Rivest, Shamir và Adleman. Đây là thuật toán mã hóa nổi tiếng nhất và cũng là thuật toán được ứng dụng thực tế nhất. IV. Hệ Thống Mã Hoá Công Khai RSA 35  Nguyên tắc :  Chọn hai số nguyên tố lớn ngẫu nhiên (cỡ gần 100 chữ số) khác nhau p và q  Tính N = p*q, (N) = (p-1)*(q-1)  Chọn một số e nhỏ hơn N và (e, N) = 1, e được gọi là số mũ lập mã  Tìm phần tử nghịch đảo d của e trên vành module (N) hay ZN, d là số mũ giải mã  Khóa công khai là KP = (e, N)  Khóa bí mật là KS = K-1P = (d, p, q) IV. Hệ Thống Mã Hoá Công Khai RSA 36  Sử dụng RSA :  Mã hóa một thông điệp M: C = Me (mod N) (0<= M < N)  Giải mã: M = Cd (mod N)  Ví dụ :  Chọn 2 số p=7, q=11  N = 7*11 = 77 và (77)=(7-1)(11-1)=60  Chọn khoá bí mật là e = 17  Khoá công khai là d = 53 IV. Hệ Thống Mã Hoá Công Khai RSA 37  Sử dụng RSA :  Mã hóa một thông điệp M: C = Me (mod N) (0<= M < N)  Giải mã: M = Cd (mod N)  Ví dụ : mã hoá “HELLO WORLD” với khoá ở slide trước.  Sử dụng mã ASCII của chuỗi “HELLO WORLD” là 07 04 11 11 14 26 22 14 17 11 03  Mã hoá : 0717 mod 77 = 28 0417 mod 77 = 16 1117 mod 77 = 44 ... 0317 mod 77 = 75 V. Chữ Ký Số 38  Trong lĩnh vực thương mại điện tử, việc gửi các văn bản, hợp đồng điện tử, hay các email, thông điệp giao dịch thương mại việc rất bình thường và xảy ra thương xuyên.  Tuy nhiên, vấn đề đặt ra là độ tin cậy của các văn bản đó chưa được xác thực. Người gởi có thể gửi các văn bản, hợp đồng hay đơn đặt hàng qua mạng, tuy nhiên sau đó học lại chối là không gửi chúng. Chính vì vậy cần phải có một cơ chế đảm bảo để chống lại sự thoái thác đó.  Giải pháp đặt ra là sử dụng chữ ký số (sử dụng phương pháp mã khoá công khai) trong các văn bản điện tử đó. V. Chữ Ký Số 39  Một văn bản (thông điệp) được ký với một khoá bí mật của người dùng sẽ được xác nhận bởi một người khác với khoá công khai. Điều này chứng mình chính người dùng đó đã gửi văn bản (thông điệp). 40