Chữ ký số (Digital Signature Algorithm) WCO2

Đến với bài viết này ta sẽ làm quen với chữ ký số hay ngắn gọn là DSA (không phải data structures and algorithms nhé :V). Mình sẽ cố gắng cô đọng lại những gì mình biết về DSA nhất để có thể để các bạn có cái nhìn tổng quát, về chuyên sâu thì các bạn có thể tham khảo thêm từ nhiều nguồn khác nhau.

Trước khi đến với thuật toán chữ ký số DSA, ta cần ôn lại kiến thức về public key cryptography:
https://vnoi.info/wiki/cs/crypto/Public-Key-Cryptography.md
https://en.wikipedia.org/wiki/Public-key_cryptography

Về cách hoạt động của RSA, ECC:
https://giapppp.notion.site/Elliptic-Curve-Cryptography-50d4401770b641349ad235e287b326d0
https://hackmd.io/@tranminhprvt01/RSA_Training_WCO2

Và chức năng của hàm Hash:
https://hackmd.io/@tvdat20004/HkxCf9eLZR

Chữ ký số là gì?

Chữ ký số cũng tương tự như chữ ký ngoài đời thường vậy, có chức năng xác nhận bạn hay một người, một tổ chức nào đó đã ký hay xác nhận một đoạn văn bản, điều khác biệt tất yếu là một loại chữ ký được dùng vào các biên bản số đã được số hoá trên không gian số (digital), loại còn lại được dùng trong các biên bản giấy (analog).

Một thuật toán chữ ký số phải bảo đảm 2 điều cơ bản:

• Chỉ có bạn mới có thể ký (hay nói cách khác, người khác không có khả năng làm giả chữ ký của bạn)
• Bất cứ ai cũng có thể xác nhận chữ ký trên văn bản là của bạn.

Cách hoạt động của chữ ký số

Một thuật toán chữ ký số thường có 3 thuật toán con bao gồm:

• Thuật toán tạo public key và private key (các bạn có thể xem lại phần các thuật toán mã hoá bất đối xứng RSA, ECC,…)
• Thuật toán để ký một văn bản khi có văn bản và private key.
• Thuật toán để xác thực chữ ký khi có chữ ký,văn bản và public key.

Các thuật toán chữ ký số tiêu biểu là RSA, DSA, ECDSA. Và trong bài viết này mình cũng sẽ đề cập nhiều đến 3 thuật toán này.

Lưu ý: văn bản hay "message" hoặc "plaintext" trong tiếng anh mà mình nhắc đến có thể là một con số rất lớn được lấy nguyên giá trị từ một văn bản, hoặc một giá trị lấy được từ một hàm hash (md5,sha1,…) sau khi đã hash văn bản. Việc hash một văn bản gần như là bắt buộc và mục đích là để góp phần làm giảm khối lượng công việc khi tính toán. Trường hợp không bắt buộc thì có thể là văn bản ngắn không cần phải qua hàm hash nhưng tốt nhất vẫn nên hash mọi văn bản khi "ký". Ký hiệu hàm hash:

$H()$ hoặc

$h()$

hình 1: Tổng quát về quá trình ký và xác thực chữ ký số

RSA

RSA ngoài chức năng mã hoá các thông tin có độ lớn bé hơn N, còn có chức năng là một thuật toán chữ ký số khá tốt.

hình 2: cách hoạt động của chữ ký số bằng thuật toán RSA

DSA

DSA dựa trên thuật toán chữ ký số Schnorr và ElGamal, khi cài đặt thuật toán cần chú ý đến độ lớn và độ ngẫu nhiên của giá trị

$k$,

$k$ là giá ngẫu nhiên cho mỗi lần ký. Giá trị

$k$ phải tuyệt đối không được trùng khi được ký bởi chung một private key.

Vậy lý do tại sao

$k$ không được trùng? (một bài tập nhỏ)

hình 3: cách hoạt động của chữ ký số bằng thuật toán DSA

ECDSA

ECDSA là thuật toán chữ ký số sử dụng ECC và dựa trên DSA, cái hay của ECDSA là nhanh, gọn, nhẹ. Nhanh hơn trong quá trình triển khai, gọn hơn về độ lớn của bit (hình 5), và nhẹ về mặt tính toán (ECC sử dụng phép cộng thay vì phép nhân).

Vì những tính chất như thế nên hiện nay trong thực tế ECDSA là lựa chọn hiệu suất nhất.
Vì ECDSA dựa trên DSA và cũng có tham số

