TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

ĐẠI HỌC QUỐC GIA HÀ NỘI

LUẬN VĂN THẠC SỸ
NGUYỄN TRỊNH ĐOÀN

Người hướng dẫn: PGS. TS. Trịnh Nhật Tiến
Hà Nội ngày 01 tháng 12 năm 2007

Chữ ký số mù nhóm
IDEA
International Data Encryption
Algorithm
Thuật toán mật mã dữ liệu
Quốc tế
LRF
Local Registration Facility
Phƣơng tiện đăng ký địa phƣơng
MAC
Message Authentication Code
Mã xác thực thông điệp
MD5
Message Digest algorithm 5
Thuật toán hàm băm MD5
PKI
Public Key Infrastructure
Cơ sở hạ tầng khoá công khai
SHA-1
Secure Hash Algorithm
Thuật toán hàm băm SHA-1
SK
Signature of Knowledge
Chữ ký dựa trên tri thức
VSF
Vote Submission Facility.
Phƣơng tiện đệ trình phiếu

Tài liệu tham khảo [2], [3], [5], [7], [33] 3
MỞ ĐẦU
1. Lý do chọn đề tài
Trong cuộc sống và trong các hoạt động của con ngƣời, việc trao đổi
thông tin là một nhu cầu thiết yếu, con ngƣời trao đổi thông tin để tồn tại và
phát triển trong quy luật vận động của tự nhiên và xã hội. Thông tin thì đa
dạng, phong phú đƣợc thể hiện dƣới nhiều dạng thức khác nhau nhƣ văn bản,
hình ảnh, âm thanh, số liệu,…Mặt khác việc trao đổi thông tin cũng diễn ra
dƣới nhiều hình thức và bằng các phƣơng pháp khác nhau.
Cùng với sự phát triển của công nghệ thông tin, các phƣơng tiện và
công nghệ truyền thông tiên tiến ra đời, trong đó mạng máy tính và đặc biệt là
mạng Intenet đã giúp con ngƣời trao đổi thông tin hết sức thuận tiện, nhanh
chóng. Một vấn đề vô cùng quan trọng đƣợc đặt ra là sự bảo mật và an toàn
trong việc trao đổi thông tin. Các thông tin truyền đi phải đảm bảo tính chính
xác, không bị sửa đổi và trong rất nhiều trƣờng hợp cần đƣợc bảo đảm tính bí
mật thông tin và cần xác thực đúng ngƣời gửi và ngƣời nhận. Xuất phát từ
thực tế này có nhiều biện pháp về an toàn thông tin ra đời.
Một giải pháp hữu hiệu cho cho việc đảm bảo tính bí mật của thông tin
là mã hóa thông tin. Mã hóa thông tin là sự biến đổi thông tin thành một dạng
khác với mục đích “che giấu” nội dung thông tin, chỉ những đối tƣợng có
thẩm quyền mới có thể giải mã thông tin đã mã hóa (hủy bỏ sự “che giấu”) để
lấy lại thông tin ban đầu.
Để xác thực thông tin, gắn trách nhiệm của một thực thể nào đó với một
thông tin, cũng nhƣ đảm bảo tính toàn vẹn, thông tin truyền đi không bị sửa
đổi ngoài ý muốn, con ngƣời đã sáng tạo ra chữ ký số.
Vấn đề xƣng danh và xác nhận danh tính của các thực thể cũng là các
vấn đề rất cần thiết trong giao dịch điện tử.

