Автопробегом по криптографии

[waspagv]

Когда я работал преподавателем на кафедре астрономии Удмуртского гос. университета, отбиваться от "доказателей" теоремы Ферма не довелось. Они ходили к алгебраистам. Мне  выпала тяжкая доля посылать постигателей основ мироздания. Как минимум раз в месяц такие к нам захаживали. Они решали фундаментальные проблемы физики и космологии на одном тетрадном листочке. Решали сразу и окончательно. Никаких доводов против своих "теорий" не слушали. Предложение представить хоть какие-то доказательства считали оскорблением. Отказ немедленно выдвинуть их на Нобелевскую премию расценивали как зажим талантов и обещали жаловаться. Жаловались в местные газеты, которые охотно их поддерживали (кроме "АиФа в Удмуртии", который напечатал на целую полосу мои подзатыльники открывателю "магнитной звезды Паллады" Юрию Иванову).

К чему я это? Вот здесь shalti_bolti скромно сообщил о "самом быстром способе" нахождения всех делителей числа. Решение в несколько строк на Паскале. С ужасом жду кризиса криптографии с открытым ключом.

P.S. Фраза "криптация с открытым ключом основывается на невозможности за конечное время разложить число на множители" из обсуждения алгоритма особенно хороша!

Comments

[m2b.livejournal.com]

криптация с открытым ключом основывается на невозможности за конечное время разложить число на множители

А правильней было бы сказать "за короткое время", правильно я понимаю?

Я от этих вопросов весьма далек, так что просьба не нападать на меня за лженаучность и мракобесие :)

[waspagv.livejournal.com]

Правильно сказать так: криптостойкость алгоритма RSA основана на предположении о невозможности разложения числа на множители за полиномиальное время. Грубо говоря, если n - размерность задачи (в нашем случае количество двоичных разрядов числа), то невозможно найти алгоритм, который раскладывает число на множители за время порядка Cn^p, где C и p - константы (не зависят от n).

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

Проблемой занимались и занимаются многие математики и криптоаналитики. Поэтому когда некто, не владеющий даже терминологией ("криптация"!), предлагает полное и окончательное решение из 20 строк, чего удивляться, что его воспримут всерьез только братья по разуму.

Не вся криптография с открытым ключом строится на трудности разложении числа на множители. В основу метода можно положить любую трудную (NP-полную (http://ru.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0), или предположительно NP-полную) задачу, например отыскание дискретного логарифма, факторизация на эллиптической кривой, разложение на множители произведения конечных автоматов и много чего еще. Российский стандарт на алгоритм электронной подписи ГОСТ Р 34.10-2001 базируется эллиптических кривых.

недавно наткнулся!

[m2b.livejournal.com]

http://amerik.livejournal.com/60914.html#cutid1

Re: недавно наткнулся!

[waspagv.livejournal.com]

Математики обо все узнают последними. :) Даже об использовании своих работ на практике.

а мужики-то не знают!

[sermp.livejournal.com]

класс!
это в science_freaks (http://community.livejournal.com/science_freaks/) срочно! =)
хотя, если честно, без объяснения идеи, прото поглядев код на паскале не понятно =) но, судя по "криптации" товарищ достаточно близко знаком с современной криптографией =)))) надо ссылку послать в ФСБ - они заинтересуются =))

Re: а мужики-то не знают!

[waspagv.livejournal.com]

Вах! Так в том сообществе упоминается (http://community.livejournal.com/science_freaks/964525.html) тот самый Юрий Иванов, с которого я начал этот пост. Далеко пошел, мужЫк!