Luận Văn Tìm hiểu, nghiên cứu vấn đề &quot Chứng minh không tiết lộ thông tin&quot và ứng dụng

Đồ án tốt nghiệp năm 2012
Đề tài: Tìm hiểu, nghiên cứu vấn đề "Chứng minh không tiết lộ thông tin" và ứng dụng


MỤC LỤC
LỜI NÓI ĐẦU .5
Chương 1. CÁC KHÁI NIỆM CƠ BẢN 6
1.1. MỘT SỐ KHÁI NIỆM TOÁN HỌC 6
1.1.1. Các khái niệm trong số học .6
1.1.1.1. Số nguyên tố .6
1.1.1.2. Nguyên tố cùng nhau . 6
1.1.1.3. Ước chung lớn nhất 6
1.1.1.4. Hàm Euler 9
1.1.1.5. Đồng dư thức . 9
1.1.2. Các khái niệm trong đại số . 10
1.1.2.1. Không gian Z
n
. 10
1.1.2.2. Nhóm nhân Z
n
*
. 12
1.1.2.3.Phần tử sinh 13
1.1.2.4.Thặng dư . 14
1.1.2.5. Khái niệm nhóm, nhóm con, nhóm Cyclic 15
1.1.3.Khái niệm độ phức tạp của thuật toán . 16
1.1.3.1.Khái niệm thuật toán 16
1.1.3.2.Khái niệm độ phức tạp của thuật toán 16
1.1.3.3. Lớp bài toán P, NP và NP – complete . 18
1.2. VẤN ĐỀ VỀ MÃ HÓA 20
1.2.1. Một số khái niệm . 20
1.2.2. Mã hóa khóa đối xứng . 21
1.2.3. Mã hóa khóa bất đối xứng . 22
1
1.3. VẤN ĐỀ VỀ CHỮ KÝ SỐ (digital signature) 25
1.3.1. Khái niệm . 25
1.3.2.Quá trình tạo ra chữ ký điện tử 26
1.3.3. Hàm băm sử dụng trong chữ ký điện tử . 26
Chương 2. PHƯƠNG PHÁP CHỨNG MINH KHÔNG TIẾT LỘ THÔNG
TIN 28
2.1. KHÁI NIỆM CHỨNG MINH KHÔNG TIẾT LỘ THÔNG TIN 28
2.1.1. Khái niệm chứng minh không tiết lộ thông tin (CM KTLTT) . 28
2.1.2. Khái niệm về chứng minh tương hỗ . 30
2.2. HỆ THỐNG CM KTLTT CHO TÍNH ĐẲNG CẤU CỦA ĐỒ THỊ 31
2.2.1 Khái niệm đồ thị đẳng cấu . 31
2.2.2. Định nghĩa hệ thống CM KTLTT hoàn thiện . 31
2.2.3. Định nghĩa hệ thống CM KTLTT hoàn thiện không điều kiện 37
2.2.4. Định lý về hệ thống chứng minh tương hỗ cho đồ thị đẳng cấu 39
2.3. HỆ THỐNG CM KTLTT CHO BÀI TOÁN THẶNG DƯ BẬC HAI . 41
2.3.1. Sơ đồ chưng minh 41
2.3.2. Tính chất của sơ đồ 42
2.3.3. Chứng minh sơ đồ có tính đầy đủ 42
Chương 3. ỨNG DỤNG CHỨNG MINH KHÔNG TIẾT LỘ THÔNG TIN . 43
3.1. ỨNG DỤNG CM KTLTT TRONG BỎ PHIẾU ĐIỆN TỬ . 43
3.1.1. Sơ đồ bỏ phiếu truyền thống 43
3.1.2. Một số khái niệm 44
3.1.3. Chứng minh tính hợp lệ của lá phiếu (x, y) (Giao thức 1) . 47
3.1.4. Chứng minh quyền sở hữu giá trị bí mật (Giao thức 2) 52
3.1.5. Giai đoạn cử tri chuyển lá phiếu tới ban kiểm phiếu (phương án 2).54
3.2. ỨNG DỤNG CM KTLTT TRONG SỬ DỤNG TIỀN ĐIỆN TỬ 56
2
3.2.1. Khái niệm thanh toán điện tử . 56
3.2.2. Khái niệm tiền điện tử 56
3.2.3. Mô hình giao dịch mua bán bằng tiền điện tử 57
3.2.4. Vấn đề “tiền điện tử” 60
3.2.5. Lược đồ tiền điện tử Brand 63
Chương 4. THỬ NGHIỆM CHƯƠNG TRÌNH 71
4.1. MÔ TẢ CHƯƠNG TRÌNH . 71
4.1.1. Giới thiệu 71
4.1.2. Các chức năng chính 72
4.2. MÃ NGUỒN CỦA CHƯƠNG TRÌNH 76
4.2.1. Cử tri chứng minh tính hợp lệ của lá phiếu 76
4.2.2. Người xác minh trung thực chứng minh có giữ tham số bí mật . 85
TÀI LIỆU THAM KHẢO 87


