..

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGUYỄN TAM CƢỜNG

SỐ HỌC SỐ LỚN CHO MẬT MÃ

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

Thái Nguyên - 2013

Số hóa bởi trung tâm học liệu

/>

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGUYỄN TAM CƢỜNG

SỐ HỌC SỐ LỚN CHO MẬT MÃ
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01

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

Ngƣời hƣớng dẫn khoa học: PGS. TSKH NGUYỄN XUÂN HUY

Thái Nguyên - 2013

Số hóa bởi trung tâm học liệu

/>

i

LỜI CAM ĐOAN
Học viên xin cam đoan, toàn bộ nội dung liên quan tới đề tài đƣợc trình
bày trong luận văn là bản thân học viên tự tìm hiểu và nghiên cứu, dƣới sự
hƣớng dẫn khoa học của Thầy giáo PGS. TSKH Nguyễn Xuân Huy.
Các tài liệu, số liệu tham khảo đƣợc trích dẫn đầy đủ nguồn gốc. Học viên
xin chịu trách nhiệm trƣớc pháp luật lời cam đoan của mình.
Thái Nguyên, ngày 10 tháng 10 năm 2013

Học viên thực hiện

Nguyễn Tam Cƣờng

Số hóa bởi trung tâm học liệu

/>

ii

LỜI CẢM ƠN
Học viên xin gửi lời cảm ơn tới các Thầy, cơ đã tận tình truyền đạt các
kiến thức quý báu cho học viên trong suốt quá trình học tập.
Đặc biệt, học viên xin gửi lời cảm ơn và biết ơn sâu sắc nhất tới Thầy giáo
PGS. TSKH Nguyễn Xuân Huy, thầy đã tận tình chỉ bảo học viên trong suốt quá

trình thực hiện đề tài. Bên cạnh những kiến thức khoa học, thầy đã giúp học viên
nhận ra những bài học về phong cách học tập, làm việc và những kinh nghiệm
sống quý báu.
Học viên xin bày tỏ lịng biết ơn tới gia đình, bạn bè, đồng nghiệp và
những ngƣời thân đã động viên khích lệ tinh thần và giúp đỡ để học viên hoàn
thành luận văn này.

Số hóa bởi trung tâm học liệu

/>

iii

MỤC LỤC
LỜI CAM ĐOAN ..................................................................................................... i
LỜI CẢM ƠN ......................................................................................................... ii
MỤC LỤC ............................................................................................................. iii
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT .............................................. v
MỞ ĐẦU................................................................................................................ 1

1. Lý do chọn đề tài .......................................................................................... 1
2. Đối tƣợng và phạm vi nghiên cứu ................................................................. 2
3. Hƣớng nghiên cứu ......................................................................................... 2
4. Những nội dung nghiên cứu chính ................................................................ 3
5. Phƣơng pháp nghiên cứu ............................................................................... 3
6. Ý nghĩa khoa học và thực tiễn cửa đề tài ...................................................... 3
Chƣơng 1: CÁC KHÁI NIỆM CƠ BẢN................................................................ 5

1.1 Một số khái niệm toán học [1], [2], [3], [6], [7], [12]. [13] ........................ 5
1.1.1 Ƣớc chung lớn nhất [1], [2], [7], [13] ................................................. 5

1.1.2 Số nguyên tố và nguyên tố cùng nhau ................................................ 7
1.1.3 Đồng dƣ thức [1][2][7] ........................................................................ 9
1.1.4 Không gian Zn và Zn* [1], [2], [7] .................................................... 10
1.1.5 Phần tử nghịch đảo [1], [2], [7] ......................................................... 10
1.1.6 Hàm

Euler [1], [2], [7] ................................................................... 11

1.1.7 Các phép tốn trong khơng gian modulo [7] .................................... 11
1.1.8 Độ phức tạp tính tốn [1], [2]............................................................ 12
1.1.9 Hàm một phía và hàm cửa sập một phía [1], [3], [6] ........................ 16
1.2 Vấn đề mã hóa [3], [6], [7], [8] ................................................................ 17
1.2.1 Một số khái niệm cơ bản về mã hoá ................................................. 17
1.2.2 Hệ mật mã ......................................................................................... 19
1.2.3 Những tính năng của hệ mật mã ....................................................... 19

Số hóa bởi trung tâm học liệu

/>

iv
1.3 Giới thiệu về hệ mã khố cơng khai......................................................... 20
1.3.1 Hệ mật mã công khai RSA (Rivest-Shamir-Adleman) ..................... 22
1.3.2 Cơ chế hoạt động của RSA [1], [3], [6], [7], [8] ................................ 23
1.3.3 Khả năng bị tấn công của hệ mật mã công khai RSA [1], [2], [6], [7] ...... 26
Chƣơng 2: THƢ VIỆN TÍNH TỐN SỐ LỚN ................................................... 29

2.1 Biểu diễn số lớn [2], [4] ........................................................................... 29
2.2 Các phép toán trên số lớn ......................................................................... 33
2.2.1 So sánh hai số [2], [4] ....................................................................... 33

