[Crypto] Hệ mã Merkle – Hellman

Mục Chính

Giới thiệu
Knapsack Problem
Hệ mã Merkel – Hellman
Lattice Reduction Attack
Lời kết

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 túi balo, hay bài toán người du lịch ). Bài toán Knapsack bắt đầ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ỉ chăm sóc 1 bài toán con của bài toán Knapsack tổng quát, trong đó :

Hạn chế số đồ vật mỗi loại là 0 (không được chọn) và 1 (được chọn).
Không quan tâm đến khối lượng đồ vật.
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):

Bạn đang đọc: [Crypto] Hệ mã Merkle – Hellman
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 thành phần của dãy đều lớn hơn tổng những thành phần 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 minh bạch. Để 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 những bit 1 để tính tổng những thành phần của T sẽ được ciphertext C :

C = 82 + 83 + 373 + 10 = 548

và gửi C cho Alice. Để giải thuật, 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 hoàn toàn có thể kiểm chứng tính đúng đắn của quy trình giải thuật 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ị chức năng :

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.

Xem thêm: 7 phương pháp dạy học tiếng việt theo hướng phát triển năng lực hiệu quả - https://thomaygiat.com

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 vận dụng giải thuật Lattice Reduction trên để tiế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 đó vận 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 thành phần 0 và 1 và thành phần ở đầu cuối là 0 ). LLL Algorithm không phải khi nào cũng tìm được vector mong ước, tuy nhiên trong trong thực tiễn Lattice Reduction Attack khá hiệu suất cao để attack hệ mã Merkle-Hellman .

Ví dụ

Để minh họa cho chiêu thức tiế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 những vector ngắn trong lattice lan rộng ra từ những 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 hoàn toàn có thể tìm hiểu thêm source code cho giải pháp tiến công này ở cuối bài viết .

Lời kết

Có rất nhiều điều tra và 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 những hệ mã bảo đả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 tiễn vì nó được gắn với cái mác “ broken ” .Download sourcecode
Advertisement

Chia sẻ:

Twitter

Facebook

Thích bài này:

Thích

Xem thêm: TOP 5 game tư duy trí tuệ cực hấp dẫn để luyện não

Đang tải ...