Nguyễn Khanh Văn

Bài mở đầu về ATBM Thông tin

HUT-2000

CHƯƠNG 0. BÀI MỞ ĐẦU
Với sự phát triển bùng nổ hiện nay của các kiến trúc hệ thống tin học, đặc biệt là các hệ thống
mạng truyền tin và các hệ thống thương mại điện tử, các vấn đề về an toàn và bảo mật trở nên có
tầm quan trọng thời sự. Trước mục đích chủ đạo của thiết kế hệ thống là làm sao cho hệ thống
được đảm bảo các chức năng làm việc, chạy tốt, ít lỗi và dễ phát triển, dễ kết nối với các hệ thống
khác. Riêng các vấn đề này cũng đủ làm đau đầu các nhà thiết kế, vì thế bảo mật là mối quan tâm
thứ yếu (mặc dù vẫn được nêu cao trong giấy tờ). Tuy nhiên với xu hướng xích lại gần nhau của
cả thế giới, công việc của mỗi cơ sở mỗi doanh nghiệp không còn là việc bếp núc của từng nhà
nữa. Các mạng truyền thông diện rộng đã cho ta mở cửa giao tiếp với bạn bè khắp nơi nhưng
cũng vì thế mà tạo cơ hội cho các hàng xóm thù địch" thường xuyên tìm cách "dòm ngó" và
"quấy phá". Câu hỏi lật ngược bây giờ là liệu một hệ thống có giá trị hay không nếu nó không
được bảo vệ để chống lại đủ mọi loại tấn công và xâm nhập của kể cả kẻ địch bên ngoài lẫn gián
điệp bên trong. Vớ nhiều hệ thống quan trọng, thực sự bài toán bảo mật được đặt lên hàng đầu với
chi phí lên tới 60% chi phí tổng thể. Qua đó chúng ta thấy một nhiệm vụ không xa của kiến thức
nhất định để không lạc hậu trong tương lai.
Chuyên đề này nhằm đưa ra một tiếp cận tổng thể với các khái niệm cơ bản về vấn đề bảo vệ các
hệ thống tin học (HTTH). Đồng thời các kiến thức cụ thể về các lĩnh vực riêng trong an toàn và
bảo mật máy tính (computer securrity) cũng được giới thiệu ở mức cận chuyên sâu; qua đó người
đọc có được một hình dung cụ thể tuy còn chưa đầy đủ toàn diện về các mô hình nghiên cứu. Một
số khái niệm cơ bản mà chúng ta sẽ đề cập tới là mã hoá đối xứng, mã hoá phi đối xứng (khai
công khai), hàm băm, chữ ký điện tử... Các mô hình phát triển hơn sẽ được giới thiệu là giao thức
mật mã (cryptographic protocol), vấn đề trao chuyển khoá, chứng thực (authentication), điều
khiển quyền truy nhập (access control), bức tường lửa (firewall), bảo mật cơ sở dữ liệu, thương
mại điện tử (electronic commerce) và bài toán thanh toán điện tử (electronic payments)... Tuy
nhiên khối lượng này sẽ còn được điều chỉnh tuỳ theo thời gian cho phép. Riêng vấn đề về virus

