id: Гость   вход   регистрация
текущее время 17:21 14/05/2021
Владелец: unknown (создано 08/02/2013 12:08), редакция от 10/02/2013 19:47 (автор: unknown) Печать
Категории: криптография, алгоритмы, шифрование с открытым ключом, распределение ключей
https://www.pgpru.com/Новости/2013/ВыполнениеПротоколаДиффи-ХеллманаВоВложенныхАлгебраическихСтруктурах
создать
просмотр
редакции
ссылки

08.02 // Выполнение протокола Диффи-Хеллмана во вложенных алгебраических структурах


Протокол Диффи-Хеллмана является истоком криптографии с открытым ключом и до сих пор применяется достаточно широко. Исходный простейший его вариант использует в качестве основы мультипликативную группу целых чисел Z*p по модулю простого числа p. Также есть открытый элемент g Z*p, который является примитивным корнем по модулю p.


Сам классический протокол выглядит так:


  1. Алиса выбирает целое число a, вычисляет A = ga mod p и публикует A.
  2. Боб выбирает целое число b, вычисляет B = gb mod p и публикует B.
  3. Алиса вычисляет KA = Ba mod p.
  4. Боб вычисляет KB = Ab mod p.

В итоге у Алисы и Боба получается совместно выведенный ключ K = KA = KB = gba mod p = gab mod p.


Безопасность протокола зависит от правильного выбора параметров, в т.ч. g. Для взлома протокола пассивный атакующий (Ева) должна вычислить gab на основании знания g и перехваченных параметров обмена ga и gb, что, как общепринято считать, сводится к труднорешаемой задаче поиска дискретного логарифма: нахождения a из g и ga. Однако, строгого доказательства эквивалентности решения проблемы Диффи-Хеллмана к поиску дискретных логарифмов до настоящего времени не существует. Также как и не существует строгого доказательства отсутствия простых методов решения таких задач.


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


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


Очередное оригинальное исследование по нестандартному выполнению DH-протокола представили Delaram KahrobaeI, Charalambos Koupparis и Vladimir Shpilrain (CUNY Graduate Center and City Tech, The City College of New York, City University of New York).


Они использовали алгебраические группы над кольцами, получая т.н. групповое кольцо, над котором впоследствии развернули матрицы. Полученная вложенная структура вида Mk (Zn [Sm ]) обладает очевидным интересным свойством: при небольших размерах составляющих элементов m, n, k, размер самой структуры получается достаточно большим. Что с одной стороны позволяет эффективно проводить вычисления, сохраняя небольшой размер ключа, а сдругой стороны обеспечить безопасность за счёт большой величины составного алгебраического объекта.


Так, один из вариантов протокола выглядит следующим образом:


  1. Алиса выбирает открытую матрицу MMk (Zn [Sm ]) и большое положительное число a, вычисляет Ma и публикует M, Ma.
  2. Боб выбирает другое большое положительное число b и публикует Mb.
  3. Обе стороны вычисляют совместный ключ K = (Ma) b = (Mb) a

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


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


Источник: ArXiV.org: Cryptography and Security, Group Theory.
См. также: Асимметричные алгоритмы на основе тропической алгебры.


 
На страницу: 1, 2 След.
Комментарии [скрыть комментарии/форму]
— spinore (10/02/2013 08:14)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786

Есть ли простой способ объяснить, почему она труднорешаемая? Ведь многие похожие задачи решаются очень легко в теории чисел.


Сама статья, стр. 14:

6.3. Quantum Algorithm Attacks. It is well known that many cryptographic protocols are vulnerable to quantum algorithm attacks [9]. In particular, the Diffie-Hellman protocol can be attacked using Shor's algorithm. This algorithm basically recasts the discrete logarithm problem as a hidden subgroup problem (HSP) and uses the quantum algorithms developed for HSP to recover the exponent.

We believe that our protocal is secure against such attacks. The HSP relies on the existence of a function f : G → S, for some set S, such that f is constanct on cosets of the unknown

А я в домового верю, и что теперь? И дальше пошло обсуждение несводимости к HSP. Ну, дак пусть честно и озвучат, что их метод DH безопасен против стандартного алгоритма Шора. Доказательство безопасности против любого квантового алгоритма я у них не увидел. В заключении, стр. 15, всё ещё короче:

