ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Thị Vân Anh NGHIÊN CỨU MỘT SỐ CHỮ KÝ SỐ ĐẶC BIỆT
VÀ ỨNG DỤNG

KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin HÀ NỘI - 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Thị Vân Anh NGHIÊN CỨU MỘT SỐ CHỮ KÝ SỐ ĐẶC BIỆT
VÀ ỨNG DỤNG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Sinh viên
Phạm Thị Vân Anh TÓM TẮT KHÓA LUẬN

Những năm gần đây, nhu cầu trao đổi thông tin từ xa của con ngƣời ngày càng
lớn, các ứng dụng trao đổi thông tin qua mạng diễn ra ngày càng nhiều. Tuy nhiên,
mỗi loại ứng dụng có những đòi hỏi riêng khác nhau, ví dụ nhƣ ứng dụng bầu cử từ xa

2.1.1. Sơ đồ chữ ký RSA 30
2.1.2. Sơ đồ chữ ký mù RSA 31
2.1.3. Ví dụ minh họa 32
2.2. ỨNG DỤNG CHỮ KÝ MÙ 33
2.2.1. Ứng dụng trong tiền điện tử 33
2.2.2. Ứng dụng trong bỏ phiếu trực tuyến. 34
Chương 3. CHỮ KÝ KHÔNG THỂ CHỐI BỎ 36
3.1. KHÁI NIỆM CHỮ KÝ KHÔNG THỂ CHỐI BỎ 36
3.1.1. Sơ đồ chữ ký không thể chối bỏ Chaum – Van Antwerpen 36
3.1.2. Ví dụ minh họa 38
3.1.3. Một số đánh giá về sơ đồ 39
3.2. HÌNH THỨC TẤN CÔNG CHỮ KÝ KHÔNG THỂ CHỐI BỎ 43
3.2.1. Tống tiền ngƣời ký 43
3.2.2. Nhiều ngƣời cùng xác thực chữ ký mà ngƣời ký không biết 43 3.3. ỨNG DỤNG CHỮ KÝ KHÔNG THỂ CHỐI BỎ 45
3.3.1. Ứng dụng trong thẻ chứng minh thƣ điện tử. 45
3.3.2. Ứng dụng trong ký hợp đồng qua điện thoại 45
Chương 4. THỬ NGHIỆM CÁC CHƢƠNG TRÌNH 46
4.1. THỬ NGHIỆM ỨNG DỤNG CHỮ KÝ SỐ 46
4.1.1. Giới thiệu 46
4.1.2. Mô tả hoạt động chƣơng trình 47
4.2. THỬ NGHIỆM CHƢƠNG TRÌNH KÝ MÙ RSA 53
4.2.1. Giới thiệu 53
4.2.2. Mô tả hoạt động chƣơng trình 53
4.3. THỬ NGHIỆM CHỮ KÝ KHÔNG THỂ CHỐI BỎ 55
4.3.1. Giới thiệu 55
4.3.2. Mô tả hoạt động chƣơng trình 56
KẾT LUẬN 60

DANH SÁCH HÌNH VẼ

Hình 1: Giao diện chương trình ký số RSA 46
Hình 2: Giao diện chức năng “Ký”RSA 47
Hình 3: Giao diện chức năng xác thực chữ ký số RSA 49
Hình 4: Giao diện chức năng mã hóa DES file văn bản và chữ ký 50
Hình 5: Giao diện chức năng giải mã DES 51
Hình 6: Giao diện chức năng ký mù 53
Hình 7: Giao diện chức năng xóa mù chữ ký 54
Hình 8: Giao diện của người ký chữ ký không thể chối bỏ 55
Hình 9: Giao diện của người xác thực chữ ký không thể chối bỏ 55
Hình 10: Thông báo khi chữ ký không thể chối bỏ được xác thực là đúng 57
Hình 11: Thông báo khi điều kiện   





  không được thỏa mãn 58
Hình 12: Thông báo khi chữ ký đúng là giả mạo 58
Hình 13: Thông báo khi phát hiện người ký cố tình chối bỏ chữ ký của mình 59

