chmod 755 hello.cpp

g++ hello.cpp

ls

./hello.out

 

 

Эллиптические кривые


Эллиптическая кривая — это набор точек, описывающихся уравнением Вейерштрассе:

Типичные варианты графиков эллиптических кривых вы сможете посмотреть под спойлером:

Графики(6 штук)


Эллиптические кривые представленые на первых 4-х рисунках называются гладкими. В то время как две нижние кривые относятся к т.н. сингулярным эллиптическим кривым.
Для гладких эллиптических кривых выполняется следующее неравенство:

Тогда как для сингулярных кривых это условие, сюрприз, не выполняется.
Если вы собираетесь самостоятельно разрабатывать криптографических продукт, поддерживающий «эллиптику» очень важно запомнить следующий факт:
Нельзя использовать в схемах ЭЦП сингулярные кривые. Подробно мы еще затронем эту тему, сейчас же просто скажем, что используя сингулярные кривые вы рискуете значительно снизить стойкость схемы ЭЦП.
Арифметические операции в эллиптической криптографии производятся над точками кривой. Основной операцией является «сложение».
Сложение двух точек легко представить графически:

Как видно из рисунка, для сложения точек P и Q, необходимо провести между ними прямую линию, которая обязательно пересечет кривую в какой-либо третьей точке R. Отразим точку R относительно горизонтальной оси координат и получим искомую точку P+Q.

Алгебраическое представление «сложения»


Запишем сложение двух точек в виде формулы:

Пусть координатами точки P будут (xp, yp), а координатами точки Q соответственно (xq, yq). Вычислим

и тогда координаты точки P+Q будут равны:



Эллиптические кривые в криптографии


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

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

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

Однако здесь есть свои подводные камни. Если мы сложим два одинаковых элемента из бинарного конечного поля, то получим в результате 0, т.к. сложение происходит по модулю 2. Это означает что характеристика такого поля равна 2. Но эллиптическая кривая вида

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

Поэтому над бинарным конечным полем используются кривые вида:


Еще одним важным понятие эллиптической криптографии является порядок эллиптической кривой, который показывает количество точек кривой над конечным полем.
Теорема Хассе утверждает, что если N — количество точек кривой, определенной над полем Zq с q элементами тогда справедливо равенство:


Т.к. бинарное конечное поле состоит из 2n элементов мы можем сказать, что порядок кривой равен , где .

С числом t связано следующее определение:
эллиптическая кривая над бинарным конечным полем называется суперсингулярной, если t делится на характеристику поле(в случае бинарного поля характеристика равна 2) без остатка.
Разумеется все это я к тому, что нельзя использовать в схемах ЭЦП суперсингулярные кривые. Строгая рекомендация не использовать сингулярные и суперсингулярные кривые для цифровой подписи имеет одну очень вескую причину, но об этом позже.

Криптография на эллиптических кривых


Точки эллиптической кривой над конечным полем представляют собой группу. И как мы отмечали выше для этой группы определена операция сложения.
Соответственно мы можем представить умножение числа k на точку G как G+G+..+G с k слагаемыми.

Теперь представим, что у нас имеется сообщение M представленное в виде целого числа. Мы можем зашифровать его используя выражение
C=M*G.
Вопрос в том, насколько сложно восстановить M зная параметры кривой E(a,b), шифротекст С и точку G.
Данная задача называется дискретным логарифмом на эллиптической кривой и не имеет быстрого решения. Более того, считается, что задача дискретного логарифма на эллиптической кривой является более трудной для решения, чем задача дискретного логарифмирования в конечных полях.

Наиболее быстрые методы, разработанные для конечных полей оказываются бесполезны в случае эллиптических кривых.
Так для решения дискретного логарифма существуют достаточно быстрые алгоритмы имеющие сложность , где c и d — некоторые константы, а p — размер поля. Такие алгоритмы называются субэкспоненциальными и позволяют сравнительно легко вскрывать дискретный логарифм в конечном поле, если размер поля не выбран очень большим, порядка 21024.
В тоже время наиболее быстрые методы решения дискретного логарифма на эллиптической кривой имеют сложность , где q — количество точек эллиптической кривой.
Таким образом, для обеспечения уровня стойкости в 280 операций необходимо чтобы q=2160. Напомню, для того, чтобы получить аналогичный уровень сложности при вычислении дискретного логарифма в конечном поле необходимо поле порядка q=21024.

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

