ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Trình bày Hệ mã hóa
Merkle – Hellman (Knapsack)
GV hướng dẫn: PGS.TS Trịnh Nhật Tiến
Học Viên : Phạm Thị Chanh
MSSV : 12025046
Hà Nội 2013
Bài tiểu luận
Trình bày về Hệ mã hóa Merkle - Hellman (Knapsack):
+ Phương pháp mã hoá Merkle - Hellman. Ví dụ mã hoá Merkle - Hellman.
+ Độ an toàn của mã hoá Merkle - Hellman. Ứng dụng của mã hoá Merkle - Hellman.
+ Chương trình mã hoá Merkle - Hellman (Dùng CT mã nguồn mở hay tự viết CT).
Bài làm
Năm 1978 hai ông Merkle – Hellman đã đề xuất một thuật toán mã hóa mật mã khóa
công khai (PKC – Public Key Cryptosystems) dựa trên bài toán xếp ba lô như sau:
o Cho một tập hợp các số dương s
i
, 1
≤
i
≤
n và một số dương T.
Hãy tìm một tập hợp chỉ số S
⊂
{1, 2, …, n} sao cho
Ts
Si
i
=
∑

, …, x
n
), ta thực hiện phép mã hóa như
sau:
T =
∑
=
n
i
ii
sx
1
(*)
o Việc giải mã là: Cho mã T, vector mang s, tìm các x
i
sao cho thỏa
mãn (*).
Sơ đồ này đã thể hiện một hàm một chiều mà dùng làm sinh mã thì tính toán rõ
ràng hơn nhưng việc giải mã, tức tính hàm ngược của nó là rất khó. Bây giờ ta sẽ tiếp
tục tìm cách dựa vào một cửa bẫy (trapdoor) để việc giải mã có thể làm đuợc dễ dàng
(nếu biết cửa bẫy bí mật).
2
Merkle áp dụng một mẹo dựa trên sử dụng vector mang đặc biệt là vector siêu
tăng (super increasing) như sau.
Một vector là siêu tăng nếu thành phần i+1 là lớn hơn tổng giá trị của các thành
phần đứng truớc nó (1
÷
i). Khi sử dụng một vector siêu tăng làm vector mang thì sẽ
thấy việc tính nguợc, tức là giải bài toán là dễ dàng nhờ một giải thuật tham ăn đơn
giản. Ðiều này đuợc minh họa qua ví dụ bằng số sau.

, x
3
, 1)
• x
3
= 1 T
2
= T
1
– x
3
= 6 – 4 = 2  (x
1
, x
2
, 1, 1)
• x
2
= 1 T
3
= T
2
– x
2
= 2 – 2 = 0  (x
1
, 1, 1, 1)
• x
1
= 0  (0, 1, 1, 1)

)
Begin
For i= n downto 1 do
If T
≥
s
i
then
T = T - s
i
x
i
= 1
else
x
i
= 0
if
∑
=
=
n
i
ii
Tsx
1
then
), ,,(
21 n
xxxx =

ni
≤≤
1
. Dãy
), ,,(
21 n
tttt =
là khóa công khai. Các
giá trị a và p dùng để biến đổi dãy được giữ mật.
 Quá trình tạo Khóa
Alice và Bob muốn trao đổi thông tin mật cho nhau, thì Alice phải thực hiện
quá trình hình thành khóa.
• Alice chọn dãy siêu tăng
( )
n
sss , ,,
21
làm khóa mật
• Chọn một số nguyên tố p, sao cho:
∑
>
n
i
sp
1
và một số nguyên ngẫu
nhiên a gọi là nhân tử sao cho nguyên tố cùng nhau với p và a thỏa mãn
11 −≤≤ pa
.
• Sau đó Alice đi tính khóa công khai

)(mod'
1
pTaT
−
=
2. Alice biết rằng T
’
= s.x nên có thể dễ dàng giải ra được x theo siêu tăng s.
Thuật toán tìm giá trị nghịch đảo theo modulo đồng dư
Việc xây dựng Knapsack với cửa bẫy đòi hỏi phải tính giá trị nghịch đảo của a
theo modulo p. Thuật toán tìm x = a
-1
mod p, sao cho x*a = 1 mod p được gọi là thuật
toán ước số chung lớn nhất mở rộng (GCD). Sở dĩ như vậy là vì trong khi tìm ước số
chung lớn nhất của hai số nguyên n
1
và n
2
, người ta luôn tính các giá trị a, b sao cho
GCD(n
1
, n
2
) = a*n
1
+ b*n
2
.
Từ đó suy ra nếu ta biết (n
1

, n
2
), q = div(n
1
, n
2
),
Cập nhật: n
1
= n
2
, n
2
= r, a
1
= a
2
, b
1
= b
2
, a
2
= a
1
– q*a
2
, b
2
= b

i
sp
1
và a thỏa mãn
11 −≤≤ pa
.
Alice tính ra khóa công khai t = (575, 436, 1586, 1030, 1921 ,569 ,721, 1183,
1570) với
)(mod psat
ii
⋅=
. Sau đó Alice gửi t cho Bob.
6
 Mã Hóa: Khi Bob muốn gửi cho Alice bản tin x = (1, 0, 1, 1, 0, 0, 1, 1,
1). Thì Bob tính bản mã:
∑
=
=
n
i
ii
txT
1
. Khi đó T = 575 + 1586 + 1030 + 721 + 1183
+ 1570 = 6665. Bob gửi T cho Alice.
 Giải Mã: Alice nhận được bản mã T thì Alice thực hiện giải mã trước
tính a
-1
là nghịch đảo của a rồi tính
)(mod'

lưu bằng tay)
9
- Định dạng tập tin khoa cong khai.txt có định dạng như sau: (định dạnh lưu tập tin)
3. Mã Hóa
Chọn nhập từ file hoặc nhập trực tiếp khóa công khai T
10
- Nhập dữ liệu cần mã hóa
Ví dụ : “Bai tieu luan Pham Thi Chanh”
Sau đó chọn vào Mã Hóa
- Sau đó thực hiện lưu lại dữ liệu đã mã hóa thành file (ví dụ đặt tên là Du Lieu Ma
Hoa.txt)
4. Giải mã
11
- Chọn đến tập tin hoặc nhập lại mảng siêu tăng, P, A.
- Chọn đến taạp tin hoặc nhập lại dữ liệu đã được mã hóa. Ở đây chọn 2 tập tin (Tao
Khoa.txt và Du Lieu Ma Hoa.txt)
- Sau đó chọn vào Giải Mã
12
Kết quả giải mã được hiển thị ngay dưới. Kết quả của chương trình giải mã được
thông tin đã gửi đi.
13