MỤC LỤC
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin
CHƯƠNG 1
AN TOÀN DỮ LIỆU TRÊN MẠNG MÁY TÍNH
Ngày nay, với sự phát triển mạnh mẽ của công nghệ thông tin việc ứng dụng các
công nghệ mạng máy tính trở nên vô cùng phổ cập và cần thiết. Công nghệ mạng máy
tính đã mang lại những lợi ích to lớn.
Sự xuất hiện mạng Internet cho phép mọi người có thể truy cập, chia sẽ và khai thác
thông tin một cách dễ dàng và hiệu quả. Các công nghệ E-mail cho phép mọi người có
thể gửi thư cho người khác cũng như nhận thư ngay trên máy tính của mình. Gần đây có
công nghệ E-business cho phép thực hiện các hoạt động thương mại trên mạng máy
tính. Việc ứng dụng các mạng cục bộ trong các tổ chức, công ty hay trong một quốc gia
là rất phong phú. Các hệ thống chuyển tiền của các ngân hàng hàng ngày có thể chuyển
hàng tỷ đôla qua hệ thống của mình. Các thông tin về kinh tế, chính trị, khoa học xã hội
được trao đổi rông rãi.
Tuy nhiên lại nảy sinh vấn đề về an toàn thông tin. Đó cùng là một quá trình tiến
triển hợp logic: khi những vui thích ban đầu về một siêu xa lộ thông tin, bạn nhất định
nhận thấy rằng không chỉ cho phép bạn truy nhập vào nhiều nơi trên thế giới, Internet
còn cho phép nhiều người không mời mà tự ý ghé thăm máy tính của bạn.
Thực vậy, Internet có những kỹ thuật tuyệt vời cho phép mọi người truy nhập, khai
thác, chia sẻ thông tin. Những nó cũng là nguy cơ chính dẫn đến thông tin của bạn bị hư
hỏng hoặc phá huỷ hoàn toàn.
Có những thông tin vô cùng quan trọng mà việc bị mất hay bị làm sai lệch có thể
ảnh hưởng đến các tổ chức, các công ty hay cả một quốc gia. Các thông tin về an ninh
quốc gia, bí mật kinh doanh hay các thông tin tài chính là mục tiêu của các tổ chức tình
báo nước ngoài về chính trị hay công nghiệp hoặc kẻ cắp nói chung. Bọn chúng có thể
làm mọi việc có thể để có được những thông tin quý giá này. Thử tưởng tượng nếu có
kẻ xâm nhập được vào hệ thống chuyển tiền của các ngân hàng thì ngân hàng đó sẽ chịu
những thiệt hại to lớn như mất tiền có thể dẫn tới bị phá sản. Chưa kể nếu hệ thông
thông tin an ninh quốc gia bị đe doạ thì hậu quả không thể lường trước được.
Theo số liệu của CERT(Computer Emegency Response Team - “Đội cấp cứu máy

 Một người dùng chuyển một thông báo điện tử cho một người sử dụng khác. Một
bên thứ ba trên cùng mạng LAN này sử dụng một thiết bị nghe trộm gói để lấy
thông báo và đọc các thông tin trong đó.
 Cũng trong tình huống trên bên thứ ba chặn thông báo, thay đổi các thành phần
của nó và sau đó lại gửi cho người nhận. Người nhận không hề nghi ngờ gì trừ
khi nhận ra thông báo đó là vô lý, và có thể thực hiện vài hành động dựa trên các
thành phần sai này đem lại lợi ích cho bên thứ ba.
 Người dùng log vào một server mà không sử dụng mật khẩu được mã hoá. Một
người khác đang nge trộm trên đường truyền và bắt được mật khẩu logon của
người dùng, sau đó có thể truy nhập thông tin trên server như người sử dụng.
 Một người quản trị hệ thống không hiểu về khía cạnh an toàn và yêu cầu của hệ
thống và vô tình cho phép người dùng khác truy nhập vào thư mục chứa các
thông tin hệ thống. Người dùng phát hiện ra họ có thể có được các thông tin hệ
thống và có thể dùng nó phục vụ cho loựi ích của mình.
GV. Lê Đắc Nhường Trang 3
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin
CHƯƠNG 2
CÁC VẤN ĐỀ CƠ BẢN
Trong phần này sẽ trình bày về một số cơ sở toán học của mã hóa, điều này sẽ giúp
ta nắm được một cách chi tiết hơn về các phương pháp mã hóa.
2.1 Lý thuyết số
2.1.1 Khái niệm đồng dư Modulo
Định nghĩa 1: Giả sử a và b là các số nguyên và m là một số nguyên dương. Khi
đó ta viết a
≡
b(mod m) nếu m chia hết cho b-a. Mệnh để a
≡
b(mod m) được gọi
là “a đồng dư với b theo mođun m”.
Giả sử chia a và b cho m và ta thu được thương nguyên và phần dư, các phần dư

m
được coi là tập hợp {0,1,…,m-1}
có trang bị hai phép toán cộng và nhân. Việc cộng và nhân trong Z
m
được thực hiện
giống như cộng và nhân các số thực ngoại trừ một điểm là các kết quả được rút gọn
theo mođun m.
2.1.2 Định lý về đồng dư thức
Định lí 1: Đồng dư thức ax
≡
b (mod m) chỉ có một nghiệm duy nhất x
∈
Z
m
với
mọi b
∈
Z
m
khi và chỉ khi UCLN(a,m) = 1.
Ta giả sử rằng, UCLN(a,m) = d >1. Khi đó, với b = 0 thì đồng dư thức ax ≡ 0 (mod
m) sẽ có ít nhất hai nghiệm phân biệt trong Zm là x = 0 và x = m/d.
2.1.3 Khái niệm phần tử nghịch đảo
Định nghĩa 2: Giả sử a
∈
Z
m
. Phần tử nghịch đảo (theo phép nhân) của a là phần
tử a
-1

0
= n, r
1
= a,
GV. Lê Đắc Nhường Trang 4
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin
r
0
= q
1
r
1
+ r
2
, 0 < r
2
< r
1
r
1
= q
2
r
2
+ r
3
, 0 < r
3
< r
2

) = …… = (r
m-1,
r
m
) = r
m
Vậy ta tìm được r
m
= (n,a). Mở rộng thuật toán Euclide bằng cách xác định thêm dãy
số t
0
, t
1
,…,t
m
:
t
0
= 0,
t
1
= 1,
t
j
=

