ĐẠI HỌC QUỐC GIA HÀ NỘI
Trường Đại Học Công Nghệ

Luận văn thạc sỹ

VẤN ĐỀ XÁC THỰC TRÊN MẠNG TRUYỀN THÔNG
KHÔNG DÂY DỰA TRÊN HỆ MẬT ĐƯỜNG CONG
ELLIPTIC

Người trình bày: Phạm Văn Toàn
Cán bộ hướng dẫn: PGS.TS Trịnh Nhật Tiến

Hà Nội – 09/2006


MỤC LỤC
Danh mục các từ viết tắt...........................................................................................3
GIỚI THIỆU..............................................................................................................4
Chương 1 - CÁC KHÁI NIỆM CƠ BẢN................................................................5
1.1. Các khái niệm toán học...............................................................................................5
1.1.1. Số học của các số nguyên ....................................................................................5
1.1.2. Khái niệm đồng dư. .............................................................................................7
1.1.3. Thặng dư thu gọn và phần tử nguyên thủy. .........................................................9
1.1.4. Phương trình đồng dư bậc hai và thặng dư bậc hai............................................10
1.1.5.Khái niệm thuật toán xác suất.............................................................................14
1.1.6. Khái niệm độ phức tạp.......................................................................................17
1.1.7. Bài toán kiểm tra số nguyên tố ..........................................................................19
1.1.8. Bài tốn phân tích thành thừa số ngun tố.......................................................24
1.1.9. Bài tốn tính logarit rời rạc theo modulo...........................................................26
1.2. Vấn đề mã hóa. .........................................................................................................30
1.2.1. Hệ mã hóa đối xứng...........................................................................................30

1.2.2. Hệ mã hóa phi đối xứng (mã hóa khóa cơng khai). ...........................................35
1.3. Vấn đề ký số. ............................................................................................................41
1.3.1. Bài toán xác nhận và sơ đồ chữ ký. ...................................................................41
1.3.2. Sơ đồ chữ ký RSA. ............................................................................................43
1.3.3. Sơ đồ chữ ký ElGamal. ......................................................................................44
1.3.4. Chuẩn chữ ký số (Digital Signature Standard). .................................................49
1.3.5. Đại diện thông điệp............................................................................................51
1.3.6. Chữ ký không phủ định được và không chối bỏ được.......................................53

Chương 2 - VẤN ĐỀ XÁC THỰC ĐIỆN TỬ.......................................................55
2.1. Xác thực điện tử........................................................................................................55
2.1.1. Khái niệm xác thực. ...........................................................................................55
2.1.2. Khái niệm xác thực số (điện tử).........................................................................56
2.2. Công cụ xác thực: CHỨNG CHỈ SỐ........................................................................58
2.2.1. Khái niệm chứng chỉ số .....................................................................................58
2.2.2. Định dạng X.509 của chứng chỉ số....................................................................59
2.3. Hạ tầng cơ sở mật mã khóa cơng khai – PKI............................................................69
2.3.1. Khái niệm PKI ...................................................................................................69
2.3.3. Các chức năng quản lý của PKIX ......................................................................74
2.3.4. Các giao thức quản lý của PKIX........................................................................77
2.3.5. Các giao thức kiểm tra trạng thái của chứng chỉ số...........................................77

Chương 3 - XÁC THỰC TRÊN MẠNG TRUYỀN THÔNG .............................78
KHÔNG DÂY DỰA TRÊN HỆ MẬT ĐƯỜNG CONG ELLIPTIC .................78
3.1. Hệ mật đường cong elliptic.......................................................................................78
3.1.1. Đường cong elliptic. ..........................................................................................78
3.1.2. Hệ mã hóa trên đường cong Elliptic ..................................................................82
3.1.3. Sơ đồ chữ ký trên đường cong Elliptic ..............................................................83
3.2. Mạng truyền thơng khơng dây. .................................................................................86
3.2.1. u cầu về an tồn truyền tin. ...........................................................................86

3.2.2. Đặc điểm của mạng truyền thông không dây. ...................................................87
3.3. Các giao thức xác thực..............................................................................................88

1


3.3.1. Các giao thức xác thực phổ biến........................................................................88
3.3.2. Giao thức xác thực dựa trên ECC. .....................................................................92
3.4. Thử nghiệm ECC. ...................................................................................................101
3.4.1. Giới thiệu .........................................................................................................101
3.4.2. Kết quả thử nghiệm..........................................................................................102
3.4.3. Đánh giá, nhận xét ...........................................................................................103
3.4.4. Một số giao diện và mã nguồn chương trình thử nghiệm................................104

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

2


Danh mục các từ viết tắt

CA

Certification Authority

CRL

Certificate Revocation List


DSS

Digital Signature Standard

ECC

Elliptic Curve Cryptography

ECDSA

Elliptic Curve Digital Signate Argorithm

MSR

Modular Square Root

OCSP

Online Certificate Status Protocol

PKI

Public Key Infrastructure

PKIX

Public-Key Infrastructure X.509

RA


Registration Authority

3


