Giáo trình Đại số hiện đại - Chương 7: Mật mã khóa đối xứng

Chương 7
MẬT MÃ KHÓA ĐỐI XỨNG
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: .
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: .
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:
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ã?
Bản mã liệu có một nghiệm duy nhất hay không?
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
Nguồn khóa
Nguồn bản tin
Mã hóa
Giải mã
Nhận bản tin
Tội phạm
K
K’
X’
X
Y
X
K
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; 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; 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 và 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:
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. 
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. 
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:
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à:
,
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.
Đị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 (X)
Quá trình mã hóa
Bản mã Y truyền qua kênh
Quá trình giải mã
(X=)
Bản tin giải mã X
Khóa mật (K)
khóa
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 thành một dãy N bit 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 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.
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:
 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ậpvào tập,, lệnh hoán đổi có dạng sau:
,
ở đâ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,khi ), tức là vị trí thứ đổi cho vị trí thứ , vị trí thứ đổi cho vị trí thứ tương tự như thế. Giá trị n gọi là chiều dài hoán đổi.
Ví dụ:
.
Tập hợp tất cả các lệnh hoán đổi ký hiệu là , và rõ ràng rằng .
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:
.
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 ,với .
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ũ.
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ử .
Đối với lệnh hoán đổi có dạng:
,
Với . Các giá trị 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:
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.
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ư ý.
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  Chuỗi bít này sẽ cộng với chuỗi bít bản rõ để nhận được chuỗi bản mã:
Ở 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:
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õ
gamma
Bản mã 
Hình 7.4. Quá trình mã hóa gamma
Bản mã
gamma
Bản rõ 
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
p
1-p
Luật phân bố Y là
Y
0
1
1/2
1/2
ở đây 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:
, nếu như A và B không giao nhau
, 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:
Đối với từng trường hợp dùng gamma khác nhau;
Để tạo ra gamma dùng phương pháp tạo số ngẫu nhiên;
Gamma phải dài tương ứng với bản mã;
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.
Một số sơ đồ dùng để thiết kế hệ mật
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
F(R,K)
L’=R
R’=F(R,K)
K
R
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 . 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 , thì vòng thứ i+1 sẽ là:
.
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à
,
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 , để 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à 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.
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.
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.
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ã.
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.
F
K
Hình 7.7. Cấu trúc mở rộng mạng Feistel loại 2
F
K
Hình 7.8. Cấu trúc mở rộng mạng Feistel loại 3
F
K
Hình 7.9. Cấu trúc mở rộng mạng Feistel loại 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.
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à là các véctơ đầu vào, là các khóa, 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.
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:
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 ... i) được hình thành theo véctơ đầu vào U = X║K и U(i) = X(i)║K, где X(i) = X Ei.
Trong số các tham số đưa ra các giá trị: q là số lượng khóa được chọn, t là số lượng bản tin được chọn thì N = qt. Việc lựa chọn q và t phụ thuộc vào giá trị của n và m. Ma trận phụ thuộc ║aij║n×m và ma trận khoảng cách Hamming ║bij║n×m có dạng sau:
Để tạo kết quả chính xác thì việc lựa chọn khóa và bản tin cần phải ngẫu nhiên.
Trong trường hợp này thì véctơ thác lũ Y(i) được hình thành theo véctơ đầu vào U = X║K và U(i) = X║K(i), где K(i) = K Ei. Trong các tiêu chí thì ma trận phụ thuộc ║aij║n×m và ma trận khoảng cách Hamming║bij║n×m có dạng sau:
Chúng ta cần chú ý rằng các tiêu chí đã xem xét là công cụ hiệu quả đối với việc xem xét điểm yếu của thuật toán, cũng như xem hiệu quả của cách miêu tả khóa, và qua đây chúng ta biết được thuật toán chúng ta nên chọn số vòng là bao nhiêu để đạt hiệu quả.
Chú ý: Ngoài ra để thiết lập quan hệ giữa các mô hình lý thuyết và thực hành người ta còn đưa ra tiêu chí ở đây chúng ta không xem xét.
Thám mã véc cạn khóa
Giả sử rằng kẻ gian có được một hoặc một số cặp (x,y). Gỉa sử rằng đối với một cặp (x,y) bất kỳ thì tồn tại một khóa k duy nhất thỏa mãn . Chúng ta sắp xếp tập hợp không gian khóa và lần lượt kiểm tra các khóa từ tập khóa K xem sự thỏa mãn biểu thức . Nếu như xem một lần kiểm tra khóa là một lệnh thì việc véc cạn khóa cần #K lệnh, ở đây #K là số lượng phần tử của tập K. Giả sử rằng khóa k trong sơ đồ mã hóa được chọn ngẫu nhiên và khả năng như nhau từ tập K. Như vậy xác suất đoán được khóa k là , và độ khó của phương pháp véc cạn sẽ bằng 1. Cho nên để đánh giá độ khó của phương pháp ta chọn kỳ vọng toán học của độ lớn ngẫu nhiên , ở đây là số phép thử trước thời điểm tìm được khóa sử dụng. Bởi vì là độ lớn ngẫu nhiên phân bố đều, nên M()=.
Thuật toán véc cạn cho phép thực hiện song song, bời vì điều này nên có thể tăng tốc đáng kể quá trình tìm khóa. Có hai hướng trong quá trình tính toán khóa song song.
Một là, xây dựng dây chuyền. Cho thuật toán của biểu thức được biểu diễn dưới dạng dây chuyền cố định các lệnh .
Chọn N quá trình , sắp xếp theo thứ tự và cho quá trình thứ i hoàn thành 3 lệnh như nhau theo thời gian:
Nhận dữ liệu thứ (i-1) quá trình;
Hoàn thành lệnh ;
Chuyển dữ liệu cho quá trình thứ (i+1);
Như vậy dây chuyền gồm N quá trình được liên kết nối tiếp nhau làm việc song song, đồng bộ làm việc với tốc độ , là tốc độ hoàn thành 1 lệnh của quá trình.
Hướng thứ hai là tập khóa K được phân nhỏ ra thành các tập không giao nhau . Hệ thống gồm Q máy thực hiện việc lựa chọn khóa, máy thứ i thực hiện việc lựa chọn khóa từ tập . Hệ thống ngừng làm việc nếu như có một máy tìm được khóa. Điều phức tạp nhất của phương pháp là tổ chức phân chia tập khóa. Thế nhưng nếu tổ chức việc tìm kiếm khóa như vậy thì trong mỗi lần thí nghiệm thì một trong N quá trình sẽ trở nên ngẫu nhiên, thời gian thí nghiệm sẽ tăng nhưng tốc độ của sơ đồ lại tăng lên đáng kể. Số bước thí nghiệm thực hiện N quá trình trong trường hợp này là .
Việc thực hiện xử lý song song như vậy phải có các cách giải quyết khác nhau. Một trong các cách được ưu tiên đó là tạo ra virut máy tính để phân bố chương trình trong mạng nội bộ.Virut cần sử dụng chu kỳ dừng của máy tính để thực hiện việc tìm kiếm theo tập khóa. Sớm hay muộn thì một trong các máy nhiểm virut sẽ tìm được khóa cần tìm. Với sự lớn của công suất máy tính cũng như tốc độ lây lang virut thì khả năng thành công của phương pháp này ngày một tăng.
Thám mã bằng phương pháp thống kê
Mục đích của phương pháp thám mã thống kê là xử lý thuật toán nhằm tìm khóa chưa biết (hoặc một phần khóa) . Chúng ta xem các nguyên tắc cơ bản và định nghĩa của phương pháp thống kê đối với mã khối.
Thực hiện phương pháp thám mã thống kê nhằm xác định khóa mật đối với mã khối cho phép nhận được đánh giá hiệu quả thuật toán hơn là phương pháp véc cạn khóa. Đầu vào là mốt số cặp (Xi,Yi), i=1,,N bản rõ và bản mã, bản mã thu được bằng cách ứng dụng ánh xạ F với khóa k. Các cặp như vậy được gọi là “tư liệu” và ký hiệu là M. Dung lượng của tư liệu tương ứng với số cặp (Xi,Yi): . Giả sử rằng các bản rõ Xi, i=1,,N được chọn ngẫu nhiên, đồng khả năng và độc lập từ không gian .
Quá trình thống kê phân loại là phần quan trọng nhất của phương pháp phân tích thống kê, quá trình này dùng để tìm các tham số chưa biết theo quan sát ngẫu nhiên. Hàm phân bố xác suất để quan sát phụ thuộc vào tham số mật này. Ý tưởng của quá trình thống kê phân loại thể hiện ở chổ, nếu như sự phận bố xác suất này mà khác nhau thì khi số lượng quan sát đủ lớn thì có thể xác định được định luật phân bố quan sát và từ đó có thể xác định tham số cần tìm.
Chúng ta ký hiệu tập hợp ở đó nhận giá trị của tham số chưa biết là .
Mỗi quá trình thống kê phân loại được xác định sự phân chia tất cả không gian quan sát M ra T phần không giao nhau: với . Vùng gọi là vùng chọn nghiệm. Đối với từng vùng Mi quá trình thống kê phân loại cũng xác định danh mục thứ thự s’ thành phần của tập hợp , lúc này với.
Để xác định thành phần chưa biết từ tập cần thực hiện các lệnh sau. Đầu tiên theo sự quan sát nhận được cần xác định số thứ tự vùng chọn nghiệm i(m). Sau đó lựa chọn lần lượt các tham số từ tập và kiểm tra xem giá trị của tham số thứ j (j=1s’) có phải là cần tìm hay không.
Thám mã vi sai
Thám mã vi sai là một trong các phương pháp phân tích cơ bản và hiệu quả nhất đối với mã khối. Phương pháp mã vi sai đươc đưa ra năm 1990 bởi các nhà nhà toán học E. Biham và Shamir. Đây là phép tấn công với việc chọn bản rõ chọn lọc, để tìm ra khóa mật hay một phần khóa mật.
Định nghĩa: Cho cặp hai véc tơ X, X*. Khoảng cách giữa hai véc tơ hay còn gọi là hiệu giữa hai véc tơ được xác định bằng lệnh XOR: .
Định nghĩa: Vi sai của vòng mã thứ i được xác định bằng cặp véc tơ (), sao cho cặp bản rõ (x,x’) có hiệu bằng có thể đi qua i vòng mã, đầu ra là cặp bản mã (y,y’) với hiệu của chúng là .
Xác suất vi sai của vòng mã thứ i- đó là xác suất có điều kiện, sao cho hiệu của cặp bản mã (y,y’) sau i vòng mã bằng với điều kiện là cặp bản rõ tương ứng (x, x’) có hiệu khoảng cách là , khi bản rõ x và các khóa k(1), k(2),,k(i) sử dụng tương ứng trong các vòng 1,2,,i là độc lập và đồng khả năng, có nghĩa là
,
lúc này xác suất phân bố vi sai đối với từng vòng là không đổi và không phụ thuộc vào vòng trước.
Giá trị vi sai ở đầu ra của vòng mã thứ i được sử dụng để tìm kiểm khóa con của vòng mã cuối cùng tức là vòng thứ i+1 bằng cách như sau:
Đối với từng cặp bản rõ –mã ta giả sử rằng giá trị vi sai đầu ra của vòng mã thứ i là . Tiếp theo để giá trị này và giá trị của cặp bản rõ –mã tìm được những giá trị có thể của khóa con trong vòng mã cuối i+1 cùng, tức là hình thành một số tập hợp khóa con mà nó thỏa mã điều kiện trên. Lúc này thì một phần trong các tập hợp là khóa đúng. Đối với tất cả tập hợp giá trị có thể của khóa vòng, chúng ta thiết lập bảng tần số xuất hiện của chúng. Tấn công sẽ thành công khi giá trị đúng của khóa vòng xuất hiện thường xuyên hơn các giá trị khác.
Trong trường hợp này có thể tính toán biểu thức tương quan giữa số lương cặp giá trị giả sử đúng và số lượng trung bình các phương án có thể của khóa vòng trong bảng tần số.
Biểu thức này được gọi là biểu thức tín hiệu – tiếng ồn S/N (Signal to noise). Nếu như kích thước bảng phương án của khóa vòng là , ở đây l là chiều dài của khóa vòng, còn số lượng trung bình các phương án là thì biểu thức S/N được viết:
 (7.1)
