2borislav

>Microsoft встраивал в свой IE5.5 поддержку 128-битного шифрования. Не более чем. Это называлось High Encryption Pack. 1024 бита, и пусть никто не удйет обиженным.

borislav не пишите больше на тему крипто. В предмете Вы абсолютно не компетентны.

Вы совершенно не понимаете разницы между симметричным шифрованием и несимметричным. Так вот: алгоритмы несимметричного шифрования (RSA и DSA) оперируют ключами огромной длины (от 512 minimum, 1024, 2048). Они всем хороши, но - УЖАСТНО тормозные. Симметричные шифры работают с ключами от 40 бит (DES, 3DES, IDEA, AES128, AES256, etc). Они быстры, надежны, но у них есть проблема - ПЕРЕДАЧА общего ключа. Угадайте, как избавится от недостатков и использовать достоинства обеих технологий по полной. Правильно! Несимметричное шифрование (в нашем случае RSA) используется ТОЛЬКО на начальном этапе защищенной сессии для согласования СИММЕТРИЧНОГО ключа. А затем уже работает (шифрование собственно сессии), например, AES128 (длина ключа - 128 бит, как Вы догадываетесь из названия). AES256 считается уже параноидальным шифром.

Так, что 128-битное шифрование - это ДЕЙСТВИТЕЛЬНО High Encryption Pack.

Технологии OpenPGP (впрочем, как и S/MIME) Вы сюда приплели совершенно напрасно - это уже из другой оперы. В областях, где используются GnuPG/PGP быстродействие не критично. И, все равно, не советуют ключи длиннее 1024

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

Мне, честное слово, досадно, что журналисты медиахолдинга "Rambler" не отличают разложение на множители числа заданной длины от стойкости алгоритма, как такового.

> Известно, что существуют суперкомпьютеры, на которых это можно проделать значительно быстрее, приводятся оценки.

Приведите их, пожалуйста. Для ключа в 2048 бит.

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

Видите ли, "сообщение, закодированное 640-битным ключом" в сколь-нибудь прикладном смысле (S/MIME, SSL, OpenPGP) само не зашифровано этим ключом. Проблема асимметричными алгоритмами состоит в том, что во-первых, они слишком медленны для того, что бы шифровать ими большие сообщения, во-вторых, ими можно зашифровать только сообщение определенной небольшой длинны, соответствующей числу, участвующему в операции возведения в степень, а механизмы сцепления блоков шифротекста не применяются. Таким образом, как правило, асимметрично шифруют ключ для симметричного шифра, которым шифруют само сообщение.

Кроме того, существуют заведомо слабые простые пары.

Наконец, существуют различные covert channels и ошибки в протоколах и реализациях. Загляните, ради интереса на сайт GnuPG, поинтересуйтесь. Там есть куча материала для заголовков "Безопасность Интернета под угрозой" и "Хакеры готовы украсть ваши деньги" - при правилной подаче, разумеется. :)

В общем, в цепочке алгоритм-протокол-реализация, алгоритм - не самое слабое звено.

Кроме того, насколько мне известно, минимальная длина ключа RSA, которая применялась практически - 768 бит. Иначе говоря, разложение числа такой длины в 2^(768-640)=340282366920938463463374607431768211456 раз сложнее. В настоящее время практически никто не применяет ключи короче 1024 бит.

> В этом было что-то противозаконное?

Ничего. Но намеки на то, что "могло бы быть" оставим Ленте.Вру.

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

Конечное. Только очень большое. И ресурсов на его поиск нужно больше, чем выигрыш, который можно получить, расшифровав сообщение. Странно, что вам это не очевидно. :)))

И чуть-чуть еще к остальным комментариям:

> Я в статье объяснил, насколько это возможно, что это было вполне себе академическое исследование - и, тем не менее, взлом в том смысле, в котором понимают взлом шифра.

Под взломом шифра RSA понималась бы возможность разложения числа на множители за полиномиальное время. То, что вы выдали за "взлом", являлось задачей, которая заведомо была бы решена.

> Вот какая штука: в 2001 году, то есть через год после снятия запрета на экспорт сильной криптографии, Microsoft встраивал в свой IE5.5 поддержку 128-битного шифрования.

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

