Tiểu luận An toàn thông tin – Các phương pháp ký số
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC DUY TÂN
KHOA SAU ĐẠI HỌC
TIỂU LUẬN
MÔN AN TOÀN THÔNG TIN
ĐỀ TÀI: CÁC PHƯƠNG PHÁP KÝ SỐ
GVHD : PGS.TS.Trịnh Nhật Tiến.
Học viên : Huỳnh Thị Phương Uyển.
Lớp : K7MCS.
Đà Nẵng, tháng 5 năm 2013
1
Tiểu luận An toàn thông tin – Các phương pháp ký số
LỜI MỞ ĐẦU
Ngày nay, với sự bùng nổ của mạng Internet, mạng máy tính đang ngày càng đóng
vai trò thiết yếu trong mọi lĩnh vực hoạt động của toàn xã hội, và khi nó trở thành
phương tiện điều hành các hệ thống thì nhu cầu bảo mật thông tin được đặt lên hàng
đầu.
Vấn đề an toàn thông tin (ATTT) trong các giao dịch, trao đổi thông tin luôn là
một yêu cầu cần phải có đối với mọi hoạt động trao đổi dữ liệu, đặc biệt là hoạt động
thương mại điện tử vì các quy trình giao dịch được thực hiện qua Internet - một
môi trường truyền thông công cộng.
Ngày càng có nhiều cá nhân và tổ chức sử dụng các tài liệu số thay cho tài liệu
giấy để thực hiện các giao dịch hàng này. Bằng cách giảm sự lệ thuộc vào tài liệu giấy,
chúng ta đang bảo vệ môi trường và tiết kiệm nguồn tài nguyên cho trái đất. Chữ ký số
hỗ trợ cho sự thay đổi này bằng cách cung cấp sự đảm bảo về tính hiệu lực và tính xác
thực của các tài liệu số. Việc sử dụng chữ ký số là một giải pháp hữu hiệu, ngày càng
được ứng dụng nhiều trong thực tế, áp dụng nhiều trong những lĩnh vực khác như ngân
hàng, viễn thông…. Đây cũng chính là lý do tôi chon đề tài “Các phương pháp ký số”
làm bài tiểu luận cho mình.
Trong thời gian hoàn thành bài tiểu luận tôi đã nhận được sự hướng dẫn tận tình

- Người nhận văn bản kiểm tra chữ ký bằng việc sử dụng chìa khóa công khai của
người gửi để giải mã văn bản.
1.2 Khái niệm về chữ ký số
1.2.1 Khái niệm
Chữ ký số là mô hình sử dụng các kỹ thuật mật mã để gắn với mỗi người sử dụng
một cặp khóa công khai - bí mật và qua đó có thể ký các văn bản điện tử cũng như trao
đổi các thông tin mật. Khóa công khai thường được phân phối thông qua chứng thực
khóa công khai. Quá trình sử dụng chữ ký số bao gồm 2 quá trình: tạo chữ ký và kiểm
tra chữ ký.
Các thuật toán chữ ký số cho phép xác định nguồn gốc, bảo đảm tính toàn vẹn của dữ
liệu được truyền đi, đồng thời nó cũng bảo đảm tính không thể phủ nhận của thực thế đã
ký thông tin.
1.2.2 Sơ đồ chữ ký số
Sơ đồ chữ ký số là bộ năm (P, A, K, S, V ), trong đó:
P là tập hữu hạn các văn bản có thể.
A là tập hữu hạn các chữ ký có thể.
K là tập hữu hạn các khoá có thể.
S là tập các thuật toán ký.
V là tập các thuật toán kiểm thử.
Với mỗi k ∈ K, có thuật toán ký Sig
k
∈ S, Sig
k
: P  A, và thuật toán kiểm thử
Ver
k
∈ V, Ver
k
: P x K  {đúng, sai}, thoả mãn điều kiện sau với mọi x ∈ P, y ∈ A:
Đúng, nếu y = Sig

