id: Гость   вход   регистрация
текущее время 10:34 29/03/2024
Автор темы: SATtva, тема открыта 21/10/2003 05:29 Печать
https://www.pgpru.com/Форум/Криптография/СравнительныйОбзорАлгоритмовPGP
создать
просмотр
ссылки

Сравнительный обзор алгоритмов PGP


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


 
На страницу: 1, 2, 3 След.
Комментарии
— Гость (22/12/2003 04:38)   <#>
Стоит ли это понимать, как конец PGP?

http://www.compulenta.ru/2003/1/28/37101/
Израильские ученые придумали чип для взлома 1024-битного шифра RSA
28 января 2003 года, 12:11
Ученые, работающие в отделе информатики и прикладной математики Вайсмановского научного института (Израиль) разработали проект вычислительного устройства, способного с высокой скоростью раскладывать большие числа на простые множители. Как известно, именно принцип вычислительной трудности факторизации (разложения на множители) больших чисел положен в основу многих современных криптографических алгоритмов.
До сих пор наиболее эффективным алгоритмом факторизации считался алгоритм NFS (number field sieve – сито числового поля). С его помощью в 1999 году был взломан алгоритм RSA c ключом длиной 512 бит. Процесс взлома занял много месяцев и потребовал огромных вычислительных ресурсов. Стойкости 1024-разрядного шифра RSA, по мнению большинства экспертов достаточно для надежной защиты информации в течение ближайших 15-20 лет.
Однако Ади Шамир (один из соавторов алгоритма RSA) и Эран Тромер полагают, что это не так. Двое исследователей разработали новое вычислительное устройство, способное факторизовать числа в несколько раз быстрее всех предыдущих разработок такого рода. В результате, взлом стойких шифров значительно облегчается.
До последнего времени наиболее совершенным устройством для быстрого разложения чисел на множители была оптоэлектронная система TWINKLE. Она состояла из подложки, разбитой на множество вычислительных ячеек, каждая из которых работала с собственной числовой последовательностью. TWINKLE последовательно перебирает различные области числового сита в соответствии с сигналами от тактового генератора. Поскольку в TWINKLE применяются оптические компоненты, полупроводниковой основой устройства служит дорогой арсенид галлия.
Устройство TWIRL, разработанное Шамиром и Тромером, использует близкий к TWINKLE подход к реализации алгоритма разложения чисел на множители. Однако новое устройство может параллельно рассматривать тысячи участков числового сита, а схема устройства не содержит оптических элементов. По сути, TWIRL представляет собой специализированную сверхбольшую интегральную схему (СБИС), работающую на частоте 1 ГГц, выполненную по 0,13-микронной технологии.
Пока исследователи разработали лишь схему TWIRL и не реализовали ее на практике, хотя предварительная оценка показывает, что с помощью TWIRL взлом шифров с ключами длиннее 512 бит становится возможным. Например, для вскрытия 1024-битного шифра понадобится специальный компьютер на основе TWIRL стоимостью около 10 млн. долл. США. Для взлома шифра такой машине понадобится около года. 512-битный шифр RSA TWIRL-компьютер стоимостью в 10000 долларов США вскроет менее чем за десять минут.
По итогам своих исследований израильские ученые готовятся опубликовать статью. С ее предварительным вариантом в формате PDF можно ознакомиться здесь (размер файла 324 кб). filehttp://psifertex.com/download/twirl.pdf
— SATtva (22/12/2003 12:20)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
B, нет, так считать не стоит.

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

Более того, PGP кроме RSA поддерживает алгоритм шифрования Эльгамаля (названный в PGP Diffie-Hellman'ом, что формально неверно) и алгоритм подписания DSA, оба основанные на математической проблеме вычисления дискретного логарифма в конечном поле. Несмотря на то, что проблемы факторизации и дискретного логарифмирования во многом близки, решение последней является более ресурсоёмкой задачей и пока недоступно с той же эффективностью, что разложение на множители.

В FAQ ( http://www.pgpru.com/faq ) в разделе Криптография я приводил некоторые доводы "за" и "против" ключей RSA и DH/DSS в PGP.

Кроме того, не исключено, что будущие версии PGP привнесут поддержку алгоритмов, основанных на эллиптических кривых (место под такой алгоритм, например, зарезервировано в самом стандарте OpenPGP) — этот подход хотя и является относительно молодым и не обладает той же научной базой, что Эльгамаль и RSA, видится весьма многообещающим: во-первых, он многократно быстрее последних, во-вторых, требует очень компактных ключей для обеспечения эквивалентной RSA и Эльгамалю стойкости.
— Вий (02/02/2005 11:54)   профиль/связь   <#>
комментариев: 510   документов: 110   редакций: 75

Например, для вскрытия 1024-битного шифра понадобится специальный компьютер на основе TWIRL стоимостью около 10 млн. долл. США. Для взлома шифра такой машине понадобится около года. 512-битный шифр RSA TWIRL-компьютер стоимостью в 10000 долларов США вскроет менее чем за десять минут.



последние алгоритмы факторизации уже субэкспоненциальны


Если последние алгоритмы факторизации уже субэкспоненциальны, то почему почему такая разница – около года и 10 минут на взлом ключей 1024 и соответственно 512 бит?
— SATtva (02/02/2005 13:29)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Потому что субэкспоненциальны, но не линейны. Соотношение между 2^512 и 2^1024 — не 1:2, а 1:2^512.
— Вий (03/02/2005 07:37)   профиль/связь   <#>
комментариев: 510   документов: 110   редакций: 75
Да в общем понятно, что каждый бит увеличивает пространство ключей вдвое. Вопрос несколько иной был. Да ладно, черт с ним, с вопросом.
— unknown (03/02/2005 08:41)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
В FAQ ( http://www.pgpru.com/faq ) в разделе Криптография я приводил некоторые доводы "за" и "против" ключей RSA и DH/DSS в PGP.

Еще один недостаток DSS – ему нужно для каждой подписи генерировать уникальное случайное сеансовое число. И под одним и тем же документом подпись будет каждый раз разная.

Если это число можно как-то предугадать, то и секретный ключ можно будет раскрыть. А еще с помощью выбора этого числа можно создавать "потайные каналы". Поэтому DSS многим поначалу не нравился по сравнению с более простым и прозрачным RSA (для подписи).
— SATtva (03/02/2005 12:17)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Да, и возможность скрытого канала в DSS стала серьёзным вопросом, применительно к PGP 7.x, исходный код которых никогда не был опубликован. При том, что неоднократно возникали подозрения в связах NAI и АНБ, многие пользователи отказались переходить на седьмую версию именно по этой причине.
— unknown (03/02/2005 13:52)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Может про особенности DSS/DSA добавить инфу в FAQ?
Хотя бы как примечание мелким шрифтом.
— SATtva (03/02/2005 14:15)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Что-то мне казалось, я там об этом писал... :roll: Добавлю, конечно.
— Гость (18/03/2005 01:19)   <#>
Почти взломан RSA – А прочие алгоритмы? Теоретически можно подобрать под любой из них систему, м-да-а-а...
URL: http://lenta.ru/news/2005/03/16/quantum/
В Австрии осуществили "необратимые" квантовые вычисления
"Необратимые" квантовые вычисления удалось впервые осуществить австрийским ученым. Антон Цайлингер (Anton Zeilinger) и его сотрудники из венского Института экспериментальной физики использовали для этого так называемые "запутанные состояния" фотонов. Результаты эксперимента, опубликованные в журнале Nature, неизбежно повлияют на современные представления о практической разрешимости ряда важных проблем теории чисел и криптографии.
Квантовые компьютеры основаны на качественно иной логике, чем современные классические. Принципы действия последних описываются булевой алгеброй, и любому состоянию вычислительной машины отвечает некоторая последовательность битов. Единицей квантовой информации является q-бит – состояние двухуровневой квантовой системы. В вычислениях существенно используются квантовые явления – суперпозиция и "запутывание" (entanglement) состояний, так что N q-битам отвечает 2N-мерное пространство, базисные векторы которого – последовательности "q-нулей" и "q-единиц".
Если "измерить" состояние квантовой системы "до" и "после", мы получим результат вычисления, которое в математической модели описывает соответствующий физический процесс. Это соображение встречается в работах Фейнмана, а в 1980 году советский алгебраист Манин сформулировал на его основе концепцию квантовых вычислений. Постановка вопроса была непривычной для математиков: требовалось "приспособить" задачу к некоторой системе, могущей ее решить.
Задач, для которых уже придуманы квантовые алгоритмы, сравнительно немного. Среди них, однако – проблема разложения на простые множители, исключительно важная для теории чисел и криптоанализа. Многие алгоритмы шифрования, криптостойкость которых с точки зрения классических вычислений не вызывает сомнений, взламываются посредством квантового компьютера.
Попытки воплотить q-бит в конкретных физических системах предпринимались с 1980-х годов. Эффективных квантовых компьютеров на основе сверхпроводимости или ядерного магнитного резонанса так и не удалось построить

А вот "реальная" машина?
URL: http://lenta.ru/internet/2001/05/18/quantumlight/
Американские ученые из университета Рочестера (University of Rochester) создали квантово-световой компьютер, который считает в миллиарды раз быстрее современных суперкомпьютеров, сообщает CNN. Появление этого устройства может сделать ненужными суперкомпьютеры.
Вместо традиционных электронных технологий в новом устройстве используются лучи света. Для такой машины элементарными задачами становится, например, взламывание шифров путем перебора комбинаций или поиск в больших базах данных.
Разработчики, представлявшие машину на конференции в Балтиморе, штат Мэриленд, привели такой пример: если обычный суперкомпьютер, выполняющий поисковую задачу – это библиотекарь, который идет к полкам с множеством книг искать среди них одну нужную, то квантово-световой компьютер – это устройство, которое клонирует библиотекаря в большом количестве, и на поиски одновременно отправляется уже целая бригада.
Проект по созданию машины финансировался американским министерством обороны.
— unknown (18/03/2005 09:01)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Сообщения о создании квантового суперкомпьютера появляются в прессе чуть ли не каждый месяц, в течении десятков лет, как сообщения о создании лекарств от рака или СПИДа. Каждый раз говорят, что СПИД (Рак, синдром Альцгеймера) почти окончательно побежден. Со временем выясняется, что в лабораторных условиях удалось замедлить рост каких-то клеток и особенного практического значения это не имеет.

А термоядерный синтез? Уже в 60-е годы вот-вот должны были сделать. Почему же человечество до сих пор сжигает нефть и уран вместо тяжелой воды?

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

Не стоит буквально воспринимать журналистские публикации. Желательно по-возможности читать первоисточники и научные доклады (если есть возможность самому разобратья в этой теме).
— Souran (01/08/2005 00:12)   профиль/связь   <#>
комментариев: 14   документов: 1   редакций: 0
Заранее извиняюсь за дилетантский вопрос. Но при наличии гипотетического квантового компьютера, существуют ли математические методы защиты информации, способные противостоять производительности квантовых криптоанализаторов?
— Вий (01/08/2005 06:35)   профиль/связь   <#>
комментариев: 510   документов: 110   редакций: 75
Добрый день! :)

Вот данные из книги Б. Шнайера.

Сложность вычисления порядком величины: Если сложность обработки для данного алгоритма составляет 2^128, то 2^128 операций требуется для вскрытия алгоритма (эти операции могут быть сложными и длительными). Так, если предполагается, что ваши вычислительные мощности способны выполнять миллион операций в секунду, и вы используете для решения задачи миллион параллельных процессоров, получение ключа займет у вас 10^19 лет, что в миллиард раз превышает время cуществования вселенной.

Теперь можно посчитать:
Пусть гипотетический квантовый компьютер будет работать в миллиард раз быстрее (хотя какова будет его скорость мне неизвестно, я просто предположил ткнув пальцем в небо) чем система из миллиона процессоров, о которой говориться в книге, каждый из которых проверяет миллион ключей/операций в секунду. Тогда для нахождения ключа грубой силой квантовому компьютеру потребуется не много не мало – время существования вселенной. При этом мы рассматриваем алгоритм с длиной ключа "всего лишь" 128 бит. А если мы возмем ключ с длиной 256 бит?

Вот еще несколько больших чисел из книги Шнайера:
Возраст планеты 2^30 лет
Время до следующего оледенения 2^14 лет
Возраст вселенной 2^34 лет
Число атомов планеты 2^170
Число атомов вселенной 2^265
Объем вселенной 2^280 см.куб.
— Вий (01/08/2005 16:28)   профиль/связь   <#>
комментариев: 510   документов: 110   редакций: 75
Еще есть сравнительные оценки построенные не на временных факторах, а на энергетических, кстати где то в этом форуме об этом уже писали. Смысл таков – если представить, что на одну операцию по проверке ключа уходит минимальная в физике единица энергии (по моему переход электрона с одной орбиты атома на другую, как раз что то из области квантовых вичислений) то для проверки всех ключей пространства 2^128 нужно будет истратить энергии столько, сколько хватит для растопления всех льдов Антарктиды. Представите, что это да компьютер должен быть и какой у этого компьютера должен быть источник питания? Роль высокопроизводительных квантовых или каких-либо других суперкомпьютеров по моему мнению важна не для прямого взлома грубой силой, а для работ криптоанализа, именно поэтому огромная роль в криптографии отводится стойкости криптосистем.
— SATtva (01/08/2005 18:02)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Souran, почитайте статьи "Пределы роста" и [[http://www.pgpru.com/articles/crypto/keysize.shtml "Длина ключа и его
полный перебор"]]. Там приведены некоторые методики атак, их ресурсозатраты и практическая осуществимость, исходя из длин ключей и других факторов, упомянутых Вием: энергетических, тепловых. Вообще пробегитесь по разделу Литературы. Думаю, найдёте немало полезного.
На страницу: 1, 2, 3 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3