PHƯƠNG PHÁP CHỨNG MINH KHÔNG TIẾT LỘ THÔNG TIN VÀ ỨNG DỤNG TRONG GIAO DỊCH TRÊN MẠNG MÁY TÍNH

LINK DOWNLOAD MIỄN PHÍ TÀI LIỆU "PHƯƠNG PHÁP CHỨNG MINH KHÔNG TIẾT LỘ THÔNG TIN VÀ ỨNG DỤNG TRONG GIAO DỊCH TRÊN MẠNG MÁY TÍNH": http://123doc.vn/document/1037694-phuong-phap-chung-minh-khong-tiet-lo-thong-tin-va-ung-dung-trong-giao-dich-tren-mang-may-tinh.htm

MỤC LỤC CÁC HÌNH VẼ
Hình 1 : Sơ đồ cử chi chuyển lá phiếu đến ban kiểm phiếu 25
Hình 2 : Quá trình khởi tạo tài khoản 33
Hình 3 : CT điền các thông tin cần thiết để mã hóa lá phiếu thăm dò 40
Hình 4 : Các thông số trả về từ TT và các tính toán của CT 41
Hình 5 : Lá phiếu khi đã được TT kiểm tra lại 41
Hình 6 : TT tính Beta và w
2
42
Hình 7 : TT tính r 42
Hình 8 : CT kiểm tra lại kết quả 43



















MỤC LỤC CÁC BẢNG
Bảng 1 : Mô tả các bước tính : 5
596
mod 1234 = 1013 8
Bảng 2 : Độ phức tạp theo bit của các phép toán cơ bản trong Z 9
Bảng 3 : Giai đoạn 1 cử tri chứng minh lá phiếu hợp lệ 26
Bảng 4 : Giai đoạn 2, TT chứng minh lá phiếu làm mù là hợp lệ 29
Bảng 5 : Phương án 1 gồm 2 giai đoạn một và hai 31
Bảng 6 : Quá trình chứng minh đại diện 34
Bảng 7 : Giao thức rút tiền 36
Bảng 8 : Giao thức thanh toán 38



















DANH MỤC TỪ VIẾT TẮT
Ký hiệu viết tắt
Giải thích
CT
Cử tri
gcd(m, n)
Ƣớc chung lớn nhất
KP
Kiểm phiếu
Prover
Ngƣời chứng minh
TT
Ngƣời trung thực
Verifier
Ngƣời xác minh


1

LỜI NÓI ĐẦU
Ngày nay Internet đã trở thành một phần không thể thiếu trong mỗi ngƣời dân
Việt Nam nói riêng cũng nhƣ mỗi ngƣời dân trên thế giới nói riêng. Thông tin không
ngừng đƣợc trao đổi, mua bán,…trên mạng Internet, cũng chính vì lý do nà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 yêu cầu cần
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 đƣợc truyền trên mạng.
Khoá luận này tập trung vào nghiên cứu các khái niệm cơ bản, cơ sở lý thuyết
toán học modulo sử dụng trong bảo mật thông tin, các phƣơng pháp “chứng minh
không tiết lộ thông tin” và đặc biệt là ứng dụng của “chứng minh không tiết lộ thông
tin” trong bỏ phiếu thăm dò từ xa.
Chứng minh không tiết lộ thông tin đã đƣợc nghiên cứu từ những năm 80, là
phƣơng pháp chứng minh không có nghĩa là “không để lộ thông tin” mà “để 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 sẽ 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 về 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ột số ứng dụng thực tế của cơ sở lý thuyết này.











2

Chương 1 : CÁC KHÁI NIỆM VÀ THUẬT TOÁN CƠ BẢN
Chƣơng này trình bày các vấn đề cơ bản trong toán học đƣợc ứng dụng nhiều
trong các bài toán an toàn thông tin. Đó là các vấn đề về lý thuyết toán học sử dụng
trong bảo mật và mã hóa thông tin nhƣ : Mã hóa đồng cấu, chữ ký mù, chia sẻ bí mật
ngƣỡng Shamir và mã hóa Elgamal. Thông qua đó hình thành cơ sở lý thuyết cho an
toàn truyền tin trên mạng máy tính.
1.1 LÝ THUYẾT MODULO
1.1.1 Hàm phi Euler
1/ Định nghĩa
Cho n >= 1, Φ(n) đƣợc định nghĩa là số các số nguyên trong khoảng từ [1, n]
nguyên tố cùng nhau với n. Hàm Φ (n) đƣợc gọi là hàm Euler phi.
2/ Tính chất của hàm Euler
 Nếu p là số nguyên tố thì Φ (n) = p – 1.
 Hàm phi Euler là hàm có tính nhân : Nếu gcd(m, n) = 1 thì Φ(mn) = Φ(m) Φ(n)