2.2.2 Cộng hai số lớn không âm [2], [4], [5] ............................................. 36
2.2.3 Trừ hai số lớn không âm [2], [4], [5], [9] ......................................... 40
2.2.4 Phép nhân hai số lớn không âm [2], [4], [5], [9]............................... 43
2.2.5 Phép chia hai số lớn không âm [2], [4], [5], [9] ................................ 45
2.2.6 Lũy thừa [2], [4], [5], [11]................................................................. 47
2.2.7 Ƣớc chung lớn nhất [1], [2], [6], [7] ................................................. 49
2.2.8 Phép cộng theo modulo p [1], [2], [6], [7] ........................................ 49
2.2.9 Phép nhân theo modulo p [1], [2], [6], [7] ........................................ 50
2.2.10 Phép cộng có dấu [1], [2], [4], [6] ................................................... 51
2.2.11 Phép trừ có dấu [1], [2], [4], [6] ...................................................... 52
2.3.12 Phép nhân có dấu [1], [2], [4], [6] ................................................... 52
2.3.13 Phép chia có dấu [1], [2], [4], [6] .................................................... 52
Chƣơng 3: ỨNG DỤNG THƢ VIỆN SỐ LỚN CHO HỆ MẬT MÃ RSA ............. 53

3.1 Phân tích các phép xử lý toán học trong hệ mật mã RSA ......................... 53
3.2 Xây dựng hệ mật mã RSA thử nghiệm [1], [2], [4], [6], [7], [8] .............. 53
3.3 Đánh giá kết quả thực nghiệm và kết luận ................................................ 63
3.3.1 Đánh giá và kết quả thực nghiệm ....................................................... 63
3.3.2 Kết luận .............................................................................................. 64
TÀI LIỆU THAM KHẢO ................................................................................... 65

Số hóa bởi trung tâm học liệu

/>

v

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
CRT


Chinese Remainder Theorem

DES

Data Encryption Standard

RSA

Rivest Shamir Adleman

GCD

Great Comon Divisor

FFT

Fast Fourier Transform
Hàm Euler

O

Biểu diễn thời gian chạy

gcd(a,b)

Ƣớc chung lớn nhất của hai số a và b
Phép tính nhân

Số hóa bởi trung tâm học liệu


/>

1

MỞ ĐẦU
1. Lý do chọn đề tài
Mật mã học là một trong những vấn đề quan trọng trong lĩnh vực bảo mật và
an tồn thơng tin. Trên thế giới, mật mã học đã đƣợc ra đời từ thời La Mã cổ đại và
ngày càng đƣợc nghiên cứu, phát triển đạt đƣợc những thành tựu to lớn. Trong mật
mã học, vấn đề bảo mật luôn đi đôi với vấn đề xác thực thơng tin, đặc biệt trong hệ
thống mã hóa khóa công khai vấn đề xác thực là vô cùng quan trọng.
Các hệ mã cơng khai nhƣ RSA thực hiện tính toán với các số nguyên lớn
hàng trăm chữ số. Độ phức tạp trong việc giải mã các hệ mã này tỉ lệ hàm mũ
với độ lớn của các số nguyên tham gia vào việc tạo khóa mã hóa và khóa cơng
khai. Do đó để hệ mã an tồn, cần tăng kích thƣớc của các số ngun.
Độ an tồn của hệ thống RSA dựa trên 2 vấn đề của toán học: bài tốn
phân tích ra thừa số ngun tố các số nguyên lớn và bài toán RSA. Nếu 2 bài
toán trên là khó (khơng tìm đƣợc thuật tốn hiệu quả để giải chúng) thì khơng
thể thực hiện đƣợc việc phá mã tồn bộ đối với RSA.
Mặt khác, khi kích thƣớc của các số nguyên cần xử lý lớn thì thời gian xử
lý của chƣơng trình mã hóa cũng tăng lên.
Thơng tin cần mã hóa ngày càng đa dạng và có khối lƣợng lớn, đòi hỏi hệ
mã giảm thiểu thời gian xử lý.
Các cơng cụ và giải thuật nhằm bẻ khóa các hệ mật mã đƣợc cải tiến đòi
hỏi hệ mã cần đƣợc nâng cấp tính bảo mật.
Tuy nhiên, việc nghiên cứu và triển khai các nâng cấp trong việc tối ƣu
hóa về mặt thuật toán trong các phép xử lý số học của các hệ mã còn hạn chế
trong phạm vi các chƣơng trình độc quyền.
Để hỗ trợ giải quyết các vấn đề trên, đề tài này tập trung vào việc xây
dựng một số thuật tốn tối ƣu hóa nhằm tăng hiệu quả các phép tính tốn thực

hiện với số ngun lớn.

Số hóa bởi trung tâm học liệu

/>

2
Các kết quả của đề tài sẽ đƣợc ứng dụng trong việc hỗ trợ cho các phép
xử lý số học của các hệ mã. Từ đó làm tăng tốc độ xử lý và tính bảo mật của các
hệ mã.
Từ tính cấp thiết của vấn đề tối ƣu hóa các hệ mã công khai, đồng thời
đƣợc sự hƣớng dẫn và gợi ý của Thầy giáo PGS.TSKH Nguyễn Xuân Huy, học
viên đã chọn đề tài cho luận văn tốt nghiệp Cao học ngành khoa học máy tính là:
“SỐ HỌC SỐ LỚN CHO MẬT MÔ.
2. Đối tƣợng và phạm vi nghiên cứu
a. Đối tƣợng của đề tài
- Độ phức tạp tính tốn.
- Cơ sở lý thuyết của số học: các phép toán trên số nguyên kích thƣớc lớn:
Cộng, trừ, nhân, chia, số dƣ, số nguyên tố, ƣớc chung lớn nhất,..
- Tổ chức dữ liệu cho các số nguyên kích thƣớc lớn.
- Các thuật toán của số học số nguyên: sơ đồ hoạt động, độ phức tạp.
b. Phạm vi nghiên cứu
Đề tài thực hiện việc tối ƣu hóa các phép tốn với số ngun lớn theo tiếp
cận hƣớng đối tƣợng.
Ứng dụng thử nghiệm trong một hệ mã nhằm so sánh hiệu năng xử lý của
hệ mã trƣớc và sau khi tối ƣu.
Đề tài giới hạn trong phạm vi nghiên cứu để đƣa ra giải pháp, việc triển
khai ứng dụng thực tiễn cần có thêm các điều kiện về thời gian và quy mô.
3. Hƣớng nghiên cứu
Đề tài tập trung vào việc xây dựng một số thuật tốn tối ƣu hóa nhằm tăng