Biểu thức (7.1) ảnh hưởng rất lớn lên số lượng cặp bản mã và rõ đúng mà số lượng này cần thiết để xác định một khóa vòng.
Thuật toán thám mã vi sai
Quá trình cơ bản của thuật toán thám mã vi sai r vòng mã sử dụng bản rõ chọn lọc, diễn ra như sau:
Đầu vào: thuật toán mã hóa, bản rõ chọn lọc và bản mã tương ứng.
Đầu ra: khóa.
1. Ở bước đầu tiên của tính toán chúng ta tìm tập hợp vi sai của cho vòng mã thứ , với, sao cho xác suất lớn nhất hoặc gần lớn nhất. Lúc này bản rõ X và tất cả khóa con đối với vòng mã là độc lập và đồng khả năng. Sắp xếp chúng theo thứ tự tăng dần của xác suất. 
2. Đối với một bản rõ bất kỳ x chúng ta tính bản rõ x’ sao cho hiệu khaỏng cách giữa x và x’ bằng . Mã hóa bản rõ x và x’ trên khóa cần tìm và sau r vòng thu được cặp bản mã . Giả sử rằng đầu ra của vòng mã thứhiệu khoảng cách của các bản mã có xác suất lớn nhất:. Từ bộ bachúng ta tìm ra tất cả giá trị có thể của khóa. 
3. Lặp lại bước 2 cho đến khi có một hoặc một số giá trị của khóa con к(r) không ngừng xuất hiện thường xuyên các giá trị khác. Chúng ta xem khóa này hoặc một tập khóa này là nghiệm mã hóa đối với khóa của vòng mã cuối cùng. 
4. Chúng ta lặp lại các bước từ 1-3 đối với vòng mã kề cuối, lúc này giá trị được tính bằng cách giải mã bản mã trên khóa tìm được. Chúng ta thực hiện tương tự để tìm ra các khóa vòng còn lại.
Hiệu quả của thuật toán phụ thuộc vào độ lớn và sự phân bố tập hữu hạn vi sai sau vòng mã, có nghĩa là biểu thức S/N. Xác suất vi sai càng nhỏ và càng phân bố đều giữa chúng thì càng khó xác định giá trị khóa .
Từ thuật toán chúng ta thấy rằng, điều kiện cần để thám mã vi sai r vòng mã thành công là tồn tại vi sai của vòng mã thứ (r-1), mà xác suât xuất hiện của chúng lớn hơn rất nhiều so với 2−m.
Điều này có nghĩa là, để phân tích khả năng thực hiện tấn công vi sai, cũng như đánh giá hiệu quả của phương pháp, cần phải biết được giá trị lớn nhất của xác suất vi sai sau một số vòng mã.
Xác suất lớn nhất của vi sai được sử dụng để xác định giới hạn dưới của độ phức tạp tấn công vi sai và có thể chứng tỏ rằng r vòng mã sẽ không bị tổn thương bởi phép tấn công này.
Đối với mật mã có vi sai không phụ thuộc vào sự lựa chọn bản rõ, nếu các khóa con của các chu kỳ độc lập nhau thì dãy các khoảng cách sau từng chu kỳ tạo thành chu trình Markob. Lúc này xác suất thu được vi sai của vòng thứ s được xác định:
P(y(s)=s | x= )=.
Đối với cặp vi sai đã cho xác suất để thu được cặp này lớn hơn nhiều so với :
P(y(i)= | x= )=,
với m là kích thước của khối mã.
Độ phức tạp bẻ khóa của vòng thứ r mật mã là Q(r) được xác định bắng số lệnh mã sử dụng trong qúa trình tìm khóa:
Q(r)2/ (Pmax - 1/(2m-1)),
ở đây:
Pmax=max( )max( )(P(y(r-1)= | x= )),
Trong số đó nếu Pmax 1/(2m-1), thì việc tấn công được xem là không thành công.
Thám mã tuyến tính
Ý tưởng của phương pháp tuyến tính lần đầu tiên được chuyên gia người Nhật M. Matsu đưa ra năm 1992. Phương pháp này được cho là một trong các phương pháp phân tích hiện đại và hiệu quả đối với mã khối. Phương pháp dựa trên tập bản rõ và bản mã tương ứng để tìm ra khóa mật. 
Thám mã tuyến tính là một trường hợp của phương pháp thám mã thống kê tổng quát trên cơ sở sử dụng biểu thức sau:
, (7.2)
ở đây a, b Î Vn, c Î Vm, 0≤ t1 ≤ t2 ≤ r (ở đây cặp véc tơ (a, b) được gọi là đặc trưng tuyến tính) . Lệnh là tích vô hướng giữa hai véc tơ a và b cùng kích thước.Ở phương pháp thám mã tuyến tính chỉ sử dụng biểu thức kiểu (7.2), xác suất để thu được biểu thức này khác với ½ và có thể viết dưới dạng: 
, (7.3)
 ở đây .số ε gọi là ưu thế (deviation, bias).
