Атака с помощью квантового компьютера.

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

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

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

Большая часть современных ЭВМ работают потакой же схеме: n бит памятихранят состояние икаждый такт времени изменяются процессором.

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

Теоретически новая схема может работать намного (в экспоненциальное число

раз) быстрее классической. Практически, (квантовый) алгоритм Гровера поискавбазе данных показывает квадратичный прирост мощности против классическихалгоритмов.

Атака с помощью квантового компьютераСпомощью квантового компьютера, если он будет построен, можнобудет взломать RSA, так как квантовый алгоритм Шорапозволяетосуществить факторизациюбольших чисел за достаточно короткоевремя. Разложив модуль n на простые множители, можно будетвычислитьсекретныйпоказательd.

В 1994 году Питер Шороткрыл так называемый «ограниченно-вероятностный»алгоритмфакторизации,которыйпозволяетспомощьюквантового компьютера разложить на множители число заполиномиальное от размерности задачи время. Алгоритм Шораразложениячиселнамножителиявилсяглавнымдостижениемвобластиквантовых вычислительных алгоритмов. Именно с этого моментаначалось усиленноефинансированиеработ по созданию квантовыхкомпьютеров.

Алгоритм Шора

Алгоритм Шора- квантовыйАлгоритмразложениячислаNнаПростыемножителиза время O((logN)3), затративO(logN)места.

Он делает потенциальноВозможнымвзломшифраRSA.

Алгоритм Шора используетквантовый компьютер.

Алгоритм способен взломатьRSAзаполиномиальноевремя.

Алгоритм Шора—это квантовый алгоритм факторизации(разложения числа напростые множители), позволяющий разложить число Nза время O((logN)3),затратив O(logN) места.

Значимость алгоритма заключается в том, что при использовании достаточномощного квантового компьютера, он сделает возможным взломкриптографической системы с открытым ключомRSA.

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

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

14. Алгоритм Диффи-Хеллмана

Предположим, что обоим абонентам известны некоторые два числа gи p(например, они могут быть «зашиты» в программное обеспечение),которые не являются секретными и могут быть известны также другимзаинтересованным лицам. Для того, чтобы создать неизвестный болееникому секретный ключ, оба абонента генерируют большие случайныечисла: первый абонент —число a, второй абонент —число b. Затемпервый абонент вычисляет значение A= gamod pи пересылает еговторому, а второй вычисляет B= gbmod pи передат первому.

Предполагается, что злоумышленник может получить оба этих значения,но не модифицировать их (то есть у него нет возможности вмешаться впроцесс передачи). На втором этапе первый абонент на основеимеющегося у него aи полученного по сети Bвычисляет значение Bamodp= gabmod p, а второй абонент на основе имеющегося у него bиполученного по сети Aвычисляет значение Abmod p= gabmod p. Какнетрудно видеть, у обоих абонентов получилось одно и то же число: K=gabmod p. Его они и могут использовать в качестве секретного ключа,поскольку здесь злоумышленник встретится с практическинеразрешимой (за разумное время) проблемой вычисления gabmodpпоперехваченным gamodpиgbmod p, если числа p,a,bвыбраныдостаточно большими.

Схема Диффи-ХеллманаПри работе алгоритма, каждая сторона:

генерирует случайное натуральное число a—закрытый ключсовместно с удалнной стороной устанавливает открытые параметрыpи g(обычно значения pиgгенерируются на одной стороне ипередаются другой), гдеpявляется случайным простым числомgявляется первообразным корнемпомодулюpвычисляет открытый ключA, используя преобразование надзакрытым ключомA = gamod pобменивается открытыми ключамисудалнной сторонойвычисляет общий секретный ключK, используя открытый ключудаленной стороны Bи свой закрытый ключ aK = Bamod p

Кполучаетсяравным с обеих сторон, потому что:Bamodp = (gbmodp)amodp = gabmodp = (gamodp)bmodp = Abmod p

В практических реализациях, для aиbиспользуются числа порядка10100 и pпорядка 10300. Число gне обязано быть большим и обычноимеет значение в пределах первого десятка.

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

15. Алгоритм Эль-Гамаля шифрование.

Схема Эль-Гамаля (Elgamal) —криптосистема, предложенная в 1984

году. Схема Эль-Гамаля лежит в основе стандартов электроннойцифровой подписивСШАи России

Сообщение шифруется следующим образом:

1Выбирается сессионный ключ — случайное целое число такое, что

2Вычисляются числа и .

3Пара чисел является шифротекстом.

Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения вдвое.

16. Эллиптические кривые. Криптографические алгоритмы на эллиптических кривых.

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

Эллиптические кривые описываются уравнением

Y^2+axy+by=x^3+cx^2+dx+e

1. Сложение с нулевым элементом ( несобственной точкой O)

А+0=А

2. Противоположные точки А={x;y},-A={x,y}

A-A=O

3. Если точки P и Q не удовлетворяют условиям 1 и 2, то прямая, проведенная через этидве точки имеет еще ровно одну точку пересечения с эллиптической кривой. Этаточка называется суммой точек P и Q. В вырожденном случае, когда прямая,проведенная через две точки P и Q , является касательной к одной из этих точек(напримерQ), то суммой точек P и Q является точка -Q.

4. Сложение точки самой с собой Q+Q. Проводится касательная к точке Q, ищетсяточка пересечения касательной с эллиптической кривой S и в качастве суммыберется точка, противоположная к S:

Q+Q=2Q= - S

Эллиптическая группа по модулю p

Ep(a,b)

для простого числа p и натуральных чисел a и b(должно выполняться условие

4a^3+27b^2modp<>0)

– множество, элементами которого являются

1) несобственная точка O

2) точки y x;

3) координаты которых удовлетворяют следующим условиям:

0<=x<=p-1

0<=y<=p-1
(y^2)modp=(x^3 + ax+ b)mod p

17. Квантовая криптография. Протокол BB84.

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

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

Идея использовать квантовые объекты для защиты информации от подделки инесанкционированного доступа впервые была высказана Стефаном Вейснером (StephenWeisner) в 1970 г. Спустя 10 лет Беннет и Брассард, которые были знакомы с работойВейснера, предложили использовать квантовые объекты для передачи секретного ключа.

В 1984 г. они опубликовали статью, в которой описывался протокол квантовогораспространения ключа ВВ84.

Носителями информации в протоколе ВВ84 являются фотоны, поляризованные подуглами 0, 45, 90, 135 градусов. В соответствии с законами квантовой физики, с помощьюизмерения можно различить лишь два ортогональных состояния: если известно, что фотонполяризован либо вертикально, либо горизонтально, то путем измерения, можноустановить — как именно; то же самое можно утверждать относительно поляризации подуглами 45 и 135 градусв. Однако с достоверностью отличить вертикально поляризованныйфотон от фотона, поляризованного под углом 45?, невозможно.

18. Контроль целостности сообщений. Защита от случайных изменений. Контрольная сумма. Продольный контроль целостности. Ротационный контроль целостности. Циклический избыточный код.