ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ LAN ANH

Nghiên cứu độ an toàn của sơ đồ ch ký s

luận văn thạc sĩ CễNG NGH THễNG TIN

Hà néi - 2006


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ LAN ANH

Nghiên cứu độ an toàn của sơ đồ ch ký s

Mó s

: 1.01.10

luận văn thạc sĩ CễNG NGH THƠNG TIN

Người hướng dẫn khoa học: PGS.TS. Trịnh Nhật Tiến

Hµ néi - 2006


LỜI GIỚI THIỆU

Con ngƣời ln có nhu cầu trao đổi thơng tin với nhau. Nhu cầu đó tăng cao
khi các công nghệ mới ra đời đáp ứng cho việc trao đổi thông tin ngày càng nhanh.
Chúng ta vẫn không quên việc chiếc máy điện thoại ra đời đã là bƣớc tiến vƣợt bậc
trong việc rút ngắn khoảng cách đáng kể cả về thời gian và không gian giữa hai bên
muốn trao đổi thơng tin. Những bức thƣ hay điện tín đƣợc gửi đi nhanh hơn khi các
phƣơng tiện truyền thông phát triển. Đặc biệt hơn là từ khi Internet xuất hiện, dƣờng
nhƣ yêu cầu trao đổi thông tin của chúng ta đƣợc đáp ứng ngay khi ấn phím “send”.
Sẽ cịn rất nhiều tiện ích mà các cơng nghệ mới đã đem lại cho chúng ta trong mọi
lĩnh vực Kinh tế- Văn hố-Giáo dục-Y tế...
Ích lợi của Internet mang lại đối với xã hội là vô cùng, nhƣng cũng không thể
không kể đến những mặt trái của nó khi con ngƣời sử dụng nó với mục đích khơng
tốt. Vì vậy mà đối với những thông tin quan trọng khi truyền trên mạng nhƣ những
bản hợp đồng ký kết, các văn kiện mang tính bảo mật... thì vấn đề quan tâm nhất đó là
có truyền đƣợc an tồn hay khơng?
Do vậy để chống lại sự tấn cơng hay giả mạo, thì nảy sinh yêu cầu là cần phải
làm thế nào cho văn bản khi đƣợc gửi đi sẽ “khơng đƣợc nhìn thấy”, hoặc khơng thể
giả mạo văn bản, dù có xâm nhập đƣợc vào văn bản. Nhu cầu đó ngày nay đã đƣợc
đáp ứng khi cơng nghệ mã hố và chữ ký số ra đời. Với cơng nghệ này, thì đã trợ giúp
con ngƣời giải quyết đƣợc bài toán nan giải về bảo mật khi trao đổi thông tin.
Cùng với sự phát triển của mật mã khố cơng khai, ngƣời ta đã nghiên cứu và
đƣa ra nhiều phƣơng pháp, nhiều kỹ thuật ký bằng chữ ký số ứng dụng trong các hoạt
động kinh tế, xã hội. Chẳng hạn nhƣ các ứng dụng trong thƣơng mại điện tử, các giao
dịch của các chủ tài khoản trong ngân hàng, các ứng dụng trong chính phủ điện tử,
địi hỏi việc xác nhận danh tính phải đƣợc đảm bảo.

1


Chính vì vậy, việc nghiên cứu các vấn đề về an tồn thơng tin nói chung và các
phƣơng pháp ký số nói riêng, có vai trị khá quan trọng, là nền tảng cho việc phát triển

