BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2
======

TRẦN HOÀNG MINH

HỆ MÃ LUÂN PHIÊN VÀ ỨNG DỤNG
TRONG BẢO MẬT DỮ LIỆU VĂN BẢN

LUẬN VĂN THẠC SĨ MÁY TÍNH

HÀ NỘI, 2015


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2
======

TRẦN HOÀNG MINH

HỆ MÃ LUÂN PHIÊN VÀ ỨNG DỤNG
TRONG BẢO MẬT DỮ LIỆU VĂN BẢN

Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 01

LUẬN VĂN THẠC SĨ MÁY TÍNH
Ngƣời hƣớng dẫn khoa học: TS. Trịnh Đình Vinh

HÀ NỘI, 2015

1

LỜI CẢM ƠN

Luận văn này đƣợc hoàn thành tại Trƣờng Đại học Sƣ phạm Hà Nội 2
dƣới sự hƣớng dẫn khoa học của Tiến sĩ Kiều Văn Hƣng. Tác giả xin đƣợc
bày tỏ lòng biết ơn chân thành đối với thẫy hƣớng dẫn đã tận tâm giúp đỡ để
luận văn đƣợc hoàn thành.
Tác giả xin chân thành các ơn Ban Giám hiệu, Phòng Sau đại học
Trƣờng Đại học Sƣ phạm Hà Nội 2 và các thầy cô giáo đã giảng dạy, giúp đỡ
tác giả trong suốt quá trình học tập và nghiên cứu.
Tác giả chân thành cảm ơn các bạn học viên lớp K17 Khoa học máy
tính, cùng gia đình, ngƣời thân đã quan tâm, động viên, giúp đỡ tác giả trong
quá trình học tập và nghiên cứu.
Ngày 03 tháng 12 năm 2015
Học viên

Trần Hoàng Minh


2

LỜI CAM ĐOAN
Tôi xin cam đoan rằng số liệu và kết quả nghiên cứu trong luận văn này
là trung thực và không trùng lặp với các đề tài khác. Tôi cũng xin cam đoan
rằng mọi sự giúp đỡ cho việc thực hiện luận văn này đã đƣợc cảm ơn và các
thông tin trích dẫn trong luận văn đã đƣợc chỉ rõ nguồn gốc.
Ngày 03 tháng 12 năm 2015
Học viên


Trần Hoàng Minh


3

MỤC LỤC
LỜI CẢM ƠN ............................................................................................................. 1
LỜI CAM ĐOAN ....................................................................................................... 2
MỤC LỤC ................................................................................................................... 3
DANH MỤC HÌNH .................................................................................................... 5
MỞ ĐẦU ..................................................................................................................... 6
1. Lý do chọn đề tài .............................................................................................. 6
2. Mục đích nghiên cứu ........................................................................................7
3. Nhiệm vụ nghiên cứu .......................................................................................7
4. Đối tƣợng và phạm vi nghiên cứu ....................................................................7
5. Phƣơng pháp nghiên cứu ..................................................................................8
Chƣơng 1. TỔNG QUAN VỀ CÁC HỆ MẬT MÃ .................................................... 9
1.1. Sơ lƣợc về lịch sử mật mã .............................................................................9
1.2. Hệ thống mã hóa .......................................................................................... 17
1.3. Thám mã và tính an toàn các hệ mã ............................................................ 20
1.3.1. Lý thuyết mã hóa................................................................................20
1.3.2. Nguyên lý ...........................................................................................21
1.3.3. Những điều căn bản về mã hoá ..........................................................21
1.3.4. Độ an toàn của thuật toán ...................................................................24
1.3.5. Phân loại các thuật toán mã hoá .........................................................25
1.3.6. Mã hóa trên kênh truyền ....................................................................26
1.3.7. Mã khối tuyến tính .............................................................................27
1.3.8. Mã kết hợp .........................................................................................29
Chƣơng 2. MÃ LUÂN PHIÊN ................................................................................ 31

2.1. Tích không nhập nhằng ...............................................................................31
2.2. Mã luân phiên .............................................................................................. 33
2.3. Đặc trƣng của mã luân phiên .......................................................................40
Chƣơng 3. ỨNG DỤNG MÃ LUÂN PHIÊN TRONG BẢO MẬT DỮ LIỆU
VĂN BẢN ................................................................................................................. 51


4
3.1. Một sơ đồ mã hóa, giải mã sử dụng mã luân phiên .....................................51
3.2. Cài đặt chƣơng trình mã hoá, giải mã RSA-ALT thử nghiệm ....................52
3.2.1. Chức năng mã hóa..............................................................................55
3.2.2. Chức năng giải mã .............................................................................58
KẾT LUẬN ............................................................................................................... 61
TÀI LIỆU THAM KHẢO ......................................................................................... 62


5

DANH MỤC HÌNH
Hình 1.1: Sơ đồ hệ mật mã .............................................................................. 18
Hình 2.1. Các Overlap của hai phân tích của từ w. ....................................... 35
Hình 2.2. Hai phân tích của w trong (XY)+ và (XY)+ X –1 . ........................... 41
Hình 2.3. Các lớp thƣơng Ui , Vj của hai phân tích. ....................................... 46
Hình 2.4. Quan hệ của các lớp mã đã xét trên A*. ......................................... 47
Hình 3.1: Sơ đồ mã hóa kết hợp ALT - RSA ................................................. 51
Hình 3.2: Sơ đồ giải mã RSA –ALT ............................................................. 52
Hình 3.3: Giao diện chính của chƣơng trình ................................................... 53
Hình 3.4: Giao diện đăng ký .......................................................................... 54
Hình 3.5: Giao diện đăng nhập ....................................................................... 55
Hình 3.6: Tạo khóa và mã hóa dữ liệu ............................................................ 56

