Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | |
Обо всём сразу 22.09.04 21:01 Число просмотров: 5503
Автор: Heller <Heller> Статус: Elderman
Отредактировано 22.09.04 21:08 Количество правок: 1
|
Во-первых, все алгоритмы факторизации работают за полиномиальное время. Их можно условно разделить на две категории: алгоритмы, основанные на эллиптических кривых и алгоритмы, которые на этих кривых не основаны.
Для всех алгоритмов, про которые я читал, которые эллиптические кривые не применяют, существуют формулы для вычесления максимального количества совершенных операций для полной факторизации. Они имеют либо экспоненциальную сложность, либо субэкспоненциальную, что их и разделяет на две больших группы. Вариантов тут нет. Алгоритмы с субэкспоненциальной сложностью являются самымы быстрыми.
Что касается эллиптических кривых, то про них я знаю не так много, поэтому утверждать что-то не буду. Из таких алгоритмов известен алгоритм Ленстры, сложность для которого определена (правда, зависит от количества простых сомножителей, но верхний предел всегда известен). Существует ещё расширенный алгоритм Ленстры, про сложность вычисления которого я ничего не слышал, но надо полагать, что она всё равно будет не выше сложности обычного алгоритма.
Так же с использованием эллиптических кривых вычисляется порядок группы точек эллиптической кривой над конечным полем. Для этого так же существует несколько алгоритмов, самый трудоёмкий из которых (из тех, что известны мне, а я этим вопросом подробно не занимался никогда) - это алгоритм Шура, полиномиальная сложность которого так же определена: O((log p)^8). Все остальные алгоритмы либо имеют свои формулы для вычисления сложности, либо доказывается, что их сложность не выше чем у алгоритма Шура.
Как видно, сложность для всех алгоритмов определена либо точно, либо определена верхняя граница. Другое дело обстоит с тестированием числа на простоту, что так же полезно при факторизации (в основном это сводится к вопросу о необходимости дальнейшей факторизации при получении какого-то набора чисел). Тесты можно разделить опять же на две группы - статистические и не статистические. Не статистически работают так же за полиномиальное время (опять же здесь максимальная граница сложности - перебор всех делителей подряд от 2 до n^(1/2)), а статистические работают вообще за время совершенно не значительное , но дают не точные результаты.
Один из не статистических алгоритмов проверки числа на простоту - алгоритм Миллера. Он имеет сложность n^(1/7). И вот здесь начинается самое интересное. Имеется возможность модифицировать его так, что его сложность резко снизится до (log n)^4, но эта модификация (которая вроде как и названия не имеет), как раз и основана на справедливости расширенной гипотезы Римана.
Что существенно: как видно, модифицированный алгоритм Миллера, основаный на гипотезе Римана, работает за полиномиальное время O(L), однако, имхо, (log n)^4 - это вообще-то не мало. Причём это единственное пратическое применение гипотезы Римана, которое я знаю. Исходя из самой гипотезы Римана (кто-то выше ссылку давал) не совсем ясно, как факторизировать числа, поэтому имеется подозрение, что алгоритм Миллера это вообще единственный алгоритм на сегодняшний день, который эту гипотезу использует. К тому же, насколько мне известно, хоть гипотеза Римана и не доказана, модифицированный алгоритм Миллера применяется сегодня на практике достаточно широко и даёт очень хорошие результаты. Проверить его не удаётся - все оценки только на основе статистических тестов.
Во всяком случае, гипотеза Римана полезна ТОЛЬКО для проверки числа на простоту, а при факторизации проверка числа на простоту полезна ТОЛЬКО если n=P1P2...Pk, где k>2. Что касается RSA, то там k, причём неизвестно с какой вероятностью (только приближённые оценки), действительно больше двух, однако, полная факторизация в RSA и не требуется, что показано где-то в одном из постов этого же топика (чей пост не помню, но не мой точно - если кто искать будет). Хотя это может и кажется странным, но действительно, если посмотреть на существующие сегодня алгоритмы - они при разложении числа на множетели не пользуются свойством простоты числа - они именно раскладывают число на множетели, вместо того, что бы подбирать простые сомножители. Проверка на простоту нужна только для того, что бы выяснить, требуется ли далнейшая факторизация полученных сомножителей (неизвестно, простые ли они) далее или нет. В RSA, как известно, не требуется.
Вроде, всё изложил.
P.S. А что касается P=NP, то это при изучении вопросов факторизации и проверки на простоту не шибко важно. Во всяком случае, я никогда в научных изданиях не встречался с использованием (даже косвенным) данной гипотезы, когда речь идёт о простоте чисел. Как сказал классик, не помню какой, "не надо плодить сущности без надобности". Имхо.
|
|
<theory>
|
Математики стоят на пороге уничтожения криптографии 08.09.04 08:11 [HandleX, !mm]
Автор: TARASA <Taras L. Stadnik> Статус: Member
|
Подтверждение гипотезы Римана, к которой близко подошли математики, может уничтожить все достижения современной криптографии, что будет иметь весьма негативное влияние на интернет-коммерцию, сообщает CNews.ru.
Математик из США французского происхождения Луис де Бранже (Louis de Branges) заявил, что он имеет доказательства гипотезы Римана.
Гипотеза Георга Фридриха Бернарда Римана была сформулирована 150 лет назад. Она касается случайных наборов простых чисел, которые являются основой систем шифрования, применяемых в интернете.
Данная гипотеза была признана одной из 7 важнейших научных проблем тысячелетия. Институт математики Clay в США предложил $1 млн. за подтверждение или опровержение гипотезы Римана.
Однако не все коллеги де Бранже согласны с тем, что он имеет корректное и четкое решение.
По утверждению профессора Оксфордского университета Маркуса ду Сатойя (Marcus du Sautoy), решение проблем теории Римана позволило бы лучше понимать "поведение" простых чисел и предсказывать его, что привело бы к полной невозможности обеспечивать безопасность электронных транзакций с помощью шифрования.
Источник: SecurityLab http://www.securitylab.ru/47775.html
|
|
Каюсь. Я от криптографии и от высшей математики далек в виду... 13.09.04 16:56
Автор: TARASA <Taras L. Stadnik> Статус: Member
|
|
Каюсь. Я от криптографии и от высшей математики далек в виду отсутствия ВО. По этому, сорри, за че купил, за то продал. Впредь буду консультироваться со старшими товарищами перед постингом чего-либо на тему криптографии. Еще раз сорри.
|
|
Задача журналиста - найти горячий материал. В принципе... 13.09.04 16:11
Автор: lime Статус: Незарегистрированный пользователь
|
> Подтверждение гипотезы Римана, к которой близко подошли
> математики, может уничтожить все достижения современной
> криптографии, что будет иметь весьма негативное влияние на
> интернет-коммерцию, сообщает CNews.ru.
>
> Математик из США французского происхождения Луис де Бранже
> (Louis de Branges) заявил, что он имеет доказательства
> гипотезы Римана.
>
> Гипотеза Георга Фридриха Бернарда Римана была
> сформулирована 150 лет назад. Она касается случайных
> наборов простых чисел, которые являются основой систем
> шифрования, применяемых в интернете.
>
> Данная гипотеза была признана одной из 7 важнейших научных
> проблем тысячелетия. Институт математики Clay в США
> предложил $1 млн. за подтверждение или опровержение
> гипотезы Римана.
>
> Однако не все коллеги де Бранже согласны с тем, что он
> имеет корректное и четкое решение.
>
> По утверждению профессора Оксфордского университета Маркуса
> ду Сатойя (Marcus du Sautoy), решение проблем теории Римана
> позволило бы лучше понимать "поведение" простых чисел и
> предсказывать его, что привело бы к полной невозможности
> обеспечивать безопасность электронных транзакций с помощью
> шифрования.
>
> Источник: SecurityLab http://www.securitylab.ru/47775.html
Задача журналиста - найти горячий материал. В принципе удалось, но вот описание причины "краха криптографии" действительно изложено через одно место.
Хотя, на мой взгляд, ввиду достаточной распространенности прикладных программ основанных на проблеме факторизации, решение данной проблемы действительно может иметь серьезные последствия.
Я не говорю о проблемах криптографии как науки в целом, но кто-нибудь может сказать, существует ли альтернатива PGP RSA в технологическом смысле. Т.е. что существует ли алгоритм, подразумевающий открытую передачу ключа?
|
| |
Существуют. Криптосистемы ЭльГамаля, Рабина, Нидеррайтера,... 13.09.04 20:16
Автор: Heller <Heller> Статус: Elderman
|
> Я не говорю о проблемах криптографии как науки в целом, но
> кто-нибудь может сказать, существует ли альтернатива PGP
> RSA в технологическом смысле. Т.е. что существует ли
> алгоритм, подразумевающий открытую передачу ключа?
Существуют. Криптосистемы ЭльГамаля, Рабина, Нидеррайтера, МакЭлиса и т. д.
|
| | |
Значит проблема будет только в быстром отказе от ставших... 15.09.04 07:55
Автор: lime Статус: Незарегистрированный пользователь
|
> > Я не говорю о проблемах криптографии как науки в
> целом, но
> > кто-нибудь может сказать, существует ли альтернатива
> PGP
> > RSA в технологическом смысле. Т.е. что существует ли
> > алгоритм, подразумевающий открытую передачу ключа?
>
> Существуют. Криптосистемы ЭльГамаля, Рабина, Нидеррайтера,
> МакЭлиса и т. д.
Значит проблема будет только в быстром отказе от ставших нестойкими методов шифрования.
|
|
Интересно, с чего такой вывод? 10.09.04 08:36
Автор: cybervlad <cybervlad> Статус: Elderman
|
> Подтверждение гипотезы Римана, к которой близко подошли
> математики, может уничтожить все достижения современной
> криптографии, что будет иметь весьма негативное влияние на
> интернет-коммерцию, сообщает CNews.ru.
Интересно, с чего такой вывод?
Ну, получим мы быстрый способ проверки числа на простоту, и хорошо. Каким местом это поможет легко решать задачу разложения на простые множители или дискретного логарифмирования?
|
| |
объясните пожалуйста еще раз 22.09.04 08:31
Автор: kata Статус: Незарегистрированный пользователь
|
Допустим есть достаточно быстрый алгоритм факторизации N. Является ли это ломом против RSA?
Допустим у меня есть E, P1...Pk, где N=P1*...*Pk. Как на их основе вычислить D?, т.е. как приспособить алгоритм Евклида для такого более общего случая, где k > 2.
Какие ещё подводные камни могут встретьтся в конкретных реализациях RSA?
|
| | |
Попробую обобщить в двух словах все ранее сказанное 22.09.04 22:47
Автор: Heller <Heller> Статус: Elderman
|
d зависит от e и ф(n). n=p1p2p3... НО! При факторизации n, что я вкратце объясняю в посте "обо всём сразу", получается НЕ разложение на простые сомножители, а просто два сомножителя числа n. Каждый из них на самом деле может быть составным, однако это не важно, т. к. исходя из алгоритмов, с помощью которых изначально генерировались p и q, они удовлетворяют основным свойствам простых чисел. А именно, они удовлетворяют теореме Ферма-Эйлера, на которой и построена RSA.
Разложение n на два сомножителя, что делают алгоритмы факторизации, естесственно, не однозначно, но необходимо учесть, что, по рекомендациям,p|~|q|~(1/2)*|n(тильда в данном случае означает "примерно"), поэтому произведение надо выбирать именно то, которое удовлетворяет данному условию. Эднако этого скорее всего не потребуется, т. к. алгоритмы факторизации "чисел RSA" изначально ищут сомножители, исходя из этого условия.
Хотя даже при полном разложении на простые сомножители числа n, мы можем вычислить ф(n) по общей формуле, которую я несколькими постами выше приводил и полученное значение так же будет работать, т. к. это опять же следует из того, что p и q генерируются в первую очередь исходя из условия выполнения условия m^kФ(n)=1(mod n), а не m^k(p-1)(q-1)=1(mod n), так как статистическая проверка числа на удовлетворение формуле с использованием Ф(n) на порядок проще чем такая же проверка для выполнения формулы с (p-1)(q-1)
|
| | | |
скорость факторизации 23.09.04 10:01
Автор: kata Статус: Незарегистрированный пользователь
|
Интересно, за какое время самый быстрый алгоритм факторизации разложит число
910522409 * 3273188221 = 2980311224095344389
У меня получилось за 10 мин.
|
| | | | |
Pari/GP раскладывает за доли секунды 23.09.04 14:46
Автор: RElf <M> Статус: Member
Отредактировано 23.09.04 14:48 Количество правок: 2
|
> Интересно, за какое время самый быстрый алгоритм
> факторизации разложит число
> 910522409 * 3273188221 = 2980311224095344389
> У меня получилось за 10 мин.
Pari/GP раскладывает за доли секунды:
? factorint(2980311224095344389)
%1 =
[910522409 1]
[3273188221 1]
официальный сайт Pari/GP
|
| | | | | |
Maple тоже 27.09.04 11:20
Автор: amirul <Serge> Статус: The Elderman
|
> > Интересно, за какое время самый быстрый алгоритм
> > факторизации разложит число
> > 910522409 * 3273188221 = 2980311224095344389
> > У меня получилось за 10 мин.
>
> Pari/GP раскладывает за доли секунды:
>
> ? factorint(2980311224095344389)
> %1 =
> [910522409 1]
> [3273188221 1]
В Maple можно посмотреть код функции факторизации. На самом же деле происходит резкий скачек во времени где-то на границе 80-ти десятичных разрядов. На чем основан алгоритм, примененный в maple я не знаю, но там есть довольно большая константа, которая и вносит это ограничение
|
| | | | | | |
Согласно его хелпу: 27.09.04 12:20
Автор: RElf <M> Статус: Member
|
> На чем основан алгоритм, примененный в maple я не знаю,
Согласно его хелпу:
If a second parameter is specified, the named method will be used when the front-end code fails to achieve the factorization. By default, the Morrison-Brillhart algorithm is used as the base method. Currently accepted names are:
'squfof' - D. Shanks' undocumented square-free factorization;
'pollard' - J.M. Pollard's rho method;
'lenstra' - Lenstra's elliptic curve method; and
'easy' - which does no further work.
|
| | | | | |
Круто! Действительно, очень быстро. Если задача факторизации... 24.09.04 06:57
Автор: kata Статус: Незарегистрированный пользователь
|
> Pari/GP раскладывает за доли секунды:
>
> ? factorint(2980311224095344389)
> %1 =
> [910522409 1]
> [3273188221 1]
Круто! Действительно, очень быстро. Если задача факторизации решена математиками, почему тогда до сих пор существует RSA?
|
| | | | | | |
В RSA сейчас используются модули порядка 2^1024, а то и... 24.09.04 10:19
Автор: RElf <M> Статус: Member
|
> > Pari/GP раскладывает за доли секунды:
> >
> > ? factorint(2980311224095344389)
> > %1 =
> > [910522409 1]
> > [3273188221 1]
> Круто! Действительно, очень быстро. Если задача
> факторизации решена математиками, почему тогда до сих пор
> существует RSA?
В RSA сейчас используются модули порядка 2^1024, а то и 2^2048 и даже 2^4096. Такие числа не по зубам даже самым быстрым из известных алгоритмов.
|
| | | | | | |
Ахренеть! 24.09.04 07:43
Автор: kata Статус: Незарегистрированный пользователь
|
Ахренеть!
factorint((30350746216736546428736454623463745*30+29)/47*(10910627382873862553453279234*30+31)/7)
[46759831640887982371942625293 1]
[19372816734087157294938162525615157 1]
решается за 10 мин
|
| | | | | | | |
Ну что такое 100 битное число - малышка. А сколько времени... 24.09.04 10:18
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 24.09.04 10:19 Количество правок: 2
|
> Ахренеть!
> factorint((30350746216736546428736454623463745*30+29)/47*(1
> 0910627382873862553453279234*30+31)/7)
>
> [46759831640887982371942625293 1]
>
> [19372816734087157294938162525615157 1]
>
> решается за 10 мин
Ну что такое 100 битное число - малышка. А сколько времени займет факторизация двухкилобитного числа, ведь все сейчас все пользуются килобитными ключами.
А ночью лучше спать.
|
| | | | |
скорость факторизации и лома 23.09.04 11:53
Автор: kata Статус: Незарегистрированный пользователь
|
> Интересно, за какое время самый быстрый алгоритм
> факторизации разложит число
> 910522409 * 3273188221 = 2980311224095344389
> У меня получилось за 10 мин.
Если 56 битный ключ удалось поломать за 39 дней (http://sp.sz.ru/98_02_27_10_.html), а мне удалось разложить число N = 2980311224095344389 < 2^64 за 10 минут, то можно ли утверждать, что мой алгоритм взлома RSA будет работать более чем в 39 дн./ 10 мин. раз быстрее?
|
| | | | | |
Если речь о RSA, то 56 битными ключами никто не пользуется... 23.09.04 19:13
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Если 56 битный ключ удалось поломать за 39 дней
Если речь о RSA, то 56 битными ключами никто не пользуется. Раз уж они за 10 минут ломаются :).
> (http://sp.sz.ru/98_02_27_10_.html), а мне удалось
> разложить число N = 2980311224095344389 < 2^64 за 10
> минут, то можно ли утверждать, что мой алгоритм взлома RSA
Что за алгоритм? Наверное прямого перебора, за 10 мин можно перебрать все 32 битные числа.
> будет работать более чем в 39 дн./ 10 мин. раз быстрее?
|
| | | | | |
немного путаницы 23.09.04 13:07
Автор: leo <Леонид Юрьев> Статус: Elderman
|
|
Вы путаете успешный подбор 56-битного ключа DES по конкурсу устроенному "RSA Data Security" и взлом алгоритма RSA. DES это слабый симметричный блочный шифр и не имеет отношения ни к простым числам, ни к проблеме факторизации.
|
| | | | |
При использовании алгоритма Ленстры сложность будет... 23.09.04 10:32
Автор: Heller <Heller> Статус: Elderman
|
> Интересно, за какое время самый быстрый алгоритм
> факторизации разложит число
> 910522409 * 3273188221 = 2980311224095344389
> У меня получилось за 10 мин.
При использовании алгоритма Ленстры сложность будет ~2980311224095333412. Вычислить из этого время достаточно сложно - всё зависит от архитектуры процессора. Информации по вычислению по заданной сложности количества простейших операций для процессоров x86 я не нашёл. В любом случае, указанное число чаще всего можно использовать как верхний предел для количества операций. Ну а отсюда, с учётом частоты, уже считается время.
(формула для сложности алгоритма Ленстры L(n)=exp[(ln(n)*ln(ln(n)))^(1/2)], при условии, что n=pq)
|
|
|
подробно о проекте
Анализ криптографических сетевых...
