RSA и safe primes

Не подскажут ли здешние спецы по криптографии, обязательно ли в качестве p и q в RSA выбирать safe prime (когда (num-1)/2 = prime), или подойдут любые простые числа?
Если safe prime требуется обязательно, то как можно ускорить факторизацию N составленого из обычных простых?

Комментарии

—	unknown (12/04/2007 15:58) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Против RSA наиболее эффективен алгоритм общего решета числового поля.
А safe-primes защищает против менее эффективных аглоритмов факторизации (метод Полларда p-1), cycling attack.
Но были разработаны обобщения этих методов, против которых Safe primes не помогают. И все эти атаки всё равно непрактичны.

Вывод такой: толку от safe primes мало, но и хуже они не делают. Дополнительные расходы на их использование незначительны.

Хотя использование Safe Primes вроде бы и не является обязательным для RSA, их включили в некоторые стандарты.

Вот ответ от RSA labs

—	unknown (12/04/2007 16:12, исправлен 12/04/2007 16:17) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Are `Strong' Primes Needed for RSA?

Ronald L. Rivest

Robert D. Silverman

November 22, 1999

Abstract

We review the arguments in favor of using so-called "strong primes" in the RSA public-key cryptosystem. There are two types of such arguments: those that say that strong primes are needed to protect against factoring attacks, and those that say that strong primes are needed to protect against "cycling" attacks (based on repeated encryption).

We argue that, contrary to common belief, it is unnecessary to use strong primes in the RSA cryptosystem. That is, by using strong primes one gains a negligible increase in security over what is obtained merely by using "random" primes of the same size.

Т.е. на данный момент safe primes это уже (или снова пока) неактуально.

см. статью на IACR ePrint

Ваша оценка документа [показать результаты]