(trong đó gcd(m, n) là ký hiệu ƣớc số chung lớn nhất của m và n)
 Nếu n = p
1
e1
p
2
e2
…p
k
ek
trong đó p
1
, p
2
, , p
k
là các thừa số nguyên tố của n thì:
Φ(n) = n(1 -
1
1
p
)(1 -
2
1
p
)… (1 -
pk
1
)
1.1.2 Đồng dƣ thức
1/ Định nghĩa
Cho a và b là các số nguyên, a đƣợc gọi là đồng dƣ với b theo modulo n, ký hiệu:
a

b (mod n) nếu (a – b) chia hết cho n. Số nguyên n đƣợc gọi là modulus đồng dƣ.
2/ Ví dụ
10  3 (mod 7) vì 10 – 3 = 7 chia hết cho 7
7  -4 (mod 11) vì 7 – (-4) = 11 chia hết cho 11
3

3/ Tính chất của đồng dư
Cho a, a
1
, b, b
1
, c

Z. Ta có các tính chất sau:
 a

b (mod n) nếu và chỉ nếu a và b cùng có số dƣ khi chia cho n
 a

a (mod n) – Tính phản xạ
 a

b (mod n) thì b

a (mod n) – Tính đối xứng
 a

b (mod n) và b

c (mod n) thì a

c (mod n) – Tính bắc cầu
 nếu a

a
1
(mod n) và b

b
1
(mod n) thì :
a + b

a
1
+ b
1
(mod n)
a.b

a
1
.b
1
(mod n)
Quan hệ “đồng dƣ” theo modulo n trên tập Z (tập các số nguyên) là một quan hệ
tƣơng đƣơng (vì có tính chất phản xạ, đối xứng, bắc cầu), do đó nó tạo ra trên tập một
phân hoạch gồm các lớp tƣơng đƣơng : hai số nguyên thuộc cùng một lớp tƣơng
đƣơng khi và chỉ khi chúng có cùng một số dƣ khi chi cho n.
Mỗi lớp tƣơng đƣơng đại diện bởi một số duy nhất trong tập Z
n
= {0, 1, 2, … , n-1}
là số dƣ khi chia các số trong lớp cho n, ký hiệu một lớp đƣợc đại diện bởi số a là [a]
n
:
Nhƣ vậy : [a]
n
= [b]
n
tƣơng đƣơng với a

b (mod n)
Vì vậy ta có thể đồng nhất Z
n
với tập các lớp tƣơng đƣơng theo modulo n.
Z
n
= {0, 1, 2, … , n-1} đƣợc gọi là tập các “thặng dƣ đầy đủ” theo modulo n. Mọi
số nguyên bất kỳ đều có thể tìm đƣợc trong Z
n
một số đồng dƣ với mình theo
modulo n.
1.1.3 Không gian Z
n

1/ Các định nghĩa trong không gian Z
n

Các số nguyên theo modul n ký hiệu Z
n
là tập hợp các số nguyên {0,1,2,…, n-1}.
Các phép toán cộng, trừ, nhân trong Z
n
đƣợc thực hiện theo modulo n.
2/ Ví dụ
Z
25
= {0,1,2,…,24}. Trong Z
25
: 13 + 16 = 4, bởi vì: 13 + 16 = 29  4 (mod 25).
Tƣơng tự, 13*16 = 8 trong Z
25
- Cho a

Z
n
. Nghịch đảo nhân của a theo modulo n là một số nguyên x

Z
n
sao
cho a*x

