Thuật toán ECDSA và ứng dụng trong chữ ký số

[DucksuckDark]

Trong lĩnh vực chữ ký số, thuật toán ECDSA được đánh giá là một trong những thuật toán mã hóa mạnh nhất, dù sinh sau đẻ muộn nhưng ECDSA được dự đoán có thể thay thế cho RSA – thuật toán phổ biến hiện nay. Vậy ECDSA là gì? Thuật toán này có gì nổi bật? Ứng dụng của nó trong chữ ký số như thế nào? Bài viết này sẽ giúp chúng ta trả lời những câu hỏi đó.

Thuật toán ECDSA là gì?​

ECDSA là viết tắt của Elliptic Curve Digital Signature Algorithm - thuật toán sinh chữ ký số dựa trên đường cong Elliptic, với công thức toán học là:

Hình 1: Ảnh minh họa đường cong elliptic
​

Trên đường cong Elliptic tồn tại 2 phép toán đó là phép cộng và phép nhân.

Phép cộng: Ta có 2 điểm P và Q như hình bên dưới, kẻ P với Q và cắt đường cong được điểm R lấy đối xứng của R qua trục Ox ta được kết quả của phép cộng

Hình 2: Ảnh minh họa phép cộng trên đường cong Elliptic​

Phép nhân: Bản chất của phép nhân là đi thực hiện phép cộng nhiều lần. Như hình bên dưới, đầu tiên có điểm P lấy tiếp tuyến cắt đường cong tại -2P đối xứng qua Ox ta được 2P tiếp tục thực hiện 1 lần nữa nối p và 2p ta sẽ được 3P.

Hình 3: Ảnh minh họa phép nhân trên đường cong elliptic​

​

Do cách tính toán trên, ta có thể dễ dàng tính toán được phép nhân khi đã biết 3 và P như trêm hình vẽ, nhưng hoàn toàn không thể tính toán được theo chiều ngược lại. Điều này giúp cho khóa bí mật được an toàn hơn khi áp dụng phép nhân để tạo cặp khóa ECDSA.

Thế mạnh của ECDSA ​

Để tìm hiểu kỹ hơn về thuật toán ECDSA cũng như để lý giải lý do vì sao mà thuật toán này lại được dự đoán soán ngôi RSA, hãy xem chi tiết tại bảng so sánh sau:

Độ dài lưu khóa ngắn

Chú thích:

• Mức độ bảo mật ở đây được định lượng bởi số bit khóa tiêu chuẩn trên lý thuyết cần sử dụng để đảm bảo độ bảo mật của ‘n’ bit.
• Độ dài khóa công khai cũng được đo bằng bit, nhưng nó là một khái niệm hoàn toàn khác, đề cập đến độ dài vật lý của chìa khóa.

Tiêu tốn ít tài nguyên trên hệ thống

Như bảng trên, có thể thấy được mặc dù cùng một mức độ bảo mật nhưng độ dài của khóa sử dụng thuật toán ECDSA lại nhỏ hơn rất nhiều so với khóa sử dụng thuật toán RSA. Đối với các doanh nghiệp lớn, họ cần lưu trữ lại rất nhiều khóa, khi đó đòi hỏi doanh nghiệp cần có đủ nguồn lực về hạ tầng để đáp ứng nhu cầu lưu trữ trên. Giả dụ, có 1 thiết bị lưu trữ với dung lượng 2048bit, nếu sử dụng RSA, ta chỉ có thể lưu trữ được 1 khóa duy nhất, còn đối với ECDSA, ta có thể lưu tới 9 khóa cùng mức độ bảo mật, mở rộng không gian lưu trữ gấp 9 lần và còn tiết kiệm được chi phí.

Rút ngắn thời gian ký số

Đối với thuật toán ECDSA, quá trình mã hóa và giải mã được rút ngắn, đồng thời cũng giảm bớt năng lượng cần sử dụng trong quá trình, hơn hẳn so với việc sử dụng thuật toán RSA. Cụ thể, khóa của ECDSA nhỏ, nên việc tạo chữ ký số sẽ nhanh hơn, giảm tải chu kỳ xử lý của CPU, không chỉ vậy, với việc sử dụng khóa của thuật toán ECDSA, chứng chỉ an toàn sẽ nhỏ và ít dữ liệu hơn, điều này hỗ trợ đẩy nhanh quá trình kết nối, cải thiện tốc độ internet.

Tăng cường độ bảo mật

ECDSA sử dụng các thuật toán phức tạp trên đường cong elliptic vào các quá trình tạo khóa, mã hóa và giải mã, giúp cho thông tin được tăng tính bảo mật, làm hacker khó khăn khi đánh cắp thông tin và hầu như là không thể hack được. Điều này làm cho ECDSA trở thành thuật toán bảo mật mạnh mẽ.

