Ví dụ về thuật toán mã hóa des

Tóm tắt: DES là thuật toán mã hoá bảo mật được sử dụng rộng rãi nhất trên thế giới, thậm chí, đối với nhiều ngưòi DES và mã hoá bảo mật là đồng nghĩa với nhau. Bài báo này giới thiệu về thuật toán bảo mật DES và một số ứng dụng thực tế của DES.

Tác giả: Nguyễn Lê Cường

Data Encryption Standard (DES)

I. Mở đầu

Năm 1972, Viện tiêu chuẩn và công nghệ quốc gia Hoa kỳ (National Institute of Standards and Technology-NIST) đặt ra yêu cầu xây dựng một thuật toán mã hoá bảo mật thông tin với yêu cầu là dễ thực hiện, sử dụng được rộng rãi trong nhiều lĩnh vực và mức độ bảo mật cao. Năm 1974, IBM giới thiệu thuật toán Lucifer, thuật toán này đáp ứng hầu hết các yêu cầu của NIST. Sau một số sửa đổi, năm 1976, Lucifer được NIST công nhận là chuẩn quốc gia Hoa kỳ và được đổi tên thành Data Encryption Standard (DES).

DES là thuật toán mã hoá bảo mật được sử dụng rộng rãi nhất trên thế giới, thậm chí, đối với nhiều ngưòi DES và mã hoá bảo mật là đồng nghĩa với nhau. ở thời điểm DES ra đời ngưòi ta đã tính toán rằng việc phá được khoá mã DES là rất khó khăn, nó đòi hỏi chi phí hàng chục triệu USD và tiêu tốn khoảng thời gian rất nhiều năm. Cùng với sự phát triển của các loại máy tính và mạng máy tính có tốc độ tính toán rất cao, khoá mã DES có thể bị phá trong khoảng thời gian ngày càng ngắn với chi phí ngày càng thấp. Dù vậy việc này vẫn vượt xa khả năng của các hacker thông thường và mã hoá DES vẫn tiếp tục tồn tại trong nhiều lĩnh vực như ngân hàng, thương mại, thông tin… nhiều năm nữa đặc biệt với sự ra đời của thế hệ DES mới-“Triple DES”.

Vậy DES hoạt động như thế nào, bài báo này sẽ giới thiệu nguyên tắc làm việc của DES, một số ứng dụng cụ thể của bảo mật DES trong bảo mật thông tin trên thế giới cũng như ở nước ta xin được giới thiệu trong các bài viết sau. Kể từ khi DES ra đời, nhiều thuật toán mã hoá bảo mật khác cũng được phát triển tương tự DES hoặc dựa trên DES, một khi nắm được các nguyên tắc của DES bạn sẽ dễ dàng hiểu các thuật toán này.

Yêu cầu đặt ra nếu muốn bảo mật tốt hơn là phải tìm được một thuật toán sao cho việc thực hiện không quá phức tạp nhưng xác suất tìm ra chìa khoá bằng cách thử tất cả các trường hợp (brute-force) là rất nhỏ (số lần thử phải rất lớn).

II. Thuật toán bảo mật DES.

Về mặt khái niệm, thông thường thuật toán mã hoá DES là thuật toán mở, nghĩa là mọi người đều biết thuật toán này. Điều quan trọng nhất là chìa khoá của DES có độ dài tới 56 bit, nghĩa là số lần thử tối đa để tìm được chìa khoá lên đến 2^56, trung bình là 2^55 = 36.028.797.018.963.968 lần, một con số rất lớn!.

