Chương 1: Các khái niệm cơ bản Trong chương này sẽ trình bày cơ sở toán học, tổng quan về mã hóa, tổng quan về thanh toán điện tử trong thương mại điện tử, tiền điện tử và một số lược đồ dùng trong hệ thống tiền điện tử Chương 2: Một số chữ ký đặc biệt Trong chương này trình bày chi tiết về thuật toán, sơ đồ chữ ký mù RSA, chữ ký mù nhóm, chữ ký mù bội, chữ ký không thể phủ định và ứng dụng của các chữ ký số trên. Chương 3: Thử nghiệm chương trình Tác giả đi vào phân tích bài toán ẩn danh đồng tiền điện tử và xây dựng chương trình Demo chữ ký mù cài đặt thuật toán để minh chứng cho kết quả của thuật toán giải quyết vấn đề ẩn danh trong thực tế. CÁC KHÁI NIỆM CƠ BẢN 1. TỔNG QUAN VỀ MẬT MÃ 1.1 Khái niệm mã hóa Để đảm bảo An toàn thông tin (ATTT) lưu trữ trong máy tính (giữ gìn thông tin cố định) hay đảm bảo An toàn thông tin trên đường truyền tin (trên mạng máy tính), người ta phải “Che giấu” các thông tin này.
“ Che ” thông tin (dữ liệu) hay “ Mã hóa” thông tin là thay đổi hình dạng thông tin gốc, và người khác khó nhận ra. Hệ mã hóa được định nghĩa là một bộ năm (P, C, K, E, D), trong đó: - P là một tập hữu hạn các bản rõ có thể. - C là một tập hữu hạn các bản mã có thể. - K là tập hữu hạn các khóa 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 E , dkd : P C 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ã.[6] Mã hoá nhằm đảm bảo các tính chất sau của thông tin: Tính bí mật (Confidentiality): thông tin chỉ được tiết lộ cho những ai được phép.
Tính toàn vẹn (Integrity): thông tin không thể bị thay đổi mà không bị phát hiện. Tính xác thực (Authentication): người gửi (hoặc người nhận) có thể chứng minh đúng họ. Tính không chối bỏ (Non-repudiation): người gửi hoặc nhận sau này không thể chối bỏ việc đã gửi hoặc nhận thông tin.2 Phân loại hệ mã hóa 1/ Hệ mã hóa khóa đối xứng Mã hóa khóa đối xứng là Hệ mã hóa mà biết được khóa lập mã thì có thể “dễ” tính được khóa giải mã và ngược lại. Đặc biệt một số Hệ mã hóa có khóa lập mã (ke) và khóa giải mã trùng nhau (kd), như Hệ mã hóa “dịch chuyển” hay DES.
2/ Hệ mã hóa khóa công khai - Hệ mã hóa khóa công khai hay Hệ mã hóa phi đối xứng do Diffie và Hellman phát minh vào những năm 1970. - Hệ mã hóa khóa phi đối xứng là Hệ mã hóa có khóa lập mã và khóa giải mã khác nhau (ke kd), biết được khóa này cũng “khó” tính được khóa kia. - Khóa lập mã cho công khai, gọi là khóa công khai (Public key). - Khóa giải mã giữ bí mật, còn gọi là khóa riêng (Private key) hay khóa bí mật.
Chọn khóa công khai b ( n) , nguyên tố cùng nhau (n). - Khóa bí mật a là phần tử nghịch đảo của b theo (n) : a * b 1(mod (n)) - Tập cặp khóa ( bí mật, công khai) K a, b / a, b Z n , a * b 1(mod (n)) Với bản rõ x P và bản mã y C , định nghĩa: - Hàm mã hóa: y ek ( x) xb mod n - Hàm giải mã: x d k ( y ) y a mod n .2 Hàm băm Hàm băm là thuật toán không dùng khóa để mã hóa ( Ở đây dùng thuật ngữ “băm” thay cho “ mã hóa”, nó có nhiệm “ lọc” ( băm ) tài liệu ( bản tin) và cho kết quả là một giá trị băm có kích thước cố định, còn gọi là “đại diện tài liệu” hay “ đại diện bản tin”, “ đại diện thông điệp”. 5 Hàm băm là hàm một chiều (One-way Hash) theo nghĩa giá trị hàm băm là duy nhất và từ giá trị băm này khó thể suy ngược lại được nội dung hay độ dài ban đầu của tài liệu gốc. Đặc tính của hàm băm 1/ Với tài liệu đầu vào ( Bản tin gốc) x, chỉ thu được giá trị băm duy nhất z = h(x) 2/ Nếu dữ liệu trong bản tin x bị thay đổi hay bị xóa thành bản tin x’ thì giá trị băm h( x ') h( x).
3/ Nội dung từ bản tin gốc khó thể suy ra từ giá trị băm của nó. Hai tính chất quan trọng nhấ của hàm băm là Tính một chiều và Tính duy nhất. Hiện nay, một số kỹ thuật băm được sử dụng phổ biến như: SHA-1, SHA- 256, SHA-384, SHA-512; MD-4, MD-5…[1], [6].2 CƠ SỞ TOÁN HỌC 1.1 Ước số , bội số Cho hai số nguyên a, b ( b 0 ). Nếu có một số nguyên q sao cho a=b*q, ta nói rằng a chia hết cho b, kí hiệu b\a.
Ta nói b là ước của a và a là bội của b. Ước chung lớn nhất, bội chung nhỏ nhất - Số nguyên d được gọi là ước chung của các số nguyên a1, a2,…,an, nếu nó là ước của tất cả các số đó. - Số nguyên m được gọi là bội chung của các số nguyên a1, a2,…,an, nếu nó là bội của tất cả các số đó. - Một ước chung d của tất cả các số nguyên a1, a2, …, an trong đó mọi ước chung của a1, a2, …, an đều là ước của d, thì d được gọi là ước chung lớn nhất (UCLN) của a1, a2, …, an.
Nếu gcd(a1, a2,…, an) - Nếu gcd(a1, a2, …, an) =1 thì các số a1, a2, …, an được gọi là nguyên tố cùng nhau. 6 - Một bội chung m>0 của các số nguyên a1, a2, …, an, trong đó mọi bội chung của a1, a2, …, an, đều là bội của m thì m được gọi là bội chung nhỏ nhất (BCNN) của a1, a2, …, an. - Tập Zn và Zn* + Zn={ 0, 1, 2, …, n-1} là tập các nguyên tố không âm < n. + Zn* = { e Z n , e là nguyên tố cùng nhau với n}.3 Thuật toán Euclide tìm ước chung lớn nhất Bài toán - Input: Cho hai số không âm a,b (a b) - Output: gcd(a,b) Thuật toán mô phỏng bằng ngôn ngữ lập trình Pascals Readln(a, b) While b>0 do Begin r:=a mod b; a:= b; b:=r; Thuật toán Euclide mở rộng Bài toán - Input: Cho hai số nguyên không âm a, b ( a b) - Output: d = gcd(a, b ) và hai số x, y sao cho ax + by = d Thuật toán ( Mô phỏ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 7 x2:=1; x1:= 0; y2:=0; y1:=1; While b>0 Do Begin q:= a div b; r:= a mod b; x:= x2 –q*x1; y:=y2-q*y1; a:= b; b:=r; x2:=x1; x1:= x; y2:=y1; y1:=y; end; d:=a; x:=x2; y:=y2; writeln ( d, x1, x2); end; 1.2 Quan hệ đồng dư 1.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 modul 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) Ví dụ: 17 5 ( mod 3) vì chia 17 và 5 cho 3 được cùng số dư là 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 1.2 Các tính chất của quan hệ đồng dư 1/ Quan hệ đồng dư là qua hệ tương đương 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) 2/ 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) 8 Tổng quát Có thể cộng hoặc trừ từng vế nhiều đồng dư thức theo cùng modulo m, ta được một đồng dư thức theo cùng modulo m tức là: k k Nếu ai bi ( mod m), i = 1, …, k thì: ti ai ti bi (mod m) với ti 1 i 1 i 1 3/ Tích các đồng dư ( a*b)( mod n) [( a mod n) * ( b mod n) ] (mod n) Tổng quát Có thể nhân từng vế với đồ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à k k Nếu ai bi ( mod m) với i= 1, …k, thì ta có ai bi (mod m) i 1 i 1 1.3 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 cùng với một số: a b ( mod m) ac bc ( mod m) với mọi c Z + Có thể nâng lũy thừa bậc nguyên không âm cho 2 vế của một đồng dư thức a b ( mod m) an bn ( mod m) với mọi n Z+ + Có thể chia 2 vế đồng dư thức cho một ước chung nguyên tố với modulo c\a, c\b, (c,m)=1, a b ( mod m) a/c b/c ( mod m).