các ứng dụng trong thực tiễn. Ngày nay chữ ký số đƣợc sử dụng trong nhiều lĩnh vực
nhƣ trong kinh tế với việc trao đổi các hợp đồng giữa các đối tác kinh doanh; trong xã
hội là các cuộc bỏ phiếu kín khi tiến hành bầu cử từ xa, hay trong các cuộc thi phạm
vi rộng lớn.
Một số chữ ký đã đƣợc xây dựng là: chữ ký RSA, chữ ký ELGAMAL, chữ ký
DSS, chữ ký RABIN... Mặc dù các chữ ký số còn nhiều hạn chế nhƣ là về kích thƣớc
chữ ký, hay khả năng chống giả mạo chƣa cao... nhƣng những khả năng mà nó đem
lại là rất hữu ích.
RSA (Rivest-Shamir-Adleman): năm 1977, R.l. Rivest, A. Shamir và L.M.
Adleman đề xuất một hệ mật mã khố cơng khai mà độ an tồn của hệ dựa vào bài
tốn khó “phân tích số ngun thành thừa số nguyên tố”, hệ này trở thành một hệ nổi
tiếng và mang tên là hệ RSA.
ELGAMAL: hệ mật mã ElGamal đƣợc T. ElGamal đề xuất năm 1985, độ an
toàn của hệ dựa vào độ phức tạp của bài tốn tính logarit rời rạc.
DSS (Digital Signature Standard) đƣợc đề xuất từ năm 1991 và đƣợc chấp
nhận vào cuối năm 1994 để sử dụng trong một số lĩnh vực giao dịch điện tử tại Hoa
Kỳ. DSS dựa vào sơ đồ chữ ký ElGamal với một vài sửa đổi.
RABIN: hệ mật mã khoá công khai đƣợc M.O. Rabin đề xuất năm 1977, độ an
tồn của hệ dựa vào bài tốn khó “phân tích số nguyên thành thừa số nguyên tố”.
Một trong những điều mà chúng ta cần quan tâm đối với chữ ký số là độ an
tồn của sơ đồ chữ ký. Đó cũng là vấn đề chính đƣợc nghiên cứu trong luận văn
“Nghiên cứu độ an toàn của sơ đồ chữ ký số”. Nội dung chính của luận văn này bao
gồm 2 chƣơng:
Chƣơng1: Tổng quan về an tồn, bảo mật thơng tin.
Chƣơng 2: Độ an toàn của sơ đồ chữ ký số.
2


Chƣơng 1: TỔNG QUAN VỀ AN TỒN, BẢO MẬT THƠNG TIN
1.1. VẤN ĐỀ AN TỒN BẢO MẬT THƠNG TIN.

Ngày nay Internet cùng với các dịch vụ phong phú của nó có khả năng cung
cấp cho con ngƣời các phƣơng tiện hết sức thuận tiện để trao đổi, tổ chức, tìm kiếm và
cung cấp thông tin. Tuy nhiên, cũng nhƣ trong các phƣơng thức 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 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 đó cùng 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. Chính vì vậy ngƣời ta khơng ngừng nghiên cứu các vấn đề bảo mật và
an tồn thơng tin để đảm bảo cho các hệ thống thông tin hoạt động an toàn. Cho đến
ngày nay, với sự phát triển của cơng nghệ mã hố phi đối xứng, ngƣời ta đã nghiên
cứu và đƣa ra nhiều kỹ thuật, nhiều mô hình cho phép chúng ta áp dụng xây dựng các
ứng dụng địi hỏi tính an tồn thơng tin cao.
Trong văn bản pháp luật của Quốc hội mới ban hành đã công nhận luật giao
dịch điện tử – Ngày 29/11/2005, Quốc hội đã thông qua luật giao dịch điện tử
51/2005/QH11. Phạm vi điều chỉnh chủ yếu là giao dịch điện tử trong hoạt động của
các cơ quan nhà nƣớc, trong lĩnh vực dân sự, kinh doanh, thƣơng mại… Luật công
nhận và bảo vệ hợp đồng điện tử. Trong giao kết và thực hiện giao dịch điện tử, thông
báo dƣới dạng thông điệp “số” có giá trị pháp lý nhƣ thơng báo truyền thống.
Nhà nƣớc công nhận giá trị pháp lý của chữ ký điện tử và chứng thƣ điện tử
nƣớc ngoài, nếu nhƣ chữ ký điện tử hoặc chứng thƣ điện tử đó có độ tin cậy tƣơng
đƣơng với độ tin cậy của chữ ký điện tử hoặc chứng thƣ điện tử theo qui định của
pháp luật. Việc xác định mức độ tin cậy của chữ ký điện tử và chứng thƣ điện tử nƣớc

3