GIỚI THIỆU
Trong những năm gần đây sự phát triển của cơng nghệ thơng tin, truyền
thơng nói chung và của Internet nói riêng đã mang lại cho con người nhiều lợi ích
vô cùng to lớn. Công nghệ thông tin đã, đang và sẽ là một trong những vấn đề có
tầm quan trọng rất lớn trong các hoạt động của xã hội lồi người.
Cũng như trong các phương thức trao đổi thơng tin truyền thống, việc trao
đổi, cung cấp thông tin điện tử trong nhiều lĩnh vực địi hỏi tính bí mật, tính tồn
vẹn, tính xác thực cũng như trách nhiệm của người gửi nhằm đảm bảo người gửi
thông tin không thể thối thác trách nhiệm về các thơng tin được trao đổi. Bên cạnh
đó tốc độ xử lý của máy tính ngày càng được nâng cao do đó với sự trợ giúp của các
máy tính tốc độ cao, khả năng tấn cơng các hệ thống thơng tin có độ bảo mật kém
rất dễ xảy ra.
Với mạng truyền thông không dây việc bảo đảm an tồn truyền tin cịn gặp
nhiều khó khăn do đặc thù riêng của nó. Chính vì thế người ta đã nghiên cứu và đưa
ra nhiều kỹ thuật, mô hình cho phép chúng ta áp dụng để đảm bảo an tồn. Trong số
các phương pháp kỹ thuật đó luận văn sẽ tập trung nghiên cứu việc áp dụng hệ mã
hóa đường cong elliptic, một hệ mã hóa đang được xem là hệ mã hóa an tồn; hiệu
quả nhất, vào mạng truyền thông không dây.
Luận văn được chia làm ba chương.
Chương 1: Các khái niệm cơ bản
Chương 2: Vấn đề xác thực điện tử
Chương 3: Xác thực trên mạng truyền thông không dây dựa trên hệ mật đường cong
Elliptic

4



Chương 1 - CÁC KHÁI NIỆM CƠ BẢN
1.1. CÁC KHÁI NIỆM TOÁN HỌC.
1.1.1. Số học của các số nguyên
Gọi Z là tập hợp các số nguyên, Z = {.....-2, -1, 0, 1, 2......}, và Z+ tập hợp số
nguyên không âm Z+ ={0, 1, 2......}. Phần này sẽ trình bày một số kiến thức về số
học của các số nguyên cần trong lý thuyết mật mã.
Tập hợp Z là đóng kín đối với các phép cộng, trừ và nhân nhưng không đóng
kín đối với phép chia: chia một số ngun cho một số nguyên không phải bao giờ
cũng được một số nguyên. Trong số học, tính chất chia hết là khi chia số nguyên a
cho số nguyên b được thương là số nguyên q (a = b.q) có một ý nghĩa đặc biệt. Khi
đó ta nói a chia hết cho b, b chia hết cho a, a là bội số của b, b là ước số của a, và ký
hiệu là b|a.
Với định nghĩa như vậy ta thấy rằng số 1 là ước của một số nguyên bất kỳ, số
không là bội của mọi số nguyên bất kỳ, mọi số nguyên a bất kỳ là ước số, đồng thời
là bội số của chính nó.
Cho hai số ngun bất kỳ a và b, b> 1. Thực hiện phép chia a cho b ta được hai số q
và r sao cho.
a= b.q +r, 0Số q được gọi là thương số của phép chia a cho b, ký hiệu a div b. Số r được
gọi là số dư của phép chia a cho b, ký hiệu là a mod b.
Số nguyên d được gọi là ước số chung của hai số nguyên a và b nếu d|a và
d|b. Số nguyên d được gọi là ước số chung lớn nhất của a và b nếu d>0, d là ước số
chung của a và b và mọi ước số chung của a và b đều là ước số của d. Ta ký hiệu ước
số chung lớn nhất của a và b là gcd(a, b).
Dễ thấy rằng với mọi số nguyên dương a ta có gcd(a, 0)=a. Trong toán học
người ta qui ước rằng gcd(0, 0) = 0.

5

Số nguyên a>1 được gọi là số nguyên tố, nếu a khơng có ước số nào ngồi 1
và chính a. Số a được gọi là hợp số nếu không phải là số nguyên tố. Các số 2, 3, 5, 7,
11.. là số nguyên tố; các số 4, 6, 8, 10, 12 là hợp số.
Hai số a và b được gọi là ngun tố với nhau nếu chúng khơng có ước chung
nào khác 1, tức là nếu gcd(a, b)=1.
Một số nguyên n>1 bất kỳ đều dược viết dưới dạng:
n= p1a . p 2a ...., p ka
1

2

k

Trong đó p 1 . p 2 ...., p k

là các số nguyên tố khác nhau, a1, a2...., ak là các

số mũ nguyên dương. Nếu không kể thứ tự các thừa số nguyên tố thì dạng biểu diễn
đó là duy nhất, ta gọi đó là dạng triển khai chính tắc của n.
Các số nguyên tố và các vấn đề về số nguyên tố có một vai trò quan trọng
trong số học và ứng dụng vào lý thuyết mật mã.
Số nguyên m được gọi là bội số chung của a và b nếu a|m và b|m.
Số m được gọi là bội số chung bé nhất của a và b, và được ký hiệu là lcm(a, b)
nếu m>0, m là bội số chung của a và b, và mọi bội số chung của a và b đều là bội
của m.
Với hai số nguyên dương a và b bất kỳ ta có quan hệ
lcm(a, b).gcd(a, b) = a.b
Nếu b>0 và b|a thì gcd(a, b)=b. Nếu a= bq +r thì gcd(a, b) = gcd(b, r).

Từ tính chất trên người ta đã xây dựng thuật tốn thực hiện việc tìm ước số
chung lớn nhất của hai số nguyên bất kỳ sau đây.
Thuật tốn Euclide
INPUT: hai số ngun khơng âm a và b, với a ≥b
OUTPUT: ước số chung lớn nhất của a và b
1. Trong khi còn b>0, thực hiện:
Đặt r:= a mod b; a:=b; b:=r
2. Cho kết quả (a)

6