neither "standard" attacks ... nor quantum algorithm attacks work with our platform, as we showed in Section 6.

Ну, вы поняли.

Вообще-то, доказательство отсутствия эффективного квантового алгоритма для решения произвольной задачи — hard problem. Кажется, есть всего несколько задач, про которые известно, что они могут быть решены быстрее квантовыми алгоритмами, и всего несколько задач, про которые известно, что они не могут быть решены быстрее даже с помощью них. Есть стойкое подозрение, что если такую заяву отошлют на реферирование тем, кто занимается quantum complexity theory, они её раскритикуют в пух и прах.

Наконец, статья только в архиве. Пока в журнал не приняли, говорить о чём-либо рано.
— unknown (10/02/2013 19:28)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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

метод DH безопасен против стандартного алгоритма Шора. Доказательство безопасности против любого квантового алгоритма я у них не увидел.

Так и хорошо, возможно авторы честно написали про отсутствии строгого доказательства. Но я не знаю тонкостей, может эта проблема как-то вообще тривиально обосновывается: вот есть к примеру асимметричная криптография на решётках и там само собой подразумевается "раз решётки — значит квантовостойкое". Может это где-то уже фундаментально доказали один раз и каждый раз на это ссылаться не нужно. Здесь авторы указывают, что квантовостойкости способствует неинвертируемость матриц. Может это тоже какой-то общеизвестный факт. И насколько я могу судить в меру своего понимания, всё, что кроме Шора, считается бесперспективным пока. Вроде, к примеру, было доказано показано отсутствие возможностей прицельного симметричного криптоанализа на каких-то принципиально новых квантовых алгоритмах, кроме как упрощения перебора. Не зная особенностей тенденций постквантовой криптографии, трудно придираться к корректности формулировок.

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

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

Чего бы я реально опасался, так это вот такого. Но тем не менее, все такие исследования стоит держать во внимании. От них м.б. неожиданный косвенный полезный эффект — даже в симметричной криптографии или криптоанализе. Или хотя бы полезно знать, что такое уже когда-то предлагали.
— spinore (11/02/2013 10:51)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
Вообще, квантовая теория сложности — не такая простая вещь, как некоторым кажется. По ссылке в вики есть обзорная статья на тему для желающих понять масштабы. Судя по поврехностному гуглению, класс задач, не решаемых быстро даже на КК — QMA. Про него Ааронсон писал:

Notably, Adam Bookatz filecompiled the first list of essentially all known QMA-complete problems, analogous to (but shorter than!) Garey and Johnson’s listing of known NP-complete problems in 1979.

Кому скучно, листайте на стр. 16 данной Ааронсоном ссылки, там есть сводная картинка.


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

Более того, авторы ссылаются только на один-единственный первоисточник — оригинальную работу Шора 94-го года. Что, с 1994-го тема заглохла? Шор сделал настолько всё, что после него ничего нового за 19 лет не было опубликовано? Даже не смешно. Более того, претензия обоснована в любом случае: у них нигде в их рассуждениях не говорится о безопасности против любого квантового алгоритма, а анализируется только Шор, в заключении же делается самое общее заявление, что делает его де юре ложью (не знаю уж, как de facto).

Кстати, количество и релевантность ссылок — один из простых методов оценки качества работы. Хотя бывают и исключения, но общий смысл следующий: если вы знакомы с литературой и трудами в области, у вас необходимо естественным образом вылезет большой список, на который нужно сослаться, даже если не хочется; когда же работу публикуют некомпетентные авторы, т.е. незнакомые с литературой, всё ограничивается ссылками на книги или на популярные обзоры. Иногда из этих книг или обзоров они выцепляют ссылки на работы-первоисточники и цитируют их, как в данном случае.


Говоря сухим языком, для этих задач доказано, что они принадлежат классу сложности BQP. У авторов же нет даже озвучивания, к какому классу сложности их задача принадлежит.
— unknown (11/02/2013 12:14, исправлен 11/02/2013 12:24)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Более того, авторы ссылаются только на один-единственный первоисточник — оригинальную работу Шора 94-го года

