Một vài ứng dụng của số học trong mã hóa và giải mã 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 (682.04 KB, 48 trang )

1

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC VINH

NGUYỄN VĂN THÀ

MỘT VÀI ỨNG DỤNG CỦA SỐ HỌC
TRONG MÃ HÓA VÀ GIẢI MÃ THÔNG TIN

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGHỆ AN – 2013

2

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC VINH

NGUYỄN VĂN THÀ

MỘT VÀI ỨNG DỤNG CỦA SỐ HỌC
TRONG MÃ HÓA VÀ GIẢI MÃ THÔNG TIN

CHUYÊN NGÀNH: ĐẠI SỐ VÀ LÝ THUYẾT SỐ
Mã số: 60 46 05

LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học
PGS.TS. NGUYỄN THÀNH QUANG

NGHỆ AN – 2013

3

MỤC LỤC

MỞ ĐẦU
CHƯƠNG 1

TRANG
1
4

MỘT SỐ KIẾN THỨC CƠ SỞ
1.1
1.2

1.3

Tổng quan về mật mã
Mã hoá
Những khái niệm và kết quả Số học có nhiều ứng dụng trong mã

4
9
16

hoá và giải mã thông tin
CHƯƠNG 2

ỨNG DỤNG CỦA SỐ HỌC

25

TRONG MỘT SỐ HỆ THỐNG MẬT MÃ
2.1
2.2
2.3

Mật mã Caesar
Thuật toán mã hoá RSA
Mật mã Vigenère

KẾT LUẬN
TÀI LIỆU THAM KHẢO

25
28
41
43
44

MỞ ĐẦU
Từ lâu loài người đã biết các thao tác về Số học và sử dụng nó trong các
giao dịch thường nhật liên tục trong nhiều thế kỷ. Nhưng đến thời phát triển của

Toán học, Số học phải nhường chỗ cho những phép tính phức tạp như đạo hàm,
vi phân, tích phân và những bài toán khác. Cho đến những năm 70 của thế kỷ
XX, Số học vẫn được xem là một trong những ngành lý thuyết thuần túy nhất
của toán học. Thậm chí, có nhà toán học cho rằng vẻ đẹp của Số học có được là

4

nhờ sự xa rời thực tiễn của nó [6]. Nhưng cũng chính nhờ máy tính, một tinh
hoa của văn minh nhân loại vào thế kỷ XX, đã làm tái sinh môn học cổ xưa này.
Máy tính không những phát huy mọi vẻ đẹp truyền thống của Số học mà còn
triển khai ra những ứng dụng đang và sẽ có cho chúng ta trong thế kỷ XXI.

Hiện nay, công nghệ thông tin, công nghệ Internet, công nghệ E-mail,
E- business phát triển như vũ bão.Việt Nam đã, đang từng bước áp dụng công
nghệ mới để “tin học hóa xã hội” tức là đưa tin học vào các lĩnh vực của xã hội
để cải thiện hoạt động thủ công trước đây. Tin học hóa đã giải phóng sức lao
động của con người bằng cách sáng chế. Như vậy chúng ta có thể trao đổi mọi
thông tin qua mạng. Thông tin gửi đi có thể là thông tin 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ư… Điều này dẫn
tới một vấn đề xảy ra là 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 truyền đi không bị lộ trên đường
truyền. Vì vậy, vấn đề an toàn cơ sở dữ liệu, thông tin cá nhân là vấn đề sống
còn của bất kỳ tổ chức nào và bảo mật thông tin là nền móng cơ bản để phát
triển. Do đó, một biện pháp được đưa ra nhằm giúp chúng ta tự bảo vệ chính

mình cũng như những thông tin gửi đi là cần phải mã hóa thông tin. Ngành khoa
học mật mã không chỉ nghiên cứu sự bảo mật của các sơ đồ mã hóa, mà còn mở
rộng đến những ứng dụng thực tiễn như chữ ký điện tử, sơ đồ định danh rồi đưa
đến những khái niệm quan trọng của ngành khoa học máy tính và rộng hơn là
của Toán học như khái niệm về các chứng minh tương tác (interactives proofs),
chứng minh không để lộ tri thức (zero-knowledge proofs) và gần đây là các
chứng minh kiểm tra được một cách xác suất bằng cách chỉ kiểm thử một hằng
số các bít thông tin trên bản chứng minh (probabilistic checkable proofs).
Những công cụ ngày càng mạnh, Số học đã dần thâm nhập vào mật mã và
góp phần đưa mật mã trở thành một ngành khoa học. Năm 1978, ba nhà khoa
học của MIT (Massachusetts Institute of Technology) là Rivest, Shamir và

5

Adleman đề xuất một hệ mã, mà nay được gọi là RSA. Tính bảo mật và độ an
toàn của hệ mã này được dựa trên độ phức tạp của bài toán số học phân tích một
số nguyên đủ lớn ra thừa số nguyên tố. Liên tiếp sau đó, các bài toán của lý
thuyết số như bài toán lôgarit rời rạc và tìm thặng dư cấp 2 cũng đã được sử
dụng để xây dựng các hệ mã Elgamal và Rabin. Ngoài ra, Định lý Euler, Định lý
Fermat bé, Định lý số dư Trung Quốc và Định lý Carmichael có rất nhiều ứng
dụng trong các bài toán về số nguyên lớn áp dụng vào Lý thuyết mật mã. Nhờ
đó, các lý thuyết mới của Số học, đặc biệt là Số học thuật toán, tìm thấy những
ứng dụng trực tiếp vào thực tiễn. Ngược lại, với sự sử dụng rộng rãi hệ mã RSA,

Elgamal trong thực tế, việc nghiên cứu các lời giải hiệu quả cho các bài toán
phân tích thành thừa số nguyên tố và lôgarit rời rạc trên các trường hữu hạn trở
nên rất được quan tâm trong Lý thuyết số.
Như vậy, Số học đã hiện hữu trong các hoạt động thực tiễn: Kỹ thuật máy
tính, mật mã, trao đổi trực tuyến giữa các ngân hàng, thẻ ATM, truyền phát tín
hiệu vệ tinh, chứng khoán…
Mục đích của bản luận văn này là tìm hiểu những ứng dụng của Số học
vào một số lĩnh vực mã hóa và giải mã thông tin, nhằm khẳng định tính đúng
đắn của các thuật toán mật mã và đảm bảo toán học của chúng.

6

Ngoài phần mở đầu, kết luận và tài liệu tham khảo, luận văn này gồm có 2
chương. Chương 1 trình bày các kiến thức cơ sở tổng quan về Mật mã học và Số
học (Phân tích nguyên tố, Phép tính đồng dư, Định lý số dư Trung Quốc, Định lý
Euler, Định lý Fermat bé, Số giả nguyên tố, Định lý Carmichael, Hàm số Euler,
Hàm số Carmichael, Phân tích Fermat). Chương 2 trình bày một số hệ mật mã (mã
Cesaz, mã RSA) có liên quan trực tiếp đến ứng dụng công cụ phép tính đồng dư và
các kết quả số học khác trong mã hoá và giải mã thông tin.
Luận văn này được hoàn thành dưới sự hướng dẫn tận tình và chu đáo của
PGS.TS. Nguyễn Thành Quang. Tác giả xin bày tỏ lòng kính trọng và biết ơn sâu
sắc tới thầy giáo hướng dẫn khoa học, người đã dành nhiều thời gian và công sức
giúp đỡ cho tôi để hoàn thành luận văn này.

Tác giả xin bày tỏ lòng biết ơn và gửi lời cảm ơn đến các thầy cô giáo thuộc
chuyên ngành Đại số và Lý thuyết số, Khoa Toán, Phòng Đào tạo Sau Đại học –
Trường Đại học Vinh, những người đã tận tình giảng dạy và tạo mọi điều kiện
thuận lợi thành công của khóa học.
Xin trân trọng cảm ơn Trường Đại học Sài Gòn đã tạo mọi điều kiện tổ chức
thuận lợi cho chúng tôi hoàn thành nhiệm vụ học tập.
Xin chân thành cảm ơn bạn bè, đồng nghiệp, gia đình đã động viên và giúp
đỡ tôi trong học tập và nghiên cứu.
Xin gửi lời cảm ơn đến Ban giám hiệu Trường Trung học Phổ thông Phùng
Hưng – Sở Giáo dục và Đào tạo TP. Hồ Chí Minh, các thầy cô giáo đồng nghiệp đã
động viên và tạo điều kiện thuận lợi để tôi hoàn thành nhiệm vụ học tập.
Mặc dù đã có nhiều cố gắng, song luận văn vẫn còn nhiều thiếu sót, tác giả

mong nhận được sự đóng góp của thầy cô giáo và các đồng nghiệp.
TÁC GIẢ

7

CHƯƠNG 1
MỘT SỐ KIẾN THỨC CƠ SỞ
1.1. TỔNG QUAN VỀ MẬT MÃ HỌC
1.1.1. Mật mã học. Mật mã học (cryptography) là một lĩnh vực liên quan với
các kỹ thuật ngôn ngữ và toán học để đảm bảo an toàn thông tin, cụ thể là
trong thông tin liên lạc. Về phương diện lịch sử, mật mã học gắn liền với quá

trình mã hóa; điều này có nghĩa là nó gắn với các cách thức để chuyển đổi thông
tin từ dạng này sang dạng khác nhưng ở đây là từ dạng thông thường có thể
nhận thức được thành dạng không thể nhận thức được, làm cho thông tin trở
thành dạng không thể đọc được nếu như không có các kiến thức bí mật. Quá
trình mã hóa được sử dụng chủ yếu để đảm bảo tính bí mật của các thông tin
quan trọng, chẳng hạn trong công tác tình báo, quân sự hay ngoại giao cũng như
các bí mật về kinh tế, thương mại. Trong những năm gần đây, lĩnh vực hoạt
động của mật mã hóa đã được mở rộng: mật mã hóa hiện đại cung cấp cơ chế
cho nhiều hoạt động hơn là chỉ duy nhất việc giữ bí mật và có một loạt các ứng
dụng như: chứng thực khóa công khai, chữ ký số, bầu cử điện tử hay thanh toán
điện tử. Ngoài ra, những người không có nhu cầu thiết yếu đặc biệt về tính bí
mật cũng sử dụng các công nghệ mật mã hóa, thông thường được thiết kế và tạo

lập sẵn trong các cơ sở hạ tầng của công nghệ tính toán và liên lạc viễn thông.
Mật mã học là một lĩnh vực liên ngành, được tạo ra từ một số lĩnh vực khác.
Các dạng cổ nhất của mật mã hóa chủ yếu liên quan với các kiểu mẫu
trong ngôn ngữ. Gần đây thì tầm quan trọng đã thay đổi và mật mã hóa sử dụng
và gắn liền nhiều hơn với toán học, cụ thể là toán học rời rạc, bao gồm các vấn
đề liên quan đến lý thuyết số, lý thuyết thông tin, độ phức tạp tính toán, thống
kê và tổ hợp. Mật mã hóa là công cụ được sử dụng trong an ninh máy tính
và mạng.

8

