TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN

TRƯỜNG ĐẠI HỌC VINH
KHOA CÔNG NGHỆ THÔNG TIN
----------o0o----------

ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC
NGÀNH: CƠNG NGHỆ THƠNG TIN

TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN

Giáo viên hướng dẫn : ThS. Trần Thị Kim Oanh
Sinh viên thực hiên

: Nguyễn Văn Thắng

Lớp

: 48K – CNTT

MSSV

: 0751070348

NGHỆ AN – 12/2011


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
LỜI CẢM ƠN
Em xin gửi lời cảm ơn chân thành tới quý thầy cô giáo khoa Công Nghệ
Thông Tin, trường Đại Học Vinh nói chung và thầy cơ giáo trong bộ mơn Các

Hệ Thống Thơng Tin nói riêng, đã giúp đỡ, tạo điều kiện cho em trong suốt quá
trình làm đồ án.
Đặc biệt em xin chân thành cảm ơn cô giáo ThS. Trần Thị Kim Oanh, người
đã giúp đỡ, chỉ bảo, hướng dẫn tận tình cho em trong quá trình làm đồ án. Trong
thời gian làm việc với cô, em không những học hỏi được nhiều kiến thức bổ ích
về các phương pháp mã hóa và tầm quan trọng của mã hóa dữ liệu trong thời đại
ngày nay mà còn học được tinh thần làm việc, thái độ nghiên cứu khoa học
nghiêm túc của cô.
Xin gửi lời cảm ơn chân thành đến gia đình, cha mẹ và bạn bè vì đã ln là
nguồn động viên to lớn, giúp đỡ con vượt qua những khó khăn trong suốt q
trình làm việc.
Mặc dù em đã cố gắng hoàn thành đề tài với tất cả nổ lực của bản thân
nhưng chắc chắn sẽ không tránh khỏi những thiếu sót. Em kính mong nhận được
sự cảm thơng và nhận được sự đóng góp của q thầy cô và các bạn.
Một lần nữa, em xin chân thành cảm ơn!

Ngày 05 tháng 12 năm 2011
Sinh viên thực hiện
Nguyễn Văn Thắng


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
MỤC LỤC
DANH MỤC VIẾT TẮT, THUẬT NGỮ ....................................................................................
DANH MỤC HÌNH VẼ ...............................................................................................................
MỞ ĐẦU ............................................................................................................................... - 1 CHƯƠNG 1. TỔNG QUAN VỀ HỆ MẬT MÃ ................................................................... - 2 -

1.1 Khái niệm về mã hóa thơng tin ...................................................................... - 2 1.1.1 Khái niệm ................................................................................................. - 2 1.1.2 Vai trị của mã hóa ................................................................................... - 2 1.1.3 Các thành phần của hệ mã hóa ............................................................... - 2 1.2 Tiêu chuẩn để đánh giá hệ mã hóa .................................................................. - 3 1.2.1 Độ an tồn của thuật tốn ....................................................................... - 3 1.2.2 Tốc độ mã hóa và giải mã ........................................................................ - 4 1.2.3 Phân phối khóa ........................................................................................ - 4 1.3 Khóa............................................................................................................... - 4 1.3.1 Khái niệm ................................................................................................. - 4 1.3.2 Ví dụ ......................................................................................................... - 4 1.4 Phân loại các thuật tốn mã hóa ...................................................................... - 4 1.4.1 Phân loại theo các phương pháp ............................................................. - 4 1.4.2 Phân loại theo số lượng khóa .................................................................. - 6 CHƯƠNG 2. MỘT SỐ PHƯƠNG PHÁP MÃ HÓA CỔ ĐIỂN ........................... - 8 2.1 Hệ mã hóa thay thế ........................................................................................... - 8 2.1.1 Hệ mã hóa CEASAR ................................................................................ - 8 2.1.2 Hệ mã hóa VIGENERE .......................................................................... - 9 2.2 Hệ mã hóa hốn vị ....................................................................................... - 11 2.2.1 Đảo ngược tồn bộ bản rõ ..................................................................... - 11 2.2.2 Mã hóa theo mẫu hình học ..................................................................... - 11 2.2.3 Đổi chỗ cột ............................................................................................. - 11 2.2.4 Hoán vị các ký tự của bản rõ theo chu kì cố định .................................. - 12 CHƯƠNG 3. MỘT SỐ THUẬT TỐN MÃ HĨA HIỆN ĐẠI ......................................... - 14 -

3.1 Thuật tốn mã hóa DES (Data Encryption Standard) .................................... - 14 3.1.1 Lịch sử ra đời .......................................................................................... - 14 3.1.2 Mơ tả thuật tốn DES ............................................................................ - 14 3.1.3 Giải mã DES .......................................................................................... - 24 3.1.4 Độ an tồn của thuật tốn ..................................................................... - 24 3.2 Thuật tốn mã hóa RSA (Rivest, Shamir, Adleman) ..................................... - 25 2.2.1 Khái quát về RSA ................................................................................... - 25 3.2.2 Mơ tả về thuật tốn ................................................................................ - 25 3.2.3 Một số phương pháp tấn công .............................................................. - 29 3.2.4 Đánh giá thuật toán ................................................................................ - 31 3.3. Thuật toán mã hóa MD5(Message-Digest algorithm 5) ............................... - 31 3.3.1 Hàm băm MD5 ....................................................................................... - 31 3.3.2 Thuật toán MD5 ...................................................................................... - 34 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ........................................................................... - 43 -