phục lại được thông điệp, đã được “ký” bởi “chữ ký” này.
Ví dụ: Chữ ký RSA là chữ ký khôi phục thông điệp, sẽ trình bày trong mục 3.
5
Tiểu luận An toàn thông tin – Các phương pháp ký số
2.1.2 Chữ ký không thể khôi phục được thông điệp
Là loại chữ ký, trong đó người gửi cần gửi “chữ ký” và phải gửi kèm cả thông điệp
đã được “ký” bởi “chữ ký” này. Ngược lại, người nhận sẽ không có được thông điệp
gốc.
Ví dụ: Chữ ký Elgamal là chữ ký đi kèm thông điệp
2.2 Phân loại chữ ký theo mức an toàn
2.2.1 Chữ ký “không thể phủ nhận”
Nhằm tránh việc nhân bản chữ ký để sử dụng nhiều lần, tốt nhất là người
gửi tham gia trực tiếp vào việc kiểm thử chữ ký. Điều đó được thực hiện bằng một
giao thức kiểm thử, dưới dạng một giao thức mời hỏi và trả lời.
Ví dụ: Chữ ký không thể phủ định Chaum - van Antwerpen
2.2.2 Chữ ký “một lần”
Để bảo đảm an toàn, “Khóa ký” chỉ dùng 1 lần (one- time) trên 1 tài liệu.
Ví dụ: Chữ ký Lamport, chữ ký Fail - Stop (Van Heyst & Pedersen).
2.3 Phân loại chữ ký theo ứng dụng đặc trưng.
Chữ ký “mù” ( Blind Signature)
Chữ ký “nhóm” ( Group Signature)
Chữ ký “bội” ( Multy Signature)
Chữ ký “mù nhóm” ( Blind Group Signature)
Chữ ký “mù bội” ( Blind Multy Signature)
3 CHỮ KÝ RSA
3.1 Sơ đồ chữ ký RSA
Sơ đồ
- Tạo cặp khóa (bí mật, công khai) (a, b) :
6
Tiểu luận An toàn thông tin – Các phương pháp ký số