Hình 3.7: Xác nhận yêu cầu mã hóa ALT....................................................... 57
Hình 3.8. Tùy chọn lƣu kết quả....................................................................... 57
Hình 3.9: Xác nhận mã hóa RSA .................................................................... 57
Hình 3.10: Thông báo kết quả mã hóa thành công ......................................... 58
Hình 3.11: Giao diện giải mã tệp tin ............................................................... 58
Hình 3.12: Giải mã tệp tin ............................................................................... 59
Hình 3.13: Xác nhận giải mã tệp tin bằng RSA .............................................. 59
Hình 3.14: Xác nhận giải mã tệp tin bằng RSA .............................................. 60
Hình 3.15: Xác nhận giải mã ALT và lƣu tệp giải mã .................................... 60


6

MỞ ĐẦU

1. Lý do chọn đề tài
Lý thuyết mã bắt nguồn từ lý thuyết thông tin do C. E. Shannon khởi
xƣớng đã đặt nền móng toán học cho lý thuyết thông tin hiện đại. Do nhu cầu
thực tiễn, lý thuyết mã phát triển theo nhiều hƣớng khác nhau, chẳng hạn nhƣ
hƣớng nghiên cứu liên quan đến mã độ dài cố định, điển hình là mã sửa sai,
ứng dụng để phát hiện và sửa lỗi xuất hiện trên các kênh truyền tin; hay một
hƣớng nghiên cứu khác có liên quan đến mã độ dài biến đổi, đƣợc nghiên cứu
đầu tiên bởi Schüzenberger. Một số bài toán cơ bản trong nghiên cứu lý
thuyết mã là: các tính chất liên quan đến sự phân tích một từ thành dãy các từ
thuộc một tập cho trƣớc; tính chất không nhập nhằng của ngôn ngữ trong
quan hệ với mã; mã trong mối qua hệ với đại số, tổ hợp trên từ, lý thuyết ngôn
ngữ hình thức và otomat (xem [7], [8]).
Bảo mật thông tin là một hƣớng nghiên cứu luôn đƣợc nhiều ngƣời
quan tâm nhằm xây dựng những hệ mật mã với độ an toàn cao, nhƣng cho
đến nay vẫn chƣa có một hệ mật mã nào có thể có độ an toàn tuyệt đối. Đây là

động lực quan trọng thúc đẩy sự liên tục phải cải tiến, nghiên cứu xây dựng
các hệ mã mới, cả về khía cạnh lý thuyết cũng nhƣ thực hành.
Năm 2004, Phan Trung Huy, Vũ Thành Nam [4] đã đề xuất các hình
thức mã mới, là mã của một cặp hai ngôn ngữ (mã luân phiên, mã luân phiên
chẵn) dựa vào phân tích luân phiên của hai ngôn ngữ trên một bảng chữ và
thiết lập đƣợc một số tính chất cơ sở ban đầu về hai lớp mã mới này. Mã luân
phiên, mã luân phiên chẵn là một phát triển mở rộng tự nhiên, nhƣng không
tầm thƣờng của mã truyền thống. Trong khi mỗi mã truyền thống là một ngôn
ngữ X trên một bộ chữ nào đó thì mã luân phiên, mã luân phiên chẵn là một
cặp {X,Y} của hai ngôn ngữ mà mỗi một trong chúng không nhất thiết phải là


7

một mã truyền thống. Mặt khác, nếu X là một mã truyền thống thì {X, X} là
một mã luân phiên chẵn. Nhƣ vậy mã luân phiên, mã luân phiên chẵn là một
mở rộng thực sự của mã truyền thống, hứa hẹn một khả năng ứng dụng rộng
rãi hơn và khả năng thúc đẩy phát triển các nghiên cứu mới, sâu sắc hơn về
ngôn ngữ nói chung, lý thuyết mã nói riêng.
Với mong muốn tìm hiểu về các hệ mật mã và mã luân phiên, luân
phiên chẵn và những ứng dụng của các hệ mã này, tôi mạnh dạn chọn đề tài
“Hệ mã luân phiên và ứng dụng trong bảo mật dữ liệu văn bản” cho luận văn
tốt nghiệp thạc sĩ chuyên ngành Khoa học máy tính.
2. Mục đích nghiên cứu
Nghiên cứu cơ sở lý thuyết về mật mã, mã luân phiên và ứng dụng
chúng trong lĩnh vực an toàn, bảo mật dữ liệu.
3. Nhiệm vụ nghiên cứu
- Tìm hiểu các khái niệm cơ bản, ứng dụng trong bảo mật dữ liệu của
các hệ mật mã;
- Nghiên cứu cơ sở toán học, các đặc trƣng, thuật toán kiểm định mã

luân phiên, mã luân phiên chẵn;
- Đề xuất một sơ đồ mã hóa, giải mã sử dụng mã luân phiên hoặc mã
luân phiên chẵn và ứng dụng trong bảo mật dữ liệu. Xây dựng chƣơng trình
thử nghiệm và đánh giá kết quả thu đƣợc.
4. Đối tƣợng và phạm vi nghiên cứu
- Đối tƣợng nghiên cứu: Các hệ mật mã, mã luân phiên, mã luân phiên
chẵn.
- Phạm vi nghiên cứu: Nghiên cứu các khái niệm, kết quả cơ bản về các
hệ mật mã hiện đại, mã luân phiên, mã luân phiên chẵn và xây dựng một sơ
đồ mã hóa, giải mã sử dụng mã luân phiên hoặc mã luân phiên chẵn.


8
5. Phƣơng pháp nghiên cứu
- Nghiên cứu lý thuyết: Nghiên cứu các kết quả đã công bố trong lĩnh
vực liên quan. Trên cơ sở đó phân tích, tổng hợp, trình bày các kết quả đã
công bố.
- Nghiên cứu thực nghiệm: Áp dụng kết quả nghiên cứu lý thuyết vào
việc đề xuất một sơ đồ ứng dụng trong bảo mật dữ liệu, cài đặt chƣơng trình
thử nghiệm và đánh giá kết quả thu đƣợc.


9

Chƣơng 1
TỔNG QUAN VỀ CÁC HỆ MẬT MÃ
Chƣơng này trình bày những khái niệm, kết quả cơ bản trong [1-3, 5]
liên quan tới Luận văn, gồm những kiến thức cơ bản về các hệ mật mã đƣợc
sử dụng trong an toàn, bảo mật thông tin.
1.1. Sơ lƣợc về lịch sử mật mã

