Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu một số thuật toán hệ mật mã khoá công khai Elgamal và ứng dụng

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

PHẠM THỊ TUYẾT

NGHIÊN CỨU MỘT SỐ THUẬT TOÁN HỆ MẬT MÃ

KHOÁ CÔNG KHAI ELGAMAL VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

THÁI NGUYÊN - 2015

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

PHẠM THỊ TUYẾT

NGHIÊN CỨU MỘT SỐ THUẬT TOÁN HỆ MẬT MÃ

KHOÁ CÔNG KHAI ELGAMAL VÀ ỨNG DỤNG

Chuyên ngành: Khoa học máy tính

Mã số: 60 48 01 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Ngƣời hƣớng dẫn khoa học: TS NGUYỄN NGỌC CƢƠNG

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

THÁI NGUYÊN - 2015

LỜI CAM ĐOAN

Tôi xin cam đoan luận văn “ Nghiên cứu một số thuật toán hệ mật mã

khoá công khai ElGamal và ứng dụng” là công trình nghiên cứu của cá nhân tôi

tìm hiểu, nghiên cứu dƣới sự hƣớng dẫn của TS Nguyễn Ngọc Cƣơng. Các kết quả

là hoàn toàn trung thực, toàn bộ nội dung nghiên cứu của luận văn, các vấn đề

đƣợc trình bày đều là những tìm hiểu và nghiên cứu của chính cá nhân tôi hoặc là

đƣợc trích dẫn từ các nguồn tài liệu đƣợc trích dẫn và chú thích đầy đủ.

TÁC GIẢ LUẬN VĂN

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Phạm Thị Tuyết

LỜI CẢM ƠN

Học viên xin bày tỏ lời cảm ơn chân thành tới tập thể các thầy cô giáo Viện

công nghệ thông tin, các thầy cô giáo Trƣờng Đại học Công nghệ thông tin và

truyền thông - Đại học Thái Nguyên đã mang lại cho học viên kiến thức vô cùng quý

giá và bổ ích trong suốt quá trình học tập chƣơng trình cao học tại trƣờng. Đặc biệt

học viên xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo TS Nguyễn Ngọc Cƣơng -

Học viện an ninh đã định hƣớng khoa học và đƣa ra những góp ý, gợi ý, chỉnh sửa

quý báu, quan tâm, tạo điều kiện thuận lợi trong quá trình nghiên cứu hoàn thành

luận văn này.

Cuối cùng, học viên xin chân thành cảm ơn các bạn bè đồng nghiệp, gia

đình và ngƣời thân đã quan tâm, giúp đỡ và chia sẻ với học viên trong suốt quá

trình học tập.

Do thời gian và kiến thức có hạn nên luận văn chắc không tránh khỏi

những thiếu sót nhất định. Học viên rất mong nhận đƣợc những sự góp ý quý báu

của thầy cô và các bạn.

Thái Nguyên, ngày tháng năm 2015

HỌC VIÊN

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Phạm Thị Tuyết

iii

MỤC LỤC

LỜI CAM ĐOAN ........................................................................................................ i

LỜI CẢM ƠN ............................................................................................................ ii

MỤC CÁC HÌNH VẼ, ĐỒ THỊ ................................................................................ vi

MỞ ĐẦU .................................................................................................................... 1

CHƢƠNG 1 ............................................................................................................... 3

TỔNG QUAN VỀ CÁC HỆ MẬT MÃ ..................................................................... 3

1.1. Lý thuyết toán học ............................................................................................... 3

1.1.1. Số nguyên tố, UCLN, BCNN ....................................................................... 3

1.1.2. Nhóm, vành, trƣờng, trƣờng hữu hạn ........................................................... 3

1.1.3 Số học Modulo (phép tính đồng dƣ) .............................................................. 5

1.1.4. Không gian rời rạc của phép lấy Logarit ...................................................... 6

1.1.5. Định lí Fermat và định lí Euler ...................................................................... 6

1.1.6. Hàm một phía và hàm một phía có cửa sập .................................................. 6

1.1.7. Định lí Trung Quốc về phần dƣ: ................................................................... 7

1.2. Mật mã ................................................................................................................ 7

1.2.1. Khái niệm ...................................................................................................... 7

1.2.2. Những yêu cầu đối với hệ mật mã ................................................................ 8

1.2.3. Hệ mã hóa RSA ............................................................................................ 8

1.2.4. Hệ mã hóa Paillier ......................................................................................... 9

1.2.5. Hệ mã hóa ElGamal .................................................................................... 10

1.2.6 Hệ mật đƣờng cong Eliptic ........................................................................... 10

1.3. Chữ ký điện tử ................................................................................................... 11

1.3.1. Sơ đồ chữ ký điện tử ................................................................................... 11

1.3.2. Chữ ký mù RSA .......................................................................................... 12

1.3.3. Chữ ký nhóm (Group Signature) ................................................................ 13

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

1.4. Khái niệm xác thực điện tử ............................................................................... 15

1.5. Hàm băm (Hash Function) ................................................................................ 16

CHƢƠNG :HỆ MẬT MÃ ELGAMAL CẢI TIẾN VÀ MÃ HÓA ĐỒNG CẤU ... 17

2.1. Hệ mã hóa ElGamal cải tiến.............................................................................. 17

2.1.1. Thuật toán mật mã ElGamal cổ điển .......................................................... 17

2.1.2. Một số thuật toán ElGamal cải tiến [3] ....................................................... 18

2.1.2.1 Thuật toán thứ nhất ............................................................................. 18

2.1.2.2 Thuật toán thứ hai ............................................................................... 21

2.1.2.3 Thuật toán thứ ba ................................................................................. 23

2.2. Hệ mã hóa đồng cấu .......................................................................................... 26

2.2.1. Khái niệm mã hóa đồng cấu........................................................................ 26

2.2.2. Hệ mã hoá Elgamal có tính chất đồng cấu .................................................. 26

2.2.3. Mô hình hệ mã hóa đồng cấu ElGamal cho mô hình bỏ phiếu có/không .... 27

2.3. Sơ đồ chia sẻ bí mật .......................................................................................... 29

2.3.1. Khái niệm chia sẻ bí mật ............................................................................. 29

2.3.2. Giao thức “Chia sẻ bí mật” Shamir ............................................................. 31

2.3.2.1. Khái niệm sơ đồ ngƣỡng A(t, m) ........................................................ 31

2.3.2.2. Chia sẻ khoá bí mật K ......................................................................... 32

2.3.2.3. Khôi phục khóa bí mật K từ t thành viên........................................... 33

CHƢƠNG 3: ỨNG DỤNG HỆ MẬT MÃ ELGAMAL TRONG BÀI TOÁN BỎ

PHIẾU THĂM DÒ TÍN NHIỆM ............................................................................. 37

3.1. Hệ thống bỏ phiếu điện tử [5] ........................................................................... 37

3.1.1. Khái niệm bỏ phiếu điện tử ......................................................................... 37

3.1.2. Yêu cầu của hệ thống bỏ phiếu điện tử ....................................................... 38

3.1.3. Những vấn đề cần giải quyết ...................................................................... 38

3.1.4.Các thành phần trong hệ thống bỏ phiếu điện tử ......................................... 39

3.1.5. Quy trình bài toán bỏ phiếu điện tử ............................................................ 39

3.2. Ứng dụng hệ mật ElGamal trong quá trình bỏ phiếu thăm dò tín nhiệm.......... 41

3.2.1. Thiết lập ...................................................................................................... 41

3.2.3. Mở phiếu bầu .............................................................................................. 43

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

3.3. Xây dựng chƣơng trình thử nghiệm mô hình bỏ phiếu thăm dò tín nhiệm ...... 44

3.3.1. Môi trƣờng cài đặt và thử nghiệm .............................................................. 44

3.3.2. Phát biểu bài toán ........................................................................................ 44

3.3.3 Các đối tƣợng của hệ thống ........................................................................ 45

3.3.4. Phân tích và thiết kế chƣơng trình bỏ phiếu: .............................................. 45

3.3.5 Các chức năng chính .................................................................................... 45

3.3.6. Thứ tự thực hiện chƣơng trình .................................................................... 46

3.3.7. Kết quả thực nghiệm ................................................................................... 47

3.4. Phân tích vấn đề bảo mật cần đạt đƣợc ............................................................. 56

3.5. Các tính chất đạt đƣợc ....................................................................................... 56

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ĐỀ TÀI ................................................. 57

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

TÀI LIỆU THAM KHẢO ........................................................................................ 58

MỤC CÁC HÌNH VẼ, ĐỒ THỊ

Hình 1.1. Sơ đồ mã hóa và giải mã ............................................................................ 7

Hình 2.1. Sơ đồ bỏ phiếu đồng ý/ không đồng ý ....................................................... 28

Hình 2.2. Sơ đồ ngƣỡng Shamir .............................................................................. 32

Hình 3.1. Sơ đồ Quy trình bỏ phiếu điện tử ............................................................. 40

Hình 3.2. Sơ đồ mô tả bỏ phiếu thăm dò tín nhiệm ................................................. 41

Hình 3.3. Sơ đồ giai đoạn bỏ phiếu tín nhiệm ......................................................... 42

Hình 3.4. Giao diện chính của chƣơng trình ............................................................ 47

Hình 3.5. Ban tổ chức đăng nhập vào hệ thống ...................................................... 48

Hình 3.6. Thông báo tạo cơ sở dữ liệu cán bộ thành công. ...................................... 48

Hình 3.7. Bảng danh sách cán bộ sau khi đƣợc ban tổ chức tạo cơ sở dữ liệu ....... 49

Hình 3.8. Thông báo tạo cơ sở dữ liệu ban kiểm phiếu thành công. ....................... 49

Hình 3.9. Cán bộ đăng nhập vào hệ thống ............................................................... 49

Hình 3.10. Quá trình bỏ phiếu .................................................................................. 50

Hình 3.11. Cán bộ cập nhật thông tin ...................................................................... 50

Hình 3.12. Thông báo nhắc nhở lựa chọn của cán bộ .............................................. 51

Hình 3.13. Thông báo xác nhận lựa chọn của cán bộ .............................................. 51

Hình 3.14. Ban kiểm phiếu đăng nhập vào hệ thống ............................................... 52

Hình 3.14. Mảnh khóa của ban kiểm phiếu ............................................................. 52

Hình 3.15. Ban kiểm phiếu cập nhật thông tin ......................................................... 53

Hình 3.16. Thông báo xác nhận quá trình gửi mảnh khóa ....................................... 53

Hình 3.17. Xác nhận tổng hợp đủ các mảnh khóa ................................................... 54

Hình 3.18. Thông báo ghép mảnh khóa thành công ................................................ 54

Hình 3.19. Kết quả bỏ phiếu .................................................................................... 55

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hình 3.20. Cơ sở dữ liệu trong mô hình bỏ phiếu tín nhiệm ................................... 56

MỞ ĐẦU

1. Tính khoa học và cấp thiết của đề tài

Cùng với sự phát triển của công nghệ thông tin, hiện nay vấn đề an toàn thông

tin trở nên hết sức cần thiết trên qui mô toàn cầu. Đảm bảo tính bảo mật, khả năng

xác thực nguồn gốc gói tin trong quá trình truyền tải thông tin qua môi trƣờng

không an toàn nhƣ Internet là một vấn đề nóng trong nghiên cứu và thực tiễn. Để

đảm bảo tính bảo mật và xác thực ngƣời ta cần phải mã hoá, có một số thuật toán

mã hoá công khai rất nổi tiếng: RSA, ElGamal, ... Tuy nhiên, các hệ mật mã này có

nhƣợc điểm là không có cơ chế xác thực thông tin đƣợc bảo mật (nguồn gốc, tính

toàn vẹn) do đó chúng không có khả năng chống lại một số dạng tấn công giả mạo

trong thực tế. Chính vì vậy hiện nay, ngƣời ta [3] đã đề xuất một số cải tiến hệ mật

mã ElGamal. Ƣu điểm của các thuật toán mới đề xuất này là ở chỗ cho phép bảo

mật và xác thực thông tin một cách đồng thời mà mức độ an toàn của các thuật toán

mới đề xuất không nhỏ hơn mức độ an toàn của thuật toán ElGamal xét theo khả

năng chống thám mã khi tấn công trực tiếp vào các thủ tục mã hóa và giải mã.

Để góp phần nâng cao hiệu năng của phƣơng pháp mã hóa ElGamal. Trong

luận văn này, học viên đặt mục tiêu nghiên cứu, thử nghiệm thuật toán mã hóa

Elgamal và các cải tiến mới của các tác giả đã đƣa ra, so sánh hiệu quả của chúng

và kiểm định thuật toán này bằng một ứng dụng trong thực tiễn. Đây là bài toán lựa

chọn các khả năng trong các giải pháp đã có bằng việc mã hóa và xác thực nhƣ bài

toán bỏ phiếu điện tử do các cán bộ tiến hành hoặc bài toán thăm dò tín nhiệm lãnh

đạo tại một đơn vị. Những bài toán này luôn đòi hỏi tính bí mật, ví dụ trong bỏ

phiếu điện tử (e-voting), việc đảm bảo tính đúng đắn bảo mật ở đây có thể bao gồm

cả việc không để lộ danh tính cử tri (ai bỏ phiếu cho ứng viên nào?), tính duy nhất

(mỗi cử tri đảm bảo chỉ tối đa 1 lần bỏ phiếu)...

2. Đối tƣợng và phạm vi nghiên cứu

- Đối tƣợng nghiên cứu: Hệ mật khóa công khai ElGamal và các cải tiến của

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

hệ mật mã.

- Phạm vi nghiên cứu: Nghiên cứu cải tiến dựa trên thuật toán đã có và xây

dựng chƣơng trình ứng dụng trong bài toán thăm dò dƣ luận về mức độ tín nhiệm

đối với một đơn vị (ở đây là tổng công ty xăng dầu Việt Nam).

3. Hƣớng nghiên cứu của đề tài

- Nghiên cứu các đề xuất một số thuật toán mật mã khóa công khai đƣợc phát

triển từ hệ mật ElGamal của các tác giả đã công bố để xây dựng chƣơng trình ứng

dụng trong bài toán bỏ phiếu thăm dò dƣ luận về mức độ tín nhiệm.

- Đánh giá ƣu điểm của các thuật toán mới do các tác giả đã đề xuất về mức độ

bảo mật và xác thực thông tin một cách đồng thời.

4. Những nội dung nghiên cứu chính

Luận văn đƣợc trình bày trong 3 chƣơng, có phần mở đầu, phần kết luận,

phần mục lục, phần tài liệu tham khảo. Các nội dung cơ bản của luận văn đƣợc trình

bày theo cấu trúc sau:

Chương 1: TỔNG QUAN VỀ CÁC HỆ MẬT MÃ

Trong chƣơng này tổng trình bày một số khái niệm cơ bản trong toán học mà

các hệ mã hoá thƣờng sử dụng nhƣ: mod, số nguyên tố, vành Zn, các phép toán

cộng, nhân, bài toán logarrit rời rạc trên không gian Zn.... Sau đó đƣa ra các khái

niệm mật mã, các thuật toán mã hoá, chữ ký số phục vụ cho việc mã hoá thông tin.

Chương 2: HỆ MẬT MÃ ELGAMAL CẢI TIẾN VÀ MÃ HÓA ĐỒNG CẤU

Tập trung nghiên cứu một số thuật toán mật mã ElGamal cải tiến, tính chất

đồng cấu của hệ mật ElGamal và sơ đồ chia sẻ bí mật theo ngƣỡng Shamir.

