информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Атака на InternetГде водятся OGRыСетевые кракеры и правда о деле Левина
BugTraq.Ru
Русский BugTraq
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Модель надежности отказоустойчивой... 
 Oracle выпустила срочный патч для... 
 Атака на WPA2 
 Outlook полгода отправлял зашифрованные... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
чем дальше в лес... 22.09.04 10:59  Число просмотров: 2909
Автор: kata Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> > > Еще вопрос:
> > > Насколько я понимаю, RSA может использовать не
> совсем
> > > простые p и q, а некоторое их приближение.
> Допустим у
> > меня
> > > есть E, P1...Pk, где N=P1*...*Pk. Как на их
> основе
> > > вычислить D?
> > Вопрос остается в силе.
> > Допустим лом RSA работает для идеального случая, когда
> > N=P*Q. Как его расширить для случая, когда
> N=P1*P2*...Pk?
> > Какие ещё подводные камни могут встретьтся в
> конкретных
> > реализациях RSA?
>
> Ну, во-первых, числа RSA генерятся с достаточно большой
> вероятностью того, что они окажутся действительно простыми.
> Даже если они не простые - они всё равно удовлетворяют всем
> статистическим св-вам, которые необходимы для работы
> теоремы Эйлера, трудоёмкой факторизации и следовательно для
> них с большой долей вероятности будут работать те же
> соотношения и для d. Не обязательно всё будет работать, но
> вероятность достаточная. Ну а если не работает - то и
> шифровать на таких ключах не целесообразно - так что тут от
> того, что n!=pq мало чего зависит.
>
> По поводу ф(n), если n - произведение нескольких простых
> чисел (больше чем двух). Общая формула такая:
>
> Ф(n)=n-n/P1-n/P2-...-n/Pk+n/P1P2+n/P1P3+...+n/P2P3+n/P2P4+.
> ..+n/P(k-1)Pk-n/P1P2P3-n/P1P2P4-...-n/P(k-2)P(k-1)Pk+...+((
> -1)^k)*n/P1P2...Pk
>
> Написал, конечно, немного криво, но я не знаю как её
> записать нормально в математическом виде на клавиатуре. То
> есть из n вычитается сумма всех n/Pi, потом прибавляется
> сумма всех n/PiPj и т. д. Если какой-то простой сомножитель
> чиcла n "содержится" в нём в какой-то степени - это формулы
> не меняет. Каждый сомножитель учитывается только один раз в
> 1 степени.
>
> Ф(n), вычисленный по этой формуле от n, имеющий несколько
> простых сомножителей, так же вполне может использоваться в
> RSA - хотя применение такого вида функции Эйлера скорее
> всего на практике и не потребуется - при факторизации ты в
> любом случае найдёшь один "простой" сомножитель, а потом
> найдёшь второй "простой", поделив q=n/p. Хоть теоретически
> это и неверно, работать в большинстве случаев будет - т.
> к., повторюсь, статистические проверки проводятся именно на
> эти св-ва.
>
> P.S. Но вообще, если мало ли Ты хочешь
> реализовать алгоритм RSA на основе
> n=p1p2p3... - то Тебе поможет фукция Эйлера (см. выше),
> однако стойкость RSA упадёт критически - смысла в таком
> алгоритме уже не будет. То есть нахождение быстрого
> алгоритма факторизации действительно убьёт RSA.
Спасибо за довольно подробное письмо, но я всё равно не понял.

Я не хочу реализовать алгоритм RSA я хочу его поломать. Допустим самое трудное решено - найден достаточно быстрый алгоритм факторизации N. Остается темная область для меня - как на основе разложения N вычислить приватный ключ.

Допустим реальный алгоритм RSA сработал так, что получились не очень простые P и Q. На их основе сгенерированы D и E.

Допустим N у меня разложилось на три числа p1, p2, p3. Что мне с ними дальше делать? Перебрать 3 возможных варианта?
p1*p2 = P, p3 = Q
p1*p3 = P, p2 = Q
p2*p3 = P, p1 = Q
А если получится 4 числа? Вариантов становится 6. Так дело не пойдет. Я слышал, что чем сложнее N, тем быстрее работает взлом, по идее, но в чем идея заключается?
<theory> Поиск 








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


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