===£offlca===
Bộ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC sư PHẠM HÀ

TRẦN HOÀNG

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,


===£offlca===

TRẦN HOÀNG

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

Nguôi huóng dẫn khoa học: TS. Trịnh Đình Vinh

HÀ NÔI.



* viên

Trần Hoàng Minh


MỤC LỤC


DANH MỤC
• HÌNH

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ã

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 tuợng và phạm vỉ 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.


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

multimedia trên 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.
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



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 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 đó.


đạ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
phang" (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.
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

(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
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.


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,l,...,m-l} , được trang bị
phép cộng (ký hiệu +) và phép nhân (ký hiệu là x). 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ị 11x13 trong Z16. Trong z, ta có kết quả phép nhân
11x13 = 143. Do 143 — 15 (mod 16) nên 11x13 = 15 trong Z16.
Một số tính chất của zm:

1. Phép cộng đóng trong zm , V a, b e Zm , e a + b Zm
2. Tính giao hoán của phép cộng trong 4, Va, b e zm,a + b = b + a
3. Tính kết họp của phép cộng trong Zm,
Va, b, c e zm , (a + b)+ c = a + (b + c)

4. zm có phần tử trung hòa là 0, Va, be Z m , 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 , V a, b e Zm, a * b e Zm
7. Tính giao hoán của phép nhân trong zm , Va, be Z m , a * b = b * a
8. Tính kết hợp của phép nhân trong zm,
V a, b, c e zm, (a * b) * c = a *(b * c)

9. zm có phần tử đơn vị là 1, Va, be z m , a * l = l*a = a
10. Tính chất phân phối của phép nhân vói phép cộng V a, b, c e z m ,

radio ở 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 nội dung thông tin được truyền đi

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ờ.


dữ liệu gốc ban đầu. Chỉ những người được phép mới có khả năng đọc được nội dung
thông tin ban đầu.
Authentication (Tính xác thực): Giúp cho người nhận dữ liệu xác định được
chắc chắn dữ liệu mà họ nhận là dữ liệu gốc ban đầu. Kẻ giả mạo không thể có khả
năng để giả dạng một người khác hay nói cách khác không thể mạo danh để gửi dữ
liệu. Ngưòi nhận có khả năng kiểm tra nguồn gốc thông tin mà họ nhận được
Integrity (Tính toàn vẹn): Giúp cho ngưòi nhận dữ liệu kiểm tra được rằng
dữ liệu không bị thay đổi trong quá trình truyền đi. Kẻ giả mạo không thể có khả năng
thay thế dữ liệu ban đầu băng dữ liệu giả mạo
Non-repudation (Tính không thể chối bỏ): Ngưòi gửi hay người nhận không
thể chối bỏ sau khi đã gửi hoặc nhận thông tin.

1.3.4.

Độ an toàn của thuật toán
Nguyên 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 toá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 toàn của một thuật toán phụ thuộc:

-

Nếu chi phí hay phí tổn cần thiết để phá vỡ một thuật toán lớn hon giá trị của thông tin
đã mã hóa thuật toán thì thuật toán đó tạm thời được coi là an toàn.

-

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 toán đó tạm
thời được coi là an toàn.


-

Mã hoá cổ điển (Classical cryptography)

-

Mã hoá đối xứng (Syraetric cryptography)

-

Mã hoá bất đối xứng(Asyraetric cryptography)

-

Hàm băm (Hash function)
Phân loại theo số lượng khoá:

-

Mã hoá khoá bí mật (Private-key Cryptography)

-

Mã hoá khoá công khai (Public-key Cryptography)

1.3.6.

Mã hóa trên kênh truyền
Mục đích của lý thuyết Mã hóa trên kênh truyền (channel encoding theory) là