Giáo trình Đại số hiện đại - Chương 10: Sơ đồ định danh

Chương 10
SƠ ĐỒ ĐỊNH DANH
Tổng quan về sơ đồ định danh
Trong thực tế có những trường hợp cần chứng minh bằng phương tiện điện tử danh tính của ai đó. Tức là Alice và Bob liên lạc với nhau, Bob muốn biết người đang liên lạc với mình có chính là Alice hay là không? Alice muốn cho Bob biết chính Alice chứ không phải ai khác, cô ta chứng minh bằng phương tiện điện tử mà không cần đưa ra bất cứ thông tin nào về bản thân Alice. Đó là mục đích của bài toán sơ đồ định danh. Sơ đồ định danh thường phục vụ cho các loại thẻ thông minh. Ví dụ thẻ rút tiền tự động ATM, thẻ này dùng số định danh PIN với 4 số nhằm để biết ai là chủ thẻ. Vì thế mà khi thiết kế các sơ đồ nên tính đến khối lượng tính toán và bộ nhớ để tương thích với các loại thẻ thông minh.
Sơ đồ định danh trên cơ sỡ mật mã đối xứng
Đây là bài toán đảm bảo được tính chân thực của phiên giao dịch, nó bao gồm là chứng thực được các đối tượng tham gia giao dịch. Kiểm tra tính chân thực của các bên tham gia của phiên giao dịch có thể thực hiện bằng cách sử dụng cơ chế “ hỏi-trả lời”.
Cơ chế “hỏi – trả lời” được thực hiện như sau. Các bên liên quan với nhau sở hửu một khóa mật K. Bây giờ bên Alice và bên Bob muốn liên kết với với nhau. Alice tạo ra số R với chiều dài n bít và gởi R cho Bob. Bob nhận được R và dùng khóa K để mã hóa R thành C=EK(R). Bob cũng tạo ra số ngẫu nhiên R’ dài n bít và gởi (C,R’) cho Alice. Alice cũng mã hóa R của mình, C*=EK(R), nếu như C*=C thì chứng nhận bên Bob. Alice thực hiện mã hóa R’: C’=EK(R’) và gởi C’ cho bên Bob. Bên Bob tương tự cũng mã hóa R’ của mình, C”=EK(R’), bên Bob so sánh nếu như C’=C” thì chứng thực bên Alice.
Sơ đồ chữ ký và sơ đồ định danh Feige-Fiat-Shamir 
Sơ đồ do Adi Shamir, Uriel Feige và Amos Fiat tạo ra và đến 09/07/1986 nhóm tác giả được nhận bằng sáng chế của Mỹ.
Sơ đồ đơn giản Feige-Fiat-Shamir 
Trước khi đưa ra các tham số mật, người có uy tín chọn modulo n, n là tích của hai số nguyên tố lớn. Trong thực tế cần phải chọn n không nhỏ hơn 512 bit và tốt nhất là chọn cở 1024 bít. n là tham số công khai.
Để tạo ra khóa mở và khóa mật, thì Alice thỏa thuận với người uy tín hay tổ chức chứng nhận (TA) để chọn số v, sao cho v là thặng dư bậc hai theo modulo n. Hay nói cách khác, chọn v sao cho v thỏa mãn phương trình: có nghiệm và tồn tại. v là tham số mở của Alice. Sau đó tính giá trị nhỏ nhất s, sao cho. Số s là tham số mật của Alice. Sơ đồ định danh được miêu tả bằng giao thức sau. Những tham số của Alice được TA và những thông tin riêng tư của Alice (ID) được ký bằng chữ ký của TA(signTA) và thuật toán kiểm tra chữ ký của TA (verifyTA) và đưa ra dấu xác nhận cho Alice:
C(Alice)=(ID(Alice),v,signTA(ID,v)).
Sơ đồ định danh được miêu tả như sau.
Alice chọn số ngẫu nhiên r, nhỏ hơn n. Sau đó cô ta tính và gởi x và dấu xác thực C(Alice) cho Bob.
Bob xác minh chữ ký của TA bằng cách kiểm tra điều kiện sau có đúng hay không: verifyTA(ID(Alice),v,signTA(ID,v))=true?
Bob gởi cho Alice một bít ngẫu nhiên b.
Nếu nhu b=0 thì Alice gởi cho Bob r. Nếu b=1 thì Alice gởi cho Bob y=r*s (mod n).
Nếu b=0, Bob kiểm tra đẳng thức: , vì tin tưởng rằng chỉ Alice biết gía trị của . Tương tự nếu b=1 thì Bob kiểm tra đẳng thức: vì chỉ có Alice mới biết giá trị .
Giao thức trên được Alice và Bob lặp lại t lần, đến khi nào Bob tin tưởng rằng người liên hệ với mình chính là Alice. Nếu như Alice không biết s, cô ta có thể lựa chọn số r sao cho có thể lừa được Bob, khi Bob gởi đến bít 0, và cũng có thể lựa chọn r để lừa Bob khi Bob gởi đến bit 1. Xác suất để Alice lừa Bob thành công là ½. Xác suất để cô ta thành công trong t lần là.
Để giao thức hoạt động, thì Alice không bao giờ sử dụng lại giá trị r, nếu không Bob sẽ tính được gía trị s. Và từ đây sơ đồ hoàn toàn bị phá vỡ.
Sơ đồ nâng cao Feige-Fiat-Shamir 
Để nâng cao tính an toàn của sơ đồ, giảm sự liên quan giữa Alice và Bob, Feige-Fiat-Shamir đã nâng cấp sơ đồ đơn giản ở trên. Sơ đồ được miêu tả như sau:
Giống như sơ đồ trước,TA tạo ra số n, là tích của hai số nguyên tố lớn. Để tạo ra khóa mở và khóa mật, Alice thỏa thuận với TA để tạo k giá trị khác nhau: , ở đây là thặng dư bậc hai theo modulo n. Hay nói cách khác được chọn sao cho thỏa mãn phương trình: có nghiệm và tồn tại . Các giá trị là công khai của Alice. Sau đó tính giá trị nhỏ nhất thỏa mãn. Dãy giá trị là khóa mật của Alice. Tương tự những tham số của Alice được TA và những thông tin riêng tư của Alice (ID) được ký bằng chữ ký của TA(signTA) và thuật toán kiểm tra chữ ký của TA (verifyTA) và đưa ra dấu xác nhận cho Alice:
C(Alice)=(ID(Alice), ,signTA(ID, )).
 Giao thức được thực hiện như sau:
Alice chọn số ngẫu nhiên r, nhỏ hơn n. Sau đó cô tính và gởi x và dấu xác thực C(Alice) cho Bob.
Bob xác minh chữ ký của TA bằng cách kiểm tra điều kiện sau có đúng hay không: verifyTA(ID(Alice), ,signTA(ID, ))=true?
Bob gởi cho Alice một dãy k bít: .
Alice tính và gởi y cho Bob.
Bob kiểm tra 
Alice và Bob lặp lại giao thức trên t lần, đến khi nào Bob tin tưởng được rằng Alice biết dãy số .
Xác suất để Alice không biết day số mà lừa thành công Bob qua t lần là . Tác giả khuyến cáo nên chọn k=5 và t=4.
Ví dụ:
Nhà tín nhiệm chọn n=35=5*7. Alice thỏa với nhà tín nhiệm để tạo ra 4 giá trị (k=4),v1=4,v2=11,v3=16,v4=29. Các giá trị si tương ứng là {3,4,9,8}.
Alice chọn , và tính 162 mod 35=11, và gởi 11 cho Bob.
Bob gởi cho Alice dãy bít:{1,1,0,1}.
Alice tính 16*(31*41*90*81) mod 35 =31 và gởi 31 cho Bob.
Bob kiểm tra 312*(41*111*160*291) mod 35 =11.
Alice và Bob lặp lại giao thức trên t lần, mỗi lần Alice chọn lại giá trị r mới, đến khi Bob tin Alice.
Cải tiến sơ đồ
Ở sơ đồ trên cần có dấu xác nhận của TA, ở đây ta không dùng dấu xác nhân nũa mà tạo các giá trị từ chính giá trị đinh danh của Alice (ID), cụ thể thực hiện như sau. Giả sử ID là định danh của Alice: tên, địa chỉ, số chứng minh nhân dân và một số thông tin cá nhân khác. Sử dụng hàm băm H(x) để tính giá trị H(ID,j), ở đây j là số không lớn. Chúng ta tìm các số j sao cho giá trị của H(ID,j) là thặng dư bậc hai của modulo n, tức là tạo ra dãy số từ H(ID,j). Và Alice gởi ID và j cho Bob trước khi tiến hành bước 1 của giao thức, Bob cũng tự tính ra các số từ H(ID,j).
Chuyển sơ đồ định danh Feige-Fiat-Shamir thành sơ đồ chữ ký Fiat-Shamir 
Yêu điểm chính của sơ đồ chữ ký này so với RSA là về tốc độ: đối với Fiat-Shamir sử dụng modulo của phép nhân nhỏ hơn nhiều lần so với RSA.
Các biến khởi tạo, giống như trong sơ đồ định danh. Tức là chọn số n là tích của hai số nguyên tố lớn. Tạo ra khóa mở và tính khóa mật, ở đây . Sơ đồ chữ ký được miêu tả như sau:
Alice chọn t số nguyên trong khoảng từ 1 đến n: và tính các giá trị , với .
Alice tính giá trị hàm băm, đối số của nó là liên kết xi và bản tin m, để tạo thành dòng bít: H(m, ). Alice sử dụng k*t bít đầu tiên của dòng bít này, tạo thành mảng bít bij, i=1,t còn j=1,k.
Alice tính các giá trị , ở đây .
Alice gởi cho Bob m, tất cả các bít bij và tất cả giá trị yi. Và Bob có được các khóa mở của Alice .
Bob tính các giá trị , ở đây . Chú ý rằng zi cần phải bằng xi.
Bob tính giá trị của dong bít: H(m, )- và lấy k*t bít đầu tiên của dòng này để so sánh với với giá trị bij mà Alice gởi cho Bob.
Tương tự như sơ đồ định danh. Sơ đồ này cũng có độ an toàn tỉ lệ với . Và độ an toàn cũng phụ thuộc vào sự phân tích n thành nhân tử. Tác giả khuyến cáo tăng k*t từ 20 (như khuyến cáo trong sơ đồ định danh) lên 72, tức là k=9 và t=8. Họ khuyến cáo chọn các số là k số nguyên tố đầu tiên.
Sơ đồ định danh và sơ đồ chữ ký Guillou-Quisquater 
Sơ đồ định danh Guillou-Quisquater
Độ an toàn sơ đồ này dựa trên cơ sở độ an tòan của hệ mật RSA. TA hình thành số công khai n từ tích của hai số nguyên tố mật đủ lớn, để bài toán phân tích thành nhân tử là không thực hiện được. Khóa mật B được Alice chọn và tính giá trị khóa công khai v theo công thức:. J là một số nguyên tố dài 40 bít là một tham số công khai. Các thông tin cá nhân của Alice (ID) và các tham số công khai được TA ký xác nhận và hình thành dấu xác nhận:
C(Alice)=(ID(Alice), v,signTA(ID, v)).
Giao thức được miêu tả như sau:
Alice chọn số nguyên ngẫu nhiên r, nằm trong khoảng 1 đến n-1. Alice tính và gởi T và dấu xác nhận C(Alice) cho Bob.
Bob xác minh chữ ký của TA bằng cách kiểm tra điều kiện sau có đúng hay không: verifyTA(ID(Alice), v,signTA(ID, v))=true?
Bob chọn số nguyên ngẫu nhiên d nằm trong khoảng 0 đến v-1. Và Bob gởi d cho Alice.
Alice tính và gởi cho Bob.
Bob tính . Nếu như thì sự chân thực của Alice được chứng minh.
Ví dụ: Giả sử TA chọn p=467, q=479, nên n=pq=223693. Giả sử chọn J=503 và số mật B=101575. Khi đó Alice tính khóa công khai:
Giả sử Alice chọn r=187485, sau đó Alice tính giá trị:
Alice gởi T cho Bob. Giả sử Bob chọn d=375 và gởi cho Alice. Lúc này Alice tính:
và đưa D cho Bob. Bob xác minh:
Nếu đúng thì Bob tin người liên hệ với mình chính là Bob.
Sơ đồ chữ ký Guillou-Quisquater
Sơ đồ định danh có thể biến thanh sơ đồ chữ ký, nên rất thuận lợi để thực hiện trong thẻ thông minh. Khóa mật và khóa công khai không thay đổi. Sơ đồ chữ ký được miểu tả như sau:
Alice chọn số ngẫu nhiên r, trong khoảng 1 đến n-1. Cô ta tính .
Alice tính , ở đây M là bức điện, còn H(x) là hàm băm. Giá trị d nhận được với sự hổ trợ của hàm băm cần phải nằm trong khoảng từ 0 đến v-1. Nếu như đầu ra của hàm băm vượt quá khoảng đó, thì cần phải thực hiện phép tính modulo v.
Alice tính . Chữ ký bao gồm bức điện M, hai giá trị d và D và các thuộc tính của Alice J. Alice gởi chữ ký cho Bob.
Bob tính. Sau đó Bob tính. Nếu như d=d’ thì chữ ký là hợp lệ.
Phương trình kiểm tra chữ ký là đúng:
Sơ đồ chữ ký tập thể Guillou-Quisquater 
Nếu như một số người muốn ký lên một bức điện. Chúng ta xem trường hợp đơn giản là Alice và Bob là hai người ký lên bức điện, còn Davic là người kiểm tra chữ ký, còn trong thực tế có thể có sự tham gia của nhiều người. Giống như sơ đồ ký đơn, ở đây Alice và Bob có cặp khóa công khai và mật v và B: (vA,BA) và (vB,BB). Giá trị n và J là chung cho cả hệ thống.
Alice chọn ngẫu nhiên số nguyên nằm trong đoạn 1 đến n-1. Cô tính và gởi cho Bob.
Bob chọn ngẫu nhiên số nằm trong đoạn 1 đến n-1. Anh ta tínhvà gởi cho Alice.
Alice và Bob mỗi người tính .
Alice và Bob mỗi người tính d=H(M,T), ở đây M là bức điện, còn H(x) là hàm băm. Giá trị d nhận được từ hàm băm, cần phải nằm trong khoảng từ 0 đến v-1. Nếu như giá trị hàm băm vượt quá khoảng trên thì cần thực hiện phép tính cho modulo v.
Alice tính và gởi cho Bob.
Bob tính và gởi cho cho Alice.
Alice và Bob mỗi người tính . Chữ ký bao gồm bức điện M và hai giá trị d và D và giá trị J của Alice và Bob.
Davic tính .
Davic tính . Sau đó tính . Nếu như d=d’, thì chữ ký là hợp lệ.
Sơ đồ này có thể mở rộng ra số lượng người ký bất kỳ. Đối với bức điện cần phải nhân các giá trị Ti ở bước 3 và các gía trị Di ở bước 7. Để kiểm tra tập chữ ký, trên tầng 8 cần nhân các giá trị vi. Chữ ký hợp lệ khi tất cả các chữ ký thành phần đúng, và không hợp lệ nếu tồn tại một chữ ký thành phần không hợp lệ.
Biến đổi sơ đồ định danh và chữ ký Guillou-Quisquater 
Trong sơ đồ định danh Guillou- Quisquater tham số công cộng được tính theo công thức:, với J là số nguyên tố. Thì ở đây chúng ta chọn J là những thông tin định danh của Alice (ID) (thường thì họ dùng giá trị hàm băm của ID) và TA chọn khóa công khai v, sau đó tính khóa mật B được tính thỏa mãn phương trình:. Chú ý chỉ có TA mới có thể tính được khóa mật B. 
Giao thức được miêu tả như sau:
Alice chọn số nguyên ngẫu nhiên r, nằm trong khoảng 1 đến n-1. Alice tính và gởi T và dấu xác nhận C(Alice) cho Bob.
Bob xác minh chữ ký của TA bằng cách kiểm tra điều kiện sau có đúng hay không: verifyTA(ID(Alice), v,signTA(ID, v))=true?
Bob chọn số nguyên ngẫu nhiên d nằm trong khoảng 0 đến v-1. Và Bob gởi d cho Alice.
Alice tính và gởi cho Bob.
Bob tính . Nếu như thì sự chân thực của Alice được chứng minh.
Sơ đồ chữ ký:
Alice chọn số ngẫu nhiên r, trong khoảng 1 đến n-1. Cô ta tính .
Alice tính , ở đây M là bức điện, còn H(x) là hàm băm. Giá trị d nhận được với sự hổ trợ của hàm băm cần phải nằm trong khoảng từ 0 đến v-1. Nếu như đầu ra của hàm băm vượt quá khoảng đó, thì cần phải thực hiện phép tính modulo v.
Alice tính . Chữ ký bao gồm bức điện M, hai giá trị d và D và các thuộc tính của Alice J. Alice gởi chữ ký cho Bob.
Bob tính. Sau đó Bob tính. Nếu như d=d’ thì chữ ký là hợp lệ.
Sơ đồ chữ ký tập thể, tương tự như trên chúng ta xem trường hợp đơn giản đối với tập thể có hai người.
Alice chọn ngẫu nhiên số nguyên nằm trong đoạn 1 đến n-1. Cô tính và gởi cho Bob.
Bob chọn ngẫu nhiên số nằm trong đoạn 1 đến n-1. Anh ta tínhvà gởi cho Alice.
Alice và Bob mỗi người tính .
Alice và Bob mỗi người tính d=H(M,T), ở đây M là bức điện, còn H(x) là hàm băm. Giá trị d nhận được từ hàm băm, cần phải nằm trong khoảng từ 0 đến v-1. Nếu như giá trị hàm băm vượt quá khoảng trên thì cần thực hiện phép tính cho modulo v.
Alice tính và gởi cho Bob.
Bob tính và gởi cho cho Alice.
Alice và Bob mỗi người tính . Chữ ký bao gồm bức điện M và hai giá trị d và D và giá trị J của Alice và Bob.
Davic tính .
Davic tính . Sau đó tính . Nếu như d=d’, thì chữ ký là hợp lệ.
Sơ đồ định danh Schnorr
Độ an toàn của sơ đồ định danh và sơ đồ chữ ký Schnorr dựa vào độ khó tính toán logarith rời rạc. Để tạo ra cặp khóa đầu tiên chọn 2 số nguyên tố p và q là ước số của p-1. Sau đó chọn a, sao cho: và. Tất cả các số này đều công khai.
Để tạo cặp khóa, thì chọn số ngẫu nhiên s làm khóa mật, s nhỏ hơn q. Và từ đây tính ra khóa công khai v:. Thông tin định danh và khóa công khai của Alice được TA chứng nhận và đưa vào dấu xác nhận:
C(Alice)=(ID(Alice), v,signTA(ID, v)).
Sơ đồ định danh được miêu tả như sau:
Alice chọn ngẫu nhiên số r, nhỏ hơn q và tính và gởi x và dấu xác nhận C(Alice) cho Bob.
Bob kiểm tra dấu xác thực nhờ thuật toán của TA: verifyTA(ID(Alice), v,signTA(ID, v))=true?
Bob gởi cho Alice số ngẫu nhiên e nằm trong khoảng từ 0 đến . Gởi e cho Alice.
Alice tính và gởi y cho Bob.
Bob kiểm tra đẳng thức sau có đúng không: .
Độ an toàn của thuật toán phụ thuộc vào tham số t. Độ phức tạp để phá thực toán bằng . Schnorr khuyến cáo chọn p khoảng 512 bít còn q khoảng 140 bít còn t=72.
Ví dụ: Giả sử p=88667, q=1031, t=10. Phần tử a=70322 có bậc q thuộc . Giả sử số mật s của Alice là 755. Khi đó:
Giả sử Alice chọn r=543, sau đó cô ta tính:
Và Alice gởi x cho Bob. Giả sử Bob chọn số e=1000 và gởi cho Alice. Khi đó Alice tính:
Alice gởi y cho Bob. Bob xem đẳng thức sau có đúng không
Nếu đẳng thức trên đúng thì Bob tin rằng người liên lạc với mình chính là Alice.
Chú ý: Biến sơ đồ định danh Schnorr thành chữ ký, sơ đồ chữ ký Schnorr đã được trình bày trong chương chữ ký số.
Sơ đồ định danh và chữ ký Okamoto
Sơ đồ định danh Okamoto
Độ an toàn của sơ đồ định danh và sơ đồ chữ ký Schnorr dựa vào độ khó tính toán logarith rời rạc. Để tạo ra cặp khóa đầu tiên chọn 2 số nguyên tố p và q là ước số của p-1. Sau đó chọn a, sao cho: và. Tất cả các số này đều công khai.
Để tạo cặp khóa, thì chọn số ngẫu nhiên s làm khóa mật, s nhỏ hơn q. Và từ đây tính ra khóa công khai v:. Thông tin định danh và khóa công khai của Alice được TA chứng nhận và đưa vào dấu xác nhận:
C(Alice)=(ID(Alice), v,signTA(ID, v)).
Sơ đồ định danh được miêu tả như sau:
Alice chọn ngẫu nhiên số r, nhỏ hơn q và tính và gởi x và dấu xác nhận C(Alice) cho Bob.
Bob kiểm tra dấu xác thực nhờ thuật toán của TA: verifyTA(ID(Alice), v,signTA(ID, v))=true?
Bob gởi cho Alice số ngẫu nhiên e nằm trong khoảng từ 0 đến . Gởi e cho Alice.
Alice tính và gởi y cho Bob.
Bob kiểm tra đẳng thức sau có đúng không: .
Độ an toàn của thuật toán phụ thuộc vào tham số t. Độ phức tạp để phá thực toán bằng . Schnorr khuyến cáo chọn p khoảng 512 bít còn q khoảng 140 bít còn t=72.
Ví dụ: Giả sử p=88667, q=1031, t=10. Phần tử a=70322 có bậc q thuộc . Giả sử số mật s của Alice là 755. Khi đó:
Giả sử Alice chọn r=543, sau đó cô ta tính:
Và Alice gởi x cho Bob. Giả sử Bob chọn số e=1000 và gởi cho Alice. Khi đó Alice tính:
Alice gởi y cho Bob. Bob xem đẳng thức sau có đúng không
Nếu đẳng thức trên đúng thì Bob tin rằng người liên lạc với mình chính là Alice.
Nên Bob tin rằng người giao tiếp với mình là Alice.
Định lý: Nếu Davic biết được giá trị . Thì Alice và Davic kết hợp để tính trong thơi gian đa thức với xác suất thành công là 1-1/q.
Sơ đồ chữ ký Okamoto
Các tham số chọn tương tự như sơ đồ định danh Okamoto. Sơ đồ chữ ký được miêu tả như sau:
Alice chọn hai số ngẫu nhiên và tính:.
Alice tính giá trị hàm băm H(x) với đối số làvà bức điện M: r=H(M, ).
Alice tính:
và chữ ký bao gồm r và . Alice chuyển chữ ký cho Bob.
Bob tính: và giá trị hàm băm H(x):r’=H(M, ). Nếu như r=r’ thì chữ ký hợp lệ.