Bảo mật thông tin
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (981.35 KB, 88 trang )
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN VINH SƠN
BẢO MẬT THÔNG TIN
LUẬN VĂN THẠC SĨ
Hà Nội - 2009
MỤC LỤC
MỞ ĐẦU............................................................................................................ 1
CHƯƠNG 1. BẢO MẬT THÔNG TIN .............................................................. 3
1.1. Khái niệm .................................................................................................... 3
1.2. Đánh giá hệ mật ........................................................................................... 4
1.3. Cơ sở toán học ............................................................................................. 5
CHƯƠNG 2. HỆ THỐNG MẬT MÃ ................................................................12
2.1. Hệ mật DES................................................................................................12
2.1.1. Sơ ñồ.............................................................................................13
2.1.2. Hoạt ñộng......................................................................................16
2.1.3. Chế ñộ làm việc.............................................................................22
2.1.4. 2DES và 3DES..............................................................................29
2.2. Hệ mật RC ..................................................................................................31
2.2.1. RC5...............................................................................................31
2.2.2. RC6...............................................................................................36
2.3. Hệ mật Gost 28147−89 ...............................................................................40
2.3.1. Chế ñộ mã thay thế đơn giản .........................................................41
2.3.2. Chế độ mã dịng ............................................................................44
2.3.3. Chế độ mã dịng hồi tiếp................................................................45
2.3.4. Thủ tục kiểm tra toàn vẹn ..............................................................45
2.4. Hệ mật IDEA ..............................................................................................46
2.5. Hệ mật AES................................................................................................49
2.5.1. Biểu diễn khối tin ..........................................................................50
2.5.2. Các phép tốn................................................................................52
2.5.3. Giải thuật ......................................................................................56
2.6. Hệ mật khóa cơng khai RSA .......................................................................70
CHƯƠNG 3. TRIỂN KHAI...............................................................................74
3.1. Phần mềm mật mã.......................................................................................74
3.2. Bảo vệ mật khẩu .........................................................................................77
3.2.1. Nguy cơ chặn bắt...........................................................................77
3.2.2. Giải pháp bảo vệ ...........................................................................79
KẾT LUẬN .......................................................................................................83
KÝ HIỆU
AES
Advanced Encryption Standard
DES
Data Encryption Standard
IDEA
International Data Encryption Algorithm
RC
Rivest’s Cipher
RSA
Rivest, Shamir, Adleman
MỞ ĐẦU
Bảo mật thông tin là nhu cầu luôn tồn tại trong thế giới tự nhiên. Các lồi động vật
cũng phải tìm cách cất giấu những thơng tin của chúng trước kẻ thù, như thông tin
về nguồn thức ăn, nước uống, nơi cư trú… Trong lịch sử loài người, xã hội phát
triển càng cao, nhu cầu bảo mật thông tin càng lớn và hình thức bảo mật thơng tin
càng hiện ñại. Từ thời Hy Lạp cổ ñại, người ta cuộn kín những vịng giấy papyrus
lên một chiếc “gậy mã hóa” rồi viết những thơng tin bí mật lên đó. Với cách làm
này, người khác phải biết cuộn lại những vòng giấy đó lên một chiếc “gậy giải mã”
có đường kính ñúng bằng chiếc “gậy mã hóa” nếu muốn ñọc. Đến nửa đầu thế kỷ
20, một số thiết bị cơ khí ñược phát minh ñể mật mã tài liệu quân sự, ñiển hình là
máy Enigma của người Đức. Kỹ thuật máy tính ra đời, lĩnh vực này đã số hóa và
bước sang một trang sử mới. Khơng giống mơ hình mật mã cổ điển và cơ học trước
đó, hệ thống mật mã máy tính hoạt động với những phép tính phức tạp của các
chuỗi nhị phân nên hiệu quả giữ bí mật tăng lên rất nhiều.
Bảo mật thông tin thường gắn với q trình “mã hóa” và “giải mã”, hay là cách
chuyển đổi thơng tin từ dạng có thể hiểu được sang dạng khơng thể hiểu được và
ngược lại. Việc mật mã giúp đảm bảo tính bí mật của các thơng tin quan trọng,
chẳng hạn thơng tin tình báo, qn sự, ngoại giao, hay các dữ liệu tài chính, thương
mại... Nhưng chúng ta đang bước tới kỷ ngun của cơng nghệ cao phục vụ cho sự
giản tiện trong sinh hoạt hàng ngày, và lĩnh vực bảo mật thông tin không nằm ngồi
mục đích đó. Giờ đây, các hệ mật mã khơng chỉ dùng để cất giấu thơng tin của cá
nhân/ tổ chức/ quốc gia này với cá nhân/ tổ chức/ quốc gia khác, mà nó cịn là cơ sở
cho việc phát triển nhiều ứng dụng trên mạng truyền thông công cộng. Kiến thức
bảo mật ứng dụng rộng rãi trong chứng thực ñiện tử, chữ ký số, bầu cử ñiện tử, giao
dịch ngân hàng, thương mại ñiện tử, phát hành và mua bán bằng tiền điện tử…
Ngồi ra, những người khơng có nhu cầu đặc biệt về tính bí mật cũng thường xun
sử dụng các cơng nghệ mật mã tích hợp trong các thiết bị điện tử tính tốn, hay các
hệ thống viễn thơng.
Như vậy, ai phải quan tâm đến bảo mật? Câu trả lời là tất cả mọi người! Thế nhưng,
không dễ nếu ta phân tách lĩnh vực này thuộc phạm vi nghiên cứu của ngành khoa
học nào – Toán học, Công nghệ Thông tin, hay Công nghệ Điện tử Viễn thơng?
Chúng ta biết rằng, bảo mật ln rất nóng tại mọi thời kỳ, nhưng đến khi ngành
Thơng tin – Truyền thơng (ICT) bùng nổ, nó mới thực sự có động lực phát triển
mạnh mẽ, do nhu cầu bảo mật và ứng dụng bảo mật trong ICT. Mặc dù vậy, bảo
mật sẽ mãi tồn tại ở thủa ban đầu, nếu khơng có những cơ sở Toán học mới mẻ,
vững chắc hậu thuẫn (cụ thể là lý thuyết số, lý thuyết thông tin, xác suất, độ phức
tạp tính tốn, đại số trừu tượng, trường hữu hạn, hàm một chiều…). Một số nước,
người ta tách biệt ñây là ngành khoa học riêng, nhưng một số nước khác thì khơng.
Và dù ở quan điểm nào, việc nghiên cứu bảo mật vẫn luôn thu hút sự chú ý của rất
nhiều người làm ICT, cũng như nhiều nhà Toán học. Bởi lẽ trong khoa học, chúng
ta vẫn thường bắt gặp những sự “giao thoa” như thế.
Tại Việt Nam, chúng ta biết có một cơ sở chun đào tạo kỹ sư mật mã học, đó là
Học viện Kỹ thuật Mật mã. Tuy nhiên việc nghiên cứu bảo mật trong các Trường
Đại học ñào tạo ICT lại khá thiếu và yếu. Đặc biệt, tài liệu về bảo mật viết bằng
tiếng Việt thì rất khan hiếm. Trên thực tế như vậy, học viên viết cuốn luận văn này
với mong muốn sử dụng hiểu biết, nghiên cứu của mình để xây dựng một tài liệu
bảo mật có chất lượng. Các kỹ sư/ cử nhân Công nghệ Thông tin, Điện tử Viễn
thông, hay bất cứ ai làm/ nghiên cứu bảo mật sẽ tìm thấy ở đây những khái niệm
xúc tích về mật mã, những hệ mật phổ biến nhất hiện nay, và một phần mềm mã
hóa, giải mã học viên thiết kế theo Chuẩn mật mã Quốc gia Hoa Kỳ − AES. Ngoài
ra, học viên xin ñề xuất một giải pháp mới giúp bảo vệ mật khẩu trong mơ hình
server/ client mà khơng sử dụng giao thức bảo mật.
Hà Nội, 2009
Nguyễn Vinh Sơn
3
CHƯƠNG 1
BẢO MẬT THƠNG TIN
1.1
Khái niệm
Trước khi tìm hiểu các nội dung bảo mật thơng tin đề cập ở cuốn luận văn này,
chúng ta cần hiểu một số khái niệm sau.
-
Mã hóa: là việc biến đổi thơng tin từ dạng có thể hiểu được sang dạng khơng
thể hiểu được.
-
Giải mã: là việc biến đổi thơng tin từ dạng khơng thể hiểu được trở về dạng
có thể hiểu được bằng cách sử dụng khóa đã biết.
-
Thám mã: là việc biến đổi thơng tin từ dạng khơng thể hiểu được trở về dạng
có thể hiểu được mà khơng biết khóa.
-
Khóa: là đại lượng thơng tin sử dụng để thực hiện mã hóa, hoặc giải mã.
-
Mã khối: là phương thức mật mã trên từng khối của bản tin.
-
Mã dòng: là phương thức mật mã trên từng bit của bản tin.
-
Hệ mật ñối xứng (hệ mật khóa bí mật): là hệ mật có khóa giải mã suy ra dễ
dàng từ khóa mã hóa và ngược lại (các khóa được giữ bí mật).
-
Hệ mật khóa cơng khai (hệ mật bất đối xứng): là hệ mật có khóa mã hóa
được cơng khai, cịn khóa giải mã được giữ bí mật (rất khó để tìm khóa giải
mã từ khóa mã hóa).
-
Chữ ký số (chữ ký điện tử): là thơng tin đi kèm dữ liệu điện tử nhằm mục
đích xác định người chủ của dữ liệu đó.
-
Chứng thực số (chứng thực khóa cơng khai): là chứng thực sử dụng chữ ký
số để gắn một khóa cơng khai với một thực thể.
-
Hạ tầng khóa cơng khai: là tập hợp các thành phần tạo, quản lý, phân phối,
sử dụng, lưu trữ, hủy chứng thực số.
-
Hàm hash: là hàm tính ra giá trị có kích thước xác định, từ bản tin bất kỳ.
4
1.2
Đánh giá hệ mật
Các hệ thống mật mã (hệ mật) khác nhau có ưu, nhược điểm khác nhau. Nhưng
nhìn chung, chúng có thể được đánh giá là tốt hay khơng, căn cứ vào độ phức tạp
của các thuật tốn thám chúng. Người ta chia độ phức tạp thuật tốn thành:
-
Độ phức tạp tuyến tính
-
Độ phức tạp lũy thừa
-
Độ phức tạp tựa hàm mũ
-
Độ phức tạp hàm mũ
Thuật tốn có độ phức tạp khơng vượt q độ phức tạp lũy thừa thì coi là “dễ” (giải
được). Thuật tốn có độ phức tạp khơng nhỏ hơn độ phức tạp hàm mũ thì coi là
“khó” (khơng giải được). Thuật tốn có độ phức tạp nằm giữa 2 mức “khó” và “dễ”
có thể giải ñược, hoặc không giải ñược.
Hệ mật tốt thuộc các loại sau:
-
Hệ mật an tồn tuyệt đối: những hiểu biết về bản mã khơng thu hẹp được độ
bất định của bản rõ đối với người thám mã, nói cách khác, hệ mật này khơng
thể thám được trên lý thuyết.
-
Hệ mật an tồn thực sự: mọi phương pháp thám mã đã biết đều cần đến thời
gian tính tốn, hoặc năng lực tính tốn vơ cùng lớn.
-
Hệ mật an tồn chứng minh: việc thám mã ñược chứng minh là tương ñương
việc giải một bài tốn khó đã biết.
Hệ mật an tồn thực sự, hay an tồn chứng minh khơng có nghĩa là khơng thể bị
thám, bởi lẽ năng lực tính tốn ngày càng cải thiện, cịn lời giải tốt cho bài tốn khó
tương ñương có thể ñược sinh ra. Trong bài viết trên tạp chí “Khoa học Quân sự”
của Pháp năm 1883, Auguste Kerckhoffs (1835 – 1903) ñề xuất 6 quy tắc triển khai
một hệ mật mã qn sự tại thời điểm đó là:
-
Hệ mật chưa từng thám ñược trong thực tế.
-
Hoạt ñộng của hệ mật, cũng như thiết bị mật mã không cần giữ bí mật.
5
-
Khóa là thành phần bí mật duy nhất, tạo mới, truyền đi, ghi nhớ dễ dàng.
-
Hệ mật tương thích với cơng nghệ điện tín.
-
Thiết bị mật mã gọn nhẹ, một người cũng có thể sử dụng.
-
Cách sử dụng dễ dàng.
Đến nay ngoại trừ quy tắc thứ 4 ñã trở nên lạc hậu, chúng ta vẫn phải hướng ñến 5
quy tắc cịn lại.
1.3
Cơ sở tốn học
Lĩnh vực bảo mật thơng tin liên quan đến lý thuyết số, lý thuyết thơng tin, xác suất,
độ phức tạp tính tốn, đại số trừu tượng, trường hữu hạn, hàm một chiều... Nhưng
với khuôn khổ của cuốn luận văn thạc sỹ ngành Điện tử Viễn thông, học viên
khơng giới thiệu chi tiết những lý thuyết đó mà chỉ trình bày ký hiệu, khái niệm,
định lý, và giải thuật toán học sử dụng trong tài liệu này.
Ký hiệu gcd(a, b), lcm(a, b) là ước chung lớn nhất, bội chung nhỏ nhất của 2 số
nguyên a, b; x, x là số nguyên lớn nhất không lớn hơn x, số ngun nhỏ nhất
khơng nhỏ hơn x; cịn Zn là tập các số nguyên {0, 1, 2, ..., n−1}.
Nhóm (G, *) là cấu trúc ñại số gồm tập G và phép tốn 2 ngơi * trong G, thỏa mãn:
-
Phép * có tính kết hợp:
a * (b * c) = (a * b) * c
(∀ a, b, c ∈ G)
-
Tồn tại phần tử trung hòa θG ∈ G:
a * θG = θG * a = a
(∀ a ∈ G)
-
Tồn tại phần tử ñối lập xG ∈ G:
a * xG = xG * a = θG
(với mỗi a ∈ G)
Nhóm (G, *) gọi là nhóm giao hốn nếu phép * cịn có tính giao hốn: a * b = b * a.
6
Vành (R, +, •) là cấu trúc đại số gồm tập R và các phép tốn 2 ngơi +, • trong R,
thỏa mãn:
-
(R, +) là nhóm giáo hốn
-
Phép • có tính kết hợp:
a • (b • c) = (a • b) • c
(∀ a, b, c ∈ R)
-
Tồn tại phần tử trung hịa θR ∈ R:
a • θR = θR • a = a
(∀ a ∈ R)
-
Phép • có tính phân phối với phép +:
a • (b + c) = (a • b) + (a • c)
(b + c) • a = (b • a) + (c • a)
(∀ a, b, c ∈ R)
Vành (R, +, •) gọi là vành giao hốn nếu phép • cịn có tính giao hốn: a • b = b • a.
Phần tử trung hịa θR của vành (R, +, •) cịn gọi là phần tử trung hịa trong phép •.
Phần tử trung hịa của nhóm giao hốn (R, +) cịn gọi là phần tử trung hịa trong
phép +, ký hiệu θr.
Trong vành giao hốn, nếu mọi phần tử khác θr đều có phần tử ñối lập trong phép •,
xR ∈ R thỏa mãn a • xR = xR • a = θR, thì ta nói vành đó là một “trường”.
Trường hữu hạn là trường có số phần tử hữu hạn.
Tập đa thức có hệ số thuộc vành (trường) R, và 2 phép toán cộng, nhân ña thức
thực hiện bởi phép cộng, nhân hệ số trong R, tạo nên vành (trường) ña thức R[x].
Định lý Fermat: [5]
Cho số nguyên tố p, nếu gcd(a, p) = 1 thì a(p−1) ≡ 1 (mod p).
Giải thuật Euclide mở rộng: [5]
Input:
2 số nguyên không âm a, b (a ≥ b).
Output: d = gcd(a, b) và 2 số nguyên x, y thỏa mãn: ax + by = d.
7
1. Nếu b = 0 thì d ← a , x ← 1 , y ← 0.
Trả về {d, x, y}.
2. Đặt x2 ← 1 , x1 ← 0 , y2 ← 0 , y1 ← 1.
3. Khi b > 0, tính:
q
←
a/b
r
←
a − qb
x
←
x2 − qx1
y
←
y2 − qy1
a
←
b
b
←
r
x2
←
x1
x1
←
x
y2
←
y1
y1
←
y
4. Chuyển d ← a , x ← x2 , y ← y2.
Trả về {d, x, y}.
Trong Zp[x] (p nguyên tố):
Input:
g(x), h(x) ∈ Zp[x].
Output: d(x) = gcd(g(x), h(x)) và s(x), t(x) ∈ Zp[x]
thỏa mãn:
s(x).g(x) + t(x).h(x) = d(x).
8
1. Nếu h(x) = 0 thì d(x) ← g(x) , s(x) ← 1 , t(x) ←0.
Trả về {d(x), s(x), t(x)}.
2. Đặt s2(x) ← 1 , s1(x) ← 0 , t2(x) ← 0 , t1(x) ← 1.
3. Khi h(x) ≠ 0, tính:
q(x)
←
g(x) div h(x)
r(x)
←
g(x) − h(x).q(x)
s(x)
←
s2(x) − q(x).s1(x)
t(x)
←
t2(x) − q(x).t1(x)
g(x)
←
h(x)
h(x)
←
r(x)
s2(x)
←
s1(x)
s1(x)
←
s(x)
t2(x)
←
t1(x)
t1(x)
←
t(x)
4. Chuyển d(x) ← g(x) , s(x) ← s2(x) , t(x) ← t2(x).
Trả về {d(x), s(x), t(x)}.
Ví dụ 1:
Input:
a = 4864 , b = 3458
Output: d = gcd(4864, 3458) = 38 , x = 32 , y = −45
thỏa mãn: (4864).(32) + (3458).(−45) = 38
9
q
r
x
y
a
b
x2
x1
y2
y1
−
−
−
−
4864
3458
1
0
0
1
1
1406
1
−1
3458
1406
0
1
1
−1
2
646
−2
3
1406
646
1
−2
−1
3
2
114
5
−7
646
114
−2
5
3
−7
5
76
−27
38
114
76
5
−27
−7
38
1
38
32
−45
76
38
−27
32
38
−45
2
0
−91
128
38
0
32
−91
−45
128
Bảng 1.1.
Giải thuật Euclide mở rộng với a = 4864, b = 3458
Ví dụ 2:
g(x)
=
x10 + x9 + x8 + x6 + x6 + x5 + x4 + 1
h(x)
=
x9 + x6 + x5 + x3 + x2 + 1
Output: d(x)
=
gcd(g(x), h(x))
s(x)
t(x)
=
=
x4
x5 + x4 + x3 + x2 + x + 1
Input:
=
x3 + x + 1
thỏa mãn: (x4).g(x) + (x5 + x4 + x3 + x2 + x + 1).h(x) = x3 + x + 1
Giải thuật là:
s2(x) ← 1 , s1(x) ← 0 , t2(x) ← 0 , t1(x) ← 1
Chu kỳ 1:
q(x)
← x+1
r(x)
← x8 + x7 + x6 + x2 + x
10
s(x)
← 1
t(x)
← x+1
g(x)
← x9 + x6 + x5 + x3 + x2 + 1
h(x)
← x8 + x7 + x6 + x2 + 1
s2(x)
← 0
s1(x)
← 1
t2(x)
← 1
t1(x)
← x+1
Chu kỳ 2:
q(x)
← x+1
r(x)
← x5 + x2 + x + 1
s(x)
← x+1
t(x)
← x2
g(x)
← x8 + x7 + x6 + x2 + 1
h(x)
← x5 + x2 + x + 1
s2(x)
← 1
s1(x)
← x+1
t2(x)
← x+1
t1(x)
← x2
Chu kỳ 3:
11
q(x)
← x3 + x2 + x + 1
r(x)
← x3 + x + 1
s(x)
← x4
t(x)
← x5 + x4 + x3 + x2 + x + 1
g(x)
← x5 + x2 + x + 1
h(x)
← x3 + x + 1
s2(x)
← x+1
s1(x)
← x4
t2(x)
← x2
t1(x)
← x5 + x4 + x3 + x2 + x + 1
Chu kỳ 4:
q(x)
← x2 + 1
r(x)
← 0
s(x)
← x6 + x4 + x + 1
t(x)
← x7 + x6 + x2 + x + 1
g(x)
← x3 + x + 1
h(x)
← 0
s2(x)
← x4
s1(x)
← x6 + x4 + x + 1
t2(x)
← x5 + x4 + x3 + x2 + x + 1
t1(x)
← x7 + x6 + x2 + x + 1
12
CHƯƠNG 2
HỆ THỐNG MẬT MÃ
Chương này, học viên trình bày các hệ thống mật mã (hệ mật) nổi tiếng, ñược sử
dụng rộng rãi là DES, RC, Gost 28147–89, IDEA, AES, và RSA. Gost 28147–89 là
Chuẩn mật mã Quốc gia Nga từ năm 1989, DES và AES lần lượt là Chuẩn mật mã
Quốc gia Hoa Kỳ từ các năm 1976 ñến 2002, và 2002 trở ñi. RC, IDEA cũng là các
hệ mật được đánh giá cao, cịn RSA là hệ mật khóa cơng khai điển hình.
2.1
Hệ mật DES
Hệ mật DES (Data Encryption Standard) ñược IBM phát triển từ ñầu thập niên
1970, sau khi hai cơ quan của Chính phủ Hoa Kỳ là Cục tiêu chuẩn Quốc gia
(National Bureau of Standards – NBS) và Cơ quan an ninh Quốc gia (National
Security Agency – NSA) kêu gọi xây dựng tiêu chuẩn trong việc mã hóa các thơng
tin mật. Ngày 17.03.1975, DES được cơng bố và một năm sau trở thành Chuẩn mật
mã Quốc gia Hoa Kỳ, cho dù có nghi ngại độ dài khóa 56 bits là ngắn, hay các khối
S được chọn như vậy có thể giúp chính NSA và khơng ai khác thám hệ mật này.
Đến thập niên 1990, hai nhà toán học người Israel, Eli Biham và Adi Shamir cảnh
báo các dạng mật mã khối có thể bị thám bởi một phương pháp mới – phương pháp
thám mã vi phân. Khi ấy, DES cho thấy IBM và NSA ñã biết ñược phương pháp
thám này từ trước ñó, và các khối S được chọn chính là để chống việc thám vi phân
một cách tốt nhất. Năm 1994, phương pháp thám mã tuyến tính được hai người
Nhật là Matsui, Yamagishi cơng bố, về lý thuyết, cũng thám ñược DES. Năm 1997,
trong một cuộc thi do Công ty RSA Security khởi xướng, dự án Deschall của
Rocke Verser, Matt Curtin, và Justin Dolske sử dụng hàng nghìn máy tính nối
mạng đã thám được DES lần ñầu tiên trong thực tế. Một năm sau, tổ chức EFF
(Electronic Frontier Foundation) xây dựng hệ thống chuyên biệt Deep Crack giá trị
lên đến 250.000 USD, có thể thám DES trong vòng 56 giờ. Năm 1998, hệ mật
Rijndael ra đời và sau đó được Viện tiêu chuẩn và cơng nghệ Hoa Kỳ (National
Institute of Standards and Technology – NIST, tiền thân là National Bureau of
13
Standards – NBS) cơng bố chính thức thay thế DES làm Chuẩn mật mã Quốc gia từ
năm 2002 với cái tên AES (Advanced Encryption Standard).
Đến nay, dù khơng cịn là Chuẩn mật mã Quốc gia, nhưng DES vẫn ñược sử dụng
rất rộng rãi trong việc bảo vệ những thông tin quan trọng mà chưa ñến mức “tối
mật”, hay “tuyệt mật”. Sự xuất hiện của DES cịn rất có ý nghĩa trong lịch sử bảo
mật thơng tin. Nó tạo nên một làn sóng nghiên cứu lĩnh vực này, cụ thể là các
phương pháp thám mã khối. DES có tốc độ mã cao khi triển khai bằng phần cứng
cũng như phần mềm, ñặc biệt với những vi xử lý chuyên dụng. Tuy nhiên, tốc ñộ
khi triển khai DES trên các hệ thống máy tính thơng thường sẽ bị hạn chế vì hệ mật
này địi hỏi nhiều phép tính trên bit, trong khi các máy tính mà chúng ta đang dùng
thực hiện tính tốn trên byte.
2.1.1 Sơ đồ
DES sử dụng một cấu trúc cơ bản là sơ ñồ Feistel. Đây cũng là cấu trúc của một số
hệ mật đối xứng mã khối khác.
Hình 2.1.
Sơ đồ Feistel
Khối đầu vào chia 2 phần có độ dài bằng nhau Li−1 và Ri−1 biến ñổi thành ñầu ra Li
và Ri bởi công thức sau, với f là một hàm bất kỳ và thường là hàm phi tuyến.
Li =
Ri−1
Ri =
f(Ri−1, ki) ⊕ Li−1
Thao tác giải mã biểu diễn bởi công thức:
14
Ri−1 =
Li
Li−1 =
f(Ri−1, ki) ⊕ Ri
Khi dùng sơ ñồ Feistel nhiều lần trong một hệ mật, 2 khối ñầu ra ở sơ đồ cuối cùng
khơng đổi vị trí cho nhau:
RN =
RN–1
LN =
f(RN–1, kN) ⊕ LN–1
Điều này cho phép ta không phải ñảo ngược khối ñầu tiên khi giải mã. Tức là q
trình giải mã diễn ra theo đúng thứ tự ở q trình mã hóa, chỉ khác trật tự dùng
khóa chu kỳ. Do vậy, khi xây dựng hệ mật ta có thể viết một chương trình, thiết kế
một bảng mạch thực hiện đồng thời 2 chức năng mã hóa, giải mã. Ngồi ra, cấu
trúc Feistel cịn có ưu điểm là khi giải mã khơng cần tìm hàm ngược của hàm f, nên
ta có thể chọn hàm f với độ phức tạp bất kỳ. Tuy nhiên, nhược ñiểm của cấu trúc
này là trong một chu kỳ chỉ mật mã ñược nửa khối.
Sơ đồ DES như sau:
Khối tin
Hốn vị IP
MÃ HĨA
(16 lần)
Hốn vị IP
Khối tin: 64 bits
Khối mã: 64 bits
K:
Khối mã
56 bits
Hình 2.2.
Sơ ñồ DES cơ bản
K
15
Hình 2.3.
Sơ đồ DES chi tiết
16
Ở sơ đồ cơ bản, ta thấy DES mã hóa khối tin 64 bits bằng khóa K 56 bits (DESK),
nhưng khơng thấy sự có mặt của cấu trúc Feistel và thao tác mã hóa cụ thể. Trong
sơ đồ chi tiết, mọi thứ ñược rõ ràng. Sơ ñồ Feistel xuất hiện 16 lần (lần cuối cùng, 2
nửa trái, phải khơng đổi chỗ cho nhau), mỗi lần sử dụng một khóa ki 48 bits. Các
khóa ki gọi là khóa con hay khóa chu kỳ, được sinh ra từ khóa chính K.
Khi giải mã (DESK−1), ta tráo đổi vị trí 2 khối hốn vị IP và IP─1 cho nhau, và ñảo
ngược thứ tự khóa chu kỳ ki: k1, k2, ..., k16 → k16, k15, ..., k1.
2.1.2 Hoạt ñộng
Hoạt ñộng của DES liên quan ñến nhiều bảng số. Các bảng này ñược ñề xuất bởi
những nhà sáng lập hệ mật, ñể ñảm bảo ñộ an toàn cao nhất. Nếu triển khai với
những bảng số, quy tắc khác, hệ mật có thể vẫn làm việc nhưng độ an tồn sẽ suy
giảm đáng kể.
2.1.2.1
Sinh khóa ki
Khóa K 56 bits ñược lưu trữ, truyền ñi, tiếp nhận dưới dạng 64 bits. Để có 64 bits,
người ta chia 56 bits thành 8 nhóm, sau đó chèn thêm 1 bit vào cuối mỗi nhóm. Giá
trị bit chèn thêm được chọn sao cho số bits “1” trong nhóm sau khi chèn là số lẻ.
Đây chính là mã sửa sai, hay mã chống nhiễu trong quá trình lưu trữ và phân phối
khóa. Ví dụ:
K
=
1010101–0010000–0011011–1100111–1001100–0101010–1101000–1100011–
K’ =
1010101100100000001101111100111010011000010101001101000011000111
Quy tắc sinh 16 khóa con ki từ khóa K dựa trên 4 bảng số dưới đây. Chú ý rằng,
bảng 2.1, 2.2, 2.4 thực chất là các dãy số với thứ tự phần tử được tính từ trái qua
phải, từ trên xuống dưới.
57
49
41
33
25
17
9
1
58
50
42
34
26
48
10
2
59
51
43
35
27
19
11
3
60
52
44
36
Bảng 2.1.
Bảng chỉ số dãy C0
17
63
55
47
39
31
23
15
7
62
54
46
38
30
22
14
6
61
53
45
37
29
21
13
5
28
20
12
4
Bảng 2.2.
Bảng chỉ số dãy D0
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n
1
1
2
2
2
2
2
2
1
2
2
2
2
2
2
1
Bảng 2.3.
Bảng bước quay dãy Ci–1, Di–1
14
17
11
24
1
5
3
28
15
6
21
10
23
19
12
4
26
8
16
7
27
20
13
2
41
52
31
37
47
55
30
40
51
45
33
48
44
49
39
56
34
53
46
42
50
36
29
32
Bảng 2.4.
Bảng chỉ số khóa ki
Hai bảng đầu tiên, mỗi bảng chứa 28 phần tử. Tổng số phần tử là 56, bằng độ dài
thực của khóa K. Mỗi phần tử nhận giá trị trên ñoạn [1, 64]. Tám giá trị không xuất
hiện là 8, 16, 24, 32, 40, 56, 64 – chính là thứ tự các bits chèn thêm. Như vậy, mỗi
phần tử trong bảng 2.1, 2.2 chỉ ñến 1 bits của khóa K 56 bits. Dựa vào đó, ta có thể
lấy ra từ khóa K 2 dãy bits, mỗi dãy 28 bits và khơng có bit nào được lấy 2 lần. Ký
hiệu hai dãy bits này là C0 và D0, ký hiệu X0 là dãy thu ñược khi ghép C0 và D0 lại
với nhau. Ví dụ:
K = 1010101–0010000–0011011–1100111–1001100–0101010–1101000–1100011
C0 = 1101100111101000000001110111
D0 = 1000110110101100000110010100
X0 = 11011001111010000000011101111000110110101100000110010100
18
Trên cơ sở bộ {C0, D0, X0}, ta xác ñịnh 16 bộ {Ci, Di, Xi} khác (i = 1, 2, …, 16).
Ci, Di là kết quả của việc quay trái Ci–1, Di–1 n bits, và Xi là 2 dãy Ci, Di ghép lại.
Bước quay n cho bởi bảng 2.3. Ví dụ:
C0 = 1101100111101000000001110111
D0 = 1000110110101100000110010100
X0 = 11011001111010000000011101111000110110101100000110010100
(n1 = 1)
C1 = 1011001111010000000011101111
D1 = 0001101101011000001100101001
X1 = 10110011110100000000111011110001101101011000001100101001
Khóa con ki được tạo bởi 48 bits của dãy Xi, vị trí các bits cần lấy cho bởi bảng 2.4.
Ví dụ:
X1 = 10110011110100000000111011110001101101011000001100101001
k1 = 000010110011101111011000100010011011000101000101
Hốn vị IP, IP−1
2.1.2.2
IP là viết tắt của Initial Permutation – hoán vị sơ bộ. Cả hai khối IP và IP−1 ñều
thực hiện dựa trên dãy số IP[i] gồm 64 phần tử (1 ≤ i ≤ 64), mỗi phần tử là một giá
trị khơng lặp lại của đoạn [1, 64]. Dãy IP[i] ñược biểu diễn dưới dạng bảng như
sau, thứ tự phần tử tính từ trái qua phải, từ trên xuống dưới:
58
50
42
34
26
18
10
2
60
52
44
36
28
20
12
4
62
54
46
38
30
22
14
6
64
56
48
40
32
24
16
8
57
49
41
33
25
17
9
1
59
51
43
35
27
19
11
3
61
53
45
37
29
21
13
5
63
55
47
39
31
23
15
7
Bảng 2.5.
Bảng hoán vị IP, IP−1
19
Khối hốn vị IP biến đổi khối tin bằng cách thay thế bit thứ i1 bởi bit thứ i2 với i2 =
IP[i1], thay thế bit thứ i2 bởi bit thứ i3 với i3 = IP[i2]… Khối hoán vị IP−1 biến ñổi
khối tin theo cách ngược lại, thay thế bit thứ i2 bởi bit thứ i1, thay thế bit thứ i3 bởi
bit thứ i2.
Ví dụ ở IP, bit thứ 1 được thay thế bởi bit thứ 58; bit thứ 58 ñược thay thế bởi bit
thứ 55; bit thứ 55 ñược thay thế bởi bit thứ 13... Ở IP−1, bit thứ 58 ñược thay thế bởi
bit thứ 1; bit thứ 55 ñược thay thế bởi bit thứ 58; bit thứ 13 ñược thay thế bởi bit
thứ 55...
2.1.2.3
Hàm f
Hàm f nhận 2 khối Ri–1, ki ở ñầu vào, cho kết quả là khối yi ở ñầu ra. Ri–1 32 bits
nới rộng thành R’i–1 48 bits, rồi ñem XOR với ki thu ñược S. Chia S làm 8 phần,
mỗi phần 6 bits chịu biến ñổi thay thế Sj (j = 1, 2, …, 8), thu được S’ 32 bits. Hốn
vị S’, thu được yi.
Ri
Nới rộng
R’i
ki
S
S1
S2
S3
S4
S5
S’
Hốn vị
yi
yi = f(Ri
ki)
Ri
S’, yi:
32 bits
R’i
S, ki:
48 bits
Hình 2.4.
Hàm f
S6
S7
S8
20
Ri–1 32 bits nới rộng thành R’i–1 48 bits bằng cách ñọc 2 lần 16 bits của Ri–1. Nếu
chia Ri–1 thành 8 khối 4 bits, thì các bits đọc 2 lần chính là bit đầu tiên và bit cuối
cùng mỗi khối. Sau đó, các bản sao liền kề hốn đổi vị trí cho nhau. Cụ thể, thứ tự
bit của Ri–1 xuất hiện trong R’i–1 như sau:
32
1
2
3
4
5
4
5
6
7
8
9
8
9
10
11
12
13
12
13
14
15
16
17
16
17
18
19
20
21
20
21
22
23
24
25
24
25
26
27
28
29
28
29
30
31
32
1
Bảng 2.6.
Bảng R’i–1
Các khối thay thế Sj có đầu vào 6 bits, đầu ra 4 bits, hoạt động dựa trên các bảng
thay thế 4 dịng, 16 cột. Giả sử ñầu vào là a1 a2 a3 a4 a5 a6. Hai bit ñầu tiên và cuối
cùng lập thành số a1 a6. Giá trị thập phân của số này (0, 1, 2, 3) tương ứng với chỉ
số dòng trong bảng Sj. Các bit còn lại lập thành số a2 a3 a4 a5, giá trị thập phân
(0, 1, ..., 15) tương ứng với chỉ số cột trong bảng Sj. Đầu ra là giá trị nhị phân của ơ
nơi dịng a1 a6 và cột a2 a3 a4 a5 giao nhau. Ví dụ, nếu đầu vào của S8 là 100100 thì
giá trị ñầu ra là 0100, tức giá trị nhị phân của ô (2,2)=4.
0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
0
14
4
13
1
2
15 11
8
3
10
6
12
5
9
0
7
1
0
15
7
4
14
2
13
1
10
6
12 11
9
5
3
8
2
4
1
14
8
13
6
2
11 15 12
9
7
3
10
5
0
3
15 12
8
2
4
9
1
7
5
11
3
14 10
0
6
13
0
15
1
8
14
6
11
3
4
9
7
2
13 12
0
5
10
1
3
13
4
7
15
2
8
14 12
0
1
10
6
9
11
5
2
0
14
7
11 10
4
13
1
5
8
12
6
9
3
2
15
3
13
8
10
1
15
4
2
11
6
7
12
0
5
14
9
3
S1
S2
21
0
1
2
3
4
5
6
7
8
9
0
10
0
9
14
6
3
15
5
1
13 12
7
2
8
1
13
7
0
9
3
4
6
10
2
8
5
14 12 11 15
1
2
13
6
4
9
8
15
3
0
11
1
2
12
5
10 14
7
3
1
10 13
0
6
9
8
7
4
15 14
3
11
5
2
12
0
7
13 14
3
0
6
9
10
1
2
8
5
11 12
4
15
1
13
8
11
5
6
15
0
3
4
7
2
12
1
10 14
9
2
10
6
9
0
12 11
7
13 15
1
3
14
5
2
8
4
3
3
15
0
6
10
1
13
8
9
4
5
11 12
7
2
14
0
2
12
4
1
7
10 11
6
8
5
3
15 13
0
14
9
1
14 11
2
12
4
7
13
1
5
0
15 10
3
9
8
6
2
4
2
1
11 10 13
7
8
15
9
12
5
6
3
0
14
3
11
8
12
7
1
14
2
13
6
15
0
9
10
4
5
3
0
12
1
10 15
9
2
6
8
0
13
3
4
14
7
5
11
1
10 15
4
2
7
12
9
5
6
1
13 14
0
11
3
8
2
9
14 15
5
2
8
12
3
7
0
4
10
1
13 11
6
3
4
3
2
12
9
5
15 10 11 14
1
7
6
0
8
13
0
4
11
2
14 15
0
8
13
3
12
9
7
5
10
6
1
1
13
0
11
7
4
9
1
10 14
3
5
12
2
15
8
6
2
1
4
11 13 12
3
7
14 10 15
6
8
0
5
9
2
3
6
11 13
8
1
4
10
7
9
5
0
15 14
2
3
12
0
13
2
8
4
6
15 11
1
10
9
3
14
5
0
12
7
1
1
15 13
8
10
3
7
4
12
5
6
11
0
14
9
2
2
7
11
4
1
9
12 14
2
0
6
10 13 15
3
5
8
3
2
1
14
7
4
10
13 15 12
9
5
6
11
8
Bảng 2.7.
10 11 12 13 14 15
0
11
3
4
S3
S4
S5
S6
S7
S8
Bảng thay thế Sj
Biến ñổi cuối cùng trong hàm f là phép hoán vị khối S’ 32 bits. Quy tắc hoán vị
giống với hốn vị IP, nhưng dựa trên bảng dưới đây:
