информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Страшный баг в WindowsАтака на Internet
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
А мой способ не ставит целью вычислить d 21.09.04 17:38  Число просмотров: 2975
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Он по заданным c, e и n вычисляет исходный текст. К сожалению, моя идея, которую выше изложил, тоже, как и все остальные, разлетелась в пух и прах.

Не учёл я, что при переборе по алгоритму Евклида (c mod n)/m произведение (m1^e)*(m2^e)>>(c1c2) mod n (m1 - открытый текст, а m2 добавляется искусственно для "упрощения" вычислений). Если, конечно, m1>n^(1/e). Ну и отсюда уже ничего не получишь.

Если бы по полученному значению (c1c2) mod n, из которого вычислялся бы целый корень степени e, можно было бы получить сразу следующее значение, из которого корень e вычиляется, то способ был бы эффективным. Но вычислить не получается. Может быть, плохо думал.
<theory>
Идея по взлому RSA 26.08.04 09:18  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Криптографию я только начинаю изучать, так что если глупость скажу или изложу широко известный метод, просьба сильно не ругать :-)

Итак, основана моя идея на гомоморфном свойстве RSA: (m1m2)^e=(m1^e)*(m2^e)=c1c2(mod n). Если я знаю некий шифротект c, а так же открытые ключи e и n, то я могу зашифровать любой небольшой текст. Пускай, к примеру, я буду шифровать число 30. Тогда в качестве с1 у меня будет выступать текст, который необходимо взломать, а в качестве c2: 30^e mod n. Тогда при переборе c1c2(mod n), я точно знаю, что меня интересуют только те числа, которые делятся на 90 (т. к. слева стоит m2^e), что проверяется элементарно и мне не придётся каждый раз вычислять корень из e, на что приходится основная часть трудоёмкости. К тому же я могу ещё больше сократить область поиска, если учесть, что меня интересуют только те значения, получающиеся при переборе, которые больше n*(30^e) (т. к. m в целях безопастности делают больше n^(1/e)). Можно ещё больше сократить область поиска - тут я уже не думал, но все стандартные свойства здесь работают, так что потери во времени при взломе не будет.

А вот дальше я в своих действиях не совсем уверен. Получается так, что как только у меня выходит число, кратное 90, у меня появляется шанс, что из него можно извлечь корень e (после деления на 30^e). А вот насколько меньше "левых" шансов будет выпадать по сравнению с обычным логарифмированием - не совсем понятно. И будет ли их вообще меньше? Тут я с математикой уже обламываюсь. Может, есть у кого какие идеи?
Тогда для "взлома" нужно знать один из множителей исходного сообщения, насколько я понял. 26.08.04 10:04  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
<"чистая" ссылка>
Нет, видимо я путано объяснил. Идея какая: при обычном... 26.08.04 10:52  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Нет, видимо я путано объяснил. Идея какая: при обычном логарифмировании мы вычисляем m=(c(mod n))^(1/e). Ну якобы обратную функцию. Перебор c (mod n) не занимает очень уж много ресурсов - основная работа приходится на вычисление ^(1/e) - корня степени e.

Ещё раз приведу гомоморфное сво-во, что бы перед глазами было, (m1m2)^e=(m1^e)*(m2^e)=с1с2 (mod n)

Если я возьму свою пару m2 и c2, то, "ломая" их произведение, я буду точно знать, из каких значений с1с2 (mod n) мне точно не надо вычислять корень. Это проистекает из свойств моего сомножителя m1. Так как он в моём примере 30 (хотя можно взять любое число, удовлетворяющее данным ключам), то я должен рассматривать только те числа, которые делятся на 90 (т. к. 30 возводится в степень e). Это проверяется элементарно. К тому же я могу сразу вычеркнуть начальную стадию перебора, ориентируясь на разрядность моего искусственно введённого m2.

Таким образом область перебора на самом деле увеличивается, однако уменьшается количество вычислений "корней степени e" - что гораздо более трудоёмко, чем ... (mod n). Вот только не совсем ясны пропорции, в каких это происходит и, соответственно, неясно насколько мой способ эффективнее.
вопрос 21.09.04 16:33  
Автор: kata Статус: Незарегистрированный пользователь
<"чистая" ссылка>
скажи, пожалуйста, как при известных p, q, e вычислить d?
А мой способ не ставит целью вычислить d 21.09.04 17:38  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Он по заданным c, e и n вычисляет исходный текст. К сожалению, моя идея, которую выше изложил, тоже, как и все остальные, разлетелась в пух и прах.

Не учёл я, что при переборе по алгоритму Евклида (c mod n)/m произведение (m1^e)*(m2^e)>>(c1c2) mod n (m1 - открытый текст, а m2 добавляется искусственно для "упрощения" вычислений). Если, конечно, m1>n^(1/e). Ну и отсюда уже ничего не получишь.

Если бы по полученному значению (c1c2) mod n, из которого вычислялся бы целый корень степени e, можно было бы получить сразу следующее значение, из которого корень e вычиляется, то способ был бы эффективным. Но вычислить не получается. Может быть, плохо думал.
еще раз 22.09.04 07:04  
Автор: kata Статус: Незарегистрированный пользователь
<"чистая" ссылка>
объясните пожалуйста, кто знает, как на основе e, (p-1)*(q-1) получить d.
Я ведь не много прошу.
Раширенным алгоритмом Евклида. 22.09.04 07:17  
Автор: RElf <M> Статус: Member
<"чистая" ссылка>
> объясните пожалуйста, кто знает, как на основе e,
> (p-1)*(q-1) получить d.

Раширенным алгоритмом Евклида.
Подробности тут: http://algolist.manual.ru/maths/teornum/nod.php
большое спасибо 22.09.04 07:46  
Автор: kata Статус: Незарегистрированный пользователь
<"чистая" ссылка>
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach