lOMoARcPSD| 40651217 lOMoAR cPSD| 4065121
Phần 2: Chuẩn mã dữ liệu DES (Data Encryption Standard) lOMoARcPSD| 40651217
1. Giới thiệu chung về DES
Ngày 13/5/1973 ủy ban quốc gia về tiêu chuẩn của Mỹ
công bố yêu cầu về hệ mật mã áp dụng cho toàn quốc.
Điều này ã ặt nền móng cho chuẩn mã hóa dữ liệu, hay là DES.
1975, công bố bởi công ty IBM, cải tiến từ hệ mã Lucifer.
Sau ó DES ược xem như là chuẩn mã hóa dữ liệu cho các ứng dụng. lOMoARcPSD| 40651217
2. Đặc iểm của thuật toán DES
DES là thuật toán mã hóa khối, ộ dài mỗi khối là 64 bit.
Khóa dùng trong DES có ộ dài toàn bộ là 64 bit. Tuy nhiên
chỉ có 56 bit thực sự ược sử dụng; 8 bit còn lại chỉ dùng cho
việc kiểm tra. DES xuất ra bản mã 64 bit.
Thuật toán thực hiện 16 vòng
Mã hoá và giải mã ược sử dụng cùng một khoá.
DES ược thiết kế ể chạy trên phần cứng. lOMoARcPSD| 40651217
2. Đặc iểm của thuật toán DES Sơ
ồ khái quát của thuật toán sinh mã trong DES y1 DES y2 … y64 lOMoARcPSD| 40651217 z1 z2 … z56 lOMoARcPSD| 40651217 3. Mô tả thuật toán lOMoARcPSD| 40651217 lOMoARcPSD| 40651217 3. Mô tả thuật toán
Thuật toán ược thực hiện trong 3 giai oạn:
1. Cho bản rõ x (64bit) ược hoán vị khởi tạo IP
(Initial Permutation) tạo nên xâu bit x0. x0 = IP(x) = L0R0
L0 là 32 bit ầu tiên của x0. lOMoARcPSD| 40651217
R0 là 32 bit cuối của x0. lOMoARcPSD| 40651217 3. Mô tả thuật toán Bộ chuyển vị IP
• Hoán vị khởi tạo nhằm thay ổi vị trí của các bít trong khối dữ liệu vào.
• Ví dụ, hoán vị khởi tạo chuyển bít 1 thành bít 58, bít 2 thành
bít 50, bít 3 thành bít 42,... 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 lOMoARcPSD| 40651217 3. Mô tả thuật toán 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7
2. Từ L0 và R0 sẽ lặp 16 vòng, tại mỗi vòng tính: Li = Ri-1
Ri = Li-1 f(Ri-1,Ki) với i= 1, 2,…,16 với:
là phép XOR của hai xâu bit: lOMoARcPSD| 40651217 3. Mô tả thuật toán 0 0=0 , 1 1=0 1 0=1, 0 1=1 f là hàm (mô tả sau).
Ki là các xâu có ộ dài 48 bit ược tính như là các hàm của khóa K.
K1 ến K16 lập nên một lịch khóa. lOMoARcPSD| 40651217 3. Mô tả thuật toán 3. Tại vòng thứ 16: lOMoARcPSD| 40651217 3. Mô tả thuật toán R16 ổi chỗ cho L16.
Sau ó ghép 2 nửa R16, L16 cho i qua hoán vị nghịch ảo của
hoán vị IP sẽ tính ược bản mã.
Bản mã cũng có ộ dài 64 bít. lOMoARcPSD| 40651217
Downloaded by Phuong Le (lephuong0301@gmail.com) lOMoARcPSD| 40651217 Hàm f
• Hàm f lấy ối số ầu là xâu nhập Ri-1 (32 bit) ối số thứ
hai là Ki (48 bit) và tạo ra xâu xuất có ộ dài 32 bit.
• Các bước sau ược thực hiện:
1. Đối số ầu Ri-1 sẽ ược “mở rộng” thành xâu có ộ dài
48 bit bởi hàm mở rộng E cố ịnh.
E(Ri) bao gồm 32 bit từ Ri, ược hoán vị theo một
cách thức xác ịnh, với 16 bit ược tạo ra 2 lần (lặp). Hàm f lOMoARcPSD| 40651217 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 Hàm mở rộng E Hàm f lOMoARcPSD| 40651217
2. Tính E(Ri-1) Ki kết quả ược một khối có ộ dài 48 bit.
• Khối này sẽ ược chia làm 8 khối B = B1B2B3B4B5B6B7B8.
• Mỗi khối có ộ dài là 6 bít.
3. Cho các khối Bi (i = 1, 2, .., 8) i qua hộp Si: biến một
khối Bi có ộ dài 6 bit thành một khối Ci có ộ dài 4 bít. lOMoARcPSD| 40651217 S-box
Mỗi hộp S (S-box) là một bảng gồm 4 hàng và 16 cột ược ánh số từ 0:
Mỗi hộp S có hàng 0,1,2,3; cột 0,1,2,…,15.
Mỗi phần tử của hộp là một số 4 bít.
6 bít vào hộp S sẽ xác ịnh số hàng và số cột ể tìm kết quả ra. S-box
Mỗi khối Bi có 6 bít kí hiệu là b1, b2, b3, b4, b5 và b6. lOMoARcPSD| 40651217
Bít b1 và b6 ược kết hợp thành một số 2 bít, nhận
giá trị từ 0 ến 3, tương ứng với một hàng trong bảng S.
4 bít ở giữa, từ b2 tới b5, ược kết hợp thành một số 4
bít, nhận giá trị từ 0 ến 15, tương ứng với một cột trong bảng S. lOMoARcPSD| 40651217 S-box lOMoARcPSD| 40651217 S-box lOMoARcPSD| 40651217 S-box lOMoARcPSD| 40651217 S-box lOMoARcPSD| 40651217 S-box
Ví dụ: Ta có B1=011000 thì b1b6= 00 (xác ịnh r=0),
b2b3b4b5=1100 (xác ịnh c=12), từ ó ta tìm ược phần tử ở vị trí
(0,12) --> S1(B1)=0101 (tương ứng với số 5). b2b3b4b5=1100 b1b6=00 Hộp S1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 lOMoARcPSD| 40651217
- Mỗi xâu xuất 4 bit của các hộp S ược ưa vào các Cj
tương ứng: Cj = Sj(Bj) (1<=j<=8). Hàm f
4. Xâu bit C = C1C2C3C4C5C6C7C8 có ộ dài 32 bit ược hoán vị bởi
hoán vị cố ịnh P. Kết quả có P(C)= f(Ri, Ki). lOMoARcPSD| 40651217 16 7 20 21 Hoán vị P 29 12 28 17 Khóa K 1 15 23 26
K là một xâu có ộ dài 64 bit trong 5 18 31 10 ó 56
bit dùng làm khóa và 8 bit dùng ể 2 8 24 14
kiểm tra (phát hiện lỗi). 32 27 3 9
Các bit ở các vị trí 8, 16,…, 64 ược xác 19 13 30 6
ịnh, sao cho mỗi byte chứa số lẻ các
số 1, vì vậy từng lỗi có thể ược 22 11 4 25 phát hiện trong mỗi 8 bit.
Các bit kiểm tra ược bỏ qua khi tính lịch khóa. lOMoARcPSD| 40651217 lOMoARcPSD| 40651217 Khóa K
Quá trình tạo các khóa con (subkeys) từ khóa K:
Cho khóa K 64 bit, loại bỏ các bit kiểm tra và hoán vị
các bit còn lại của K tương ứng với hoán vị cố ịnh PC- 1.
Ta viết PC1(K) = C0D0, với C0 bao gồm 28 bít ầu tiên của
PC-1(k) và D0 là 28 bit còn lại. lOMoARcPSD| 40651217 Khóa K Trong
ó, bảng số bit dịch trái tại mỗi vòng: lOMoARcPSD| 40651217 Khóa K Các hoán vị cố ịnh PC-1 và PC-2: lOMoARcPSD| 40651217 Khóa K Các hoán vị cố ịnh PC-1 và PC-2: lOMoARcPSD| 40651217 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 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ừ K16 ến K1, nghĩa là trong bước 2 của quá trình mã
hoá dữ liệu ầu vào ở trên Ri-1 sẽ ược XOR với K17-i chứ không phải với Ki. Đặc iểm của mã DES lOMoARcPSD| 40651217
Tính chất bù của mã DES: DES có tính chất bù: trong ó:
Ā là phần bù của A theo từng bít (1 thay bằng 0 và ngược lại).
EK là bản mã hóa của E với khóa K. P và C là văn bản rõ (trước
khi mã hóa) và văn bản mã (sau khi mã hóa).
Do tính bù, ta có thể giảm ộ phức tạp của tấn công duyệt toàn
bộ xuống 2 lần (tương ứng với 1 bít) với iều kiện là ta có thể lựa chọn bản rõ. Đặc iểm của mã DES lOMoARcPSD| 40651217
Các khóa yếu trong mã DES:
• DES có 4 khóa yếu (weak keys).
• Khi sử dụng khóa yếu thì mã hóa (E) và giải mã (D) sẽ cho ra cùng kết quả: EK(EK(P)) = P hoặc tương ương EK = DK Đặc iểm của mã DES
Các khóa yếu trong mã DES: •
Bên cạnh ó, còn có 6 cặp khóa nửa yếu (semi-weak keys). •
Mã hóa với một khóa trong cặp (K1), tương ương với giải mã với khóa còn lại (K2): EK1(EK2(P))=P hoặc tương ương EK1=DK2 lOMoARcPSD| 40651217 •
Tuy nhiên có thể dễ dàng tránh ược những khóa này
khi thực hiện thuật toán, có thể bằng cách thử hoặc
chọn khóa một cách ngẫu nhiên. •
Khi ó khả năng chọn phải khóa yếu là rất nhỏ. Đặc iểm của mã DES 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. lOMoARcPSD| 40651217
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 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. Bài tập
Cho bản rõ mang nội dung: x=“NANGLUONGGIO”. Cho khoá K=THUATTOANDES
Thực hiện mã hóa văn bản rõ trên theo thuật toán DES