1

LỜI MỞ ĐẦU
Trong những năm gần đây, sự bùng nổ của cách mạng thông tin đang diễn ra
nhanh chóng trên phạm vi toàn thế giới. Sự phổ biến rộng rãi của Internet đã kết nối

2

Chƣơng 2: Chữ ký mù RSA: trình bày về sơ đồ chữ ký mù RSA, ví dụ minh
họa và ứng dụng chữ ký mù.
Chƣơng 3: Chữ ký không thể chối bỏ: trình bày về sơ đồ chữ ký không thể
chối bỏ Chaum van Antwerpen, ví dụ minh họa, các hình thức tấn công chữ ký không
thể chối bỏ và ứng dụng của của chữ ký này.
Chƣơng 4: Thử nghiệm các chƣơng trình: thử nghiệm chƣơng trình chữ ký
số RSA, chƣơng trình chữ ký mù RSA và chƣơng trình chữ ký không thể chối bỏ.
Kết luận.

3

2
, …, 

, nếu nó
là bội của tất cả các số đó.
+ Một ƣớc chung d > 0 của các số nguyên 
1
, 
2
, …, 

, trong đó mọi ƣớc
chung của 
1
, 
2
, …, 

đều là ƣớc của d, thì d đƣợc gọi là ƣớc chung lớn
nhất (UCLN) của 
1
, 
2
, …, 

.
Ký hiệu d = gcd (
1
, 
2

chung của 
1
, 
2
, …, 

đều là bội của m, thì m đƣợc gọi là bội chung nhỏ
nhất (BCNN) của 
1
, 
2
, …, 

.
Ký hiệu m = lcm(
1
, 
2
, …, 

) hay m = BCNN(
1
, 
2
, …, 

).
4

Ví dụ:

7


là |
7

| = 6.
2/. Tính chất
- d = gcd(
1
, 
2
, …, 

)  tồn tại các số x
1
,

x
2
,…, x
n
sao cho:
d = a
1
x
1
+ a
2
x

n
x
n

- d = gcd(
1
, 
2
, …, 

)  gcd(
1
/, 
2
/, …, 

/) =1.
- m = lcm(
1
, 
2
, …, 

)  gcd(/
1
, /
2
, …, /

) =1.

b
r
a = b.q + r
30
18
12
30 = 18 * 1+12
18
12
6
18 = 12 * 1+6
12
6
0
12 = 6 * 2 + 0
4/. Thuật toán Euclide mở rộng
- Bài toán:
+ Dữ liệu vào: Cho hai số nguyên không âm a, b, a ≥ b.
+ Kết quả: d = gcd (a,b) và hai số x, y sao cho: a.x + b.y = d.
- Thuật toán (Mô phỏng bằng ngôn ngữ Pascal):
Readln(a, b);
IF b=0 THEN
Begin
d := a; x := 1; y := 0; writeln(d, x, y);
End
ELSE
Begin
x2 := 1; x1 := 0; y2 := 0; y1 := 1;
While b>0 Do
begin

), tức là m \ (a - b).
+ (2)  (3):
Nếu có (2), tức là m\(a – b). Nghĩa là có t  Z sao cho a - b = mt hay a = b + mt
+ (3)  (1):
Nếu có (3), tức là tồn tại số nguyên t sao cho a = b + m.t.
Lấy a chia cho m, giả sử thƣơng là q
a
và dƣ r, hay a = mq
a
+ r (0 ≤ r < m), do đó:
b + m.t = a = mq
a
+ r hay b = m(q
a
- t) + r (0 ≤ r < m).
Điều đó chứng tỏ khi chia a và b cho m đƣợc cùng số dƣ r, hay a ≡ b (mod m).
2/. Các tính chất của quan hệ “đồng dƣ”
- Quan hệ “đồng dư” là quan hệ tương đương trong Z
Với mọi số nguyên dƣơng m ta có:
+ a ≡ a (mod m) với mọi a  Z (tính chất phản xạ)
+ a ≡ b (mod m) thì b ≡ a (mod m) (tính chất đối xứng)
+ a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m) (tính chất bắc cầu)

