ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HÀ THỊ THANH HUYỀN

NGHIÊN CỨU
MỘT SỐ BÀI TOÁN
TRONG HỆ THỐNG TIỀN ĐIỆN TỬ

LUẬN VĂN THẠC SĨ
4). Độ phức tạp của thuật toán đơn định. 18
5). Phân lớp bài toán theo độ phức tạp 19
1.2. MÃ HOÁ. 21
1.2.1. Khái niệm mã hoá. 21 3
1.2.2. Hệ mã hoá khoá công khai RSA. 23
1.3. KÝ SỐ. 24
1.3.1. Giới thiệu về ký số. 24
1.3.2. Một số sơ đồ ký số. 25
1). Sơ đồ ký số RSA. 25
2). Sơ đồ ký số Schnorr. 26
1.3.3. Chữ ký mù. 27
1). Giới thiệu về chữ ký mù. 27
2). Chữ ký mù RSA. 29
3). Chữ ký mù Schnorr. 31
1.3.4. Chữ ký nhóm và ứng dụng. 32
1). Sơ đồ chữ ký nhóm dạng 1. 32
2). Sơ đồ chữ ký nhóm dạng 2. 33
3). Sơ đồ chữ ký nhóm dạng 3. (Jan Camenish và Stadler) 33
1.3.5. Chữ ký nhóm mù và ứng dụng. 35
1.3.6. Chữ ký dùng một lần. 37
1.3.7. Chữ ký không thể chối bỏ. 38
1). Sơ đồ chữ ký không thể chối bỏ của Chaum. 39
2). Ví dụ. 40
1.3.8. Chia sẻ bí mật có thể xác minh. 41
1). Sơ đồ chia sẻ bí mật 41
2). Sơ đồ chia sẻ bí mật có thể xác minh. 42
1.3.9. Hàm băm. 43
5
5). Phân tích lƣợc đồ Fair tracing. 65
3.2.4. So sánh lƣợc đồ KV và lƣợc đồ Fair tracing. 68
3.3. GIẢI PHÁP CHO BÀI TOÁN ẨN DANH VÀ 70
CHỐNG GIAN LẬN GIÁ TRỊ ĐỒNG TIỀN. 70
3.3.1. Giới thiệu giải pháp. 70
3.3.2. Lƣợc đồ Chaum-Fiat-Naor. 72
1). Giao thức Rút tiền. 74
2). Giao thức Thanh toán. 75
3). Giao thức Gửi. 75
4). Đánh giá. 75
5). Chi phí 76
6). Tấn công 76
3.3.3. Lƣợc đồ Brand. 77
1). Khởi tạo tài khoản. 77
2). Giao thức rút tiền. 79
3). Giao thức thanh toán. 81
4). Giao thức Gửi. 82
5). Đánh giá 83
6). Tấn công 85
CHƢƠNG 4. XÂY DỰNG THỬ NGHIỆM HỆ THỐNG TIỀN ĐIỆN TỬ DỰA
TRÊN LƢỢC ĐỒ BRAND 86
4.1. MÔ TẢ BÀI TOÁN NGHIỆP VỤ. 86
1). Khởi tạo tài khoản (Open account). 87
2). Chứng minh đại diện tài khoản (Authenticate). 87
3). Rút tiền (Withdraw Money). 87
4). Thanh toán (Payment Money). 87
5). Gửi tiền (Deposit Money). 87

7
DANH MỤC CÁC KÝ HIỆU.

