Bài giảng Lý thuyết mật mã và an toàn thông tin - 3
3.5 Phép tối ưu hoá thời gian - Bộ nhớ
Bằng cách phân tích xát suất thành công của thuật toán có
thể chứng tỏ rằng nếu mt2 ~ N=256 thì xác suất để K= X(i,t-j)
với i, j nào đó sẽ vào khoảng 0.8 mt/ N. Điều này gợi ý cho ta
nên lấy m ~ t ~ N1/3 và xây dựng khoảng N1/3 bảng, mỗi bảng
dùng hàm rút gọn khác nhau. Khi đó thời gian tính toán là cỡ O(N).
17 trang |
Chia sẻ: vutrong32 | Lượt xem: 1206 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Bài giảng Lý thuyết mật mã và an toàn thông tin - 3, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
3.4.1 Các chế độ hoạt động của DES
3.5 Phép tối ưu hoá thời gian - Bộ nhớ
3.4 DES trong thực tế
1_ Chế độ chuyển mã điện tử ECB
( Electronic CodeBook mode)
4_ Chế độ phản hồi mã CFB
( Cipher FeedBack mode)
2_ Chế độ phản hồi đầu ra OFB
( Output FeedBack mode)
3_ Chế độ liên kết khối mã CBC
( Cipher Block Chaining mode)
Chương 3: CHUẨN MÃ DỮ LIỆU DES (tt)
Chương 3: CHUẨN MÃ DỮ LIỆU DES (tt)
3.4 DES trong thực tế
Mặc dù việc mô tả DES khá dài song người ta có thể thực
hiện DES rất hữa hiệu bằng cả phần cứng lẫn phần mềm. Phép toán
duy nhất cần được thực hiện là phép hoặc loại trừ (XOR) các xâu bít.
Hàm mở rộng E, các hộp S, các hoán vị IP và P và việc tính toán
các giá tri K1,...,K16 đều có thể thực hiện được cùng lúc bằng tra
bảng(trong phần mền) hoặc bằng cách nối cứng chúng thành một
mạch.
Các ứng dụng phần cứng hiện thời có thể đạt được tốc độ mã
hoá cực nhanh. Công ty Digital Equipment đã thông báo tại hội nghị
CRUPTO'92 rằng họ sẽ chế tạo một chíp có 50 ngàn tranzistor có thể
mã hoá với tốc độ 1 Gbít/s bằng cách dùng nhịp có tốc độ 250MHz.
Giá của chíp này vào khoảng 300$.
Tới năm 1991 đã có 45 ứng dụng phần cứng và chương trình cơ sở
của DES được Uỷ ban tiêu Chuẩn quốc gia Mỹ (NBS) chấp
thuận.
Một ứng dụng quan trọng của DES là trong giao dịch
ngân hàng, DES được dùng để mã hoá các số định danh
cá nhân (PIN) và việc chuyển tài khoản bằng máy tự
động ATM. Ngoài ra DES còn được sử dụng rộng rãi
trong các tổ chức chính phủ chẳng hạng như bộ năng
lượng, Bộ Tư pháp và hệ thống dự trử liên bang.
3.4 DES trong thực tế
- Bảo mật cho mạng không dây
- Thẻ thông minh và cảm ứng nhận dang vân tay
- Bảo mật trong UNIX và LINUX
- Chế tạo ổ cứng an toàn
3.4.1 Các chế độ hoạt động của DES
Chế độ ECB tương ứng với cách dùng thông thường của mã
khối: với một dãy các khối bản rõ cho trước x1x2 . . .
(mỗi khối có 64 bít), mỗi xi sẽ được mã hoá bằng cùng một khoá K
để tạo thành một chuỗi các khối bản mã y1 y2 ... theo quy tắc yi =
eK(yi-1 xi) với i 1.
1_ Chế độ chuyển mã điện tử ECB
( Electronic CodeBook mode)
3.4.1 Các chế độ hoạt động của DES
2_ Chế độ phản hồi đầu ra OFB
( Output FeedBack mode)
Trong chế độ OFB dòng khoá được tạo ra sẽ được cộng
mod 2 với bản rõ (hoạt động như hệ mã vòng). OFB thực sự là
hệ mã vòng đồng bộ: dòng khoá được tạo bởi việc mã lặp vectơ
khởi tạo 64 bit (vectơ IV). Ta xác định z0= IV và dòng khoá
z1 z2 theo công thức zi= eK (zi-1) với i 1
Dãy bản rõ x1 x2 sau đó sẽ được mã hoá bằng cách tính
yi = xi zi với i 1
3.4.1 Các chế độ hoạt động của DES
3_ Chế độ liên kết khối mã CBC
( Cipher Block Chaining mode)
Trong chế độ CBC mỗi khối bản mã y1 y2 với
yi = ek(yi-1 xi) là kết quả của phép XOR của khối bản mã tiếp
theo với khoá K, với yo=IV , i 1 mô tả ở hình 3.4
Hình 3.4. Chế độ CBC
3.4.1 Các chế độ hoạt động của DES
x1 x2
+ +
eK eK
y1 y2
IV=y0 . . .
Encrypt
y1 y2
dK dK
+ +
x1 x2
IV=y0 . . .
Decrypt
4_ Chế độ phản hồi mã CFB
( Cipher FeedBack mode)
3.4.1 Các chế độ hoạt động của DES
Bắt đầu là vectơ khởi tạo y0=IV tiếp theo tạo các phần
tử zi của dòng khoá bằng cách mã hoá khối bản mã trước đó
với zi= eK(yi-1) , i 1 . Cuối cùng ta tính yi = zi xi , i 1
mô tả ở hình 3.5
x1 x2
+ +
y1 y2
IV=y0
. . .
Encrypt
eK eK
y1 y2
+ +
x1 x2
IV=y0
. . .
Decrypt
eK eK
3.4.1 Các chế độ hoạt động của DES
Hình 3.5 CFB
Nhận xét
+ ECB và OFB thì sự thay đổi của một số bản xi làm thay đổi
khối mã yi tương ứng, nhưng các khối bản mã khác không
ảnh hưởng nên OFB thường được dùng để mã hoá khi truyền
vệ tinh.
+ Trong chế độ CBC và CFB nếu một khối bản rõ xi bị thay đổi
thì yi và tất cả khối bản mã tiếp theo sẽ bị ảnh hưởng nên chế
độ CBC và CFB rất hiệu quả trong việc xác thực
3.5 Phép tối ưu hoá thời gian - Bộ nhớ
Trong phần này sẽ mô tả phép tối ưu hoá thời gian- bộ nhớ
khi phá mã DES bằng cách tấn công bản rõ chọn lọc.Oscar
thu cặp rõ-mã được tạo bởi khóa K (chưa biết) tức là có x , y
với y= eK(x) và muốn xác định khoá K
Tìm khoá bằng pp vét cạn: Với một cặp rõ-mã cho trước
thì ta phải thử tất cả 255 khoá trước khi tìm được khoá đúng.
Oscar tính yK= eK(x) đối với toàn bộ 2
56 khoá K và lập bảng
các cặp (yK,K) sau đó Oscar thu được bản mã y và chỉ cần
nhìn vào giá trị y trong bảng thì tìm ngay được khoá K.
Như vậy việc tìm K yêu cầu một thời gian cố định nhưng cần
thời gian tính toán trước lớn và cũng cần dung lượng bộ nhớ
lớn.
3.5 Phép tối ưu hoá thời gian - Bộ nhớ
Phép tối ưu hoá thời gian- bộ nhớ sẽ có thời tgian tính toán
nhỏ hơn phép tìm kiếm vét cạn và yêu cầu bộ nhớ nhỏ hơn
viêc lập bảng tra cứu. Có thể mô tả thuật toán theo 2 tham số
m và t là các số nguyên dương, thuật toán cần một hàm rút
rọn R để rút gọn xâu bít có độ dài 64 bít thành xâu có độ dài
56 bít.
Giả sử x là một xâu bản rõ 64 bit, hãy xác định hàm
g(Ko)=R(eKo(x)) với một xâu Ko có độ dài 56 bít, g là một
hàm thực hiện ánh xạ từ 56 bít sang 56 bít. Đầu tiên Oscar
chọn ngẫu nhiên m xâu có độ dài 56 bít được ký hiệu X(i,0) ,
1 i m và tính x(i,j) với theo công thức sau:
X(i,j)=g(X(i,j-1)) với 1 i m , 1 j t mô tả ở hình 3.6
3.5 Phép tối ưu hoá thời gian - Bộ nhớ
),(...)1,()0,(
.
.
.
),2(...)1,2()0,2(
),1(...)1,1()0,1(
tmXmXmX
tXXX
tXXX
ggg
ggg
ggg
Hình 3.6: Tính X(i,j)
Sau đó Oscar xây dựng một bảng các cặp T=(X(i,t),X(i,0))
được sắp xếp theo toạ độ đầu của chúng (tức là chỉ lưu giữ
cột đầu và cột cuối của mảng X).
Sau khi thu được bản mã y (là bản mã của bản rõ x đã chọn).
Oscar cần phải xác định K và chỉ xác định được nếu K nằm
trong t cột đầu của mảng X, tuy nhiên ông ta làm được điều
này bằng cách chỉ nhìn vào bảng T
Giả sử rằng K=X(i,t-j) với 1 j t (giả sử K nằm ở t cột đầu
tiên của X). Khi đó gj(K)= x(i,t) trong đó gj kí hiệu hàm
nhận được bằng cách lặp g một số lần bằng j .Ta thấy rằng
gj(K)= gj-1 (g (K))
= gj-1 (R (e K(x))) = g
j-1 (R (y))
3.5 Phép tối ưu hoá thời gian - Bộ nhớ
Chúng ta tính lại yj , với 1 j t như sau:
Từ đó ta thấy yj = X(i,t) nếu K= X(i,t-j). Tuy nhiên cần chú
ý rằng yj = X(i,t) chưa đủ đảm bảo là K= X(i,t-j) vì hàm rút
gọn R không phải là hàm đơn ánh: miền xác định của R có
lực lượng là 264 nhưng miền giá trị có lực lượng là 256 , vì
vậy trung bình có 28 = 256 nghịch ảnh của một xâu bít bất kỳ
cho trước có độ dài 56. Do đó cần phải kiểm tra xem
y= eX(i,t-j)(x) hay không để biết liệu X(i,t-j) có thực sự là
khoá hay không. Ta không cần lưu giá trị X(i,t-j) nhưng có
thể dễ dàng tính lại nó từ X(i,0) bằng cách lặp t-j lần hàm g.
3.5 Phép tối ưu hoá thời gian - Bộ nhớ
R(y) nếu j = 1
yj =
g(yj-1) nếu 2 j t
3.5 Phép tối ưu hoá thời gian - Bộ nhớ
Oscar thực hiện thuật toán được mô tả như sau:
1. Tính y1= R(y)
2. For j = 1 to t do
3. If yj = X(i,t-j) với giá trị i nào đó then
4. Tính X(i,t-j) từ X(i,0) bằng cách lặp t-j lần hàm g
5. If y = eX(i,t-j)(x) then
đặt K= X(i,t-j) và QUIT
6. Tính yj+1 = g(yj)
3.5 Phép tối ưu hoá thời gian - Bộ nhớ
Bằng cách phân tích xát suất thành công của thuật toán có
thể chứng tỏ rằng nếu mt2 ~ N=256 thì xác suất để K= X(i,t-j)
với i, j nào đó sẽ vào khoảng 0.8 mt/ N. Điều này gợi ý cho ta
nên lấy m ~ t ~ N1/3 và xây dựng khoảng N1/3 bảng, mỗi bảng
dùng hàm rút gọn khác nhau. Khi đó thời gian tính toán là cỡ
O(N).
Các file đính kèm theo tài liệu này:
- mon_mat_ma_an_toan_thong_tin_3_28.pdf