Пожалуй, вас стоит предложить кандидатом на "чугунную крысу". :)))

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

Приведите, пожалуйста, ссылки на авторитетный источник, а не на журналистский бред, где показано, что из-за разложения RSA640 надежность RSA вообще оказалась ниже.

> на не бог весть каких машинах.

да. до тепловой смерти Вселенной, пожалуй, управимся. :)))

>В серьезных делах длины ключей всегда были больше.

В "серьезных делах" всегда используется т.н. абсолютный шифр Шеннона (по сути - XOR) с совершенно случайным (математически случайным!)ключем, длина которого равна длине сообщения и он (ключ) ни когда дважды не используется.

И - ни каких RSA, DSA, DH! Все эти алгоритмы построены на ПРЕДПОЛОЖЕНИИ об огромной вычислительной сложности факторизации больших чисел (этого еще ни кто не доказал, впрочем, как и обратного). "Серьезные дяди" ТАК рисковать не имеют права.

> с совершенно случайным (математически случайным!)ключем

Наверное, все-таки, с "физически случайным" - в том смысле, что он не алгоритмом создается, а за счет случайных физических процессов.

>> с совершенно случайным (математически случайным!) ключем

>Наверное, все-таки, с "физически случайным" - в том смысле, что он не алгоритмом создается, а за счет случайных физических процессов.

Именно "математически"! Дело в том, что в случайной последовательности, созданной действительно физическим (тепловым) генератором все равно попадаются достаточно большие участки, как бы не совсем белого шума. По этому, выходная последовательность всегда математически проверяется на "случайность" (например, автокорреляционные функии со сдвигом на 1 бит, на 2 бита и так далее, остановка по степени паранойи. И много еще чего)

> Именно "математически"! Дело в том, что в случайной последовательности, созданной действительно физическим (тепловым) генератором все равно попадаются достаточно большие участки, как бы не совсем белого шума.

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

> Вот какая штука: в 2001 году, то есть через год после снятия запрета > на экспорт сильной криптографии, Microsoft <a href=http://www. > microsoft.com/windows/ie/downloads/recommended/128bit/default.mspx>; > встраивал</a> в свой IE5.5 поддержку 128-битного шифрования. Не > более чем. Это называлось High Encryption Pack.

С Вами все ясно. Вы типичный журналист для желтой прессы - высасываете сенсации из пальца, при этом совершенно не разбираясь в предмете. То, о чем Вы написали (128bit) НИКАК не относится к RSA! Это длина симметричного ключа (случайно сгенерированного), который применяется для шифрования конкретной сессии. И то, что Вы этого не понимаете, следует из Вашего утверждения совершенно четко.

Впрочем, чего еще можно ожидать от "журналистов" ленты.вру?

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

Кто бы спорил! Повторю еще раз: последовательность, порожденная физическим генератором, всегда еще ДОПОЛНИТЕЛЬНО математически проверяется на "истинную случайнось". Участки гаммы, не прошедшие такой проверки отправляются в мусор.

Томми знал как взломать RSA..

> И - ни каких RSA, DSA, DH! Все эти алгоритмы построены на ПРЕДПОЛОЖЕНИИ об огромной вычислительной сложности факторизации больших чисел

Неправда. На этом предположение основывается только алгоритм RSA. В основе DSA и DH лежит другая проблема - дискретное логарифмирование.

> Математическая проблема факторизации больших чисел, которая лежит в основе RSA, пока считается NP-задачей.

Задача факторизации, очевидно, лежит в классе NP, но до сих пор неизвестно является ли она NP-полной. Поэтому нижеследующий вывод необоснован.

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

Тезис "невзламываемый за разумное время" предполагает использование (лучших из) _известных_ на данный момент алгоритмов. Кто знает, возможно, в будущем удастся найти куда более эффективные алгоритмы, которые помогут разложить 1024-битные модули "за разумное время".

Фактроризация и NP-полнота

Насчет фактроризации и NP-полноты см. пункт 2 в

http://www.cryptography.ru/db/msg.html?mid=1169815

Сейчас там какие-то проблемы с сайтом, если не откроется см. сохраненную гуглом версию:

http://64.233.187.104/search?q=cache:q3aoUJpRH20J:www.cryptography.ru/db/msg.html%3Fmid%3D1169815

Судя по тому, что Борислав так и не появился здесь снова, чтобы извиниться перед читателями (отстаивать далее свою точку зрения ему смысла уже нет, ivlad и Ко уже настолько все разжевали, что защищать лентаврушную писанину может теперь только глупец), я думаю, можно констатировать факт: слив Бориславу таки да засчитан.

Сейчас только утро. Может быть позже пожалует. Я бы подождал. Вдруг еще пару-тройку перлов выдаст? :)

> авось разложит ко второму пришествию То-то, я смотрю, честные парни ложат всё в init.d, а к факторизованым числам причастны одни и те же кексы (Монтгомери и иже с ним).. ;)

>То, о чем Вы написали (128bit) НИКАК не относится к RSA!

Это правда.

56 (и 128) бит действительно имеют отношение к алгоритмам закрытого ключа. Для RSA экспортные ограничения касались 512-битных и более длинных ключей. Я исправил это место в тексте. Теперь можете засчитывать мне слив.

Кавычки, реплики про желтую прессу и остальное - Ваше законное право.

Кстати о птичках.

>Так или иначе, если даже современные методы интернет-криптографии и безопасны, то могут лишиться этого свойства весьма скоро. Об этом, кстати, предупреждает при первом запуске популярный браузер Internet Explorer: "Сведения, переданные в Интернет, могут быть доступны другим пользователям".

Вообще, данные передаются "в Интернет" именно для того, чтобы они были доступны другим пользователям. Если IE этого не может обеспечить, то MS показывает это сообщение совершенно правильно. Только правильнее было бы это сообщение показывать всегда, а не только при первом запуске.

>Более удачно то же сформулировал Иосиф Бродский

Я могу сформулировать еще удачнее: use firefox :) Тогда они точно будут доступны другим пользователям. :)))

PS: мне тут как раз вспомнились постоянные жалобы на сбои при добавлении сообщений. Так вот откуда ноги ростут! Бедные пользователи передают информацию "в Интернет", передают, еще раз передаю, она все никак не может стать доступной другим. Оказывается, они просто невнимательно прочитали это сообщение при первом запуске. =)))

2borislav

То, что после ТАКОГО разгрома Вы появились здесь и признаете свою неправоту, заслуживает уважения. По крайней мере в моих глазах.

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

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

Мое мнение - Вы своей работой наносите ВРЕД. Очень хочется, что бы Вы это вспоминали всякий раз, когда получаете гонорары в редакции за свои статьи.

>Высшее математическое образование - что бы просто грамотно использовать терминологию

Я не успел получить высшего математического образования - я ограничился четырьмя семестрами. После четвертого университетский курс алгебры заканчивается для тех, кто собирается заниматься другими разделами математики.

"Механизм" RSA формулируется в терминах, понятных матшкольнику. Алгоритмы факторизации (когда речь не идет о дивизорах и эллиптических кривых) требуют умения разбираться с полями Галуа и кольцами многочленов. Этим любопытным вещам был посвящен один из экзаменов, которые я сдавал - алгебра, третий семестр. Для грамотного пользования терминологией, на мой взгляд, достаточно.

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

С вами мы, кстати, тоже разговаривали о другом. Я не уверен, что сведения практикующих линукс-специалистов о криптографии - академического происхождения.

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

У меня нет поводов считать, что я наношу кому-либо вред. Из тридцати тысяч читателей сто озаботятся и пойдут читать Шнейера или Коблица. Дабы, само собой, убедиться, что в действительности все не так, как на самом деле.

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

Маловато будет. © "Падал прошлогодний снег"

Richard P. Brent "Recent Progress and Prospects for Integer Factorization Algorithms" http://xyyxf.at.tut.by/rpb196sp.pdf

Michael Case "A Beginner's Guide to the General Number Field Sieve" http://islab.oregonstate.edu/koc/ece575/03Project/Case/paper.pdf

Matthew E. Briggs "An Introduction to the General Number Field Sieve" http://scholar.lib.vt.edu/theses/available/etd-32298-93111/unrestricted/etd.pdf

Советую прочесть в указанном порядке :)