Mật mã học là ngành khoa học ứng dụng toán học vào việc biến đổi
thông tin thành một dạng khác với mục đích che dấu nội dung, ý nghĩa thông
tin cần mã hóa. Đây 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… Cùng với sự phát triển của khoa học máy
tính và Internet, các nghiên cứu và ứng dụng của khoa học mật mã ngày càng
trở nên đa dạng hơn, mở ra nhiều hƣớng nghiên cứu chuyên sâu vào từng lĩnh
vực ứng dụng đặc thù với những đặc trƣng riêng. Ứng dụng của khoa học mật
mã không chỉ đơn thuần là mã hóa và giải mã thông tin mà còn bao gồm
nhiều vấn đề khác nhau cần đƣợc nghiên cứu và giải quyết: chứng thực nguồn
gốc nội dung thông tin (kỹ thuật chữ ký điện tử), chứng nhận tính xác thực về
ngƣời sở hữu mã khóa (chứng nhận khóa công cộng), các quy trình giúp trao
đổi thông tin và thực hiện giao dịch điện tử an toàn trên mạng... Những kết
quả nghiên cứu về mật mã cũng đã đƣợc đƣa vào trong các hệ thống phức tạp
hơn, kết hợp với những kỹ thuật khác để đáp ứng yêu cầu đa dạng của các hệ
thống ứng dụng khác nhau trong thực tế, ví dụ nhƣ hệ thống bỏ phiếu bầu cử
qua mạng, hệ thống đào tạo từ xa, hệ thống quản lý an ninh của các đơn vị với
6 hƣớng tiếp cận sinh trắc học, hệ thống cung cấp dịch vụ multimedia trên


10
mạng với yêu cầu cung cấp dịch vụ và bảo vệ bản quyền sở hữu trí tuệ đối với
thông tin số...
Mật mã cổ điển:
Những bằng chứng sớm nhất về sử dụng mật mã học là các chữ tƣợng
hình không tiêu chuẩn tìm thấy trên các bức tƣợng Ai Cập cổ đại (cách đây
khoảng 4500). Những ký hiệu tỏ ra không phải để phục vụ mục đích truyền
thông tin bí mật mà có vẻ nhƣ là nhằm mục đích gợi nên những điều thần bí,

trí tò mò hoặc thậm chí để tạo sự thích thú cho ngƣời xem. Ngoài ra còn rất
nhiều ví dụ khác về những ứng dụng của mật mã học hoặc là những điều
tƣơng tự. Muộn hơn, các học giả về tiếng Hebrew có sử dụng một phƣơng
pháp mã hóa thay thế bảng chữ cái đơn giản chẳng hạn nhƣ mật mã
Atbash (khoảng năm 500 đến năm 600). Mật mã học từ lâu đã đƣợc sử dụng
trong các tác phẩm tôn giáo để che giấu thông tin với chính quyền hoặc nền
văn hóa thống trị. Ví dụ tiêu biểu nhất là "số chỉ kẻ thù của Chúa" (tiếng
Anh: Number of the Beast) xuất hiện trong kinh Tân Ƣớc của Cơ đốc giáo. Ở
đây, số 666 có thể là cách mã hóa để chỉ đến Đế chế La Mã hoặc là đến hoàng
đế Nero của đế chế này. Việc không đề cập trực tiếp sẽ đỡ gây rắc rối khi
cuốn sách bị chính quyền chú ý. Đối với Cơ đốc giáo chính thống thì việc che
giấu này kết thúc khi Constantine cải đạo và chấp nhận đạo Cơ đốc là tôn giáo
chính thống của đế chế. Ngƣời Hy Lạp cổ đại cũng đƣợc biết đến là đã sử
dụng các kỹ thuật mật mã (chẳng hạn nhƣ gậy mật mã). Cũng có những bằng
chứng rõ ràng chứng tỏ ngƣời La Mã nắm đƣợc các kỹ thuật mật mã (mật mã
Caesar và các biến thể). Thậm chí đã có những đề cập đến một cuốn sách nói
về mật mã trong quân đội La Mã; tuy nhiên cuốn sách này đã thất truyền.
Tại Ấn Độ, mật mã học cũng khá nổi tiếng. Trong cuốn sách Kama
Sutra, mật mã học đƣợc xem là cách những ngƣời yêu nhau trao đổi thông tin
mà không bị phát hiện.


11
Mật mã thời trung cổ:
Nguyên do xuất phát có thể là từ việc phân tích bản kinh Qur'an, do
nhu cầu tôn giáo, mà kỹ thuật phân tích tần suất đã đƣợc phát minh để phá vỡ
các hệ thống mật mã đơn ký tự vào khoảng năm 1000. Đây chính là kỹ
thuậtphá mã cơ bản nhất đƣợc sử dụng, mãi cho tới tận thời điểm của thế
chiến thứ II. Về nguyên tắc, mọi kỹ thuật mật mã đều không chống lại đƣợc
kỹ thuật phân tích mã (cryptanalytic technique) này cho tới khi kỹ thuật mật