Ta biết rằng nếu gcd(a, b) = d, thì phương trình bất định a.x + b.y = d có
nghiệm ngun (x, y). Một nghiệm nguyên (x, y) như vậy có thể tìm được bởi thuật
tốn Euclide mở rộng.
Thuật tốn Euclide mở rộng
INPUT: hai số nguyên không âm a và b với a≥b
OUTPUT: d=gcd (a, b) và hai số x, y sao cho a.x + b.y = d
1. Nếu b = 0 thì đặt d←a, x←1, y←0, và cho ra (d, x, y)
2. Đặt x2 =1, x1= 0, y2 =0, y1=1
3. Trong khi còn b >0 thực hiện:
q:=a div b; r:=a mod b; x:=x2 - qx1; y:=y2 – qy1;
q:=b; b:=r; x2:=x1; x1:=x; y2:=y1; y1:=y;
4. Đặt d:=a; x:=x2; y:=y2 và cho kết quả (d, x, y).
1.1.2. Khái niệm đồng dư.
Cho n là một số nguyên dương. Ta nói rằng hai số nguyên a và b đồng dư với
nhau theo modulo n, và viết a≡b (mod n), nếu n|a-b (tức cũng là nếu a-b chia hết cho
n, hay khi chia a và b cho n ta được cùng một số dư).
Quan hệ đồng dư (theo một modulo n) trên tập hợp các số ngun có tính
chất phản xạ, đối xứng và bắc cầu, tức là một quan hệ tương đương. Do đó tạo ra

một phân hoạch trên tất cả các tập hợp số nguyên Z thành ra các lớp tương đương:
hai số nguyên cùng thuộc một lớp tương đương khi và chỉ khi chúng cho cùng một
số dư nếu chia cho n. Mỗi lớp tương đương như vậy được đại diện bởi một số duy
nhất trong tập hợp Zn ={0, 1, 2, 3......n-1}, là số dư khi chia các số trong lớp đó cho
n.
Vì vậy, ta có thể đồng nhất Zn với tập hợp các các lớp tương đương các số
nguyên theo mod n.
Cho a ∈ Zn. Một số nguyên x ∈ Zn được gọi là nghịch đảo của a theo mod n,
nếu a.x ≡1 (mod n).
Nếu có số x như vậy thì ta nói a là khả nghịch, và ký hiệu là a-1 mod n.
Từ đó có thể suy ra rằng a là khả nghịch theo mod n khi và chỉ khi

7


gcd(a, n)=1, tức là khi a và n nguyên tố với nhau.
Ta định nghĩa phép chia trong Zn như sau:
a: b (mod n) = a.b-1 mod n. Phép chia chỉ thực hiện được khi b là khả nghịch
theo mod n.
Bây giờ ta xét các phương trình đồng dư tuyến tính.
Phương trình đồng dư tuyến tính có dạng:
a.x ≡ b(mod n),

(1)

trong đó a, b, n là các số nguyên, n>0, x là ẩn số. Phương trình đó có nghiệm khi và
chỉ khi d = gcd(a, n)|b, và khi đó có đúng d nghiệm theo mod n.
Thực vậy, đặt a’= a/d, b’= b/d, n’= n/d, ta thấy phương trình đồng dư (1)
tương đương với phương trình:
a’.x ≡ b’(mod n’)

Vì gcd (a’, n’) = 1, nên phương trình có một nghiệm theo mod n’.
X= x0 ≡ b’a’-1(mod n’).
Và do đó phương trình (1) có d nghiệm theo mod n là:
X= x0, x0+ n’, x0+ (d-1)n’ (mod n).
Tất cả d nghiệm đó khác nhau theo mod n, nhưng cùng đồng dư theo mod n’.
Bây giờ ta xét hệ thống các phương trình đồng dư tuyến tính. Một hệ như vậy có thể
đưa về dạng
x1a1 (mod n1)
x2a2 (mod n2)
..................

(2)

xkak (mod nk)
Ta ký hiệu n= n1.n2....nk, N = n/ni. Ta có định lý sau đây.
Định lý số dư trung quốc.
Giả sử các số nguyên n1, n2,...., nk là từng cặp số nguyên tố với nhau. Khi đó,
hệ phương trình đồng dư tuyến tính (2) có một nghiệm duy nhất theo mod n.
Nghiệm duy nhất nói trong Định lý số dư trung quốc được cho bởi biểu thức:

8


x = ∑ki=1 ai Ni Mi mod n,
trong đó Mi = Ni-1 mod ni (có Mi vì Ni và ni nguyên tố với nhau).
Nếu (n1, n2) = 1 thì cặp phương trình x ≡ a (mod n1) và x ≡ a (mod n2) có nghiệm
duy nhất x ≡ a (mod n) theo mod n với n = n1.n2.
1.1.3. Thặng dư thu gọn và phần tử nguyên thủy.
Tập Zn= {0, 1, 2,...., n-1} thường được gọi là các tập thặng dư đầy đủ theo
mod n, vì mọi số nguyên bất kỳ đều tìm thấy được trong Zn một số đồng dư với mình

(theo mod n).
Tập Zn là đóng đối với các phép cộng, trừ và nhân theo mod n, nhưng khơng
đóng đối với phép chia, vì phép chia cho a theo mod n chỉ thực hiện được khi a và n
nguyên tố với nhau.
Bây giờ ta xét tập Z n* = { a ∈ Zn: gcd(a, n) = 1}, tức Z n* là tập con của Zn bao
gồm các phần tử nguyên tố với n. Z n* được gọi là tập thặng dư thu gọn theo mod n.
Mọi số nguyên tố với n đều có thể tìm thấy trong Z n* một đại diện đồng dư với mình
theo mod n. Dễ thấy rằng nếu p là một số nguyên tố thì Z *p = {0, 1, 2,..., p-1}.
Tập Z n* lập thành một nhóm con đối với phép nhân của Zn, vì trong Z n* phép chia
theo mod n bao giờ cũng thực hiện được, Z n* được gọi là nhóm nhân của Zn.
Theo đại số học, ta gọi số các phần tử trong một nhóm là cấp của nhóm đó. Ta
ký hiệu Φ(n) là số các số nguyên dương bé hơn n và nguyên tố với n. Như vậy, nhóm
Z n* có cấp Φ(n), và nếu p là số nguyên tố thì nhóm Z *p có cấp p – 1.

Ta nói phần tử g € Z n* có cấp m, nếu m là số nguyên dương bé nhất sao cho
gm = 1 trong Z n* .
Người ta đã chứng minh được rằng: m |Φ(n). Vì vậy, với mọi b € Z n* ta ln
có bΦ(n) ≡ 1 mod n.
Nếu p là một số nguyên tố thì Φ(p) = p-1, vì vậy với mọi b € Z n* ta có:
bp-1 ≡ 1(mod p).

