id: Гость   вход   регистрация
текущее время 07:20 19/09/2021
Владелец: unknown (создано 05/08/2008 17:38), редакция от 21/11/2011 22:25 (автор: Гость) Печать
Категории: криптография, алгоритмы, шифрование с открытым ключом
https://www.pgpru.com/Новости/2008/НовыеНаправленияВАссиметричнойКриптографии
создать
просмотр
редакции
ссылки

05.08 // Новые направления в асимметричной криптографии


Криптография с открытым (или публично доступным) ключом (Public Key Crypto – PKC) стала известна в семидесятые годы прошлого века. Рассекреченые позднее документы, относящиеся к 1970 году, свидетельствуют об открытии её в секретных службах Великобритании исследователями James H. Ellis, Clifford Cocks, и Malcolm Williamson.


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


Такую криптографию стали называть также асимметричной в отличии от симметричной, где требуется сохранение в тайне ключа, необходимого для связи. Однако такое деление быстро стало условным – реальные криптосистемы являются комплексными и сочетают в себе и асимметричные и симметричные алгоритмы, а асимметричные алгоритмы служат часто лишь для распределения симметричных ключей.


В практическом аспекте асимметричная криптография решает задачу построения связи на основе доверия к владельцу ключа. Оно может быть достигнуто разными способами, которые используют криптографию, но сами по себе основаны на организационных и психологических методах (построение сетей доверия, интерактивное общение, сообщества по интересам – например разработчиков открытого ПО и т.д.). Таким образом криптография с открытым ключём играет важную роль в жизни информационного общества.


Первый асимметричный алгоритм совместной генерации сеансового симметричного ключа был опубликован Диффи и Хеллманом в 1976 году (DH). Предшествовавший ему алгоритм Меркла считается непрактичным. Алгоритм DH основан на трудности нахождения дискретных логарифмов. Его идея была адаптирована для создания алгоритма шифрования с открытым ключом Эль-Гамаля и алгоритма подписи Эль-Гамаля (1984 год), вариант которой, предложенный американским Агентством Национальной Безопасности совместно с институтом стандартов NIST, был принят как стандарт DSA.


Другой известный алгоритм для шифрования и подписи был изобретён Райвистом, Шамиром и Адлеманом (RSA) и опубликован в 1978 году. Он основан на другой проблеме – трудности нахождения множителей произведения двух простых чисел (целочисленной факторизации). Система шифрования Рабина также полагается на трудность этой проблемы.


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


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


В 1985-1987 Коблиц и Миллер дали начало идее криптографии на эллиптических кривых (Elliptic Curve Cryptography – ECC), которая позволила перенести все алгоритмы, основанные на проблеме Диффи-Хеллмана в группы точек на эллиптических кривых. Если в традиционных DH-алгоритмах используются мультипликативные группы, то здесь применяются аддитивные группы точек эллиптических кривых над конечными полями. Это позволило убрать возможность применения ненужных операций, которые только способствуют ускоренному взлому и несмотря на повышенный объём вычислений в процессе работы криптоалгоритмов, увеличить относительную стойкость. Соответственно длина ключа становится значительно меньше, и при такой длине ключа абсолютная скорость возрастает. Многие системы, в которых происходит или обработка очень большого числа запросов (электронное голосование), или используется очень слабый процессор для операций (смарт-карты) проектируются на основе ECC-алгоритмов.


Двумя основными проблемами асимметричных алгоритмов по прежнему остаются:

  1. Низкая скорость – в тысячи-сотни раз ниже, чем у симметричных.
  2. Привязка к одному классу теоретически трудных задач – дискретному логарифмированию и целочисленной факторизации.

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


Более общая задача состоит в исследовании возможностей создания асимметричных алгоритмов на основе новых принципов.


Задачи на основе укладки рюкзака и теории конечных автоматов не привели к созданию стойких схем.