ngoài phải căn cứ vào các tiêu chuẩn quốc tế đã thừa nhận, điều ƣớc của nƣớc Cộng
hoà xã hội chủ nghĩa Việt Nam là thành viên và các yếu tố có liên quan khác.
Vấn đề đặt ra ở đây là việc bảo đảm an ninh, an toàn trong giao dịch điện tử đối
với các bên tham gia giao dịch điện tử. Và việc nghiên cứu độ an toàn của chữ ký điện

tử là rất cần thiết cho việc bảo đảm an ninh, an toàn trong giao dịch điện tử.

4


1.2. CƠ SỞ TỐN HỌC TRONG AN TỒN BẢO MẬT THÔNG TIN.
1.2.1. Số học của các số nguyên.
+

Ta ký hiệu Z là tập hợp các số nguyên, Z = ... –2, -1, 0, 1, 2....., và tập Z tập
+

hợp số nguyên không âm Z = 0, 1, 2...... Trong mục này sẽ nhắc lại một số kiến
thức về số học của các số nguyên cần cho việc trình bày lý thuyết mật mã.
1). Tính chia hết của các số nguyên.
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ố nguyên 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, tức khi chia số nguyên a
cho số nguyên b đƣợc thƣơng là số nguyên q (a = b.q) có ý 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
b│a.
Với định nghĩa nhƣ trên ta thấy rằng số 1 là ƣớc của số nguyên bất kỳ, số 0 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,

0

Số 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 tốn học ngƣời ta
qui ƣớc 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 nó. Số a đƣợc gọi là hợp số nếu không phải là số nguyên tố. Thí dụ 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à nguyên tố cùng 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 đƣợc viết dƣới dạng:
a a
ak
n = p1 1.p2 2 .....pk
Trong đó p1, p2, ...., pk là các số nguyên tố khác nhau, a1, a2, ..., ak là các số 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ố ngun tố có 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 số
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
Ta thấy rằng, nếu b>0 và b│a thì gcd(a, b) = b và nếu a = bq + r thì
gcd(a, b) = gcd(b, r).
Từ tính chất đó 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ố ngun bất kỳ.
Thuật tốn Euclide tìm ƣớc số chung lớn nhất:
INPUT: hai số nguyên 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 ra 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), và một nghiệm nguyên nhƣ vậy có thể tìm đƣợc bởi thuật tốn
Euclide mở rộng nhƣ sau:
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:
3.1. q  a div b, r  a mod b, x  x2-qx1, y  y2-qy1
3.2. q  b, b  r, x2  x1, x1  x, y2  y1, và y1  y
4. Đặt d  a, x  x2, y  y2, và cho ra kết quả (d, x, y).
2). Phƣơng trình đồng dƣ tuyến tính.
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 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 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.
Khi đó, nó tạo ra một phân hoạch trên tập hợp số nguyên Z, thành 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 một số duy nhất trong tập hợp
Zn = 0, 1, 2,..., 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 lớp tƣơng đƣơng các số nguyên theo mod n.

7


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(modn).
Nếu có số x nhƣ vậy thì ta nói a là khả nghịch, và ký hiệu là a mod n.
Từ định nghĩa ta có thể suy ra rằng a là khả nghịch theo mod n khi và chỉ khi
gcd(a, n) = 1, tức là khi a và n nguyên tố với nhau.
-1

Định nghĩa phép chia trong Zn nhƣ sau: a:b (mod n) = a.b mod n.
Phép chia chỉ thực hiện đƣợc khi b khả nghịch theo mod n.
Phƣơng trình đồng dƣ tuyến tính có dạng
a.x  b(mod n),

(1.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 đó nó có đúng
d nghiệm theo mod n.
Thật vậy, đặt a‟ = a/d, b‟ = b/d, n‟ = n/d ta thấy phƣơng trình đồng dƣ (1.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 này có một nghiệm theo mod n‟:
-1

x = x0  b‟.a‟ (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ƣ với nhau theo mod n‟.
Hệ phƣơng trình đồng dƣ tuyến tính có dạng:
x1  a1 (mod n1)
x2  a2 (mod n2)
........................

(1.2)

8


xk  ak (mod nk)

3). Thặng dƣ thu gọn và phần tử nguyên thuỷ.
Tập Zn = 0, 1, 2,..., n-1 đƣợc gọi là tập các thặng dƣ đầy đủ theo mod n, vì
mọi số ngun bất kỳ đều có thể tìm đƣợ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 tính cộng, trừ và nhân theo modn, nhƣng
khơng đóng đối với phép chia, vì phép chia cho a theo mod n chỉ có thể thực hiện
đƣợc khi a và n nguyên tố với nhau, tức khi gcd(a, n) = 1.
Xét tập Zn

*

*
=  a  Zn: gcd(a, n) = 1, tức Zn là tập con của Zn

*
gồm các phần tử nguyên tố với n. Zn đƣợ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 Zn một đại diện đồng dƣ với mình
*
theo mod n. Nếu p là một số nguyên tố thì Zp = 0, 1, 2,..., p-1.
*
*
Tập Zn lập thành một nhóm con đối với phép nhân của Zn, vì trong Zn phép
*
chia theo mod n bao giờ cũng thực hiện đƣợc, Zn đƣợc gọi là nhóm nhân của Zn.
Trong đại số, 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 Zn có cấp (n), và nếu p là số ngun tố thì nhóm Zp có cấp p-1.
*

Nói phần tử g  Zn
m

có cấp m, nếu m là số nguyên dƣơng bé nhất sao cho

*

g = 1 trong Zn .

9


Ngƣời ta đã chứng minh đƣợc rằng: m│(n) . Vì vậy, với mọi b  Zn* ta ln
(n)

có b

 1 mod n.
*

Nếu p là số nguyên tố, thì dễ thấy (p) = p-1, vì vậy ta có với mọi b  Zn có:
b

p-1

 1(mod p).

(1.3)

Nếu b có cấp p-1, tức p-1 là số mũ bé nhất thoả mãn công thức (1.3), thì các
phần tử

b, b2, ..., b

p-1

*

đều khác nhau và theo modp, chúng lập thành Zp .

*

Khi đó Zp là một nhóm cyclic và b là một phần tử sinh, hay phần tử nguyên
thuỷ 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 thuỷ:
*

1. Với mọi số nguyên tố p, Zp là nhóm cyclic, và có (p-1) phần tử nguyên thuỷ.
2. Nếu p-1 = p1 a . p2 a ... pk a
1

a

(p-1)/p 1

2

là triển khai chính tắc của p-1 và nếu

k

(p-1)/p k

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

 1(mod p),
*

thì a là phần tử nguyên thuỷ theo mod p (tức của Zp )
3. Nếu g là phần tử nguyên thuỷ 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 thuỷ theo mod p.
Ba tính chất đó là cơ sở giúp ta tìm đƣợc các phần tử nguyên thuỷ theo mod p,
với p là số nguyên tố bất kỳ.
Một số tính chất sau đây, đƣợc ứng dụng nhiều trong mật mã học:
p-1

* Định lý Fermat: Nếu p là số nguyên tố và gcd(a, p) = 1, thì a
*

(n)

* Định lý Euler: Nếu a  Zn , thì a

 1(mod n).
r

s

Nếu r  s (mod (n)) thì a  a (mod n).

10

 1(mod p).

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ì nói a là
thặng dƣ bậc hai mod n.
Khi nó khơng có nghiệm thì nói a là bất thặng dƣ bậc hai mod n.
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ƣ mod n.
* Tiêu chuẩn Euler.
Khi p
(p-1)/2

a

là số nguyên tố, số a là thặng dƣ bậc 2 mod p nếu và chỉ nếu
 1(mod p).

Chứng minh:
(p-1)/2

Giả sử có x sao cho x2  a(mod p), khi đó a
(p-1)/2

Ngƣợc lại, giả sử a

2 (p-1)/2

 (x )

p-1

x

 1(mod p).

*

 1(mod p). Khi đó a  Zp . Lấy b là phần tử nguyên
i

thuỷ mod p, ắt có số i nào đó sao cho a = b mod p.
Từ đó,

(p-1)/2

a

(p-1)/2

 bi

 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à  bj (mod p).
* Ký hiệu Legendre.

a

Cho p là số lẻ. Với mọi a  0 ký hiệu Legendre

p

0, khi a  0 (mod p)

11

nhƣ sau:


a

1, khi a  Qp (Tức a là thặng dƣ bậc hai mod p).

=

-1, khi a  Qp (Tức a là bất thặng dƣ bậc hai mod p).

p

Từ định nghĩa suy ra ngay a là thặng dƣ bậc hai mod p khi và chỉ khi

a

= 1.

p
Theo tiêu chuẩn euler, với mọi a  0, ta có:
a

(p-1)/2

a

(mod p).

p
* Ký hiệu Jacobi.
Mở rộng ký hiệu legendre, ta có ký hiệu Jacobi đối với mọi số nguyên lẻ hơn
n  1 và mọi số nguyên a  0.
Giả sử a có triển khai chính tắc thành thừa số nguyên tố là
n = p1
a

a1

.p

a2
2

= a

n

p1

a1

...p
a

ak
k

a2

thì:

..... a

p2

ak

pk

Khi n = p là số nguyên tố, thì giá trị của ký hiệu legendre và Jacobi 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:
1. Nếu m1  m2 mod n thì m1

m2

n = n
1, khi a  1 (mod 8)
2.

2 =

n

3.

-1, khi a  3 (mod 8)

m1.m2 = m1 . m2
n

n

n

4. Nếu m và n đều là số lẻ, thì:

12


_
m

=

n

n

khi m  3 mod 4 AND n  3 mod 4

m

n

khi m  3 mod 4 OR n  3 mod 4

m

* Phương trình đồng dư bậc hai:
x2 = a (mod n)

(1.4)

Trong 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à số nguyên nguyên tố với p.
Theo tiêu chuẩn Euler ta biết phƣơng trình (1.4) có nghiệm khi và chỉ khi
(p-1)/2

a

 1(mod p).

Khi đó ta có:
(p-1)/2+1

a

2(m+1)

 a (mod p),

 a (mod p).

a

m+1

Do đó x   a

(mod p) là nghiệm của phƣơng trình (1.4).

13


1.2.2. Độ phức tạp tính tốn.
1). Khái niệm độ phức tạp tính tốn.
Lý thuyết thuật tốn và hàm số 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 đƣợc” trong tốn học,
đƣa đến nhiều kết quả rất quan trọng và lý thú. Nhƣng từ cái “tính đƣợc” một cách
trừu tƣợng, hiểu theo nghĩa tiềm năng, đến việc tính đƣợc trong thực tế của khoa học
tính tốn bằng máy tính điện tử, là cả một khoảng cách rất lớn.
Biết bao thứ đƣợc chứng minh là tính đƣợc một cách tiềm năng, nhƣng khơng
tính đƣợc trong thực tế, dù có sự hỗ trợ của máy tính điện tử. Vấn đề là ở chỗ, địi hỏi
về khơng gian vật chất và về thời gian để thực hiện các tiến trình tính tốn nhiều khi
vƣợt xa khả năng thực tế. Vào những năm 60 (của thế kỷ trƣớc), một lý thuyết về độ
phức tạp tính tốn đƣợc hình thành và phát triển 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, cả những bài toán
thuần tuý về lý thuyết đến những bài toán thƣờng gặp trong thực tế.
Độ 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 đó.
Dữ liệu đầu vào đối với một thuật toán thƣờng đƣợc biểu diễn qua các từ trong

một bảng ký tự nào đó. Độ dài của một từ là số ký tự trong từ đó.
Cho thuật tốn A trên bảng ký tự  (tức có đầu vào là các từ trong ).

14


Độ phức tạp tính tốn A đƣợc hiểu là 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 các dữ liệu vào có độ dài  n.
Ta nói thuật tốn A có độ phức tạp tính tốn thời gian đa thức, nếu có đa thức
p(n) sao cho với mọi n đủ lớn ta có A(n)  p(n), trong đó A(n) là độ phức tạp tính
tốn theo thời gian của A.
Bài toán “quyết định” là bài toán đƣợc xác định bởi:
- Một tập dữ liệu vào I (trong một bảng ký tự  nào đó).
- Một câu hỏi Q trên các dữ liệu vào, sao cho với mỗi dữ liệu vào x  I, câu hỏi
Q có một trả lời đúng hoặc sai.
Ta nói bài tốn quyết định P giải đƣợc, nếu có thuật tốn dễ giải nó, tức là thuật
tốn làm việc có kết thúc trên mọi dữ liệu vào của bài toán, và cho kết quả đúng sai
tuỳ theo câu hỏi Q trên dữ liệu đó có trả lời đúng hoặc sai. Bài tốn P là giải đƣợc
trong thời gian đa thức, nếu có thuật tốn giải nó với độ phức tạp thời gian đa thức.
2). Lớp phức tạp.
Ta xét một số lớp bài toán đƣợc xác định theo độ phức tạp tính tốn của chúng.
Định nghĩa P là lớp tất cả các bài toán có thể giải đƣợc bởi thuật tốn đơn định trong
thời gian đa thức.
Giả sử cho hai bài toán P1 và P2 với các tập dữ liệu trong hai bảng kí tự tƣơng
*

