Có một biến thể hiệu quả của RSA sử dụng CRT
Trên thực tế, theo cách chúng tôi thường sử dụng thuật ngữ, nó không phải là 'biến thể', thay vào đó, nó là một triển khai thay thế. Nghĩa là, những thay đổi duy nhất được thực hiện đối với thuật toán RSA được thực hiện với cách thực hiện thao tác riêng tư (và định dạng của khóa riêng tư); bất kỳ ai chỉ thực hiện các hoạt động công khai không cần phải biết về việc triển khai riêng tư (tạo chữ ký hoặc giải mã khóa chung) đang làm gì.
Tôi sử dụng thuật toán CRT ở đâu (như được viết ở đó)?
Bất cứ khi nào bạn muốn hiệu quả hơn một chút (4x) và không ngại phức tạp thêm một chút. Hầu hết thời gian, đây là một sự đánh đổi đáng giá.
Ý tôi là việc thiết lập RSA đã định nghĩa cho tôi p,q,d,c và vì vậy tôi không có hệ thống đồng dư.
Trên thực tế, tất cả các tham số bổ sung $d_p, d_q, qinv$ được tính toán dễ dàng trong thời gian tạo khóa, và đó là điều chúng tôi thường làm.
Cho rằng $\log d = \log n=B$ và $\log p = \log q = B/2$ và $d,d_p,d_q$ có nhiều số 0 và 1 bằng nhau. Tôi có thể nói gì về số lượng hoạt động của kích thước $B$ của biến thể này?
Trên thực tế, số lượng 0 và 1 hầu như không liên quan, chúng ta có thể thực hiện phép lũy thừa mô đun của một $B$ giá trị bit với $(1 + o(1)) \log_2 B$ bội số mô-đun (không phụ thuộc vào trọng số hamming của số mũ); trong phạm vi của B đang được xem xét, điều này có thể là $(1 + 1/6) \log_2 B$.
Với hoạt động riêng của RSA trong sách giáo khoa, điều này liên quan đến một phép lũy thừa mô-đun duy nhất của một $B$ giá trị bit bằng một $B$ số mũ bit; đây là về $(1 + 1/6) \log_2 B$ nhân lên. Nếu chúng ta sử dụng một $O(n^2)$ thuật toán nhân mô-đun (về mức tối ưu cho phạm vi B mà chúng ta đang thảo luận - có các quy trình nhân với độ phức tạp tiệm cận thấp hơn, nhưng với các hằng số tỷ lệ lớn hơn nhiều), chúng ta đang nói về $(1 + 1/6) (\log_2 B)^3$
Bây giờ, với CRT, có hai số mũ mô-đun của hai $B/2$ từng chút một $B/2$ số mũ bit (cộng với một số thao tác cả trước và sau - cả hai đều tương đối nhanh). Sử dụng logic tương tự, điều này mất khoảng $2 (1 + 1/6) (\log_2 B/2)^3 = 1/4 (1 + 1/6) (\log_2 B)$, tức là nhanh gấp khoảng 4 lần (vâng, đây là bỏ qua một số yếu tố nhỏ); tuy nhiên, ngay cả khi chúng tôi tính đến những yếu tố nhỏ đó, CRT vẫn đáng kể nhanh hơn
