Báo cáo Mã hoá đồng cấu và ứng dụng

Hệ mã hoá Elgamal có tính chất đồng cấu, nhờ nó có thể tính được kết quả trong cuộc bỏ phiếu “chọn một trong hai”, mà không cần giải mã từng lá phiếu. Sơ đồ chia sẻ bí mật Shamir phối hợp với hệ mã hoá Elgamal còn có tính chất đặc biệt hơn nữa, nhờ nó có thể chia lá phiếu thành nhiều mảnh, cử tri gửi mỗi mảnh cho một thành viên ban kiểm phiếu, khi khớp các mảnh phiếu lại sẽ được nội dung đầy đủ của lá phiếu. ...
Nội dung trích xuất từ tài liệu:
Báo cáo " Mã hoá đồng cấu và ứng dụng "Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 26 (2010) 44-48 Mã hoá đồng cấu và ứng dụng Trịnh Nhật Tiến*, Đặng Thu Hiền, Trương Thị Thu Hiền, Lương Việt Nguyên Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, ĐHQGHN, 144 Xuân Thủy, Hà Nội, Việt Nam Nhận ngày 8 tháng 10 năm 2009 Tóm tắt: Hệ mã hoá Elgamal có tính chất đồng cấu, nhờ nó có thể tính được kết quả trong cuộc bỏ phiếu “chọn một trong hai”, mà không cần giải mã từng lá phiếu. Sơ đồ chia sẻ bí mật Shamir phối hợp với hệ mã hoá Elgamal còn có tính chất đặc biệt hơn nữa, nhờ nó có thể chia lá phiếu thành nhiều mảnh, cử tri gửi mỗi mảnh cho một thành viên ban kiểm phiếu, khi khớp các mảnh phiếu lại sẽ được nội dung đầy đủ của lá phiếu. Bài báo này trình bày các tính chất trên và chỉ ra ứng dụng của chúng trong bỏ phiếu từ xa.1. Tính chất đồng cấu của hệ mã hóa Elgamal∗ Ek (m) là hàm mã hoá bản rõ m theo tham số ngẫu nhiên bí mật k. Hệ mã hóa E được gọi là có tính chất1.1. Hệ mã hóa Elgamal (⊕, ⊗)- đồng cấu, nếu với tham số k=k1+k2, Chọn số nguyên tố lớn p sao cho bài toán thỏa mãn công thức đồng cấu:logarit rời rạc trong Zp là khó giải, g là phần tử Ek1 (m1) ⊗ Ek2 (m2) = Ek (m1 ⊕ m2), trongsinh trong Zp* . Chọn tập bản rõ P = Zp , chọn đó m1, m2 là 2 bản rõ, k1, k2 là 2 tham sốtập bản mã C ={(a, b) / a, b ∈Zp }. ngẫu nhiên bí mật. a ∈Zp* , khóa công Chọn khóa bí mật làkhai là h = g a . 1.3. Hệ mã hóa Elgamal có tính chất đồng cấu Để mã hóa m, ta chọn số ngẫu nhiên bí mậtk, bản mã là (x, y) = Ek (m) = ( g k, h k m). a) Hệ mã hoá Elgamal có tính chất đồng cấu, vì Tài liệu được giải mã là m = y / x a . với k = k1 + k2 , ta có: Ek1 (m1) = (gk1 , hk1 m1), Ek2 (m2) = (gk2, hk2 m2) thoả mãn công thức đồng cấu:1.2. Khái niệm mã hoá đồng cấu Ek1 (m1)*Ek2 (m2) = (gk1 gk2 , hk1 hk2 m1 m2) Cho tập bản rõ P tạo thành nhóm với phép = ( gk1+ k2 , hk1+ k2 m1 m2 )tính ⊕, tập bản mã C tạo thành nhóm với phép = ( gk , hk m1 m2 ) = Ek (m1 m2).tính ⊗. b) Trường hợp chọn thông tin m = gv, trong đó_______ v = 0 hoặc v = 1:∗ Tác giả liên hệ. ĐT: 84-4-37547064 Bởi vì: E-mail: tientn@vnu.edu.vn 44 T.N. Tiến và nnk. / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 26 (2010) 44-48 45 Eki (gvi) = (xi, yi) = (gki , hki g vi), i = 1, 2. V1 chọn ngẫu nhiên k1 = 5, mã hóa v1 = 0 thành (x1, y1) = (35, 95 * 30 ) = (35, 95 ). Do đó: V2 mã hóa lá phiếu của mình như sau và gửi (x1, y1) * (x2, y2) = (x1x2, y1y2) = tới Ban kiểm phiếu: (gk1+k2 , hk1+k2 gv1+v2). [1] V2 chọn ngẫu nhiên k2 = 3, mã hóa v2 = 1 thành (x2, y2) = (33, 93 * 31 ) = ( 33, 93 * 3).2. Ứng dụng hệ mã hóa đồng cấu Elgamal V3 mã hóa lá phiếu của mình như sau và gửicho loại bỏ phiếu có/ không tới Ban kiểm phiếu: V3 chọn ngẫu nhiên k3 = 3, mã hóa v3 = 1 Bài toán: Cần lấy ý kiến về một việc nào thành (x3, y3) = (33, 93 * 31 ) = (33, 93 * 3).đó, cử tri phải ghi vào lá phiếu: đồng ý (1) hay V4 mã hóa lá phiếu của mình như sau và gửikhông đồng ý (0). tới Ban kiểm phiếu: Nội dung lá phiếu được mã hoá và gửi về V4 chọn ngẫu nhiên k4 = 7, mã hóa v4 = 0Ban kiểm phiếu. Vấn đề là Ban kiểm phiếu tính t ...