Какви са предизвикателствата при генериране на 1024-битови прости числа в съвременната криптография?

При ранните опити за използване на PGP през 90-те години на миналия век, процесът на генериране на ключове може да се види като изтласкващ границите на технологията за тези времена. Тогава създаването на нов ключ на машини като 80386 или 80486 под Linux отнемаше изключително много време, но технологиите от тогава до днес са претърпели значителни промени.

В наши дни, продължавайки тенденцията за подобряване на криптографските методи и оптимизиране на алгоритмите, използването на GPG (GNU Privacy Guard) за генериране на PGP ключове все още може да предизвика съобщения за недостатъчна ентропия в системата, което би било сериозно препятствие ако се появи.

За да се гарантира, че числата са наистина прости и достатъчно големи за целите на RSA криптографията, обикновено се изисква първият и последният бит на числото да бъдат зададени на 1. Последният бит се задава на 1, за да се гарантира, че числото е нечетно, тъй като всяко четно число (с изключение на 2) не може да бъде просто. Първият бит се задава на 1 за да се осигури, че числото е достатъчно голямо и заема желания брой битове, като по този начин се намалява ентропията, но се поддържа числото в необходимия диапазон.

При генерациите на ключове за RSA, обикновено се изискват две големи прости числа. На практика, ако едно от тях е 1024 бита, другото може да бъде значително по-малко – около 200 бита, и все пак комбинираният ключ да достига необходимите битове ентропия. Това добавя гъвкавост при избора на безопасни числа, което е критично за издръжливостта на криптографските алгоритми.

Алгоритъмът на Милър-Рабин, който често се използва за проверка на простота, може да се направи детерминистичен в ограничени случаи с известни бази, което позволява значително по-бърза проверка за по-малки числените диапазони. За числа с около 1024 бита обаче, базите, които правят Милър-Рабин детерминистичен, не са известни, което налага използването на вероятностни методи за проверка. Това повишава интереса към оптимизации на тези алгоритми, за да се намали времето за генериране на ключове.

В методите за паралелна изработка на ключове, може да се използва просто инкрементиране на числа и тестване, което дава възможности за оптимизации чрез използване на различни ядра или даже различни машини. Така, процеса на тестване и потвърждаване че едно число е просто, може значително да се ускори, позволявайки по-бързо генериране на криптографски ключове, което е от съществено значение за съвременните ИТ системи.