Варианты атак

 

  1. Алгоритма Полига-Хеллмана. Алгоритм решения дискретного логарифма. Предположим, что n — количество точек эллиптической кривой. Пусть число n раскладывается на простые числа p1, p2,.., pn. Суть метода сводится к тому, чтобы найти дискретные логарифмы по модулю числе pi, а затем получить общее решение с помощью китайской теоремы об остатках. Атака позволяет свести проблему дискретного логарифма в большом поле n к той же задаче, но с гораздо меньшим полем p. Для того, чтобы противостоять атаке необходимо просто выбирать кривые, количество точек которых делится на очень большое простое число q≈n.
  2. Алгоритм Шенкса, более известный как шаги младенца/шаги гиганта. Типичный пример time memory trade off. Для группы размером n вычисляется таблиц размером n1/2, затем по этой таблице происходит поиск нужного элемента. Сложность алгоритма .
  3. Уязвимость сингулярных и суперсингулярных кривых. Я уже упоминал, что для решения задачи дискретного логарифма не существует субэкспоненциальных методов решения. На самом деле есть одна оговорка, такие методы есть, но только для определенного рода кривых: сингулярных и суперсингулярных. Особые свойства таких кривых позволяют свести задачу дискретного логарифма на эллиптической кривой, к задаче дискретного логарифма в конечном поле. Соответственно для такого класса кривых стандартные ключи размером в 160-320 бит, будут фатально уязвимы, что позволит злоумышленникам вскрыть секретный ключ, за относительно небольшое время.
  4. Уязвимость аномальных кривых Напомню, что количество точек эллиптической кривой вычисляется по формуле
    n=q+1-t, где q — размер исходного поля. И что кривая называется суперсингулярной если t делится на 2.
    Поэтому, на первый взгляд может показаться хорошей идеей использовать кривые в которых количество точек равно q, т.е. t=1.
    Однако такие кривые называются аномальными и решение дискретного логарифма на аномальных эллиптических кривых является еще более простой задачей, чем для суперсингулярных и сингулярных кривых.



Подытожим


На основании всего вышесказанного выпишем основные достоинства и недостатки эллиптической криптографии:
Итак, основные плюсы:

  1. Гораздо меньшая длина ключа по сравнению к «классической» асимметричной криптографией.
  2. Скорость работы эллиптических алгоритмов гораздо выше, чем у классических. Это объясняется как размерами поля, так и применением более близкой для компьютеров структуры бинарного конечного поля.
  3. Из-за маленькой длины ключа и высокой скорости работы, алгоритмы асимметричной криптографии на эллиптических кривых могут использоваться в смарт-картах и других устройствах с ограниченными вычислительными ресурсами.


Основные минусы эллиптической криптографии:

  1. Все плюсы эллиптической криптографии вытекают из одного конкретного факта:
    для задачи дискретного логарифмирования на эллиптических кривых не существует субэкспоненциальных алгоритмов решения. Это позволяет уменьшить длину ключа и увеличить производительность. Однако если такие алгоритмы появятся, то это будет означать крах эллиптической криптографии.
  2. Эллиптическая криптография — это очень сложно. Не то чтобы я считал обычную асимметричную криптографию совсем уж простой штукой. Но «эллиптика» — это огромное количество тонкостей, которые необходимо учесть. Начиная с выбора эллиптической кривой и заканчивая генерацией ключей. При массовом переходе на эллиптику скорее всего обязательно будет большое количество ошибок и уязвимостей, которые уже отработаны для более привычных методов.



На основании всего вышесказанного, я сделал для себя вывод, что повсеместный переход на «эллиптику» не является необходимостью. В конце концов, пока мирно сосуществуют обычные RSA, DSA с одной стороны, и ГОСТ 34.10, ECDSA с другой, есть пусть и ложное, но успокаивающее чувство альтернативы, которого мы можем лишиться, погнавшись за самыми современными криптографическими методами.