5
2. Nội dung nghiên cứu của luận văn
Luận văn tập trung nghiên cứu một số vấn đề chính sau đây:
1) Một số kiến thức toán học sử dụng trong khoa học mật mã
2) Tổng quan về mã hóa và chữ ký số (chữ ký điện tử).
3) Sơ đồ chữ ký RSA.
4) Các sơ đồ chữ ký số mù, chữ ký số nhóm, chữ ký số mù nhóm.
5) Ứng dụng của các sơ đồ chữ ký nói trên.
Sơ đồ chữ ký RSA là một sơ đồ chữ ký thông dụng hiện nay vì sự cài
đặt đơn giản và tính an toàn cao, làm cơ sở xây dựng nhiều loại chữ ký khác.
Các sơ đồ chữ ký số mù, chữ ký số nhóm và chữ ký số mù nhóm là các
sơ đồ chữ ký đặc biệt có nhiều ứng dụng trong các lĩnh vực: Tiền điện tử, giao
dịch ngân hàng, thƣơng mại điện tử, bỏ phiếu trực tuyến,…Các loại chữ ký
này đƣợc thiết kế để giải quyết các vấn đề: ẩn danh, làm việc theo nhóm và ký
đại diện cho nhóm trong giao dịch điện tử.
3. Phƣơng pháp nghiên cứu
Luận văn đƣợc nghiên cứu dựa trên:
1) Học hỏi, xin ý kiến của thầy hướng dẫn và các đồng nghiệp.
2) Nghiên cứu các tài liệu chuyên môn liên quan bằng tiếng Việt,
tiếng Anh, tìm kiếm thông tin trên Internet.
3) Tìm hiểu và quan sát thực tiễn.
4) Thử nghiệm một số chương trình đơn giản. 6
4. Tổ chức luận văn
Luận văn gồm 6 chƣơng nhƣ sau:
Chương 1: Các kiến thức cơ sở.
Chương 2: Tổng quan về mã hóa và chữ ký số.
Chương 3: Chữ ký mù.

phép chia a cho b. Nếu r = 0 thì ta có phép chia hết.
Ví dụ: a = 13, b = 5; 13 = 5.2 + 3 → q = 2, r = 3.
1.1.1.2. Một số tính chất
Với a, b, c là các số nguyên ta có:
1) ±1\a, với mọi a; a\0, a\a, với mọi a ≠ 0.
2) Nếu a\b và b\c thì a\c, với mọi a ≠ 0, b ≠ 0.
3) Nếu a\b thì a\b.c, với mọi a ≠ 0.
4) Nếu a\b và a\c thì a\(b+c) và a\(b-c), với mọi a ≠ 0.
5) Nếu a\b và c\d thì a.c\b.d, với mọi a ≠ 0, c ≠ 0. 8
1.1.2. Ƣớc chung lớn nhất, bội chung nhỏ nhất
1.1.2.1. Định nghĩa 1.1.2
1) Mộ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ố đó.
2) Một số nguyên m đƣợc gọi là bội chung của các số nguyên a
1
, a
2
, …, a
n

nếu nó là bội của tất cả các số đó.

2
, …, a
n
).
4) Nếu gcd(a
1
, a
2
, …, a
n
) = 1 thì các số a
1
, a
2
, …, a
n
đƣợc gọi là nguyên tố
cùng nhau.
5) Một bội chung m>0 của các số nguyên a
1
, a
2
, …, a
n
sao cho mọi bội chung
của a
1
, a
2
, …, a

,…, x
n
sao cho:
d = a
1
x
1
+a
2
x
2
+…+a
n
.
2) m = lcm(a
1
, a
2
, …, a
n
) khi và chỉ khi (m/a
1
, m/a
2
,…, m/a
n
) =1.
3) Nếu d là một ƣớc chung của a
1
, a

) = m.gcd(a
1
, a
2
, …, a
n
) (với m≠0).
9) lcm(a, b) = ab/gcd(a, b).
1.1.2.3. Thuật toán Euclide tìm ước chung lớn nhất
1) Bài toán
 Dữ liệu vào: Cho hai số nguyên không âm a, b, a ≥ b.
 Kết quả: gcd(a,b).
2) Thuật toán (mô phỏng bằng ngôn ngữ Pascal)
Readln(a, b);
While b > 0 do
Begin
r := a mod b; a := b; b := r;
End;
Writeln(a);
3) Ví dụ
Cho: a = 30, b = 18;
Ta có: gcd(30,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) = 6.
a
b
r
a = b.q + r
30
18
12
30 = 18.1 + 12

d := a; x := x2; y := y2;
writeln(d, x, y);
End; 11
1.1.3. Số nguyên tố
1.1.3.1. Định nghĩa 1.1.3
Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có hai ƣớc là 1 và chính nó.
Ví dụ: Các số 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 là số nguyên tố.
Số nguyên tố có vai trò và ý nghĩa to lớn trong số học và lý thuyết mật mã.
Bài toán kiểm tra tính nguyên tố của một số nguyên dƣơng N và phân tích một
số N ra thừa số nguyên tố là các bài toán rất đƣợc quan tâm và có nhiều công
trình nghiên cứu và đã đạt đƣợc các kết quả to lớn. Hiện nay bài toán kiểm tra
tính nguyên tố đƣợc xếp vào lớp bài toán P.
Có một số phƣơng pháp kiểm tra tính nguyên tố của một số nguyên
bằng xác xuất nhƣ: Solovay-Strassen, Lehmann-Peralta, Miller-Rabin [5].
Ví dụ: 10 số nguyên tố đƣợc tìm thấy [33].
Thứ
hạng
Số nguyên tố
Số chữ số
Tác
giả
Thời
gian
Tham khảo
1
2
32582657

