1

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Trịnh Thị Nhẫn

NGHIÊN CỨU CHỮ KÍ SỐ VÀ BÀI TOÁN
BỎ PHIẾU TỪ XA

Chuyên ngành: Khoa Học Máy Tính
Mã số: 60.48.01
Người hướng dẫn khoa học: TS Hồ Khánh Lâm
TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2012 2MỞ ĐẦU

Để đáp ứng các nhu cầu trao đổi thông tin qua các thiết
bị điện tử nói chung và qua mạng Internet nói riêng. Mật mã

Chương 3: Phân tích thiết kế và xây dựng ứng dụng mô hình
hóa cho bài toán bỏ phiếu từ xa
Trong luận văn em sử dụng các phương pháp mã hóa cổ
điển, mã hóa đối xứng, mã hóa công khai… được thể hiện bằng
ngôn ngữ lập trình C# trên nền của asp.net để xây dựng mô
hình hóa và cơ sở dữ liệu em sử dụng SQL server 2005.

4

CHƯƠNG 1
TỔNG QUAN VỀ MẬT MÃ
VÀ CÁC PHƯƠNG PHÁP MÃ HÓA
Nội dung của chương bao gồm các phần sau:
 Mật mã học và các yêu cầu bảo mật thông tin
 Các phương pháp mã hóa
 Khái niệm chữ kí số
 Cơ sở toán học của lý thuyết số
 Mã hóa công khai Elgamal

- Không chối bỏ được
- Chống lặp lại
1.2. Các phương pháp mã hóa:
1.2.1. Các phương pháp mã hóa cổ điển:
1.2.1.1. Phương pháp chuyển vị:
Phương pháp này là đổi chỗ lại các kí tự trong văn bản
rõ làm cho đối phương không thể hiểu được nội dung thông
báo
Trong phương pháp này ta sử dụng một số kĩ thuật sau: 6

- Đảo ngược toàn bộ văn bản gốc.
- Mã hóa theo mẫu hình học.
1.2.1.2. Phương pháp thay thế:
Phương pháp này mã hóa bằng cách thay đổi một hay
một nhóm kí tự của văn bản gốc bằng một hay một nhóm các
kí tự khác để tạo thành văn bản mã. Bên nhận chỉ việc đảo
ngược trình tự thay thế trên văn bản mã là có được văn bản
gốc.
Một số kĩ thuật thay thế:
- Thay thế đơn giản.
- Thay thế nhiều hàng.
1.2.2. Mã khóa đối xứng:
Phương pháp mã khóa đối xứng là phương pháp sử
dụng cùng một khóa cho cả quá trình mã hóa và mật mã.
Một số thuật toán trong mã khóa đối xứng: DES, RC4.
1.2.3. Mã khóa bất đối xứng:
Mật mã hóa công khai là một dạng mật mã hóa cho

Số a được gọi là chia hết cho số b ≠ 0 hay b là ước số của a
nếu a = b * m trong đó a, b, m là các số nguyên. Ta kí hiệu b|a 8

1.3.2.2. Số nguyên tố và số nguyên tố cùng nhau:
Một số nguyên p > 1 gọi là số nguyên tố nếu nó chỉ có các ước
± 1 và ± p.
Định lí cơ bản của số học: Mọi số nguyên a > 1 đều có thể
được phân tích một cách duy nhất dưới dạng các lũy thừa của
các số nguyên tố khác nhau.
a = b
1
x1
+ b
2
x2
+ b
3
x3
+…+b
i
xi

Trong đó b
1
, b
2
, b

+
thì chúng ta định nghĩa a
mod n phần dư của phép chia a cho n. Với ví dụ trên ta có: r =
a mod n.
Hai số nguyên a và b được gọi là đồng dư với nhau theo modul
n nếu và chỉ nếu:
a mod n = b mod n và kí hiệu là a  b mod (n)
chú ý: nếu a  0 mod (n) thì n|a
Từ việc tính đồng dư theo mod n ta tách được số nguyên
thành n lớp mỗi lớp chứa các số nguyên đồng dư với nhau theo
(mod n) và tập các lớp này được kí hiệu là: Z/nZ và chứa đúng
n phần tử thuộc đoạn [0, n-1].
1.3.2.5. Định lí Fermat và định lí Euler:
 Định lí Fermat:
Nếu p là một số nguyên tố và a là một số nguyên thì a
p

a (mod p).
Nếu a không chia hết cho p tức là (a(mod p) ≠ 0) thì a
p-1

1 (mod p).
 Định lí Euler: Nếu gcd(a,m) = 1 thì a
Ф(m)
= 1 mod m.
Trong trường hợp m là số nguyên tố thì Ф(m) = m-1 và ta
có định lí Fermal
1.3.2.6. Định lí Trung Quốc về phần dư:
Giả sử m
1




r
i
iii
MyMax
1
mod

Trong đó M
i
= M / m
i
và y
i
= M
i
-1
mod m
i
với 1 ≤ i ≤ r
1.3.2.7. Không gian rời rạc của phép lấy Logarit:
Ta kí hiệu F
p
là tập các lớp đồng dư theo Modul p hay F
p
=
Z/pZ = (0, 1, 2,…, p-1)
Z/pZ