hiệu quả các phép tính tốn thực hiện với số ngun lớn .
- Nghiên cứu các q trình thực hiện mã hóa và giải mã của các hệ mã
cơng khai.
- Tìm hiểu các thuật toán xử lý số học đƣợc dùng trong các hệ mã.

Số hóa bởi trung tâm học liệu

/>

3
- Phát hiện các giải thuật tính tốn cần tối ƣu hóa.
- Đƣa ra giải pháp tối ƣu hóa các giải thuật này.
- Ứng dụng trong một hệ mã RSA.
- Đối sánh với kết quả thực thi của hệ mã khi chƣa thực hiện tối ƣu hóa.
4. Những nội dung nghiên cứu chính
- Đề tài luận văn thuộc lĩnh vực lý thuyết thuật tốn xử lí các số ngun
lớn dài hàng trăm chữ số và ứng dụng trong mật mã, cụ thể là khảo sát cách tổ
chức dữ liệu và các thuật tốn số học số lớn.
- Học viên tìm hiểu tổng quan về lớp các số Big Numbers, các thuật tốn
mật mã RSA, khảo sát tính ngun tố theo Miller-Rabin.
- Lập trình và kiểm thử, đối sánh với các sơ đồ hiện có.
5. Phƣơng pháp nghiên cứu
- Thu thập và phân tích các tài liệu và thơng tin liên quan đến đề tài.
- Nghiên cứu dựa trên việc tìm hiểu các giải thuật xử lý với số nguyên
lớn của các hệ mã. Cụ thể là hệ mã hóa RSA, từ kết quả nghiên cứu có đƣợc sẽ
định hƣớng lựa chọn thuật tốn nào cần tối ƣu hóa.
- Thực hiện việc tối ƣu hóa các giải thuật bằng cách tối ƣu các phép xử lý
với số học lớn. Thao tác này sử dụng kết hợp các phƣơng pháp tính tốn với số
học với phƣơng pháp chia để trị nhằm tăng hiệu năng của từng bƣớc xử lý.
- Kết hợp các nghiên cứu trƣớc đây của các tác giả trong và ngồi nƣớc

cùng với sự chỉ bảo, góp ý của giáo viên hƣớng dẫn để hoàn thành nội dung
nghiên cứu.
- Thực nghiệm cài đặt ứng dụng để minh họa các vấn đề trình bày trong
đề tài.
6. Ý nghĩa khoa học và thực tiễn cửa đề tài
* Ý nghĩa khoa học:
- Trình bày các kiến thức toán học cơ bản, lý thuyết độ phức tạp của
thuật toán, các thuật toán thƣờng dùng trong các hệ mật mã khố cơng khai.

Số hóa bởi trung tâm học liệu

/>

4
- Trình bày các phƣơng pháp mật mã gồm: phƣơng pháp mã hố khóa bí
mật và phƣơng pháp mã hố khóa cơng khai. Với phƣơng pháp mã hóa khóa
cơng khai thì tập trung vào các thuật tốn mã hóa RSA. Với phƣơng pháp mã
hóa khóa bí mật chỉ giới thiệu sơ lƣợc để so sánh với phƣơng pháp mã hóa khóa
cơng khai.
- Tối ƣu các phép xử lý số học với số nguyên lớn là một yêu cầu cần
thiết trong việc xây dựng các hệ mã hóa có tốc độ xử lý và độ an toàn cao.
* Ý nghĩa thực tiễn:
- Cài đặt hoàn chỉnh các giải thuật xử lý số học với số nguyên lớn cỡ hàng
trăm chữ số.
- Xây dựng chƣơng trình thử nghiệm các giải thuật xây dựng đƣợc trong
một hệ mã.
- Đánh giá kết quả so sánh hiệu năng xử lý của hệ mã trƣớc và sau khi tối ƣu.

Số hóa bởi trung tâm học liệu


/>

5
Chƣơng 1
CÁC KHÁI NIỆM CƠ BẢN
1.1 Một số khái niệm toán học [1], [2], [3], [6], [7], [12]. [13]
1.1.1 Ước chung lớn nhất [1], [2], [7], [13]
Trong toán học, nếu số nguyên a chia hết cho số nguyên d thì số d đƣợc
gọi là ƣớc của số nguyên a, a đƣợc gọi là bội của d.
Ƣớc chung lớn nhất (ƢCLN) của hai số a và b là số nguyên d khi d là ƣớc
chung lớn nhất của a và b.
Trong trƣờng hợp cả hai số nguyên a và b đều bằng 0 thì chúng khơng có
ƢCLN vì khi đó mọi số tự nhiên khác không đếu là ƣớc chung của a và b. Nếu
chỉ một trong hai số a hoặc b bằng 0, số kia khác khơng thì ƢCLN của chúng
bằng giá trị tuyệt đối của số khác không.
Ƣớc chung lớn nhất của hai số a và b đƣợc ký hiệu là ƢCLN(a, b) hoặc
gcd(a, b)
Thí dụ: gcd(12, 18) = 6; gcd(−4, 14) = 2; gcd(5, 0) = 5
Các tính chất của ƣớc chung lớn nhất:
Mọi ƣớc chung của a và b là ƣớc của gcd(a, b)
gcd(a, b) với a và b khác 0, có thể định nghĩa tƣơng đƣơng nhƣ số nguyên
dƣơng d nhỏ nhất có dạng d = a p + b q trong đó p và q là các số nguyên
dƣơng.
gcd(a, 0) =