Chương 3: ỨNG DỤNG HỆ MẬT MÃ ELGAMAL TRONG BÀI TOÁN BỎ PHIẾU

THĂM DÒ TÍN NHIỆM

Cài đặt thử nghiệm thuật toán hệ mật ElGamal cải tiến và kỹ thuật chia sẻ

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

khóa bí mật Shamir.

CHƢƠNG 1

TỔNG QUAN VỀ CÁC HỆ MẬT MÃ

1.1. Lý thuyết toán học

1.1.1. Số nguyên tố, UCLN, BCNN

a), Số nguyên tố: là số nguyên dƣơng lớn hơn 1và chỉ có duy nhất 2 ƣớc là 1và

chính nó.

b), Ƣớc chung lớn nhất (ƢCLN):

Cho hai số nguyên a và b, 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(b\a). Khi đó b là ƣớc của a và a là bội của b.

Số nguyên d đƣợc gọi là ƣớc chung của các số nguyên a1, a2, .., an nếu nó là

ƣớc của tất cả các số đó.

d đƣợc gọi là ƣớc chung lớn nhất của a1, a2, .., an nếu d > 0 và là số lớn nhất

trong tập hợp các ƣớc chung của các số đó. Ký hiệu d = gcd ( a1, a2, .., an ) hay d

= UCLN (a1, a2, .., an ). a) Bội chung nhỏ nhất (BCNN):

Số nguyên m đƣợc gọi là bội chung của các số nguyên a1, a2, .., an nếu nó là

bội của tất cả các số đó.

m đƣợc gọi là bội chung nhỏ nhất của a1, a2, .., an nếu m > 0 và là số nhỏ nhất

trong tập hợp các bội chung của các số đó. Kí hiệu m = lcm(a1, a2, .., an ) hay m

= BCNN(a1, a2, .., an ).

Hai số nguyên tố p và q đƣợc gọi là nguyên tố cùng nhau nếu ƣớc chung lớn

nhất của chúng bằng 1. Kí hiệu: UCLN (m, n) = 1

1.1.2. Nhóm, vành, trƣờng, trƣờng hữu hạn

a) Phép toán hai ngôi

Cho G là một tập hơp. Phép toán hai ngôi (*) là một ánh xạ:

(*):

Ví dụ: G = Z. Phép toán (*) là phép (+)

b) Nhóm

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

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ồn tại phần tử trung lập e G: e * x = x * e = x,

- Tồn tại phần tử nghịch đảo x’ G: x’ * x = x * x’ = e

Nhóm Cyclic: 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 để 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à nhóm Cyclic có phần tử sinh là 1.

Cấp của nhóm Cyclic: Cho (G,*) là nhóm Cyclic với phần tử sinh là g, và phần tử trung lập e. Nếu tồn tại số tự nhiên nhỏ nhất n mà gn = e thì G sẽ chỉ gồm có n phần tử khác nhau: e, g, g1, g2,…, g n-1. Khi đó G đƣợc gọi là nhóm Cyclic hữu hạn cấp n. Nếu không tồn tại số tự nhiên n để gn = e thì G có cấp vô hạn.

c, Vành

Vành là một tập R với 2 toán tử + (cộng) và * (nhân) thỏa mãn các điều kiện

là nhóm Abel

là nửa nhóm

Phép nhân phân phối đối với phép cộng: với các phần tử tùy ý x, y, z X ta có:

x(y + z) = xy + z và

(y + z) x = yx + zx

Nếu phép nhân là giao hoán thì R đƣợc gọi là vành giao hoán

d, Trƣờng

Giả sử F là tập hợp khác rỗng, trên đó có hai phép toán đóng hai ngôi bất

kỳ, chẳng hạn ký hiệu là + (cộng) và * (nhân). F là một trƣờng nếu và chỉ nếu:

(F,+) là nhóm giao hoán với phần tử đơn vị là "0"

(F\{0},*) là nhóm giao hoán với phần tử đơn vị là "1"

Các phép toán cộng và nhân có tính chất phân phối: a(b+c) = ab + ac

Số phần tử của một trƣờng đƣợc gọi là bậc của một trƣờng. Một trƣờng có số

phần tử hữu hạn đƣợc gọi là trƣờng hữu hạn, một trƣờng có số phần tử vô hạn đƣợc

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

gọi là trƣờng vô hạn.

Trƣờng hữu hạn là trƣờng chứa hữu hạn các phần tử. Mọi trƣờng hữu hạn có một

số nguyên tố là đặc số của trƣờng. Một trƣờng F có đặc số thì với mọi a F,

e. Trƣờng hữu hạn Fp:

Cho p là số nguyên tố. Trƣờng hữu hạn Fp bao gồm tập các số nguyên {0, 1, 2,

.., p-1} cùng với các phép toán:

Phép cộng: Nếu a, b Fp , ta có a + b = r, với r là phần dƣ khi chia a + b cho p

và . Đây gọi là phép cộng modulo p.

Phép nhân: Nếu a, b Fp , ta có a.b = s, với s là phần dƣ khi chia a.b cho p

và . Đây gọi là phép nhân modulo p.

Phép nghịch đảo: Nếu a 0), phép nghịch đảo của a modulo p, ký Fp (a

hiệu là a-1, nếu tồn tại duy nhất số nguyên c Fp sao cho a.c = 1.

Trƣờng hữu hạn F2m:

Trƣờng F2m, kí hiệu F2m = {0,1, a1, a2, ..., a2m-2}, đƣợc gọi là trƣờng hữu

1, ...,

m-1 trong F2m sao cho mỗi

hạn nhị phân. Khi đó tồn tại m phần từ

phẩn tử F2m có thể viết duy nhất dƣới dạng:

0 + a1

1 + ... + am-1 m-1 với ai

A = a0

1, ..., m-1 } đƣợc gọi là cơ sở của F2m trên F2. Với mỗi cơ sở

Một bộ { 0,

nhƣ vậy thì một phần tử của trƣờng có thể biểu diễn dƣới dạng xâu bit ( a0a1 am-1).

1.1.3 Số học Modulo (phép tính đồng dƣ)

Cho mỗi số nguyên dƣơng n và một số nguyên a bất kì nếu chúng ta chia a cho

n đƣợc thƣơng là q và phần dƣ là r: a = q*n

+ r với 0 = < r < n và q = [a/n]

Kí hiệu [x] là số nguyên lớn nhất nhỏ hơn hoặc bằng x.

Nhƣ vậy, nếu a Z và n Z+ 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ỉ

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

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.1.4. Không gian rời rạc của phép lấy Logarit

Ta kí hiệu Fp là tập các lớp đồng dƣ theo Modul p hay Fp = Z/pZ = (0, 1,

2,…, p-1)

Zp/Z* là những tập gồm các số nguyên tố cùng nhau với p hay tập các phần tử

có nghịch đảo trong Z/pZ. Ta kí hiệu Fp* = Z/pZ*

Với p là số nguyên tố thì Z/pZ = Z/pZ * = Fp = Fp* = (0, 1, 2, …, p-1).

1.1.5. Định lí Fermat và định lí Euler

* Định lí Fermat:

a (mod p).

Nếu p là một số nguyên tố và a là một số nguyên thì ap Nếu a không chia hết cho p tức là (a(mod p) ≠ 0) thì ap-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í Fermat.

1.1.6. Hàm một phía và hàm một phía có cửa sập

a, Hàm một phía:

Một hàm một phía là hàm mà dễ dàng tính toán ra quan hệ một chiều nhƣng

rất khó để tính ngƣợc lại.

Ví dụ: Biết giả thiết x thì có thể dễ dàng tính ra f(x), nhƣng nếu biết f(x) thì

khó tính ra đƣợc x. Trong trƣờng hợp này “khó” có nghĩa là để tính ra đƣợc kết quả

thì phải mất nhiều thời gian để tính toán.

b, Hàm một phía có cửa sập:

F(x) đƣợc gọi là hàm một phía có cửa sập nếu tính xuôi y = f(x) thì dễ tính ngƣợc x = f-1(y ) thì khó tuy nhiên nếu có “ cửa sập” thì vấn đề tính ngƣợc trở nên

dễ dàng. Cửa sập ở đây là một điều kiện nào đó giúp chúng ta dễ dàng tính ngƣợc.

Ví dụ: Hộp thƣ là một ví dụ khác về hàm một phía có cửa sập. Bất kỳ ai cũng

có thể bỏ thƣ vào thùng. Bỏ thƣ vào thùng là một hành động công cộng. Mở thùng

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

thƣ không phải hành động công cộng. Nó là khó khăn, bạn sẽ cần đến mỏ hàn để

phá hoặc những công cụ khác. Tuy nhiên, nếu bạn có “ cửa sập” ( trong trƣờng hợp

này là chìa khóa của hòm thƣ) thì công việc mở hòm thƣ thật dễ dàng.

1.1.7. Định lí Trung Quốc về phần dƣ:

Giả sử m1, m2,…,mr là các số nguyên dƣơng nguyên tố cùng nhau từng đôi

một và cho a1, a2,…,ar là các số nguyên. Khi đó, hệ r đồng dƣ thức: x= ai mod mi

(1 ≤ i ≤ r) sẽ có một nghiệm duy nhất theo modul M= m1, m2,…, mr đƣợc tính

-1 mod mi với 1 ≤ i ≤ r

theo công thức sau:

Trong đó Mi = M / mi và yi = Mi

1.2. Mật mã

1.2.1. Khái niệm

- Bản rõ (plaintext or cleartext): Chứa các xâu ký tự gốc, thông tin trong bản

rõ là thông tin cần mã hoá để giữ bí mật.

- Bản mã (ciphertext): Chứa các ký tự sau khi đã đƣợc mã hoá, mà nội dung

đƣợc giữ bí mật.

- Mật mã học (Crytography): Là khoa học để giữ thông tin đƣợc an toàn.

- Sự mã hoá (Encryption): Quá trình che dấu thông tin bằng phƣơng pháp nào

đó để làm ẩn nội dung bên trong gọi là sự mã hoá.

- Sự giải mã (Decryption): Quá trình biến đổi trả lại bản mã thành bản rõ.

Bản rõ gốc

Bản rõ

Bản mã mãmax max

Mã hóa

Giải mã

Hình 1.1. Sơ đồ mã hóa và giải mã

Quá trình mã hoá và giải mã đƣợc thể hiện trong sơ đồ sau:

- Hệ mật mã: Là một hệ bao gồm 5 thành phần (P, C, K, E, D) thoả mãn các

tính chất sau:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

P (Plaintext): Là tập hợp hữu hạn các bản rõ có thể.

C (Ciphertext): Là tập hợp hữu hạn các bản mã có thể.

K (Key): Là tập hợp các bản khoá có thể.

E (Encrytion): Là tập hợp các qui tắc mã hoá có thể.

D (Decrytion): Là tập hợp các qui tắc giải mã có thể.

Với mỗi k có một hàm lập mã ek, ek:P, và một hàm giải mã dk, dk:C sao cho: dk (ek(x)) =x, với  x € P. .

- Một thông báo thƣờng đƣợc tổ chức dƣới dạng bản rõ. Ngƣời gửi sẽ làm

nhiệm vụ mã hoá bản rõ, kết quả thu đƣợc gọi là bản mã. Bản mã này đƣợc gửi đi

trên một đƣờng truyền tới ngƣời nhận sau khi nhận đƣợc bản mã ngƣời nhận giải

mã nó để tìm hiểu nội dung.

Ek(P) = C và Dk (C) = P

1.2.2. Những yêu cầu đối với hệ mật mã

Cung cấp một mức cao về tính bảo mật, tính toàn vẹn, tính chống chối bỏ và

tính xác thực:

 Tính bảo mật: Bảo đảm bí mật cho các thông báo và dữ liệu bằng việc che

dấu thông tin nhờ các kỹ thuật mã hóa.

 Tính toàn vẹn (integrity): Bảo đảm với các bên rằng bản tin không bị thay

đổi trên đƣờng truyền tin.

 Tính không thể chối bỏ (Non-repudiation): Có thể xác nhận rằng tài liệu đã

đến từ ai đó, ngay cả khi họ cố gắng từ chối nó.

 Tính xác thực (Authentication): Cung cấp hai dịch vụ:

o Nhận dạng nguồn gốc của một thông báo và cung cấp một vài bảo

đảm rằng nó là đúng sự thực.

o Kiểm tra định danh của ngƣời đang đăng nhập một hệ thống, tiếp tục

kiểm tra đặc điểm của họ trong trƣờng hợp ai đó cố gắng kết nối và giả danh là

ngƣời sử dụng hợp pháp.

1.2.3. Hệ mã hóa RSA

Sinh khóa:

Giả sử A và B cần trao đổi thông tin bí mật thông qua một kênh không an

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

toàn (ví dụ nhƣ Internet). Với thuật toán RSA, A đầu tiên cần tạo ra cho mình

cặp khóa gồm khóa công khai và khóa bí mật theo các bƣớc sau:

- Chọn 2 số nguyên tố lớn p và q với

- Tính: n = p.q

- Tính giá trị hàm số Ơle

- Chọn một số tự nhiên e sao cho và là số nguyên tố cùng

nhau với .

- Tính d sao cho .

Khóa công khai (n,e)

Khóa bí mật (n, d)

Mã hóa:

Giả sử B muốn gửi đoạn thông tin M cho A. Đầu tiên B chuyển M thành

một số m < n theo một hàm có thể đảo ngƣợc (từ m có thể xác định lại M) đƣợc

thỏa thuận trƣớc. Lúc này B có m và biết n cũng nhƣ e do A gửi. B sẽ tính c là bản

mã hóa của m theo công thức:

c = me mod n

Giải mã: A nhận c từ B và biết khóa bí mật d. A có thể tìm đƣợc m từ c theo công

thức sau:

m = cd mod n

1.2.4. Hệ mã hóa Paillier

Hệ mã hóa Paillier đƣợc đặt theo tên và phát minh của Pascal Paillier năm

1999. Đây là thuật toán bất đối xứng cho hệ mật mã khóa công khai.

Sinh khóa:

- Chọn hai số nguyên tố lớn p và q

- Tính n = p * q sao cho gcd(n, (p-1)(q-1)) = 1

- Chọn ngẫu nhiên thỏa mãn với

và

Khóa công khai là (n, g);

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Khóa bí mật là: (p, q, )

Mã hóa:

nhƣ sau: Mã hóa thông điệp m

c = gmrn mod n2

Giải mã:

Sử dụng khóa bí mật để giải mã nhƣ sau:

1.2.5. Hệ mã hóa ElGamal

Hệ mật mã ElGamal đƣợc T. ElGamal đề xuất năm 1985, dựa vào bài toán tính

logarit rời rạc và sau đó đã nhanh chóng đƣợc sử dụng rộng rãi không những trong

vấn đề bảo mật truyền tin mà còn trong các vấn đề xác nhận và chữ ký điện tử.

* Tạo cặp khóa (bí mật, công khai( (a, b):

Chọn số nguyên tố p sao cho bài toán logarit rời rạc trong Zp là “khó” giải.

Chọn phần tử nguyên thủy . Tính khóa công khai h ≡ ga mod p.

Định nghĩa tập khóa: K = {(p, g, a, h): h ≡ ga mod p}. Các giá trị p, g, h đƣợc

công khai, phải giữ bí mật a. Với bản rõ x P và bản mã y C , với khóa k K.

* Lập mã : Chọn ngẫu nhiên bí mật r Zp-1,

Bản mã là y = ek(x, r) = (y1, y2). Trong đó : y1 = gr mod p và y2 = x * hr mod p a )-1 mod p. * Giải mã : dk (y1, y2) = y2( y1

1.2.6 Hệ mật đƣờng cong Eliptic - Định nghĩa: Cho p > 3 là số nguyên tố. Đƣờng cong Eliptic y2 = x3 + ax + b trên Zp là tập các nghiệm (x,y) Zp x Zp của đồng dƣ thức y2 = x3 + ax + b(mod p)

0(mod p) (để đa thức Trong đó a, b Zp là các hằng số thỏa mãn 4a3 + 27b2

x3 + ax + b không có nghiệm bội) cùng với điểm đặc biệt 0 đƣợc gọi là điểm vô hạn.

- Định lý Hasse: Việc xây dựng các hệ mật mã trên dƣờng cong Eliptic bao gồm việc

lựa chọn đƣờng cong E thích hợp và một điểm G trên E gọi là điểm cơ sở. Xét trƣờng

K là Fq.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

N là số điểm của E trên Fq (trƣờng hữu hạn q phần tử). Khi đó:

. . Từ định lý Hasse suy ra E(Fq) = q +1 – t trong dó

- Hệ mật trên đƣờng cong Eliptic

Hệ ElGamal làm việc với nhóm Cyclic hữu hạn. Năm 1978, Kobliz đã đƣa

một hệ trên ECC dựa trên hệ ElGamal.

Để xây dựng hệ mã hóa dựa trên đƣờng cong Eliptic ta chọn đƣờng cong

E(a,b) và một điểm G trên đƣờng cong làm điểm cơ sở. Mỗi ngƣời dùng A một

khóa bí mật nA là một số nguyên và sinh khóa công khai PA = nA *G.

Khi đó hệ mã hóa đƣờng cong Eliptic đƣợc xây dựng tƣơng tự hệ mã hóa

ElGamal, trong đó thuật toán mã hóa và giải mã đƣợc xác định nhƣ sau:

Thuật toán mã hóa: Giả sử ngƣời dùng A muốn gửi thông điệp cần mã hóa Pm

tới ngƣời dùng B, chọn một số ngẫu nhiên k và gửi thông điệp mã hóa Cm đƣợc tính

nhƣ sau: (PB là khóa công khai của B).

Thuật toán giả mã: Để giải thông điệp , ngƣời dùng

B thực hiện tính nhƣ sau:

Chỉ B mới có thể giải mã vì B có nB (là khóa bí mật).

1.3. Chữ ký điện tử

1.3.1. Sơ đồ chữ ký điện tử

Một sơ đồ chữ ký điện tử S là một bộ năm: S = (P, A, K, S, V) thỏa mãn các

điều kiện dƣới đây:

P: tập hữu hạn các thông báo có thể có.

A: tập hữu hạn các chữ ký số có thể có.

K: tập hữu hạn các khóa có thể.

S: tập các thuật toán ký.

V: tập các thuật toán kiểm thử.

Mỗi khóa K’ K có hai thành phần K’ = (K1, K2), K1 là khóa bí mật dùng

để ký, còn K2 là khóa công khai để xác thực chữ ký.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Với mỗi K’ = (K1, K2), trong S có thuật toán kí:

x P y= Sigk(x)

Và trong V có thuật toán kiểm thử: Nếu

Hai thuật toán thỏa mãn điều kiện sau với mọi

Sai Nếu y

Sigk(x)

Verk(x, y) = Đúng Nếu y = Sigk(x)

1.3.2. Chữ ký mù RSA

a) Khái niệm

Chữ ký mù đƣợc David Chaum đƣa ra vào năm 1983. Trong hệ chữ ký

thông thƣờng, ngƣời ký phải đƣợc nắm rõ nội dung văn bản cần kỹ, có thể lƣu bản

sao. Trong hệ chữ ký mù (blind signature), ngƣời ký sẽ không đƣợc thấy rõ nội

dung mà mình ký, các thông điệp cần đƣợc kí bị “che” đi. Tuy nhiên hệ chữ ký

cũng đảm bảo cho ngƣời ký có thể kiểm tra tính hợp lệ của thông tin cần ký. Chữ ký

mù thƣờng đƣợc dùng trong các vấn đề đòi hỏi sự ẩn danh, nó dƣợc ứng dụng phổ

biến trong tiền điện tử, bỏ phiếu điện tử…

Nội dung M trƣớc khi ngƣời A đƣa cho ngƣời kí B sẽ bị làm mù thành M’.

Ngƣời kí lúc này sẽ kí trên M’ chứ không phải trên M. Sau khi có đƣợc chữ kí trên

M’, A xóa mù để có đƣợc chữ kí trên M. Nhƣ vậy ngƣời A vẫn có chữ kí hợp lệ của

ngƣời B trên M mà B không biết thông tin gì về M.

Ví dụ: A chuẩn bị một văn bản M, cho vào một phòng bì A4, có kèm một tờ

giấy than, rồi dán lại và đƣa cho B. B chỉ có thể ký lên phía ngoài phong bì, nhƣng

chữ ký sẽ đƣợc tạo ra trong văn bản bên trong thông qua tờ giấy than. Mặc dù B

không thể biết đƣợc nội dung thật của văn bản này, nhƣng có thể đánh giá đƣợc tính

trung thực của A (không tạo ra gì xấu cho B) mà một phép kiểm tra theo phƣơng

pháp thách thức - đáp ứng.

b) Sơ đồ chữ ký RSA

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

- Chọn p, q nguyên tố lớn .

Tính n = p.q; (n) = (p-1)(q-1).

(n).

mod (n).

Chọn b nguyên tố cùng Chọn a nghịch đảo với b; a = b-1 - Ký trên x: Sig (x) = xa mod n

- Kiểm tra chữ ký: Ver (x,y)= True x yb mod n

Ví dụ:

- p = 3; q = 5; n =15; (n) = 8;

Chọn b = 3; a = 3

mod 15 = 8

- Ký x = 2: Chữ ký : y = xa Kiểm tra: x = yb mod n = 23 mod n = 83 mod 15 =2 (chữ ký đúng)

c) Sơ đồ chữ ký mù RSA