(3)

9


Nếu b có cấp p-1, tức p-1 là số mũ bé nhất thỏa mãn cơng thức (3), thì các phần tử b,
b2,.... bp-1 đều khác nhau và theo mod p, chúng lập thành Z *p .
Khi đó Z *p là một nhóm cyclic và b là phần tử sinh, hay phần tử nguyên thủy
của nhóm đó. Tức là các phần tử trong nhóm sẽ được xác định khi biết b.

Trong lý thuyết số người ta đã chứng minh được các tính chất sau đây của
phần tử nguyên thủy:
1. Với mọi số nguyên tố p, Z *p là nhóm cyclic, và có Φ(p-1) phần tử nguyên thủy.
2. Nếu p − 1 = p1α . p 2α ... p αs là khai triển chính tắc của p-1 và nếu
1

a

p −1
p1

2

s

≡ 1(mod p ),...., a

p −1
ps

≡ 1(mod p ) ,

thì a là phần tử nguyên thủy theo mod p (tức của Z *p )
3. Nếu g là phần tử nguyên thủy theo mod p, thì β = gi theo mod p với mọi i mà
gcd(i, p-1)=1, cũng là phần tử nguyên thủy theo mod p.
Ba tính chất đó là cơ sở giúp ta tìm được các phần tử nguyên thủy theo mod p,
với p là số ngun tố bất kỳ.
Ngồi ra cịn có một một số tính chất sau đây, được ứng dụng nhiều trong mật
mã học:
Định lý Fermat

Nếu p là số nguyên tố và gcd (a, p) = 1, thì ap-1 ≡ 1(mod p).
Định lý Euler
Nếu a ∈ Z n* , thì aΦ(n) ≡ 1(mod n). Nếu r ≡ s (modΦ(n)) thì ar ≡ as (mod n).
1.1.4. Phương trình đồng dư bậc hai và thặng dư bậc hai.
Ta xét phương trình đồng dư bậc hai có dạng đơn giản sau đây:
x2≡ a (mod n)
Trong đó n là số nguyên dương, a là số nguyên với gcd(a, n)= 1, và x là ẩn số.
Phương trình đó khơng phải bao giờ cũng có nghiệm, khi nó có nghiệm thì ta gọi a là
thặng dư bậc hai mod n. Ngược lại thì a gọi là một bất thặng dư bậc hai mod n.

10


Tập các số nguyên nguyên tố với n được phân hoạch thành hai tập con: Tập
Qn các thặng dư bậc hai mod n, và tập Qn các bất thặng dư bậc hai mod n.
Tiêu chuẩn Euler
Khi p là số nguyên tố, số a là thặng dư bậc 2 mod p nếu và chỉ nếu a(p-1)/2 ≡ 1
(mod p).
Chứng minh:
Giả sử có x sao cho x2 ≡ a (mod p), khi đó ta cũng có
a(p-1)/2 ≡ (x2)(p-1)/2 ≡ xp-1≡1 (mod p).
Ngược lại, giả sử a(p-1)/2 ≡1 (mod p). Khi đó a ∈ Z *p . Lấy b là một phần tử
nguyên thủy mod p, ắt có một số i nào đó sao cho a=bi mod p.
Từ đó, a(p-1)/2 ≡ bi(p-1)/2≡1 (mod p).
Phần tử b có cấp p-1, do đó (p-1) chia hết i(p-1)/2, i phải là số chẵn, i=2*j, và a có
căn bậc 2 là ± b j (mod p).
Ký hiệu Legendre
⎛a ⎞

Cho p là số nguyên tố lẻ. Với mọi a ≥ 0 ta định nghĩa ⎜ ⎟ như sau:

⎝ p⎠
⎧0, khi a ≡ 0(mod p);
⎛a ⎞ ⎪
⎜ ⎟ = ⎨1, khi a ∈ Q p ;
⎝ p⎠ ⎪
⎩−1, khi a ∉ Q p .

Chú ý:
⎛a ⎞

+ Từ định nghĩa suy ra ngay a là thặng dư bậc hai mod p khi và chỉ khi ⎜ ⎟ = 1.
⎝ p⎠
+ Theo tiêu chuẩn Euler nói trên, với mọi a ≥ 0, ta có:
⎛a ⎞
(p-1)/2
(mod p).
⎜ ⎟ ≡a
⎝ p⎠

11


Ký hiệu Jacobi
Bây giờ ta mở rộng ký hiệu Legendre để được ký hiệu Jacobi đối với mọi số
nguyên lẻ n ≥ 1 và mọi số nguyên a ≥ 0.
Giả sử a có khai triển chính tắc thành thừa số nguyên tố là n = p 1a1 .p a2 2 ....p ak
k thì
a

1

⎛a ⎞ ⎛a ⎞
⎜ ⎟= ⎜ p ⎟
⎝ p⎠ ⎝ 1⎠

a

2
⎛a ⎞
⎛a ⎞
⎜ ⎟ ....... ⎜ p ⎟
⎝ p2 ⎠
⎝ k⎠

ak

.

Khi n = p là số nguyên tố thì giá trị của các ký hiệu Legendre và Jacobi là như
nhau. Việc tính ký hiệu Legendre có thể phức tạp khi p rất lớn, trong khi việc tính ký
hiệu Jacobi có thể thuận lợi hơn do có thể sử dụng các tính chất 1-4 sau đây:
⎛m ⎞ ⎛m ⎞
1. Nếu m1≡ m2 mod n thì ⎜ 1 ⎟ = ⎜ 2 ⎟ .
⎝n ⎠ ⎝n ⎠
⎛ 2 ⎞ ⎧1, khi a ≡ ± 1 (mod 8)
.
2. ⎜ ⎟ = ⎨
⎝ n ⎠ ⎩−1, khi, a ≡ ± 3 (mod 8)
⎛ m .m ⎞ ⎛ m ⎞ ⎛ m ⎞
3. ⎜ 1 2 ⎟ = ⎜ 1 ⎟ .⎜ 2 ⎟ .
⎝ n ⎠ ⎝n ⎠ ⎝n ⎠