mã dùng nhiều bảng chữ cái đƣợc Alberti sáng tạo (năm 1465).
Mật mã học (tuy âm thầm) ngày càng trở nên quan trọng dƣới tác động
của những thay đổi, cạnh tranh trong chính trị và tôn giáo. Chẳng hạn tại châu
Âu, trong và sau thời kỳ Phục hƣng, các công dân của các thành bang thuộc
Ý, gồm cả các thành bang thuộc giáo phận và Công giáo La Mã, đã sử dụng
và phát triển rộng rãi các kỹ thuật mật mã. Tuy nhiên rất ít trong số này tiếp
thu đƣợc công trình của Alberti (các công trình của họ không phản ảnh sự
hiểu biết hoặc tri thức về kỹ thuật tân tiến của Alberti) và do đó hầu nhƣ tất cả
những ngƣời phát triển và sử dụng các hệ thống này đều quá lạc quan về độ
an toàn. Điều này hầu nhƣ vẫn còn đúng cho tới tận hiện nay, nhiều nhà phát
triển không xác định đƣợc điểm yếu của hệ thống. Do thiếu hiểu biết cho nên
các đánh giá dựa trên suy đoán và hy vọng là phổ biến.
Mật mã học, phân tích mã học và sự phản bội của nhân viên tình báo,
của ngƣời đƣa thƣ, đều xuất hiện trong âm mƣu Babington diễn ra dƣới triều
đại của nữ hoàng Elizabeth I dẫn đến kết cục xử tử nữ hoàng Mary I của
Scotland. Một thông điệp đƣợc mã hóa từ thời "ngƣời dƣới mặt nạ sắt" (Man
in the Iron Mask) (đƣợc giải mã vào khoảng 1900 bởi Étienne Bazeries) cho
biết một số thông tin về số phận của tù nhân này (đáng tiếc thay là những
thông tin này cũng chƣa đƣợc rõ ràng cho lắm). Mật mã học, và những lạm
dụng của nó, cũng là những phần tử liên quan đến mƣu đồ dẫn tới việc xử


12
tử Mata Hari và âm mƣu quỷ quyệt dẫn đến trò hề trong việc kết án Dreyfus
và bỏ tù hai ngƣời đầu thế kỷ 20. May mắn thay, những nhà mật mã học
(cryptographer) cũng nhúng tay vào việc phơi bày mƣu đồ dẫn đến các khúc
mắc của Dreyfus; Mata Hari, ngƣợc lại, đã bị bắn chết.
Ngoài các nƣớc ở Trung Đông và châu Âu, mật mã học hầu nhƣ không
đƣợc phát triển. Tại Nhật Bản, mãi cho tới 1510, mật mã học vẫn chƣa đƣợc
sử dụng và các kỹ thuật tiên tiến chỉ đƣợc biết đến sau khi nƣớc này mở cửa

với phƣơng Tây (thập kỷ 1860).
Mật mã từ năm 1800 tới thế chiến thứ II:
Tuy mật mã học có một lịch sử dài và phức tạp, mãi cho đến thế kỷ
19 nó mới đƣợc phát triển một cách có hệ thống, không chỉ còn là những tiếp
cận nhất thời, vô tổ chức. Những ví dụ về phân tích mã bao gồm công trình
của Charles Babbage trong kỷ nguyên củaChiến tranh Krim (Crimean War)
về toán phân tích mật mã đơn ký tự. Công trình của ông, tuy hơi muộn màng,
đã đƣợc Friedrich Kasiski, ngƣời Phổ, khôi phục và công bố. Tại thời điểm
này, để hiểu đƣợc mật mã học, ngƣời ta thƣờng phải dựa vào những kinh
nghiệm từng trải (rules of thumb); xin xem thêm các bài viết về mật mã học
của Auguste Kerckhoffs cuối thế kỷ 19. Trong thập niên 1840, Edgar Allan
Poe đã xây dựng một số phƣơng pháp có hệ thống để giải mật mã. Cụ thể là,
ông đã bày tỏ khả năng của mình trong tờ báo hằng tuần Alexander's Weekly
(Express) Messenger ở Philadelphia, mời mọi ngƣời đệ trình các phƣơng pháp
mã hóa của họ, và ông là ngƣời đứng ra giải. Sự thành công của ông gây chấn
động với công chúng trong vài tháng. Sau này ông có viết một luận văn về các
phƣơng pháp mật mã hóa và chúng trở thành những công cụ rất có lợi, đƣợc
áp dụng vào việc giải mã của Đức trong Thế chiến II.
Trong thời gian trƣớc và tới thời điểm của Thế chiến II, nhiều phƣơng
pháp toán học đã hình thành (đáng chú ý là ứng dụng của William F. Friedman


13
dùng kỹ thuật thống kê để phân tích và kiến tạo mật mã, và thành công bƣớc
đầu của Marian Rejewski trong việc bẻ gãy mật mã của hệ thống Enigma của
Quân đội Đức). Sau Thế chiến II trở đi, cả hai ngành, mật mã học và phân
tích mã, ngày càng sử dụng nhiều các cơ sở toán học. Tuy thế, chỉ đến khi
máy tính và các phƣơng tiện truyền thông Internet trở nên phổ biến, ngƣời ta
mới có thể mang tính hữu dụng của mật mã học vào trong những thói quen sử
dụng hằng ngày của mọi ngƣời, thay vì chỉ đƣợc dùng bởi các chính quyền

quốc gia hay các hoạt động kinh doanh lớn trƣớc đó.
Mật mã trong thế chiến thứ II:
Trong thế chiến II, các hệ thống mật mã cơ khí và cơ điện tử đƣợc sử
dụng rộng rãi mặc dù các hệ thống thủ công vẫn đƣợc dùng tại những nơi
không đủ điều kiện. Các kỹ thuật phân tích mật mã đã có những đột phá trong
thời kỳ này, tất cả đều diễn ra trong bí mật. Cho đến gần đây, các thông tin
này mới dần đƣợc tiết lộ do thời kỳ giữ bí mật 50 năm cjủa chính phủ Anh đã
kết thúc, các bản lƣu của Hoa Kỳ dần đƣợc công bố cùng với sự xuất hiện của
các bài báo và hồi ký có liên quan.
Ngƣời Đức đã sử dụng rộng rãi một hệ thống máy rôto cơ điện tử, dƣới
nhiều hình thức khác nhau, có tên gọi là máy Enigma. Vào tháng 12 năm 1932,
Marian Rejewski, một nhà toán học tại Cục mật mã Ba Lan (tiếng Ba Lan:
Biuro Szyfrów), đã dựng lại hệ thống này dựa trên toán học và một số thông
tin có đƣợc từ các tài liệu do đại úy Gustave Bertrand của tình báo quân
sự Pháp cung cấp. Đây có thể coi là đột phá lớn nhất trong lịch sử phân tích
mật mã trong suốt một nghìn năm trở lại. Rejewski cùng với các đồng sự của
mình là Jerzy Różycki và Henryk Zygalski đã tiếp tục nghiên cứu và bắt nhịp
với những tiến hóa trong các thành phần của hệ thống cũng nhƣ các thủ tục
mật mã hóa. Cùng với những tiến triển của tình hình chính trị, nguồn tài chính
của Ba Lan trở nên cạn kiệt và nguy cơ của cuộc chiến tranh trở nên gần kề,


