Chương 7 - Mật mã đối xứng | An toàn thông tin | Đại học Công nghiệp Thành phố Hồ Chí Minh

lOMoARcPSD| 45470368 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 F 1 K (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? lOMoARcPSD| 45470368
Để 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 ( PX ) ( ) PXPY ( ) / ( PY ) Y X 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; P YX ( ) 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; P XY ( ) 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 P XY ( ) 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ăngsố
lượng phần tử ngẫu nhiên phải làm tăng entropy. lOMoARcPSD| 45470368
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ảibằ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( )log2 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 mã ( ) X 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 lOMoARcPSD| 45470368
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 (x x1, 2,..., xN ) F(2)N thành một dãy N bit y (y y1, 2,..., yN ) 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: 1 2 ... n 1 2 ... n , lOMoARcPSD| 45470368
ở đâ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ứ , vị trí thứ
tương tự như thế. Giá trị n gọi là chiều dài hoán 1
2 đổi cho vị trí thứ 2 đổ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à , và rõ ràng rằng n 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
lệnh hoán đổi có dạng: 1, 2,..., n 1 2 ... n S 1' 2' ... n' , Với ' ' ' ' ' ' không bắt buộc là 1 , 2 ,...,n ' . Các giá trị 1, 2 ,..., n khác nhau.
Ví dụ lệnh thay thế 2 bit này thành 2 bít khác: 1 2 3 4 lOMoARcPSD| 45470368 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ị.
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 k k … Chuỗi bít này sẽ 1, 2,...,ki
cộng với chuỗi bít bản rõ p p1, 2,..., 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: lOMoARcPSD| 45470368 ci ki pi 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 gammaBản mã ci ki
Hình 7.4. Quá trình mã hóa gamma Bản mã ci gammaBả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 i P p 1- p Y 0 1 Luật phân bố Y là i P 1 / 2 1 / 2
ở đây P 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à i
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: lOMoARcPSD| 45470368 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) lOMoARcPSD| 45470368
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
, thì vòng thứ i+1 sẽ là: i L Ri, i X i 1 R F R Ki, ( i, 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à Xr
F R(r 1, Kr 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 , để giải mã, chúng ta dung đúng thuật toán mã hóa, tham số của thuật to r án
bây giờ là khối dữ liệu là X và thực hiện r vòng với đảo thứ tự các khóa con ngược với r
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ênlàm không gian khóa giảm đi một nữa. lOMoARcPSD| 45470368
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. X X X 2 3 4 K F
Hình 7.7. Cấu trúc mở rộng mạng Feistel loại 2 X X X 2 3 K F 4
Hình 7.8. Cấu trúc mở rộng mạng Feistel loại 3 X X X 2 3 4 K F
Hình 7.9. Cấu trúc mở rộng mạng Feistel loại 2 lOMoARcPSD| 45470368
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. X X 1 2 K 1 K 2 Y Y 1 2
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 X là các véctơ đầu vào, là véc tơ đầu ra. 1, 2
K K1, 2 là các khóa, Y Y1,2
Ư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 lOMoARcPSD| 45470368
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ó. lOMoARcPSD| 45470368
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. lOMoARcPSD| 45470368
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. lOMoARcPSD| 45470368
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 k 1 F k 2 F k 16 F 1 IP 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( ) (L R0, 0 ) , 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 lOMoARcPSD| 45470368 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 L R0,0 .
2. Khối (L R0, 0) 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à x
, chú ý là mỗi vòng sẽ có một i 1
R F R Ki, ( i, i ) Li
khóa k ,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 ở i
phần sau. Hàm F được miêu tả bằng sơ đồ trên hình 7.12:
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:
Downloaded by Trang Mai (trang1201@gmail.com) lOMoARcPSD| 45470368
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 S S
, mỗi bảng S có 64 phần tử,xếp 1, 2,...,S8
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 S
, thì đầu ra sẽ là 4 bít, cách xác định 4 bit
i là 6 bít bb b b b b1 2 3 4 5 6
đó như sau: 2 bit bb xác định thứ tự hàng của bảng S, 4 bít xác định 1 6 b b b b2 3 4 5
cột của bảng S, và phần tử cần xác định tương ứng có hàng thứ bb và cột thứ 1 6 b b b b
. 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ẽ 2 3 4 5
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 lOMoARcPSD| 45470368 Downloaded by Trang Mai (trang1201@gmail.com) lOMoARcPSD| 45470368
Chú ý. Quá trình mã hóa thì thứ tự khóa con tham gia lần lượt cho 16 vòng là k k1,
, quá trình giải mã thì thực hiện theo thứ tự ngược lại. 2,...,k16
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 Khóa 64 bít PC1 K K 1 Down 25 16
loaded by Trang Ma <<< i (tran g1201@g P m C a 2 il. com) <<< lOMoARcPSD| 45470368
Quá trình sinh khóa con được miêu tả bằng sơ đồ hình 7.13.
Hình 7.13 Sơ đồ sinh khóa DES
Giải thích sơ đồ. Quá trình sinh khóa có thể chia ra hai giai đoạn sau:
1. Với 64 bit khóa ban đầu, ta loại các bit kiểm tra tính chẳn lẻ, còn lại 56 bit tathực
hiện hoán vị cố định PC1, với PC1 được cho ở bảng dưới:
Với 56 bít nhận được phân chia ra hai khối con, mỗi khối 28 bít C D0, 0 .
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 C Di, i 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 k chiều dài là 48 bít, PC2 được cho ở bảng sau: i Downloaded by Trang Mai (trang1201@gmail.com)