DES được thực hiện nhờ các phép dịch, hoán vị và các phép toán logic trên các bit. Mỗi ký tự trong bức thư hay bản tin cần mã hoá được biểu diễn bởi 2 số hexa hay 8 bít. DES mã hoá từng khối 64 bít tương đương 16 số hexa. Để thực hiện việc mã hoá DES sử dụng một chìa khoá cũng dưới dạng 16 số hexa hay 64 bít tức 8 byte, nhưng các bít thứ 8 trong các byte này bị bỏ qua trong khi mã hoá vì vậy độ lớn thực tế của chìa khoá là 56 bit. Ví dụ, ta mã hoá một bản tin hexa “0123456789ABCDEF” với chìa khoá là “5A5A5A5A5A5A5A5A” thì kết quả là “72AAE3B3D6916E92”. Nếu kết quả này được giải mã với cùng chìa khoá “5A5A5A5A5A5A5A5A” thì ta sẽ thu lại được đúng bản tin “0123456789ABCDEF”.

DES bao gồm 16 vòng, nghĩa là thuật toán chính được lặp lại 16 lần để tạo ra bản tin được mã hoá.

Sau đây chúng tôi sẽ trình bày quy trình của thuật toán DES.

Chuẩn bị chìa khoá:

Bước đầu tiên là chuyển 64 bit chìa khoá qua một bảng hoán vị gọi là Permuted Choice hay PC-1 để thu được chìa khoá mới có 56 bit.

Sau khi vệc chuẩn bị chìa khoá và dữ liệu mã hoá hoàn thành, thực hiện mã hoá bằng thuật toán DES. Đầu tiên, khối dữ liệu đầu vào 64 bit được chia thành hai nửa, L và R. L gồm 32 bit bên trái và R gồm 32 bit bên phải. Quá trình sau đây được lặp lại 16 lần tạo thành 16 vòng của DES gồm 16 cặp L[0]-L[15] và R[0]-R[15]:

1. R[r-1]- ở đây r là số vòng, bắt đầu từ 1- được lấy và cho qua bảng E (E-bit Selection Table), bảng này giống như một bảng hoán vị, có điều là một số bit được dùng hơn một lần do vậy nó sẽ mở rộng R[r-1] từ 32 bit lên 48 bit để chuẩn bị cho bước tiếp theo.

2. 48 bit R[r-1] được XOR với K[r] và được lưu trong bộ nhớ đệm, vì vậy R[r-1] không thay đổi.

3. Kết quả của bước trước lại được chia thành 8 đoạn, mỗi đoạn 6 bit, từ B[1] đến B[8]. Những đoạn này tạo thành chỉ số cho các bảng S (Substitution) được sử dụng ở bước tiếp theo. Các bảng S, là một bộ 8 bảng (S[1]-S[8]) 4 hàng, 16 cột. Các số trong bảng có độ dài 4 bit vì vậy có giá trị từ 0 đến 15.

4. Bắt đầu từ B[1], bit đầu và cuối của khối 6 bit được lấy ra và sử dụng làm chỉ số hàng của bảng S[1], nó có giá trị từ 0 đến 3, và 4 bit giữa được dùng làm chỉ số cột, từ 0 đến 15. Giá trị được chỉ đến trong bảng S được lấy ra và lưu lại. Việc này được lặp lại đối với B[2] và S[2] cho đến B[8] và S[8]. Lúc này bạn có 8 số 4 bit, khi nối lại với nhau theo thứ tự thu được sẽ tạo ra một chuỗi 32 bit.

5. Kết quả của bước trước được hoán vị bit bằng bảng hoán vị P (Permutation).

6. Kết quả thu được sau khi hoán vị được XOR với L[r-1] và chuyển vào R[r]. R[r-1] được chuyển vào L[r].

7. Lúc này bạn có L[r] và R[r] mới. Bạn tiếp tục tăng r và lặp lại các bước trên cho đến khi r= 17, đIều đó có nghĩa là 16 vòng đã được thực hiện và các chìa khoá phụ K[1]-K[16] đã được sử dụng.

Khi đã có L[16] và R[16], chúng được ghép lại với nhau theo cách chúng bị tách ra (L[16] ở bên trái và R[16] ở bên phải) thành 64 bit. 64 bit này được hoán vị để tạo ra kết quả cuối cùng là dữ liệu 64 bit đã được mã hoá.