+ các tài sản cần bảo vệ (asssets).
+ những mối đe doạ (threats).
+ những biện pháp ngăn chặn (control).
hiệu quả của các BPNC được đánh giá qua chi phí (cost) và kết quả thu được.
Tài sản
Hệ thống máy tính là một tập hợp gồm các thành phần của hardwware, software & dữ liệu. Mỗi
thành tố là một tài sản cần bảo vệ. Như vậy tài sản ở đây có thể là thiết bị, chương trình cài đặt và
các dữ liệu làm việc và tích tụ qua thời gian.
Những mối đe doạ:
Có 3 hình thức chính:
+ Phá hoại : trong đó một tài sản nào đó bị làm mất giá trị. Ví dụ như: phá hỏng một thiết bị phần
cứng hay xoá một chương trình cài đặt.
+Can thiệp (interrception): tài sản bị truy nhập trái phép bởi những người không có thẩm quyền.
Ví dụ: nghe trộm trên mạng (wiretapping network), sao chép trái phép. Thông thường rất khó
phát hiện.
+ Sửa đổi: các tài sản bị sửa đổi, đánh tráo trái phép. Ví dụ: sửa đổi dữ liệu trong các CSDL hoặc
đang trên đường truyền qua mạng.
Thiệt hại cho tài sản có thể vô ý hay cố ý. Chẳng hạn thiết bị có thể hỏng do các nguyên nhân
chẳng may như: bụi lâu ngày, sự cố ở nguồn. Thiệt hại cũng có thể do cố ý như: ăn cắp, nắc nối
trộm. Tuy nhiên ở đây chúng ta sẽ chỉ nghiên cứu những thiệt hại do cố ý.


Nguyễn Khanh Văn

Bài mở đầu về ATBM Thông tin

HUT-2000

Thiệt hại đối với phần mềm và dữ liệu có thể dễ dàng phát hiện thông qua việc chương trình treo
khi chạy hoặc dữ liệu hỏng. Tuy nhiên cũng có thể rất khó phát hiện khi đối phương cố tình

liệu.
Mục tiêu và nguyên tắc chung cuả ATBM (an toàn & bảo mật - security)
Ba mục tiêu của ATBM:


Nguyễn Khanh Văn

Bài mở đầu về ATBM Thông tin

HUT-2000

1. Đảm bảo tính bí mật (Cofidentiality): tài sản không thể bị truy nhập trái phép bởi những người
có thẩm quyền.
2. Đảm bảo tính nguyên vẹn (Intergrity): tài sản không thể bị sửa đổi, bị làm giả bởi những người
không có thẩm quyền.
3. Tính sẵn dùng (Availability): tài sản là sẵn sàng để đáp ứng sử dụng cho người có thẩm quyền2
Ba mục đích này thường được ghép viết tắt cho dễ nhớ là CIA. Chú ý rằng thông thường phải có
sự thoả hiệp để cùng đạt được ba mục đích trên một cách cân bằng.
Hai nguyên tắc quan trọng trong việc thiết kế và đánh giá các hệ thống bảo mật:
+ Phải tính đến tất cả các khả năng mà kẻ địch có thể thâm nhập. Kẻ địch thường thử mọi cách có
thể được để hòng thâm nhập phá hoại cho nên không được phép giả sử rằng kẻ sẽ tấn công chỉ ở
một số điểm này mà không ở những chỗ khác, nói cách khác phải đề phòng cả những khả năng
khó tin nhất. Nguyên tắc này làm cho việc thẩm định về bảo mật trở nên rất khó, do tất cả các khả
năng bị phá hoại phải được tính đến.
+ Tài sản phải được bảo vệ cho đến khi hết giá trị sử dụng hoặc hết ý nghĩa mật.
Trên cơ sở các mục đích và nguyên tắc nói trên người ta sẽ thiết kế/ phát triển và đánh giá được
các mô hình và kiến trúc bảo vệ.
Qua phần trình bày có tính dẫn dắt vừa rồi, chúng ta có thể hình dung rằng bài toán ATBM là hết
sức phức tạp, ở đây tất cả các yếu tố đều phải được tính đến để bảo vệ. Trong khi đó bản thân các
hệ thống tin học cần bảo vệ lại hết sức đa dạng và phong phú làm cho các vấn đề cần nghiên cứu


Y
Receiver R

Sender S

Key Z

X=DZ(Y)

Enemy E

Key Z