Giả sử ngƣời A muốn có đƣợc chữ kí của B trên văn bản M theo sơ đồ

chữ kí RSA nhƣng không muốn cho B biết nội dung của M. A cần thực hiện các

bƣớc sau:

Ví dụ: Giả sử B dùng sơ đồ chữ ký RSA (n, p, q, b, a). - A che dấu M bởi y = M*rb (mod n), (r đƣợc chọn sao cho tồn tại phần tử

nghịch đảo r-1 (mod n)).

- A gửi bí danh y cho B - B ký trên bí danh y đƣợc chữ ký z: z = ya (mod n)

- B gửi chữ ký z cho A.

- A "xoá mù" trên z sẽ tìm lại đƣợc chữ ký trên M bằng cách tính toán: Unblind(z) = z*r-1 = (M*rb)a * r-1 = (xa *r) * r-1 = Ma (mod n)

A đã có đƣợc chữ ký của B trên M, đó là Ma (mod n)

Nhƣ vậy ta đã đạt đƣợc mục đích: A đã nhận đƣợc chữ kí của B (là: Ma mod n)

mà B không biết nội dung của M.

1.3.3. Chữ ký nhóm (Group Signature)

Chữ ký nhóm Chữ ký nhóm là chữ ký điện tử đại diện cho một nhóm ngƣời,

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

một tổ chức. Các thành viên của một nhóm đƣợc phép ký trên thông điệp với tƣ cách

là ngƣời đại diện cho nhóm.

Chữ ký nhóm đƣợc David Chaum và Van Heyst giới thiệu lần đầu tiên vào

năm 1991. Kể từ đó đến nay đã có nhiều nhà khoa học nghiên cứu và đƣa ra một số

sơ đồ chữ ký nhóm khác nhau nhƣ sơ đồ chữ ký nhóm của Chen và Pedersen năm

1994, sơ đồ chữ ký nhóm của Camenisch và Stadler năm 1997.

Đặc điểm của chữ ký nhóm:

- Chỉ có thành viên trong nhóm mới có thể ký tên vào bản thông báo đó.

- Ngƣời nhận thông điệp có thể kiểm tra xem chữ ký đó có đúng là của nhóm

đó hay không, nhƣng ngƣời nhận không thể biết đƣợc ngƣời nào đã ký vào thông điệp đó.

- Trong trƣờng hợp cần thiết chữ ký có thể đƣợc “mở” (có hoặc là không có sự

giúp đỡ của thành viên trong nhóm) để xác định ngƣời nào đã ký vào thông điệp đó.

Một số hệ chữ ký nhóm:

- Undeniable Signature (chữ kí không thể phủ nhận)

- MultiSignature (đồng ký)

- Proxy Signature (chữ ký ủy nhiệm)

Các thành phần của sơ đồ chữ kí nhóm:

- Ngƣời quản lý nhóm

- Các thành viên trong nhóm

- Ngƣời không thuộc nhóm

Một sơ đồ chữ kí nhóm thƣờng bao gồm 5 thủ tục:

- KeyGen: Là thuật toán sinh khóa công khai của nhóm, khóa bí mật của

ngƣời quản lý nhóm:

KeyGen()  (pk, gmsk)

Trong đó pk là khóa công khai của nhóm (dùng để xác minh chữ kí của nhóm),

gmsk là khóa bí mật của nhóm. Nếu số ngƣời trong nhóm là cố định thì:

KeyGen()  (pk, gmsk,ski)

Trong đó ski là khóa bí mật của thành viên thứ i trong nhóm.

- Join: Cho phép một ngƣời không phải là thành viên trong nhóm muốn tham

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

gia nhóm. Khi gia nhập nhóm, thành viên i sẽ nhận đƣợc khóa bí mật của mình là

ski, ngƣời quản lý nhóm có trách nhiệm lƣu thông tin của thành viên mới này.

- Sig: Khi thành viên i muốn ký thông điệp m đại diện cho nhóm, anh ta sẽ

sử dụng thủ tục:

Sig: Sig(m,ski) 

Chữ ký trên thông điệp m sẽ là .

- Verify: Khi muốn kiểm tra chữ ký có phải là chữ kí đại diện cho nhóm

trên m hay không, ta sử dụng thủ tục:

- Open: Với mỗi chữ ký trên thông điệp m, ngƣời quản lý nhóm có thể xác

định đƣợc thành viên nào đã ký vào thông điệp bằng việc sử dụng thủ tục:

Open(gmsk,m, )

đầu ra của thủ tục là thông tin về thành viên đã ký.

1.4. Khái niệm xác thực điện tử

Xác thực điện tử là việc chứng minh từ xa bằng phƣơng tiện điện tử, sự tồn tại

chính xác và hợp lệ danh tính của một chủ thể khi tham gia trao đổi thông tin điện

tử nhƣ: cá nhân, tổ chức, dịch vụ,... hoặc một lớp thông tin nào đó mà không cần

biết các thông tin đó cụ thể nhƣ thế nào, thông qua thông tin đặc trƣng đại diện cho

chủ thể đó mà vẫn đảm bảo đƣợc bí mật của chủ thể, hoặc lớp thông tin cần chứng

minh.

Xác thực điện tử là việc cần thực hiện trƣớc khi thực sự diễn ra các cuộc trao

đổi thông tin điện tử chính thức.

Việc xác thực điện tử trong hệ thống trao đổi thông tin điện tử đƣợc uỷ quyền

cho một bên thứ ba tin cậy. Bên thứ ba ấy chính là CA (Certification Authority),

một cơ quan có tƣ cách pháp nhân thƣờng xuyên tiếp nhận đăng ký các thông tin

đặc trƣng đại diện cho chủ thể: khoá công khai và lƣu trữ khoá công khai cùng lý

lịch của chủ thể trong một cơ sở dữ liệu đƣợc bảo vệ chặt chẽ. CA chuyên nghiệp

không nhất thiết là cơ quan nhà nƣớc. Điều quan trọng nhất của một CA là uy tín để

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

khẳng định sự thật, bảo đảm không thể có chuyện "đổi trắng thay đen".

Mục đích của việc xác thực điện tử: Chống giả mạo, chống chối bỏ, đảm bảo

tính toàn vẹn, tính bí mật, tính xác thực của thông tin và mục đích cuối cùng là

hoàn thiện các giải pháp an toàn thông tin.

Cơ sở ứng dụng đề xây dựng các giải pháp an toàn cho xác thực điện tử là các

hệ mật mã.

Ứng dụng trong: Thƣơng mại điện tử, trong các hệ thống thanh toán trực

tuyến, là nền tảng của chính phủ điện tử.

1.5. Hàm băm (Hash Function)

Hàm băm là một hàm tính toán có hiệu quả khi ánh xạ các dòng nhị phân có

độ dài tùy ý thành các dòng nhị phân có độ dài cố định nào đó.

Hàm băm yếu: hàm băm đƣợc gọi là yếu nếu cho một thông điệp x thì về

mặt tính toán không tìm ra đƣợc thông điệp x’ khác x sao cho: h(x’) = h(x)

Hàm băm mạnh: hàm băm đƣợc gọi là mạnh nếu về mặt tính toán không tìm

ra đƣợc hai thông điệp x và x’ sao cho: x’ ≠ x và h(x’) = h (x)

Chọn giá trị x ngẫu nhiên, x ϵ x

Tính z = h(x), tính x1 = A(z)

Nếu x1 ≠ x thì x1 và x va chám dƣới h (thành công)

Ngƣợc lại là thất bại.

Hàm băm có tính chất một chiều: hàm băm có tính chất một chiều nếu cho

trƣớc thông điệp rút gọn z thì về mặt tính toán không tìm ra đƣợc thông điệp x sao

cho: h(x) = z

Hàm băm yếu làm cho chữ ký số trở nên tin cậy giống nhƣ việc ký trên

toàn thông điệp.

Hàm băm mạnh có tác dụng chống lại kẻ giả mạo tạo ra hai bản thông điệp có

nội dung khác nhau, sau đó thu nhận chữ ký hợp pháp cho một bản thông điệp dễ

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

đƣợc xác nhận rồi lấy nó giả mạo làm chữ ký của thông điệp thứ 2

CHƢƠNG 2

HỆ MẬT MÃ ELGAMAL CẢI TIẾN

VÀ MÃ HÓA ĐỒNG CẤU

2.1. Hệ mã hóa ElGamal cải tiến

2.1.1. Thuật toán mật mã ElGamal cổ điển

Sơ đồ (ElGamal đề xuất năm 1985)

a/. Sinh khóa (bí mật, công khai) (a, h) :

Chọn số nguyên tố p sao cho bài toán logarit rời rạc trong Zp là “khó” giải.

Chọn phần tử nguyên thuỷ g  Zp* .

Z p*.

Đặt P = Z p*, C = Z p* Chọn khóa bí mật là a  Zp* . Tính khóa công khai h  g a mod p.

Định nghĩa tập khóa: = {(p, g, a, h): h  g a mod p}.

Các giá trị p, g, h đƣợc công khai, phải giữ bí mật a.

Với Bản rõ x  P và Bản mã y  C, với khóa k  định nghĩa:

b/. Lập mã:

Chọn ngẫu nhiên bí mật r  Zp-1,

Bản mã là y = ek (x, r) = (y1, y2) Trong đó y1 = g r (mod p) và y2 = x * h r (mod p)

a) -1 ( mod p) = x.

