Безопасно ли использование функции BigInteger probablePrime для шифрования RSA?

Я написал код, который может генерировать 2048-битные простые числа p и q и использовать их для шифрования сообщений в RSA. Я генерирую эти числа с помощью функции probablePrime() пакета java.math.BigInteger. Мой вопрос заключается в том, насколько сильны шифрование, сгенерированное этими простыми числами с точки зрения шифрования.

Вот мой код для генерации этих чисел, isPrime — это просто логическая функция, которую я написал, чтобы проверить, является ли число простым.

BigInteger definitePrime(int bits, Random rnd) {
  BigInteger prime = new BigInteger("4");
  while (!isPrime (prime)) {
    prime = BigInteger.probablePrime(bits, rnd);
  }
  return prime;
}

java encryption rsa biginteger
person Omer Eldar    schedule 11.04.2015    source источник
comment
Я не хочу сомневаться в ваших навыках программирования, но вы утверждаете, что написали метод, который может эффективно проверять, являются ли значения, возвращаемые BigInteger.probablePrime(2048, new Random()), простыми?   -  person Paul Boddington    schedule 12.04.2015
comment
Здесь вы должны использовать цикл do/while, чтобы избежать инициализации и избыточного первого теста.   -  person user207421    schedule 12.04.2015
comment
Да, это цикл for, который начинается с i = 2 и продолжается до тех пор, пока i меньше квадратного корня из числа. Затем он принимает число по модулю i и, если значение равно нулю, возвращает false. Если он проходит через цикл без num%i, приводящего к нулю, он возвращает true. Это очень эффективный метод проверки того, является ли число простым.   -  person Omer Eldar    schedule 13.04.2015

Ответы (3)


arrow_upward
2
arrow_downward

Как указывает Стивен С в своем ответе, простые числа, вероятно, подходят для шифрования RSA.

Криптографическая случайность

Я бы добавил, что на самом деле вы не должны использовать какой-либо Random экземпляр, а только лучшую SecureRandom реализацию вашей системы.

new Random() не является источником криптографической случайности, тогда как new SecureRandom() должен им быть. Если случайные числа, которые используются для генерации простых чисел, не являются криптографически безопасными, то у злоумышленника может быть шанс просто воссоздать их на основе другой информации (например, времени или предыдущих выходных данных источника слабой случайности).

Нет учебника RSA

Вы делаете все сами, и кажется, что вы действительно хотите использовать это для серьезного шифрования. Если да, то вы упускаете что-то важное, и это схема заполнения.

Методы BigInteger легко использовать для реализации RSA, чтобы он работал, но этого недостаточно, чтобы сделать его безопасным. Вам необходимо использовать схему заполнения, такую ​​как PKCS#1 v1.5 (больше не рекомендуется) или PKCS#1 v2 OAEP (рекомендуется).

Используйте существующие реализации

Вместо реализации этих схем заполнения для вашего RSA, созданного вручную, используйте Cipher экземпляр, который предоставляет RSA следующие схемы заполнения:

  • RSA/ECB/PKCS1Padding
  • RSA/ECB/OAEPWithSHA-256AndMGF1Padding
