Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
1
LỜI NÓI ĐẦU
Trong xu hướng phát triển của thế giới và Việt Nam hiện nay, mạng Internet đang
đem đến sự bùng nổ thông tin một cách mạnh mẽ. Nó được sử dụng để truyền thư điện
tử, truy cập các website, kết nối các công sở, liên lạc với các khách hàng và sử dụng
các dịch vụ ngân hàng, các giao dịch điện tử…
Tiềm năng của mạng Internet là rất lớn. Như ta đã biết các giao tiếp, trao đổi thông
tin qua Internet đều sử dụng giao thức TCP/IP. Các gói tin truyền từ điểm nguồn tới
điểm đích sẽ đi qua rất nhiều máy tính trung gian, vì vậy độ an toàn thấp, nó rất dễ bị
xâm phạm, theo dõi và giả mạo trên đường truyền. Vấn đề không an toàn cho thông tin
trên đường truyền khiến nhiều người đắn đo trong việc sử dụng mạng Internet cho
những ứng dụng về tài chính, giao dịch ngân hàng, hoạt động mua bán và khi truyền
các thông tin kinh tế, chính trị vv…
Những biện pháp đảm bảo an toàn thông tin đưa ra đều nhằm đáp ứng 3 yêu cầu:
bảo mật thông tin, xác thực thông tin và toàn vẹn thông tin trên đường truyền. Các
hệ mã hóa thông tin bảo đảm tính bí mật nội dung thông tin, các sơ đồ chữ ký số bảo
đảm xác thực thông tin trên đường truyền.
Tuy nhiên, nhu cầu của con người không chỉ dừng lại ở việc giao dịch giữa các cá
nhân với nhau, mà còn giao dịch thông qua mạng giữa các nhóm người, các công ty,
các tổ chức khác nhau trên thế giới. Dựa trên những yêu cầu thực tế đó các nhà khoa
học đã nghiên cứu và đề xuất ra một kiểu chữ ký mới, đó chính là chữ ký nhóm.
Trong đồ án này tôi đã tìm hiểu và nghiên cứu về chữ ký nhóm. Đây là một loại
chữ ký điện tử cho phép một nhóm người tạo các chữ ký đại diện cho nhóm, và chỉ
những thành viên trong nhóm mới có thể ký vào các thông điệp của nhóm. Người quản
trị của nhóm có trách nhiệm thành lập nhóm và trong trường hợp cần thiết phải biết
được ai là người ký vào thông điệp.
Trong quá trình làm đồ án tốt nghiệp, em đã nhận được sự hướng dẫn tận tình của
TS.Lê Phê Đô. Em xin chân thành cảm ơn! Đồng thời, em xin cảm ơn các thày cô giáo
bộ môn Tin học – trường Đại học Dân lập Hải Phòng đã trang bị cho em những kiến
thức cơ bản trong quá trình học tập tại trường.
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
2
Chương I
CÁC KHÁI NIỆM CƠ BẢN
1.1 Cơ sở toán học
1.1.1. Ước số - Bội số
Định nghĩa : Ước số của a và b là c nếu c|a và c|b
Ước số chung lớn nhất : Là số lớn nhất mà a và b chia hết
Ký hiệu : c = gcd (a,b) ; (great common divisor)
Bội số chung nhỏ nhất : d là BCNN của a và b nếu
∀
c mà a|c , b|c → d|c
Ký hiệu : d = lcm (a,b) ; (least common multiple)
Tính chất: lcm (a,b) = a.b/gcd(a,b)
1.1.2. Số nguyên tố
Định nghĩa : Số nguyên tố là số chỉ chia hết cho 1 và chính nó, ngoài ra không còn
số nào nó có thể chia hết nữa. Hệ mật thường sử dụng số nguyên tố lớn cỡ 512bits và
thậm chí còn lớn hơn nữa.
Hai số m và n gọi là hai số nguyên tố cùng nhau khi ước số chung lớn nhất của
chúng bằng 1. Chúng ta có thể viết như sau:
UCLN(m,n) = 1
1.1.3. Khái niệm nhóm
Định nghĩa : Nhóm là bộ đôi (G,
∗
), trong đó G là tập
φ
≠
và ∗ là một phép toán
hai ngôi trong G thỏa mãn ba tiên đề sau
1. Phép toán nhóm kết hợp
a * (b * c) = (a * b) * c
∀
a, b, c
∈
G
2. Có một phần tử 0
∈
G được gọi là phần tử đơn vị thỏa mãn
a * 0 = 0 * a
∀
a
∈
G
3. Với mỗi a ∈G, tồn tại một phần tử a-1
∈
G được gọi là nghịch đảo
a * a-1 = a-1 * a = 0
Nhóm được gọi là giao hoán (hay nhóm Abel) nếu
a * b = b * a
∀
a, b
∈
G
1.1.4. Nhóm hữu hạn
Định nghĩa : Nhóm (G, ∗) hữu hạn nếu |G| là hữu hạn. Số các phần tử của nhóm G
được gọi là cấp của nhóm.
Ví dụ :
Tập các số nguyên Z với phép cộng sẽ tạo nên một nhóm. Phần tử đơn vị
của nhóm này được kí hiệu là 0, phần tử ngược của một số nguyên a là
số nguyên –a.
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
3
Tập Zn với phép cộng modulo tạo nên một nhóm cấp n. Tập Zn với phép
toán nhân theo modulo n không phải là một nhóm vì không phải mọi
phần tử của nhóm đều có nghịch đảo. Tuy nhiên tập Z*
n sẽ là một nhóm
cấp
φ
(n) với phép toán nhân theo modulo n và có phần tử đơn vị là 1.
1.1.5. Nhóm con
Định nghĩa : Bộ đôi (S, ∗) được gọi là nhóm con của (G,
) nếu:
S ⊂ G, phần tử trung gían e ∈ S
x, y ∈ S ⇒ x * y ∈ S
1.1.6. Nhóm Cyclic
Định nghĩa : Nhóm G được gọi là nhóm cyclic nếu tồn tại một phần tử α ∈ G sao
cho với mỗi b ∈G có một số nguyên I sao cho b = αi. Phần tử α như vậy được gọi là
phần tử sinh của G
Nếu G là một nhóm và a ∈ G thì tập tất cả các lũy thừa của a sẽ tạo nên một nhóm
con cyclic của G. Nhóm này được gọi là nhóm con sinh bởi a và được kí hiệu là a
1.1.7. Các thuật toán trong Z
Cho a và b là các số nguyên không âm và nhỏ hơn hoặc bằng n. Cần chú ý rằng số
các bit trong biểu diễn nhị phân của n là [lgn] + 1 và số này xấp xỉ bằng lg n. Số các
phép toán bit đối với bốn phép toán cơ bản trên các số là cộng , trừ, nhân và chia sử
dụng các thuật toán kinh điển được tóm lược trên bảng sau. Các kỹ thuật tinh tế hơn
đối với các phép toán nhân và chia sẽ có độ phức tạp nhỏ hơn.
Phép toán Độ phức tạp bit
Cộng a + b
Trừ a – b
Nhân a * b
Chia a = qb + r
0(lg a + lg b) = 0 (lg n)
0(lg a + lg b) = 0 (lg n)
0
(
)
b) (lg*a) (lg = 0
(
)
n)2 (lg
0
(
)
b) (lg*a) (lg = 0
(
)
n)2 (lg
1.1.8. Thuật toán Euclide : Tính UCLN của 2 số nguyên
VÀO : Hai số nguyên không âm a và b với a > b
RA : UCLN của a và b
(1). while b ≠ 0 do
R
← a mod b, a ← b, b ← r
(2). Return (a)
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
4
1.1.9. Thuật toán Euclide mở rộng
VÀO : Hai số nguyên không âm a và b với a > b
RA : d = UCLN (a, b) và các số nguyên x và y thỏa mãn ax + by = d
(1) Nếu b = 0 thì đặt d ← a, x ← l, y ← 0 và return (d, x, y)
(2) Đặt x2 ← l, x1 ← 0, y2 ← 0, y1 ← l
(3) while b > 0 do
1. q ← [a/b], r ← a – qb, x ← x2 – qx1 , y ← y2 – qy1
2. a ← b, b ← r, x2 ← x1, x1 ← x, y2 ← y1 , y1 ← y
(4) Đặt d ← a, x ← x2, y ← y2 và return (d, x, y)
1.1.10. Định nghĩa hàm Φ Euler
Định nghĩa : Với n≥1 chúng ta gọi
φ
(n) là tập các số nguyên tố cùng nhau với n
nằm trong khoảng [1,n].
Tính chất :
Nếu p là số nguyên tố →
φ
(p) = p-1
Nếu p=m.n , gcd(m,n)=1
→
φ
(p)=
φ
(m).
φ
(n)
Nếu n = k
e
k
eee pppp ....
3
21 321 là thừa số nguyên tố của n thì
→
φ
(n) = n ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛−
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛−
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛−
k
ppp
1
1...
1
1
1
1
21
1.1.11. Đồng dư thức
Định nghĩa : Cho a và b là hai số nguyên tố, a được gọi là đồng dư với b theo
modulo n, ký hiệu là a ≡ b(mod n) nếu a, b chia cho n có cùng số dư.
Ví dụ : 24 ≡ 9 mod 5 vì 24 - 9 = 3 * 5
-11
≡ 17 mod 7 vì -11 - 17 = -4 * 7
Tính chất :
Đối với a, a1, b, b1, c ∈ Z ta có :
a ≡ a (mod n)
a ≡ b (mod n) ↔ b ≡ a (mod n)
a ≡ b (mod n) , b ≡ c (mod n) → a ≡ c (mod n)
a ≡ a1 (mod n) , b ≡ b1 (mod n)
a+b≡ a1+b1 (mod n)
a.b ≡ a1.b1 (mod n)
1.1.12. Số nghịch đảo
Định nghĩa : Cho a ∈ Zn. Một số nguyên x ∈ Zn gọi là nghịch đảo của a theo mod n
nếu a.x ≡ 1mod n..
Nếu có số x như vậy thì nó là duy nhất và ta nói a là khả nghịch. Ký hiệu là a-1. Có
thể suy ra rằng a khả nghịch theo mod n khi và chỉ khi gcd (a,n)=1.
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
5
1.1.13. Nhóm nhân Z*n
Định nghĩa : Nhóm nhân của Zn ký hiệu là Z*n là tập hợp các phần tử sao cho gcd
(a,n)=1. Đặc biệt với n là số nguyên tố thì Z*n={ a ∈ Zn | 1≤a≤n-1}
Định nghĩa : Cho a ∈ Z*n khi đó bậc của a kí hiệu là ord (a) là một số nguyên
dương t nhỏ nhất sao cho a t
≡
1(mod n).
1.1.14. Định nghĩa thặng dư bậc 2
Định nghĩa : Cho a ∈ Z*n gọi a là thặng dư bậc 2 theo modulo n nếu tồn tại x sao
cho x2 ≡ a (mod n) . Nếu không tồn tại thì gọi a là bất thặng dư bậc 2. Tập tất cả các
thặng dư bậc hai modulo n được kí hiệu là n
Q , còn tập tất cả các thặng dư không bậc
hai được kí hiệu là n
Q.
1.1.15. Phần dư China CRT ( Chinese Remainder Theorem)
Nếu các số nguyên n1, n2, …, nk là nguyên tố cùng nhau từng thì hệ các phương
trình đồng dư:
x ≡ a1 (mod n1)
x ≡ a2 (mod n2)
………………
x ≡ ak (mod nk)
sẽ có nghiệm duy nhất theo modulo n (n = n1, n2, …, nk)
x =
∑
=
k
i1
ai Ni Mi mod n
Trong đó Ni = n / ni và Mi = N 1−
i mod ni
Các tính toán này có thể được thực hiện bởi 0
(
)
)2n (lg các phép toán trên bit.
Ví dụ : Cặp phương trình đồng dư
x ≡ 5 (mod 9)
x ≡ 19 (mod 23) có nghiệm duy nhất x ≡ 203 (mod 207)
Tính chất
Nếu (n1, n2) = 1 thì cặp phương trình đồng dư
x ≡ a (mod n1), x ≡ a (mod n2)
có một nghiệm duy nhất x ≡ a (mod n1, n2)
1.1.16. Độ phức tạp tính toán
Lý thuyết thuật toán và các hàm số tính được ra đời từ những năm 30 của thế kỉ 20
đã đặt nền móng cho việc nghiên cứu các vấn đề “ tính được ”, “ giải được ” trong toán
học. Tuy nhiên từ các “ tính được ” đến việc tính toán thực tế là một khoảng cách rất
lớn. Có rất nhiều vấn đề chứng minh là có thể tính được nhưng không tính được trong
thực tế dù có sự trợ giúp của máy tính. Vào những năm 1960 lý thuyết độ phức tạp