Tạo khóa RSA 4096 bit chậm hơn 2048 bit bằng cách sử dụng Jsch

Question

Tôi cần tạo khóa RSA công khai và riêng tư cho ứng dụng khách/máy chủ và tôi đang sử dụng JSch library để làm như vậy. Tôi đã tạo ra các khóa 4096 bit cho đến bây giờ, vì tôi muốn có bảo mật tốt nhất có thể. Tuy nhiên, điều này mất 3 ~ 5 phút, trong khi tạo ra một khóa 2048-bit mất một cái gì đó để điều chỉnh 10 giây. Có một sscce:

import com.jcraft.jsch.JSch; 
import com.jcraft.jsch.JSchException; 
import com.jcraft.jsch.KeyPair; 

public class KeyGenerator { 

    public static void main(String[] args) { 
     JSch jsch = new JSch(); 

     System.out.println("Starting..."); 

     try { 
      KeyPair keyPair = KeyPair.genKeyPair(jsch, KeyPair.RSA, 4096); 
     } 
     catch (JSchException e) { 
      e.printStackTrace(); 
     } 

     System.out.println("Done."); 
    } 
} 

có sự khác biệt lớn này trong thời gian thế hệ được mong đợi? Tôi không siêu rõ ràng về cách các khóa RSA được tạo ra (do đó sử dụng một thư viện) nhưng tôi cho rằng thời gian cần thiết có thể là theo cấp số mũ? Có vẻ như ... quá mũ.

Đây là JSch API (do chính thư viện và trang web đến từ bên cạnh không có tài liệu).

Cập nhật: Tôi đã thực hiện một số hồ sơ. Dưới đây là một biểu đồ của thời gian keygen, bắt đầu từ 512 bit và đi lên đến 4096, với 30 mẫu cho mỗi kích thước khóa.

Và đây là một biểu đồ tương tự với các thử nghiệm 4096-bit loại trừ (cùng bộ dữ liệu):

Những trông khá giống nhau, biểu thị một sự gia tăng theo cấp số nhân khá trơn tru trong thời gian. Tôi đoán tôi chỉ thiếu kiên nhẫn!

Answer 1

Tạo khóa RSA yêu cầu tìm hai số nguyên tố ngẫu nhiên lớn đáp ứng các tiêu chí nhất định. Việc tìm kiếm các số nguyên tố như vậy về cơ bản là vấn đề chọn số ngẫu nhiên và sau đó kiểm tra xem chúng có phải là số nguyên tố hay không bằng cách thực hiện các thử nghiệm nhất định. Prime Number Theorem cho chúng ta biết rằng khi số nguyên tố lớn hơn, chúng cũng trở nên hiếm hơn, do đó bạn phải tạo ra nhiều số ngẫu nhiên hơn để tìm số nguyên tố chính. Việc kiểm tra để xác định xem số có phải là số nguyên tố cũng mất nhiều thời gian hơn cho các số lớn hơn hay không.

Tất cả các yếu tố trên góp phần tăng thời gian cần thiết để tạo ra các khóa lớn hơn, tuy nhiên điều này sang một bên, có vẻ như thư viện này không phải là đặc biệt nhanh. Sử dụng OpenSSL trên một máy tính hiện đại hợp lý tôi có thể tạo ra một khóa 2048 bit trong ~ 1 giây và một phím 4096 bit trong < 10 giây, vì vậy thời gian của bạn 10 giây và 3-5 phút có vẻ quá mức. Nếu hiệu suất là vấn đề, tôi khuyên bạn nên thử một thư viện khác, với sự hiểu biết hơn mọi thư viện sẽ chậm hơn để tạo các khóa lớn hơn các thư nhỏ hơn!

Answer 2

Tạo khóa dài 4096 bit mất nhiều thời gian hơn nhiều so với khóa 2048 bit, xem số điểm chuẩn here.

Answer 3

Một hơi muộn cho một câu trả lời, nhưng là câu trả lời khác là hoàn toàn heuristic, ở đây một số nền tảng về lý do tại sao phải mất quá nhiều thời gian hơn:

Phần chậm nhất của một thế hệ khóa RSA thường là kiểm tra Fermat, mà phải được chạy cho mỗi ứng cử viên chính x và bao gồm kiểm tra nếu 2^{x-1} = 1 modulo x [sử dụng 2 có thể được thực hiện nhanh hơn so với sử dụng các căn cứ khác]. Vậy thời gian cần thiết cho các bài kiểm tra Fermat phụ thuộc vào độ dài bit của x là bao nhiêu?

1) Thời gian chạy cho phép nhân là về bậc hai trong các bit-chiều dài của các yếu tố, do đó tăng gấp đôi chiều dài gấp bốn lần thời gian (đó là cho phép nhân học, nếu bạn sử dụng Karatsuba, sau đó nó khoảng gấp ba lần thời gian; để biết thêm phương pháp nhân phức tạp, độ dài bit của RSA quá ngắn).

2) Thời gian chạy cho một lũy thừa môđun là tuyến tính theo chiều dài bit của số mũ.

3) Xác suất cho số n bit ngẫu nhiên là số nguyên tố là 1: log (2^n), trong đó log là logarit tự nhiên, tức là 1: (n * log (2)).

Vì vậy, tăng gấp đôi độ dài bit cung cấp cho bạn hệ số 4 từ 1) và gấp hai lần hệ số 2 từ 2) và 3) cho thời gian chạy của quá trình tạo khóa RSA, vì vậy tổng thời gian chạy cho Fermat thử nghiệm tăng lên theo hệ số 16 (hoặc 12 bằng Karatsuba). Vì có các phần khác của việc tạo khóa mà thời gian chạy không tăng lên nhanh chóng, nên hệ số khoảng 10 như được chỉ ra bởi Iridium là hợp lý.