Đây là mô hình cơ bản của truyền tin bảo mật. Khác với truyền tin thông thường, có các yếu tố
mới thêm vào như là khái niệm kẻ địch ẩn giấu và các pha mã hoá và giải mã đề chống lại.
Sau đây là cơ chế hoạt động cụ thể: Người phát S (sender) muốn gửi một thông tin (message) X
tới người nhận R (receiver) qua một kênh truyền tin (communication channel). Kẻ thù E
(enenmy) có thể trộm để lấy được thông tin X.
S sử dụng một phép biến đổi, tức mã hoá (encryption), lên thông tin X ở dạng đọc được
(plaintext), để chế biến ra một đoạn mã hoá Y (cryptogram), không thể đọc được.
Cryptogram (còn gọi là ciphertext) đã che giấu nội dung của thông tin plaintext.
Khoá (key) là thông số điều khiển của phép biến đổi này. Khoá Z chỉ được biết đến bởi các bên
tham gia truyền tin S và R.
Giải mã (decryption) là quá trình ngược lại cho phép người nhận thu được thông tin ban đầu X từ
đoạn mã hoá Y.
Chú ý: Một quá trình biến đổi không khoá (không phụ thuộc vào một khoá nào cả gọi là một
code. Ví dụ: Morse code, ASCII code.
Luật Kirchoff (1835-1903), một giả thiết cơ bản trong môn mã hoá: Toàn bộ cơ chế mã/giải mã
trừ khoá là không bí mật với kẻ thù.

phép mã hoá).
Trong cipher loại này, khoá chỉ được dùng đúng một lần duy nhất. Vernam tin rằng cipher của
ông là không thể phá được nhưng không thể chứng minh được.
+ Kỷ nguyên của ngành khoa học mã hoá được đánh dấu bởi bài báo của Shannon.
(Commication Theory of secretcy systems, 1949). Công trình này dựa trên một bài báo trước đó
của ông trong đó ông đã sáng lập ra ngành khoa học lý thuyết về thông tin (inforrmation theory).
Sự bùng nổ thực sự trong lý thuyết về mã hoá (Cryptolagy) bắt đầu từ bài báo của Diffie &
Hellman "New directions in cryptography". Các ông này đã chứng tỏ rằng trong truyền tin bí mật,
không nhất thiết là cả hai bên đều phải biêt khoá bí mật (tức bên gửi phải làm cách nào đó chuyển
đựơc khoá cho bên nhận). Hơn nữa họ đã lần đầu tiên giới thiệu khái niệm về chữ ký điện tử
(digital signature).


Nguyễn Khanh Văn

Bài mở đầu về ATBM Thông tin

HUT-2000

CHƯƠNG 1. MỘT SỐ CIPHER CỔ ĐIỂN
Việc nghiên cứu các cipher cổ điển là cần thiết vì các nguyên tắc học được sẽ có thể áp dụng
được trong thiết kế và phân tích các cipher hiện đại.
Monoalphabetic ciphers
Ở đây thuật toán dựa trên phép hoán vị trong một bảng alphabet.
Ví dụ1.1 Đây là một cipher dựa trên một bảng hoán vị của tiếng Anh:
a
b
c
d
e

Ví dụ 1.2 Plainext alphabet là một tập hợp của các xâu nhị phân với độ dài là 3.
Bảng biến đổi:
p.text
000 001 010 011 100 101 110 111
c.text
101 111 000 110 010 100 001 011
Do đó xâu plaintext 100101111 sẽ được mã hoá thành 010100011
Để giải mã một xâu ciphertext tạo ra bởi thuật toán như trên, người nhận được ciphertext cần biết
khóa, do đó yêu cầu một giao thức về trao khoá. Đơn giản nhất việc này có thể làm là người ghi
khoá ra đĩa và chuyển đĩa cho người nhận. Rõ ràng cách làm này đơn giản nhưng không thực tế.
Trong thực tế người ta sử dụng nhiều giao thức phức tạp và tinh vi hơn.
Nếu như kẻ thù không biết được khoá thì liệu chúng có thể đoán được không ? Hiển nhiên là điều
đó phụ thuộc vào số lượng khoá có thể có (độ lớn của không gian khoá có thể có). Nếu kích thước
của bảng alphabet là N thì số khoá có thể là N! =N(N-1)...1 và được tính xấp xỉ theo công thức:
N!  (2πn)1/2(n/e)n
Cho N=26, ta có N!=26!926.
Chú ý rằng, số lượng bit được chuyển mật này được gọi là chiều dài của khoá.


