Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Другими словами, k является порядком e по модулю Ф(n). 18.01.05 22:42 Число просмотров: 2634
Автор: RElf <M> Статус: Member
|
> Фактически, для такого метода криптоанализа нам надо подсчитать:
>
> (...((ce mod
> n)e mod
> n)e...)e=c
>
> Это же можно записать так:
>
> cek mod n=c
> cek-1 mod n=m
>
> Остаётся найти k. Вообще из этой формулы видно, что
> d=ek-1 (здесь стОит вспомнить, что
> ключей d бесконечное множество). При этом, т. к. d не
> зависит от выбранного шифротекста, можно утверждать, что
> значение k для любого шифротекста будет одинаковым.
>
> По определению:
>
> e*d=e*ek-1=ek=1 (mod Ф(n))
>
> При этом нас так же удовлетворит в качестве k либое
> значение k*j, где j - произвольное натуральное число и не
> удовлетворит ни одно k'<k.
Другими словами, k является порядком e по модулю Ф(n).
> Отсюда:
>
> ek*j=1 (mod Ф(n))
>
> При этом, опять же по определению, НОД(e,Ф(n))=1. Перед
> нами, вообще говоря, теорема Эйлера в несколько непривычном
> виде, а значит, что k=Ф(Ф(n)).
Не значит. Порядок e по модулю Ф(n) может быть меньше Ф(Ф(n)), но обязан делить это число. Т.е. k в общем случае является делителем Ф(Ф(n)).
> То есть для криптоанализа RSA достаточно вычислить Ф(Ф(n)).
> Если найдётся способ вычисления такой функции минуя
> вычисление Ф(n), то взлом RSA не будет представлять из себя
> проблему.
Это как? Ну есть у вас то самое k, скажем, примерно равное n^(2/3). Как вы собираетесь вычислять d, если ни Ф(n), ни Ф(Ф(n)) не известны? Шифровать k-1 раз практически неосуществимо.
Далее, пусть даже вы знаете Ф(Ф(n)). Чтобы подобраться к числу Ф(n) (а это единственный способ извлечь пользу из Ф(Ф(n)), который я вижу), придется факторизовать Ф(Ф(n)). Где гарантия, что это сильно проще сделать чем факторизовать n?
[...]
> Третее, уже более интересное. Если взять множество всех
> шифротекстов C (|C|=Ф(n), т. к. по условию НОД(m,n)=1,
> m<n) и задать на нём отношение:
>
> r={(x,y) in CxC|Exists
> k:y=xek mod
> n}
>
> Очевидно, что это отношение эквивалентности, которое
> разбивает множество шифротекстов на какое-то число
> подмножеств, причём мощность каждого из подмножеств
> одинакова и равна k=Ф(Ф(n)).
Неверно. Мощности подмножеств могут быть различны. Единственное, что про них можно утверждать, что каждая мощность является делителем Ф(Ф(n)).
> Ну а отсюда уже следует, что Ф(Ф(n)) - это один из сомножителей Ф(n).
Конечно же, это не так. Посмотрите хотя бы на мелком примере:
n=7*11=77,
Ф(n)=6*10=2^2*3*5=60,
Ф(Ф(n))=16 не является делителем Ф(n)=60.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
Другими словами, k является порядком e по модулю Ф(n). - RElf