MỞ ĐẦU Trong suốt nhiều thế kỉ qua trên thế giới, các cuộc bầu cử đã giữ một vai trò quan trọng trong việc xác lập thể chế chính trị của các quốc gia. Và trong xu hƣớng phát triển của khoa học công nghệ ngày nay, công nghệ thông tin đã ngày càng phổ biến và đƣợc áp dụng trong mọi lĩnh vực đời sống. Các cuộc bầu cử cũng không phải là ngoại lệ. Ngƣời ta đã bỏ rất nhiều công sức để nghiên cứu cải tiến các phƣơng thức bầu cử để nó ngày càng trở nên tốt và tiện lợi hơn.
Các phƣơng thức thay đổi theo từng thời kỳ, theo sự tiến bộ của xã hội. Và với sự tiến bộ của xã hội ngày nay thì các dự án chính phủ điện tử để giúp nhà nƣớc điều hành đất nƣớc là một điều tất yếu, kèm theo đó thì sự phát triển của bỏ phiếu điện tử để thay thế cho bỏ phiếu thông thƣờng là điều sẽ diễn ra trong tƣơng lai. Nắm đƣợc tầm quan trọng và tính tất yếu của bỏ phiếu điện tử, các nƣớc, các tổ chức đã và đang xây dựng giải pháp cho bỏ phiếu điện tử. Khóa luận sẽ đi sâu về các bài toán về an toàn thông tin trong một cuộc bỏ phiếu điện tử, đặc biệt là trong giai đoạn đăng ký bỏ phiếu.
Sau đó phân tích thiết kế thử nghiệm một ứng dụng nhỏ về bỏ phiếu điện tử. MỘT SỐ KHÁI NIỆM CƠ BẢN 1. MỘT SỐ KHÁI NIỆM TOÁN HỌC 1. Số nguyên tố và nguyên tố cùng nhau 1/.
+ Số nguyên tố là số chỉ chia hết cho 1 và chính nó. + Hai số nguyên tố 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. Số nguyên tố thƣờng đƣợc sử dụng trong các hệ mã hóa (thƣờng là các số lớn hơn 10150). là các số nguyên tố.
+ Hai số 9 và 14 là nguyên tố cùng nhau. Cho các số nguyên a, b, n (n > 0), khi đó a đƣợc gọi là đồng dƣ với b theo modulo n, nếu chia a và b cho n có cùng một số dƣ. Số nguyên n đƣợc gọi là modulo của đồng dƣ. Ví dụ: 5 ≡ 7 mod 2 vì 5 mod 2 = 7 mod 2 = 1.
Tính chất của đồng dƣ: Cho a, a1, b, b1, c Z. Ta có các tính chất sau: + a ≡ b mod n nếu chỉ nếu a và b có cùng số dƣ khi chia cho n. + Tính phản xạ: a ≡ a mod n. + Tính đối xứng: Nếu a ≡ b mod n thì b ≡ a mod n.
+ Tính giao hoán: Nếu a ≡ b mod n và b ≡ c mod n thì a ≡ c mod n. + Nếu a ≡ a1 mod n, b ≡ b1 mod n thì a + b ≡ a1 + b1 mod n và ab ≡ a1b1 mod n. Không gian Zn và Zn* 1/. Không gian các số nguyên theo modulo n: Z là tập hợp các số nguyên không âm nhỏ hơn n.
Tức là : Zn = {0, 1, 2,. Tất cả các phép toán trong Zn đều đƣợc thực hiện trong modulo n. Không gian Zn* là tập hợp các số nguyên p thuộc Zn sao cho ƣớc chung lớn nhất của p và n là 1. Tức là Zn* = {p thuộc Zn | UCLN(n, p) = 1} 2/.
Khái niệm nhóm, nhóm con, nhóm Cyclic 1/. a) Nhóm là bộ các phần tử (G, *) thỏa mãn các tính chất sau: + Tính chất kết hợp: ( x * y ) * z = x * ( y * z ) + Tính chất tồn tại phần tử trung gian e G: e * x = x * e = x, x G + Tính chất tồn tại phần tử nghịch đảo x’ G: x’ * x = x * x’ = e b) 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, tức là x * y S với mọi x, y S. + S khép kín đối với phép lấy nghịch đảo trong G, tức x-1 S với mọi x S.
c) Nhóm cyclic: (G, *) là nhóm đƣợ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 để gn = a. Khi đó g là phần tử sinh hay phần tử nguyên thủy của nhóm G. Ví dụ: (Z+, *) gồm các số nguyên dƣơng là một nhóm cyclic có phần tử sinh là 1.
Khái niệm: Cho n ≥ 1. (n) đƣợc định nghĩa là các số nguyên trong khoảng [1, n] nguyên tố cùng nhau với n. Hàm đƣợc gọi là phi Euler. Tính chất: + Nếu p là số nguyên tố thì (n) = p - 1.
+ Hàm phi Euler là hàm có tính nhân: + Nếu UCLN(m, n) = 1 thì (mn) = (m) (n) + Nếu n = là thừa số nguyên tố của m thì (n) = [1. Phần tử nghịch đảo 1/. 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.
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 khả nghịch theo modulo n. + Cho a Zn, a khả nghịch khi và chỉ khi UCLN(a, n) = 1. + Giả sử d = UCLN (a, n).
Phƣơng trình đồng dƣ ax b mod n có nghiệm x nếu và chỉ nếu d chia hết cho b, trong trƣờng hợp các nghiệm d nằm trong khoảng [0, n-1] thì các nghiệm đồng dƣ theo modulo. Các phép tính cơ bản trong không gian modulo Cho n là 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,. Nếu a, b Zn thì: (a + b) mod n = Vì vậy, phép cộng modulo (và phép trừ modulo) có thể đƣợc thực hiện mà không cần thực hiện các phép chia dài.
Phép nhân modulo của a và b đƣợc thực hiện bằng phép nhân thông thƣờng a với b nhƣ các số nguyên bình thƣờng, sau đó lấy phần dƣ của kết quả sau khi chia cho n. Độ phức tạp của thuật toán 1/. Chi phí của thuật toán. Chi phí phải trả cho một quá trình tính toán gồm chi phí 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 một 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ã hóa. Thuật toán A tính trên dữ liệu vào e phải trả một giá nhất định.
Ký hiệu: tA(e) là giá thời gian và lA(e) là giá bộ nhớ. Độ phức tạp về bộ nhớ: tA(n) = max { lA(e), với |e| n}, n là “kích thƣớc” đầu vào của thuật toán. Độ phức tạp về thời gian: lA(n) = max { tA(e), với |e| n}. Độ 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 tồn tại các số n0 , c mà PT(n) c.
Độ phức tạp đa thức: Độ phức tạp PT(n) đƣợc gọi là đa thức, nếu nó tiệm cận tới đa thức p(n). 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 là đa thức. Hàm một phía và hàm cửa sập một phía 1/. Hàm một phía.
Hàm f(x) đƣợc gọi là hàm một phía nếu tính xuôi y = f(x) thì dễ, nhƣng tính ngƣợc x = f-1(y) lại rất khó. Trong trƣờng hợp này “khó” có nghĩa là để tỉnh ra đƣợc kết quả thì phải mất rất nhiều thời gian để tính toán. Hàm một phía y = f(x) = gx (mod p) với p là số nguyên tố lớn (g là phần tử nguyên thủy mod p). Hàm cửa sập một phía a/.
Hàm f(x) đƣợc gọi là hàm cửa sập một phía nếu tính “xuôi” y = f(x) thì “dễ”, tính x = f-1 (y) lại rất “khó”. Tuy nhiên có cửa sập Z để tính x = f-1 (y) là dễ. Nếu chỉ biết a và n thì tính x = f-1 (y) là rất khó, nhƣng nếu biết cửa sập p và q, thì tính đƣợc f-1 (y) là “dễ”. Giới thiệu Để đảm bảo an toàn thông tin lƣu trữ trong máy tính hay bảo đảm thông tin trên đƣờng truyền tin, ngƣời ta phải “che giấu” các thông tin này.
+ “Che” thông tin 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. + “Giấu” thông tin là cất giấu thông tin trong bản tin khác, và ngƣời khác cũng khó nhận ra. Trong chƣơng này chúng ta sẽ bàn về “mã hóa” thông tin. 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 khóa có thể. + E là 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ã.
Hiện có 2 loại hệ mã hóa chính: hệ mã hóa khóa đối xứng và mã hóa khóa bất đối xứng. Hệ mã hóa khóa đối xứng 1/. Hệ mã hóa khóa đối xứng là hệ mã hóa có khóa lập mã và khóa giải mã là “giống nhau”, theo nghĩa biết đƣợc khóa này thì “dễ” tính đƣợc khóa kia. Vì vậy phải giữ bí mật cả hai khóa.
Đặc biệt có một số hệ mã hóa có khóa lập mã và khóa giải mã trùng nhau (ke = kd), nhƣ hệ mã hóa “dịch chuyển” hay DES. Ƣu điểm: + 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. Hạn chế: + Hệ mã hóa khóa đối xứng chƣa thật an toàn với lý do sau: Khóa phải đƣợc giữ bí mật tuyệt đối vì biết đƣợc khóa này dễ tính đƣợc khóa kia và ngƣợc lại. + Vấn đề thỏa thuận khóa và quản lý khóa chung là khó khăn và phức tạp.
Ngƣời gửi và ngƣời nhận phải luôn thống nhất về khóa. Việc thay đổi khóa là rất khó và dễ bị lộ. Khóa chung phải đƣợc gửi cho nhau trên kênh an toàn.