*

ứng là 1 và 2. Thuật toán  : 1  2 đƣợc gọi là phép qui dẫn bài tốn P1 về

bài tốn P2, nếu nó biến mỗi dữ liệu x của bài toán P1 thành dữ liệu (x) của bài toán
P2, và sao cho câu hỏi của P1 trên x có trả lời đúng khi và chỉ khi câu hỏi của P2
trên(x) cũng có trả lời đúng.

15


Ta nói bài tốn P1 quy dẫn được về bài toán P2 trong thời gian đa thức và ký
hiệu P1P2 nếu có thuật tốn  với độ phức tạp thời gian đa thức, quy dẫn bài toán P1
về bài toán P2.
Ta dễ thấy rằng nếu P1P2 và P2  P, thì cũng có P1  P.
Một lớp quan trọng các bài toán đã đƣợc nghiên cứu nhiều là lớp các bài toán
thƣờng gặp trong thực tế, nhƣng cho đến nay chƣa có khả năng nào chứng tỏ là chúng
có thể giải đƣợc trong thời gian đa thức. Đó là lớp các bài toán N P đầy đủ.
Cùng với khái niệm thuật tốn tất định (có thể mơ tả chính xác chẳng hạn bởi
máy Turing tất định), ta xét khái niệm thuật tốn khơng đơn định.
Đối với máy Turing tất định, khi máy đang ở trạng thái q và đang đọc ký tự a
thì cặp

