Решенные билеты (1085496), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Параметры

• n=pq, р и q—простые.

• t, k  N — параметры надежности.

• h: {0,1}^*  Z_n — криптографически стойкая хэш-функция.

Ключи

• Открытый ключ: v =(I,(j_i)_i=1,…,k), где j_i  {0,1}*— битовые строки такие, что v_i =h(1|| j_i)  QR_n для всех i.

• Закрытый ключ: набор (s_i)_i=1,…,k,s_i =v_i^-1/2. Вычисляется центром распределения ключей, которому известно разложение n на множители.

0. P V | v | V вычисляет и проверяет (v_i)_i=1,…,k.

Следующие шаги выполняются t раз.

V проверяет, что z=y² (v₁^b1…v_k^bk).

Утверждение. Вероятность угадывания набора (b_i) и выбора соответствующих z и у без знания закрытого ключа на одной итерации протокола равна 2^-k, а за t итераций — 2^-kt.

Утверждение. Это протокол с нулевым раскрытием, т.е. даже без участия Р проверяющий V может изготовить сколько угодно правильных пар (х,у), распределенных так же, как соответствующие пары при участии Р.

Злоумышленник может фальсифицировать открытый ключ, подбирая одновременно s и j так, чтобы s²=h(I || j). Но количество попыток, необходимых для удачного попадания, равно приблизительно , где N — количество возможных значений h. Кроме того, можно ограничить размер допустимых чисел ;.

Достоинства модифицированной схемы Фиата — Шамира.

• Быстрее, чем RSA.

• Не требует использования схемы распределения открытых ключей.

• С нулевым раскрытием.

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

В работе Micali S., Shamir A. предложен способ уменьшить количество вычислений, которые делает проверяющий. Для этого в качестве значений (v_i)_i=1,…,k берутся k первых простых чисел, а каждый доказывающий участник сам выбирает для себя значение п.

Схема идентификации Шнорра

Эта схема (Schnorr ) еще быстрее схемы Фиата — Шамйра и основывается на трудности вычисления дискретных логарифмов.

Протокол Шнорра идентификации клиента Р в системе V. Пусть клиент однозначно идентифицируется строкой I {0,1}^*.

Параметры

• p=qt+1, p и q — простые, g — элемент порядка q в Z_p^* .

• S (х) — схема цифровой подписи.

• t,k  N - параметры надежности.

• h: {0,1}* Z_n — криптографически стойкая хэш-функция.

Ключи

• Закрытый ключ: s  Z_q.

• Открытый ключ: v=g^-s  Z_p^* , сертификат ключа S(I,v).

Р доказывает знание дискретного логарифма v:

1. Р V | (I,v,S(I,v)) | V проверяет подпись.

Повторять t раз.

Если для некоторого z известны e₀, у₀, е₁, y₁ такие, что d=e₁ – e₀ 0 и z=g^y0 v^e0=g^y1v^e1 в Z_p*, то можно найти t=у₀-y₁ такое, что g^t=v^d. Поскольку q — простое, можно найти c Z_q такое, что cd=l в Z_q. Тогда tc — дискретный логарифм v.

Таким образом, если Р может дать правильный ответ у хотя бы для двух различных значений е, то он знает закрытый ключ. Без знания закрытого ключа можно только угадать е на всех раундах протокола и выбрать вероятность этого не превосходит k^-t.

Ограничение на величину е добавлено Шнорром в свете изменившихся взглядов на доказательства с нулевым раскрытием.

В процессе проверки Р должен произвести одно умножение и одно сложение, набор значений z можно подготовить заранее.[1]

-------------------------------------------------ЧАСТЬ2--------------------------------------------------------

Вопрос 19.

Квантовая криптография. Распределение ключей по оптическому квантовому каналу связи.

Гильбертово пространство для одиночного поляризованного фотона является 2-мерным. Таким образом, состояние фотона может быть полностью описано в виде линейной комбинации, к примеру, двух единичных векторов r₁=(1,0) и r₂=(0,1), представляющих соответственно горизонтальную и вертикальную поляризации. В частности фотон, поляризованный под углом  к горизонтали, описывается вектором состояния (cos, sin). В том случае, когда такой фотон подвергается измерению на предмет горизонтальности или вертикальности своей поляризации, то в действительности он как бы выбирает, стать ли ему горизонтально" поляризованным с вероятностью cos² и вертикально поляризованным с вероятностью sin². Два ортогональных вектора r₁ и r₂, таким образом, служат примером разложения 2-мерного гильбертова пространства на 2 ортогональных одномерных подпространства. С этого момента мы будем говорить, что пара векторов (r₁, r₂) составляют прямоугольный базис рассматриваемого гильбертова пространства.

Другой возможный базис того же гильбертова пространства задается двумя диагональными векторами

d₁= (1,1) и d₂= (1,-1).

В этом диагональном базисе d₁ представляет фотон, поляризованный под углом 45°, а d₂ — фотон с поляризацией под углом 135°.

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

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

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

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

Рассмотрим более подробно, каким образом Алиса и Боб могут осуществить открытое распределение ключей с использованием квантового канала.

В качестве первого шага с выхода датчиков случайных чисел Алиса выбирает произвольную битовую строку

 =

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

B = ,

+ - прямоугольный базис,  - диагональный базис.

Затем она посылает Бобу ряд поляризованных фотонов

= ,

где угол поляризации фотона определяется как значением битовой строки, так и "значением" базиса:

,

,

,

.

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

Несмотря на это, Боб в каждом такте квантовой передачи решает абсолютно случайным для каждого фотона образом и совершенно независимо от Алисы измерить, какую поляризацию имеют все фотоны, прямоугольную или диагональную. Для этого он выбирает случайным и равновероятным образом угол оптической оси призмы – 0⁰ или 45⁰ и получает, формально обозначая, два возможных исхода:

=1 – регистрация фотона в прямом луче,

=2 – регистрация фотона в ортогональном луче.

(Выбор = 0⁰ соответствует измерению в прямоугольном базисе, = 45⁰ соответствует измерению в диагональном базисе.)

Нетрудно видеть, что если

, =0⁰ и =0⁰, то вероятность P( =1)=1,

, =90⁰ и =0⁰, то вероятность P( =2)=1,

, =45⁰ и =45⁰, то вероятность P( =1)=1,

, =135⁰ и =45⁰, то вероятность P( =2)=1.

Во всех остальных случаях вероятность P( =1)=P( =2)=1/2.

Таким образом, если базисы у Алисы и Боба совпадают (+( =0⁰), ( =45⁰)), то измерения поляризации фотона на приемном конце приобретают детерминированный характер. Боб полагает значение бита =0, если =1 и =1, если =2. При условии совпадения базисов

Характеристики

Список файлов ответов (шпаргалок)