
Ch ng 10ươ
S Đ Đ NH DANHƠ Ồ Ị
10.1 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.ạ ẻ
10.2 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 Aộ ậ ờ lice 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*=EủK(R), n u nh C*=C thì ch ng nh n bên Bob. Aliceế ư ứ ậ
th c hi n mã hóa R’: C’=Eự ệ K(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”=EủK(R’), bên Bob so sánh n u nh C’=C” thì ch ng th c bên Alice.ế ư ứ ự
10.3 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 .ả ượ ậ ằ ế ủ ỹ
10.3.1 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: ọ ỏ ươ
)(mod
2nvx ≡
có nghi m và t n t iệ ồ ạ
)(mod
1nv−
. v là tham s m c a Alice. Sau đó tính giá tr nh nh t s, sao choố ở ủ ị ỏ ấ
)(mod
1nvs −
≡
. 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(signượ ằ ữ ủ TA) 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.ơ ồ ị ượ ả ư
1. Alice ch n s ng u nhiên r, nh h n n. Sau đó cô ta tính ọ ố ẫ ỏ ơ
)(mod
2nrx −=
và g i xở
và d u xác th c C(Alice) cho Bob.ấ ự
2. 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?
3. Bob g i cho Alice m t bít ng u nhiên b.ở ộ ẫ
4. 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).
5. N u b=0, Bob ki m tra đ ng th c: ế ể ẳ ứ
)(mod
2nrx −=
, vì tin t ng r ng ch Aliceưở ằ ỉ
bi t gía tr c a ế ị ủ
)(mod nvs ≡
. T ng t n u b=1 thì Bob ki m tra đ ng th c:ươ ự ế ể ẳ ứ
)(mod*
2nvyx =
vì ch có Alice m i bi t giá tr ỉ ớ ế ị
)(mod
1nvs −
≡
.
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àầ
t
)2/1(
.
Đ 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 .ẽ ượ ị ừ ơ ồ ị ỡ
10.3.2 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: ở ậ ỏ ậ ớ ể ạ ị
k
vvv ,...,, 21
, ở
đây
i
v
là th ng d b c hai theo modulo n. Hay nói cách khác ặ ư ậ
i
v
đ c ch n sao cho th aượ ọ ỏ
mãn ph ng trình: ươ
)(mod
2nvx i
≡
có nghi m và t n t i ệ ồ ạ
)(mod
1nvi
−
. Các giá tr ị
k
vvv ,...,, 21
là
công khai c a Alice. Sau đó tính giá tr nh nh t ủ ị ỏ ấ
i
s
th a mãnỏ
)(mod
1nvs ii
−
≡
. Dãy giá trị
k
sss ,...,, 21
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(signư ủ ượ ằ ữ ủ TA) và thu t toánậ
ki m tra ch ký c a TA (verifyể ữ ủ TA) và đ a ra d u xác nh n cho Alice:ư ấ ậ
C(Alice)=(ID(Alice),
k
vvv ,...,, 21
,signTA(ID,
k
vvv ,...,, 21
)).
Giao th c đ c th c hi n nh sauứ ượ ự ệ ư :
1. Alice ch n s ng u nhiên r, nh h n n. Sau đó cô tính ọ ố ẫ ỏ ơ
)(mod
2nrx −=
và g i x vàở
d u xác th c C(Alice) cho Bob.ấ ự
2. 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),
k
vvv ,...,, 21
,signTA(ID,
k
vvv ,...,, 21
))=true?
3. Bob g i cho Alice m t dãy k bít: ở ộ
k
bbb ,...,, 21
.
4. Alice tính
))(mod*...**(* 21
21 nsssry k
b
k
bb
=
và g i y cho Bob.ở
5. Bob ki m tra ể
))(mod*...**(* 21
21
2nvvvyx k
b
k
bb
=
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 ế ố
k
sss ,...,, 21
.
Xác su t đ Alice không bi t day s ấ ể ế ố
k
sss ,...,, 21
mà l a thành công Bob qua t l n làừ ầ
kt
2/1
. 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 sịi t ng ng là {3,4,9,8}.ươ ứ
1. Alice ch n ọ
16=r
, và tính 162 mod 35=11, và g i 11 cho Bob.ở
2. Bob g i cho Alice dãy bít:{1,1,0,1}.ở
3. Alice tính 16*(31*41*90*81) mod 35 =31 và g i 31 cho Bob.ở
4. Bob ki m tra 31ể2*(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 ạ ị
k
vvv ,...,, 21
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 ứ ạ ố
k
vvv ,...,, 21
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 ế ướ ủ ứ ự ố
k
vvv ,...,, 21
t H(ID,j).ừ
10.3.3 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 ố ố ớ ạ ở
k
vvv ,...,, 21
và tính khóa m tậ
k
sss ,...,, 21
, đâyở
)(mod
1nvs ii
−
≡
. S đ ch ký đ c miêu t nh sau:ơ ồ ữ ượ ả ư
1. Alice ch n t s nguyên trong kho ng t 1 đ n n: ọ ố ả ừ ế
t
rrr ,...,, 21
và tính các giá trị
t
xxx ,...,, 21
, v i ớ
)(mod
2nrx ii ≡
.
2. Alice tính giá tr hàm băm, đ i s c a nó là liên k t xị ố ố ủ ế i và b n tin m, đ t o thànhả ể ạ
dòng bít: H(m,
t
xxx ,...,, 21
). 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 bảij, i=1,t còn j=1,k.
3. Alice tính các giá tr ị
t
yyy ,...,, 21
, đây ở
))(mod*...**(* 21
21 nsssry ikii b
k
bb
ii =
.
4. Alice g i cho Bob m, t t c các bít bở ấ ả ij và t t c giá tr yấ ả ị i. Và Bob có đ c cácượ
khóa m c a Alice ở ủ
k
vvv ,...,, 21
.
5. Bob tính các giá tr ị
t
zzz ,...,, 21
, đây ở
))(mod*...**(* 21
21
2nvvvyz ikii b
k
bb
ii =
. Chú ý r ngằ
zi c n ph i b ng xầ ả ằ i.
6. Bob tính giá tr c a dong bít: H(m, ị ủ
t
zzz ,...,, 21
)- 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 bể ớ ớ ị ij 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 ươ ự ư ơ ồ ị ơ ồ ộ ỉ ệ ớ
kt
2/1
. 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 ọ ố
k
vvv ,...,, 21
là k s nguyên t đ u tiên.ố ố ầ
10.4 S đ đ nh danh ơồị và s đ ch ký Guillou-Quisquater ơ ồ ữ
10.6.1 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:ứ
)(mod)( 1nBv J−
=
. 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ứ ượ ả ư :
1. Alice ch n s nguyên ng u nhiên r, n m trong kho ng 1 đ n n-1. Alice tínhọ ố ẫ ằ ả ế
)(mod nrT J
=
và g i T và d u xác nh n C(Alice) cho Bob.ở ấ ậ
2. 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?
3. 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.
4. Alice tính
)(mod nrBD d
=
và g i cho Bob.ở
5. Bob tính
)(mod' nvDT dJ
=
. N u nh ế ư
)(mod' nTT ≡
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:ậ
89888
)223693(mod)101575(
)(mod)(
5031
1
=
=
=
−
−nBv J
Gi s Alice ch n r=187485, sau đó Alice tính giá tr :ả ử ọ ị
24412
)223693(mod187485
)(mod
503
=
=
=nrT J