Việc nghiên cứu tìm các phương thức để phá vỡ việc sử dụng mật mã được
gọi là phân tích mật mã, hay phá mã. Mật mã hóa và phân tích mật mã đôi khi
được nhóm lại cùng nhau dưới tên gọi chung mật mã học, nó bao gồm toàn bộ
các chủ đề liên quan đến mật mã. Trong thực tế, thuật ngữ mật mã hóa thông
thường được sử dụng để nói đến ngành này một cách tổng thể.
Mật mã hóa là quá trình chuyển đổi các thông tin thông thường (văn bản
thường hay văn bản rõ hay văn bản trơn) thành dạng không đọc trực tiếp được,
là văn bản mã hóa. Giải mật mã hay giải mã là quá trình ngược lại, phục hồi lại
văn bản thường từ văn bản mã. Mật mã là thuật toán để mật mã hóa và giải mật
mã. Hoạt động chính xác của mật mã thông thường được kiểm soát bởi
các khóa — một đoạn thông tin bí mật nào đó cho phép tùy biến cách thức tạo ra
văn bản mã. Các giao thức mật mã chỉ rõ các chi tiết về việc mật mã (và các nền

tảng mật mã hóa khác) được sử dụng như thế nào để thu được các nhiệm vụ cụ
thể. Một bộ các giao thức, thuật toán, cách thức quản lý khóa và các hành động
quy định trước bởi người sử dụng cùng phối hợp chặt chẽ tạo thành hệ thống
mật mã.
Trong cách nói thông thường, “mã” bí mật thông thường được sử dụng đồng
nghĩa với “mật mã”. Trong mật mã học, thuật ngữ này có ý nghĩa kỹ thuật đặc
biệt: Các mã là các phương pháp tham gia vào việc thay thế các đơn vị văn bản
lớn hơn, thông thường là các từ hay câu văn (ví dụ, ” qua tao” thay thế cho “tan
cong luc rang dong”).

Ngược lại, mật mã hóa cổ điển thông thường thay thế

hoặc sắp xếp lại các chữ cái riêng biệt (hoặc một nhóm nhỏ các chữ cái). Ví dụ,
“tan cong luc rang dong” trở thành “ubo dpoh mvd sboh epoh” bằng cách thay thế.

9

Hình 1: Sơ đồ khái quát về một hệ thống mật mã.

1.1.2. Lịch sử phát triển của mật mã
Mật mã học là một ngành có lịch sử từ hàng nghìn năm nay. Trong phần
lớn thời gian phát triển của mình (ngoại trừ vài thập kỷ trở lại đây), lịch sử mật
mã học chính là lịch sử của những phương pháp mật mã học cổ điển – các

phương pháp mật mã hóa với bút và giấy, đôi khi có hỗ trợ từ những dụng cụ cơ
khí đơn giản. Vào đầu thế kỷ XX, sự xuất hiện của các cơ cấu cơ khí và điện cơ,
chẳng hạn như máy Enigma, đã cung cấp những cơ chế phức tạp và hiệu quả
hơn cho việc mật mã hóa. Sự ra đời và phát triển mạnh mẽ của ngành điện tử và
máy tính trong những thập kỷ gần đây đã tạo điều kiện để mật mã học phát triển
nhảy vọt lên một tầm cao mới. Sự phát triển của mật mã học luôn luôn đi kèm
với sự phát triển của các kỹ thuật phá mã (hay thám mã). Các phát hiện và ứng
dụng của các kỹ thuật phá mã trong một số trường hợp đã có ảnh hưởng đáng kể
đến các sự kiện lịch sử. Hai sự kiện đã khiến cho mật mã học trở nên thích hợp
cho mọi người, đó là: sự xuất hiện của tiêu chuẩn mật mã hóa DES và sự ra đời
của các kỹ thuật mật mã hóa khóa công khai.

10

1.1.3. Mật mã học 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 năm). 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 cổ điển.
Trong mật mã học, mật mã học cổ điển là một dạng của mật mã học đã
được sử dụng trong lịch sử phát triển của loài người nhưng ngày nay đã trở nên

lạc hậu do các phương thức mã hóa này quá đơn giản và những kẻ tấn công có
thể dễ dàng bẻ khóa thông qua nhiều phương thức như tấn công vét cạn (ví dụ
như dùng máy tính thử hết mọi trường hợp) hay dựa trên tấn công thống kê (dựa
trên tần suất xuất hiện của các chữ cái).
Nói chung, mật mã học cổ điển hoạt động trên cơ sở bảng chữ cái (chẳng
hạn các ký tự từ “A” tới “Z” trong tiếng Anh), và chúng được thực hiện bằng tay
hay một số máy móc cơ khí đơn giản. Ngược lại, các mô hình mã hóa hiện đại
sử dụng các máy tính hay các công nghệ số hóa khác, và hoạt động mã hóa dựa
trên việc thay thế các bit hay byte. Các phương thức mã hóa cổ điển thông
thường dễ bị tổn thương (phá mã) bởi các tấn công văn bản mã hóa, đôi khi
thậm chí kẻ tấn công không cần biết các chi tiết cụ thể của hệ thống mã hóa,
bằng cách sử dụng các công cụ như phân tích tần suất. Đôi khi người ta cũng

cho rằng các phương thức mã hóa như cách thức mã hóa của cỗ máy
Enigma thuộc về các phương thức mã hóa cổ điển mặc dù cách thức mã hóa này
đã sử dụng các thiết bị và công nghệ hiện đại nhất vào thời điểm đó (trong thời
kỳ của Thế chiến II).
Các phương thức mã hóa cổ điển chủ yếu dựa trên mật mã hóa hoán
vị và mật mã hóa thay thế. Trong mật mã hóa thay thế, các ký tự (hoặc nhóm ký

11

tự) được thay thế một cách có quy luật trong toàn bộ thông điệp bằng các ký tự
khác (hoặc nhóm ký tự), chẳng hạn câu I am Mr. Enigma from được thay bằng

câu This is morning star, sau đó các ký tự còn lại trong bảng chữ cái được thay
thế theo một quy luật nào đó xác định trước. Trong phương thức mật mã hóa
hoán vị thì các ký tự được giữ không đổi, nhưng trật tự của chúng trong bản tin
lại thay đổi theo một quy luật nào đó. Có các thuật toán phức tạp để thực hiện
việc mật mã hóa bằng cách tổ hợp hai phương thức trên để tạo ra sản phẩm mã
hóa; các phương thức mã hóa khối hiện đại như DES hay AES thực hiện việc
lặp đi lặp lại một số bước thay thế và hoán vị.
1.1.4. Mật mã học 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 sự ra đời của máy tính kỹ thuật số và điện tử học thì các mật mã cực
kỳ phức tạp đã có thể được thực hiện. Đặc trưng của mật mã máy tính là chúng
thực hiện trên các chuỗi nhị phân, không giống như trong các mô hình mật mã
hóa cổ điển và cơ học (chỉ sử dụng bảng chữ cái với khoảng 26 ký tự – phụ
thuộc vào từng ngôn ngữ). Mật mã máy tính cũng có khả năng chịu đựng việc
phân tích mật mã tốt hơn; rất ít các mật mã như thế dễ bị tổn thương chỉ bởi kiểu

tấn công biết bản mã.

12

Các nghiên cứu rộng rãi có tính học thuật về mật mã hóa hiện đại là tương
đối gần đây – nó chỉ được bắt đầu trong cộng đồng mở kể từ những năm thập
niên 1970 với các chi tiết kỹ thuật của DES (viết tắt trong tiếng Anh của Data
Encryption Standard tức Tiêu chuẩn Mật mã hóa Dữ liệu) và sự phát minh ra mã
RSA. Kể từ đó, mật mã hóa đã trở thành công cụ được sử dụng rộng rãi trong

liên lạc và bảo mật máy tính.

1.2. MÃ HOÁ
1.2.1. Khái niệm mã hoá và giải mã
Trong mật mã học, một ngành toán học ứng dụng cho công nghệ thông
tin, mã hóa là phương pháp để biến thông tin (phim ảnh, văn bản, hình ảnh…) từ
định dạng bình thường sang dạng thông tin không thể hiểu được nếu không có
phương tiện giải mã.
Giải mã là phương pháp để đưa từ dạng thông tin đã được mã hóa về dạng
thông tin ban đầu, quá trình ngược của mã hóa.
Mục đích của mã hóa là che dấu thông tin trước khi truyền trên kênh.
1.2.2. Khái niệm hệ thống mã hoá. Một hệ thống mã hóa (hệ mật mã) bao
gồm 5 thành phần (P, C, K, D, E):
1. Các thông tin trước khi mã hóa, kí hiệu là P (Plaintext),

2. Các thông tin sau khi mã hóa, kí hiệu là C (Ciphertext),
3. Các chìa khóa, kí hiệu là K (Key);
4. Các quy tắc mã hóa, ký hiệu là E (Encrytion),
5. Các quy tắc giải mã, kí hiệu là D (Decrytion),
thoả mãn điều kiện sau: Với mỗi k ∈ K có một quy tắc mã ek : P → C và một quy
tắc giải mã tương ứng d k : C → P sao cho d k ( ek ( x) ) = x, ∀x ∈ P.

13

Như vậy, quá trình mã hóa được tiến hành bằng cách áp dụng hàm toán
học từ E lên P, vốn được biểu diễn dưới dạng số, để trở thành thông tin đã mã

hóa C.

Hình 2: Các thành phần của mật mã
Quá trình giải mã được tiến hành ngược lại: Áp dụng hàm D lên thông
tin C để được thông tin đã giải mã P.
Một thông báo thường được tổ chức dưới dạng bản rõ (văn bản trơn).
Người gửi bản thông báo sẽ làm nhiệm vụ mã hoá bản rõ, kết quả thu được
sau mã hoá được gọi là bản mã (văn bản mã hoá). Bản mã được gửi đi trên một
đường truyền tới người nhận. Sau khi nhận bản mã, người nhận giải mã nó để
tìm hiểu nội dung.
Sử dụng các ký hiệu của hệ mật mã, các công việc trên được toán học hoá
bởi các công thức sau:

EK ( P ) = C ; DK (C ) = P.

Như vậy trong một hệ thống mật mã khái quát sẽ có các thành phần sau:
– Văn bản trơn (plaintext), tức là thông điệp nguyên gốc chưa được mã
hóa.
– Văn bản mã hóa (ciphertext), tức là thông điệp đã được mã hóa.

14

– Thuật toán mã hóa (enciphering algorithm) là các giao thức hoặc hướng
dẫn có tác dụng chuyển đổi văn bản trơn thành văn bản mã hóa. Đối với các hệ

thống mật mã truyền thống, chỉ có người gửi thông điệp biết được thuật toán mã
hóa, tuy nhiên đối với các hệ thống dùng mật mã hóa khóa công khai (Public
key code – PKC), tất cả mọi người đều có thể biết thuật toán mã hóa mà không
ảnh hưởng tiêu cực đến an ninh của hệ thống.
– Khóa mã hóa (enciphering key) là một hoặc nhiều đối tượng (thường là
các con số hay là các hướng dẫn quan trọng nào đó) được dùng trong việc mã
hóa văn bản trơn. Ngoại trừ trong hệ thống PKC, để đảm bảo bí mật an toàn thì
khóa mã hóa thường chỉ được người gửi biết.
– Thuật toán giải mã (deciphering algorithm) là các giao thức hoặc hướng
dẫn có tác dụng chuyển đổi văn bản mã hóa trở về văn bản trơn. Để đảm bảo bí
mật, chỉ có người nhận thông điệp biết được thuật toán giải mã.
– Khóa giải mã (deciphering key) là một hoặc nhiều đối tượng (thường là các

con số hay là các hướng dẫn quan trọng nào đó) được dùng trong việc giải mã
văn bản bị mã hóa. Để đảm bảo bí mật, chỉ có người nhận thông điệp biết được
khóa giải mã.
1.2.3. Một số thuật ngữ sử dụng trong hệ mật mã
Người gửi (Sender): Người gửi thông báo.
Người nhận (Receiver): Người nhận thông báo.
Văn bản rõ (Plaintext – Cleartext): Thông tin trước khi được mã hoá. Đây là
dữ liệu ban đâu ở dạng rõ. Thông tin gốc được ghi bằng hình ảnh âm thanh, chữ
số, chữ viết,… Mọi tín hiệu đều có thể được số hoá thành các xâu ký tự.
Như vậy, quá trình mã hóa được tiến hành bằng cách áp dụng hàm toán
học từ E lên P, vốn được biểu diễn dưới dạng số, để trở thành thông tin đã mã
hóa C.