TT
Ký hiệu
Chú giải cho ký hiệu sử dụng
1
RSA
Hệ mã hoá công khai đƣợc đề xuất bởi Ron Rivest, Adi
Shamir, Len Adlemon năm 1977
2
TPD
Thƣ mục công khai tin tƣởng - Trusted Public
Directory).
3
SSS
Sơ đồ chia sẻ bí mật - Secret Sharing Schemes
4
VSS
Sơ đồ chia sẻ bí mật có thể xác minh - Verify Secret
Sharing
5
KV
Lƣợc đồ KV, (tên viết tắt của hai tác giả D. Kugler và
H. Vogt)
6
TTP
Bên thứ ba tin cậy - Trusted Third Party 9
MỞ ĐẦU
1. Tính cấp thiết của luận văn.
Sự mở rộng và phổ biến của Internet đã tạo ra phƣơng thức mua bán hàng
qua mạng (thƣơng mại điện tử). Nó tác động mạnh mẽ đến lĩnh vực ngân hàng
truyền thống, làm xuất hiện các sản phẩm mới có liên quan đến ngân hàng nhƣ thẻ
tín dụng, giao dịch ngân hàng, qua điện thoại di động, ngân hàng tự phục vụ và
tiền điện tử hay ví điện tử cũng đang trở thành hiện thực. Hầu hết mọi ngƣời đều
mong đợi một ngày nào đó tiền giấy sẽ không còn là phƣơng thức thanh toán trong
các phiên giao dịch nữa. Trên toàn thế giới, tiền điện tử đã và đang đƣợc ứng dụng
thành công, đem lại những lợi ích lớn lao cho ngƣời dùng.
Tuy nhiên trong thực tế, quá trình sử dụng tiền điện tử đã nảy sinh một số
vấn đề đáng quan tâm nhƣ: ngƣời dùng gian lận giá trị đồng tiền, tiêu nhiều lần một
đồng tiền hay khó xác định đƣợc danh tính của ngƣời sở hữu đồng tiền.
Chính vì vậy, luận văn đi vào nghiên cứu một số bài toán trong hệ thống tiền
điện tử, phân tích và nêu ra các giải pháp phù hợp.
Từ đó, xây dựng mô phỏng một hệ thống thanh toán bằng tiền điện tử dựa
trên lƣợc đồ Brand.
2. Mục đích của luận văn.
Mục đích của luận văn là nghiên cứu và đƣa ra những giải pháp khoa học
cho các bài toán phát sinh trong quá trình sử dụng tiền điện tử.
Từ đó, luận văn so sánh, đánh giá ƣu nhƣợc điểm của các giải pháp, chỉ rõ
giải pháp nào sẽ đạt hiệu quả tối ƣu đối với từng loại tiền điện tử.
3. Đối tƣợng nghiên cứu.
Đối tƣợng nghiên cứu của luận văn là các bài toán phát sinh khi dùng tiền
điện tử.
Chƣơng 3: Một số bài toán phát sinh khi dùng tiền điện tử.
Nêu các bài toán phổ biến có thể phát sinh trong quá trình sử dụng tiền điện
tử nhƣ: bài toán ẩn danh ngƣời dùng, bài toán gian lận giá trị đồng tiền và bài toán
double-spending.
Đối với từng bài toán, nêu ra các giải pháp, phân tích rõ ƣu, nhƣợc điểm, có
sự so sánh đối chiếu giữa các giải pháp.
Chƣơng 4: Xây dựng thử nghiệm hệ thống tiền điện tử dựa trên lƣợc đồ Brand. 12
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.
(Tham khảo tài liệu [1])
1.1.1. Khái niệm trong số học.
1). Số nguyên tố và nguyên tố cùng nhau.
Số nguyên tố là số chỉ chia hết cho 1 và chính nó.
Ví dụ: 2, 3, 5, 7, 17, … là những số nguyên tố.
Hai số m và n đƣợc gọi là nguyên tố cùng nhau nếu ƣớc số chung lớn nhất của
chúng bằng 1.
Ký hiệu: gcd(m,n) = 1.
Ví dụ: 9 và 14 là nguyên tố cùng nhau.
2). Đồng dư thức.
Định nghĩa:
Cho a và b là các số nguyên, n là số nguyên dƣơng thì a đƣợc gọi là đồng dƣ
với b theo modullo n nếu n|(a-b) (tức (a – b) chia hết cho n, hay khi chia a và b cho
n đƣợc cùng một số dƣ nhƣ nhau). Số nguyên n đƣợc gọi là modullo của đồng dƣ.
Kí hiệu:
(mod )a b n

Ví dụ:

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 Z
n
= {0, 1, 2, 3, ,n-1}, là số dƣ chung khi chia các số đó cho n. Vì vậy, ta có
thể đồng nhất Z
n
với tập tất cả các lớp tƣơng đƣơng các số nguyên theo mod n, trên
tập đó ta có thể xác định các phép tính cộng, trừ và nhân theo mod n.
Tập Z
n
= {0, 1, 2, 3, ,n-1} đƣợc gọi là tập thặng dƣ đầy đủ theo mod n, vì
mọi số nguyên bất kỳ đều có thể tìm đƣợc trong Z
n
một số đồng dƣ với mình
(theo mod n).
Tập Z
n
*
= {a  Z
n
: gcd (a, n) = 1}, tức Z
n
*
là tập con của Z
n
bao gồm tất cả
các phần tử nguyên tố với n. Ta gọi tập đó là tập các thặng dƣ thu gọn theo mod n. 14

15
1.1.2. Khái niệm trong đại số.
1). Khái niệm nhóm.
Khái niệm:
Nhóm là bộ các phần tử (G, *) thỏa mãn các tính chất sau:
Tính chất kết hợp: ( x * y ) * z = x * ( y * z )
Tính chất tồn tại phần tử trung gian:
e  G: e * x = x * e = x , x  G
Tính chất tồn tại phần tử nghịch đảo:
x’  G: x’ * x = x * x’ = e
Cấp của nhóm:
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
*
n
Z
có cấp
()n

và nếu p là số nguyên tố thì nhóm
*
p
Z
có cấp p-1.
Cấp của phần tử:
Ta nói một phần tử

,…,g
k
) (k  2, g
i
 G) và
phần tử h cố định.
Tìm đại diện của h, ví dụ nhƣ:

1
i
k
a
i
i
hg