c/. Giải mã: dk (y1, y2) = y2 (y1

Ví dụ

* Bản rõ x = 1985. Chọn p = 2179, g = 2, a = 365. Tính khóa công khai h = 2 365 mod 2179 = 2175.

* Lập mã: Chọn ngẫu nhiên r = 503.

Bản mã là y = (932, 91), trong đó y1 = 2503 mod 2179 = 932 và y2 = 1985 * 2175 503 mod 2179 = 91

a) -1 mod p = 91(932365)-1 mod 2179 = 1985.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

* Giải mã: x = y2 (y1

Độ an toàn

a/. Hệ mã hóa ElGamal là không tất định, tức là với một bản rõ x và 1 khóa bí

mật a, thì có thể có nhiều hơn một bản mã y, vì trong công thức lập mã còn có thành

phần ngẫu nhiên r.

b/. Độ an toàn của hệ mật ElGamal dựa vào khả năng giải bài toán logarit rời

rạc trong Zp. Theo giả thiết trong sơ đồ thì bài toán này phải là “khó” giải.

Cụ thể nhƣ sau:

Theo công thức lập mã: y = ek (x, r) = (y1, y2), trong đó: y1 = g r mod p và y2 = x * h r mod p Nhƣ vậy muốn xác định bản rõ x từ công thức y2, thám mã phải biết đƣợc r.

Giá trị này có thể tính đƣợc từ công thức y1, nhƣng lại gặp bài toán logarit rời

rạc.

2.1.2. Một số thuật toán ElGamal cải tiến [3]

2.1.2.1 Thuật toán thứ nhất

Thuật toán thứ nhất ở đây có điểm khác biệt cơ bản với thuật toán ElGamal là

ở chỗ thuật toán có cơ chế xác thực nguồn gốc thông tin 2 chiều đƣợc thiết lập dựa

trên việc sử dụng khóa công khai của ngƣời nhận (yB) trong thủ tục mã hóa và khóa

công khai của ngƣời gửi (yA) trong thủ tục giải mã.

a) Thủ tục hình thành tham số và khóa

 Chọn số nguyên tố lớn p sao cho bài toán logarit rời rạc trong Zp là khó giải.

 Chọn g là phần tử sinh của .

 Chọn khóa mật x là số nguyên thỏa mãn: 1 < x < p-1.

 Tính khóa công khai y theo công thức: y = gx mod p

 Giữ bí mật: x; công khai: p, g, y. Khóa công khai y cần phải đƣợc chứng thực

bởi một CA (Certificate Authority) đáng tin cậy.

b) Thủ tục mã hóa

Giả sử ngƣời gửi là A, ngƣời nhận là B. Ngƣời gửi A có khóa bí mật là xA và

khóa công khai là yA. Ngƣời nhận B có khóa bí mật là xB và khóa công khai là yB.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Khi đó, để gửi bản tin M cho B, với: 0 M p, A sẽ thực hiện các bƣớc nhƣ sau:

 Chọn số ngẫu nhiên kA thỏa mãn: 1 kA ( p 1).

 Tính giá trị R theo công thức:

 Sử dụng khóa công khai của B để tính:

 Và gửi ba n mã (C, R) đến ngƣời nhận B.

c, Thủ tục giải mã:

Để khôi phục bản tin ban đầu (M) từ bản mã (C, R) nhận đƣợc, ngƣời nhận B

thực hiện các bƣớc nhƣ sau:

Tính giá trị Z theo công thức: Z = (R x yA)-1 mod p.

Khôi phục bản tin ban đầu (M):

d, Tính đúng đắn của thuật toán mới đề xuất

Điều cần chứng minh ở đây là:

Cho p là số nguyên tố, g là phần tử sinh của , 1 x A , xB p 1 ,

, 1kA p 1 ,

thì . Nếu: Z = (R x yA)-1 mod p,

Chứng minh:

Thật vậy ta có:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

e) Mức độ an toàn của thuật toán

Ở thuật toán này việc tấn công trực tiếp vào thủ tục mã hóa là khó khăn hơn

thuật toán ElGamal, vì ở thuật toán này cả 2 khóa bí mật ngắn hạn (kA) và dài hạn

(xA) của ngƣời gửi cùng đƣợc sử dụng để mã hóa bản tin. Do đó, việc thám mã và

giả mạo, xét trong trƣờng hợp này, chỉ có thể thực hiện thành công khi cả 2 khóa bí

mật đồng thời bị lộ. Từ đây có thể thấy rằng, mức độ an toàn của thuật toán này xét

theo khả năng chống thám mã và chống tấn công làm lộ khóa mật là không nhỏ hơn

mức độ an toàn của thuật toán ElGamal trong khi mức độ chống giả mạo nguồn gốc

bản tin đƣợc bảo mật lại cao hơn thuật toán ElGamal.

Ví dụ:

a, Thủ tục hình thành tham số và khoá

Bản rõ M = 1983. Chọn p = 13669, g = 2

Ngƣời A: xA = 3651.

= 23651 mod 13669 = 12834. Tính khóa công khai yA :

Ngƣời B: xB = 1507.

= 21507 mod 13669 = 3626. Tính khóa công khai yB :

b, Thủ tục mã hoá

 Chọn số ngẫu nhiên kA = 5013.

 Tính giá trị R: = 25013 mod 13669 = 8239

 Sử dụng khóa công khai của B để tính:

C = 1983 x (3626)5013+3651 mod 13669 = 10923

Và gửi ba n mã (10923, 8239) đến ngƣời nhận B.

c, Thủ tục giải mã:

Để khôi phục bản tin ban đầu (M) từ bản mã (10923, 8239) nhận đƣợc, ngƣời

nhận B thực hiện các bƣớc nhƣ sau:

Tính giá trị Z = (R x yA)-1 mod p = (8239 x 12834 )-1 mod 13669 = 13605.

Khôi phục bản tin ban đầu (M):

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

= 10923 x (13605)1507 mod 13669 = 1983.

2.1.2.2 Thuật toán thứ hai

Thuật toán có cách thức thực hiện dƣới dạng một giao thức (protocol). Ngoài

ra, bản mã đƣợc tạo ra bởi thuật toán này chỉ có một thành phần duy nhất.

a) Thủ tục hình thành tham số và khóa

 Chọn số nguyên tố lớn p sao cho bài toán logarit rời rạc trong Zp là khó giải.

 Chọn g là phần tử sinh của .

 Chọn khóa mật x là số nguyên thỏa mãn: 1 < x < (p-1).

 Tính khóa công khai y theo công thức: y = gx mod p

 Giữ bí mật: x; công khai: p, g, y. Khóa công khai y cần phải đƣợc chứng thực

bởi một CA (Certificate Authority) đáng tin cậy.

b) Thủ tục mã hóa

Giả sử ngƣời gửi là A, ngƣời nhận là B. Ngƣời gửi A có khóa bí mật là xA và

khóa công khai là yA. Ngƣời nhận B có khóa bí mật là xB và khóa công khai là yB.

Khi đó, để gửi bản tin M cho B, với: 0 M p, A sẽ thực hiện các bƣớc nhƣ sau:

Bước 1: Đối tƣợng B thực hiện:

 Chọn giá trị kB thỏa mãn: 1 kB ( p 1).

 Tính giá trị RB theo công thức:

 Gửi giá trị RB cho đối tƣợng A.

Bước 2: Đối tƣợng A thực hiện:

 Mã hóa bản tin M theo công thức:

 Và gửi ba n mã C đến đối tƣợng nhận B.

c, Thủ tục giải mã:

Để khôi phục bản tin ban đầu (M) từ bản mã (C) nhận đƣợc, ngƣời nhận B thực

hiện các bƣớc nhƣ sau:

 Tính giá trị Z theo công thức: Z = ( yA)-1 mod p.

 Khôi phục bản tin ban đầu (M):

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

d, Tính đúng đắn của thuật toán

Điều cần chứng minh ở đây là:

Cho p là số nguyên tố, g là phần tử sinh của , 1 x A , xB p 1 ,

1 k B p 1 ,

thì . Nếu: Z = ( yA)-1 mod p,

Chứng minh: Thật vậy ta có:

e) Mức độ an toàn của thuật toán mới đề xuất

Ở thuật toán này có khả năng chống thám mã xét trong trƣờng hợp tấn công

trực tiếp vào thủ tục mã hóa là tƣơng đƣơng với thuật toán ElGamal, nhƣng thủ tục

giải mã của thuật toán có khả năng chống thám mã cao hơn so với thuật toán

ElGamal do việc sử dụng kết hợp đồng thời cả 2 khóa bí mật ngắn hạn (kB) và dài

hạn (xB) của ngƣời nhận (B).

Ví dụ:

a, Thủ tục hình thành tham số

Bản rõ M = 5983. Chọn p = 16127, g = 5

Ngƣời A: xA = 1258.

= 51258 mod 16127 = 4487. Tính khóa công khai yA :

Ngƣời B: xB = 532.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

= 5532 mod 16127 = 3699. Tính khóa công khai yB :

b, Thủ tục mã hoá

Bước 1: Đối tƣợng B thực hiện:

 Chọn giá trị kB = 823.

= 5823 mod 16127 = 3639.  Tính giá trị RB :

 Gửi giá trị RB = 3639 cho đối tƣợng A.

Bước 2: Đối tƣợng A thực hiện:

 Mã hóa bản tin M theo công thức:

C = 5983 x (3639 x 3699)1258 mod 16127 = 5983 x 286 mod 16127 = 1676

 Và gửi ba n mã 1676 đến đối tƣợng nhận B.

c, Thủ tục giải mã:

Để khôi phục bản tin ban đầu (M) từ bản mã (C) nhận đƣợc, ngƣời nhận B thực

hiện các bƣớc nhƣ sau:

 Tính giá trị Z = ( yA)-1 mod 16127 = (4487)-1 mod 16127 = 13665.

 Khôi phục bản tin ban đầu (M):

M = 1676 x (13665)1355 mod 16127 = 1676 x 12349 = 5983

2.1.2.3 Thuật toán thứ ba

Thuật toán có mức độ an toàn xét theo khả năng chống thám mã và giả mạo

cao hơn do thủ tục mã hóa sử dụng đồng thời 2 khóa bí mật ngắn hạn và dài hạn của

ngƣời gửi, còn thủ tục giải mã lại sử dụng đồng thời 2 khóa bí mật ngắn hạn và dài

hạn của ngƣời nhận. Ở thuật toán này, việc thám mã và giả mạo chỉ có thể thực hiện

thành công khi bị lộ đồng thời cả 2 khóa bí mật ngắn hạn và dài hạn.

a) Thủ tục hình thành tham số và khóa

 Chọn số nguyên tố lớn p sao cho bài toán logarit rời rạc trong Zp là khó giải.

 Chọn g là phần tử sinh của .

 Chọn khóa mật x là số nguyên thỏa mãn: 1 < x < (p-1).

 Tính khóa công khai y theo công thức: y = gx mod p

 Giữ bí mật: x; công khai: p, g, y. Khóa công khai y cần phải đƣợc chứng thực

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

bởi một CA (Certificate Authority) đáng tin cậy.

b) Thủ tục mã hóa

Giả sử ngƣời gửi là A, ngƣời nhận là B. Ngƣời gửi A có khóa bí mật là xA và

khóa công khai là yA. Ngƣời nhận B có khóa bí mật là xB và khóa công khai là yB.

Khi đó, để gửi bản tin M cho B, với: 0 M p, A sẽ thực hiện các bƣớc nhƣ sau:

Bước 1: Đối tƣợng B thực hiện:

 Chọn giá trị kB thỏa mãn: 1 kB ( p 1).

 Tính giá trị RB theo công thức:

 Gửi giá trị RB cho đối tƣợng A.

Bước 2: Đối tƣợng A thực hiện:

 Chọn giá trị kA thỏa mãn: 1 kA ( p 1).

 Hình thành phần thứ nhất của bản mã theo công thức:

 Hình thành phần thứ hai của bản mã:

 Và gửi ba n mã (C, R) đến đối tƣợng nhận B.

c, Thủ tục giải mã:

Để khôi phục bản tin ban đầu (M) từ bản mã (C, R) nhận đƣợc, ngƣời nhận B

thực hiện các bƣớc nhƣ sau:

 Tính giá trị Z theo công thức: Z = ( R x yA)-1 mod p.

 Khôi phục bản tin ban đầu (M):

d, Tính đúng đắn của thuật toán mới đề xuất

Điều cần chứng minh ở đây là:

Cho p là số nguyên tố, g là phần tử sinh của , 1 x A , xB p 1 ,

1kA, k B p 1 ,

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

thì . Nếu: Z = ( R x yA)-1 mod p,

Chứng minh: Thật vậy ta có:

e) Mức độ an toàn của thuật toán

Cả 2 khóa bí mật ngắn hạn (kA) và dài hạn (xA) của ngƣời gửi (A) cũng nhƣ

khóa bí mật ngắn hạn (kB) và dài hạn (xB) của ngƣời nhận (B) đều đƣợc sử dụng kết

hợp trong các thủ tục mã hóa và giải mã. Vì vậy, mức độ an toàn của thuật toán xét

theo khả năng chống thám mã trong cả 2 trƣờng hợp tấn công trực tiếp vào thủ tục

mã hóa và giải mã đều cao hơn thuật toán ElGamal.

Ví dụ:

a, Thủ tục hình thành tham số và khoá

Bản rõ M = 2015. Chọn p = 11719, g = 5

Ngƣời A: xA = 7235.

= 57235 mod 11719 = 5984. Tính khóa công khai yA :

Ngƣời B: xB = 9726.

= 59726 mod 11719 = 8872. Tính khóa công khai yB :

b, Thủ tục mã hoá

Bước 1: Đối tƣợng B thực hiện:

 Chọn giá trị kB = 562.

= 5562 mod 11719 = 4814.  Tính giá trị RB :

 Gửi giá trị 4814 cho đối tƣợng A.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Bước 2: Đối tƣợng A thực hiện:

 Chọn giá trị kA = 123.

 Hình thành phần thứ nhất của bản mã:

= 2015 x (4814 x 8872)7358 mod 11719 = 7429.

 Hình thành phần thứ hai của bản mã: R = 5123 mod 11719 = 1066.

 Và gửi ba n mã (7429, 1066) đến đối tƣợng nhận B.

c, Thủ tục giải mã:

Để khôi phục bản tin ban đầu (M) từ bản mã (7429, 1066) nhận đƣợc, ngƣời

nhận B thực hiện các bƣớc nhƣ sau:

 Tính giá trị Z = ( R x yA)-1 mod 11719

 Khôi phục bản tin ban đầu (M):

= (1066 * 5984)-1 mod 11719 = 5641.

M = 7429 x 564110288 mod 11719 = 2015

2.2. Hệ mã hóa đồng cấu

2.2.1. Khái niệm mã hóa đồng cấu

Cho tập bản rõ P tạo thành nhóm với phép tính , tập bản mã C tạo thành

nhóm với phép tính . [4]

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ất (, )- đồng cấu, nếu với tham số k

= k1 + k2, thỏa mãn công thức đồng cấu: Ek1 (m1)  Ek2 (m2) = Ek (m1  m2),

trong đó m1, m2 là 2 bản rõ; k1, k2 là 2 tham số ngẫu nhiên bí mật.

2.2.2. Hệ mã hoá Elgamal có tính chất đồng cấu

Trong hệ mã hóa Elgamal với k = k1 + k2 , ta có [4]:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

thỏa mãn công thức đồng cấu:

- Trƣờng hợp chọn thông tin m = gv, trong đó v = 0 hoặc v = 1 vì:

, i = 1, 2 do đó:

2.2.3. Mô hình hệ mã hóa đồng cấu ElGamal cho mô hình bỏ phiếu có/không

Mô hình bỏ phiếu này đƣợc đề xuất bởi Cramer (1997), nó sử dụng thuộc tính

đặc biệt của thuật toán mã hóa đồng cấu để thiết lập kiểm chứng phổ quát trong

cuộc bỏ phiếu với quy mô lớn, mặt khác vẫn giữ đƣợc sự riêng tƣ bảo mật cho mỗi

lá phiếu. Cho PT (plaintext) là tập bản rõ, CT (Ciphertext) là tập các bản mã. Và

PT là một nhóm đối với phép , CT là một nhóm đối với phép . Kí hiệu

là kí hiệu mã hóa thông điệp m sử dụng thông số r1. Một mô hình mã hóa

là ( ) - đồng cấu nếu: cho và , tồn tại r sao cho

Trong mô hình bỏ phiếu điện tử, biến thể của thuật toán mã hóa ElGamal

đƣợc sử dụng [7]. Cho p, q là các số nguyên tố lớn sao cho q|p-1, và Gq là nhóm

con của cấp q. Đối với mô hình này, các lá phiếu là m1 = g, m0 = 1/g (yes, no),

với g là phần tử sinh cố định của Gq. Khóa bí mật là s đƣợc chọn ngẫu nhiên, khóa

công khai tƣơng ứng là , với g là phần tử sinh của Gq. Một cử tri i

gửi lá phiếu của mình theo mẫu với và chứng

minh tính hợp lệ của lá phiếu.

Kết thúc cuộc bỏ phiếu, ban bỏ phiếu sẽ tính toán:

Cho tất cả các lá phiếu hợp lệ. cuối cùng, ban bỏ phiếu tính và

nhận đƣợc , với T là sự khác biệt của những lá phiếu yes và những

lá phiếu no. Vì trong thực tế T không phải là lũy thừa quá lớn, nên thuật toán

“Baby step gaint step” hoặc phƣơng thức Pollard có thể giải quyết đƣợc.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Bài toán:

Công ty X cần lấy ý kiến về việc tiếp tục sản xuất sản phẩm Y hay không?

Các thành viên của công ty (gọi là cử tri) bỏ phiếu để quyết định bằng cách: đồng ý

(1) hay không đồng ý (0). Nội dung lá phiếu đƣợc mã hoá và gửi về Ban kiểm

phiếu. Vấn đề là Ban kiểm phiếu tính kết quả bỏ phiếu nhƣ thế nào, trong khi

không biết nội dung từng lá phiếu ? (Vì chúng đã đƣợc mã hóa).

Giải quyết:

Cử tri ghi ý kiến vào lá phiếu

Giả sử có 4 cử tri tham gia bỏ phiếu là: V1, V2, V3, V4 và chọn các giá trị mi =

{0,1} tƣơng ứng với đồng ý hay không đồng ý: V1 = 0, V2 = 1, V3 = 1, V4 = 0.

Chọn phần tử sinh g, hệ mã hóa ElGamal đƣợc sử dụng ở đây có các khóa nhƣ

sau: Ban kiểm phiếu chọn khóa bí mật a, tính khóa công khai h = ga

Ví dụ: Chọn phần tử sinh g = 3, hệ mã hóa ElGamal đƣợc sử dụng ở đây có các

khóa nhƣ sau: Khóa bí mật a = 2, khóa công khai h = ga = 32 = 9.

Mỗi cử tri Vi, chọn khóa ngẫu nhiêu bí mật k để mã hóa lá phiếu m của mình

thành (x,y) = (gk, hkm).

Hình 2.1. Sơ đồ bỏ phiếu đồng ý/ không đồng ý

Cử tri mã hóa lá phiếu

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Các cử tri Vi mã hóa lá phiếu của mình nhƣ sau và gửi tới ban kiểm phiếu:

- V1 chọn ngẫu nhiêu k1, mã hóa V1 thành (x1, y1) = (g k1, h k1*gm1) - V2 chọn ngẫu nhiêu k2, mã hóa V2 thành (x2, y2) = (gk2, hk2*gm2) - V3 chọn ngẫu nhiêu k3, mã hóa V3 thành (x3, y3) = ((gk3, gk3*gm3) - V4 chọn ngẫu nhiêu k4, mã hóa V4 thành (x4, y4) = ((gk4, gk4*gm4) Ví dụ: - V1 chọn ngẫu nhiêu k1 = 5, mã hóa V1 = 0 thành (x1, y1) = (35, 95*30) =

(35,95) = (243, 59049).

- V2 chọn ngẫu nhiêu k2 = 3, mã hóa V2 = 1 thành (x2 ,y2) = (33, 93*31) =

(33,93*3) = (27,2187)

- V3 chọn ngẫu nhiêu k3 = 3, mã hóa V3 = 1 thành (x3, y3) = (33, 93*31) =

(33,93*3) = (27,2187)

- V4 chọn ngẫu nhiêu k4 = 7, mã hóa V4 = 0 thành (x4, y4) = (37, 97* 30)= (37,

97* 3)= (2187,14348907)

Ban kiểm phiếu tính kết quả:

Ban kiểm phiếu không cần giải mã từng lá phiếu, vẫn có thể tính đƣợc kết quả

bỏ phiếu bằng cách tính nhân các lá phiếu đã đƣợc mã hóa.

Theo tính chất đồng cấu thì tích của phép nhân trên chính là kết quả bỏ

phiếu. Cụ thể tích của 4 giá trị lá phiếu đã đƣợc mã hóa ở ví dụ trên là:

Giải mã (X,Y) bằng cách tính: m = g v = Y / X a = 9 1 8 * 3 2 / ( 3 1 8 ) 2 = 3 2

N h ƣ v ậ y s ố p h i ế u đ ồ n g ý ( g h i 1 ) l à 2 . [ 1 4 ]

2.3. Sơ đồ chia sẻ bí mật

2.3.1. Khái niệm chia sẻ bí mật

Thông tin quan trọng (Tin gốc) cần giữ bí mật, không nên trao cho một ngƣời

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

nắm giữ, mà phải chia thông tin đó thành nhiều mảnh và trao cho mỗi ngƣời một

hay một số mảnh. Thông tin gốc chỉ có thể đƣợc xem lại, khi mọi ngƣời giữ các

mảnh đều nhất trí. Các mảnh thông tin đƣợc khớp lại để đƣợc Tin gốc.

- Thông tin cần giữ bí mật đƣợc chia thành nhiều mảnh và trao cho mỗi thành

viên tham gia nắm giữ.

Thông tin bí mật Các mảnh đƣợc chia

- Khi các mảnh đƣợc khớp lại sẽ cho ta tín hiệu gốc

Các mảnh đƣợc chia Thông tin bí mật

Ví dụ: Cần sử dụng phƣơng pháp “chia sẻ bí mật” là chia nhỏ “lá phiếu” trong

bỏ phiếu điện tử. Trên thực tế nhiều khi ngƣời ta chƣa thật tin vào một nhóm ít ngƣời

trong ban kiểm phiếu, ngƣời bỏ phiếu đƣợc phép chia “lá phiếu” thành nhiều “mảnh

phiếu”, sau đó gửi cho mỗi ngƣời trong ban kiểm phiếu một “mảnh”. Nhƣ vậy từng

thành viên trong ban kiểm phiếu khó thể đọc đƣợc nội dung “lá phiếu”.

Khi mọi thành viên trong ban kiểm phiếu nhất trí xem nội dung lá phiếu, thì các

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

“mảnh phiếu” mới đƣợc khớp lại để có đƣợc “lá phiếu” ban đầu của ngƣời bỏ phiếu.

Chia nhỏ “lá phiếu“ có thể hiểu theo nhiều nghĩa: Có thể là chia khóa bí mật

để giải mã nội dung lá phiếu; Có thể chính nội dung lá phiếu (tên, mã số ứng cử

viên, ý kiến đồng ý hay không đồng ý, …) đƣợc chia thành các “mảnh tin” (trên

thực tế bản thân mỗi mảnh tin đều không có nghĩa).

Phƣơng pháp “Chia sẻ bí mật” đƣợc thể hiện bằng “sơ đồ” chỉ rõ cách thức

“Chia sẻ bí mật” và cách thức “khớp lại” các mảnh bí mật.

Sơ đồ “Chia sẻ bí mật” dùng để chia sẻ “tin mật” cho n thành viên, sao cho chỉ

những tập con “hợp thức” các thành viên mới có thể khôi phục lại “tin mật”, còn lại,

bất kỳ tập con “không hợp thức” các thành viên thì khó thể làm đƣợc điều đó.

Ví dụ: Ngân hàng có một két bạc phải mở hàng ngày, “chìa khóa” mở két bạc

là “chìa khóa số”. Ngân hàng có 3 thủ quỹ kinh nghiệm, nhƣng họ không tin ngƣời

nào. Bởi vậy họ cần xây dựng một hệ thống sao cho bất kỳ 2 trong 3 thủ quỹ nào

cũng có thể mở đƣợc két bạc bằng cách họ khớp 2 mảnh khóa của họ với nhau, sẽ

nhận đƣợc chìa khóa gốc để mở két bạc, nhƣng riêng từng ngƣời một thì khó thể mở

đƣợc. Vấn đề này có thể đƣợc giải quyết bằng phƣơng pháp “Chia sẻ bí mật”. Đó là

cơ chế “Chia sẻ bí mật” “2 trong 3”.

Một sơ đồ chia sẻ bí mật là hoàn hảo, nếu bất kì một tập hợp những ngƣời

tham gia mà không đƣợc chỉ định, sẽ không thu đƣợc thông tin về bí mật.

2.3.2. Giao thức “Chia sẻ bí mật” Shamir

2.3.2.1. Khái niệm sơ đồ ngƣỡng A(t, m)

Cho t, w là các số nguyên dương, t w. Một sơ đồ ngưỡng A(t,w) là một

phương pháp phân chia khóa K cho một tập w thành viên (kí hiệu là P) sao cho t

thành viên bất kì có thể tính được K nhưng không một nhóm (t-1) thành viên nào có

thể làm được điều đó.

Giá trị K đƣợc chọn bởi một thành viên đặc biệt đƣợc gọi là ngƣời phân phối

(D). D P. Khi D phân chia khóa K cho mỗi thành viên trong P bằng cách cho mỗi

thành viên một thông tin “cục bộ” nào đó về K, đƣợc gọi là các “mảnh khoá”. Các

mảnh đƣợc phân phát một cách bí mật để không thành viên nào biết đƣợc mảnh

đƣợc trao cho các thành viên khác.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Một tập con các thành viên B P sẽ kết hợp các mảnh của họ để tính khóa K

(cũng có thể trao các mảnh của mình cho một ngƣời đáng tin cậy để tính khóa hộ).

Nếu t thì họ có khả năng tính đƣợc K.

Nếu < t thì họ không thể tính đƣợc K.

Gọi P là tập các giá trị đƣợc phân phối khóa K: P = {Pi: 1

K là tập khóa: tập tất cả các khóa có thể

S tập mảnh: tập tất cả các mảnh có thể

Sơ đồ ngƣỡng của Shamir đƣợc đƣa ra năm 1979.

2.3.2.2. Chia sẻ khoá bí mật K

Khởi tạo:

(1). D chọn số nguyên tố p, và m phần tử xi (1≤ i ≤ m) khác nhau - khác 0

trong Z p , xi là công khai. D trao giá trị xi cho mỗi thành viên Pi .

Phân phối mảnh:

(2). Để chia mảnh khoá K  Zp , D chọn bí mật (ngẫu nhiên, độc lập) t-1

phần tử của Zp là a1, …, a t-1,

(3). Lập đa thức trong Z p là P(x) = K + aj xj mod p

(4). Với 1≤ i ≤ m, D tính yi = P(xi), và trao mảnh yi cho Pi .

Hình 2.2. Sơ đồ ngƣỡng Shamir

Trong sơ đồ ngƣỡng Shamir D xây dựng một đa thức ngẫu nhiên P(x) có bậc

tối đa là t-1.

Trong đa thức này hằng số là khóa K. Mỗi thành viên Pi sẽ có một điểm (xi,yi)

trên đa thức.

Ví dụ 1: Chia sẻ khóa bí mật Khóa K=13 cần chia thành 3 mảnh cho 3

ngƣời P1, P3, P5.

1). Chọn số nguyên tố p = 17, chọn m = 5 phần tử xi = i, trong Zp, i =1, 2,

3, 4, 5. D trao giá trị công khai xi cho Pi .

2). D chọn bí mật t - 1 = 2 phần tử trong Zp : a1 =10, a2 = 2.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

3). Lập đa thức:

P(x) = K + a j xj j mod p = 13 + a1 x + a2 x2 (mod 17).

4). D tính yi = P( xi ), 1 ≤ i ≤ m, trao mảnh yi cho Pi :

= 13 + 10 .1 + 2 .1 = 8

y1 = P(x1) = P(1) = 13 + a1 .1 + a2 .1 2 = 13 + 10 .3 + 2 .3 = 10 y3 = P(x3) = P(3) = 13 + a1 .3 + a2 .3

= 13 + 10 .5 + 2 .5 = 11 y5 = P(x5) = P(5) = 13 + a1 .5 + a2 .5

2.3.2.3. Khôi phục khóa bí mật K từ t thành viên

Một tập con gồm t thành viên có thể khôi phục lại khoá nhƣ thế nào. Có hai

phƣơng pháp: giải hệ phƣơng trình tuyến tính và dùng công thức nội suy Lagrangre.

1). Phương pháp 1: Giải hệ phƣơng trình tuyến tính khôi phục K.

Giải hệ phƣơng trình tuyến tính t ẩn số, t phƣơng trình.

Giả sử rằng các thành viên Pi muốn xác định khoá K. Họ biết rằng:

yij = P(x ij), 1≤ j ≤ t, trong đó P(x)  Zp [x] là đa thức do phân phối khóa D chọn. Vì P(x) có bậc lớn nhất là (t-1) nên có thể viết P(x) = a0 + a1 x + …+ a t-1 x t-1

Ta có hệ các phƣơng trình tuyến tính (trong Zp) nhƣ sau:

Trong đó các hệ số a0 , a1 , …, a t-1 là chƣa biết của Z p, còn a0 = K là khoá.

Vì yij = P (x ij), nên ta có hệ phƣơng trình tuyến tính t ẩn số, t phƣơng trình.

Chú ý ở đây các phép tính số học đều thực hiện trên Z p. Nếu các phƣơng trình

độc lập tuyến tính, thì sẽ có một nghiệm duy nhất, trong đó giá trị khoá a0 = K.

Ví dụ 2: Khôi phục khóa bí mật K = 13 (Bằng phương pháp 1).

Trong ví dụ 1, ta đã biết D chọn số nguyên tố p = 17, chọn m = 5 phần tử

xi = i trong Zp, i =1, 2, 3, 4, 5. D trao giá trị công khai xi cho Pi . Giả sử nhóm

thành viên giữ các “mảnh khóa“ B = {P1, P3, P5} sẽ kết hợp các mảnh của họ tƣơng

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

ứng là y1 = 8, y3 = 10, y5 = 11, để khôi phục lại khóa K.

B biết đa thức P(x) = K +

2 (mod 17).

a j xj j mod p = a0 + a1 x + a2 x

2 (mod 17), a0 = K. Thay x1 = 1, x3 = 3, x5 = 5 vào P(x) = a0 + a1 x + a2 x

Ta nhận đƣợc 3 phƣơng trình với 3 ẩn số a0 , a1, a2.