Это во всех работах так, если я не путаю, даже со спец. конференции PostQuantum Crypto. Упоминают только стойкость против Шора (вроде бывают какие-то мелкие исключения). Но вот, чтобы подробно разбиралась квантовая стойкость, так как вы говорите — не встречал даже в специфических работах и обзорах по постквантовой криптографии. Может за этим есть какая-то проработанная теория, которую интересующиеся типа должны знать и которую даже в источниках не указывают, мне об этом неизвестно.


Строгого доказательства принадлежности алгоритмов к квантовым классам сложности в таких работах не встречал.

— spinore (11/02/2013 13:32)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786

Для меня это звучит открытием, если честно. Если бы они доказывали принадлежность чего-то там к BQP, это ещё можно было бы понять как «ну, полнимальная сводимость к задаче факторизации (или чему там) полуочевидна ⇒ сложность нахождения решения не более, чем BQP». А вот как доказать отрицание? Из того, что их задача более не решается лобовым Шором, разве следует её принадлежность к другому классу сложности? Есть же тривиальный контрпример: ряд постквантовых алгоритмов оказался нестоек к классическому криптоанализу, т.е. был найден эффективный алгоритм, решающий эти задачи за полиномиальное время. Насколько я помню, квантовая модель вычислений включает себя и классическую, т.е. всё, что может быть решено полиномиально быстро классическими алгоритмами, может быть решено полиномиально быстро и квантовыми1. Грубо говоря, можно себе представлять, что КК может номинально работать, как классический компьютер, производящий классические операции над битами2. Т.о., почти по определению, некоторое постквантовое крипто оказалось уязвимым в т.ч. и к КК. И как же тут обойтись одним Шором?

Боюсь наговорить лишнего, но, имхо, создание постквантовой классической криптографии — не уровень компетенции классических криптографов, и не стоит им туда лезть. Я скорее поверю, что кто-то из квантовых информатиков разберётся в классическом крипто и что-то предложит квантово-стойкое, чем то, что кто-то из классических криптографов вдруг разберётся с квантовыми вычислениями. В любом случае, если речь идёт о безусловной безопасности (information-theoretical security), все уловки классической криптографии (то, в основном ради чего она существует и разрабатывается) идут лесом, тут скорее нужна теория информации per se для анализа, а не криптография.

Если не изменяет память, в Нильсоне & Чанге вопрос о задачах, эффективно решаемых/нерешаемых на КК, обсуждался примерно в таком ключе: очень мало что известно про такие задачи. Книжка не самая новая, с тех пор могло много что поменяться, но вряд ли очень сильно.

Наконец, что такое постквантовое крипто вообще? Если оно асимметричное, то я ещё могу допустить, что есть какие-то задачи из QMA, на которые можно завязаться3, но что делать с симметричным? Раз под ним нет никакой information-theoretic security изначально, то о чём вообще можно вести речь? Его класс сложности сугубо спеклятивен даже в рамках чисто классических вычислений, не говоря уже о квантовых, поскольку алгоритм строится по принципу запутывания. Насколько мне представляется, нет ни одного классического симметричного блочного шифра (одноразовый блокнот не считаем), про который доказана его принадлежность хотя бы к тому же NP. И что тогда считать безопасным против КК? По аналогии с классикой, в духе «ни один известный квантовый алгоритм не решает задачу за полиномиальное время ⇒ он КК-безопасен»? А нахождение квантового алгоритма, решающего задачу быстро, считать аналогом взлома классическим криптоанализом? Или постквантовое классическое симметричное крипто вообще не разрабатывается / не имеет смысла? Типа, эффективная длина ключа уполовинивается, и всё на том, дальше всё равно лучше не сделать?


1Имеет ли это смысл — это уже другой вопрос.
2Просто суперпозиция/запутанность (ку)битов не будет использоваться, и всё.
3Обсуждаемый пример с DH как раз к этому случаю относится.
— unknown (11/02/2013 14:10, исправлен 11/02/2013 14:16)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Симметричные криптоалгоритмы считаются условно идеальными и поэтому для их атак не работает никакой квантовый алгоритм, кроме Гровера, сокращающий перебор ключа на 2k/2. Поэтому их в PQC, действительно, вообще не рассматривают.


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


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