Giải mã:

Việc giải mã dùng cùng một thuật toán như việc mã hoá. Để giải mã dữ liệu đã được mã hoá, quá trình như giống như mã hoá được lăp lạI nhưng các chìa khoá phụ được dùng theo thứ tự ngược lạI từ K[16] đến K[1], nghĩa là trong bước 2 của quá trình mã hoá dữ liệu đầu vào ở trên R[r-1] sẽ được XOR với K[17-r] chứ không phảI với K[r].

Các chế độ của DES:

Thuật toán DES mã hoá đoạn tin 64 bit thành đoạn tin mã hoá 64 bit. Nếu mỗi khối 64 bit được mã hoá một cách độc lập thì ta có chế độ mã hoá ECB (Electronic Code Book). Có hai chế độ khác của mã hoá DES là CBC (Chain Block Coding) và CFB (Cipher Feedback), nó làm cho mỗi đoạn tin mã hoá 64 bit phụ thuộc vào các đoạn tin trước đó thông qua phép toán XOR.

Triple DES:

Triple-DES chính là DES với hai chìa khoá 56 bit. Cho một bản tin cần mã hoá, chìa khoá đầu tiên được dùng để mã hoá DES bản tin đó, kết quả thu được lạI được cho qua quá trình giải mã DES nhưng với chìa khoá là chìa khoá thứ hai, bản tin sau qua đã được biến đổi bằng thuật toán DES hai lần như vậy lại được mã hoá DES với một lần nữa với chìa khoá đầu tiên để ra được bản tin mã hoá cuối cùng. Quá trình mã hoá DES ba bước này được gọi là Triple-DES.

Ứng dụng của DES

DES thường được dùng để mã hoá bảo mật các thông tin trong quá trình truyền tin cũng như lưu trữ thông tin. Một ứng dụng quan trọng khác của DES là kiểm tra tính xác thực của mật khẩu truy nhập vào một hệ thống (hệ thống quản lý bán hàng, quản lý thiết bị viễn thông…), hay tạo và kiểm tính hợp lệ của một mã số bí mật (thẻ internet, thẻ điện thoại di động trả trước), hoặc của một thẻ thông minh (thẻ tín dụng, thẻ payphone…).

Phá khóa DES

Năm 1998, một nhóm nghiên cứu đã chi phí 220.000USD để chế tạo một thiết bị có thể thử toàn bộ số chìa khoá DES 56 bit trong trung bình 4,5 ngày. Tháng 7 năm 1998 họ thông báo đã phá chìa khoá DES trong 56 giờ. Thiết bị này gọi là Deep Crack gồm 27 board mạch, mỗi board chứa 64 chip và có khả năng thử 90 tỷ chìa khoá trong một giây.

Tuy nhiên, việc phá khóa Triple DES là điều rất khó khăn, một chuyên gia về bảo mật đã cho rằng ” Không có đủ silic trong giải ngân hà (để chế tạo chip-TG) cũng như không đủ thời gian trước khi mặt trời bị phá huỷ để phá khoá Triple DES”.

III. Kết luận

Không thể phủ nhận là thuật toán DES có nhiều ứng dụng trong viễn thông và công nghệ thông tin, việc làm chủ và cứng hóa các thuật toán rất có ý nghĩa đối với sự an toàn trong các giao dịch trên mạng. Nhìn chung, đối với Việt Nam, việc làm chủ công nghệ cứng hóa thuật toán DES rất có ý nghĩa trong việc đảm bảo an toàn giao dịch trên mạng, đảm bảo an toàn trong truyền tin cho các đơn vị cơ yếu tại Việt Nam. Hiện nay, chúng tôi đang triển khai cứng hóa thuật toán DES nhờ các công nghệ thiết kế số hiện đại, các chương trình và mạch phần cứng sẽ được chúng tôi đề cập đến trong các bài báo tiếp theo.