LỜI NÓI ĐẦU
Ngày nay, công nghệ thông tin đang phát triển mạnh mẽ, Internet đã trở
thành một phần không thể thiếu trong cuộc sống hàng ngày thì các hoạt động trao
đổi thông tin, mua bán, trên mạng Internet diễn ra thường xuyên và ngày càng
phổ biến hơn. Chính vì vậy mà việc bảo mật, đảm bảo an toàn thông tin đang là
nhu cầu cấp thiết. Trước các nhu cầu cấp thiết đó, lý thuyết về mật mã thông tin đã
ra đời nhằm đảm bảo tính an toàn dữ liệu tại nơi lưu trữ cũng như khi dữ liệu đang
được truyền trên mạng.
Khóa luận này gồm có 4 chương với các nội dung:
Chương 1. CÁC KHÁI NIỆM CƠ BẢN
Chương 2. PHƯƠNG PHÁP CHỨNG MINH KHÔNG TIẾT LỘ THÔNG TIN
Chương 3. ỨNG DỤNG CHỨNG MINH KHÔNG TIẾT LỘ THÔNG TIN
Chương 4. THỬ NGHIỆM CHƯƠNG TRÌNH
“Chứng minh không tiết lộ thông tin”, là phương pháp chứng minh không có
nghĩa là “không để lộ thông tin” mà là “để lộ thông tin ở mức ít nhất” về sự vật, sự
việc cần chứng minh. Với việc “không để lộ” người xác minh không có nhiều hiểu
biết về sự vật sự việc, họ chỉ thu được chút ít thông tin (coi như là không) về đặc
điểm tính chất của nó.
Ngành mật mã học luôn phát triển không ngừng, trong phạm vi khóa luận
này, chúng tôi chỉ trình bày một vấn đề nhỏ là phương pháp “chứng minh không
tiết lộ thông tin” đồng thời tìm hiểu mộ số ứng dụng thực tế của cơ sở lý thuyết này.


Chương 1. CÁC KHÁI NIỆM CƠ BẢN
1.1. MỘT SỐ KHÁI NIỆM TOÁN HỌC
1.1.1. Các khái niệm trong số học
1.1.1.1. Số nguyên tố
Khái niệm:
Số nguyên tố là số nguyên dương chỉ chia hết cho một và chính nó
Ví dụ:
Các số 2, 3, 5, 7, 11, 13, 17, 19, 23 là số nguyên tố. Số 2 là số nguyên tố
chẵn duy nhất.
Tính chất:
+ Nếu p là số nguyên tố và p|ab thì ta có a|p hoặc b|p hoặc cả a và b chia hết cho p.
+ Có vô số, số nguyên tố.
1.1.1.2. Nguyên tố cùng nhau
Hai số m và n được gọi là nguyên tố cùng nhau, nếu ước số chung lớn nhất
của chúng bằng 1. Ký hiệu: (m,n)=1. Ví dụ: 9 và 14.
1.1.1.3. Ước chung lớn nhất
1/. Ước số
Khái niệm:
Cho hai số nguyên a, b Z, b 0. Nếu có một số nguyên q sao cho a=b*q,
thì ta nói rằng a chia hết cho b, ký hiệu b|a. Ta nói b la ước của a, và a là bội của b.
Ví dụ:
+ Cho a=6, b=2, ta có 6=2*3, ký hiệu 2|6. Ở đấy 2 là ước của 6 và 6 là bội của 2.
7
Tính chất:
Cho a, b, c Z
+ a|a.
+ a|b, b|c a|c.
+ a|b, a|c a|(bx+cy) x, y Z.
+ a|b, b|a a= b.
2/. Ước chung lớn nhất
Khái niệm ước chung lớn nhất:
Số nguyên d được gọi là ước chung của các số nguyên a
1
, a
2
, ,a
n
,nếu nó là
ước của tất cả các số đó.
Một ước chung d > 0 của các số nguyên a
1
,a
2
, ,a
n, trong đó mọi ước chung
của a
1
, a
2
, ,a
n
, đều là ước của d, thì d được gọi là ước chung lớn nhất (ƯCLN) của
a
1
, a
2
, ,a
n
. Ký hiệu d = gcd(a
1
, a
2
, ,a
n
) hay d = ƯCLN(a
1
, a
2
, ,a
n
).
Ví dụ:
Cho a = 12, b = 15, gcd(12,15) = 3.


TÀI LIỆU THAM KHẢO
[1] Andrew Neff, “Conducting a Universally Verifiable Electronic
Election Using Homomorphic Encryption ”, VoteHere.net, November 2000.
[2] Berry Schoenmakers, “A brief Comparision of Cryptographic Schemes
for Electronic Voting”, Tartu, Estonia, May 17, 2004 .
[3] Byoungcheon Lee, Kwangjo Kim, “Receipt-free Electronic Voting
hrough Collaboration of Voter and honest Verifier” .
[4] Helger Lipmaa, “Zero knowledge and some applications”, Nordic
Research Training course, Bergen, June 15, 2004.
[5] Information Security Research Centre, Faculty of Information
Technology, Queensland University of Technology, “Electronic Voting and
Cryptography”, May 2002 .
[6] Trịnh Nhật Tiến, Nguyễn Đình Nam, Trương Thị Thu Hiền, “Một số
kỹ huật Bỏ phiếu từ xa”, Hội thảo Một số vấn đề chọn lọc của Công nghệ thông
tin,Thái Nguyên, tháng 8 năm 2003.
[7] Trịnh Nhật Tiến, Trương Thị Thu Hiền, “Mã hóa đồng cấu và ứng
dụng”, Hội nghị khoa học cơ bản và ứng dụng CNTT toàn quốc lần thứ 1, Đại học
Quốc Gia Hà Nội, tháng 10 năm 2003.