1. Kết quả đạt được .............................................................................................. - 43 2. Hướng phát triển .............................................................................................. - 43 3. Kết luận ............................................................................................................ - 43 TÀI LIỆU THAM KHẢO ................................................................................................... - 44 -


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN

DANH MỤC VIẾT TẮT, THUẬT NGỮ

STT
1
2
3
4
5
6

Từ viết tắt
DES
AES
RC
CATS
MD
SHA

7

FIPS

8
9

10

RSA
MIT
NSA

Giải nghĩa
Data Encryption Standard
Advanced Encryption Standard
Rivest Cipher
Carlisle Adams, and Stafford Tavares
Message Digest
Secure Hash Alorithm
Federal Information Processing Standard
(tiêu chuẩn xử lý thông tin liên bang)
Rivest, Shamir, Adleman
Học viện công nghệ Massachusetts
Cơ quan Bảo mật quốc gia Hoa Kỳ


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN

DANH MỤC HÌNH VẼ
Hình 1.1: Mơ hình mã hóa ................................................................... - 3 Hình 1.2: Mơ hình mã hóa khóa bí mật ............................................... - 6 Hình 1.3: Mơ hình mã hóa khóa cơng khai .......................................... - 7 Hình 2.1: Hình vng Vigenere ........................................................ - 10 Hình 3.1: Sơ đồ tổng qt mã hóa DES ............................................. - 15 Hình 3.2: Sơ đồ tạo khóa.................................................................... - 16 Hình 3.3: Biểu diễn dãy 64 bit x chia thành 2 thành phần L0,R0 ....... - 18 Hình 3.4: Sơ đồ chi tiết một vòng ....................................................... - 18 Hình 3.5: Sơ đồ hoạt động của hàm f................................................. - 19 Hình 3.6: Hốn vị mở rộng ................................................................ - 20 Hình 3.7: Sơ đồ thuật tốn RSA ......................................................... - 27 Hình 3.8: Mơ hình một vịng .............................................................. - 33 Hình 3.9: Sơ đồ vịng lặp của MD5.................................................... - 35 Hình 3.10: Sơ đồ khối tổng quát ........................................................ - 39 Hình 3.11: Sơ đồ xử lý 512 bit ........................................................... - 41 -


Tìm hiểu một số phương pháp mã hóa thơng tin
MỞ ĐẦU
Lí do chọn đề tài:
Hiện nay, nước ta đang trong giai đoạn tiến hành cơng nghiệp hóa, hiện đại

hóa đất nước. Tin học được xem là một trong những ngành mũi nhọn. Tin học
đã và đang đóng góp rất nhiều cho xã hội trong mọi khía cạnh của cuộc sống.
Mã hóa thơng tin là một ngành quan trọng và có nhiều ứng dụng trong đời
sống xã hội. Ngày nay, các ứng dụng mã hóa và bảo mật thơng tin đang được sử
dụng ngày càng phổ biến hơn trong các lĩnh vực khác nhau trên thế giới, từ các
lĩnh vực an ninh, quân sự, quốc phòng, … cho đến các lĩnh vực dân sự như
thương mại điện tử, ngân hàng, …
Ứng dụng mã hóa và bảo mật thơng tin trong hệ thống thương mại điện tử,
giao dịch chứng khoán,… đã trở nên phổ biến trên thế giới và sẽ ngày càng trở
nên quen thuộc với người dân Việt Nam. Tháng 7/2000, thị trường chứng khốn
lần đầu tiên được hình thành tại Việt Nam, các thẻ tín dụng bắt đầu được sử
dụng, các ứng dụng hệ thống thương mại điện tử đang ở bước đầu được quan
tâm và xây dựng. Do đó, mã hóa có vai trị rất quan trọng, đặc biệt là trong giao
dịch điện tử. Nó giúp đảm bảo bí mật, tồn vẹn của thơng tin, khi thơng tin đó
được truyền trên mạng. Mã hóa cũng là nền tảng của kĩ thuật chữ ký điện tử, hệ
thống PKI (Public key infrastructure – Hạ tầng khóa cơng khai), .... Chính vì vậy
em đã chọn “Tìm hiểu các thuật tốn mã hóa thơng tin” làm bài đề tài tốt
nghiệp của mình.
Cấu trúc đề tài như sau:
 Chương 1: Tổng quan về hệ mật mã
 Chương 2: Một số phương pháp mã hóa cổ điển
 Chương 3: Một số thuật tốn mã hóa hiện đại

-1-


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
CHƯƠNG 1. TỔNG QUAN VỀ HỆ MẬT MÃ
1.1 Khái niệm về mã hóa thơng tin
1.1.1 Khái niệm

Mã hóa thơng tin là chuyển đổi thông tin từ dạng rõ (dạng đọc được) sang
dạng mờ (dạng không thể đọc được) và ngược lại. Nhằm mục đích ngăn chặn
nguy cơ truy cập thơng tin truyền đi trên mạng một cách bất hợp pháp. Thông
tin sẽ được truyền đi trên mạng dưới dạng mờ và không thể đọc được với bất kỳ
ai cố tình muốn lấy thơng tin đó [1, 2, 3].
Khi chúng ta có nhu cầu trao đổi thơng tin, thì Internet là mơi trường khơng
an tồn, đầy rủi ro và nguy hiểm, khơng có gì đảm bảo rằng thơng tin mà chúng
ta truyền đi khơng bị đọc trộm trên đường truyền. Vì vậy mã hóa là biện pháp
giúp ta bảo vệ chính mình cũng như thơng tin mà ta gửi đi.
Ngồi ra mã hóa cịn đảm bảo tính tồn vẹn của dữ liệu.
1.1.2 Vai trị của mã hóa
Các hệ mã hóa phải thực hiện được các vai trị sau.
 Các hệ mã hóa phải che dấu được nội dung của văn bản rõ (PlainText) để
