Chơng 9
Các sơ đồ định danh
9.1 Giới thiệu.
Các kỹ thuật mật mã cho phép nhiều bài toán dờng nh không thể giải đợc
thành có thể giải đợc. Một bài toán nh vậy là bài toán xây dựng các sơ đồ định
danh mật. Trong nhiều trờng hợp cần thiết phải chứng minh bằng phơng tiện
điện tử danh tính của ai đó. Dới đây là một số trờng hợp điển hình:
1. Để rút tiền từ một máy thủ quỹ tự động (ATM), ta dùng thẻ cùng với số
định danh cá nhân (PIN) có 4 chữ số.
2. Để trả tiền cho các cuộc mua bán trên điện thoại dùng thẻ tín dụng, tất cả
đều cần số thẻ tín dụng (và thời hạn dùng thẻ)
3. Để trả tiền cho các cú gọi điện thoại đờng dài (dùng thẻ gọi) chỉ cần số
điện thoại và PIN 4 chữ số.
4. Để vào mạng máy tính, cần tên hợp lệ của ngời sử dụng và mật khẩu tơng
ứng.
Thực tế, các kiểu sơ đồ này thờng không đợc thực hiện theo cách an toàn.
Trong các giao thức thực hiện trên điện thoại, bất kì kẻ nghe trộm nào cũng có
thể dùng thông tin định danh cho mục đích riêng của mình. Những ngời này
cũng có thể là ngời nhận thông tin. Các mu đồ xấu trên thẻ tín dụng đều hoạt
động theo cách này. Thẻ ATM an toàn hơn một chút song vẫn còn những điểm
yếu. Ví dụ, ai đó điều khiển đờng dây liên lạc có thể nhận đợc tất cả các thông
tin đợc mã hoá trên dải từ tính của thẻ cũng nh thông tin về PIN. Điều này cho
phép một kẻ mạo danh tiếp cận vào tài khoản nhà băng. Cuối cùng, việc chui
vào mạng máy tính từ xa cũng là vấn đề nghiêm trọng do các ID và mật khẩu
của ngời sử dụng đợc truyền trên mạng ở dạng không mã. Nh vậy, họ là những
vùng dễ bị tổn thơng đối với những ngời điều khiển mạng máy tính.
Mục đích của sơ đồ định danh là: ai đó nghe nh Alice t xng danh với
Bob không thể tự bịa đặt mình là Alice. Ngoài ra, chúng ta sẽ cố gắng giảm
xác suất để chính Bob có thể thử mạo nhận là Alice sau khi cô ta tự xng danh
với anh ta. Nói cách khác, Alice muốn có khả năng chứng minh danh tính của
mình bằng phơng tiện điện tử mà không cần đa ra chút thông tin nào hết về

Giả sử Alice và Bob dùng hàm mã làm luỹ thừa tính modulo:
e
K
(x) = x
102379
mod 167653.
Giả sử yêu cầu của Bob x = 77835. Khi đó Alice sẽ trả lời với y = 100369.
Mọi sơ đồ định danh thực sự đều là các giao thức Yêu cầu và đáp ứng
song các sơ đồ hiệu quả nhất lại không yêu cầu các khoá chia sẻ (dùng chung).
ý tởng này sẽ đợc tiếp tục trong phần còn lại của chơng này.
9.2 Sơ đồ định danh Schnorr.
Ta bắt đầu bằng việc mô tả sơ đồ định danh Schnorr - là một trong
những sơ đồ định danh thực tiễn và đáng chú ý nhất. Sơ đồ này đòi hỏi một ng-
ời đợc uỷ quyền có tín nhiệm mà ta ký hiệu là TA. Ta sẽ chọn các tham số cho
sơ đồ nh sau:
1. p là số nguyên tố lớn (tức p 2
512
) sao cho bài toán logarithm rời rạc trong
Zp là không giải đợc.
2. q là ớc nguyên tố lớn của p-1 (tức q 2
140
).

*
p
Z
có bậc q (có thể tính nh (p-1) ) đều đợc công khai.

Xác suất để Olga phỏng đoán đúng r là 2
-t
nếu r đợc Bob chọn ngẫu nhiên. Nh
vậy, t = 40 là giá trị hợp lý với hầu hết các ứng dụng, (tuy nhiên, chú ý rằng,
Bob sẽ chọn r ngẫu nhiên mỗi lần Alice xng danh với anh ta. Nếu Bob luôn
dùng cùng một r thì Olga có thể mạo danh Alice bằng phơng pháp mô tả ở
trên).
Có hai vấn đề nảy sinh trong giao thức xác minh. Trớc hết, chữ kí s
chứng minh tính hợp lệ của dấu xác nhân của Alice. Nh vậy, Bob xác minh
chữ ký của TA trên dấu xác nhận của Alice để thuyết phục chính bản thân
mình rằng dấu xác nhận là xác thực. Đây là xác nhận tơng tự nh cách đã dùng
ở chơng 8.
Vấn đề thứ hai của giao thức liên quan đến mã số mật a. Giá trị a có
chức năng tơng tự nh PIN để thuyết phục Bob rằng, ngời thực hiện giao thức
định danh quả thực là Alice. Tuy nhiên có một khác nhau quan trọng so với
PIN là: trong giao thức định danh, a không bị lộ. Thay vào đó, Alice (hay
chính xác hơn là thẻ thông minh của cô) chứng minh rằng, cô (thẻ) biết giá trị
a trong bớc 5 bằng cách tính y trong khi trả lời đòi hỏi r do Bob đa ra. Vì a
không bị lộ nên kĩ thuật này gọi là chứng minh không tiết lộ thông tin.
Hình 9.3. sơ đồ định danh Schnorr
1. Alice chọn một số ngẫu nhiên k, 0 k q-1 và tính:
=
k
mod p.
2. Alice gửi dấu xác nhận của mình cho C(Alice) = (ID(Alice),v,s) và cho
Bob.
3. Bob xác minh chữ kí của TA bằng cách kiểm tra xem có thoả mãn
ver(ID(Alice),v,s) = true hay không.
4. Bob chọn một số ngẫu nhiên r, 1 r 2
t

Nh vậy sẽ chấp nhận bằng chứng về danh tính của Alice và giao thức đ-
ợc gọi là có tính đầy đủ.
Dới đây là một ví dụ nhỏ minh hoạ khía cạnh thách thức và đáp ứng
của giao thức.
Ví dụ 9.2
Giả sử p=88667, q = 1031, t=10. Phần tử = 70322 có bậc q thuộc
*
p
Z
. Giả sử
số mã mật của Alice a = 755. Khi đó:
v =
-a
(

mod p)
= 70322
1031-755
mod 88667
= 13136
Giả sử Alice chọn k = 543, sau đó cô tính:
=
k
mod p
= 70322
543
mod 88667
= 84109
và gửi cho Bob. Giả thiết Bob đa ra yêu cầu r = 1000. Khi đó Alice tính:
y = k + ar mod q


1/2
t-1
để giả mạo
Alice thành công trong giao thức xác minh. Khi đó Olga có thể tính a trong
thời gian đa thức.
Chứng minh
Với một phần

trên 2
t
yêu cầu r, Olga có thể tính giá trị y (sẽ đợc Bob
chấp nhận trong bớc 6). Vì

1/2
t-1
nên ta có 2
t
/

2 và bởi vậy, Olga có thể
tính đợc các giá trị y
1
,y
2
,r
1
và r
2
sao cho

a(r
1
- r
2
) (mod q)
Xét thấy 0 < | r
1
- r
2
| <2
t
và q > 2
t
là nguyên tố. Vì UCLN(r
1
- r
2
, q) = 1 và
Olga có thể tính:
a = (y
1
-y
2
)(r
1
- r
2
)
-1
mod q

Alice chứng minh danh tính của mình cho cô ta, để sau đó Olga có thể giả
dạng nh Alice.
Nói chung, có thể hình dung tình huống khi Alice chứng minh danh
tính của mình với Olga trong một số tình huống khác nhau. Có lẽ Olga không
chọn các yêu cầu của cô (tức các giá trị r) theo kiểu ngẫu nhiên. Sau vài lần
thực hiện giao thức, Olga sẽ cố gắng xác định giá trị a để sau đó có thể mạo
danh Alice. Nếu Olga không thể xác định đợc chút thông tin nào về a qua
tham gia với số lần đa thức thực hiện giao thức và sau đó thực hiện một lợng
tính toán đa thức thì giao thức có thể đợc gọi là an toàn.
Hiện tại vẫn cha chứng minh đợc rằng giao thc Schnorr là an toàn, song
trong phần tiếp sau, ta sẽ đa ra một cải tiến về sơ đồ này (do Okmoto đa ra) mà
có thể chứng minh đợc nó là an toàn khi cho trớc giả thuyết tính toán nào đó.
Sơ đồ Schnorr đã đợc thiết kế với tốc độ nhanh và hiệu quả theo quan
điểm cả về tính toán lẫn lợng thông tin cần thiết để trao đổi trong giao thức.
Nó cũng đợc thiết kế nhằm tối thiểu hoá lợng tính toán mà Alice phải thực
hiện. Đây là những đặc tính tốt vì trong thực tế, các tính toán của Alice sẽ phải
tính trên các thẻ thông minh có khả năng tính toán thấp trong khi các tính toán
của Bob lại trên các máy lớn.
Vì mục đích thảo luận, ta hãy giả sử rằng, ID(Alice) là chuỗi 512 bit, v
cũng gồm 512 bit, còn s bằng 320 bit nến DSS đợc dùng nh sơ đồ chữ kí. Kích
thớc tổng cộng của dấu xác nhận C(Alice) (cần đợc lu trên thẻ của Alice) là
1444 bit.
Xét các tính toán của Alice: Bớc 1 cần lấy mũ theo modulo, bớc 5 so
sánh một phép công modulo và một phép nhân modulo. Đó là phép luỹ thừa
modulo mạnh về tính toán song có thể tính toán gián tiếp nếu muốn. Còn các
tính toán trực tiếp đợc Alice thực hiện bình thờng.
Việc tính số bit cần thiết trong quá trình liên lạc để thực hiện giao thức
cũng khá đơn giản. Có thể mô tả thông tin đợc liên lạc ở dạng đồ hình nh sau
C,
Alice r Bob