Вот самое новаторство по этой теме, которое вы так критиковали. Оно никем пока особо не признано, ничего лучше похоже вообще нет (широко неизвестно, игнорируется).

— spinore (11/02/2013 15:04)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786

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


Я отправил письменный запрос компенетному лицу. Надеюсь, что получу какой-нибудь ответ помимо «не знаю» (хотя бы устный и хотя бы в двух словах).
— unknown (11/02/2013 15:14, исправлен 11/02/2013 15:16)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Пока можете вводные части книжки Бернштейна почитать. С 15 по 32 стр. хотя бы. Это самый примитивный уровень, есть достаточное количество каких-то более специфичных публикаций именно со стороны криптографов. Но похоже, на этот консенсус все и полагаются.

— Гость (14/06/2013 07:57)   <#>
Времени нет, поэтому пока не забыл вообще всё полностью из того, что было накоплено, изложу в виде краткой выжимки результаты обсуждения со специалистами по квантовой теории сложности:

  • Книжку Бернштейна не читал, но пролистал. Спасибо, очень интересная. Зря вы на него наговариваете, про класс сложности там как раз есть, и немало написано. Этот класс — SZK, ищите в тексте.
  • Чем сложнее класс сложности, тем тяжелее создавать алгоритмы, поэтому в QMA никто криптографию не развивает. Вместо этого используется SZK, про который верят, что он посложнее, чем то, что взламывается на КК (NP?). Детали, между какими классами (как верят люди) он расположен, уже забыл, но дословно было что «он лишь чуть-чуть сложнее, чем то-то». Если не боитесь сойти с ума, можете полистать статьи про SZK и QMA. Сейчас по поиску, например, нашёл fileработу Ааронсона на эту тему.
  • QMA — не совсем абстракция, есть алгоритмы, про которые доказано, что они в QMA. Правда, их формулировки сильно «физичные» типа «существует ли стационарный уровень с энергией ниже некоторой в системе с данным гамильтонианом?». Тем не менее, такую же задачу можно перефразировать на формальный математический язык примерно так: «существует ли у данной матрицы собственное значение, которое меньше заданного числа?». Вот, примерно такие вещи сидят в QMA.
  • Бернштейн очень крут, нереально крут знает, о чём пишет, его квалификация в квантовой теории сложности вопросов не вызывает.
  • Проблема развиваемой постквантовой криптографии в том, что она может ломаться классическими алгоритмами (впрочем, на форуме это уже обсуждалось).
  • Бершнейн очень странный (про историю его поездки в Россию вы уже писали, помню) и совершенно неконформный по своему поведению. Очевидцы рассказывают, что на одной из конференций (где-то была ссылка на точную конференцию и доклад/слайды) докладчик, который был перед Берштейном, что-то рассказывал (про постквантовое крипто, которое сломали? Уже забыл. То ли McElice, то ли ещё что-то). После этого вышел Бернштейн делать свой доклад, и он его полностью и целиком посвятил опусканию предыдущего докладчика, объясняя, что проблема не заслуживает интереса, что там сплошной бред, что сломать можно и так и иначе. Т.е., аргументы были высказаны по существу, но, видимо, очень предвзято и очень однобоко. В общем, меня предупредили, что «Бернштейн очень специфичный и особый, учти это».
— unknown (14/06/2013 10:27, исправлен 14/06/2013 10:28)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

У нас был раньше на форуме Дэниэл Надь, который тоже предупреждал о DJB, он отказался с ним связываться, что-то зная о нём. Вообще, DJB уже давно всяким-таким известен, хамскими письмами, ещё какими-то выходками и пр.


Зато выиграл в своё время судебный процесс "DJB против США" по поводу регуляции криптографии, своими исследованиями успешно вытаскивает эллиптическую криптографию из под патентного гнёта, получил грант от НИСТ на проведение неформального конкурса на новые шифры на предполагаемыую замену AES и пр. Ещё один пример, что люди с тараканами в голове бывают полезны для общества. И полезная деятельность вполне себе бывает на грани неадекватности.


Если по-жизни уже попадались люди приблизительно такого склада и с ними как-то удавалось наладить контакт, то можете попробовать, это не так страшно, как кажется :)


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