Используемая литература

 

  1. Don Johnson, Alfred Menezes, Scott Vanstone — The Elliptic Curve Digital Signature Algorithm.
  2. А. Болотов, С. Гашков, А. Фролов, А. Часовских — Элементарное введение в эллиптическую криптографию.
  3. Lawrence Washington — Elliptic curves, Number theory and Cryptography.

Курс Dlink

Курс ICND1 v1.0 @ Atraining / Руслан Карманов (5 дней)

 

  Основы безопасности@ Atraining / Руслан Карманов

 Курс ICND2 @ Atraining / Руслан Карманов

 

Windows Server 2012 R2.

Linux

Квантовая криптография

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

Кубиты

Кубит — это и есть состояние, которое передается при квантовой телепортации. Квантовый бит находится в суперпозиции двух состояний. Классическое состояние находится, например, либо в состоянии 0, либо в состоянии 1. Квантовое находится в суперпозиции, и, что очень важно, пока мы его не измерим, оно не будет определено. Представим себе, что у нас был кубит на 30% — 0 и на 70% — 1. Если мы его измерим, мы можем получить как 0, так и 1. За одно измерение нельзя ничего сказать. Но если приготовить 100, 1000 таких одинаковых состояний и раз за разом их измерять, мы можем достаточно точно охарактеризовать это состояние и понять, что действительно там было 30% — 0 и 70% — 1.

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

Мы также используем явление квантовой нелокальности, то есть явление, которое невозможно в привычном для нас мире, для того чтобы здесь это состояние исчезло, а там появилось. Причем самое интересное, что применительно к тем же квантовым объектам существует теорема о неклонировании. То есть невозможно создать второе идентичное состояние. Надо уничтожить одно, чтобы появилось другое.

Квантовая запутанность

Что такое эффект запутанности? Это особым образом приготовленные два состояния, два квантовых объекта — кубита. Для простоты можно взять фотоны. Если эти фотоны разнести на большое расстояние, они будут коррелировать между собой. Что это значит? Представим себе, что у нас один фотон синий, а другой зеленый. Если мы их разнесли, посмотрели и у меня оказался синий, значит, у вас оказался зеленый, и наоборот. Или если взять коробку обуви, где есть правый и левый ботинок, незаметно их вытащить и в мешке отнести один ботинок вам, другой мне. Вот я открыл мешок, смотрю: у меня правый. Значит, у вас точно левый.

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

Если взять не цвет, а поляризацию, то есть направление колебаний электрического поля, можно выделить два варианта: вертикальная и горизонтальная поляризация и +45° — -45°. Если сложить вместе в равной пропорции горизонтальную и вертикальную, то получится +45°, если вычесть одну из другой, то -45°. Теперь представим, что точно так же один фотон попал ко мне, а другой к вам. Я посмотрел: он вертикальный. Значит, у вас горизонтальный. Теперь представим, что я увидел вертикальный, а вы посмотрели его в диагональном базисе, то есть посмотрели — он +45° или -45°, вы увидите с равной вероятностью тот ли иной исход. Но если я посмотрел в диагональном базисе и увидел +45°, то точно знаю, что у вас -45°.

Парадокс Эйнштейна — Подольского — Розена

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

Но на самом деле теорию относительности это не нарушает, потому что информацию с помощью этого эффекта мы передать все равно не можем. Измеряется либо вертикальный, либо горизонтальный фотон. Но неизвестно заранее, какой именно он будет. Несмотря на то что нельзя передавать информацию быстрей скорости света, запутанность позволяет реализовать протокол квантовой телепортации. В чем он заключается? Рождается запутанная пара фотонов. Одна направляется к передатчику, другая — к приемнику. Передатчик производит совместное измерение целевого фотона, который он должен передать. И с вероятностью ¼ он получит результат OK. Он может сообщить об этом получателю, и получатель в этот момент узнает, что у него точно такое же состояние, как было у передатчика. А с вероятностью ¾ он получает другой результат — не то чтобы неуспешное измерение, а просто другой результат. Но в любом случае это полезная информация, которую можно передать получателю. Получатель в трех из четырех случаев должен произвести дополнительный поворот своего кубита, чтобы получить передаваемое состояние. То есть передается 2 бита информации, и при помощи них можно телепортировать сложное состояние, которое ими закодировать нельзя.