, với mọi a ≠ 0, vì mọi số khác khơng bất kỳ là ƣớc của 0,

và ƣớc lớn nhất của a là

.


Nếu a là ƣớc của tích b c, và gcd(a, b) = d, thì a/d là ƣớc của c.
Nếu m là số nguyên dƣơng, thì gcd(m·a, m·b) = m·gcd(a, b).
Nếu m là số nguyên bất kỳ , thì gcd(a + m·b, b) = gcd(a, b).
Nếu m ƣớc chung (khác 0) của a và b, thì gcd(a/m, b/m) = gcd(a, b)/m.
gcd là hàm giao hốn: gcd(a, b) = gcd(b, a).

Số hóa bởi trung tâm học liệu

/>

6
gcd là hàm kết hợp: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c).
gcd của ba số a, b, c tính đƣợc nhờ công thức gcd(a, b, c) = gcd(gcd(a, b) , c).
Cách tính ƣớc chung lớn nhất:
Muốn tìm ƣớc chung lớn nhất của hai số ta thực hiện các bƣớc nhƣ sau:
 Bƣớc 1: Phân tích mỗi thừa số ra thừa số nguyên tố.
 Bƣớc 2: Chọn ra các thừa số nguyên tố chung.
 Bƣớc 3: Lập tích các thừa số chọn, mỗi thừa số lấy với số mũ nhỏ nhất
của nó. tích đó là ƢCLN phải tìm.
Thí dụ: tìm gcd (18, 84)
Bƣớc 1: 18 = 2 32; 84 = 22 3 7
Bƣớc 2: thừa số chung: 2; 3
Bƣớc 3: tính tính 2 3 = 6  gcd(18, 84) = 6
Việc tìm ƢCLN bằng cách phân tích ra thừa số ngun tố trong thực tế
chỉ áp dụng cho các số nhỏ; việc phân tích các số lớn ra thừa số nguyên tố mất
rất nhiều thời gian.
Một phƣơng phát hiệu quả là giải thuật Euclid. Giải thuật này đã đƣợc
biết đến từ khoảng năm 300 trƣớc Cơng Ngun. Nhà tốn học Hy Lạp cổ
Euclid đã viết giải thuật này trong cuốn sách tốn nổi tiếng Elements.

Thí dụ: tìm gcd(91, 287)
Trƣớc hết lấy 287 (số lớn hơn trong 2 số) chia cho 91: 287 = 91 3 + 14
(91 và 14 sẽ đƣợc dùng cho vòng lặp kế)
Nhận xét: bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi:
287

91 3 = 14

Tƣơng tự, số chia hết bởi 91 và 14 cũng chia hết bởi 91 3 + 14 = 287. Do
đó, gcd(91, 287) = gcd(91, 14). Bài tốn trở thành tìm gcd(91, 14). Lặp lại quy
trình trên cho đến khi phép chia khơng cịn số dƣ nhƣ sau:
91 = 14 6 + 7 (14 và 7 sẽ đƣợc dùng cho vịng lặp kế)

Số hóa bởi trung tâm học liệu

/>

7
14 = 7 2 (khơng cịn số dƣ, kết thúc, nhận 7 làm kết quả)
Cuối cùng ta có: 7 = gcd(7, 0) = gcd(14, 7) = gcd(91, 14) = gcd(287, 91).
1.1.2 Số nguyên tố và nguyên tố cùng nhau
a, Số nguyên tố [1], [2], [7]
Số nguyên tố là số tự nhiên p (p >1) chỉ chia hết cho ±1 và ±p.
Thí dụ: các số nguyên tố từ 2 đến 100:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97
Số 2 là số nguyên tố nhỏ nhất, và 2 cũng là số nguyên tố chẵn duy nhất.
Hệ mật mã thƣờng sử dụng các số nguyên tố ít nhất là lớn hơn 10150.
Thuật tốn kiểm tra tính ngun tố: [1], [7], [12]
Ta thấy rằng, để kiểm tra tính nguyên tố của một số nguyên bằng phƣơng

pháp Monte Carlo (thuật tốn Miller-Rabin, Soloway-Strassen) đều có tốc độ
thực hiện khá nhanh (khoảng O(n2), với n là số bit của số cần kiểm tra). Tuy
nhiên, những thuật tốn này khơng đƣa ra một kết luận chính xác về tính nguyên
tố của con số, mà ln có một xác suất sai sót. Nhƣ vậy để có một sai số cực nhỏ
chấp nhận đƣợc, ta phải thực hiện thuật toán kiểm tra nhiều lần. Vậy thì, với
khoảng bao nhiêu số nguyên dƣơng ngẫu nhiên (có chiều dài xác định) thì có thể
tìm ra đƣợc một số nguyên tố. Theo lý thuyết thì số các số nguyên tố nhỏ hơn N
là: N/

.
Giả sử ta chọn p là số ngun có chiều dài 512-bits, thì xác suất để số p

nguyên tố là 1/354. Mặt khác, do chúng ta chỉ quan tâm đến những số lẻ, nên
xác suất để p nguyên tố là 2/354 = 1/177. Vậy thì, trung bình khoảng 177 số lẻ
ngẫu nhiên sẽ có 1 số nguyên tố.
Ngƣời ta đã cũng chứng minh đƣợc, thuật tốn Miller-Rabin dùng kiểm
tra tính ngun tố của một số nguyên dƣơng lẻ với sai số nhiều nhất là 1/4. Nếu
thực hiện thuật tốn này t lần thì sai số nhiều nhất sẽ là 1/4t, để đảm bảo chắc