đảm bảo sao cho chỉ người chủ hợp pháp của thơng tin mới có quyền truy
cập thơng tin, hay nói cách khác là chống truy cập không đúng quyền hạn.
 Tạo các yếu tố xác thực thông tin, đảm bảo thông tin lưu hành trên hệ
thống đến người nhận hợp pháp xác thực.
 Tổ chức các sơ đồ chữ ký điện tử, đảm bảo khơng có hiện tượng giả mạo,
mạo danh để gửi thông tin trên mạng.
Ưu điểm lớn nhất của các hệ mã hóa là có thể đánh giá được độ phức tạp của
tính tốn mà “kẻ địch” phải giải quyết bài tốn để có thể lấy được thơng tin của
dữ liệu. Tuy nhiên mỗi hệ mã hóa đều có một số ưu và nhược điểm khác nhau,
nhưng nhờ đánh giá được độ phức tạp tính tốn, mức độ an tồn của mỗi hệ mã
hóa mà ta có thể ứng dụng cụ thể tùy theo yêu cầu về độ an toàn [1, 2].
1.1.3 Các thành phần của hệ mã hóa
Một hệ mã hóa là một bộ 5 (P, C, D, K, E) thõa mã các điều kiện sau:
- P là một tập hợp hữu hạn các bản rõ (PlainText), nó cịn được gọi là
khơng gian bản rõ.
-2-



TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN

- C là tập hợp hữu hạn các bản mã (CipherText), nó cịn được gọi là
khơng gian bản mã. Mỗi phần tử của C có thể nhận được bằng cách áp
dụng phép mã hóa Ek lên một phần tử của P.
- K là tập hợp hữu hạn các khóa hay cịn gọi là khơng gian khóa. Đối với
mỗi phần tử k của K được gọi là một khóa (Key). Số lượng của khơng
gian khóa phải đủ lớn để “kẻ địch” khơng đủ thời gian để thử mọi khóa
(phương pháp vét cạn).
- E và D lần lượt là tập luật mã hóa và giải mã. Với mỗi k của K có một
quy tắc mã hóa ek: PC và một quy tắc giải mã tương ứng dk € D. Mỗi
ek: PC và dk: CP là những hàm mà: dk(ek(x))=x với mọi bản rõ x €
P.

Hình 1.1: Mơ hình mã hóa
1.2 Tiêu chuẩn để đánh giá hệ mã hóa
1.2.1 Độ an tồn của thuật tốn
Ngun tắc đầu tiên trong mã hoá là “Thuật toán nào cũng có thể bị phá vỡ”.
Các thuật tốn khác nhau cung cấp mức độ an toàn khác nhau, phụ thuộc vào độ
phức tạp để phá vỡ chúng. Tại một thời điểm, độ an tồn của một thuật tốn phụ
thuộc [3].
o Nếu chi phí hay phí tổn cần thiết để phá vỡ một thuật tốn lớn hơn giá
trị của thơng tin đã mã hóa thuật tốn thì thuật tốn đó tạm thời được
coi là an toàn.
o Nếu thời gian cần thiết dùng để phá vỡ một thuật toán là quá lâu thì
thuật tốn đó tạm thời được coi là an tồn.

-3-



TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
o Nếu lượng dữ liệu cần thiết để phá vỡ một thuật toán quá lớn so với
lượng dữ liệu đã được mã hố thì thuật tốn đó tạm thời được coi là an
tồn.
1.2.2 Tốc độ mã hóa và giải mã
Khi đánh giá hệ mã hóa phải chú ý đến tốc độ mã hóa và giải mã. Hệ mã hóa
tốt thì thời gian mã hóa và giải mã nhanh.
1.2.3 Phân phối khóa
Một hệ mã hóa phụ thuộc vào khóa, khóa này được truyền cơng khai hay
truyền bí mật. Phân phối khóa bí mật thì chi phí sẽ cao hơn so với các thuật tốn
mã hóa khóa cơng khai. Vì vậy đây cũng là một tiêu chí khi lựa chọn hệ mã hóa.
1.3 Khóa
1.3.1 Khái niệm
Một khóa mã hóa là một phần thơng tin đặc biệt được kết hợp với một
thuật toán để thi hành mã hóa và giải mã. Mỗi khóa khác nhau có thể tạo ra
các văn bản mã hóa khác nhau, nếu khơng chọn đúng khóa thì khơng thể mở
được tài liệu đã mã hóa trên, cho dù biết được thuật tốn trên dùng thuật
tốn mã hóa gì, sử dụng khóa càng phức tạp thì độ an tồn của dữ liệu càng
lớn [1, 2, 3].
1.3.2 Ví dụ
Mã hóa nội dung của một bức thư với khóa là “Thay thế mỗi ký tự xuất hiện
trong bức thư bằng ký tự đứng thứ 2 sau nó”. Cùng thật tốn trên nhưng sử dụng
khóa là “Thay thế mỗi ký tự xuất hiện trong bức thư bằng ký tự đứng thứ 3 sau
nó”. Như vậy kết quả của một bức thư có nội dung như nhau sau khi sử dụng hai
khóa khác nhau sẽ có hai bản mã khác nhau.
1.4 Phân loại các thuật toán mã hóa
1.4.1 Phân loại theo các phương pháp
1.4.1.1 Mã hố cổ điển
Xuất hiện trong lịch sử, thuật toán sử dụng khóa đơn giản, dễ hiểu. Là

