ĐẠi học quốc gia hà NỘi trưỜng đẠi học công nghệ 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
tải về 0.65 Mb.
|
- Điều hướng trang này:
- 2.1.1. Các mô hình thanh toán điện tử.
Chương 1. CÁC KHÁI NIỆM CƠ BẢN
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/. 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)
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.
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 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)
(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/. 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.
UCLN (a, n) = 1 Phần tử a Zn có phần tử nghịch đảo. 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.
Cho p là số nguyên tố, g là phần tử nguyên thuỷ của Zp ,  “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).
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 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.
+ 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/. 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 xS.
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/. 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.
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:
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.
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. 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:
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, ...
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/. 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ớ.
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. 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.
Độ 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:
* 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.
Có 2 loại: + Hệ mã hóa khóa đối xứng + Hệ mã hóa khóa công khai
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.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ữ: R E N A I S S A N C E *Sinh khóa: 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 N A I S S A N C E (Dấu cách) 17 04 13 00 08 18 18 00 13 02 04 26 m1 m2 m3 m4 m5 m6 Theo phép lập mã: ci = mi b mod n = mi 71 mod 3233, ta nhận được: * Bản mã số: c1 c2 c3 c4 c5 c6 3106 0100 0931 2691 1984 2927 Theo phép giải mã: mi = ci a mod n = ci 791 mod 3233, ta nhận lại bản rõ.
- 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.
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.
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ử. 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
Sai, nếu y Sig k (x)
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/. 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)
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.
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ó.
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))
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.
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)
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 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
Ngân hàng lấy ngẫu nhiên r Zq Tính t = gr và gửi t cho Alice
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).
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.
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)
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.
Trong phần trước ta đã trình bày một số sơ đồ chữ ký điện tử. Trong các sơ đồ đó, việc kiểm thử tính đúng đắn của chữ ký là do người nhận thực hiện. Nhằm tránh việc nhân bản chữ ký để sử dụng nhiều lần, tốt nhất là để người gửi tham gia trực tiếp vào việc kiểm thử chữ ký. Điều đó được thực hiện bằng một giao thức kiểm thử, dưới dạng một giao thức mời hỏi và trả lời. Giả sử tài liệu cùng chữ ký từ G gửi đến N. Khi N yêu cầu G cùng kiểm thử chữ ký, thì một vấn đề nảy sinh là làm sao để ngăn cản G chối bỏ một chữ ký mà anh ta đã ký, G có thể tuyên bố rằng chữ ký đó là giả mạo ? Để giải quyết tình huống trên, cần có thêm giao thức chối bỏ, bằng giao thức này, G có thể chứng minh một chữ ký là giả mạo. Nếu G từ chối tham gia vào giao thức đó, thì có thể xem rằng G không chứng minh được chữ ký đó là giả mạo. Như vậy sơ đồ chữ ký không phủ định được gồm 3 phần: một thuật toán ký, một giao thức kiểm thử, và một giao thức chối bỏ. 1/. Sơ đồ. (Chaum - van Antverpen). Chuẩn bị các tham số: Chọn số nguyên tố p sao cho bài toán log rời rạc trong Zp là khó. p = 2*q+1, q cũng là số nguyên tố. Gọi P là nhóm nhân con của Zp* theo q (P gồm các thặng dư bậc hai theo mod p). Chọn phần tử sinh g của nhóm P cấp q. Đặt P = A = P, K = (p, g, a, h): a Z q*, h g a mod p Thuật toán ký: Dùng khoá bí mật k’ = a để ký lên x: Chữ ký là y = Sig k’ (x) = x a mod p.
Với x, y P, người nhận N cùng người gửi G thực hiện giao thức kiểm thử: 1/. N chọn ngẫu nhiên e1, e2 Zq* 2/. N tính c = y e1 h e2 mod p, và gửi cho G. 3/. G tính 4/. N chấp nhận y là chữ ký đúng, nếu d x e1 g e2 mod p * Giao thức chối bỏ: 1/. N chọn ngẫu nhiên e1, e2 Zq* 2/. N tính c = y e1 h e2 mod p, và gửi cho G. 3/. G tính 4/. N thử điều kiện d x e1 g e2 (mod p). 5/. N chọn ngẫu nhiên f1, f2 Zq*. 6/. N tính 7/. G tính 8/. N thử điều kiện D x f1 g f2 (mod p). 9/. N kết luận y là chữ ký giả mạo nếu:  (thay bằng g).
Ví dụ Ký trên x = 229 Chuẩn bị các tham số: Chọn số nguyên tố p = 467 = 2 * q + 1, q = 233 cũng là số nguyên tố. Chọn phần tử sinh của nhóm P là g = 4, (P là nhóm nhân con cấp q của Zp*). Đặt P = A = P, K = (p, g, a, h): a Z q*, h g a mod p Chọn khóa mật a = 121. Khóa công khai h g a mod p = 4121 mod 467 = 422.
Dùng khoá bí mật k’ = a để ký lên x = 229: Chữ ký là y = Sig k’ (x) = x a mod p = 229121 mod 467 = 9.
1/. N chọn ngẫu nhiên e1 = 48, e2 = 213 Zq* 2/. N tính c = y e1 h e2 mod p = 116 và gửi cho G. 3/. G tính 4/. N chấp nhận y là chữ ký đúng, nếu d x e1 g e2 mod p N thử điều kiện d x e1 g e2 mod p. Rõ ràng 235 229 48 * 4 213 (mod 467). N chấp nhận y = 9 đúng là chữ ký của G trên x = 229. * Giao thức chối bỏ: Giả sử G gửi tài liệu x = 226 với chữ ký y = 183. Giao thức chối bỏ thực hiện: 1/. N chọn ngẫu nhiên e1 = 47, e2 = 137 Zq* 2/. N tính c = y e1 h e2 mod p = 306, và gửi cho G. 3/. G tính 4/. N thử điều kiện d x e1 g e2 (mod p). Điều kiện trên không đúng vì 184 226 47 * 4 137 145 mod 467. N lại tiếp tục thực hiện bước 5 của giao thức. 5/. N chọn ngẫu nhiên f1 = 225, f2 = 19 Zq*. 6/. N tính 7/. G tính 8/. N thử điều kiện D x f1 g f2 (mod p). D = 426 trong khi x f1 g f2 (mod p) = 226 225 * 4 19 295 mod 467. Điều kiện 8 là đúng, nên N thực hiện bước 9: 9/. N kết luận y là chữ ký giả mạo nếu:
N tính giá trị của 2 vế đồng dư (d* -e2)f1 (184 * 4 -137)225 79 mod 467 (D* -f2)e1 (426 * 4 -19)47 79 mod 467 Hai giá trị đó bằng nhau. Kết luận chữ ký y là giả mạo
Các sơ đồ chia sẻ bí mật (Secret Sharing Schemes - SSS), được phát minh một cách độc lập bởi Blakley và Shamir. Một trong những mục đích của việc chia sẻ bí mật là để quản lý khóa an toàn. Ý tưởng cơ bản của việc chia sẻ bí mật là phân chia một khóa bí mật thành các mảnh và phân phối các mảnh này cho những người khác nhau, sao cho một nhóm con của những người này có thể kết hợp với nhau để tìm ra khóa ban đầu. Sơ đồ chia sẻ bí mật gọi là lược đồ (k ,n) với k, n là các số nguyên. Trong sơ đồ, có một người quản lý (Giả sủ là Alice) và n thành viên. Alice phân chia bí mật thành n phần và đưa cho mỗi thành viên một phần sao cho bất kỳ k thành phần nào được kết hợp với nhau cũng có thể tìm ra khóa bí mật, nhưng bất kỳ (k-1) thành phần nào kết hợp với nhau cũng không thể tìm ra khóa bí mật. Các mảnh được gọi là share hoặc shadow (dấu vết). Các giá trị khác nhau cho k và n phản ánh sự tương quan giữa tính an toàn và tính tin cậy của hệ thống. Một sơ đồ chia sẻ bí mật là hoàn hảo nếu bất kỳ nhóm nào với tối đa (k-1) thành viên trong số n thành viên cũng không thể tìm được khóa mật. Giá trị của k được gọi là ngưỡng. các giá trị f(i) (1 ≤ i ≤ n) cho các thành viên, trừ f(0). Như vậy, k thành viên kết hợp lại với nhau có thể tìm ra được bí mật vì khi đó chúng ta có một hệ k phương trình k ẩn. Ưu điểm của sơ đồ này là tính hiệu quả và tính an toàn mà không cần bổ sung và Alice có thể thêm vào sơ đồ một thành viên mới.
Sơ đồ chia sẻ bí mật có thể xác minh ( Veriffy Secret Sharing - VSS) hướng đến giải quyết vẫn đề nêu trên. Có nhiều đề xuất về sơ đồ VSS, ở đây trình bày sơ đồ của Okamoto và Yamamoto. Gọi s là giá trị bí mật, k là ngưỡng, n là số thành viên. Alice chọn đa thức ngẫu nhiên: f(x) = (s + a1x + a2x2 + ….+ ak-1xk-1) mod q Alice phân phối f(j) cho thành viên j, 1 ≤ j ≤ n Alice chọn p sao cho q|(p-1), phần tử sinh ngẫu nhiên g Zp* cấp q và tính: c0 = gs mod p c1 = ga1 mod p . ........ ck-1 = gak-1 mod p Thành viên nào cũng có thể kiểm tra việc phân phối của Alice có trung thực hay không Ver = true gf(j) = c0 c1j c2j2 …..ck-1 jk-1 Vì: c0 c1j c2j2 …..ck-1 jk-1 = gs ga1j …..gak-1 jk-1 = gf(j)
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: 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). Dù chỉ là một sự thay đổi nhỏ, ví dụ chỉ thay đổi 1 bit dữ liệu của bản tin gốc x, thì giá trị băm h(x) của nó cũng vẫn thay đổi. Điều này có nghĩa là: hai thông điệp khác nhau, thì giá trị băm của chúng cũng khác nhau. 3). Nội dung của bản tin gốc “khó” thể suy ra từ giá trị hàm băm của nó. Nghĩa là: với thông điệp x thì “dễ ” tính được z = h(x), nhưng lại “khó” tính ngược lại được x nếu chỉ biết giá trị băm h(x) (kể cả khi biết hàm băm h).
1). Hàm băm không va chạm yếu. Hàm băm h được gọi là không va chạm yếu, nếu cho trước bức điện x, “khó” thể tính toán để tìm ra bức điện x’ x mà h(x’) = h(x). 2). Hàm băm không va chạm mạnh. Hàm băm h được gọi là không va chạm mạnh nếu “khó” thể tính toán để tìm ra hai bức thông điệp khác nhau x’ và x (x’ 3) Hàm băm một chiều. Hàm băm h được gọi là hàm một chiều nếu khi cho trước một bản tóm lược thông báo z thì “khó thể” tính toán để tìm ra thông điệp ban đầu x sao cho h(x) = z.
Khâu quan trọng nhất của Thương mại điện tử (TMĐT) là việc thanh toán, bởi vì mục tiêu cuối cùng của cuộc trao đổi thương mại là người mua nhận được những cái gì cần mua và người bán nhận được số tiền thanh toán. Thanh toán là một trong những vấn đề phức tạp nhất của TMĐT. Hoạt động TMĐT chỉ phát huy được tính ưu việt của nó khi áp dụng được hình thức thanh toán điện tử (TTĐT). TTĐT là việc thanh toán tiền thông qua các thông điệp điện tử (Electronic message) thay cho việc thanh toán bằng tiền Sec hay tiền mặt. Bản chất của mô hình TTĐT cũng là mô phỏng lại mô hình thanh toán truyền thống, nhưng các thủ tục giao dịch, các thao tác xử lý dữ liệu, quá trình chuyển tiền… tất cả đều được thực hiện thông qua mạng máy tính, được nối bằng các giao thức chuyên dụng.
Trong mô hình này, thời điểm tiền mặt được rút ra khỏi tài khoản bên mua để chuyển sang bên bán, xảy ra ngay (pay-now) hoặc sau (pay-later) giao dịch mua bán. Hoạt động của hệ thống dựa trên nguyên tắc Tín dụng (Credit crendental). Nó còn được gọi là mô hình mô phỏng Séc (Cheque-like model). 2.1.1.2. Mô hình trả tiền trước. Trong mô hình này, khách hàng liên hệ với ngân hàng (hay công ty môi giới – Broker) để có được chứng từ do ngân hàng phát hành. Chứng từ hay Đồng tiền số này mang dấu ấn của ngân hàng, được đảm bảo bởi ngân hàng và do đó có thể dùng ở bất cứ nơi nào đã có xác lập hệ thống thanh toán với ngân hàng này. Để đổi lấy chứng từ của ngân hàng, tài khoản của khách hàng bị triết khấu đi tương ứng với giá trị của chứng từ đó. Như vậy, khách hàng đã thực sự trả tiền trước khi sử dụng chứng từ này để mua hàng và thanh toán.Chứng từ ở đây không phải do khách hàng tạo ra, không phải dành cho một cuộc mua bán cụ thể, mà do ngân hàng phát hành và có thể sử dụng vào mọi mục đích thanh toán. Vì nó có thể sử dụng giống như tiền mặt, do đó mô hình này còn được gọi là mô hình mô phỏng tiền mặt (Cash-like model). Khi có người mua hàng tại cửa hàng và thanh toán bằng chứng từ như trên, cửa hàng sẽ kiểm tra tính hợp lệ của chúng, dựa trên những thông tin đặc biệt do ngân hàng tạo ra trên đó. Cửa hàng có thể chọn một trong hai cách: Hoặc là liên hệ với ngân hàng để chuyển vào tài khoản của mình số tiền trước khi giao hàng (deposit-now), hoặc là chấp nhận và liên hệ chuyển tiền sau vào thời gian thích hợp (deposit-later). Trường hợp riêng của mô hình mô phỏng tiền mặt là mô hình “tiền điện tử” (Electronic Cash). Hiện tại hầu hết các dịch vụ mua bán hàng hoá trên mạng đều sử dụng hình thức thanh toán bằng thẻ tín dụng (Credit card). Người sử dụng cần nhập vào các thông tin: tên người sử dụng, mã số thẻ, ngày hết hạn của thẻ. Nhưng vì thẻ tín dụng được dùng phổ biến cho các thanh toán khác nhau, nên những thông tin trên có nhiều người biết. Thực tế hiện nay, các gian lận về thẻ trên Internet chiếm 6-7% tổng số các giao dịch thẻ ở các nước châu Âu, tỷ lệ này ở châu Á là 10%. Tại Việt nam, dịch vụ thẻ tín dụng mới sử dụng cuối năm 1996, nhưng đến nay, tỷ lệ các giao dịch gian lận trên tổng số các giao dịch là hơn 10%. Trên thế giới hiện nay, nhu cầu về thương mại điện tử rất phổ biến, nhưng các vấn đề hạ tầng trong thanh toán điện tử vẫn chưa được giải quyết tương xứng và đáp ứng được các đòi hỏi đặt ra. Việc nghiên cứu xây dựng các hệ thống thanh toán điện tử để đảm bảo an toàn thông tin trong các dịch vụ thương mại điện tử là một hướng nghiên cứu rất cần thiết hiện nay. Xây dựng các hệ thống thanh toán điện tử về mặt kỹ thuật chính là ứng dụng các thành tựu của lý thuyết mật mã. Các mô hình thanh toán sử dụng các giao thức mật mã được xây dựng để đảm bảo an toàn cho việc giao dịch thông tin giữa các bên tham gia.
|
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)
.
Đúng, nếu y = Sig k (x)
và gửi cho N.
và gửi cho G.
và gửi cho N.
x) mà có h(x’) = h(x).