person Artjom B.    schedule 12.04.2015
comment
Я делаю это только для удовольствия. Однако я хотел бы поблагодарить вас за ваш вклад, и я обязательно рассмотрю схемы заполнения. - person Omer Eldar; 13.04.2015
comment
Вам действительно нужно заполнение, если ваши входные и выходные данные представляют собой большие целые числа, которые вам не нужно преобразовывать в байты и строки? Что прокладывать в этом случае? - person Oleg Gryb; 18.05.2019
comment
@OlegGryb Заполнение необходимо только для безопасности. Если вы не заботитесь о безопасности и вам достаточно смеси безопасности и обфускации, то вы можете пропустить заполнение. Поскольку заполнение обычно применяется в двоичной форме, вам придется преобразовать ввод в байты, затем добавить заполнение (надеюсь, OAEP), преобразовать его обратно в BigInteger и выполнить оставшиеся шаги как RSA для учебника. Я бы посоветовал не реализовывать RSA или какое-либо дополнение RSA самостоятельно. Возможно, вы открываете реализацию для атак по сторонним каналам или простого криптоанализа. - person Artjom B.; 20.05.2019
comment
@Artjom B. Ты не читал мои вопросы. Ввод уже является большим целым числом. Что вы собираетесь прокладывать и как в этом случае? Еще одна важная деталь - размер меньше ключа. - person Oleg Gryb; 20.05.2019
comment
@OlegGryb Кажется, ты не читал мой ответ. Да, вам нужно дополнение, если вы хотите безопасности. Это не имеет никакого отношения к тому, есть ли у вас byte[] или BigInteger. Если у вас есть BigInteger и у вас есть функция заполнения, которая использует byte[], вам нужно преобразовать ее в byte[]. Входные данные для RSA должны быть дополнены. - person Artjom B.; 20.05.2019
comment
@Artjom B. Ни в чем нет 100%. Даже с OAEP, который семантически лучше, чем PKCSv1.5, можете ли вы сказать, что OAEP/SHA1 (не говоря уже о PKCSv1.5) небезопасны и все должны использовать OAEP/SHA256? Сказать, что что-то безопасно или небезопасно, мало что говорит. Было бы неплохо увидеть, сколько попыток грубой силы требуется для взлома RSA, RSA/PKCS1.5, RSA/OAEP/SHA1 и RSA/OAEP/SHA256. Для AES 128 или 256 я видел цифры. Если у вас есть что-то для RSA, пожалуйста, поделитесь. Безопасность — вещь сравнительная. - person Oleg Gryb; 20.05.2019
comment
@OlegGryb Правильно, безопасность оценивается по сравнению с другими механизмами. Я не могу указать вам ресурс, который показывает, сколько лет ЦП необходимо для грубой силы учебника RSA, RSA с заполнением PKCS1.5 и с OAEP. Я знаю, что учебник RSA считается недостаточным для криптографов с первых лет, когда была задумана RSA. Учебник RSA может подойти, если открытый текст выбран случайным образом, но он не обязательно должен быть безопасным. В последние годы набивка PKCS 1.5 привлекла большое внимание, и в гроб было забито несколько гвоздей. ОАЭП нет, несмотря на то, что он тоже довольно старый. - person Artjom B.; 21.05.2019
comment
... OAEP может использовать две разные хеш-функции. Насколько я помню из дискуссий по Криптографии, когда SHA1 был взломан два года назад, SHA1 для MGF все еще был в порядке, а SHA1 для хеширования - нет. - person Artjom B.; 21.05.2019
comment
@Artjom B. Забивать гробы - это перспективное дело. Прошло некоторое время с тех пор, как 3DES и CBC называли небезопасными, но реальность такова, что индустрия даже близко не избавится от 3DES, и никто всерьез не рассматривает возможность удаления CBC из существующих приложений. Если вы проводите картой на более старом терминале, вероятность того, что используется 3DES, очень высока. Из-за этого никто не перестает пользоваться картами. SHA1 по-прежнему подходит для таких случаев, как PBKDF/SAH1 и OAEP/SHA1, поэтому безопасность следует оценивать в зависимости от вариантов использования, чтобы избежать ненужных расходов. - person Oleg Gryb; 21.05.2019

arrow_upward
1
arrow_downward

В javadoc для BigInteger.probablePrime() говорится :

Возвращает положительное значение BigInteger, которое, вероятно, является простым числом с указанной длиной бита. Вероятность того, что BigInteger, возвращаемый этим методом, является составным, не превышает 2-100.

2-100 означает один шанс из 1 267 650 600 228 229 401 496 703 205 376; т. е. 1 шанс из ~1,267 * 1030

Поскольку вы пытаетесь сгенерировать 2 простых числа, это означает, что у вас есть 2 шанса примерно из 1030 создать слабую пару ключей RSA.

Я бы подумал, что этого достаточно, но если вы так не думаете, вы можете использовать BigInteger.isProbablePrime(certainty) для проверки своих основных кандидатов с еще более высоким уровнем достоверности.

Мой вопрос заключается в том, насколько сильны шифрование, сгенерированное этими простыми числами с точки зрения шифрования.

Я не знаю, существует ли математически строгий способ количественной оценки силы алгоритма шифрования. Но приведенный выше анализ говорит вам о вероятности того, что данная сгенерированная пара ключей будет слабой/легко взломанной.

person Stephen C    schedule 12.04.2015
comment
Спасибо за ваш вклад, это определенно достаточная вероятность для меня. - person Omer Eldar; 13.04.2015

arrow_upward
-1
arrow_downward

Сгенерированные простые числа не являются безопасными, если вы используете что-то вроде java.util.Random вместо экземпляра SecureRandom. Ваш фрагмент кода не сообщает нам, что вы используете, поэтому невозможно проверить ваш код. Конечно, вам, вероятно, следует просто использовать JCE для создания новых ключей RSA.

person duh    schedule 12.04.2015