Квантовая криптография

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

У этой технологии есть один большой недостаток. Дело в том, что, как мы уже раньше говорили, создать копию фотона невозможно. Обычный сигнал в оптоволокне можно усилить. Для квантового случая усилить сигнал невозможно, так как усиление будет эквивалентно некоторому перехватчику. В реальной жизни, в реальных линиях передача ограничена расстоянием приблизительно до 100 километров. В 2016 году Российским квантовым центром была проведена демонстрация на линиях Газпромбанка, где показали квантовую криптографию на 30 километрах волокна в городских условиях.

В лаборатории мы способны показывать квантовую телепортацию на расстоянии до 327 километров. Но, к сожалению, большие расстояния непрактичны, потому что фотоны теряются в волокне и скорость получается очень низкая. Что делать? Можно поставить промежуточный сервер, который будет получать информацию, расшифровывать, потом снова зашифровывать и передавать дальше. Так делают, например, китайцы при строительстве своей сети квантовой криптографии. Такой же подход используют и американцы.

Квантовая телепортация в данном случае — это новый метод, который позволяет решить задачу квантовой криптографии и увеличить расстояние до тысяч километров. И в этом случае тот самый фотон, который передается, многократно телепортируется. Над этой задачей работает множество групп во всем мире.

Квантовая память

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

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

Ход эксперимента в лаборатории

Если вы придете в лабораторию квантовых коммуникаций, то вы увидите много электроники и волоконную оптику. Вся оптика стандартная, телекоммуникационная, лазеры в маленьких стандартных коробочках — чипах. Если вы зайдете в лабораторию Александра Львовского, где, в частности, делают телепортацию, то вы увидите оптический стол, который стабилизирован на пневмоопорах. То есть если этот стол, который весит тонну, потрогать пальцем, то он начнет плавать, покачиваться. Это сделано по причине того, что техника, которая реализует квантовые протоколы, очень чувствительна. Если вы поставите на жесткие ножки и будете ходить вокруг, то это все будет по колебаниям стола. То есть это открытая оптика, достаточно большие дорогие лазеры. В целом это достаточно громоздкое оборудование.

Исходное состояние готовится лазером. Для подготовки запутанных состояний используется нелинейный кристалл, который накачивается импульсным или непрерывным лазером. За счет нелинейных эффектов рождаются пары фотонов. Представим себе, что у нас есть фотон энергии два — ℏ(2ω), он преобразуется в два фотона энергии один — ℏω+ ℏω. Эти фотоны рождаются только вместе, не может сначала отделиться один фотон, потом другой. И они связаны (запутаны) и проявляют неклассические корреляции.

История и актуальные исследования

Итак, в случае квантовой телепортации наблюдается эффект, который в ежедневной жизни мы наблюдать не можем. Но зато был очень красивый, фантастический образ, который как нельзя кстати подходил для описания этого явления, поэтому и назвали так — квантовая телепортация. Как уже было сказано, нет момента времени, когда здесь кубит еще существует, а там он уже появился. То есть сначала здесь уничтожено, а только потом там появляется. Это и есть та самая телепортация.

Квантовая телепортация была предложена теоретически в 1993 году группой американских ученых под руководством Чарльза Беннета — тогда и появился этот термин. Первая экспериментальная реализация была проведена в 1997 году сразу двумя группами физиков в Инсбруке и Риме. Постепенно ученым удавалось передавать состояния на все большее расстояние — от одного метра до сотен километров и более.

Сейчас люди пытаются делать эксперименты, которые, возможно, в будущем станут основой для квантовых повторителей. Ожидается, что спустя 5–10 лет мы увидим реальные квантовые повторители. Развивается и направление передачи состояния между объектами разной природы, в том числе в мае 2016 года была проведена гибридная квантовая телепортация в Квантовом центре, в лаборатории Александра Львовского. Теория тоже не стоит на месте. В том же Квантовом центре под руководством Алексея Федорова разрабатывается протокол телепортации уже не в одну сторону, а двунаправленный, чтобы с помощью одной пары сразу одновременно навстречу друг другу телепортировать состояния.

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

 

Компьютерные сети

Системы связи

Администрирование

Безопасность

Основы программирования

Прочие