Dễ dàng thấy được thuật toán ECDSA đáp ứng được các vấn đề mà RSA còn chưa được tối ưu như độ dài khóa, hiệu suất. Và không có gì ngạc nhiên khi ECDSA được dự đoán là soán ngôi của RSA.

Ứng dụng của ECDSA trong chữ ký số​

Việc áp dụng ECDSA cũng tương tự như hệ mật RSA trong lĩnh vực chữ ký số. Gồm có ba quá trình: tạo khóa, mã hóa và giải mã và chỉ khác về mặt thuật toán và cách thức hoạt động.

Được dùng để ra cặp khóa ECDSA

Để sinh cặp khóa của ECDSA, ta sử dụng phép nhân qua thuật toán mã hóa đường cong elliptic

• Bước 1: Chọn 1 điểm bất kì trên đường cong gọi nó là điểm sinh G.
• Bước 2: Chọn một số ngẫu nhiên dA, đây chính là khóa bí mật.
• Bước 3: Sử dụng phép nhân dA với G ta được điểm gọi là QA, đây chính là khóa công khai.

Đã có cặp khóa công khai và bí mật tiếp theo ta sẽ áp dụng nó vào quá trình ký và xác nhận chữ ký.

Được dùng để tạo ra chữ ký với ECDSA

Đầu tiên ta sẽ phải tạo chữ ký, chữ ký này có 2 phần ta gọi là R và S, để tạo chữ ký ECDSA (R, S) ta sẽ có các bước sau:

• Bước 1: Tạo ra một giá trị ngẫu nhiên gọi là K
• Bước 2: Ta tính P(x,y)=K×G, lấy Px được phần R của chữ ký
• Bước 3: Tính S. Đầu vào sẽ là tin nhắn đã được băm m cùng với dA, nghịch đảo của k và R

Sau khi có được chữ ký, tiếp theo ta cần phải xác minh chữ ký ta có các bước sau đây:

• Bước 1: Sử dụng khóa công khai QA cùng điểm G và tin nhắn đã băm m​
• Bước 2: Tính nghịch đảo của S trong chữ ký và gọi nó là S^(-1)​
• Bước 3: Khôi phục điểm ngẫu nhiên P từ G, hàm đã băm m, S^(-1), R và QA​

• Bước 4: So sánh nếu Px=R thì chữ ký hợp lệ, ngược lại là không hợp lệ​

Hình ảnh minh họa quá trình ký ECDSA​

Thực tế đã có một số doanh nghiệp, công ty hàng đầu của Mỹ đã đưa ECDSA vào sử dụng như dùng xác thực cho các trình quyệt web an toàn qua SSL/TLS cụ thể hơn nếu truy cập các trang web như Google.com, Amazon.com, Facebook.com… sau đó truy cập vào chứng chỉ an toàn ta sẽ thấy được.

Hình ảnh chứng chỉ an toàn của Google
​

Ngoài ứng dụng trong chữ ký số, ECDSA còn được sử dụng để bảo vệ thông tin liên lạc nội bộ, trong các dự án nó sử dụng để giúp đảm bảo ẩn danh, nó cũng được dùng để chứng minh quyền sở hữu trong bitcoin, cung cấp chữ kí số trong dịch vụ iMessage của Apple, và dùng để mã hóa thông tin DNS với DNSCurve.​

Thuật toán ECDSA tại Việt Nam​

Ở nước ngoài, thuật toán ECDSA đã và đang được đưa vào sử dụng trong các doanh nghiệp, còn ở Việt Nam tương lai của ECDSA như thế nào?

Theo như tìm hiểu thì mô hình CA nước ta đang sử dụng là Hierarchical Model (mô hình CA phân tầng) và các doanh nghiệp lớn vẫn đang sử dụng thuật toán RSA.

Mô hình Hierarchical Model
​

Mô hình Hierarchical Model bắt đầu từ RootCA. Nó sẽ ban hành chứng chỉ cho chính nó cùng với các CA cấp dưới, khi đó các CA cấp dưới sẽ giữ khóa công khai của RootCA và để đảm bảo có thể đồng bộ được tất cả các CA một cách chắc chắn, ta cần dùng chung một thuật toán để hạn chế sai sót. Vì vậy, việc chuyển đổi thuật toán mới sẽ cần phải có sự đồng thuận từ tất cả các nhà CA.

Nhưng với những thế mạnh của thuật toán ECDSA tôi tin rằng thuật toán này sẽ nhanh chóng thay thế RSA, trở thành thuật toán phổ biến nhất tại Việt Nam trong tương lai. Mong rằng bài viết này sẽ giúp các bạn có cái nhìn tổng quát hơn về ECDSA. Hẹn gặp các bạn trong những bài viết tiếp theo.