Hiệu quả của phương pháp thám mã tuyến tính càng lớn nếu như trị tuyệt đối của ε càng lớn. Cho nên khi xây dựng một thuật toán cụ thể xác định khóa bằng phương pháp thám mã tuyến tính thì nhiệm vụ đặt ra là tìm các véc tơ a, b Î Vn, c Î Vm, để giá trị tuyệt đối của có thể lớn nhất: . Lúc này thì hiệu quả và độ khó của phương pháp được xá định bằng độ lớn đã cho |ε|, có nghĩa là để xây dựng các véc tơ a, b Î Vn, c Î Vm, cần biết đánh giá |ε| trong biểu thức (7.3).
Chúng ta xem một phương án đơn giản nhất (không phải hiệu quả nhất) của thám mã tuyến tính – đó là thuật toán xác định một bít khóa, được gọi là thuật toán 1 Masui. Thuật toán này sử dụng biểu thức (7.2) với t1=0 và t2=r, có nghĩa là biểu thức (7.2) được viết lại dưới dạng bản rõ và bản mã như sau:
,
ở đây cặp véc tơ (Xi, Yi) là căp bản rõ và bản mã mà thám mã biết. Phương pháp thám mã vi sai tương ứng với phương án đã cho xác định tổ hợp tuyến tính các bít khóa. Tập hợp công sức được tính:
Quá trình phân loại thống kê phân chia tất cả không gian quan sát M ra hai phần M0 và M1 (: Đối với vùng M0 tương ứng với , còn vùng M1 ứng với . Thuật toán sử dụng nguyên tắc sự hợp lý cực đại: Nếu như và trong biểu thúc (7.3) hoặc và trong biểu thức (7.3) , thì thuật toán đưa ra giá trị , trong trường hợp ngược lại thì . Các bít khóa còn lại xác định theo phương pháp véc cạn.
Hệ mã dòng RC4
Thuật toán RC4.
Đây là một hệ mã dòng, với chiều dài khóa biến đổi, tác giả của nó là Ronald Rivest, được nêu ra năm 1987. 
Hạt nhân của thuật toán là thủ tục tạo khóa dòng, xem hình 7.42, hàm này tạo dãy bít sau đó cộng với bản tin theo modulo 2 với bản rõ ta thu được bản mã, và khi giải mã thì cũng sinh ra mã dòng, rồi cộng với bản mã theo từng bít ta thu được bản rõ ban đầu. RC4 làm việc ở chế độ OFB. Gọi k là giá trị mã dòng được sinh. Việc sinh mã dòng được thực hiện trên cơ sỡ khối hoán đổi kích thước 8x8 : S[0],...S[255]. Khối hoán đổi là phép hoán vị các số 0,, 255 phụ thuộc vào khóa, được thực hiện bởi các lệnh sau:
1. 
2. 
3. Hoán đổi giá trị của S[i] và S[j]
4. Tính tổng S[i] và S[j], gán cho t: t= (S[i] + S[j]) mod 256
5. k=S[t].
Hình .7.42. Sơ đồ tạo khóa dòng k
Trong quá trình sử dụng, bộ đếm i sẽ làm cho nội dung của khối S thay đổi chậm, còn bộ đếm j sẽ đảm bảo sự thay đổi này là ngẫu nhiên. 
Byte k được tạo ra cộng với byte của bản rõ để tạo ra byte bản mã.
Một phần chính của thuật toán nữa là khởi tạo khối hoán đổi S, việc khởi tạo được thực hiện các bước sau:
Gán cho mỗi phần tử giá trị bằng chỉ số của nó: S[0]=0,,S[255]=255.
Tạo một mảng key gồm 256 phần tử, mỗi phần tử có kích thước 1 byte. Điền đầy mảng key bằng các byte của khóa K, nếu mảng key chưa điền đầy thì lặp lại mốt số bye của khóa K. 
Xáo trộn khối S: 
i = 0..255 
j = (j + S[i] + key[i]) mod 256 
Hóan đổi giá trị: S[i] ↔ S[j] 
Những ưu điểm chính của RC4
Thuật toán đơn giản. Ý nghĩa của từng bước rõ ràng, logic. 
RC4 tỏ ra an toàn đối với cả 2 phương pháp thám cơ bản là thám tu‎yến tính và thám vi phân (chưa có công trình nào về thám RC4 được công bố) . Số trạng thái mà RC4 có thể có là 256!×256×256 » 21700. 
Tốc độ mã đạt rất cao. Ví dụ so với DES thì RC4 nhanh gấp 10 lần.
Có thể khía quát thuật toán trên cơ sở từ có chiều dài lớn và kích thước khối hoán đổi lớn, ví dụ 16x16.
Mã dòng WAKE
Đây là thuật toán mã dòng, tác giả của WAKE là Devit Uyler. Ở đầu ra nhận được chuỗi từ 32 bít. WAKE làm việc ở chế độ CFB – từ trước của bản mã được dùng để tạo ra từ tiếp theo bằng chuỗi khóa.
Trong thuật toán sử dụng khối hoán đổi đặc biệt S gồm 256 từ 32 bít. Ở đây các bytes cao của từ là hoán đổi các số từ 0 đến 255, còn 3 bytes thấp được chọn ngẫu nhiên.
Ban đầu khối hoán đổi được khởi tạo trên cơ sở khóa. Sau đó 4 thanh ghi A, B, C và D được khởi tạo bằng giá trị ban đầu, cũng phụ thuộc vào khóa: . Từ tiếp theo của khóa dòng nhận được theo công thức .
Sau bước này thì giá trị của các thanh ghi bị thay đổi:
Với 
Thuật toán này có tốc độ lớn mặc dầu nó không vững chắc với phép tấn công theo phương pháp chọn bảng rõ ban đầu.