4. Nếu m và n đều là số lẻ, thì.
⎧ ⎛n ⎞
⎪− ⎜ ⎟ , khi m ≡ 3 mod 4 & n ≡ 3 mod 4
⎛ m⎞ ⎪ ⎝m⎠
⎜ ⎟=⎨
⎝ n ⎠ ⎪⎛ n ⎞
, khi m ≡ 1 mod 4 ∨ n ≡ 1 mod 4
⎪⎜⎝ m ⎟⎠
⎩

Bây giờ ta xét việc giải phương trình đồng dư bậc hai:
x2= a (mod n).

(4)

Trong một trường hợp đặc biệt khi n=p là số nguyên tố có dạng p = 4m+3, tức
là p đồng dư với 3 theo mod 4, và a là một số nguyên nguyên tố với p. Theo tiêu
chuẩn Euler ta biết phương trình (4) có nghiệm khi và chi khi a(p-1)/2 ≡ 1(mod p). Khi
đó ta có:
a

p −1
+1
2

≡ a (mod p),

a 2( m +1) ≡ a (mod p),

12


Do đó x ≡ ± am+1 (mod p) là hai nghiệm của phương trình (4).

13


1.1.5. Khái niệm thuật toán xác suất.
a. Khái niệm xác suất.
Ta xét tập hợp Ω={s1, s2,…, si}, được gọi là không gian sự kiện sơ cấp. Các
phần tử Ω, tức các sự kiện sơ cấp hay các mẫu, có thể được xem như các kết quả có
thể (và loại trừ lẫn nhau) của một thực nghiệm nào đó.
Một phân bố xác suất P trên Ω được định nghĩa là một tập các số thực khơng
âm P= {p1, p2,…, pn} có tổng

∑p

i

= 1 . Số pi được coi là xác suất của sự kiện sơ cấp si.

Tập con E ⊆ Ω được gọi là một sự kiện. Xác suất của sự kiện E được định
nghĩa là p(E) =

∑ p( s) .

Giả sử E là một sự kiện trong không gian xác suất Ω. Ta định nghĩa sự kiện bù
của E, ký hiệu E , là sự kiện gồm tất cả sự kiện sơ cấp trong không gian Ω không
thuộc E, ta có thể định nghĩa các sự kiện hợp E1 ∪ E2 và sự kiện giao E1 ∩ E2 của hai

sự kiện E1 và E2 bất kỳ.
Kết luận:
1) Giả sử E là một sự kiện. Khi đó 0 ≤ p(E) ≤ 1 và p( E ) = 1- P(E).
p(Ω) = 1 và p( φ ) = 0.
2) Giả sử E1 và E2 là hai sự kiện. Nếu E1 ⊆ E2 thì p(E1)≤ p(E2).
p(E1 ∪ E2) + p(E1 ∩ E2) = p(E1 ∪ E2).
p(E1 ∪ E2) = p(E1 ∩ E2) khi và chỉ khi E1 ∩ E2 = φ , tức là khi E1 và E2 là hai sự kiện
loại trừ lẫn nhau.
Cho E1 và E2 là hai sự kiện, với p(E2) > 0. Định nghĩa xác suất có điều kiện
của E1 khi có E2 là
p(E1/E2) =

p ( E1 ∩ E 2 )
p(E 2 )

Từ định nghĩa suy ra công thức Bayes:
p ( E1 / E 2 ) =

p ( E1 ). p ( E 2 / E1 )
p( E 2 )

14


Ta nói sự kiện E1 và E2 là độc lập và nếu p(E1 ∩ E2) = p(E1).p(E2). Khi đó ta cũng nói
p(E1/E2) = p(E1) và p(E2/E1) = p(E2)…
Giả sử Ω là không gian mẫu với mọi phân bố xác suất P. Ta gọi đại lượng
ngẫu nhiên ξ trên Ω là ánh xạ gán cho mỗi s ∈ Ω một số thực ξ(s). Hiển nhiên, nếu ξ
và η là các đại lương ngẫu nhiên trên Ω, thì ξ+η, ξ.η được định nghĩa là:
∀ s ∈ Ω: (ξ+η) (s) = ξ(s) + η(s), (ξ.η) (s) = ξ(s). η(s).

Cũng là đại lượng ngẫu nhiên trên Ω .
Giả sử ξ là đại lượng ngẫu nhiên trên khơng gian mẫu Ω . Điều đó có nghĩa là
với mọi s ∈ Ω , ξ lấy giá trị bằng ξ(s) với xác suất p(s). Định nghĩa giá trị kỳ vọng
(hay trung bình) của ξ là
E(ξ) =

∑ ξ (s). p(s)

s∈Ω

Phương sai của đại lượng ngẫu nhiên ξ có giá trị trung bình μ được định nghĩa
là Var (ξ) = E((ξ- μ )2).
Căn bậc hai không âm của Var (ξ) được gọi là độ lệch chuẩn của ξ.
b. Thuật toán xác suất
Khái niệm thuật toán mà ta thường hiểu là thuật tốn tất định, đó là một tiến
trình thực hiện phép toán trên dữ liệu đầu vào và cho kết quả đầu ra. Theo D.E
Knuth, thuật tốn có 5 thuộc tính cơ bản: tính hữu hạn - thuật tốn ln kết thúc sau
một số hữu hạn bước; tính xác định - mỗi bước của thuật toán phải xác định một
cách chính xác; tập hợp đầu vào, đầu ra của thuật tốn cũng được xác định rõ ràng;
tính hiệu quả - mọi phép toán trong thuật toán đều phải là cơ bản, có thể xác định
chính xác trong một thời gian xác định.
Thuật toán là khái niệm cơ bản đối với việc lập trình trên máy tính, và đã sử
dụng rất phổ biến. Tuy nhiên đối với nhiều bài toán trong thực tế, khơng phải bao giờ
cũng tìm được thuật tốn giải chúng với độ phức tạp tính tốn chấp nhận được. Vì
vậy, cùng với thuật tốn tất định, đối với một số bài toán ta sẽ xét thêm các thuật
tốn xác suất, đó là những thuật tốn mà cùng với những dữ liệu đầu vào ta bổ sung