1 (mod n). Nếu x tồn tại thì đó là giá trị duy nhất và a đƣợc gọi là khả
nghịch, nghịch đảo của a ký hiệu là a
-1
.
4

- Cho a, b

Z
n
. Phép chia của a cho b theo modulo n là tích của a và b
-1
theo
modulo n, và chỉ dƣợc xác định khi b có nghịch đảo theo modulo n.
3/ Các tính chất trong không gian Z
n

- Cho a

Z
n
, a có nghịch đảo khi và chỉ khi gcd(a, n) = 1 trong đó :
gcd(a, n) (greatest common divisor) là ký hiệu ƣớc số chung lớn nhất của a và n
Ví dụ:
Các phần tử khả nghịch trong Z
9
là: 1, 2, 4, 5, 7 và 8.
Ví dụ 4
-1
= 7 vì 4 .7  1 (mod 9)
Tiếp theo là sự tổng quát hoá của tính chất 1.6
- Giả sử d = gcd(a, n). Phƣơng trình đồng dƣ ax

b (mod n) có nghiệm x nếu và
chỉ nếu d chia hết cho b, trong trƣờng hợp các nghiệm d nằm trong khoảng 0 đến
n-1 thì các nghiệm đồng dƣ theo modulo n/d.
4/ Định lý phần dư Trung Hoa CRT
Nếu các số nguyên n
1
, n
2
, …, n
k
là các số nguyên tố cùng nhau từng đôi một thì
hệ phƣơng trình đồng dƣ :
x

a
1
(mod n
1
)
x

a
2
(mod n
2
)
…
x

a
k
(mod n
k
)
có nghiệm duy nhất theo modulo n = n
1
n
2
… n
k
5/ Thuật toán của Gausse
Nghiệm x trong hệ phƣơng trình đồng dƣ (định lý phần dƣ Trung Hoa) đƣợc tính
nhƣ sau :
x =


k
i 1
a
i
N
i
M
i
mod n
trong đó: N
i
= n/n
i
, M
i
= N
i
-1
mod n
i
5

Ví dụ:
Cặp đồng dƣ: x  3 (mod 7) và x  7 (mod 13) có nghiệm duy nhất
x  59 (mod 91)
Tính chất :
Nếu gcd(n
1,
n
2
) = 1 thì cặp đồng dƣ x

a (mod n
1
) và x

a (mod n
2
) có nghiệm
duy nhất x

a (mod n
1
n
2
)
1.1.4 Nhóm nhân Z
n
*

1/ Các định nghĩa trong nhóm nhân Z
*
n
Nhóm nhân của Z
n
ký hiệu là Z
*
n
= {a

Z
n
| gcd (a, n) = 1}.
Đặc biệt, nếu n là số nguyên tố thì Z
*
n
= {a

Z
n
| 1 ≤ a ≤ n-1}
Cho a

Z
n
*
.
Bậc của a, ký hiệu là ord(a) là số nguyên dƣơng t nhỏ nhất sao cho
a
t


1 (mod n).
2/ Các tính chất trong Z
n
*
- Cho n ≥ 2 là số nguyên :
 (Định lý Euler) Nếu a

Z
n
*
thì a
Φ(n)

1 (mod n).
 Nếu n là tích của các số nguyên tố phân biệt và nếu r

s (mod Φ(n))
a
r


a
s
(mod n) với mọi số nguyên a. Nói cách khác, làm việc với các số theo
modulo nguyên tố p thì số mũ có thể giảm theo modulo Φ(n)
- Cho p là số nguyên tố :
 (Định lý Fermat) Nếu gcd(a, p) = 1 thì a
p-1

1 (mod p).
 Nếu r

s (mod p-1) thì a
r


a
s
(mod p) với mọi số nguyên a. Nói cách khác,
làm việc với các số theo modulo nguyên tố p thì số mũ có thể giảm theo
modulo p-1
 Đặc biệt a
p


a (mod p) với mọi số nguyên a.
6

1.1.5 Thặng dƣ
1/ Định nghĩa thặng dư
Cho a

Z
n
*
.
a đƣợc gọi là thặng dƣ bậc 2 theo modulo n hoặc bình phƣơng theo
modulo n nếu tồn tại x

Z
n
*
sao cho x
2