phương pháp mà từng ký tự (hay từng nhóm ký tự) trong bản rỏ được thay thế
bằng một ký tự (hay nhóm ký tự) khác tạo nên bản mã. Bên nhận chỉ cần đảo
ngược lại trình tự thay thế trên thì sẽ nhận được bản rõ ban đầu [1, 3].
-4-


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
Mã hóa cổ điển có hai phương pháp nổi bật là: Mã hóa thay thế và mã hóa
hốn vị.
Các hệ mã hóa thường được sử dụng trong lịch sử là: Hệ mã hóa Ceasar,
Vigenere, Hill…
1.4.1.2 Mã hóa đối xứng
Mã hóa đối xứng hay mã hóa chia sẻ khóa là mơ hình mã hóa hai chiều, có
nghĩa là tiến trình mã hóa và giải mã đều dùng chung một khóa. Khóa này được
chuyển giao bí mật giữa hai đối tượng tham gia giao tiếp. Khóa này có thể được
cấu hình trong phần mềm (software) hoặc được mã hóa trong phần cứng
(hardware). Mã hóa đối xứng thực hiện nhanh nhưng có thể gặp rủi ro nếu khóa
bị đánh cắp [1, 3].
Một số thuật tốn mã hóa đối xứng nổi tiếng như: DES, AES, RC2, RC4,
RC5, RC6…
Ngồi ra cịn một số thuật tốn như: Skipjact, Blowfish, CATS-128.
1.4.1.3 Mã hóa bất đối xứng
Mã hóa bất đối xứng là mơ hình mã hóa hai chiều sử dụng một cặp khóa là
khóa chung (Public Key) và khóa riêng (Private Key). Trong đó khóa chung
Public Key có thể được công bố rộng rãi. Thông thường thông tin được người
gửi sử dụng khóa Public Key để mã hóa và gửi đi. Người nhận thơng tin sẽ dùng
khóa Private Key để giải mã. Khóa Private Key chỉ do một người giữ do đó các
phương pháp mã hóa bất đối xứng đảm bảo tính bí mật hơn. Một điều quan
trọng của phương pháp mã hóa này là cặp khóa Public Key và Private Key phải
tương đồng nhau. Có nghĩa là chỉ có Private Key trong cùng một cặp khóa mới

có thể giải mã được dữ liệu đã mã hóa bởi khóa Public Key tương ứng [1, 2, 3].
Thuật tốn mã hóa bất đối xứng nổi tiếng và được sử dụng nhiều nhất hiện
nay là RSA.
Ngồi ra cịn một số thuật tốn khác như: Hellman, Elgamal…
1.4.1.4 Mã hóa hàm băm
Là cách thức mã hóa một chiều tiến hành biến đổi bản rõ thành bản mã mà
không bao giờ giải mã được. Người ta ví loại mã hóa này như một củ hành được
băm nhuyễn thì sẽ khơng bao giờ tái tạo lại được củ hành ban đầu [1, 2, 3].

-5-


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
Trong xử lý hàm băm, dữ liệu đầu vào có thể khác nhau về độ dài, nhưng độ
dài của xử lý băm luôn xác định. Hàm băm được xử lý trong mô hình xác thực
mật khẩu.
Một số thuật tốn mã hóa hàm băm thường dùng như: MD4, MD5, SHA…
1.4.2 Phân loại theo số lượng khóa
1.4.2.1 Mã hóa khóa bí mật
Mã hóa khóa bí mật là thuật tốn mà tại đó khóa giải mã có thể được tính
tốn từ khóa mã hóa. Trong rất nhiều trường hợp khóa mã hóa và khóa giải mã
là giống nhau. Thuật toán này yêu cầu người gửi và người nhận thỏa thuận một
khóa trước khi thơng tin được gửi đi và khóa này phải đảm bảo tính bí mật. Độ
an tồn của thuật này phụ thuộc nhiều vào độ bí mật của khóa, nếu để lộ khóa
thì thì bất kì người nào cũng có thể mã hóa và giải mã thông tin một cách dễ
dàng [1, 2, 3].

Hình 1.2: Mơ hình mã hóa khóa bí mật
Trong đó :
K1 có thể trùng K2.

K1 có thể được tính từ K2.
K2 có thể được tính từ K1.
Mã hóa khóa bí mật thường được sử dụng cho các trường hợp dễ chuyển
khóa. Tức là người nhận và người gửi có thể trao đổi khóa cho nhau an tồn,
khó bị kẻ khác tấn cơng. Thường dùng để trao đổi trong văn phịng.
Một số vấn đề liên quan
 Các phương pháp mã hóa khóa bí mật địi hỏi người mã hóa và người