7

- Tổng hay hiệu các “đồng dư”
+ (a+b) (mod n)

[(a mod n) + (b mod n)] (mod n)
+ (a- b) (mod n)

[(a mod n) * (b mod n)] (mod n)
Tổng quát:
Có thể nhân từng vế nhiều đồng dƣ thức theo cùng một modulo m, ta đƣợc một
đồng dƣ thức theo cùng modulo m, tức là:
Nếu a
i
≡ b
i
(mod m) với i = 1 k, thì ta có:



 


=1
( )

=1

- Hệ quả:
+ Có thể cộng hoặc trừ cùng một số vào hai vế của một đồng dƣ thức.
+ Có thể chuyển vế các số hạng của đồng dƣ thức bằng cách đổi dấu các số hạng
đó.
+ Có thể cộng vào một vế của đồng dƣ thức một bội của modulo:
a ≡ b (mod m)  a + km ≡ b (mod m) với mọi k  Z
+ Có thể nhân hai vế của một đồng dƣ thức với cùng một số:
a ≡ b (mod m)  ac ≡ bc (mod m) với mọi c

Z

.Nhƣ vậy [a]
m
= [b]
m
 a ≡ b (mod m)
Vì vậy ta có thể đồng nhất Z
m
với tập các lớp tƣơng đƣơng theo modulo m.
- Z
m
={0, 1, 2,…, m-1} đƣợc gọi là tập các “thặng dư đầy đủ” theo modulo m.
Mọi số nguyên bất kỳ đều có thể tìm đƣợc trong Z
m
một số đồng dƣ với mình
theo modulo m.
1.1.1.3. Số nguyên tố
1/. Khái niệm
Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ƣớc là 1 và chính nó.
Ví dụ:
Các số 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 là số nguyên tố.
2/. Một số định lý về số nguyên tố
- Định lý: về số nguyên dương > 1
Mọi số nguyên dƣơng n > 1 đều có thể biểu diễn đƣợc duy nhất dƣới dạng:
1 2 k
n n n
1 2 k
.
=P P P
n


Cho số nguyên dƣơng n, số lƣợng các số nguyên dƣơng bé hơn n và nguyên tố
cùng nhau với n đƣợc ký hiệu () và gọi là hàm Euler.
+ Nhận xét: Nếu p là số nguyên tố, thì 



= 
Ví dụ:
Tập các số nguyên không âm nhỏ hơn 7 là Z
7
= {0, 1, 2, 3, 4, 5, 6}.
Do 7 là số nguyên tố, nên tập các số nguyên dƣơng nhỏ hơn 7 và nguyên tố cùng
nhau với 7 là Z
7
*
= {1, 2, 3, 4, 5, 6}. Khi đó |Z| = (p) = p - 1 = 7 - 1 = 6
+ Định lý về hàm Euler
Nếu n là tích của hai số nguyên tố p, q thì




= 



. 




+ Trên cơ sở các định lý về số nguyên tố, hiện nay ngƣời ta có các phƣơng pháp
“xác suất“ để kiểm tra tính nguyên tố của một số nguyên dƣơng n.
Ví dụ các phƣơng pháp: Solovay-Strassen [13], Miller-Rabin [7][14],…
+ Định lý Ferma:
Nếu p là số nguyên tố, a là số nguyên, thì a
p
≡ a (mod p).
Nếu p nguyên tố, p không chia hết cho a, thì a
p-1
≡ 1 (mod p).
Ví dụ: 4
7
≡ 4 (mod 7); 4
7-1
≡ 1 (mod 7).
+ Định lý Euler
Nếu gcd(a, m) = 1 thì 
()
1 (mod m).
Trƣờng hợp m là số nguyên tố, ta có định lý Ferma.
Ví dụ: m = 10, 



= 

2

. 



Z và vì vậy


= 
+

()
= 

. (

()
)

 

(mod m), theo định lý Euler.
11