2
20996011
-1
6320430
G6
2003
Mersenne 40
6
2
13466917
-1
4053946
G5
2001
Mersenne 39
7
19249·2
13018586
+1
3918990
SB10
2007

8
27653·2
9167433
+1
2759677
SB8
2005

k
n P P P
với k, n
i
là các số tự nhiên, P
i
là các số nguyên tố đôi
một khác nhau (i = 1, 2, , k).
2) Định lý 1.1.2 (Định lý Mersenne)
Cho p = 2
k
-1, nếu p là số nguyên tố thì k là số nguyên tố.
Chứng minh
Giả sử k không là số nguyên tố. Khi đó k = a.b với 1 < a, b < k, do đó
p = 2
k
-1 = 2
ab
-1 = (2
a
)
b
-1 = (2
a
-1).E (E là một biểu thức nguyên) mâu thuẫn
giả thiết p là nguyên tố. Vậy giả sử là sai, hay k là số nguyên tố.
3) Định lý 1.1.3 (Hàm Euler)
▪ Hàm Euler
Cho số nguyên dƣơng n, số lƣợng các số nguyên dƣơng bé hơn n và
nguyên tố cùng nhau với n đƣợc ký hiệu

a = mq
a
+ r; b = mq
b
+ r; suy ra a - b = m(q
a
- q
b
) chứng tỏ m \ a-b;
2)→3) : m\a-b nên có t

Z sao cho a - b = mt hay a = b + mt
3)→1) : Lấy a chia cho m giả sử thƣơng là q
a
và dƣ r: a = mq
a
+ r (0 ≤ r <m),
do đó: b + mt = a = mq
a
+ r hay b = m(q
a
- t) + r (0 ≤ r < m). Điều đó chứng tỏ
khi chia a và b cho m đƣợc cùng số dƣ r hay a ≡ b(mod m)
1.1.4.2. Các tính chất
1) Quan hệ đồng dƣ theo modulo m là một quan hệ tƣơng đƣơng trong Z:
(1) a ≡ a (mod m) với mọi a

Z ( phản xạ) .
(2) Nếu a ≡ b (mod m) thì b ≡ a (mod m) (đối xứng).
(3) Nếu a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m) (bắc cầu).

(mod )
kk
ii
ii
a b m



.
Hệ quả
a) a ≡ b (mod m) → a ± c ≡ b ± c (mod m).
b) a + c ≡ b (mod m) → a ≡ b - c (mod m).
c) a ≡ b (mod m) → a+km ≡ b (mod m) với mọi k

Z.
d) a ≡ b (mod m) → ac ≡ bc (mod m) với mọi c

Z.
e) a ≡ b (mod m) → a
n
≡ b
n
(mod m) với mọi n

Z
+
.

f) c\a, c\b, (c,m)=1, a ≡ b (mod m) → a/c ≡ b/c (mod m).
g) a ≡ b (mod m), c > 0 → ac ≡ bc (mod mc) và

m
một số đồng
dƣ với mình theo modulo m [3, 33].
1.1.4.4. Các định lý
1) Định lý 1.1.4 (Định lý Ferma)
Nếu p là số nguyên tố, a là số nguyên thì a
p

≡ a (mod p). Nếu p không
chia hết a thì a
p-1
≡ 1 (mod p).
Ví dụ: 4
7
≡ 4 (mod 7); 4
7-1
≡ 1 (mod 7).
2) Định lý 1.1.5 (Định lý Euler)
Nếu gcd(a, m) = 1 thì a

(m)

≡ 1 (mod m). Trƣờng họp m là số nguyên
tố ta có định lý Ferma.
Ví dụ
Cho m = 10,

(m) =

(2).

bậc cao một cách đáng kể. Ví dụ muốn tính 2
1004
(mod 15):
Ta thấy

(15) =

(5).