a (mod n). Nếu không tồn tại x thì a đƣợc gọi
là thặng dƣ không bậc 2 theo modulo n. Tập hợp các thặng dƣ bậc 2 theo modulo n ký
hiệu là Q
n
và tập hợp các thặng dƣ không bậc 2 theo modulo n ký hiệu là
___
Q
n
.
Chú ý vì định nghĩa 0

Z
n
*
nên 0

Q
n
và 0

___
Q
n
2/ Tính chất của thặng dư
Cho n là tích của 2 số nguyên tố p và q. Khi đó a

Z
n
*
là một thặng dƣ bậc 2 theo
modulo n khi và chỉ khi a

Q
n
và a

___
Q
n
. Ta có, |Q
n
| = |Q
p
|.|Q
q
| = (p-1)(q-1)/4 và
|
___
Q
n
| = 3(p-1)(q-1)/4
3/ Ví dụ
Cho n = 21. Khi đó: Q
21
= {1, 4, 16} và
___
Q
21
= {2, 5, 8, 10, 11, 13, 17, 19, 20}
1.1.6 Căn bậc Modulo
1/ Định nghĩa
Cho a

Q
n
. Nếu a

Z
n
*
thoả mãn x
2


a (mod n) thì x đƣợc gọi là căn bậc 2 của
a theo modulo n.
2/ Tính chất (Số căn bậc 2)
 Nếu p là một số nguyên tố lẻ thì a

Q
n
thì a có chính xác 2 căn bậc 2 theo
modulo p
 Tổng quát hơn: cho n = p
1
e1
p
2
e2
…p
k
ek
trong đó p
i
là các số nguyên tố lẻ phân
biệt và e
i
≥1. Nếu a

Q
n
thì a có chính xác 2
k
căn bậc 2 theo modulo n.
3/ Ví dụ
Căn bậc 2 của 13 theo modulo 37 là 7 và 30. căn bậc 2 của 121 modulo 315 là
11, 74, 101, 151, 164, 214, 241 và 304.
7

1.1.7 Các thuật thoán trong Z
n
*

1/ Định nghĩa
Cho n là số nguyên dƣơng. Nhƣ đã nói ở trƣớc, các phần tử trong Z
n
sẽ đƣợc thể
hiện bởi các số nguyên {0, 1, 2,…, n-1}. Ta thấy rằng: nếu a, b

Z
n
thì:
(a + b) mod n=

a + b nếu a + b < n
a + b – n nếu a + b ≥ n
Vì vậy, phép cộng modulo (và phép trừ modulo) có thể đƣợc thực hiện mà không
cần thực hiện các phép chia . Phép nhân modulo của a và b có thể đƣợc thực hiện bằng
phép nhân thông thƣờng a với b nhƣ các số nguyên bình thƣờng, sau đó lấy phần dƣ
của kết quả sau khi chia cho n. Phép tính nghịch đảo trong Z
n
có thể đƣợc thực hiện
nhờ sử dụng thuật toán Euclidean mở rộng nhƣ mô tả sau:
2/Thuật toán tính nghịch đảo nhân trong Z
n
INPUT: a

Z
n

OUTPUT: a
-1
mod n nếu tồn tại.
1. Sử dụng thuật toán Euclidean mở rộng sau để tìm các số nguyên x và y
sao cho: ax + ny = d với d = gcd(a, n).
2. Nếu d > 1 thì a
-1
mod n không tồn tại. Ngƣợc lại, return (x).
3/ Thuật toán Euclidean mở rộng:
INPUT: 2 số nguyên dƣơng a và b với a ≥ b.
OUTPUT: d = gcd(a, b) và các số nguyên x, y thoả mãn: ax + by = d
1. Nếu b = 0 thì đặt d

a, x

1, y

0 và return (d, x, y)
2. Đặt x
2

1, x
1

0, y
2

0, y
1

1
3. Khi b > 0 thực hiện:
3.1. q

[a/b], r = a – qb, x


x
2
– qx
1
, y

y
2
– qy
1

3.2. a

b, r

b, x
2

x
1
, x
1

x, y
2

y
1
, y
1

y
4. Đặt d

a, x


x
2
, y


y
2
và return (d, x, y)