Nhận xét: Hệ quả trên giúp giảm nhẹ việc tính toán đồng dƣ của lũy thừa bậc
cao.
Ví dụ: Ta thấy 

15

= 

5




Trong trƣờng hợp a > 

m

, khi ấy b < a. Ngƣời ta dùng hệ quả 1 để tính “đồng
dƣ” của “ lũy thừa” lớn.
- Trường hợp 



> a
Trong thực tế tính toán thƣờng gặp m lớn, do đó 



lớn, thậm chí > a, khi ấy
ngƣời ta dùng kỹ thuật khác, ví dụ phƣơng pháp bình phƣơng liên tiếp.
+ Phương pháp bình phương liên tiếp
Ví dụ: Tính 87
43
(mod 103).
Khai triển số mũ 43 dƣới dạng cơ số 2:
43 = 32 + 8 + 2 + 1 = 2
5
+ 2
3
+ 2
1


87
32
(mod 103) = 55
2
(mod 103) = 38 (ứng với 2
5
)
Theo khai triển (*), lấy tích của các lũy thừa bậc 2
5
, 2
3
, 2
1
, 2
0
(rút gọn theo
modulo 103), thu đƣợc kết quả:
87
43
(mod 103) = 38 * 63 * 50 * 87 (mod 103) = 85
+ Định lý về Số dư (ĐL Trung Quốc)
Cho tập số nguyên tố cùng nhau từng đôi một m
1
, m
2
,…m
r
. Với mỗi bộ số nguyên
bất kỳ a

1
a
2
m
3
…m
r
b
2
+ m
1
m
2
a
3
m
3
…m
r
b
3
+…+ m
1
m
2
…m
r-1
a
r
b


x 3118

mod 5353

x 139

mod 391

x 239

mod 247



Vì các số 5353, 391, 247 nguyên tố cùng nhau, nên theo định lý Trung Quốc về
số dƣ, hệ có nghiệm duy nhất theo modulo m = 5353*391*247 = 516976681.
Để tìm x mod m ta tính:
m
1
= m/5353 = 96577 → y
1
= 96577
-1
mod 5353 = 5329
m
2

= m/391 = 1322191 → y
2


G)


x

G, có phần tử nghịch đảo x’

G: x * x’ = x’ * x = e.
- Cấp của nhóm G đƣợc hiểu là số phần tử của nhóm, ký hiệu là
G
.
Cấp của nhóm có thể là  nếu G có vô hạn phần tử.
- Nhóm Abel là nhóm (G, *), trong đó phép toán hai ngôi * có tính giao hoán.
Tính chất: Nếu a * b = a * c, thì b = c
Nếu a * c = b * c, thì a = b
Ví dụ:
- Tập hợp các số nguyên Z cùng với phép cộng (+) thông thƣờng là nhóm giao
hoán, có phần tử đơn vị là số 0. Gọi là nhóm cộng các số nguyên.
- Tập Q* các số hữu tỷ khác 0 (hay tập R* các số thực khác 0), cùng với phép
nhân (*) thông thƣờng là nhóm giao hoán, gọi là nhóm nhân các số hữu tỷ (số
thực) khác 0.
- Tập các vectơ trong không gian với phép toán cộng vectơ là nhóm giao hoán.
2/. Nhóm con của nhóm (G, *)
Nhóm con của G là tập S  G, S  , và thỏa mãn các tính chất sau:
- Phần tử trung lập e của G nằm trong S.
- S khép kín đối với phép tính (*) trong G, tức là x*y  S (,  S)
- S khép kín đối với phép lấy nghịch đảo trong G, tức 
1
 S (xS)

n
= e, thì G có cấp .
Ví dụ: (Z
+
, +) gồm các số nguyên dƣơng là Cyclic với phần tử sinh g = 1, e = 0.
Đó là nhóm Cyclic vô hạn, vì không tồn tại số tự nhiên n để g
n
= e.
3/. Cấp của một phần tử trong nhóm Cyclic
Phần tử   G đƣợc gọi là có cấp d nếu d là số nguyên dƣơng nhỏ nhất sao cho