Các phƣơng trình cụ thể trong Z 17 là

y1 = P(x1) = P(1) = a0 + a1 + a2 = 8 (mod 17).

y3 = P(x3) = P(3) = a0 + 3 a1 + 9 a2 = 10 (mod 17).

y5 = P(x5) = P(5) = a0 + 5 a1 + 8 a2 = 11 (mod 17).

Hệ này có nghiệm duy nhất trong Z17 là a0 = 13, a1 = 10, a2 = 2.

Nhƣ vậy khoá đƣợc khôi phục lại là : K = a0 = 13.

2). Phương pháp 2: Dùng công thức nội suy Lagrangre khôi phục K

Giả sử ta có n thực thể A1, A2, …, An-1 và có 1 ngƣời đƣợc ủy quyền B biết

đƣợc toàn bộ khóa bí mật S є N.

Ngƣời đƣợc ủy quyền B thực hiện các bƣớc sau đây:

(1) B chọn một số nguyên tố P đủ lớn sao cho: . Với

(2) B tiếp theo chọn 2n-1 số một cách ngẫu nhiên :

a1, a2, ... , an-1

v0, v1, v2, ..., vn-1

Trong đó:

: (3) B xác định một đa thức với các hệ số a1, a2, ... , an-1 trên

(4) Bây giờ B gửi cho Aj (một cách công khai ) cặp (vj, (vj)) với j = 0, 1, 2,

..., n-1 coi nhƣ mảnh riêng của Aj

Khôi phục bí mật S:

Tất cả n ngƣời A1,…,An có thể hợp tác lại để khôi phục lại bí mật S bằng cách:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Khi đó dễ dàng xác định đƣợc S = g(0)

Ta có định lý sau: n thực thể kết hợp với nhau thì có thể khôi phục bí mật S

một cách có hiệu quả đó là: S = g(0) = f(0)

Ví dụ 1: Có 3 ngƣời A1, A2, A3 muốn chia sẻ bí mật S = 472

Cho p = 1999 công khai.

A chọn v0 = 626, v1 = 674, v2 = 93, a1 = 334, a2 =223.

Tính:

Áp dụng công thức trên với S = 472 ta có:

A1 có cặp

A2 có cặp

A3 có cặp

3 ngƣời hợp lại sẽ xác định đƣợc S:

Với

Áp dụng công thức trên ta tính đƣợc:

b0 =1847

b1 =1847

b2 =1847

S = g(0) = = 472

Ví dụ 2: Cho số p = 342853815608923 (Đây là 1 số nguyên tố đƣợc lấy trong bảng

các số nguyên tố từ cuốn “The Art of Programing” của Knut(Vol 2)

n = 3, ta có

a1 = 53958111706386.

a2 = 151595058245452

v0 = 111350135012507

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

v1 = 207244959855905

v2 = 20545949133543

Giả sử bí mật là S = 151595058245452

Tính:

f(v0) = 109351520587519

f(v1) = 174675701531216

f(v2) = 117471713218253

Đặt

S = g(0) =

Ta có

b0 = 266921901220910

b1 = 129147516050688

b2 =289638215946249

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Ta tính đƣợc S’ =151595058245452. S’ trùng với khóa bí mật đã cho.

CHƢƠNG 3

ỨNG DỤNG HỆ MẬT MÃ ELGAMAL

TRONG BÀI TOÁN BỎ PHIẾU THĂM DÕ TÍN NHIỆM

Để thử nghiệm hệ mật mã Elgamal cải tiến, trong chƣơng này, học viên sẽ ứng

dụng thuật toán thứ ba (nội dung đƣợc trình bày trong mục 2.1.2.3) để giải quyết bài

toán thăm dò về mức độ tín nhiệm đối với một đơn vị (ở đây là tổng công ty xăng

dầu Việt Nam). Về bản chất bài toán thăm dò tín nhiệm là một dạng của bài toán bỏ

phiếu điện tử, ở đây các cán bộ trong cơ quan là đóng vai trò là cử tri, việc lựa chọn

các mức tín nhiệm cũng tƣơng tự nhƣ việc lựa chọn ai trong danh sách bỏ phiếu.

Bài toán thăm dò tín nhiệm cũng rất hay gặp trong môi trƣờng giáo dục, chẳng hạn

hàng năm đều có các cuộc thăm dò ý kiến các em học sinh về các môn học, hay

hoạt động giảng dạy của giáo viên đang công tác tại trƣờng hay của các lãnh đạo tại

các trƣờng học hay các cơ quan. Tuy nhiên, số lƣợng ngƣời tham gia các cuộc bỏ

phiếu này rất ít và phần đa các em học sinh, giáo viên, nhân viên không quan tâm,

không muốn tham gia vì không muốn kết quả bỏ phiếu của mình bị lộ làm mất lòng

ngƣời khác trong khi việc tham gia bỏ phiếu đó chính là quyền lợi và cũng là nghĩa

vụ của họ.

Ở các trƣờng đại học hàng đầu trên thế giới nhƣ Harvard, việc sinh viên bầu ra

những đứng đầu đại diện cho trƣờng trong các hoạt động đoàn thể, học tập,… diễn

ra rất phổ biến và các sinh viên rất nhiệt tình tham gia. Việc làm đó của các sinh

viên chính là bảo vệ đƣợc quyền lợi chính đáng của mình đồng thời thể hiện đƣợc

tính dân chủ, đoàn kết.

3.1. Hệ thống bỏ phiếu điện tử [5]

3.1.1. Khái niệm bỏ phiếu điện tử

Bỏ phiếu điện tử là một cuộc “bỏ phiếu” đƣợc thực hiện từ xa trên mạng

máy tính thông qua các phƣơng tiện “điện tử” nhƣ máy tính cá nhân, điện thoại di

động… Với phƣơng pháp mới này các cử tri không cần nhìn thấy nhau, không cần

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

trực tiếp đến địa điểm tổ chức bỏ phiếu nhƣng vẫn có thể tham gia bỏ phiếu đƣợc.

Ví dụ: Năm 2011 Vịnh Hạ Long đƣợc trang web New7Wonders của tổ chức

New Open World công bố vịnh Hạ Long của Việt Nam là một trong 7 “kỳ quan

thiên nhiên” mới của Thế Giới. Cuộc bầu chọn 7 kỳ quan thiên nhiên mới đƣợc

New Open World phát động qua mạng Internet từ năm 2007. Đây là một hình thức

bỏ phiếu từ xa để lấy ý kiến của cộng đồng thông qua mạng Internet, mạng điện

thoại di động,…

Bỏ phiếu điện tử cũng nhƣ tất cả các cuộc bỏ phiếu khác phải đảm bảo các yêu

cầu về tính bí mật, tính toàn vẹn và xác thực của lá phiếu; mỗi cử tri chỉ đƣợc bỏ

phiếu một lần, mọi ngƣời đều có thể kiểm tra tính đúng đắn của cuộc bỏ phiếu, cử

tri không thể chỉ ra mình đã bỏ phiếu cho ai để tránh cơ hội mua bán phiếu bầu…

Bỏ phiếu điện tử mang lại rất nhiều lợi ích :

- Tiết kiệm đƣợc tiền của, công sức, thời gian của nhà nƣớc và của nhân dân.

- Nhanh chóng, thuận tiện, an toàn, trung thực .

- Đảm bảo cho việc bỏ phiếu diễn ra khách quan, dân chủ.

3.1.2. Yêu cầu của hệ thống bỏ phiếu điện tử

Một hệ thống bỏ phiếu điện tử phải đáp ứng đƣợc các yêu cầu sau:

- Bảo đảm tính bí mật:

+ Không thể biết đƣợc nội dung lá phiếu nếu không đƣợc cấp quyền hạn: lá

phiếu phải đƣợc mã hóa.

+ Không thể biết đƣợc lá phiếu đó là của ai, trừ cử tri sở hữu nó: làm

mù lá phiếu, chia sẻ khóa bí mật, trộn phiếu bầu,…

- Bảo đảm tính toàn vẹn của lá phiếu: Trên đƣờng truyền tin, nội dung lá

phiếu không thể bị thay đổi, tất cả lá phiếu đều đƣợc chuyển tới hòm phiếu an toàn,

đúng thời gian, chúng đƣợc kiểm phiếu đầy đủ.

- Bảo đảm tính xác thực của lá phiếu: Lá phiếu gửi tới hòm phiếu phải hợp lệ,

đúng là ngƣời có quyền bỏ phiếu, cử tri có thể nhận ra lá phiếu của họ.

3.1.3. Những vấn đề cần giải quyết

- Cƣỡng chế: Cử tri có thể bị cƣỡng chế bỏ phiếu cho một ứng cử viên nhất định

vì bị ép buộc. Trong trƣờng hợp này cách giải quyết là cử tri không đƣợc liên kết

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

với phiếu bầu của mình.

- Hối lộ: Cử tri có thể bị mua chuộc để bỏ phiếu cho một ứng cử viên nào đó

và có thể là nghĩa vụ bỏ phiếu dƣới sự giám sát của ngƣời hối lộ. Để giải quyết vấn

đề này, các cử tri trong hệ thống này không thể chứng minh phiếu bầu của mình, khi

đó ngƣời mua chuộc không biết các phiếu bầu là cho mình không.

- Truy cập trái phép: Chỉ có ngƣời quản trị hay đội ngũ lập trình đáng tin cậy

mới có thể theo dõi quá trình bỏ phiếu, họ cũng không thể thay đổi kết quả bỏ

phiếu trong các cơ sở dữ liệu trong quá trình bỏ phiếu

3.1.4.Các thành phần trong hệ thống bỏ phiếu điện tử

- Ban tổ chức: Quản lý các hoạt động bỏ phiếu, trong đó có thiết lập danh

sách cử tri cùng các hồ sơ của mỗi cử tri, qui định cơ chế định danh cử tri.

- Ban đăng ký: Nhận dạng cử tri và ký cấp quyền bỏ phiếu cho họ, theo dõi

cuộc bỏ phiếu, chống lại việc cử tri bỏ phiếu hai lần. Có hệ thống "ký" hỗ trợ.

- Ban kiểm tra: Xác minh tính hợp lệ của lá phiếu; vì lá phiếu đã mã hoá

nên ban kiểm phiếu không thể biết đƣợc lá phiếu có hợp lệ không, nên cần phải xác

minh tính hợp lệ của lá phiếu trƣớc khi nó đến hòm phiếu. (Bỏ phiếu truyền thống

không có ban này).

- Ban kiểm phiếu: Tính toán và thông báo kết quả bỏ phiếu. Có hệ thống

"kiểm phiếu" hỗ trợ.

- Hệ thống máy tính và các phần mềm phục vụ qui trình bỏ phiếu từ xa.

- Ngƣời dùng thực hiện kiểm soát Server đảm bảo yêu cầu bảo mật và toàn vẹn

của kết quả bỏ phiếu.

- Một số kỹ thuật đảm bảo an toàn thông tin: Chữ ký mù, mã hóa đồng cấu,

chia sẻ bí mật.

- Hệ thống phân phối khoá tin cậy sẵn sàng cung cấp khoá cho công việc mã

hoá và giải mã hay ký "số".

3.1.5. Quy trình bài toán bỏ phiếu điện tử

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 quy trình có ƣu nhƣợc điểm riêng, trong luận văn này học viên chỉ nghiên

cứu sơ đồ bỏ phiếu tín nhiệm gồm ba giai đoạn chính: Giai đoạn đăng ký bỏ phiếu,

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

giai đoạn bỏ phiếu và giai đoạn kiểm phiếu nhƣ sau:

Mạng trộn

Mã hóa đồng cấu

Chứng minh không tiết lộ thông tin

Lá phiếu

Hòm phiếu

Lá phiếu

Cử tri

Kiểm phiếu

Bảng niêm yết công khai

Đăng ký

Chữ ký mù

Sơ đồ chia sẻ bí mật

Hình 3.1. Sơ đồ Quy trình bỏ phiếu điện tử

(1) Đăng ký bỏ phiếu: Cử tri sử dụng thông tin cá nhân của mình để đăng

ký tham gia bỏ phiếu. Ban đăng ký sẽ kiểm tra tính hợp lệ của cử tri. Nếu hợp lệ

(đúng thông tin trong cơ sở dữ liệu và mới chỉ đăng ký lần đầu) thì tiến hành phát

mã cử tri. Ban đăng ký ghi số chứng minh thƣ của cử tri vào danh sách cử tri đã

đƣợc cấp chữ ký (để tránh việc cử tri đăng ký bỏ phiếu nhiều lần).

(2) Bỏ phiếu: Chỉ những cử tri có mã cử tri hợp lệ mới đƣợc tham gia bỏ phiếu

và chỉ đƣợc bỏ phiếu duy nhất một lần. Cử tri sử dụng mã cử tri hợp lệ để tham gia

bỏ phiếu

(3) Kiểm phiếu: Ban kiểm phiếu sẽ tính toán dựa vào các lá phiếu hợp lệ để

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

tổng hợp kết quả, sau đó công bố kết quả cuộc bỏ phiếu.

3.2. Ứng dụng hệ mật ElGamal trong quá trình bỏ phiếu thăm dò tín nhiệm

Các bƣớc Cán bộ Ban tổ chức

- Một số nguyên tố lớn p

thực hiện

- Tạo khóa bí mật và

ngẫu nhiên. khóa công khai theo

thuật toán ElGamal Thiết lập - g là điểm sinh của - Tạo khóa bí mật và khóa cải tiến.

công khai theo thuật toán

ElGamal cải tiến.

- Lá phiếu đã mã - Kiểm tra chữ ký và tính - Chọn ý kiến của hóa bằng khóa hợp lệ của lá phiếu. mình cho lá phiếu Bỏ phiếu công khai của - Mã hóa lại lá phiếu và đã có chữ ký của

gửi về hòm phiếu. ban tổ chức. ban tổ chức.

- Khôi phục khóa bí mật.

Mở phiếu - Tính kết quả bỏ phiếu.

bầu - Thông báo và niêm yết

công khai.

Hình 3.2. Sơ đồ mô tả bỏ phiếu thăm dò tín nhiệm

3.2.1. Thiết lập

Xét một cuộc bỏ phiếu thăm dò tín nhiệm với m phƣơng án lựa chọn.

Ban tổ chức bỏ phiếu tín nhiệm cần chuẩn bị hệ mật mã ElGamal cải tiến (nội

dung trình bày trong mục 2.1.2.3) với :

Chọn một số nguyên tố lớn p ngẫu nhiên sao cho bài toán logarit rời rạc trong

Zp là khó giải và g là điểm sinh của

Chọn khóa bí mật x là số nguyên thỏa mãn: 1 < x < (p-1). Tính khóa công khai y theo công thức: y = gx mod p

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Giữ bí mật: x; công khai: p, g, y.

Chọn ý kiến cho lá phiếu của mình

Lá phiếu đã mã hóa bằng khóa công khai của ban tổ chức.

Cán bộ 

“Chứng minh không tiết lộ thông tin”

3.2.2. Bỏ phiếu

Kiểm tra chữ ký (Liên hệ với ban đăng ký) Thực hiện các giao thức tƣơng tác với cán bộ để kiểm tra tính hợp lệ của lá phiếu Mã hóa lại lá phiếu, gửi tới hòm phiếu

Ban kiểm tra 

Hình 3.3. Sơ đồ giai đoạn bỏ phiếu tín nhiệm

Giả sử một cán bộ muốn bỏ phiếu lựa chọn cho một phƣơng án, quá trình bỏ

phiếu của cán bộ này gồm 4 bƣớc:

Bƣớc 1: Lựa chọn phƣơng án

Sau khi lá phiếu có chữ ký của Ban tổ chức, cán bộ lựa chọn phƣơng án của

mình vào lá phiếu bằng cách đánh dấu lên lá phiếu.

Bƣớc 2: Mã hóa nội dung lá phiếu

Để không bị lộ thông tin về sự lựa chọn của mình, cán bộ sẽ mã hóa nội dung

lá phiếu trƣớc khi lá phiếu đƣợc chuyển tới hòm phiếu.

Cán bộ mã hóa lá phiếu bằng khóa công khai của ban tổ chức và gửi tới

ban tổ chức lá phiếu đã bị mã hóa, đinh danh thật ( không bị làm mù) của họ,

chữ ký của ban tổ chức về cho ban tổ chức.

Giả sử cán bộ p muốn bỏ phiếu cho phƣơng án M, thực hiện nhƣ sau:

- Mã hóa phƣơng án M bằng khóa công khai y của ban tổ chức, lá phiếu đƣợc

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

hệ thống mã hóa thành 2 giá trị C và R.

- Gửi (C,R) cùng với chữ ký của nó đến trạm bỏ phiếu (ghi nhận 2 giá trị này

vào cơ sở dữ liệu).

Bƣớc 3: Kiểm tra lá phiếu.

Trƣớc khi lá phiếu đƣợc chuyển đến hòm phiếu. Thì lá phiếu sẽ đƣợc kiểm

tra chữ ký, cấp quyền bỏ phiếu trên lá phiếu qua ban kiểm tra.

Tiếp theo ban kiểm tra, kiểm tra xem cán bộ đó có trong danh sách đƣợc phép

bỏ phiếu hay không và đảm bảo rằng cán bộ chƣa bỏ phiếu trƣớc đó. Trong trƣờng

hợp này, cán bộ phải chứng minh đƣợc lá phiếu của mình là hợp lệ.

Bƣớc 4: Mã hóa lại lá phiếu và gửi tới hòm phiếu.

3.2.3. Mở phiếu bầu

Khi cuộc bỏ phiếu kết thúc, ban tổ chức bắt đầu tiến hành giải mã lá phiếu và

thống kê kết quả bỏ phiếu. Quá trình này đƣợc chia thành 3 bƣớc:

Bƣớc 1: Giải mã lá phiếu

Theo phƣơng pháp mã hóa đồng cấu, ban kiểm phiếu không cần giải mã từng

lá phiếu mà vẫn có thể kiểm phiếu đƣợc. Khi kiểm phiếu, từng thành viên ban kiểm

phiếu dùng các mảnh khóa riêng của mình do ban tổ chức đƣa ra để khôi phục khóa

bí mật x (khóa này đã bị chia sẻ qua sơ đồ bí mật Shamir).

Bƣớc 2: Tính toán kết quả

Khi các lá phiếu hợp lệ cộng tất cả các lá phiếu để cuối cùng kiểm soát kết

quả của bỏ phiếu tín nhiệm.

Bƣớc 3: Công bố kết quả

Kết quả của cuộc bỏ phiếu tín nhiệm đƣợc công bố công khai trên bảng niêm

yết, chứa tất cả thông tin cần thiết để xác minh tính đúng đắn của toàn bộ quá trình.

Đó là:

1) Kết quả bỏ phiếu ( số lƣợng phiếu của mỗi phƣơng án).

