Chữ ký số ngời xác nhận không thể chối bỏ
Đặt vấn đề
Khi ứng dụng trên mạng máy tính ngày càng trở nên phổ biến, thuận lợi
và quan trọng thì yêu cầu về an toàn mạng, về an ninh dữ liệu trên mạng ngày
càng trở nên cấp bách và cần thiết. Nguồn tài nguyên trên mạng rất dễ bị đánh
cắp hoặc phá hỏng nếu không có một cơ chế bảo mật cho chúng hoặc sử dụng
những cơ chế bảo mật quá lỏng lẻo. Thông tin trên mạng, dù đang truyền hay đ-
ợc lu trữ đều cần đợc bảo vệ. Hoặc các thông tin ấy phải đợc giữ bí mật, hoặc
chúng phải cho phép ngời ta kiểm tra để tin tởng rằng chúng không bị sửa đổi
so với dạng nguyên thuỷ của mình và chúng đúng là của ngời nhận gửi nó cho
ta.
Mạng máy tính có đặc điểm nổi bật là có nhiều ngời sử dụng, nhiều ngời
cùng khai thác một kho tài nguyên, đặc biệt là tài nguyên thông tin và các điểm
có ngời sử dụng thờng phân tán về mặt địa lý. Các điểm này thể hiện lợi ích to
lớn của mạng thông tin máy tính đồng thời nó cũng là điều kiện thuận lợi cho
những ngời muốn phá hoại an toàn thông tin trên mạng máy tính.
Do đó cách tốt nhất để bảo mật thông tin là mã hoá thông tin trớc khi gửi
đi. Mục tiêu cơ bản của mật mã là cho phép 2 ngời, thờng đợc đề cập đến nh
Alice và Bob, liên lạc trên kênh không an toàn theo cách mà đối thủ Orcar
không thể hiểu cái gì đang đợc nói. Kênh này có thể là đờng điện thoại hoặc
mạng máy tính. Thông tin mà Alice muốn gửi đến Bob sẽ đợc gọi là bản rõ
(plaintext), có thể là bất kỳ tài liệu nào có cấu trúc tuỳ ý. Alice mã bản rõ bằng
cách dùng khoá xác định trớc, và gửi bản rõ thu đợc trên kênh không an toàn.
Orcar dù thu trộm đợc mã trên kênh song không thể hiểu đợc bản rõ là gì, nhng
Bob là ngời biết khoá mã có thể giải mã và thiết lập bản rõ.
Có hai loại mật mã là mật mã bí mật và mật mã khoá công khai.Trong
mật mã bí mật, 2 ngời muốn trao đổi thông tin cho nhau phải thoả thuận chọn
một cách bí mật khoá k. Từ k suy ra quy tắc mã hoá e
k
và quy tắc giải mã d
k

báo nhận đợc một cách hiệu quả ta cần có một cửa sập 1 chiều. Điều này đảm
bảo độ bí mật cao.
Mặt khác, mã hoá còn bao gồm cả xác thực và chữ ký số. Xác thực có
nhợc điểm là ở đây 2 bên cùng có chung một khoá nên không thể phân xử đợc
khi 1 trong 2 ngời chối bỏ thông báo họ đã gửi cho ngời kia. Hơn nữa, trong
mạng có nhiều ngời sử dụng, nếu mỗi cặp có một khoá thoả thuận nh vậy thì
mỗi ngời phải lu giữ n-1 khoá bí mật. Khi n đủ lớn, đó là một việc phiền phức,
phức tạp. Chính vì vậy mà chữ ký số đợc sử dụng nhiều hơn. Chữ ký số có
nhiệm vụ giống chữ ký tay nghĩa là nó dùng để thực hiện các chức năng xác
nhận của một ngời gửi trên một văn bản. Nó phải vừa mang dấu vết không chối
cãi đợc của ngời gửi, vừa gắn với từng bit của văn bản mà nếu thay đổi dù chỉ
một bit của văn bản thì chữ ký cũng không còn đợc chấp nhận. Nói chung các l-
ợc đồ chữ ký thì không cần đối thoại. Nhng trong một số trờng hợp để tăng
thêm trách nhiệm trong việc xác nhận, ngời ta dùng các giao thức hỏi- đáp để
xác định độ tin cậy của chữ ký.
Trong đồ án này tôi đi sâu tìm hiểu về lợc đồ chữ ký chống chối bỏ có
ngời xác nhận. ở đây chữ ký có thể đợc kiểm tra mà không cần đến sự cộng tác
của ngời ký mà là một ngời thứ 3- ngời xác nhận.
Chơng I
TổNG QUAN Về NGÔN NGữ C
I.1. Lịch sử hình thành và phát triển
Ngôn ngữ C do Brian W.Kernighan và Dennis M.Ritchie phát triển vào
đầu những năm 70 tại phòng thí nghiệm BELL ( Hoa Kỳ) với mục đích ban đầu
là để phát triển hệ điều hành UNIX. Bối cảnh ra đời xuất phát từ nhu cầu cần
phải có một ngôn ngữ lập trình hệ thống thay thế cho hợp ngữ (Assembly) vốn
nặng nề, độ tin cậy thấp và khó chuyển đổi giữa các hệ máy tính khác nhau.
Ngoài việc C đợc dùng để viết hệ điều hành UNIX, ngời ta nhanh chóng
nhận ra sức mạnh của C trong việc xử lý các vấn đề hiện đại của tin học: xử lý
số, văn bản, cơ sở dữ liệu, lập trình hớng đối tợng. C đã trở thành một chuẩn
mặc nhiên.

khác ngoài cấp phát tĩnh, cấp phát động theo nguyên tắc xếp chồng cho các
biến cục bộ của hàm; không cung cấp cơ chế I/O, không có phơng pháp truy
nhập tệp. Tất cả các cơ chế này đợc thực hiện bằng những lời gọi hàm trong th
viện.
C đa ra các kết cấu điều khiển cơ bản cần cho các chơng trình có cấu
trúc nh: nhóm tuần tự các câu lệnh, chọn quyết định (if); chu trình với phép
- 3 -
Chữ ký số ngời xác nhận không thể chối bỏ
kiểm tra kết thúc ở đầu (for, while), hoặc ở cuối (do while); và việc lựa chọn
một trong các trờng hợp có thể (switch).
C cung cấp con trỏ và khả năng định địa chỉ số học. Các đối của hàm đ-
ợc truyền bằng cách sao chép giá trị đối và hàm đợc gọi không thể thay đổi đợc
giá trị của đối hiện tại.
C cho phép hàm đợc gọi đệ quy và các biến cục bộ của hàm sẽ tự
động sinh ra hoặc tạo mới với mỗi lần gọi mới. Các định nghĩa hàm không
đợc lồng nhau nhng các biến có thể đợc khai báo theo kiểu cấu trúc khối. Các
hàm có thể dịch tách biệt. Các biến có thể trong hoặc ngoài hàm. Hàm chỉ
biết đợc các biến ngoài trong cùng một tệp gốc, hoặc biến tổng thể extern. Các
biến tự động có thể đặt trong các thanh ghi để tăng hiệu quả, nhng việc khai báo
thanh ghi chỉ là một hớng dẫn cho chơng trình dịch và không liên quan gì đến
các thanh ghi đặc biệt của máy.
C không phải là một ngôn ngữ có kiểu mạnh mẽ theo nghĩa của PASCAL
hoặc ALGOL/68. Nó tơng đối thoải mái trong chuyển đổi dữ liệu nhng không
tự động chuyển các kiểu dữ liệu một cách phóng túng nh của PL/I. Các chơng
trình dịch hiện có đều không đa ra cơ chế kiểm tra chỉ số mảng, kiểu đối số
Mặc dù vậy, C vẫn còn tồn tại một số nhợc điểm nh một số phép toán có
thứ tự thực hiện cha đúng; một số phần cú pháp có thể làm tốt hơn; hiện có
nhiều phiên bản của ngôn ngữ, chỉ khác nhau ở một vài chi tiết.
Tóm lại, C vẫn tỏ ra là một ngôn ngữ cực kỳ hiệu quả và đầy sức diễn
cảm đối với nhiều lĩnh vực ứng dụng lập trình. Hơn nữa, ta biết rằng hệ mật

một thông báo đã ký số bị sử dụng lại. Ví dụ, nếu Bob ký thông báo số
cho quyền Alice rút $100 từ tài khoản ở nhà băng của mình, anh ta chỉ muốn
Alice làm việc đó một lần. Do đó, thông báo tự nó phải chứa thông tin để ngăn
chặn Alice làm lại việc đó nhiều lần.
Lợc đồ chữ ký số gồm 2 thành phần: một thuật toán ký và một thuật toán
kiểm tra. Bob có thể ký thông báo x nhờ thuật toán ký (bí mật) Sig. Chữ ký thu
đợc Sig(x) sau đó có thể đợc kiểm tra nhờ thuật toán kiểm tra công khai Ver.
- 5 -
Chữ ký số ngời xác nhận không thể chối bỏ
Khi cho cặp (x,y) thuật toán kiểm tra sẽ trả lời đúng hoặc sai phụ thuộc vào
việc chữ ký có đích thực không?
II. 2. Định nghĩa lợc đồ chữ ký số
Lợc đồ chữ ký số là một bộ năm phần tử (P, A, K, S, V) thoả mãn các điều
kiện sau:
1. P _ là một tập hữu hạn các thông báo.
2. A _tập hữu hạn các chữ ký có thể.
3. K _tập hữu hạn các khoá, không gian khoá.
4. Với mỗi k K, sig
k
S và ver
k
V
Mỗi sig
k
: P A, ver
k
: P * A {true, false} là những hàm sao cho mỗi
bức điện x P và mỗi chữ ký y A thoả mãn:
Ver(x,y) =
( )

II. 3. Một vài lợc đồ chữ ký số
II.3. 1. Lợc đồ chữ ký số RSA
Lợc đồ chữ ký RSA đợc định nghĩa nh sau:
* Tạo khoá:
Cho n = p. q; với p, q là các số nguyên tố lớn khác nhau, (n) = (p - 1)(q -
1). Cho P = A = Z
n
và định nghĩa:
K = {(n, p, q, a, b): n = p.q; p, q là các số nguyên tố; ab 1mod (n)}
Các giá trị n và b là công khai; các giá trị p, q, a là bí mật.
* Tạo chữ ký:
Với K = (n, p, q, a, b) xác định:
- 6 -
Chữ ký số ngời xác nhận không thể chối bỏ
Sig
K
(x) = x
a
mod n
* Kiểm tra chữ ký:
Ver
K
(x, y) = true x y
b
mod n; x, y Z
n
.
Giả sử Bob muốn ký thông báo x, anh ta tính chữ ký y bằng cách:
y = sig
K

Bob
của Bob, khi đó cô ta
nhận đợc z = e
Bob
(x, y). Bản mã z sẽ đợc truyền tới Bob. Khi nhận đợc z, việc tr-
ớc tiên là anh ta giải mã bằng hàm d
Bob
để nhận đợc (x, y). Sau đó anh ta sử
dụng hàm kiểm tra công khai của Alice để kiểm tra xem liệu ver
Alice
(x, y) =
true?
Nếu Alice mã hoá x trớc rồi sau đó mới ký lên bản mã đã đợc mã hoá thì
sao? Khi đó cô ta tính:
y = sig
Alice
(e
Bob
(x))
Alice sẽ truyền cặp (z, y) cho Bob. Bob sẽ giải mã z, nhận đợc x và kiểm
tra chữ ký y trên bằng cách sử dụng ver
Alice
. Một vấn đề tiềm ẩn trong biện pháp
này là nếu Orcar có đợc cặp (z, y) kiểu này, anh ta có thể thay thế chữ ký y của
Alice bằng chữ ký của anh ta: y

= sig
Orcar
(e
Bob

= y
b
modn = 74
7
mod247 = 100 = x.
Alice chấp nhận y = 74 là chữ ký tin cậy.
II.3.2. Lợc đồ chữ ký ElGamal
Lợc đồ chữ ký số ElGamal đợc giới thiệu năm 1985 và đợc Viện tiêu
chuẩn và Công nghệ quốc gia Mỹ sửa đổi thành chuẩn chữ ký số. Lợc đồ
ElGamal không tất định cũng giống nh hệ thống mã hoá công khai ElGamal.
Điều này có nghĩa là có nhiều chữ ký hợp lệ cho một thông báo bất kỳ. Thuật
toán kiểm tra phải có khả năng chấp nhận bất kỳ chữ ký hợp lệ nào khi xác
minh.
Lợc đồ chữ ký số ElGamal đợc định nghĩa nh sau:
* Tạo khoá:
Cho p là số nguyên tố sao cho bài toán lôgarit rời rạc trong Z
p
là khó và
giả sử Z
*
p
là phần tử nguyên thủy.
Cho P = Z
*
p
, A = Z
*
p
ì Z
p-1



x
modp.
Chứng minh:
Nếu chữ ký đợc thiết lập đúng thì kiểm tra sẽ thành công vì:





a.


r.

modp

x
modp ( vì a + r x mod(p - 1)).
Bob tính chữ ký bằng cách dùng cả giá trị bí mật a ( là một phần của
khoá) lẫn số ngẫu nhiên bí mật k (dùng để ký trên x). Việc kiểm ta có thể thực
hiện duy nhất bằng thông tin công khai.
Ví dụ: Giả sử p = 467, = 2, a = 127
Khi đó: =
a
modp = 2
127
mod467 = 132
Giả sử Bob có thông báo x = 100 và anh ta chọn ngẫu nhiên k = 213 vì


-

. Mặt khác, nếu anh ta chọn trớc và sau đó thử tìm thì anh ta
phải giải phơng trình




x
modp, trong đó là ẩn. Bài toán này cha có lời
giải, tuy nhiên dờng nh nó liên quan đến bài toán đã nghiên cứu. Vẫn còn có
khả năng là tìm và đồng thời để (, ) là chữ ký. Hiện thời không ai tìm đợc
cách giải song cũng không ai khẳng định đợc là nó không có lời giải.
- 9 -
Chữ ký số ngời xác nhận không thể chối bỏ
Nếu Orcar chọn và , sau đó thử giải để tìm x, anh ta sẽ phải tính bài
toán logarit rời rạc, tức phải tính log





. Vì thế Orcar không thể ký một
thông điệp ngẫu nhiên bằng cách này. Tuy nhiên có một cách để Orcar ký lên
thông điệp ngẫu nhiên bằng việc chọn , , x đồng thời.
Giả thiết i và j là các số nguyên 0 i p 2; 0 j p 2 và (j, p - 1)
=1.
Khi đó thực hiện các phép tính:
=

i
j
1
modp



-i.j
1


-



-

.i.j
1
modp

x
modp.
Ví dụ: p = 467; = 2; = 132.
Giả sử Orcar chọn i = 99; j = 179, khi đó j
-1
mod(p -1) = 151. Anh ta tính:
= 2
99
132

mod(p - 1)
x

= (hx + i)(h - j)
-1
mod(p - 1)
Trong đó (h - j)
-1
đợc tính theo module (p - 1).
Kiểm tra:


à

'
x
modp (, à) là chữ ký hợp lệ của x

.
Cả 2 phơng pháp trên đều tạo các chữ ký giả mạo hợp lệ song không xuất
hiện khả năng đối phơng giả mạo chữ ký trên thông điệp có lựa chọn của chính
họ mà không phải giải bài toán logarit rời rạc. Vì thế không có gì nguy hiểm về
độ an toàn của lợc đồ ElGamal.
- 11 -
Chữ ký số ngời xác nhận không thể chối bỏ
Chơng III
Hàm Hash
III.1. Giới thiệu
Đối với xác thực và chữ ký số ta thấy rằng các thuật toán thờng nhận
đầu vào là một dòng bít có độ dài rất ngắn( 64,128,160 bit) và tốc độ thực hiện

Hàm Hash là một hàm tính toán có hiệu quả khi ánh xạ các dòng nhị
phân có độ dài tuỳ ý thành các dòng nhị phân có độ dài cố định nào đó.
- 12 -
Chữ ký số ngời xác nhận không thể chối bỏ
- Hàm Hash yếu: Hàm Hash đợc gọi là yếu nếu cho một thông báo x thì về mặt
tính toán không tìm ra đợc thông báo x

khác x sao cho :
h(x

) = h(x)
- Hàm Hash mạnh: Hàm Hash đợc gọi là mạnh nếu về mặt tính toán không tìm
ra đợc hai thông báo x và x

sao cho:
x

x và h(x

) = h(x)
1. Chọn giá trị x ngẫu nhiên, x X
2. Tính z = h(x)
3. Tính x
1
= A(z)
4. Nếu x
1
x thì x
1
và x va chạm dới h( thành công)

m: là số các khối đầu vào.
b
ji
: là bit thứ i trong khối thứ j
: là phép cộng modulo 2.
- 13 -
Chữ ký số ngời xác nhận không thể chối bỏ
Sơ đồ hàm Hash sử dụng phép XOR:
Khối 1: b
11
b
12
b
1n
Khối 1: b
21
b
22
b
2n

Khối m: b
m1
b
m2
b
mn
Mã Hash: C
1
C

Y
2
Y
N+1
III.3.2. Kỹ thuật khối xích
Ngời đầu tiên đề xuất kỹ thuật mật mã xích chuỗi nhng không có khoá bí
mật là Rabin.
Kỹ thuật này thực hiện nh sau:
Chia thông báo M thành các khối có cỡ cố định là M
1
, M
2
, ,M
N
. Sử dụng
hệ mã thuận tiện nh DES để tính mã Hash nh sau.
H
o
= Giá trị ban đầu
H
i
= E
Mi
(H
i-1
), i =
N,1
G = H
N
III.3.3. Các hàm Hash mở rộng

* Xét trờng hợp m t + 2
Giả sử x X, vậy thì tồn tại n để x (Z
2
)
n
, n m.
Ký hiệu:
x
là độ dài của x tính theo bit. Khi đó:
x
= n.
Ký hiệu: x y là dãy bit thu đợc do nối x với y.
Giả sử
x
= n m. Ta có thể biểu diễn x nh sau:
x = x
1
x
2
x
k
Trong đó
1
x
=
2
x
= =
1k
x

k
0
d
( 0
d
là dãy có d số 0. Khi đó y
k
dài m t - 1)
3. y
k+1
là biểu diễn nhị phân của d (
1+k
y
= m t - 1)
4. g
1
= h( 0
t+1
y
1
) (
1
g
= t, 0
t+1
y
1
dài m)
5. Cho i = 1 tới k thực hiên:
g

khi m = t + 1 nh sau:
1. Cho y = y
1
y
2
y
k
= 11f(x
1
) f(x
2
) f(x
n
) (x
1
là một bit)
- 15 -
Chữ ký số ngời xác nhận không thể chối bỏ
2. g
1
= h( 0
t
y
1
) (
1
y
= m t )
3. Cho i = 1 tới k 1 thực hiện
g

4 AA: = A; BB: = B; CC: = C; DD: = D
5 Round1
6 Round2
7 Round3
8 AA: = A +AA; BB: = B + BB; CC: = C + CC;
DD: = D + Ddmod23
32
Chữ ký số ngời xác nhận không thể chối bỏ
Giải thích thuật toán thực hiện MD4:
Giả sử x là một thông báo cần hash. Đầu tiên bổ sung số 1 nối vào x, sau
đó là dãy các số 0 sao cho độ dài thu đợc đồng d với 448mod512. Cuối cùng,
gắn thêm 64 bit nữa vào để đợc thông báo mở rộng. Đây là 64 bit biểu diễn nhị
phân độ dài nguyên thuỷ của x. Kết quả ta đợc thông báo mở rộng M có độ dài
chia hết cho 512. Vì vậy khi cắt thành những từ có độ dài 32 bit ta sẽ đợc số N
chia hết cho 16.
Biểu diễn M đới dạng dãy liên tiếp N các từ có độ dài 32 bit:
M = M[0] M[1] M[N 1]
Do M chia hết cho 512 nên N chia hết cho 16.
Thuật toán xây dựng M trong MD4 nh sau:
Bớc 1: d = 447 (xmod512)
Bớc 2: Cho l biểu diễn nhị phân của xmod2
64
, l= 64
Bớc 3: M = x10
d
l
Trong khi xây dựng M chúng ta bổ sung l vào x và thêm toàn số 0 sao
cho độ dài đồng d với 448mod512 (độ dài mod512) và cuối cùng gắn thêm 64
bit biểu diễn nhị phân độ dài nguyên thuỷ của x. Kết quả chuỗi M có độ dài
chia hết cho 512. Vì vậy khi cắt thành những từ có độ dài 32bit ta sẽ đợc số N

h(A, B, C) = A B C
Ta ký hiệu các hằng số:
K
1
= 0x5a827999
K
2
= 0x6ed9eba1
Các biến X
i
, i =
15,0
Bảng chân lý của 3 hàm:
A B C f(A, B, C) g(A, B, C) h(A, B, C)
0 0 0 0 0 0
0 0 1 1 0 1
0 1 0 0 0 1
0 1 1 1 1 0
1 0 0 0 0 1
1 0 1 0 1 0
1 1 0 1 1 0
1 1 1 1 1 1
3 vòng Round1, Round2, Round3 đợc mô tả theo bảng sau:
- 18 -
Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá
Round1:
1 A = (A + f(B, C, D) + X
o
)<<3
2 D = (D + f(A, B, C) + X

11
)<<19
13 A = (A + f(B, C, D) + X
12
)<<3
14 D = (D + f(A, B, C) + X
13
)<<7
15 C = (C + f(D, A, B) + X
14
)<<11
16 B = (B + f(C, D, A) + X
15
)<<19
Round2:
1 A = (A + g(B, C, D) + X
o
+ K
1
)<<3
2 D = (D + g(A, B, C) + X
4
+ K
1
)<<5
3 C = (C + g(D, A, B) + X
8
+K
1
)<<9

10 D = (D + g(A, B, C) + X
6
+ K
1
)<<5
11 C = (C + g(D, A, B) + X
10
+K
1
)<<9
12 B = (B + g(C, D, A) + X
14
+ K
1
)<<13
13 A = (A + g(B, C, D) + X
3
+ K
1
)<<3
14 D = (D + g(A, B, C) + X
7
+ K
1
)<<5
15 C = (C + g(D, A, B) + X
11
+K
1
)<<9

)<<3
6 D = (D + h(A, B, C) + X
10
+ K
2
)<<9
- 19 -
Chữ ký số ngời xác nhận không thể chối bỏ
7 C = (C + h(D, A, B) + X
6
+ K
2
)<<11
8 B = (B + h(C, D, A) + X
14
+ K
2
)<<15
9 A = (A + h(B, C, D) +X
1
+ K
2
)<<3
10 D = (D + h(A, B, C) + X
9
+ K
2
)<<9
11 C = (C + h(D, A, B) + X
5

IV.1. Giới thiệu
Chữ ký chống chối bỏ đợc công bố bởi Chaum và van Antwerpen vào
năm 1989. Nó có một số nét riêng mới lạ rất thú vị. Quan trọng nhất trong số đó
là chữ ký không thể kiểm tra khi không có sự cộng tác của ngời ký, Bob.
Sự bảo vệ này của Bob đề phòng khả năng chữ ký trong tài liệu của anh ta
bị sao chép và phân bố bởi thiết bị điện tử mà không có sự đồng ý của anh ta.
Ví dụ, Bob có một phần mềm và chữ ký kèm theo đợc tạo ra nhờ thuật toán của
chữ ký số thông thờng. Nh vậy, sẽ không tránh khỏi trờng hợp phần mềm đó bị
sao chép mà Bob không biết. Ngời mua sẽ kiểm tra chữ ký kèm theo phần mềm
nhờ thuật toán kiểm tra công khai Ver và công nhận đó là chữ ký đúng. Vì nh
chúng ta đã biết bản sao của chữ ký số là đồng nhất với bản gốc. Đơng nhiên
nh vậy Bob đã bị mất bản quyền. Để tránh điều bất lợi đó Bob đã dùng chữ ký
số chống chối bỏ. Sự kiểm tra sẽ thành công khi thực hiện giao thức hỏi - đáp.
Lợc đồ chữ ký chống chối bỏ gồm 3 phần: thuật toán ký, giao thức kiểm
tra, giao thức chối bỏ.
IV.2. Lợc đồ chữ ký chống chối bỏ
IV.2.1. Thuật toán ký
* Tạo khoá:
Cho p, q là các số nguyên tố lẻ sao cho p = 2q + 1 và bài toán rời rạc trên
Z
p
là khó. Lấy Z
p
*
là một phần tử của bậc q (Nếu
0
là phần tử nguyên thuỷ
của Z
p
thì =

ngẫu nhiên, e
1
, e
2
Z
p
*
.
2 2. Alice tính c = y
1
e

2
e
modp và gửi nó cho Bob.
3. Bob tính d = c
qa mod
1
modp và gửi nó cho Alice.
3 4. Alice chấp nhận y là chữ ký đúng khi và chỉ khi:
d x
1
e

2
e
modp.
* Vai trò của p, q trong lợc đồ:
Lợc đồ nằm trong Z
p

1
a
modp (1)
Ta lại có:
a
modp

1
a
modp (2)
- 21 -
Chữ ký số ngời xác nhận không thể chối bỏ
Tơng tự ta cũng có: y = x
a
modp
y
1
a
= x modp (3)
Thay (2), (3) vào (1) đợc:
d x
1
e

2
e
modp. _ Đó là điều phải chứng minh.
Ví dụ: Giả sử chúng ta lấy p = 467. Từ 2 là căn nguyên thuỷ => 2
2
= 4 là

Alice gửi c =13 cho Bob và Bob sẽ tính d theo:
d = c
qa mod
1
modp
d = 13
101
1
mod233
mod467 (q = (p - 1)/2 = (467 1 )/2 = 233)
d = 9
Alice kiểm tra chữ ký y theo bớc 4. Có:
x
1
e

2
e
modp = 119
38
4
397
mod467 = 9
d x
1
e

2
e
modp .


2
e
modp và gửi nó cho Bob.
3. Bob tính d = c
qa mod
1
modp và gửi nó cho Alice.
5 4. Alice kiểm tra d x
1
e

2
e
modp.
5.Alice chọn f
1
, f
2
ngẫu nhiên, f
1
, f
2
Z
q
*
.
6 6. Alice tính C = y
1
f

kiểm tra. Bớc 9 là bớc kiểm tra tính chính xác cho phép Alice xác định rõ chữ
ký đó có xác thực hay không nếu sự trả lời của Bob đợc tạo ra nh giao thức theo
lý thuyết.
Ví dụ: Ta lấy tơng tự nh ví dụ trớc. Lấy p =467, = 4, a = 101, = 449.
Ký thông báo x =286 với chữ ký y = 83 (là giả mạo). Bob muốn thuyết phục
Alice rằng chữ ký đó là không đúng. Vậy phải thực hiện nh sau:
Alice chọn ngẫu nhiên e
1
= 45, e
2
= 237. Alice tính c = 305 và Bob trả lời
với d = 109. Alice tính: 286
45
. 4
237
mod467 = 149.
Vì 149 109 nên Alice thực hiện tiếp giao thức chối bỏ.
Alice chọn tiếp f
1
= 125, f
2
= 9, ngẫu nhiên, Alice tính C = 270 và Bob trả
lời với D = 68. Alice tính: 286
125
.4
9
mod467 = 25.
Vì 25 68 nên Alice thực hiện bớc cuối cùng của giao thức tức là thực
hiện kiểm tra tính chính xác.
Ta có: (109.4

IV.3.1 Định lý 1: Nếu y x
a
modp, Alice sẽ chấp nhận y nh là một chữ ký đúng
của x với xác suất
q
1
.
Chứng minh:
Trớc tiên, ta nhận xét rằng mỗi yêu cầu c có thể xảy ra sẽ tơng ứng chính
xác với một cặp (e
1
, e
2
) bậc q. (Bởi vì y và đều là phần tử của nhóm nhân G có
bậc nguyên tố lẻ q). Khi Bob nhận yêu cầu c anh ta không biết Alice đã dùng
cặp (e
1
, e
2
) nào để xây dựng c. Chúng ta cần phải chứng minh rằng, nếu y
x
a
modp thì các câu trả lời của Bob d G có thể đúng với duy nhất một cặp (e
1
,
e
2
) trong các cặp (e
1
, e

modp (2)
(1)
i

l .e
1
.
e
2
modp
với =
a
modp

i

l .e
1
.
a.e
2
modp

i

l .e
1
+ a .e
2
modp

i l.e
1
+ a.e
2
modq
j k.e
1
+ e
2
modq
Xét D =
l
k

a
1
= l a.k (5)
Mặt khác: y x
a
modp (gt)

l

k .a
modp
l a.k modq (6)
Từ (5) và (6) D 0
Vì hệ số ma trận của hệ đồng d theo modun q 0 nên hệ có một nghiệm
duy nhất nghĩa là ta tìm đợc duy nhất một cặp (e
1

2
)
e
1
modp.
Chứng minh:
Ta có: d c
a
1
modp
Mà c y
e
1

e
2
modp
d y
e
1
.a
1
.
e
2
.a
1
modp
Mặt khác:
a

.a
.
-e
2
)
f
1
modp
y
e
1
.a
1
.f
1
.
e
2
.f
1
e
2
.f
1
modp
y
e
1
.a
1