CHỮ KÝ KHÔNG THỂ PHỦ NHẬN
1. Khái niệm chữ ký không thể phủ nhận
Chữ ký số, không giống như chữ ký trên giấy, nó có thể dễ dàng bị sao chép một cách chính
xác. Thuộc tính này có thể có lợi cho những ứng dụng cần sự phổ biến rộng rãi của các thông
báo cùng với khóa công khai, khi mà càng nhiều bản sao chép được phát ra càng tốt. Tuy nhiên,
nó không phù hợp với nhiều ứng dụng khác. Ví dụ ứng dụng chữ ký điện tử thay thế cho ứng
dụng mang tính cá nhân hoặc nhạy cảm như bản cam kết viết tay hoặc bằng miệng. Trong những
trường hợp này, sự phổ biến của bản sao chép có thể làm cho người dùng không hợp lệ thực hiện
các hành vi như tống tiền hoặc gián điệp. Người nhận của những cam kết này có thể chắc chắn
rằng người ký cam kết này sau này không thể chối bỏ nó, nhưng người nhận không thể đưa ra
bản cam kết này cho bất kỳ ai khác khi không có sự đồng thuận của người ký. Chữ ký không thể
chối bỏ phù hợp với các ứng dụng như ở trên. Chữ ký không thể chối bỏ, giống như chữ ký số
thông thường, là một số được đưa ra bởi người ký, phụ thuộc vào khóa bí mật của người ký và
thông điệp cần ký. Tuy nhiên, không giống như chữ ký số thông thường, kiểm tra chữ ký không
thể chối bỏ phải có sự hợp tác của người ký.
Tính hợp lệ của chữ ký không thể chối bỏ có thể được kiểm tra (bởi bất kỳ ai) bằng cách đưa
ra các giá trị hỏi (challenge) cho người ký, và người ký sẽ đưa ra các giá trị đáp lại (response).
Nếu kiểm tra là sai, có hai trường hợp xảy ra: (a) chữ ký là không hợp lệ hoặc (b) người ký cố
tình đưa ra các giá trị đáp sai để cố tình chối bỏ một chữ ký do anh ta ký. Tuy nhiên cho dù
người ký có máy tính với năng lực tính toán vô hạn, người kiểm thử chữ ký có thể phân biệt
được trường hợp (a) và (b) với độ chắc chắn cao bằng giao thức hỏi đáp thứ hai.
1.1. Sơ đồ chữ ký không thể chối bỏ Chaum – Van Antwerpen
Sơ đồ chữ ký không thể chối bỏ được David Chaum và Hans van Antwerpen đề xuất năm
1989. Sơ đồ gồm 3 phần: thuật toán ký, giao thức kiểm thử và giao thức chối bỏ.
1/. 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 Z
p
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 = g

- Bob tính c = mod p và gửi cho Alice.
- Alice tính d = mod p và gửi cho Bob.
- Bob kiểm tra d ≢ mod p
- Bob chọn ngẫu nhiên f
1
, f
2
∈
- Bob tính C = mod p và gửi cho Alice
- Alice tính D = mod p và gửi cho Bob
- Bob kiểm tra D ≢ mod p
- Bob kết luận chữ ký y thực sự là giả mạo nếu:
mod p
1.2. Ví dụ minh họa
Trong ví dụ này, Alice là người ký, Bob là người cần xin chữ ký.
1/. Chuẩn bị các tham số
Alice chuẩn bị các tham số cho việc ký
- Chọn số nguyên tố p = 59747 = 2 * q + 1, q = 29873 cũng là số nguyên tố
- G là nhóm nhân con của cấp q. Chọn phần tử sinh của nhóm G là g = 3.
- Đặt P = A = G, K = {(p, g, a, h ): a ∈ , h ≡ g
a
mod p }
Chọn a = 11, h = 3
11
mod 59747 = 57653
2/. Thuật toán ký
Dùng khóa bí mật sk = a để ký lên x = 229
Chữ ký thu được là y = sig
sk
(x) = x