Интерес продолжают вызывать система МакЭлиса (1978 год) и система Нидеррайтера на основе кодов коррекции ошибок (серьёзных методов взлома продемонстрировано не было (известны атаки Штерна, Сидельникова, Canteaut-Sendrier-Chabaud), и эти системы являются одними из основных кандидатов на алгоритмы, устойчивые к квантовому криптоанализу), однако практически не применяются из-за большой длины ключа (несколько сотен тысяч бит).


Недавние исследования, изложенные в работе Daniel J. Bernstein, Tanja Lange Christiane Peters Attacking and defending the McEliece cryptosystem привели к созданию улучшенного метода атаки на систему МакЭлиса и Нидеррайтера.


Используя компьютер с процессором Core 2 Quad 6600 на проведение атаки на систему МакЭлиса с предполагавшимися ранее параметрами безопасности потребовалось бы 1400 дней (или 258 процессорных циклов). Используя кластер из двухсот компьютеров стоимостью $200000 можно уменьшить время вскрытия до одной недели. При этом коммуникации между узлами кластера практически не требуется.


Данный пример отражает прогресс в области вычислительных технологий – аналогичная атака, проводимая в 1998 году на процессорах 433MHz DEC Alpha потребовала бы 7400000 дней (268 процессорных циклов).


Уменьшение времени атаки с 7400000 до 1400 дней за десять лет выглядит впечатляюще.
Дешёвые процессоры Core 2 Quad работают в 5.54 раз быстрее по тактовой частоте, чем процессор Alpha 21164, имеют 4 параллельных ядра вместо одного и способны выполнять три арифметические инструкции за один цикл (в отличие от двух).


Однако только за счёт роста вычислительных мощностей время проведения атаки уменьшилось бы с 7400000 до 220000 дней. Остальной прирост получен за счёт алгоритмических оптимизаций. Исследователи предложили модификацию систем МакЭлиса и Нидеррайтера для противостояния данным атакам без существенного увеличения размеров ключей.


Система Ajtai-Dwork (AD) – (1997 год) – первая, основанная на использовании таких математических объектов как решётки. Она непрактична из-за медленного побитового шифрования, значительного увеличения шифртекста по сравнению с открытым текстом и больших размеров ключей. Другие схемы на основе решёток (Goldreich-Goldwasser-Halevi – GGH97) также не получили распространения. Они также считаются трудными для квантового криптоанализа, однако методы обычного криптоанализа против них более эффективны.


NTRU (1998) – система асимметричного шифрования, основанная на операциях с полиномами в кольце целых чисел, однако методы её анализа также сводятся к проблеме решёток. Она считается практичной и быстрой по отношению к RSA. Как и для практически всех остальных алгоритмов, предполагается, что она квантовостойкая в том плане, что квантовый компьютер способен лишь ускорить криптоанализ классическими методами.


Boaz Barak и Avi Wigderson в работе Public Key Cryptography from Different Assumptions недавно предложили подход, основанный на использовании псевдослучайных генераторов и теории графов, однако о практическом построения алгоритма говорить пока рано.


Интересно, что первый асимметричный алгоритм, появившийся незадолго до DH (и вдохновивший Диффи и Хэллмана) – "головоломки Меркла", был основан на симметричных алгоритмах (хэш-функциях), но был непрактичен. Идея использовать симметричные алгоритмы в создании асимметричных интересна, так как позволяет быстро переделать алгоритм, не быть привязанным к конкретной вычислительно-трудной задаче и избежать взлома на основе квантовых компьютеров.


Другой известный "симметрично-асимметричный" алгоритм Лампорта использует хэширование для создания одноразовых подписей. Используя так называемые "деревья Меркла" такие подписи можно сделать многоразовыми (хотя поддерживать такую структуру между многими пользователями нелегко), а используя цепочки подписей можно осуществлять потоковые микроплатежи в системах электронных денег. Низкие затраты на вычисления позволяют пользователю с помощью потоковой подписи оплачивать платную он-лайн услугу в режиме реального времени – "по центу за байт", что может в некоторых случаях исключать мошенничество сторон – как только предоставление контента прекращается, пользователь прекращает переводить денежный поток (который может составлять доли центов в секунду) и наоборот – как только пользователь прекращает оплату, он отключается от сервиса.


