Giáo án an toàn bảo mật 7
- 11 trang
- file .pdf
khi tìm được một khoá K thảo mãn eK(x) = y. Cần chú ý là có thể có nhiều
hơn một khoá K như vậy).
Ngay từ năm 1977, Diffie và Hellman đã gợi ý rằng có thể xây dựng
một chíp VLSI (mạch tích hợp mật độ lớn) có khả năng kiểm tra được
106khoá/giây. Một máy có thể tìm toàn bộ không gian khoá cỡ 106 trong
khoảng 1 ngày. Họ ước tính chi phí để tạo một máy như vậy khoảng 2.107$.
Trong cuộc hội thảo tại hội nghị CRYPTO’93, Michael Wiener đã đưa
ra một thiết kế rất cụ thể về máy tìm khoá. Máy này có khả năng thực hiện
đồng thời 16 phép mã và tốc độ tới 5×107 khoá/giây. Với công nghệ hiện nay,
chi phí chế tạo khoảng 10,5$/khung. Giá của một khung máy chứa 5760 chíp
vào khoảng 100.000$ và như vậy nó có khả năng tìm ra một khoá của DES
trong khoảng 1,5 ngày. Một thiết bị khung 10 khung máy như vậy có giá
chừng 106 $ sẽ giảm thời gian tìm kiếm khoá trng bình xuống còn 3,5 giờ.
3.13. DES trong thực tế.
Mặc dù việc mô tả DES khá dài dòng 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ền. Các phép toán duy nhất
cần được thực hiện là phép hoặc loại trừ 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 xung có 50 ngàn xung có thể mã hoá với tốc độ 1
Gbít/s bằng cách xung nhịp có tốc độ 250MHz. Giá của xung 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 Mỹ -
(ABA) 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 thủ quỹ tự động (ATM). DES cũng được Hệ
thống chi trả giữa các nhà băng của Ngân hàng hối đoái (CHIPS) dùng để xác
http://www.ebook.edu.vn 67
thực các giao dịch vào khoản trên 1,5×1012 USA/tuần. DES còn được sử dụng
rộng rãi trong các tổ chức chính phủ. Chẳng hạn như bộ năng lượng, Bộ Tư
pháp và Hệ thống dự trữ liên bang.
3.14. Các chế độ hoạt động của DES.
Có 4 chế độ làm việc đã được phát triển cho DES: Chế độ chuyển mã
điện tử (ECB), chế độ phản hồi mã (CFB), chế độ liên kết khối mã (CBC) và
chế độ phản hồi đầu ra (OFB). 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 x1,x2,. . .( 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ã y1y2 ... theo quy tắc yi = eK(yi-1⊕xi) i ≥ 1. Việc sử
dụng chế độ CBC được mô tả trên hình 3.4.
Hình 3.4. Chế độ CBC.
http://www.ebook.edu.vn 68
x1 x2
IV=y0 + +
...
Mã hoá
eK eK
Encrypt
y1 y2
y1 y2
Giải mã
dK dK
Decrypt
IV=y0 + + ...
x1 x2
Trong các chế độ OFB và CFB dòng khoá được tạo ra sẽ được cộng mod 2
với bản rõ (tức là nó hoạt động như một hệ mã dòng, xem phần 1.1.7). OFB
thực sự là một hệ mã dòng đồng bộ: dòng khoá được tạo bởi việc mã lặp véc
tơ khởi tạo 64 bít (véc tơ IV). Ta xác định z0 =IV và rồi tính dòng khoá z1z2 . .
. theo quy tắc zi = eK(zi-1), i≥1. Dãy bản rõ x1x2 . . . sau đó sẽ được mã hoá
bằng cách tính yi = xi ⊕ zi,i ≥1.
Trong chế độ CFB, ta bắt đầu với y0 = IV (là một véc tơ khởi tạo 64
bít) và tạo phần tử zi của dòng khoá bằng cách mã hoá khối bản mã trước đó.
Tức zi = eK(yi-1), i ≥1. Cũng như trong chế độ OFB: yi = xi ⊕ zi,i ≥1. Việc sử
dụng CFB được mô tả trên hình 3.5 (chú ý rằng hàm mã DES eK được dùng
cho cả phép mã và phép giải mã ở các chế độ CFB và OFB).
Hình 3.5. Chế độ CFB
http://www.ebook.edu.vn 69
x1 x2
...
IV=y0 eK + eK +
Mã hoá
Encrypt y2
y1
y1 y2
...
IV=y0 eK + eK +
Giải mã
Decrypt x2
x1
Cũng còn một số biến tấu của OFB và CFB được gọi là các chế độ phản hồi K
bít (1 < K < 64 ). ở đây ta đã mô tả các chế độ phản hồi 64 bít. Các chế độ
phản hồi 1 bít và 8 bít thường được dùng trong thực tế cho phép mã hoá đồng
thời 1 bit (hoặc byte) số liệu.
Bốn chế độ công tác có những ưu, nhược điểm khác nhau. ở chế độ
ECB và OFB, sự thay đổi của một khối bản rõ xi 64 bít sẽ làm thay đổi khối
bản mã yi tương ứng, nhưng các khối bản mã khác không bị ảnh hưởng.
http://www.ebook.edu.vn 70
Trong một số tình huống đây là một tính chất đáng mong muốn. Ví dụ, chế độ
OFB thường được dùng để mã khi truyền vệ tinh.
Mặt khác ở các chế độ CBC và CFB, nếu một khối bản rõ xi bị thay đổi
thì yi và tất cả các khối bản mã tiếp theo sẽ bi ảnh hưởng. Như vậy các chế độ
CBC và CFB có thể được sử dụng rất hiệu quả cho mục đích xác thực. Đặc
biệt hơn, các chế độ này có thể được dùng để tạo mã xác thực bản tin ( MAC -
message authentication code). MAC được gắn thêm vào các khối bản rõ để
thuyết phục Bob tin rằng, dãy bản rõ đó thực sự là của Alice mà không bị
Oscar giả mạo. Như vậy MAC đảm bảo tính toàn vẹn (hay tính xác thực) của
một bản tin ( nhưng tất nhiên là MAC không đảm bảo độ mật).
Ta sẽ mô tả cáchb sử dụng chế độ BCB để tạo ra một MAC. Ta bắt đầu
bằng véc tơ khởi tạ IV chứa toàn số 0. Sau đó dùng chế đô CBC để tạo các
khối bản mã y1,. . . ,yn theo khoá K. Cuối cùng ta xác định MAC là yn. Alice
sẽ phát đi dãy các khối bản rõ x1,x2,. . . ,xn cùng với MAC. Khi Bob thu được
x1. . .xn anh ta sẽ khôi phục lại y1. . .yn bằng khoá K bí mật và xác minh xem
liệu yn có giống với MAC mà mình đã thu được hay không.
Nhận thấy Oscar không thể tạo ra một MAC hợp lệ do anh ta không
biết khoá K mà Alice và Bob đang dùng. Hơn nữa Oscar thu chặn được dãy
khối bản rõ x1. . .xn và thay đổi ít nhiều nội dung thì thì chắc chắn là Oscar
không thể thay đổi MAC để được Bob chấp nhận.
Thông thường ta muốn kết hợp cả tính xác thực lẫn độ bảo mật. Điều
đó có thể thực hiện như sau: Trước tiên Alice dùng khoá K1 để tạo MAC cho
x1. . . xn . Sau đó Alice xác định xn+1 là MAC rồi mã hoá dãy x1. . .xn+1 bằng
khoá thứ hai K2 để tạo ra bản mã y1. . .yn+1 . Khi Bob thu được y1. . .yn+1 ,
trước tiên Bob sẽ giải mã ( bằng K2) và kiểm tra xem xn+1 có phải là MAC đối
với dãy x1. . .xn dùng K1 hay không.
Ngược lại, Alice có thể dùng K1 để mã hoá x1. . .xn và tạo ra
được y1...yn , sau đó dùng K2 để tạo MAC yn+1 đối với dãy y1. . .yn. Bob sẽ
dùng K2 để xác minh MAC và dung K1 để giải mã y1. . .yn
http://www.ebook.edu.vn 71
Chương 4: Mật mã công khai
4.1. Giới thiệu về hệ mật mã khóa công khai.
4.1.1. Giới thiệu.
Trong mô hình mật mã cổ điển mà cho tới nay vẫn còn đang được
nghiên cứu Alice (người gửi) và Bob (người nhận) bằng cách chọn một
khoá bí mật K. Sau đó Alice dùng khoá K để mã hoá theo luật eK và Bod
dùng khoá K đó để giải mã theo luật giải dK . Trong hệ mật này, dK hoặc
giống như eK hoặc dễ dàng nhận được từ nó vì quá trình giải mã hoàn toàn
tương tự như quá trình mã, nhưng thủ tục khoá thì ngược lại. Nhược điểm
lớn của hệ mật này là nếu ta để lộ eK thì làm cho hệ thống mất an toàn,
chính vì vậy chúng ta phải tạo cho các hệ mật này một kênh an toàn mà
kinh phí để tạo một kênh an toàn không phải là rẻ.
Ý tưởng xây dựng một hệ mật khoá công khai là tìm một hệ mật
không có khả năng tính toán để xác định dK nếu biết được eK. Nếu thực
hiện được như vậy thì quy tắc mã eK có thể được công khai bằng cách công
bố nó trong danh bạ, và khi Alice (người gửi) hoặc bất cứ một ai đó muốn
gửi một bản tin cho Bob (người nhận) thì người đó không phải thông tin
trước với Bob (người nhận) về khoá mật, mà người gửi sẽ mã hoá bản tin
bằng cách dùng luật mã công khai eK. Khi bản tin này được chuyển cho
Bob (người nhận) thì chỉ có duy nhất Bob mới có thể giải được bản tin này
bằng cách sử dụng luật giải mã bí mật dK.
Ý tưởng về hệ mật khoá công khai đã được Diffie và Heliman đưa ra
vào năm 1976. Còn việc thực hiện hệ mật khoá công khai thì lại được
Rivest. Shamin và Adieman đưa ra đầu tiên vào năm 1977. Họ đã tạo nên
hệ mật RSA nổi tiếng. Kể từ đó đã có một số hệ mật được công bố, độ mật
của từng hệ dựa trên các bài toán tính toán khác nhau. Trong đó quan trọng
nhất là các hệ mật sau:
• Hệ mật RSA
Độ bảo mật của hệ RSA dựa trên độ khó của việc phân tích ra thừa số
nguyên tố các số nguyên tố lớn.
http://www.ebook.edu.vn 72
• Hệ mật xếp balô Merkle – Hellman.
Hệ này và các hệ có liên quan dựa trên tính khó giải của bài toán tổng
các tập con.
• Hệ mật McEliece
Hệ mật nanỳ dựa trên lý thuyết mã đại số và vẫn được coi là an toàn.
Hệ mật McEliece dựa trên bài toán giải mã cho các mã tuyến tính.
• Hệ mật ElGamal
Hệ ElGamal dựa trên tính khó giải của bài toán Logarit rời rạc trên
các trường hữu hạn.
• Hệ mật Chor – Rivest
Hệ mật Chor – Rivest cũng được xem như một loại hệ mật xếp balô.
Tuy nhiên hệ mật này vẫn còn được coi là hệ mật an toàn.
• Hệ mật trên các đường cong Elliptic.
Các hệ này là biến tướng của hệ mật khác, chúng làm việc trên các
đường cong Elliptic chứ không phải trên các trường hữu hạn. Hệ mật này
đảm bảo độ mật vơí khoá số nhỏ hơn các hệ mật khoá công khai khác.
Một chú ý quan trọng là một hệ mật khoá công khai không bao giờ có
thể bảo đảm được độ mật tuyệt đối (an toàn vô điền kiện). Sở dĩ vậy vì đối
phương nghiên cứu một bản mã C có thể mã lần lượt các bản rõ có thể
bằng luật mã công khai eK cho tới khi anh ta tìm được một bản rõ duy nhất
P bảo đảm C = eK(P). Bản rõ P này chính là kết quả giải mã của C. Bởi vậy
ta chỉ nghiên cứu độ mật về mặt tính toán của hệ này.
Một chú ý quan trọng và có ý ích khi nghiên cứu nữa là khái niệm về
hàm cửa sập một chiều. Ta định nghĩa khái niệm này một cách không hình
thức.
Định nghĩa: Hàm f: X →Y đực gọi là hàm một chiều nếu tính y=f(x)
với mọi x ∈ X là dễ nhưng việc tìm x khi biết y lại là vấn đề khó.
Thực ra phát biểu trên chỉ là định nghĩa phi hình thức (do thuật ngữ
“khó” được dùng đến là không định lượng và thậm chí sau này chúng ta đã
biết là ngay cả khi đã định lượng bằng sự không tồn tại thuật toán giải bài
http://www.ebook.edu.vn 73
toán ngược trong phạm vi đa thức thì khái niệm “khó” nêu trên có tồn tại hay
không cũng chưa được ai khẳng định rõ ràng) và điều đáng tiếc hơn nữa là tất
cả các hàm ứng cử viên cho khái niệm này cho đến nay chỉ mới “được coi là
một chiều.
Chúng ta dễ dàng thống nhất được với nhau là chỉ riêng hàm một chiều
là không đủ để xây dựng thành một luật mã theo kiểu công khai hàm mã hoá
do vì chính bản thân chủ nhân của bức điện mật cũng gặp phải hoàn cảnh
tương tự như người khác. Như vậy để có thể giải mã một cách hữu hiệu thì
người giải mã phải có một “hiểu biết tuyệt mật” nào đó về khoá giải (một hiểu
biết theo kiểu nếu biết nó thì cách giải dễ dàng) “hiểu biết tuyệt mật” này
được gọi là cửa sập. Hàm một chiều như trên được gọi là hàm một chiều có
cửa sập.
Dĩ nhiên dù không biết cửa sập thì người thám mã vẫn có thể sử dụng
hiểu biết về hàm f để lần lượt tính tất cả các giá trị f(x) cho mọi bản rõ x cho
tới khi tìm được bản rõ thoả mãn y=f(x). Bản rõ tìm được trên chính là kết
quả giải mã của y. Ngoài ra người thám mã còn có thể sử dụng nhiều phương
pháp tấn công khác nhằm vào đặc thù riêng của từng hàm f để tìm ra bản rõ
trong các trường hợp riêng rẽ khác chứ không nhất thiết phải giải bài toán
ngược.
Tóm lại đọc an toàn của hệ mật khoá công khai không chỉ phụ thuộc vào
độ khó của việc giải bài toán ngược mà tính bền của sự an toàn này còn phụ
thuộc vào các phương pháp tấn công của các thám mã, vả lại như đã trình bày
ở trên thì toàn bộ các hê khoá mật công khai đang được sử dụng đều chưa đực
sự khẳng định về tính “khó” mà ngay cả khi đã có sự đảm bảo này thì có sự
tiến bộ không ngừng của công nghệ tính toán tghì hiển nhiên nhiều vấn đề
chưa thể chứp nhận được trong hiện tại sẽ được chấp nhận trong tương lai.
Thực tế không chỉ đối với các hệ mât khoá công khai do vậy quan niêm mới
về tính an toàn tương đối mà với nó đã nẩy sinh ra các hệ mật khoá công khai
đồng thời cũng đặt cho chúng ta nhiều bài toán nghiêm túc phải giải quyết khi
sử dụng hệ mật này. Chương này giới thiệu cụ thể một số hệ mật công khai
http://www.ebook.edu.vn 74
hơn một khoá K như vậy).
Ngay từ năm 1977, Diffie và Hellman đã gợi ý rằng có thể xây dựng
một chíp VLSI (mạch tích hợp mật độ lớn) có khả năng kiểm tra được
106khoá/giây. Một máy có thể tìm toàn bộ không gian khoá cỡ 106 trong
khoảng 1 ngày. Họ ước tính chi phí để tạo một máy như vậy khoảng 2.107$.
Trong cuộc hội thảo tại hội nghị CRYPTO’93, Michael Wiener đã đưa
ra một thiết kế rất cụ thể về máy tìm khoá. Máy này có khả năng thực hiện
đồng thời 16 phép mã và tốc độ tới 5×107 khoá/giây. Với công nghệ hiện nay,
chi phí chế tạo khoảng 10,5$/khung. Giá của một khung máy chứa 5760 chíp
vào khoảng 100.000$ và như vậy nó có khả năng tìm ra một khoá của DES
trong khoảng 1,5 ngày. Một thiết bị khung 10 khung máy như vậy có giá
chừng 106 $ sẽ giảm thời gian tìm kiếm khoá trng bình xuống còn 3,5 giờ.
3.13. DES trong thực tế.
Mặc dù việc mô tả DES khá dài dòng 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ền. Các phép toán duy nhất
cần được thực hiện là phép hoặc loại trừ 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 xung có 50 ngàn xung có thể mã hoá với tốc độ 1
Gbít/s bằng cách xung nhịp có tốc độ 250MHz. Giá của xung 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 Mỹ -
(ABA) 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 thủ quỹ tự động (ATM). DES cũng được Hệ
thống chi trả giữa các nhà băng của Ngân hàng hối đoái (CHIPS) dùng để xác
http://www.ebook.edu.vn 67
thực các giao dịch vào khoản trên 1,5×1012 USA/tuần. DES còn được sử dụng
rộng rãi trong các tổ chức chính phủ. Chẳng hạn như bộ năng lượng, Bộ Tư
pháp và Hệ thống dự trữ liên bang.
3.14. Các chế độ hoạt động của DES.
Có 4 chế độ làm việc đã được phát triển cho DES: Chế độ chuyển mã
điện tử (ECB), chế độ phản hồi mã (CFB), chế độ liên kết khối mã (CBC) và
chế độ phản hồi đầu ra (OFB). 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 x1,x2,. . .( 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ã y1y2 ... theo quy tắc yi = eK(yi-1⊕xi) i ≥ 1. Việc sử
dụng chế độ CBC được mô tả trên hình 3.4.
Hình 3.4. Chế độ CBC.
http://www.ebook.edu.vn 68
x1 x2
IV=y0 + +
...
Mã hoá
eK eK
Encrypt
y1 y2
y1 y2
Giải mã
dK dK
Decrypt
IV=y0 + + ...
x1 x2
Trong các chế độ OFB và CFB dòng khoá được tạo ra sẽ được cộng mod 2
với bản rõ (tức là nó hoạt động như một hệ mã dòng, xem phần 1.1.7). OFB
thực sự là một hệ mã dòng đồng bộ: dòng khoá được tạo bởi việc mã lặp véc
tơ khởi tạo 64 bít (véc tơ IV). Ta xác định z0 =IV và rồi tính dòng khoá z1z2 . .
. theo quy tắc zi = eK(zi-1), i≥1. Dãy bản rõ x1x2 . . . sau đó sẽ được mã hoá
bằng cách tính yi = xi ⊕ zi,i ≥1.
Trong chế độ CFB, ta bắt đầu với y0 = IV (là một véc tơ khởi tạo 64
bít) và tạo phần tử zi của dòng khoá bằng cách mã hoá khối bản mã trước đó.
Tức zi = eK(yi-1), i ≥1. Cũng như trong chế độ OFB: yi = xi ⊕ zi,i ≥1. Việc sử
dụng CFB được mô tả trên hình 3.5 (chú ý rằng hàm mã DES eK được dùng
cho cả phép mã và phép giải mã ở các chế độ CFB và OFB).
Hình 3.5. Chế độ CFB
http://www.ebook.edu.vn 69
x1 x2
...
IV=y0 eK + eK +
Mã hoá
Encrypt y2
y1
y1 y2
...
IV=y0 eK + eK +
Giải mã
Decrypt x2
x1
Cũng còn một số biến tấu của OFB và CFB được gọi là các chế độ phản hồi K
bít (1 < K < 64 ). ở đây ta đã mô tả các chế độ phản hồi 64 bít. Các chế độ
phản hồi 1 bít và 8 bít thường được dùng trong thực tế cho phép mã hoá đồng
thời 1 bit (hoặc byte) số liệu.
Bốn chế độ công tác có những ưu, nhược điểm khác nhau. ở chế độ
ECB và OFB, sự thay đổi của một khối bản rõ xi 64 bít sẽ làm thay đổi khối
bản mã yi tương ứng, nhưng các khối bản mã khác không bị ảnh hưởng.
http://www.ebook.edu.vn 70
Trong một số tình huống đây là một tính chất đáng mong muốn. Ví dụ, chế độ
OFB thường được dùng để mã khi truyền vệ tinh.
Mặt khác ở các chế độ CBC và CFB, nếu một khối bản rõ xi bị thay đổi
thì yi và tất cả các khối bản mã tiếp theo sẽ bi ảnh hưởng. Như vậy các chế độ
CBC và CFB có thể được sử dụng rất hiệu quả cho mục đích xác thực. Đặc
biệt hơn, các chế độ này có thể được dùng để tạo mã xác thực bản tin ( MAC -
message authentication code). MAC được gắn thêm vào các khối bản rõ để
thuyết phục Bob tin rằng, dãy bản rõ đó thực sự là của Alice mà không bị
Oscar giả mạo. Như vậy MAC đảm bảo tính toàn vẹn (hay tính xác thực) của
một bản tin ( nhưng tất nhiên là MAC không đảm bảo độ mật).
Ta sẽ mô tả cáchb sử dụng chế độ BCB để tạo ra một MAC. Ta bắt đầu
bằng véc tơ khởi tạ IV chứa toàn số 0. Sau đó dùng chế đô CBC để tạo các
khối bản mã y1,. . . ,yn theo khoá K. Cuối cùng ta xác định MAC là yn. Alice
sẽ phát đi dãy các khối bản rõ x1,x2,. . . ,xn cùng với MAC. Khi Bob thu được
x1. . .xn anh ta sẽ khôi phục lại y1. . .yn bằng khoá K bí mật và xác minh xem
liệu yn có giống với MAC mà mình đã thu được hay không.
Nhận thấy Oscar không thể tạo ra một MAC hợp lệ do anh ta không
biết khoá K mà Alice và Bob đang dùng. Hơn nữa Oscar thu chặn được dãy
khối bản rõ x1. . .xn và thay đổi ít nhiều nội dung thì thì chắc chắn là Oscar
không thể thay đổi MAC để được Bob chấp nhận.
Thông thường ta muốn kết hợp cả tính xác thực lẫn độ bảo mật. Điều
đó có thể thực hiện như sau: Trước tiên Alice dùng khoá K1 để tạo MAC cho
x1. . . xn . Sau đó Alice xác định xn+1 là MAC rồi mã hoá dãy x1. . .xn+1 bằng
khoá thứ hai K2 để tạo ra bản mã y1. . .yn+1 . Khi Bob thu được y1. . .yn+1 ,
trước tiên Bob sẽ giải mã ( bằng K2) và kiểm tra xem xn+1 có phải là MAC đối
với dãy x1. . .xn dùng K1 hay không.
Ngược lại, Alice có thể dùng K1 để mã hoá x1. . .xn và tạo ra
được y1...yn , sau đó dùng K2 để tạo MAC yn+1 đối với dãy y1. . .yn. Bob sẽ
dùng K2 để xác minh MAC và dung K1 để giải mã y1. . .yn
http://www.ebook.edu.vn 71
Chương 4: Mật mã công khai
4.1. Giới thiệu về hệ mật mã khóa công khai.
4.1.1. Giới thiệu.
Trong mô hình mật mã cổ điển mà cho tới nay vẫn còn đang được
nghiên cứu Alice (người gửi) và Bob (người nhận) bằng cách chọn một
khoá bí mật K. Sau đó Alice dùng khoá K để mã hoá theo luật eK và Bod
dùng khoá K đó để giải mã theo luật giải dK . Trong hệ mật này, dK hoặc
giống như eK hoặc dễ dàng nhận được từ nó vì quá trình giải mã hoàn toàn
tương tự như quá trình mã, nhưng thủ tục khoá thì ngược lại. Nhược điểm
lớn của hệ mật này là nếu ta để lộ eK thì làm cho hệ thống mất an toàn,
chính vì vậy chúng ta phải tạo cho các hệ mật này một kênh an toàn mà
kinh phí để tạo một kênh an toàn không phải là rẻ.
Ý tưởng xây dựng một hệ mật khoá công khai là tìm một hệ mật
không có khả năng tính toán để xác định dK nếu biết được eK. Nếu thực
hiện được như vậy thì quy tắc mã eK có thể được công khai bằng cách công
bố nó trong danh bạ, và khi Alice (người gửi) hoặc bất cứ một ai đó muốn
gửi một bản tin cho Bob (người nhận) thì người đó không phải thông tin
trước với Bob (người nhận) về khoá mật, mà người gửi sẽ mã hoá bản tin
bằng cách dùng luật mã công khai eK. Khi bản tin này được chuyển cho
Bob (người nhận) thì chỉ có duy nhất Bob mới có thể giải được bản tin này
bằng cách sử dụng luật giải mã bí mật dK.
Ý tưởng về hệ mật khoá công khai đã được Diffie và Heliman đưa ra
vào năm 1976. Còn việc thực hiện hệ mật khoá công khai thì lại được
Rivest. Shamin và Adieman đưa ra đầu tiên vào năm 1977. Họ đã tạo nên
hệ mật RSA nổi tiếng. Kể từ đó đã có một số hệ mật được công bố, độ mật
của từng hệ dựa trên các bài toán tính toán khác nhau. Trong đó quan trọng
nhất là các hệ mật sau:
• Hệ mật RSA
Độ bảo mật của hệ RSA dựa trên độ khó của việc phân tích ra thừa số
nguyên tố các số nguyên tố lớn.
http://www.ebook.edu.vn 72
• Hệ mật xếp balô Merkle – Hellman.
Hệ này và các hệ có liên quan dựa trên tính khó giải của bài toán tổng
các tập con.
• Hệ mật McEliece
Hệ mật nanỳ dựa trên lý thuyết mã đại số và vẫn được coi là an toàn.
Hệ mật McEliece dựa trên bài toán giải mã cho các mã tuyến tính.
• Hệ mật ElGamal
Hệ ElGamal dựa trên tính khó giải của bài toán Logarit rời rạc trên
các trường hữu hạn.
• Hệ mật Chor – Rivest
Hệ mật Chor – Rivest cũng được xem như một loại hệ mật xếp balô.
Tuy nhiên hệ mật này vẫn còn được coi là hệ mật an toàn.
• Hệ mật trên các đường cong Elliptic.
Các hệ này là biến tướng của hệ mật khác, chúng làm việc trên các
đường cong Elliptic chứ không phải trên các trường hữu hạn. Hệ mật này
đảm bảo độ mật vơí khoá số nhỏ hơn các hệ mật khoá công khai khác.
Một chú ý quan trọng là một hệ mật khoá công khai không bao giờ có
thể bảo đảm được độ mật tuyệt đối (an toàn vô điền kiện). Sở dĩ vậy vì đối
phương nghiên cứu một bản mã C có thể mã lần lượt các bản rõ có thể
bằng luật mã công khai eK cho tới khi anh ta tìm được một bản rõ duy nhất
P bảo đảm C = eK(P). Bản rõ P này chính là kết quả giải mã của C. Bởi vậy
ta chỉ nghiên cứu độ mật về mặt tính toán của hệ này.
Một chú ý quan trọng và có ý ích khi nghiên cứu nữa là khái niệm về
hàm cửa sập một chiều. Ta định nghĩa khái niệm này một cách không hình
thức.
Định nghĩa: Hàm f: X →Y đực gọi là hàm một chiều nếu tính y=f(x)
với mọi x ∈ X là dễ nhưng việc tìm x khi biết y lại là vấn đề khó.
Thực ra phát biểu trên chỉ là định nghĩa phi hình thức (do thuật ngữ
“khó” được dùng đến là không định lượng và thậm chí sau này chúng ta đã
biết là ngay cả khi đã định lượng bằng sự không tồn tại thuật toán giải bài
http://www.ebook.edu.vn 73
toán ngược trong phạm vi đa thức thì khái niệm “khó” nêu trên có tồn tại hay
không cũng chưa được ai khẳng định rõ ràng) và điều đáng tiếc hơn nữa là tất
cả các hàm ứng cử viên cho khái niệm này cho đến nay chỉ mới “được coi là
một chiều.
Chúng ta dễ dàng thống nhất được với nhau là chỉ riêng hàm một chiều
là không đủ để xây dựng thành một luật mã theo kiểu công khai hàm mã hoá
do vì chính bản thân chủ nhân của bức điện mật cũng gặp phải hoàn cảnh
tương tự như người khác. Như vậy để có thể giải mã một cách hữu hiệu thì
người giải mã phải có một “hiểu biết tuyệt mật” nào đó về khoá giải (một hiểu
biết theo kiểu nếu biết nó thì cách giải dễ dàng) “hiểu biết tuyệt mật” này
được gọi là cửa sập. Hàm một chiều như trên được gọi là hàm một chiều có
cửa sập.
Dĩ nhiên dù không biết cửa sập thì người thám mã vẫn có thể sử dụng
hiểu biết về hàm f để lần lượt tính tất cả các giá trị f(x) cho mọi bản rõ x cho
tới khi tìm được bản rõ thoả mãn y=f(x). Bản rõ tìm được trên chính là kết
quả giải mã của y. Ngoài ra người thám mã còn có thể sử dụng nhiều phương
pháp tấn công khác nhằm vào đặc thù riêng của từng hàm f để tìm ra bản rõ
trong các trường hợp riêng rẽ khác chứ không nhất thiết phải giải bài toán
ngược.
Tóm lại đọc an toàn của hệ mật khoá công khai không chỉ phụ thuộc vào
độ khó của việc giải bài toán ngược mà tính bền của sự an toàn này còn phụ
thuộc vào các phương pháp tấn công của các thám mã, vả lại như đã trình bày
ở trên thì toàn bộ các hê khoá mật công khai đang được sử dụng đều chưa đực
sự khẳng định về tính “khó” mà ngay cả khi đã có sự đảm bảo này thì có sự
tiến bộ không ngừng của công nghệ tính toán tghì hiển nhiên nhiều vấn đề
chưa thể chứp nhận được trong hiện tại sẽ được chấp nhận trong tương lai.
Thực tế không chỉ đối với các hệ mât khoá công khai do vậy quan niêm mới
về tính an toàn tương đối mà với nó đã nẩy sinh ra các hệ mật khoá công khai
đồng thời cũng đặt cho chúng ta nhiều bài toán nghiêm túc phải giải quyết khi
sử dụng hệ mật này. Chương này giới thiệu cụ thể một số hệ mật công khai
http://www.ebook.edu.vn 74