CÁC KHÁI NIỆM CƠ BẢN
MỘT SỐ KHÁI NIỆM TOÁN HỌC
1.1.1 Các khái niệm trong số học
Số nguyên tố là số nguyên dương chỉ chia hết cho một và chính nó
Các số 2, 3, 5, 7, 11, 13, 17, 19, 23 là số nguyên tố Số 2 là số nguyên tố chẵn duy nhất
+ Nếu p là số nguyên tố và p|ab thì ta có a|p hoặc b|p hoặc cả a và b chia hết cho p + Có vô số, 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: (m,n)=1 Ví dụ: 9 và 14
Cho hai số nguyên a, b Z, b 0 Nếu có một số nguyên q sao cho a=b*q, thì ta nói rằng a chia hết cho b, ký hiệu b|a Ta nói b la ƣớc của a, và a là bội của b
+ Cho a=6, b=2, ta có 6=2*3, ký hiệu 2|6 Ở đấy 2 là ƣớc của 6 và 6 là bội của 2
Khái niệm ước chung lớn nhất:
Số nguyên d đƣợc gọi là ƣớc chung của các số nguyên a1, a2,…,a n ,nếu nó là ƣớc của tất cả các số đó
Ước chung lớn nhất (ƢCLN) của các số nguyên a1, a2,…,an là một số d > 0, sao cho mọi ước chung của a1, a2,…,an đều là ước của d Ký hiệu ƢCLN(a1, a2,…,an) hay gcd(a1, a2,…,an) được sử dụng để biểu thị giá trị này.
+ d = gcd(a1, a2,…,a n ) khi và chỉ khi tồn tại các số x1, x2,…,x n sao cho: d = a 1 x 1 + a 2 x 2 + ….+ a n x n Đặc biệt: a 1 , a2,…,a n nguyên số cùng nhau tồn tại các số x1, x2,…,x n sao cho: 1 = a1x1 + a2x2+ ….+ a n xn
+ gcd(m.a1, m.a2,…, m.an) = m* gcd(a1, a2,…,an) (với m )
3/.Thuật toán Euclide tìm ƣớc chung lớn nhất
* Dữ liệu vào: Cho hai số nguyên không âm a,b, a b
Ví dụ : a= 30, b= 18 gcd(30,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) = 6
Bảng 1: Mô tả các bước tính gcd(30,18) a b r a = b.q + r
Cho n 1, đặt (n) là các số nguyên trong khoảng [1,n] và nguyên tố cùng nhau với n Hàm nhƣ thế đƣợc gọi là hàm phi-Euler
= 10 do 11 là số nguyên tố nên = n-1
+ Nếu n là số nguyên tố thì (n) = n-1
+ Nếu n = p1 e1 p2 e2 …pk ek là thừa số nguyên tố của n thì : (n) = n(1 - )(1 - )…(1 - )
Nếu a và b là các số nguyên, a được gọi là đồng dư với b theo modulo n, ký hiệu là a ≡ b (mod n), khi a và b có cùng số dư khi chia cho n hoặc (a-b) chia hết cho n Số nguyên n được gọi là modulo trong trường hợp đồng dư này.
5 7(mod 2) vì: 5 mod 2 = 1 và 7 mod 2 = 1
3/.Một số tính chất của đồng dƣ
Cho a, a 1 , b, b 1 , c Z Ta có các tính chất sau:
a b (mod n), nếu và chỉ nếu a và b có cùng số dƣ khi chia cho n hoặc (a-b)|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), 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)
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
Cho a cố định đồng dư với n trong không gian Z vào các lớp tương đương
Nếu a = qn + r, trong đó 0 r n thì a r (mod n)
Mỗi số nguyên a có một thặng dư nhỏ nhất theo modulo n, là số nguyên duy nhất trong khoảng từ 0 đến n-1 Số a và thặng dư r thuộc cùng một lớp tương đương, do đó r có thể được sử dụng để đại diện cho lớp tương đương này.
1.1.2.Các khái niệm trong đại số
Các số nguyên theo modulo n, ký hiệu là Zn, là tập hợp các số nguyên {0, 1, 2, , n-1} Tập Zn đại diện cho tất cả các lớp tương đương theo modulo n Trong tập Zn, các phép toán cộng, trừ và nhân được thực hiện theo quy tắc modulo n.
Z 25 = {0, 1, 2, 3,…, 24} Trong Z 25 : 13 + 16 = 4, vì 13 +16 = 29 4 (mod 25) Tương tự : 13*16 = 8 trong Z25
3/.Các phép toán trong không gian modulo
Cho n là các số nguyên dương Các phần tử trong Zn được thể hiện bởi các số nguyên{0, 1, 2, 3,…,n-1} Nhận xét rằng: nếu a, b Zn thì:
Phép cộng và phép trừ modulo có thể thực hiện mà không cần chia dài, với công thức (a + b) mod n Phép nhân modulo giữa a và b được thực hiện bằng cách nhân a với b như các số nguyên bình thường, sau đó lấy phần dư khi chia cho n Để tính nghịch đảo trong Z n, có thể sử dụng thuật toán Euclid mở rộng.
Input : 2 số nguyên không âm a,b (a b)
Output : d=gcd(a,b) và x,y thỏa mãn ax + by = d
4/.Phần tử nghịch đảo trong Z n Định nghĩa:
Cho a Zn , nghịch đảo của a là số nguyên 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 là a -1
Một phần tử có phần tử nghịch đảo, gọi là khả nghịch
+ Cho a, b Zn , a/b (mod n) = a.b -1 (mod n) đƣợc xác định khi và chỉ khi b là khả nghịch theo modulo của n
+ a Zn , a là khả nghịch khi và chỉ khi gcd(a, n) = 1
Ví dụ: Các phần tử khả nghịch trong Z9 là 1, 2, 4, 5, 7 và 8
Cho d = gcd(a,n) Phương trình đồng dư a.x ≡ b (mod n) sẽ có nghiệm x nếu và chỉ nếu d chia hết cho b Nếu các nghiệm nằm trong khoảng từ 0 đến n-1, thì các nghiệm đồng dư sẽ theo modulo n/d.
Ví dụ: 4 -1 = 7 (mod 9) vì 4.7 1 (mod 9)
Nhóm nhân (phép nhân) của tập Zn ký hiệu là Zn
* = {a Zn | gcd(a,n) = 1} Đặc biệt, nếu n là một số nguyên tố thì Z n * = {a|1 a n-1}
Cấp của Zn * đƣợc định nghĩa là số phần tử trong Zn *
|) Theo định nghĩa hàm phi – Euler ta có | Zn *
+ Định lý Euler : Nếu a Zn
Nếu n là tích của các số nguyên tố phân biệt và r s(mod n), thì a^r ≡ a^s (mod n) với mọi số nguyên a Điều này có nghĩa là khi làm việc với các số theo modulo của một số nguyên tố p, số mũ có thể được giảm theo modulo n.
Cho p là số nguyên tố:
+ Định lý Fermat : Nếu gcd(a,p) = 1 thì a p-1 1 (mod p)
Nếu r s (mod p-1), thì a^r ≡ a^s (mod p) với mọi số nguyên a Điều này có nghĩa là khi làm việc với các số theo modulo một số nguyên tố p, số mũ có thể được giảm theo modulo p-1 Ngoài ra, a^p ≡ a (mod p) cho mọi số nguyên a.
Trong nhóm Z n * với cấp độ (n), phần tử a được gọi là phần tử sinh hay phần tử nguyên thủy Nếu Z n * có ít nhất một phần tử sinh, thì nhóm này được gọi là nhóm cyclic Đặc biệt, nếu n là số nguyên tố, cấp của nhóm sẽ là (n) = n-1.
+ Nếu là phần tử sinh của Zn
+ Giả sử là một phần tử sinh của Zn
* Khi đó , b = mod n cũng là một phần tử sinh của Z n * khi và chỉ khi gcd(i, (n)) = 1 Và sau đó nếu Z n * là nhóm cyclic thì số phần tử sinh sẽ là ( (n))
+ Z n * là phần tử sinh của Z n * khi và chỉ khi ! 1 (mod n) với mỗi số chia nguyên tố của (n)
* có phần tử sinh khi và chỉ khi n = 2, 4, hay 2 khi p là số nguyên tố lẻ và k 1 Còn nếu p là số nguyên tố thì chắc chắn có phần tử sinh
Một số a được gọi là thặng dư bậc hai theo modulo n nếu tồn tại một x thuộc Z_n* sao cho x^2 ≡ a (mod n) Ngược lại, nếu không tồn tại x thỏa mãn điều kiện này, a được gọi là bất thặng dư bậc hai theo modulo n Tập hợp các số bất thặng dư bậc hai được ký hiệu là
Chú ý : Vì định nghĩa 0 Zn * nên 0 Qn và 0
Cho n là tích của hai số nguyên tố p và q Khi đó, a Zn * là một thặng dƣ bậc 2 theo modulo n khi và chỉ khi a Qn và a Ta có :
1.1.2.5 Khái niệm nhóm, nhóm con, nhóm Cyclic
Nhóm: là bộ các phần tử (G,*) thỏa mãn các tính chất sau:
Tồn tại phần tử trung gian 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
Nhóm con: là các bộ phần tử (S,*) là nhóm thỏa mãn các tính chất sau:
Nhóm Cyclic là nhóm trong đó mọi phần tử x được sinh ra từ một phần tử đặc biệt g, được gọi là phần tử nguyên thủy.
(Z + , *) là một nhóm Cyclic có phần tử sinh là 1
Cấp của nhóm đƣợc định nghĩa là số các phần tử trong nhóm đó
Nhƣ vậy, nhóm Zn * có cấp (n)
Nếu p là số nguyên tố thì nhóm Zp
*, cấp của a ký hiệu là ord(a) được định nghĩa là số nguyên dương nhỏ nhất t thỏa mãn: a t 1 (mod n)
(21) = |Z 21 * | và cấp của từng phần trong Z 21 * là: a Z 21 * 1 2 4 5 8 10 11 13 16 17 19 20
1.1.3 Khái niệm độ phức tạp của thuật toán
Thuật toán là phương pháp giải quyết một bài toán, có thể hiểu theo hai cách: trực giác và hình thức.
Thuật toán có thể được hiểu một cách trực giác là một chuỗi hữu hạn các quy tắc và chỉ thị mô tả quy trình tính toán Mục tiêu của thuật toán là chuyển đổi dữ liệu đầu vào (Input) thành kết quả đầu ra (Output) cho một bài toán cụ thể.
+ 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
+ Phân loại : 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
1.1.3.2.Khái niệm độ phức tạp của thuật toán
Chi phí của thuật toán : (tính theo một bộ dữ liệu vào)
Chi phí cho một quá trình tính toán bao gồm chi phí về thời gian và bộ nhớ Chi phí thời gian phản ánh thời gian cần thiết để thực hiện quá trình tính toán Đối với thuật toán tương tự Algol, chi phí thời gian được xác định bởi số lượng 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 quy trình tính toán
Thuật toán A là một phương pháp xử lý, trong đó e đại diện cho dữ liệu đầu vào đã được mã hóa Khi áp dụng thuật toán A trên dữ liệu e, nó sẽ trả về một giá trị xác định.
TA(e) là giá thời gian và IA(e) là giá bộ nhớ Độ phức tạp về bộ nhớ: (Trong trường hợp xấu nhất)
LA(n) = max {IA(e), với |e| n}, n là kích thước đầu vào của thuật toán
17 Độ phức tạp thời gian: (Trong trường hợp xấu nhất)
VẤN ĐỀ VỀ MÃ HÓA
Mã hóa đã có lịch sử lâu dài trong các lĩnh vực ngoại giao, chính trị và quân sự Tuy nhiên, chỉ sau khi Claude Shannon công bố bài báo “Lý thuyết truyền tin trong các hệ thống bảo mật”, mã hóa mới được công nhận là một môn khoa học thực thụ Trước đó, các vấn đề liên quan đến mã hóa và mật mã chủ yếu được coi là một loại “nghệ thuật”.
Mã hóa đóng vai trò quan trọng trong bảo mật thông tin, giúp tài liệu trở nên an toàn hơn Thay vì truyền tải dữ liệu thô trên những đường truyền được bảo vệ nghiêm ngặt, việc sử dụng mã hóa cho phép truyền tải tài liệu qua bất kỳ kênh nào mà không lo ngại về việc bị đánh cắp Ngay cả khi dữ liệu bị rơi vào tay kẻ xấu, chúng cũng không thể hiểu được nội dung nhờ vào quá trình mã hóa.
- Thuật toán mã hóa/giải mã: Là thuật toán dùng để chuyển thông tin thành dữ liệu mã hóa hoặc ngƣợc lại
- Khóa : Là thông tin mà thuật toán mã/giải mã sử dụng để mã/giải mã thông tin
Mỗi khi thông tin được mã hóa, chỉ những người sở hữu khóa thích hợp mới có khả năng giải mã Nếu không có khóa, việc sử dụng cùng một thuật toán giải mã cũng không thể phục hồi thông tin ban đầu Điều này nhấn mạnh rằng mã hóa phụ thuộc vào khóa, không phải vào thuật toán mã và giải mã.
Với việc sử dụng thư điện tử phổ biến mà không áp dụng các công cụ mã hóa, bảo mật và chữ ký điện tử, nhiều rủi ro có thể phát sinh.
+ Không chỉ có người nhận mà người khác có thể đọc được thông tin
+ Thông tin mà ta nhận được có thể không phải của người gửi đúng đắn
+ Bị nghe trộm: Thông tin được truyền đi trên đường truyền có thể bị ai đó
“xâm nhập” vào lấy ra tuy nhiên vẫn đến được người nhận mà không bị thay đổi
+ Bị lấy cắp: Thông tin bị lấy ra hoàn toàn không đến được người nhận
Thông tin có thể bị thay đổi trong quá trình truyền tải, khiến cho người nhận nhận được dữ liệu đã bị chỉnh sửa mà không hay biết Để bảo vệ thông tin, trước khi gửi đi, nó sẽ được mã hóa và sau đó được giải mã khi tới tay người nhận Việc sử dụng các thuật toán mã hóa đặc biệt đảm bảo rằng chỉ người nhận có quyền truy cập mới có thể đọc được nội dung, trong khi thông tin có thể bị theo dõi và đánh cắp trong quá trình truyền tải Khi thông tin được mã hóa, kết quả là nội dung trở nên "không có ý nghĩa" đối với kẻ tấn công Để hiểu được thông điệp, kẻ tấn công cần phải giải mã, và nếu chi phí giải mã cao hơn giá trị thông tin, thì bảo mật được coi là thành công.
Các thuật toán mã hóa thông tin có thể được phân loại thành hai loại chính: mã hóa khóa đối xứng và mã hóa khóa bất đối xứng.
1.2.2 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
Hệ mã hóa khóa đối xứng mã hóa và giải mã nhanh hơn hệ mã hóa khóa bất đối xứng
+ Mã hóa khóa đối xứng chƣa thật an toàn với lý do sau:
Người mã hóa và người giải mã phải có “chung” một khóa
Khóa phải đƣợc giữ bí mật tuyệt đối, vì biết khóa này “dễ” xác định khóa kia và ngƣợc lại
Vấn đề thỏa thuận khóa và quản lý khóa chung là một thách thức phức tạp, đòi hỏi sự đồng thuận giữa người gửi và người nhận về khóa Việc thay đổi khóa gặp khó khăn và có nguy cơ bị lộ Do đó, khóa chung cần được truyền tải qua kênh an toàn để đảm bảo tính bảo mật.
Mặt khác khi hai người (lập mã, giải mã) cùng biết “chung” một bí mật, thì càng khó giữ đƣợc bí mật
3/.Nơi sử dụng hệ mã hóa khóa đối xứng
Hệ mã hóa khóa đối xứng là phương pháp phổ biến trong các môi trường mà khóa chung có thể được chia sẻ dễ dàng, như trong mạng nội bộ Phương pháp này thường được sử dụng để mã hóa các bản tin lớn do tốc độ mã hóa và giải mã nhanh hơn so với hệ mã hóa khóa công khai.
*Một số hệ mã hóa khoá đối xứng:
Hệ mã hóa khóa đối xứng cổ điển bao gồm nhiều phương pháp như hệ mã hóa dịch chuyển, hệ mã hóa thay thế, hệ mã hóa AFFINE, hệ mã hóa VIGENERE, hệ mã hóa hoán vị cục bộ và hệ mã hóa HILL Những phương pháp này đều sử dụng cùng một khóa để mã hóa và giải mã thông tin, giúp đảm bảo tính bảo mật trong việc truyền tải dữ liệu.
+ Hệ mã hóa khóa đối xứng DES
DES: 56 bit, không an toàn.Có thể dễ dàng bẻ khóa trong vài phút
Triple DES, DESX, GDES, RDES: Mở rộng độ dài khóa ở mã DES lên 168 bit
1.2.3 Mã hóa khóa bất đối xứng
Mã hóa bất đối xứng là phương pháp mã hóa sử dụng hai loại khóa khác nhau: khóa lập mã (ke) và khóa giải mã (kd) Việc biết một trong hai khóa không giúp xác định khóa còn lại, do đó chỉ cần bảo mật khóa giải mã, trong khi khóa lập mã có thể được công khai Hệ thống mã hóa này thường được gọi là hệ mã hóa khóa công khai.
Hệ mã hóa công khai có ưu điểm nổi bật là cho phép thuật toán được viết một lần và sử dụng nhiều lần cho nhiều người dùng khác nhau, trong đó mỗi người chỉ cần bảo vệ bí mật khóa riêng của mình.
Khi đã biết các tham số ban đầu của hệ mã hóa, việc tính toán cặp khóa công khai và khóa bí mật cần phải thực hiện một cách dễ dàng, tức là trong thời gian đa thức.
Người gửi bản rõ P và khóa công khai, thì “dễ” tạo ra bản mã C
Người nhận bản mã C và khóa bí mật, thì “dễ” giải được thành bản rõ P
+ Người mã hóa dùng khóa công khai, người giải mã giữ khóa bí mật Khả năng lộ khóa bí mật nhỏ hơn vì chỉ có một người giữ gìn
Nếu thám mã biết khóa công khai, cố gắng tìm khóa bí mật, thì chúng phải đương đầu với bài toán “khó”
Nếu kẻ thám mã nắm giữ khóa công khai và bản mã C, việc xác định bản rõ P trở thành một bài toán "khó", với số phép trừ rất lớn, khiến cho việc giải mã trở nên không khả thi.
Hệ mã hóa khóa công khai: mã hóa và giải mã chậm hơn hệ mã hóa đối xứng
3/.Nơi sử dụng hệ mã hóa khóa bất đối xứng
Hệ mã hóa khóa bất đối xứng được sử dụng chủ yếu trên các mạng công khai như Internet, nơi việc trao đổi khóa bí mật gặp nhiều khó khăn Đặc trưng nổi bật của hệ thống này là khả năng gửi khóa công khai và bản mã (Ciphertext) qua kênh truyền tin không an toàn.
Có biết cả khóa công khai và bản mã, thì thám mã cũng không dễ khám phá đƣợc bản rõ
* Các đặc điểm của hệ mật mã khóa công khai:
Khi đã nắm rõ các điều kiện ban đầu, việc xác định cặp khóa công khai và bí mật sẽ trở nên đơn giản và được thực hiện trong thời gian đa thức.
Người gửi G có khóa công khai, có bản tin P thì có thể tạo ra bản mã C nhanh gọn, nghĩa là trong thời gian đa thức
Người nhận N khi nhận được bản mã hóa C và khóa bí mật có thể giải mã bản tin dễ dàng trong thời gian đa thức
VẤN ĐỀ VỀ CHỮ KÝ SỐ (digital signature)
Việc sử dụng mật mã ngày càng trở nên phổ biến không chỉ trong quân đội mà còn trong thương mại và các mục đích cá nhân Do đó, các đoạn tin và tài liệu điện tử cần có chữ ký tương tự như các tài liệu giấy.
Chữ ký điện tử giống như chữ ký truyền thống, xác nhận danh tính người gửi thư Nó sử dụng thuật toán mã không đối xứng để định danh và bảo vệ văn bản Việc ứng dụng chữ ký điện tử và công nhận giá trị pháp lý của nó là điều kiện thiết yếu trong thương mại điện tử Trong khi giả mạo chữ ký viết tay hoặc dấu là khó khăn, việc làm giả thông tin lại dễ dàng hơn Do đó, việc quét chữ ký hoặc con dấu của công ty để xác nhận tài liệu không phải là giải pháp hiệu quả.
Khi cần ký một văn bản hoặc tài liệu, bước đầu tiên là tạo chữ ký và thêm vào thông điệp Thủ tục này có thể được hình dung như sau:
Phần mềm mã hóa mà bạn sử dụng sẽ phân tích nội dung văn bản và tạo ra một chuỗi thông tin độc nhất cho văn bản đó Mọi thay đổi trong văn bản đều sẽ dẫn đến sự thay đổi tương ứng của chuỗi thông tin này.
Phần mềm sẽ sử dụng khóa mật của bạn để mã hóa chuỗi thông tin và thêm nó vào cuối văn bản như một động tác ký Điều này cho thấy rằng chúng ta không mã hóa nội dung văn bản mà chỉ thực hiện một hành động ký xác nhận.
Khi nhận văn bản, người nhận sẽ lặp lại quá trình tạo chuỗi thông tin đặc trưng và sử dụng mã công khai đã gửi để kiểm tra tính hợp lệ của chữ ký điện tử cũng như sự toàn vẹn của nội dung thông điệp Thuật toán mã hóa không đối xứng nổi tiếng nhất, RSA, được đặt theo tên ba tác giả Rivest, Shamir và Adleman.
1.3.2.Quá trình tạo ra chữ ký điện tử
1) Tạo một câu ngắn gọn để nhận dạng – ví dụ nhƣ “Tôi là sinh viên”
2) Mã hóa nó bằng khóa bí mật của mình tạo ra chữ ký điện tử
3) Gắn chữ ký điện tử vào thông điệp cần gửi rồi mã hóa toàn bộ bằng khóa công khai của người nhận
5) Người nhận sẽ dùng khóa bí mật của mình để giải mã thông điệp và lấy chữ ký ra sau đó họ sẽ giải mã chữ ký này bằng khóa công khai của người gửi.Chỉ người nào gửi có khóa bí mật phù hợp mới có thể tạo ra chữ ký mà người nhận giải mã thành công Do đó người nhận có thể định danh người gửi
1.3.3 Hàm băm sử dụng trong chữ ký điện tử
Hàm băm chuyển đổi thông điệp thành một giá trị ngắn gọn và cố định, được gọi là "đại diện" hay "bản tóm tắt" Mỗi thông điệp có một đại diện duy nhất, và việc tìm hai thông điệp khác nhau có cùng một đại diện qua hàm băm là rất khó khăn.
Hàm băm kết hợp với chữ ký điện tử tạo ra một chữ ký an toàn hơn, giúp ngăn chặn việc cắt/dán và kiểm tra tính toàn vẹn của thông điệp Các bước để tạo ra chữ ký điện tử bao gồm:
1) Đƣa thông điệp cần gửi qua hàm băm tạo ra đại diện cho thông điệp đó
2) Mã hóa đại diện bằng khóa bí mật của người gửi để tạo ra chữ ký điện tử
3) Mã hóa toàn bộ thông điệp và chữ ký bằng khóa công khai của người nhận và gửi đi
Người nhận sử dụng khóa bí mật để giải mã thông điệp và khóa công khai của người gửi để xác thực chữ ký, từ đó lấy đại diện của thông điệp Tiếp theo, họ áp dụng hàm băm để tạo ra đại diện mới và so sánh với đại diện đã nhận Nếu hai đại diện giống nhau, người nhận có thể xác định danh tính người gửi và kiểm tra tính toàn vẹn của thông điệp.
*Một số hàm băm thường gặp:
- MD5(Message Digest) : 128 bit, nhanh, đƣợc sử dụng rộng rãi
- SHA (Secure Hash Algorithm) : 160 bit.
PHƯƠNG PHÁP CHỨNG MINH KHÔNG TIẾT LỘ THÔNG TIN
KHÁI NIỆM CHỨNG MINH KHÔNG TIẾT LỘ THÔNG TIN
2.1.1 Khái niệm chứng minh không tiết lộ thông tin (CM KTLTT)
Hệ thống chứng minh không tiết lộ thông tin cho phép một đối tượng thuyết phục đối tượng khác tin vào một điều gì đó mà không tiết lộ phương pháp chứng minh.
Ta xét một ví dụ đơn giản sau:
Trong trò chơi bài, P và V cùng tham gia, trong đó P đặt 2 quân bài úp và khẳng định đó là “át cơ” và “2 cơ” P sau đó yêu cầu V chọn quân bài “át cơ”.
Trước khi chọn quân "át cơ", V yêu cầu P chứng minh rằng hai quân bài đó thực sự là "át cơ" và "2 cơ" Nếu P lật hai quân bài lên để chứng minh, trò chơi sẽ kết thúc vì V đã nhìn thấy chúng và có thể dễ dàng chọn quân bài "át cơ".
P có thể chứng minh rằng hai quân bài trên tay mình là “át cơ” và “2 cơ” mà không cần lật chúng lên, bằng cách đưa 50 quân bài còn lại cho V Nếu V kiểm tra và phát hiện thiếu một quân bài “át cơ” và một quân bài “2 cơ”, điều đó xác nhận rằng hai quân bài của P đúng như anh ta đã nói.
“Chứng minh không tiết lộ thông tin” không đồng nghĩa với việc “không để lộ thông tin”, mà có nghĩa là chỉ tiết lộ thông tin ở mức tối thiểu về sự vật, sự việc cần chứng minh Những thông tin này cho phép người xác minh có được hiểu biết hạn chế, gần như là “zero knowledge”, về đặc điểm và tính chất của đối tượng được đề cập.
Giao thức ∑ là giao thức “Hỏi - Đáp” 3 bước, để P chứng minh cho V một vấn đề nào đó
- P gửi cho V: một giá trị ngẫu nhiên
- V gửi lại P: một giá trị ngẫu nhiên nhƣ là giá trị dùng để kiểm thử
- P gửi đáp lại V: một giá trị
Kết quả V bác bỏ hoặc thừa nhận vấn đề P chứng minh
Chứng minh không tiết lộ thông tin, viết tắt là GMR, được phát minh bởi Goldwasser, Micali và Rackoff vào năm 1981 Đây là một lý thuyết quan trọng và có ảnh hưởng lớn trong lĩnh vực khoa học máy tính, bao gồm cả chứng minh tương tác.
3/.Các thành phần trong phép chứng minh không tiết lộ thông tin
Có hai nhân vật mà chúng ta thường xuyên nhắc đến trong vấn đề này:
- Peggy Prover (người chứng minh): Peggy có thông tin muốn chứng minh cho Victor thấy, nhƣng cô ấy lại không muốn nói thẳng bí mật đó cho Victor
Victor Verifier đã đặt ra nhiều câu hỏi cho Peggy nhằm xác định xem cô có thực sự nắm giữ bí mật hay không Dù Victor có thể sử dụng những chiêu trò hoặc không tuân thủ quy tắc, anh vẫn không thể thu được thông tin gì từ bí mật mà Peggy sở hữu.
2.1.2 Khái niệm về chứng minh tương hỗ
Hệ thống chứng minh tương hỗ bao gồm hai thành viên: Lan, người chứng minh, và Nam, người kiểm tra Lan muốn chứng minh cho Nam rằng cô biết một bí mật mà chỉ cô biết Giao thức chứng minh này diễn ra qua nhiều vòng hỏi đáp, nhằm xác định tính xác thực của thông tin mà Lan cung cấp.
Trong mỗi vòng, Lan và Nam luân phiên thực hiện các công việc sau:
- Nhận một thông báo từ nhóm khác
- Thực hiện một tính toán riêng
- Gửi một thông báo tới nhóm khác
Một vòng giao thức bao gồm một yêu cầu từ Nam và một phản hồi từ Lan Cuối cùng, Nam sẽ quyết định chấp nhận hoặc từ chối phép chứng minh của Lan dựa trên việc Lan có thực hiện thành công các yêu cầu của mình hay không.
Phép chứng minh tương hỗ có:
- Tính đầy đủ khi và chỉ khi trong trường hợp Lan biết phép chứng minh x cho bài toán , thì Nam luôn chấp nhận Lan
- Tính đúng đắn nghĩa là nếu Lan không biết cách chứng minh x cho bài toán thì xác suất để Nam chấp nhận Lan là rất nhỏ
Phép chứng minh tương hỗ có thể thực hiện được trong thời gian đa thức gọi là phép chứng minh tương hỗ trong thời gian đa thức
HỆ THỐNG CM KTLTT CHO TÍNH ĐẲNG CẤU CỦA ĐỒ THỊ…
2.2.1 Khái niệm đồ thị đẳng cấu
Bài toán đồ thị đẳng cấu vẫn chưa có thuật toán giải quyết với thời gian đa thức, mặc dù nó không thuộc lớp bài toán NP đầy đủ Định nghĩa đồ thị đẳng cấu là một khái niệm quan trọng trong lý thuyết đồ thị, liên quan đến việc xác định xem hai đồ thị có cấu trúc tương tự hay không.
Cho hai đồ thị n đỉnh G 1 = (V1 , E1) và G2 = (V2 , E2) , G1 và G2 đƣợc đẳng cấu nếu có một song ánh p: V1 V2 sao cho {u,v} E1 khi và chỉ khi
2/.Một sơ đồ chứng minh tương hỗ cho tính đẳng cấu của đồ thị
Sơ đồ dưới đây nhằm thuyết phục Nam rằng hai đồ thị đã cho là đẳng cấu thông qua một giao thức chứng minh tương hỗ Tuy nhiên, sau khi kết thúc giao thức, Nam vẫn không có thông tin nào để chứng minh rằng hai đồ thị đó là đẳng cấu, cho dù là cho bản thân hay cho người thứ ba Đây là một khái niệm khó định nghĩa hình thức, vì vậy chúng ta sẽ xem xét một ví dụ trước khi đưa ra định nghĩa.
Hệ thống CM KTLTT hoàn thiện cho tính đẳng cấu của đồ thị: Đầu vào:
Thông tin công khai: Hai đồ thị G1 và G2 ,mỗi đồ thị có tập đỉnh {1…n} Thông tin bí mật của Lan: Phép hoán vị đƣa G2 trở thành G1
Lặp lại các bước sau n lần:
- Lan chọn một phép hoán vị ngẫu nhiên của {1…n} cô ta tính H là ảnh của G1 theo và gửi H cho Nam
- Nam chọn một số nguyên ngẫu nhiên i = 1 hoặc 2 và gửi nó cho Lan
Lan sẽ thực hiện một phép hoán vị để biến H thành Gi Cô ấy sẽ gửi cho Nam kết quả, trong đó nếu i=1, Lan sẽ xác định H = Gi, còn nếu i=2, Lan sẽ xác định là hợp của H và Gi.
-Nam sẽ kiểm tra xem H có phải là ảnh của Gi theo hay không
Nam sẽ chỉ chấp nhận chứng minh của Lan, nếu H là ảnh của Gi ở mỗi một trong n vòng
Giả sử G1 = (V, E1) và G2 = (V, E2) trong đó V = {1, 2, 3, 4} , E1 = {12, 13, 14,34} và E2 = {12, 13, 23, 24}.Một phép đẳng cấu từ G2 sang G1 là hoán vị = (4,
Bây giờ giả sử ở trong vòng nào đó của giao thức, Lan chon hoán vị = (2,
4, 1, 3).Khi đó H sẽ có tập cạnh {12, 13, 23, 24}
Nếu yêu cầu của Nam là i = 1 thì Lan sẽ cho Nam phép hoán vị và Nam sẽ kiểm tra xem ảnh của G1 theo có phải là H không
Nếu yêu cầu của Nam là i = 2 thì Lan sẽ cho Nam phép hợp = = (3, 2,
1, 4) và Nam sẽ kiểm tra xem ảnh của G2 theo có phải là H không
Việc kiểm tra tính đầy đủ và tính đúng đắn của giao thức là rất dễ dàng Nếu Lan biết phép chứng minh G1 đẳng cấu với G2, xác suất để Nam chấp nhận sẽ là 1 Ngược lại, nếu Lan không biết phép chứng minh, cô chỉ có thể lừa dối Nam bằng cách giả định giá trị i mà Nam sẽ chọn ở mỗi vòng và truyền cho Nam một đồ thị ngẫu nhiên đẳng cấu.
Gi tương ứng).Xác xuất để Lan giả định đúng các yêu cầu của Nam trong cả n vòng là 2 -n
Tất cả các tính toán của Nam có thể thực hiện trong thời gian đa thức nhờ vào việc chỉ cần thực hiện các phép sinh số ngẫu nhiên và hoán vị Tương tự, các tính toán của Lan cũng có thể hoàn thành trong thời gian đa thức nếu cô biết đến sự tồn tại của phép hoán vị để biến G2 thành G1.
Hệ thống chứng minh được coi là không tiết lộ thông tin vì mặc dù Nam đã thuyết phục rằng G1 là đẳng cấu với G2, anh vẫn không thu được kiến thức nào để tìm ra phép hoán vị đưa G2 về G1 Những gì Nam thấy trong mỗi vòng chứng minh chỉ là một đồ thị ngẫu nhiên H đẳng cấu với G1 và G2, cùng với một phép hoán vị từ G1 hoặc G2 thành H, nhưng không phải cả hai Nam có khả năng tự tính toán các bản sao ngẫu nhiên của các đồ thị này mà không cần sự trợ giúp từ Lan Việc các đồ thị H được chọn độc lập và ngẫu nhiên trong mỗi phần của phép chứng minh không giúp Nam tìm ra phép đẳng cấu từ G1 sang G2.
Ta xem xét kĩ lƣỡng thông tin mà Nam thu đƣợc nhờ tham gia vào hệ thống chứng minh tương hỗ :
- Tất cả các thông báo đƣợc Lan và Nam gửi đi
- Các số ngẫu nhiên mà Nam dùng để tạo các yêu cầu của mình
Bởi vậy, các thông tin T thu được qua sơ đồ chứng minh tương hỗ về phép đẳng cấu đồ thị sẽ có dạng sau: T = ((G 1 , G 2 ); (H j , i j , ) … (H n , i n , ))
Giả mạo biên bản ghi nhận sau giao thức chứng minh là một vấn đề quan trọng trong lĩnh vực bảo mật thông tin Điểm mấu chốt là bất kỳ ai, bao gồm cả Nam, có thể giả mạo thông tin T mà không cần tham gia vào hệ thống chứng minh tương hỗ, tương tự như các thông tin thực tế Việc này được thực hiện thông qua một thuật toán cụ thể, cho thấy sự cần thiết phải cải thiện các biện pháp bảo vệ trong các giao thức chứng minh không tiết lộ thông tin.
Thuật toán giả mạo chứng minh tương hỗ cho tính đẳng cấu: Đầu vào:
Hai đồ thị G 1 và G2 , mỗi đồ thị có tập đỉnh {1…n}
Chọn ngẫu nhiên ij = 1 hoặc 2 Chọn là một hoán vị ngẫu nhiên của {1, …., n}
Tính Hj là ảnh của theo Ghép (Hj , ij , ) vào cuối của T
Theo ngôn ngữ của phép chứng minh không tiết lộ thông tin, thuật toán giả mạo được gọi là bộ mô phỏng Sự tồn tại của bộ mô phỏng có thể tạo ra T mang lại hệ quả quan trọng: mọi kết quả mà Nam (hay bất kỳ ai khác) có thể tính từ T cũng có thể tính được từ một bản T giả mạo Do đó, việc tham gia vào hệ thống chứng minh không làm tăng khả năng tính toán của Nam, và điều này cũng không cho phép Nam tự chứng minh rằng G1 và G2 là đẳng cấu Hơn nữa, Nam không thể thuyết phục người khác rằng G1 và G2 là đẳng cấu chỉ bằng cách cho họ một bản T, vì không có cách nào để phân biệt bản T hợp lệ và bản T giả mạo.
2.2.2 Định nghĩa hệ thống CM KTLTT hoàn thiện
Thông tin giả mạo được định nghĩa một cách chính xác là những dữ liệu hoặc thông tin sai lệch, thường được phát tán với mục đích gây hiểu lầm Để hiểu rõ hơn, chúng ta có thể áp dụng các khái niệm trong lý thuyết xác suất, từ đó xây dựng một định nghĩa chặt chẽ về thông tin giả mạo trong bối cảnh các phân bố xác suất.
Giả sử có một phép chứng minh tương hỗ x cho bài toán và một bộ mô phỏng thời gian đa thức S Tập hợp tất cả thông tin có thể tính từ x được ký hiệu là F(x).
F được nhận từ việc thực hiện phép chứng minh tương hỗ giữa Lan và Nam Kí hiệu tập giả mạo có thể được tạo ra bởi S Với thông tin bất kỳ T, xác suất để T trở thành thông tin giả mạo do S tạo ra được xem xét.
Hệ thống chứng minh tương hỗ được định nghĩa là một hệ thống chứng minh không tiết lộ thông tin hoàn thiện đối với Nam, trong đó F(x) và bất kỳ T nào đều có thể tương đương, tức là tập hợp các thông tin thực đồng nhất với tập hợp các thông tin giả mạo và hai phân bố xác suất là như nhau.
Đặc tính không tiết lộ thông tin có thể được định nghĩa theo nhiều cách, nhưng cần giữ nguyên nội dung cốt lõi Một hệ thống chứng minh tương hỗ được coi là không tiết lộ thông tin cho Nam nếu tồn tại một mô phỏng tạo ra T có phân bố xác suất giống với phân bố xác suất của thông tin mà Nam nhận được trong giao thức Do đó, những gì Nam có thể làm sau khi tham gia giao thức cũng tương đương với những gì anh ta có thể thực hiện khi sử dụng mô phỏng để tạo T giả mạo Mặc dù không định nghĩa "thông tin" theo cách này, nhưng bất kỳ điều gì được xem là thông tin thì Nam sẽ không thu được bất kỳ thông tin nào.
Chứng minh: Sơ đồ là hệ thống CM KTLTT hoàn thiện:
Hệ thống chứng minh tương hỗ cho tính đẳng cấu đồ thị mà chúng ta sẽ trình bày sau đây là một hệ thống chứng minh không tiết lộ thông tin hoàn thiện đối với Nam.
Giả sử G1 và G2 là hai đồ thị đẳng cấu với n đỉnh, một bản T (thực hoặc giả mạo) sẽ bao gồm n bộ ba dạng (H, i) trong đó i = 1 hoặc i = 2, là một phép hoán vị của {1…n} và H là ảnh của G theo hoán vị Bộ ba này được gọi là bộ ba hợp lệ và được ký hiệu là R Đầu tiên, chúng ta sẽ tính |R|, số lượng các bộ ba hợp lệ, điều này là hiển nhiên.
|R| = 2.n! vì mỗi phép chọn i và sẽ xác định một đồ thị duy nhất H
HỆ THỐNG CM KTLTT CHO BÀI TOÁN THẶNG DƢ BẬC HAI
Bài viết này sẽ giới thiệu một số ví dụ về hệ thống chứng minh không tiết lộ thông tin hoàn thiện Một phương pháp chứng minh không tiết lộ thông tin hoàn thiện được áp dụng cho các thặng dư bậc hai (modulo n=p.q, với p và q là các yếu tố).
Chứng minh tương hỗ không tiết lộ thông tin hoàn thiện cho thặng dư bậc hai liên quan đến một số nguyên n có phân tích n = p.q, trong đó p và q là các số nguyên tố, và x thuộc QR(n).
Lặp lại các bước sau logn2 lần:
- Lan chọn một số ngẫu nhiên v Zn
*và tính y=v 2 mod n.Lan gửi y cho Nam
- Nam chọn một số nguyên ngẫu nhiên i=0 hoặc 1 và gửi nó cho Lan
- Lan tính z = u i v mod n Trong đó u là căn bậc hai của x và gửi x cho Nam
- Nam sẽ kiểm tra xem liệu có thỏa mãn z 2 x i y (mod n)
- Nam sẽ chấp nhận chứng minh của Lan nếu tính toán ở bước được 5 kiểm tra cho mỗi vòng (trong log2n vòng)
Lan cần chứng minh rằng x là một thặng dư bậc hai Trong mỗi vòng, cô sẽ tạo ra một thặng dư bậc hai ngẫu nhiên y và gửi cho Nam Tùy thuộc vào yêu cầu của Nam, Lan sẽ cung cấp cho anh ta căn bậc hai của y hoặc căn bậc hai của xy.
2.3.2 Tính chất của sơ đồ
Giao thức này chứng minh tính đúng đắn khi chỉ ra rằng nếu x không phải là một thặng dư bậc hai, Lan chỉ có thể đáp ứng một trong hai yêu cầu Trong trường hợp này, y sẽ là thặng dư bậc hai nếu và chỉ nếu xy không phải là thặng dư bậc hai Do đó, Lan sẽ bị mắc kẹt trong một vòng xác suất nhất định của giao thức, với xác suất để Lan lừa Nam trong toàn bộ n vòng chỉ bằng (–1)/n Số vòng log2n liên quan đến kích thước đặc trưng của bài toán tỉ lệ với số bit trong biểu diễn nhị phân Vì vậy, xác suất để Lan đánh lừa sẽ là một hàm mũ âm của kích thước đặc trưng của bài toán, tương tự như trong chứng minh không tiết lộ thông tin cho tính đẳng cấu đồ thị.
2.3.3 Chứng minh sơ đồ có tính đầy đủ
Tính không tiết lộ thông tin hoàn thiện của Nam có thể được minh họa qua bài toán đẳng cấu đồ thị Để tạo ra bộ bab (y, i, z), Nam sẽ chọn các giá trị i và z, sau đó xác định y bằng công thức: y = z²(xᵢ) - i mod n.
Các bộ ba được tạo ra theo phương pháp này có phân bố xác suất tương tự như các bộ ba được hình thành trong giao thức với giả thiết rằng Nam chọn yêu cầu một cách ngẫu nhiên Tính không tiết lộ thông tin hoàn thiện (với V * tùy ý) có thể được chứng minh bằng phương pháp tương tự như trong bài toán đẳng cấu đồ thị Điều này yêu cầu xây dựng một mô phỏng S * để giả định các yêu cầu của V * và chỉ giữ lại các bộ ba tương ứng với các giả định chính xác.
ỨNG DỤNG CHỨNG MINH KHÔNG TIẾT LỘ THÔNG TIN… 43 3.1 ỨNG DỤNG CM KTLTT TRONG BỎ PHIẾU ĐIỆN TỬ
Sơ đồ bỏ phiếu truyền thống
Trong lịch sử, bầu cử đã đóng vai trò quan trọng trong việc xác lập thể chế chính trị của các quốc gia Ngày nay, việc bỏ phiếu bầu quốc hội là một sự kiện thiết yếu của đất nước Do đó, nhiều nỗ lực đã được đầu tư vào việc cải tiến phương thức bầu cử để nâng cao chất lượng Mặc dù phương thức bầu cử thay đổi theo thời gian và sự tiến bộ của xã hội, nhưng bản chất của một cuộc bầu cử "tốt" vẫn giữ nguyên.
Quyền bỏ phiếu là một quyền cơ bản, chỉ những người đủ điều kiện mới được tham gia và mỗi cá nhân chỉ được thực hiện quyền này một lần Để đảm bảo tính công bằng và thuận lợi, cuộc bỏ phiếu cần được tổ chức sao cho những người có quyền bầu cử dễ dàng thực hiện quyền lợi của mình.
Tính chất bí mật trong cuộc bỏ phiếu đảm bảo rằng người bỏ phiếu có thể an tâm khi thể hiện ý kiến của mình, vì không ai có thể biết được họ đã chọn ai Điều này giúp ngăn chặn việc trả thù đối với những người có quan điểm khác biệt.
Kết quả chính xác trong bầu cử là quyền của mỗi cá nhân, cho phép họ kiểm tra và phát hiện sai phạm trong quá trình bầu cử theo thể lệ đã được quy định Tất cả cử tri và ban kiểm phiếu đều có quyền tham gia vào việc này Để đảm bảo tính minh bạch, cần có phương pháp hiệu quả để giải quyết các sai phạm phát sinh.
Hiện nay, hầu hết các cuộc bầu cử vẫn diễn ra theo phương thức truyền thống Tuy nhiên, với sự phát triển nhanh chóng của công nghệ thông tin và xu hướng “chính phủ điện tử”, việc số hóa bầu cử để thay thế phương pháp truyền thống là điều tất yếu trong tương lai gần Gần đây, nhiều quốc gia trên thế giới đã bắt đầu thử nghiệm bỏ phiếu điện tử.
Sơ đồ bỏ phiếu truyền thống:
Khi tham gia bỏ phiếu truyền thống, người dân cần mang theo giấy tờ cá nhân và lá phiếu trống đến bàn đóng dấu, nơi nhân viên kiểm tra giấy tờ để xác minh quyền bỏ phiếu và đóng dấu xác thực lên lá phiếu Sau đó, họ vào phòng bỏ phiếu, cất giấy tờ đi, đảm bảo rằng lá phiếu không chứa thông tin định danh Cuối cùng, họ điền thông tin vào lá phiếu và bỏ vào hòm, quy trình này được coi là nặc danh nếu tất cả người tham gia tuân thủ đúng quy trình.
Từ sơ đồ bỏ phiếu truyền thống, việc bỏ phiếu có thể chia ra làm ba giai đoạn: Đăng kí, bỏ phiếu, kiểm phiếu.
Một số khái niệm
1/.Vấn đề “bỏ phiếu điện tử” (Electronic Voting)
Nghiên cứu về "Bỏ phiếu thăm dò từ xa" là yếu tố quan trọng thúc đẩy sự phát triển của xã hội dân chủ Một hệ thống bỏ phiếu thăm dò an toàn và tin cậy sẽ được áp dụng thường xuyên để thu thập ý kiến cộng đồng cho các quyết định chính trị và xã hội thông qua tự động hóa Để đạt được hiệu quả, "Bỏ phiếu thăm dò từ xa" cần có những đặc điểm tương tự như bỏ phiếu truyền thống Quy trình bỏ phiếu bao gồm nhiều giai đoạn, và hiện nay có nhiều kỹ thuật mật mã tiên tiến để thực hiện hiệu quả trong từng giai đoạn này.
Trong khóa luận này, tôi sẽ thảo luận về quá trình chuyển phiếu thăm dò từ Cử tri (CT) đến Ban kiểm phiếu (Ban KP) trong sơ đồ bỏ phiếu "Chọn 1 trong k" Giai đoạn này áp dụng các kỹ thuật tiên tiến như "Mã hóa đồng cấu – Chia sẻ bí mật" (Homomorphic Encryption – Secret Sharing) và "Chứng minh không tiết lộ thông tin" (Zero-knowledge proof) để đảm bảo tính bảo mật và minh bạch trong quá trình bỏ phiếu.
2/ Giai đoạn cử tri chuyển lá phiếu tới ban kiểm phiếu
Theo quan điểm thông thường, khi Cử tri chuyển lá phiếu đến Ban kiểm phiếu, việc mã hóa nội dung lá phiếu là điều cần thiết Sau đó, Ban kiểm phiếu chỉ cần giải mã để tính toán kết quả kiểm phiếu.
Nhƣng trên thực tế có thế xảy ra các tình huống sau:
Ban KP đã phát hiện một nhóm thành viên không trung thực đã gian lận phiếu thăm dò bằng cách sửa đổi nội dung lá phiếu sau khi giải mã Để khắc phục tình trạng này, kỹ thuật “Mã hóa đồng cấu – Chia sẻ bí mật” đã được áp dụng Giải pháp này cho phép Ban KP tính toán kết quả mà không cần phải giải mã từng lá phiếu.
Để đảm bảo tính công khai trong quá trình kiểm phiếu, lá phiếu mã hóa khi đến Ban Kiểm Phiếu (KP) cần được niêm yết công khai Điều này giúp cử tri nhận diện lá phiếu của mình, dẫn đến khả năng “bán” lá phiếu thăm dò Để khắc phục vấn đề này, một “Người xác minh trung thực” (TT) được sử dụng làm trung gian giữa cử tri và Ban KP Cử tri gửi lá phiếu từ xa đến Ban KP thông qua người xác minh TT Sau khi xác minh tính hợp lệ của lá phiếu, người này sẽ mã hóa lại lá phiếu (mù hóa) và gửi về Ban KP Nhờ đó, cử tri không thể nhận diện lá phiếu của mình trên bảng niêm yết công khai, ngăn chặn việc “bán” phiếu thăm dò.
Khi giải quyết 2 tình huống trên lại xuất hiện hai vấn đề khác:
Cử tri cần chứng minh tính hợp lệ của lá phiếu bằng cách đảm bảo rằng nội dung chỉ ghi một trong số k lựa chọn đã được quy định.
Chứng minh không tiết lộ thông tin cho phép người bỏ phiếu chọn lựa mà không cần chỉ rõ nội dung lá phiếu Phương pháp này đảm bảo rằng lá phiếu vẫn giữ được tính bảo mật, trong khi vẫn cung cấp đủ bằng chứng để xác nhận tính hợp lệ của nó.
Người xác minh thông tin cần chứng minh cho cử tri và Ban Kiểm phiếu rằng lá phiếu bị làm “mù” vẫn hợp lệ bằng cách chỉ ra rằng họ sở hữu giá trị để thực hiện việc này Phương pháp chứng minh được sử dụng là “Chứng minh không tiết lộ thông tin”, cho phép xác minh mà không cần tiết lộ giá trị cụ thể.
Sau đây là sơ đồ giai đoạn Cử tri chuyển lá phiếu tới Ban kiểm phiếu:
Cử tri mã hóa lá phiếu của mình bằng hệ mã hóa Elgamal và gửi đến người xác minh TT, kèm theo "Chứng minh không tiết lộ thông tin" để xác nhận tính hợp lệ của lá phiếu.
Sau khi xác minh tính hợp lệ của lá phiếu, người xác minh TT sẽ tiến hành làm “mù” lá phiếu và gửi kèm theo “Chứng minh không tiết lộ thông tin” về Ban KP Chứng minh này thể hiện quyền sở hữu giá trị bí mật được sử dụng để làm “mù” lá phiếu.
Lá phiếu đã Lá phiếu mã hóa mã hóa (x,y) đã bị làm mù
Lựa chọn ứng Xác minh tính hợp - Kiểm phiếu viên lệ của lá phiếu - Niêm yết công
Mã hóa lá Làm mù lá phiếu khai các lá phiếu phiếu đã mã hóa 2 lần
Gửi tới Trung tâm lá phiếu “Chứng minh không tiết lộ” đã mã hóa và “Chứng thông tin” để xác nhận tính hợp lệ của lá phiếu mới (đã bị làm mù).
Sơ đồ Cử tri chuyển lá phiếu tới Ban kiểm phiếu
Cử tri Người xác minh trung thực Ban kiểm phiếu
Chứng minh tính hợp lệ của lá phiếu (x, y) (Giao thức 1)
Trong quá trình chuyển lá phiếu từ Cử tri (CT) tới Ban kiểm phiếu (Ban KP), Cử tri phải thực hiện giao thức mã hóa bằng hệ thống Elgamal Lá phiếu sau khi được mã hóa sẽ được gửi tới người xác minh trung thực (TT) kèm theo "Chứng minh không tiết lộ thông tin" để đảm bảo tính hợp lệ của lá phiếu.
Trong cuộc bầu cử "chọn 1 trong k", cử tri có thể chọn ứng cử viên Gi, với i = 1, 2,…, k Để lá phiếu hợp lệ, cử tri phải ghi rõ Gi Sử dụng mã hóa Elgamal, lựa chọn Gi được mã hóa thành cặp (x, y) = ( , Gi).
Để chứng minh rằng lá phiếu (x, y) là hợp lệ, cử tri cần chỉ ra một trong k đẳng thức sau đây là đúng trước người xác minh trung thực.
Để chứng minh (1) mà không tiết lộ G i, Cử tri và người xác minh TT thống nhất sử dụng giao thức “Chứng minh không tiết lộ thông tin” như sau: (loggx = logh(y/G1)) và (loggx = logh(y/Gk)).
Giai đoạn 1 cử tri chứng minh lá phiếu hợp lệ
Cử tri (CT) Người xác minh TT
- Mã hóa lá phiếu [(x, y) = ( , Gi)]
Chọn dj, rj Zp (chƣa chọn di, ri)
(Sử dụng a i , b i đã tính ở trên)
- TT chọn ngẫu nhiên c Zp
- CT tính: (chƣa chon di , ri) d i = c- r i = w – d j
- TT kiểm tra: c = d 1 +…+d k Cho j = 1,…, k aj bj Nếu đều đúng TT kết luận: Lá phiếu họp lệ
Với k=1 ta có: x = = loggx y = G1 = logh(y/G1) loggx = logh(y/G1)
Với k=i x = = loggx y = Gi = logh(y/Gi) loggx = logh(y/Gi)
Với k=k x = = loggx y = Gk = logh(y/Gk) loggx = logh(y/Gk)
Ta có: lá phiếu (x, y) loggx = logh(y/G1) … loggx = logh(y/Gi) … loggx = logh(y/Gk)
Lá phiếu hợp lệ được xác định khi chỉ chọn một ứng cử viên duy nhất Để chứng minh tính hợp lệ của lá phiếu với ứng cử viên thứ i, chúng ta chỉ cần xác minh đẳng thức loggx = logh(y/Gi) trong số k đẳng thức đã nêu.
Ví dụ: Chứng minh tính hợp lệ của lá phiếu đã mã hóa (x, y) = ( , Gi)
Trong cuộc bầu cử "chọn 1 trong 3", cử tri có ba lựa chọn: 1, 2 hoặc 3, với ký hiệu ứng cử viên thứ i là G i Để đảm bảo tính hợp lệ của lá phiếu, cử tri cần chứng minh rằng log g x = log h (y/G i ), log g x = log h (y/G 2 ) và log g x = log h (y/G 3 ) Để thực hiện điều này, cử tri và người xác thực thông tin (TT) sẽ thống nhất sử dụng một giao thức cụ thể.
“Chứng minh không tiết lộ thông tin” nhƣ sau:
Chọn phần tử sinh g=3, =5 , khóa bí mật s=7, khóa công khai h=g s =3 7
Ký hiệu 3 ứng cử viên G1 = 1, G2 = 2, G3 = 3 Giả sử cử tri chọn Gi = 2
Cử tri (CT) Người xác minh TT
- Cử tri mã hóa lá phiếu [(x, y) = (3 5 , (3 7 ) 5 2)]
- TT kiểm tra: c = d1 + d2 + d3 =(8 + (-5) + 10) = 13 Cho j =1,2,3 a j b j Kết luận: Lá phiếu hợp lệ
Chứng minh quyền sở hữu giá trị bí mật (Giao thức 2)
Theo sơ đồ giai đoạn Cử tri (CT) chuyển lá phiếu tới Ban kiểm phiếu (Ban KP), quy trình cần tuân thủ giao thức 2 Sau khi xác minh tính hợp lệ của lá phiếu, người xác minh sẽ thực hiện việc "mù" lá phiếu và gửi nó tới Ban KP, kèm theo "Chứng minh không tiết lộ thông tin" để đảm bảo tính hợp lệ của lá phiếu đã được làm "mù".
Người xác minh TT thực hiện việc "mù" lá phiếu thông qua cặp (u, v) dựa trên giá trị bí mật Để chứng minh rằng lá phiếu bị làm "mù" vẫn hợp lệ, người xác minh TT cần chứng minh sở hữu giá trị bí mật thỏa mãn u = , v = Tuy nhiên, người xác minh TT cũng không muốn tiết lộ giá trị bí mật này Để giải quyết vấn đề này, có một giao thức hiệu quả cho phép người xác minh TT thực hiện công việc này Trong sơ đồ dưới đây, người xác minh TT đóng vai trò là người chứng minh (P), trong khi người kiểm tra (V) là CT, Ban KP, và các bên liên quan khác.
Người xác minh TT (P) Người kiểm tra (V)
P gửi V giá trị ngẫu nhiên w thông qua (a, b) c
V gửi lại P giá trị ngẫu nhiên c
- Kiểm tra: g r = au c ; h r = bv c Nếu đều đúng V thừa nhận P sở hữu giá trị
Giai đoan 2 TT chứng minh lá phiếu làm mù hợp lệ
Nếu P không biết giá trị thì P không thể tạo ra r chính xác để cho V kiểm tra
Người chứng minh P chon g = 3, s = 7, h = g s = 3 7 Có = 5 sử dụng (u, v)
= ( ) = (3 5 , (3 7 ) 5 ), cặp số ngày dùng để làm “mù” lá phiếu đã mã hóa của Cử tri
P chứng minh với V rằng mình sở hữu mà không muốn để lộ giá trị P thực hiện giao thức ∑ với người xác minh V như sau:
Người xác minh TT (P) Người kiểm tra (V)
- Kiểm tra các giá trị của đẳng thức: g r = 3 57 = 3 2 (3 5 ) 11 = au c h r = (3 7 ) 57 = (3 7 ) 5 ((3 7 ) 2 ) 11 = bv c
Nếu ai đó giả mạo việc tạo (u, v) = ( , ), việc tính toán r = w + c sẽ trở nên "khó khăn", dẫn đến việc kiểm thử g r = au c và h r = bv c cũng "khó" thực hiện Do a, b, c, r, g, h, u, v đều là công khai, bất kỳ ai cũng có thể xác minh r = w + c Nhờ vào giao thức này, mọi người tin rằng người xác minh đã sử dụng để làm "mù" lá phiếu.
Giai đoạn cử tri chuyển lá phiếu tới ban kiểm phiếu (phương án 2).54 3.2 ỨNG DỤNG CM KTLTT TRONG SỬ DỤNG TIỀN ĐIỆN TỬ
Trong mục 2.3.3 của khóa luận, giai đoạn Cử tri (CT) chuyển lá phiếu tới Ban kiểm phiếu (Ban KP) được trình bày thông qua hai phương án Phương án 1 sử dụng Giao thức 1 và Giao thức 2 để thực hiện quá trình này Bên cạnh đó, còn có phương án 2, cũng áp dụng hai giao thức tương tự, trong đó Giao thức 1 giống với phương án 1.
2 có thay đổi nhƣ sau:
Sau khi người xác minh thông tin (TT) xác nhận lá phiếu của cử tri là hợp lệ, cử tri sẽ thực hiện việc "mù" lá phiếu và gửi về Ban Kiểm Phiếu (KP), thay vì để người xác minh thực hiện như trong giao thức 2 của phương án 1 Chúng tôi đề xuất rằng trong mỗi lần xử lý một lá phiếu, nếu tại bất kỳ bước nào điều kiện không được thỏa mãn, quá trình xử lý sẽ dừng lại với lá phiếu đó và chuyển sang lá phiếu tiếp theo.
Phương án 1 gồm 2 giai đoạn một và hai
Cử tri (CT) Người xác minh TT
- CT mã hóa lá phiếu
- CT chọn ngẫu nhiên w1 Zp
Tính ai = ; bi - Tính với j = 1,…, i-1,1+1,…,k
(x, y),(A, B) c1 - TT chọn ngẫu nhiên c1 Zp
- CT tính di = c1 - ; ri = w1 - di
-TT kiểm tra:c 1 =d 1 +…+ d k Cho j=1,…,k aj bj - Nếu điều kiện sai thì dừng giao thức và hủy bỏ lá phiếu
- Nếu đúng thì tiếp tục giao thức
- TT chọn ngẫu nhiên bí mật và tính:
TT gửi CT giá trị w2 thông qua (a, b)
CT gửi lại TT giá trị c2 r
TT đáp lại CT bằng r
-Nếu điều kiện sai thì dừng giao thức và hủy bỏ lá phiếu
- Nếu điều kiện đúng thì CT mã hóa lại (làm “mù”) lá phiếu nhờ cặp (u, v) của TT:
Sau đó gửi về Ban KP
3.2 ỨNG DỤNG CM KTLTT TRONG SỬ DỤNG TIỀN ĐIỆN TỬ
Khái niệm thanh toán điện tử
Trong thương mại điện tử, thanh toán đóng vai trò quan trọng nhất, vì mục tiêu cuối cùng của giao dịch là người mua nhận được sản phẩm mong muốn và người bán thu được khoản thanh toán.
Thanh toán là một trong những thách thức lớn nhất trong thương mại điện tử (TMĐT) Để tối ưu hóa lợi ích của TMĐT, việc áp dụng hình thức thanh toán điện tử (TTĐT) là điều cần thiết.
TTĐT, hay thanh toán điện tử, là hình thức thanh toán tiền qua các thông điệp điện tử thay vì sử dụng tiền mặt hoặc séc Mô hình TTĐT mô phỏng lại phương thức thanh toán truyền thống, nhưng mọi giao dịch, xử lý dữ liệu và chuyển tiền đều được thực hiện qua mạng máy tính với các giao thức chuyên dụng.
Khái niệm tiền điện tử
Tiền điện tử, còn được gọi là E-money, E-currency, Internet money, Digital money, Digital currency, hay Digital cash, là một khái niệm chưa được định nghĩa rõ ràng Tuy nhiên, có thể hiểu rằng tiền điện tử là loại tiền được giao dịch qua phương thức điện tử, liên quan đến mạng máy tính và các hệ thống lưu trữ giá trị dưới dạng số.
Tiền điện tử cho phép người dùng thực hiện các giao dịch mua sắm và vay mượn tiền bằng cách truyền tải các dãy số từ thiết bị này sang thiết bị khác, chẳng hạn như từ máy tính hoặc thẻ thông minh (Smart Card) sang thiết bị tương ứng.
Similar to the serial numbers on banknotes, each cryptocurrency has a unique identifier Each "digital currency" is issued by an organization, such as a bank, and represents a specific amount of real money There are two types of digital currency: anonymous identified e-money and identified e-money.
Tiền ẩn danh không tiết lộ thông tin định danh của người dùng, tương tự như tiền mặt Tiền điện tử ẩn danh cho phép người dùng rút tiền từ tài khoản và chi tiêu hoặc chuyển cho người khác mà không để lại dấu vết Có nhiều loại tiền ẩn danh: một số chỉ ẩn danh với người bán, trong khi một số khác hoàn toàn ẩn danh với tất cả mọi người.
Tiền điện tử định danh cho phép tiết lộ thông tin cá nhân của người dùng, tương tự như thẻ tín dụng, giúp ngân hàng theo dõi và ghi nhận dấu vết của các giao dịch tài chính.
Tiền trênh được chia thành hai loại: trực tuyến và không trực tuyến Tiền trực tuyến yêu cầu sự tương tác với bên thứ ba để quản lý giao dịch, trong khi tiền không trực tuyến cho phép người dùng kiểm soát giao dịch mà không cần phụ thuộc vào ngân hàng hay bên trung gian nào.
Hiện nay, có hai hệ thống tiền điện tử chính là thẻ thông minh và phần mềm Cả hai đều có những đặc điểm cơ bản giống nhau, bao gồm tính an toàn, tính riêng tư, tính độc lập, khả năng chuyển nhượng và tính phân chia.
Mô hình giao dịch mua bán bằng tiền điện tử
Mô hình giao dịch mua bán bằng tiền điện tử
Mô hình giao dịch mua bán bằng tiền điện tử có 3 giao dịch với 3 đối tƣợng: Ngân hàng, Người trả tiền A (mua hàng), Người được trả tiền B (bán hàng)
- Rút tiền: Ông A chuyển tiền của mình từ tài khoản ở ngân hàng vào “Túi” của mình (“Túi” có thể la Smart Card hay máy tính)
- Thanh toán: Ông A chuyển tiền từ “Túi” của mình đến “Túi” ông B
- Gửi tiền: Ông B chuyển tiền nhận đƣợc vào tài khoản của mình ở ngân hàng
Mô hình có thể được thực hiện bằng 2 cách:
Khi thực hiện thanh toán trực tuyến, B cần liên hệ với ngân hàng để xác minh tính hợp lệ của đồng tiền trước khi tiến hành giao dịch và phân phối hàng Quá trình thanh toán và gửi tiền diễn ra đồng thời, đặc biệt quan trọng cho các giao dịch có giá trị lớn Tuy nhiên, hệ thống yêu cầu liên lạc với ngân hàng trong mỗi giao dịch, dẫn đến chi phí cao hơn về cả tiền bạc lẫn thời gian.
Khi thực hiện giao dịch không trực tuyến (offline), B cần liên hệ với ngân hàng để xác minh tính hợp lệ của đồng tiền sau khi thanh toán Phương thức này thường được áp dụng cho các giao dịch có giá trị thấp.
Các mô hình thanh toán điện tử:
Hệ thống thanh toán điện tử (TTĐT) cung cấp nhiều phương thức thanh toán cho khách hàng mà tiền mặt và séc thông thường không thể thực hiện Nó cho phép người mua thanh toán hàng hóa và dịch vụ theo nhiều hình thức, bao gồm trả tiền ngay, trả tiền sau hoặc trả tiền trước, mang lại sự linh hoạt trong giao dịch.
Mô hình trả tiền sau cho phép tiền mặt được rút ra từ tài khoản của bên mua để chuyển cho bên bán, có thể diễn ra ngay lập tức hoặc sau đó.
Hệ thống giao dịch mua bán hoạt động dựa trên nguyên tắc Tín dụng, còn được gọi là mô hình mô phỏng Séc.
Mô hình trả tiền trước yêu cầu khách hàng liên hệ với ngân hàng hoặc công ty môi giới để nhận chứng từ do ngân hàng phát hành Chứng từ này, hay còn gọi là đồng tiền số, mang dấu ấn của ngân hàng và được đảm bảo bởi ngân hàng, cho phép sử dụng tại bất kỳ nơi nào có hệ thống thanh toán liên kết Để nhận chứng từ, tài khoản của khách hàng sẽ bị triết khấu tương ứng với giá trị của chứng từ đó, nghĩa là khách hàng đã thực sự trả tiền trước khi sử dụng để mua hàng và thanh toán.
Chứng từ được phát hành bởi ngân hàng và không phải do khách hàng tạo ra, không giới hạn cho một giao dịch mua bán cụ thể Nó có thể được sử dụng cho nhiều mục đích thanh toán khác nhau, tương tự như tiền mặt, vì vậy 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 khách hàng thanh toán tại cửa hàng bằng chứng từ, cửa hàng sẽ xác minh tính hợp lệ của chứng từ dựa trên thông tin đặc biệt do ngân hàng cung cấp.
Cử hàng có hai lựa chọn: liên hệ với ngân hàng để chuyển tiền vào tài khoản trước khi giao hàng (deposit-now) hoặc chấp nhận và chuyển tiền sau vào thời gian phù 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 nay, hầu hết các dịch vụ mua bán trực tuyến đều áp dụng hình thức thanh toán bằng thẻ tín dụng Người dùng chỉ cần nhập thông tin như tên, mã số thẻ và ngày hết hạn để hoàn tất giao dịch.
Hiện nay, tỷ lệ gian lận thẻ trên internet ở Châu Âu chiếm khoảng 7% tổng giao dịch, trong khi ở Châu Á con số này là 10% Tại Việt Nam, dịch vụ thẻ tín dụng chỉ mới được sử dụng từ cuối năm 1996, nhưng tỷ lệ giao dịch gian lận đã vượt quá 10% tổng số giao dịch.
Nhu cầu thương mại điện tử đang gia tăng trên toàn cầu, tuy nhiên, vấn đề hạ tầng thanh toán điện tử vẫn chưa được giải quyết đầy đủ Việc nghiên cứu và phát triển các hệ thống thanh toán điện tử an toàn là rất cần thiết để đáp ứng yêu cầu của dịch vụ thương mại điện tử hiện nay.
Hệ thống thanh toán điện tử ứng dụng lý thuyết mật mã để đảm bảo an toàn cho các giao dịch Mô hình thanh toán này sử dụng giao thức mật mã nhằm bảo vệ thông tin giữa các bên tham gia.
Vấn đề “tiền điện tử”
Vấn đề ẩn danh trong giao dịch tiền tệ là một đặc tính quan trọng, mang lại sự tiện lợi cho người sử dụng Tính ẩn danh có nghĩa là người tiêu tiền không để lại dấu vết, giúp ngân hàng không thể xác định ai là chủ sở hữu của giao dịch Đối với tiền điện tử, kỹ thuật được áp dụng nhằm bảo vệ tính ẩn danh này đóng vai trò quan trọng trong việc đảm bảo quyền riêng tư cho người dùng.
Chữ ký mù là một loại chữ ký điện tử đặc biệt, yêu cầu người ký thực hiện ký vào thông điệp mà không biết nội dung bên trong Sau khi ký, người ký có thể kiểm tra tính xác thực của chữ ký nhưng không thể nhớ thời gian và địa điểm ký Hình thức này tương tự như việc ký tên trên giấy khi nhắm mắt.
Với “chữ ký mù” của ngân hàng, họ không thể tìm mối liên hệ nào giữa đồng tiền điện tử và chủ sở hữu của nó
Lƣợc đồ CHAUM-FIAT-NAOR dùng chữ ký mù RSA Lƣợc đồ BRAND dung chữ ký mù Schnorr
2/ Vấn đề gian lận giá trị đồng tiền (“khai man giá trị” đồng tiền)
Việc ngân hàng sử dụng “chữ ký mù” để ký vào đồng tiền tạo ra rủi ro gian lận, ví dụ như trường hợp ông A xin ngân hàng “ký” vào đồng tiền trị giá 1$, nhưng thực tế lại gửi đồng tiền có giá trị 50$ Kết quả là ông A có được đồng tiền 50$ kèm theo “chữ ký” của ngân hàng, trong khi tài khoản của ông chỉ bị khấu trừ 1$.
Ngân hàng không thể xác định giá trị thực của đồng tiền do việc "ký mù", dẫn đến khả năng xảy ra gian lận Để khắc phục tình trạng này, có hai phương pháp hiệu quả.
Ngân hàng sử dụng các bộ khóa khác nhau, bao gồm khóa ký và khóa kiểm tra chữ ký, cho mỗi loại tiền tệ Điều này có nghĩa là nếu có n giá trị đồng tiền, ngân hàng sẽ cần n bộ khóa riêng biệt để đảm bảo tính bảo mật và xác thực.
Ví dụ, đồng tiền có giá trị 1$ sử dụng khóa k1, trong khi đồng tiền 50$ sử dụng khóa k50 Nếu Q gian lận và tạo ra đồng tiền 50$ bằng khóa k1, thì đồng tiền đó sẽ bị coi là không hợp lệ.
Cách 2: Dùng giao thức “Cắt và chọn” (Cut and choose) Ý tưởng như sau: Để rút từ ngân hàng một đồng tiền giá trị T, ông A phải tạo k đồng tiền C 1 ,
C2, C3,…,CK đều có giá trị T và được gán định danh riêng, với điểm khác biệt duy nhất là số sê-ri A thực hiện việc "mù" những đồng tiền này trước khi gửi chúng đến ngân hàng.
Ngân hàng yêu cầu ông A cung cấp thông tin để thực hiện quá trình khử “mù” cho k-1 đồng tiền bất kỳ Sau khi khử “mù” và kiểm tra tính hợp lệ, ngân hàng sẽ “ký mù” lên đồng tiền còn lại Ci (đồng tiền chưa được khử “mù”) và gửi lại cho ông A.
Ngân hàng có độ tin cậy cao rằng đồng tiền còn lại Ci là hợp lệ, vì nếu ông A gửi k đồng tiền mà có đồng tiền không hợp pháp, xác suất bị phát hiện ít nhất là k-1/k, và xác suất này tăng lên khi k lớn hơn Tuy nhiên, nếu k quá lớn, hệ thống xử lý sẽ phải trao đổi nhiều dữ liệu và thực hiện nhiều phép tính.
3/ Vấn đề tiêu xài một đồng tiền nhiều lần (double - spending)
Tiền điện tử được số hóa, điều này cho phép dễ dàng sao chép từ bản gốc Sự khó khăn trong việc phân biệt giữa đồng tiền gốc và đồng tiền sao khiến cho kẻ gian có thể sử dụng đồng tiền sao nhiều lần mà không bị phát hiện.
Hệ thống tiền điện tử cần phải có khả năng ngăn chặn hoặc phát hiện hiện tượng "một đồng tiền tiêu xài nhiều lần" (double spending) Để giải quyết vấn đề này, các giải pháp khác nhau đã được áp dụng tùy thuộc vào từng loại tiền điện tử.
* Với hệ thống Tiền điện tử trực tuyển:
Ngân hàng lưu trữ thông tin về tất cả các đồng tiền điện tử đã được sử dụng trước đó Khi người bán hàng cần xác nhận, họ sẽ liên hệ với ngân hàng để biết được đồng tiền nào còn khả năng sử dụng.
Khi ngân hàng thông báo rằng một loại tiền tệ đã bị tiêu xài, người bán hàng ngay lập tức từ chối giao dịch Tình huống này tương tự như việc người bán hàng hiện nay kiểm tra thẻ tín dụng tại các điểm bán hàng.
* Với hệ thống Tiền điện tử không trực tuyến: Phát hiện việc “tiêu xài nhiều lần” một đồng tiền, đƣợc thực hiện bằng 2 cách:
Cách 1: Tạo thẻ thông minh (smart card) với chip “chống chộm cắp”, còn gọi là “người theo dõi”, giúp lưu giữ dữ liệu về các giao dịch tiền điện tử Chip này phát hiện khi người sở hữu Thẻ cố gắng sao chép đồng tiền và tiêu xài lần 2, từ chối giao dịch để ngăn chặn gian lận Dữ liệu trên chip không thể bị xóa trừ khi Thẻ bị phá hủy.
Cách 2: Dựa vào cấu trúc của tiền điện tử và những giao thức mật mã để có thể truy vết tìm ra kẻ gian lận (“tiêu xài” nhiều lần)
Nếu người dùng nhận thức được rằng hành vi gian lận sẽ bị xử lý nghiêm, khả năng xảy ra gian lận sẽ giảm Phương pháp này có ưu điểm là không cần sử dụng chip đặc biệt, mà có thể phát triển hệ thống trên phần mềm và chạy trên máy tính cá nhân hoặc thẻ thông minh Cách thứ hai có hai trường hợp khác nhau.
Với Tiền điện tử Định danh – không trực tuyến (Indentified offline):
Lƣợc đồ tiền điện tử Brand
Lược đồ Brand được phát triển dựa trên chữ ký số Schnorr và bài toán đại diện trong nhóm cấp nguyên tố Gq là nhóm con cấp q của Zp*, với p và q là các số nguyên tố thỏa mãn điều kiện q|(p-1) Ngân hàng khởi tạo 5 thành phần chính: (g, h, g1, g2, d).
- (g, h) Gq (generator - tuple): khóa công khai của ngân hàng đƣợc dùng trong sơ đồ ký của giao thức rút tiền, x la khóa bí mật của ngân hàng x = loggh (h = g x )
- g 1 , g 2 : bộ phần tử sinh của G q
- Phần tử sinh giả d (khác g1 và g2), đảm bảo rằng định danh của người dùng sẽ không bị phát hiện trong giao thức thanh toán
- Alice tạo ngẫu nhiên u 1 , u 2 Z q , tính I = ,chuyển I đến Ngân hàng
- Ngân hàng lưu I = cùng định danh của Alice và số tài khoản, nhƣng ngân hàng không biết u 1 , u2
Trường hợp Alice tiêu xài đồng tiền hai lần, ngân hàng có thể tìm ra (u 1 , u 2 ) và tính đƣợc I, từ I tìm ra định danh kẻ gian lận
Quá trình khởi tạo tài khoản Chứng minh đại diện tài khoản:
Khi Alice muốn rút tiền, cô cần xác minh danh tính với ngân hàng để chứng minh quyền sở hữu tài khoản.
Phương pháp "chứng minh tri thức của một đại diện" cho phép Alice chứng minh với ngân hàng rằng cô biết giá trị u1 và u2 mà không cần tiết lộ thông tin cụ thể về chúng Điều này đảm bảo rằng Alice có quyền sở hữu tài khoản mà vẫn bảo vệ được tính riêng tư của các giá trị này.
Quá trình xác thực đƣợc tiến hành nhƣ sau:
+ Alice chọn ngẫu nhiên w1, w2 Zq và gửi y = đến ngân hàng
+ Ngân hàng thƣ thách kiểm tra có đúng Alice sở hữu tài khoản không, bằng cách chọn ngẫu nhiên Cr Zq và gửi đến Alice
+ Alice tính r1 = w1 + Cru1 (mod q),r2 = w2 + Cru2(mod q),gửi đến ngân hàng + Ngân hàng chấp nhận xác thực là đúng khi và chỉ khi y = trong đó I 65
Nếu Alice không biết u1, u2 (hay đại diện của I), thì Alice không thể tính tạo ra r1, r2 để cho ngân hàng kiểm tra
Alice (người chứng minh) Ngân hàng (người kiểm tra)
Biết u 1 , u 2 là đại diện của I = Chỉ biết I, g 1 , g 2 ; không biết u 1 , u 2 Tạo 2 số ngẫu nhiên w1, w2 Zq
Tính y = gửi đến ngân hàng Nhận y, chọn ngẫu nhiên Cr Zq
Gửi thử thách Cr đến Alice Nhận Cr tính: r1 = w1 + Cru1 (mod q); r 2 = w 2 + C r u 2 (mod q)
Và gửi chúng đến ngân hàng
Nhận r1, r2 kiểm tra: y Nếu thỏa mãn, ngân hàng chấp nhận Alice biết đại diện của I (có nghĩa là biết u 1 , u2)
Quá trình chứng minh đại diện tài khoản
Nếu xác thực đƣợc chấp nhận, thì quá trình rút tiền đƣợc tiến hành nhƣ sau:
Ngân hàng trừ một số tiền từ tài khoản của Alice và cùng với cô tính toán giá trị m = Id, trong đó d là phần tử sinh và công khai Ngân hàng sau đó gửi cho Alice các giá trị z = m x, a = g w, và b = m w, với w được chọn ngẫu nhiên từ Zq và x là khóa bí mật của ngân hàng.
+ Alice chọn 3 số ngẫu nhiên s Zq
* ; u, v Zq để làm “mù” m, z, a, b: m’ = m s = (Id) s = d s z’ = z s ; a’ = a u g v ; b’ = b su m sv
Tách ngẫu nhiên: u1s = (x1 + x2) mod q, u2s = (y1 + y2) mod q với s = z1 + z2 (mod q) tính:
A = ; B = m’ / A + Alice dùng hàm băm H tính c’= H(m’, z’, a’, b’, A)
Làm “mù” c’ bằng c = (mod q) , gửi c đến ngân hàng
Ngân hàng ký vào giá trị c với r = xc + w (mod q) và gửi r cho Alice, đồng thời ghi có vào tài khoản của cô Alice sẽ chấp nhận giao dịch nếu kiểm tra thấy g^r = h^c*a và m^r = z^c*b Sau đó, cô tính toán r’ = ru + v (mod q) Như vậy, Alice sở hữu đồng tiền điện tử thực sự được đại diện bởi kết quả này.
A, B, Sign(A, B) với Sign(A, B) = (z’, a’, b’, r’) là chữ ký của ngân hàng Nhƣng làm thế nào chúng ta có thể biết đƣợc giá trị của đồng tiền Có 2 cách khác nhau để giải quyết vấn đề này:
Ngân hàng áp dụng một khóa công khai riêng cho mỗi loại tiền tệ, điều này có nghĩa là nếu có k loại tiền khác nhau, ngân hàng sẽ công khai k khóa công khai tương ứng: (g1, h1), (g2, h2), …, (gk, hk).
Cách 2: Chọn k phần tử sinh giả (dummy generator) khác nhau đƣợc công khai d1,…, dk Mỗi phần tử sinh đƣợc dùng để biểu hiện giá trị của mỗi đồng tiền
Nếu ngân hàng không biết x, thì ngân hàng không thể tạo ra r để cho Alice kiểm tra
I Quá trình chứng minh đại diện
Ngân hàng x: khóa bí mật (g, h): khóa công khai (h = g x ) z, a, b
Tách ngẫu nhiên: u, v Zq a’ = a u g v b’ = b su m su c’ = H (m’, z’, a’, b’, A) c= (mod q) c r r = xc + w (mod q)
Tính r’ = ru + v (mod q) Đồng tiền: (A, B, Sign(A, B)) với Sign(A, B) = (z’, a’, b’, r’)
Khi Alice muốn mua hàng hoặc sử dụng dịch vụ của Bob, cô ấy cần gửi tiền cho Bob trước Quá trình thanh toán sẽ được thực hiện qua các bước sau đây.
+ Alice gửi tiền (A, B, Sign(A, B)) đến Bob
+ Đầu tiên, Bob kiểm tra xem AB 1 hay không
Ngân hàng không thể xác định được u1 và u2 trong trường hợp "double-spending" Tiếp theo, Bob sẽ kiểm tra tính hợp lệ của chữ ký ngân hàng sign(A, B) Nếu chữ ký hợp lệ, Bob sẽ thách thức Alice bằng cách gửi c Zq *.
, c không cần thiết là số ngẫu nhiên, nhƣng phải đảm bảo là duy nhất trong mỗi lần thanh toán
Bob tính c nhƣ sau: c = H0 (A, B, Ib, date/time), với I là định danh cảu Bob, date/time là nhãn thời gian của giao dịch, H 0 là hàm băm
+ Alice phản hồi với: r1 = x1 + cx2 (mod q) r2 = y1 + cy2 (mod q) r3 = z1 + cz2 (mod q)
+ Bob kiểm tra, nếu = AB c thì chấp nhận thanh toán
Nếu Alice không biết x 1 , y 1 , z 1 , x 2 , y 2 , z 2 , thì Alice không thể tạo ra r 1 , r 2 , r 3 để cho Bob kiểm tra
AB 1 ? Kiểm tra chữ ký (A, B) c Zq
* c r1 = x1 + cx2 (mod q) r2 = y1 + cy2 (mod q) r3 = z1 + cz2 (mod q) r1, r2, r3
Nếu đúng Bob chấp nhận thanh toán
+ Bob gửi thông tin thanh toán (A, B, Sign(A, B)), c, r1, r2, và r3 đến ngân hàng
+ Ngân hàng kiểm tra chữ ký có chính xác không và đồng tiền không đƣợc tiêu xài trước đó
+ Bob thử thách Alice bằng giá trị c = H 0 (A, B, I b , date/time)
+ Alice trả lời lại giá trị r1, r2, r3
+ Nếu tất cả đều thỏa mãn, Ngân hàng gửi tiền vào tài khoản của Bob.