giải mã phải cùng chung một khóa hoặc là có thể biết khóa của nhau, khi
đó khóa phải được giữ bí mật tuyệt đối. Do đó kẻ địch dễ dàng xác định
được một khóa nếu biết khóa kia.

-6-


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
 Phương pháp này khơng đảm bảo được sự an tồn vì có xác suất cao
khóa người gửi bị lộ. Khóa phải được gửi đi trên kênh an toàn nếu kẻ địch
tấn cơng trên kênh này có thể phát hiện ra khóa.
 Vấn đề quản lý và phân phối khóa là khó khăn và phức tạp, người gửi và
người nhận phải thống nhất với nhau về khóa việc thay đổi khóa là khó
khăn và dễ bị lộ.
1.4.2.2 Mã hóa khóa cơng khai
Mã hóa khóa cơng khai là các thuật tốn sử dụng khóa mã hóa và khóa giải
mã là hồn tồn khác nhau. Hơn nữa khóa giải mã khơng thể tính tốn được từ
khóa mã hóa [1, 2, 3].
Khác với mã hóa khóa bí mật, khóa mã hóa của thuật tốn mã hóa cơng khai
được cơng bố rộng rãi. Một người bất kì có thể sử dụng khóa cơng khai để mã
hóa thơng tin, nhưng chỉ có người nhận thơng tin có khóa giải mã phù hợp với
khóa mã hóa để giải mã thơng tin đó.
Mơ hình mã hóa khóa cơng khai :


Hình 1.3: Mơ hình mã hóa khóa cơng khai
Trong đó :
Khóa mã hóa khơng thể giống khóa giải mã.
Khóa giải mã khơng thể được tính từ khóa mã hóa.
Một điều đặc biệt của loại mã hóa này là cả khóa cơng khai và bản mã có thể
được gửi đi trên kênh khơng an tồn mà thơng tin vẫn khơng hoặc khó bị đọc
trộm dù biết được khóa mã hóa.
Chính vì mức độ an tồn cao nên mã hóa khóa cơng khai được sử dụng trên
mạng cơng khai Internet. Mã hóa khóa cơng khai có nhiều ứng dụng quan trọng
trong các hệ thống lớn.
-7-


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
CHƯƠNG 2. MỘT SỐ PHƯƠNG PHÁP MÃ HÓA CỔ ĐIỂN
2.1 Hệ mã hóa thay thế
2.1.1 Hệ mã hóa CEASAR
Hệ mã hóa CEASAR là một ví dụ điển hình cho hệ mã hóa thay thế. Nó làm
việc trong bảng chữ cái tiếng Anh 26 ký tự [1, 3]. Ceasar sử dụng các số nguyên
thay cho các ký tự, đánh số các ký tự trong bảng chử cái theo thứ tự bảng sau.

Các phép tốn số học được thực hiên trên Modul 26 (có nghĩa là 26 tương
ứng với 0, 27 tương ứng với 1, 28 tương ứng với 2,…, 79 = 26x3 + 1 tức 79
tương ứng với 1).
Hệ CAESAR sử dụng thuật tốn mã hóa Ek, trong đó mỗi ký tự được thay
thế bởi một ký tự khác được xác định bằng cách dịch ký tự cần mã hóa sang phải
k bước theo modul 26.
Ek() = ( + k) MOD 26.
Với  là một ký tự, 0  k  26, MOD là phép chia lấy phần dư.

Thuật toán giải mã tương ứng Dk là lùi lại k bước trong bảng chữ cái theo
modul 26.
Dk() = ( - k) MOD 26
Không gian khóa của hệ CEASAR bao gồm 26 số: 0, 1, 2, …, 25.
Ví dụ: Với k = 3, A được thay bằng D, B được thay bằng E,…, W được thay
bằng Z,…, Y được thay bằng B và Z được thay bằng C. Ta có:
Bảng chữ cái gốc.

Bảng chữ cái dùng để mã hóa.

-8-


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
Trong trường hợp này bản rõ “KHOA CNTT” được mã hóa thành “NKRD
FQWW”, (Chú ý: Các ký tự trống trong bảng mã được bỏ đi để đảm bảo tính an
tồn).
Hệ CEASAR là hệ mã hóa cũ và khơng an tồn vì khơng gian khóa của nó
rất nhỏ, do đó có thể thám mã theo phương pháp vét cạn. Khóa giải mã có thể
tính ngay ra được từ khóa mã hóa. Do chỉ có 26 khóa nên ta có thể thử lần lượt
các khóa cho đến khi tìm được khóa đúng.
2.1.2 Hệ mã hóa VIGENERE
Hệ mã hóa này được đặt theo tên của một nhà mật mã người Pháp Blaise De
Vigenere (1523 – 1596) [1, 3].
Vinegere là một phương pháp mã hóa văn bản bằng cách sử dụng xen kẽ một
số phép mã hóa CEASAR khác nhau dựa trên các chữ cái của một từ khóa.
Hình vng VIGENERE được sử dụng để mã hóa và giải mã. (Hình 2.1)
Mỗi cột của hình vng Vigenere có thể xem như là một hệ CEASAR, với
các khóa: 0, 1, 2,...., 25. Để mã hóa thì bản rõ được đọc từ các hàng và khóa
được đọc từ các cột.

