Website: http://www.docs.vn Email : lienhe@docs.vn Tel : 0918.775.368
Chữ ký số ngời xác nhận không thể chối bỏ
đợ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 chuẩn hay
chữ ký số luôn cần một bộ số rất lớn tức là kích cỡ của không gian khoá rất lớn
khoảng trên 300 số thập phân. Do đó, ngôn ngữ C đủ mạnh để có thể đáp ứng đợc
điều đó.
- 5 -
Website: http://www.docs.vn Email : lienhe@docs.vn Tel : 0918.775.368
Chữ ký số ngời xác nhận không thể chối bỏ
Chơng II
CHữ Ký Số
II.1. Giới thiệu chung về chữ ký số
Nh chúng ta đã biết, chữ ký viết tay thờng lệ gắn với tài liệu đợc dùng để
chỉ ra ngời đã ký nó. Chữ ký đợc sử dụng hàng ngày nh để viết th, ký hợp đồng
ở đây, chúng ta tìm hiểu về chữ ký hoàn toàn khác đó là chữ ký số. Nó là
phơng pháp ký thông báo đợc lu dới dạng điện tử và thông báo đợc ký có thể
truyền trên mạng máy tính. Chữ ký tay và chữ ký số dù cùng có nhiệm vụ chung
là ký nhng có sự khác nhau cơ bản giữa chúng.
Thứ nhất, về việc ký tài liệu: Với chữ ký tay thì chữ ký là bộ phận vật lý
của tài liệu đợc ký. Tuy nhiên, chữ ký số không gắn một cách vật lý với thông
báo đợc ký mà đợc gắn với thông báo theo logic, do đó thuật toán đợc dùng phải
trói chữ ký với thông báo theo một cách nào đó.
Thứ hai, về việc kiểm tra: chữ ký tay đợc kiểm tra bằng cách so sánh nó
với những cái khác, những chữ ký đã xác thực. Ví dụ, một ngời ký trên một tấm
séc mua hàng, ngời bán hàng phải so sánh chữ ký trên tấm séc với chữ ký nằm ở
sau thẻ tín dụng để kiểm tra. Tất nhiên, phơng pháp này không an toàn lắm vì nó
tơng đối dễ đánh lừa bởi chữ ký của ngời khác. Khác với chữ ký tay, chữ ký số có
thể đợc kiểm tra bằng cách dùng thuật toán kiểm tra công khai đã biết. Vì vậy,
bất kỳ ngời nào đó đều có thể kiểm tra chữ ký số. Và việc sử dụng lợc đồ ký an
toàn sẽ ngăn chặn khả năng đánh lừa.
Điều khác nhau cơ bản giữa chữ ký tay và chữ ký số là bản sao thông
báo số đợc ký là đồng nhất với bản gốc. Trong khi đó, bản sao chép tài liệu giấy
đã ký thờng là khác với bản gốc. Điều này nghĩa là phải cẩn thận để ngăn chặn
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ố
- 6 -
Website: http://www.docs.vn Email : lienhe@docs.vn Tel : 0918.775.368
Chữ ký số ngời xác nhận không thể chối bỏ
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. 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) =
( )
( )
.
,
,
=
xsigykhifalse
xsigykhitrue
*Yêu cầu:
- Với mỗi khoá k K, các hàm sig
k
và ver
k
là các hàm thời gian đa thức.
- Ver
k
là hàm công khai; sig
k
là hàm bí mật để tránh trờng hợp Orcar có thể giả
mạo chữ ký của Bob để ký thông báo x. Với mỗi x chỉ duy nhất Bob tính đợc chữ
ký y sao cho:
Ver(x, y) = True.
- 7 -
Website: http://www.docs.vn Email : lienhe@docs.vn Tel : 0918.775.368
Chữ ký số ngời xác nhận không thể chối bỏ
Lợc đồ chữ ký phải an toàn. Bởi vì Orcar có thể kiểm tra tất cả các khả năng của
chữ ký y nhờ thuật toán kiểm tra công khai Ver cho tới khi đạt đợc yêu cầu tức là
tìm đợc chữ ký đúng. Do đó, nếu có đủ thời gian cần thiết Orcar có
thể giả mạo đợc chữ ký của Bob. Vì vậy mục đích của chúng ta là tìm các lợc đồ
chữ ký sao cho Orcar không đủ thời gian thực tế để thử nh thế.
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:
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
(x) = x
a
B
modn (a
B
là tham số bí mật của Bob).
Bob gửi cặp (x, y) cho Alice. Nhận đợc thông báo x và chữ ký số y, Alice tiến
hành kiểm tra đẳng thức:
x = y
b
B
modn (b
B
là khóa công khai của Bob)
Nếu đúng, Alice công nhận y là chữ ký trên x của Bob. Ngợc lại, Alice sẽ
coi x không phải của Bob gửi cho mình (chữ ký không tin cậy).
Ngời ta có thể giả mạo chữ ký của Bob nh sau: chọn y, sau đó tính x =
ver
K
(y), khi đó y = sig
K
(x). Một cách để khắc phục khó khăn này là việc yêu cầu
- 8 -
Website: http://www.docs.vn Email : lienhe@docs.vn Tel : 0918.775.368
Chữ ký số ngời xác nhận không thể chối bỏ
x phải có nghĩa. Do đó chữ ký giả mạo nói trên sẽ thành công với xác suất rất
nhỏ.
Ta có thể kết hợp chữ ký với mã hoá sẽ làm cho độ an toàn của chữ ký tăng
thêm.
Giả sử rằng, Alice sẽ tính chữ ký của cô ta là y = sig
Alice
(x), và sau đó mã
hoá cả x và y bằng cách sử dụng mật mã công khai e
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
(x))
Chú ý rằng Orcar có thể ký bản mã e
bob
(x) ngay cả khi anh ta không biết
bản rõ x.
Khi đó, nếu Orcar truyền (z, y
) tới Bob, chữ ký của Orcar sẽ đợc kiểm thử
vì Bob sử dụng ver
Orcar
, và Bob có thể suy ra rằng bản rõ x xuất phát từ Orcar.
Điều này cũng làm cho ngời sử dụng hiểu rằng nên ký trớc rồi sau đó mới tiến
hành mã hoá.
Ví dụ: Giả sử Bob dùng lợc đồ chữ ký số RSA với n = 247 (p = 13, q = 19);
(n) = 12.18 = 216. Khoá công khai của Bob là b = 7
a = 7
-1
mod216 = 31.
- 9 -
Website: http://www.docs.vn Email : lienhe@docs.vn Tel : 0918.775.368
Chữ ký số ngời xác nhận không thể chối bỏ
Bob công khai (n, b) = (247, 7).
Bob ký lên thông báo x = 100 với chữ ký:
y = x
a
modn = 100
31
mod247 = 74.
Bob gửi cặp (x, y) = (100, 74) cho Alice. Alice kiểm tra bằng cách sử dụng khoá
công khai của Bob nh sau:
x
= 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
và định nghĩa:
K = {(p, a, , ): =
a
modp }.
Các giá trị p, , là công khai, a là bí mật.
* Tạo chữ ký:
Với K = (p, a, , ) và với số ngẫu nhiên k Z
*
1
p
, định nghĩa:sig
k
(, ),
trong đó:
=
k
modp và = (x - a) k
-1
mod(p - 1).
* Kiểm tra chữ ký số:
Với x, Z
*
p
và Z
p-1
, ta định nghĩa:
Ver (x, , ) = True
.
x
modp.
- 10 -
Website: http://www.docs.vn Email : lienhe@docs.vn Tel : 0918.775.368
Chữ ký số ngời xác nhận không thể chối bỏ
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ì
(213, 466) =1 và 213
-1
mod466 = 431
Bob ký trên x nh sau:
=
k
modp = 2
213
mod467 = 29
và = (x - a)k
-1
mod(p -1) = (100 127. 29).431 mod466 = 51.
Chữ ký của Bob trên x = 100 là (29, 51).
Bất kỳ ngời nào đó cũng có thể kiểm tra chữ ký này bằng cách:
132
29
. 29
51
189 mod 467
2
100
189 mod 467
Do đó chữ ký là tin cậy.
Bây giờ, ta xét độ an toàn của lợc đồ chữ ký ElGamal.
Giả sử Orcar thử giả mạo chữ ký trên thông báo x cho trớc mà không biết
a. Nếu Orcar chọn giá trị và thử tìm tơng ứng, anh ta phải tính logarit rời rạc
của log
x
-
. 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
- 11 -
Website: http://www.docs.vn Email : lienhe@docs.vn Tel : 0918.775.368
Chữ ký số ngời xác nhận không thể chối bỏ
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.
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
modp
= -.j
-1
mod(p - 1)
x = -
i
.j
-1
mod(p - 1) = i. mod(p - 1).
Trong đó j
-1
đợc tính theo module (p - 1). Ta thấy rằng (, ) là chữ ký hợp lệ của
x. Điều này đợc chứng minh qua việc kiểm tra:
-
(
i
j
)
-
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
179
mod467 = 117
= - 177. 151 mod466 = 41
x = 99. 41 mod 466 = 331
Và (117, 41 ) là chữ ký trên x = 331.
Kiểm tra:
- 12 -
Website: http://www.docs.vn Email : lienhe@docs.vn Tel : 0918.775.368
Chữ ký số ngời xác nhận không thể chối bỏ
132
117
117
41
303mod 467
và 2
331
303 mod467
Do đó chữ ký là hợp lệ.
Orcar có thể giả mạo chữ ký theo kiểu khác là bắt đầu từ thông báo x đã đ-
ợc Bob ký. Giả sử (, ) là chữ ký hợp lệ trên x. Khi đó Orcar có khả năng ký lên
nhiều thông báo khác nhau. Giả sử i, j, h là các số nguyên; 0 h; i, j p 2 và
(h - j, p - 1) = 1. Thực hiện các phép tính:
=
h
i
j
modp
à = (h - j)
-1
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.
- 13 -
Website: http://www.docs.vn Email : lienhe@docs.vn Tel : 0918.775.368
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 chậm.
Mặt khác, các thông báo cần ký thờng có độ dài khác nhau và trong nhiều trờng
hợp chúng có độ dài lớn cỡ vài Kilôbyte hoặc vài Megabyte. Do vậy, muốn ký
một chữ ký ngắn trên một thông báo dài ta cần phải cắt thông báo ra nhiều đoạn
có độ dài hữu hạn và cố định rồi tiến hành ký độc lập từng đoạn đó và gửi từng
đoạn đó đi. Khi đó lại xuất hiện nhiều vấn đề nh:
- Tốc độ thực hiện sẽ rất chậm vì phải ký trên quá nhiều đoạn.
- Dễ xảy ra trờng hợp không sắp xếp đợc thông báo theo đúng trật tự ban
đầu.
- Có thể bị mất các đoạn riêng biệt trong quá trình truyền tin.
- 14 -
Không có nhận xét nào:
Đăng nhận xét