Nguyễn Khanh Văn

Bài mở đầu về ATBM Thông tin

HUT-2000

Ví dụ 1.3 Chiều dài khoá của một cipher loại đang xét là 26*5 bits = số lượng bits yêu cầu để
chuyển đi dòng thứ hai trong bảng chuyển vị trên. (Dòng thứ nhất đã được ngầm định là
ABC..XYZ, nên không cần chuyển).
Chú ý: Không phải tất cả các cipher như trên là che giấu được nội dung của thông tin.
Ví dụ 1.4: Sau đây là một cipher hầu như không làm thay đổi plaintext.

E
F
G
H
...
A
B
C
Additive cipher có thể được biểu diễn thông qua phép cộng đồng dư.
Giả sử ta gán các giá trị từ A-Z với các số 1-25,0
Thế thì một chữ plaintext X có thể mã thành ciphertext Y theo công thức:
Y = X  Z. với Z là giá trị của khoá,  là phép cộng đồng dư 26.
Lấy ví dụ ta dùng mã Xe-da nói trên thì:
D=a 3, E=b 3,... A=x 3, B=y 3, C=z 3
Rõ ràng số lượng khoá có thể dùng được là 25 và số lượng bít cần thiết cho việc chuyển khoá là 5
(24 < 25
I
e
II
t,a,o,i,n,s,h,r
III
d,l
VI
c,u,m,w,f,g,y,p,b
V
v,k,j,x,q,z
Một số các cặp 2 chữ, hoặc bộ 3 chữ liên tiếp hay xuất hiện là;
Th, he, in, an, re, ed, on, es, st, en at, to
The, ing, and, hex, ent, tha, nth, was eth, for, dth.
Chú ý là quan sát trên chỉ đúng với tiếng Anh và như vậy tiếng Việt của chúng ta sẽ có qui luật
khác.


Nguyễn Khanh Văn

Bài mở đầu về ATBM Thông tin

HUT-2000

Sau khi đã có các quan sát như trên, người ta có thể dùng phương pháp đoán chữ và giải mã dựa
trên việc thống kê tần xuất xuất hiện các chữ cái trên mã và so sánh với bảng thống kê quan sát
của plaintext.
Ví dụ 1.8 sau đây sẽ minh hoạ phương pháp này.
Example 0.11 What is the key?
Algorithm: key phrase substitution
YKHLBA JCZ SVIJ JZB TZVHI JCZ VHJ DR IZXKHLBA VSS RDHEI DR YVJV

W
5

C
19
J
29
Q
1
X
17

D
23
K
6
R
11
Y
12

E
12
L
21
S
14
Z
45




Nguyễn Khanh Văn

Bài mở đầu về ATBM Thông tin

HUT-2000

VI = a ?

As
an  s  I

VHZ = a ?e

Ate
are  r  H

JCLI = th?s  i  L, o  D
a
V
k
u

b

c

l


r

i
L
s

j

H I

J

t

z

 Chữ cái đầu là f
b  W, c  X, d  Y
on n
DR = o ?

B

of f
or r

H

ox f,x


Đồng âm

A
I
L
N
O
P
T
E
...

17 11 25 64 2 19 4 31
22 95 14 21 79 54
12 93 71

64 7 8 47 ... (15 đồng âm)
...

Như vậy có thể thấy đây là một bảng biến đổi từ chữ tin sang đồng âm mã.
Tin
Mã

P
27

l
12

A



Nguyễn Khanh Văn

Bài mở đầu về ATBM Thông tin

HUT-2000

Xét một hệ mã đơn giản với bảng chữ plaintext alphabet:{a,b,c,d}
Giả sử tần xuất xuất hiện của mỗi chữ như sau:
Pa = 0.5, Pb =0.05, Pc = 0.2, Pd = 0.25
Ta dùng hai bảng thế và một chuỗi khóa để quyết định thứ tự hòa trộn hai bảng thế này.
Bảng thế 1
a
B

b
D

C
A

d
C

P.text alphabet
C. text alphabet

Bảng thế 2
P.text alph

BBB
CBAB

da
21
AB

ca
21
CB

baa
212
BBD

Ở ví dụ trên người ta đã hoà trộn hai bảng thế liên tục kế tiếp nhau. Nhờ đó Phân bố tần xuất xuất
hiện của các chữ mã sẽ bị thay đổi so với tin và bằng phẳng hơn.
Mã đa bảng thế (polyalphabetic cipher)
Trong thể loại này, người ta dùng nhiều bảng thế theo phương pháp vừa g/t trên.
Sau đây là một ví dụ về một cipher cổ điển nổi tiếng. Vigenere cipher
Vigenere cipher
Trong Vigenere Cipher, người ta dùng tất cả 26 bảng thế là sự thu được từ bảng gốc chữ cái tiếng
Anh mà dịch đi từ 0-25 vị trí. Sự hoà trộn này có quy luật hoàn toàn xác định bởi khoá. Mỗi chữ
của khoá sẽ xác định mỗi bảng thế được dùng.

0
1
2
3
4


c
C
D
E
F
G
H
I

d
D
E
F
G
H
I
J

e
E
F
G
H
I
J
K

F
F

M
N
O

j
J
K
L
M
N
O
P

k
K
L
M
N
O
P
P

l
L
M
N
O
P
Q
R

R
S
T
U
V
W

r
R
S
T
U
V
W
X

s
S
T
U
V
W
X
Y

T
T
U
V
W


C
D

D
E

E
F

F
G

G
H

H
I

I
J

J
K

K
L

L M N
M N O


I
E
M

o
b
P

r
r
I

a
e
E

o
O
P
Q
R
S
T
U

d
a
D


(k=1,2,3 ... ; i=0,p-1), tức là được mã hoá theo bảng thế với chữ khoá [i].
3. Dùng phương pháp một bảng thế đã biết để giải từng đoạn phân mã
Người ta sử dụng khái niệm IC (Index of Coincidence) để tính chu kỳ p.
Theo định nghĩa, IC xác định qua công thức:
25i=0 fi (fi-1)
IC = ----------------n(n-1)
Trong đó là xác xuất của phép thử - nhặt ra 2 con chữ ngẫu nhiên bất kỳ từ trong một đoạn văn
bản - để thu được cùng một chữ  cho trước.
Số bảng thế (p)

1

2

3

4

5

...

10

IC

0.068

0.052


b z t

Z:
Y:

A
Y

s u n ny
GOI I G

d a y
FA S


Nguyễn Khanh Văn

•

•
•
•

Bài mở đầu về ATBM Thông tin

HUT-2000

Đề xuất bởi G. Vernam (1917), sau đó được chứng mình là có perfect secretcy (1949)
– “One-time pad”: khóa viết trên 1 băng (tape) dài, sử dụng đúng 1 lần
– Chuỗi khóa là chuỗi ngẫu nhiên

b

c

d

e

f

g h

i

j

k

l

m n o p q

r

s

t

u v w x y



l

m n o p q

K T

r

s

t

A

u v w x y

z

F

E

MÃ:

A

Z

N


y

p

l

a

y

TIN 2:

r

e

d

b

l

u

e

c

a


y

P.text2:

c

a

k

e

P.text3:

m

i

s

t

P.text4:

W

a

s


Z

r

s

t

H

u v w x y

z

Z

K
L

H

K Z

Qua các ví dụ 12 và 13 có thể thấy được rằng đối với monalphabetic, khi MÃ còn tương đối ngắn
thì luôn luôn tồn tại cùng lúc nhiều đoạn TIN có nghĩa mà có thể mã hoá thành mã đang xét được
(tất nhiên là khoá dự đoán tương ứng). Tuy nhiên với MÃ có độ dài trên 50 trở lên thì sẽ chỉ có
duy nhất một plaintext thoả mãn, tức chính nó là TIN cần tìm. Như vậy, nếu như E – nhà phân
tích giải phá mã (cryptanalyst) – “tóm” được một đoạn MÃ có độ dài đủ lớn, thì nói chung luôn
luôn có thể phá được mã loại 1-bảng thế này.


0.070
0.257
0.003

0.427

0.182


Nguyễn Khanh Văn
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5

0.28
0.010
0.024
0.002
0,020
0.001
0.082
0.015
0.028
0.043
0.127
0.022
0.020
0.061
0.070
0.002
0.008
0.040
0.024
0.067
0.075
0.019
0.001

HUT-2000

0.052
0.128

0.001


Lý thuyết về bí mật tuyệt đối.
Trong hệ thống đảm bảo bí mật tuyệt đối, mã dù bị tiết lộ cho kẻ thù cũng không hề đem lại một ý
nghĩa nào. Nó không làm thay đổi phân phối xác xuất ban đầu của plaintext.
Hay là, một hệ thống là có bí mật tuyệt đối nếu:
P(X) = P(X/Y)  TIN X VÀ MÃ Y
Định lý Shannon:
Trong hệ thống có BMTĐ, số lượng khoá có thể (độ lớn không gian khoá) phải lớn hơn hoặc
bằng số lượng thông báo có thể (độ lớn không gian TIN). Điều này cho thấy để đạt được BMTĐ
thì khoá phải rất dài, do đó việc trao chuyển khoa giữa hai bên truyền tin sẽ làm cho hệ thống trở
nên phi thực tế.
Như vậy, nhìn chung chúng ta không thể đạt được an toàn và bảo mật vô điều kiện mà chỉ có thể
có được các hệ thống với mức an toàn thực tế (Practical security) được cài đặt tuỳ theo giá trị của
thông tin cần bảo vệ và thời gian sống của nó.
Đánh giá mức độ bảo mật của một cipher.
Shannon đưa ra một khái niệm, unicity distance, để “đo” mức security của một hệ thống: Unicity
distance, ký hiệu N0, là số ít nhất các chữ mã “cần tóm được” để có thể xác định được khóa đúng
duy nhất. Unicity distance có thể được tính theo công thức:
log 2 E
d
Trong đó d là độ dư thừa của ngôn ngữ sử dụng của TIN.
N0 

Ví dụ 1.15. Câu tốc ký sau đây thực tế có thể “khôi phục” được về dạng đầy đủ một cách duy
nhất:
Mst ids cn b xprsd n fwr ltrs, bt th xprsn s mst nplsnt  Most ideas can be expressed in fewer
letters, but the expression is most unpleasant.
Điều này chứng tỏ những chữ đã bị mất trong câu ban đầu là dư thừa về mặt thông tin.
Khái niệm độ dư thừa có thể được định nghĩa thông qua công thức:
d = R - r bits

Ví dụ 1.19. Với mã one-time-pad:
X = không gian khóa = {tập hợp các đoạn văn bản tiếng Anh có độ dài k}
Z = không gian khóa = {tập các chuỗi chữ độ dài k trông bảng chữ cái tiếng Anh}
Giả thiết các khóa được chọn một cách ngẫu nhiên với xác xuất đồng nhất
N0 = log2E/d
E= 26k log2(26k) = k log2264.7k
N0 = (4.7k)/3.7 = 1.37k
Do đó, thậm chí nếu E nghe trộm toàn bộ tất cả các chữ cái của đoạn MÃ, cô ta vẫn không thể
giải phá mã (tìm được TIN tương ứng duy nhất).
Ta có thể “tăng” tính mật của một hệ mã cho trước hay không?
1. Tăng độ lớn không gian khóa
2. Giảm tính dư thừa của ngôn ngữ văn bản TIN: tiền xử lý qua 1 bước thuật toán nén
Chú ý: một thuật toán nén lý tưởng có thể đem lại độ dư thừa 0, do đó N0  0
3. Có thể chèn thêm một đoạn văn bản ngẫu nhiên để “phẳng hóa“ độ thị tần xuất của văn
bản TIN. Ta sẽ xét cụ thể biện pháp này dưới đây

M
Văn bản TIN gốc

L
Chuỗi ngẫu nhiên chèn

Công thức sau cho biết độ dư thừa của văn bản mới (sau khi chèn thêm chuỗi ký tự ngẫu nhiên)
~
M
d
d 
LM



KAC

KBC
C

Điểm yếu của hệ mã đối xứng là:
Vấn đề quản lý khoá (Tạo, lưu mật, trao chuyển ...) là rất phức tạp và càng ngày càng
khó khi sử dụng trong môi trường trao đổi tin giữa rất nhiều người dùng. Với số lượng
user là n thì số lượng khoá 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
khoá 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à không
an toàn khi n tăng lớn.
Vấn đề thứ hai là trên cơ sở mã đối xứng, không thể thiết lập được khái niệm chữ ký
điện tử (mà thể hiện được các chức năng của chữ ký tay trong thực tế) và cũng do đó
không có dịch vụ non-repudiation 1 (không thể phủ nhận được) cho các giao dịch
thương mại trên mạng.
Vấn đề là ở chỗ trong mã hoá với khoá bí mật, thông tin mật đều được chia sẻ chung bởi cả
hai bên Alice và Bob, do đó Alice có thể làm được bất kỳ cái gì mà Bob làm và ngược lại
(chữ ký ở đây là mã hoá của tài liệu theo khoá đối xứng và do đó cả hai bên đều có thể tạo
được, tức là không thoả mãn tính một chủ duy nhất như chữ ký tay thường). Giải pháp duy
nhất cho vấn đề này là phải có thêm một thành phần thứ ba trong bất cứ giao dịch nào giữa
1

Dịch vụ non-repudiation cho phép trong mọi trường hợp của một quá trình giao dịch giữa hai bên Alice (A
và B(Bob), mỗi bên đều có bằng chứng để chứng gian những trường hợp phía bên kia chối bỏ một giao dịch
nào đó, chẳng hạn như Alice có thể cãi lấy cớ là một kẻ nào khác mạo nhận là mình để tiến hành giao dịch x
nào đó với Bob từ trước.

Chương III - 1 -



thông tin với khoá CK (ZA) của A rồi gửi đi. Chỉ có A mới có thể khoá riêng để giải mã
(zA) và đọc được tin, E dù có nghe trộm cũng không thể giải mã để lấy được tin vì không
có khoá zA.
Còn (2) sẽ được sử dụng để xây dựng các hệ chữ ký điện tử như sau này ta sẽ nghiên cứu
(Ký bằng E(ZA) và kiểm định bằng D(zA) ).
Hệ mã theo nguyên tắc nói trên được gọi là hệ mã với khoá công khai (public key
cryptosystems - PKC) hay còn được gọi là mã phi đối xứng (asymmetric key
cryptosystems).
Nguyên tắc cấu tạo một hệ PK (trapdoor)

Một hệ mã PKC có thể được tạo dựng trên cơ sở sử dụng một hàm kiểu one - way (1
chiều). Một hàm f được gọi là one-way nếu:
1. Đối với mọi X tính ra Y = f(X) là dễ dàng.
2. Khi biết Y rất khó để tính ra X.
Ví dụ. Cho n số nguyên tố p1, p2, ...pn ta có thể dễ dàng tính được N = p1 * p2 * ... * pn, tuy
nhiên khi biết N, việc tìm các thừa số nguyên tố của nó là khó khăn hơn rất nhiều, đặc biệt
là khi N lớn và các thừa số nguyên tố của nó cũng lớn.

Chương III - 2 -


Nguyễn Khanh Văn

Mật mã và An toàn Thông tin

ĐHBKHN-2000

Chúng ta cần một hàm one-way đặc biệt mà có trạng bị một trap door (cửa bẫy), sao cho
nếu biết trap- door này thì việc tính X khi biết f(X)( tức là đi tìm nghịch đào của f) là dễ
dàng, còn ngược lại thì vẫn khó như thường.

Việc giải mã là: Cho mã T, vector mang a, tìm các Xi sao cho thoả mãn (*).
Trong sơ đồ này thể hiện một hàm one-way với việc sinh mã rất dễ dàng nhưng việc giải
mã là rất khó. Bây giờ ta phải tìm cách xây dựng một trapdoor để việc giải mã có thể làm
được dễ dàng.
Merkle sử dụng một mẹo là áp dụng một vector mang đặc biệt là vector siêu tăng (superincreasing), trong đó thành phần i+1 là lớn hơn tổng giá trị của các thành phần đứng trước
nó (1÷i). Khi đó việc giải mã có thể diễn ra dễ dàng như ví dụ bằng số sau:
Ví dụ:
Chương III - 3 -


Nguyễn Khanh Văn

Mật mã và An toàn Thông tin

ĐHBKHN-2000

Vector mang siêu tăng: a=(1,2,4,8)
Cho T=14, ta sẽ thấy việc tìm X=(X1,X2,X3,X4) sao cho T= ∑ aiXi là dễ dàng:
Đặt T=T0
X4=1 T1=T0-X4=6 Î (X1 X2 X3 1)
X3=1 T2=T1-X3=2 Î (X1 X2 1 1)
X2=1 T3=T2-2=0
Î (X1 1 1 1)
X1= 0
Î (0 1 1 1)
Bài toán được giải quyết dần qua các bước. Ở bước i, tổng đích là Ti (tức là phải tìm các aj
để tổng bằng Ti). Ta đem so sánh Ti với thành phần lớn nhất trong phần còn lại của vector,
nếu lớn hơn thì thành phần này được chọn tức là Xi tương ứng bằng 1, còn ngược lại thì Xi
tương ứng bằng 0. Sau đó tiếp tục chuyển sang bước sau với Ti+1 = Ti-Xi.
Mặc dù ta đã thấy vector siêu tăng cho phép giải mã dễ dàng nhưng tất nhiên nó chưa thể


ĐHBKHN-2000

Như vậy chúng ta đã xem xét xong sơ đồ cụ thể của Merkle-Hellman về một hệ PKC dựa
trên bài toán đóng thùng.
Brute Force Attack (tấn công vũ phu)
Với những kẻ không biết trapdoor (a’, m, ω), giải mã đòi hỏi phải tìm kiếm vét cạn qua 2n
khả năng của X.
Sự đổ vỡ của giải pháp dùng Knapsack (1982-1984).
Shamir-Adleman đã chỉ ra chỗ yếu của GP này bằng cách đi tìm 1 cặp (ω’,m’) sao cho nó
có thể biến đổi ngược a về a’ (từ Public key về Private key).
1984, Brickell tuyên bố sự đổ vỡ của hệ thống Knapsack với dung lượng tính toán khoảng
1 giờ máy Cray -1, với 40 vòng lặp chính và cỡ 100 trọng số.
Thuật toán tìm giá trị nghịch đảo theo modul đồ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 ω theo modul
m. Thuật toán tìm x = ω-1 mod m, sao cho x.ω = 1 (mod m) được gọi là thuật toán GCD
mở rộng hay Euclide mở rộng (GCD - Greatest common divior - ước số chung lớn nhất).
Sở dĩ như vậy là vì trong khi đi tìm ước số chung lớn nhất của hai số nguyên n1 và n2,
người ta sẽ tính luôn các giá trị a,b sao cho GCD(n1, n2) = a.n1 + b.n2.
Từ đó suy ra nếu ta đã biết (n1,n2)=1 thì thuật toán này sẽ cho ta tìm được a, b thoả mãn
a.n1+b.n2=1, tức là n1 chính là nghịch đảo của a theo modulo n2 (tức là m)
Sau đây là sơ đồ thuật toán và ví dụ bằng số
Start

n1, n2
n1>0
Initialization:
a=1, b1=0
a2 = 0, b2 = 1