t
j-2
–


n
*
có
cấp m, nếu m là số nguyên dương bé nhất sao cho g
m
= 1 trong Z
n
*
.
Theo một định lý đại số, ta có m |
φ
(n) (ký hiệu m là ước số của
φ
(n)) vì vậy với mọi
b ∈ Z
n
*
ta luôn có: b
φ
(n)
≡ 1 (mod n)
Nếu p là số nguyên tố, thì do
φ
(p) = p-1, nên ta có với mọi b nguyên tố với p
b
p-1
≡ 1 (mod p) (1)
Nếu b có cấp p-1, thì p-1 là số mũ bé nhất sao cho có công thức (1), do đó các phần
tử b, b
2

thặng dư bậc hai theo mođun p, nếu phương trình: y
2
≡ x (mod p) có lời giải.
Ta có tiêu chuẩn Euler sau đây: x là thặng dư bậc hai theo mođun p, nếu và chỉ nếu
GV. Lê Đắc Nhường Trang 5








p
a
0 nếu a 0 (mod p)
1 nếu a là thặng dư bậc hai theo mod p
-1 nếu a không là thặng dư bậc hai theo mod p
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin
x
(p-1)/2
≡ 1 (mod p)
Tiêu chuẩn đó được chứng minh như sau: Giả sử có x

