Đề tài Chuẩn Chữ ký số và ứng dụng

ằng chiều dài của bản tin M ban đầu là l bít. Cách độn bản tin sẽ được tiến hành như sau: đầu tiên, ta thêm một bít “1” vào cuối bản tin và ngay tiếp sau bít “1” vừa được thêm vào này, ta thêm k bít “0” liên tiếp, trong đó k là số nguyên nhỏ nhất thỏa mãn l + 1 +k ≡ 448 mod 512. Sở dĩ l +1+k ≡ 448 mod 512 là vì khối 64 bít cuối cùng đã được dành ra để lưu thông tin về kích thước l của bản tin ban đầu. Ví dụ với bản tin hệ mã ASCII-8 bít có nội dung là “abc” thì chiều dài của bản tin này sẽ là l = 8.3 = 24 bít. Vì bản tin được độn thêm một bít “1” nên số bít “0” cần độn thêm vào bản tin sẽ là 448 - (24 +1) = 423. Như vậy từ một bản tin M ban đầu có kích thước là 24 bít, bằng việc độn thêm bít như này, ta thu được một bản tin độn có kích thước là 512 bít, thỏa mãn là bội số của 512. Với SHA-384 và SHA-512. Giả sử rằng chiều dài của bản tin M ban đầu là l bít. Các độn bản tin sẽ được tiến hành như sau: đầu tiên, ta thêm một bít “1” vào cuối bản tin và ngay tiếp sau bít “1” vừa được thêm vào này, ta thêm k bít “0” liên tiếp, trong đó k là số nguyên nhỏ nhất thỏa mãn l + 1+ k ≡ 896 mod 1024. Sở dĩ l+1+ k ≡ 896 mod 1024 là vì khối 128 bít cuối cùng đã được dành ra để lưu thông tin về kích thước l của bản tin ban đầu. Ví dụ với bản tin hệ mã ASCII-8 bít có nội dung là “abc” thì chiều dài của bản tin này sẽ là l = 8.3 = 24 bít. Vì bản tin được độn thêm một bít “1” nên số bít “0” cần độn thêm vào bản tin sẽ là 896 - (24 + 1) = 871. Như vậy từ một bản tin M ban đầu có kích thước là 24 bít, bằng việc độn thêm bít như này, ta thu được một bản tin độn có kích thước là 1024 bít, thỏa mãn là bội số của 1024. b. Phân phối bản tin độn Sau khi bản tin được độn thêm bít, nó cần phải được phân ra thành N khối m-bít trước khi quá trình tính toán băm được bắt đầu. SHA-1 và SHA-256. Với SHA-1 and SHA-256, bản tin độn sẽ được phân ra thành N khối 512 bít: M(1), M(2),…, M(N). Mỗi khối tin M(i) biểu diễn 16 từ-32 bít: M0(i), M1(i),…, M15(i). SHA-384 và SHA-512. Với SHA-384 và SHA-512, bản tin độn được phân ra thành N khối 1024 bít. M(1), M(2),…, M(N). Mỗi khối tin M(i) có độ lớn 1024 bít có thể biểu diễn thánh 16 từ-64 bít M0(i), M1(i),…, M15(i). c. Thiết lập giá trị băm khởi tạo-H(0) Trước khi thực hiện tính toán băm cho mỗi một giải thuật băm, giá trị băm khởi tạo-H(0) cần phải được khởi tạo. Kích thước và số lượng từ của H(0) phụ thuộc vào kích thước của thông điệp rút gọn. SHA-1. Với SHA-1, giá trị băm khởi tạo H(0) bao gồm 5 từ 32 bít sau: SHA-256. Với SHA-256, giá trị băm khởi tạo H(0) bao gồm 8 từ 32 bít sau: H= 6a09e667 H= bb67ae85 H= 3c6ef372 H= a54ff53a H= 510e527f H= 9b05688c H= 1f83d9ab H= 5be0cd19 SHA-384. Với SHA-384, giá trị băm khởi tạo H(0) bao gồm 8 từ-64 bít sau: SHA-512. Với SHA-512, giá trị băm khởi tạo H(0) bao gồm 8 từ-64 bít sau: 1.3.5. Các giải thuật hàm băm an toàn Trong phần này, em xin trình bày giải thuật SHA-512 trước giải thuật SHA-384 bởi vì giải thuật SHA-384 giống hệt giải thuật SHA-512, chỉ có giá trị băm khởi tạo là khác và giá trị băm cuối cùng được cắt lấy 384 bít chứ không phải lấy toàn bộ 512 bít như giải thuật SHA-512 để tạo ra thông điệp rút gọn. Mỗi giải thuật băm an toàn đều có các phương pháp tính luân phiên để tạo ra kết quả. a. SHA-1 SHA-1 có thể được dùng để tính băm cho các thông điệp M có độ dài là l bít với 0 ≤ l < 264 . Giải thuật sử dụng: Một danh sách thông định sẵn gồm 80 từ-32 bít. Năm biến làm việc có độ dài 32 bít. Một giá trị băm bao gồm 5 từ-32 bít. Kết quả cuối cùng của giải thuật SHA-1 là một thông điệp rút gọn 160 bít. Các từ của danh sách thông định sẵn được đánh nhãn là W0, W1,…, W79. Năm biến làm việc là a, b, c, d và e. Các từ của giá trị băm được gán nhãn là H0(i), H1(i), …, H4(i) trong đó giá trị băm khởi tạo H(0) liên tiếp được thay thế bởi các giá trị băm trung gian H(i) cho đến giá trị băm cuối cùng H(N). Ngoài ra SHA-1 còn sử dụng một biến trung gian T có kích thước bằng một từ 32 bít. Qui trình tiền xử lý của SHA-1. 1. Độn tin cho bản tin M. 2. Phân bản tin M ra thành N khối 512 bít M(1), M(2), …, M(N). 3. Thiết lập giá trị khởi tạo H(0). Qui trình tính toán băm của SHA-1. Để tính toán băm, giải thuật SHA-1 sử dụng các hàm và các hằng số được cho trong mục 2.3.2 và 2.3.3. Phép cộng (+) được thực hiện trên modulo 232. Sau khi tiền xử lý, mỗi khối tin M(1), M(2), …, M(N) được xử lý lần lượt theo các bước sau: For i = 1 to N: { Chuẩn bị danh sách thông định sẵn {Wt}: Khởi tạo 5 biến hoạt động a, b, c, d và e ứng với giá trị băm thứ (i-1). a = H0(i-1) b = H1(i-1) c = H2(i-1) d = H3(i-1) e = H4(i-1) For t = 0 to 79: { T = ROTL5(a) + ft(b, c, d) +e + Kt + Wt e = d d = c c = ROTL30(b) b = a a = T } Tính giá trị băm trung gian thứ i - H(i) H0(i) = a + H0(i-1) H1(i) = b + H1(i-1) H2(i) = c + H2(i-1) H3(i) = d + H3(i-1) H4(i) = e + H4(i-1) } Sau khi lặp lại các bước từ (1) tới (4) là N lần, thông điệp rút gọn 160 bít của M sẽ là H0(N) || H1(N) || … || H4(N) b. SHA-256. SHA-256 có thể được dùng để tính băm cho các thông điệp M có độ dài là l bít với 1 ≤ l ≤ 264. Giải thuật SHA-256 sử dụng 1. Một danh sách thông định sẵn gồm 64 từ-32 bít.: 2. Tám biến hoạt động có độ dài 32 bít. 3. Một giá trị băm gồm 8 từ-32 bít. Kết quả cuối cùng của giải thuật SHA-256 là thông điệp rút gọn dài 256 Các từ của danh sách thông định sẵn được gán nhãn là W0, W1,…, W63. Tám biến hoạt động đặt tên là a, b, c, d, e, f, g và h. Các từ của giá trị băm được gán nhãn là H0(i), H1(i), …, H7(i) trong đó giá trị băm khởi tạo H(0) sẽ được thay thế liên tiếp bằng các giá trị băm trung gian H(i) cho đến giá trị băm cuối cùng là H(N). SHA-256 còn sử dụng hai biến trung gian T1 và T2 có độ lớn là 32 bít. Qui trình tiền xử lý của SHA-256. 1. Độn tin cho bản tin M. 2. Phân bản tin M ra thành N khối 512 bít M(1), M(2), …, M(N). 3. Thiết lập giá trị khởi tạo H(0). Qui trình tính toán băm của SHA-256. SHA-256 sử dụng các hàm và các hằng số được mô tả trong phần 2.3.2 và 2.3.3 để tính toán băm. Phép toán cộng (+) được thực hiện theo modulo 232. Sau bước tiền xử lý, từng khối tin M(1), M(2), …, M(N) sẽ được xử lý tuần tự theo các bước sau: For i = 1 to N: { Chuẩn bị danh sách thông định sẵn, {Wt}: Khởi tạo 8 biến hoạt động a, b, c, d, e, f, g và h với giá trị băm thứ (i-1) a = H0(i-1) b = H1(i-1) c = H2(i-1) d = H3(i-1) e = H4(i-1) f = H5(i-1) g = H6(i-1) h = H7(i-1) For t = 0 to 63: { T1 = h + T2 = + Ch(e, f, g) + Kt{256} + Wt h = g g = f f = e e = d + T1 d = c c = b a = T1+ T2 } Tính toán giá trị băm trung gian thứ i (H(i)) H0(i) = a + H0(i-1) H1(i) = b + H1(i-1) H2(i) = c + H2(i-1) H3(i) = d + H3(i-1) H4(i) = e + H4(i-1) H5(i) = g + H5(i-1) H6(i) = f + H6(i-1) H7(i) = h + H7(i-1) } Sau khi lặp lại N lần các bước từ (1) tới (4) thì ta thu được thông điệp rút gọn 256 bít của thông điệp M là: H0(N) || H1(N) || H2(N) || H3(N) || H4(N) || H5(N) || H6(N) || H7(N) c. SHA-512. SHA-512 có thể được dùng để tính băm cho các thông điệp M có độ dài là l bít với 1 ≤ l ≤ 2128. Giải thuật SHA-512 sử dụng: 1. Một danh sách thông định sẵn gồm 80 từ-64 bít. 2. Tám biến hoạt động có độ dài 64 bít. 3. Một giá trị băm gồm 8 từ-64 bít. Kết quả cuối cùng của giải thuật SHA-512 là thông điệp rút gọn dài 512 bít. Các từ của danh sách thông định sẵn được gán nhãn là W0, W1,…, W79. Tám biến hoạt động đặt tên là a, b, c, d, e, f, g và h. Các từ của giá trị băm được gán nhãn là H0(i), H1(i), …, H7(i) trong đó giá trị băm khởi tạo H(0) sẽ được thay thế liên tiếp bằng các giá trị băm trung gian H(i) cho đến giá trị băm cuối cùng là H(N). SHA-512 cũng sử dụng hai biến trung gian T1 và T2 nhưng có độ lớn là 64 bít. Qui trình tiền xử lý của SHA-512. 1. Độn tin cho bản tin M. 2. Phân bản tin M ra thành N khối 1024 bít M(1), M(2), …, M(N). 3. Thiết lập giá trị khởi tạo H(0). Qui trình tính toán băm của SHA-512. SHA-512 sử dụng các hàm và các hằng số được mô tả trong phần 2.3.2 và 2.3.3 để tính toán băm. Phép toán cộng (+) được thực hiện theo modulo 264. Sau bước tiền xử lý, từng khối tin M(1), M(2), …, M(N) sẽ được xử lý tuần tự theo các bước sau: For i = 1 to N: { Chuẩn bị danh sách thông định sẵn, {Wt}: Khởi tạo 8 biến hoạt động a, b, c, d, e, f, g và h với giá trị băm thứ (i-1) a = H0(i-1) b = H1(i-1) c = H2(i-1) d = H3(i-1) e = H4(i-1) f = H5(i-1) g = H6(i-1) h = H7(i-1) For t = 0 to 79: { T1 = h + + Ch(e, f, g) + Kt{512} + Wt T2 = h + + Ch(e, f, g) + Kt{512} + Wt h = g g = f f = e e = d + T1 d = c c = b b = a a = T1 + T2 } Tính toán giá trị băm trung gian thứ i (H(i)) H0(i) = a + H0(i-1) H1(i) = b + H1(i-1) H2(i) = c + H2(i-1) H3(i) = d + H3(i-1) H4(i) = e + H4(i-1) H5(i) = g + H5(i-1) H6(i) = f + H6(i-1) H7(i) = h + H7(i-1) } Sau khi lặp lại N lần các bước từ (1) tới (4) thì ta thu được thông điệp rút gọn 512 bít của thông điệp M là: H0(N) || H1(N) || H2(N) || H3(N) || H4(N) || H5(N) || H6(N) || H7(N). d. SHA-384 SHA-384 có thể được dùng để tính băm cho các thông điệp M có độ dài l bít với 0 ≤ l ≤ 2128. Giải thuật này được định nghĩa giống y hệt với giải thuật SHA-512 trừ hai điểm khác biệt duy nhất sau: 1. Giá trị băm khởi tạo H(0) của SHA-384 khác với giá trị khởi tạo H(0) của SHA-512. 2. Thông điệp rút gọn của SHA-384 có độ dài là 384-bít chứ không phải là 512 bít như của SHA-512. Bởi vì ở khâu cuối cùng, nó chặt bớt 128 bít bên phải của giá trị băm cuối cùng H(N), và chỉ giữ lại 384 bít trái nhất của giá trị băm cuối cùng đó để tạo ra thông điệp rút gọn là: H0(N) || H1(N) || H2(N) || H3(N) || H4(N) || H5(N) thay vì là giữ nguyên toàn bộ tất cả các bít (hay các từ) của H(N) như SHA-512. Chương 2 CHUẨN CHỮ KÝ SỐ (DSS – FIPS PUB 186-3) 2.1. Giới thiệu Để nâng cấp việc sử dụng thương mại điện tử của quốc gia và trong việc giao dịch, Viện tiêu chuẩn và công nghệ quốc gia Hoa kỳ (NIST) đã đưa ra chuẩn xử lý thông tin FIPS 186 là chuẩn chữ ký số (DSS- Digital Signature Standard) vào ngày 19/5/1994 và được chấp nhận từ ngày 1/12/1994. Phiên bản đầu tiên của chuẩn chữ ký số là FIPS PUB 186, phiên bản tiếp theo là FIPS PUB 186-1 được đưa ra vào ngày 15/12/1998, phiên bản thứ 3 là FIPS PUB 186-2 đưa ra vào ngày 27/1/2000 và phiên bản mới nhất hiện nay là FIPS PUB 186-3 được công bố vào tháng 3/2006. Bảng dưới đây so sánh sự khác nhau giữa các phiên bản đã có của DSS. Phiên bản Giá trị cặp (L,N) (bits) Nội dung Chuẩn hàm băm sử dụng FIPS PUB 186 L [512,1024] N [159,160] Giải thuật DSA Chưa có FIPS PUB 186-1 L [512,1024] N [159,160] Giải thuật DSA FIPS 180-1 FIPS PUB 186-2 L [512,1024] N [159,160] Giải thuật DSA Giải thuật ECDSA FIPS 180-1 FIPS PUB 186-3 L = 1024, N = 160 L = 2048, N = 224 L = 3072, N = 256 Giải thuật DSA Giải thuật RSA Giải thuật ECDSA FIPS 180-2 Bảng 3.1 Sự khác nhau giữa các phiên bản DSS Trong phần tiếp theo em xin trình bày về giải thuật DSA trong phiên bản FIPS PUB 186-3. Một hàm băm sẽ được sử dụng tương ứng trong giải thuật tạo và xác thực chữ ký, nhằm giảm bớt độ dài thông điệp ký. Sơ đồ sau thể hiện việc sử dụng hàm băm trong giải thuật tạo và xác nhận chữ ký số. Khóa bí mật Hàm băm Thông điệp Thông điệp rút gọn Thuật toán tạo chữ ký số Chữ ký số Tạo chữ ký số Hàm băm Thông điệp Thông điệp rút gọn Khóa công khai Thuật toán xác nhận chữ ký số Hợp lệ / không hợp lệ Xác nhận chữ ký số Hình 3.1. Sơ đồ sử dụng giải thuật hàm băm trong giải thật chữ ký số 2.3. Giải thuật chữ ký số 2.3.1. Các tham số của DSA Chữ ký số DSA được tính toán dựa trên một tập các tham số miền, khóa bí mật, số bí mật của mỗi thông điệp, dữ liệu để ký và một hàm băm. Việc xác nhận chữ ký số cũng dựa trên tập các tham số miền và khóa công khai này, dựa trên dữ liệu dùng để xác nhận và hàm băm đã dùng để tạo ra chữ ký. Các tham số này là: p: là một số nguyên tố trong đó 2L-1 < p < 2L với L là độ dài bit của biến p. q: là một ước số nguyên tố của p-1 trong đó 2N-1< p < 2N với N là chiều dài của biến q(tính theo bít). g: là căm bậc q của 1 theo modulo p. Dễ dàng tính được g như sau: g = h(p-1)/q mod p. Với 1< h < p-1 x: là khóa bí mật. x là một số nguyên dương được tạo ra một cách ngẫu nhiên sao cho 0< x < q-1. y: là khóa công khai, trong đó y = gx mod p. k: là số bí mật và là duy nhất với mỗi một tin nhắn. k là số nguyên được tạo ra ngẫu nhiên sao cho 0 < k < q. 2.3.2. Lựa chọn kích thước tham số và hàm băm cho DSA Chuẩn này có đưa ra một số các lựa chọn cho cặp (L, N) như sau: (L = 1024, N = 160), (L = 2048, N = 224) và (L = 3072, N = 256) Quá trình tạo chữ ký số sẽ sử dụng tới một hàm băm. Độ an toàn của hàm băm này phải bằng hoặc lớn hơn độ an toàn của cặp (L,N). Người ta khuyến cáo rằng độ an toàn của cặp (L, N) và của hàm băm là như nhau trừ khi có một sự thỏa thuận giữa các bên tham gia nhằm sử dụng một hàm băm mạnh. Những hàm băm có độ an toàn nhỏ hơn độ an toàn của cặp (L, N) sẽ không được sử dụng. Nếu đầu ra của hàm băm có chiều dài là T > N bít thì N bít trái nhất của nó sẽ được sử dụng (thay cho T bít đầu ra như thường lệ) trong mọi tính toán của qui trình tạo và xác nhận chữ ký số. Mỗi cặp (L, N) được lựa chọn sao cho nó có thể bảo vệ được thông tin trong toàn bộ quãng thời gian sống của thông tin. Ví dụ nếu chữ ký số được tạo ra năm 2007 cho thông tin cần được bảo vệ trong 5 năm thì cặp (L, N) được chọn phải đủ lớn để có thể bảo vệ được thông tin trong suốt 5 năm đó. Sau đây là bảng lựa chọn hàm băm cho từng cặp (L, N) Cặp L, N (bits) Bit an toàn (bits) Hàm băm L = 1024 N = 160 80 SHA-1 SHA-256 SHA-384 SHA-512 L = 2048 N = 224 112 SHA-256 SHA-384 SHA-512 L = 3072 N = 256 128 SHA-256 SHA-384 SHA-512 Bảng 3.1. Lựa chọn hàm băm cho cặp (L, N) 2.3.3. Các tham số miền của DSA Giải thuật DSA qui định cặp khóa được sử dụng cho quá trình tạo và xác nhận chữ ký số phải được tạo ra dựa trên tập các tham số miền của DSA. Các tham số miền này có thể được một nhóm người hoặc cả cộng đồng biết tới. Người sử dụng tập tham số này sẽ phải đảm bảo tính hợp lệ của chúng trước khi sử dụng chúng. Mặc dù các tham số này có thể là công khai nhưng chúng vẫn cần phải được quản lý nhằm bảo vệ sự phù hợp tương ứng giữa cặp khóa và các tham số miền cho tất cả các bên sử dụng cặp khóa. Với chuẩn DSA, tham số miền gồm có các số nguyên p, q, g và domain_parameter_seed - tham số gốc, counter - bộ đếm (nếu có yêu cầu) đã sử dụng để tạo ra p, q. Như vậy bộ tham số miền đầy đủ sẽ là (p, q, g { domain_parameter_seed, counter}). Tạo các tham số miền Các tham số miền có thể do một bên ủy nhiệm thứ 3 hoặc do một thực thể nào đó tạo ra. Việc xác nhận đảm bảo tính hợp lệ của chúng sẽ được tiến hành trước khi tạo khóa cũng như trước khi tạo và xác chữ ký số. Việc tạo p, q sẽ được trình bày chi tiết trong mục 3.4. Qui trình tạo p, q có đầu vào là các giá trị L, N - là độ dài tương ứng của các số p, q cần tạo ra và có đầu ra là giá trị của p, q cũng như các biến domain_parameter_seed, counter (nếu cần). Trong mục 3.4 em cũng trình bày chi tiết qui trình tạo tham số g. Quản lý các tham số miền Bởi vì cặp khóa được tạo ra dựa trên tập các tham số miền nên giữa chúng có một sự gắn kết chặt chẽ. Chính vì vậy các tham số miền sau khi được tạo ra cần phải được quản lý để tránh việc chỉnh sửa bất hợp pháp cho đến khi chúng không còn được sử dụng nữa. 2.3.4. Cặp khóa Mỗi một người ký đều sở hữu một cặp khóa bao gồm khóa bí mật x và khóa công khai y, và chúng có quan hệ toán học qua lại lẫn nhau. Trong đó khóa bí mật chỉ sử dụng khi tạo chữ ký số còn khóa công khai vẫn tiếp tục được sử dụng khi chữ ký số vẫn còn cần xác nhận. Tạo cặp khóa. Cặp khóa (x, y) được tạo ra dựa trên tập các tham số miền (p, q, g { domain_parameter_seed, counter}) và giải thuật tạo khóa được trình bày cụ thể trong mục 3.5. Quản lý cặp khóa. Quản lý cặp khóa là một công việc thiết yếu và quan trọng. Việc sử dụng chữ ký số có được an toàn hay không là phụ thuộc vào việc quản lý cặp khóa, cụ thể như sau: Các tham số miền cần phải đuợc đảm bảo trước khi tạo cặp khóa cũng như trước khi xác nhận và kiểm chứng chữ ký số. Mỗi cặp khóa cần phải được gắn liền với một tập các tham số miền nhất định mà dựa trên đó, cặp khóa được tạo ra. Cặp khóa chỉ đuợc sử dụng để tạo và xác nhận chữ ký số bằng cách sử dụng các tham số miền gắn kết với nó. Khóa bí mật chỉ được sử dụng để tạo ra chữ ký số và sau đó, nó phải được giữ bí mật. Còn khóa công khai chỉ được sử dụng để xác nhận chữ ký số và được công khai cho mọi người biết. Bên định ký cần phải chắc chắn sở hữu khóa bí mật trước hoặc lúc dùng nó để tạo ra chữ ký số. Khóa bí mật cần phải được bảo vệ tránh các truy cập, giả mạo và chỉnh sửa bất hợp pháp. Khóa công khai cần phải được bảo về tránh việc chỉnh sửa bất hợp pháp (bao gồm cả trường hợp thay thế). Người xác nhận cần phải chắc chắn về quan hệ ràng buộc giữa khóa công khai, các tham số miền của nó và người sở hữu cặp khóa. Người xác nhận cần phải có được khóa công khai theo một cách thức đáng tin cậy. Người xác nhận cũng cần phải đảm bảo được rằng người tuyên bố là mình đã ký lên thông điệp phải là người sở hữu cặp khóa và rằng người sở hữu này phải nắm giữ khóa bí mật đã được dùng để tạo ra chữ ký số vào thời điểm chữ ký được tạo ra (khóa bí mật phải gắn chặt với khóa công khai mà sẽ được dùng để xác nhận chữ ký số). Người ký và người xác nhận cần phải đảm bảo chắc chắc về tính hợp lệ của khóa công khai. 2.3.5. Số bí mật cho mỗi thông điệp Trước khi ký lên một thông điệp thì bên ký sẽ cần phải tạo ra một số nguyên k một cách ngẫu nhiên. Số k này sẽ được dùng để tạo ra chữ ký cho thông điệp đó và nó sẽ được giữ bí mật. Ngoài ra, qui trình tạo tạo chữ ký số còn sử dụng phần tử nghịch đảo k-1 của k (theo modulo q). Cả k và k-1 đều có thể được tính trước khi người ký biết mình cần ký lên thông điệp nào, bởi vì k và k-1 được tạo ra một cách ngẫu nhiên, độc lập với thông điệp cần ký. Phương pháp tạo ra số bí mật k này được trình bày cụ thể trong mục 3.5. 2.3.6. Tạo chữ ký số DSA Trước khi tạo ra chữ ký cho thông điệp, bên định ký sẽ phải thực hiện thủ tục cài đặt ban đầu để thu được các tham số cần thiết cũng như đảm bảo tính hợp lệ của chúng để tạo ra được chữ ký. Chữ ký trên thông điệp M là một cặp số (r, s) được tính toán như sau: r = (gk mod p) mod q. Với p, q là nguyên tố, gq ≡ 1 mod q và k là số bí mật được tạo ngẫu nhiên cho thông điệp. s = k-1(z + x.r) mod q. z = N bít trái nhất của hàm Hash(M). Trong bước tính s, kết quả đầu ra của hàm Hash(M) sẽ được chuyển từ dạng chuỗi sang dạng số nguyên tương ứng. Sau đó giá trị của r và s sẽ được kiểm tra để xem chúng có bằng 0 hay không. Nếu một trong hai giá trị này bằng không thì bên ký sẽ phải tạo ra một giá trị k khác và chữ ký số sẽ phải được tính toán loại. Tuy nhiên rất hiếm khi r và s bằng 0 nếu như qui trình tạo chữ ký được thực hiện một cách đúng đắn. Chữ ký số (r,s) này có thể sẽ được truyền đi kèm với thông điệp cho người xác nhận. 2.3.7. Kiểm tra và xác thực chữ ký DSA Bất kỳ ai cũng có thể xác nhận được chữ ký điện tử bằng cách sử dụng khóa công khai của người ký. Bên ký có thể tiến hành xác nhận lại chữ ký của mình trước khi gửi thông điệp cho người nhận và sau đó bên nhận sẽ xác nhận chữ ký trên thông điệp để đảm bảo tính xác thực của chữ ký. Trước khi xác nhận chữ ký trên thông điệp thì các tham số miền, khóa công khai của người đã tạo ra chữ ký đó cũng như các đặc điểm nhận dạng của người tự nhận này phải sẵn dùng và có hiệu lực cho người xác nhận chữ ký. Đặt M’, r’, s’ là thông điệp và chữ ký cần đi xác nhận. Đặt y là khóa công khai của người tuyên bố đã tạo ra chữ ký, N là chiều dài của q. Qui trình xác nhận chữ ký được thực hiện như sau: Kiểm tra xem 0 < r’< q và 0 < s’ < q không. Nếu một trong hai điều kiện này không thỏa mãn thì chữ ký số bị coi là không hợp lệ. Nếu cả hai điều kiện trong bước 1 đều thỏa mãn thì người xác nhận sẽ đi thực hiện tiếp như sau: w = (s’)-1 mod q. z = N bít trái nhất của Hash(M’). u1 = z.w mod q. u2 = r’.w mod q. v = (g. y mod p) mod q. Nếu v = r’ thì chữ ký số được xác nhận. Bởi vì v = r’ chỉ khi M = M’, r’ = r và s’= s. Nếu v khác r’ thì có thể là do thông điệp hoặc chữ ký số đã bị chỉnh sữa, hoặc là qui trình tạo chữ ký số đã mắc lỗi, hoặc cũng có thể là bởi vì một kẻ giả danh đã cố gắng giả mạo chữ ký trong khi lại không biết khóa bí mật của người ký. Tuy nhiên, dù là nguyên nhân nào thì chữ ký số đều bị coi là không hợp lệ. Trước khi xác nhận là chữ ký hợp lệ thì người xác nhận cần phải thực hiện các đảm bảo cần thiết như đã nói trong mục 3.3. 2.3.8. Chứng minh giải thuật DSA. Ta có: v = (g. y mod p) mod q = (gz.w mod q. yr’.w mod q mod p) mod q = (gz.w mod q. gx.r’.w mod q mod p) mod q = (g(z+x.r’)w mod q mod p) mod q Mà s = k-1(z + x.r) mod q s-1 = k(z + x.r)-1 mod q Vậy nếu s = s’, r = r’, M = M’ thì v = (g(z+x.r’).k.(z + x.r)mod q mod p) mod q = (gk mod q mod p) mod q = r = r’ 2.3.9. Đánh giá giải thuật DSA DSA dựa vào sơ đồ chữ ký ElGamal, với một vài sửa đổi. Vì vậy tính bảo mật của DSA cũng dựa trên độ khó của bài toán logarit rời rạc. Để bảo đảm an toàn, số nguyên tố p cần phải đủ lớn, trong phiên bản này thì p nhỏ nhất có độ dài biểu diễn nhị phân là 1024 bit. Nếu p có độ lớn 1024 bit thì với sơ đồ ký RSA hoặc ElGamal đã trình bày trong chương 1 thì chữ ký sẽ có độ dài là 1024 bit và 2048 bit, nhưng thực tế nhiều ứng dụng lại cần có chữ ký ngắn hơn vì thế DSA với một vài sửa đổi so với sơ đồ ký ElGamal thì chữ ký chỉ còn độ dài là 320 bit. Việc xác thực chữ ký của DSA chậm hơn so với quá trình tạo chữ ký. Nhưng lại có nhiều ứng dụng chỉ cần tạo chữ ký một lần sau đó việc xác thực lại được dùng nhiều lần và với một thời gian dài như vậy sử dụng DSA cho những ứng dụng này không phải là một lợi thế. Ví dụ nếu dùng giải thuật RSA làm sơ đồ chữ ký và với số mũ bé thì việc xác thực sẽ nhanh hơn rất nhiều so với việc tạo chữ ký. 2.4. Tạo và xác nhận tham số miền 2.4.1. Tạo các số nguyên tố p và q a. Tạo số nguyên tố p và q bằng việc sử dụng hàm băm Phương pháp này sử dụng một hàm băm phải có độ an toàn bằng hoặc lớn hơn độ an toàn của cặp (L, N). Tuy nhiên người ta khuyến cáo rằng độ an toàn của hàm băm và của cặp (L, N) sẽ là như nhau trừ khi có một sự thỏa thuận giữa các bên tham gia nhằm sử dụng một hàm băm mạnh. Tham số gốc domain_parameter_seed có độ dài là seedlen bit, trong đó seedlen ≥ N. Qui trình này sẽ trả về cặp 2 số nguyên p và q có xác suất là nguyên tố rất cao. Để giúp cho người xác nhận có thể xác nhận được chính xác chúng thì giá trị của tham số domain_parameter_seed và counter sử dụng trong quá trình tạo p, q sẽ được trả về trong đó domain_parameter_seed và counter không cần thiết phải giữ bí mật. Đặt Hash() là hàm băm được lựa chọn phù hợp với cặp (L, N) và outlen là chiều dài đầu ra của hàm băm trong đó outlen ≥ N. Qui trình tạo p, q như sau: Đầu vào: 1. L Chiều dài mong muốn của số nguyên tố p. 2. N Chiều dài mong muốn của số nguyên tố q. 3. seedlen Chiều dài mong muốn của tham số gốc trong đó seedlen ≥ N. Đầu ra: 1. status Trạng thái trả về của hàm tạo, trong đó status có thể là VALID hoặc INVALID. Nếu status = INVALID được trả về thì có nghĩa là không có giá trị nào của các tham số đầu ra được trả về hoặc là giá trị của chúng không hợp lệ. 2. p,q Các số nguyên tố tạo được p, q. 3. domain_parameter_seed (tùy chọn). Là một giá trị khởi tạo được sử dụng để tạo ra p và q 4. counter Bộ đếm(tùy chọn). Là giá trị đếm được tạo ra trong quá trình tạo p, q. Qui trình: 1. Kiểm tra cặp (L, N) có thuộc danh sách các cặp (L, N) được chấp nhận (nêu trong phần 4.2) không. Nếu không thuộc thì trả về giá trị INVALID. 2. If (seedlen < N), then return INVALID. 3. n = L / outlen - 1. 4. b = L - 1 - (n * outlen). 5. Gán một chuỗi bất kì có độ dài seedlen bít cho tham số gốc. 6. U = Hash (domain_parameter_seed) mod 2N. 7. q = U 2N-11. /* Mục đích của bước này là gán bít đầu tiên (bít thứ N) và bít cuối cùng (bít 0) của U thành 1 */ 8. p is prime? /* Kiểm tra xem p có là nguyên tố không bằng cách sử dụng thuật toán kiểm tra tính nguyên tố mạnh nêu trong mục c. */ 9. If q is not a prime, then go to step 5. /* Nếu q không là nguyên tố thì quay lại bước 5 để gán cho tham số gốc một giá trị mới nhằm thu được một số q mới có thể là nguyên tố */ 10. offset = 1. /*tạo được q là nguyên tố rồi, bắt đầu tạo p*/ 11. For counter = 0 to 4095 do /*thử tối đa 4095 lần*/ 11.1 For j = 0 to n do Vj = Hash ((domain_parameter_seed + offset + j) mod 2seedlen). 11.2 W = V0 + (V1 * 2outlen) + ... + (Vn-1 * 2(n-1) * outlen) + ((Vn mod 2b) * 2n * outlen). /* Mục đích của bước này là tạo ra một số W gồm đúng L bít. W có dạng như sau: W =Vn’ Vn-1 Vn-2…V1V0 trong đó Vn’ = Vn mod 2b có độ dài là b bít, Vn-1, …, V0 đều có độ dài là outlen bít. Có thể hiểu là ta ghép liên tiếp các chuỗi V0,…, Vn-1, Vn’ để tạo ra W */ 11.3 X = W + 2L-1. /* Vì W được