15

thêm giá trị của một đại lượng ngẫu nhiên tương ứng nào đó, thường là các số ngẫu
nhiên.
Người ta chia các thuật toán xác suất thành hai loại: loại thuật toán Monte
Carlo và loại thuật toán Las Vegas.
Thuật toán Monte Carlo kết thúc với kết quả có hoặc khơng đối với một dữ
liệu đầu vào bất kỳ. Thuật toán Las Vegas tuy cũng kết thúc với mọi dữ liệu, nhưng
có thể kết thúc với mọi thơng báo khơng có trả lời có hoặc khơng.
Thuật tốn Monte Carlo được gọi là thiên về có nếu nó cho trả lời có và trả lời
đó chắc chắn là đúng, cịn nó trả lời là khơng thì trả lời đó có thể sai với mọi xác
suất ε nào đó.
Thuật tốn Monte Carlo được giọi là thiên về khơng nếu nó trả lời là khơng và
trả lời đó chắc chắn là đúng, cịn nếu trả lời là có thì trả lời đó có thể sai với mọi xác
suất ε nào đó.
Thuật tốn Las Vegas nếu nó kết thúc với trả lời có hoặc khơng, thì trả lời đó
chắc chắn đúng, và có thể kết thúc với thơng báo khơng có trả lời với mọi xác suất ε
nào đó.

16


1.1.6. Khái niệm độ phức tạp.
a. Khái niệm độ phức tạp
Độ phức tạp tính tốn (về khơng gian hay thời gian) của một tiến trình tính
tốn là số ơ nhớ được dùng hay số phép toán sơ cấp được thực hiện trong tiến trình
tính tốn đó. Độ phức tạp tính toán của thuật toán A được hiểu là một hàm số fA(n)
sao cho với mỗi số n, fA(n) là số ô nhớ hay số phép toán sơ cấp tối đa mà A cần để
thực hiện tiến trình tính tốn của mình trên dữ liệu vào có độ dài ≤ n.
Độ phức tạp đa thức, độ phức tạp hàm mũ
Thuật toán A có độ phức tạp thời gian đa thức nếu có một đa thức P(n) sao

cho với mọi n đủ lớn ta có fA(n) ≤ P(n). Trong đó fA(n) là độ phức tạp theo thời gian
của thuật toán A.
Thuật toán A có độ phức tạp thời gian hàm mũ nếu có một hàm mũ P(n) sao
cho với mọi n đủ lớn ta có fA(n) ≤ P(n).
Bài tốn dễ, bài tốn khó
Bài tốn được gọi là “dễ” nếu độ phức tạp thời gian giải bài tốn đó là đa
thức.
Bài tốn được gọi là “khó” nếu độ phức tạp thời gian giải bài tốn đó là hàm
mũ.
Khái niệm độ phức tạp thuật toán cung cấp cho ta một cách tiếp cận mới đối
với vấn đề an tồn thơng tin. Dù ngày nay có những máy tính điện tử có tốc độ tính
tốn rất lớn, cỡ hàng tỷ phép tính/giây, nhưng với những thuật tốn có độ phức tạp
tính tốn cỡ f(n) = 2n, thì ngay với những dữ liệu có độ dài khoảng n = 1000, việc
thực hiện các thuật toán đã khơng thể xem là khả thi, do địi hỏi thực hiện khoảng
10300 phép tính. Một giải pháp mật mã có thể xem là có độ bảo mật cao, nếu để giải
mã cần phải thực hiện một tiến trình tính tốn có độ phức tạp rất lớn. Do đó, việc
phát hiện và sử dụng các hàm số có độ phức tạp tính tốn rất lớn có ý nghĩa hết sức
quan trọng đối với việc xây dựng các giải pháp về mật mã và an tồn thơng tin.

17


b. Khái niệm hàm một phía
Hàm số y=f(x) được gọi là hàm một phía (one-way function), nếu biết x thì
việc tính y là “dễ”, nhưng nếu tính ngược, tức biết y tìm ra x là rất “khó”.
Hàm y=f(x) được gọi là hàm cửa sập một phía (trapdoor one-way function),
nếu biết x tính ra y là “dễ”, cịn việc tính ngược từ y tìm lại x là rất “khó”, nhưng nếu
có một yếu tố trợ giúp z nào đó thì việc tính x từ y và z lại trở thành dễ. Khi đó ta gọi
z là “cửa sập” của hàm y=f(x).

18


1.1.7. Bài toán kiểm tra số nguyên tố
Cho n là một số nguyên bất kỳ. Làm thế nào để có thể biết n có là số ngun
tố hay khơng?. Bằng những phương pháp đơn giản như phương pháp sàng
Euratosthène, từ rất sớm người ta đã xây dựng được các bảng số nguyên tố đầu tiên,
rồi tiếp tục bằng nhiều phương pháp khác tìm thêm được nhiều số nguyên tố lớn.
Tuy nhiên chỉ đến giai đoạn hiện nay của lý thuyết mật mã hiện đại, nhu cầu sử dụng
các nguyên tố và thử tính nguyên tố của các số mới trở thành một nhu cầu to lớn và
phổ biến, đòi hỏi nhiều phương pháp mới có hiệu quả hơn.
Một số tính chất của các số nguyên tố và hợp số:
a. Tiêu chuẩn Euler-Solovay-Strassen:
Tiêu chuẩn:
i) Nếu n là số nguyên tố, thì với mọi số nguyên dương a ≤ n-1:
⎛ a ⎞ (n-1)/2
mod n.
⎜ ⎟ ≡a
⎝n⎠