Ví dụ: Mã hóa bản “DAI HOC VINH” với từ khóa “ KHOA KINH TE”.
Đầu tiên ta tìm điểm giao của hàng D cột K ta được N, tiếp tục ta tìm điểm giao
của hàng A cột H ta được H. Cứ như vậy ta được bản mã là “ NHW HYK
IPGL” . Ta sẽ thu được bản mã tưng tự nếu ta đọc bản rõ tưng ứng với cột và
khóa đọc tưng ứng với hàng. Muốn giải mã thơng tin vừa mã hóa trên ta thực
hiện bằng cách, ta nhìn vào hàng nào chứa N trong cột K, ta tìm được chữ D,
tương tự nhìn vào hàng nào chứa H trong cột H, ta tìm được chữ A. Cứ như vậy
ta sẽ tìm được bản rõ là “DAI HOC VINH”.
Trong ví dụ trên thì độ dài bản rõ bằng độ dài khóa. Nhưng trong thực tế độ
dài bản rõ thường dài hơn rất nhiều so với khóa. Như vậy để mã hóa hay giải mã
thì ta phải áp dụng từ khóa một cách tuần hồn. Nghĩa là từ khóa được lặp đi lặp
lại nhiều lần sao cho các ký hiệu trong bản rõ phải được đọc hết.
Ta thấy rằng trong hệ mã hóa VIGENERE, với khóa có độ dài d thì sẽ có 26 d
khóa hợp lệ. Vì vậy chỉ cần với giá trị d nhỏ thì phương pháp thám mã vét cạn
cũng đòi hỏi khá nhiều thời gian.

-9-


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN

A B C D E F G H I J K L MN O P Q R S T U V WX Y Z
B C D E F G H I J K L MN O P Q R S T U V WX Y Z A
C D E F G H I J K L MN O P Q R S T U V WX Y Z A B
D E F G H I J K L MN O P Q R S T U V WX Y Z A B C
E F G H I J K L MN O P Q R S T U V WX Y Z A B C D
F G H I J K L MN O P Q R S T U V WX Y Z A B C D E
G H I J K L MN O P Q R S T U V WX Y Z A B C D E F
H I J K L MN O P Q R S T U V WX Y Z A B C D E F G
I J K L MN O P Q R S T U V WX Y Z A B C D E F G H

J K L MN O P Q R S T U V WX Y Z A B C D E F G H I
K L MN O P Q R S T U V WX Y Z A B C D E F G H I J
L MN O P Q R S T U V WX Y Z A B C D E F G H I J K
MN O P Q R S T U V WX Y Z A B C D E F G H I J K L
N O P Q R S T U V WX Y Z A B C D E F G H I J K L M
O P Q R S T U V WX Y Z A B C D E F G H I J K L MN
P Q R S T U V WX Y Z A B C D E F G H I J K L MN O
Q R S T U V WX Y Z A B C D E F G H I J K L MN O P
R S T U V WX Y Z A B C D E F G H I J K L MN O P Q
S T U V WX Y Z A B C D E F G H I J K L MN O P Q R
T U V WX Y Z A B C D E F G H I J K L MN O P Q R S
U V WX Y Z A B C D E F G H I J K L MN O P Q R S T
V WX Y Z A B C D E F G H I J K L MN O P Q R S T U
WX Y Z A B C D E F G H I J K L MN O P Q R S T U V
X Y Z A B C D E F G H I J K L MN O P Q R S T U V W
Y Z A B C D E F G H I J K L MN O P Q R S T U V WX
Z A B C D E F G H I J K L MN O P Q R S T U V WX Y
Hình 2.1: Hình vng Vigenere

- 10 -


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
2.2 Hệ mã hóa hốn vị
Hệ mã hóa hốn vị hay cịn gọi là hệ mã hóa đổi chỗ. Là hệ mã hóa mà các
ký tự của bản rõ vẫn được giữ nguyên, nhưng thứ tự của chúng được đổi chỗ
vòng quanh [1, 3].
Phương pháp này có các kỹ thuật mã hóa sau:
2.2.1 Đảo ngược toàn bộ bản rõ
Nghĩa là bản gốc được viết theo thứ tự ngược lại từ sau ra trước, để tạo bản

mã. Đây là phương pháp mã hóa đơn giản nhất vì vậy khơng đảm bảo an tồn.
Ví dụ: PlainText: IT IS ME
Bản mã: EMSITI
2.2.2 Mã hóa theo mẫu hình học
Bản gốc được sắp xếp lại theo một mẫu hình học nào đó, thường là một
mảng hoặc ma trận hai chiều.
Ví dụ: Bản rõ “KHOA CONG NGHE THONG TIN” được viết theo ma trận
4x5 như sau:

Nếu lấy các ký tự ra theo số thứ tự cột 2,5,4,1,3 thì ta thu được bản mã
“HCAKONGNOGEOHHTGNINT”.
2.2.3 Đổi chỗ cột
Đầu tiên biểu diễn các ký tự trong ban rõ thành dạng hình chữ nhật theo cột,
sau đó các cột được sắp xếp lại và các chữ cái được lấy ra theo hàng ngang.

- 11 -


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
Ví dụ: Bản rõ là “KHOA CONG NGHE THONG TIN” được viết dưới dạng
ma trận 4x5 theo cột như sau:

Vì có 5 cột nên ta có thể sắp xếp lại theo 5!=120 cách khác nhau. Để tăng độ
an tồn có thể chọn một trong các cách sắp xếp lại đó.
Nếu ta chuyển vị trí các cột theo các cột theo thứ tự 5,3,4,2,1. Rồi lấy các ký
tự ra theo hàng ngang ta sẽ được bản mã là:
“GNTCKTGHOHIHONONENGA”.
Lưu ý: Các ký tự cách trống được bỏ đi.
2.2.4 Hoán vị các ký tự của bản rõ theo chu kì cố định
Nếu hàm f là một hoán vị của một khối gồm d ký tự thì khóa mã hóa được

biểu diễn bởi K(d, f).
Do vậy, bản rõ:
M=m1m2...mdmd+1...m2d.
Với mi là các ký tự, và bản mã sẽ được mã hóa thành:
Ek(M)= mf(1)mf(2)…mf(d)md+f(1)…md+f(d).
Trong đó mf(1)mf(2)…mf(d) là một hoán vị của m1m2...md.

- 12 -


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
Ví dụ: Mã hóa bản rõ “BAO MAT” chọn d=6 và f hoán vị dãy i= 123456
thành f(i)=351462.

Theo bảng trên ta thấy ký tự đầu sau khi hoán vị chuyển đến vị trí thứ 3, ký
tự thứ 2 chuyển tới vị trí thứ 5, ký tự thứ 3 chuyển tới vị trí thứ 1,… Như vậy
sau khi mã hóa ta thu được bản mã là “OABMTA”.
Nếu kích thước bản rõ lớn hơn nhiều so với d thì ta sẽ phải chia bản rõ thành
các khối d ký tự và tiến hành mã hóa theo từng khối. Ví dụ:
Bản rõ “KHOA CONG NGHE THONG TIN”, giả sử d = 5, và f hoán vị dãy
i = 12345 thành f(i) = 35142.
Ta thu được bản mã “OCKAHGGONNTOHHETNIG”

- 13 -


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
CHƯƠNG 3. MỘT SỐ THUẬT TỐN MÃ HĨA HIỆN ĐẠI
3.1 Thuật tốn mã hóa DES (Data Encryption Standard)
3.1.1 Lịch sử ra đời

Khoảng những năm 1970, tiến sĩ Horst Feistel đã đặt nền móng đầu tiên cho
chuẩn mã hóa DES với phương pháp mã hóa Feistel Cipher. Vào năm 1976 Cơ
quan Bảo mật quốc gia Hoa Kỳ (NSA) đã công nhận DES dựa trên phương pháp
Feistel là chuẩn mã hóa dữ liệu. Kích thước khóa ban đầu của DES là 128 bit
nhưng tại bản cơng bố FIPS kích thước được rút xuống 56 bit để tăng tốc độ xử
lý và đưa ra các tiêu chuẩn thiết kế một chuẩn mã hóa dữ liệu [1].
Nội dung phương pháp mã hóa DES:
DES thực hiện mã hóa dữ liệu qua 16 vịng lặp mã hóa, mỗi vịng sử dụng
một khóa chu kỳ 48 bit được tạo ra từ khóa ban đầu có độ dài 56 bit. DES sử
dụng 8 bảng hằng số S-box để thao tác.
3.1.2 Mơ tả thuật tốn DES
3.1.2.1 Sơ đồ tổng qt
Phương pháp DES mã hóa khối thơng tin x có độ dài 64 bit với khóa k có độ
dài 56 bit thành khối y có độ dài 64 bit.
Nền tảng để xây dựng khối của DES là sự kết hợp đơn giản của các kỹ thuật
thay thế và hoán vị bản rõ dựa trên khóa, đó là vịng lặp. DES sử dụng 16 vòng
lặp áp dụng cùng một kiểu kết hợp các kỹ thuật trên khối bản rõ.
Thuật toán chỉ sử dụng các phép tốn số học và logic thơng thường trên các
số 16 bit, vì vậy nó dễ dàng thực hiện vào những năm 1970 trong điều kiện về
công nghệ phần cứng lúc bấy giờ.

- 14 -


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
Sơ đồ tổng qt:
Plaintext
IP
L0


R0


K
1

R1=L0(R0,K1)

L1=R0


K
2

L2=R1

R2=L1(R1,K2)

L15=R14

R15=L14(R14,K15)


R16=L15(R15,K16
)

K16
L16=R15

IP -1

Ciphertext

Hình 3.1: Sơ đồ tổng qt mã hóa DES

- 15 -


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
Q trình có 16 vịng thực hiện giống nhau trong q trình xử lý. Ngồi ra có
hai lần hốn vị đầu IP và cuối IP-1, hai hoán vị này được sử dụng với mục đích
đưa thơng tin vào và lấy thơng tin ra.
Muốn vào vịng mã hóa thì khối thơng tin x ban đầu 64 bit được chia làm hai
khối, mỗi khối 32 bit. Hàm f làm biến đổi một nữa của khối đang xử lý với một
khóa con tương ứng với vịng mã hóa.
Trong đầu ra của hàm có hàm f được kết hợp với nửa khối cịn lại bằng phép
tốn XOR, và hai phần được trao đổi để xử lý trong chu trình kế tiếp.
Cứ thực hiện các vịng như vậy cho tới vịng cuối cùng thì hai phần khơng bị
tráo đổi nữa, chính vì điều này mà q trình mã hóa và giải mã là giống nhau.
3.1.2.2 Tạo khóa
Quá trình mã hóa được thực hiện 16 vịng, mỗi vịng cần một khóa. Như vậy
từ khóa ban đầu tạo ra 16 khóa con cho 16 vịng lặp tương ứng.
Sơ đồ q trình tạo khóa.