Số hóa bởi trung tâm học liệu

/>

8
chắn tính nguyên tố cho số kiểm tra nên chọn số t > 20. Thuật toán này đƣợc sử
dụng trong q trình tạo khóa ở hệ mật mã RSA.
Thuật tốn Miller-Rabin: Kiểm tra tính nguyên tố của một số dạng 2km+1
Input n > 2, n = 2km + 1
Output [True, False] (True: n là số nguyên tố, False: n là hợp số)
Algorithm

1.

Giả sử n = 2km + 1; ( với m lẻ)

2.

Chọn số ngẫu nhiên a

3.

Tính b = am (mod n);

4.

if (b ^ 1 and b ^ (n - 1)) Return True; /* n

{2,..., n-1};

nguyên tố */
5.

i = 1;

6.

while (i < k and b ^ (n - 1))
{ b = b2 (mod n);
if (b = 1) Return False;

/* n là hợp số */


i ++;
}
if (b! = (n - 1)) Return False;/*

7.

n

hợp

số

*/
Return True;

8.

/* n là số nguyên tố */

Thuật toán: Kiểm tra tính nguyên tố của một số dạng 2km+1 với t lần thực
hiện (t > 20)
Input n > 2, n = 2km + 1
Output {True, False} (True: n là số nguyên tố, False: n là hợp số)
Algorithm
1.

Giả sử n = 2km + 1;

2.


For (j = 1; j < t; j++)
{ Chọn số ngẫu nhiên a

{2,

,n-1}

Tính b = am mod n;

Số hóa bởi trung tâm học liệu

/>

9
if (b = 1) continue;

/* quay lại bước

2*/.
i= 1;
while ((i < k) and (b ^ n - 1))
{ b = b2 mod n;
If (b = 1) Return False; /* n hợp số */
i= i + 1;
}
if (b <> (n -1)) Return False; /* n hợp số */
}

Return True;


3.

/* n là số nguyên tố

*/.

b, Số nguyên tố cùng nhau [1], [2], [7]
Trong toán học, các số nguyên a và b đƣợc gọi là nguyên tố cùng nhau
nếu chúng có ƣớc số chung lớn nhất là 1. Ký hiệu gcd (a, b) = 1.
Thí dụ: 6 và 35 là hai nguyên tố cùng nhau.
1.1.3 Đồng dư thức [1][2][7]
- Cho a và b là các số nguyên n là số nguyên dƣơng. Khi đó a đƣợc gọi là
đồng dƣ với b theo modulo n, ký hiệu là a

b (mod n), nếu a, b chia cho n có

cùng số dƣ. n đƣợc gọi là modulo của đồng dƣ.
Kí hiệu: a
Thí dụ: 11

b (mod n)
5 (mod 3) vì 11 và 5 khi chia cho 3 đều dƣ số dƣ là 2.

- Tính chất đồng dƣ
Cho a, a1, b, b1, c
a

Z. Ta có các tính chất sau:


b mod n nếu và chỉ nếu a và b có cùng số dƣ khi chia cho n

Tính phản xạ: a

a mod n

Tính đối xứng: Nếu a

b mod n thì b

Tính giao hốn: Nếu a

b mod n và b

Số hóa bởi trung tâm học liệu

a mod n
c mod n thì a

c mod n

/>

10
Nếu a

a1 mod n, b

b1 mod n thì a + b


(a1 + b1) mod n và a b

(a1 b1) mod n
Lớp tƣơng đƣơng:
Lớp tƣơng đƣơng của số nguyên a là tập hợp các số nguyên đồng dƣ với a
theo modulo n.
Cho n cố định đồng dƣ với n trong không gian các số nguyên vào các lớp
tƣơng đƣơng. Nếu a = qn + r, trong đó 0

r

r mod n. Vì vậy mỗi

n thì a

số nguyên a là đồng dƣ theo modulo n với duy nhất một số nguyên trong khoảng
từ 0 đến n

1 và đƣợc gọi là thặng dƣ nhỏ nhất của a theo modulo n. Cũng vì

vậy, a và r cùng thuộc một lớp tƣơng đƣơng. Do đó r có thể đơn giản đƣợc
sử dụng để thể hiện lớp tƣơng đƣơng.
1.1.4 Không gian Zn và Zn* [1], [2], [7]
Không gian Zn (các số nguyên theo modulo n)
Không gian các số nguyên theo modulo n: Zn là tập hợp các số nguyên
không âm nhỏ hơn n. Tức là Zn ={0, 1, 2, … n

1}. Tất cả các phép toán trong

Zn đều đƣợc thực hiện theo modulo n.

Thí dụ: Z10 ={0,1,2,3,.., 9}
Trong Z10: 6 + 7 = 3, bởi vì 6 + 7 = 13

3 (mod 10).

Không gian Zn*
Là tập hợp các số nguyên p
Tức là: Zn* = { p

Zn, nguyên tố cùng n.

Zn | gcd (n, p) = 1}, (n) là số phần tử của Zn*

Nếu n là một số nguyên tố thì: Zn* = { p

Zn | 1

p

n – 1}

Thí dụ: Z2 = {0, 1} thì Z2* = {1} vì gcd (1, 2) = 1.
1.1.5 Phần tử nghịch đảo [1], [2], [7]
Định nghĩa: Cho a
nguyên x

Zn sao cho a x

Zn. Nghịch đảo của a theo modulo n là số
1(mod n). Nếu x tồn tại thì đó là giá trị duy nhất, và


