Báo Cáo Bài Tập Lớn
Môn: An Toàn Bảo Mật Thông Tin

Đề Tài : Tìm Hiểu Về Sơ Đồ Xưng Danh
Guillou Quisquater
GV HD:
SV TH:

I. TÌM HIỂU VỀ SƠ ĐỒ XƢNG
DANH

A. Sơ đồ xƣng danh là gì ?
• Xưng danh và xác nhận danh tính là thuật ngữ
ngày nay được nhắc đến rất nhiều, nó đảm bảo
rằng bên nhận văn bản đúng là bên ta định
nhằm tới, hay chắc chắn rằng các thao tác
trên văn bản là do bên được phép thực hiện.
Cho đến giữa những năm 1970 người ta vẫn
còn cho rằng xưng danh và xác nhận danh tính
với mã hóa thực chất cùng là một mục tiêu an
toàn thông tin. • Nhưng cùng với khám phá ra hàm băm, chữ ký
điện tử, người ta nhận ra rằng đó là hai mục
tiêu an toàn thông tin, đặc biệt là khi các hoạt
động này thông qua mạng. Mục tiêu an toàn
của việc xưng danh là đảm bảo sao cho khi
“nghe” một chủ thể U nào đó xưng danh với
chủ thể V. Bất kỳ ai khác U cũng không thể
sau đó mạo nhận mình là U.

khác do Guillou và Quisquater đưa ra , nhưng
không phải là bài toán tính loogarit rời rạc mà là
bài toán dựa trên RSA. Việc thiết lập sơ đồ như
sau: TA chọn 2 số nguyên tố p và q và lập tích n
=pq. Giá trị của p và q được giữ bí mật trong khi
n công khai. Giống như trước đây, p và q nên
chọn đủ lớn để việc phân tích n không thể thực
hiện được. Cũng như vậy, TA chọn số nguyên tố
đủ lớn b giữ chức năng tham số mật như số mũ
mật trong RSA. Giả thiết b là số nguyên tố dài 40
bít. Cuối cùng TA chọn sơ đồ chữ kí và hàm hash 1. Hệ mật mã RSA • Mô tả sơ lƣợc
Thuật toán được Ron Rivest, Adi Shamir và Len
Adleman mô tả lần đầu tiên vào năm 1977 tại Học
viện Công nghệ Massachusetts (MIT).
Thuật toán RSA có hai khóa: khóa công khai (hay
khóa công cộng) và khóa bí mật (hay khóa cá nhân).
Mỗi khóa là những số cố định sử dụng trong quá trình
mã hóa và giải mã. Khóa công khai được công bố
rộng rãi cho mọi người và được dùng để mã hóa.
Những thông tin được mã hóa bằng khóa công khai
chỉ có thể được giải mã bằng khóa bí mật tương ứng.
Nói cách khác, mọi người đều có thể mã hóa nhưng
chỉ có người biết khóa cá nhân (bí mật) mới có thể
giải mã được.

gửi. Bob sẽ tính c là bản mã hóa của m theo công
thức: C = m
e
mod n
• Hàm trên có thể tính dễ dàng sử dụng phương
pháp tính hàm mũ (theo môđun) bằng (thuật toán
bình phương và nhân) Cuối cùng Bob gửi c cho
Alice.

• Alice nhận c từ Bob và biết khóa bí mật d. Alice có thể tìm
được m từ c theo công thức sau: • Biết m, Alice tìm lại M theo phương pháp đã thỏa thuận trước. Quá trình
giải mã hoạt động vì ta có • Do ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), (theo Định lý Fermat nhỏ) nên:
và

Do p và q là hai số nguyên tố cùng nhau, ta có:.

hay

Giải mã
ví dụ



• Thuật toán bình phương và nhân là thuật
toán tính nhanh lũy thừa tự nhiên của một số
(thực hoặc nguyên), trong trường hợp cơ số là
số nguyên có thể được rút gọn theo
một môđun nào đó.
• Phép nâng lên lũy thừa tự nhiên bậc n của số x
(x được gọi là cơ số) được định nghĩa từ hệ
thức

• Với n lớn số phép nhân là rất lớn.
• Chắng hạn với n=35 quá trình tính x35 qua 35
bước:

• Ta nhận xét rằng có thể giảm bớt số phép nhân
chẳng hạn với dãy phép tính

