Постквантовая альтернатива RSA уже взломана

Вот статья координаторов проекта:
http://cr.yp.to/codes/mceliece-20080807.pdf

>станит - это новый материал, вроде гранита? :-)

Нет "станнит" - это соль оловянистой кислоты. ?:-(

ты утверждаешь, что полупроводниковые калькуляторы хороши тем, что можно носить в кармане, а ламповые - нет, именно поэтому они сакс. ты формально прав, но заостряешь внимание не на том.

понятие стойкости ко взлому на квантовом компьютере намного шире понятия быстрой факторизации чисел. ты обобщаешь не в ту сторону. более того, этот квантовый компутир в глаза еще никто не видел.

а вот за статью спасибо - пригодится

а откуда ты линк взял? :) статья весьма свежа на первый взгляд, особенно главное: оптимизация алгоритма Стерна

Полезная тулза

Скачай, поставь, расскажи

> а откуда ты линк взял? :)

Кто ищет, тот найдёт.

> понятие стойкости ко взлому на квантовом компьютере намного шире понятия быстрой факторизации чисел. ты обобщаешь не в ту сторону.

А что ещё дают квантовые компьютеры, кроме быстрой факторизации?

> более того, этот квантовый компутир в глаза еще никто не видел.

Кое что в этой области уже есть, причём не только на бумаге.

ты главное не соглашайся воду возить.

> Допустим, MD5 гарантировано не даёт коллизий при длинах менее, скажем, 64 байта

Это тоже самое если допустить что, например, земля плоская и заселена троллями.
128 бит могут гарантированно не давать коллизий в пределах 128 бит, а учитывая натуру алгоритма - даже это не гарантированно.


> one-way хеш гарантирует необратимость функции.

Плохо гарантирует, в алгоритме есть слабые места и коллизию можно подобрать достаточно быстро. Меня всегда улыбало когда пароль шифруют MD5 или DES. Равносильно вообще его не шифровать.

>А что ещё дают квантовые компьютеры, кроме быстрой факторизации?

Они делают ужасную вещь: многие NP-complete проблемы становятся решабельные за полиномное время. А если решается одна NP-complete проблема, то потенциально решаются все таковые (а там и рса, и декодирования линейных кодов,...)

Почитал. Вменяемая статья, кстати, спасибо. Только вот на вопросы она не отвечает. Я в подробности не вдавался, но насколько я понимаю, аргументированная сложность взлома данного шифра опирается на тот факт, что задача поиска кодового слова с данным весом в линейном двоичном коде NP-трудна (сам не утверждаю - так пишет Шнайер). Нет абсолютно никакой гарантии того, что очередной Шор не придумает квантовый алгоритм, решающий и эту задачу. Поэтому "постквантовая альтернатива RSA" - это слишком сильно сказано. Кроме того, у системы МакЭлиса есть недостатки, связанные с _существенным_ увеличением длин ключей (в оригинале МакЭлис предложил брать длины: ~2^20 бит - закрытый ключ, 2^19 бит - открытый ключ - и, как мы видим, этого на данный момент уже мало! O_O), а также длины шифртекста. Поэтому система Эль-Гамаля сейчас выглядит явно предпочтительнее. В том числе и как "постквантовая" альтернатива RSA.

> а там и рса

Задача факторизации числа никогда не была NP-полной.

это так, но от того не легче

It is known to be in both NP and co-NP. This is because both YES and NO answers can be trivially verified given the prime factors (we can verify their primality using the AKS primality test, and that their product is N by multiplication)

If it could be proved that it is in either NP-Complete or co-NP-Complete, that would imply NP = co-NP. That would be a very surprising result

>* Совсем не понятно, что такое "атака на алгоритм": они разузнали ключ или расшифровали одно сообщение?

на сколько я понял расшифровал сообщение. ищется слово весом меньше 50, а не матрица.

>* То, что классический МакЭелис не явлается достаточно секурным, было показано еще в 2001 году: A. Al Jabri. A Statistical Decoding Algorithm for General Linear Block Codes. B. Honary (Ed.): Proceedings of 8th IMA International Conference on Cryptography and Coding, Cirencester, UK, December 17-19, 2001, Lecture Notes in Computer Science 2260, p. 1-8, 2001. Он на 700МГц пицуке за 2^9 часов сделал подобное.

интересно получается. Al Jabri использует почему-то Гоппа код (1024, 512, 51) вместо предложенного МакЭелисом (1024,524,50), что вроде как ещё секурней чем оригинал, если я не ошибаюсь. Тем не менее Al Jabri заявляет время меньшее, чем заявил Bernstein & Co. Единственно, что мне но понятно, пытался ли Al Jabri реально заимплементировать свой метод, который реально даёт результат.