(3) = 4.2 = 8 và 1004 ≡ 4 (mod 8), do đó:
2
1004
(mod 15) = 2
4
(mod 15) = 16 (mod 15) = 1.
Hệ quả 2: Nếu e, d là các các số nguyên thỏa mãn e.d ≡ 1 (mod

(m)) thì với
mọi số c nguyên tố cùng nhau với m ta có (c
e
)
d
≡ c (mod m).
Nhận xét: Với a = ed và b = 1, từ hệ quả 1 ta có hệ quả 2. Hệ quả này đóng
vai trò then chốt trong việc thiết lập các hệ mã mũ sau này (nhƣ RSA).
1.1.4.5. Tính toán đồng dư của các lũy thừa bậc lớn
Hệ quả 1 áp dụng hiệu quả trong trƣờng hợp a lớn hơn hẳn

(m) vì chỉ
khi ấy b mới thực sự nhỏ hơn a. Trong thực tế tính toán ta thƣờng gặp m lớn

2
(mod 103) = 63
87
16
(mod 103) = 63
2
(mod 103) = 55
87
32
(mod 103) = 55
2
(mod 103) = 38 17
Tổng hợp lại, căn cứ theo khai triển (*) ta lấy tích của các lũy thừa bậc 2
5
, 2
3
,
2
1
, 2
0
(rút gọn theo modulo 130) sẽ thu đƣợc kết quả là:
87
43
(mod 103) = 38.63.50.87 (mod 103) = 85.
Định lý 1.1.6 (Định lý Trung Quốc về số dư)
Cho tập số nguyên tố cùng nhau từng đôi một m

3
…m
r
b
1
+ m
1
a
2
m
3
…m
r
b
2
+ m
1
m
2
a
3
m
3
…m
r
b
3
+ … +
m
1

i
), với mọi i = 1, 2,…, r.
Nhận xét
Định lý số dƣ Trung Quốc cho phép ta tính toán đồng dƣ theo modulo
của một số lớn (tích của nhiều số nguyên tố cùng nhau) thông qua tính toán
đồng dƣ theo modulo các số nhỏ (từng thừa số).
Ví dụ: Tìm nghiệm của hệ phƣơng trình

3118(mod 5353)
139(mod 391)
239(mod 247)
x
x
x









Vì các số 5353, 391, 247 nguyên tố cùng nhau nên theo định lý Trung Quốc
về số dƣ hệ có nghiệm duy nhất theo modulo m = 5353.391.247 = 516976681.
Để tìm x mod m ta tính:
m
1
= m/5353 = 96577 → y
1

ta ký hiệu: a
n
= a.a….a.a (n phần tử a).
3) Phần tử đơn vị
- Phần tử e đƣợc gọi là phần tử đơn vị trái của phép toán hai ngôi (.) nếu
e.a = a với mọi a

A.
- Phần tử e đƣợc gọi là phần tử đơn vị phải của phép toán hai ngôi (.) nếu
a.e = a với mọi a

A.
- Phần tử e đƣợc gọi là phần tử đơn vị (trung lập) của phép toán hai ngôi (.)
nếu vùa là đơn vị trái vừa là đơn vị phải.
- Phần tử a’ gọi là phần tử đối (hay nghịch đảo) của a nếu: a’.a = a.a’ = e,
trong đó e là phần tử đơn vị, ký hiệu a’ là a
-1
. Nếu a’ là nghịch đảo của a thì
a là nghịch đảo của a’. Ta có (a.b)
-1
= b
-1
.a
-1
.

1.1.5.2. Nhóm
1) Định nghĩa 1.1.5
Nhóm: Nhóm là một tập hợp G cùng với phép toán hai ngôi (.) thỏa mãn
các điều kiện sau [33]:

Tính chất: (a) Nếu a.b = a.c, thì b = c.
(b) Nếu a.c = b.c, thì a = b.
Bậc của phần tử: cho a

G, nếu có một số nguyên dƣơng n sao cho a
n
=
e thì ta nói a có bậc hữu hạn, số nguyên dƣơng n nhỏ nhất nhƣ vậy gọi là
bậc của a, ký hiệu o(a). Nếu không tồn tại n sao cho a
n
= e ta nói a có bậc
vô hạn.
2) Ví dụ:
(1) Tập số nguyên Z cùng với phép cộng (+) thông thƣờng là một nhóm
giáo hoán, có phần tử đơn vị là số 0, gọi là nhóm cộng các số nguyên.
(2) Tập Q
*
các số hữu tỷ khác 0 (hoặc R
*
tập các số thực khác 0), cùng với
phép nhân (.) thông thƣờng là một nhóm giao hoán, gọi là nhóm nhân
các số hữu tỷ (số thực) khác 0.
1.1.5.3. Nhóm con
1) Bộ phận ổn định: Một bộ phận B của tập A gọi là ổn định đối với phép
toán hai ngôi (.) trong A nếu a.b