К сожаление этот метод нельзя использовать для асимметричного шифрования.


Chris J. Mitchel в 2003 году в работе file"Public key encryptions using block ciphers" предложил усовершенствовать идею головоломок Меркла. Для построения асимметричного алгоритма используются любые блочные шифры. К сожалению, для обеспечения 64-битного уровня безопасности (аналогичного симметричным шифрам, что явно недостаточно), требуется закрытый ключ размером 30 гигабайт и открытый размером 60 гигабайт, увеличение стойкости схемы делает её еще более непрактичной.


Попытки создания асимметричных алгоритмов на основе блочных шифров с секретными параметрами S-блоков (Patarin's 2-Round Public Key System with S-boxes) не увенчались созданием стойких схем.


Нахождение решения системы уравнений квадратичных многочленов (MQ) в конечном поле было предложено в качестве кандидата на асимметричный алгоритм в середине 80-хх годов. Многие схемы на основе MQ-систем были взломаны, однако их разработка продолжалась и их считают превосходящими по своим параметрам системы на эллиптических кривых.


Тем интереснее выглядит работа Public Key Block Cipher Based on Multivariate Quadratic Quasigroups Danilo Gligoroski and Smile Markovski and Svein J. Knapskog, в которой авторы соединяют теорию многовариантых квадратичных многочленов и использование квазигруп. Им уже удалось относительно успешно продемонстрировать потоковый шифр Edon 80 на конкурсе eStream, где он хотя и не стал победителем, но был отмечен за перспективный дизайн на основе квазигрупп.


Теория квазигрупп изучается уже давно (в середине 50-х годов XX века одним из ведущих мировых учёных, занимавшихся этой проблемой, был советский математик Белоусов).


Квазигруппы считаются перспективным, хотя и трудным в реализации направлением в криптографии, так как обладают неупорядоченной структурой по сравнению с обычными алгебраически высокоструктурированными объектами, что затрудняет использование против них многих видов криптоанализа, в частности алгебраического. Частично, теория квазигрупп использовалась в создании алгоритма IDEA.


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


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


  1. Алгоритм является детерминистским (не требует ввода случайных параметров) и является однозначным отображением.
  2. Алгоритм не увеличивает размер сообщения после шифрования
  3. Алгоритм имеет один параметр n=(140,160,180,200) – длина шифрованного блока в битах.
  4. Предполагаемый уровень стойкости алгоритма 2(n/2)
  5. Скорость шифрования сопоставима с алгоритмами на многовариантных квадратичных многочленах.
  6. Скорость расшифрования и подписи сопоставима со скоростью работы обычных блочных шифров (в 500-1000 раз быстрее традиционных асимметричных алгоритмов).
  7. Алгоритм подходит для создания коротких подписей.

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


Алгоритм протестирован как на быстрых процессорах (скорость работы 160-битной C-реализации на Intel Core 2 Duo составляет 11000 циклов за такт на одном ядре и 6000 циклов на двух ядрах, что говорит о хорошем распараллеливании), так и на медленных программируемых микросхемах FPGA (Xilinx Virtex-5: 249.4 Mhz – скорость расшифрования 399 Mbps, зашифрование при частоте 276.7 Mhz – скорость зашифрования 44.27 Gbps)


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


И хотя стойкость алгоритма может вызывать сомнения (неудачные случаи использования квазигрупп в криптографии тоже встречались), на всякий случай стоит запомнить название новой, необычной криптосистемы – Multivariate Quadratic Quasigroups (MQQ).


Источник: Cryptology ePrint Archive


 
— Гость (06/08/2008 01:23)   <#>
Забавно :)
Правда, к отходу от стандартных "высокоупорядоченных" структур отношусь со скептицизмом, оно мне напоминает "безопасность через неясность". Мне приходилось решать задачу, например, которая официально не сводилась к спектральной, и в этом была вся её сложность, однако спустя некоторое время удалось показать, что широкий класс подобных задач к некоторым спектральным всё же сводится (а про спектр мы знаем почти всё). В этом смысле как ни крути, а те же свойства и структуры всё равно вылезут, рано или поздно... О степени прогресса в теории квазигрупп не осведомлён.
— unknown (06/08/2008 09:01, исправлен 06/08/2008 09:48)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Нечто похожее предполагали про шифры с псевдослучайно сгенерированными, но большими S-блоками вместо специально сконструированных (алгоритмы Twofish, Blowfish) – дескать тоже безопасность через неясность. Но это не совсем верное употребление термина "неясность" – алгоритм генерации открыт и вполне ясен.

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

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