ii) Nếu n là hợp số, thì
⎧
⎫ n −1
⎛a⎞
(n-1)/2
mod n ⎬ ≤
.
⎨a :1 ≤ a ≤ n − 1, ⎜ ⎟ ≡ a
2
⎝n⎠

⎩
⎭

Thuật toán Euler-Solovay-Strassen:
Dữ liệu vào: số nguyên dương n và t số ngẫu nhiên a1,..., at
(1 ≤ ai ≤ n − 1 ),
1. for i: = 1 to t do
⎛a ⎞

2. if ⎜ i ⎟ ≡ a i( n −1) / 2 mod n, then
⎝n ⎠
3. answer “n là số nguyên tố”
4. else
5. answer “n là hợp số ” and quit
Thuật toán này nếu cho trả lời “n là hợp số ” thì đúng n là hợp số, nhưng nếu
nó cho trả lời “n là số ngun tố ” thì trả lời đó có thể sai với một xác suất MonteCarlo thiên về có nếu xem nó là thuật tốn thử tính là hợp số; cịn nó là một thuật

19


tốn xác suất thiên về khơng nếu xem nó là thuật tốn thử tính ngun tố của các số
ngun
b. Tiêu chuẩn Solovay-Strassen-Lehmann:
Tiêu chuẩn:
i) Nếu n là số nguyên tố, thì với mọi số nguyên dương a ≤ n-1:
a(n-1)/2 ≡ ± 1(mod n).
ii) Nếu n là hợp số, thì

{a :1 ≤ a ≤ n − 1, a

( n −1) / 2

≡ ± 1mod n} ≤

n −1
.
2

Thuật toán Solovay-Strassen-Lehmann:
Dữ liệu vào: số nguyên dương n và t số ngẫu nhiên a1,..., at
(1 ≤ ai ≤ n − 1 ),
1. for i: = 1 to t do
2. if a(n-1)/2 ≡ ± 1(mod n) then
3. answer “n là số nguyên tố”
4. else
5. answer “n là hợp số ” and quit
c.Tiêu chuẩn Miler-Rabin:
Tiêu chuẩn:
i) Cho n là số nguyên lẻ, ta viết n-1 =2e.u, với u là số lẻ. Nếu n là số nguyên
tố thì với mọi số nguyên dương a ≤ n-1:
(au ≡ 1mod n) ∨ ∃ k < e(a2

k

.u

≡ -1mod n ).

ii) Nếu n là hợp số, thì

{a : 1 ≤ a ≤ n − 1, (a

u

k

}

≡ 1 mod n) ∨ ∃k < e(a 2 .u ≡ −1 mod n) ≤

n −1
2

20


Thuật toán Miler-Rabin:
Dữ liệu vào: số nguyên dương n và t số ngẫu nhiên a1,..., at
(1 ≤ ai ≤ n − 1 ),
1. for i: = 1 to t do
2. if (au ≡ 1mod n) ∨ ∃ k < e(a2

k

.u

≡ -1mod n ) then

3. answer “n là số nguyên tố”
4. else answer “n là hợp số ” and quit

Trong đó u và e được xác định bởi:n-1=2e.u, u là số lẻ.
Các tiêu chuẩn kể trên là cơ sở để xây dựng các thuật tốn xác suất kiểu
Monte-Carlo thử tính ngun tố (hay hợp số) của các số nguyên.
Xác suất sai lầm ε khi nhận được kết quả “n là số ngun tố ” trong các thuật
tốn đó được tính như sau: Giả sử n là một số lẻ trong khoảng N và 2N, tức
1Nquả trả lời n là số nguyên tố ”. Ta phải tính xác suất ε= p(A|B). Theo tính chất b) của
tiêu chuẩn Euler-Solovay-Strassen, nếu n là hợp số, thì sự kiện
⎛a⎞
(n-1)/2
mod n
⎜ ⎟≡ a
⎝n⎠

đối với mỗi a ngẫu nhiên (1 ≤ a ≤ n − 1 ) có xác suất ≤ 1/2, vì vậy ta có
p(B/A) ≤

1
.
2t

Theo cơng thức Bayes ta có
p(B/A) =

p ( A / B). p ( A)
p( B / A). p( A)
=
.
p( B)

p( B / A). p( A). p( B / A). p( A)

Theo định lý về số nguyên tố, số các số nguyên tố giữa N và 2N xấp xỉ
số các số lẻ là

n
N
≈
,
ln N ln n

N n
2
2
, và p( A ) ≈ 1. Dĩ nhiên ta có
≈ , do đó p( A ) ≈
2 2
ln n
ln n

p( B / A) = 1 . Thay các giá tri đó vào cơng thức trên, ta được:

21


2 −t (1 −

p( A / B) ≤

2 −t (1 −

2
)
ln n

2
2
)+
ln n ln n

=

ln n − 2
. (5)
ln n − 2 + 2 t +1

Đánh giá đó cũng đúng đối với thuật tốn Solovay-Strassen-lehmann, cịn đối với
thuật tốn Miler-Rabin thì ta được một đánh giá tốt hơn, cụ thể là
p( A / B) =

ln n − 2
.
ln n − 2 + 2 t +1

Khi t = 50 thì đại lượng ở vế phải của (5) ≈ 10-13, và vế phải của (6) ≈ 10-28; do đó nếu
chọn cho dữ liệu vào năm mươi số ngẫu nhiên ai thì các thuật toán Euler -SolovayStrassen và Solovay-Strassen-lehmann sẽ thử cho ta một số nguyên tố với xác suất
sai lầm ≤ 10-13 và thuật toán Miler-Rabin với xác suất sai lầm là ≤ 10-28.
Độ phức tạp tính tốn về thời gian của các thuật toán xác suất kể trên vào cỡ
đa thức logn tức là đa thức của độ dài biểu diễn của dữ liệu vào (là số n), tuy nhiên
các thuật tốn đó chỉ cho ta tính thử ngun tố của một số với một xác suất sai lầm ε