a đƣợc gọi là khả nghịch.

Số hóa bởi trung tâm học liệu

/>

11
Nghịch đảo của a ký hiệu là a 1.
Tính chất:
Cho a, b

Zn. Phép chia a cho b theo modulo n là tích của a và b theo

modulo n, và chỉ đƣợc xác định khi b có nghịch đảo theo modulo n.
Cho a

Zn, a là khả nghịch khi và chỉ khi gcd (a, n) = 1.

Giả sử d = gcd (a, n). Phƣơng trình đồng dƣ a x = b mod n có nghiệm x
nếu và chỉ nếu d chia hết cho b, trong trƣờng hợp các nghiệm d nằm trong
khoảng 0 đến n – 1 thì các nghiệm đồng dƣ theo modulo n/d.
Thí dụ: 4 1 = 7 (mod 9) vì 4 7
1.1.6 Hàm

1 (mod 9)

Euler [1], [2], [7]

Định nghĩa: Cho n


1. (n) đƣợc định nghĩa là các số nguyên trong khoảng

từ [1; n] nguyên tố cùng nhau với n. Hàm

đƣợc gọi là hàm phi Euler.

Tính chất:
 Nếu p là số nguyên tố thì (n) = p

1.

 Hàm phi Euler là hàm có tính nhân:
Nếu (m, n) = 1 thì (m n) = (m) (n).
 Nếu n = p1e1p2e2…pkek là thừa số nguyên tố của n thì:
(n) = n 1

1
p1

1

1
… 1
p2

1
pn

1.1.7 Các phép tốn trong khơng gian modulo [7]

Cho n là số nguyên dƣơng. Nhƣ trƣớc, các phần tử trong Zn là tập các số
nguyên {0, 1, 2,…, n
(a + b) mod n =

1}. Nhận xét rằng: nếu a, b

a b
if
a b n if

Zn thì:

a b n
a b n

Vì vậy, phép cộng modulo (và phép trừ modulo) có thể đƣợc thực
hiện mà không cần thực hiện các phép chia dài.

Số hóa bởi trung tâm học liệu

/>

12
Phép nhân modulo của a và b đƣợc thực hiện bằng phép nhân thông
thƣờng a với b nhƣ các số ngun bình thƣờng, sau đó lấy phần dƣ của
kết quả sau khi chia cho n.
Phép tính nghịch đảo trong Zn có thể đƣợc thực hiện nhờ thuật tốn Euclid
mở rộng
Bài tốn phát biểu nhƣ sau: Cho a


Zn, hãy tìm a 1 mod n nếu có.

Bƣớc đầu, dùng thuật tốn Euclid mở rộng sau để tìm các số nguyên x và
y sao cho:
a x + n y = d với d = gcd(a,n).
Nếu d > 1 thì a 1 mod n khơng tồn tại. Ngƣợc lại, return (x).
* Thuật tốn Euclid mở rộng(N={1,2,3,...,} là tập các số nguyên dương)

Algorithm Euclid
INPUT:

a, b

N+;

OUTPUT:

x, y

Z thoả:

ax + by = gcd(a, b)

Method
x:= 0 ;

y:= 1 ;

u:= 1 ;


v:= 0 ;

q:= a div b ; r:= a mod b ;
While r > 0 do
a:= b;

b:= r;

t:= u;

u:= x;

x:= t – q*x;

t:= v;

v:= y;

y:=

t-q*y;

end while;
return (x, y) ;
end.

1.1.8 Độ phức tạp tính tốn [1], [2]
Lý thuyết thuật tốn và các hàm tính đƣợc ra đời từ những năm 30 của thế
kỷ 20 đã đặt nền móng cho việc nghiên cứu các vấn đề “tính được”, “giải


Số hóa bởi trung tâm học liệu

/>

13
được” trong tốn học. Tuy nhiên từ cái “tính đƣợc” đến việc tính tốn thực tế là
một khoảng cách rất lớn. Có rất nhiều vấn đề đƣợc chứng minh là có thể “tính
đƣợc” nhƣng khơng tính đƣợc trong thực tế cho dù có sự hỗ trợ của máy tính.
Vào những năm 1960, lý thuyết độ phức tạp tính tốn đƣợc hình thành và phát
triển một cách nhanh chóng, cung cấp nhiều hiểu biết sâu sắc về bản chất
phức tạp của các thuật toán và các bài toán, từ những bài toán thuần túy lý
thuyết đến những bài toán thƣờng gặp trong thực tế.
Thuật toán: Một hệ thống chặt chẽ và rõ ràng các chỉ thị nhằm xác định
một dãy thao tác trên dữ liệu vào sao cho: Bất kể dữ liệu vào (input) nhƣ
thế nào, sau một số hữu hạn bƣớc thực hiện các thao tác đã chỉ ra, ta thu
đƣợc một kết quả (output) mong muốn.
Đặc trƣng của thuật tốn: Tính đơn nghĩa, tính dừng, tính đúng đắn, tính
phổ dụng, tính khả thi.
Các thức mơ tả thuật tốn: Ngơn ngữ tự nhiên, sơ đồ khối, mã giả
Thuật toán đơn định (deterministic): Với hai bộ dữ liệu vào giống nhau,
thuật toán đơn định sẽ thi hành các mã lệnh giống nhau và cho kết quả
giống nhau.
Thuật toán ngẫu nhiên (randomized): Với hai bộ dữ liệu vào giống nhau,
thuật toán ngẫu nhiên có thể thực hiện theo những mã lệnh khác nhau và
cho kết quả khác nhau.
Thuật toán và giải thuật khơng có sự phân biệt trong thuật ngữ tiếng Anh
(Algorithm). Nhƣng chúng ta có thể hiểu nhƣ sau:
 Thuật tốn: Cách thức giải quyết bài tốn (thuần túy trên mơ hình
tốn học)
 Giải thuật: Thuật tốn và cách thức cài đặt trên một cấu trúc dữ liệu