14
vào ngày 25 tháng 7 năm 1939 tại Warszawa, cục mật mã Ba Lan, dƣới chỉ
đạo của bộ tham mƣu, đã trao cho đại diện tình báo Pháp và Anh những thông
tin bí mật về hệ thống Enigma.
Ngay sau khi Thế chiến II bắt đầu (ngày 1 tháng 9 năm 1939), các thành
viên chủ chốt của cục mật mã Ba Lan đƣợc sơ tán về phía tây nam; và đến
ngày 17 tháng 9, khi quân đội Liên Xô tiến vào Ba Lan, thì họ lại đƣợc chuyển
sang România. Từ đây, họ tới Paris (Pháp). Tại PC Bruno, ở gần Paris, họ tiếp

tục phân tích Enigma và hợp tác với các nhà mật mã học của Anh tại Bletchley
Park lúc này đã tiến bộ kịp thời. Những ngƣời Anh, trong đó bao gồm những
tên tuổi lớn của ngành mật mã học nhƣ Gordon Welchman và Alan Turing,
ngƣời sáng lập khái niệm khoa học điện toán hiện đại, đã góp công lớn trong
việc phát triển các kỹ thuật phá mã hệ thống máy Enigma.
Ngày 19 tháng 4 năm 1945, các tƣớng lĩnh cấp cao của Anh đƣợc chỉ
thị không đƣợc tiết lộ tin tức rằng mã Enigma đã bị phá, bởi vì nhƣ vậy nó sẽ
tạo điều kiện cho kẻ thù bị đánh bại cơ sở để nói rằng họ đã "không bị đánh
bại một cách sòng phẳng" (were not well and fairly beaten)[1].
Các nhà mật mã học của Hải quân Mỹ (với sự hợp tác của các nhà mật
mã học Anh và Hà Lan sau 1940) đã xâm nhập đƣợc vào một số hệ thống mật
mã của Hải quân Nhật. Việc xâm nhập vào hệ thống JN-25 trong số chúng đã
mang lại chiến thắng vẻ vang cho Mỹ trong trận Midway. SIS, một nhóm
trong quân đội Mỹ, đã thành công trong việc xâm nhập hệ thống mật mã
ngoại giao tối mật của Nhật (một máy cơ điện dùng "bộ chuyển mạch dịch
bƣớc" (stepping switch) đƣợc ngƣời Mỹ gọi là Purple) ngay cả trƣớc khi thế
chiến II bắt đầu. Ngƣời Mỹ đặt tên cho những bí mật mà học tìm đƣợc từ việc
thám mã, có thể đặc biệt là từ việc phá mã máy Purple, với cái tên "Magic".
Ngƣời Anh sau này đặt tên cho những bí mật mà họ tìm ra trong việc thám
mã, đặc biệt là từ luồng thông điệp đƣợc mã hóa bởi các máy Enigma, là
"Ultra". Cái tên Anh trƣớc đó của Ultra là Boniface.


15
Quân đội Đức cũng cho triển khai một số thử nghiệm cơ học sử dụng
thuật toán mật mã dùng một lần (one-time pad). Bletchley Park gọi chúng
là mã Fish, và ông Max Newman cùng đồng nghiệp của mình đã thiết kế ra
một máy tính điện tử số khả lập trình (programmable digital electronic
computer) đầu tiên là máy Colossus để giúp việc thám mã của họ. Bộ ngoại
giao Đức bắt đầu sử dụng thuật toán mật mã dùng một lần vào năm 1919; một

số luồng giao thông của nó đã bị ngƣời ta đọc đƣợc trong Thế chiến II, một
phần do kết quả của việc khám phá ra một số tài liệu chủ chốt tại Nam Mỹ, do
sự bất cẩn của những ngƣời đƣa thƣ của Đức không hủy thông điệp một cách
cẩn thận.
Bộ ngoại giao của Nhật cũng cục bộ xây dựng một hệ thống dựa trên
nguyên lý của "bộ điện cơ chuyển mạch dịch bƣớc" (đƣợc Mỹ gọi là Purple),
và đồng thời cũng sử dụng một số máy tƣơng tự để trang bị cho một số tòa đại
sứ Nhật Bản. Một trong số chúng đƣợc ngƣời Mỹ gọi là "Máy-M" (Mmachine), và một cái nữa đƣợc gọi là "Red". Tất cả những máy này đều ít
nhiều đã bị phía Đồng Minh phá mã.
Các máy mật mã mà phe Đồng Minh sử dụng trong thế chiến II, bao
gồm cả máy TypeX của Anh và máy SIGABA của Mỹ, đều là những thiết kế
cơ điện dùng rôto trên tinh thần tƣơng tự nhƣ máy Enigma, song với nhiều
nâng cấp lớn. Không có hệ thống nào bị phá mã trong quá trình của cuộc
chiến tranh. Ngƣời Ba Lan sử dụng máy Lacida, song do tính thiếu an ninh,
máy không tiếp tục đƣợc dùng. Các phân đội trên mặt trận chỉ sử dụng
máy M-209 và các máy thuộc họ M-94 ít bảo an hơn. Đầu tiên, các nhân viên
mật vụ trong Cơ quan đặc vụ của Anh (Special Operations Executive - SOE)
sử dụng "mật mã thơ" (các bài thơ mà họ ghi nhớ là những chìa khóa), song ở
những thời kỳ sau trong cuộc chiến, họ bắt đầu chuyển sang dùng các hình
thức của mật mã dùng một lần (one-time pad).


16
Mật mã hiện đại:
Nhiều ngƣời cho rằng kỷ nguyên của mật mã học hiện đại đƣợc bắt đầu
với Claude Shannon, ngƣời đƣợc coi là cha đẻ của mật mã toán học. Năm
1949 ông đã công bố bài Lý thuyết về truyền thông trong các hệ thống bảo
mật (Communication Theory of Secrecy Systems) trên tập san Bell System
Technical Journal - Tập san kỹ thuật của hệ thống Bell - và một thời gian
ngắn sau đó, trong cuốn Mathematical Theory of Communication - Lý thuyết

toán học trong truyền thông - cùng với tác giả Warren Weaver. Những công
trình này, cùng với những công trình nghiên cứu khác của ông về lý thuyết về
tin học và truyền thông (information and communication theory), đã thiết lập
một nền tảng lý thuyết cơ bản cho mật mã học và thám mã học. Với ảnh
hƣởng đó, mật mã học hầu nhƣ bị thâu tóm bởi các cơ quan truyền thông mật
của chính phủ, chẳng hạn nhƣ NSA, và biến mất khỏi tầm hiểu biết của công
chúng. Rất ít các công trình đƣợc tiếp tục công bố, cho đến thời kỳ giữa thập
niên 1970, khi mọi sự đƣợc thay đổi.
Thời kỳ giữa thập niên kỷ 1970 đƣợc chứng kiến hai tiến bộ công chính
lớn (công khai). Đầu tiên là sự công bố đề xuất Tiêu chuẩn mật mã hóa dữ
liệu

(Data Encryption Standard) trong "Công báo Liên bang" (Federal

Register) ở nƣớc Mỹ vào ngày 17 tháng 3 năm 1975. Với đề cử của Cục Tiêu
chuẩn Quốc gia (National Bureau of Standards - NBS) (hiện là NIST), bản đề
xuất DES đƣợc công ty IBM (International Business Machines) đệ trình trở
thành một trong những cố gắng trong việc xây dựng các công cụ tiện ích cho
thƣơng mại, nhƣ cho các nhà băng và cho các tổ chức tài chính lớn. Sau
những chỉ đạo và thay đổi của NSA, vào năm 1977, nó đã đƣợc chấp thuận và
đƣợc phát hành dƣới cái tên Bản Công bố về Tiêu chuẩn Xử lý Thông tin của
Liên bang (Federal Information Processing Standard Publication - FIPS)
(phiên bản hiện nay là FIPS 46-3). DES là phƣơng thức mật mã công khai đầu


17
tiên đƣợc một cơ quan quốc gia nhƣ NSA "tôn sùng". Sự phát hành bản đặc tả
của nó bởi NBS đã khuyến khích sự quan tâm chú ý của công chúng cũng nhƣ
của các tổ chức nghiên cứu về mật mã học.
Năm 2001, DES đã chính thức đƣợc thay thế bởi AES (viết tắt của

Advanced Encryption Standard - Tiêu chuẩn mã hóa tiên tiến) khi NIST công
bố phiên bản FIPS 197. Sau một cuộc thi tổ chức công khai, NIST đã chọn
Rijndael, do hai nhà mật mã ngƣời Bỉ đệ trình, và nó trở thành AES.
1.2. Hệ thống mã hóa
Định nghĩa 1.1: Hệ thống mã hóa (cryptosystem) là một bộ năm (P, C,
K, E, D) thỏa mãn các điều kiện sau:
1. Tập nguồn P là tập hữu hạn tất cả các mẩu tin nguồn cần mã hóa có
thể có.
2. Tập đích C là tập hữu hạn tất cả các mẩu tin có thể có sau khi mã
hóa.
3. Tập khóa K là tập hữu hạn các khóa có thể đƣợc sử dụng.
4. E và D lần lƣợt là tập mã hóa và giải mã với mỗi khóa k € K, tồn tại
luật mã hóa ek € E và luật giải mã dk € D tƣơng ứng. Luật mã hóa ek : P → C
và luật giải mã dk : C→ P là hai ánh xạ thỏa mãn dk(ek(x))= x x € P.
Tính chất 4 là tính chất quan trọng của một hệ thống mã hóa. Tính chất
này đảm bảo một mẩu tin x € P đƣợc mã hóa bằng luật mã hóa ek € E có thể
đƣợc giải mã chính xác bằng thuật giải mã dk € D.


18

Hệ mật mã

Mã không
dùng khóa

Hàm hash

Mã dòng


Mã dùng một
khóa

Mã đối xứng

Mã dùng hai
khóa

Mã bất đối
xứng

Chữ ký điện
tử

Mã khối

Hình 1.1: Sơ đồ hệ mật mã
Hàm hash – là hàm mật mã (thuật toán), mà đối số của nó là một bản
tin có độ dài bất kỳ biểu diễn dƣới dạng dãy bit, giá trị của hàm hash có kích
thƣớc không đổi. Vì có đặc tính nhƣ thế, nên hash là một lớp mã hõa đặc biệt
kiểm tra tính toàn vẹn của thông tin. Thƣờng thì hàm hash không có sự tham
gia của khóa mật và nó phải đảm bảo đƣợc độ phức tạp phụ thuộc của giá trị
đầu ra của hàm vào từng bit của bản tin.
Mật mã đối xứng là thuật toán mật mã mà quá trình mã hóa và giải mã
chỉ dùng một khóa. Thực tế thì hai khóa(mã hóa, giải mã) có thể khác nhau,
trong trƣờng hợp này thì một khóa nhận đƣợc từ khóa kia bằng phép tính toán
đơn giản.
Mật mã đối xứng thì đƣợc chia ra thành hai loại: mã dòng và mã khối.
Mã khối là mã, thực hiện biến đổi khối dữ liệu với một kích thƣớc
không đổi.

Mã dòng là mã, thực hiện biến đổi tuần tự từng bit hoặc ký tự riêng rẻ.


19
Mật mã bất đối xứng là phƣơng pháp mật mã dùng hai khóa: Khóa
công khai dùng cho quá trình mã, khóa mật dùng cho quá trình giải mã. Khóa
công khai và khóa mật có quan hệ với nhau bằng biểu thức phức tạp, khóa
công khai tính dễ dàng từ khóa mật, còn tính khóa mật từ khóa công khai là
bài toán khó và hầu nhƣ không giải đƣợc.
Chữ ký điện tử là phƣơng pháp ký một bức điện dƣới dạng điện tử, để
đảm bảo tính nguyên vẹn và xác thực quyền tác giả. Nhƣ trong mật mã bất đối
xứng, chữ ký điện tử cũng dùng thuật toán mật mã với hai khóa, khóa công
khai tính dễ dàng từ khóa mật, còn khóa mật thì rất khó và hầu nhƣ là không
thể tính đƣợc từ khóa công khai. Nhƣng khác với mật mã bất đối xứng là quá
trình ký bức điện dùng khóa mật, còn quá trình kiểm tra bứu điện dùng khóa
công khai. Và khóa mật ngoài chủ của bức điện thì không ai biết đƣợc, nhờ
tính chất này mà chống từ chối bức điện.
Định nghĩa 1.2: Zm đƣợc định nghĩa là tập hợp {0,1,...,m−1} , đƣợc
trang bị phép cộng (ký hiệu +) và phép nhân (ký hiệu là ×). Phép cộng và
phép nhân trong Zm đƣợc thực hiện tƣơng tự nhƣ trong Z, ngoại trừ kết quả
tính theo modulo m.
Ví dụ: Ta cần tính giá trị 11×13 trong Z16. Trong Z, ta có kết quả phép
nhân 11×13 = 143. Do 143 ≡ 15 (mod 16) nên 11×13 = 15 trong Z16.
Một số tính chất của Zm:
1. Phép cộng đóng trong Zm ,  a, b Zm , a + b Zm
2. Tính giao hoán của phép cộng trong Zm ,  a, b  Zm , a + b = b + a
3. Tính kết hợp của phép cộng trong Zm,
a, b, c  Zm , (a + b)+ c = a + (b + c)
4. Zm có phần tử trung hòa là 0, a, b  Zm , a + 0 = 0 + a = a
5. Mọi phần tử a trong Zm đều có phần tử đối là m a

6. Phép nhân đóng trong Zm ,  a, b Zm, a * b  Zm


20
7. Tính giao hoán của phép nhân trong Zm , a, b  Zm , a * b = b * a
8. Tính kết hợp của phép nhân trong Zm,
 a, b, c  Zm , (a * b) * c = a *(b * c)
9. Zm có phần tử đơn vị là 1, a, b  Zm , a * 1 = 1 * a = a
10. Tính chất phân phối của phép nhân với phép cộng  a, b, c  Zm,
(a + b)* c = a * c + b * c.
1.3. Thám mã và tính an toàn các hệ mã
1.3.1. Lý thuyết mã hóa
Là một ngành của toán học và khoa học điện toán(computer science)
nhằm giải quyết tình trạng lỗi dễ xảy ra trong quá trình truyền thông số liệu
trên các kênh truyền có độ nhiễu cao (noisy channels), dùng những phƣơng
pháp tinh xảo khiến phần lớn các lỗi xảy ra có thể đƣợc chỉnh sửa. Nó còn xử
lý những đặc tính của mã, và do vậy giúp phù hợp với những ứng dụng cụ thể.
Có hai loại mã hiệu:
Mã hóa dùng nguồn (Mã hóa entrôpi (Entropy encoding));
Mã hóa trên kênh truyền (Sửa lỗi ở phía trƣớc (Forward error
correction)).
Đầu tiên chúng ta nói đến là mã hóa dùng nguồn. Ý định của phƣơng
pháp này là nén dữ liệu từ chính nguồn của nó, trƣớc khi truyền đi, giúp cho
việc truyền thông có hiệu quả hơn. Chúng ta chứng kiến thói quen này hằng
ngày trên Internet, nhất là trong cách dùng "zip" nén dữ liệu để giảm lƣợng dữ
liệu phải truyền, giảm nhẹ gánh nặng cho mạng lƣới truyền thông, đồng thời
thu nhỏ cỡ tập tin. Cái thứ hai là mã hóa trên kênh truyền. Bằng việc cộng
thêm những bit mới vào trong dữ liệu đƣợc truyền, còn gọi là bit chẵn lẻ
(parity bits), kỹ thuật này giúp cho việc truyền thông tín hiệu chính xác hơn
trong môi trƣờng nhiễu loạn của kênh truyền thông. Có nhiều chƣơng trình

ứng dụng, mà ngƣời dùng trung bình không để ý đến, sử dụng mã hóa trên


21
kênh truyền. Kỹ thuật Reed-Solomon đƣợc dùng để nhằm sửa lỗi do những
vết xƣớc và bụi trên bề mặt đĩa âm nhạc CD thông thƣờng. Trong ứng dụng
này, kênh truyền thông lại chính là bản thân cái đĩa CD. Điện thoại di động
"Cell phones" cũng dùng kỹ thuật mã hóa có hiệu ứng cao (powerful coding
technique) để sửa các lỗi trong việc truyền sóng rađiô ở tần số cao bị yếu mờ
và bị nhiễu. Modem xử lý số liệu, việc truyền thông qua đƣờng điện thoại, và
đƣơng nhiên ngay cả chính NASA, tất cả đều sử dụng kỹ thuật mã hóa trên
kênh truyền hiệu ứng để truyền những bit số liệu qua đƣờng dây.
1.3.2. Nguyên lý
Entrôpi của nguồn là một đo đạc về tin tức. Căn bản mà nói, mã của
nguồn đƣợc dùng để loại bỏ những phần thừa, không cần thiết còn tồn trong
nguồn, để lại phần nguồn với số lƣợng bit ít hơn, nhƣng với nhiều tin tức hơn.
Mỗi loại mã hóa nguồn sử dụng một kỹ thuật khác nhau hòng đạt đƣợc
giới hạn entrôpi của nguồn. C ( x)  H ( x) , trong đó H(x) là entrôpi của nguồn
(tần số bit), và C(x) là tần số bit sau khi số liệu đã đƣợc nén. Cụ thể là, không
có phƣơng pháp mã hóa nguồn nào có thể tốt hơn giới hạn entrôpi của ký
hiệu (the entroy limit of the symbol).
1.3.3. Những điều căn bản về mã hoá
Khi bắt đầu tìm hiểu về mã hoá, chúng ta thƣờng đặt ra những câu hỏi
chẳng hạn nhƣ là: Tại sao cần phải sử dụng mã hoá ? Tại sao lại có quá nhiều
thuật toán mã hoá ? …
Tại sao cần phải sử dụng mã hoá ?
Thuật toán Cryptography đề cập tới nghành khoa học nghiên cứu về mã
hoá và giải mã thông tin. Cụ thể hơn là nghiên cứu các cách thức chuyển đổi
thông tin từ dạng rõ (clear text) sang dạng mờ (cipher text) và ngƣợc lại. Đây
là một phƣơng pháp hỗ trợ rất tốt cho trong việc chống lại những truy cập bất

hợp pháp tới dữ liệu đƣợc truyền đi trên mạng, áp dụng mã hoá sẽ khiến cho


22
nội dung thông tin đƣợc truyền đi dƣới dạng mờ và không thể đọc đƣợc đối
với bất kỳ ai cố tình muốn lấy thông tin đó.
Nhu cầu sử dụng kỹ thuật mã hoá?
Không phai ai hay bất kỳ ứng dụng nào cũng phải sử dụng mã hoá. Nhu
cầu về sử dụng mã hoá xuất hiện khi các bên tham gia trao đổi thông tin muốn
bảo vệ các tài liệu quan trọng hay gửi chúng đi một cách an toàn. Các tài liệu
quan trọng có thể là: tài liệu quân sự, tài chính, kinh doanh hoặc đơn giản là
một thông tin nào đó mang tính riêng tƣ.
Nhƣ chúng ta đã biết, Internet hình thành và phát triển từ yêu cầu của
chính phủ Mỹ nhằm phục vụ cho mục đích quân sự. Khi chúng ta tham gia
trao đổi thông tin, thì Internet là môi trƣờng không an toà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. Do đó, mã hoá đƣợc áp dụng nhƣ một biện pháp
nhằm giúp chúng ta tự bảo vệ chính mình cũng nhƣ những thông tin mà
chúng ta gửi đi. Bên cạnh đó, mã hoá còn có những ứng dụng khác nhƣ là bảo
đảm tính toàn vẹn của dữ liệu.
Tại sao lại có quá nhiều thuật toán mã hoá?
Theo một số tài liệu thì trƣớc đây tính an toàn, bí mật của một thuật
toán phụ thuộc vào phƣơng thức làm việc của thuật toán đó. Nếu nhƣ tính an
toàn của một thuật toán chỉ dựa vào sự bí mật của thuật toán đó thì thuật toán
đó là một thuật toán hạn chế (Restricted Algrorithm). Restricted Algrorithm
có tầm quan trọng trong lịch sử nhƣng không còn phù hợp trong thời đại ngày
nay. Giờ đây, nó không còn đƣợc mọi ngƣời sử dụng do mặt hạn chế của nó:
mỗi khi một user rời khỏi một nhóm thì toàn bộ nhóm đó phải chuyển sang sử
dụng thuật toán khác hoặc nếu ngƣời đó ngƣời trong nhóm đó tiết lộ thông tin
về thuật toán hay có kẻ phát hiện ra tính bí mật của thuật toán thì coi nhƣ

thuật toán đó đã bị phá vỡ, tất cả những user còn lại trong nhóm buộc phải
thay đổi lại thuật toán dẫn đến mất thời gian và công sức.


23
Hệ thống mã hoá hiện nay đã giải quyết vấn đề trên thông qua khoá
(Key) là một yếu tố có liên quan nhƣng tách rời ra khỏi thuật toán mã hoá. Do
các thuật toán hầu nhƣ đƣợc công khai cho nên tính an toàn của mã hoá giờ
đây phụ thuộc vào khoá. Khoá này có thể là bất kì một giá trị chữ hoặc số
nào. Phạm vi không gian các giá trị có thể có của khoá đƣợc gọi là Keyspace.
Hai quá trình mã hoá và giải mã đều dùng đến khoá. Hiện nay, ngƣời ta phân
loại thuật toán dựa trên số lƣợng và đặc tính của khoá đƣợc sử dụng.
Nói đến mã hoá tức là nói đến việc che dấu thông tin bằng cách sử
dụng thuật toán. Che dấu ở đây không phải là làm cho thông tin biến mất mà
là cách thức chuyển từ dạng tỏ sang dạng mờ. Một thuật toán là một tập hợp
của các câu lệnh mà theo đó chƣơng trình sẽ biết phải làm thế nào để xáo trộn
hay phục hồi lại dữ liệu. Chẳng hạn một thuật toán rất đơn giản mã hoá thông
điệp cần gửi đi nhƣ sau:
Bƣớc 1: Thay thế toàn bộ chữ cái “e” thành số “3”;
Bƣớc 2: Thay thế toàn bộ chữ cái “a” thành số “4”;
Bƣớc 3: Đảo ngƣợc thông điệp.
Trên đây là một ví dụ rất đơn giản mô phỏng cách làm việc của một
thuật toán mã hoá. Sau đây là các thuật ngữ cơ bản nhất giúp chúng ta nắm
đƣợc các khái niệm:
- Sender/Receiver: Ngƣời gửi/Ngƣời nhận dữ liệu.
- Plaintext (Cleartext): Thông tin trƣớc khi đƣợc mã hoá. Đây là dữ liệu
ban đầu ở dạng rõ.
- Ciphertext: Thông tin, dữ liệu đã đƣợc mã hoá ở dạng mờ.
- Key: Thành phần quan trọng trong việc mã hoá và giải mã.
- CryptoGraphic Algorithm: Là các thuật toán đƣợc sử dụng trong việc

mã hoá hoặc giải mã thông tin.