1.3. Chữ ký số
Trong phần này, chúng ta xem xét chữ ký số. Đây là nguyên thủy mật mã thứ hai, cùng với các hàm băm, mà chúng ta cần làm khối xây dựng cho cuộc thảo luận về tiền điện tử trong Phần 1.5. Chữ ký số được cho là tương tự kỹ thuật số đối với chữ ký viết tay trên giấy. Chúng ta mong muốn có hai thuộc tính từ chữ ký số tương ứng tốt với sự tương tự chữ ký viết tay. Đầu tiên, chỉ bạn mới có thể tạo chữ ký của mình, nhưng bất kỳ ai nhìn thấy nó đều có thể xác minh rằng chữ ký đó hợp lệ. Thứ hai, chúng ta muốn chữ ký được gắn với một tài liệu cụ thể, do đó, chữ ký đó không thể được sử dụng để biểu thị sự đồng ý hoặc chứng thực của bạn đối với một tài liệu khác. Đối với chữ ký viết tay, thuộc tính thứ hai này tương tự để đảm bảo rằng ai đó không thể lấy chữ ký của bạn và cắt nó ra khỏi một tài liệu và dán nó vào dưới cùng của một tài liệu khác.
Làm thế nào chúng ta có thể xây dựng điều này ở dạng kỹ thuật số bằng cách sử dụng mật mã? Đầu tiên, hãy làm cho cuộc thảo luận trực quan ở trên cụ thể hơn một chút. Điều này sẽ cho phép chúng ta lý luận tốt hơn về các lược đồ chữ ký số và thảo luận về các thuộc tính bảo mật của chúng.
Sơ đồ chữ ký số. Sơ đồ chữ ký số bao gồm ba thuật toán sau:
• (sk, pk) := generateKeys(keysize) Phương thức generateKeys nhận kích thước khóa và tạo ra một cặp khóa. Khóa bí mật sk được giữ riêng tư và được sử dụng để ký tin nhắn. pk là khóa xác minh công khai mà bạn cung cấp cho mọi người. Bất kỳ ai có khóa này đều có thể xác minh chữ ký của bạn.
• sig := sign(sk, message) Phương thức ký nhận một thông điệp và một khóa bí mật, sk, làm đầu vào và đầu ra một chữ ký cho thông báo dưới sk.
• isValid := verify(pk, message, sig) Phương thức verify lấy thông báo, chữ ký và khóa công khai làm đầu vào. Nó trả về một giá trị boolean, isValid, sẽ đúng nếu sig là chữ ký hợp lệ cho thông báo dưới khóa công khai pk, và ngược lại là false.
Chúng ta yêu cầu hai thuộc tính sau phải giữ:
• Chữ ký hợp lệ phải xác minh: verify(pk, message, sign(sk, message)) == true.
• Chữ ký là tồn tại không thể giả mạo được.
Chúng ta lưu ý rằng generateKeys và sign có thể là các thuật toán ngẫu nhiên. Thật vậy, generateKeys tốt hơn nên được ngẫu nhiên hóa, bởi vì nó phải tạo ra các khóa khác nhau cho những người khác nhau. Ngược lại, verify sẽ luôn mang tính xác định.
HÌNH 1.9. Trò chơi không thể giả mạo. Kẻ tấn công và người thách thức chơi trò chơi không thể giả mạo. Nếu kẻ tấn công có thể xuất thành công chữ ký trên một tin nhắn mà hắn chưa từng thấy trước đó, kẻ đó sẽ thắng. Nếu anh ta không thể làm như vậy, người thách thức sẽ thắng và kế hoạch chữ ký số là không thể giả mạo được. Ảnh của Whit Diffie (phải), đã cắt, © Kevin Bocek. Được cấp phép theo Creative Commons CC BY 2.0.
Bây giờ chúng ta hãy kiểm tra hai thuộc tính mà chúng ta yêu cầu của một lược đồ chữ ký số một cách chi tiết hơn. Thuộc tính đầu tiên rất đơn giản—rằng các chữ ký hợp lệ phải có thể xác minh được. Nếu tôi ký một tin nhắn bằng sk, khóa bí mật của tôi và sau đó ai đó cố gắng xác thực chữ ký đó trên cùng một tin nhắn bằng khóa công khai của tôi, pk, thì chữ ký đó phải xác thực chính xác. Thuộc tính này là một yêu cầu cơ bản để chữ ký trở nên hữu ích.
Không thể giả mạo được. Yêu cầu thứ hai là nó không khả thi về mặt tính toán để giả mạo chữ ký. Có nghĩa là, đối thủ biết khóa công khai của bạn và nhìn thấy chữ ký của bạn trên một số thư khác không thể giả mạo chữ ký của bạn trên một số thư mà anh ta chưa thấy chữ ký của bạn. Tính chất không thể giả mạo này thường được chính thức hóa trong điều kiện một trò chơi mà chúng ta chơi với đối thủ. Việc sử dụng các trò chơi là khá phổ biến trong các bằng chứng bảo mật mật mã.
Trong trò chơi không thể giả mạo, đối thủ tuyên bố rằng anh ta có thể giả mạo chữ ký và người thách thức kiểm tra tuyên bố này (Hình 1.9). Điều đầu tiên chúng ta làm là sử dụng generateKeys để tạo khóa ký bí mật và khóa xác minh công khai tương ứng. Chúng ta cung cấp khóa bí mật cho người thách thức và chúng ta cung cấp khóa công khai cho cả người thách thức và đối thủ. Vì vậy, đối thủ chỉ biết thông tin công khai, và nhiệm vụ của anh ta là cố gắng giả mạo một thông điệp. Người thách thức biết chìa khóa bí mật. Vì vậy, anh ta có thể tạo chữ ký.
Trực quan, thiết lập của trò chơi này phù hợp với các điều kiện trong thế giới thực. Một kẻ tấn công thực sự có thể sẽ nhìn thấy các chữ ký hợp lệ từ nạn nhân của mình trên các tài liệu khác nhau. Và kẻ tấn công thậm chí có thể thao túng nạn nhân ký vào các tài liệu trông có vẻ vô hại nếu điều đó hữu ích với kẻ tấn công.
Để mô hình hóa điều này trong trò chơi của chúng ta, chúng ta cho phép đối thủ lấy chữ ký trên một số tài liệu mà anh ta lựa chọn, bao lâu tùy thích, miễn là số lượng phỏng đoán là hợp lý. Để đưa ra một ý tưởng trực quan về ý nghĩa của chúng ta về một số lượng dự đoán hợp lý, chúng ta sẽ cho phép đối thủ thử 1 triệu lần đoán, nhưng không phải 280 lần đoán. Theo thuật ngữ tiệm cận, chúng ta cho phép đối thủ thử một số phép đoán là một hàm đa thức có kích thước khóa, nhưng không hơn (ví dụ: anh ta không thể thử nhiều lần đoán theo cấp số nhân).
Một khi đối thủ hài lòng rằng anh ta đã nhìn thấy đủ chữ ký, sau đó anh ta chọn một số thông điệp, M, mà anh ta sẽ cố gắng giả mạo chữ ký. Hạn chế duy nhất đối với M là nó phải là một tin nhắn mà đối phương chưa từng thấy chữ ký trước đó (bởi vì sau đó anh ta rõ ràng có thể gửi lại một chữ ký mà anh ta đã được cho). Người thách thức chạy thuật toán xác minh để xác định xem chữ ký do kẻ tấn công tạo ra có phải là chữ ký hợp lệ trên M dưới khóa xác minh công khai hay không. Nếu nó xác minh thành công, đối thủ sẽ thắng trò chơi.
Chúng ta nói rằng sơ đồ chữ ký là không thể giả mạo được nếu và chỉ khi, bất kể đối thủ đang sử dụng thuật toán nào, cơ hội giả mạo thành công một thông điệp của anh ta là cực kỳ nhỏ—nhỏ đến mức chúng ta có thể cho rằng nó sẽ không bao giờ xảy ra trong thực tế.
Mối quan tâm thực tế
Một số điều thực tế phải được thực hiện để biến ý tưởng thuật toán thành một cơ chế chữ ký số có thể được thực hiện. Ví dụ: nhiều thuật toán chữ ký được ngẫu nhiên hóa (đặc biệt là thuật toán được sử dụng trong Bitcoin) và do đó chúng ta cần một nguồn ngẫu nhiên tốt. Không thể đánh giá quá mức tầm quan trọng của yêu cầu này, vì tính ngẫu nhiên không tốt sẽ làm cho thuật toán an toàn của bạn không an toàn.
Một mối quan tâm thực tế khác là kích thước tin nhắn. Trên thực tế, có một giới hạn về kích thước thư mà bạn có thể ký, bởi vì các lược đồ thực sẽ hoạt động trên các chuỗi bit có độ dài hạn chế. Có một cách dễ dàng để giải quyết hạn chế này: ký mã băm của tin nhắn, thay vì ký tên vào chính tin nhắn. Nếu chúng ta sử dụng hàm băm mật mã với đầu ra 256 bit, thì chúng ta có thể ký một cách hiệu quả một thông điệp có độ dài bất kỳ miễn là lược đồ chữ ký của chúng ta có thể ký các thông điệp 256 bit. Như chúng ta đã thảo luận, thật an toàn khi sử dụng hàm băm của thông báo như một bản tóm tắt thông báo theo cách này, vì hàm băm có khả năng chống va chạm.
Một thủ thuật khác mà chúng ta sẽ sử dụng sau đó là bạn có thể ký một con trỏ băm. Nếu bạn ký vào một con trỏ băm, thì chữ ký sẽ bao phủ hoặc bảo vệ toàn bộ cấu trúc — không chỉ bản thân con trỏ băm mà còn tất cả mọi thứ mà chuỗi con trỏ băm trỏ đến. Ví dụ: nếu bạn ký con trỏ băm nằm ở cuối chuỗi khối, thì kết quả là bạn sẽ ký kỹ thuật số toàn bộ chuỗi khối.
ECDSA
Bây giờ chúng ta hãy đi vào các sự việc thực tế (nuts and bolts). Bitcoin sử dụng một lược đồ chữ ký kỹ thuật số cụ thể được gọi là Thuật toán chữ ký kỹ thuật số đường cong Elliptic (ECDSA). ECDSA là một tiêu chuẩn của chính phủ Hoa Kỳ, một bản cập nhật của thuật toán DSA trước đó được điều chỉnh để sử dụng các đường cong elliptic. Các thuật toán này đã nhận được phân tích mật mã đáng kể trong nhiều năm và thường được cho là an toàn.
Cụ thể hơn, Bitcoin sử dụng ECDSA trên đường cong elliptic tiêu chuẩn secp256k1, được ước tính cung cấp 128 bit bảo mật (tức là, rất khó để phá vỡ thuật toán này vì nó thực hiện 2128 hoạt động mật mã khóa đối xứng, chẳng hạn như gọi một hàm băm). Mặc dù đường cong này là một tiêu chuẩn đã được công bố, nhưng nó hiếm khi được sử dụng bên ngoài Bitcoin; các ứng dụng khác sử dụng ECDSA (chẳng hạn như trao đổi khóa trong giao thức TLS để duyệt web an toàn) thường sử dụng đường cong secp256r1 phổ biến hơn. Đây chỉ là một sự kỳ quặc của Bitcoin, vì nó đã được Satoshi chọn (xem Lời nói đầu) trong đặc điểm kỹ thuật ban đầu của hệ thống và hiện rất khó thay đổi.
Chúng tôi sẽ không đi sâu vào tất cả các chi tiết về cách thức hoạt động của ECDSA, vì một số phép toán phức tạp có liên quan và việc hiểu nó là không cần thiết đối với phần còn lại của cuốn sách này. Nếu bạn quan tâm đến chi tiết, hãy tham khảo phần Đọc thêm của chúng tôi ở cuối chương này. Tuy nhiên, có thể hữu ích nếu có hiểu biết về kích thước của các số lượng khác nhau:
| Khóa cá nhân: | 256 bit |
| Khóa công khai, không nén: | 512 bit |
| Khóa công khai, được nén: | 257 bit |
| Thông báo được ký: | 256 bit |
| Chữ ký: | 512 bit |
Lưu ý rằng mặc dù về mặt kỹ thuật ECDSA chỉ có thể ký các thông báo dài 256 bit, nhưng đây không phải là vấn đề: các thông báo luôn được băm trước khi được ký, do đó, bất kỳ thông báo kích thước nào cũng có thể được ký một cách hiệu quả.
Với ECDSA, một nguồn ngẫu nhiên tốt là điều cần thiết, bởi vì một nguồn xấu có thể sẽ làm rò rỉ khóa của bạn. Theo trực quan, nếu bạn sử dụng tính ngẫu nhiên không hợp lệ khi tạo khóa, thì khóa bạn tạo có thể sẽ không an toàn. Nhưng có một điều khó hiểu của ECDSA là, ngay cả khi bạn chỉ sử dụng tính ngẫu nhiên xấu khi tạo chữ ký và bạn sử dụng khóa hoàn toàn tốt của mình, thì chữ ký xấu cũng sẽ làm rò rỉ khóa cá nhân của bạn. (Đối với những người quen thuộc với DSA, đây là một điểm lạ thường chung trong DSA và không dành riêng cho biến thể đường cong elliptic.) Và sau đó trò chơi kết thúc: nếu bạn làm lộ khóa cá nhân của mình, đối thủ có thể giả mạo chữ ký của bạn. Do đó, chúng ta cần phải đặc biệt cẩn thận về việc sử dụng ngẫu nhiên tốt trong thực tế. Sử dụng một nguồn ngẫu nhiên xấu là một cạm bẫy phổ biến của các hệ thống an toàn khác.
Điều này hoàn thành cuộc thảo luận của chúng ta về chữ ký số như là một nguyên thủy mật mã. Trong phần tiếp theo, chúng ta sẽ thảo luận về một số ứng dụng của chữ ký số sẽ trở nên hữu ích cho việc xây dựng tiền điện tử.