cụ thể
Thí dụ: Thuật tốn tìm kiếm nhị phân có thể cài đặt dễ dàng trên mảng

Số hóa bởi trung tâm học liệu

/>

14
nhƣng không cài đặt đƣợc trong danh sách nối đơn.
Đánh giá thuật tốn (giải thuật) = đánh giá mơ hình cài đặt thuật tốn đó
trên một cấu trúc dữ liệu cụ thể.
Đánh giá giải thuật: Là việc tìm cách đánh giá, ƣớc lƣợng nguồn tài
nguyên cần phải có khi thực hiện chƣơng trình cài đặt giải thuật đó.
Tài ngun: thời gian, bộ nhớ, số lƣợng bộ vi xử lý, tốc độ đƣờng truyền mạng…
Đánh giá chƣơng trình

Đánh giá giải thuật

Thực hiện sau khi cài đặt chƣơng trình Thực hiện trƣớc khi viết chƣơng trình
trên một máy cụ thể
Thử chạy với một vài bộ dữ liệu cụ thể, Nhằm xác định tính khả thi của giải
đo thời gian thực hiện, lƣợng bộ nhớ thuật, chọn thuật toán tốt nhất để cài đặt
chiếm dụng trong trƣờng hợp cụ thể

Có nhiều chỉ tiêu để đánh giá giải thuật nhƣng phổ biến nhất là đánh giá
thời gian thực hiện giải thuật.
Phân tích thời gian thực hiện giải thuật:
 Dữ liệu càng lớn

thời gian sử lý càng chậm.


 Dữ liệu kích thƣớc n

thời gian thực hiện T(n) là một hàm xác

định dƣơng.
 Thực hiện trên mơ hình máy tính trừu tƣợng.
 Độc lập với phần cứng cụ thể.
Độ phức tạp tính tốn:
Thời gian thực hiện một thuật toán phụ thuộc vào cỡ (size) của dữ liệu
vào:
Thí dụ:- Tìm một đối tƣợng có trong danh sách N phần tử hay không ?
- Sắp xếp một dãy số gồm N số.
- Bài toán ngƣời bán hàng cần thăm N địa điểm.
Trong các dữ liệu vào cùng một cỡ (N), thời gian chạy của thuật toán cũng
thay đổi:

Số hóa bởi trung tâm học liệu

/>

15
Thí dụ: Tìm xem một đối tƣợng có trong danh sách N phần tử hay không ?
- Đối tƣợng nằm ở đầu danh sách.
- Đối tƣợng nằm ở giữa danh sách.
- Đối tƣợng nằm ở cuối danh sách.
Biểu diễn thời gian chạy bởi kí hiệu O
Định nghĩa: Giả sử f(n) và g(n) là các hàm thực không âm của đối số
ngun khơng âm n. Ta nói „f(n) là Big O g(n)‟ và viết là: f(n) = O(g(n)) nếu tồn
tại các hằng số dƣơng c* và n0 sao cho f(n) ≤ c*g(n) với mọi n ≥ n0.


Thí dụ: Giả sử f(n) = 5n3 + 2n2 + 13n + 6 , ta có:
f(n) = 5n3 + 2n2 + 13n + 6 ≤ 5n3 + 2n3 + 13n3 + 6n3 = 26n3
f(n) = O(n3)
Tổng quát nên nếu f(n) là một đa thức bậc k của n:
f(n) = aknk + ak 1nk

1

+ … + a1n + a0 thì f(n) = (nk)

Bảng kí hiệu thời gian chạy:
Kí hiệu O lớn Tên gọi
hằng

O(1)
O(

)

logarit
tuyến tính

O(n)
O(n

)

O(n2)
3


n
bình phƣơng

O(n )

lập phƣơng

O(2n)

mũ

Số hóa bởi trung tâm học liệu

/>

16
Thời gian chạy của các lệnh
 Lệnh gán
X = <biểu thức>
Thời gian chạy của lệnh gán bằng thời gian thực hiện biểu thức.
 Lệnh lựa chọn
if(điều kiện)  T0(n)
lệnh 1 T1(n)
else
lệnh 2  T2(n)
Thời gian: T0(n) + max(T1(n) + T2(n))
 Lệnh lặp: for, while, do – while

Thí dụ:


với X(n) số vòng lặp.

Điều kiện lặp.

Thời gian thực hiện vòng lặp thứ i
1.1.9 Hàm một phía và hàm cửa sập một phía [1], [3], [6]
Hàm một phía:
Một hàm một phía là hàm mà dễ dàng tính tốn ra quan hệ một chiều nhƣng
rất khó để tính ngƣợc lại. Ví nhƣ: Biết giả thiết x thì có thể dễ dàng tính ra f(x),
nhƣng nếu biết f(x) thì rất khó tính ra đƣợc x. Trong trƣờng hợp này “khó” có nghĩa
là để tính ra đƣợc kết quả thì phải mất rất nhiều thời gian để tính tốn.
Thí dụ: Phân tích ra thừa số. Tính p q = n là dễ nhƣng nếu biết n tìm p và
q là “khó”.
Thí dụ: logarit rời rạc. Tính y = f(x) = αx mod p là dễ nhƣng tính ngƣợc
lại x = logα y là bài tốn “khó”
Hàm cửa sập một phía:
f(x) đƣợc gọi là hàm cửa sập một phía có nếu tính xi y = f (x) thì dễ