11

Ta định nghĩa: Một sơ đồ chữ kí số là một bộ 5 (P, A,K,S,
V) thỏa mãn các điều kiện sau:
- P là tập hữu hạn các bức điện.
- A là tập hữu hạn các chữ kí.
- K là không gian khóa hay tập hữu hạn các khóa.
Với mỗi k  K tồn tại một thuật toán kí sig
k
 S và là một
thuật toán xác minh ver
k
 V. Mỗi sig
k
: P  A và ver
k
: P x A
 {true, false} là những hàm sao cho mỗi bức điện x  P và
mỗi chữ kí y  A thỏa mãn phương trình sau đây.
ver
k
=



False
true

Với mỗi k  K hàm sig

Trong đó p, ,  là công khai và a là bí mật.
Với K = (p, , a, ) và
một bộ số ngẫu nhiên (mật) k  Z
p-1
định nghĩa:
sig
k
(x,y)=( r,s) ; trong đó : r = 
k
mod p và
s = (x - a*r) k
-1
mod (p-1)
.

Nếu y = sig(x)
Nếu y ≠ sig(x) 12

Với x, r  Zp và s  Zp-1.

CHƯƠNG 2
BỎ PHIẾU TỪ XA
Nội dung của chương bao gồm các phần sau:
 Vấn đề bỏ phiếu từ xa
 Quy trình bỏ phiếu từ xa
 Các kĩ thuật bỏ phiếu từ xa
2.1. Vấn đề bỏ phiếu từ xa:

2.2. Quy trình bỏ phiếu từ xa:
Hiện nay, người ta đã nghiên cứu và thử nghiệm một số quy
trình bỏ phiếu từ xa, mỗi qui trình có ưu nhược điểm riêng,
trong chương này chúng ta chỉ nghiên cứu sơ đồ bỏ phiếu như
sau: 14
Hình 2.1. Quy trình bỏ phiếu từ xa.
Trộn phiếu
Sơ đ
ồ chia sẻ
bí m
ật
Cử tri Ban đăng kí Ban kiểm phiếu
Hòm phiếu
Lá phi
ếu

không có thông tin định danh.
Quá trình bỏ phiếu kiểu này được coi là “nặc danh”!
Theo phương thức bỏ phiếu “điện tử”, mỗi lá phiếu phải có
thông tin định danh.
Nó có thể là một con số x nào đó và phải khác nhau. Trên mỗi
lá phiếu phải có chữ ký trên số định danh x, thì lá phiếu mới có
giá trị để bầu cử.
Cử tri biến đổi x thành y trước khi đưa cho Ban KP kí xác
nhận. Ban KP ký vào y, mà không biết đó là số định danh x đã
bị che dấu.Họ trao chữ ký trên y là z cho CT.
Cử tri “xóa mù” trên z sẽ được chữ ký của Ban KP trên số định
danh x, như vậy CT có quyền bầu cử. 16

2.3.2. Chia sẻ bí mật ngưỡng Shamir và Mã hóa
Elgamal:
2.3.2.1. Mã hóa đồng cấu Elgamal:
 Hệ mã hóa Elgamal:
 Khái niệm mã hóa đồng cấu.
Cho P là tập bản rõ, tạo thành nhóm với phép tính .
Cho C là tập bản mã, tạo thành nhóm với phép tính .
E
k
(m) là hàm mã hóa bản rõ m theo tham số ngẫu nhiên k.
Cho 2 văn bản rõ cần mã hóa: m1, m2
Cho k1,k2 là 2 tham số ngẫu nhiên
Hệ mã hóa được gòi là có tính chất đồng cấu nếu có tham
số k mà: E

2.3.3. Chia sẻ bí mật ngưỡng Shamir phối hợp với mã
hóa Elgamal:
2.3.3.1. Kĩ thuật chia sẻ bí mật:
Là kĩ thuật phân chia khóa k cho 1 tập m thành viên,
sao cho t thành viên bất kì có thể tính được khóa k nhưng
không một nhóm gồm (t-1) thành viên nào có thể làm được
điều đó, người phân chia khóa không nằm trong t thành viên
đó.
2.3.3.2. Chia sẻ bí mật ngưỡng Shamir phối hợp với mã
hóa Elgamal.
Ban kiểm phiếu (KP) phải giải mã mới biết lá phiếu ghi
gì.Thực tế có thể có 1 người hay 1 nhóm người của Ban KP
muốn biết trước nội dung lá phiếu để thực hiện gian lận bầu cử
(sửa lại nội dung lá phiếu)
Để đảm bảo 1 người hay 1 nhóm người của Ban KP không
thể biết trước nội dung lá phiếu, người ta dùng kỹ thuật “Chia
sẻ bí mật”
2.3.3.3. Ứng dụng sơ đồ chia sẻ bí mật ngưỡng Shamir
phối hợp với mã hóa Elgamal.
Giả sử Cử tri mã hóa lá phiếu của mình sau đó phân
chia lá phiếu thành t mảnh với t là số thành viên Ban kiểm
phiếu KP, việc phân chia được thực hiện sao cho chỉ khi tất cả
các thành viên của Ban KP đồng ý thì Ban KP mới có thể biết
rõ được nội dung lá phiếu của cử tri. 18

