Атака на RSA при малом размере открытого текста

Есть сообщение малого размера (64 бита), из которого известно 40 бит. Это все защифровано RSA. Таких сообщение можно заполучить довольно много. Ни открытого, ни закрытого ключа не имею Задача или вскрыть закрытый ключ или вскрывать полностью сообщения за короткое время.

Порывшись на эту тему нашел очень хорошую книгу "Modern Cryptography: Theory and Practice, Wenbo Mao". В главе 8 есть пример такой атаки на RSA (даже приводится пример с расшифровкой ключа DES), но насколько я понимаю там нужно знать открытый ключ (N и e). Тогда как можно узнать N и e имея большое кол-во пар (C ; m') где m' - имеется ввиду часть от m, а C = m^e mod N.

 

bsnake

те, кто знают ответ на этот вопрос - тебе не ответят, а кто не знает -тот не знает))))
с таким же успехом ты мог бы просто задать вопрос: "Как ломануть рса????????"))))

 

Да чисто перебрать варианты - не секрет конечно... если ключик небольшой, то может и повезёт. Ну и кое-какие вещи можно и сократить\отбросить в процессе взлома, т.к. вероятность некоторых ключей меньше... Есть тут одна непонятная закономерность... Сам ещё не до конца "разжевал"...

Большое количество пар - это что за число такое?

 

TOLSTOPUZ
Ну т.е. можно заполучить очень много зашифрованных сообщений и к каждому такому сообщению знать 40 из 64 бит информации.

C1 = m1^e mod N
C2 = m2^e mod N
C3 = m3^e mod N

Для каждого m я знаю его часть, если бы я знал e и N то мог бы читать полностью m, за очень короткое время. Но ключ шифрования недоступен. Сейчас самая сложность это получить открытый ключ.

 

bsnake

вообще, не понял о чём ты)))) берёшь любой файл и шифруешь его открытым ключом - какие "40 бит")?? m1.....mn известны полностью.

 

Я в некоторых вопросах дилетант...
Взлом RSA может дать практическую пользу?

 

если ты это реализуешь - то тебя либо убъют, либо заставят работать на корпорации - но вероятность твоего физического устранения более реальна

 

Ясно. Стойкость RSA держится на угрозе физического устранения...

 

TOLSTOPUZ

не только, но KiNDeR реально прав - бабок на этом деле крутится много. мля, я б на эту тему с удовольствием написал бы биллитристику, но нет таланта писателя(

 

KiNDeR
ЛОЛ! Прям как пионеры в походе у костра страшилки рассказываешь

bsnake
Боюсь что без знания хотя бы N тебе ловить нечего.

 

CreatorCray

твоя точка зрения по весу равна точке зрения KiNDeR'a - он тебе не сможет доказать свою правоту, ибо нет у него методы, а ты свою правоту не сможешь доказать, ибо нет у тебя на руках мат. обоснования нижней границы надёжности рса, так что оставь свои колкости)) хотя, всё же надо признать, что ничто не обесценивает так бесценную жизнь человека, как презренный, и в тоже время, страстно желаемый многими металл)) теперь позволь задать тебе вопрос: что будет, если вдруг сказка станет былью - падёт рса, а может быть и другие......... погладят ли Прометея по головке иль вспомнят про его печень))???

P. S.

забавные слова: бесценный, бесценная.............

 

UbIvItS
Что за бред? Какую правоту он мне должен вдруг доказывать?
Вот этот прогон что ли?

деЦкий сад - штаны на лямках.

 

CreatorCray

да, никакую - ситуацию я описал, хотя она даже веселей)

 

CreatorCray
я ничего ни доказывать, не объяснять не собираюсь...
считаешь, это детским садом - считай...

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

конечно же это - все сказки и бред, ведь ни кто из нас не попадал в такую ситуацию...

 

KiNDeR
Да я вообще то от тебя и не требовал никаких объяснений. Это вон убивца чегой то лихорадит.

Впрочем, про бабло и RSA...

Ну вот представь - случилось невероятное и, к примеру UbIvItS, таки "сломал" RSA. Т.е. может расшифровывать любое RSA сообщение за приемлемое время.
Он опубликовал свою работу. Какой смысл его теперь устранять? Алгоритм уже скомпрометирован, алгоритм известен - смысл?

Если он же публиковать не будет а сунется с ним в криминал или спецслужбы - сам дурак. И там и там его заставят замолчать - неважно каким способом, а наработками воспользуются самостоятельно.

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

Причем еще до появления практического результата, который можно использовать, будут известны примерные черты алгоритма. Который будет проанализирован и, при достаточной вероятности осуществления атаки, RSA будет либо изменен, либо произойдет отказ от него в пользу того же ECIES (впрочем на него и так переходят). Внезапного же взлома не будет.

Поэтому, может не стоит заниматься теоретизированием касательно "убьют/не убьют того кто это хакнет" а приложить свои усилия к какой либо практической задаче? Хоть польза будет.

 

ну а что тебя останвливает?.. прилагай...

я с трудом представляю себе такого альтруиста...

 

CreatorCray

алгос сей сломаю не я)

месть.

реально.
--------------------------
ну, а теперича изложу окончательно свою точку зрения
я, конечно, люблю позубаскалить на эту тему, но не могу отрицать тот факт, что нахождение оптимальной по скорости методы вовсе не означает окончательной и бесповоротной смерти рса, например, O(n^50) - хорошо, но, ведь, жить - то можно) а сломщикам рекомендую смотреть в сторону аналоговых вычислений - бонус там имеется) мат. либы самой природы. подводных камней там тоже много, но кто нам обещал лёгкой жизни......... да, и скучна лёгкая жизнь, хотя излишне весёлая быстро утомляет)

 

UbIvItS
вскрывай!
если что, мы за тебя отомстим, мало им не покажется

 

>> месть.
Не смешите мои тапочки!

 

CreatorCray
Не месть, а устрашение : чтоб другим неповадно было публиковать такое.
ВОТ И НЕ ПУБЛИКУЕТ НИКТО :-(
А если серьезно, для постановки задачи(той с которой началось) нужно листочков 10 серьезных выкладок, а не десяток очевидных строчек. А так - пустой треп.