nào đó, dù ε là rất bé. Trong nhiều ứng dụng ta muốn có được một số nguyên tố với
độ chắc chắn 100% là số nguyên tố. Khi đó ta có thể dùng các thuật tốn xác suất
như trên và sau đó tìm kiếm những thuật tốn tất định để thử tính nguyên tố với độ
chính xác tuyệt đối. Adleman, Pomerance và Rumely đã đề xuất một số thuật toán
kiểu như vậy trong đó nổi bật là thuật tốn thử tổng Jacobi, sau đó được đơn giản hóa
bởi Cohen và Lenstra. Gold Wasser, Kilian, Adleman và Hoang đề xuất thuật toán
thử bằng đường cong Elliptic, và được tiếp tục hoàn thiện bởi Atkin và Morain. Các
thuật toán này đã được dùng để tìm nhiều số ngun tố rất lớn.
Các nhà tốn học Ấn độ Agrawal, Kayal và Saxena đã đưa ra một thuật tốn
tất định mới thử tính ngun tố có độ phức tạp tính tốn thời gian đa thức khá đơn
giản.
d.Thuật toán Agrawal - Kayal – Saxena:
Input: integer n>1
1. If (n is of the form ab, b>1) output COMPOSITE1;
2. r:=2;

22


3. While (r
{

4.

if (gcd(n, r) ≠ 1) output COMPOSITE;

5.

if (r is prime)

6.

let q be the largest prime factor of r-1;
if (q ≥ 4 r log n) and ( n

7.
8.

≠ 1(mod r))

break;

9.
10.

r −1
q

r:=r+1;

}

11. for a:=1 to 2 r log n
12. if (x-a)n ≠ (xn-a)(mod xr-1, n)) output COMPOSITE;
13. output PRIME;
Thuật toán này đã được một số nhà toán học kiểm nghiệm, đánh giá cao và
xem là một thuật tốn tốt, có thể dùng cho việc kiểm thử tính nguyên tố của các số
nguyên.
Trong thực tiễn xây dựng các giải pháp mật mã nhu cầu về các số nguyên tố

rất lớn. Để tìm được các số như vậy, người ta thường chọn ngẫu nhiên một số rất lớn,
rồi dùng trước cho nó một thuật toán xác suất, chẳng hạn như thuật toán MillerRabin; nếu như thuật toán cho ta kết quả “là số nguyên tố” với một xác suất sai ε
nào đó thì sau đó ta dùng tiếp một thuật tốn tất định (chẳng hạn như thuật toán
Agrawal - Kayal – Saxena) để đảm bảo chắc chắn 100% rằng số đó là nguyên tố.
Thuật toán Agrawal - Kayal - Saxena được chứng tỏ là có độ phức tạp thời gian đa
thức cỡ O((log n)12) khi thử trên số n; và nếu số nguyên tố được thử có dạng Sophie
Gerrmain, tức dạng 2p+1, thì độ phức tạp thời gian sẽ chỉ cỡ O((log n)6).

23


1.1.8. Bài tốn phân tích thành thừa số ngun tố.
Bài tốn phân tích một số ngun thành thừa số ngun tố cũng được xem là
bài tốn khó, thường được sử dụng trong lý thuyết mật mã. Biết một số n là hợp số
thì việc phân tích n thành thừa số mới là có nghĩa; do đó khi giải bài tốn phân tích n
thành thừa số, ta thử trước n có phải là hợp số hay khơng. Bài tốn phân tích n thành
thừa số có thể dẫn về bài tốn tìm một ước số của n. Vì khi biết một ước số d của n
thì tiến trình phân tích n được tiếp tục thực hiện bằng cách phân tích d và n/d.
Bài tốn phân tích thành thừa số, hay bài tốn tìm ước số của một số nguyên
cho trước, đã được nghiên cứu nhiều, nhưng cũng chưa có một thuật tốn hiệu quả
nào để giải nó trong trường hợp tổng quát. Do đó người ta có khuynh hướng tìm
thuật tốn giải nó trong những trường hợp đặc biệt, chẳng hạn khi n có một ước số
nguyên tố p với p-1 là B-mịn. Một số nguyên n được gọi là B-mịn nếu tất cả các ước
số nguyên tố của nó đều ≤ B) với một cận B>0 nào đó, hoặc khi n là số Blum (tức là
số có dạng tích của 2 số nguyên tố lớn nào đó n=p.q).
a. Trường hợp n là số B-mịn:
Giả sử n là B-mịn. Ký hiệu Q là bội chung bé nhất của tất cả các lũy thừa của
các số nguyên tố ≤ B mà bản thân chúng ≤ n.
⎢ ln n ⎥

Nếu ql ≤ n thì lln(q) ≤ ln n, tức l ≤ ⎢
⎥ ( ⎣x ⎦ là số nguyên bé nhất lớn hơn x).
⎣ ln q ⎦
Ta có
Q= ∏ q ⎣ln n / ln q ⎦ ,
q≤ B

Trong đó tích lấy theo tất cả các số nguyên tố khác nhau q ≤ B. Nếu p là một
thừa số nguyên tố của n sao cho p-1 là B-mịn, thì p-1 Q , và do đó với mọi a bất kỳ
thõa mãn gcd(a, p) =1, theo định lý Fermat ta có aQ ≡ 1 (mod p). Vì vậy, nếu lấy
d=gcd(aQ-1, n) thì p d . Nếu d=n thì coi như thuật tốn khơng cho ta điều mong
muốn, tuy nhiên điều đó chắc khơng xảy ra nếu n có ít nhất hai thừa số ngun tố
khác nhau. Từ những lập luận đó ta có:
(p-1) - thuật tốn Pollard phân tích thành thừa số:

24