B với mọi a, b

B. Phép toán (.) của A
áp dụng trên các phần tử của B gọi là phép toán cảm sinh của A trên B.

-1


H.
(c) Với mọi a, b

H thì ab
-1


H.
4) Ví dụ: Bộ phận mZ gồm các số nguyên là bội của một số nguyên m là một
nhóm con của nhóm cộng các số nguyên Z: Thật vậy áp dụng hệ quả (c),
mZ là nhóm con vì: ma, mb

mZ → ma-mb = m(a-b)

mZ .
1.1.5.4. Nhóm Cyclic
1) Định nghĩa 1.1.7
Cho một nhóm G và một phần tử nào đó thuộc G. Tập hợp:
<a> = {x

G \ x = a
n
với n

Z}
đƣợc gọi là nhóm con cyclic đƣợc sinh bởi a.
Nhóm G đƣợc gọi là nhóm Cyclic nếu có một phần tử a

5) Định lý 1.1.10: Cho a là một phần tử của nhóm G
(1) Nếu a có bậc vô hạn và a
k
= a
m
với k, m

Z thì k = m.
(2) Nếu a có bậc hữu hạn và k

Z thì: a
k
= e ↔ o(a) \ k.
(3) Nếu a có bậc hữu hạn o(a) = n thì với các số nguyên k, m ta có:
a
k
= a
m
↔ k ≡ m (mod n)

và
<a> = O(a)
.

6) Định lý 1.1.11 (Lagrange): Nếu H là nhóm con của nhóm hữu hạn G thì
bậc của H là ƣớc của bậc của G.
Hệ quả 1: Cho G là nhóm hữu hạn có bậc n, với mọi a

G ta có
(a) o(a) \ n.

*

Z
n
= {0, 1, 2, …, n-1} là tập hợp các lớp đồng dƣ theo modulo n cùng
với phép phép toán cộng (+) : [a]
n

+ [b]
n
= [a+b]
n
lập thành một nhóm. Nhóm
cộng Z
n
có n phần tử và phần tử đơn vị là [0]
n
.
Z
n
*
= {a

Z
n
: gcd(a, n) = 1} cùng với phép nhân (.): [a]
n
.
[b]
n


Z
n
sao cho ab 1 (mod n) thì ta nói b là
phần tử nghịch đảo của a trong

Z
n
, ký hiệu là a
-1
, a gọi là phần tử khả nghịch.
Định lý 1.1.12
Phần tử a

Z
n
có nghịch đảo khi và chỉ khi (a,n) = 1.
Nhận xét
Mọi phần tử trong Z
n
*
đều có nghịch đảo. Để tìm phần tử nghịch đảo ta
có thể dùng thuật toán Euclid mở rộng.
Chứng minh
Nếu aa
-1
≡ 1 (mod n) thì aa
-1
= 1+kn ↔ aa
-1

<> 0 do
begin
y := g
i-1
div g
i
; g
i+1
:= g
i+1
-y.g
i
;
u
i+1
:= u
i+1
-y.u
i
; v
i+1
:= v
i+1
-y.v
i
;
i := i+1;
end;
x := v
i+1

2
1
1
-2
3
3
0

Vì v = 2 = -2 < 0 do đó x = -2+7 = 5.
Ta có 5 là phần tử nghịch đảo nhân của 3 trong Z
7
. 24
1.2. LÝ THUYẾT ĐỘ PHỨC TẠP TÍNH TOÁN
1.2.1. Thuật toán của một bài toán
1.2.1.1. Bài toán
Bài toán đƣợc cấu tạo bởi hai phần:
▪ Input : Các dữ liệu vào của bài toán.
▪ Output: Các dữ liệu ra (kết quả).
Không mất tính chất tổng quát ngƣời ta giả thiết các dữ liệu đều là số nguyên.
1.2.1.2. Định nghĩa thuật toán
Định nghĩa 1.2.1
▪ Bằng trực quan: Thuật toán của một bài toán đƣợc hiểu là một dãy hữu hạn
các qui tắc (chỉ thị, mệnh lệnh) mô tả một quá trình tính toán để từ Input ta
đƣợc Output của bài toán [7].