Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | | | |
Пусть так 29.06.04 13:19 Число просмотров: 4043
Автор: amirul <Serge> Статус: The Elderman
|
> местах. Хотя нет гарантии, обладатель красной рубашки твой
> друг. Но все же круг значительно сужается, а это то, что
> нам надо.
Незначительно. На 10^10 будет страшно подумать сколько вариантов. Но даже если вариант только один на 10^10 чисел, то это позволит сбросить только 10 десятичных порядков (около 30-ти двоичных). То бишь, если на факторизацию числа порядка 2^1024 ушло бы 2^800 (к примеру) лет, то с твоим методом уйдет 2^770 лет. Кроме того, не стоит думать, что чисел будет так уж мало и что так уж легко будет их найти. При порядке 2^30 все еще более-менее нормально, а вот DES порядка 2^56 ломали несколько лет всем интернетом, а там нет никаких вычислений со сверхбольшими числами - обычные перестановки по таблицам.
|
|
<theory>
|
Алгоритм решения RSA 06.06.04 16:09
Автор: volizar Статус: Незарегистрированный пользователь
|
Необходимо переложить на программный язык решение RSA.
Неочевидный алгоритм.
Москва.
|
| |
Ооо, замечательные фразы по ссылке! 16.07.04 10:06
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Тут: http://www.livejournal.com/users/relf/25391.html
Ооо, замечательные фразы по ссылке!
Все равно не брошу на досуге ломать голову над этой прблемой.
|
|
Алгоритм разбит на три части:
08.06.04 13:58
Автор: volizar Статус: Незарегистрированный пользователь
|
Алгоритм разбит на три части:
1. Факторизация
2. Корень, т.е. «хвост»
3. Вставка (новое)
1.Факторизация
Возьмем число А. Извлечем корень а. Из таблицы простых чисел берем число b, ближайшее к а, так что b <= a. Делим А на b. Имеем b , c (второе целое число) и d (остаток. Если d равен нулю, то факторизация завершена). A = b*c +d.
Если d будет больше b, d >b , то надо проделать еще кое-что.
А именно: находим новое c, c:= c + d/b (без остатка)
новое d, d:= d (mod b)
Пока у нас есть b, c и d. Наша задача – довести d до нуля.
Процедура такая:
Берём следующее простое число b2, так что b2<b1.
Ищем следующее d. Оно будет равно d: = d + (c - b2)*( b1 - b2).
Само c станет равно c: = c + (b1 - b2).
Если d будет больше b2, d >b2 , то
находим новое c, c = c + d/b2 (без остатка)
новое d, d = d (mod b2)
В принципе, это вся первая часть. Пример:
A = 377, a = 19.146…, b = 19, c = 19, d = 16
Шаг 1 : b2 = 17, d = 16 + (19 - 17)*(19-17) = 20, c = 19 + 2 = 21.
Видим d >b2, находим c = 21 + d/b = 21 +1 = 22
d = 20(mod17) = 3
Шаг 2: b = 13, d = 3 + ( 22 - 13)*(17-13) = 39, c = 22 + 4 = 26.
Опять d > b, значит c = 26 + 3 = 29, d = 39(mod13) = 0.
Процедура закончена. Результат: b = 13, c = 29.
На мой взгляд, алгоритм сам по себе очень удобный и не потребует много ресурсов.
Но это всего лишь один механизм обработки данных.
Осталось ещё два. Но об этом позже.
P.S. Есть пока замечания? Не придирайтесь, пожалуйста к мелочам.
|
| |
Постараюсь объяснить третий этап (набросок).
29.06.04 15:07
Автор: volizar Статус: Незарегистрированный пользователь
|
Постараюсь объяснить третий этап (набросок).
Предположим, надо факторизовать некое число А.
Находим b, c и d , как на первой стадии. A=b*c+d.
Суть в том, что (b-k)*(c+x)=b*c+d. k - это отклонение, шаг. х - неизвестное.
После преобразований (d я отбросил,т.к. оно не сильно влияет)
приходим к следующему х = (kc) / (b - k).
Можно отбросить и k в знаменателе, тогда имеем: х = kc / b .
Если учесть, что в RSA c / b это где-то 10 в третьей-четвертой степени,
а k-max возьмем, скажем, 10 в пятой-седьмой степени,
то имеем число х-мах= 10^9.
Обратите внимание, что к и х максимальные, их можно отрегулировать и т.д.
Я к чему?
Отклонение х-мах на 9-10 знаков говорит о том, что только последние 9-10 знаков(максимум) изменятся. А остальные останутся на месте. И здесь нам поможет таблица.
По ней мы можем спускаться и вылавливать подходящие пары.
Если у нас таблица окончаний на глубину 15- 20,
то можно сравнивать 10-12 цифр слева по лексикографическому принципу (как в словаре).
Сравнивать придется ТОЛЬКО окончания, а сами большие числа будут где-то в базе,
куда каждый будет обращаться при раздаче.
Вероятность, что кандидатов будет много ничтожно мала. Поэтому процесс будет достаточно динамичным.
В любом случае, есть смысл просчитать, сколько эта процедура может занять времени.
В-общем, что мы имеем?
Мы имеем RSA-число А.
Имеем универсальную таблицу окончаний делителей этого числа (на глубину 20, 30, 40 цифр. Нужно найти оптимальную глубину).
Компьютеры запрашивают некоторый интервал чисел, сканируют таблицу и в случае нахождения пары-кандидата (вероятность чего чрезвычайно мала) проверяют ее с помощью алгоритма №1 или посылают на проверку.
Никаких сложных и больших вычислений не требуется.
|
| |
2. Корень, т.е. «хвост»
28.06.04 12:12
Автор: volizar Статус: Незарегистрированный пользователь
|
2. Корень, т.е. «хвост»
Предположим, что у нас есть некое число .......................................3674219074501203672391386473. Проделываем следующую процедуру: распутываем клубок с конца.
Тройка получается при перемножении 1 и 3, 7 и 9.
.....73 две цифры с конца :
...01*...73 ...07*...39
11 * 43 17 * 69
21 * 13 27 * 99
31 * 83 37 * 29
41 * 53 47 * 59
51 * 23 57 * 89
61 * 93 67 * 19
71 * 63 77 * 49
81 * 33 87 * 79
99 * 03 97 * 09
Перемножение соответствующих пар дает дает на конце искомые цифры. Продолжаем эту процедуру до необходимой глубины, например до 10 цифр. Что мы имеем? Мы имеем набор цифр, жестко связанных между собой. В этом наборе порядка 10^10 пар (строго говоря меньше, порядка (10^10)*0.4 т.к. последней цифрой могут быть только 4 нечетные цифры). Нахождение пар глубины 10 займет немного времени. Теперь необходимо составить таблицу пар по восходящей (нисходящей. Надо проверить, что удобней). В таблице две колонки, причем в первой колонке (которая будет ранжирована) будут присутствовать ВСЕ окончания. Таким образом, в двух колонках будут те же наборы цифр, только в первой колонке они будут упорядочены, а во второй нет. Вторая колонка будет привязана к первой.
Для глубины 2 это будет выглядеть так:
01 73
03 91
07 39
09 97
11 43
13 21
17 69
19 67
21 13
23 51
27 99
29 37
31 83
33 81
37 29
39 07
41 53
43 11
47 59
49 77
51 23
53 41
57 89
59 47
61 93
63 71
67 19
69 17
71 63
73 01
77 49
79 87
81 33
83 31
87 79
89 57
91 03
93 61
97 09
99 27
Имея такую таблицу, можно кое-что сделать...
Продолжение следует.
|
| | |
Почитай все таки про СОК 29.06.04 11:35
Автор: amirul <Serge> Статус: The Elderman
|
> 2. Корень, т.е. «хвост»
> Предположим, что у нас есть некое число
> .......................................36742190745012036723
> 91386473. Проделываем следующую процедуру: распутываем
> клубок с конца.
> Тройка получается при перемножении 1 и 3, 7 и 9.
> .....73 две цифры с конца :
Брать в качестве модулей не взаимно простые числа (10, 100, 1000...) не эффективно: зачем брать тройку, как 1*3 и 7*9, если все комбинации для 73 (наверное ты опечатался и имел в виду 23) будут составлять одну из комбинаций для 3. С этой единственной оговоркой то, что ты говоришь уже придумано Акушским.
> Перемножение соответствующих пар дает дает на конце искомые
> цифры. Продолжаем эту процедуру до необходимой глубины,
> например до 10 цифр. Что мы имеем? Мы имеем набор цифр,
> жестко связанных между собой. В этом наборе порядка 10^10
Они не просто жестко связаны. Достаточно самой внешней комбинации, все остальные - выводятся из нее и являются избыточными и не несущими дополнительной информации.
> пар (строго говоря меньше, порядка (10^10)*0.4 т.к.
> последней цифрой могут быть только 4 нечетные цифры).
> Нахождение пар глубины 10 займет немного времени. Теперь
Это даст возможность факторизовать числа порядка 10^10. Я могу дать тебе гораздо более эффективный алгоритм для этого.
Таблица не нужна. Насколько мне известно, существует агоритм деления по модулю. Одно БОЛЬШОЕ но. Модули простого числа будут делиться точно так же как и составного и отличить одно от другого ты таким способом не сможешь
|
| | | |
Само RSA-число несет в себе информацию и о делителях, и мы... 29.06.04 11:56
Автор: volizar Статус: Незарегистрированный пользователь
|
> > Перемножение соответствующих пар дает дает на конце
> искомые
> > цифры. Продолжаем эту процедуру до необходимой
> глубины,
> > например до 10 цифр. Что мы имеем? Мы имеем набор
> цифр,
> > жестко связанных между собой. В этом наборе порядка
> 10^10
> Они не просто жестко связаны. Достаточно самой внешней
> комбинации, все остальные - выводятся из нее и являются
> избыточными и не несущими дополнительной информации.
Само RSA-число несет в себе информацию и о делителях, и мы пытаемся их найти. Мы же не считаем делители избыточными. Также если окончания могут нам помочь, стоит их найти. Если есть более эффективные пути нахождения этих пар, то это еще лучше. Таблица всего лишь средство и нет разницы, каким путем она найдена. Чем быстрее и легче мы ее найдем, тем лучше.
|
| | | | |
Пример: число 23 - простое. Оканчивается на 3 и на 23 29.06.04 12:03
Автор: amirul <Serge> Статус: The Elderman
|
> Само RSA-число несет в себе информацию и о делителях, и мы
> пытаемся их найти. Мы же не считаем делители избыточными.
Что в твоем случае даст опять таки 1*3 и 7*9, ну и стопку чисел с 23. Такое разгребание НЕ НУЖНО. Так как 23 само по себе подразумевает 3 и надо сразу брать максимальное окончание.
> Также если окончания могут нам помочь, стоит их найти. Если
Не могут.
> есть более эффективные пути нахождения этих пар, то это еще
> лучше. Таблица всего лишь средство и нет разницы, каким
> путем она найдена. Чем быстрее и легче мы ее найдем, тем
> лучше.
В случае с взаимно простыми модулями они будут оставаться достаточно короткими и не зависящими друг от друга (модулярные каналы) и над ними можно будет произвести такую операцию. В твоем случае алгоритм подразумевает факторизацию длинных чисел вплоть с 10-ти и вплоть до самого числа. Зачем тратить столько сил на факторизацию всех хвостов, если можно сразу факторизовать число.
В десятый раз говорю: "НАЙДИ И ПОЧИТАЙ КНИГУ АКУШСКОГО".
|
| | | | | |
Мы с тобой говорим о разных вещах.
29.06.04 12:30
Автор: volizar Статус: Незарегистрированный пользователь
|
Мы с тобой говорим о разных вещах.
Никто не собирается распутывать клубок до конца.
На бирже есть технари и фундаменталисты. Фундаменталисты ищут серьезные основания, перелопачивают горы информации, строят глобальные гипотезы и т.д.
Технари пытаются по каким-то незначительным, несущественным с традиционной точки зрения, признакам уловить тенденцию. Один из них говорил: " Мне не надо видеть всю картину. Достаточно заглянуть в щелочку и увидеть в каком направлении бежит акция. А дальше я могу просчитать, что будет (на определенном временном отрезке)".
Надо сказать, что ни те ни эти особо не преуспевают. Хотя каждый вносит свою лепту в развитие экономической теории.
Тебе, наверное, ближе фундаментальный подход. Я же пытаюсь подойти с другого берега.
Так вот, эта таблица предназначена для определения потенциальных клиентов (кандидатов) на высокое звание делителей заумного RSA-числа. Если ты ищешь в толпе друга в красной рубашке и зеленых тапочках ( не белых), то можешь ориентироваться на красный и зеленый цвет в соответствующих местах. Хотя нет гарантии, обладатель красной рубашки твой друг. Но все же круг значительно сужается, а это то, что нам надо.
|
| | | | | | |
Пусть так 29.06.04 13:19
Автор: amirul <Serge> Статус: The Elderman
|
> местах. Хотя нет гарантии, обладатель красной рубашки твой
> друг. Но все же круг значительно сужается, а это то, что
> нам надо.
Незначительно. На 10^10 будет страшно подумать сколько вариантов. Но даже если вариант только один на 10^10 чисел, то это позволит сбросить только 10 десятичных порядков (около 30-ти двоичных). То бишь, если на факторизацию числа порядка 2^1024 ушло бы 2^800 (к примеру) лет, то с твоим методом уйдет 2^770 лет. Кроме того, не стоит думать, что чисел будет так уж мало и что так уж легко будет их найти. При порядке 2^30 все еще более-менее нормально, а вот DES порядка 2^56 ломали несколько лет всем интернетом, а там нет никаких вычислений со сверхбольшими числами - обычные перестановки по таблицам.
|
| | | | | | | |
В 1999-м году взлом DES "всем интернетом" занял около 22... 08.07.04 16:17
Автор: RElf <M> Статус: Member
|
> а вот DES порядка 2^56 ломали несколько лет всем интернетом
В 1999-м году взлом DES "всем интернетом" занял около 22 часов.
См. http://www.rsasecurity.com/rsalabs/node.asp?id=2108
|
| | | | | | | |
первое, при чем тут ДЕС, если вопрос факторизации актуален... 06.07.04 13:01
Автор: andrew Статус: Незарегистрированный пользователь
|
> При порядке 2^30 все еще более-менее нормально, а вот DES
> порядка 2^56 ломали несколько лет всем интернетом, а там
> нет никаких вычислений со сверхбольшими числами - обычные
> перестановки по таблицам.
первое, при чем тут ДЕС, если вопрос факторизации актуален для РСА (ну и в пределе - для систем с открытыми ключами)
второе, когда это ДЕС ломали несколько лет всем Интернетом? мы про сегодняшний день или на день публикации ДЕС? если мне не изменяет склероз нынче это - единицы-десятки часов. а специальный аппарат (ок. 300 тыс уебаксов) - единицы-десятки секунд.
да и неактуален ДЕС в "чистом" виде. либо 3-5-7ДЕС, либо АЕС, либо давайте менять таблицы замен (как дополнительный секретный элемент, как сделано в ГОСТе)
|
| | | | | | | | |
При том, что перебор ВСЕХ чисел из 2^56 с применением к каждому довольно простых преобразований весьма нетривиальная задача 06.07.04 13:12
Автор: amirul <Serge> Статус: The Elderman
|
> первое, при чем тут ДЕС, если вопрос факторизации актуален
А уж если к каждому варианту перебора нужно еще и пара десятков умножений и модулярных экспонент со сверхбольшими числами, то тут уж просто дело швах.
> для РСА (ну и в пределе - для систем с открытыми ключами)
Сравниваю не МЕТОДЫ взлома, а алгоритмическую сложность этих методов. Я взял лучший случай для приведенного метода факторизации и он оказался значительно сложнее того же DES, что же говорить о реальном положении.
> второе, когда это ДЕС ломали несколько лет всем Интернетом?
Действительно, давно это было. Но и сейчас задач на distributed.net немало.
|
| |
Алгоритм разбит на три части: 10.06.04 12:39
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Возьмем число А. Извлечем корень а. Из таблицы простых
> чисел берем число b, ближайшее к а, так что b <= a.
> Делим А на b. Имеем b , c (второе целое число)
> и d (остаток. Если d равен нулю, то факторизация
> завершена). A = b*c +d.
> Если d будет больше b, d >b , то надо проделать еще
> кое-что.
Остаток d первоначально не будет больше делителя b. Но это, действительно мелочи.
> А именно: находим новое c, c:= c + d/b (без остатка)
> новое d, d:= d (mod b)
Ну, ну, что-то вроде получения результатов деления (частного и остатка) для нового делителя по известным результатам для старого.
По-моему все-равно по этому алгоритму придется перебирать все простые числа от квадратного корня исходного до минимального из сомножителей.
> Пока у нас есть b, c и d. Наша задача – довести d до
> нуля.
Над минимизацией остатка я подумывал, но увы, находим локальный минимум, а дальше что? Забросил по причине того, что посчитал эту ветку тупиковой.
> Процедура такая:
> Берём следующее простое число b2, так что b2<b1.
> Ищем следующее d. Оно будет равно d: = d + (c - b2)*( b1 -
> b2).
> Само c станет равно c: = c + (b1 - b2).
> Если d будет больше b2, d >b2 , то
> находим новое c, c = c + d/b2 (без остатка)
> новое d, d = d (mod b2)
> Осталось ещё два. Но об этом позже.
Ждемс...
> P.S. Есть пока замечания? Не придирайтесь, пожалуйста к
> мелочам.
Не, к мелочам не буду, остальное - не мелочи.
Самое главное не разочароваться натыкаясь на препятствия/тупики.
|
| |
Алгоритм разбит на три части: 08.06.04 14:10
Автор: amirul <Serge> Статус: The Elderman
|
> Возьмем число А. Извлечем корень а. Из таблицы простых
> чисел берем число b, ближайшее к а, так что b <= a.
> Берём следующее простое число b2, так что b2<b1.
> P.S. Есть пока замечания?
Дело в том, что таблицы простых чисел нет. По крайней мере для чисел, которые используются в RSA.
Пусть порядок ключа ~2^1024 (который уже считается слабым и сейчас меньше, чем 2^2048 не рекомендуют). Корень из этого дела будет порядка 2^512. То есть на одно (!!!) число в такой таблице надо 2^509 (153 десятичных знака) байт. Простых чисел в этом диапазоне примерно 2^510.
Если бы у меня было столько памяти, то я бы без всяких алгоритмов искал бы простые числа решетом Эратосфена.
|
| | |
Во-первых, алгоритм может работать без таблиц, т.к. он годен... 09.06.04 10:15
Автор: volizar Статус: Незарегистрированный пользователь
|
Во-первых, алгоритм может работать без таблиц, т.к. он годен для любых (не только простых) чисел.
Во-вторых, нам не нужны сами числа, а только разница чисел (b1-b2=k, c-b1=m, например). Единственная трудность возникает, когда d > b. Здесь надо что-то придумать.
В-третьих, было б неплохо использовать таблицу известных! простых чисел, вернее, их разниц.
|
| | | |
Таблици простых чисел нет.
13.06.04 13:46
Автор: maggres Статус: Незарегистрированный пользователь
|
> Во-первых, алгоритм может работать без таблиц, т.к. он
> годен для любых (не только простых) чисел.
> Во-вторых, нам не нужны сами числа, а только разница чисел
> (b1-b2=k, c-b1=m, например). Единственная трудность
> возникает, когда d > b. Здесь надо что-то придумать.
>
> В-третьих, было б неплохо использовать таблицу известных!
> простых чисел, вернее, их разниц.
Таблици простых чисел нет.
Даже еслы бы она существовала то у Вас exp рост объема памяти от размерности задачи.
в общем случаее разница между числами будет требовать тогоже порядка памяти что и хранения самих чисел, и также будет иметь exp требования к памяти.
С точки зрения практики в алг RSA в качестве p и q используются числа претендующие быть простыми, т.е. прошедшие ряд тестов на простоту, что совсем не гарантирует нам что он действительно простые, при спуске по таблици из простых имеем шанс простой "проскочить" нужный делитель.
|
| | | | |
Вот она: 15.06.04 12:28
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 15.06.04 12:29 Количество правок: 1
|
> Таблици простых чисел нет.
Вот она: 2, 3, 5, 7, 11, 13, 17, 19, ...
Поскольку простых чисел бесконечно много, а память компьютера не бесконечна, я не могу привести все простые числа.
> Даже еслы бы она существовала то у Вас exp рост объема
> памяти от размерности задачи.
А показатель экспоненты какой - больще 1 или меньше, а может отрицательный?
> в общем случаее разница между числами будет требовать
> тогоже порядка памяти что и хранения самих чисел, и также
> будет иметь exp требования к памяти.
>
> С точки зрения практики в алг RSA в качестве p и q
> используются числа претендующие быть простыми, т.е.
> прошедшие ряд тестов на простоту, что совсем не гарантирует
> нам что он действительно простые, при спуске по таблици из
А я везде встречал, что p и q должны быть простыми а не претендующими. Дайте кто-нибудь ссылочку на определение числа, претендующего быть простым, и допустимость использования в РСА составных чисел, пожалуйста.
> простых имеем шанс простой "проскочить" нужный делитель.
|
| | | | | |
да еще стоит учесть что проверка числа на простоту,... 09.07.04 14:52
Автор: maggres Статус: Незарегистрированный пользователь
|
> > Таблици простых чисел нет.
> Вот она: 2, 3, 5, 7, 11, 13, 17, 19, ...
> Поскольку простых чисел бесконечно много, а память
> компьютера не бесконечна, я не могу привести все простые
> числа.
да еще стоит учесть что проверка числа на простоту, ресурсозатратное дело, так что из твоих слов также следует что таблици простых чисел не существует. При этом все простые числа никто не знает, также не известно конечен или нет ряд простых чисел.
> > Даже еслы бы она существовала то у Вас exp рост объема
> > памяти от размерности задачи.
> А показатель экспоненты какой - больще 1 или меньше, а
> может отрицательный?
а подумать :)? конечно >1, точно значение не имеет значения, важен характер ф-и.
> > С точки зрения практики в алг RSA в качестве p и q
> > используются числа претендующие быть простыми, т.е.
> > прошедшие ряд тестов на простоту, что совсем не
> гарантирует
> > нам что он действительно простые, при спуске по
> таблици из
>
> А я везде встречал, что p и q должны быть простыми а не
> претендующими. Дайте кто-нибудь ссылочку на определение
> числа, претендующего быть простым, и допустимость
> использования в РСА составных чисел, пожалуйста.
В RSA можно использовать составные числа, просто от этого критически упадет его стойкость.
Любая реализация RSA использует числа претендующие быть простыми, или ты и впрям думаешь что во всех реализация прошита "таблица" простых и оттуда берется число, или что используемое чило проверяется на простоту детерменированным методом :)?
|
|
|
подробно о проекте
Анализ криптографических сетевых...
