Sau khi nhận được các bức điện mã hoá, các nhà phân tích mật mã (mã
thám) cần thực hiện một loạt các bước nghiên cứu nhằm khôi phục được
bản rõ hoặc tìm ra khoá từ các bản mã nhận được. Sau đây chúng ta sẽ
trình bày các bước cơ bản nhất đó là:
Bước 1: Phân loại bản mã
Sau khi nhận được một số bức điện mã, các nhà phân tích mật mã có thể
phân loại xem những bức điện mã có cùng một loại phương pháp mã, có cùng một
loại khoá mã. Mặc dù chúng ta chưa biết được phương pháp mã
hoá của các bức điện đó, nhưng chúng vẫn phân loại được.
Đây là một bước quan trọng quyết định sự thành công hay thất bại của mã
thám nên rất mất nhiều thời gian. Nếu việc phân loại chính xác thì sẽ
thuận lợi cho các bước tiến hành tiếp theo. Ngược lại, nếu phân loại
thiếu chính xác thì sẽ gây khó khăn cho các bước sau đó, thậm chí thất
bại.
Người ta có nhiều phương pháp thực thi giai đoạn này, một trong số đó
là áp dụng kỹ thuật phân loại các đối tượng. Ý tưởng của bài toán phân loại như sau:
Giả sử ta nhận được m bản mã M1, M2,..., Mm với m $ 2. Mỗi bản mã ta
gọi là một đối tượng. Tập hợp m bản mã (các đối tượng) ta ký hiệu là G.
Vậy G = {M1, M2,..., Mm}. Ứng với mỗi đối tượng ta cần tìm ra các đặc
trưng tham số. Giả sử đối tượng Mi có pi đặc trưng. Ở đây, để cho đơn
giản, ta giả thiết p1 = p2 = ...= pm= p. Vấn đề đặt ra là hãy phân tập
hợp G thành k lớp không giao nhau mà ta ký hiệu là G1, G2, ..., Gk, k
> 1 sao cho:
(i) Gi khác 0 i = 1,k
(ii) Gi 1 Gj i khác j
(iii) G1c G2c...c YGk = G
và sao cho sai sót trong phân loại là bé nhất có thể được. Để thực hiện
việc phân loại các đối tượng ta cần đưa ra một độ đo “khoảng cách” giữa
các đối tượng. Các đối tượng “gần gũi” nhau sẽ được gán cho cùng một loại.
Bước 2 : Xác định phương pháp mã
Sau khi hoàn thành việc phân loại mã ở bước 1, chúng ta
tiến hành xác định phương pháp mã dịch ứng với từng lớp cụ thể (cần
chú ý rằng, thường thì chúng ta tiến hành xác định phương pháp mã đối với các
bản mã có nhiều đặc điểm nhất theo quan điểm của các nhà mã thám ).
Đây là một khâu rất quan trọng của công tác mã thám truyền thống. Tuy
nhiên đối với một số hệ mật đối xứng hiện đại như mã DES, 3DES, AES,
IDEA, PGP... thì bước này coi như được bỏ qua bởi ngay từ đầu bản mã,
người ta đã chỉ ra rằng bản mã đó thuộc loại bản phương pháp mã nào. Ở đây
chúng ta chỉ trình bày cách thức xác định phương pháp mã đối với các luật mã
truyền thống (bước này được bỏ qua đối với những hệ mật mà thuật toán
mã hoá - phương pháp mã - được công khai hoàn toàn). Bước này bao gồm
các công việc sau đây:
a)Tính tần số
Mục đích của việc tính tần số là để phát hiện tính quy luật không ngẫu
nhiên tồn tại trong bản mã. Có rất nhiều loại tần số khác nhau cần
tính, mà đối với mỗi phương pháp mã có thể tồn tại tính không ngẫu nhiên (có
quy luật) đặc thù riêng cho nó. Theo kinh nghiệm phân tích mà người ta
tiến hành tính tần số loại phù hợp nhất thông qua đó có thể bộc lộ rõ
nhất tính quy luật (không ngẫu nhiên) trong bản mã. Việc tính tần số
thường gồm:
- Tần số đơn:
Tần số đơn là tần số từng ký tự một trong bản mã.
Sau khi có được kết quả tính tần số đơn, ta tiến hành sắp xếp lại thứ tự các ký tự theo tần số từ cao đến thấp.
Cũng có thể lập bảng tần xuất bằng cách chia tần số từng ký tự cho độ dài bản mã cần tính để xem tần số tương đối của chúng.
- Tần số bộ đôi móc xích (concatenate frequency of pairs)
Tần số bộ đôi móc xích là tần số bộ đôi nhưng các cặp kề đè lên nhau một ký tự.
Mục đích của việc tính tần số bộ đôi móc xích là để xem quan hệ phụ
thuộc giữa ký tự sau với ký tự kề ngay trước đó như thế nào, (ta thường
gọi là quan hệ xích Makov cấp 1). Từ đó có thể ước lượng được xác suất
xuất hiện một ký tự nào đó khi biết trước ký tự đứng ngay trước nó.
- Tần số bộ đôi thường:
Tần số bộ đôi thường là tần số bộ đôi rời nhau, ví dụ: cho đoạn văn : Vi ee tj na m thì tần số bộ đôi thường gồm:
Vi: xuất hiện 1 lần
e e: xuất hiện 1 lần
t j: xuất hiện 1 lần
n a: xuất hiện 1 lần
Ký tự cuối cùng được bỏ qua (chỉ gồm có 4 bộ đôi). Trong khi đó, tần số
bộ đôi móc xích sẽ được thể hiện là: Vi, ie, ee, et, tj, jn, na, am
gồm 8 bộ đôi. Lưu ý:
- Số tất cả các bộ đôi móc xích trong văn bản độ dài n là n – 1
- Còn số tất cả các “bộ đôi thường” là: [n)2]
Trong đó ký hiệu [x] là số nguyên lớn nhất nhưng bé hơn hoặc bằng x.
- Tần số bộ 3, 4, 5...
Tuỳ theo từng trường hợp cụ thể đôi khi chúng ta phải tính tần số bộ
3, bộ 4, bộ
5....
b) Tính trùng mã
Tính trùng mã tức là tính tần số trùng lặp của các dãy ký tự liền nhau
trong bản mã. Thường là tính trùng lặp 3 ký tự (bộ 3), 4 ký tự (bộ 4), 5
ký tự (bộ 5)... có thể xuất hiện trong bản mã và vị trí của chúng
trong bản mã đó.
Khi tính trùng mã (các bộ) ta phải quan tâm các tham số sau đây:
1. Tần số trùng mã (trùng lặp)
2. Độ dài trùng lặp
3. Vị trí các trùng lặp
4. Khoảng cách giữa các trùng lặp
5. Trùng mã trong một bản mã và trong các bản mã khác nhau.
Những tham số trên đây rất có ích trong việc xác định phương pháp mã.
c)Tần số định kỳ:
Ngoài việc tính tần số đơn, bộ đôi móc xích, bộ đôi thường v.v... và
trùng mã (sự trùng lặp) trong bản mã hoặc các bản mã, trong nhiều
trường hợp người ta phải tính tần số định kỳ. Giả sử ta có bản mã M độ
dài n nào đó. Thường n khá lớn và càng lớn càng tốt. Bây giờ ta lập
bảng k cột (k $ 2 và thường thì k $ 3) và n/k hàng. Sau đó, ta viết bản
mã lần lượt trái qua phải và viết từ trên xuống dưới cho đến hết thì
dừng. Bây giờ ta tiến hành tính tần số đơn theo cột từ cột 1 đến cột k.
Như vậy ta thường phải tính toán tần số các “định kỳ” khác nhau lần
lượt k = 3, 4, 5..., 10. Tần số như vậy được gọi là tần số định kỳ.
Trong nhiều trường hợp tần số đơn, đôi, bộ 3 của bản mã tương đối san
bằng (tức là không vi phạm các tiêu chuẩn 3s và c2) nhưng tần số định kỳ
lại có quy luật rất rõ.
d) Tần số bộ đôi dọc và bộ đôi dọc đồng tự.
Nếu ta viết 2 bản mã lần lượt bản mã này dưới bản mã kia. Ví dụ 2 bản mã M1=m11,m12...m1n1 và M2=m21m22...m2n2
Ta có : M1=m11m12m13... m1n1
M2=m21m22m23...m2n1...m2n2
Ta cắt phần thừa là m2n1+1, ...m2n2 (giả sử n1 < n2), và ta ký hiệu
độ dài hai bản mã còn lại là n. Ta tiến hành tính tần số từng cặp
(m1k...m2k), với k = 1, 2,... n. Ta sẽ có tần số bộ đôi và bảng này
được gọi là bảng tần số bộ đôi dọc. Các phần tử trên đường chéo chính
của ma trận tần số bộ đôi được tạo ra từ M1, M2 là tần số của các bộ đôi
dọc đồng tự.
e) Phân tích kết quả tính các tần số và trùng mã
Bước này dựa vào các kết quả tính các loại tần số, trùng mã để kết
luận bản mã (các bản mã) đó thuộc loại phương pháp mã nào. Để đánh giá độ
chênh lệch tần số hoặc tính độc lập của các ký tự trong bản mã, người
ta thường dùng các tiêu chuẩn thống kê toán học, chẳng hạn tiêu chuẩn
3s, tiêu chuẩn c2 hoặc tiêu chuẩn MLR (Most Likelihood Ratio- tỷ số hợp
lý cực đại). Nói chung việc xác định phương pháp mã là công việc rất phức
tạp, nó phụ thuộc một phần vào trình độ và kinh nghiệm của các mã thám
viên. Có nhiều trường hợp thoáng nhìn bản mã người ta đã dự đoán được
phương pháp mã nhưng cũng có rất nhiều trường hợp phải nghiên cứu rất
công phu mà độ rủi ro không phải là không có.
f) Xác định ngôn ngữ được dùng
Đây cũng là một bước giúp cho việc mã thám đột phá thành công.
Bước 3. mã thám
Giả sử đã xác định được phương pháp mã tại bước thứ 2 trên đây, nay chuyển
sang nghiên cứu, phân tích bản mã. Bước này cũng có hai công
đoạn:
a) Giải trực tiếp
Nếu phương pháp mã thuộc loại truyền thống đã biết như các phương pháp mã thủ công
hoặc được mã bằng một máy mã cụ thể nào đó mà ta đã có thuật toán giải
thì có thể tiến hành giải trực tiếp luôn (thực hiện thủ công và sau đó
có thể tự động hoá bằng lập trình trên máy tính).
b) Xây dựng phương pháp giải
Nếu phương pháp mã thuộc loại mới, công việc yêu cầu phức tạp hơn là phải xây
dựng phương pháp thám thì có hai phương pháp giải là phương pháp phân
tích và phương pháp dự đoán “Từ phỏng chừng”.
Phương pháp phân tích: được sử dụng trong trường hợp nhà mã thám đã
biết được cấu trúc khoá mã đã được sử dụng làm “mầm khoá” (key seed) để
mã hoá bản mã này. Khi đó có nhiều kiểu để xác định khoá có thể, ví
dụ: phương pháp “thử - sai”, phương pháp “lượng sai”, phương pháp
“những phần tử tách biệt”, phương pháp “tuyến tính”. Tóm lại tuỳ theo
thuật toán mã hoá của bản mã như thế nào mà chọn phương pháp phân tích
nào cho hợp lý.
Phương pháp “từ phỏng chừng”: Phương pháp này chủ yếu là dựa vào thông
tin tiên nghiệm về khoá và thông tin về bản rõ mà đối tượng sử dụng
(quy luật ngôn ngữ) để dự đoán khoá được sử dụng. Nội dung của phương
pháp này là dự đoán cụm từ có thể xuất hiện trong bản rõ gốc ứng với
bản mã, sau đó tìm cách xác định khoá đúng. Nếu khoá là đúng thì có thể
dịch bản mã để cho ra bản rõ.
Ngoài một số phương pháp truyền thống trên, ngày nay, nhờ tốc độ máy
tính đã được cải thiện đáng kể, trong những bài toán mà không gian khoá
không quá lớn người ta còn có thể áp dụng một phương pháp nữa đó là
“khai thác”. Đối với không gian khoá lớn, đây thật sự là phương pháp kém
hiệu quả nếu chúng ta chỉ thực hiện khai thác một cách thông thường. Tuy
nhiên nếu áp dụng đồng thời các kỹ thuật bổ trợ thì nó vẫn phát huy được
hiệu quả tốt. Các kỹ thuật hỗ trợ được nói tới ở đây là xây dựng một
thư viện phục vụ việc “khai thác” bao gồm cơ sở dữ liệu về khoá và các
tiêu chuẩn bản rõ tốt. Trên cơ sở đó tìm cách phân chia không gian
khoá S thành hai tập con rời nhau là S1 và S2 sao cho khoá đúng sẽ
“chắc chắn” thuộc một trong hai tập con đó. Từ đó tiến hành sử dụng
thuật toán khai thác trên tập con có chứa khoá đúng, khi đó việc “khai thác” trong tập con nhanh chóng thể hiện tính hiệu lực của nó. Việc này
cũng có thể thực hiện ngay đối với một số phương pháp truyền thống đã có
được những kết quả đáng ngạc nhiên. Khi giải ra bản rõ ta chỉ cần đọc
được lỗ chỗ đã là thành công vì lúc đó bằng quy luật ngôn ngữ ta sẽ
khôi phục được bản rõ gốc như mong muốn.
Ngày nay, người ta đã có những công cụ tính toán rất nhanh nhờ công
nghệ cluster. Từ đó người ta có thể xây dựng mạng tính toán song song
với tốc độ tính toán đạt tới gần 100GF (một trăm tỷ phép tính dấu phảy
động trên một giây). Như vậy người ta có phân tích bài toán để thực hiện
việc tính toán song song rất có hiệu quả, đặc biệt đối với những bài
toán có độ phức tạp tính toán lớn.
No comments:
Post a Comment