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

Вот генту бы на квантовом компьютере скомпилировать, а им бы только пароли ломать

чорт, у меня квантовый компьютер уже лет 10 под столом пылится, а я ему применение найти не могу, спасибо за подсказку - теперь стану властителем интернета

Зря смеётесь...

Давно было ясно, что современная криптоматематика имеет толстые бэкдоры, а факт, что соорудили публичные решатели - слабо интересен в сравнении с закрытыми разработками 30-летней давности.

> алгоритм RSA стан__и__т легко уязвимым

Решением военно-полевого граммарнаци-суда шома признан виновным в злоупотреблении доверием русскоязычных посетителей сайта и надругательством на родной речью и приговаривается к высшей мере наказания — модерированию ЖЖ-сообщества devki_v_shope. Приговор вступает в силу немедленно и обжалованию не подлежит.

>Постквантовая альтернатива RSA уже взломана
>При этом алгоритм Роберта Джи Мак-Элиса всё ещё считается неуязвимым к взлому на квантовом компьютере.

Надоели заголовки в стиле Комсомольской правды

А вдруг это стеганография, тайное сообщение Юстасу? :-)) Можно было молча исправить. А така, какой пример анонимусам?

>слабо интересен в сравнении с закрытыми разработками 30-летней давности.

предлагаете скрывать алгоритм шифрования? %)

> > Постквантовая альтернатива RSA уже взломана > > При этом алгоритм Роберта Джи Мак-Элиса всё ещё считается неуязвимым к взлому на квантовом компьютере.

> Надоели заголовки в стиле Комсомольской правды

Его взломали на квантовом компьютере? Надоели комментарии в стиле комсомольского собрания.

И, в солидарность с предыдущими ораторами, предлагаю подписать петицию за принудительную установку модераторам спеллчекера

>>Его взломали на квантовом компьютере?

>уже взломана
>всё ещё считается неуязвимым

Не видите противоречия?

ага, ломается на полупроводниковом и неуязвимо на квантовом. :)

>Его взломали на квантовом компьютере? Надоели комментарии в стиле комсомольского собрания.

Желтопресса любит таким баловаться
Заголовок новости: "Болезнь, от которой нет лекарства! Мы все умрем!"
А в текста написано: "Лекарство активно разрабатывается и через 2.5 часа поступит во все аптеки"

> > Его взломали на квантовом компьютере? Надоели комментарии в стиле комсомольского собрания.

> Желтопресса любит таким баловаться Заголовок новости: "Болезнь, от которой нет лекарства! Мы все умрем!" А в текста написано: "Лекарство активно разрабатывается и через 2.5 часа поступит во все аптеки"

Пример совершенно нерелевантный.

Ещё раз, специально для медленно понимающих простой текст. Главное свойство алгоритма McEliece - стойкость к взлому на квантовом компьютере. Тоесть при помощи алгоритма, реализуемого только там. Со взломом на обычном двоичном компьютере это никак не связано. Взлом на обычном компьютере должен быть таким же трудно осуществимым как и взлом RSA на этом компьютере. Он таковым и является, но опыт показал, что длину ключа, предложеную автором, следует увеличить. Однако основное свойство алгоритма McEliece - стойкость ко взлому на квантовом компьютере. Теперь достаточно понятно разжёвано?

> предлагаете скрывать алгоритм шифрования? %)

Думаю, что стоит к шифрованию добавить распределённую проверку подлинности автора и отправителя, тотальное логирование и прочие радости. "Чем выше забор - тем добрее соседи" (С)

> И, в солидарность с предыдущими ораторами, предлагаю подписать петицию за принудительную установку модераторам спеллчекера

Спеллчекер не поможет против перлов "студенту, учащемуся на степень доктора".

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

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

ага, квантовый криптостойкий наноматериал :-)

>защищённого от взлома на квантовом компьютере

Нашли от чего защищаться, наши и на атлоне поломают

> Спеллчекер не поможет против перлов "студенту, учащемуся на степень доктора".

Тебе уже точно ничего не поможе: "Neill Costigan, PhD student at DCU". Любой учащийся университета, не важно на какую степень, является студентом. Неучь ты бестолковая.

мы все умрем

А как это поможет защититься от взлома?

>мы все умрем >bernd (*) (29.10.2008 2:16:36)

>А как это поможет защититься от взлома? >bbk123 ** (*) (29.10.2008 2:18:24)

А разве не очевидно?

Не очевидно. Вопрос был о защите от взлома, а не о защите целостности информации.

"Роберта Джи Мак-Элиэса (Robert J McEliece). "

шаман, это:"J"-буква "джей". джи - "G". так, для памяти

Если есть математики - обьясните давно мучающаю очевидную для вас вещь.
Я, конечно, ламер в криптографии, но обьясните на пальцах - почему следующая простая схема не работает?

Допустим, MD5 гарантировано не даёт коллизий при длинах менее, скажем, 64 байта (известный кряк предполагает что ключ - как минимум 1024 бит, а здесь - в 2 раза меньше).
Вводим пароль. Потом шифруем стрим: (каждые 64 байта стрима+64 байта пароля - всё ещё менее 1024) и получаем на каждый такой блок - хеш. Брут-форсом - 26^64 (больше гугола) не переберёшь, a one-way хеш гарантирует необратимость функции.

Почему это не работает? как взломать такой стрим теоретически?

Товарищ bbk123, Вы, безусловно, правы - любой учащийся университета, не важно на какую степень, является студентом. В английском языке это, пожалуй, верно (про другие иностранные я не в курсе), а в русском есть термины студент, аспирант, докторант.

> давно идут поиски альтернативного криптографического алгоритма с открытым ключём, защищённого от взлома на квантовом компьютере

