пришел звиздец RSA

Так и делают (Есть спец процессора которое это реализуют). Это проще и быстрей.
А все алгоритмы поиска простых чисел нужны чисто для иследований.

Для практического применения я прогу не писал. Я иследовал распределение простых чисел (невроде тервера)
Довольно интересная гистограмма получается если строить её по расстояниям.

Ненадо сравнивать обычный комп и квантовый.
Полно примерев на которых плохо работает квантовый и на оборот для булевых

 

Разности между простыми числами тебе для нахождения множителя не помогут (особенно на значениях реальных ключей использующих RSA - 512-1024 бита).
Теперь, условно согласимся что для 2^32 тебе хватит 193 Мб - значит для 2^33 тебе уже нужно как минимум 386 Мб - а для 256-512 бит (размер множителя реального ключа) соответственно 193*2^(224-480) Мб памяти (что нереально ни для спецпроцессоров, ни для всех компьютеров Земли в настоящее время).
Насчет спецпроцессоров - "не надо песен" (максимум из устройств такого рода - Twinkle, теоретически разработанный в Израиле, да и D. Bernstain с его предположениями по ускорению поиска зависимостей для GNFS путем аппаратных решений) - они юзают ранее упомянутый мной алгоритм GNFS и никакого перебора (и несмотря на свою "аппаратность", для Twinkle нужен ГОД для факторизации 512 битного числа).

 

Для 128 еще можно таблицу хранить (самые распостроненные ключи)

В остальном я согласен (чем больше число тем больше расстояние -> нужно более 1 байта для его хранения)

Вопрос:
Наскока качественно современные реализации RSA выбирают P и Q?

P.S. Думаю у спецов есть чето помощней если они пропустили этот алгоритм как стандарт. (даже наша гос. противится сложным шифрам неговоря уж про США).

 

P & Q при выборе являются safeprime (P-1)/2 = prime, (Q-1)/2 = prime.
эээ... ты считаешь, что 128 битное шифрование означает 128 битные ключи???
Для справки, 128 битный ключ шифрования используется в симметричных шифрах (в которых он передается один раз при установке соединения, зашифрованный ключом RSA гораздо большим чем размер ключа для симметричного шифрования в рамках сессии), так что найти ключ RSA 128 бит тебе не удастся (и зачем городить огород - числа 128мибитные легко раскладываются в Maple, Mathematica, CrypTool), только это не RSA модули.

 

Оффтоп
Ссылку нашел странную
http://www.beton-smesi.biz/odp/index.php?c=/Science/Math/Number_Theory/Prime_Numbers/
как-то не вяжется beton-smesi с тем, что в подвальной части.
Добавлено
Похоже это все взято из Гугля

 

Интересно, где это они самые распостраненные? Ни в одном нормальном решении (не считая глючных ламерских поделок) я никогда не видел использования rsa с ключем меньше 512 (типичные размеры 1024-4096).

Так что SWR, стены тут будет мало, надо еще и йаду...

 

PageFault
про 128 бит RSA - я плакал =)

но, справделивости ради, нужно сказать что такая каша не только у SWR в голове... Trillian 3 использует DH на 128 бит (что ломается сложнее чем RSA-128 но все равно ломается), в схемах регистрации некоторых программ используетя RSA-128... и во всех случаях люди думают что 128 бит - это секьюрно )


Про брутфорс RSA - это глупость. Для RSA-512 нужно 2^256 операций - нереально даже для "правительственных спецвычислителей".

 

PageFault
Еще ясельки незакончил?

flankerx
Я протоже, что многие досих пор думают что 128 - надежно. (очень много таких решений (например для быстроты шиврования )) (не для смешанных шифрах)
Недавно про винт читал который как раз шифрует 128 битным RSA алгоритмом.

>>Про брутфорс RSA - это глупость. Для RSA-512 нужно 2^256 операций - нереально даже для "правительственных спецвычислителей".
Лучше промолчу.

 