15
mod 59747 = 19071
- Alice tính d = mod p = mod 59747 = 33692
- Bob kiểm tra điều kiện d ≡ mod p
Có = 229
11
3
15
mod 59747 = 43319 ≠ 33692 mod 59747
=> Bob thực hiện tiếp
Bob chọn ngẫu nhiên f1 = 17, f2 = 19 ∈
- Bob tính C = mod p = 30178
17
57653
19
mod 59747 = 9217 và gửi cho Alice
- Alice tính D = mod p = mod 59747 = 33028 và gửi cho Bob
- Bob kiểm tra D ≢ mod p
- Bob kiểm tra:
(dg
-e2
)
f1
≡ (Dg
-f2
)
e1
(mod p)
Có (dg
-e2

tức là 1/q ≤ 2
−512
, một xác suất rất bé, có
thể bỏ qua; và vì vậy, các yêu cầu đối với các giao thức kiểm thử và giao thức chối bỏ như trong
phần đặt vấn đề có thể xem như là được thỏa mãn.
1.3. Một số đánh giá về sơ đồ
1.3.1. Độ an toàn của chữ ký
Độ 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 = g
a
mod p => a = log
g
h 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.
1.3.2. Chứng minh tính đúng đắn của giao thức xác thực
1/. Kết luận 1
Nếu y đúng là chữ ký của Alice trên x ( tức là y ≡ x
a
mod p ), thì việc Bob chấp nhận y là
chữ ký của Alice trên x theo giao thức kiểm thử là đúng
Chứng minh
Giả sử y là chữ ký hợp lệ trên x. Bắt đầu từ giá trị d mà Bob nhận từ Alice:
d = mod p = mod p (1)
- Lại có y ≡ x
a
mod p => ≡ x mod p (2)
h ≡ g
a
mod p => ≡ g mod p (3)
Từ (1) (2) (3) => d ≡ x

mod q, x = g
k
mod q, y = g
l
mod q trong đó i, j, k, l ϵ Zq.
+ Kết hợp với
c ≡ y
e1
h
e2
(mod p)
d ≡ x
e1
g
e2
(mod p)
(I)

Do giả thiết y ≠ x
a
( mod p )
=> l ≢ ak ( mod q )
=> Định thức của ma trận hệ số của (I) với các ẩn số e1, e2 là khác 0 => (I) có nghiệm duy
nhất => bất kỳ d ∈ G là giá trị đáp ( response ) của chỉ một trong q cặp giá trị có thể ( e1, e2 )
=> Xác suất để Alice đưa ra giá trị đáp đúng cho Bob trong quá trình xác thực chữ ký là 1/q.
Nhận định đưa ra đã được chứng minh.
1.3.3. Chứng minh tính đúng đắn của giao thức chối bỏ
1/. Kết luận 1
 Nếu y ≠ x
a

Như vậy, đồng dư thức ở bước 7 của giao thức được nghiệm đúng, và kết luận y là chữ ký
giả mạo của A trên x là chính xác, không thể bác bỏ được
. 2/. Kết luận 2
Một điều thú vị có thể xảy ra khi Alice cố tình muốn chối bỏ một chữ ký của mình bằng
cách không tuân theo giao thức hỏi – đáp một cách trung thực. Alice có thể làm cho Bob nghĩ
rằng chữ ký thực sự là giả mạo trong khi không phải như thế. Dưới đây xin nêu ra 1 kết luận như
sau: Xác suất để Alice chối bỏ một chữ ký đúng của anh ta là 1/q
Chứng minh
Nếu Alice cố gắng lừa Bob để Bob nghĩ rằng chữ ký đó là giả mạo, có nghĩa là những điều
kiện sau đây đồng thời xảy ra:
y ≡ x
a
mod p (1)
d ≢ x
e1
g
e2
mod p (2)
D ≢ x
f1
g
f2
mod p (3)
(dg
-e2
)
f1
≡ (Dg
-f2
)

g
-e2/e1
mod p
Từ 2 điều trên => x ≠ d
o
. Điều này có nghĩa là Alice làm cho Bod nghĩ rằng y là giả
mạo với xác suất 1/q.
2. Các hình thức tấn công chữ ký không thể phủ nhận
Trong [8], Markus Jakobsson trình bày hai hình thức tấn công chữ ký không thể chối bỏ như
sau:
2.1. Tống tiền người ký
Giả sử Alice ký chữ ký y trên thông điệp x, nhưng không muốn để lộ thông tin về x cho các
đối thủ của cô biết. Người tống tiền Eve bằng cách nào đó, tìm được (x, y) và quyết định tống
tiền Alice. Eve thực hiện:
- Bước 1: Eve thông báo cho các đối thủ của Alice biết cô ta có một số thông tin mà họ cần.
Cô ta đưa cho mỗi đối thủ {Enemy
i
}( i = 1 – n ) cặp giá trị {y, h} và yêu cầu mỗi đối thủ tạo hai
số bí mật ai, bi sau đó tính bí mật c
i
= y
a1
h
bj
và đưa giá trị c
i
cho Eve.
- Bước 2: Eve cũng tạo bí mật cặp (a
0
, b

có thể thấy cặp (a
i
, b
i
) được dùng trong tập {a
i
}{b
i
} dùng để xác thực chữ ký. Vì thế họ tin rằng
Alice đã kí lên thông điệp x.
2.2. Nhiều người cùng xác thực chữ ký mà người ký không biết
Eve là người đứng ra xác thực, cô ta tính c = từ các giá trị c
i
= y
ai
h
bi
mà những người
muốn xác thực chữ ký gửi đến cho cô ta. Eve gửi c cho Alice.
Sau khi nhận được d từ Alice, Eve gửi ( , , d) cho những người vừa gửi c
i
đến
cho Eve. Tất cả những người này đã xác thực được chữ ký mà Alice không hề hay biết. Thật vậy:
c = = = y
=> e1 = và e2 = . Khi đó tất cả những người gửi ci cho Eve kiểm tra được
rằng (ai, bi) đã được sử dụng trong giao thức kiểm tra chữ ký, và chữ ký được kiểm tra như là
liên hệ trực tiếp với Alice.
3. Ứng dụng chữ ký không thể phủ nhận
3.1. Ứng dụng trong thẻ chứng minh thư điện tử
Bởi vì quá trình xác thực một chữ ký cần sự cộng tác của người ký, chữ ký không thể chối bỏ