Generowanie 4096-bitowego klucza RSA jest wolniejsze niż 2048-bitów przy użyciu Jsch

Question

Potrzebuję utworzyć publiczne i prywatne klucze RSA dla aplikacji klient/serwer i używam do tego celu JSch library. Do tej pory generowałem klucze 4096-bitowe, ponieważ chciałbym mieć najlepsze możliwe zabezpieczenia. Zajmuje to od 3 do 5 minut, podczas gdy generowanie klucza 2048-bitowego zabiera coś w tempie 10 sekund. Masz 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."); 
    } 
} 

Czy należałoby oczekiwać tak dużej różnicy w czasie generowania? Nie jestem super jasne, w jaki sposób generowane są klucze RSA (stąd przy użyciu biblioteki), ale przypuszczam, że wymagany czas może być wykładniczy? To po prostu wydaje się ... zbyt wykładnicze.

Oto JSch API (ponieważ sama biblioteka i strona internetowa, z której pochodzi, nie zawierają dokumentacji).

Aktualizacja: Zrobiłem profilowanie. Oto wykres czasów keygen, zaczynając od 512 bitów i idąc do 4096, z 30 próbkami na klucz.

A oto podobny wykres z badań 4096-bitowych wykluczona (samego zestawu danych):

Te wyglądają bardzo podobnie, co oznacza dość gładki wykładniczy wzrost czasu. Chyba jestem po prostu niecierpliwy!

Answer 1

Generowanie klucza RSA wymaga znalezienia dwóch dużych, losowych liczb pierwszych spełniających określone kryteria. Znalezienie takich liczb pierwszych jest w istocie kwestią wybierania liczb losowych, a następnie sprawdzania, czy są one najlepsze, czy nie, poprzez wykonanie pewnych testów. Prime Number Theorem mówi nam, że w miarę jak liczby pierwsze stają się większe, stają się coraz rzadsze, więc musisz wygenerować więcej liczb losowych, aby znaleźć taki, który jest najlepszy. Sprawdzanie, czy liczba jest liczbą pierwszą, również zajmuje więcej czasu w przypadku większych liczb.

Wszystkie powyższe czynniki przyczyniają się do wydłużenia czasu potrzebnego na wygenerowanie większych klawiszy, jednak to brzmi, jakby ta biblioteka nie była szczególnie szybka. Używając OpenSSL na dość nowoczesnym komputerze mogę wygenerować klucz 2048 bitów w ~ 1 sekundę i 4096 bitowy klucz w < 10 sekund, więc twoje czasy 10 sekund i 3-5 minut wydają się wygórowane. Jeśli wydajność jest problem, proponuję wypróbować inną bibliotekę, z tym że biblioteka będzie wolniej generować duże klucze niż mniejsze!

Answer 2

Generowanie klucza o długości 4096 bitów zajmuje znacznie więcej czasu niż klucz 2048 bitowy, patrz wartości odniesienia here.

Answer 3

Trochę późno na odpowiedź, ale jak inne odpowiedzi są czysto heurystyczny, oto niektóre tła o tym, dlaczego to trwa tak znacznie dłużej:

Najwolniejszym częścią generowania kluczy RSA jest zwykle test Fermata, które musi być uruchamiany dla każdego głównego kandydata x i polega na sprawdzeniu, czy 2^{x-1} = 1 modulo x [za pomocą 2 można dokonać szybciej niż przy użyciu innych baz]. Jak więc czas potrzebny na testy Fermata zależy od długości bitów x?

1) Czas trwania mnożenia wynosi około kwadratów w długościach bitowych czynników, więc podwojenie długości czterokrotnie zwiększa czas (to jest dla mnożenia w szkole, jeśli używasz Karatsuba, to jest to około trzykrotnego czasu; zaawansowane metody mnożenia długości bitów RSA są zbyt krótkie).

2) Czas działania potęgowania modułowego jest liniowy w długości bitu wykładnika.

3) Prawdopodobieństwo, że losowa liczba n-bitów będzie pierwsza, wynosi 1: log (2^n), gdzie log jest logarytmem naturalnym, tzn. Jest to 1: (n * log (2)).

Tak więc podwojenie długości bitowej daje współczynnik 4 od 1) i dwa razy współczynnik 2 od 2) i 3) czas działania generowania klucza RSA, czyli całkowity czas działania Fermata testy zwiększają się o współczynnik 16 (lub 12 przy użyciu Karatsuba). Ponieważ istnieją inne części generacji kluczy, których czas działania nie wzrasta tak szybko, więc współczynnik około 10, jak wskazuje Iridium, jest rozsądny.