MỤC LỤC
LỜI NÓI ĐẦU
Trong thời đại công nghệ số phát triển nhanh chóng và ngày càng đa
dạng, con người giảm bớt được rất nhiều công việc cần phải thực hiện thủ công
như trước đây, nhưng bên cạnh đó, yêu cầu bảo mật khi tiến hành truyền thông
tin đặc biệt là những thông tin quan trọng trên mạng càng vô cùng cần thiết,
không thể thiếu.
Ngày nay, vấn đề không dừng lại ở việc bảo vệ thông tin mà còn là những
vấn đề cấp bách, mang tính sống còn trong thời đại mất thông tin là mất tất cả,
thông tin càng cần phải bảo mật, do đó càng có nhiều hơn những phương pháp
bảo mật, giúp con người cảm thấy an toàn trong các giao dịch truyền tin qua
- 1 -
mạng, một mạng lưới rộng lớn nhưng không an toàn nếu không có những biện
pháp bảo vệ thông tin hợp lý, đầy đủ.
Một trong những biện pháp bảo mật thông tin của mình gửi đi, đảm bảo
không lộ thông tin ra ngoài đó là mã hóa thông tin để chỉ có người có được khóa
để giải mã mới có thể xem được thông tin, cũng như các hệ mã hóa càng ngày
càng phát triển để người ngoài không thể dễ dàng giải được mã có được chìa
khóa giải mã được thông tin.
1. Giới thiệu chung
1.1. Hệ mã khóa bất đối xứng ( khóa công khai)
Hệ mã hóa đối xứng và hệ mã hóa bất đối xứng là hai hệ mã hóa
phổ biến trong hệ thống bảo mật an toàn thông tin.
Hệ thống đối xứng( hệ mã hóa bí mật) do hai bên gửi và nhận có
vai trò như nhau khi thực hiện sử dụng chung một khóa bí mật. Tuy nhiên
các hệ mã hóa đối xứng có những nhược điểm cơ bản như sau:
• Vấn đề quản lý khóa( tạo, lưu mật, trao quyền…) là rất phức tạp
trong khi sử dụng trong môi trường trao đổi thông tin giữa rất nhiều
người dùng. Với số lượng người dùng là n thì số lượng khóa cần
tạo lập là n(n-1)/2. Mối người dùng phải tạo và lưu n-1 khóa bí mật
để làm việc với n-1 người khác trên mạng. Như vậy rất khó khăn và

công khai đầu tiên được phát minh bởi Ralph Merkle và Martin Hellman
trong năm 1978.Hệ mã hóa khóa công khai này được coi là đơn giản hơn
hệ mã hóa RSA. Tuy nhiên hệ mã hóa này đã bị phá bỏ và hiện tại không
còn được sử dụng.
Hệ mã hóa Merkle–Hellman là hệ mã hóa bất đối xứng, trong đó có
2 khóa : khóa công khai và khóa bí mật. Hơn nữa không giống như RSA,
nó là một chiều: khóa công khai dùng để mã hóa và khóa bí mật dùng để
giải mã. Do đó ta không thực hiện xác thực bằng hệ mã hóa này giống
như hệ mã hóa RSA.
2. Mã hóa và giải mã MHK
2.1. Ý tưởng của hệ mã hóa
Xuất phát từ việc giải bài toán : Làm thế nào đặt các đồ vật vào ba
lô sao cho tổng giá trị của nó là lớn nhất có thể và tổng khối lượng không
được lớn hơn 15kg?
- 4 -
Việc giải bài toán sẽ được áp dụng với thuật toán giải mã trong hệ
mã hóa MHK. Bài toán giải quyết vấn đề này là một vấn đề khó, chưa có
cách nào tối ưu hơn thuật toán vét cạn, do đó Merkel đã áp dụng một mẹo
nhỏ để có thể giải quyết bài toán một cách dễ dàng hơn, nhờ vào thuật
toán tham ăn, vì việc tính ngược sẽ trở lên dễ dàng hơn.
• Vector siêu tăng
Vector siêu tăng là vector tuần tự a= (a
1,
a
2,…
a
j,…
a
n
) sao cho