Bản mã hoá (Ciphertext): Thông tin, dữ liệu đã được mã hoá dưới dạng mờ.

15

Khóa (key): Thành phần quan trọng trong việc mã hoá và giải mã. Khóa là
đại lượng bí mật, biến thiên trong một hệ mật.
Thuật toán mã hoá (CryptoGraphic Algorithm): Các thuật toán được sử dụng
trong việc mã hoá hoặc giải mã thông tin.
Hệ thống mã (CryptoSystem): Hệ thống mã hoá bao gồm thuật toán mã
hoá, khoá, Plaintext, Ciphertext.
Kỹ thuật mật mã (Cryptology) là môn khoa học bao gồm hai lĩnh vực: mật

mã (Cytography) và mã thám (Cryptoanalysis).
Mật mã: là lĩnh vực khoa học về các phương pháp biến đổi thông tin nhằm
mcụ đích bảo vệ thông tin khỏi sự truy cập của những người không có thẩm
quyền.
Mã thám: là lĩnh vực khoa học chuyên nghiên cứu, tìm kiếm yếu điểm của
các hệ mật để từ đó đưa ra phương pháp tấn công các hệ mật đó.
Sơ đồ mật mã là tập hợp các thuật toán mã hóa, giả mã, kiểm tra sự toàn vẹn
vàcác chức năng khác của một hệ mật.
Giao thức mật mã là tập hợp các quy tắc, thủ tục quy định cách thức sử dụng
sơ đồ mật mã trong một hệ mật mã.
Lập mã (Encrypt) là việc biến văn bản nguồn thành văn bản mã
Giải mã (Decrypt) là việc đưa văn bản đã mã hóa trở thành dạng văn

bản nguồn.
Định mã (encode/decode) là việc xác định ra phép tương ứng giữa các chữ
và số – Tốc độ mã được đặc trưng bởi số lượng phép tính (N) cần thực hiện để
mã hóa (giải mã) một đơn vị thông tin.
Khả năng chống nhiễu của mã là khả năng chống lại sự phát tán lỗi trong
bản tin sau khi giải mã, nếu trước đó xảy ra lỗi với bản mã trong quá trình bản
mã được truyền từ người gửi đến người nhận.

16

Mã dòng (Stream cipher) là việc tiến hành mã hóa liên tục trên từng ký tự

hay từng bit.
Mã khối (Block cipher) là việc tiến hành mã hoá trên từng khối văn bản.
1.2.3. Những yêu cầu đối với hệ mật mã hoá
Mật mã hóa được sử dụng phổ biến để đảm bảo an toàn cho thông tin liên
lạc. Các thuộc tính được yêu cầu là:
1. Bí mật: Chỉ có người nhận đã xác thực có thể lấy ra được nội dung của thông
tin chứa đựng trong dạng đã mật mã hóa của nó. Nói khác đi, nó không thể cho
phép thu lượm được bất kỳ thông tin đáng kể nào về nội dung của thông điệp.
2. Nguyên vẹn: Người nhận cần có khả năng xác định được thông tin có bị thay
đổi trong quá trình truyền thông hay không.
3. Xác thực: Người nhận cần có khả năng xác định người gửi và kiểm tra xem
người gửi đó có thực sự gửi thông tin đi hay không.

4. Không từ chối: Người gửi không thể từ chối việc mình đã gửi thông tin đi.
5. Chống lặp lại: Không cho phép bên thứ ba copy lại văn bản và gửi nhiều lần
đến người nhận mà người gửi không hề hay biết.
Mật mã học có thể cung cấp cơ chế để giúp đỡ thực hiện điều này. Tuy
nhiên, một số mục tiêu không phải bao giờ cũng là cần thiết, trong nghĩa cảnh
của thực tế hay mong muốn của người sử dụng. Ví dụ, người gửi thông tin có
thể mong muốn giữ mình là nặc danh; trong trường hợp này tính không từ chối
rõ ràng là không thích hợp.
1.2.4. Các hệ thống mã hóa
Có hệ thống mã hóa đối xứng (Hình 3) và hệ thống mã hóa bất đối xứng
(Hình 4). Hai loại mã hóa này khác nhau ở số lượng khóa. Mã hóa đối xứng sử
dụng cùng một khóa để mã hóa / giải mã. Trong khi đó, mã hóa bất đối xứng sử

dụng hai khóa khác nhau để mã hóa và giải mã thông tin. Mỗi hệ thống mã hóa
có ưu nhược điểm riêng. Mã hóa đối xứng xử lí nhanh nhưng độ an toàn không

17

cao. Mã hóa bất đối xứng xử lí chậm hơn, nhưng độ an toàn và tính thuân tiện
trong quản lí khóa cao. Trong các ứng dụng mã hóa hiện tại, người ta thường kết
hợp các ưu điểm của cả hai loại mã hóa này.

Hình 3: Sơ đồ mã hoá và giải mã đối xứng (mật mã khoá bí mật)

18

Hình 4: Mã hoá bất đối xứng (Mật mã khoá công khai)

Một thông điệp sau khi được mã hóa bởi chìa công khai sẽ chỉ có thể
được giải mã với chìa bí mật tương ứng. Do các thuật toán loại này sử dụng một
chìa khóa công khai (không bí mật) nên còn có tên gọi khác là public-key
cryptography (thuật toán mã hóa dùng chìa khóa công khai).
1.2.5. Ứng dụng của mã hóa
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, toà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ử.
Mã hoá có thể sử dụng để thi hành các giao thức khác nhau: không kỹ
năng kiểm chứng, an toàn tính toán nhiều bên và chia sẻ bí mật.
Mã hoá có thể sử dụng để thi hành việc quản lý bản quyền số hóa.
Mật mã hóa khóa công khai là một dạng mật mã hóa cho phép người sử
dụng trao đổi các thông tin mật mà không cần phải trao đổi các khóa chung bí

19

mật trước đó. Điều này được thực hiện bằng cách sử dụng một cặp khóa có quan
hệ toán học với nhau là khóa công khai và khóa cá nhân (hay khóa bí mật).

Thuật ngữ mật mã hóa khóa bất đối xứng thường được dùng đồng nghĩa
với mật mã hóa khóa công khai mặc dù hai khái niệm không hoàn toàn tương
đương. Có những thuật toán mật mã khóa bất đối xứng không có tính chất khóa
công khai và bí mật như đề cập ở trên mà cả hai khóa (cho mã hóa và giải mã)
đều cần phải giữ bí mật.
Trong mật mã hóa khóa công khai, khóa cá nhân phải được giữ bí mật trong
khi khóa công khai được phổ biến công khai. Trong 2 khóa, một dùng để mã hóa
và khóa còn lại dùng để giải mã. Điều quan trọng đối với hệ thống là không thể
tìm ra khóa bí mật nếu chỉ biết khóa công khai.
Hệ thống mật mã hóa khóa công khai có thể sử dụng với các mục đích sau:
– Mã hóa: giữ bí mật thông tin và chỉ có người có khóa bí mật mới giải mã
được.

– Tạo chữ ký số: cho phép kiểm tra một văn bản có phải đã được tạo với một
khóa bí mật nào đó hay không.
– Thỏa thuận khóa: cho phép thiết lập khóa dùng để trao đổi thông tin mật
giữa 2 bên.
Thông thường, các kỹ thuật mật mã hóa khóa công khai đòi hỏi khối lượng
tính toán nhiều hơn các kỹ thuật mã hóa khóa đối xứng nhưng những lợi điểm
mà chúng mang lại khiến cho chúng được áp dụng trong nhiều ứng dụng.
1.3. NHỮNG KHÁI NIỆM VÀ KẾT QUẢ SỐ HỌC
CÓ NHIỀU ỨNG DỤNG TRONG MÃ HÓA VÀ GIẢI MÃ THÔNG TIN
1.3.1. Số nguyên tố. Số nguyên tố là số nguyên lớn hơn 1, không chia hết cho số
nguyên dương nào ngoài 1 và chính nó. Số nguyên lớn hơn 1 không phải là số
nguyên tố được gọi là hợp số.

20

Định lý sau đây của Số học là một cơ sở quan trọng của thuật toán tìm các
số nguyên tố không vượt quá một số tự nhiên cho trước.
1.3.2. Định lí. Mọi hợp số n đều có ước nguyên tố nhỏ hơn hoặc bằng n .
Chứng minh. Thật vậy, vì n là hợp số nên ta gọi a và b là các ước thật sự của n.
Khi đó n = ab, trong đó 1 < a ≤ b < n. Rõ ràng ta phải có a hoặc b không vượt
quá

n, giả sử đó là a. Khi đó, ước nguyên tố của a cũng đồng thời là ước

nguyên tố của n.
1.3.3. Hệ quả. Mọi số tự nhiên n lớn 1 không có ước nguyên tố nhỏ hơn hoặc
bằng

n đều là số nguyên tố.
Chẳng hạn, số 31 không có có ước nguyên tố là 2, 3, 5 (các số nguyên tố

không vượt quá

31 ) nên 31 là số nguyên tố. Như vậy, để kiểm tra tính nguyên

tố của số 31 thay vì cần phải kiểm tra cả thảy là 30 phép chia, ta chỉ cần kiểm tra
3 phép chia, tức số phép chia giảm đi 10 lần.
Từ hệ quả trên, ta có thuật toán viết tất cả các số nguyên tố nhỏ hơn hoặc
bằng một số nguyên dương n cho trước.
1.3.4. Thuật toán sàng các số nguyên tố của Eratosthenes. Trước tiên, ta viết
dãy các số tự nhiên từ 1 đến n. Trong dãy đó, ta gạch bỏ số 1 vì nó không phải là
số nguyên tố. Số nguyên tố đầu tiên của dãy là số 2. Tiếp theo đó ta gạch khỏi
dãy số tất cả những số chia hết cho 2. Số đầu tiên không chia hết cho 2 là 3 và
đó chính là số nguyên tố. Ta lại gạch khỏi dãy số còn lại những số nào không
chia hết cho 3. Ta thu được số nguyên tố tiếp theo là 5. Tiếp tục như thế, ta gạch
khỏi dãy những số chia hết cho mọi số nguyên tố bé hơn hoặc bằng

n.

Sàng Eratosthenes mặc dù cho ta thuật toán xác định mọi số nguyên tố
không vượt quá một số cho trước nhưng lại rất ít được sử dụng để xác định xem
một số đã cho có phải là số nguyên tố hay không. Nguyên nhân là vì thuật toán

21

có độ phức tạp khá lớn: để kiểm tra n, ta phải thực hiện phép chia cho tất cả các
số nguyên tố không vượt quá n .
1.3.5. Định lí cơ bản của Số học. Mọi số nguyên lớn hơn 1 đều phân tích được