2) Danh sách cán bộ ( tên và khóa công khai của mỗi cán bộ).

3) Phiếu đã nhận cùng với chữ ký của chúng ( ở cột "Chọn") và bằng chứng về

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

tính đúng đắn.

3.3. Xây dựng chƣơng trình thử nghiệm mô hình bỏ phiếu thăm dò tín nhiệm

3.3.1. Môi trường cài đặt và thử nghiệm

Chƣơng trình thử nghiệm đƣợc viết bằng ngôn ngữ C#.Net trên bộ Visual Studio

2010 sử dụng phiên bản Net Framework 4.5. Dữ liệu của chƣơng trình đƣợc lƣu trữ

trong hệ quản trị cơ sở dữ liệu Microsoft Access 2007.

3.3.2. Phát biểu bài toán

Với sự phát triển của khoa học kỹ thuật, nhu cầu trao đổi thông tin nhanh

chóng và tiết kiệm thì hình thức họp trực tuyến, lấy ý kiến thăm dò về các vấn đề

quan trọng đƣợc sử dụng phổ biến. Trong hình thức họp trực tuyến, khi cần lấy biểu

quyết về một vấn đề nào đó thì biểu quyết giơ tay không hiệu quả và thiếu tính

khách quan (do camera đặt cố định, không bao quát hết các thành viên tham gia

họp), bên cạnh đó do yêu cầu muốn ẩn danh ý kiến biểu quyết của các cán bộ, cán

bộ (ngƣời cho ý kiến) không muốn ban kiểm phiếu biết đƣợc mình biểu quyết là

đồng ý hay không đồng ý, ban kiểm phiếu chỉ có thể biết đƣợc tổng số phiếu nhƣng

không biết đƣợc nội dung từng lá phiếu.

Từ yêu cầu thực tế đó, luận văn đƣa ra phƣơng án giải quyết dựa trên

tính chất đồng cầu của hệ mã Elgamal. Theo phƣơng pháp này thì nội dung lá

phiếu sẽ đƣợc mã hóa và gửi về ban tổ chức. Khi kiểm phiếu, ban kiểm phiếu

không biết đƣợc nội dung lá phiếu nhƣng xác minh đƣợc nguồn gốc của lá phiếu,

ban kiểm phiếu sẽ tính đƣợc kết quả của cuộc bỏ phiếu.

Luận văn sử dụng chƣơng trình mô phỏng nhằm kiểm chứng tính đúng đắn

của bài toán kết hợp sơ đồ chia sẻ bí mật Shamir và thuật toán ElGamal cải tiến để

ứng dụng trong bỏ phiếu tín nhiệm với tổng công ty xăng dầu Việt Nam, ...

Dữ liệu đầu vào của chƣơng trình là các lá phiếu hợp lệ của cán bộ. Với

chƣơng trình mô phỏng bỏ phiếu lấy ý kiến về mức độ tín nhiệm đối với tổng công

ty xăng dầu Việt Nam, ... Trên lá phiếu có 3 sự lựa chọn: “A. Tín nhiệm cao ”, “B.

Tín nhiệm ”, “C. Tín nhiệm thấp”.

Dữ liệu ra của chƣơng trình là bảng kết quả thống kê số phiếu của từng

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

phƣơng án, phƣơng án đƣợc lựa chọn nhiều nhất. Và quan trọng nhất là kết quả của

chƣơng trình phải đảm bảo an toàn, trung thực đáp ứng đƣợc các tính chất của một

cuộc bỏ phiếu tín nhiệm: tính bí mật, tính toàn vẹn, yêu cầu xác thực lá phiếu.

3.3.3 Các đối tƣợng của hệ thống

(1) Ban tổ chức: Hệ thống này có trách nhiệm tạo, lƣu trữ các khóa riêng và

công bố các khóa công khai. Tất cả các bên phải tin tƣởng vào hệ thống này.

(2) Cán bộ: Họ là những ngƣời có quyền tham gia bỏ phiếu.

(3) Ban kiểm phiếu: Có trách nhiệm tổng hợp và công bố kết quả khi kết thúc

cuộc bỏ phiếu.

3.3.4. Phân tích và thiết kế chƣơng trình bỏ phiếu: Phân tích chƣơng trình:

- Nhập danh sách các cán bộ tham gia bỏ phiếu và thông tin cá nhân của cán

bộ.

- Cung cấp thẻ cán bộ cho các nhân viên đƣợc tham gia bỏ phiếu.

- Kiểm tra thẻ trƣớc khi cán bộ bỏ phiếu

- Kiểm phiếu và niêm yết kết quả.

Thiết kế chƣơng trình:

- Bảng lƣu giữ các thông tin của cán bộ: Xác định danh sách các cán bộ tham

gia bỏ phiếu.

- Bảng xác định cán bộ đã tham gia bỏ phiếu hay chƣa, mỗi cán bộ chỉ đƣợc

bỏ phiếu 1 lần, bảng này nhằm xác định những cán bộ nào chƣa bỏ phiếu và cán bộ

nào đã bỏ phiếu.

- Bảng lƣu nội dung lá phiếu của các cán bộ: Nội dung của lá phiếu đã đƣợc

cán bộ mã hóa và đƣợc lƣu trong bảng này

3.3.5 Các chức năng chính

- Nhập vào các thông tin của cán bộ bao gồm cả thông tin định danh, hệ

thống sẽ mã hoá định danh và xác nhận tính hợp lệ của cán bộ.

- Sử dụng hệ mã hóa ElGamal cải tiến để tạo khóa: Là quá trình sinh ngẫu

nhiên bộ khóa công khai và khóa riêng cho toàn bộ cán bộ. Mỗi cán bộ là một bộ

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

khóa khác nhau.

- Sử dụng sơ đồ chia sẻ bí mật Shamir tạo bộ khóa cho ban kiểm phiếu.

- Cán bộ đăng nhập và bỏ phiếu.

- Mã hóa nội dung lá phiếu trên bộ khóa của cán bộ.

- Giải mã lá phiếu: Hệ thống nhận đƣợc văn bản mã, sẽ sử dụng khóa riêng

để giải mã, sau đó thu đƣợc văn bản gốc.

- Thống kê và đƣa ra kết quả của cuộc bỏ phiếu.

Trên thực tế, để thiết kế đƣợc một chƣơng trình hoàn chỉnh, ngoài modul mã

hóa còn rất nhiều modul hỗ trợ khác nhƣ: xác thực quyền bỏ phiếu của cán bộ, phân

bổ khóa, xác định tính hợp lệ của lá phiếu,... Tuy nhiên, do giới hạn về mặt thời

gian nghiên cứu nên luận văn chỉ tập trung vào việc sử dụng thuật toán ElGamal cải

tiến và sơ đồ chia sẻ bí mật Shamir trong bỏ phiếu thăm dò về mức độ tín nhiệm đối

với một đơn vị.

3.3.6. Thứ tự thực hiện chƣơng trình

Xét một cuộc bỏ phiếu thăm dò tín nhiệm, có ba phƣơng án đƣợc đƣa ra: Tín

nhiệm cao, Tín nhiệm, Tín nhiệm thấp. Hệ thống thiết kế thứ tự thực hiện chƣơng

trình nhƣ sau:

(1) Ban tổ chức (Admin). Sau khi ban tổ chức đăng nhập, hệ thống tự sinh số

nguyên tố trên trƣờng hữu hạn Fp, với p đƣợc lấy ngẫu nhiên gồm 10.000 số

nguyên tố lớn hơn 1.000.000 trong cơ sở dữ liệu và điểm sinh g trong . Khóa bí

mật x của ban tổ chức đƣợc lấy ngẫu nhiên trong đoạn [1, p-1], hệ thống đƣa ra

khóa công khai y. Sau khi tạo cơ sở dữ liệu cho cử tri các khóa bí mật đƣợc lƣu

ở một nơi an toàn.

Tiếp đó, ban tổ chức đƣa ra 3 phƣơng án lựa chọn khác nhau.

Cuối cùng, hệ thống sử dụng sơ đồ chia sẻ bí mật Shamir tạo bộ khóa cho ban

kiểm phiếu: Danh sách trong cơ sở dữ liệu có bao nhiêu ngƣời trong ban kiểm

phiếu thì hệ thống sẽ tự động chia thành từng đó mảnh khóa. Ví dụ, trong danh sách

ban kiểm phiếu có 3 ngƣời thì hệ thống tự động sinh ra 3 mảnh khóa, và phát cho

các thành viên.

(2) Cán bộ: Cán bộ tiến hành đăng nhập vào hệ thống. Khi cán bộ login, hệ

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

thống sẽ kiểm tra trong cơ sở dữ liệu xem có tồn tại tài khoản đó không. Nếu

có, hệ thống chuyển sang giao diện tiếp theo. Nếu không, hệ thống báo lỗi đăng

nhập.

Tiếp theo cán bộ lựa chọn phƣơng án mà mình muốn bỏ phiếu, submit vào hệ

thống và gửi nó đến trạm bỏ phiếu.

(3) Sau khi kết thúc cuộc bỏ phiếu, ban kiểm phiếu sẽ đăng nhập và họ

gửi mảnh khoá mà họ giữ lên hệ thống. Khi các mảnh khoá đƣợc tổng hợp đủ, hệ

thống sẽ ghép các mảnh khóa lại để khôi phục khóa bí mật, hệ thống sử dụng khoá

mật này để giải mã các lá phiếu của cán bộ và thống kê kết quả cuối cùng.

Tuy nhiên giới hạn của luận văn là mô hình bỏ phiếu tín nhiệm thì mức độ đơn

giản hơn nhƣng vẫn theo ý trên đây.

3.3.7. Kết quả thực nghiệm

Chƣơng trình bỏ phiếu lấy ý kiến về mức độ tín nhiệm đối với tổng công ty

xăng dầu Việt Nam với 3 chức năng chính là: Ban tổ chức tạo cơ sở dữ liệu cho cán

bộ và ban kiểm phiếu, cán bộ bỏ phiếu và ban kiểm phiếu thực hiện kiểm phiếu tính

kết quả cuộc bỏ phiếu.

Giao diện chính của chƣơng trình:

Hình 3.4. Giao diện chính của chƣơng trình

a, Đối với ban tổ chức

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Ban tổ đăng nhập vào hệ thống:

Hình 3.5. Ban tổ chức đăng nhập vào hệ thống

Nếu sai tên đăng nhập hoặc mật khẩu, hệ thống báo lỗi. Nếu đúng hệ thống

thông báo đăng nhập thành công.

Ở đây, Ban tổ chức sẽ có 3 quyền đƣợc phân chia: đầu tiên là sinh khoá cho

toàn bộ cán bộ có trong cơ sở dữ liệu, chia sẻ khoá cho ban kiểm phiếu và sửa đổi

khoá cho bất kì cán bộ nào.

Khi ban tổ chức chọn nút “Tạo dữ liệu cho cán bộ”, hệ thống sẽ tự động sinh

khóa cho toàn bộ cán bộ có trong cơ sở dữ liệu, mỗi cán bộ sẽ là một bộ tham số

khác nhau để tăng tính bảo mật.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hình 3.6. Thông báo tạo cơ sở dữ liệu cán bộ thành công.

Hình 3.7. Bảng danh sách cán bộ sau khi đƣợc ban tổ chức tạo cơ sở dữ liệu

Khi ban tổ chức chọn nút “Tạo dữ liệu cho ban kiểm phiếu”, hệ thống sử dụng

sơ đồ chia sẻ bí mật Shamir tạo bộ khóa cho ban kiểm phiếu, danh sách trong cơ sở

dữ liệu có bao nhiêu ngƣời thì hệ thống sẽ tự động chia thành từng đó mảnh khóa. Ở

đây ban kiểm phiếu có 3 thành viên, hệ thống sẽ chia làm 3 mảnh khóa và cấp cho

mỗi ngƣời một mảnh:

Hình 3.8. Thông báo tạo cơ sở dữ liệu ban kiểm phiếu thành công.

b) Đối với cán bộ

Cán bộ đăng nhập vào hệ thống để bỏ phiếu. Yêu cầu cán bộ có tài khoản

trong danh sách cán bộ ở hệ thống cơ sở dữ liệu trung tâm thì mới đƣợc tham gia bỏ