(q, a) xác định duy nhất một hành động kế tiếp của máy. Đối với máy

Turing không đơn định, ta quy ƣớc rằng (q, a) xác định không phải duy nhất, mà là
một tập hữu hạn các hành động kế tiếp.
Nhƣ vậy, đối với một dữ liệu vào x, thuật tốn khơng đơn định khơng phải chỉ
có một tiến trình tính tốn duy nhất, mà có thể có một số hữu hạn những tiến trình tính
tốn khác nhau.
Ta nói thuật tốn khơng đơn định A chấp nhận dữ liệu x, nếu A có ít nhất một
tiến trình tính tốn kết thúc ở trạng thái chấp nhận đƣợc (tức với kết quả đúng).
Bài toán P đƣợc gọi là giải được bởi thuật tốn khơng đơn định trong thời gian
đa thức nếu có thuật tốn khơng đơn định A và đa thức p(n), sao cho với mọi dữ liệu

vào x có độ dài n, thì x  P (tức là câu hỏi của P có trả lời đúng trên x) khi và chỉ khi
thuật toán A chấp nhận bởi tiến trình tính tốn có độ phức tạp thời gian  p(n).
Ký hiệu lớp tất cả các bài toán giải đƣợc bởi thuật tốn khơng đơn định trong
thời gian đa thức là N P.

16


Bài toán P đƣợc gọi là N P đầy đủ, nếu P  N P và với mọi Q  N P đều có
Q  P.
Lớp N P có một số tính chất sau:
1. P  N P
2. Nếu P1  P2 và P1  N P , thì P2  N P
3. Nếu P1, P2  N P, P1  P2, và P1 là N P đầy đủ, thì P2 cũng là N P đầy đủ .
Có thể xem rằng trong lớp NP, lớp P là lớp con các bài toán “dễ” nhất, các bài
toán N P đầy đủ là các bài tốn “khó” nhất. Nếu có ít nhất một bài toán N P đầy đủ
đƣợc chứng minh là thuộc P , thì lập tức suy ra P = N P.

3). Hàm một phía.
Khái niệm độ phức tạp tính toán cung cấp cho ta một cách tiếp cận mới đối với
vấn đề bí mật trong các vấn đề bảo mật và 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
n

những thuật tốn có độ phức tạp tính tốn cỡ (n) = 2 , 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, vì
nó đị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.
Hàm số y = (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 biết y, thì tính ngƣợc x = ƒ-1(y) là “khó”.
Ví dụ 1:

17


Cho p là số nguyên tố lớn, và  là phần tử nguyên thuỷ mod p. Hàm số
x

*

*

y= mod p (từ Zp vào Zp ) là hàm một phía, vì hàm ngƣợc của nó, biết y và  tìm
x = log(y), là hàm có độ phức tạp tính tốn rất lớn.
Ví dụ 2:
Cho n = p.q là tích của hai số nguyên tố lớn, (n) = (p -1)(q - 1).
a là số nguyên sao cho gcd(a, (n)) = 1, a.b  1 mod (n).
Hàm số y = xa mod n (từ Zn vào Zn ) cũng là hàm một phía.

Hàm y = (x) đƣợc gọi là hàm một phía có cửa sập (trapdoor one-way
funtion), nếu biết x tính ra y là “dễ”, việc tính ngƣợc từ y tìm x là “khó”.
Nhƣng có yếu tố z nào đó trợ giúp thì việc tính x từ y lại trở thành “dễ”. Khi đó ta gọi
z là “cửa sập” của hàm y = (x).
Ví dụ 3:

a
Hàm số y=x mod n (với n là tích của hai số nguyên tố lớn p, q; n = p.q;

(n) = (p -1)(q - 1)) là hàm một phía có cửa sập. Từ x tính y là dễ, từ y tính x (nếu
chỉ biết n, a) là “khó”.
Nhƣng vì biết p và q nên biết (n)=(p-1)(q-1), và dùng thuật tốn Euclide mở
b

rộng tìm đƣợc b sao cho a.b  1(mod (n)), từ đó dễ tìm đƣợc x=y mod n.
Ở đây, có thể xem p, q là cửa sập.

18


1.2.3. Một số bài toán quan trọng trong mật mã.
Trong phần này sẽ xét ba bài tốn có vai trị quan trọng trong lý thuyết mật mã,
đó là ba bài tốn: Kiểm tra số ngun tố, phân tích một số nguyên thành tích của các
thừa số nguyên tố, tính logarit rời rạc của một số theo modulo nguyên tố. Ở đây ta
mặc định rằng các số nguyên tố là rất lớn.
1). Bài toán kiểm tra số nguyên tố lớn.
Cho n là số nguyên bất kỳ. Làm thế nào để biết n là số ngun tố hay khơng?
Bài tốn đƣợc đặt ra từ những buổi đầu của số học, và trải qua hơn 2000 năm đến nay
vẫn một là bài toán chƣa có đƣợc những cách giải dễ dàng. Bằng những phƣơng pháp
đơn giản nhƣ phƣơng pháp sàng Eurratosthè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.

19


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.

Trong mục này sẽ lƣợc qua vài tính chất của số nguyên tố và một vài phƣơng
pháp thử tính nguyên tố của một số nguyên bất kỳ.
a/. Tiêu chuẩn Euler-Solovay-Strassen:
a) 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

a

b

mod n.

b) Nếu n là hợp số, thì:
a:1  a  n-1,

a

(n-1)/2

a

mod n  Error!

b
b/. Tiêu chuẩn Solovay-Strassen-Lehmann:
a) Nếu n là số nguyên tố, thì với mọi số nguyên dƣơng a  n-1:
(n-1)/2

a

 1mod n.

b) Nếu n là hợp số thì
(n-1)/2

a:1  a  n-1, a

 1mod n  Error!

c/. Tiêu chuẩn Miler-Rabin:
e

a) Cho n là số nguyên lẻ, ta viết (n-1)= 2 .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):
u

2 k .u

(a  1 mod n)  k < e ( a
b) Nếu n là hợp số, thì

20

 -1 mod n).


2 k .u

u

a:1  a  n-1, (a  1 mod n)  k < e(a

 -1 mod n) 

Error!
Các tiêu chuẩn kể trên là cơ sở để ta xây dựng các thuật tốn xác suất kiểu MonteCarlo thử tính nguyên tố (hay hợp số) của các số nguyê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
(n-1)/2

2. if (ai/n)  ai

mod n, then

3. answer “n là số nguyên tố”
4. else
5. answer “n là hợp số” and quit
Nếu thuật toán cho trả lời “n là hợp số” thì đúng n là hợp số.
Nếu thuật toán cho trả lời “n là số nguyên tố”, thì trả lời đó có thể sai với xác
suất Monte-Carlo thiên về có, nếu xem nó là thuật tốn thử tính là hợp số. Thuật tốn
xác suất thiên về khơng, nếu nó là thuật tốn thử tính ngun tố của các số nguyên.
Tƣơng tự, dựa vào các tiêu chuẩn 2 và 3, ngƣời ta đã xây dựng các thuật toán
xác suất Solovay-Strassen-Lehmann và Miler-Rabin kiểu Monte-Carlo để thử tính
nguyên tố (hay là hợp số) của các số nguyên.
Hai thuật toán đó chỉ khác thuật tốn Euler-Solovay-Strassen ở chỗ cơng thức
trong hàng lệnh 2 cần đƣợc thay tƣơng ứng bởi
(n-1)/2

a

 1mod n

hay
u

2 k .u

(a  1mod n)  k < e(a

 -1mod n)

trong đó u và e đƣợc xác định bởi: n-1=2e.u, u là số lẻ.

21


Xác suất sai lầm  khi nhận đƣợc kết quả “n là số nguyên tố” trong các thuật
toán trên đƣợc tính nhƣ sau:
Giả sử n là số lẻ trong khoảng N và 2N, tức Nnguyên tố”, và B là sự kiện “thuật toán cho kết quả 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
(n-1)/2

a

a

mod n

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)  Error!.
Theo cơng thức Bayes ta có

p(A/B)= Error! =

p ( A / B ). p( A)
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ỉ N/1nNn/1n n,
số các số lẻ là N/2  n/2, do đó p( A ) 2/ ln n và p( A ) 1 – 2/ 1n n. Dĩ nhiên ta có
p(B/ A )=1. Thay các giá trị đó vào cơng thức trên, ta đƣợc:
P(A/B) 

2 t (1 

2
)
ln n

2
2
2 (1 
)
ln n ln n

t



ln n  2
ln n  2  2t 1

(1.5)

Chú ý:
Đánh giá đó cũng đúng đối với thuật tốn Solovay-Strassen-Lehmann. Đối với
thuật toán Miler-Rabin, ta đƣợc một đánh giá tốt hơn, cụ thể là:
p(A/B) =

ln n  2
ln n  2  2t 1

(1.6)

22


-13

Chú ý rằng khi t = 50 thì đại lƣợng ở vế phải của (1.5)  10 , và vế phải của
-28

(1.6)  10 ; 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-Solovay-Strassen và Solovay-Strassen-Lehmann sẽ thử cho ta một số
nguyên tố với xác suất sai lầm  10

là  10

-13

và thuật tốn Miler-Rabin với xác suất sai lầm

-28

.

Có thể tính đƣợc độ 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ỡ logn, tức là đa thức theo độ dài biểu diễn của dữ liệu vào (số n).
Tuy nhiên các thuật tốn đó chỉ cho ta tính thử nguyên 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 số
nguyên tố với độ chắc chắn 100% là số ngun 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
ngun tố với độ chính xác tuyệt đối.
Adleman, Pomerance và Rumely đã đề xuất một số thuật tố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 hoá 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 tốn này đã
đƣợc dùng để tìm nhiều số ngun tố rất lớn.
d/. Thuật toán Agrawal-Kayal-Saxena.
Tháng 8-2002, các nhà toán học Ấn độ Agrawal, Kayal và Saxena đã đƣa ra
thuật tốn tất định, thử tính ngun tố, có độ phức tạp thời gian đa thức, khá đơn giản.
Thuật toán Agrawal-Kayal-Saxena.
Input: integer n>1
b

1. If (n is of the form a , b>1) output COMPOSITE1;

2. r = 2;
3. While (r4.

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

5.

if (r is prime)
23