(a
i
là các số nguyên)
Bài toán tìm đại diện của h rất khó, trừ khi ta đã có (g
1
, g
2
,…,g
k
) và (a
1
, a
2

quá trình tính toán đó.
* Với thuật toán tựa Algol:
Chi phí thời gian của một quá trình tính toán là số các phép tính cơ bản cần thực
hiện trong quá trình tính toán đó từ khi nhập dữ liệu vào đến khi cho ra kết quả. 18 * Với máy Turing:
Chi phí thời gian của một quá trình tính toán là số bƣớc chuyển hình trạng từ hình
trạng đầu q
0
đến hình trạng kết thúc q
n
.
b/. Chi phí bộ nhớ của một quá trình tính toán là dung lƣợng nhớ cần thiết để thực
hiện quá trình tính toán đó.
* Với thuật toán tựa Algol:
Tổng số: biến vào, biến ra, biến phụ cần dùng trong quá trình tính toán.
* Với máy Turing:
Số ô nhớ cần dùng trên băng nhớ tuyến tính dùng trong quá trình tính toán.
4). Độ phức tạp của thuật toán đơn định.
a/. Độ phức tạp trung bình
* Là tổng các chi phí về bộ nhớ và thời gian chia cho tổng số các đầu vào.
b/. Độ phức tạp cực đại (trong trƣờng hợp xấu nhất).
* Độ phức tạp về bộ nhớ trong trƣờng hợp xấu nhất:
L
A
(n) = max{ l

Có nghĩa, thuật toán đƣợc xử lý trong thời gian đủ nhanh, thực tế cho phép,
đó là thuật toán có độ phức tạp thời gian đa thức.
+ Thực tế khó giải: “Khó giải”.
Có nghĩa, thuật toán phải xử lý trong nhiều thời gian, thực tế khó chấp
nhận,
đó là thuật toán có độ phức tạp thời gian là trên đa thức (hàm mũ).
P: là lớp bài toán giải đƣợc bằng thuật toán đơn định, đa thức (Polynomial).
NP : là lớp bài toán giải đƣợc bằng thuật toán không đơn định, đa thức.
 P  NP (hiện nay ngƣời ta chƣa biết P ≠ NP).
Lớp bài toán NP- Hard, NP- Complete.
Khái niệm "Dẫn về được".
Bài toán B gọi là "Dẫn về đƣợc” bài toán A một cách đa thức, ký hiệu: B 
p
A.
nếu có thuật toán đơn định đa thức để giải bài toán A thì cũng có thuật toán đơn
định đa thức để giải bài toán B.
Nghĩa là: Bài toán A "khó hơn" bài toán B, hay B "dễ” hơn A.
Chú ý: Quan hệ 
p
có tính chất bắc cầu, có nghĩa: C  B và B  A  C  A.
Khái niệm "Khó tương đương".
Bài toán A gọi là “khó tƣơng đƣơng” bài toán B, ký hiệu A ~ B,
nếu : A  B và B  A
Bài toán NP- Hard.
Bài toán A đƣợc gọi là NP - hard (NP- khó) nếu  L  NP đều là L  A. 20
Lớp bài toán NP - hard bao gồm tất cả những bài toán NP - hard.
Bài toán NP - hard có thể nằm trong hoặc ngoài lớp NP.

Mã hoá công khai (phi đối xứng).
Sau đây là định nghĩa hình thức về sơ đồ mã hoá và cách thức thực hiện để
lập mã và giải mã:
Một sơ đồ hệ thống mã hoá là một bộ năm

= (P, C, K, E, D) thoả mãn:
P là một tập hữu hạn các ký tự bản rõ,
C là một tập hữu hạn các ký tự bản mã,
K là một tập hữu hạn các khoá,
E là một ánh xạ từ P x K vào C đƣợc gọi là phép lập mã
P là một ánh xạ từ K x C vào P, đƣợc gọi là phép giải mã
Với mỗi K  K ta định nghĩa e
K
: P C, d
K
: C P là hai hàm cho bởi:
 x  P: e
K
(x) = E (K, x)
 y  C: d
K
(y) = D (K, y)
e
K
và d
K
đƣợc gọi là hàm lập mã và hàm giải mã ứng với khoá mật mã K.
Các hàm đó phải thoả mãn hệ thức:
 x  P: d
K


3. Tính giá trị hàm số Ơle:
( ) ( 1)( 1)n p q   

4. Chọn số tự nhiên b,
1 ( )bn  
và là số nguyên tố cùng nhau với
()n

5. Tính a là nghịch đảo của b:
1(mod ( ))ab n

Khi đó, b là khoá lập mã, công khai
a là khoá giải mã, bí mật
Lập mã:
Chọn P = C = Z
n
với
 
. , 0,1,2, , 1n p q Z n
n
  

mod
b
x Z y x n Z
nn
   

Giải mã:

Mỗi
:sig P A
k

và
 
er x ,:
k
true falsev P A
là những hàm sao cho mỗi
thông điệp x  P và mỗi chữ ký y A thoả mãn phƣơng trình dƣới đây:

er( , )v x y 
()
er( , )
()
true khi y sig x
v x y
false khi y sig x






b
(mod n)

Trích đoạn Cấu trúc tiền điện tử Giới thiệu giải pháp GIẢI PHÁP CHO BÀI TOÁN ẨN DANH VÀ

---