Khóa luận Nghiên cứu một số giải pháp công nghệ thông tin trong việc sử dụng tiền điện tử
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
---------- YZ ----------
Nguyễn Thị An
NGHIÊN CỨU MỘT SỐ GIẢI PHÁP CÔNG NGHỆ
THÔNG TIN TRONG VIỆC SỬ DỤNG TIỀN ĐIỆN TỬ
KHOÁ LUẬN TỐT NGHIỆP HỆ ĐẠI HỌC CHÍNH QUY
Ngành: Công Nghệ Thông Tin
HÀ NỘI - 2009
1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
---------- YZ ----------
Nguyễn Thị An
NGHIÊN CỨU MỘT SỐ GIẢI PHÁP CÔNG NGHỆ
THÔNG TIN TRONG VIỆC SỬ DỤNG TIỀN ĐIỆN TỬ
KHOÁ LUẬN TỐT NGHIỆP HỆ ĐẠI HỌC CHÍNH QUY
Ngành: Công Nghệ Thông Tin
Cán bộ hướng dẫn: PGS.TS Trịnh Nhật Tiến
HÀ NỘI - 2009
2
LỜI CẢM ƠN
Lời đầu tiên, em xin được gửi lời cảm ơn chân thành và sâu sắc nhất tới PGS.TS
Trịnh Nhật Tiến – người Thầy luôn chỉ bảo, hướng dẫn hết sức nhiệt tình, giúp đỡ em
trong suốt quá trình học tập và xây dưng khóa luận.
Em xin chân thành cảm ơn các Thầy, Cô giáo đã dạy dỗ em trong suốt quá trình
học tập tại trường Đại học Công Nghệ. Những kiến thức các thầy cô truyền đạt sẽ mãi
là hành trang để em vững trong tương lai.
Xin được cảm ơn tới các bạn K50HTTT đã cung cấp cho mình những tài liệu quý
báu để mình hoàn thành khóa luận. Cảm ơn tới tất cả các bạn bè của mình đã luôn sát
vai, tin tưởng và giúp đỡ mình trong suốt 4 năm đại học qua.
Cuối cùng, con xin được gửi lời biết ơn sâu sắc nhất tới Bố mẹ và những người
thân trong gia đình, những người luôn dành cho con tình yêu, niềm tin và động viên
con trong suốt quá trình học tập.
Hà nội, tháng 5 năm 2009
Sinh viên
Nguyễn Thị An
3
TÓM TẮT NỘI DUNG
Thương mại điện tử nói chung và tiền điện tử nói riêng đang còn là một lĩnh
vực mới mẻ. Vì vậy, để tiền điện tử có thể thực sự thâm nhập vào cuộc sống, trở
thành một phương thức thanh toán hiệu quả đòi hỏi cần phải có quá trình nghiên cứu
và phát triển.
Khóa luận sẽ trình bày những kiến thức khái quát về Tiền điện tử, sau đó tập
trung nghiên cứu hai vấn đề lớn hiện đang đặt ra đối với tiền điện tử:vấn đề ẩn danh
người sử dụng và vấn đề ngăn chặn người sử dụng tiêu một đồng Tiền điện tử
nhiều lần. Khóa luận cũng giới thiệu và phân tích một số hệ thống tiền điện tử hiện
nay trên thế giới, và đề xuất việc ứng dụng tiền điện tử tại Việt nam. Ngoài ra, khóa
luận sẽ Demo một chương trình nhỏ về một hệ thống tiền điện tử bằng ngôn ngữ C++.
4
MỤC LỤC
LỜI CẢM ƠN ................................................................................................................. 3
TÓM TẮT NỘI DUNG.................................................................................................. 4
MỤC LỤC ....................................................................................................................... 5
DANH MỤC CÁC KÝ KIỆU........................................................................................ 8
DANH MỤC BẢNG BIỂU ............................................................................................ 9
MỞ ĐẦU........................................................................................................................ 10
Chương 1. CÁC KHÁI NIỆM CƠ BẢN .................................................................... 12
1.1. MỘT SỐ KHÁI NIỆM TOÁN HỌC.............................................................. 12
1.1.1.
1.1.2.
1.1.3.
Khái niệm trong số học.................................................................... 12
Khái niệm trong đại số..................................................................... 15
Độ phức tạp...................................................................................... 17
1.2. MÃ HÓA. .......................................................................................................... 20
1.2.1.
1.2.2.
1.2.3.
1.2.4.
Khái niệm về mã hóa. ...................................................................... 20
Hệ mã hóa. ....................................................................................... 21
Mã hóa và giải mã............................................................................ 21
Hệ mã hóa khóa công khai RSA...................................................... 22
1.3. CHỮ KÝ............................................................................................................ 24
1.3.1.
1.3.2.
Giới thiệu về chữ ký......................................................................... 24
Một số sơ đồ chữ ký ........................................................................ 26
1.4. CHIA SẺ BÍ MẬT CÓ THỂ XÁC MINH. .................................................... 35
1.4.1.
1.4.2.
Sơ đồ chia sẻ bí mật......................................................................... 35
Sơ đồ chia sẻ bí mật có thể xác minh............................................... 36
1.5. HÀM BĂM........................................................................................................ 37
1.5.1. Hàm băm h là hàm một chiều (One-way Hash) với các đặc tính sau:...... 37
1.5.2. Tính chất của hàm băm............................................................................... 37
5
Chương 2: GIỚI THIỆU VỀ TIỀN ĐIỆN TỬ .......................................................... 38
2.1. KHÁI NIỆM THANH TOÁN ĐIỆN TỬ. ...................................................... 38
2.1.1. Các mô hình thanh toán điện tử.................................................................. 38
2.2. KHÁI NIỆM TIỀN ĐIỆN TỬ......................................................................... 40
2.2.1. Mô hình giao dịch mua bán bằng tiền điện tử. ........................................... 41
2.2.2. Cấu trúc của Tiền điện tử............................................................................ 43
2.2.3. Tính chất của tiền điện tử: .......................................................................... 44
Chương 3: MỘT SỐ VẤN ĐỀ PHÁT SINH KHI DÙNG TIỀN ĐIỆN TỬ ........... 47
3.1. MỘT SỐ VẤN ĐỀ PHÁT SINH..................................................................... 47
3.1.1. Vấn đề ẩn danh người sử dụng đồng tiền. .................................................. 47
3.1.2. Vấn đề gian lận giá trị đồng tiền................................................................. 47
3.1.3. Vấn đề tiêu xài một đồng tiền hai lần......................................................... 48
3.2. GIẢI PHÁP CHO BÀI TOÁN “ẨN DANH” VÀ “CHỐNG GIAN LẬN
GIÁ TRỊ ĐỒNG TIỀN”. ........................................................................................ 49
3.2.1. Giới thiệu giải pháp. ................................................................................... 49
3.2.2. Lược đồ Chaum-Fiat-Naor.......................................................................... 51
3.2.3. Lược đồ Brand. ........................................................................................... 55
3.3. GIẢI PHÁP CHO BÀI TOÁN “TIÊU NHIỀU LẦN MỘT ĐỒNG TIỀN”
..................................................................................................................... 64
3.3.1. Giới thiệu giải pháp..................................................................................... 64
3.3.2. Lược đồ truy vết gian lận KV..................................................................... 65
3.3.3. Lược đồ Fair tracing. .................................................................................. 69
3.3.4. So sánh lược đồ KV và Fair tracing............................................................ 77
Chương 4: MỘT SỐ HỆ THỐNG TIỀN ĐIỆN TỬ.................................................. 78
4.1. HỆ THỐNG DIGICASH................................................................................. 78
4.1.1. Phương thức hoạt động............................................................................... 79
4.4.2. Nhận xét...................................................................................................... 81
6
4.2. HỆ THỐNG PAYWORD................................................................................ 82
4.2.1. Phương thức hoạt động............................................................................... 82
4.2.2. Nhận xét..................................................................................................... 84
4.3. VẤN ĐỀ DÙNG TIỀN ĐIỆN TỬ Ở VIỆT NAM.......................................... 85
KẾT LUẬN ................................................................................................................... 88
DANH MỤC TÀI LIỆU THAM KHẢO .................................................................... 89
7
DANH MỤC CÁC KÝ KIỆU
TT Ký hiệu
Chú giải cho ký hiệu sử dụng
1
KV
Lược đồ KV (tên viết tắt của hai tác giả
D.Kugler và H.Vogt )
2
RSA
Hệ mã hóa khóa công khai được đề xuất bởi
Ron Rivest, Adi Shamir, Len Adlemon năm
1977.
3
4
5
SSS
TTP
VSS
Sơ đồ chia sẻ bí mật – Secret Sharing Schemes
Bên thứ ba tin cậy – Trusted Third Party
Sơ đồ chia sẻ bí mật có thể xác minh – Verify
Secret Sharing
8
DANH MỤC BẢNG BIỂU
Hình 1:
Hình 2:
Hình 3:
Hình 4:
Hình 5:
Hình 6:
Hình 7:
Hình 8:
Hình 9:
Hình 10:
Hình 11:
Hình 12:
Mô hình giao dịch cơ bản của hệ thống Tiền điện tử.
Mô hình phương thức thanh toán
Mô hình giao dịch có tính chuyển nhượng
Khái quát lược đồ Fair tracing
Quá trình khởi tạo tài khoản của lược đồ Brand
Quá trình chứng minh đại diện tài khoản của lược đồ Brand.
Giao thức rút tiền trong lược đồ Brand
Giao thức thanh toán
Tóm tắt lược đồ KV
Giai đoạn chuẩn bị trong lược đồ Fair tracing.
Giao thức rút tiền trong lược đồ Fair tracing.
Giai đoạn chuẩn bị với TTP.
9
MỞ ĐẦU
1. Tính cấp thiết của khóa luận.
Sự mở rộng và phổ biến của Internet đã thúc đẩy sự phát triển của Thương mại
điện tử. Một nhu cầu nảy sinh là thanh toán “điện tử”, đơn giản là người mua và
người bán thanh toán qua ngân hàng bằng thẻ tín dụng điện tử. Hình thức thanh toán
này chưa thật thuận tiện. Một hình thức thanh toán mới đã xuất hiện: thanh toán bằng
tiền điện tử.
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 lợi
ích cho người dùng.Tuy nhiên trong 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 xác định danh tính người sở hữu đồng tiền.
Vì vậy, khóa luận đi vào nghiên cứu một số bài toán trong hệ thống tiền điện tử
và trình bày những cách giải quyết phù hợp cho các vấn đề trên.
2. Mục đích của khóa luận.
Mục đích của khóa luận là nghiên cứu một số 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ử, so sánh, đánh giá ưu nhược điểm của
các giải pháp và chỉ rõ giải pháp nào phù hợp 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 là các bài toán phát sinh khi dùng tiền điện tử.
4. Phương pháp nghiên cứu.
Để nghiên cứu được các bài toán tiền điện tử, phần đầu khóa luận tổng hợp lại
những khái niệm toán học và những kiến thức cơ bản về lý thuyết mật mã có
liên quan. Sau đó đi sâu nghiên cứu về tiền điện tử, chỉ rõ cấu trúc, tính chất các loại
tiền điện tử đã và đang được sử dụng trên thế giới. Từ đó, phân tích để thấy rõ các
bài toán đã phát sinh như thế nào trong quá trình sử dụng tiền điện tử, và nêu lên các
giải pháp phù hợp cho từng bài toán.
10
5. Kết cấu của khóa luận.
Khóa luận gồm 4 chương.
Chương 1: Trình bày lại một số khái niệm toán học, và lý thuyết cơ bản về mật
mã học.
Chương 2: Trình bày khái niệm về tiền điện tử, cấu trúc, tính chất và mô hình
giao dịch của tiền điện tử.
Chương 3: Nêu một số bài toán phát sinh trong quá trình dùng tiền điện tử. Đối
với mỗi bài toán, nêu ra các giải pháp, phân tích rõ ưu nhược điểm của các giải pháp.
Chương 4: Giới thiệu một số hệ thống tiền điện tử của các nước trên thế giới và
demo hệ thống tiền điện tử KV.
Cuối cùng là kết luận lại những điểm chính, những đóng góp chính của khóa
luận, đồng thời chỉ ra những điểm cần khắc phục và định hướng phát triển tiếp theo
cho khóa luận.
11
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.1.1. Khái niệm trong số học.
1.1.1.1. Số nguyên tố và số nguyên tố cùng nhau.
1/. Khái niệm.
Số nguyên tố là số chỉ chia hết cho 1 và chính nó.
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
2/. Ví dụ.
2, 3, 5, 7, 11…là những số nguyên tố.
15 và 16 là hai số nguyên tố cùng nhau.
1.1.1.2. Đồng dư thức.
1/. Khái niệm.
Cho các số nguyên a, b, m (m>0). Ta nói rằng a và b “đồng dư” với nhau theo
modulo m, nếu chia a và b cho m, ta nhận được cùng một số dư.
Ký hiệu: a ≡ b (mod m)
2/. Ví dụ.
17 ≡ 5 (mod 3) vì chia 17 và 5 cho 3, được cùng số dư 2.
Nhận xét: Các mệnh đề sau đây là tương đương.
1) a ≡ b (mod m)
2) m \ (a - b)
3) Tồn tại số nguyên t sao cho a = b + mt
3/. Các tính chất của quan hệ “đồng dư”.
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ạ)
(tính chất đối xứng)
(tính chất bắc cầu)
a ≡ b ( mod m) thì b ≡ a ( mod m);
a ≡ b ( mod m) và b ≡ c ( mod m) thì a ≡ c ( mod m);
12
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ích các đồng dư:
(a*b) (mod n) ≡ [(a mod n) * (b mod n)] (mod n)
4/. Các lớp thặng dư:
Quan hệ “đồng dư” theo modulo m trên tập Z (tập các số nguyên) là một
quan hệ tương đương (vì có tính chất phản xạ, đối xứng, bắc cầu), do đó nó tạo ra trên
tập Z một phân hoạch gồm các lớp tương đương: hai số nguyên thuộc cùng một lớp
tương đương khi và chỉ khi chúng có cùng một số dư khi chia cho m.
Mỗi lớp tương đương đại diện bởi một số trong tập Zm ={0, 1,…, m-1} là số dư
khi chia các số trong lớp cho m, ký hiệu một lớp được đại diện bởi số a là [a]m .
Như vậy [a]m = [b]m ⇔ a ≡ b (mod m)
Vì vậy ta có thể đồng nhất Zm với tập các lớp tương đương theo modulo m.
Zm ={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 Zm một số đồng dư với mình theo
modulo m.
1.1.1.3. Phần tử nghịch đảo.
1/. Khái niệm.
Cho a ∈ Zn , nếu tồn tại b ∈ Zn sao cho a b ≡ 1 (mod n), ta nói b là phần tử
nghịch đảo của a trong Zn và ký hiệu a -1.
Một phần tử có phần tử nghịch đảo, gọi là khả nghịch.
2/. Định lý.
UCLN (a, n) = 1 ⇔ Phần tử a ∈ Zn có phần tử nghịch đảo.
13
3/. Tính chất.
Cho a, b ∈ Zn, phép chia của a cho b theo modulo n là tích của a và b-1 theo
modulo n, và chỉ được xác định khi b có nghịch đảo theo modulo n.
Cho a ∈ Zn. Khả nghịch khi và chỉ khi gcd(a,n) = 1
Giả sử d = gcd(a,n). Phương trình đồng dư ax ≡ b mod n có nghiệm x khi và
chỉ khi 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.
1.1.1.4. Khái niệm Logarit rời rạc.
Cho p là số nguyên tố, g là phần tử nguyên thuỷ của Zp , β ∈ Z*p
“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).
14
1.1.2. Khái niệm trong đại số.
1.1.2.1. Khái niệm nhóm.
1/. Khái niệm.
Nhóm là một bộ (G, *), trong đó G ≠ ∅, * là phép toán hai ngôi trên G
thoả mãn ba tính chất sau:
+ Phép toán có tính kết hợp: (x*y)* z = x*(y*z) với mọi x, y, z ∈ G.
+ Có phần tử phần tử trung lập e ∈ G: x*e = e*x = x với mọi x ∈ G.
+ Với mọi 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.
2/. 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.
1.1.2.2. Nhóm con của nhóm (G,*).
1/. Khái niệm.
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 với mọi x, y∈ S.
+ S khép kín đối với phép lấy nghịch đảo trong G, tức x -1 ∈ S với mọi x∈S.
15
2/. Ví dụ.
Xét nhóm cộng theo modulo 6 các số tự nhiên nhỏ hơn 6.
Z6= {0, 1, 2, 3, 4, 5}
Ta có các nhóm con sinh bởi các phần tử 2,3 là:
<2> = {0, 2, 4}
<3> ={0, 3}
1.1.2.3. Nhóm Cyclic.
1/. Khái niệm.
Nhóm (G, *) được gọi là Nhóm Cyclic nếu nó được sinh ra bởi một trong
các phần tử của nó.
Tức là có phần tử g ∈ G mà với mỗi a ∈ G, đều tồn tại số n ∈ N để
g n = g * g * … * g = a. (Chú ý g * g * … * g là g * g với n lần).
Khi đó g được gọi là phần tử sinh hay phần tử nguyên thuỷ của nhóm G.
Nói cách khác: G được gọi là Nhóm Cyclic nếu tồn tại g ∈ G sao cho mọi
phần tử trong G đều là một luỹ thừa nguyên nào đó của g.
2/. Ví dụ.
Nhóm (Z+ , +) gồm các số nguyên dương là Cyclic với phần tử sinh g = 1.
16
1.1.3. Khái niệm độ phức tạp.
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:
Input: Các dữ liệu vào của bài toán.
Output: Các dữ liệu ra của bài toán (kết quả).
Không mất tính chất tổng quát, giả thiết các dữ liệu trong bài toán đều là số nguyên.
2/. Khái niệm Thuật toán.
”Thuật toán” được hiểu đơn giản là cách thức để giải một bài toán. Cũng có thể
được hiểu bằng hai quan niệm: Trực giác hay Hình thức như sau:
• Quan niệm trực giác về ”Thuật toán”.
Một cách trực giác, Thuật toán được hiểu là một dãy hữu hạn các qui tắc (Chỉ thị,
mệnh lệnh) mô tả một quá trình tính toán, để từ dữ liệu đã cho (Input) ta nhận được
kết quả (Output) của bài toán.
• Quan niệm toán học về ”Thuật toán”.
Một cách hình thức, người ta quan niệm thuật toán là một máy Turing.
Thuật toán được chia thành hai loại: Đơn định và không đơn định.
Thuật toán đơn định (Deterministic):
Là thuật toán mà kết quả của mọi phép toán đều được xác định duy nhất.
Thuật toán không đơn định (NonDeterministic):
Là thuật toán có ít nhất một phép toán mà kết quả của nó là không duy nhất.
17
3/. Hai mô hình tính toán
Hai quan niệm về thuật toán ứng với hai mô hình tính toán.
Ứng với hai mô hình tính toán có hai cách biểu diễn thuật toán:
• Mô hình ứng dụng:
Thuật toán được biểu diễn bằng ngôn ngữ tựa Algol.
+ Đơn vị nhớ: Một ô nhớ chứa trọn vẹn một dữ liệu.
+ Đơn vị thời gian: Thời gian để thực hiện một phép tính cơ bản trong số học
hay logic như cộng, trừ, nhân, chia, ...
• Mô hình lý thuyết:
Thuật toán được biểu diễn bằng ngôn ngữ máy Turing.
+ Đơn vị nhớ: 1 ô nhớ chứa một tín hiệu. Với mã nhị phân thì đơn vị nhớ là 1 bit.
+ Đơn vị thời gian: Thời gian để thực hiện một bước chuyển hình trạng.
1.1.3.2. Khái niệm độ phức tạp của Thuật toán.
1/. Chi phí của thuật toán (Tính theo một bộ dữ liệu vào):
Chi phí phải trả cho một quá trình tính toán gồm chi phí về thời gian và bộ nhớ.
Chi phí thời gian của một quá trình tính toán là thời gian cần thiết để thực hiện
quá trình tính toán đó.
Với thuật toán tựa Algol: Chi phí thời gian là số các phép tính cơ bản thực hiện
trong quá trình tính toán .
Chi phí bộ nhớ của một quá trình tính toán là số ô nhớ cần thiết để thực hiện một
quá trình tính toán.
Gọi A là một thuật toán, e là dữ liệu vào của bài toán đã được mã hoá bằng cách
nào đó. Thuật toán A tính trên dữ liệu vào e phải trả một giá nhất định. Ta ký hiệu:
t 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):
LA(n) = max{ l A (e), với |e| ≤ n}, n là “kích thước” đầu vào của thuật toán.
18
3). Độ phức tạp thời gian (Trong trường hợp xấu nhất):
TA(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ố n0 , c mà PT(n) ≤ c.f(n) , ∀n ≥ n0.
5). Độ phức tạp đa thức:
Độ phức tạp PT(n) được gọi đa thức, nếu nó tiệm cận tới đa thức p(n).
6). Thuật toán đa thức:
Thuật toán được gọi là đa thức, nếu độ phức tạp về thời gian (trong trường hợp
xấu nhất) của nó là đa thức.
- Nói cách khác:
+ Thuật toán thời gian đa thức là thuật toán có độ phức tạp thời gian O(n t ),
trong đó t là hằng số.
+ Thuật toán thời gian hàm mũ có độ phức tạp thời gian O(t f (n) ), trong đó
t là hằng số và f(n) là đa thức của n.
- Thời gian chạy của các lớp thuật toán khác nhau:
Độ
phức tạp
Số phép tính(n=106)
Thời gian(106ptính/s)
O(1)
1
1micro giây
1 giây
O(n)
106
O(n2)
O(n3)
O(2n)
1012
1018
10301 030
11,6 ngày
32 000 năm
10301 006 tuổi của vũ trụ
19
1.2. MÃ HÓA.
1.2.1. Khái niệm về mã hóa.
* Mã hóa là quá trình chuyển thông tin có thể đọc được (gọi là Bản rõ) thành
thông tin “khó” thể đọc được theo cách thông thường (gọi là Bản mã).
Đó là một trong những kỹ thuật để bảo mật thông tin.
* Giải mã là quá trình chuyển thông tin ngược lạI: từ Bản mã thành Bản rõ.
* Thuật toán mã hoá hay giải mã là thủ tục tính toán để thực hiện mã hóa hay
giải mã.
* Khóa mã hóa là một giá trị làm cho thuật toán mã hoá thực hiện theo cách
riêng biệt và sinh ra bản rõ riêng. Thông thường khoá càng lớn thì bản mã càng an toàn.
Phạm vi các giá trị có thể có của khoá được gọi là Không gian khoá.
* Hệ mã hóa là tập các thuật toán, các khóa nhằm che giấu thông tin, cũng như
làm cho rõ nó.
Phân loại: Phân loại mã hóa theo đặc trưng của khóa
Có 2 loại:
+ Hệ mã hóa khóa đối xứng
+ Hệ mã hóa khóa công khai
20
1.2.2. Hệ mã hóa.
Việc mã hoá phải theo quy tắc nhất định, quy tắc đó gọi là Hệ mã hóa.
Hệ mã hóa được định nghĩa là bộ năm (P, C, K, E, D), trong đó:
P là tập hữu hạn các bản rõ có thể.
C là tập hữu hạn các bản mã có thể.
K là tập hữu hạn các khoá có thể.
E là tập các hàm lập mã.
D là tập các hàm giải mã.
Với khóa lập mã ke ∈ K, có hàm lập mã eke ∈ E, eke: P→ C,
Với khóa giải mã kd ∈ K, có hàm giải mã dkd ∈ D, dkd: C→ P,
sao cho dkd (eke (x)) = x, ∀ x ∈ P.
Ở đây x được gọi là bản rõ, eke (x) được gọi là bản mã.
1.2.3. Mã hóa và giải mã.
Người gửi G
→ →
eke (T)
→ → Người nhận N
(có khóa giải mã
(có khóa lập mã ke)
kd)
↑
Tin tặc có thể trộm bản mã eke (T)
21
1.2.4. Hệ mã hóa khóa công khai RSA.
1). Sơ đồ
(Rivest, Shamir, Adleman đề xuất năm 1977)
- Tạo cặp khóa (bí mật, công khai) (a, b) :
Chọn bí mật số nguyên tố lớn p, q, tính n = p * q, công khai n, đặt P = C = Zn
Tính bí mật φ(n) = (p-1).(q-1). Chọn khóa công khai b < φ(n), nguyên tố với φ(n).
Khóa bí mật a là phần tử nghịch đảo của b theo mod φ(n): a*b ≡ 1 mod φ(n).
Tập cặp khóa (bí mật, công khai) K = {(a, b)/ a, b ∈ Zn , a*b ≡ 1 mod φ(n)}.
Với Bản rõ x ∈ P và Bản mã y ∈ C, định nghĩa:
Hàm Mã hoá: y = ek (x) = x b mod n
Hàm Giải mã: x = dk (y) = y a mod n
2). Ví dụ .
Bản rõ chữ:
*Sinh khóa:
R E N A I S S A N C E
Chọn bí mật số nguyên tố p= 53, q= 61, tính n = p * q = 3233, công khai n.
Đặt P = C = Zn , tính bí mật φ(n) = (p-1). (q-1) = 52 * 60 = 3120.
+ Chọn khóa công khai b là nguyên tố với φ(n), tức là ƯCLN(b, φ(n)) = 1,
ví dụ chọn b = 71.
+ Khóa bí mật a là phần tử nghịch đảo của b theo mod φ(n): a*b ≡ 1(mod φ(n)).
Từ a*b ≡ 1 (mod φ(n)), ta nhận được khóa bí mật a = 791.
* Bản rõ số:
R E
17 04 13 00
m1 m2
N A
I
S
S
A
N C
18 00 13 02
m4 m5
E
(Dấu cách)
08 18
04
26
m3
m6
b
Theo phép lập mã: ci = mi mod n = mi 71 mod 3233, ta nhận được:
22
* Bản mã số:
c1
c2
0100
c3
c4
c5
c6
3106
0931
2691
1984
2927
a
Theo phép giải mã: mi = ci mod n = ci 791 mod 3233, ta nhận lại bản rõ.
3). Độ an toàn
- Hệ mã hóa RSA là tất định, tức là với một bản rõ x và một khóa bí mật a, thì
chỉ có một bản mã y.
- Hệ mật RSA an toàn, khi giữ được bí mật khoá giải mã a, p, q, φ(n).
Nếu biết được p và q, thì thám mã dễ dàng tính được φ(n) = (q-1)*(p-1).
Nếu biết được φ(n), thì thám mã sẽ tính được a theo thuật toán Euclide mở rộng.
Nhưng phân tích n thành tích của p và q là bài toán “khó”.
Độ an toàn của Hệ mật RSA dựa vào khả năng giải bài toán phân tích số
nguyên dương n thành tích của 2 số nguyên tố lớn p và q.
23
1.3. CHỮ KÝ.
1.3.1. Giới thiệu về chữ ký.
Ký số là phương pháp ký một thông điệp lưu dưới dạng “số”(điện tử).Thông điệp
được ký và chữ ký cùng truyền trên mạng tới người nhận.
Người ta tạo ra “chữ ký số” (chữ ký điện tử) trên “tài liệu số” giống như tạo ra
“bản mã” của tài liệu với “khóa lập mã”.
Như vậy “ký số” trên “tài liệu số” là “ký” trên từng bit tài liệu. Kẻ gian khó thể
giả mạo “chữ ký số” nếu nó không biết “khóa lập mã”.
Để kiểm tra một “chữ ký số” thuộc về một “tài liệu số”, người ta giải mã
“chữ ký số” bằng “khóa giải mã”., và so sánh với tài liệu gốc.
Ngoài ý nghĩa để chứng thực nguồn gốc hay hiệu lực của các tài liệu số hóa,
Mặt mạnh của “chữ ký số” hơn “chữ ký tay” là ở chỗ người ta có thể “ký”
vào tài liệu từ rất xa trên mạng công khai. Hơn thế nữa, có thể “ký” bằng các thiết bị
cầm tay (ví dụ: điện thoại di động) tại khắp mọi nơi miễn là kết nối được vào mạng.
Đỡ tốn bao thời gian, sức lực, chi phí, …
“Ký số” thực hiện trên từng bit tài liệu, nên độ dài của “chữ ký số” ít nhất cũng
bằng độ dài của tài liệu. Do đó thay vì ký trên tài liệu dài, người ta thường dùng “hàm
băm” để tạo “đại diện” cho tài liệu, sau đó mớI “Ký số” lên “đại diện” này
1). Sơ đồ chữ ký số
Sơ đồ chữ ký là bộ năm (P, A, K, S, V ), trong đó:
P là tập hữu hạn các văn bản có thể.
A là tập hữu hạn các chữ ký có thể.
K là tập hữu hạn các khoá có thể.
S là tập các thuật toán ký.
V là tập các thuật toán kiểm thử.
24
Với mỗi khóa k ∈ K có:
Thuật toán ký Sig k ∈ S, Sig k : P→ A,
Thuật toán kiểm tra chữ ký Ver k ∈ V, Ver k : P × A→ {đúng, sai}, thoả mãn
điều kiện sau với mọi x ∈ P, y ∈ A
Đúng, nếu y = Sig k (x)
Ver k (x, y) =
Sai, nếu y ≠ Sig k (x)
25
1.3.2. Một số sơ đồ chữ ký .
1.3.2.1. Sơ đồ ký số RSA.
1/. Sơ đồ (Đề xuất năm 1978)
*Tạo cặp khóa (bí mật, công khai) (a, b) :
Chọn bí mật số nguyên tố lớn p, q, tính n = p * q, công khai n, đặt P = C = Zn
Tính bí mật φ(n) = (p-1).(q-1). Chọn khóa công khai b < φ(n), nguyên tố với φ(n)
Khóa bí mật a là phần tử nghịch đảo của b theo mod φ(n): a*b ≡ 1 (mod φ(n).
Tập cặp khóa (bí mật, công khai) K = {(a, b)/ a, b ∈ Zn , a*b ≡ 1 (mod φ(n))}.
* Ký số: Chữ ký trên x ∈ P là y = Sig k (x) = x a (mod n), y ∈ A. (R1)
* Kiểm tra chữ ký: Verk (x, y) = đúng ⇔ x ≡ y b (mod n). (R2)
1.3.2.2. Sơ đồ ký số Schnoor.
1/. Sơ đồ:
Lấy G là nhóm con cấp q của Zn* với q là số nguyên tố.
Chọn phần tử sinh g ∈ G sao cho bài toán logarit trên G là khó giải.
Chọn x ≠ 0 làm khóa bí mật
Tính y = gx làm khóa công khai
Lấy H làm hàm băm không va chạm.
* Ký:
Giả sử cần ký trên văn bản m
Chọn r ngẫu nhiên thuộc Zq
Tính c = H (m,xr)
Tính s = (r+xc) mod q
Chữ ký Schorr là cặp (c,s)
* Kiểm tra chữ ký:
Với một văn bản m cho trước, một cặp (c, s) được gọi là một chữ ký Schnorr hợp
lệ nếu thỏa mãn phương trình.
c = H (m, gs * ys)
26
1.3.2.3. Chữ ký mù.
Chữ ký mù được Chaum giới thiệu vào năm 1983. Mục đíchc của chữ ký mù là
làm cho người ký trên văn bản không biết nội dung văn bản.
Ứng dụng trong hệ thống tiền điện tử: Mua bán hàng trên mạng.
Giả sử Alice muốn mua một quyến sách B giá 100$ từ Bob. Giả sử cả hai người
đều sử dụng dịch vụ của một ngân hàng. Giao thức giao dịch sẽ gồm 3 giai đoạn.
Rút tiền:
Alice tạo tiền điện tử C (với những thông tin : số seri, giá trị của C, ví dụ là 100$)
Alice yêu cầu ngân hàng ký mù lên C.
Giao thức ký thành công, ngân hàng sẽ trừ 100$ trong tài khoản của Alice.
Tiêu tiền:
Alice đưa cho Bob tiền C đã có chữ ký của ngân hàng, và yêu cầu Bob đưa cho
quyển sách B.
Bob kiểm tra chữ ký trên C. Nếu không hợp lệ, Bob sẽ dừng ngay giao dịch.
Gửi tiền:
Bob lấy C từ Alice và gửi cho ngân hàng.
Ngân hàng xác thực chữ ký trên C:
+ Nếu hợp lệ, ngân hàng kiểm tra xem C đã được tiêu trước đó hay chưa.
+ Nếu C chưa được tiêu thì ngân hàng cộng thêm C vào tài khoản của Bob.
+ Nếu việc gửi tiền thành công, Bob sẽ gửi quyển sách B cho Alice.
Bob khó thể biết rằng C là từ tài khoản nào. Khi Bob gửi C thì ngân hàng cũng
“khó” thể biết rằng C được lấy ra từ tài khoản của Alice vì nó đã được ký mù. Như vậy
tiền điện tử C không lưu lại dấu vết của những ai đã tiêu nó.
27
1/. Sơ đồ chữ ký mù RSA:
Yêu cầu bài toán là: A muốn lấy chữ ký của B trên x nhưng không muốn B biết x.
Quá trình thực hiện như sau.
+ Lấy p, q là các số nguyên tố lớn, tính n = p*q
+ Tính φ(n) = (p-1).(q-1), ab ≡ 1 mod φ(n)
+ r là số ngẫu nhiên ∈ Zn (chọn r sao cho tồn tại phần tử nghịch đảo r-1( mod n))
Bước 1: A làm mù x bằng một hàm:
Blind(x) = x*rb mod n = z, và gửi z cho B
Bước 2: B ký trên z bằng hàm:
Sign(z) = Sign(Blind (x)) = za mod n = y, và gửi lại y cho A.
Bước 3: A tiến hành xóa mù y bằng thuật toán:
UnBlind(y) = UnBlind( Sign( Blind( x))) = y/r mod n = sign(x)
Ví dụ:
Alice cần Bob ký lên thông điệp x = 8.
Nếu theo chữ ký RSA, thì kết quả thông điệp sau khi ký là :
Sign( x=8) = xa mod n = 87 mod 15 = 2 = y
Nhưng Alice muốn Bob ký mù lên x.
Bước 1(làm mù): Alice tiến hành làm mù x = 8
Blind (x) = x* rb mod n= 8 * 11 7 (mod 15)
= 8 * 19487171 (mod 15)
= 15589368 mod 15 = 13 = z.
Với r = 11 là số ngẫu nhiên ∈ Z15 ( thoa: gcd(11, 15) = 1)
Bước 2: Tiến hành ký trên z.
y = Sign(z) = za mod n = 137 (mod 15) = 7
Bước 3: Tiến hành xóa mù:
UnBlind(y) = y/r (mod n) =7/11 (mod 15) = 7 * 11-1 mod 15 = 2
28
2/. Sơ đồ chữ ký mù Schnorr:
Sơ đồ chữ ký Schnorr được xây dựng bằng cách mù hóa sơ đồ ký số Schnorr.
Giao thức thực hiện các bước sau:
Chuẩn bị:
Khóa bí mật của ngân hàng là x, khóa công khai là y = g x mod n
Alice cần ký lên đồng tiền Cm
Ký:
Bước 1:
Ngân hàng lấy ngẫu nhiên r ∈ Zq
Tính t = gr và gửi t cho Alice
Bước 2:
Alice lấy ngẫu nhiên γ, δ ∈ Zq
Tính t’ = t gγ yδ mod n
Tinh c = H (Cm, t’)
Tính c’ = c- δ mod q = H(Cm,t’) – δ mod q.
Gửi c’ cho ngân hàng.
Bước 3:
Ngân hàng tính s = c’ – r x mod q
Gửi s cho Alice.
Bước 4:
Tính s’ = s + γ mod q. Chữ ký là (c, s’)
Kiểm tra chữ ký:
Chữ ký (c, s) là hợp lệ nếu: c = H(Cm, t’) = H(Cm. gs * yc).
29
1.3.2.4. Chữ ký dùng một lần:
Sơ đồ chữ ký dùng một lần có nhiều ứng dụng, đặc biệt là một số ứng dụng trong
các mô hình tiền điện tử. Sau đây là sơ đồ chữ ký dùng một lần của Schorr.
Với sơ đồ này, người dùng trong cùng một hệ thống có thể chia sẻ một số ngẫu
nhiên và 2 số nguyên tố p và q sao cho: q | (p-1), q ≠ 1 và gq = 1 mod q
Chuẩn bị:
Người dùng, giả sử Alice chọn Sk ∈ Zq ngẫu nhiên làm khóa bí mật.
Tính Pt= g-sk mod p làm khóa công khai.
Ký:
Giả sử Alice cần ký trên thông điệp m
Alice lấy ngẫu nhiên r ∈ Zq*
Tính x = gr mod p, c = H (m||x), y= ( r + cSk )mod q
Chữ ký trên thông điệp m là (c, y)
Kiểm tra:
Ver = true Ù x = gr mod p và c = H (m || x)
Nhận xét:
Số r không được dùng quá một lần để tạo ra các chữ ký khác nhau.
Alice sử dụng r để ký hai lân thông điệp m và m’, tạo ra hai chữ ký khác nhau là
(c, y) và (c’, y’). Khi đó ta có:
(y – y’) = [(r + cSk) – (r + c’Sk)] = Sk * (c – c’)
Như vậy, nếu Alice sử dụng r quá một lần để ký cho hai thông điệp khác nhau, thì
bất kỳ ai có hai thông điệp trên, đều có thể giải mã được khóa bí mật Sk.
Vì vậy, sơ đồ chữ ký này được gọi là sơ đồ chữ ký dùng một lần.
30
Tải về để xem bản đầy đủ
89 trang
16/04/2025
170
Bạn đang xem 30 trang mẫu của tài liệu "Khóa luận Nghiên cứu một số giải pháp công nghệ thông tin trong việc sử dụng tiền điện tử", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- khoa_luan_nghien_cuu_mot_so_giai_phap_cong_nghe_thong_tin_tr.pdf
