Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| |
Нет, видимо я путано объяснил. Идея какая: при обычном... 26.08.04 10:52 Число просмотров: 3325
Автор: 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). Вот только не совсем ясны пропорции, в каких это происходит и, соответственно, неясно насколько мой способ эффективнее.
|
|
<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 Статус: Незарегистрированный пользователь
|
|
|
|
|
подробно о проекте
Анализ криптографических сетевых...
