[Crypto] Hệ Mã Merkle – Hellman - Nhat Truong Blog

Giới thiệu

Hệ mã Merkle – Hellman thuộc nhóm Public key Cryptosystem, dựa vào bài toán Knapsack (bài toán xếp ba lô, hay bài toán người du lịch). Bài toán Knapsack ban đầu được phát biểu như sau:

Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là M. Vậy kẻ trộm nên bỏ vào ba lô những món nào và số lượng bao nhiêu để đạt giá trị cao nhất trong khả năng mà hắn có thể mang đi được. Ta có n loại đồ vật, x0 tới xn-1. Mỗi đồ vật xi có một giá trị pi và một khối lượng wi. Khối lượng tối đa mà ta có thể mang trong ba lô là X. Ta cần cực đại hóa tổng pi * xi sao cho wi * xi < X.

Bài toán Knapsack có nhiều biến thể. Ở đây ta chỉ quan tâm 1 bài toán con của bài toán Knapsack tổng quát, trong đó:

1. Hạn chế số đồ vật mỗi loại là 0 (không được chọn) và 1 (được chọn).
2. Không quan tâm đến khối lượng đồ vật.
3. Ràng buộc giá trị: Tổng giá trị đồ vật phải bằng với 1 giá trị cho trước X.

Trong trường hợp này, bài toán tương đương với bài toán tổng các tập con (subset sum problem):

Cho một tập các số nguyên, tồn tại hay không một tập con có tổng đúng bằng X?

Từ đây, khi nói đến Knapsack Problem, tôi muốn đề cập đến bài toán subset sum problem.

Knapsack Problem

Cho dãy trọng số W = (w0,w1,...,wr-1) và tổng X. Tìm dãy x = (x0,x1,...,xr-1) với xi ∈ {0,1} sao cho:X = x0w0 + x1w1 + ... + xr-1wr-1

Ví dụ cho W = (4,3,9,1,12,17,19,23) và X = 35.

Một đáp án của bài toán là x = (01011010) vì:

0x4 + 1x3 + 0x9 + 1x1 + 1x12 + 0x17 + 1x19 + 0x23 = 35

Ta định nghĩa một dãy trọng số W là siêu tăng (superincreasing knapsack) nếu mỗi phần tử của dãy đều lớn hơn tổng các phần tử phía trước nó. Ví dụ:

W = (2,3,6,13,29,55,112,220) là 1 dãy siêu tăng.

Việc giải bài toán knapsack tổng quát với dãy W tùy ý là rất khó, trong khi bài toán knapsack siêu tăng lại có thể giải dễ dàng, ví dụ với dãy W như trên và X = 76. Vì X < 112 nên x7 = x6 = 0. Vì X > 55 và 2+3+6+13+29 < 55 nên ta phải có x5=1, vì nếu x5=0 ta không thể đạt được tổng X = 76. Đặt X1 = X-55 = 21. Vì 13 < X1 < 29 nên x4 = 0 và x3 = 1. Tiếp tục như vậy ta sẽ tìm được đáp án là x = (10110100)

Hệ mã Merkel – Hellman dựa trên độ khó của việc giải bài toán knapsack tổng quát.

Hệ mã Merkel – Hellman

Hệ mã Merkel – Hellman là loại mã bất đối xứng, hay mã khóa công khai. Để tạo Public Key và Private Key, Alice cần:

• Chọn một dãy siêu tăng S = (s0,s1,...,sr-1)
• Chọn một số m và modul n sao cho gcd(m,n) = 1 và n lớn hơn tổng các phần tử của S.
• Tính k = m-1 (mod n)

Trong đó m-1 (mod n) là modul nghịch đảo của m theo modul n.

Sau đó Alice tính dãy T như sau:

T = (s0m (mod n), s1m (mod n), ...,sr-1m (mod n))

T sẽ là Public Key, và Private Key bao gồm S, m, n, k.

Nếu Bob muốn gửi 1 tin nhắn M cho Alice. Bob chuyển M thành dãy bit B có chiều dài r. Sau đó dùng các bit 1 của B để chọn các phần tử của T, tính tổng các phần tử này sẽ được ciphertext C. Để mã hóa tin nhắn dài hơn, Bob chia message thành từng khối bit có chiều dài  r và mã hóa từng khối một.

Ví dụ, Alice chọn Private Key:

• S = (2,3,7,14,30,57,120,251)
• m = 41 và modul n = 491
• k = m-1 (mod n) = 41-1 (mod 491) = 12

Dùng cách tính đã định nghĩa, Alice tính được Public Key:

T = (82,123,287,83,248,373,10,471)

Giả sử Bob muốn mã hóa tin nhắn M = 150 để gửi cho Alice. Bob chuyển 150 thành dãy bit 10010110. Dùng các bit 1 để tính tổng các phần tử của T sẽ được ciphertext C:

C = 82 + 83 + 373 + 10 = 548

và gửi C cho Alice. Để giải mã, Alice dùng Private Key của mình để tính:

C.k (mod n) = 548 x 12 (mod 491) = 193

