MỞ ĐẦU 1. Tính cấp thiết của luận văn Hiện nay, sự phát triển nhanh chóng của mạng và công nghệ thông tin, sự bùng nổ của Internet đã mang lại những thay đổi chƣa từng thấy trong thƣơng mại điện tử. Với xu thế hội nhập vào nền kinh tế thế giới, sự phát triển các dịch vụ của thƣơng mại điện tử là xu hƣớng tất yếu. Trên thế giới, tiền điện tử đã và đang đƣợc ứng dụng thành công với nhiều hình thức phong phú, nhƣng khái niệm “tiền điện tử” vẫn còn là khái niệm khá mới mẻ ở Việt Nam.
Mục đích của luận văn Luận văn nghiên cứu một số hệ thống tiền điện tử trên thế giới và đề xuất về khả năng sử dụng tiền điện tử ở Việt Nam. Đối tƣợng nghiên cứu Đối tƣợng nghiên cứu của luận văn là một số hệ thống tiền điện tử. Phạm vi nghiên cứu Luận văn tập trung nghiên cứu về năm hệ thống tiền điện tử điển hình trên thế giới: First Virtual, Digicash, Millicent, Mondex, PayWord. Phƣơng pháp nghiên cứu Nghiên cứu những kiến thức khái quát về tiền điện tử và một số hệ thống tiền điện tử thông qua các sách báo, tạp chí bằng tiếng Việt, tiếng Anh và một số trang Web có liên quan đến đề tài.
Ý nghĩa khoa học và thực tiễn của luận văn Luận văn trình bày những kiến thức khái quát về tiền điện tử, đi sâu nghiên cứu, phân tích một số hệ thống tiền điện tử và một số vấn đề hiện đang đặt ra đối với tiền điện tử cùng các hƣớng giải quyết cho các vấn đề đó. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Kết cấu luận văn Luận văn gồm có 4 chƣơng: - Chƣơng 1: Các khái niệm cơ bản. Trình bày 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: Cơ sở khoa học của tiền điện tử. Trình bày những kiến thức khái quát về thƣơng mại điện tử và tiền điện tử (khái niệm, cấu trúc, tính chất, phân loại tiền điện tử; các hình thức thanh toán bằng tiền điện tử; một số vấn đề về tiền điện tử). - Chƣơng 3: Một số hệ thống tiền điện tử. Giới thiệu, phân tích, so sánh các hệ thống tiền điện tử đã đƣợc triển khai.
- Chƣơng 4: Khảo sát tình hình sử dụng tiền điện tử. Trình bày về tình hình sử dụng tiền điện tử ở một số quốc gia trên thế giới và đề xuất về khả năng sử dụng tiền điện tử ở Việt Nam. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 Chƣơng 1 - CÁC KHÁI NIỆM CƠ BẢN 1. MỘT SỐ KHÁI NIỆM TOÁN HỌC 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ố nguyên lớn hơn 1, chỉ có hai ƣớc dƣơng là 1 và chính nó. Ví dụ: 2, 3, 5, 7, 17, … là những số nguyên tố. Các hệ mật mã thƣờng sử dụng các số nguyên tố lớn hơn 10150.
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. Ví dụ: 9 và 14 là hai số nguyên tố cùng nhau. Đồng dư thức Cho n là số nguyên dƣơng. Ta nói số nguyên a đồng dƣ với số nguyên b theo modulo 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ƣ [1]. Kí hiệu: a b (mod n) Ví dụ: 67 ≡ 11 (mod 7), bởi vì 67 (mod 7) = 4 và 11 (mod 7) = 4 * Tính chất của đồng dƣ Cho a, a1, b, b1, c Z. Ta có các tính chất sau: a b mod n khi và chỉ khi a và b có cùng số dƣ khi chia cho n. Tính phản xạ: a a mod n.
Tính đối xứng: Nếu a b mod n thì b a mod n. Tính bắc cầu: Nếu a b mod n và b c mod n thì a c mod n. Nếu a a1 mod n, b b1 mod n, thì a + b (a1 + b1) mod n và ab (a1b1) mod n. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 * Lớp tƣơng đƣơng Lớp tƣơng đƣơng của một số nguyên a là tập hợp các số nguyên đồng dƣ với a theo modulo n.
Không gian Zn, Z *n Tập Zn = {0, 1, 2,…, n-1}, đƣợc gọi là tập thặng dư đầy đủ theo mod n. Mọi số nguyên đều có thể tìm đƣợc trong Zn một số đồng dƣ với mình (theo mod n). Các phép toán trong Zn nhƣ cộng, trừ, nhân, chia đều đƣợc thực hiện theo modulo n. Ví dụ: Z10 = {0, 1, 2, 3,…, 9} Tập Zn* = {p Zn gcd (n, p) = 1}, tức Zn* là tập hợp các số nguyên p thuộc Zn, nguyên tố cùng nhau với n.
Ta gọi tập đó là tập các thặng dư thu gọn theo mod n. Nếu n là một số nguyên tố thì: Zn* = { p Zn | 1 ≤ p ≤ n-1}. Ví dụ: Z2 = {0, 1} thì Z2* = {1} vì gcd (1, 2)= 1. Phần tử nghịch đảo trong Zn Định nghĩa: Cho a Zn.
Nghịch đảo “nhân” của a theo modullo n là một số nguyên x Zn sao cho ax ≡ 1 (mod n). Nếu tồn tại số x nhƣ vậy thì đó là giá trị duy nhất, và a đƣợc gọi là khả nghịch, nghịch đảo của a ký hiệu là a-1 mod n.7 ≡ 1 (mod 9) 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, a có nghịch đảo 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 nếu và chỉ nếu d chia hết b, trong trƣờng hợp các nghiệm nằm trong khoảng từ 0 đến n - 1, thì các nghiệm đồng dƣ theo modulo n/d. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Khái niệm trong đại số 1/.
Nhó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 ) ( x, y, z G) Tồn tại phần tử trung lập e G: e * x = x * e = x ( x G) Tồn tại phần tử nghịch đảo x’ G: x’ * x = x * x’ = e ( x G) 2/. Nhóm con Nhóm con là bộ các phần tử (S, *) là nhóm thỏa mãn các tính chất sau: S G, phần tử trung gian e S x, y S => x * y S 3/. Nhóm Cyclic Nhóm Cyclic: Là nhóm mà mọi phần tử x của nó đƣợc sinh ra từ một phần tử đặc biệt g G. Phần tử này đƣợc gọi là phần tử sinh (nguyên thủy), tức là: Với x G: n N mà gn = x.
Ví dụ: (Z+, +) là một nhóm cyclic có phần tử sinh là 1. Bộ phần tử sinh (Generator-tuple) {g1,., gk} đƣợc gọi là bộ phần tử sinh nếu mỗi gi là một phần tử sinh và những phần tử này khác nhau (gi ≠ gj nếu i ≠ j). Ví dụ: {3, 5} là bộ phần tử sinh của Z7*, bởi vì : 1 = 36 mod 7 = 56 mod 7; 2 = 32 mod 7 = 54 mod 7 3 = 31 mod 7 = 55 mod 7; 4 = 34 mod 7 = 52 mod 7 5 = 35 mod 7 = 51 mod 7; 6 = 33 mod 7 = 53 mod 7 2 không phải là phần tử sinh của Z7*, bởi vì: {2, 22, 23, 24, 25, 26} = {2, 4, 1, 2, 4, 1} <=> {1, 2, 4} LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 Tuy nhiên {1, 2, 4} là tập con của {1, 2, 3, 4, 5, 6} = Z7*. Do đó số 2 đƣợc gọi là “phần tử sinh của nhóm G(3)”, G(3) nghĩa là nhóm có 3 thành phần {1, 2, 4}.
Bài toán đại diện (“Presentation problem”) Gọi g là phần tử sinh của nhóm con G(q) thuộc Zn*. Bài toán logarit rời rạc liên quan đến việc tìm số mũ a, sao cho: a = loggh mod n (với h G(q)) Tổng quát, bài toán đại diện ([1]) là việc tìm kiếm logarit rời rạc a, nghĩa là liên quan đến việc tìm kiếm tập những con số gọi là "index-tuple". Bài toán đại diện là cho h thuộc G(q) tìm index-tuple {a1, ., ak}, của generator-tuple {g1, ., gk}, sao cho: g1 1 * g 2 2 *. , ak} đƣợc gọi là đại diện (representation).
Ví dụ: Cho tập Z23* thì ta có thể tìm đƣợc nhóm con: G(11) = {1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18} với những phần tử sinh gi là: 2, 3. {2, 3} là bộ phần tử sinh của nhóm con G(11) trong Z23*. Nhƣ vậy, với h = 13, bài toán đại diện là tìm a1 và a2 sao cho 2 a * 3a 13 mod 23. 1 2 Kết quả là: a1 = 2 và a2 = 2, vì 22 * 32 = 4*9 = 36 13 mod 23.
Hay a1 = 7 và a2 = 11, vì 27 * 311 = 128*177147 = 22674816 13 mod 23. Nhƣ vậy sẽ có nhiều kết quả khác nhau. Tuy nhiên có thể rút ra kết luận nếu có k thành phần trong đại diện {a1, ., ak}, thì sẽ có: nk-1 đại diện của h. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Khái niệm độ phức tạp tính toán 1/. Khái niệm bài toán Bài toán thƣờng đƣợc cho dƣới dạng: Input: Các dữ liệu vào của bài toán. Output: Các dữ liệu ra (Kết quả giải quyết yêu cầu của bài toán). Quan niệm trực quan về thuật toán Thuật toán [3] là một dãy hữu hạn các quy tắc (chỉ thị, mệnh lệnh) mô tả một quá trình tính toán (xử lý thông tin).
Theo đó, ứng với mỗi bộ dữ liệu vào (Input), cho ít nhất một kết quả (bộ dữ liệu ra: Output) Thuật toán đơn định (Deterministic): Có 1 kết quả ra Thuật toán không đơn định (NonDeterministic): Có số kết quả ra ≥ 2 3/. Độ phức tạp của thuật toán a/. Khái niệm độ phức tạp cực đại * Độ phức tạp về bộ nhớ trong trƣờng hợp xấu nhất: LA(n)= max {lA(e) | |e| ≤ n}. * Độ phức tạp thời gian trong trƣờng hợp xấu nhất: TA(n)= max {tA(e) | |e| ≤ n}.
Khái niệm độ 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 n0, c mà PT(n) ≤ c.