Giải thuật ký số

Giải thuật ký số (Digital Signature Algorithm, viết tắt DSA) là chuẩn của chính phủ Mỹ hoặc FIPS cho các chữ ký số. Giải thuật này được đề nghị bởi Viện các tiêu chuẩn và công nghệ quốc gia (NIST) vào tháng 8/1991 để sử dụng trong chuẩn chữ ký số (DSS), được chỉ ra trong FIPS 186 [1], được chấp nhận năm 1993. Một sửa đổi nhỏ được đưa ra năm 1996 trong FIPS 186-1 [2], chuẩn được mở rộng hơn năm 2000, được xem như FIPS 186-2 [3]

Giải thuật ký số

Tạo khoá

• Chọn số nguyên tố 160 bit q.
• Chọn một số nguyên tố L bit p, sao cho p=qz+1 với số nguyên z nào đó, 512 ≤ L ≤ 1024, L chia hết cho 64.

Chú ý: Trong FIPS-186-2 Lưu trữ 2009-05-18 tại Wayback Machine, giả sử L luôn bằng 1024.

• Chọn h, với 1 < h < p - 1 sao cho g = h^z mod p > 1. (z = (p-1) / q.)
• Chọn x ngẫu nhiên, thoả mãn 0 < x < q.
• Tính giá trị y = g^x mod p.
• Khoá công khai là (p, q, g, y). Khoá riêng là x.

Chú ý (p, q, g) có thể dùng chung bởi nhiều người dùng trong hệ thống, nếu muốn. FIPS 186-3 sử dụng SHA-224/256/384/512 như hàm băm, q với kích thước 224, 256, 384, và 512 bit, L nhận giá trị 2048, 3072, 7680, và 15360 tương ứng. Có các giải thuật hiệu quả để tính toán các biểu thức mũ và lấy phần dư khi chia cho số nguyên tố lớn h^z mod p và g^x mod p.

Hầu hết các số h đều thoả mãn yêu cầu, vì vậy giá trị 2 thông thường được sử dụng.

Ký

• Tạo một số ngẫu nhiên với mỗi thông điệp, giá trị k thỏa mãn 0 < k < q
• Tính r = (g^k mod p) mod q
• Tính s = (k⁻¹(SHA-1(m) + x*r)) mod q, ở đây SHA-1(m) là hàm băm mã hoá SHA-1 áp dụng cho thông điệp m
• Tính toán lại chữ ký trong trường hợp không chắc chắn khi r=0 hoặc s=0
• Chữ ký là (r,s)

Giải thuật Euclid mở rộng có thể được sử dụng để tính toán biểu thức k⁻¹ mod q.

Xác nhận

• Loại bỏ chữ ký nếu hoặc 0< r <q hoặc 0< s <q không thỏa mãn.
• Tính w = (s)⁻¹ mod q
• Tính u1 = (SHA-1(m)*w) mod q
• Tính u2 = (r*w) mod q
• Tính v = ((g^u1*y^u2) mod p) mod q
• Chữ ký là có hiệu lực nếu v = r

DSA tương tự với Lược đồ ký số ElGamal.

Sự đúng đắn của giải thuật

Lược đồ ký số là đúng đắn có ý nghĩa khi người xác nhận luôn chấp nhận các chữ ký thật. Điều này có thể được chỉ ra như sau:

Từ g = h^z mod p suy ra g^q ≡ h^qz ≡ h^p-1 ≡ 1 (mod p) bởi định lý Fermat nhỏ. Bởi vì g>1 và q là số nguyên tố suy ra g có bậc q.

Người ký tính

$s=k^{-1}({\mbox{SHA-1}}(m)+xr)\mod {q}.$

Như vậy

${\begin{matrix}k&\equiv &{\mbox{SHA-1}}(m)s^{-1}+xrs^{-1}\\&\equiv &{\mbox{SHA-1}}(m)w+xrw{\pmod {q}}.\\\end{matrix}}$

Bởi vì g có bậc q chúng ta có

${\begin{matrix}g^{k}&\equiv &g^{{\rm {SHA-1}}(m)w}g^{xrw}\\&\equiv &g^{{\rm {SHA-1}}(m)w}y^{rw}\\&\equiv &g^{u1}y^{u2}{\pmod {p}}.\\\end{matrix}}$

Cuối cùng, tính đúng đắn của DSA suy ra từ

$r=(g^{k}\mod p)\mod q=(g^{u1}y^{u2}\mod p)\mod q=v.$

Xem thêm

• Giải thuật ký số đường cong elip

Liên kết ngoài

• FIPS-186, Ấn bản đầu tiên của đặc tả kỹ thuật DSA chính thức.
• FIPS-186, change notice No.1, thông báo thay đổi đầu tiên đối với bản đặc tả kỹ thuật đầu tiên.
• FIPS-186-1, sửa đổi đầu tiên đối với bản đặc tả kỹ thuật DSA.
• FIPS-186-2 Lưu trữ 2009-05-18 tại Wayback Machine, thay đổi lần 2 đối với bản đặc tả kỹ thuật (bao gồm từ thông báo thay đổi đầu tiên cho đến sự thay đổi này).
• Các khuyến cáo đối với quản lý khóa -- Phần 1: Tổng quát, Ấn bản đặc biệt 800-57 của NIST, trang 62–63