+ Chọn khóa công khai b là nguyên tố với φ(n), tức là ƯCLN(b, φ(n)) = 1,
ví dụ chọn b = 3.
+ Khóa bí mật a là phần tử nghịch đảo của b theo mod φ(n): a*b ≡ 1 (mod φ(n)).
Từ a*b ≡ 1 (mod φ(n)), ta nhận được khóa bí mật a = 3.
- Ký số
x = 2 ∈ P
y = Sig
k
(x) = x
a
( mod n) = 2
3
( mod 15) = 8
7
Tiểu luận An toàn thông tin – Các phương pháp ký số
- Kiểm tra chữ Ký.
Ver
k
(x,y) = đúng  x = y
b
( mod n)  2 = 8
3
( mod 15)
Như vậy, việc ký là mã hóa, việc kiểm tra lại chính là việc giãi mã.
Việc ‘ký số’ vào x tương ứng với việc ‘mã hõa’ tài liệu x
Việc kiểm tra chữ ký chính là việc giãi mã ‘chữ ký’, để kiểm tra xem tài liệu đã
giãi mã có đúng tài liệu trước khi ký không.
3.3 Độ an toàn chữ ký RSA
1). Chữ ký RSA là tất định, tức là với một bản rõ x và một khóa bí mật a, thì chỉ
có một bản mã y.

)(mod
2/1
Nms ←
.
ở đây chúng ta thấy để tạo nên chữ ký s thì m phải thuộc QR
N
. Alice có thể chọn cơ chế
thích hợp để tạo nên m. Chú ý có đến ¼ số phần tử của nhóm
*
N
Z
thuộc về QR
N
nên
Alice hình thành m là không khó.
4.3 Thẩm tra chữ ký
Để thẩm tra chữ ký Bob xem thủ tục sau:
Verify
(N)
(m,s)=TRUE, nếu như
)(mod
2
Nsm ≡
.
Sơ đồ chữ ký Rabin có nhưng ưu điểm hơn so với sơ đồ RSA. Thứ nhất là giả mạo
chữ ký là phức tạp như là phân tích số nguyên ra thừa số nguyên tố. Thứ hai là việc
thẩm tra chữ ký hoàn thành nhanh hơn và hòan toàn thuận lợi thực thi các ứng dụng.
5 CHỮ KÝ ELGAMAL
Sơ đồ chữ ký Elgamal được giới thiệu năm 1985. Sơ đồ này thiết kế dành riêng cho
chữ ký số khác với sơ đồ RSA dành chung cho cả hệ thống mã công khai và chữ ký số.

k
thỏa mãn
1−< pk
và
UCLN(k,p-1)=1 và hình thành nên chữ ký là cặp (r,s), ở đây
).1)(mod(
),(mod
1
−−←
←
−
prxmks
pr
A
k
α
5.1.3 Kiểm tra chữ ký
Để thẩm tra chữ ký (r,s) Bob xem kết quả của hàm kiểm tra:
Verify
(
α
,yA,p)
(m,(r,s))=TRUE, nếu như r < p và
)(mod pry
msr
A
α
≡
.
Chúng ta xem sự đúng đắn của phương trình thẩm tra chữ ký:

α
=
=21
27
mod 467=132
Alice muốn ký lên bức điện m=100, thì Alice chọn số ngẫu nhiên k, ví dụ Alice chọn
k=213 (UCLN(213,467)=1) và tính 213
-1
(mod 466)=431. Khi đó:
r=2
213
mod 467=29
s=431(100-127.29) mod 466=51
Bob hay bất kỳ ai cũng có thể thẩm tra được chữ ký này bằng cách:
)467(mod1892
)467(mod18929132
100
5129
≡
≡
Vậy chữ ký là hợp lệ.
10
Tiểu luận An toàn thông tin – Các phương pháp ký số
5.3 Đánh giá độ an toàn của sơ đồ chữ ký Elgamal
Cánh báo 1.
Đầu tiên để kiểm tra chữ ký thì cần phải kiểm tra bất đẳng thức r < p. Nếu như r > p
thì có khả năng bị tấn công, cách này đề xuất bởi Bleichenbacher. Giả sử (r,s) là chữ ký
của bức điện m. Tội phạm có thể giã mạo chữ ký với một bức điện bất kỳ m’ bằng cách
hình thành như sau:
1.

≡≡≡=
Tấn công kiểu như thế này là không thể nếu như r < p, bởi vì trong trường hợp này
giá trị r’ được tính toán theo bước 3 ứng dụng định lý phần dư Trung Hoa theo modulo
p(p-1).
Cảnh báo 2.
Cảnh báo này cũng hình thành bởi Bleichenbacher. Alice cần phải lựa chọn phần tử
ngẫu nhiên
α
từ nhóm
*
p
Z
. Nếu như tham số này không được lựa chọn bởi Alice (điều
này là có thể, khi hệ thống người sử dụng có một tham số mở
α
và p), thì cần phải kiểm
tra một số lần rằng
α
là số ngẫu nhiên (điều này có thể áp dụng hàm tạo số giả ngẫu
nhiên).
Giả sử rằng các tham số mở
α
và p được lựa chọn bởi tội phạm Oscar. Tham số p
hình thành trên cơ sở phương pháp chuẩn: Giả sử p-1=bq, với q là số nguyên tố đủ lớn,
11
Tiểu luận An toàn thông tin – Các phương pháp ký số
nhưng b có thể có thừa số nguyên tố nhỏ, và tính toán logarithm trong nhóm bậc b
không khó).
Oscar hình thành tham số
α

A
α
=
Khi tính được giá trị z thì Oscar có thể giả mạo chữ ký của Alice bằng các lệnh sau
đây:
).1)(mod(
,
−−←
=←
pcqzmts
cqr
β
Chúng ta xem việc thẩm tra chữ ký:
)(mod)(
)(
pyry
mcqzmcqzcqzmtcq
A
sr
A
αααβ
≡≡≡
−−
Rõ ràng chúng ta thấy cặp (r,s) là chữ ký của bức điện m, nhưng việc tạo thành chữ
ký này không có sự tham gia của khóa mật x
A
(mà có sự tham gia của số x
A
(mod b)).
Chú ý rằng trong quá trình hình thành chữ ký giả mạo thì số q là ước số của r. Dẫn

pl
tồn tại, và từ bất đẳng thức
)1(mod
21
−≠ pmm
dẫn đến:
)1)(mod/()(
2121
1
−−−≡
−
pmmssl
,
Có nghĩa
1−
l
bị lộ. Nhưng quan trọng nhất là khóa mật Alice x
A
có thể tính toán từ
công thức hình thành s, và suy ra x
A
theo công thức:
)1(mod/)(
11
−−≡ prlsmx
A
.
Điều này cho chúng ta thấy chỉ được sử dụng tham số k một lần duy nhất.
6 HỌ CHỮ KÝ ELGAMAL
Sau khi đăng sơ đồ chữ ký Elgamal, thì sau đó một số cải tiến của sơ đồ này xuất

khi
1≠g
).
3 Lựa chọn hàm hash H:
{ }
q
Z
*
1,0
(Ví dụ có thể chọn SHA-1).
Các tham số (p,q,g,H) sẽ phân bố giữa các người dùng hệ thống.
Hình thành khóa mật và khóa công cộng:
Alice tạo ra số ngẫu nhiên
*
p
Zx ∈
và thực hiện lệnh:
)(mod pgy
x−
←
.
Các tham số công cộng là (p,q,g,y,H) còn x là khóa mật.
Tạo chữ ký:
Để ký lên bức điện
{ }
*
1,0∈m
, thì Alice tạo ra số ngẫu nhiên
q
Zl

được tạo ra bởi Alice. Nghĩa là:
)(mod' prgygyygygr
leleelxees
≡≡≡≡≡
−+
.
Như chúng ta thấy việc ứng dụng nhóm con bậc q của nhóm
p
Z
cho phép quá trình
ký của sơ đồ Schonorr nhanh hơn nhiều so với sơ đồ Elgamal: Để chuyển chữ ký của
Schonorr cần 2|q| bít, trong khi đó để chuyển chữ ký Elgamal cần 2|p| bít. Chữ ký ngắn
hơn rất nhiều cho phép giảm số lệnh cần thiết để hình thành chữ ký và thẩm định chữ
ký: trong sơ đồ Schonorr tốn O(
)loglog
2
2
pq
, còn trong sơ đồ Elgamal cần O(
p
3
log
).
6.2 Sơ đồ chữ ký DSS
Đây cũng là phiên bản cải tiến của Elgamal. Nó được để xuất năm 1991, tuy nhiên
nó được chấp nhận làm chuẩn từ 01/12/1994. Giống như sơ đồ chữ ký Schnorr, chuẩn
chữ ký DSS cũng có những ưu điểm so với Elgamal.
Sơ đồ chữ ký được miêu tả như sau:
Thiết lập tham số hệ thống:
Các tham số hệ thống giống như sơ đồ chữ ký Schnorr. Và chuẩn DSS chọn hàm

←
−
Thẩm tra chữ ký
Để thẩm tra chữ ký, Bob dùng cặp (m,(r,s)) cho tính toán sau
),(mod
),(mod)(
),(mod
2
1
1
qrwu
qwmHu
qsw
←
←
←
−
Verify(p,q,g,y,h)(m,(r,s))=TRUE, nếu như
)))(mod(mod(
21
qpygr
uu
=
.
Chúng ta xem việc kiểm tra chữ ký là hợp lý:
Đặt
))](mod)(mod[)))(mod(mod(
)(mod)(mod)(
11
21

mod 239 = 136.
γ = (α
k
mod p) mod q = (7098
58
mod 7649)

mod 239 = 593 mod 239 = 115
δ = (x+ a*γ)*k
-1
mod q = (1246+85*115)*

136
-1
mod 239 = 87.
Khi đó(115, 87) là chữ ký đúng đối với văn bản x = 1246, vì:
δ
-1
= 87
-1
mod 239 = 11
e
1
= x* δ
-1
mod q = 1246*11 mod 239 = 83
16
Tiểu luận An toàn thông tin – Các phương pháp ký số
e
2

7.1 Khái niệm
Trong các sơ đồ trước, việc kiểm thử tính đúng đắn của chữ ký là do người nhận
thực hiện. Nhằm tránh việc nhân bản chữ ký để sử dụng nhiều lần, tốt nhất là để người
gởi tham gia trực tiếp vào việc kiểm thử chữ ký. Điều đó được thực hiện bằng một giao
thức kiểm thử, dưới dạng một giao thức mời hỏi và trả lời.
Sơ đồ chữ ký không chối được gồm ba phần: thuật toán ký, giao thức xác minh và
giao thức từ chối.
17
Tiểu luận An toàn thông tin – Các phương pháp ký số
7.2 Sơ đồ chữ ký không thể chối bỏ Chaum – Van Antwerpen
Sơ đồ chữ ký không chối được do Chaum- Antwerpen đưa ra năm 1989. Chúng ta sẽ
thấy một điểm yếu của chữ ký là hiện tượng nhân bản chữ ký của Alice, và phân phối
chữ ký này bằng phương pháp điện tử mà không hề có sự đồng ý của Alice. Để tránh
trường hợp này thì chúng ta dùng giao thức “hỏi và trả lời”, tức là có sự tham gia của
Alice để xác minh chữ ký. Nhưng có trường hợp xảy ra là Alice có thể tuyên bố chữ ký
hợp lệ là giả mạo và từ chối xác minh nó hoặc thực hiện giao thức theo cách để chữ ký
không thể xác minh được. Để ngăn chặn tình huống này xãy ra, sơ đồ chữ ký không
chối được đã kết hợp với giao thức từ chối, theo giao thức này, Alice có thể chứng mình
với mọi người là chữ ký là giả mạo, điều này đồng nghĩa với việc nếu Alice không nhận
tham gia vào giao thức từ chối, là bằng chứng chứng tỏ chữ ký trên là thật.
Chuẩn bị các tham số
+ Chọn số nguyên tố p sao cho bài toán logarit rời rạc trong là khó giải, đồng thời
thỏa mãn điều kiện p = 2 * q + 1, q cũng là nguyên tố.
+ Chọn g ∈ là phần tử có cấp q.
+ Chọn 1 ≤ a ≤ q – 1, tính h = mod p.
+ G là nhóm con (theo phép nhân) cấp q sinh ra bởi g của
+ Tập hữu hạn các văn bản có thể P, tập hữu hạn các chữ ký có thể A
+ P = A = G
+ Khóa công khai được định nghĩa pk = (p, g, h ), khóa bí mật sk = a.
Thuật toán ký

mod p, tức y là chữ ký đúng đối với x, thì theo giao thức kiểm thử, chắc chắn
N sẽ chấp nhận y là chữ ký đúng đối với x.
Chứng minh :
Giả sử y ≡ x
a
mod p. Khi đó y
a-1
≡ x mod p. (chú ý rằng tất cả các số mũ được
tính theo mod q).
Ta cũng có β
a-1
≡ mod q. Khi đó y
a-1
≡ x mod p. Do đó
19
Tiểu luận An toàn thông tin – Các phương pháp ký số

)(mod
)(mod
)(mod
px
py
pcd
ee
ee
a
21
21
1
α

)(mod))*(()*(
py
py
py
pyd
afe
fefeafe
feafeafe
fe
a
eefe
1
11
1212
1
11
12
1
12
1
11
12
1
2112
−
−
−−
−
≡
≡

, f
2
là để thực hiện giao thức kiểm thử y có là chữ ký
đối với x hay không.
20
Tiểu luận An toàn thông tin – Các phương pháp ký số
7.4 Độ an toàn của chữ ký Chaum – Van Antwerpen
Độ an toàn của hệ thống phụ thuộc vào bài toán logarit rời rạc do khóa bí mật
sk = a được tính từ công thức h = mod p  a = mod p, trong đó g, h, p là công khai.
Đây chính là vấn đề của bài toán logarit rời rạc khó giải.
8 CHỮ KÝ FAIL-STOP
8.1 Khái niệm
Sơ đồ chữ ký Fail-Stop ngăn chặn việc giả mạo khá hữu hiệu. Nếu H giả mạo chữ
ký của G thì G sẽ chứng minh được ngay chữ ký đó là giả mạo.
Sơ đồ này được xây dựng năm 1992 bởi van Heyst và Pedersen. Đây là chữ ký
1 lần (tức một khoá cho trước chỉ ký 1 lần trên 1 văn bản).
Hệ gồm thuật toán ký, thuật toán kiểm thử và chứng minh tính giả mạo.
8.2 Sơ đồ chữ ký Fail-Stop
Giả sử p là số nguyên tố sao cho bài toán log rời rạc trong Z
p
là khó,
p = 2*q+1, và q cũng là số nguyên tố, α ∈ Z
p
*
là một phần tử cấp q.
1 ≤ a
0
≤ q-1 và
β α
α

2
, b
1
, b
2
∈ Z
q

γ
1
= α
a1
*β
a2
mod p
γ
2
= α
b1
*β
b2
mod p
Với x ∈ Z
q
, ta định nghĩa:
Sig
k
(x) = (y
1
, y

α
=
0
mod
p
.
Các giá trị p, q, α, β là công khai, a
0
là bảo mật.
Đặt P = Z
q
và A = Z
q
× Z
q
Khoá có dạng K = (γ
1
, γ
2
, a
1
, a
2
, b
1
, b
2
)
Với a
1

, y
2
)
Với y
1
= a
1
+ x*b
1
mod q
y
2
= a
2
+x*b
2
mod q.
Để kiểm thử ta tính
ver
k
(x, y) = true ⇔
)(mod* p
yy
x
21
21
βαγγ
≡∗
Để chữ ký của G thoả mãn điều kiện kiểm thử, ta trở lại vấn đề bảo mật và cách
làm việc của sơ đồ.

2
= γ
2
’.
Bổ đề:
Giả sử 2 khoá k và k' bằng nhau và ver
k
(x, y) = true khi đó ver
k’
(x, y) = true.
22
Tiểu luận An toàn thông tin – Các phương pháp ký số
Giả sử k = (γ
1
, γ
2
, a
1
, a
2
, b
1
, b
2
) và k’ = (γ
1
’, γ
2
’, a
1

1
+ x*b
1
mod q
y
2
= a
2
+x*b
2
mod q.
Sau đó ta kiểm tra y bằng cách sử dụng khoá k’:
)(mod
)(mod)*(**
)(mod**
''''
''''
p
p
p
x
x
bbaa
baba
21
2121
221121
γγ
βαβα
βαβα

βαγ
=
)(mo d* p
bb
21
2
βαγ
=
y
1
= a
1
+ x*b
1
(mod q)
y
2
= a
2
+ x*b
2
(mod q).
Nếu α là phần tử sinh của P, khi đó tồn tại duy nhất cặp c
1
, c
2
, a
0
sao cho:
)(mod p

≡ b
1
+ a
0
*b
2
(mod q)
y
1
≡ a
1
+ x *b
1
(mod q)
y
2
≡ a
1
+ x *b
2
(mod q)
Ta viết dưới dạng ma trận như sau:














2
1
2
1
2
1
2
1
0
0
010
001
100
001
y
y
c
c
b
b
a
a
x
x
a

(x’).
Phải hiểu rằng 2 hệ quả trên đều nói về tính bảo mật của sơ đồ. Cho y là chữ ký
đúng đối với văn bản x, thì có thể có q khoá ký trên x để được y. Nhưng với mọi x’ ≠ x,
các khoá q này tạo ra q chữ ký khác trên văn bản x’.
TÀI LIỆU THAM KHẢO
24
Tiểu luận An toàn thông tin – Các phương pháp ký số
[1] Phan Đình Diệu. Lý thuyết mật mã và an toàn thông tin – NXB Đại học Quốc
gia Hà Nội - 2006
[2] Trịnh Nhật Tiến. Giáo trình An toàn dữ liệu
[3] Trịnh Nhật Tiến. Chữ ký: mù, nhóm, mù nhóm và ứng dụng. Kỷ yếu HN KH
FAIR lần 2 tại TP Hồ Chí Minh 9/2005
[4]
[5]
[6] />
25