Потом Al Jabri говорит, что для его метода надо много памяти (много на 2001 год?). Атака Bernstein'а не нуждается в большом количестве памяти

>Так что не кипятиться! Ждем статьи.

http://cr.yp.to/codes/mceliece-20080807.pdf

эта статья была написана ещё, когда эксперимент был в процессе.

Его статья (Al Jabri) мне выглядит не без изъянов: он почти опускает поиск слов с малым/большим весом, а этот поиск сложен.

На счет имплементации... ээээх, ваш покорный слуга должен ее реализовать до конца семестра :)

Можно линк на текст? А-то я так понимаю, ты приводишь инфу не о факторизации, а о проверке числа на простоту. Задачу факторизации вообще никак нельзя отнести ни к NP, ни к co-NP (тем более к их пересечению), т.к. эти сложностные классы образованы только задачами распознавания, в то время как факторизация - это задача поиска.

На самом деле в 2002 году индусами был представлен алгоритм проверки числа на простоту (кстати, именно AKS primality test). Поэтому данная задача вообще лежит в классе P. Правда, там полином 12й степени. :) Но всё-таки полином. Однако даже с этими результатами сама по себе факторизация числа остается задачей, алгоритма решения которой до сих пор не придумано, и при этом сложность ее также ничем не аргументирована (то есть не доказано, что такого алгоритма не существует).

Lenstra вроде опустил степень до 6.

> Lenstra вроде опустил степень до 6.

Ага, точно. Википедия сказала, что в 2005м он понизил степень. :)

http://en.wikipedia.org/wiki/Integer_factorization ?

че-то я ход мыслей не улавливаю. так факторизация распознает или ищет?

> так факторизация распознает или ищет?

факторизация ищет проверка на простоту распознает

> На счет имплементации... ээээх, ваш покорный слуга должен ее реализовать до конца семестра :)

время ещё есть. :) очень интересно будет посмотреть на результат. Это курсовик? Преследуемая цель написание кода более теоретическая (чтоб понять) или практическая (чтоб ломать)?

Твой "ящик для спама" актуален?

актуален :)

Квантовые компьютеры — 128-битные? Они есть? Или когда появятся? Кто что думает? И есть ли уже какие нибудь ОС для таких процев?

http://ru.wikipedia.org/wiki/Квантовый_компьютер

>Они делают ужасную вещь: многие NP-complete проблемы становятся решабельные за полиномное время

Тока одно маленькое уточнение. Их нет в природе. Есть тока эмули на сотню-дргую кубитов максимум. Как устройства, DWave представляла в прошлом году аж 16кубитный вычислитель не пойми чего. На след го они обещали 1024кубита. У вас будет время посмотреть как эти парни круто облажались.

>Они есть? Или когда появятся? В викимусорке касательно реализации написан полубред, это имейте ввиду при чтении сего образовательного матирьяла

>Ты бредишь или просто неуч. Главное свойство McEliece является то, что эта система не основывается на теории чисел, как РСА, а на теории кодирования в связке с полями Галуа и прочими фишками. Одним словом, где в РСА числа, там в МакЭлисе полиномы.

Бугога, а что, уже есть разница между полиномом и числом? Поля Галуа в частности, и теория конечных полей в целом являются малым подмножеством теории чисел.

>Они делают ужасную вещь: многие NP-complete проблемы становятся решабельные за полиномное время. А если решается одна NP-complete проблема, то потенциально решаются все таковые (а там и рса, и декодирования линейных кодов,...)

Бред не надо тут распространять.

и ты прав. можно пофилосовствовать о числах и значениях. но вот поля - это алгебра, а тория чисел немного другое. но я должен согласиться, что обе дисциплины изучаются в рамках единой науки математика ;)

это скорее сверические кони.

а ещё бывает алгебраическая теория чисел!

> Тока одно маленькое уточнение. Их нет в природе. Есть тока эмули на сотню-дргую кубитов максимум. Как устройства, DWave представляла в прошлом году аж 16кубитный вычислитель не пойми чего. На след го они обещали 1024кубита. У вас будет время посмотреть как эти парни круто облажались.

Я сам занимаюсь квантовыми компьютерами и квантовой теорией информации и с полной отвественностью заявляю, что пока не сделают квантовый компьютер с ~1000 кубит - он бесполезен. Современные разработки не позволяют создать кв комп более нескольких десятков кубит. И этот порог не могут преодолеть уже лет 7. Технология не позволяет. Чтоб сделать больше - нужно придумать принципиально новую технологию. А это - далеко не тривиальная задача. Так что с криптоалгоритмами можно пока что не паниковать.