Sau khi Ban kiểm phiếu KP nhận được phiếu bầu cử
của cử tri, mỗi thành viên chỉ được giữ một phần của lá phiếu.

3.1.1. Mô hình cài đặt chữ kí số:
Xây dựng chương trình chữ kí điện tử với thứ tự các bước thực
hiện như sau:
- Nhập vào một bản tin cần kí.
- Sử dụng lược đồ chữ kí số Elgamal để tạo khóa công
khai và khóa riêng.
- Kết hợp bản tin cần kí và khóa riêng để tạo chữ kí điện
tử.
- Gán chữ kí điện tử và bản tin rồi mã hóa, mã hóa bằng
hệ mã hóa DES.
- Truyền bản tin đền bên nhận (bản tin mã hóa + khóa bí
mật).
- Bên nhận sử dụng khóa bí mật để giải mã bản tin và
kiểm tra chữ kí số. 20

3.1.2. Mô hình cài đặt bỏ phiếu từ xa:
Xây dựng ứng dụng cho quá trình bỏ phiếu điện tử - mô hình
bỏ phiếu có/không cho một công ty. Quy trình thực hiện như
sau:
- Xây dựng cơ sở dữ liệu cho quá trình bỏ phiếu.
- Cung cấp thẻ cử tri cho các nhân viên.
- Các cử tri sử dụng thẻ cử tri được xác minh và tham gia
bỏ phiếu.
- Ban kiểm phiếu KP thực hiện kiểm phiếu mà không
biết nội dung lá phiếu là gì.
3.2. Phân tích và thiết kế chương trình:
3.2.1. Phân tích và thiết kế chương trình chữ kí số:

- Tính nghịch đảo Module.
- Tính a^k mod n.
- Module kiểm tra tính nguyên tố của một số dựa vào
hàm kiểm tra xác suất Miller-Rabin.
- Sinh số nguyên tố p lớn.
- Chọn ngẫu nhiên số nguyên x nhỏ hơn số nguyên y. 22

3.2.2. Phân tích và thiết kế chương trình bỏ phiếu từ xa:
 Phân tích chương trình:
- Nhập danh sách các cử tri tham gia bỏ phiếu và thông
tin cá nhân của cử tri.
- Cung cấp thẻ cử tri cho các nhân viên được tham gia bỏ
phiếu.
- Kiểm tra thẻ trước khi cử tri bỏ phiếu
- Kiểm phiếu và niêm yết kết quả.
 Thiết kế chương trình:
 Thiết kế cơ sở dữ liệu:
- Bảng lưu giữ các thông tin của cử tri: Xác định danh
sách các cử tri tham gia bầu cử. Bảng tbl_ThongTinCuTri.
- Bảng mô tả mối quan hệ giữa Nhân viên và số thẻ cử
tri: Mỗi nhân viên chỉ có một số thẻ cử tri. Bảng tbl_NV_CT
- Bảng xác định cử tri đã tham gia bỏ phiếu hay chưa,
mỗi cử tri chỉ được bỏ phiếu 1 lần, bảng này nhằm xác định
những cử tri nào chưa bỏ phiếu và cử tri nào đã bỏ phiếu. Bảng
tbl_CT_BP
- Bảng lưu nội dung lá phiếu của các cử tri: Nội dung của
lá phiếu đã được cử tri mã hóa và được lưu trong bảng này.


24KẾT LUẬN
Trên đây em đã trình bày những nghiên cứu của em về
luận văn “Nghiên cứu chữ kí số và bài toán bỏ phiếu từ xa”.
Mặc dù đã cố gắng nghiên cứu nhưng do lĩnh vực khó và còn
mới mẻ nên luận văn còn nhiều thiếu sót. Em sẽ cố gắng tiếp
tục nghiên cứu để hoàn thiện luận văn hơn trong thời gian tới.
Để có thể ứng dụng được trong thực tế.
 Những đóng góp của luận văn:
- Xây dựng một chương trình chữ kí số.
- Xây dựng ứng dụng cho quá trình bỏ phiếu từ xa – mô
hình bỏ phiếu từ xa có/không cho một công ty.
 Kiến nghị về những nghiên cứu tiếp theo:
- Xây dựng mô hình ứng dụng nhỏ minh họa nhiều hơn 1
sơ đồ chữ kí số và mô hình một quá trình bỏ phiếu từ
xa.
- Nghiên cứu phát triển chương trình trên Internet để mở
rộng liên kết.
Em xin gửi lời cảm ơn chân thành tới TS Hồ Khánh Lâm đã tận
tình hướng dẫn em hoàn thành luận văn, đồng cảm ơn các thầy
cô và các bạn trong lớp đã giúp đỡ em.