≡ y
2
(mod p). Khi đó có:
x
(p-1)/2
≡ (y

a≥0, ta có:
≡ a
(p-1)/2
(mod p).
2.1.7 Một số thuật toán kiểm tra tính nguyên tố
Ta phát biểu một số tính chất sau đây, chúng là cơ sở cho việc phát triển một số
thuật toán xác suất thử tính nguyên tố của các số nguyên.
Solovay_Strassen :
Nếu n là số nguyên tố, thì với mọi 1 ≤ a ≤ n-1:






n
a
≡ a
(n-1)/2
(mod n).
Nếu n là hợp số thì:
|{a: 1 ≤ a ≤ n-1,






n
a

lớn. Lý thuyết về độ phức tạp tính toán được nghiên cứu bắt đầu từ những năm 60 đã bù
đắp cho khoảng trống đó, cho ta nhiều tri thức cơ bản, đồng thời có nhiều ứng dụng
thực tế rất phong phú.
Độ phức tạp (về không gian hay thời gian) của một quá trình tính toán là số ô nhớ
hay số các phép toán được thực hiện trong quá trình tính toán đó.
Độ phức tạp tính toán của một thuật toán được hiểu là một hàm số f, sao cho với
mỗi n, f(n) là là số ô nhớ hay số các phép toán tối đa mà thuật toán thực hiện quá trình
tính toán của mình trên các dữ liệu vào có độ lớn n.
Độ phức tạp tính toán của một bài toán (của một hàm) được định nghĩa là độ phức
tạp của một thuật toán tốt nhất có thể tìm được để giải bài toán (hay tính hàm) đó.
Một bài toán được cho bởi:
• Một tập các dữ liệu vào Y
• Một câu hỏi dạng R(I)? với I ∈ Y, lời giải bài toán là đúng hay không
Ví dụ:
• Bài toán đồng dư bậc hai
o Dữ liệu: Các số nguyên dương a,b,c
o Câu hỏi: Có hay không số x < c sao cho x
2
≡ a mod b ?
• Bài toán hợp số
o Dữ liệu: Số nguyên dương N
o Câu hỏi: Có hay không hai số m,n > 1 sao cho N = m×n ?
2.2.5 Các lớp phức tạp
Ta định nghĩa P là lớp các bài toán có độ phức tạp thời gian là đa thức tức lớp các
bài toán mà đối với chúng có thuật toán giải bài toán đó trong thời gian đa thức.
Một lớp quan trọng các bài toán đã được nghiên cứu nhiều là lớp NP, tức các bài
toán mà đối với chúng có thuật toán không đơn định để giải trong thời gian đa thức.
Thuật toán không đơn định là một mô hình tính toán trừu tượng, được giả định là sau
mỗi bước có thể có một số hữu hạn bước được lựa chọn đồng thời tiếp sau.
Nhiều bài toán được chứng tỏ là thuộc lớp NP, nhưng chưa ai chứng minh được là

khối lượng tính toán trên đòi hỏi một máy tính 1 tỷ phép tính/giây làm việc không
nghỉ trong khoảng 3000 năm)
Hàm f(x) được gọi là hàm cửa sập một phía, nếu tính y = f(x) là dễ, tính x = f
-1
(y) là
rất khó, nhưng có cửa sập z để tính x = f
z
-1
(y) là dễ
Ví dụ: Cho n = p×q là tích của hai số nguyên tố lớn, a là số nguyên, hàm
f(x)=x
a
(mod n) là hàm cửa sập một phía, nếu chỉ biết n và a thì tính x = f
-1
(y) là rất
khó, nhưng nếu biết cửa sập, chẳng hạn hai thừa số của n, thì sẽ tính được f
-1
(y)
khá dễ.
Trên đây là hai thí dụ điển hình, và cũng là hai trường hợp được sử dụng rộng rãi về
hàm một phía và hàm cửa sập một phía. Vì đây là những điểm then chốt của lý thuyết
mật mã khóa công khai, nên việc tìm kiếm các loại hàm một phía và cửa sập một phía
được nghiên cứu rất khẩn trương, và đến nay tuy có đạt được một số kết quả, nhưng
việc tìm kiếm vẫn tiếp tục, đầy hứng thú nhưng cũng đầy khó khăn.
GV. Lê Đắc Nhường Trang 9
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin
CHƯƠNG 3
GIỚI THIỆU VỀ MÃ HÓA
3.1 Các thuật ngữ
Hệ mật mã là tập hợp các thuật toán và các thủ tục kết hợp để che dấu thông tin

Dễ dàng thấy được công việc trên khi sử dụng định nghĩa hệ mật mã :
E
K
( P) = C và D
K
( C ) = P
3.3 Những yêu cầu đối với hệ mật mã
Cung cấp một mức cao về độ tin cậy, tính toàn vẹn, sự không từ chối và sự xác thực.
GV. Lê Đắc Nhường Trang 10
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin
 Độ tin cậy: cung cấp sự bí mật cho các thông báo và dữ liệu được lưu bằng
việc che dấu thông tin sử dụng các kỹ thuật mã hóa.
 Tính toàn vẹn: cung cấp sự bảo đảm với tất cả các bên rằng thông báo còn lại
không thay đổi từ khi tạo ra cho đến khi người nhận mở nó.
 Tính không từ chối: có thể cung cấp một cách xác nhận rằng tài liệu đã đến từ
ai đó ngay cả khi họ cố gắng từ chối nó.
 Tính xác thực: cung cấp hai dịch vụ: đầu tiên là nhận dạng nguồn gốc của một
thông báo và cung cấp một vài sự bảo đảm rằng nó là đúng sự thực. Thứ hai là
kiểm tra đặc tính của người đang logon một hệ thống và sau đó tiếp tục kiểm
tra đặc tính của họ trong trường hợp ai đó cố gắng đột nhiên kết nối và giả
dạng là người sử dụng
3.4 Các phương pháp mã hoá
3.4.1 Mã hoá đối xứng khoá bí mật
Định nghĩa: Thuật toán đối xứng hay còn gọi thuật toán mã hoá cổ điển là thuật
toán mà tại đó khoá mã hoá có thể tính toán ra được từ khoá giải mã. Trong rất nhiều
trường hợp, khoá mã hoá và khoá giải mã là giống nhau. Thuật toán này còn có nhiều
tên gọi khác như thuật toán khoá bí mật, thuật toán khoá đơn giản, thuật toán một
khoá. Thuật toán này yêu cầu người gửi và người nhận phải thoả thuận một khoá trước
khi thông báo được gửi đi, và khoá này phải được cất giữ bí mật. Độ an toàn của thuật
toán này vẫn phụ thuộc và khoá, nếu để lộ ra khoá này nghĩa là bất kỳ người nào cũng

Định nghĩa: Vào những năm 1970 Diffie và Hellman đã phát minh ra một hệ mã
hoá mới được gọi là hệ mã hoá công khai hay hệ mã hoá phi đối xứng.
Thuật toán mã hoá công khai là khác biệt so với thuật toán đối xứng. Chúng được
thiết kế sao cho khoá sử dụng vào việc mã hoá là khác so với khoá giải mã. Hơn nữa
khoá giải mã không thể tính toán được từ khoá mã hoá. Chúng được gọi với tên hệ
thống mã hoá công khai bởi vì khoá để mã hoá có thể công khai, một người bất kỳ có
thể sử dụng khoá công khai để mã hoá thông báo, nhưng chỉ một vài người có đúng
khoá giải mã thì mới có khả năng giải mã.
Trong nhiều hệ thống, khoá mã hoá gọi là khoá công khai (public key), khoá giải mã
thường được gọi là khoá riêng (private key).
Trong hình vẽ trên thì :
K1 không thể trùng K2, hoặc
K2 không thể tính toán từ K1.
Đặc trưng nổi bật của hệ mã hoá công khai là cả khoá công khai (public key) và bản
tin mã hoá (ciphertext) đều có thể gửi đi trên một kênh thông tin không an toàn.
3.4.2.1 Nơi ứng dụng
Sử dụng chủ yếu trên các mạng công khai như Internet khi mà khoá chuyển tương
đối khó khăn.
3.4.2.2 Điều kiện hệ mã hóa khóa công khai
Diffie và Hellman đã xác đinh rõ các điều kiện của một hệ mã hoá công khai như
sau:
1. Việc tính toán ra cặp khoá công khai K
B
và bí mật k
B
dựa trên cơ sở các điều
kiện ban đầu phải được thực hiện một cách dễ dàng, nghĩa là thực hiện trong thời
gian đa thức.
2. Người gửi A có được khoá công khai của người nhận B và có bản tin P cần gửi
đi thì có thể dễ dàng tạo ra được bản mã C.

cho hai người sử dụng (tạm gọi là Alice và Bob) sao cho đối phương (Oscar) không thể
hiểu được thông tin được truyền đi. Kênh này có thể là một đường dây điện thoại hoặc
một mạng máy tính. Thông tin mà Alice muốn gửi cho Bob (bản rõ) có thể là một văn
bản tiếng Anh, các dữ liệu bằng số hoặc bất cứ tài liệu nào có cấu trúc tuỳ ý. Alice sẽ
mã hoá bản rõ bằng một kháo đã được xacs định trước và gửi bản mã kết quả trên kênh.
Oscar có bản mã thu trộm được trên kênh song không thể xác định nội dung của bản
rõ, nhưng Bob (người đã biết khoá mã) có thể giải mã và thu được bản rõ.
Ta sẽ mô tả hình thức hoá nội dung bằng cách dung khái niệm toán học như sau:
Định nghĩa:
Một hệ mật là một bộ 5 (
P,C,K,E,D
) thoả mãn các điều kiện sau:
P là một tập hữu hạn các bản rõ có thể.
C là một tập hữu hạn các bản mã có thể.
K (không gian khoá) là tập hữu hạn các khoá có thể.
Đối với mỗi k∈ K có một quy tắc mã ek: P → C và một quy tắcv giải mã tương ứng
dk ∈ D. Mỗi ek: P → C và dk: C → P là những hàm mà:
d
k
(e
k
(x)) = x với mọi bản rõ x
∈

P.
Trong tính chất 4 là tính chất chủ yếu ở đây. Nội dung của nó là nếu một bản rõ x
được mã hoá bằng e
k
và bản mã nhận được sau đó được giải mã bằng d
k

Kênh an toàn
Nguồn khoá
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin
sẽ được gửi trên kênh. Khi Bob nhận đươc y1,y2 ,. . .,yn anh ta sẽ giải mã bằng hàm
giải mã dk và thu được bản rõ gốc x1,x2 ,. . .,xn. Hình dưới là một ví dụ về một kênh
liên lạc
Hình 3.3. Kênh liên lạc
Rõ ràng là trong trường hợp này hàm mã hoá phải là hàm đơn ánh ( tức là ánh xạ 1-
1), nếu không việc giải mã sẽ không thực hiện được một cách tường minh. Ví dụ
y = ek(x1) = ek(x2)
trong đó x1 ≠ x2 , thì Bob sẽ không có cách nào để biết liệu sẽ phải giải mã thành x1
hay x2 . Chú ý rằng nếu
P
=
C
thì mỗi hàm mã hoá là một phép hoán vị, tức là nếu tập
các bản mã và tập các bản rõ là đồng nhất thì mỗi một hàm mã sẽ là một sự sắp xếp lại
(hay hoán vị ) các phần tử của tập này.
Do các ví dụ của chúng ta xét trên tập dữ liệu là bảng chữ cái nên chúng ta coi bảng
chữ cãi tiếng anh là tập hợp gồm 26 giá trị như bảng bên dưới.
A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12
N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25
3.5.1 Mã dịch vòng
Mã dịch vòng được xác định trên Z
26
(do có 26 chữ cái trên bảng chữ cái tiếng Anh)
mặc dù có thể xác định nó trên Zm với modulus m tuỳ ý. Dễ dàng thấy rằng, MDV sẽ
tạo nên một hệ mật như đã xác định ở trên, tức là dK (eK(x)) = x với mọi x∈ Z

0 19 12 8 3 13 8 6 7 19
sau đó cộng 11 vào mỗi giá trị rồi rút gọn tổng theo modulo 26
7 15 7 19 22 22 23 15 15 4
11 4 23 19 14 24 19 17 18 4
Cuối cùng biến đổi dãy số nguyên này thành các kí tự thu được bản mã sau:
HPHTWWXPPELEXTOYTRSE
Để giả mã bản mã này, trước tiên, Bob sẽ biến đổi bản mã thành dãy các số nguyên
rồi trừ đi giá trịcho 11 ( rút gọn theo modulo 26) và cuối cùng biến đổi lại dãy nàythành
các ký tự.
Nhận xét: Trong ví dụ trên , ta đã dùng các chữ in hoa cho bản mã, các chữ thường
cho bản rõ để tiện phân biệt. Quy tắc này còn tiếp tục sử dụng sau này.
Nếu một hệ mật có thể sử dụng được trong thực tế thì nó phảo thoả mãn một số tính
chất nhất định. Ngay sau đây sẽ nêu ra hai trong số đó:
1. Mỗi hàm mã hoá e
K
và mỗi hàm giải mã d
K
phải có khả năng tính toán được
một cách hiệu quả.
2. Đối phương dựa trên xâu bản mã phải không có khả năng xác định khoá K đã
dùng hoặc không có khả năng xác định được xâu bản rõ x.
Tính chất thứ hai xác định (theo cách khá mập mờ) ý tưởng ý tưởng "bảo mật". Quá
trình thử tính khoá K (khi đã biết bản mã y) được gọi là mã thám (sau này khái niệm
này sẽ đực làm chính xác hơn). Cần chú ý rằng, nếu Oscar có thể xác định được K thì
anh ta có thể giải mã được y như Bob bằng cách dùng dK. Bởi vậy, việc xác định K chí
ít cũng khó như việc xác định bản rõ x.
Nhận xét: MDV (theo modulo 26) là không an toàn vì nó có thể bị thám theo
phương pháp vét cạn. Do chỉ có 26 khoá nên dễ dàng thử mọi khoá dK có thể cho tới
khi nhận được bản rõ có nghĩa. Điều này được minh hoạ theo ví dụ sau:
Ví du 2: Cho bản mã

MTT, thích hợp hơn là xem phép mã và giải mã như các hoán vị của các kí tự.
Định nghĩa: Một hệ mật là một bộ 5 (
P,C,K,E,D
)
Cho
P
=
C
= Z
26
.
K
chứa mọi hoán vị có thể của 26 kí hiệu 0,1, . . . ,25
Với mỗi phép hoán vị π ∈
K
, ta định nghĩa:
e
π
(x) = π(x)
và d
π
(y) = π

-1(y)
trong đó π

-1 là hoán vị ngược của π.
Sau đây là một ví dụ về phép hoán vị ngẫu nhiên π tạo nên một hàm mã hoá (cũng
như trước, các kí hiệu của bản rõ được viết bằng chữ thường còn các kí hiệu của bản mã
là chữ in hoa).

26 là một số rất lớn. Bởi vậy, phép tìm khoá vét cạn không thể thực hiện
được, thậm chí bằng máy tính. Tuy nhiên, sau này sẽ thấy rằng MTT có thể dễ dàng bị
thám bằng các phương pháp khác.
3.5.3 Mã Apphin
MDV là một trường hợp đặc biệt của MTT chỉ gồm 26 trong số 26! các hoán vị có
thể của 26 phần tử. Một trường hợp đặc biệt khác của MTT là mã Affine được mô tả
dưới đây. trong mã Affine, ta giới hạn chỉ xét các hàm mã có dạng:
e(x) = ax + b mod 26,
a,b ∈ Z
26
. Các hàm này được gọi là các hàm Affine (chú ý rằng khi a = 1, ta có MDV).
Để việc giải mã có thể thực hiện được, yêu cầu cần thiết là hàm Affine phải là đơn
ánh. Nói cách khác, với bất kỳ y ∈ Z
26
, ta muốn có đồng nhất thức sau:
ax + b ≡ y (mod 26)
phải có nghiệm x duy nhất. Đồng dư thức này tương đương với:
ax ≡ y-b (mod 26)
Vì y thay đổi trên Z
26
nên y-b cũng thay đổi trên Z
26
. Bởi vậy, ta chỉ cần nghiên cứu
phương trình đồng dư:
ax ≡ y (mod 26) (y∈ Z
26
).
Ta biết rằng, phương trình này có một nghiệm duy nhất đối với mỗi y khi và chỉ khi
UCLN(a,26) = 1 (ở đây hàm UCLN là ước chung lớn nhất của các biến của nó). Trước
tiên ta giả sử rằng, UCLN(a,26) = d >1. Khi đó, đồng dư thức ax ≡ 0 (mod 26) sẽ có ít

P
= { (a,b) ∈ Z
26
× Z
26
: UCLN(a,26) =1 }
Với K = (a,b) ∈
K
, ta định nghĩa:
e
K
(x) = ax +b mod 26
và dK(y) = a-1(y-b) mod 26, x,y ∈ Z
26
Ví dụ: Giả sử K = (7,3). Như đã nêu ở trên, 7
-1
mod 26 = 15.
GV. Lê Đắc Nhường Trang 17
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin
Hàm mã hoá là
e
K
(x) = 7x+3
Và hàm giải mã tương ứng là:
d
K
(x) = 15(y-3) = 15y -19
Ở đây, tất cả các phép toán đều thực hiện trên Z
26
.

XVI.
Sử dụng phép tương ứng A ⇔ 0, B ⇔ 1, . . . , Z ⇔ 25 mô tả ở trên, ta có thể gắn
cho mỗi khoa K với một chuỗi kí tự có độ dài m được gọi là từ khoá. Mật mã Vigenère
sẽ mã hoá đồng thời m kí tự: Mỗi phần tử của bản rõ tương đương với m ký tự.
Định nghĩa: Một hệ mật là một bộ 5 (P,C,K,E,D)
Cho m là một số nguyên dương cố định nào đó.
Định nghĩa P = C = K = (Z
26
)
m
. Với khoá K = (k
1
, k
2
, . . . ,k
m
) ta xác định :
e
K
(x
1
, x
2
, . . . ,x
m
) = (x
1
+k
1
, x

trong đó tất cả các phép toán được thực hiện trong Z
26
Ví dụ: Giả sử m =6 và từ khoá là CIPHER.
Từ khoá này tương ứng với dãy số K=(2,8,15,4,17).
Giả sử bản rõ là xâu: thiscryptosystemisnotsecure
GV. Lê Đắc Nhường Trang 18
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin
Ta sẽ biến đổi các phần tử của bản rõ thành các thặng dư theo modulo 26, viết chúng
thành các nhóm 6 rồi cộng với từ khoá theo modulo 26 như sau:
Bởi vậy, dãy ký tự tương ứng của xâu bản mã sẽ là:
V P X Z G I A X I V W P U B T T M J P W I Z I T W Z T
Để giải mã ta có thể dùng cùng từ khoá nhưng thay cho cộng, ta trừ cho nó theo
modulo 26.
Ta thấy rằng các từ khoá có thể với số độ dài m trong mật mã Vigenère là 26
m
, bởi
vậy, thậm chí với các giá trị m khá nhỏ, phương pháp tìm kiếm vét cạn cũng yêu cầu
thời gian khá lớn. Ví dụ, nếu m = 5 thì không gian khoá cũng có kích thước lớn hơn 1,1
× 10
7
. Lượng khoá này đã đủ lớn để ngăn ngừa việc tìm khoá bằng tay( chứ không phải
dùng máy tính).
Trong hệ mật Vigenère có từ khoá độ dài m,mỗi ký tự có thể được ánh xạ vào trong
m ký tự có thể có (giả sử rằng từ khoá chứa m ký tự phân biệt). Một hệ mật như vậy
được gọi là hệ mật thay thế đa biểu (polyalphabetic). Nói chung, việc thám mã hệ thay
thế đa biểu sẽ khó khăn hơn so việc thám mã hệ đơn biểu.
3.5.5 Mã HILL
Trong phần này sẽ mô tả một hệ mật thay thế đa biểu khác được gọi là mật mã Hill.
Mật mã này do Lester S.Hill đưa ra năm 1929. Giả sử m là một số nguyên dương, đặt P
= C = (Z


y
2
= 8x
1
+ 7x
2

Tất nhiên có thể viết gọn hơn theo ký hiệu ma trận như sau
GV. Lê Đắc Nhường Trang 19
19 7 8 18 2 17 24 15 19 14 18 24
2 8 15 7 4 17 2 8 15 7 4 17
21 15 23 25 6 8 0 23 8 21 22 15
18 19 4 12 8 18 13 14 19 18 4 2
2 8 15 7 4 17 2 8 15 7 4 17
20 1 19 19 12 9 15 22 8 15 8 19
20 17 4
2 8 15
22 25 19
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin
1 2 1 2
11 8
( y ) ( )
3 7
y x x
 
=
 ÷
 
Nói chung, có thể lấy một ma trận K kích thước m × m làm khoá.

k k
 
 ÷
=
 ÷
 ÷
 
Nói một cách khác y = xK.
Chúng ta nói rằng bản mã nhận được từ bản rõ nhờ phép biến đổi tuyến tính. Ta sẽ
xét xem phải thực hiện giải mã như thế nào, tức là làm thế nào để tính x từ y. Bạn đã
làm quen với đại số tuyến tính sẽ thấy rằng phải dùng ma trận nghịch đảo K
-1
để giả mã.
Bản mã được giải mã bằng công thức y K
-1
.
Định nghĩa: Một hệ mật là một bộ 5 (P,C,K,E,D)
Cho m là một số nguyên dương có định. Cho P = C = (Z
26
)
m
và cho
K = { các ma trận khả nghịch cấp m × m trên Z
26
}
Với một khoá K ∈K ta xác định
e
K
(x) = xK
và d

3 7
 
= + + =
 ÷
 
Và
11 8
(11,21) (121 72,88 168) (11,22)
3 7
 
= + + =
 ÷
 
Bởi vậy bản mã của July là DELW. Để giải mã Bob sẽ tính:
7 18
(3,4) (9, 20)
23 11
 
=
 ÷
 
và
7 18
(11,22) (11,24)
23 11
 
=
 ÷
 
Như vậy Bob đã nhận được bản đúng.

1,1
a
2,2
- a
1,2
a
2,1
có nghịch đảo. Khi đó
2,2 1,2
1 1
2,1 1,1
(det )
a a
A A
a a
− −
−
 
=
 ÷
−
 
Trở lại ví dụ đã xét ở trên . Trước hết ta có:
11 8
3 7
Det
 
 ÷
 
=(11.7-8.3) mod 26 = 77 - 24 mod 26 = 53 mod 26 =1

)m và cho
K
gồm tất cả các hoán vị của {1, . . ., m}. Đối một khoá π ( tức là một hoán vị) ta
xác định
eπ(x1, . . . , xm ) = (xπ(1), . . . , xπ(m))
và dπ(x1, . . . , xm ) = (yπ -1(1), . . . , yπ -1(m))
trong đó π -1 là hoán vị ngược của π
Ví dụ: Giả sử m = 6 và khoá là phép hoán vị ( π ) sau:
GV. Lê Đắc Nhường Trang 21
123456
351642
123456
361524
Hoán vị Hoán vị -1
K =
0 0 1 0 0 0
0 0 0 0 0 1
1 0 0 0 0 0
0 0 0 0 1 0
0 1 0 0 0 0
0 0 0 1 0 1
và K-1 =
0 0 1 0 0 0
0 0 0 0 1 0
1 0 0 0 0 0
0 0 0 0 0 1
0 0 0 1 0 0
0 1 0 0 0 0
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin
Khi đó phép hoán vị ngược π

(ma trận hoán vị là ma trận trong đó mỗi hàng và mỗi cột chỉ có một số "1", còn tất
cả các giá trị khác đều là số "0". Ta có thể thu được một ma trận hoán vị từ ma trận đơn
vị bằng cách hoán vị các hàng hoặc cột).
Dễ dàng thấy rằng, phép mã Hill dùng ma trận K
π
trên thực tế tương đương với phép
mã hoán vị dùng hoán vị π. Hơn nữa K
-1
π
= K
π

-1
tức ma trận nghịch đảo của K
π
là ma
trận hoán vị xác định theo hoán vị π
-1
. Như vậy, phép giải mã Hill tương đương với
phép giải mã hoán vị.
Đối với hoán vị π được dung trong ví dụ trên, các ma trận hoán vị kết hợp là:
Bạn có thể kiểm tra để thấy rằng, tích của hai ma trận này là một ma trận đơn vị.
GV. Lê Đắc Nhường Trang 22
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin
GV. Lê Đắc Nhường Trang 23
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin
CHƯƠNG 4
HỆ MÃ HÓA DES
Ngày 15.5.1973. Uỷ ban tiêu chuẩn quốc gia Mỹ đã công bố một khuyến nghị cho
các hệ mật trong Hồ sơ quản lý liên bang. Điều này cuối cùng đã dẫn đến sự phát triển

Ta sẽ tính L
i
R
i
, 1≤i≤16 theo quy tắc sau:
L
i
= R
i-1
R
i
= L
i-1
⊕
f(R
i-1
,K
i
)
trong đó: kí hiệu phép hoặc loại trừ của hai xâu bít (cộng theo modulo 2). f là một
hàm mà ta sẽ mô tả ở sau, còn K
1
,K
2
, . . . ,K
16
là các xâu bít độ dài 48 được tính như
hàm của khoá K. (trên thực tế mỗi K
i
là một phép chọn hoán vị bít trong K). K

1. Biến thứ nhất A được mở rộng thành một xâu bít độ dài 48 theo một hàm mở rộng
cố định E. E(A) gồm 32 bít của A (được hoán vị theo cách cố định) với 16 bít xuất
hiện hai lần.
2. Tính E(A) ⊕ J và viết kết quả thành một chuỗi 8 xâu 6 bít = B
1
B
2
B
3
B
4
B
5
B
6
B
7
B
8
.
3. Bước tiếp theo dùng 8 bảng S
1
, S
2
, ,S
8
( được gọi là các hộp S ). Với mỗi S
i
là một
bảng 4×16 cố định có các hàng là các số nguyên từ 0 đến 15. Với xâu bít có độ dài 6

4
b
5
) xác định biểu diễn nhị phân
của cột c của S
j
( 0 ≤ c ≤ 15 ).
Khi đó S
j
(B
j
) sẽ xác định phần tử S
j
(r,c); phần tử này viết dưới dạng nhị phân là một
xâu bít có độ dài 4. ( Bởi vậy, mỗi S
j
có thể được coi là một hàm mã mà đầu vào là
một xâu bít có độ dài 2 và một xâu bít có độ dài 4, còn đầu ra là một xâu bít có độ
dài 4). Bằng cách tương tự tính các C
j
= S
j
(B
j
), 1 ≤ j ≤ 8.
4. Xâu bít C = C
1
C
2
C