d
= e, trong đó e là phần tử trung lập của G.
Nhƣ vậy phần tử

có cấp 1, nếu

= e.
1.1.2.3. Nhóm (


, phép nhân mod n)
1/. Khái niệm tập thặng dƣ thu gọn theo modulo
- Kí hiệu Z
n
= 0, 1, 2, . , n-1 là tập các số nguyên không âm < n.
Z
n
và phép cộng (+) lập thành nhóm Cyclic có phần tử sinh là 1, phần tử trung
lập e = 0.

*
, phép nhân mod n) không phải là nhóm Cyclic.
- Nhóm nhân 

là Cyclic chỉ khi n có dạng: 2, 4, p
k
, hay 2p
k
với p là nguyên tố lẻ.
2/. Một số kết quả đã đƣợc chứng minh
- Định lý Lagrange: Nếu G là nhóm cấp n và

 G, thì cấp của

là ước của n.
- Hệ quả: Giả sử

 có cấp m, thì m là ước của

(n).
- Định lý: Nếu p là số nguyên tố thì là nhóm Cyclic.
Nếu b  thì


(n)

 1 (mod n). Nếu p là số nguyên tố thì

, nếu tồn tại b

Z
n
sao cho a.b

1 (mod n), ta nói b là phần tử
nghịch đảo của a trong Z
n
và ký hiệu a
-1
.
Một phần tử có phần tử nghịch đảo, gọi là khả nghịch.
- Định lý: UCLN (a, n) = 1  Phần tử a

Z
n
có phần tử nghịch đảo.
Chứng minh:
Nếu a.a
-1
≡ 1 (mod n) thì a.a
-1
= 1 + kn ↔ a.a
-1
- kn = 1 → (a, n) =1.
Nếu (a, n) = 1, ta có aa
-1
+ kn = 1 → a.a
-1

Z
*
n
Z
16

- Tìm phần tử nghịch đảo bằng Thuật toán Euclid mở rộng
Input: a  Z
n
, n
Output: Phần tử nghịch đảo của a.
Procedure Invert(a,n);
begin
g
0
:=n; g
1
:=a; u
0
:=1; u
1
:=0; v
0
:=0; v
1
:=1; i:=1;
while g
i
 0 do
begin

-1
:= t + n;
end;
Ví dụ: Tìm phần tử nghịch đảo của 3 trong Z
7

Tức là phải giải phƣơng trình 3.x ≡ 1 (mod 7), x sẽ là phần tử nghịch đảo của 3.
Bảng 2: Ví dụ sử dụng thuật toán Euclide mở rộng để tìm phần tử nghịch đảo
i









y
0
7
1
0

1
3
0
1
2
2








“Logarit rời rạc” chính là việc giải phƣơng trình x = log
g

(mod p) với ẩn x.
Hay phải tìm số x duy nhất sao cho: g
x




(mod p).
5/. Thặng dƣ bậc hai
- Thặng dƣ bậc hai:
Cho p là số nguyên tố lẻ, x là một số nguyên dƣơng  p-1. x đƣợc gọi là “thặng
dư bậc hai” mod p, nếu phƣơng trình y
2


x mod p có lời giải.
1.1.3. Khái niệm độ phức tạp của thuật toán
1.1.3.1. Khái niệm thuật toán
1/. Khái niệm bài toán
Bài toán đƣợc diễn đạt bằng hai phần:

A
(e) là giá thời gian và l
A
(e) là giá bộ nhớ.
2/. Độ phức tạp về bộ nhớ (trong trƣờng hợp xấu nhất)
l
A
(n) = max{l
A
(e), với |e|

n}. (n là kích thƣớc đầu vào của thuật toán)
3/. Độ phức tạp thời gian (trƣờng hợp xấu nhất) t
A
(n) = max{t
A
(e), với |e|

n}
4/. Độ phức tạp tiệm cận
Độ phức tạp PT(n) đƣợc gọi là tiệm cận tới hàm f(n), ký hiệu O(f(n)) nếu  các
số n
0
, c mà PT(n)  c.f(n) ,

n

n
0
.