SWR
Так называемые тобой "Смешанные шифры" имеют вполне известное и пожалуй, знакомое всем криптологам-криптографам название - RC4, RC5, RC6 и придуманы соавтором RSA (Роном Ривестом из MIT - http://www.rsa.com/rsalabs/node.asp?id=2512). Так что насчет скорости ты не прав (модулярная эскпоненциация по модулю 128 бит гораздо медленнее шифрования симметричным шифром с помощью ключа в 128 бит).

 

Более конкретно - реализации SSL используют эти "смешанные" шифры

 

Ты с какого дурдома сбежал, убогий?

Ссылку на этот бред пожалуйста.

Дада. Молчи, может за умного сойдешь.

P.S. стену советую выбирать бетонную

 

Смешанные - это когда симметричный клуч передается зашифрованный более медленным не семетричным(например RSA) и дале инфа шифруется им
, а RC4, RC5, RC6 это отдельные алгоритмы никаким боком тута не косающиеся. Обычно с рса используют дес(к).

P.S. Насчет скорости я мел ввиду, что 128 быстрее 256 и тд. (от этого его используют в харде и динамич. шивр. (так авторы прог пишут) ) Тонкостей реализации я незнаю (в винте).

 

SWR
Кури меньше.
http://www.seagate.com/docs/pdf/marketing/po_momentus_5400_fde.pdf

 

Насчет винта с RSA - считай сам:
1. Запись (то есть, возведение в степень e, равную открытому ключу, небольшому) - время T1
2. Чтение (то есть, возведение в степень d, равную закрытому ключу, порядка N) - время T2
Отношение T2:T1 ~ log2(N):log2(e)
Теперь вопрос - кому на х. такой винт нужен?

 

:off:
походу только его изобретателю )

 

это разумно =)

RC4 - обычный потоковый шифр,
RC5, RC6 - обычные блочные шифры.
Никакой "смешанности" в них нет.

Насколько я понимаю, речь идет о т.н. hybrid encryption, когда данные шифруются симметричным алгоритмом на случайном ключе, а сам этот случайный сеансовый ключ зашифровывается на открытом ключе получателя и передается абоненту.

SWR
хватит уже нести чушь про 128-битный RSA. Или примеры реальные давай (а не "в каком-то харде, про который я где-то читал и вообще не в курсе"), или иди учить матчасть.

 

flankerx
вникни в суть потом пиши.

ECk
Чето я непонял про ответ с P Q
Просто по алгоритму эти 2 числа (я так понял) обычно берут близкими -> их разряднасть в 2 раза меньше и для
перебора нужно меньше пространство простых чисел
например для 64 хатитит перебрать все числа от 0 до uint32(-1) (если не отходить от правил).

PageFault
Иди на другие форумы разводи.
Не пиши ответ.

 

SWR
Посмотри в гугле определение safeprime.
Если числа таковыми не являются, их легко разложить с помощью методов P+1, P-1.
Если являются таковыми - то только с помощью xS (QS,SIQS,MPQS,SNFS,GNFS) - короче, аглоритмами с решетом (квадратичное решето, самоинициализирующееся квадратичное решето, мультиполиномиальное квадратичное решето, особое решето числового поля, общее решето числового поля). Вообще, все алгоритмы описаны на www.mathworld.wolfram.com

 

SWR
Ты мне запрещаешь писать ответы? Да пошел ты (очень далеко...).
Ты видимо тут считаешь себя самым умным. Так вот, таких как ты пора стрелять, чтобы они не отравляли мир своей тупостью.
Если ты говоришь о легко ломаемом rsa, то докажи свои теории на практике. Вот тебе ключик в 2 раза меньший, чем обычно реально применяют. Традиционным GNFS он раскладывается на крутейшем core duo за 6 лет. Но ты авось сделаешь быстрее (самый умный ведь).

7E81A05B6D8974362B0645541524163439B2169221C4994734F8AADAC313406C8121B1E5AE23
E8701F000503B23FF8BEFC2F26123EC62E95066B82C01BC69131

 

Оффтоп
По-моему, назрела необходимость добавления в форум темы "Ринг" (как у Соловьева)