информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Страшный баг в WindowsSpanning Tree Protocol: недокументированное применениеАтака на Internet
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
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Про n=p1p2p3.. 22.09.04 09:46  Число просмотров: 3121
Автор: Heller <Heller> Статус: Elderman
Отредактировано 22.09.04 09:52  Количество правок: 1
<"чистая" ссылка>
> > Еще вопрос:
> > Насколько я понимаю, 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.
<theory> Поиск 








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


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