Số hóa bởi trung tâm học liệu

/>

17
nhƣng tính ngƣợc x = f 1(y) thì khó tuy nhiên nếu có “cửa sập” thì vấn đề tính
ngƣợc trở nên dễ dàng. Cửa sập ở đây là một điều kiện nào đó giúp chúng ta dễ
dàng tính ngƣợc.
Thí dụ:
y = f (x) = xb mod n tính xi thì dễ nhƣng tính ngƣợc x = ya mod n thì khó
vì phải biết a với a b


1 (mod ( (n)) trong đó (n) = (p 1)(q 1). Nhƣng nếu

biết cửa sập p, q thì việc tính n = p q và tính a trở nên dễ dàng.
Hộp thƣ là một thí dụ khác về hàm một phía có cửa sập. Bất kỳ ai cũng có
thể bỏ thƣ vào thùng. Bỏ thƣ vào thùng là một hành động công cộng. Mở thùng
thƣ khơng phải là hành động cơng cộng. Nó là khó khăn, bạn sẽ cần đến mỏ hàn
để phá hoặc những cơng cụ khác. Tuy nhiên, nếu bạn có “cửa sập” (trong trƣờng
hợp này là chìa khóa của hịm thƣ) thì cơng việc mở hịm thƣ thật dễ dàng.
1.2 Vấn đề mã hóa [3], [6], [7], [8]
1.2.1 Một số khái niệm cơ bản về mã hoá
Lịch sử của mật mã học đã có từ rất sớm, ban đầu con ngƣời cố gắng tìm
một cách để bảo vệ thơng tin, tránh việc thơng tin bị giải mã khi ngƣời khác có
đƣợc chúng. Các cách áp dụng đó thƣờng mang tính mẹo mực đơn giản và có
thể dễ dàng bị giải mã nếu thông tin về cách thức che giấu bị lộ hoặc bị suy
đoán. Mật mã học ban đầu đƣợc áp dụng nhiều trong lĩnh vực quân đội. Các
phƣơng pháp mã hóa cổ điển đã đƣợc áp dụng nhƣ Caesar, Playfair, ...
Các hệ mật mã cổ điển đƣợc sử dụng nhiều nhƣng dần dần chúng bộc lộ
một hạn chế lớn. Do các cách mã hóa đều dựa trên phƣơng pháp mã khóa bí
mật, khi gửi bản mã đi thì cần phải gửi kèm theo cả cách giải mã. Bên cạnh đó,
nếu cách mã hóa là quen thuộc hoặc đơn giản thì ngƣời có đƣợc thơng tin đã bị
mã hóa có thể tiến hành các cách để dị ra luật mã hóa để có đƣợc văn bản gốc.
Ngày nay cũng với sự trợ giúp của máy tính điện tử, các phƣơng pháp mã
hóa với khóa bí mật đƣợc sử dụng chung cho q trình mã hóa và giải mã (hay
cịn gọi là mã hóa cổ điển) có thể dễ dàng bị giải mã.

Số hóa bởi trung tâm học liệu

/>


18
Sự cần thiết phải có các phƣơng pháp mã hóa an toàn hơn đã đƣợc đáp
ứng bằng việc áp dụng các kết quả nghiên cứu của toán học. Sự thay đổi về
phƣơng pháp mã hóa cũng nhƣ độ an tồn của các hệ mã mới đã đƣa lịch sử của
mật mã học sang trang mới. Các hệ mật mã với khóa mã đối xứng đã góp phần
to lớn trong việc củng cố vai trò của mật mã học trong các ứng dụng của con
ngƣời. Đƣa mật mã đến với cả các ứng dụng trong cuộc sống đời thƣờng của
con ngƣời, mật mã khơng cịn chỉ đƣợc nhắc đến nhiều trong lĩnh vực quân sự.
Ứng của mật mã học đã trở thành một công cụ cần thiết cho mọi ngƣời, cần thiết
cho các hoạt động thƣờng ngày.
Các phƣơng pháp mã hóa khác nhau có những ƣu, nhƣợc điểm khác nhau.
Khi sử dụng các phƣơng pháp mã hóa, ngƣời dùng sẽ cân nhắc để lựa chọn
phƣơng pháp mã hóa thích hợp nhất đối với mình. Có thể lựa chọn mơi trƣờng
cần phải an toàn tuyệt đối bất kể thời gian và chi phí hoặc lựa chọn mơi trƣờng
lại cần giải pháp dung hịa giữa bảo mật và chi phí.
Các mơ hình mã hóa có chung một số thuật ngữ nhƣ sau:
Bản rõ: Là nội dung của thông điệp cần gửi đi và cần đƣợc bảo vệ an tồn.
Nó có thể là xâu các bít, các file văn bản, các file có cấu trúc.
Mã hố: Là q trình xử lý thơng điệp cần bảo mật trƣớc khi gửi đi.
Bản mã: Là kết quả thu đƣợc khi mã hóa bản rõ theo qui trình mã hóa của
phƣơng pháp đang đƣợc chọn.
Giải mã: Là quá trình xử lý ngƣợc, tiến hành giải mã bản mã để thu lại
bản rõ. Ví dụ: Mã hóa văn bản có nội dung là “ABC” với luật mã là tịnh
tiến vòng 1 đơn vị đối với mã ASCII của mỗi kí tự.
Vậy ta có:
Bản rõ: “ABC”
Mã hóa: Thực hiện mã hóa theo luật mã.
Biến đổi các kí tự thành các số theo mã ASCII của kí tự đó.

Số hóa bởi trung tâm học liệu


/>