Мне приходилось решать задачу, например, которая официально не сводилась к спектральной, и в этом была вся её сложность, однако спустя некоторое время удалось показать, что широкий класс подобных задач к некоторым спектральным всё же сводится (а про спектр мы знаем почти всё).

Совершенно верное замечание, в квазигруппах есть похожая проблема. Есть набор не до конца определённых критериев, по которым их нужно подбирать, но до сих пор неясно почему некоторые из них дают псевдослучайные последовательности, а некоторые – абсолютно периодические и предсказуемые.

В шифре Edon-80 были использованы квазигруппы 4-порядка. Всего их может быть 576. Из них 384 были отобраны как подходящие, а 64 как особо подходящие для потокового шифра. Другие исследователи изучили их алгебраические свойства. На первый взгляд у них не было никаких "упорядочивающих" алгебраических свойств – все не являлись группами, семигруппами, были некоммутативны. Но путём полного перебора выяснилось, что все 64 квазигруппы являются изотопами квазигруппы модулярного вычитания с правым нулём, а это позволяет перекинуть мостик к обычным алгебраическим объектам и возможно свести на нет все их преимущества. Дополнительные свойства, открытые у этих квазигрупп доказали, что они являются изотопами группы (Z n, +). Так что из всех "алгебраически неупорядоченных" объектов самыми подходящими были отобраны как раз сводимые к самым упорядоченным.

Это пример самого примитивного случая, когда можно просто перебрать все 64 варианта таблиц размером 4x4. А если кто-то поковыряет, что придумали в квазигруппах большего порядка авторы MQQ (который пока никем ещё не проанализирован) на этот раз, то может и ещё найдут массу чего интересного.

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

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

Работа вызывает интерес в том плане, что очень много теоретических наработок в этом направлении всё-таки есть, авторы признаны своими работами и им удалось построить практически реализуемый алгоритм. Даже если его взломают (может даже наверняка), направление может оказаться перспективным, будут созданы другие алгоритмы на похожих принципах.
— Гость (08/08/2008 01:57)   <#>
Познавательно :)
— unknown (12/08/2008 09:38)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
s/семигруппами/полугруппами//g

(калька со слова semigroup) :-)
— unknown (28/10/2008 10:11, исправлен 28/10/2008 10:12)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Авторы Mohamed Saied Emam Mohamed, Jintai Ding, Johannes Buchmann взломали MQQ.

Ими был осуществлён практический взлом на обычном компьютере MQQ-системы с размером ключа 160 бит. А поскольку этот шифр приравнивался по скорости к симметричному, то и ключи в этой системе предлагались 128, 160, 192, 256 бит.

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

Это произошло потому, что удалось применить новый метод алгебраического криптоанализа – MutantXL, использующий (только не пугайтесь ;) "мутирующие полиномы" или "многочлены-мутанты", с помощью чего можно легко упростить и решить систему уравнений, описывающую криптопреобразование.

Авторы не рассматривали симметричные алгоритмы на квазигруппах, и другие альтернативные асимметричные тоже на квазигруппах (которые по скорости и ресурсоёмкости близки к RSA), но данный конкретный алгоритм (MQQ) похоже можно закрывать.

В этом смысле как ни крути, а те же свойства и структуры всё равно вылезут, рано или поздно...

Провидец ;-)
— Гость (28/10/2008 11:06)   <#>
Провидец ;-)

Гыыы) Оракул примает заказы))

