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