Sau đó, Alice giải bài toán superincreasing knapsack cho dãy S với X = 193 và phục hồi được dãy x = 10010110, khi chuyển sang số thập phân sẽ được plaintext M = 150.

Bạn đọc có thể kiểm chứng tính đúng đắn của quá trình giải mã trong ví dụ trên như sau:

548k = 82k + 83k + 37k + 10k

= 2mk + 14mk + 57mk + 120mk

= 2 + 14 + 57 + 120 = 193 (mod 491)

Như vậy, nếu attacker Eve không biết Private Key (S, m, k, n), Eve muốn phá mã thì phải tìm được một tập con của T sao cho có tổng bằng C. Đây là bài toán knapsack tổng quát rất khó để giải. Tuy nhiên, năm 1983, Shamir đã chứng minh rằng hệ mã Merkel-Hellman là không an toàn, khi mà Knapsack Problem có thể bị tấn công bằng phương pháp Lattice Reduction Attack được trình bày dưới đây.

Lattice Reduction Attack

Lattice Reduction là một kỹ thuật được ứng dụng để giải nhiều bài toán mã hóa.

Trước hết cần hiểu Lattice là gì? Giả sử ta có 2 vector đơn vị:

Vì c0 và c1 độc lập tuyến tính, bất kỳ điểm nào trong mặt phẳng đều có thể viết dưới dạng α0c0 + α1c1 với α0 và α1 là các số thực. Nếu ta giới hạn α0 và α1 là các hệ số nguyên, ta sẽ thu được 1 lattice gồm tập hợp các điểm trong mặt phẳng như sau:

Tóm lại, lattice L là một bộ gồm tất cả các tổ hợp của vector ci với các hệ số nguyên.

Lattice Reduction

Cho A là ma trận [m x n], B là ma trận [m x 1]. Giả sử ta muốn tìm ma trận U gồm các phần tử 0 và 1 sao cho thỏa mãn phương trình AU = B. Phương trình này có thể viết lại thành:

Trong đó W nằm trong lattice L, tạo thành từ các cột của M.

Năm 1982, Lenstra, Lenstra và Lovasz đã đưa ra giải thuật LLL Algorithm (hay Lattice Reduction Algorithm) cung cấp một phương pháp hiệu quả để tìm vector ngắn nhất trong một lattice, từ đó tìm ra được  vector U.

Năm 1983, Shamir áp dụng giải thuật Lattice Reduction trên để tấn công hệ mã Merkle-Hellman.

Lattice Reduction Attack for Merkle-Hellman CryptoSystem

Giả sử Publick Key của Alice là T = (t0,t1,...,tr-1) và Bob gửi cho Alice 1 ciphertext block T. Vì Attacker Eve biết T và C nên Eve có thể attack nếu Eve giải được phương trình ma trận TU = C trong đó U là một vector cột gồm các phần tử 0 và 1.

Eve viết lại phương trình TU = C thành:

sau đó áp dụng LLL Algorithm với ma trận M. Các vector thu được sẽ được check xem có dạng của W hay không (là một cột gồm r phần tử 0 và 1 và phần tử cuối cùng là 0). LLL Algorithm không phải lúc nào cũng tìm được vector mong muốn, tuy nhiên trong thực tế Lattice Reduction Attack khá hiệu quả để attack hệ mã Merkle-Hellman.

Ví dụ

Để minh họa cho phương pháp tấn công này, ta lấy luôn ví dụ cặp Private Key và Public Key trong phần trước:

Private Key

• S = (2,3,7,14,30,57,120,251)
• m = 41 và modul n = 491
• k = m-1 (mod n) = 41-1 (mod 491) = 12

Public Key

• T = (82,123,287,83,248,373,10,471)

Ciphertext C = 548. Eve muốn attack thì cần tìm được dãy U = (u0,u1,...,ur-1) gồm các phần tử 0 và 1 sao cho TU = C, hay:

82u0 + 123u1 + 287u2 + 83u3 +248u4 + 373u5 + 10u6 + 471u7 = 548

Eve viết lại phương trình dưới dạng MV = W và áp dụng LLL Algorithm cho M.

Giải thuật LLL cho ra ma trận M’, gồm các vector ngắn trong lattice mở rộng từ các cột của M.

Ta thấy cột thứ 4 của M’ có dạng đúng của vector W, đó là 1 đáp án cho bài toán knapsack. Vì vậy Eve thu được:

U = (1,0,0,1,0,1,1,0)

Sử dụng T và C = 548, Eve dễ dàng xác nhận lại U chính là plaintext cần tìm.

Bạn đọc có thể tham khảo source code cho phương pháp tấn công này ở cuối bài viết.

Lời kết

Có rất nhiều nghiên cứu về knapsack problem từ khi hệ mã Merkel-Hellman bị phá vỡ. Có nhiều biến thể của bài toán knapsack tạo ra được các hệ mã an toàn hơn. Tuy nhiên, người ta lại rất ít sử dụng hệ mã này trong thực tế vì nó được gắn với cái mác “broken”.

Download sourcecode

Chia sẻ:

• Twitter
• Facebook

Thích Đang tải...

Có liên quan