— Гость (16/06/2013 18:51)   <#>
от ведущего собаковода планеты на тему SZK, QMA, CTC, оракулов, денег, путешествий во времени и зачем вообще жить. набегаем, не тормозим. если блочат эксит меняем личину, некоторые срабатывают. либо щёлкаем синий прямоугольник по центру экрана тута
— Гость (22/06/2013 06:14)   <#>

Понятно. Человек типа меня, значит.


Трудно что-то сказать, не зная человека, но всё же думаю, удалось бы наладить. Пока что с ним не встречался. Он вроде бы даже несколько раз приезжал к нам, вместе с Таней Ланге, но я не успел застать его, меня ещё тогда тут не было.

Людей, которые выбешивают, к сожалению, тоже удалось в жизни повстречать. Предполагаю, что 100 Бернштейнов вместе сложить если, такого мудака всё равно не получится. Очень редкий экземпляр, карикатурный хрестоматийно несмотря на то, что у него пол-сотни интересных и очень сильных работ в теме, да и fileдиссер замечательный. Страдает семитизмом в самой крайней степени этого проявления, может помочь только газовая камера эватанзия, без преувеличений. Сколько евреев в жизни перевидал и в науке и в жизни, но такое чудо, думал, возможно только в пропагандистских фильмах. Ан нет, ошибся. Главное, из-за таких характерных единиц потом на всей нации клеймо стоит. Как говорится, «работы их читайте, но по делам их не поступайте не пытайтесь с ними хоть что-то обсуждать, испачакаетесь грязью так, что потом неделю мыться ходить будете». Человек совершенно неадекватен болен, хотя пару интересных мыслей выудить с него с большим трудом всё же удалось. Надеюсь, разговаривал с ним первый и последний раз в этой жизни.


Неплохо. Оказалось, что на работе имеется то же самое, но в бумажной печатной форме, взял почитать.
— unknown (22/06/2013 10:12)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Манера изложения в книге интересная, похожа на раннего Шнайера: охват широких областей без распыления на мелочи, ясность изложения сложных понятий, остроумие к месту.
— Гость (23/06/2013 00:24)   <#>
Один из отзывов на эту книгу сравнил её с такой классикой как фейнмановские лекции по физике:

"Not since Richard Feynman's Lectures on Physics has there been a set of lecture notes as brilliant and as entertaining. Aaronson leads the reader on a wild romp through the most important intellectual achievements in computing and physics, weaving these seemingly disparate fields into a captivating narrative for our modern age of information.

Aaronson wildly runs through the fields of physics and computers, showing us how they are connected, how to understand our computational universe, and what questions exist on the borders of these fields that we still don't understand.

This book is a poem disguised as a set of lecture notes. The lectures are on computing and physics, complexity theory and mathematical logic and quantum physics. The poem is made up of proofs, jokes, stories, and revelations, synthesizing the two towering fields of computer science and physics into a coherent tapestry of sheer intellectual awesomeness."

Dave Bacon, Google

Пожалуй, можно согласиться. Фейнмановские лекции по рассказам (сам их мало читал) тоже такие: мало формул, попытка на пальцах объяснить концептуально сложные вещи, представить читателю единую картину физического мировоззрения, но фейнмановские леции — это всё же 60-ые, с тех пор пол века прошло, а тут самое-самое свежее, о чём ещё ни в одной книге не писалось.
— Гость (23/06/2013 00:34)   <#>
Судя по википедии, Ааронсону 32 года всего. Рассказывали, что в MIT политика сделать средний возраст сотрудников как можно меньше, поэтому они всем молодым и самым перспективным раздают позиции. Т.е., делают попытку собрать у себя со всего мира всех лучших, кто моложе некоторого возраста.

Ааронсону значительно повезло с тем, что он занимается областью, где работает много народа, и ещё больше народа просто интересуется этой областью. Соответственно, есть кому читать его статьи, цитировать их, выступать с докладами, создавать свою «тусовку». Во многих других областях КТИ с этим туже, интереса они порождают меньше, людей ими занимается меньше, но фундаментальная значимость тоже есть. Обратная сторона медали — в узкой мало кому интересной области проще стать королём, чем в популярной, где работает много грандов/топов.
На страницу: 1, 2 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3