$k$, trường hợp này số

$k$ có được trùng không? nếu có/không, lý do vì sao? (một bài tập nhỏ khác)

hình 4: cách hoạt động của chữ ký số bằng thuật toán ECDSA

hình 5: NIST guidelines for public key size (bảng so sánh giữa độ lớn bit cần thiết trong cùng các cấp về bảo mật, ví dụ 7680 bit độ lớn khoá của RSA hay DSA sẽ có cùng cấp độ bảo mật với 384-511 bit độ lớn khoá của ECC)

Tại sao phải quan tâm đến chữ ký số?

Câu hỏi này khá giống như câu hỏi tại sao chữ ký của chúng ta vậy. Việc ký một văn bản là một việc làm cực kỳ quan trọng nếu văn bản ấy là một văn bản quan trọng (thuộc một cá nhân, nhóm, tập đoàn, cơ sở hay nhà nước, chính phủ)

Và vì DSA cung cấp các chức năng sau:

Bảo đảm tính toàn vẹn dữ liệu (Data Integrity): DSA đảm bảo rằng dữ liệu không bị thay đổi trong quá trình truyền tải, bảo vệ khỏi việc sửa đổi trái phép hoặc không được ủy quyền.

Xác thực (Authentication): Chữ ký số xác thực người gửi, xác nhận danh tính và tác giả của tin nhắn.

Không thể phủ nhận (Non-Repudiation): Một khi chữ ký số được gắn, người gửi không thể phủ nhận sự tham gia của họ, cung cấp bằng chứng pháp lý và bằng chứng cho các giao dịch số.

Câu hỏi

Một số câu hỏi để ôn lại cho thú vị nhé :Đ (không cần nộp câu trả lời)

1. Tại sao phải sử dụng chữ ký số?
2. Tính chất cần có của một thuật toán dùng cho chữ ký số?
3. Có bao nhiêu thuật toán chữ ký số phổ biến mà bạn đã biết?
4. Hiện tại thuật toán chữ ký số nào đang phổ biến hay an toàn nhất hiện nay? Vì sao lại sử dụng thuật toán này?

Một số cách tấn công tiêu biểu

RSA:
Blinding attack: https://en.wikipedia.org/wiki/Blind_signature
Duplicate signature attack: https://www.agwa.name/blog/post/duplicate_signature_key_selection_attack_in_lets_encrypt

ECDSA, DSA (một số attack của ECDSA có thể áp dụng vào DSA và ngược lại):
Reuse nonce (bị trùng

$k$ như đã nói ở trên)
Related nonce: https://eprint.iacr.org/2023/305.pdf
Biased nonce: https://cryptopals.com/sets/8/challenges/62.txt
Fault attack: https://asecuritysite.com/ecc/ecd7
Curveball: https://research.kudelskisecurity.com/2020/01/15/cve-2020-0601-the-chainoffools-attack-explained-with-poc/

Bài tập

Bài tập bắt buộc: (vì sắp thi cuối kỳ nên các bạn chọn tối thiểu 4 bài)
Mình fan cứng cryptohack nên :D
https://cryptohack.org/challenges/rsa/ (phần Signatures Part 1)
https://cryptohack.org/challenges/ecc/ (phần Signatures)

Bài tập tự do:
https://cryptohack.org/challenges/rsa/ (phần Signatures Part 2)
https://hackropole.fr/en/challenges/crypto/fcsc2024-crypto-el-gamal-fait-1/
https://hackropole.fr/en/challenges/crypto/fcsc2024-crypto-el-gamal-fait-2/
Challengename - bi0sCTF 2024

Tài liệu trích dẫn

[DSA]:https://en.wikipedia.org/wiki/Digital_Signature_Algorithm
[RSA]:https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Signing_messages
https://hackmd.io/@tranminhprvt01/RSA_Training_WCO2
[ECDSA]:https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
[ECC]:https://giapppp.notion.site/Elliptic-Curve-Cryptography-50d4401770b641349ad235e287b326d0
[ElGamal]:https://en.wikipedia.org/wiki/ElGamal_encryption
[Schnorr]:https://en.wikipedia.org/wiki/Schnorr_signature
https://hackmd.io/@tvdat20004/HkxCf9eLZR
https://vnoi.info/wiki/cs/crypto/Public-Key-Cryptography.md
https://en.wikipedia.org/wiki/Public-key_cryptography