Tài liệu Kỹ thuật lập trình - Chương 7: Mật mã khóa đối xứng

Chia sẻ: | Ngày: | Loại File: DOC | Số trang:83

Thêm vào BST

Báo xấu

112
lượt xem 14
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 7: Mật mã khóa đối xứng, giới thiệu đến người học về lý thuyết cơ bản của Shannon, định nghĩa mật mã đối xứng, các lệnh dùng để xây dựng thuật toán mật mã đối xứng, một số sơ đồ dùng để thiết kế hệ mật.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tài liệu Kỹ thuật lập trình - Chương 7: Mật mã khóa đối xứng

Chương 7 MẬT MÃ KHÓA ĐỐI XỨNG 7.1 Lý thuyết cơ bản của Shannon Nhiều người cho rằng kỷ nguyên của mật mã học hiện đại được bắt đầu với Claude Shannon, người được coi là cha đẻ của mật mã toán học. Năm 1949 ông đã công bố bài Lý thuyết về truyền thông trong các hệ thống bảo mật (Communication Theory of Secrecy Systems) trên tập san Bell System Technical Journal - Tập san kỹ thuật của hệ thống Bell - và một thời gian ngắn sau đó, trong cuốn Mathematical Theory of Communication - Lý thuyết toán học trong truyền thông - cùng với tác giả Warren Weaver. Những công trình này, cùng với những công trình nghiên cứu khác của ông về lý thuyết về tin học và truyền thông (information and communication theory), đã thiết lập một nền tảng lý thuyết cơ bản cho mật mã học và thám mã học. Với ảnh hưởng đó, mật mã học hầu như bị thâu tóm bởi các cơ quan truyền thông mật của chính phủ, chẳng hạn như NSA, và biến mất khỏi tầm hiểu biết của công chúng. Rất ít các công trình được tiếp tục công bố, cho đến thời kỳ giữa thập niên 1970, khi mọi sự được thay đổi. Claude Shannon xem xét mô hình 7.1, ở đây nguồn bản tin sinh ra bản rõ X, nguồn khóa tạo ra khóa K, khóa K được truyền qua kênh mật từ nơi truyền đến nơi nhận. Quá trình mã hóa biến đổi bản rõ X nhờ khóa thành bản mã Y: FK ( X ) . Quá trình giải mã, biến đổi bản mã nhận được Y thành bản rõ X cũng nhờ khóa K: X = FK−1 (Y ) . Tội phạm (hay thám mã) sẽ tìm cách nhận được bản rõ và khóa trên cơ sỡ bản mã. Claude Shannon xem xét các câu hỏi lý thuyết và thực hành mật. Để nhận được lý thuyết mật Shannon hình thành các câu hỏi sau: 1. Hệ thống ổn định ở mức độ nào, nếu như thám mã không giới hạn thời gian và có tất cả các thiết bị cần thiết đối với việc phân tích bản mã? 2. Bản mã liệu có một nghiệm duy nhất hay không? 3. Với lượng thông tin bản mã bao nhiêu mà thám mã cần thu nhặt để nghiệm trở nên duy nhất?
Để trả lời câu hỏi của Shannon chúng ta đưa vào định nghĩa “tuyệt mật” với s ự hổ trợ các điều kiện sau: Bản mã thu được không đêm đến cho thám mã bất kỳ thông tin nào. Theo định lý Bayes PY ( X ) = P ( X ) PX (Y ) / P (Y ) K Nguồn khóa K X X Nguồn bản Mã hóa Y Giải mã Nhận bản tin tin Tội phạm K’ X’ Hình 7.1. Mô hình truyền tin Shannon Với P(X) là xác suất xuất hiện bản tin X; PX (Y ) xác suất điều kiện, xuất hiện bản mã Y với điều kiện bản tin X đã được chọn, có nghĩa là tổng xác suất của tất cả các khóa, mà các khóa này chuyển bản tin X tương ứng với bản mã Y; P(Y)-xác suất nhận được bản mã Y; PY ( X ) là xác suất nhận được bản rõ X với điều kiện nhặt được bản mã Y. Để “tuyệt mật” thì giá trị của PY ( X ) và P( X ) cần phải bằng nhau với tất cả giá trị của X và Y. Để chống lại phương pháp phân tích thống kê bản mã (đây là một cách thám mã) Shannon đề ra hai phương pháp: khuyết tán và pha trộn. Định nghĩa Entropy thông tin. Entropy thông tin mô tả mức độ hỗn loạn trong một tín hiệu lấy từ một sự kiện ngẫu nhiên. Nói cách khác, entropy cũng chỉ ra có bao nhiêu thông tin trong tín hiệu, với thông tin là các phần không hỗn loạn ngẫu nhiên của tín hiệu. Lý thuyết về thông tin sẽ trình bày đầy đủ hơn về Entropy, ở đây chúng tôi chỉ đ ưa ra cái cơ bản. Claude E. Shannon đã xây dựng định nghĩa về entropy để thoả mãn các giả định sau: 1. Entropy phải tỷ lệ thuận liên tục với các xác suất xuất hiện của các phần tử ngẫu nhiên trong tín hiệu. Thay đổi nhỏ trong xác suất phải dẫn đến thay đổi nhỏ trong entropy.
2. Nếu các phần tử ngẫu nhiên đều có xác suất xuất hiện bằng nhau, việc tăng số lượng phần tử ngẫu nhiên phải làm tăng entropy. 3. Có thể tạo các chuỗi tín hiệu theo nhiều bước, và entropy tổng cộng phải bằng tổng có trọng số của entropy của từng bước. Shannon cũng chỉ ra rằng bất cứ định nghĩa nào của entropy, cho một tín hiệu có thể nhận các giá trị rời rạc, thoả mãn các giả định của ông thì đều có dạng: n − K ∑ p (i ) log p (i ) i =1 Với K là một hằng số, chỉ phụ thuộc vào đơn vị đo; n là tổng số các giá trị có thể nhận của tín hiệu; i là giá trị rời rạc thứ i; p(i) là xác suất xuất hiện của giá trị i; Nếu một sự kiện ngẫu nhiên rời rạc x, có thể nhận các giá trị là 1..n, thì entropy của nó là: n H ( x) = −∑ p (i ) log 2 p (i ) , i =1 với p(i) là xác suất xảy ra của giá trị i. Entropy thông tin trong trường hợp phần tử tín hiệu ngẫu nhiên rời rạc còn được gọi là entropy Shannon. 7.2 Định nghĩa mật mã đối xứng Định nghĩa. Mật mã đối xứng là hệ mật mà quá trình mã hóa và quá trình giải mã dùng chung một khóa mật, và việc bảo mật bản tin phụ thuộc vào quá trình l ưu khóa mật. Sơ đồ tổng quát của hệ mã đối xứng được miêu tả ở hình 7.2. Bản tin nguồn Bản tin giải (X) mã X Quá trình mã Bản mã Y Quá trình giải hóa truyền qua mã kênh (X=) khóa Khóa mật (K) khóa Tạo ra khóa mật
Hình 7.2. Sơ đồ mật mã đối xứng ở đây bản tin nguồn X là thông tin cần mã để bảo mật, trước khi chuyển đến nơi nhận nó phải được mã hóa bằng hàm mã hóa E, hàm mã hóa E là tổng hợp các phép biến đổi với sự tham gia của khóa mật K; qua biến đổi của hàm E chúng ta thu được bản mã Y; bản mã Y truyền qua kênh thông tin đến nơi người cần nhận, ở nơi nhận với sự giúp đở của quá trình giải mã và khóa mật K, sẽ giải bản mã Y thành bản tin X ban đầu. Chú ý, nếu như khóa K không đúng, hoặc bản mã Y bị biến đổi trong quá trình truyền thì quá trình giải mã không thể thu được bản tin ban đầu X. Như đã nói, mật mã đối xứng được chia ra làm hai phần, mật mã khối và mật mã dòng. Chúng ta xem định nghĩa về chúng. Định nghĩa mật mã khối. Mã khối là tổ hợp lệnh toán học (hoán vị, thay thế,…) biến đổi dãy N bit x = ( x1 , x2 ,..., xN ) ∈ F (2) N thành một dãy N bit y = ( y1 , y2 ,..., y N ) ∈ F (2) N với sự tham gia của khóa mật k từ không gian khóa K, có thể viết dưới dạng y = F ( x, k ) , ở đây F là hàm mã hóa hay giải mã. Định nghĩa mã dòng. Là một hệ mã đối xứng, trong đó từng ký tự của bản rõ được biến đổi thành ký tự của bản mã phụ thuộc không chỉ vào khóa sử dụng mà còn vào v ị trí của nó trong bản rõ. Mã khối thì chia bản rõ ra các khối bằng nhau rồi thực hiện mã, nên sẽ có một số khối giống nhau mã cùng một khóa, ở mã dòng thì không như vậy. 7.3 Các lệnh dùng để xây dựng thuật toán mật mã đối xứng Hầu như tất cả các hệ mật đối xứng đảm bảo bảo mật thông tin thường được xây dựng trên cơ sở các lệnh cơ sở sau: 7.3.1 Lệnh hoán đổi Định nghĩa. Đây là phương pháp biến đổi mật mã đơn giản, là một phép hoán đổi các vị trí của các kí tự trong bản rõ theo một quy luật nào đó. Chúng ta có thể biểu diễn chúng bằng toán học như sau: Hoán đổi π của tập hữu hạn Ω , với Ω gồm n phần tử, là một đơn ánh từ tập Ω vào tập Ω , Ω = {1,2,..., n} , lệnh hoán đổi π có dạng sau:  α α 2 ...α n  π = 1  δ δ ... δ  ,  1 2 n  ở đây hang đầu tiên là vị trí ký tự của bản rõ, hang thứ 2 là các vị trí mà ký t ự ban đ ầu cần hoán đổi tương ứng, δ i ,α i ∈ {1,2,..., n} (δ i ≠ δ j ,α i ≠ α j khi i ≠ j ), tức là vị trí thứ α1 đổi
cho vị trí thứ δ1 , vị trí thứ α 2 đổi cho vị trí thứ δ 2 tương tự như thế. Giá trị n gọi là chiều dài hoán đổi. Ví dụ: 1 2 3 4 π = 2 3 .  1 4  Tập hợp tất cả các lệnh hoán đổi π ký hiệu là π n , và rõ ràng rằng π n = n! . Có nhiều cách biểu diễn lệnh hoán vị. Ví dụ như từ ví dụ trên ta có các cách biểu diễn sau: π = (1,2,3)(4) = (2,3,1)(4) . Chúng ta thấy lệnh hoán đổi như một hàm, tham số của nó là số nguyên, hàm này có thể ký hiệu π (α i ) ,với π (α i ) = δ i , ∀i ∈ {1,2,..., n} . Tiêu chuẩn xây dựng nên lệnh hoán đổi: Chúng ta phải xây dựng lệnh hoán đổi sao cho đạt được độ phát tán tốt, nhằm tăng hiệu ứng thác lũ. 7.3.2 Lệnh thay thế. Định nghĩa.Trong mật mã, lệnh thay thế có thể hiểu là một qúa trình thay một số phần tử này bằng một số phần tử khác, hay nói cách khác là thay thế một ký t ự hay một nhóm ký tự của bản tin bằng một ký tự hay một nhóm ký tự khác. Theo toán học thì chúng ta có thể định nghĩa như sau: Lệnh thay thế S là một ánh xạ s: Ω  Ω' , với Ω,Ω' là tập hữu hạn và với ∀ω ∈ Ω , tồn tại duy nhất một phần tử ω '∈ Ω': ω ' = S (ω ) . Đối với Ω = {ω1 , ω2 ,..., ωn } lệnh hoán đổi có dạng:  ω ω2 ... ωn  S =  1' ω ω '  ' ,  1 2 ... ωn   Với ω1' , ω2 ,..., ωn ∈ Ω' . Các giá trị ω1' , ω2 ,..., ωn không bắt buộc là khác nhau. ' ' ' ' Ví dụ lệnh thay thế 2 bit này thành 2 bít khác: 1 2 3 4 S = 3 4   1 2  Tuy nhiên một số phép thay thế có thể biểu diễn ở dạng khác như đồ thị, dùng hàm số…vv.
Tiêu chí để xây dựng nên lệnh thay thế: Khi sử dụng lệnh thay thế phải có được các tính chất: Bậc đại số cao, có độ phi tuyến tính lớn, tạo ra tính tính pha tr ộn bít và phát tán bít tốt. 7.3.3 Mạng hoán vị thay thế Kết hợp lệnh hoán vị và lệnh thay thế, có thể xây dựng nên mạng hoán vị thay th ế. Đây là cấu trúc xen kẻ nhiều lớp mỗi lớp kết hợp phép thay thế và phép hoán vị. Với mạng thay thế hoán vị, có thể tạo cho thuật toán có độ phân tán vào xáo trộn rất tố. Chúng ta tìm ví dụ mạng hoán vị thay thế được miêu tả ở hình 7.3 , đầu vào là 32 bít qua mạng chuyển vị 4 lớp, mỗi lớp gồm 8 bảng thay thế 4 bít cho 4 bít, các bảng này có thể khác nhau, sau phép thế là phép hoán vị. S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 S_4/4 Hình 7.3.Mạng hoán vị thay thế S_BOX 32/22 Để tạo ra mạng hoán vị, chúng ta cần tính toán đến hiệu quả thác lũ để chọn ra cách xây dựng như ý. 7.3.4 Lệnh Gamma dành cho mã dòng Nguyên lý cơ bản của mã dòng là tạo ra chuỗi khóa, cũng thường hay gọi là tạo ra khóa dòng hay khóa dịch hay gamma được cho bằng chuỗi bít k1 , k2 ,..., ki … Chuỗi bít này sẽ cộng với chuỗi bít bản rõ p1 , p2 ,..., pi ,... để nhận được chuỗi bản mã: ci = pi ⊕ ki Ở bên nhận bản mã sẽ cộng bản mã với cùng chuỗi khóa đó để khôi phục lại bản mã ban đầu: ci ⊕ ki = p i ⊕ ki ⊕ ki = pi Sự vững chắc của hệ mã phụ thuộc hoàn toàn vào cấu trúc bên trong sinh ra chuỗi khóa. Nếu việc sinh ra không tạo ra chuỗi với chu kỳ lớn thì hệ sẽ không vững chắc.
Có thể biểu diễn bằng sơ đồ sau quá trình mã và giải mã tương ứng ở hình 7.4 và 7.5. Bản rõ pi gamma Bản mã ci ki Hình 7.4. Quá trình mã hóa gamma Bản mã ci gamma Bản rõ pi ki Hình 7.5. Quá trình giải mã gamma Độ an toàn khi dùng lệnh gamma. Claude Shannon đã chứng minh rằng mã bằng lệnh gamma là tuyệt đối an toàn. Chứng minh của Shannon: Giả sử X và Y là giá trị ngẫu nhiên rời rạc. X là giá trị ngẫu nhiên đối với bản rõ, Y là giá trị ngẫu nhiên đối với gamma, khi đó luật phân bố X sẽ là X 0 1 Pi p 1-p Luật phân bố Y là Y 0 1 Pi 1/2 1/2 ở đây Pi là xác suất gặp X, hoặc Y. Ở đây chúng thấy trong số gamma thì xác suất gặp 0 và 1 là như nhau. Z là giá trị ngẫu nhiên rời rạc cho bản mã. Từ hình chúng ta thấy rằng Z=X+Y (mod 2). Chúng ta đi tính xác suất gặp 0 và 1 trong định luật phân bố Z: Chúng ta dùng: 1) P ( A + B) = P ( A) + P ( B ) , nếu như A và B không giao nhau 2) P ( A * B ) = P ( A) * P ( B ) , nếu như A và B độc lập Chúng ta có:
P(Z=0) = P(X=0,Y=0)+P(X=1,Y=1) = = P(X=0)*P(Y=0)+P(X=1)*P(Y=1) =p*1/2+(1-p)*1/2 = 1/2 . Nên P(Z=1) = 1-P(Z=0) = ½. Điều này chúng ta thấy luật phân bố Z là đối xứng, có nghĩa là chúng ta nh ận đ ược gamma hoặc là nhiễu (tức là Z không bao gồm một thông tin nào từ X) nên mã tuyệt đối an toàn. Cách chọn gamma: 1) Đối với từng trường hợp dùng gamma khác nhau; 2) Để tạo ra gamma dùng phương pháp tạo số ngẫu nhiên; 3) Gamma phải dài tương ứng với bản mã; 4) Lựa chọn gamma một cách thông minh để thám mã khó mò. Mã dòng rất hữu ích đối với mã dòng dữ liệu liên tục, ví dụ trong mạng truy ền t ải dữ liệu. 7.4 Một số sơ đồ dùng để thiết kế hệ mật 7.4.1 Mạng Feistel và các kiểu biến dạng của nó Một trong các phương pháp thông dụng tạo ra mã khối là dựa trên cấu trúc có tên là Feistel được Horst Feisel tạo ra. Cấu trúc một vòng của mạng Feistel biểu diễn hình 7.6. R R K F(R,K) L’=R R’=F(R,K) Hình 7.6. Sơ đồ 1 vòng Feistel
Trong sơ đồ này thì hàm F là hàm cơ bản để xây nên khối mạng Feistel, nó luôn được chọn là hàm phi tuyến tính và trong tất cả các trường hợp nó không có hàm ngược. Hàm F có hai thám số, một là nữa khối bên phải và tham số còn lại là khóa. Giả sử X là khối bản tin, biểu diễn dưới dạng hai khối con có độ dài như nhau X = { L, R} . Lúc này một vòng của mạng có thể biều diễn như sau, giả sử sau i vòng ta thu được X i = { Li , Ri } , thì vòng thứ i+1 sẽ là: X i +1 = { Ri , F ( Ri , K i ) ⊕ Li } . Mã khối xây dựng trên cơ sở mạng Feistel có r vòng như thế, số vòng này xác đ ịnh độ an toàn của hệ mã, và vòng cuối cùng không thực hiện hoán đổi giữa khối con bên phải và khối con bên trái, tức là X r = { F ( Rr −1 , K r −1 ) ⊕ Lr −1 , Rr −1} , Việc làm này không ảnh hưởng đến độ an toàn của thuật toán mã, mà nó sẽ làm cho quá trình mã hóa và giải mã là hai quá trình thuận nghịch nhau, tức là sau khi mã chúng ta thu được X r , để giải mã, chúng ta dung đúng thuật toán mã hóa, tham số của thuật toán bây giờ là khối dữ liệu là X r và thực hiện r vòng với đảo thứ tự các khóa con ngược với quá trình mã hóa, chúng ta thu được bản tin ban đầu. Ưu và nhược điểm khi thực hiện mã khối trên cơ sở mạng Feistel. Ưu điểm. 1. Quá trình mã hóa và giải mã trùng nhau, chỉ khác nhau ở thứ tự khóa con, điều này sẽ tiết kiệm được nữa tài nguyên khi thực hiện thuật toán trên phần cứng. 2. Hàm F có thể chọn với độ khó bất kỳ, vì không phải tìm hàm nghịch. Nhược điểm. 1. Vì mỗi vòng mã chỉ thực hiện biến đổi nữa khối dữ liệu, nên cần số vong mã hóa lớn để đảm bảo độ an toàn của hệ mật, điều này làm giảm đáng kể tốc độ mã. 2. Ngoài ra xây dựng trên cơ sở mạng Feistel tồn tại lớp khóa tương đương, nên làm không gian khóa giảm đi một nữa. Ngoài ra chúng ta thấy nếu xây dựng một mã khối có kích cở lớn thì dùng mạng Feistel với hai nhánh ở trên không thuận lợi, lúc này chúng ta dùng mạng Feistel 4 nhánh với các kiểu của nó biểu diễn ở hình 7.7, 7.8 và 7.9.
X2 X3 X4 K F Hình 7.7. Cấu trúc mở rộng mạng Feistel loại 2 X 2 X3 X 4 K F Hình 7.8. Cấu trúc mở rộng mạng Feistel loại 3 X 2 X3 X 4 K F
Hình 7.9. Cấu trúc mở rộng mạng Feistel loại 2 7.4.2 Sơ đồ cấu trúc cộng nhân Cấu trúc cộng nhân có thể xem như là một trong các kiểu hạt nhân cấu tạo nên các hàm vòng, trong đó sử dụng các phép toán số học đơn giản và được nghiên cứu cẩn thận. Cấu trúc này được đề xuất bởi J.L.Massey và X.Lai. Cấu trúc được cho như hình vẻ 7.10. X1 X2 K1 K2 Y1 Y2 Hình 7.10. Sơ đồ cấu trúc cộng nhân ở đây đây ta dùng hai phép toán số học là cộng và nhân theo modulo trong nhóm tương ứng và X 1 , X 2 là các véctơ đầu vào, K1 , K 2 là các khóa, Y1 ,Y2 là véc tơ đầu ra. Ưu điểm của cấu trúc. Khi thiết kế mã khối theo cấu trúc cộng nhân, thì mã khối có tính khuyếch tán tốt. 7.5 Các bước cơ bản để thiết kế một hệ mật Khi thiết kế mật mã thì vấn đề đảm bảo độ vững chắc của thuật toán là một vấn đề quan trọng nhất.Và đây cũng là vấn đề phức tạp nhất. Đánh giá độ vững chắc c ủa thuật toán là một trong các công đoạn lâu nhất và khó nhất. Vì chưa có một lý thuy ết hoàn chỉnh để đánh giá độ an toàn của mã khối nên phương pháp sáng tạo là một cách quan trọng nhất để đánh giá. Thế nhưng có thể đưa ra một số yêu cầu chung đ ể xây dựng nên một thuật toán mật mã. Nếu như mật mã thỏa mãn nhưng yêu cầu đó thì nói rằng thuật toán an toàn. Cần chú ý rằng vấn đề đảm bảo độ an toàn cao chưa phải là một mục đích duy nhất, bởi khi xây dựng thuật toán mật mã đảm cần bảo đ ược tốc độ mã hóa và vi ệc
thực hiện chúng trên phần cứng và phần mền có phức tạp hay không cũng là yêu cầu không kém quan trọng. Phụ thuộc vào yêu cầu của ứng dụng mà chọn sơ đồ mật mã và các bước đánh giá cho phù hợp tức là tầm quan trọng của ứng dụng quy ết đ ịnh cho chúng ta chọn thuật toán tương ứng với tham số mật mã (như công suất, độ phức tạp thực hiện,..vv). Quá trình xây dựng thuật toán mã khối được tiến hành theo các bước sau: 1. Nghiên cứu lĩnh vực ứng dụng . Ở bước này thực hiện chọn lựa kiểu hệ mật và hình thành các yêu cầu ứng với tham số cơ bản của hệ mật. Mã dòng cho phép nhận được tốc độ mã hóa cao nhất và đảm bảo khả năng độc lập biến đổi từng bit và byte, và cho phép giảm khả năng lỗi khi truyền bản mật mã qua kênh. Thế nhưng đối với mã dòng tỏ ra khó khoăn khi truy cập bất kỳ đến dữ liệu mã hóa. Khuyết điểm này có thể tránh nếu sử dụng phần tử khóa gamma phụ thuộc vào khóa mật và số thứ tự của phần tử đó. Trong các mật mã thế này có dấu hiệu của mật mã khối. Hiện nay các mật mã khối được sử dụng rộng rãi nhất. Mã khối đảm bảo được tính an toàn cao ở chế độ độc lập mã hóa từng khối, và cho phép truy cập bất kỳ đến dữ liệu mã hóa. Trong số các thiết bị bảo mật thông tin từ truy cập trai phép sử dụng các thuật toán mật mã file với tốc độ cao ở chế độ on-line với sự kết hợp các kiểu hệ mật, tức là mã dòng và mã khối. Ở mã dòng thực hiện biến đổi độc lập từng byte, nhưng nó thực hiện mã phụ thuộc vào thứ tự của byte trong từng file và vào các dấu hiệu đặc biệt của file. Căn cứ vào lĩnh vực ứng dụng mà xác định các giá trị của các phương án thực hiện (chương trình, máy), độ phức tạp khi thực hiện trên máy và tốc độ mã. 2. Lựa chọn chiều dài khóa mật. Cần chú rằng, bất kỳ một hệ mật với một chiều dài khóa hữu hạn luôn luôn tồn tại khả năng tìm kiếm khóa mật bằng phương pháp véc cạn khóa. Hiện nay đối với trường hợp tổng quát thì chiều dài khóa được cho là an toàn nếu không nhỏ hơn 128 bit, nhưng trong một số trường hợp riêng có thể dùng khóa với chiều dài 64 bit, có khi 56 bit, nếu như thông tin cần bảo vệ không quá quan trọng. 3. Lựa chọn cách miêu tả khóa. Chúng ta có những cách miêu ta tả khóa khác nhau, phần này xem cụ thể ở phần các cách miêu tả khóa.
4. Lựa chọn các phần tử mật mã cơ sở và cách xử lý hệ mật. Để hoàn thành bước này cần am hiểu các phương pháp cơ bản để xây dựng mật mã, kiểu khối các hệ mật, hiểu được từng lệnh sử dụng trong hệ mật, và cũng cần đánh giá về chi phí khi thực hiện trên phần cứng cũng như thời gian trể của nó. 5. Đánh giá tài nguyên cần thiết để thực hiện thuật toán mật mã. Xem các khả năng thực hiện trên phần cứng và phần mềm. Thực hiện các thí nghiệm cũng như mô hình hóa chương trình cho hệ mật. 6. Đánh giá về cống suất của mật mã. Xác định tốc độ mã đối với các phương án thực hiện khác nhau trên phần cứng và phần mềm. Nếu như trên bước 5 và 6 kết quả đánh giá nhận được không thỏa mãn giá trị mục đích của bước 1, thì quay lại bước 4. 7. Xem độ an toàn của hệ mật đối với các kiểu tấn công mật mã khác nhau. Xem xét các cách thám mã cơ bản, cũng như các khả năng tấn công khác với việc sử dụng các ứng dụng đặc biệt. Dựa trên các cách tấn công đó, xác định được độ khó tấn công và từ đó đánh giá được độ an toàn của hệ mật. 8. Biến đổi thuật toán. Cân nhắc kết qủa nhận được trên bước 7, có thể biến đổi thuật toán, chọn lựa các phần tử tối ưu cho hệ mật nhằm nâng cao độ khó cho cách tấn công hệ mật hiệu quả nhất. Nếu cần có thể lặp lại một số lần ở bước này với các các thay đổi khác nhau nhằm đạt được mục đích. 9. Thực hiện phân tích chi tiết biến đổi hệ mật . Nếu như phân tích chi tiết vạch ra sự tồn tại điểm yếu của hệ mật trong sơ đồ biến đổi thì lặp lại bước 8, nếu cần có thể lặp lại cả bước 4. 10. Thực hiện kiểm tra thống kê và các thì nghiệm đặc biệt . Trên bước này thực hiện chương trình thuật toán của hệ mật hoặc thực hiện chúng trên phần cứng và tiến hành kiểm tra thống kê và các thí nghiệm đặc biệt, lập quy hoạch kết quả phân tích để kiểm tra toàn diện và tương ứng với lý thuy ết. Ngoài ra việc kiểm tra hệ mật cũng chú ý đến các khả năng tấn công mới. Bước phân tích hệ mật được tiếp tục thực hiện trong quá trình sử dụng hệ mật. Các cách miêu tả khóa
1. Sử dụng tính trước. Ở đây chúng ta sử dụng một quá trình hay thuật toán để biến đổi khóa mật thành khóa mở rộng. Việc sử dụng quá trình tính toán ban đầu để mở rộng khóa cho phép đảm bảo được sự phụ thuộc phức tạp của khóa vòng vào khóa mật. Cách làm này, nếu như có một thuật toán mở rộng tốt thì sẽ tránh tấn công của thám mã nhằm đạt được khóa mật. Thế nhưng phương pháp này có nhược điểm là sẽ làm giảm tốc độ mã trong ứng dụng ở chế độ khóa phiên. Ngoài ra khi thực hiện trên máy cần tốn thêm một lượng tài nguyên để thực hiện sơ đồ mở rộng khóa. 2. Trực tiếp sử dụng khóa mật. Ở đây sử dụng một phần khóa mật (kích cở là 32 hoặc 64 bit) cho mỗi vòng mã. Tiêu biểu cho cách sử dụng này là thuật toán chuẩn liên xô 28147-89, chúng ta sẽ xem chi tiết thuật toán này ở phần sau. Nhược điểm của phương pháp này là khóa vòng phụ thuộc rõ ràng vào khóa mật nên thám mã có thể lợi dụng ở đây mà tấn công. Ngoài ra thực hiện trực tiếp khóa mật tồn tại phần lớn lớp khóa yếu, tức là các khóa mà dùng cho quá trình mã hóa và quá trình giải mã trùng nhau. Mặc dầu khóa yếu rất hiếm xuất hiện và khi xử lý hệ mật thì tìm cách để tránh xuất hiện nó. Ưu điểm khi dùng trực tiếp khóa mật làm khóa vòng là đảm bảo được tốc độ mã ở chế độ khóa phiên và cũng không cần thêm tài nguyên cho quá trình mở rộng khóa khi thực hiện trên máy. 3. Hình thành khóa vòng trong quá trình mã khối dữ liệu. Ở phương pháp này thì vòng đầu tiên của quá trình mã sử dụng một phần khóa mật, nhưng khi hoàn thành mã vòng đầu tiên thì hình thành khóa con cho vòng thứ hai. Và khi mã vòng hai xong rồi thì tính toán khóa con cho vòng thứ ba và cứ tiếp tục như thế. Quá trình giải mã cũng có qúa trình hình thành tương tự. Và rõ ràng chúng ta thấy quan hệ khóa con giữa hai qúa trình mã và giải mã là vòng mã thứ i và giải mã thứ R-i+1 có khóa con như nhau, ở đây R là số vòng mã hay giải mã. Phương pháp này thì cũng cần thêm một lượng tài nguyên khi thực hiện trên phần cứng nhưng nó đảm bảo được tốc độ mã ở chế độ khóa phiên. 4. Biến đổi khóa con phụ thuộc vào biến đổi dữ liệu. Ở phương pháp này thì một phần khóa mật được sử dụng trực tiếp, nhưng trước khi nó tham gia biến đổi trên khối dữ liệu con thì nó bị biến đổi bằng lệnh, lệnh này phụ
thuộc giá trị hiện tại của một trong các khối con. Lệnh này có thể thực hiện đồng thời với biến đổi của khối dữ liệu con khác, cho nên nó không làm giảm tốc độ mã hóa. Phương pháp này cũng tồn tại xuất hiện khóa yếu, nhưng vấn đề này có thể khắc phục bằng cách xây dựng hệ mật có một vòng mã không là thuận nghịch (involution). Phương pháp này còn dễ thực hiện trên phần cứng và đảm bảo được tốc độ cao ở chế độ khóa phiên. 7.6 Chuẩn mã khối DES và các biến dạng của nó 7.6.1 Tổng quan về DES. DES (viết tắt của Data Encryption Standard, hay Tiêu chuẩn Mã hóa Dữ liệu) là một phương pháp mật mã hóa được FIPS (Tiêu chuẩn Xử lý Thông tin Liên bang Hoa Kỳ) chọn làm chuẩn chính thức vào năm 1976. Sau đó chuẩn này được sử dụng rộng rãi trên phạm vi thế giới. DES mã hóa một xâu bit x dài 64 bằng một khóa có đ ộ dài 56 bit. Và tất nhiên bản mã cũng có độ dài 64 bit. Vì lý do DES có khóa mật quá ngắn, nên với kỹ thuật hiện nay thì DES hoàn toàn bị phá. Nhưng để hiểu sâu về mã khối chúng ta không thể không biết về DES. Miêu tả thuật toán DES. Sơ đồ miêu tả DES được cho ở hình 7.11. Bản rõ x IP k1 F k2 F k16 F IP − 1 Bản mã y Hình 7.11 Sơ đồ thuật toán DES Ta giải thích sơ đồ thuật toán, có thể xem thuật thuật toán có 3 giai đoạn sau: 1. Khối bản rõ x có độ dài 64. Nó sẽ bị biến đổi bằng lệnh hoán vị IP:
x0 = IP( x) = ( L0 , R0 ) , Với hoán vị IP được cho bảng dưới. 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 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 Ở đây ta hiểu là, bit thứ 58 sẽ đổi về vị trí 1, bit thứ 50 về vị trí 2, tương tự như thế cho các bit còn lại. Khối x0 chia thành hai khối con có độ dài bằng nhau L0 , R0 . 2. Khối ( L0 , R0 ) sẽ bị biến đổi qua 16 vòng, mỗi vòng sẽ biến đổi đúng trong miểu tả mạng Feistel, tức là xi +1 = { Ri , F ( Ri , K i ) ⊕ Li } , chú ý là mỗi vòng sẽ có một khóa ki ,khóa này được tạo ra bởi hàm tính toán khóa con, chúng ta sẽ nói ở phần sau. Hàm F được miêu tả bằng sơ đồ trên hình 7.12: 32 bít dữ liệu 48 bít khóa con E 48 bít S1 S2 S3 S4 S5 S6 S7 S8 P 32 bít Hình 7.12 Sơ đồ miêu tả hàm F của DES Diễn giải sơ đồ như sau: Hàm F có hai tham số đầu vào, là khối dữ liệu 32 bit và khóa con 48 bit, khối dữ liệu 32 bit sẽ mở rộng bằng hàm mỡ rộng E, để thành 48 bit, hàm E biểu diễn bằng bảng chọn bít sau: 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 Sau đó nó cộng loại trừ với khóa con 48 bit, như hình vẽ, ta sẽ thu được 48 bit, 48 bít này sẽ đi qua 8 bảng hoán đổi S1 , S 2 ,..., S8 , mỗi bảng S có 64 phần tử,xếp thành 4 hàng, mỗi hàng 16 phần tử, mỗi phần tử là 4 bít. Giả sử đ ầu vào mỗi bảng hoán đổi Si là 6 bít b1b2b3b4b5b6 , thì đầu ra sẽ là 4 bít, cách xác định 4 bit đó như sau: 2 bit b1b6 xác định thứ tự hàng của bảng S, 4 bít b2b3b4b5 xác định cột của bảng S, và phần tử cần xác định tương ứng có hàng thứ b1b6 và cột thứ b2b3b4b5 . Kết quả của quá trình hoán đổi chúng ta thu được là 32 bít. 32 bít này sẽ thực hiện tiếp một hoán vị P và 32 bít nhận được là đầu ra của hàm F, với P được cho ở bảng sau: 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 6 bảng S được cho như sau: S1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 S2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 2 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 3 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 S3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 1 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 2 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 3 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
S4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 2 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 S5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 2 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 3 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 S6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 2 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 3 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 S7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 2 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 3 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 S8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 3 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 Chú ý. Quá trình mã hóa thì thứ tự khóa con tham gia lần lượt cho 16 vòng là k1 , k 2 ,..., k16 , quá trình giải mã thì thực hiện theo thứ tự ngược lại. 3. Qua 16 vòng, ta thu được 64 bit, và 64 bít này lại tiếp tục thực hiện hoán vị ngược IP −1 của hoán vị IP ta thu được 64 bít mã. IP −1 tính ra như sau: 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 Quá trình sinh khóa con được miêu tả bằng sơ đồ hình 7.13. Khóa 64 bít PC1
2. Với i chạy từ 1 đến 16 thực hiện các bước sau: Hai khối con Ci −1 , Di −1 bít thực hiện dịch vòng trái shifts[ i ] bít, với mảng shifts[ ] = [1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1] , thu được 2 khối 28 bít Ci , Di tương ứng. Trong 56 bít thu được, ta thực hiện hoán vị cố định PC2 có 48 phần tử đ ể thu được khóa con ki chiều dài là 48 bít, PC2 được cho ở bảng sau: 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 Chúng ta thấy PC2 vừa là hoán vị vừa là bảng chọn 48 bít từ 56 bít. Biến dạng của DES. Như nói ở phần trước, vì hạn chế của DES trước các phương pháp tấn công, nên họ tìm cách làm tăng khả năng an toàn cho thuật toán. Chúng ta sẽ tìm hiểu hai cách biện dạng hiệu quả trong số các biến dạng của DES. 3DES. Sở dĩ nó có tên là 3DES bởi vì người ta dùng 3 lần liên tiếp DES với 3 khóa khác nhau để mã hóa/giải mã. Chúng ta xem sơ đồ mã hóa 3DES trên hình 7.14, với E là quá trình mã hóa của DES, tương ứng với quá trình giải mã là D. K1 K3 C M E D E Hình 7.14. Sơ đồ 3DES − Viết gọn như sau: 3DES K , K 1 2 ,K3 ( M ) = DES K 3 ( DES K1 ( DES ( M )) 2 Tức là bản tin ban đầu M sẽ được mã hóa bởi khóa K1 được C1 , C1 tiếp tục giải mã bởi K 2 được C2 , C2 tiếp tục mã hóa bởi K 3 được bản mã là C. Quá trình giải mã thì ngược lại, tức là bản mã C sẽ giải mã bởi khóa K 3 thu được C2 , C2 mã hóa bởi K 2 thu được C1 , C1 giải mã bởi K1 ta thu được bản tin ban đầu M. Lúc này chiều dài khóa sẽ là 56.3=168 bít. Chúng ta dễ dàng nhận thấy nếu K1 = K 2 = K 2 thì 3DES trở thành DES.