2,
x
3,
1)
x
3
= 1 T
2
= T
1
– x
3
= 2 => x =(x
1,
x
2,
1
,
1)
x
2
= 1 T
3
= T
2
- x
2
= 0 => x =(x
1,
1

gồm 2 khóa, khóa công khai để mã hóa, khóa bí mật để giải mã. Do đó
việc đầu tiên cần thực hiện là tạo được 2 khóa công khai và bí mật này.
Khóa công khai, người dùng công khai trên mạng để người cần chuyển tin
dùng khóa công khai này cùng với thông điệp cần chuyển mã hóa thành
bản mã để chuyển cho người dùng cần chuyển. Người này nhận bản mã
dùng khóa bí mật để giải mã, lấy được thông điệp đã được chuyển tới
mình.
- 5 -
Công việc tạo mã gồm 3 bước :
o Bước 1 : Chọn vector siêu tăng a= (a
1,
a
2,…
a
j,…
a
n
) ( trong đó n là
số bit trong bản rõ cần mã hóa và giải mã là n bit).
o Bước 2 : Chọn một số nguyên dương q >Σ a
i
và số nguyên
dương r là số nguyên tố cùng nhau với q; r<q
o Bước 3 : tính khóa công khai là vector β (β
1,
β
2…,
β
j,….
β

khai nhân với bản mã( n bit tương ứng) .
T = Σ β
i
* X
i
Việc mã hóa của thuật toán là tương đối dễ dàng, đầu tiên, ta chỉ cần biểu
diễn thông điệp dưới dạng n bit dựa trên khóa công khai số bit được biểu
diễn bằng số lượng trong khóa công khai được người đó công khai trên
mạng. Sau đó lấy từng bit tương ứng này nhân với khóa công khai ta có
được bản mã sau khi mã hóa. Bản mã này sau khi được mã hóa xong sẽ
được gửi đến cho A để A dựa vào khóa bí mật của mình tiến hành giải mã.
- 6 -
• Ví dụ : Tạo mã hóa cho thông điệp hello với khóa công khai như
trên ví dụ phần tạo mã.
Ta biểu diễn từng chữ cái trong từ thành 7 bit :
 h = 1001000
 e = 1100101
 l = 1101100
 o = 1101111
Khóa công khai là β =( 30, 50, 150, 250, 101, 222, 55)
Ta tính được :
 T
h
=1*30 + 1* 250 =280
 T
e
=30 +50 +101 + 55 = 236
 T
l
= 30+50+250 +101 = 431

x
4
< 28 -> x
4
= 1 T = 3
x
1
= 3 => x
1
= 1
Vậy ta có biểu diễn dưới dạng 7 bit là 1001000
Tương tực với các số khác trong bản mã thì ta se giải mã
được thông điệp.
3. Đánh giá hệ mã khóa MHK
Ban đầu, với những người không biết khóa bí mật ( a, q,r) muốn giải
mã phải thực hiện thuật toán vét cạn qua 2
n
khả năng của X, vì vậy với n
đủ lớn thì việc tìm kiếm theo thuật toán vét cạn được gọi là bất khả thi do
đó nó được gọi là khá an toàn.
Nhưng việc tìm kiếm giải mã theo kiểu vét cạn không phải là cách duy
nhất. Năm 1982, Shamir- Adleman đã chỉ ra chỗ yếu của giải pháp này
bằng cách đi tìm một cặp (r, q) sao cho có thể biến đổi ngược β về a ( tính
được khóa bí mật từ khóa công khai). Năm 1984, Brickell tuyên bố sự đổ
vỡ của hệ thống Knapsack với dung lượng tính toán khoảng một giời máy
Cray-1 với 40 vòng lặp chính và cỡ 100 trọng số.
- 8 -
KẾT LUẬN
Hệ mã hóa MHK mặc dù hiện tại không còn được sử dụng trong thực tế vì
tính bảo mật kém cũng như dễ dàng có thể tìm được khóa của bài toán. Nhưng