một cách duy nhất thành tích các số nguyên tố, trong đó các thừa số được viết
với thứ tự không giảm.
Chứng minh. Ta chứng minh mọi số nguyên lớn hơn 1có thể viết dưới dạng tích
của một hoặc nhiều số nguyên tố. Trước hết, mỗi số nguyên tố là tích của một
thừa số là chính nó. Giả sử rằng có các số nguyên dương lớn hơn 1 không biểu
diễn được thành tích các số nguyên tố. Khi đó gọi n là số nhỏ nhất trong các số
đó. Số n ≠ 1 và là hợp số. Do đó n = ab, trong đó cả a và b là các số nguyên
dương nhỏ hơn n. Vì n là số nhỏ nhất không thể phân tích thành tích các số
nguyên tố nên cả a và b phân tích được thành tích các số nguyên tố. Nhưng khi
đó n = ab lại phân tích được. Điều này mâu thuẫn với giả thiết.
Ta giả sử rằng tồn tại số nguyên lớn hơn 1 mà có hai cách biểu diễn dưới
dạng tích các thừa số nguyên tố. Khi đó, giả sử s là số nhỏ nhất trong các số như

vậy, tức là s = p1p2…pm = q1q2…qn với pi,qj là các số nguyên tố. Do p1 chia hết
q1q2…qn suy ra tồn tại qj mà p1 chia hết qj. Từ đó ta có pi = qj, bỏ hai số nguyên tố
ra khỏi đẳng thức ta được hai vế là hai khai triển khác nhau của số s chia cho p1,
mà theo giả thiết s là số nhỏ nhất như vậy, mâu thuẫn này chứng tỏ giả thiết là
sai. Vậy mỗi số nguyên lớn hơn 1 chỉ có một biểu diễn duy nhất dưới dạng tích
thừa số nguyên tố (không kể đến thứ tự các thừa số). ▄
1.3.6. Thuật toán Euclid. Thuật toán cho phép xác định ước chung lớn nhất
(gcd) của hai số nguyên nguyên dương. Với a, b là các số nguyên dương (giả
thiết a > b). Ta xét 3 trường hợp sau:
a) Nếu b là ước của a thì (a, b) = b.
b) Nếu a = bq + r thì (a, b) = (b, r).

22

c) Trường hợp tổng quát:
Ta thực hiện liên tiếp các phép chia sau đây cho tới khi xuất hiện số dư
bằng 0 thì dừng lại.
a = bq0 + r0, 0 < r0 ≤ b − 1
b = r0 q1 + r1, 0 < r1 ≤ r0 − 1
r0 = r1q2 + r2, 0 < r2 ≤ r1 − 1
M
rm −2 = rm −1qm + rm, 0 < rm ≤ rm −1 − 1
rm −1 = rm qm +1 ,

rm +1 = 0.
Vì bất đẳng thức sau đây là xảy ra, nên quá trình chia nói trên là dừng lại
sau không quá a bước, hay quá trình này là một thuật toán:
a > b > r0 > r1 > L > rm−1 > rm > rm+1 = 0 .

Từ đó, ta có ước chung lớn nhất của a, b là
d = (a, b) = (b, r0 ) = (r0, r1 ) = (r1, r2 ) = L = (rm −1, rm ) = rm .
Thuật toán trên được gọi là Thuật toán Euclid tìm ước chung lớn nhất của
hai số nguyên dương.
1.3.7. Thuật toán Euclide mở rộng. Thuật toán này sử dụng để giải phương
trình Diophant ax + by = c, trong đó a,b,c là các số nguyên; x, y là các ẩn nhận
giá trị nguyên. Điều kiện cần và đủ để phương trình này có nghiệm nguyên là

ước chung lớn nhất của a và b là ước của c. Khẳng định này dựa trên một mệnh
đề sau: Nếu d là ước chung lớn nhất của a,b thì tồn tại các số nguyên x, y sao
cho ax + by = d .
Thuật toán Euclid mở rộng kết hợp quá trình tìm ước chung lớn nhất của
a,b trong thuật toán Euclid với việc tìm một cặp số nguyên x, y thoả mãn
phương trình Diophantine nói trên bằng phương pháp truy hồi.

23

1.3.8. Định nghĩa. Hàm số Euler ϕ (m) là hàm số học có giá trị tại mỗi số tự
nhiên m ≠ 0 bằng số các số nguyên dương không vượt quá m và nguyên tố cùng

nhau với m:

ϕ ( m) =

∑

1

1≤ k ≤m
( k, m ) =1

.

Hàm ϕ (m) có nhiều ứng dụng vì nó là kích thước (xem 1.3.12) của nhóm
nhân các số nguyên modulo m. Hơn nữa, đối với hàm Euler ϕ (m) ta có công
thức Gaus là công thức tổng trải trên các ước dương d của m:

å j (d ) = m .
dm

1.3.9. Định lí Euler. Nếu a và m > 1 là các số nguyên, nguyên tố cùng nhau thì

aϕ ( m ) ≡ 1(mod m) .
Định lí Euler có thể dùng để tìm nghịch đảo modm. Chẳng hạn, nếu a và

m là các số nguyên nguyên tố cùng nhau, ta có aaϕ ( m) −1 ≡ 1(mod m) tức là aϕ ( m )−1
là nghịch đảo của a theo modm. Từ đó cũng suy ra nghiệm của phương trình
đồng dư tuyến tính ax ≡ b(mod m) với ( a, m) = 1 là x ≡ aϕ ( m )−1b(mod m) .
Các tính chất của hàm Euler được sử dụng để tính đồng dư của những lũy
thừa rất lớn. Chẳng hạn, ta cần tính a n mod k, trong đó n là một số nguyên lớn.
Ta xét một ví dụ bằng số. Tìm số dư trong phép chia 21000000 cho 77.
Ta có ϕ (7) = 6; ϕ (11) = 10;26 ≡ 1(mod 7); 210 ≡ 1(mod11) .
Do đó, 230 ≡ 1(mod 7); 230 ≡ 1(mod11) .
Vì vậy

230 º 1(mod 77).

Mặt khác, 1000000 = 30.33333 + 10 cho nên:
21000000 º 210 º 23(mod 77) .

24

1.3.10. Định lí Fermat bé. Nếu p là số nguyên tố và a là số nguyên không chia
hết cho p thì a p −1 ≡ 1(mod p) Nói cách khác, nếu p là số nguyên tố và a là số
nguyên bất kỳ thì a p ≡ a (mod p ) .
Một cách độc lập các nhà toán học Trung quốc đã đưa ra một giả thuyết
(thường gọi là Giả thuyết Trung Quốc) nói rằng: p là một số nguyên tố khi và
chỉ khi 2 p º 2(mod p). Đúng là, nếu p là số nguyên tố, thì 2 p º 2(mod p). Đây

là trường hợp đặc biệt của Định lý bé Fermat. Tuy thế, điều ngược lại
(nếu 2 p º 2(mod p) thì p là số nguyên tố) là sai. Chẳng hạn, 2341 º 2(mod341) ,
nhưng 341 = 11.31 là hợp số. Như vậy, mệnh đề ngược lại của Định lí Fermat
bé không đúng. Tuy nhiên, qua nhiều thống kê cho thấy rằng nếu một số nguyên
thỏa mãn kết luận của Định lí Fermat bé thì “có nhiều khả năng” nó là số nguyên
tố. Do đó, dẫn xuất đến khái niệm sau.
1.3.11. Số giả nguyên tố. Nếu ta muốn kiểm tra số n có là số nguyên tố không,
ta lấy ngẫu nhiên các số a và kiểm tra xem đồng dư thức a n ≡ a(mod n) có đúng
không. Nếu nó không đúng với một giá trị a nào đó thì n là hợp số. Nếu đồng dư
thức đúng với một hoặc nhiều giá trị của a, thì ta nói rằng n là số nguyên tố với
xác suất nào đó, hay n là một số giả nguyên tố (pseudoprime).
Nếu n là một hợp số và tồn tại một số nguyên a sao cho a n º a(mod n) ,

thì p được gọi là số giả nguyên tố cơ sở a.
F. Sarrus vào năm 1820 đã tìm thấy 341 = 11×31 là số giả nguyên tố cơ
sở 2 đầu tiên.
Một số nguyên n là số giả nguyên tố cơ sở a với mọi số nguyên a được
gọi là số Carmichael (chẳng hạn số 561).

25

1.3.12. Định lí Trung Quốc (Chinese Remainder Theorem). Giả sử m1,…, mr
là các số nguyên dương, nguyên tố cùng nhau từng đôi một. Khi đó, hệ phương
trình đồng dư:

 x ≡ a1 (mod m1 )
 x ≡ a (mod m )

2
2

 M
 x ≡ ar (mod mr )
có nghiệm duy nhất theo môđun m = m1m2 …mr .
1.3.13. Nhóm nhân ¢ *m các số nguyên modm
Nếu m > 1 là một số nguyên thì tập hợp các lớp đồng dư modm có đại
diện nguyên tố cùng nhau với m tạo thành một nhóm với phép nhân và được ký

hiệu bởi ¢ *m. Cấp của nhóm này cho bởi giá trị j (m) của hàm Euler. Giá trị
j (m) được gọi là kích thước của nhóm nhân ¢ *m. Nếu m là số nguyên tố, thì

kích thước và cấp của nhóm này là m − 1. Một phần tử sinh của nhóm nhân ¢ *m
được gọi là một căn nguyên thủy modm.
Dùng Định lý số dư Trung Hoa, ta có kết quả: Nhóm nhân ¢ *m là tích trực
tiếp của các nhóm nhân theo mỗi lũy thừa cực đại của các ước nguyên tố của m.
*
*
*
Chẳng hạn, ¢ 24 = ¢ 2 × ¢ 3 là một nhóm xyclic cấp 8.
3

Nhóm ¢ *m có nhiều ứng dụng trong Lý thuyết số và Mật mã học bởi công
cụ kích thước j (m) của nó.
1.3.14. Bậc của một số nguyên. Cho a, m là các số nguyên dương, nguyên tố
cùng nhau. Khi đó, theo Định lý Euler ta có đồng dư thức
aj ( m ) º 1(mod m) .
Số nguyên dương x nhỏ nhất thỏa điều kiện
a x º 1(mod m)

BỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG ĐẠI HỌC VINHNGUYỄN VĂN THÀMỘT VÀI ỨNG DỤNG CỦA SỐ HỌCTRONG MÃ HÓA VÀ GIẢI MÃ THÔNG TINCHUYÊN NGÀNH : ĐẠI SỐ VÀ LÝ THUYẾT SỐMã số : 60 46 05LU ẬN VĂN THẠC SĨ TOÁN HỌCNgười hướng dẫn khoa họcPGS. TS. NGUYỄN THÀNH QUANGNGHỆ AN – 2013M ỤC LỤCMỞ ĐẦUCHƯƠNG 1TRANGM ỘT SỐ KIẾN THỨC CƠ SỞ1. 11.21.3 Tổng quan về mật mãMã hoáNhững khái niệm và tác dụng Số học có nhiều ứng dụng trong mã16hoá và giải thuật thông tinCHƯƠNG 2 ỨNG DỤNG CỦA SỐ HỌC25TRONG MỘT SỐ HỆ THỐNG MẬT MÃ2. 12.22.3 Mật mã CaesarThuật toán mã hoá RSAMật mã VigenèreKẾT LUẬNTÀI LIỆU THAM KHẢO2528414344MỞ ĐẦUTừ lâu loài người đã biết các thao tác về Số học và sử dụng nó trong cácgiao dịch thường nhật liên tục trong nhiều thế kỷ. Nhưng đến thời tăng trưởng củaToán học, Số học phải nhường chỗ cho những phép tính phức tạp như đạo hàm, vi phân, tích phân và những bài toán khác. Cho đến những năm 70 của thế kỷXX, Số học vẫn được xem là một trong những ngành kim chỉ nan thuần túy nhấtcủa toán học. Thậm chí, có nhà toán học cho rằng vẻ đẹp của Số học có được lànhờ sự xa rời thực tiễn của nó [ 6 ]. Nhưng cũng chính nhờ máy tính, một tinhhoa của văn minh quả đât vào thế kỷ XX, đã làm tái sinh môn học cổ xưa này. Máy tính không những phát huy mọi vẻ đẹp truyền thống lịch sử của Số học mà còntriển khai ra những ứng dụng đang và sẽ có cho tất cả chúng ta trong thế kỷ XXI.Hiện nay, công nghệ thông tin, công nghệ tiên tiến Internet, công nghệ E-mail, E – business tăng trưởng như vũ bão. Nước Ta đã, đang từng bước vận dụng côngnghệ mới để “ tin học hóa xã hội ” tức là đưa tin học vào các nghành của xã hộiđể cải tổ hoạt động giải trí thủ công bằng tay trước đây. Tin học hóa đã giải phóng sức laođộng của con người bằng cách sáng tạo. Như vậy tất cả chúng ta hoàn toàn có thể trao đổi mọithông tin qua mạng. tin tức gửi đi hoàn toàn có thể là thông tin quân sự chiến lược, kinh tế tài chính, kinhdoanh hoặc đơn thuần là một thông tin nào đó mang tính riêng tư … Điều này dẫntới một yếu tố xảy ra là Internet là môi trường tự nhiên không bảo đảm an toàn, đầy rủi ro đáng tiếc và nguyhiểm, không có gì bảo vệ rằng thông tin truyền đi không bị lộ trên đườngtruyền. Vì vậy, yếu tố bảo đảm an toàn cơ sở tài liệu, thông tin cá thể là yếu tố sốngcòn của bất kể tổ chức triển khai nào và bảo mật thông tin thông tin là nền móng cơ bản để pháttriển. Do đó, một giải pháp được đưa ra nhằm mục đích giúp tất cả chúng ta tự bảo vệ chínhmình cũng như những thông tin gửi đi là cần phải mã hóa thông tin. Ngành khoahọc mật mã không chỉ nghiên cứu và điều tra sự bảo mật thông tin của các sơ đồ mã hóa, mà còn mởrộng đến những ứng dụng thực tiễn như chữ ký điện tử, sơ đồ định danh rồi đưađến những khái niệm quan trọng của ngành khoa học máy tính và rộng hơn làcủa Toán học như khái niệm về các chứng tỏ tương tác ( interactives proofs ), chứng tỏ không để lộ tri thức ( zero-knowledge proofs ) và gần đây là cácchứng minh kiểm tra được một cách Tỷ Lệ bằng cách chỉ kiểm thử một hằngsố các bít thông tin trên bản chứng tỏ ( probabilistic checkable proofs ). Những công cụ ngày càng mạnh, Số học đã dần xâm nhập vào mật mã vàgóp phần đưa mật mã trở thành một ngành khoa học. Năm 1978, ba nhà khoahọc của MIT ( Massachusetts Institute of Technology ) là Rivest, Shamir vàAdleman yêu cầu một hệ mã, mà nay được gọi là RSA. Tính bảo mật thông tin và độ antoàn của hệ mã này được dựa trên độ phức tạp của bài toán số học nghiên cứu và phân tích mộtsố nguyên đủ lớn ra thừa số nguyên tố. Liên tiếp sau đó, các bài toán của lýthuyết số như bài toán lôgarit rời rạc và tìm thặng dư cấp 2 cũng đã được sửdụng để kiến thiết xây dựng các hệ mã Elgamal và Rabin. Ngoài ra, Định lý Euler, Định lýFermat bé, Định lý số dư Trung Quốc và Định lý Carmichael có rất nhiều ứngdụng trong các bài toán về số nguyên lớn vận dụng vào Lý thuyết mật mã. Nhờđó, các kim chỉ nan mới của Số học, đặc biệt quan trọng là Số học thuật toán, tìm thấy nhữngứng dụng trực tiếp vào thực tiễn. trái lại, với sự sử dụng thoáng đãng hệ mã RSA, Elgamal trong thực tiễn, việc nghiên cứu và điều tra các giải thuật hiệu suất cao cho các bài toánphân tích thành thừa số nguyên tố và lôgarit rời rạc trên các trường hữu hạn trởnên rất được chăm sóc trong Lý thuyết số. Như vậy, Số học đã hiện hữu trong các hoạt động giải trí thực tiễn : Kỹ thuật máytính, mật mã, trao đổi trực tuyến giữa các ngân hàng nhà nước, thẻ ATM, truyền phát tínhiệu vệ tinh, sàn chứng khoán … Mục đích của bản luận văn này là tìm hiểu và khám phá những ứng dụng của Số họcvào 1 số ít nghành mã hóa và giải thuật thông tin, nhằm mục đích chứng minh và khẳng định tính đúngđắn của các thuật toán mật mã và bảo vệ toán học của chúng. Ngoài phần mở màn, Kết luận và tài liệu tìm hiểu thêm, luận văn này gồm có 2 chương. Chương 1 trình diễn các kiến thức và kỹ năng cơ sở tổng quan về Mật mã học và Sốhọc ( Phân tích nguyên tố, Phép tính đồng dư, Định lý số dư Trung Quốc, Định lýEuler, Định lý Fermat bé, Số giả nguyên tố, Định lý Carmichael, Hàm số Euler, Hàm số Carmichael, Phân tích Fermat ). Chương 2 trình diễn một số hệ mật mã ( mãCesaz, mã RSA ) có tương quan trực tiếp đến ứng dụng công cụ phép tính đồng dư vàcác tác dụng số học khác trong mã hoá và giải thuật thông tin. Luận văn này được triển khai xong dưới sự hướng dẫn tận tình và chu đáo củaPGS. TS. Nguyễn Thành Quang. Tác giả xin bày tỏ lòng kính trọng và biết ơn sâusắc tới thầy giáo hướng dẫn khoa học, người đã dành nhiều thời hạn và công sứcgiúp đỡ cho tôi để hoàn thành xong luận văn này. Tác giả xin bày tỏ lòng biết ơn và gửi lời cảm ơn đến các thầy cô giáo thuộcchuyên ngành Đại số và Lý thuyết số, Khoa Toán, Phòng Đào tạo Sau Đại học – Trường Đại học Vinh, những người đã tận tình giảng dạy và tạo mọi điều kiệnthuận lợi thành công xuất sắc của khóa học. Xin trân trọng cảm ơn Trường Đại học Hồ Chí Minh đã tạo mọi điều kiện kèm theo tổ chứcthuận lợi cho chúng tôi hoàn thành xong trách nhiệm học tập. Xin chân thành cảm ơn bè bạn, đồng nghiệp, mái ấm gia đình đã động viên và giúpđỡ tôi trong học tập và nghiên cứu và điều tra. Xin gửi lời cảm ơn đến Ban giám hiệu Trường Trung học Phổ thông PhùngHưng – Sở Giáo dục và Đào tạo TP. Hồ Chí Minh, các thầy cô giáo đồng nghiệp đãđộng viên và tạo điều kiện kèm theo thuận tiện để tôi triển khai xong trách nhiệm học tập. Mặc dù đã có nhiều cố gắng nỗ lực, tuy nhiên luận văn vẫn còn nhiều thiếu sót, tác giảmong nhận được sự góp phần của thầy cô giáo và các đồng nghiệp. TÁC GIẢCHƯƠNG 1M ỘT SỐ KIẾN THỨC CƠ SỞ1. 1. TỔNG QUAN VỀ MẬT MÃ HỌC1. 1.1. Mật mã học. Mật mã học ( cryptography ) là một nghành nghề dịch vụ tương quan vớicác kỹ thuật ngôn từ và toán học để bảo vệ bảo đảm an toàn thông tin, đơn cử làtrong thông tin liên lạc. Về phương diện lịch sử dân tộc, mật mã học gắn liền với quátrình mã hóa ; điều này có nghĩa là nó gắn với các phương pháp để quy đổi thôngtin từ dạng này sang dạng khác nhưng ở đây là từ dạng thường thì có thểnhận thức được thành dạng không hề nhận thức được, làm cho thông tin trởthành dạng không hề đọc được nếu như không có các kỹ năng và kiến thức bí hiểm. Quátrình mã hóa được sử dụng hầu hết để bảo vệ tính bí hiểm của các thông tinquan trọng, ví dụ điển hình trong công tác làm việc tình báo, quân sự chiến lược hay ngoại giao cũng nhưcác bí hiểm về kinh tế tài chính, thương mại. Trong những năm gần đây, nghành hoạtđộng của mật mã hóa đã được lan rộng ra : mật mã hóa văn minh phân phối cơ chếcho nhiều hoạt động giải trí hơn là chỉ duy nhất việc giữ bí hiểm và có một loạt các ứngdụng như : xác nhận khóa công khai minh bạch, chữ ký số, bầu cử điện tử hay thanh toánđiện tử. Ngoài ra, những người không có nhu yếu thiết yếu đặc biệt quan trọng về tính bímật cũng sử dụng các công nghệ tiên tiến mật mã hóa, thường thì được phong cách thiết kế và tạolập sẵn trong các hạ tầng của công nghệ tiên tiến giám sát và liên lạc viễn thông. Mật mã học là một nghành nghề dịch vụ liên ngành, được tạo ra từ 1 số ít nghành khác. Các dạng cổ nhất của mật mã hóa hầu hết tương quan với các kiểu mẫutrong ngôn từ. Gần đây thì tầm quan trọng đã biến hóa và mật mã hóa sử dụngvà gắn liền nhiều hơn với toán học, đơn cử là toán học rời rạc, gồm có các vấnđề tương quan đến kim chỉ nan số, kim chỉ nan thông tin, độ phức tạp đo lường và thống kê, thốngkê và tổng hợp. Mật mã hóa là công cụ được sử dụng trong bảo mật an ninh máy tínhvà mạng. Việc điều tra và nghiên cứu tìm các phương pháp để phá vỡ việc sử dụng mật mã đượcgọi là nghiên cứu và phân tích mật mã, hay phá mã. Mật mã hóa và nghiên cứu và phân tích mật mã đôi khiđược nhóm lại cùng nhau dưới tên gọi chung mật mã học, nó gồm có toàn bộcác chủ đề tương quan đến mật mã. Trong thực tiễn, thuật ngữ mật mã hóa thôngthường được sử dụng để nói đến ngành này một cách tổng thể và toàn diện. Mật mã hóa là quy trình quy đổi các thông tin thường thì ( văn bảnthường hay văn bản rõ hay văn bản trơn ) thành dạng không đọc trực tiếp được, là văn bản mã hóa. Giải mật mã hay giải thuật là quy trình ngược lại, hồi sinh lạivăn bản thường từ văn bản mã. Mật mã là thuật toán để mật mã hóa và giải mậtmã. Hoạt động đúng chuẩn của mật mã thường thì được trấn áp bởicác khóa — một đoạn thông tin bí hiểm nào đó được cho phép tùy biến cách thức tạo ravăn bản mã. Các giao thức mật mã chỉ rõ các chi tiết cụ thể về việc mật mã ( và các nềntảng mật mã hóa khác ) được sử dụng như thế nào để thu được các trách nhiệm cụthể. Một bộ các giao thức, thuật toán, phương pháp quản trị khóa và các hành độngquy định trước bởi người sử dụng cùng phối hợp ngặt nghèo tạo thành hệ thốngmật mã. Trong cách nói thường thì, ” mã ” bí hiểm thường thì được sử dụng đồngnghĩa với ” mật mã “. Trong mật mã học, thuật ngữ này có ý nghĩa kỹ thuật đặcbiệt : Các mã là các giải pháp tham gia vào việc sửa chữa thay thế các đơn vị chức năng văn bảnlớn hơn, thường thì là các từ hay câu văn ( ví dụ, ” qua tao ” thay thế sửa chữa cho ” tancong luc rang dong ” ). trái lại, mật mã hóa cổ xưa thường thì thay thếhoặc sắp xếp lại các vần âm riêng không liên quan gì đến nhau ( hoặc một nhóm nhỏ các vần âm ). Ví dụ, ” tan cong luc rang dong ” trở thành ” ubo dpoh mvd sboh epoh ” bằng cách thay thế sửa chữa. Hình 1 : Sơ đồ khái quát về một mạng lưới hệ thống mật mã. 1.1.2. Lịch sử tăng trưởng của mật mãMật mã học là một ngành có lịch sử dân tộc từ hàng nghìn năm nay. Trong phầnlớn thời hạn tăng trưởng của mình ( ngoại trừ vài thập kỷ trở lại đây ), lịch sử vẻ vang mậtmã học chính là lịch sử dân tộc của những giải pháp mật mã học cổ xưa – cácphương pháp mật mã hóa với bút và giấy, nhiều lúc có tương hỗ từ những dụng cụ cơkhí đơn thuần. Vào đầu thế kỷ XX, sự Open của các cơ cấu tổ chức cơ khí và điện cơ, ví dụ điển hình như máy Enigma, đã cung ứng những chính sách phức tạp và hiệu quảhơn cho việc mật mã hóa. Sự sinh ra và tăng trưởng can đảm và mạnh mẽ của ngành điện tử vàmáy tính trong những thập kỷ gần đây đã tạo điều kiện kèm theo để mật mã học phát triểnnhảy vọt lên một tầm cao mới. Sự tăng trưởng của mật mã học luôn luôn đi kèmvới sự tăng trưởng của các kỹ thuật phá mã ( hay thám mã ). Các phát hiện và ứngdụng của các kỹ thuật phá mã trong một số ít trường hợp đã có tác động ảnh hưởng đáng kểđến các sự kiện lịch sử vẻ vang. Hai sự kiện đã khiến cho mật mã học trở nên thích hợpcho mọi người, đó là : sự Open của tiêu chuẩn mật mã hóa DES và sự ra đờicủa các kỹ thuật mật mã hóa khóa công khai minh bạch. 101.1.3. Mật mã học cổ điểnNhững vật chứng sớm nhất về sử dụng mật mã học là các chữ tượnghì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 đâykhoảng 4500 năm ). Những ký hiệu tỏ ra không phải để ship hàng mục tiêu truyềnthông tin bí hiểm mà có vẻ như như thể nhằm mục đích mục tiêu gợi nên những điều thần bí, trítò mò hoặc thậm chí còn để tạo sự thú vị cho người xem. Ngoài ra, còn rất nhiềuví dụ khác về những ứng dụng của mật mã học cổ xưa. Trong mật mã học, mật mã học cổ xưa là một dạng của mật mã học đãđược sử dụng trong lịch sử dân tộc tăng trưởng của loài người nhưng thời nay đã trở nênlạc hậu do các phương pháp mã hóa này quá đơn thuần và những kẻ tiến công cóthể thuận tiện bẻ khóa trải qua nhiều phương pháp như tiến công vét cạn ( ví dụnhư dùng máy tính thử hết mọi trường hợp ) hay dựa trên tiến công thống kê ( dựatrên tần suất Open của các vần âm ). Nói chung, mật mã học cổ xưa hoạt động giải trí trên cơ sở bảng vần âm ( chẳnghạn các ký tự từ ” A ” tới ” Z ” trong tiếng Anh ), và chúng được thực thi bằng tayhay một số ít máy móc cơ khí đơn thuần. trái lại, các quy mô mã hóa hiện đạisử dụng các máy tính hay các công nghệ tiên tiến số hóa khác, và hoạt động giải trí mã hóa dựatrên việc sửa chữa thay thế các bit hay byte. Các phương pháp mã hóa cổ xưa thôngthường dễ bị tổn thương ( phá mã ) bởi các tiến công văn bản mã hóa, đôi khithậm chí kẻ tiến công không cần biết các chi tiết cụ thể đơn cử của mạng lưới hệ thống mã hóa, bằng cách sử dụng các công cụ như nghiên cứu và phân tích tần suất. Đôi khi người ta cũngcho rằng các phương pháp mã hóa như phương pháp mã hóa của cỗ máyEnigma thuộc về các phương pháp mã hóa cổ xưa mặc dầu phương pháp mã hóa nàyđã sử dụng các thiết bị và công nghệ tiên tiến văn minh nhất vào thời gian đó ( trong thờikỳ của Thế chiến II ). Các phương pháp mã hóa cổ xưa hầu hết dựa trên mật mã hóa hoánvị và mật mã hóa thay thế sửa chữa. Trong mật mã hóa sửa chữa thay thế, các ký tự ( hoặc nhóm ký11tự ) được thay thế sửa chữa một cách có quy luật trong hàng loạt thông điệp bằng các ký tựkhác ( hoặc nhóm ký tự ), ví dụ điển hình câu I am Mr. Enigma from được thay bằngcâu This is morning star, sau đó các ký tự còn lại trong bảng vần âm được thaythế theo một quy luật nào đó xác lập trước. Trong phương pháp mật mã hóahoán vị thì các ký tự được giữ không đổi, nhưng trật tự của chúng trong bản tinlại biến hóa theo một quy luật nào đó. Có các thuật toán phức tạp để thực hiệnviệc mật mã hóa bằng cách tổng hợp hai phương pháp trên để tạo ra mẫu sản phẩm mãhóa ; các phương pháp mã hóa khối tân tiến như DES hay AES thực thi việclặp đi lặp lại 1 số ít bước thay thế sửa chữa và hoán vị. 1.1.4. Mật mã học hiện đạiNhiều người cho rằng kỷ nguyên của mật mã học tân tiến được bắt đầuvớ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 kim chỉ nan về truyền thông online trong các mạng lưới hệ thống bảo mật thông tin ( Communication Theory of Secrecy Systems ) trên tập san Bell SystemTechnical Journal – Tập san kỹ thuật của mạng lưới hệ thống Bell – và một thời hạn ngắnsau đó, trong cuốn Mathematical Theory of Communication – Lý thuyết toánhọc trong truyền thông online – cùng với tác giả Warren Weaver. Những công trìnhnày, cùng với những khu công trình nghiên cứu và điều tra khác của ông về kim chỉ nan về tin họcvà truyền thông online ( information and communication theory ), đã thiết lập một nềntảng triết lý cơ bản cho mật mã học và thám mã học. Với sự sinh ra của máy tính kỹ thuật số và điện tử học thì các mật mã cựckỳ phức tạp đã hoàn toàn có thể được triển khai. Đặc trưng của mật mã máy tính là chúngthực hiện trên các chuỗi nhị phân, không giống như trong các quy mô mật mãhóa cổ xưa và cơ học ( chỉ sử dụng bảng vần âm với khoảng chừng 26 ký tự – phụthuộc vào từng ngôn từ ). Mật mã máy tính cũng có năng lực chịu đựng việcphân tích mật mã tốt hơn ; rất ít các mật mã như thế dễ bị tổn thương chỉ bởi kiểutấn công biết bản mã. 12C ác nghiên cứu và điều tra thoáng đãng có tính học thuật về mật mã hóa tân tiến là tươngđối gần đây – nó chỉ được mở màn trong hội đồng mở kể từ những năm thậpniên 1970 với các cụ thể kỹ thuật của DES ( viết tắt trong tiếng Anh của DataEncryption Standard tức Tiêu chuẩn Mật mã hóa Dữ liệu ) và sự ý tưởng ra mãRSA. Kể từ đó, mật mã hóa đã trở thành công cụ được sử dụng thoáng đãng trongliên lạc và bảo mật thông tin máy tính. 1.2. MÃ HOÁ1. 2.1. Khái niệm mã hoá và giải mãTrong mật mã học, một ngành toán học ứng dụng cho công nghệ tiên tiến thôngtin, mã hóa là giải pháp để biến thông tin ( phim ảnh, văn bản, hình ảnh … ) từđịnh dạng thông thường sang dạng thông tin không hề hiểu được nếu không cóphương tiện giải thuật. Giải mã là chiêu thức để đưa từ dạng thông tin đã được mã hóa về dạngthông tin bắt đầu, quy trình ngược của mã hóa. Mục đích của mã hóa là che dấu thông tin trước khi truyền trên kênh. 1.2.2. Khái niệm mạng lưới hệ thống mã hoá. Một mạng lưới hệ thống mã hóa ( hệ mật mã ) baogồm 5 thành phần ( P., C, K, D, E ) : 1. Các thông tin trước khi mã hóa, kí hiệu là P. ( Plaintext ), 2. Các thông tin sau khi mã hóa, kí hiệu là C ( Ciphertext ), 3. Các chìa khóa, kí hiệu là K ( Key ) ; 4. Các quy tắc mã hóa, ký hiệu là E ( Encrytion ), 5. Các quy tắc giải thuật, kí hiệu là D ( Decrytion ), thoả mãn điều kiện kèm theo sau : Với mỗi k ∈ K có một quy tắc mã ek : P. → C và một quytắc giải thuật tương ứng d k : C → P. sao cho d k ( ek ( x ) ) = x, ∀ x ∈ P. 13N hư vậy, quy trình mã hóa được triển khai bằng cách vận dụng hàm toánhọc từ E lên P., vốn được màn biểu diễn dưới dạng số, để trở thành thông tin đã mãhóa C.Hình 2 : Các thành phần của mật mãQuá trình giải thuật được thực thi ngược lại : Áp dụng hàm D lên thôngtin C để được thông tin đã giải thuật P.Một thông tin thường được tổ chức triển khai dưới dạng bản rõ ( văn bản trơn ). Người gửi bản thông tin sẽ làm trách nhiệm mã hoá bản rõ, hiệu quả thu đượcsau mã hoá được gọi là bản mã ( văn bản mã hoá ). Bản mã được gửi đi trên mộtđường truyền tới người nhận. Sau khi nhận bản mã, người nhận giải thuật nó đểtìm hiểu nội dung. Sử dụng các ký hiệu của hệ mật mã, các việc làm trên được toán học hoábởi các công thức sau : EK ( P. ) = C ; DK ( C ) = P.Như vậy trong một mạng lưới hệ thống mật mã khái quát sẽ có các thành phần sau : – Văn bản trơn ( plaintext ), tức là thông điệp nguyên gốc chưa được mãhóa. – Văn bản mã hóa ( ciphertext ), tức là thông điệp đã được mã hóa. 14 – Thuật toán mã hóa ( enciphering algorithm ) là các giao thức hoặc hướngdẫn có công dụng quy đổi văn bản trơn thành văn bản mã hóa. Đối với các hệthống mật mã truyền thống lịch sử, chỉ có người gửi thông điệp biết được thuật toán mãhóa, tuy nhiên so với các mạng lưới hệ thống dùng mật mã hóa khóa công khai minh bạch ( Publickey code – PKC ), tổng thể mọi người đều hoàn toàn có thể biết thuật toán mã hóa mà khôngảnh hưởng xấu đi đến bảo mật an ninh của mạng lưới hệ thống. – Khóa mã hóa ( enciphering key ) là một hoặc nhiều đối tượng người dùng ( thường làcác số lượng hay là các hướng dẫn quan trọng nào đó ) được dùng trong việc mãhóa văn bản trơn. Ngoại trừ trong mạng lưới hệ thống PKC, để bảo vệ bí hiểm bảo đảm an toàn thìkhóa mã hóa thường chỉ được người gửi biết. – Thuật toán giải thuật ( deciphering algorithm ) là các giao thức hoặc hướngdẫn có tính năng quy đổi văn bản mã hóa trở về văn bản trơn. Để bảo vệ bímật, chỉ có người nhận thông điệp biết được thuật toán giải thuật. – Khóa giải thuật ( deciphering key ) là một hoặc nhiều đối tượng người tiêu dùng ( thường là cáccon số hay là các hướng dẫn quan trọng nào đó ) được dùng trong việc giải mãvăn bản bị mã hóa. Để bảo vệ bí hiểm, chỉ có người nhận thông điệp biết đượckhóa giải thuật. 1.2.3. Một số thuật ngữ sử dụng trong hệ mật mãNgười gửi ( Sender ) : Người gửi thông tin. Người nhận ( Receiver ) : Người nhận thông tin. Văn bản rõ ( Plaintext – Cleartext ) : tin tức trước khi được mã hoá. Đây làdữ liệu ban đâu ở dạng rõ. tin tức gốc được ghi bằng hình ảnh âm thanh, chữsố, chữ viết, … Mọi tín hiệu đều hoàn toàn có thể được số hoá thành các xâu ký tự. Như vậy, quy trình mã hóa được thực thi bằng cách vận dụng hàm toánhọc từ E lên P., vốn được màn biểu diễn dưới dạng số, để trở thành thông tin đã mãhóa C.Bản mã hoá ( Ciphertext ) : tin tức, tài liệu đã được mã hoá dưới dạng mờ. 15K hóa ( key ) : Thành phần quan trọng trong việc mã hoá và giải thuật. Khóa làđại lượng bí hiểm, biến thiên trong một hệ mật. Thuật toán mã hoá ( CryptoGraphic Algorithm ) : Các thuật toán được sử dụngtrong việc mã hoá hoặc giải thuật thông tin. Hệ thống mã ( CryptoSystem ) : Hệ thống mã hoá gồm có thuật toán mãhoá, khoá, Plaintext, Ciphertext. Kỹ thuật mật mã ( Cryptology ) là môn khoa học gồm có hai nghành nghề dịch vụ : mậtmã ( Cytography ) và mã thám ( Cryptoanalysis ). Mật mã : là nghành nghề dịch vụ khoa học về các chiêu thức đổi khác thông tin nhằmmcụ đích bảo vệ thông tin khỏi sự truy vấn của những người không có thẩmquyền. Mã thám : là nghành khoa học chuyên nghiên cứu và điều tra, tìm kiếm yếu điểm củacác hệ mật để từ đó đưa ra giải pháp tiến công các hệ mật đó. Sơ đồ mật mã là tập hợp các thuật toán mã hóa, giả mã, kiểm tra sự toàn vẹnvàcác công dụng khác của một hệ mật. Giao thức mật mã là tập hợp các quy tắc, thủ tục lao lý phương pháp sử dụngsơ đồ mật mã trong một hệ mật mã. Lập mã ( Encrypt ) là việc biến văn bản nguồn thành văn bản mãGiải mã ( Decrypt ) là việc đưa văn bản đã mã hóa trở thành dạng vănbản nguồn. Định mã ( encode / decode ) là việc xác lập ra phép tương ứng giữa các chữvà số – Tốc độ mã được đặc trưng bởi số lượng phép tính ( N ) cần triển khai đểmã hóa ( giải thuật ) một đơn vị chức năng thông tin. Khả năng chống nhiễu của mã là năng lực chống lại sự phát tán lỗi trongbản tin sau khi giải thuật, nếu trước đó xảy ra lỗi với bản mã trong quy trình bảnmã được truyền từ người gửi đến người nhận. 16M ã dòng ( Stream cipher ) là việc triển khai mã hóa liên tục trên từng ký tựhay từng bit. Mã khối ( Block cipher ) là việc thực thi mã hoá trên từng khối văn bản. 1.2.3. Những nhu yếu so với hệ mật mã hoáMật mã hóa được sử dụng phổ cập để bảo vệ bảo đảm an toàn cho thông tin liênlạc. Các thuộc tính được nhu yếu là : 1. Bí mật : Chỉ có người nhận đã xác nhận hoàn toàn có thể lấy ra được nội dung của thôngtin tiềm ẩn trong dạng đã mật mã hóa của nó. Nói khác đi, nó không hề chophép thu lượm được bất kể thông tin đáng kể nào về nội dung của thông điệp. 2. Nguyên vẹn : Người nhận cần có năng lực xác lập được thông tin có bị thayđổi trong quy trình tiếp thị quảng cáo hay không. 3. Xác thực : Người nhận cần có năng lực xác lập người gửi và kiểm tra xemngười gửi đó có thực sự gửi thông tin đi hay không. 4. Không phủ nhận : Người gửi không hề phủ nhận việc mình đã gửi thông tin đi. 5. Chống lặp lại : Không được cho phép bên thứ ba copy lại văn bản và gửi nhiều lầnđến người nhận mà người gửi không hề hay biết. Mật mã học hoàn toàn có thể phân phối chính sách để giúp sức triển khai điều này. Tuynhiên, một số ít tiềm năng không phải khi nào cũng là thiết yếu, trong nghĩa cảnhcủa trong thực tiễn hay mong ước của người sử dụng. Ví dụ, người gửi thông tin cóthể mong ước giữ mình là nặc danh ; trong trường hợp này tính không từ chốirõ ràng là không thích hợp. 1.2.4. Các mạng lưới hệ thống mã hóaCó mạng lưới hệ thống mã hóa đối xứng ( Hình 3 ) và mạng lưới hệ thống mã hóa bất đối xứng ( Hình 4 ). Hai loại mã hóa này khác nhau ở số lượng khóa. Mã hóa đối xứng sửdụng cùng một khóa để mã hóa / giải thuật. Trong khi đó, mã hóa bất đối xứng sửdụng hai khóa khác nhau để mã hóa và giải thuật thông tin. Mỗi mạng lưới hệ thống mã hóacó ưu điểm yếu kém riêng. Mã hóa đối xứng xử lí nhanh nhưng độ bảo đảm an toàn không17cao. Mã hóa bất đối xứng xử lí chậm hơn, nhưng độ bảo đảm an toàn và tính thuân tiệntrong quản lí khóa cao. Trong các ứng dụng mã hóa hiện tại, người ta thường kếthợp các ưu điểm của cả hai loại mã hóa này. Hình 3 : Sơ đồ mã hoá và giải thuật đối xứng ( mật mã khoá bí hiểm ) 18H ình 4 : Mã hoá bất đối xứng ( Mật mã khoá công khai minh bạch ) Một thông điệp sau khi được mã hóa bởi chìa công khai minh bạch sẽ chỉ có thểđược giải thuật với chìa bí hiểm tương ứng. Do các thuật toán loại này sử dụng mộtchìa khóa công khai minh bạch ( không bí hiểm ) nên còn có tên gọi khác là public-keycryptography ( thuật toán mã hóa dùng chìa khóa công khai minh bạch ). 1.2.5. Ứng dụng của mã hóaMã hóa có vai trò rất quan trọng, đặc biệt quan trọng là trong thanh toán giao dịch điện tử. Nógiúp bảo vệ bí hiểm, toàn vẹn của thông tin, khi thông tin đó được truyền trênmạng. Mã hóa cũng là nền tảng của kĩ thuật chữ ký điện tử. Mã hoá hoàn toàn có thể sử dụng để thi hành các giao thức khác nhau : không kỹnăng kiểm chứng, bảo đảm an toàn thống kê giám sát nhiều bên và san sẻ bí hiểm. Mã hoá hoàn toàn có thể sử dụng để thi hành việc quản trị bản quyền số hóa. Mật mã hóa khóa công khai minh bạch là một dạng mật mã hóa cho phép người sửdụng trao đổi các thông tin mật mà không cần phải trao đổi các khóa chung bí19mật trước đó. Điều này được thực thi bằng cách sử dụng một cặp khóa có quanhệ toán học với nhau là khóa công khai minh bạch và khóa cá thể ( hay khóa bí hiểm ). Thuật ngữ mật mã hóa khóa bất đối xứng thường được dùng đồng nghĩavới mật mã hóa khóa công khai minh bạch mặc dầu hai khái niệm không trọn vẹn tươngđương. Có những thuật toán mật mã khóa bất đối xứng không có đặc thù khóacông khai và bí hiểm như đề cập ở trên mà cả hai khóa ( cho mã hóa và giải thuật ) đều cần phải giữ bí hiểm. Trong mật mã hóa khóa công khai minh bạch, khóa cá thể phải được giữ bí hiểm trongkhi khóa công khai minh bạch được phổ cập công khai minh bạch. Trong 2 khóa, một dùng để mã hóavà khóa còn lại dùng để giải thuật. Điều quan trọng so với mạng lưới hệ thống là không thểtìm ra khóa bí hiểm nếu chỉ biết khóa công khai minh bạch. Hệ thống mật mã hóa khóa công khai minh bạch hoàn toàn có thể sử dụng với các mục tiêu sau : – Mã hóa : giữ bí hiểm thông tin và chỉ có người có khóa bí hiểm mới giải mãđược. – Tạo chữ ký số : được cho phép kiểm tra một văn bản có phải đã được tạo với mộtkhóa bí hiểm nào đó hay không. – Thỏa thuận khóa : được cho phép thiết lập khóa dùng để trao đổi thông tin mậtgiữa 2 bên. Thông thường, các kỹ thuật mật mã hóa khóa công khai minh bạch yên cầu khối lượngtính toán nhiều hơn các kỹ thuật mã hóa khóa đối xứng nhưng những lợi điểmmà chúng mang lại khiến cho chúng được vận dụng trong nhiều ứng dụng. 1.3. NHỮNG KHÁI NIỆM VÀ KẾT QUẢ SỐ HỌCCÓ NHIỀU ỨNG DỤNG TRONG MÃ HÓA VÀ GIẢI MÃ THÔNG TIN1. 3.1. Số nguyên tố. Số nguyên tố là số nguyên lớn hơn 1, không chia hết cho sốnguyên dương nào ngoài 1 và chính nó. Số nguyên lớn hơn 1 không phải là sốnguyên tố được gọi là hợp số. 20 Định lý sau đây của Số học là một cơ sở quan trọng của thuật toán tìm cácsố nguyên tố không vượt quá 1 số ít tự nhiên cho trước. 1.3.2. Định lí. Mọi hợp số n đều có ước nguyên tố nhỏ hơn hoặc bằng n. Chứng minh. Thật vậy, vì n là hợp số nên ta gọi a và b là các ước thật sự của n. Khi đó n = ab, trong đó 1 < a ≤ b < n. Rõ ràng ta phải có a hoặc b không vượtquán, giả sử đó là a. Khi đó, ước nguyên tố của a cũng đồng thời là ướcnguyên tố của n. 1.3.3. Hệ quả. Mọi số tự nhiên n lớn 1 không có ước nguyên tố nhỏ hơn hoặcbằngn đều là số nguyên tố. Chẳng hạn, số 31 không có có ước nguyên tố là 2, 3, 5 ( các số nguyên tốkhông vượt quá31 ) nên 31 là số nguyên tố. Như vậy, để kiểm tra tính nguyêntố của số 31 thay vì cần phải kiểm tra cả thảy là 30 phép chia, ta chỉ cần kiểm tra3 phép chia, tức số phép chia giảm đi 10 lần. Từ hệ quả trên, ta có thuật toán viết toàn bộ các số nguyên tố nhỏ hơn hoặcbằng một số ít nguyên dương n cho trước. 1.3.4. Thuật toán sàng các số nguyên tố của Eratosthenes. Trước tiên, ta viếtdãy các số tự nhiên từ 1 đến n. Trong dãy đó, ta gạch bỏ số 1 vì nó không phải làsố nguyên tố. Số nguyên tố tiên phong của dãy là số 2. Tiếp theo đó ta gạch khỏidãy số tổng thể những số chia hết cho 2. Số tiên phong không chia hết cho 2 là 3 vàđó chính là số nguyên tố. Ta lại gạch khỏi dãy số còn lại những số nào khôngchia hết cho 3. Ta thu được số nguyên tố tiếp theo là 5. Tiếp tục như vậy, ta gạchkhỏi dãy những số chia hết cho mọi số nguyên tố bé hơn hoặc bằngn. Sàng Eratosthenes mặc dầu cho ta thuật toán xác lập mọi số nguyên tốkhông vượt quá một số ít cho trước nhưng lại rất ít được sử dụng để xác lập xemmột số đã cho có phải là số nguyên tố hay không. Nguyên nhân là vì thuật toán21có độ phức tạp khá lớn : để kiểm tra n, ta phải thực thi phép chia cho toàn bộ cácsố nguyên tố không vượt quá n. 1.3.5. Định lí cơ bản của Số học. Mọi số nguyên lớn hơn 1 đều nghiên cứu và phân tích đượcmột cách duy nhất thành tích các số nguyên tố, trong đó các thừa số được viếtvới thứ tự không giảm. Chứng minh. Ta chứng tỏ mọi số nguyên lớn hơn 1 hoàn toàn có thể viết dưới dạng tíchcủa một hoặc nhiều số nguyên tố. Trước hết, mỗi số nguyên tố là tích của mộtthừa số là chính nó. Giả sử rằng có các số nguyên dương lớn hơn 1 không biểudiễn được thành tích các số nguyên tố. Khi đó gọi n là số nhỏ nhất trong các sốđó. Số n ≠ 1 và là hợp số. Do đó n = ab, trong đó cả a và b là các số nguyêndương nhỏ hơn n. Vì n là số nhỏ nhất không hề nghiên cứu và phân tích thành tích các sốnguyên tố nên cả a và b nghiên cứu và phân tích được thành tích các số nguyên tố. Nhưng khiđó n = ab lại nghiên cứu và phân tích được. Điều này xích míc với giả thiết. Ta giả sử rằng sống sót số nguyên lớn hơn 1 mà có hai cách trình diễn dướidạng tích các thừa số nguyên tố. Khi đó, giả sử s là số nhỏ nhất trong các số nhưvậy, tức là s = p1p2 ... pm = q1q2 ... qn với pi, qj là các số nguyên tố. Do p1 chia hếtq1q2 ... qn suy ra sống sót qj mà p1 chia hết qj. Từ đó ta có pi = qj, bỏ hai số nguyên tốra khỏi đẳng thức ta được hai vế là hai khai triển khác nhau của số s chia cho p1, mà theo giả thiết s là số nhỏ nhất như vậy, xích míc này chứng tỏ giả thiết làsai. Vậy mỗi số nguyên lớn hơn 1 chỉ có một màn biểu diễn duy nhất dưới dạng tíchthừa số nguyên tố ( không kể đến thứ tự các thừa số ). ▄ 1.3.6. Thuật toán Euclid. Thuật toán được cho phép xác lập ước chung lớn nhất ( gcd ) của hai số nguyên nguyên dương. Với a, b là các số nguyên dương ( giảthiết a > b ). Ta xét 3 trường hợp sau : a ) Nếu b là ước của a thì ( a, b ) = b. b ) Nếu a = bq + r thì ( a, b ) = ( b, r ). 22 c ) Trường hợp tổng quát : Ta thực thi liên tục các phép chia sau đây cho tới khi Open số dưbằng 0 thì dừng lại. a = bq0 + r0, 0 < r0 ≤ b − 1 b = r0 q1 + r1, 0 < r1 ≤ r0 − 1 r0 = r1q2 + r2, 0 < r2 ≤ r1 − 1 rm − 2 = rm − 1 qm + rm, 0 < rm ≤ rm − 1 − 1 rm − 1 = rm qm + 1, rm + 1 = 0. Vì bất đẳng thức sau đây là xảy ra, nên quy trình chia nói trên là dừng lạisau không quá a bước, hay quy trình này là một thuật toán : a > b > r0 > r1 > L > rm − 1 > rm > rm + 1 = 0. Từ đó, ta có ước chung lớn nhất của a, b làd = ( a, b ) = ( b, r0 ) = ( r0, r1 ) = ( r1, r2 ) = L = ( rm − 1, rm ) = rm. Thuật toán trên được gọi là Thuật toán Euclid tìm ước chung lớn nhất củahai số nguyên dương. 1.3.7. Thuật toán Euclide lan rộng ra. Thuật toán này sử dụng để giải phươngtrình Diophant ax + by = c, trong đó a, b, c là các số nguyên ; x, y là các ẩn nhậngiá trị nguyên. Điều kiện cần và đủ để phương trình này có nghiệm nguyên làước chung lớn nhất của a và b là ước của c. Khẳng định này dựa trên một mệnhđề sau : Nếu d là ước chung lớn nhất của a, b thì sống sót các số nguyên x, y saocho ax + by = d. Thuật toán Euclid lan rộng ra tích hợp quy trình tìm ước chung lớn nhất củaa, b trong thuật toán Euclid với việc tìm một cặp số nguyên x, y thoả mãnphương trình Diophantine nói trên bằng giải pháp truy hồi. 231.3.8. Định nghĩa. Hàm số Euler ϕ ( m ) là hàm số học có giá trị tại mỗi số tựnhiên m ≠ 0 bằng số các số nguyên dương không vượt quá m và nguyên tố cùngnhau với m : ϕ ( m ) = 1 ≤ k ≤ m ( k, m ) = 1H àm ϕ ( m ) có nhiều ứng dụng vì nó là kích cỡ ( xem 1.3.12 ) của nhómnhân các số nguyên modulo m. Hơn nữa, so với hàm Euler ϕ ( m ) ta có côngthức Gaus là công thức tổng trải trên các ước dương d của m : å j ( d ) = m. dm1. 3.9. Định lí Euler. Nếu a và m > 1 là các số nguyên, nguyên tố cùng nhau thìaϕ ( m ) ≡ 1 ( mod m ). Định lí Euler hoàn toàn có thể dùng để tìm nghịch đảo modm. Chẳng hạn, nếu a vàm là các số nguyên nguyên tố cùng nhau, ta có aaϕ ( m ) − 1 ≡ 1 ( mod m ) tức là aϕ ( m ) − 1 là nghịch đảo của a theo modm. Từ đó cũng suy ra nghiệm của phương trìnhđồng dư tuyến tính ax ≡ b ( mod m ) với ( a, m ) = 1 là x ≡ aϕ ( m ) − 1 b ( mod m ). Các đặc thù của hàm Euler được sử dụng để tính đồng dư của những lũythừa rất lớn. Chẳng hạn, ta cần tính a n mod k, trong đó n là một số nguyên lớn. Ta xét một ví dụ bằng số. Tìm số dư trong phép chia 21000000 cho 77. Ta có ϕ ( 7 ) = 6 ; ϕ ( 11 ) = 10 ; 26 ≡ 1 ( mod 7 ) ; 210 ≡ 1 ( mod11 ). Do đó, 230 ≡ 1 ( mod 7 ) ; 230 ≡ 1 ( mod11 ). Vì vậy230 º 1 ( mod 77 ). Mặt khác, 1000000 = 30.33333 + 10 do đó : 21000000 º 210 º 23 ( mod 77 ). 241.3.10. Định lí Fermat bé. Nếu p là số nguyên tố và a là số nguyên không chiahết cho p thì a p − 1 ≡ 1 ( mod p ) Nói cách khác, nếu p là số nguyên tố và a là sốnguyên bất kể thì a p ≡ a ( mod p ). Một cách độc lập các nhà toán học Trung quốc đã đưa ra một giả thuyết ( thường gọi là Giả thuyết Trung Quốc ) nói rằng : p là một số nguyên tố khi vàchỉ khi 2 p º 2 ( mod p ). Đúng là, nếu p là số nguyên tố, thì 2 p º 2 ( mod p ). Đâylà trường hợp đặc biệt quan trọng của Định lý bé Fermat. Tuy thế, điều ngược lại ( nếu 2 p º 2 ( mod p ) thì p là số nguyên tố ) là sai. Chẳng hạn, 2341 º 2 ( mod341 ), nhưng 341 = 11.31 là hợp số. Như vậy, mệnh đề ngược lại của Định lí Fermatbé không đúng. Tuy nhiên, qua nhiều thống kê cho thấy rằng nếu 1 số ít nguyênthỏa mãn Tóm lại của Định lí Fermat bé thì ” có nhiều năng lực ” nó là số nguyêntố. Do đó, dẫn xuất đến khái niệm sau. 1.3.11. Số giả nguyên tố. Nếu ta muốn kiểm tra số n có là số nguyên tố không, ta lấy ngẫu nhiên các số a và kiểm tra xem đồng dư thức a n ≡ a ( mod n ) có đúngkhông. Nếu nó không đúng với một giá trị a nào đó thì n là hợp số. Nếu đồng dưthức đúng với một hoặc nhiều giá trị của a, thì ta nói rằng n là số nguyên tố vớixác suất nào đó, hay n là một số ít giả nguyên tố ( pseudoprime ). Nếu n là một hợp số và sống sót 1 số ít nguyên a sao cho a n º a ( mod n ), thì p được gọi là số giả nguyên tố cơ sở a. F. Sarrus vào năm 1820 đã tìm thấy 341 = 11 × 31 là số giả nguyên tố cơsở 2 tiên phong. Một số nguyên n là số giả nguyên tố cơ sở a với mọi số nguyên a đượcgọi là số Carmichael ( ví dụ điển hình số 561 ). 251.3.12. Định lí Trung Quốc ( Chinese Remainder Theorem ). Giả sử m1, …, mrlà các số nguyên dương, nguyên tố cùng nhau từng đôi một. Khi đó, hệ phươngtrình đồng dư :  x ≡ a1 ( mod m1 )  x ≡ a ( mod m )  M   x ≡ ar ( mod mr ) có nghiệm duy nhất theo môđun m = m1m2 … mr. 1.3.13. Nhóm nhân ¢ * m các số nguyên modmNếu m > 1 là một số nguyên thì tập hợp các lớp đồng dư modm có đạidiện nguyên tố cùng nhau với m tạo thành một nhóm với phép nhân và được kýhiệu bởi ¢ * m. Cấp của nhóm này cho bởi giá trị j ( m ) của hàm Euler. Giá trịj ( m ) được gọi là size của nhóm nhân ¢ * m. Nếu m là số nguyên tố, thìkích thước và cấp của nhóm này là m − 1. Một phần tử sinh của nhóm nhân ¢ * mđược gọi là một căn nguyên thủy modm. Dùng Định lý số dư Nước Trung Hoa, ta có tác dụng : Nhóm nhân ¢ * m là tích trựctiếp của các nhóm nhân theo mỗi lũy thừa cực lớn của các ước nguyên tố của m. Chẳng hạn, ¢ 24 = ¢ 2 × ¢ 3 là một nhóm xyclic cấp 8. Nhóm ¢ * m có nhiều ứng dụng trong Lý thuyết số và Mật mã học bởi côngcụ kích cỡ j ( m ) của nó. 1.3.14. Bậc của 1 số ít nguyên. Cho a, m là các số nguyên dương, nguyên tốcùng nhau. Khi đó, theo Định lý Euler ta có đồng dư thứcaj ( m ) º 1 ( mod m ). Số nguyên dương x nhỏ nhất thỏa điều kiệna x º 1 ( mod m )

Source: https://mindovermetal.org
Category: Ứng dụng hay