So sánh ECDSA với RSA

Giới thiệu

Gần đây, đã có nhiều cuộc thảo luận về ưu và nhược điểm của RSA[01]
và ECDSA[02], trong cộng đồng tiền điện tử. Đối với những người không quen biết, họ là hai trong số
các thuật toán chữ ký số được sử dụng rộng rãi nhất, nhưng ngay cả đối với công nghệ cao hơn
hiểu biết, nó có thể khá khó khăn để theo kịp với sự thật. Bài viết này là một
cố gắng so sánh đơn giản hóa hai thuật toán. Mặc dù, đây không phải là
một bài luận kỹ thuật sâu sắc, người đọc thiếu kiên nhẫn hơn có thể kiểm tra kết thúc của
bài viết cho một bảng TL; DR nhanh chóng với phần tóm tắt của cuộc thảo luận.

ECDSA và RSA

ECDSA và RSA là các thuật toán được sử dụng bởi mật mã khóa công khai[03] hệ thống,
để cung cấp một cơ chế cho xác thực. Mật mã khóa công khai là
khoa học thiết kế hệ thống mật mã sử dụng các cặp khóa: a công khai
chính (do đó tên) có thể được phân phối miễn phí cho bất cứ ai, cùng với một
tương ứng khóa cá nhân, mà chỉ được biết đến với chủ sở hữu của nó. Xác thực
đề cập đến quá trình xác minh rằng một thư, được ký bằng khóa cá nhân, là
được tạo bởi người giữ một khóa riêng cụ thể. Các thuật toán được sử dụng cho
xác thực được gọi chung là thuật toán chữ ký số [04.

Các thuật toán như vậy dựa trên các vấn đề toán học phức tạp tương đối đơn giản
để tính toán một cách, mặc dù khá không thực tế để đảo ngược. Điều này có nghĩa là cho
Kẻ tấn công giả mạo chữ ký số, mà không có bất kỳ kiến ​​thức nào về tư nhân
chính, họ phải giải các bài toán khó hiểu, chẳng hạn như số nguyên
nhân tố hóa, mà không có giải pháp hiệu quả được biết đến [05].

Trên tài khoản đó, vì không có giải pháp hiệu quả nào cho
các vấn đề toán học cơ bản, đánh giá các thuật toán mật mã có thể
chỉ xảy ra đối với các chi tiết thực hiện của họ kết hợp với
mức độ bảo mật họ cung cấp. Đối với mục đích này, phần này trình bày một
so sánh RSA và ECDSA bằng cách sử dụng năm (hoặc sáu) số liệu định lượng. Mỗi số liệu
được giới thiệu trong phần riêng của mình, cùng với ý nghĩa của nó đối với bất kỳ ai
cố gắng quyết định giữa hai thuật toán.

Nhận con nuôi

RSA là tiêu chuẩn công nghiệp cho mật mã khóa công khai trong nhiều năm
hiện nay. Hầu hết SSL /TLS chứng chỉ đã (và vẫn đang) được ký bằng các khóa RSA.
Mặc dù hiện tại, hầu hết các CA đã triển khai hỗ trợ cho ECDSA
giấy chứng nhận, việc áp dụng lâu dài này đã dẫn đến nhiều hệ thống di sản chỉ
hỗ trợ RSA. Do đó, nếu một nhà cung cấp yêu cầu khả năng tương thích ngược với cũ
phần mềm máy khách, họ buộc phải sử dụng các chứng chỉ đã ký với RSA. Ngày nay,
mặc dù, hầu hết các khách hàng hiện đại đã triển khai hỗ trợ cho ECDSA, điều này sẽ
có thể loại bỏ ràng buộc tương thích này trong tương lai gần.

Tiêu chuẩn trưởng thành

RSA lần đầu tiên được chuẩn hóa cho SSL /TLS vào năm 1994 [06], trong khi ECDSA được giới thiệu
trong đặc điểm kỹ thuật của TLS v1.2 năm 2008 [07]. Sự chênh lệch tuổi tác này cho thấy một
sự chênh lệch về độ chín của các tiêu chuẩn mô tả các thực tiễn tốt nhất cho
từng thuật toán. Mặc dù, các tiêu chuẩn RSA đã được nghiên cứu rộng rãi và
đã được kiểm toán, ECDSA đã không được chú ý nhiều. Gần đây, ủng hộ điều này
thuật toán của các CA chính và việc áp dụng nó trong SSL /TLS khách hàng có
dẫn đến nghiên cứu sâu rộng hơn được công bố, nhưng nó vẫn còn là một
Đề án tương đối mới. Điều này để lại chỗ cho các lỗi thiết kế chưa được khám phá hoặc
triển khai sai lầm được tiết lộ trong tương lai.

Tỷ lệ kích thước khóa đến mức bảo mật

Cấp độ bảo mật [08] là một số liệu về mật mã, đề cập đến sức mạnh
của một chức năng hoặc nguyên thủy mật mã. Nó thường được đo bằng "bit"
biểu thị số lượng hoạt động mà kẻ tấn công cần thực hiện để thỏa hiệp
Bảo vệ. Số liệu này có thể cung cấp một phương pháp định lượng để so sánh hiệu quả
của các hệ thống mật mã khác nhau. Cần nhấn mạnh rằng kích thước khóa công khai cũng là
được đo bằng bit, nhưng nó là một khái niệm hoàn toàn khác, đề cập đến
kích thước vật lý của chìa khóa.

Về vấn đề này, khóa chung RSA 2048 bit cung cấp mức bảo mật là
112 bit. Tuy nhiên, ECDSA chỉ yêu cầu các khóa công khai có kích thước 224 bit để cung cấp
cùng mức bảo mật 112 bit. Sự khác biệt nổi bật về kích thước khóa này có hai
ý nghĩa quan trọng. Kích thước khóa nhỏ hơn yêu cầu ít băng thông hơn để thiết lập
SSL /TLS phát trực tuyến, có nghĩa là chứng chỉ ECDSA là lý tưởng cho thiết bị di động
các ứng dụng. Hơn nữa, các chứng chỉ như vậy có thể được lưu trữ vào các thiết bị với nhiều
hạn chế hơn các hạn chế bộ nhớ, một thực tế cho phép m /TLS ngăn xếp để được
triển khai trong các thiết bị IoT mà không phân bổ nhiều tài nguyên. Được phát hành
nghiên cứu, thậm chí cho thấy rằng ECDSA hiệu quả hơn [09] để thực hiện trong nhúng
thiết bị.

Hiệu suất và thời gian phức tạp

Thuật toán là các công thức trừu tượng mô tả một phương pháp để đạt được một mục tiêu nhất định.
Trong khoa học máy tính, hiệu suất của chúng được đo bằng cách đếm số lượng
các hoạt động cơ bản cần thiết để đạt được kết thúc định trước này
tình trạng. Số liệu như vậy được gọi là phức tạp thời gian. Vì đầu vào khác nhau
kích thước yêu cầu số lượng hoạt động khác nhau, độ phức tạp thời gian thường
thể hiện như một hàm của kích thước đầu vào.

Cả hai thuật toán trong câu hỏi, thực hiện về cùng một thời gian
các phép toán, chẳng hạn như phép chia và phép nhân. Do đó, kích thước đầu vào
(trong trường hợp này là kích thước của các phím của họ) vẫn là đáng kể nhất
yếu tố ảnh hưởng đến hiệu suất của họ. So sánh hai thuật toán, cần phải được
phân biệt giữa ký một tin nhắn và xác minh một chữ ký. Ở hầu hết các
triển khai thực tế, RSA dường như nhanh hơn đáng kể so với ECDSA trong
xác minh chữ ký, mặc dù nó chậm hơn trong khi ký.

Mọi thứ trở nên phức tạp đối với các cấp độ bảo mật cao hơn. Ví dụ, trong hầu hết
Cấu hình phổ biến ở mức bảo mật 112 bit, RSA yêu cầu 2048 bit
so với ECDSA cần các khóa 224 bit. Ở mức phổ biến tiếp theo là 128 bit, RSA
yêu cầu khóa 3072 bit, trong khi ECDSA chỉ 256 bit. Điều này dẫn đến RSA's
hiệu suất giảm đáng kể, trong khi ECDSA chỉ bị ảnh hưởng một chút. Như
hậu quả của vấn đề mở rộng này, mặc dù RSA có vẻ hiệu quả hơn tại
Thời điểm này, sự gia tăng liên tục trong các yêu cầu bảo mật rất có thể khiến
ECDSA là giải pháp thực tế trong tương lai.

Kháng sau lượng tử

thuật toán Shor của [10] là một thuật toán nổi tiếng để phá khóa RSA bằng cách sử dụng
máy tính lượng tử. Vì không có triển khai thực tế (công khai) của một
Máy như vậy, sau đây là một phỏng đoán về tương lai của khóa công khai
mật mã. Tại thời điểm viết bài này, cách triển khai tốt nhất của Shor's
thuật toán có thể đánh bại mã hóa RSA 15 bit. Mặc dù điều này không có âm thanh
liên quan, vì ngày càng có nhiều nghiên cứu hướng tới điện toán lượng tử, RSA
có thể gặp rắc rối nghiêm trọng bất cứ lúc nào.

Mặc dù vậy, những người ủng hộ ECDSA không nên nhanh chóng ăn mừng vì hình elip
mật mã đường cong cũng dễ bị tổn thương [11] sang phiên bản sửa đổi của Shor's
thuật toán. Do đó, nếu cả hai mật mã có thể bị phá vỡ bởi một máy tính lượng tử,
chỉ số khách quan duy nhất là độ phức tạp cần thiết để thực hiện như vậy
tấn công. Theo nghiên cứu công khai, khóa RSA 2048 bit cần 4098 qubit
(và 5.2 nghìn tỷ cổng Tofolli) bị đánh bại, trong khi các khóa 256 bit của ECDSA
chỉ cần 2330 qubit (và 126 tỷ cổng Tofolli). Do đó, RSA là nhiều hơn
tốn kém để phá vỡ, sử dụng một máy lượng tử lý thuyết.

Kết luận

Mặc dù sự so sánh này không có nghĩa là toàn diện, nhưng rõ ràng là
RSA đã có được vị trí là chữ ký số hàng đầu
thuật toán cho hầu hết các ứng dụng chứng chỉ. Tuy nhiên, vì công nghệ luôn luôn
tiến bộ theo những cách khó lường hơn, nhận thức và nhu cầu bảo mật cũng được
tăng. Hơn mười năm trước, bảo mật thiết bị nhúng là
viễn tưởng và truyền thông an toàn ngày nay là điều bắt buộc đối với bất kỳ thế giới thực nào
ứng dụng. Kết quả là, ngay cả khi ECDSA tương đối trẻ, nó là của bất kỳ ai
đoán xem nó có thay thế RSA làm tiêu chuẩn xác thực trong SSL /TLS
thực hiện.

Nếu bạn, người đọc, vẫn không thể quyết định nên chọn thuật toán nào, có
các giải pháp hỗ trợ cả ECDSA và RSA (như một cơ chế dự phòng), cho đến khi
cộng đồng tiền điện tử giải quyết một người chiến thắng. Kiểm tra phần bài viết này cho một tương lai
Hướng dẫn Cách làm.

Bảng TL; DR

dự án

• [01] Thuật toán RSA
• [02] Thuật toán ECDSA
• [03] Mật mã khóa công khai
• [04] Thuật toán chữ ký số
• [05] Độ phức tạp NP
• [06] SSL v.0.0 RFC
• [07] TLS v.1.2 RFC
• [08] Cấp độ bảo mật
• [09] RSA so với ECC cho các hệ thống nhúng
• [10] Thuật toán rút gọn
• [11] Ước tính tài nguyên lượng tử cho ECDL