Давно идут поиски? МакЭлис представил свою схему шифрования в 1978 году, что на год позже опубликования системы RSA. Кроме того, никто пока не отменял систему Эль-Гамаля. Шор предложил квантовый алгоритм факторизации в 1994. То есть альтернативы RSA на тот момент уже существовали. И, кстати, чем схема МакЭлиса гарантирована от взлома на квантовом компьютере?

Из второго абзаца нихрена непонятно. Кто произвел взлом, и сколько времени на это ушло? При какой длине ключа?

а квантовый компьютер разве не закопали? вроде как был материал в этом году?

да да, конечно, как только у народа появятся квантовые компьютеры - народ сразу побежит взламывать ключи, зашифрованные этим алгоритмом. Идиоты из центра исследований похоже не догадались, что 8000 часов без перерыва никто и ничего взламывать не будет. Да даже 4000 часов. Да даже один месяц, всё равно это нафиг никому будет не нужно. Вот что бывает, когда студенту_с_корочками дают задание из реальной жизни.

> Тебе уже точно ничего не поможе: "Neill Costigan, PhD student at DCU". Любой учащийся университета, не важно на какую степень, является студентом. Неучь ты бестолковая.

Ошибаются все люди. Дураки настаивают на своих ошибках. Привел доказательство, потому что в английском PhD student, ха. В английском и школьников называют student - может ты бы еще перевел "школьник, обучающийся на доктора"?

> Поэтому давно идут поиски альтернативного криптографического алгоритма с открытым ключём, защищённого от взлома на квантовом компьютере.

> алгоритма с открытым ключём

> ключём

вот всегда так - вместо того, чтобы ходить в школу на уроки русского языка, строчат новости на мой ЛОР... 'О' там должна быть, а не 'Ё'.

> Студенту Дублинского университета (DCU) Нейлу Костигану, учащемуся на степень доктора

если "учится" на доктора, то это не студент, а докторант

> Почему это не работает? как взломать такой стрим теоретически?

md5 - хеш функция, а алгоритм шифрования ... поэтому и работать не будет ... как потом расшифровывать-то ...

md5 - хеш функция, а не алгоритм шифрования ... поэтому и работать не будет ... как потом расшифровывать-то ...

/fixed

> Идиоты из центра исследований похоже не догадались, что 8000 часов без перерыва никто и ничего взламывать не будет. Да даже 4000 часов. Да даже один месяц, всё равно это нафиг никому будет не нужно.

Во-первых, если ломается за 8000 часов, то есть значительная вероятность, что в каком-то конкретном случае сломается и за 800 часов. А во-вторых, совсем не обязательно ломать одним компом, можно зарядить сто компов. Целесообразность зависит от того, что спрятано за ломаемым ключиком.

> Вот что бывает, когда студенту_с_корочками дают задание из реальной жизни.

Реальная Жизнь гораздо шире, чем то, что может успеть увидеть один человек за одну свою жизнь.

> Любой учащийся университета, не важно на какую степень, является студентом

это у них за языковой бедностью не важно

а в русском языке помимо студентов есть:

магистранты, аспиранты, докторанты

> а в русском языке помимо студентов есть:

> магистранты, аспиранты, докторанты

И ещё соискатели. Но местным аффтарам и модераторам на это наплевать, они ни русского ни английского не знают.

ЦАП + Аналоговое шифрование сигналов с цифровой модуляцие в tcp-ip пакеты спасет мир.

А у меня магистрская по Маклису... :)

Не на правах эксперта, но все же:

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

* То, что классический МакЭелис не явлается достаточно секурным, было показано еще в 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 часов сделал подобное.

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

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

РСА хорош теперь, но уже теперь существует (вероятностный) алгоритм для квантовых компьютеров, факторизирующий большие числа за полиномное время. Все. МакЭлис хорош только тем, что не водится с факторизацией чисел.

А длину ключа надо увеличивать уже давно. Желтизна.

Но против термокомпьютера (CodeName "PAYALNIK") этот алгоритм бессилен :(

>> Студенту Дублинского университета (DCU) Нейлу Костигану, учащемуся на степень доктора

> если "учится" на доктора, то это не студент, а докторант

Причем PhD - это все-же ближе к нашему кандидату. Так что аспирант.

> Но против термокомпьютера (CodeName "PAYALNIK") этот алгоритм бессилен :(

Не надоело ещё про паяльник твердить? Одно дело, когда ты сам кому-то ключ расскажешь и будешь знать, твои секреты - больше не секреты. Совсем другое - когда твои данные умыкнут так, что ты и не заметишь... до поры до времени.

> Докторанту Дублинского университета

Бу-га-га. Новость отредактировали, заменили "студента" на "докторанта". Однако малограмотным модераторам невдомёк, что "PhD student" --- это аспирант. "Докторант" --- это "postdoctoral".

> В английском и школьников называют student

Да, в основном в американском :) А вообще, student - это еще и просто "изучающий", напр. a student of cryptography :)

> > Студенту Дублинского университета (DCU) Нейлу Костигану, учащемуся на степень доктора

> если "учится" на доктора, то это не студент, а докторант

Докторант - это doctoral candidate, а там написано PhD student. И вообще, советская/российчкая градация академических званий и степеней отличается от западной.

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

Ну и в чём тут противоречие? Если алгоритм McEliece не основан на теории чисел, если быстрая факторизация больших чисел ему не страшна, то почему нельзя сказать, что главное свойство этого алгоритма это "стойкость к взлому на квантовом компьютере"? Может быть ты сам бредишь или просто не понимаешь текст?

О, Квантовые вычисления на... найобиумной основе :)

Не будет квантовых компьютеров сложнее "аппарата для решения уравнения Шредингера" (читать: "струя воды из крана как компьютер для решения уравнений Навье-Стокса") ;)