DSA

Thuật toán chữ ký số – Digital Signature Algorithm (DSA) – là 1 tiêu chuẩn xử lý thông tin cơ bản (Federal Information Processing Standard – FIPS) cho các chữ ký số. Nó được đề xuất bởi Học viện quốc giá về tiêu chuẩn và kỹ thuật – National Institute of Standards and Technology (NIST) vào tháng 8/1991 để sử dụng cho các tiêu chuẩn chữ ký số – Digital Signature Standard (DSS) và được thông qua như FIPS 186 (tiêu chuẩn số 186) trong năm 1993.  4 sửa đổi với đặc điểm kỹ thuật ban đầu đã được phát hành: FIPS 186-1 vào năm 1996, FIPS 186-2 vào năm 2000, FIPS 186-3 vào năm 2009 và FIPS 186-4 vào năm 2013.

DSA được bao hàm bên trong bằng sáng chế số 5.231.668 được chính phủ Hoa Kỳ cấp vào ngày 26/7/1991 và được đóng góp bởi David W. Kravitz, 1 cựu nhân viên của NSA. Bằng sáng chế này đã được trao cho chính phủ  Hoa Kỳ, đại diện bởi Bộ trưởng thương mại, tại thủ đô Washington, và NIST đã làm cho bằng sáng chế này trở thành miễn phí trên toàn thế giới. Claus P. Schnorr cho rằng bằng sáng chế số 4.995.082 của ông đã bao hàm luôn DSA; tuyên bố này vẫn đang được tranh cãi. DSA là 1 biến thể của sơ đồ chữ ký ElGamal.

Phát sinh khóa

Việc phát sinh khóa có 2 giai đoạn. Giai đoạn đầu là việc chọn các tham số thuật toán mà có thể chia sẻ giữa các người dùng khác nhau của hệ thống, trong khi giai đoạn thứ 2 tính toán các khóa công khai và bí mật cho 1 người dùng.

Phát sinh tham số

  • Chọn 1 hàm băm mật mã đã được phê duyệt H. Trong DSS ban đầu, H luôn luôn là SHA-1, nhưng các hàm băm mạnh hơn SHA-2 đã được cho phép  sử dụng trong DSS gần đây. Kết quả xuất ra của hàm băm có thể được cắt lại bằng với kích thước của cặp khóa.
  • Quyết định 1 chiều dài khóa LN. Đây là thước đó chính cho độ bảo mật của khóa. DSS ban đầu giới hạn L là bội số của 64 sao cho 512 < L < 1024. NIST 800-57 đề nghị chiều dài là 2048 (hoặc 3072) cho các khóa với vòng đời bảo mật mở rộng vượt qua 2010 (hoặc 2030), sử dụng N dài hơn tương ứng. FIPS 186-3 chỉ rõ các cặp chiều dài của LN là (1024, 160), (2048, 224) và (3072, 256).
  • Chọn số nguyên tố q có độ lớn N bit. N phải nhỏ hơn hoặc bằng chiều dài kết quả băm ở trên.
  • Chọn số nguyên tố p có độ lớn L bit sao cho  (p-1) mod q = 0.
  • Chọn g với công thức sau

g = h(p–1)/q mod p  với g > 1

với h là 1 số bất kỳ thỏa 1< h <p-1. Nếu g = 1, thử lại với h khác. Đa số các giá trị của h đều dẫn đến 1 giá trị g khả dụng; thường thì h=2 được sử dụng phổ biến.

Các tham số thuật toán (p,q,g) có thể được chia sẻ giữa các người dùng khác nhau trong hệ thống.

Tạo khóa

Từ tập các tham số có được ở trên, giai đoạn 2 tính toán các khóa bí mật và công khai cho 1 người dùng:

  • Chọn x ngẫu nhiên sao cho 0 < x < q
  • Tính y = gx mod p
  • Khóa công khai là (p, q, g, y).
  • Khóa bí mật là (p, q, g, x)

Gọi H là hàm băm và m là thông điệp:

  • Chọn số ngẫu nhiên cho từng thông điệp có giá trị là k sao cho 0 < k < q.
  • Tính

dsa_01

 

Trong trường hợp r = 0, tính lại r với 1 giá trị k ngẫu nhiên khác.

  • Tính

dsa_02

Trong trường hợp s = 0, tính lại s với 1 giá trị k ngẫu nhiên khác.

  • Chữ ký số của chúng ta gồm (r,s).

Xác thực

  • Bỏ chữ ký nếu điều kiện 0 < r < q hoặc 0 < s < q không thỏa.
  • Tính

dsa_03

  • Tính

dsa_04

 

  • Tính

dsa_05

  • Tính

dsa_06

  • Chữ ký hợp lệ nếu

dsa_07

 

 

 

Discussion

  1. Trackback: Lịch sử Blockchain và Bitcoin 06/15/2018

Leave a Reply