Phát triển lược đồ chữ ký số mù
Hội Thảo Quốc Gia 2015 về Điện tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
PHÁT TRIỂN LƯỢC ĐỒ CHỮ KÝ SỐ MÙ
Nguyễn Tiền Giang, Nguyễn Đức Thụy, Lưu Hồng Dũng.
Cục Công Nghệ Thông Tin – Bộ QP, Trường Cao Đẳng Kinh Tế - Kỹ Thuật Thành Phố Hồ Chí Minh,
Khoa Công Nghệ Thông Tin. Học Viện Kỹ Thuật Quân Sự.
Lược đồ chữ ký số mù RSA được phát triển từ lược đồ chữ
ký số RSA [6]. Lược đồ chữ ký số mù RSA có thể mô tả như
sau: Giả sử A là người ký có khóa bí mật (d), công khai (n,e)
được hình thành theo lược đồ chữ ký RSA. B là người tạo ra
bản tin M và yêu cầu A ký lên M (người yêu cầu ký). Để che
dấu danh tính của B sau khi bản tin M đã được ký, thủ tục
hình thành chữ ký (“ký mù”) được thực hiện qua các bước như
sau:
Tóm tắt— Bài báo đề xuất xây dựng 2 lược đồ chữ ký số mù
từ việc phát triển lược đồ chữ ký số trên cơ sở bài toán
logarithm rời rạc. Các lược đồ mới đề xuất ở đây có mức
độ an toàn cao hơn về khả năng chống tấn công làm lộ
nguồn gốc của bản tin được ký so với một số lược đồ đã
biết trước đó trong thực tế
.
Từ khóa- Digital Signature, Blind Signature, Digital
Signature Scheme, Blind Signature Scheme.
Bước 1: B làm “mù” bản tin M bằng cách chọn ngẫu nhiên
một giá trị k thỏa mãn: 1< k < n và k nguyên tố cùng nhau
với n (gcd(k,n) = 1), sau đó B tính: m'= m × ke modn , ở
đây: m = H(M ) là giá trị đại diện của bản tin cần ký M và
I.
ĐẶT VẤN ĐỀ
Khái niệm chữ ký số mù được đề xuất bởi D. Chaum vào
năm 1983 [1], đây là một loại chữ ký số được sử dụng để xác
thực tính toàn vẹn của một bản tin điện tử và danh tính của
người ký, nhưng không cho phép xác thực nguồn gốc thực sự
của bản tin được ký. Nói cách khác, loại chữ ký này cho phép
ẩn danh người tạo ra bản tin được ký. Trong [2-4] đã chỉ ra
ứng dụng của loại chữ ký này khi cần bảo vệ tính riêng tư của
các khách hàng trong các hệ thống thanh toán điện tử hay vấn
đề ẩn danh của cử tri trong việc tổ chức bầu cử trực tuyến [5].
Một điểm cần chú ý ở đây là, với các loại chữ ký số thông
thường thì người ký cũng chính là người tạo ra bản tin được
ký, còn với chữ ký số mù thì người ký và người tạo ra bản tin
được ký là 2 đối tượng hoàn toàn khác nhau. Đây là tính chất
đặc trưng của chữ ký số mù và cũng là một tiêu chí quan trọng
để đánh giá mức độ an toàn của loại chữ ký số này.
Trong [1-5] các tác giả đã đề xuất một số lược đồ chữ ký số
mù ứng dụng khi cần bảo vệ tính riêng tư của các khách hàng
trong các hệ thống thanh toán điện tử hay vấn đề ẩn danh của
cử tri trong việc tổ chức bầu cử trực tuyến. Tuy nhiên, điểm
yếu chung của các lược đồ trên là không có khả năng chống lại
kiểu tấn công làm lộ nguồn gốc của bản tin được ký, vì thế khả
năng ứng dụng của các lược đồ này trong thực tế là rất hạn chế.
Nội dung bài báo tập trung phân tích điểm yếu có thể tấn công
làm lộ nguồn gốc bản tin được ký của một số lược đồ chữ ký số
mù đã được công bố, từ đó đề xuất xây dựng một lược đồ mới
có độ an toàn cao hơn về khả năng giữ bí mật nguồn gốc của
bản tin được ký có thể đáp ứng các yêu cầu mà thực tế đặt ra.
H(.) là hàm băm kháng va chạm. B gửi bản tin đã được làm
mù (m’) cho A.
Bước 2: A sẽ ký lên m’ bằng thuật toán ký của lược đồ
RSA: s'= (m')d modn rồi gửi lại s’ cho B.
Bước 3: B “xóa mù” s’ và nhận được chữ ký s như sau:
s = s'×k−1 modn
.
Việc kiểm tra tính hợp lệ của s và do đó là tính toàn vẹn
của M được thực hiện như ở lược đồ RSA. Vấn đề ở đây là,
một đối tượng bất kỳ có thể kiểm tra tính hợp lệ của s, từ đó
khẳng định tính toàn vẹn của M và danh tính người ký bằng
thuật toán kiểm tra RSA, nhưng không thể xác định được bản
tin M là do ai tạo ra. Nghĩa là danh tính của B đã được giấu
kín.
2.1.2. Tấn công làm lộ nguồn gốc bản tin được ký
Với lược đồ chữ ký số mù RSA như đã mô tả ở trên, việc
xác định danh tính của người tạo ra bản tin được ký M là có
thể thực hiện được. Bởi vì tại thời điểm ký, người ký (A) chỉ
không biết nội dung của M, nhưng danh tính của B thì A hoàn
toàn biết rõ, điều này là hiển nhiên vì A chỉ ký khi biết rõ B là
ai. Giả sử danh tính của B được ký hiệu là IDB, để xác định
danh tính của người yêu cầu ký từ bản tin M và chữ ký s tương
ứng sau thời điểm ký (khi M và s đã được công khai), ở mỗi
lần ký chỉ cần A lưu trữ giá trị s’ và IDB trong một cơ sở dữ
liệu. Từ đó, việc xác định danh tính của người yêu cầu ký -
IDB từ bản tin được ký M và chữ ký s là hoàn toàn có thể thực
hiện được bằng một thuật toán như sau:
Thuật toán 1.1:
II. TẤN CÔNG LÀM LỘ NGUỒN GỐC BẢN TIN ĐỐI
VỚI MỘT SỐ LƯỢC ĐỒ CHỮ KÝ SỐ MÙ.
Input: (M,s), {(si’, IDBi)| i=0,1,2,…N}.
Output: IDBi.
[1].
, i = 0
m ← H (M )
2.1. Tấn công lược đồ chữ ký số mù RSA
2.1.1. Lược đồ chữ ký số mù RSA
Hội Thảo Quốc Gia 2015 về Điện tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Output: IDBi.
[2]. select: (si ', IDBi )
[1].
, i = 0
m ← H (M )
k∗ ← si '×m−d modn
[3].
[2]. select:
(
Ri ',mi ', si ', IDBi )
[4]. if gcd(k∗,n) ≠ 1 then
[3].
α
β
← mi '×m−1 × r × −1 mod q
R'
s − si '×r ×
× gβ mod p
[4.1]. i ← i +1
[4.2]. goto [2]
−1
)
← m−1 ×
(
R'
modq
[4].
[5].
[6].
s∗ ← si '×(k∗ )−1 modn
α
[5].
R ←
(
Ri '
)
[6]. if (s∗ ≠ s) then
r∗ ← Rmodq
[7]. if
(
r∗ ≠ r
)
then
[6.1]. i ← i +1
[6.2]. goto [2]
[7]. return IDBi
Nhận xét:
[7.1]. i ← i +
[7.2]. goto [2]
[8]. return IDBi
Nhận xét:
1
Từ Thuật toán 1.1 cho thấy, nếu N không đủ lớn thì việc
xác định được danh tính của người yêu cầu ký (người tạo ra
bản tin được ký) là hoàn toàn có thể thực hiện được. Nói cách
khác, lược đồ chữ ký số mù RSA là không an toàn nếu số
lượng bản tin được ký không đủ lớn.
Tương tự như với lược đồ chữ ký mù RSA, từ Thuật toán
1.2 cho thấy, nếu N không đủ lớn thì việc xác định được danh
tính của người yêu cầu ký (người tạo ra bản tin được ký) là
hoàn toàn có thể thực hiện được. Nói cách khác, lược đồ chữ
ký số mù DSA cũng sẽ không an toàn xét theo khía cạnh
chống tấn công làm lộ nguồn gốc bản tin nếu số lượng bản tin
được ký không đủ lớn.
2.3. Tấn công lược đồ chữ ký số mù Nyberg-Rueppel
2.3.1. Lược đồ chữ ký số Nyberg-Rueppel
Tham số hệ thống của lược đồ chữ ký số do K. Nyberg và
R. A. Rueppel đề xuất [7] được lựa chọn tương tự như ở lược
2.2. Tấn công lược đồ chữ ký số mù DSA
2.2.1. Lược đồ chữ ký số mù DSA
Từ lược đồ chữ ký số DSA [8], nhóm tác giả Jan L.
Camenisch, Jean-Marc Piveteau, Markus A. Stadler đề xuất
một lược đồ chữ ký số mù [8] với thủ tục hình thành tham số
hệ thống bao gồm một số nguyên tố p, một số nguyên tố q là
ước của (p-1) và phần tử sinh g ∈ Z *p có bậc là q. Người ký
đồ DSA. Để ký lên một bản tin M có giá trị đại diện m ∈ Zp
,
có khóa bí mật x ∈ Zq và khóa công khai tương ứng là
x
người ký chọn ngẫu nhiên một giá trị
và tính:
k ∈ Zq
. Thủ tục hình thành chữ ký “mù” bao gồm các
y = g mod p
bước như sau:
r = m × gk mod p
s = k + x.r mod q
1. a) Người ký (A) chọn một giá trị k ∈ Zq và tính
R' = gk mod p
Chữ ký lên bản tin M ở đây là cặp (r,s). Chữ ký được coi là
hợp lệ nếu thỏa mãn phương trình kiểm tra:
b) A kiểm tra nếu
thì thực hiện lại bước
gcd(R', q) ≠ 1
m = y−s × gr × r mod p
a). Ngược lại, A gửi R cho người yêu cầu ký (B).
2. a) Người yêu cầu ký B chọn 2 giá trị
Ở đây
m
là giá trị đại diện của bản tin cần thẩm tra M:
và tính
α
,
β
∈ Zq
, với H(.) là hàm băm.
m = H(M )
α
)
× gβ mod p
.
R =
(
R'
2.3.2. Lược đồ chữ ký số mù Nyberg-Rueppel
b) B kiểm tra nếu
thì tính tiếp giá trị
gcd(R', q) = 1
Cũng nhóm tác giả Jan L. Camenisch, Jean-Marc
Piveteau, Markus A. Stadler [8] đã đề xuất một lược đồ chữ ký
số mù được phát triển từ lược đồ chữ ký Nyberg-Rueppel với
thủ tục hình thành chữ ký “mù” bao gồm các bước như sau:
m'=
× m × R'×R−1 mod q
rồi gửi m’ cho A. Nếu
α
điều kiện chỉ ra không thỏa mãn, B thực hiện lại bước
a).
3. Người ký A tính giá trị
1. Người ký (A) chọn một giá trị k ∈ Zq và tính
rồi
s' = (k × m'+x × R') mod q
r'= gk mod p
gửi cho B.
rồi gửi cho người yêu cầu ký (B).
4. Người yêu cầu ký B tính các thành phần (r,s) của chữ
α ∈ Zq , β
∈ Zq* và tính
−1
2. a) B chọn ngẫu nhiên giá trị
ký:
,
.
s = (s'×R × R' + β × m) mod q
r = R mod q
( )
β
)
r = m × gα ×
(
r'
mod p
m'= r × β −1 modq
Thủ tục kiểm tra tính hợp lệ của chữ ký hoàn toàn tương
tự như ở lược đồ chữ ký DSA.
,
.
b) B kiểm tra nếu m'∈ Zq* thì gửi m’ cho người ký A.
2.2.2. Tấn công làm lộ nguồn gốc bản tin được ký
Để tấn công làm lộ nguồn gốc bản tin được ký M, người
ký A cần lưu trữ giá trị các tham số {R’,m’,s’} và IDB ở mỗi
lần ký. A có thể xác định được danh tính của B bằng Thuật
toán 1.2 như sau:
Ngược lại, B thực hiện lại bước a).
3. A tính giá trị
rồi gửi cho B.
s'= (k + x ×m') modq
4. B tính
và chữ ký của A lên M là
s = (s'×
β + α) mod q
cặp (r,s).
Thuật toán 1.2:
Input: (M,r,s), {(Ri’, mi’,si’,IDBi)| i=0,1,2,…N}.
Hội Thảo Quốc Gia 2015 về Điện tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
e∗ = FH (T ∗ || M )
ị:
Thủ tục kiểm tra tính hợp lệ của chữ ký tương tự như ở
lược đồ chữ ký Nyberg-Rueppel. Nghĩa là: chữ ký (r,s) được
coi là hợp lệ nếu thỏa mãn phương trình kiểm tra:
3. Tính giá tr
4. Ki m tra n
. Ngược l
2.4.2. T n công làm l
ể
ế
u: e∗ = e
'
thì
(
e
',
ch
s
') được công nh
ận hợp
m = y−s × gr × r mod p
lệ
ạ
i,
(
e
', s')
sẽ
b
ị
t
ừ
ố
i.
ấ
ộ
ngu
ngu
các tham s
xác định được danh tính c
ồ
n g
ố
c b
c b
{T,e,s} và IDB
a B b
ả
n tin được ký
n tin được ký M, người ký
i l n ký.
Ở đây
m là giá trị đại diện của bản tin cần thẩm tra M.
Để n công làm l
A c n l u tr giá tr
ừ đó, A có th
t
ấ
ư
ộ
ồ
n g
ố
ả
2.3.3. Tấn công làm lộ nguồn gốc bản tin được ký
Để tấn công làm lộ nguồn gốc bản tin được ký M, người ký
A cần lưu trữ giá trị các tham số {r’,m’,s’} và IDB ở mỗi lần
ký. Từ đó, A có thể xác định được danh tính của B bằng thuật
toán như sau:
ầ
ữ
ị
ố
ở mỗ ầ
T
ể
ủ
ằ
ng Thuật
toán 1.4 nh
ư
sau:
Thuật toán 1.4
:
Input: (M,e’,s’), {(ei, si,Ti, IDBi)| i=0,1,2,…N}.
Output: IDBi.
Thuật toán 1.3:
Input: (M,r,s), {(ri’, mi’,si’, IDBi)| i=0,1,2,…N}.
Output: IDBi.
[1].
, i = 0
m ← H (M )
[1].
, i = 0
m ← H (M )
[2]. select
:
(ei , si ,T , IDBi )
i
[2]. select:
(r ',mi ', si ', IDBi )
i
[3].
[4].
[5].
τ
← (e'−ei )modq
[3].
β
← r ×
mi '
( )
−1 mod q
ε
← (s'−si )mod q
[4].
[5].
T ∗ = Ti × yτ × gε mod p
α
← (s − si '×
β
)modq
β
)
r* = m × gα ×
(
r '
mod p
e∗ = FH (T∗ || M )
i
[6].
[6]. if
(
r
*
≠ r
)
then
[7]. if (
e∗ ≠ e') then
[6.1]. i ← i +
[6.2]. goto [2]
[7]. return IDBi
1
[7.1]. i ← i +
[7.2]. goto [2]
[8]. return IDBi
1
Nh
ương t
toán 1.3 cho th
không an toàn n
ó vi c xác định ngu
2.4. Tấn công lược đồ chữ ký số mù Moldovyan
2.4.1. Lượ đồ ch ký s mù Moldovyan
ây là lượ đồ ch ký s mù được N.A. Modovyvan [9]
t trên c phát tri n t chu ch ký s
th ng bao g
n t sinh
ận xét:
Nh
ương t
toán 1.4 cho th
toàn n u s ượng b
c xác định ngu n g
ận xét:
T
ự
nh
ấ
ế
ư
2 thu
y lượ
u s ượng b
n g c b
ậ
t toán ký mù
đồ ch ký mù Nyberg-Rueppel là
n tin được ký không đủ n, khi
n tin là có th th c hi được.
đã xét ở trên, Thuật
T
ự
nh
ư
các thu
ậ
t toán ký mù
đ
ã xét
ở
trên, Thuật
c
ữ
ấ
y lượ
c
đồ ch
ữ
ký mù Moldovyan là không an
n, khi
được.
ố
ồ
l
ả
ả
lớ
ế
ố
l
ả
n tin được ký (N) không đủ
c b n tin là có th th c hiện
l
ớ
đó
đ
ệ
ố
ể
ự
ện
vi
ệ
ồ
ố
ả
ể
ự
c
ữ
ố
ữ
III. ÂY D
X
Ự
NG LƯỢ ĐỒ CH KÝ S
C
Ữ
Ố
MÙ
ây
t như ở
như ở các lượ
Đ
c
ố
Qua phân tích các lượ
c
đồ ch
ữ
ký s mù trên
ố
đ
đã cho
đề xu
ấ
ơ
sở
ể
ừ
ẩ
n
ữ
ố của
thấ
y vi c làm “mù” b n tin v
ký s mù RSA, hay v
DSA, Nyberg-Rueppal và Moldovyan thì người ký v
tìm được ngu n g c th c s a b n tin được ký (danh tính
a người yêu c u ký). M c này đề xu t vi c phát tri n lượ
đồ ch ký s mù t t lượ đồ ch ký c ở được c i ti n t
ượ đồ ch ký Schnorr [13] và m t lượ đồ xây d ng trên bài
toán logarit r i r c – DLP (Discrete Logarithm Problem) [14].
m c a các lượ đồ i này là c ng ch ng 2 tham
bí m t như ở các lượ đồ mù DSA, Nyberg-Rueppal hay
Moldovyan,... nh ng không cho phép người ký hay b t k
đối tượng nào khác có th xác định được ngu n g c th
a b n tin như ở các lượ đồ đ được công b trướ ó [1-
ệ
ả
ớ
i mộ
t tham s bí m
ố
ậ
l
c
ượ
c
Belarusian STB 1176.2-9 [12]. Các tham s
ố
h
ầ
ệ
ố
ử
ồm
g ∈ Z*p
đồ ch
ữ
ố
ớ
i 2 tham s
ố
đồ
n có thể
2 s nguyên t p, q th a mãn: q|(p-1) và ph
ố
ố
ỏ
ẫ
có b
ậ
c là q. Người ký có khóa bí mật
và khóa công
x ∈ Zq
c hình thành chữ ký
ồ
ố
ự
ự
c
ủ
ả
c
ủ
ầ
ụ
ấ
ệ
ể
c
ừ
x
khai tương
ứ
ng là
. Th
ủ
t
ụ
y = g mod p
ữ
ố
ừ
m
ộ
c
ữ
ơ
s
ả
ế
“mù” bao g
1. Người ký A ch
ồ
m các bước nh
n ng
< k < q và tính
ư
ẫ
sau:
l
c
ữ
ộ
c
ự
ọ
u nhiên m
ộ
t giá tr
ị k thỏa mãn:
ờ
ạ
k
1
r
ồ
i g i T cho người
ử
T = g mod p
Ưu
đ
i
ể
ủ
c
mớ
ũ
ỉ sử dụ
yêu c
2. B ch
T'= T × y × g mod p
ây: FH(.) là hàm b
ầ
ọ
u ký B.
n ngẫu nhiên 2 giá trị τ và ϵ rồi tính:
ε
số
ậ
c
ư
ấ
ỳ
ực
τ
,
và
, ở
)modq
mộ
t
ể
ồ
ố
c đ
e'= FH (T'|| M )
e = (e'−
τ
sự
c
ủ
ả
c
ã
ố
đ
ă
m và “||” là toán t
ử nối 2 xâu bit .
5].
Sau
đ
ó B g
ử
i e cho A.
3. A tính giá tr
ị
r
ồ
i g
ử
i cho B.
3.1. Xây dựng lược đồ chữ ký cơ sở
3.1.1. Lược đồ chữ ký cơ sở LD 15.01A
s = (k − x ×e)mod q
n th 2 c a ch
a A lên M là c
m tra tính h p l
STB 1176.2-9, nh sau:
1. Ki m tra n u:
2. Ngược l
2. Tính giá tr
4. B tính thành ph
ch ký c
Th c ki
ầ
ứ
ủ
ữ
ký:
và
s'= (s +ε)modq
Lược đồ chữ ký cơ sở ở đây, ký hiệu LD 15.01A, được
cải tiến từ lược đồ chữ ký do C. Schnorr đề xuất vào năm 1991
và được sử dụng làm cơ sở để phát triển lược đồ chữ ký số mù
ở phần tiếp theo. Lược đồ chữ ký LD 15.01A bao gồm các
thuật toán hình thành tham số và khóa, thuật toán hình thành
và kiểm tra chữ ký như sau:
ữ
ủ
ặp (e', s').
ủ
t
ụ
ể
ợ
ệ của chữ ký tương tự như ở
ư
ể
ế
và
thì chuy
ể
n sang bướ
p l
c
1< s'< q
0 < e'< q
ạ
i,
(
e
',
s
')
sẽ
b
ị
t
ừ
chối v
ề
tính h
ợ
ệ.
T
=
gs
×
ye mod p
a) Thuật toán hình thành tham số và khóa
∗
'
'
ị:
Hội Thảo Quốc Gia 2015 về Điện tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
M
ứ
c
độ an toàn c
ủ
a m
ng:
n công làm l
n công gi
ng t
độ an toàn xét theo kh
t c a lượ đồ ph
a bài toán logarit r i r c, hoàn toàn tương t
các lượ đồ ch
Schnorr [13].
kh
(2.5a) và (2.6a) c
(không được t
khóa bí m t x c
là ch ký h p l
n tin M n u th
e = H((gs × ye mod p) || M)modq
ương t như ở ượ đồ ch
(2.10a) là m ng bài toán khó n
thước c a d đầu ra hàm b m H(.) được ch
3.1.2. Lượ LD 15.01B
ượ đồ ch ở đề xu ở đây, ký hi
được xây d a bài toán DLP và được s
mù trong ph n ti p theo.
và khóa
ột lược đồ chữ ký số nói chung được
Thuật toán 2.1a:
đ
ánh giá qua các khả nă
Input: p, q|(p-1), x – khóa bí mật của A.
Output: g, y, H(.).
-
-
Ch
Ch
ố
ố
ng t
ng t
ấ
ấ
ộ
khóa m
o ch
n công làm l
ậ
t.
g ← h( p−1) / q mod p
ả
ấ
m
ạ
ữ ký.
[1].
,
1< h < p
0,1 ∗
H :{ } a Zt
V
ề
kh
y m
khóa m
ả
n
ă
c
ng ch
ố
ộ
khóa mât: T
ừ (2.1a)
q < t < p
,
[2]. select
cho th
làm l
gi i c
ấ
ứ
ả
nă
ng ch ng t
ố
ấ
n công
y ← g−x mod p
ộ
ậ
ủ
c
c
ơ
s
ở
ụ
thu
ộ
c vào m
ứ
c
độ khó
[3].
(2.1a)
ả
ủ
ờ
ạ
ự
như với
[4]. return {g,y,H(.)}
c
ữ ký DSA [9] , GOST R34.10-94 [10] và
b) Thuật toán ký
V
ề
ả
n
ă
ng ch
a lượ
o ra b
a người ký) nh
đối tượng s
a mãn u ki n:
ố
ng t
ấ
n công gi
đồ cho th
i Thu t toán ký 2.2a c
ng v n sẽ được công nh
ả
m
ạ
ấ
o ch
ữ
ộ
ký: T
t c p (e,s) b
a lượ đồ và
ừ (2.3a),
ủ
ạ
ủ
c
c
c
ơ
s
ở
y, m
ặ
ất
Thuật toán 2.2a
Input: p, q, g, x, k, M – b
Output: (e,s) – ch ký c
:
k
ỳ
ở
ậ
ủ
c
ả
n tin c
ần ký.
t
ừ
ậ
ợ
ư
ẫ
ậ
n
ữ
ủa
A
lên M.
ữ
ệ
ủ
a
ở
hữ
u khóa công khai y lên
r ← gk mod p
e ← H r || M modq
s ← (k + x × e)mod q
[1].
[2].
[3].
(2.2a)
b
ả
ế
ỏ
đ
i
ề
ệ
(2.3a)
(2.4a)
(2.10a)
T
ự
l
c
ữ
ký Schnorr, có th
ể
th
p, q và kích
đủ n.
ấy rằng
[4]. return (e,s)
Chú thích:
ộ
t d
ạ
ế
u các tham s
ố
n
ủ
ữ
li
ệ
u
ă
ọ
lớ
- Toán t
c) Thu t toán ki
Thuật toán 2.3a
Input: p, q, g, y, M, (e,s).
ử
“||” ở đây là phép n
ố
i 2 xâu bit.
c
đồ ch
ữ
ký c
ơ
s
ở
ậ
ể
m tra
L
c
ữ
ký c
ơ
s
ấ
t
ệu LD 15.01B,
:
ự
ng d
ự
a trên tính khó c
n lượ đồ ch ký s
t toán hình thành tham s
Thuật toán 21b
ủ
ố
ố
ử
d
ụ
ng để phát tri
ể
c
ữ
ầ
ế
Output: (e,s) = true
/
.
false
a) Thu
ậ
s
e
[1].
[2].
(2.5a)
u ← g × y mod p
:
(2.6a)
v ← H
(
u || M
)
mod q
Input: p, q|(p-1), x – khóa bí m
Output: g, y, H(.).
ật của A.
[3]. if
else
Chú thích:
- N u k t qu
ngu n g c và tính toàn v
công nh n.
- N u k t qu
i dung b n tin M
d) Tính úng đắn c
u c n ch
a mãn u ki
(
v = e
)
then {return true }
g ← h( p−1) / q mod p 1< h < p
[1].
,
false
}
{
return
[2]. select
[3].
H : a Zt ,q < t < p
0,1 ∗
{ }
y ← gx modp
ế
ế
ả
tr
ả
về
true thì ch
ữ
ký (e,s) h
ợp lệ, do đó
−1
(2.1b)
ồ
ố
ẹ
n c a b n tin c
ủ
ả
ầ
n th m tra M đượ
ẩ
c
[4]. return {g,y,H(.)}
ậ
ế
ế
ả
tr
ả
v
đ
ủ
ề
là false thì ch
ã b đổi.
a lượ đồ
ữ
ký (e,s) là gi
ả
mạo, hoặ
c
n
ộ
ả
ị sửa
c
b) Thu
Thuật toán 2.2b
Input: p, q, g, x, k, M – b
ật toán ký
đ
cơ sở LD 15.01A
:
Đ
i
ề
ầ
ứ
ng minh ở đây là: cho p, q là 2 s
ố
nguyên t
ố
i:
ả
n tin c
ần ký.
g = h( p−1) / q mod p
th
ỏ
đ
i
ề
ệ
n
q | (p −1)
,
vớ
Output: (e,s) – ch
ữ
ký c
ủa
A
lên M.
r ← gk mod p
H :
{
0,1 ∗
}
a Zt
[1].
(2.2b)
q < t < p
,
vớ
i:
,
1 < x,k < q
,
,
1< h < p
[2].
[3].
(2.3b)
(2.4b)
r = gk mod p
e ← H
(r || M )modq
y = g−x mod p
e = H(r || M)modq
u = gs × ye mod p
,
,
s ← x ×(k + e)mod q
.
N
ế
u:
và
s = (k + x × e)mod q
[4]. return (e,s)
thì: v = e
.
v = H
u || M
mod q
Th t v
ậ
ậ
y, t
ừ
(2.1a), (2.3a), (2.4a) và (2.5a) ta có:
c) Thu
Thuật toán 2.3b
Input: p, q, g, y, M, (e,s).
ật toán kiểm tra
u = gs × ye mod p = gk+x.e × g−x.e mod p
= gx.e+k−x.e mod p = gk mod p
:
(2.7a)
Output: (e,s) = true
/
.
false
T
ừ (2.2a) và (2.7a), suy ra:
u = r
u ← g−e × ys mod p
[1].
(2.5b)
(2.6b)
(2.8a)
(2.9a)
Thay (2.8a) vào (2.6a) ta được:
v = H u || M modq = H(r || M )modq
(2.3a) và (2.9a), suy ra: v = e
ây là u c n ch ng minh.
độ an toàn c a lượ đồ
[2].
v ← H(u || M )modq
(
)
[3]. if ( v = e ) then
{
return true
}
T
ừ
false
else
{
return
}
Đ
đ
i
ề
ầ
ứ
e) M
ức
ủ
c
cơ sở
d) Tính
đ
úng đắn c
ủ
a lượ
c
đồ
c
ơ
sở
LD 15.01B
H
ộ
i Thả
o Quố
c Gia 2015 về Đ
i
ệ
n tử
, Truy
ề
n Thông và Công Ngh
ệ
Thông Tin (ECIT 2015)
Đ
i
ề
u c
ầ
n ch
ứ
u ki
ng minh ở đây là: cho p, q là 2 s
ố
nguyên tố
Output: (e,s) = true
/
.
false
q | (p −1)
g = h( p−1) / q mod p
th
ỏ
a mãn
đ
i
ề
ệ
n
,
v
ớ
i:
,
u ← gs × ye mod p
[1].
[2].
(3.7a)
(3.8a)
0,1 ∗
}
a Zt
vớ
i:
q < t < p
,
,
H :
{
1 < x,k < q
1< h < p
y = g x mod p
v ← H
(u || M
)
modq
−1
r = gk mod p
e = H(r || M)modq
[3]. if
else
Chú thích:
- N u k t qu
được công nh n, do
M và danh tính c a người ký (A) được kh
- N u k t qu tr là false thì ch ký (e,s) là gi
i dung b n tin M
c) Tính úng đắn c
u c n ch
a mãn
(
v = e
)
then
{return true }
,
,
,
u = g−e × ys mod p
false
}
{
return
.
N
.
ế
u:
và
s = x × (k + e) mod q
thì: v = e
v = H
r || M
modq
ế
ế
ả
tr
ả
về
true thì tính h
ợ
ủ
p l
a b
ng định.
ệ
ả
c
ủ
a ch
ữ
ký (e,s)
m tra
Th
ậ
t v y, t
ậ
ừ
(2.1b), (2.3b), (2.4b) và (2.5b) ta có
:
ậ
đ
ó tính toàn v n c
ẹ
n tin c n thẩ
ầ
−1
u = g−e × ys mod p = g−e × g x.x .(k+e) mod p
= ge+k−e mod p = gk mod p
(2.7b)
ủ
ẳ
ế
ế
ả
ả
về
ữ
ả
m
ạ
o, ho
ặ
c
n
ộ
ả
đ
ã b
ị
s
ử
c
a
đổi.
T
ừ
(2.2b) và (2.7b), suy ra:
u = r
đ
ủ
a lượ
đồ LD 15.02A
(2.8b)
(2.9b)
Đ
i
ề
ầ
ứ
ng minh ở đây là: cho p, q là 2 s
ố
nguyên t
ố
Thay (2.8b) vào (2.6b) ta được:
v = H u || M mod q = H (r || M )mod q
(2.3b) và (2.9b), suy ra: v = e
ây là u c n ch ng minh.
độ an toàn c a lượ đồ
ương t ượ đồ LD 15.01A, m
ng ch ng t n công làm l khóa m
15.01B ph thu c vào m độ khó gi i c a bài toán logarit r
c, còn kh ng ch ng t n công gi o ch ký ph thu
vào độ khó c a vi c gi i (2.10b):
e = H((g−e × ys modp) || M)modq
3.2. Xây dựng lược đồ chữ ký số mù
3.2.1. Lượ đồ ch ký s mù LD 15.02A
đồ ch ký s mù ở đây được phát tri
LD 15.01A. Gi A là người người ký có khóa công
t toán 2.1a c a lượ đồ
n tin M được ký. Khi ó, thu t toán ký
a lượ đồ được ch ra nh
g = h( p−1) / q mod p
th
1< h < p
y = g−x mod p
ỏ
đ
i
ề
u ki
ệ
n
,
vớ
i:
q | (p −1)
0,1 ∗
}
a Zq
1 < x,k < q
1 <
α
,
β
< q
,
,
,
,
H :
{
T
Đ
ừ
α
β
đ
i
ề
ầ
ứ
k
,
,
,
r =
ra
×
y × g
mod p
ra = g mod p
b
e) M
ứ
c
ủ
c
c
ơ
sở
LD 15.01B
độ an toàn xét theo
t c a lượ đồ LD-
eb =
α
−1 ×(e −
β
)modq
,
,
e = H(r || M) modq
b
T
ự
l
c
ấ
ức
,
.
Nếu:
kh
ả
n
ă
ố
ộ
ậ
ủ
c
s =
(
α
× sa +
β mod q
)
sa =
u = (g)s ×
Th t v y, t
u = gs × ye mod p
(
k + x × eb
)
mod q
e mod p
ụ
ộ
ứ
c
ả
ủ
ời
và
thì: v = e .
y
v = H
u || M mod q
r
ạ
ả
nă
ố
ấ
ả
m
ạ
ữ
ụ
ộc
ậ
ậ
ừ (3.4a), (3.5a), (3.6a) và (3.7a) ta có:
ủ
ệ
ả
(2.10b)
= g(
) × y(α
) mod p
α
.sa
+
β
.eb +β
c
ữ
ố
.(k+x.eb )+
β
α.eb +β
= gα
× g−x.(
) mod p
(3.9a)
L
ượ
c
ữ
ố
ển từ lược đồ
α
−x.eb .α
= gk. × g x.e . × gβ × g
× g−x. mod p
α
β
b
c
ơ
sở
ả sử
α
β
khai được hình thành theo Thu
và B là người t o ra b
và ki m tra ch ký c
a) Thu t toán ký
Thuật toán 3.1a
ậ
ủ
c
cơ sở
=
=
(
(
ra
gk
)
×
(
g−x
)
× gβ mod p
ạ
ả
đ
ậ
α
)
× yβ × gβ mod p
ể
ữ
ủ
c
ỉ
ư
sau:
ậ
α
=
(ra )
×(y × g)β mod p
:
T
T
ừ
(2.1a), (3.1a) và (3.9a) ta có:
Input: p, q, g, x, y,
Output: (e,s).
α,
β, k , M.
β
α
u = g−
×
g −x
×
g −k
mod p
β
(3.10a)
ra ← gk mod p
α
)
β
=
(
ra
× g− × yβ mod p
[1].
(3.1a)
(3.2a)
(3.3a)
(3.4a)
(3.5a)
(3.6a)
α
β
[2].
[3].
[4].
[5].
[6].
ừ
(3.2) và (3.10), suy ra:
rb ←
ra
×
y × g
mod p
u = r
(3.11a)
e ← H(r || M )modq
b
b
eb ← α −1 ×(e −
sa ← k + x × eb
s ← × sa + modq
β
)modq
Thay (3.11a) vào (3.8a) ta có:
v = H u || M mod q = H(r || M )mod q
(3.2a) và (3.12a), suy ra: v = e
(3.12a)
u c n chứng
b
(
)
mod q
T
ừ
.
Đ
ây là
đ
i
ề
ầ
(
α
β
)
minh.
[7]. return (e,s)
Chú thích:
d) M
ứ
c
độ an toàn c
ương t nh
ký mù m
ủ
ớ
a lượ
i lượ
đề xu
c đồ LD 15.02A
T
ự
ư
v
c
đồ
t c
c
ơ
sở
, mứ
c
đ
độ an toàn c
ánh giá qua các kh
ủa lượ
c
- Các bước [1], [5] do người ký A th
ự
c hiện.
đồ ch
ữ
ớ
i
ấ
ũ
ng đượ
c
ả
- Các bước [2], [3], [4], [6] và [7] do người có b
n ký B th c hi n.
- Tham s k do A l a ch
- Tham số α do B l a ch
- {x,y} là c p khóa bí m t/công khai c
t toán ki m tra
ản tin
nă
ng:
c
ầ
ự
ệ
-
-
Ch
Ch
ố
ố
ng t
ng gi
i m
ấ
n công làm l
ộ
ký.
đồ ch
khóa m
ậ
t.
ố
ự
ọ
n th
ỏ
a mãn: 1< k < q.
a mãn: 1 <
a A.
ả
mạ
o ch
ữ
,
β
ự
ọ
n th
ỏ
α, β < q.
Ngoài ra, v
a nó còn đượ
ngu n g c b
ượ đồ đề xu
ký A hay b t k
ớ
ộ
t lượ
c
ữ
ả
ký s
ố
mù, m
ứ
c
độ an toàn
n công làm l
đặt ra đối v
được ký, thì ngườ
ng nào khác c
ặ
ậ
ủ
c
ủ
c
đ
ánh giá qua kh
n
ă
ng ch
ố
ng t
ấ
ộ
b) Thu
ậ
ể
ồ
ố
ả
n tin sau khi được ký. Yêu c
t là b n tin M sau khi
đối tượng s
ầ
u
ớ
i
i
l
c
mớ
i
ấ
m
ả
đã
Thuật toán 3.2a
Input: p, q, g, y, M – b
ký c a A.
:
ấ
ỳ
ộ
t
ử
d
ụ
ũ
ng hoàn
ả
n tin cần thẩm tra, (e,s) – chữ
ủ
Hội Thảo Quốc Gia 2015 về Điện tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
toàn không thể biết được bản tin M được tạo ra từ đối tượng
B.
dụng bản tin đã ký M cùng thành phần thứ nhất e của chữ
ký, A vẫn có thể xác định được danh tính của B bằng
Thuật toán 3.4a như sau:
Khả năng chống tấn công làm lộ khóa mật và giả mạo chữ
ký
Thuật toán 3.4a:
Mức độ an toàn của lược đồ chữ ký mù mới đề xuất được
thiết lập dựa trên mức độ an toàn của lược đồ cơ sở . Xét theo
khả năng chống tấn công làm lộ khóa mật và khả năng chống
giả mạo chữ ký, có thể thấy rằng mức độ an toàn của 2 lược
đồ này là tương đương như nhau.
Input: {(rai,IDBi)| i=1,2,…N}, (M,e), α, β.
Output: IDBi.
[1].
, i = 0
m ← H (M )
[2]. select:
(
rai
,
IDBi
)
Khả năng chống tấn công làm lộ nguồn gốc của bản tin
được ký
α
β
[3].
[4].
r *←
rai
×
g × y
mod p
bi
e∗ ← H(r *|| M)modq
Thuật toán ký của lược đồ mới đề xuất cho thấy, nếu ở mỗi
lần ký bằng việc lưu trữ các tham số {sa,ra,eb,k} cùng với định
danh của người yêu cầu ký (IDB), người ký A có thể xác định
được mối quan hệ giữa {M,(e,s)} với IDB, nghĩa là từ bản tin
M và chữ ký tương ứng (e,s) có thể xác định được danh tính
của người yêu cầu ký B, với điều kiện người ký A biết được
các tham số (α,β). Thật vậy, khi biết (α,β) người ký A hoàn
toàn có thể xác định được IDB bằng Thuật toán 3.3a như sau:
Thuật toán 3.3a:
bi
[5]. if e∗ ≠ e then
[5.1]. i ← i +
[5.2]. goto [2];
[6]. return IDBi
1
;
Trường hợp chỉ lưu giữ các tham số (ra,,IDB) và sử
dụng thành phần thứ nhất e của chữ ký, A vẫn có thể xác
định được danh tính của B bằng Thuật toán 3.5a như sau:
Input: {(rai,ebi,sai,ki,IDBi)| i=0,1,2,…N}, M, (e,s), α, β.
Output: IDBi.
Thuật toán 3.5a:
Input: {(ebi,IDBi)| i=0,1,2,…N}, e, α, β.
Output: IDBi.
[1].
, i = 0
m ← H (M )
[2]. select: (rai ,ebi , sai ,ki , IDBi )
[1]. i = 0
α
β
[2]. select:
(
ebi
,
IDBi
)
[3].
[4].
r *←
e∗ ← H(r *|| M)modq
rai
×
g × y
mod p
bi
eb∗i ←α −1 ×(e −
β
)modq
[3].
bi
[4]. if eb∗i ≠ ebi then
[5]. if e∗ ≠ e then
[4.1]. i ← i +1;
[5.1]. i ← i +1
;
[4.2]. goto [2];
[5]. return IDBi
[5.2]. goto [2];
∗
ebi ←α −1 ×(e −
β
)modq
[6].
Trường hợp chỉ lưu giữ các tham số (sa,,eb,k,IDB) và
sử dụng thành phần thứ hai s của chữ ký, A xác định được
danh tính của B bằng Thuật toán 3.6a như sau:
[7]. if eb∗i ≠ ebi then
[7.1]. i ← i +
[7.2]. goto [2];
[8].
1
;
Thuật toán 3.6a:
Input: {(ebi,sai,ki,IDBi)| i=0,1,2,…N}, s, α, β.
Output: IDBi.
[1]. i = 0
sa∗i ←
[9]. if sa∗i ≠ sai then
[9.1]. i ← i +
ki + x×ebi mod q
[2]. select: (ebi , sai , ki , IDBi )
1
;
sa∗i ←
(ki + x×ebi )mod q
[9.2]. goto [2];
[10].
[3].
s∗ ←
[11]. if s∗ ≠ s then
[11.1]. i ← i +
α
× sai +
β mod q
[4]. if sa∗i ≠ sai then
[4.1]. i ← i +
1
;
[4.2]. goto [2];
[5]. return IDBi
1
;
[11.2]. goto [2];
[12]. return IDBi
Trường hợp chỉ lưu giữ các tham số (sa,,IDB) và sử dụng
thành phần thứ hai s của chữ ký, A xác định được danh
tính của B bằng Thuật toán 3.7a như sau:
Thuật toán 3.3a trên đây có thể xác định được danh
tính của B với độ chính xác cao, nhưng đòi hỏi phải lưu
giữ nhiều tham số (sa,ra,eb,k,IDB) và mất nhiều thời gian
tính toán. Tuy nhiên, từ thuật toán này có thể chỉ ra sau
đây một số thuật toán tấn công khác đòi hỏi việc lưu giữ
tham số và thời gian tính toán ít hơn mà vẫn có thể xác
định được danh tính của người yêu cầu ký bản tin B.
Thuật toán 3.7a:
Input: {(sai,IDBi)| i=0,1,2,…N}, e, α, β.
Output: IDBi.
[1]. i = 0
[2]. select: (sai , IDBi )
Trường hợp chỉ lưu giữ các tham số (ra,,IDB) và sử
Hội Thảo Quốc Gia 2015 về Điện tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
b). Thu t toán ki m tra
s∗ ←
[4]. if s∗ ≠ s then
[4.1]. i ← i +
(
α
× sai +
β )modq
ậ
ể
[3].
Thuật toán 3.2b
Input: p, q, g, y, M – b
ch ký c a A.
:
ả
n tin c
ầ
n thẩ
m tra, (e,s) –
1
;
ữ
ủ
[4.2]. goto [1];
[5]. return IDBi
Output: (e,s) = true
/
.
false
u ← g−e × ys mod p
[1].
(3.7b)
(3.8b)
Nhận xét:
[2].
v ← H
[3]. if
else
Chú thích:
- N u k t qu
được công nh
th m tra M và danh tính c
định.
- N u k
ho c n
c) Tính úng đắn c
u c n ch ng minh ở đây là: cho p, q là 2 s
a mãn u ki
u || M
)
modq
Các thuật toán từ 3.3a đến 3.7a đều chung đặc điểm là có
thể xác định được danh tính của người yêu cầu ký B nếu biết
được các tham số bí mật (α,β) do B tạo ra. Nói cách khác, mức
độ an toàn của lược đồ mới đề xuất xét theo khả năng giữ bí
mật nguồn gốc của bản tin phụ thuộc vào mức độ khó của việc
tìm được các tham số bí mật (α,β). Từ thuật toán ký của lược
đồ mới đề xuất cho thấy tại thời điểm ký A chỉ biết được các
tham số ra, eb, sa. Điều đó có nghĩa là để tính được (α,β), A cần
phải giải (3.13a):
(
v = e
then {return true }
false
}
{
return
ế
ế
ả
tr
ả
về
true thì tính h
n, do ó tính toàn v
a người ký (A) được kh
ợ
p l
ẹ
ệ
n c
c
ủ
ủ
a ch
ữ
ký (e,s)
n tin c
ng
ậ
đ
a b
ả
ần
ẩ
ủ
ẳ
ế
ế
t qu
i dung b
a lược
ả
tr
ả
v
ề
là false thì ch
n tin M ã b
đồ LD 15.02B
ữ
ký (e,s) là gi
ả mạo,
β
ặ
ộ
ả
đ
ị sửa đổi.
eb =
α
−1 ×(H((r )α ×
g × y
mod p || M ) mod q −
β
) mod q
(3.13a)
a
đ
ủ
Đ
i
ề
ầ
ứ
ố nguyên tố
q | (p −1) g = h( p−1)/ q mod p
Tuy nhiên, từ các kết quả nghiên cứu đã được công bố có
thể thấy rằng (3.13a) là một dạng bài toán khó chưa có lời giải
nếu các tham số p, q được chọn đủ lớn để phương pháp vét
cạn là không khả thi trong các ứng dụng thực tế.
th
ỏ
đ
i
ề
ệ
n
,
v
ớ
i:
,
0,1 ∗
}
a Zt
1 < x,k < q
q < t < p
,
,
vớ
i:
H :
{
1< h < p
−1
y = g x mod p
1 <
α
,
β
< q
ra = gk mod p
,
,
,
,
Mặt khác, do mỗi bước thực hiện của thuật toán ký (Thuật
toán 3.1) đều sử dụng 2 tham số bí mật (α,β) do B tạo ra nên
các dạng tấn công làm lộ nguồn gốc bản tin như các thuật toán
đã chỉ ra ở Mục 2 (Thuật toán 1.1, 1.2, 1.3 và 1.4) là không
khả thi đối với lược đồ mới đề xuất.
α
.
β
,
rb ←
eb =α −1
s = α ×
v = H u || M
ra
× g β × yα mod p
e = H(r || M)modq
b
,
,
(
e +
β mod q
)
sa = x ×
(
k + eb
)
mod q
×
sa + β
mod q
u = g −e × ys mod p
.
N
ế
u:
và
thì: v = e
.
t v
mod q
3.2.2. Lược đồ chữ ký số mù LD 15.02B
Lược đồ chữ ký số mù, ký hiệu LD-15.02B, được phát
triển từ lược đồ cơ sở LD-15.01B. Cũng giả thiết rằng A là
người ký có khóa công khai được hình thành theo Thuật toán
2.1b của lược đồ cơ sở LD 15.01B và B là người tạo ra bản tin
M được ký. Khi đó, thuật toán ký và kiểm tra chữ ký của lược
đồ được chỉ ra như sau:
Th
ậ
ậ
y, t
ừ
(3.4b), (3.5b), (3.6b) và (3.7b) ta có:
u = g−e × ys mod p
−1
−
−
α
α
.eb
.
α
.(
β
β
+sa
+ x.
= gβ
= gβ
× gx
× gx
) mod p
−1
.eb
.α
.
(
(k +eb
)) mod p
α
x−1
.α
.
β
α
.x−1.(k+eb )
= gβ × g−e . × g
× gx.
mod p
b
a) Thuật toán ký
α.β
−1
α
α
.eb
= gβ × g−e .
×
(
α.β
gx
)
×
(
gk
)
× gα mod p
b
Thuật toán 3.1b:
Input: p, q, g, x, y, α, β, k , M.
(3.9b)
−1
α
= gβ ×
(
gx
)
×
(
gk
)
mod p
Output: (e,s).
ra ← gk mod p
T
ừ
(2.1b), (3.1b) và (3.9b) ta có:
[1].
[2].
[3].
[4].
[5].
[6].
(3.1b)
(3.2b)
(3.3b)
(3.4b)
(3.5b)
(3.6b)
α.β
−1
ra
( )
α × gβ × yα.β mod p
u = gβ ×
gx
×
β
gk
α mod p
r ←
b
(3.10b)
α
.
e ← H(r || M ) mod q
eb ← α −1 × (e +
β ) mod q
=
(ra
)
× gβ × yα mod p
b
T
ừ
(3.2) và (3.10), suy ra: u = r
(3.11b)
(3.12b)
b
sa ← x ×
s ←
(
k + eb
sa +
)
mod q
Thay (3.11) vào (3.8) ta có:
v = H u || M modq = H(rb || M ) modq
(3.2b) và (3.12b), suy ra: ây là
(
)
α
×
(
β
)
mod q
T
ừ
. Đ
v = e
đ
i
ề
u c
ầ
n ch
ứ
ng
[7]. return (e,s)
Chú thích:
minh.
d) M
ương t
ngu n g
ứ
c
độ an toàn c
ủ
a lượ
đồ LD 15.02A, kh
a b n tin sau khi ký c
ánh giá qua phân tích kh
n công nh sau:
Thuật toán 3.3b
c
đồ LD 15.02B
ng ch
a lược
- Các bước [1], [5] do người ký A th
- Các bước [2], [3], [4], [6] và [7] do người có b
B th c hi n.
- Tham s k do A l
- Tham số α do B l
- {x,y} là c p khóa bí m
ực hiện.
T
ự
ố
l
ươ
c c
c
ủ
ả
nă
ố
ng t
đồ LD-15.02B
ng th c hiện
ấn công làm
ả
n tin cần ký
l
ộ
ồ
ả
ủ
ự
ệ
c
m
ũ
ộ
ng có thể đượ
c
đ
ả
n
ă
ự
ố
ự
a ch
a ch
t/công khai củ
ọ
n th
ỏ
a mãn: 1< k < q.
a mãn: 1 <
a A.
t s thu t t
ố
ậ
ấ
ư
,
ặ
β
ự
ọ
n th
ỏ
α, β < q.
:
ậ
H
ộ
i Th
ả
o Qu
ố
c Gia 2015 về Đ
i
ệ
n t
ử
, Truy
ề
n Thông và Công Ngh
ệ
Thông Tin (ECIT 2015)
:
Input: {(rai,ebi,sai,ki,IDBi)| i=0,1,2,…N}, M, (e,s), α, β.
Output: IDBi.
Thuật toán 3.5b
Input: {(ebi,IDBi)| i=0,1,2,…N}, e,
Output: IDBi.
α, β.
[1].
, i = 0
m ← H (M )
[1]. i = 0
[2]. select:
(rai ,ebi , sai ,ki , IDBi )
[2]. select
:
(ebi , IDBi )
α
.
β
[3].
r * ←
( )
× gβ × yα mod p
r
eb∗i ←α −1 ×(e +
β
)modq
bi
ai
[3].
e∗ ← rbi *×H(M)modq
[4].
∗
ebi ≠ ebi
[4]. if
then
∗
e ≠ e
[5]. if
then
[4.1]. i ← i +1;
[4.2]. goto [2];
[5]. return IDBi
[5.1]. i ← i +1
;
[5.2]. goto [2];
∗
ebi ←α −1 ×(e +
β
)modq
[6].
Trường h
ng thành ph
danh tính c a B b
Thuật toán 3.6b:
ợ
p 3, A ch
n th
ng Thu
ỉ
l
ư
u gi
hai
t toán 3.6b như
ữ
các tham s
a ch ký, A xác định đượ
sau:
ố (sa,,eb,k,IDB) và
s
ử
d
ụ
ầ
ằ
ứ
s
c
ủ
ữ
c
[7]. if eb∗i ≠ ebi then
[7.1]. i ← i +
[7.2]. goto [2];
[8].
ki + ebi )modq
ủ
ậ
1
;
Input: {(ebi,sai,ki,IDBi)| i=0,1,2,…N}, s, α, β.
Output: IDBi.
[1]. i = 0
sa∗i ← x ×
[9]. if sa∗i ≠ sai then
[9.1]. i ← i +
(
[2]. select
:
(ebi , sai ,ki , IDBi )
ki + ebi mod q
1
;
sa∗i ← x ×
[3].
[9.2]. goto [2];
[4]. if sa∗i ≠ sai then
s∗ ←
[11]. if s∗ ≠ s then
[11.1]. i ← i +
α
×
sai +
β mod q
[10].
[4.1]. i ← i +
1
;
[4.2]. goto [2];
[5]. return IDBi
1
;
[11.2]. goto [2];
[12]. return IDBi
Trường h
ng thành ph
tính c a B b ng Thu
Thuật toán 3.7b
ợ
ầ
p 4, A ch
n th hai
t toán 3.7b nh
ỉ
s
l
ư
u giữ
các tham s
ố
(
sa,,IDB) và s
ử
d
ụ
ứ
ậ
c
ủ
a ch
ữ
ư
ký, A xác định được danh
sau:
Thuật toán 3.3b trên đây có thể xác định được danh tính
của B với độ chính xác cao, nhưng đòi hỏi phải lưu giữ nhiều
tham số (sa,ra,eb,k,IDB) và mất nhiều thời gian tính toán. Tuy
nhiên, từ thuật toán này có thể chỉ ra sau đây một số thuật toán
tấn công tương ứng với các trường hợp đòi hỏi việc lưu giữ
tham số và thời gian tính toán ít hơn mà vẫn có thể xác định
được danh tính của người yêu cầu ký bản tin B.
ủ
ằ
:
Input: {(sai,IDBi)| i=0,1,2,…N}, e,
Output: IDBi.
[1]. i = 0
α, β.
[2]. select: (sai , IDBi )
s∗ ←
α
×
(
sai +
β modq
)
[3].
Trường hợp 1, A chỉ lưu giữ các tham số (ra,,IDB) và sử
dụng bản tin đã ký M cùng thành phần thứ nhất e của chữ ký,
A vẫn có thể xác định được danh tính của B bằng Thuật toán
3.4b như sau:
[4]. if s∗ ≠ s then
[4.1].
i
← i +1;
[4.2]. goto [1];
[5]. return IDBi
Thuật toán 3.4b:
Input: {(rai,IDBi)| i=1,2,…N}, (M,e), α, β.
Output: IDBi.
Nh
ậ
n xét
:
[1].
, i = 0
m ← H (M )
Các Thu
ậ
ể
t toán 3.3b, 34b, 3.5b, 3.6b và 3.7b trên
xác định được danh tính c a B n u bi
bí m t ( ) do B t o ra. Nh y, m độ an toàn
đồ LD 15.02B xét theo kh ng gi bí m t ngu
a b n tin ph thu c vào m độ khó c a vi c tìm đượ
các tham s bí m t ( thu t toán ký c a lượ đồ
LD 15.02B cho th y A ch được các tham s ra, eb, sa t
th m ký. Nên để có th ), A c n ph i gi
đ
ây cho
[2]. select:
phép A có th
các tham s
a lượ
c c
ủ
ế
ức
ế
t
đượ
c
(rai , IDBi )
× gβ × yα mod p
e∗ ← rbi *×H(M)modq
ố
ậ
α
,
β
ạ
ư
ă
vậ
α
.
β
[3].
r * ←
r
bi
ai
c
g
ủ
ố
c
ả
n
ữ
ủ
ậ
ồn
c
[4].
ủ
ả
ụ
ộ
ứ
c
ệ
ủ
ố
ậ
α
,
β
ỉ
ể
). T
ừ
ậ
c
[5]. if e∗ ≠ e then
ấ
bi
ế
t
ố
ại
ờ
i
đ
i
ể
tính (
α
,
β
ầ
ả
ả
i
được:
[5.1]. i ← i +
[5.2]. goto [2];
[6]. return IDBi
1
;
eb = α −1 × (H(((ra )α × g β × yα mod p) || M ) mod q +
β
) mod q
.
β
(3.13b)
ng bài toán khó
p, q được ch đủ để
Trường h
ng thành ph
được danh tính c
ợ
ầ
p 2, A ch
n th nh t e c
a B b
ỉ
l
ư
u gi
ữ
các tham s
ký, A v n có th
sau:
ố
(ra,,IDB) và s
ử
Có th
ể
ờ
th
i gi
ấ
y r
ằ
ng, (3.13b) c
ũng là một dạ
ố
d
ụ
ứ
ấ
ằ
ủa ch
ữ
ẫ
ể
xác định
ch
ư
a có l
ả
i n
ế
u các tham s
ọ
n
lớn
ủ
ng Thu
ậ
t toán 3.5b nh
ư
H
ộ
i Thả
o Quố
c Gia 2015 về Đ
i
ệ
n t , Truy
ử
ền Thông và Công Nghệ Thông Tin (ECIT 2015)
[5] D. Chaum, B. den Boer, E. van Heyst, S. Mjolsnes, A. Steenbeek,
“Efficient Offline Electronic Checks”, Advances in Cryptology,
Eurocrypt’89, LNCS 434, Springer Verlag, pp. 294-301.
phương pháp “vét c
th c t . M t khác, do m
Thu t toán 3.1b
ra nên các d
thu t toán
là không kh
ạ
n” là không kh
ả
thi trong các ứng dụng
ự
ế
ặ
ỗ
d
i bước th
ụ
ự
c hi n c a thu
ng 2 tham s bí m
ngu
ệ
ủ
ậ
c b
ậ
β
t toán ký
) do B t
n tin nh các
(
ậ
)
đều s
ử
ố
t (
ả
α
,
ạo
[6] B. C. Rivest R., Shamir A., Adleman L. (1978), “A Method for
Obtaining Digital Signatures and Public Key Cryptosystems”,
Communications of the ACM, Vol. 21, No. 2, pp. 120 – 126.
ạ
ã ch
ng t
ỉ
ấ
ra
n công làm l
c 2 (Thu
ộ
ồ
n g
ố
ư
ậ
đ
ả
ở
M
ụ
ậ
t toán 1.1, 1.2, 1.3 và 1.4
đề xu t.
)
[7] K. Nyberg, R. A. Rueppel, A New Signature Scheme Base on the DSA
Giving Message Recovery, 1st ACM conference on Computer and
Communications Security, November 3 – 5, Fairfax, Virginia.
thi đối v
ớ
i lượ
c
đồ
m
ớ
i
ấ
IV.
K
Ế
T LU
u c a m
t 2 lượ
đồ ch ký c
a bài toán logarit r i r c, 2 lượ
độ an toàn cao h n các lượ đồ đã bi t v
n công làm l ngu n g c c a b n tin được ký.
u t quan tr ng cho phép lượ
thi trong các ng d ng th c t
ẬN
[8] Jan L. Camenisch, Jean-Marc Piveteau, Markus A. Stadler, Blind
Signatures Base on Discrete Logarithm Problem, Swiss KWF
Foundation, grant no. 2724.1.
T
ừ
vi
được công b
được phát tri n t
trên tính khó c
ệ
c phân tích
đ
i
ể
m yế
ủ
ộ
t số
l
ượ
c
đồ ch
ữ
ký số
mù
đ
ã
ố
, bài báo đề xu
ấ
c
đồ ch
ữ
ký số mù
[9] Nikolay A. Moldovyan, Blind Collective Signature Protocol, Computer
mớ
i
ể
ừ
các lượ
c
ữ
ạ
ơ
s
c
ở
xây d
đồ
kh
ự
ớ
ng d
i này có
ng ch ng
ây là m
t có tính kh
ựa
Science Journal of Moldova, vol.19, no.1(55), 2011.
ủ
ờ
m
[10] National Institute of Standards and Technology, NIST FIPS PUB 186-3.
mứ
c
ơ
c
ế
ề
ả
nă
ố
Digital Signature Standard, U.S. Department of Commerce, 1994.
t
ấ
ộ
ồ
ố
ủ
ả
Đ
ộ
t
[11] GOST
R
34.10-94. Russian Federation Standard. Information
yế
ố
ọ
c
đồ
m
ớ
i
đề xu
ấ
ả
Technology. Cryptographic data Security. Produce and check
procedures of Electronic Digital Signature based on Asymmetric
Cryptographic Algorithm. Government Committee of the Russia for
Standards, 1994 (in Russian).
ứ
ụ
ự ế.
TÀI LI
Ệ
U THAM KH
Ả
O
[12] Kharin Yu.S., Bernik V.I., Matveev G.V., Aguievich S.V. Mathematic
and computer foundations of cryptology, Novoe znanie, Minsk, 2003.
381 p. (in Russian).
[1] D. Chaum, Blind Signature Systems, Advances in Cryptology, Crypto’
83, Plenum Press, pp. 153.
[13] C. P. Schnorr, “Efficient signature generation by smart cards”, Journal
[2] D. Chaum, A. Fiat, M. Naor, “Untraceable Electronic Cash”, Advances
of Cryptology, vol. 4, pp. 161 – 174, 1991.
in Cryptology,Crypto’ 88, LNCS 403, Springer Verlag, pp. 319-327.
[14] T. ElGamal, “ A public key cryptosystem and a signature scheme based
on discrete logarithms”, IEEE Transactions on Information Theory.
1985, Vol. IT-31, No. 4. pp.469–472.
[3] D. Chaum, “Privacy Protected Payment”, SMART CARD 2000, Elsevier
Science Publishers B.V., 1989, pp. 69-93.
[4] N. Ferguson, “Single Term Off-line Coins”, Advances in Cryptology,
Eurocrypt’93, LNCS 765, Springer Verlag, pp. 318-328.
9 trang
27500
Free
Bạn đang xem tài liệu "Phát triển lược đồ chữ ký số mù", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- phat_trien_luoc_do_chu_ky_so_mu.pdf