Công thức đệ quy
• Quá trình tính toán trên chính là quá trình tính
nhờ công thức đệ quy
• Với n=0 thì xn = 1
• Với n>0 ta có công thức • Như vậy phép tính xn được quy về một số
phép bình phương và phép nhân do vậy mà có
tên gọi thuật toán bình phương và nhân

Giải thuật sau tính đệ quy x
n


Tổng kết

• Dù là hệ mã công khai xuất hiện đầu tiên , nhưng
cho đến nay hệ mã RSA vẫn cho thấy là một hệ
mã rất an toàn . Tính an toàn của nó dựa trên bài
toán Phân tích số nguyên .Mà thuật toán phân tích
một số nguyên m thành thừa số lại cần đến một
thời gian tăng theo cấp số luỹ thừa so với chiều
dài của m . Nghĩa là nếu chỉ thêm cho mvài ký tự,
thời gian cần để đặt m thành thừà số sẽ tăng gấp
đôi. Vì khi thêm vài ký tự vào R là làm cho nó lớn
thêm hàng trăm hay ngàn lần nhiều hơn, tức là gia
tăng danh sách các cặp thừa số có thề dùng làm p
và q.
Cơ chế hoạt động của sơ đồ xƣng
danh guillou-quisquater
• Sơ đồ cũng cần có sự tham gia của một cơ quan
ủy thác (TA). Để cấp chứng chỉ cho các người
tham gia. TA chọn 2 số nguyên tố lớn p và q và
tính tích n=p.q, giữ bí mật p, q và công khai n.
Các tham số đó được chọn sao cho bài toán phân
tích n thành thừa số là rất khó. TA cũng chọn
thêm một số b là số nguyên tố có độ lớn khoảng
2
40
như là một tham số an toàn. Sô b cũng được
xem là số mũ thỏa mãn điều kiện RSA, nghĩa là
việc tính v=u
b


Xưng danh

• Bây giờ, với chứng chỉ C(A) đó, A có thể xưng danh
với bất kỳ đối tác B nào bằng cách cùng B thực hiện
một giao thức xác nhận danh tính như sau :
• A chọn thêm một số ngẫu nhiên k(0 ≤ k ≤ n-1), tính
γ = k
b
mod n,
và gửi cho B các thông tin C(A) và γ.
• 2.B kiểm thử chữ ký của TA trong chứng chỉ C(A)
bởi hệ thức
• ver
TA
(ID(A), v, s)= đúng. kiểm thử xong, B chọn một
số ngẫu nhiên r(1 ≤ r ≤ b-1) và gửi r cho A.
• 3.A tính y=k.u
r
mod n và gửi y cho B
• 4.B thử điều kiện
γ ≡ v
r1
y
b
1
(mod n).
• Và nếu điều kiện dó được thỏa mãn thì xác nhận danh
tính của A.


thức xác nhận để có thể được mạo nhận là A, chẳng hạn ít
nhất 2 lần. Điều đó có nghĩa là O biết được hai số
• r
1
≠ r
2
và hai số y
1
,y
2
sao cho
γ ≡ v
r1-r2
≡ v
r2
y
b
2

(mod n).
• Giả thiết r
1
> r
2
, khi đó ta có
V
r1-r2
≡ (y
2
/y

(mod n).
• Do t=(r
1
-r
2
)
-1
mod b nên ta có
(r
1
-r
2
)t=lb+1
• Với l là 1 số nguyên tố dương nào đó, vì vaatyj,
V
lb+1
≡ (y
2
/y
1
)
bt
(mod n),
• Hay là
V ≡ (y
2
/y
1
)
bt

TA
(ID(A), v) và cấp cho A
chứng chỉ
C(A) = (ID(A),v,s).
• Giả thiết A muốn xưng danh với B, A chọn k=
187485, và gửi cho B giá trị
γ =187485
503
mod 223693 =24412.
• B dùng thuật toán kiểm thử ver
TA
để thử điều
kiện ver
TA
(ID(A),v,s) = đúng, sau đó gửi đến
đến A câu hỏi r=375. A sẽ trả lời lại bằng
y = 187485.101576
375
mod 223693
• = 93725.
• B thử điều kiện γ ≡ v
r
y
b
(mod n), trong trường
hợp này là
24412 ≡ 89888
375
.93725
503