Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | | |
И вновь каша в голове. 01.10.04 12:40 Число просмотров: 4210
Автор: lime Статус: Незарегистрированный пользователь
Отредактировано 01.10.04 14:21 Количество правок: 1
|
И вновь каша в голове.
Абзац первый: "все алгоритмы факторизации работают за полиномиальное время".
Абзац второй: "Они имеют либо экспоненциальную сложность, либо субэкспоненциальную".
Может все-таки следует глубоко вздохнуть и подумать?
По поводу "верхний предел всегда известен" - это да... Для любой задачи размера n с экспоненциальной сложностью верхний предел тоже известен. Он равен O(k^n). И это не делает его полиномиальным.
А теперь по поводу постскриптума.
Аргумент вида "Во всяком случае, я никогда в научных изданиях не встречался с использованием даже косвенным) данной гипотезы, когда речь идёт о простоте чисел." - это только аргумент. Люди умные обычно используют в своей бесебе другие категории, называемые доказательством.
Иными словами я предлагаю Вам доказать состоятельность постскриптума в полном объеме.
В свою очередь в данном посте http://www.bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m=112803 я уже обещал сделать обратное.
Ну как?
|
|
<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)
|
|
|
подробно о проекте
Анализ криптографических сетевых...