Hình 3.2: Sơ đồ tạo khóa
Theo sơ đồ ta thấy đầu tiên khóa K có độ dài 64 bit, sau đó được giảm xuống
56 bit bằng cách loại bỏ 8 bit chẵn lẻ. Sự loại bỏ được thực hiên khi đi qua PC1.

- 16 -



TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
Bảng PC1 :

Như vậy các bit ở vị trí 8, 16, 24, 32, 40, 48, 56, 64 bị loại bỏ. 56 bit thu
được chia làm hai phần, mỗi phần 28 bit, các phần được xử lý độc lập nhau. Các
phần này được dịch 1 hay 2 bit là phụ thuộc vào vòng đó. Số bit dịch được cho
trong bảng sau.

Sau khi dịch bit, 56 bit này được chọn ra 48 bit. Bởi vì sự thực hiện đổi chỗ
thứ tự các bit như là sự lựa chọn một tập con các bit, nó cịn được gọi là hốn vị
nén hoặc hốn vị lựa chọn. Sự thực hiện này cung cấp một tập hợp các bit cùng
cỡ với đầu ra của hoán vị mở rộng. Bảng PC2 định nghĩa hoán vị nén (cũng gọi
là hốn vị lựa chọn). Ví dụ, bit ở vị trí 33 của khóa được dịch chuyển tới vị trí
35 của đầu ra và bit ở vị trí 8 của khóa bị bỏ qua.
Bảng PC2( hoán vị nén).

Như vậy sau khi đi qua PC2 còn lại 48 bit, 48 bit này sẽ được sử dụng làm
khóa K1 để sử dụng trong vịng mã hóa.
Hai phần, mỗi phần 28 bit sau khi được dịch bit ở lần thứ nhất, tiếp tục dịch
bit ở lần thứ 2 và qua bảng PC2 để hoán vị nén 48 bit và làm K2.
Quá trình cứ tiếp tục như vậy ta thu được 16 khóa Ki (i=1…16).
3.1.2.3 Hốn vị khởi đầu
Mục đích của hốn vị khởi đầu là đổi chỗ các bit của khối dữ liệu vào thơng
qua bảng IP. Nó khơng ảnh hưởng đến sự an toàn của DES.

- 17 -


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
Với khối dữ liêu vào x 64 bit cho trước, một xâu bit x0 sẽ được xây dựng

bằng cách hoán vị các bit của x theo phép hoán vị cố định ban đầu IP. Ta viết
x0=IP(x)=L0R0 trong đó L0 gồm 32 bit đầu và R0 gồm 32 bit cuối.
L0

R0
x0

Hình 3.3: Biểu diễn dãy 64 bit x chia thành 2 thành phần L0,R0
Bảng hốn vị khởi đầu IP.

3.1.2.4 Mã hóa chi tiết một vịng
Q trình xử lý các vịng là giống nhau, ta xét q trình xử lý của một vịng i
với 1 i  16.
Li-1

Ri-1

f

Ki



Li

Ri

Hình 3.4: Sơ đồ chi tiết một vịng
Ta thấy:
Li = Ri-1

Ri =Li-1  f(Ri-1,Ki)

- 18 -


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
Hàm f có hai tham số là Ri-1 và Ki. Được thực hiện theo sơ đồ sau :

Hình 3.5: Sơ đồ hoạt động của hàm f
Ri-1 được mở rộng từ 32 bit thành 48 bit nhờ sự thay đổi thứ tự của các bit
bằng cách lặp lại một số bit nào đó, nó được hiểu như là một sự hốn vị mở
rộng.
Để xác định ở đầu vào có 32 bit, bit nào được lặp lại và xuất hiện tại vị trí
nào của đầu ra 48 bit người ta xác định như sau:
Đầu vào có 32 bit chia làm 8 bộ, mỗi bộ có 4 bit. Bit đầu tiên và bit cuối
cùng của mỗi bộ tương ứng với 2 bit của khối dữ liệu ra, trong khi bit thứ 2 và
bit thứ 3 của mỗi bộ tương ứng với một bit ở khối dữ liệu ra. Ví dụ, bit ở vị trí
thứ 3 của khối dữ liệu vào được chuyển tới vị trí thứ 4 trong khối dữ liệu ra, bit
thứ 8 trong khối dữ liệu vào thì được chuyển tới vị trí 11 và 13 trong khối dữ
liệu ra.

- 19 -


TÌM HIỂU CÁC THUẬT TỐN MÃ HĨA THƠNG TIN
Hộp E.

1 2 3 4

5 6 7 8


1 2 3 4 5 6
24

7 8 9 10 11 12

9 10 11 12

13 14 15 16

48

32

13 14 15 16 17 18 19 20 21 22 23

Hình 3.6: Hốn vị mở rộng
Như vậy 16 bit của Ri được hoán vị hai lần. Mặc dù khối dữ liệu ra rộng hơn
khối dữ liệu vào, nhưng một khối dữ liệu vào chỉ có duy nhất một khối dữ liệu
ra.
Như vậy E(Ri-1) là một dãy 48 bit. Thực hiện phép tốn XOR cho dãy bit
E(Ri-1) với khóa Ki. Ta thu được dãy 48 bit B. Biểu diễn B thành từng nhóm 6
bit B = B1B2B3B4B5B6B7B8.
- 20 -