phiếu:

Hình 3.9. Cán bộ đăng nhập vào hệ thống

Nếu tên đăng nhập hoặc mật khẩu là sai hệ thống báo “Bạn chƣa đăng nhập

đúng”. Nếu đúng “Bạn đã đăng nhập thành công”

Tiếp theo, hệ thống hiển thị giao diện thông tin cán bộ. Cửa sổ này đƣợc chia

làm hai phần: Phần bên trái chứa thông tin cán bộ, phần bên phải là các phƣơng án

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

bỏ phiếu.

Hình 3.10. Quá trình bỏ phiếu

Khi cán bộ vào chức năng sửa các thông tin cá nhân của mình:

Hình 3.11. Cán bộ cập nhật thông tin

Cán bộ có thể chỉnh sửa các thông tin cá nhân của mình nếu có sai sót. Sau đó

nhấp chuột vào nút “CẬP NHẬT”, hệ thống sẽ tự động cập nhật thông tin mà cán

bộ vừa thay đổi vào cơ sở dữ liệu của hệ thống.

Cuối cùng, cán bộ lựa chọn phƣơng án mà mình muốn bỏ phiếu sau đó ghi

nhận bằng việc nhấn vào nút “BỎ PHIẾU”, hệ thống sẽ đƣa ra thông báo xác nhận

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

“Bạn đã chắc chắn với phương án lựa chọn chưa?”

Hình 3.12. Thông báo nhắc nhở lựa chọn của cán bộ

Nếu chƣa nhấn vào nút “No” hệ thống đƣa cán bộ về giao diện bỏ phiếu. Nếu

đã chắc chắn với phƣơng án lựa chọn nhấn vào nút “Yes” khi đó hệ thống đƣa ra

thông báo xác nhận lại phƣơng án mà cán bộ đã lựa chọn.

Hình 3.13. Thông báo xác nhận lựa chọn của cán bộ

Hệ thống đƣa ra thông báo bỏ phiếu thành công và tự đăng xuất tài khoản của

cán bộ sau khi cập nhật phƣơng án lựa chọn vào cơ sở dữ liệu của hệ thống.

c) Ban kiểm phiếu thực hiện kiểm phiếu và tính kết quả.

Sau khi các cán bộ hoàn thành việc bỏ phiếu, nhiệm vụ của ban kiểm phiếu là

tiến hành giải mã các lá phiếu để kiểm phiếu. Việc giải mã các lá phiếu đƣợc thực

hiện bằng cách ghép các mảnh khóa của các thành viên ban kiểm phiếu lại sau đó

thực hiện giải mã các lá phiếu. Nếu thiếu bất kỳ một mảnh khóa nào của thành viên

ban kiểm phiếu thì việc kiểm phiếu sẽ không thực hiện đƣợc. Vì vậy việc kiểm

phiếu sẽ đƣợc thực hiện khi tất cả thành viên trong ban kiểm phiếu đăng nhập vào

hệ thống bỏ phiếu và gửi mảnh khóa mà mình giữ.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Ban kiểm phiếu đăng nhập vào hệ thống bỏ phiếu:

Hình 3.14. Ban kiểm phiếu đăng nhập vào hệ thống

Hệ thống thông báo “Bạn chưa đăng nhập đúng” nếu thành viên ban kiểm

phiếu đăng nhập với TÊN ĐĂNG NHẬP hoặc MẬT KHẨU sai, khi đó ban kiểm

phiếu phải đăng nhập lại.

Ngƣợc lại, hệ thống thông báo “Bạn đã đăng nhập thành công với vai trò

ban kiểm phiếu”.

Khi ban kiểm phiếu đăng nhập thành công, màn hình sẽ hiển thị bộ khóa mà

ngƣời thuộc ban kiểm phiếu này đang giữ.

Hình 3.14. Mảnh khóa của ban kiểm phiếu

Cũng nhƣ cán bộ, ban kiểm phiếu có thể xem và sửa đổi thông tin cá nhân của

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

mình.

Hình 3.15. Ban kiểm phiếu cập nhật thông tin

Ban kiểm phiếu có thể thay đổi mật khẩu của mình sau đó nhấn nút “Cập

nhật” để ghi nhận quá trình sửa đổi. Hệ thống đƣa ra thông báo cập nhật thành công:

Hoặc nếu không muốn thay đổi cán bộ chọn nút “Thoát” để đăng xuất khỏi hệ

thống.

Từng thành viên ban kiểm phiếu phải thực hiện một công việc quan trọng đó

là gửi mảnh khóa mà mình đang giữ tới cơ sở dữ liệu của hệ thống bằng cách nhấn

nút “Gửi khóa”, hệ thống đƣa ra thông báo xác nhận cán bộ đã chắc chắn muốn gửi

khóa chƣa:

Hình 3.16. Thông báo xác nhận quá trình gửi mảnh khóa

Nếu không đồng ý gửi mảnh khóa của mình thì nhấn nút “No”, ngƣợc lại nếu

đã chắc chắn với phƣơng án lựa chọn nhấn nút “Yes”, khi đó hệ thống sẽ hiển thị

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

thông báo “Đã submit khóa thành công”.

Tất cả các thành viên của ban kiểm phiếu đồng ý gửi mảnh khóa mà mình giữ

khi đó đã có thể tiến hành kiểm phiếu bằng cách nháy chuột vào nút “Kiểm phiếu”,

hệ thống sẽ đƣa ra thông báo “Đã tổng hợp đủ các mảnh khóa nhấn OK để ghép

các mảnh khóa”,

Hình 3.17. Xác nhận tổng hợp đủ các mảnh khóa

Tiếp tục nhấn “OK” hệ thống đƣa ra thông báo xác nhận “Các mảnh khóa đã

khớp nhấn OK để kiểm phiếu”, lúc này hệ thống sẽ tự động ghép các mảnh khóa

lại thành khóa bí mật để giải mã các lá. Nhƣ vậy, nhờ áp dụng giao thức chia sẻ bí

mật Shamir hệ thống bỏ phiếu sẽ phòng tránh đƣợc bài toán “Thành viên ban kiểm

phiếu thông gian sửa đổi nội dung lá phiếu”.

Hình 3.18. Thông báo ghép mảnh khóa thành công

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Sau khi nhấn “OK” hệ thống đƣa ra kết quả cuộc bỏ phiếu nhƣ sau:

Hình 3.19. Kết quả bỏ phiếu

Ban kiểm phiếu công bố tất cả những phiếu kín đƣợc chấp nhận. Mỗi cán bộ

phải kiểm tra xem phiếu của mình đã đƣợc công bố chƣa.

Bất kì ai đều có thể kiểm tra tính hợp lý của các phiếu kín và xem tổng số

phiếu kín có bằng tổng số đăng kí hay không để ngăn chặn ban kiểm phiếu bỏ thêm

phiếu kín vào.

Trên cơ sở dữ liệu: bảng CanBo sẽ đƣợc công khai, trên đó có hiển thị sự lựa

chọn của cán bộ ở cột “Chon” tuy nhiên nhìn vào đó cán bộ không thể chứng minh

cho ngƣời khác biết đƣợc mình đã lựa chọn phƣơng án nào vì lựa chọn đó đã bị mã

hóa bởi thuật toán ElGamal cải tiến. Nhƣ vậy sẽ giải quyết đƣợc bài toán chống

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

mua bán phiếu.

Hình 3.20. Cơ sở dữ liệu trong mô hình bỏ phiếu tín nhiệm

Kết quả thực nghiệm chƣơng trình thu đƣợc: Bảng thống kê đƣa ra đƣợc số

phiếu bầu cho các phƣơng án và phƣơng án đƣợc lựa chọn nhiều nhất. Và trên hết

đó là kết quả của cuộc bỏ phiếu đảm bảo đƣợc các tính chất: tính bí mật của lá

phiếu, tính toàn vẹn lá phiếu và yêu cầu xác thực của lá phiếu.

3.4. Phân tích vấn đề bảo mật cần đạt đƣợc

An ninh: An ninh luôn là yêu cầu hàng đầu trong thiết kế hệ thống, và phải

đƣợc chú trọng toàn diện từ an ninh của một hệ thống hoàn chỉnh cho đến an ninh

của từng lá phiếu và việc lƣu trữ các lá phiếu trong cơ sở dữ liệu.

Độ tin cậy: Ứng dụng phải có những cơ chế xác minh các lá phiếu khi

chúng đƣợc “bỏ” và phải đảm bảo không có sự can thiệp hay thay đổi nào có thể

xảy ra một khi phiếu đã bỏ.

Tính linh hoạt và thực tiễn cao: Hệ thống phải có khả năng làm việc nhiều

ngày trong suốt kỳ bỏ phiếu.

3.5. Các tính chất đạt đƣợc

Tính toàn vẹn: Khi bảng thông báo đƣợc đƣa ra công khai, không thể có lá

phiếu nào đƣợc mã hóa mà có thể bị xóa khỏi bảng, vì bất kì ngƣời nào cũng có

thể chứng minh đƣợc tính hợp lệ của lá phiếu. Vì vậy không có lá phiếu nào đƣợc

mã hóa hợp lệ mà bị mất đi hoặc xử lý sai.

Tính bí mật: Bảo đảm tính bí mật của lá phiếu riêng lẻ đƣợc đảm bảo bởi sự an

toàn của hệ thống chia sẻ bí mật. Bất kỳ nhóm ít hơn t ngƣời kiểm phiếu đều không

giải mã đƣợc lá phiếu.

Tính hợp pháp: Mỗi cán bộ chỉ có thể có đƣợc 1 định danh. Định danh không

hợp lý hoặc trùng sẽ bị loại. Lá phiếu không hợp lệ cũng sẽ không đƣợc tính.

Tính xác minh phổ thông: bất kỳ một ngƣời nào cũng có thể kiểm tra phần

chứng minh tính hợp lệ của lá phiếu, tính tích các lá phiếu hợp lệ và xác minh tính

đúng đắn của việc giải mã bằng cách kiểm việc sử dụng khóa bí mật của ban tổ

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

chức.

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ĐỀ TÀI

Các kết quả đạt đƣợc

a. Nghiên cứu tài liệu để trình bày các vấn đề sau:

- Trình bày tổng quan về các hệ mật mã

- Giới thiệu một số thuật toán mã hóa ElGamal cải tiến, mã hóa đồng cấu, chia

sẻ bí mật, …

b. Thử nghiệm mô hình bỏ phiếu tín nhiệm tại một tổng công ty xăng dầu Việt Nam sử

dụng thuật toán ElGamal cải tiến và sơ đồ chia sẻ bí mật Shamir:

Cài đặt chƣơng trình thuật toán mã hóa lá phiếu sử dụng hệ mật mã

ElGamal cải tiến thứ 3 trên bộ khóa của cán bộ. Mỗi cán bộ là một bộ khóa khác

nhau.

Những hƣớng nghiên cứu tiếp theo:

Nghiên cứu mô hình bỏ phiếu, kiểm thử ứng dụng trong phạm vi một

địa phƣơng và cải thiện chất lƣợng công cụ.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Tối ƣu hóa hệ thống, cải thiện tốc độ xử lý dữ liệu của mô hình.

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1] Phan Đình Diệu (2011), “Lý thuyết mật mã và An toàn thông tin”, NXB Đại học

quốc gia Hà Nội.

[2] PGS.TS Trịnh Nhật Tiến (2008), Giáo trình An toàn dữ liệu, NXB Đại học

Quốc Gia.

[3] Lƣu Hồng Dũng, Ngô Đăng Tiến, Trần Trung Dũng, Vũ Tất Thắng (2012), Phát

triển một số thuật toán mật mã khóa công khai, Hội thảo @ lần thứ XV, trang

367-373.

[4] Trịnh Nhật Tiến, Trƣơng Thị Thu Hiền (2010), Mã hóa đồ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, trang 44- 48.

[5] PGS.TS Trịnh Nhật Tiến, ThS. Trƣơng Thị Thu Hiền, Về một quy trình bỏ

phiếu từ xa, Trƣờng Đại học công nghệ - ĐHQGHN.

Tiếng Anh

[6] Andrea Huszti, “A homomorphic encryption-based secure electronic voting

scheme”, 2011

[7] Basso, A., F. Bergadano, I. Coradazzi and P. D. Checco (2004), “Lightweight

security for internet polls”, in: EGCDMAS.

[8 Cyber Vote, Report on Review of Cryptographic Protocols and Security

Techniques for Electronic Voting, 2002.

[9] Craig Gentry and Shai Halevi (2011), “Implementing Gentry’s fully-

homomorphic encryption scheme”, In EUROCRYPT.

[10] D.Stinson (2002), Cryptography Theory and Practice. 2nd ed. Chapman &

Hall/CRC.

[11] Kristin Lauter, Michael Naehrig, and Vinod Vaikuntanathan, “Can

Homomorphic Encryption be Practical?”, ACM, 2011

[12] R.L Rivest, A. Shamir, and L.M. Adleman (1978), “A Method for Obtaining

Digital Signatures and Public key Cryptosystems”/ Communication of the

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

ACM, Vol. 21, No.2, pp 120-126.

[13] T. ElGamal (1985), A public key cryptosystem and a signature scheme based

on discrete logarithms. IEEE Transactions on Information Theory, Vol. IT-31,

No. 4. pp. 469–472.

[ 1 4 ] Zuzana Rjaskova ( 2 0 0 2 ) , E l e c t r o n i c V o t i n g S c h e m e s . Department

of Computer ScienceFaculty of Mathematics, Physics and Informatics Comenius

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

University, Bratislava

Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu một số thuật toán hệ mật mã khoá công khai Elgamal và ứng dụng

NGHIÊN CỨU MỘT SỐ THUẬT TOÁN HỆ MẬT MÃ

KHOÁ CÔNG KHAI ELGAMAL VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGHIÊN CỨU MỘT SỐ THUẬT TOÁN HỆ MẬT MÃ

KHOÁ CÔNG KHAI ELGAMAL VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

LỜI CAM ĐOAN

LỜI CẢM ƠN

Chương 3: ỨNG DỤNG HỆ MẬT MÃ ELGAMAL TRONG BÀI TOÁN BỎ PHIẾU

a) -1 ( mod p) = x.

a) -1 mod p = 91(932365)-1 mod 2179 = 1985.

2 (mod 17).

2 (mod 17), a0 = K. Thay x1 = 1, x3 = 3, x5 = 5 vào P(x) = a0 + a1 x + a2 x

Cử tri

Kiểm phiếu

Đăng ký

Có thể bạn quan tâm

Tài liêu mới

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok

Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu một số thuật toán hệ mật mã khoá công khai Elgamal và ứng dụng

NGHIÊN CỨU MỘT SỐ THUẬT TOÁN HỆ MẬT MÃ

KHOÁ CÔNG KHAI ELGAMAL VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGHIÊN CỨU MỘT SỐ THUẬT TOÁN HỆ MẬT MÃ

KHOÁ CÔNG KHAI ELGAMAL VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

LỜI CAM ĐOAN

LỜI CẢM ƠN

Chương 3: ỨNG DỤNG HỆ MẬT MÃ ELGAMAL TRONG BÀI TOÁN BỎ PHIẾU

a) -1 ( mod p) = x.

a) -1 mod p = 91(932365)-1 mod 2179 = 1985.

2 (mod 17).

2 (mod 17), a0 = K. Thay x1 = 1, x3 = 3, x5 = 5 vào P(x) = a0 + a1 x + a2 x

Cử tri

Kiểm phiếu

Đăng ký

Có thể bạn quan tâm

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok