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 mưu đồ 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ư xưng
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ự xưng 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ề danh tính của mình.
Một vài sơ đồ định danh như vậy đã được nêu ra. Một mục đích thực
tế là tìm một sơ đồ đủ đơn giản để có thể thực hiện được trên thẻ thông
minh, đặc biệt là thẻ tín dụng gắn thêm một chíp có khả năng thực hiện các
tính toán số học. Vì thế, thẻ đòi hỏi cả khối lượng tính toán lẫn bộ nhớ nhỏ
đến mức có thể. Thẻ như vậy an toàn hơn các thẻ ATM hiện tại. Tuy nhiên,
điều quan trọng cần chú ý là sự an toàn “đặc biệt” liên quan đến người điều
khiển đường dây thông tin. Vì nó là thẻ để chứng minh danh tính nên không
cần bảo vệ chống mất thẻ. Song nó vẫn cần thiết có PIN để biết ai là chủ
nhân thực sự của thẻ.
Trong các phần sau sẽ mô tả một số sơ đồ định danh thông dụng nhất.
Tuy nhiên, trước hết hãy xét một sơ đồ rất đơn giản dựa trên hệ thống mã
khoá riêng bất kì, chẳng hạn như DES. Giao thức mô tả trên hình 9.1 được
gọi là giao thức “yêu cầu và trả lời”, trong đó giả thiết rằng, Alice đang tự
xưng danh với Bob cô và Bob chia nhau một khoá mật chung K, khoá này
chỉ là hàm mã eK.
Hình 9.1: Giao thức Yêu cầu và đáp ứng:
1. Bob chọn một yêu cầu x- là một chuỗi ngẫu nhiên 64 bit. Bob gửi x cho
Alice
2. Alice tính y = eK(x)
gửi nó cho Bob.
3. Bob tính:
y’ = eK(x)
và xác minh y’ = y.
Ta sẽ minh hoạ giao thức này bằng ví dụ nhỏ dưới dây.
Ví dụ 9.1
Giả sử Alice và Bob dùng hàm mã làm luỹ thừa tính modulo:
eK(x) = x102379 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 2512) 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 2140).
 *
p
Z có bậc q (có thể tính như (p-1)
) đều được công khai.
TA sẽ đóng một dấu xác nhận cho Alice. Khi Alice muốn nhận được
một dấu xác thực từ TA, cô phải tiến hành các bước như trên hình 9.2. Vào
thời điểm cuối, khi Alice muốn chứng minh danh tính của cô trước Bob, cô
thực hiện giao thức như trên hình 9.3.
Như đã nêu ở trên, t là một tham số mật. Mục đích của nó là ngăn kẻ
mạo danh - chẳng hạn Olga - khỏi phỏng đoán yêu cầu r của Bob. Ví dụ, nếu
Olga đoán đúng giá trị r, cô ta có thể chọn giá trị bất kỳ cho y và tính
= yv mod p
Cô sẽ đưa cho Bob như trong bước 1 và sau đó khi nhận được yêu cầu r, cô
sẽ cung cấp giá trị y đã chọn sẵn. Khi đó sẽ được Bob xác minh như trong
bước 6.
Hình 9.2 Cấp dấu xác nhận cho Alice.
1. TA thiết lập danh tính của Alice bằng cách lập giấy chứng minh thông
thường chẳng hạn như xác nhận ngày sinh, hộ chiếu ... Sau đó TA thiết
lập một chuỗi ID (Alice) chứa các thông tin định danh của cô ta.
2. Alice bí mật chọn một số mũ ngẫu nhiên a, 0 a q-1. Alice tính:
v = -a mod p
và gửi v cho TA
3. TA tạo ra một chữ kí:
s =sigTA(I,v).
Dấu xác nhận
C(Alice) = (ID(Alice),v,s)
và đưa cho Alice
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 xưng 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 2t và đưa nó cho Alice.
5. Alice tính:
y = k + ar mod q
và đưa y cho Bob.
6. Bob xác minh xem có thoả mãn đồng dư thức sau không
yvr (mod p).
Các đồng dư sau đây chứng minh rằng Alice có khả năng chứng minh danh
tính của cô cho Bob:
yvr k+arvr (mod p)
k+arvar (mod p)
k(mod p)
(mod p)
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)
= 703221031-755mod 88667
= 13136
Giả sử Alice chọn k = 543, sau đó cô tính:
= k mod p
= 70322543 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
= 543 + 755 1000 mod 1031
= 851
và gửi y cho Bob. Sau đó Bob xác minh xem
84109 70322851131361000(mod 88667)
Nếu đúng, Bob sẽ tin rằng anh ta đang liên lạc với Alice.
Tiếp theo ta hãy xem xét cách ai đó có thể mạo danh Alice. Olga - kẻ
đang cố mạo danh Alice bằng cách làm giả dấu xác nhận:
C’(Alice) = (ID(Alice), v’, s’),
trong đó v’v. Song s’ được giả thiết là chữ kí của (ID(Alice), v’, s’) và nó
được Bob xác minh trong bước 3 của giao thức. Nếu sơ đồ chữ kí của TA là
an toàn, Olga sẽ không thể làm giả chữ kí s’ (mà sau này sẽ bị Bob xác
minh).
Biện pháp khác sẽ cho Olga dùng dấu xác nhận đúng của Alice
C(Alice) = (ID(Alice), v, s) (nhớ lại rằng, các dấu xác nhận không mật và
thông tin trên dấu xác nhận bị lộ mỗi lần thực hiện giao thức định danh).
Tuy nhiên Olga sẽ không thể mạo danh Alice trừ phi cô ta cũng biết giá trị a.
Đó là vì “yêu cầu” r trong bước 4. ở bước 5, Olga sẽ phải tính y mà y là hàm
của a. Việc tính a từ v bao hàm việc giải bài toán logarithm rời rạc là bài
toán mà ta đã giả thiết là không thể giải được.
Có thể chứng minh một định lí chính xác hơn về tính an toàn của giao
thức như sau:
Định lí 9.1.
Giả sử Olga biết giá trị
nhờ đó cô có xác suất
1/2t-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 2t 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/2t-1 nên ta có 2t/
2 và bởi vậy,
Olga có thể tính được các giá trị y1,y2,r1 và r2 sao cho
y1 y2
và 11 Îy v
22 Îy v
(mod p)
hay )(mod
212 pv rryy
Vì v = -a nên ta có:
y1-y2 a(r1- r2) (mod q)
Xét thấy 0 < | r1- r2 | <2t và q > 2t là nguyên tố. Vì UCLN(r1- r2, q) = 1
và Olga có thể tính:
a = (y1-y2)(r1 - r2)-1mod q
như mong muốn…