Мне слова MQQ мало о чём говорят, это же не промышленный криптоалгоритм, не серпент, не райндел, не фиш и т.п. Возможно, MQQ был "слишком модельным" потому и сломали.
— unknown (28/10/2008 12:05, исправлен 28/10/2008 12:19)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Никаких технических подробностей нет, но судя по громкому заголовку
"Researchers crack Internet security of the future", размещённому на сайте Technische Universiteit Eindhoven – TU/e взломана криптосистема МакЭлиса!

Или это продолжение работы Бернштейна-Петерса-Ланге, или это новый результат, раз о нём сообщено гораздо позднее. Можно только предполагать, что они научились за две недели ломать ключи любой практически приемлимой длины.

А криптосистема МакЭлиса была основным кандидатом на постквантовое крипто – почти единственная проверенная временем, хотя намного менее удобная чем RSA в практическом исполнении, но зато стойкая к квантовому криптоанализу.
— Гость (28/10/2008 12:39)   <#>
Ещё обиднее будет если все не подумав перейдут на какой-нибудь новомодный квантовостойкий ассиметричный алгоритм типа wwwNTRU, а он окажется нестойким против неквантовых методов анализа.

© unknown
— Гость (28/10/2008 12:40)   <#>
Провидец ;-)
— unknown (28/10/2008 14:26)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
От провидца слышу.

Всё-таки NTRU – это не МакЭлис, МакЭлис основан на кодирующих преобразованиях, ну да ладно ;)
— SATtva (28/10/2008 14:31)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4110
Всё-таки NTRU – это не МакЭлис

Будем надеяться, он окажется более TRU, чем МакЭлис. ;-)
— Гость (28/10/2008 15:35)   <#>
Чё надеяться – ломать надо! ... пока руки чешутся :)
— unknown (18/10/2010 16:20)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Авторы MQQ-SIG отдали его в свободное использование (по крайней мере royalty free) с полным описанием для всех желающих:
http://arxiv.org/abs/1010.3163

Там же обещается более полная работа с обзором публикаций по уязвимостям (может они там чего-то пофиксили)?
— Гость (22/11/2011 00:45)   <#>
практически не применяются из-за большой длины ключа (несколько сотен тысяч бит)
Несколько сот килобит – меньше мегабита, это много? Всё равно ведь ключи хранятся на машинных носителях и обрабатываются программно.
— unknown (22/11/2011 09:48, исправлен 22/11/2011 10:21)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Крупные SSL-серверы будут обрабатывать тысячи соединений, базы хранения пользовательских ключей будут хранить ключи сотен тысяч пользователей и т.д.


Даже такой гигант информации как Google долго не вводил обычное SSL-шифрование (а затем сначала использовал неполное — только для логина) вовсе не по полититическим соображениям, а из-за накладных расходов.


Вот несколько устаревшая цитата (сейчас Google ввёл почти полный SSL), но она отражает долговременную тенденцию:


Inefficient cryptography is an option for some users but is not an option for a busy Internet server handling tens of thousands of clients each second. If you make a secure web connection today to https://www.google.com, Google redirects your browser to http://www.google.com, deliberately turning off cryptographic protection. Google does have some cryptographically protected web pages but apparently cannot afford to protect its most heavily used web pages. If Google already has trouble with the slowness of today's cryptographic software, surely it will not have less trouble with the slowness of post-quantum cryptographic software. Constraints on space and time have always posed critical research challenges to cryptographers and will continue to pose critical research challenges to post-quantum cryptographers. On the bright side, research in cryptography has produced many impressive speedups, and one can reasonably hope that increased research efforts in post-quantum cryptography will continue to produce impressive speedups. There has already been progress in several directions; for details, read the rest of this book!

© D.J.Bernstein "Post-Quantum Cryptography"


Кратко, для тех, кому "много нерусских букв": неэффективная криптография может подойти отдельным пользователям, но не серверам, обрабатывающим тысячи соединений в секунду. Если Google с трудом освоил внедрение "простой" быстрой криптографии, то кто будет возиться с широким развёртыванием медленных и расходующих память систем постквантовой криптографии.

Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3