CHƯƠNG 1 CƠ SỞ LÝ THUYẾT 1. Các hệ thống, kỹ thuật bảo mật 1.Thuật toán mã hóa DES 1.1 Lịch sử ra đời Khoảng những năm 1970, tiến sĩ Horst Feistel đã đặt nền móng đầu tiên cho chuẩn mã hóa DES với phương pháp mã hóa Feistel Cipher. Vào năm 1976 Cơ quan Bảo mật quốc gia Hoa Kỳ (NSA) đã công nhận DES dựa trên phương pháp Feistel là chuẩn mã hóa dữ liệu. Kích thước khóa ban đầu của DES là 128 bit nhưng tại bản công bố FIPS kích thước được rút xuống 56 bit để tăng tốc độ xử lý và đưa ra các tiêu chuẩn thiết kế một chuẩn mã hóa dữ liệu.
Nội dung phương pháp mã hóa DES. DES thực hiện mã hóa dữ liệu qua 16 vòng lặp mã hóa, mỗi vòng sử dụng một khóa chu kỳ 48 bit được tạo ra từ khóa ban đầu có độ dài 56 bit. DES sử dụng 8 bảng hằng số S-box để thao tác.Mô tả thuật toán DES 1.Sơ đồ tổng quát Phương pháp DES mã hóa khối thông tin x có độ dài 64 bit với khóa k có độ dài 56 bit thành khối y có độ dài 64 bit. Nền tảng để xây dựng khối của DES là sự kết hợp đơn giản của các kỹ thuật thay thế và hoán vị bản rõ dựa trên khóa, đó là vòng lặp.
DES sử dụng 16 vòng lặp áp dụng cùng một kiểu kết hợp các kỹ thuật trên khối bản rõ. Thuật toán chỉ sử dụng các phép toán số học và logic thông thường trên các số 16 bit, vì vậy nó dễ dàng thực hiện vào những năm 1970 trong điều kiện về công nghệ phần cứng lúc bấy giờ. 3 Plaintext IP L0 R0 K1 L1=R0 R1=L0(R0,K1) K2 L2=R1 R2=L1(R1,K2) L15=R14 R15=L14(R14,K15) K16 R16=L15(R15,K16) L16=R15 IP -1 Ciphertext Hình 1.1: Sơ đồ tổng quát mã hóa DES 4 Quá trình có 16 vòng thực hiện giống nhau trong quá trình xử lý. Ngoài ra có hai lần hoán vị đầu IP và cuối IP-1, hai hoán vị này được sử dụng với mục đích đưa thông tin vào và lấy thông tin ra.
Muốn vào vòng mã hóa thì khối thông tin x ban đầu 64 bit được chia làm hai khối, mỗi khối 32 bit. Hàm f làm biến đổi một nữa của khối đang xử lý với một khóa con tương ứng với vòng mã hóa. Trong đầu ra của hàm có hàm f được kết hợp với nửa khối còn lại bằng phép toán XOR, và hai phần được trao đổi để xử lý trong chu trình kế tiếp. Cứ thực hiện các vòng như vậy cho tới vòng cuối cùng thì hai phần không bị tráo đổi nữa, chính vì điều này mà quá trình mã hóa và giải mã là giống nhau.2 Tạo khóa Quá trình mã hóa được thực hiện 16 vòng, mỗi vòng cần một khóa.
Như vậy từ khóa ban đầu tạo ra 16 khóa con cho 16 vòng lặp tương ứng. Sơ đồ quá trình tạo khóa.2: Sơ đồ tạo khóa Theo sơ đồ ta thấy đầu tiên khóa K có độ dài 64 bit, sau đó được giảm xuống 56 bit bằng cách loại bỏ 8 bit chẵn lẻ. Sự loại bỏ được thực hiên khi đi qua PC1. Bảng PC1 : Như vậy các bit ở vị trí 8, 16, 24, 32, 40, 48, 56, 64 bị loại bỏ.
56 bit thu được chia làm hai phần, mỗi phần 28 bit, các phần được xử lý độc lập nhau. Các phần này được dịch 1 hay 2 bit là phụ thuộc vào vòng đó. Số bit dịch được cho trong bảng sau. 6 Sau khi dịch bit, 56 bit này được chọn ra 48 bit.
Bởi vì sự thực hiện đổi chỗ thứ tự các bit như là sự lựa chọn một tập con các bit, nó còn được gọi là hoán vị nén hoặc hoán vị lựa chọn. Sự thực hiện này cung cấp một tập hợp các bit cùng cỡ với đầu ra của hoán vị mở rộng. Bảng PC2 định nghĩa hoán vị nén (cũng gọi là hoán vị lựa chọn). Ví dụ, bit ở vị trí 33 của khóa được dịch chuyển tới vị trí 35 của đầu ra và bit ở vị trí 8 của khóa bị bỏ qua.
Bảng PC2( hoán vị nén): Như vậy sau khi đi qua PC2 còn lại 48 bit, 48 bit này sẽ được sử dụng làm khóa K1 để sử dụng trong vòng mã hóa. Hai phần, mỗi phần 28 bit sau khi được dịch bit ở lần thứ nhất, tiếp tục dịch bit ở lần thứ 2 và qua bảng PC2 để hoán vị nén 48 bit và làm K2. Quá trình cứ tiếp tục như vậy ta thu được 16 khóa Ki (i=1…16).3 Hoán vị khởi đầu Mục đích của hoán vị khởi đầu là đổi chỗ các bit của khối dữ liệu vào thông qua bảng IP. Nó không ảnh hưởng đến sự an toàn của DES.
Với khối dữ liêu vào x 64 bit cho trước, một xâu bit x0 sẽ được xây dựng bằng cách hoán vị các bit của x theo phép hoán vị cố định ban đầu IP. Ta viết x0=IP(x)=L0R0 trong đó L0 gồm 32 bit đầu và R0 gồm 32 bit cuối.3: Biểu diễn dãy 64 bit x chia thành 2 thành phần L0, R0 7 Bảng hoán vị khởi đầu IP.4 Mã hóa chi tiết một vòng Quá trình xử lý các vòng là giống nhau, ta xét quá trình xử lý của một vòng i với 1=< i =< 16. L i- 1 R i- 1 f Ki Li Ri Hình 1.4: Sơ đồ chi tiết một vòng Ta thấy: Li = Ri-1 Ri =Li-1 f(Ri-1,Ki) Hàm f có hai tham số là Ri-1 và Ki. Được thực hiện theo sơ đồ sau : 8 Hình 1.5: Sơ đồ hoạt động của hàm f Ri-1 được mở rộng từ 32 bit thành 48 bit nhờ sự thay đổi thứ tự của các bit bằng cách lặp lại một số bit nào đó, nó được hiểu như là một sự hoán vị mở rộng.
Để xác định ở đầu vào có 32 bit, bit nào được lặp lại và xuất hiện tại vị trí nào của đầu ra 48 bit người ta xác định như sau: Đầu vào có 32 bit chia làm 8 bộ, mỗi bộ có 4 bit. Bit đầu tiên và bit cuối cùng của mỗi bộ tương ứng với 2 bit của khối dữ liệu ra, trong khi bit thứ 2 và bit thứ 3 của mỗi bộ tương ứng với một bit ở khối dữ liệu ra. Ví dụ, bit ở vị trí thứ 3 của khối dữ liệu vào được chuyển tới vị trí thứ 4 trong khối dữ liệu ra, bit thứ 8 trong khối dữ liệu vào thì được chuyển tới vị trí 11 và 13 trong khối dữ liệu ra.6: Hoán vị mở rộng Như vậy 16 bit của Ri được hoán vị hai lần. Mặc dù khối dữ liệu ra rộng hơn khối dữ liệu vào, nhưng một khối dữ liệu vào chỉ có duy nhất một khối dữ liệu ra.
Như vậy E(Ri-1) là một dãy 48 bit. Thực hiện phép toán XOR cho dãy bit E(Ri-1) với khóa Ki. Ta thu được dãy 48 bit B. Biểu diễn B thành từng nhóm 6 bit B = B1B2B3B4B5B6B7B8.
Sử dụng 8 hộp S = S1, S2, S3, S4, S5, S6, S7, S8. Mỗi hộp Si có kích thước 4 x 16. Mỗi dòng của hộp nhận đủ giá trí từ 015. 10 Xét dãy 6 bit Bi=b1b2b3b4b5b6.
Si(Bi) được xác định bằng giá trị của phần tử tại dòng m cột n. Trong đó m, n được xác định bằng cách. Giá trị m được xác định bằng bit b1 và b6 được kết hợp thành một số 2 bit nhận giá trị từ 0 đến 3, tương ứng với một hàng trong bảng. Giá trị n được xác định bằng cách ghép bit b2b3b4b5 thành một số 4 bit nhận giá trị từ 0 đến 15, tương ứng với cột trong bảng.
Phần tử ở vị trí hàng 2 cột 13 là 6, sang giá trị nhị phân là 0110. Như vậy 0110 thay cho 111010. Như vậy tập dãy 4 bit thu được C ta có dãy C = C1, C2, C3, C4, C5, C6, C7, C8. Dãy 32 bit thu được bằng cách hoán vị hoán vị C theo quy luật P nhất định.
Đây là kết quả của hàm f(Ri-1,Ki) XOR với Li-1 tạo thành khối Ri với 32 bit. Hộp hoán vị P chứa khối dữ liệu 32 bit ra của hộp thay thế S được hoán vị tiếp trong hộp P. Sự hoán vị này ánh xạ mỗi bit dữ liệu vào tới một vị trí trong khối dữ liệu ra, không có bit nào được sử dụng hai lần và cũng không bit nào bị bỏ qua. Nó được gọi là hoán vị trực tiếp.
Hộp hoán vị P. Hoán vị cuối cùng Hoán vị cuối cùng là nghịch đảo của hoán vị khởi đầu. Được mô tả theo bảng IP-1. Tại vòng cuối cùng của mã hóa DES thì nửa trái và nửa phải không được tráo đổi cho nhau nữa.
Khi đó R16L16 được sử dụng như khối dữ liệu ra của hoán vị cuối cùng. Hoán vị cuối cùng IP-1.Giải mã DES Quá trình giải mã hoàn toàn tương tự với quá trình mã hóa. Nhưng quá trình mã hóa thực hiện hoán vị IP trước hoán vị IP-1, còn giải mã thì thực hiện hoán vị IP-1 trước hoán vị IP. Các khóa phải được thực hiện trái ngược nhau.
Tức là nếu mã hóa, khóa thực hiện cho các vòng lần lượt là K1, K2,…, K16, thì giải mã là K16, K15,…, K2, K1. Ngoài ra, sau mỗi chu trình tạo khóa các bit được dịch phải thay vì dịch trái như khi mã hóa, và số bit để dịch được lấy theo chiều ngược lại.4 Độ an toàn của thuật toán Đã có rất nhiều nghiên cứu về độ dài của khóa, số vòng lặp và thiết kế hộp S. Trong phương pháp mã hóa này chỉ có hộp S là khó hiểu. Mọi tính toán trong DES đều là tuyến tính ngoại trừ hộp S, các hộp S chứa các thành phần phi tuyến tính của hệ là yếu tố quan trọng nhất đối với sự an toàn của hệ thống.
Tính bảo mật của một hệ mã hóa đối xứng phụ thuộc chủ yếu vào hai yếu tố: Độ phức tạp của thuật toán và độ dài của khóa. Giã sử phương pháp này an toàn về độ phức tạp của thuật toán. Có nghĩa là không có phương pháp nào để phá vỡ hệ thống mật mã hơn là cố gắng thử mọi khóa có thể, còn gọi là phương pháp vét cạn. Nếu khóa có độ dài 8 bit thì sẽ có 28= 256 khóa.
Như vậy muốn tìm ra khóa thì mất nhiều nhất là 256 lần thử khóa. Thuật toán DES sử dụng khóa có độ dài 56 bit nên có 256 khóa. Đây là con số rất lớn do đó việc tìm kiếm khóa là rất khó khăn. Giả sử có một máy tính có thể thử một triệu khóa trong một giây, thì nó sẽ cần hơn 2000 năm để thử hết khóa.