Почему KeyPairGenerator.genKeyPair() такой медленный

Question

У меня есть некоторый код Java и когда я запускаю функцию KeyPairGenerator.genKayPair() это работает 40 секунд или больше. Как изменить эту ситуацию? Если я бегу

openssl req -x509 -nodes -days 365 -newkey rsa:4096 -keyout server.key -out cert.pem 

это работает 3 секунды. Медленный код:

KeyPairGenerator gen = KeyPairGenerator.getInstance("RSA");
SecureRandom random = new SecureRandom();
gen.initialize(4096, random);        
keyPair = gen.generateKeyPair();        
PublicKey pubk = keyPair.getPublic();
PrivateKey prvk = keyPair.getPrivate();

Answer 1

Во-первых, хотя Java, безусловно, быстр в отношении бизнес-логики, оптимизированный код C (со сборкой, где он имеет значение) выбьет его из воды, когда дело доходит до криптографии. Ява будет использовать BigInteger выполнить эти расчеты, и BigInteger - насколько я знаю - не содержит родной оптимизированный множитель Монтгомери. Языки сценариев, как правило, намного хуже, чем Java, если они не вызывают нативный код.

Java также нужно время для оптимизации байтового кода. Это означает, что он работает быстрее, если он вызывается несколько раз. Поэтому вам нужно как минимум вызвать один ключевой ген, прежде чем посмотреть, что произойдет, если такой метод вызывается несколько раз в вашем приложении. В этом случае время выполнения может быть настолько высоким, что его уже можно оптимизировать - это зависит от виртуальной машины.

Генерация ключа RSA зависит главным образом от нахождения двух больших простых чисел. Поиск больших простых чисел - это процесс, требующий значительных ресурсов процессора. Это также зависит от генератора случайных чисел для создания отправных точек. Таким образом, используемая реализация генератора случайных чисел имеет большое значение, особенно если генератор случайных чисел может блокироваться, если недостаточно энтропии. Так что поиграйте с генераторами случайных чисел, пока не найдете достаточно быстрый и безопасный.

Поиск простого числа определенной длины - это процесс, который не имеет назначенного времени выполнения. Выбирается очень большое число (в данном случае размером около 2048 бит) и начинается тестирование, если последующие числа являются простыми. Это то, что забивает ваш процессор. Поэтому вам нужно рассчитать среднее время выполнения генерации простого числа - в случае, если вы генерируете много из них - или вам придется жить с неопределенностью относительно времени, которое требуется.

---

Это все немного спорно, хотя. Как правило, вам не нужно много ключей RSA - вы генерируете от одного до трех на пользователя. Так что это становится проблемой только тогда, когда 1) у вас много пользователей 2) у вас есть протокол, который требует много пар ключей или 3) вам нужны очень большие ключи RSA.

Если вы хотите иметь более быстрый способ генерации пар ключей, вы можете сделать несколько вещей:

1. получить нативную реализацию Java Provider это делает это для вас;
2. переключиться на другой алгоритм, для которого генерируется пара ключей, такой как криптография с эллиптической кривой;
3. генерировать ключи, используя openssl и просто импортируйте / используйте их в своем приложении Java;

Обычно, хотя вам нужно будет исправить протокол вместо генератора пар ключей.