Các bước cơ bản để tiến hành thám mã

15:34 | 19/12/2011 | GP MẬT MÃ
Bài báo này trình bày các bước cơ bản của quá trình thám mã truyền thống nhằm nêu ra những khó khăn, phức tạp trong quá trình phân tích mật mã. Nội dung này cũng giúp các nhà lập mã thấy được những sơ suất có thể bị các nhà thám mã lợi dụng và từ đó có biện pháp khắc phục.

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 mã pháp, có cùng một loại khoá mã. Mặc dù chúng ta chưa biết được mã pháp (phương pháp mã hoá) của các bức điện đó, nhưng chúng vẫn phân loại (phân lớp) đượ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 lớp các đối tượng. Ý tưởng của bài toán phân lớp 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 lớp là bé nhất có thể được. Để thực hiện việc phân lớp 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 lớp.

Bước 2 : Xác định mã pháp
Sau khi hoàn thành việc phân lớp  (phân loại mã pháp) ở 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 mã pháp đố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à  thám mã).  Đây là một khâu rất quan trọng của công tác thám 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 mã pháp nào. Ở đây chúng ta chỉ trình bày cách thức xác định mã pháp đố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 mã pháp 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 mã pháp.
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 mã pháp 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 mã pháp 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 thám mã đột phá thành công.
Bước 3. Thám mã
Giả sử đã xác định được mã pháp tại bước thứ 2 trên đây, nay chuyển sang nghiên cứu, phân tích bản mã (thám mã). Bước này cũng có hai công đoạn:
a) Thám trực tiếp
Nếu mã pháp thuộc loại truyền thống đã biết như các mã pháp 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 thám thì có thể tiến hành thám 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 thám
Nếu mã pháp 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 thám 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à “vét cạn”. Đố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 vét cạn 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 “vét cạn” 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 hoạch 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 vét cạn trên tập con có chứa khoá đúng, khi đó việc “vét cạn” 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 thám 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 cực 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 rã bài toán để thực hiện việc tính toán song song cực kỳ 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.

Tin cùng chuyên mục

Tin mới