авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 | 5 |

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА Факультет вычислительной математики и кибернетики ...»

-- [ Страница 3 ] --

=H (3) x y y x y 2 2 Вычисляя величину (3) как функцию параметра q, можно получить, что информация Евы начинает превосходить взаимную информацию Алисы и Боба, когда q превышает 11 %, что является теоретическим пределом. Таким образом, построенная атака является наиболее эф фективной.

СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) РАСШИРЕНИЕ ОБЛАСТИ СЕКРЕТНОСТИ Рис. 1. Расположение векторов базиса, в котором выписываются матрицы операторов (2), относитель но векторов {|i, |i } в пространстве Евы.

1.1 Внесение дополнительного шума Рассмотрим теперь, что происходит при внесении Алисой дополнительного шума, задава емого вероятностью ошибки p. Исходная ошибка q на стороне Боба становится равной Q = (1 p)(1 q) + pq, (4) а Ева, как нетрудно видеть, стоит перед необходимостью различения состояний E = TrE |X X| = (1 p) [(1 q)|x x | + q|x x |] + p [(1 q)|y y | + q|y y |], x (5) E = TrE |Y Y | = (1 p) [(1 q)|y y | + q|y y |] + p [(1 q)|x x | + q|x x |].

y В этом случае можно посчитать величину Холево для этих состояний при заданной ве личине исходной ошибки q и оптимальном (для Алисы и Боба) выборе параметра шума p.

Выпишем матрицы операторов (5) в базисе {|0, |1, |0, |1 }, элементы которого располо жены симметрично относительно векторов |i и |i (рисунок 1):

(1 q) 1 + (1 2p) 1 2 (1 q) 0 1 (1 q) (1 q) 1 (1 2p) 1 0 E =, x q 1 + (1 2p) 1 2 0 0 q 1 q 1 (1 2p) 0 0 q 1 (1 q) 1 (1 2p) (1 q) 0 1 (1 q) (1 q) 1 + (1 2p) 1 0 E =.

y 1 q 1 (1 2p) 2 0 0 q 1 q 1 + (1 2p) 0 0 q Собственные значения этих матриц совпадают и равны 1q 1 4p(1 p)(1 2 ), 1± 1,2 = q 1 4p(1 p)(1 2 ), 1± 3,4 = а с учетом (1) их можно переписать в виде 1q 1± 1 16pq(1 p)(1 q), 1,2 = q 1± 1 16pq(1 p)(1 q).

3,4 = Для подсчета величины Холево для состояний Евы требуются также собственные значения оператора 2 (E + E ). Они не отличаются от аналогичных значений при отсутствии допол x y нительного шума и равны {(1 q)2, q(1 q), q(1 q), q 2 }. С учетом этого информация Евы вычисляется по формуле IAE = 2h(q) + i log i i= СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 72 КРОНБЕРГ 0. no optimization by noise by blocks 0. by blocks and noise 0. 0. 0. 0. 0.10 0.12 0.14 0.16 0.18 0.20 0. Рис. 2. Зависимость длины секретного ключа протокола BB84 от наблюдаемой на приемной стороне ошибки q при разных действиях перехватчика. Сплошная линия соответствует отсутствию предва рительной обработки данных, пунктирная линия проведению оптимизации по вносимому шуму, штрихпунктирная линия оптимизации по блочному исправлению ошибок, штрихованная линия комбинированию методов предварительной обработки данных. Показана только область, на которой применение методов предварительной обработки данных существенно меняет исходную длину ключа.

При малых значениях ошибки все графики практически совпадают.

p и q. Информация на приемной стороне с учетом (4) равна и зависит от двух параметров IAB (p, q) = 1 h (1 p)q + (1 q)p = 1 + Q log Q + (1 Q) log(1 Q).

Вычисления показывают, что при использовании дополнительного шума критическая ве личина ошибки, до которой возможно секретное распространение ключей, увеличивается при мерно до 12,4 %, что соответствует результатам, изложенным в [4]. Отношение длины сек ретного ключа к общей длине передаваемой последовательности с учетом потерь, вызванных дополнительным шумом, равна r (q) = max 1 h (1 p)q + (1 q)p 2h(q) i log i.

n p i= На рисунке 2 пунктирной линией показан график зависимости длины секретного ключа от ошибки на приемной стороне без предварительной обработки данных и с внесением допол нительного шума. Увеличение длины секретного ключа достигается только там, где исходная ошибка близка к критической, в случае же небольшой исходной ошибки внесение дополни тельного шума оказывается нецелесообразным.

1.2 Блочное исправление ошибок При блочном исправлении ошибок с длиной блока, равной N, ошибка на стороне Боба будет равна qN Q=. (6) (1 q)N + q N СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) РАСШИРЕНИЕ ОБЛАСТИ СЕКРЕТНОСТИ При этом, поскольку все блоки с разными исходами измерений на стороне Боба отбрасываются, Ева будет стоять перед необходимостью различать состояния, соответствующие получению только правильных или только ошибочных исходов. Это состояния N x |N + Q|x N x |N, E = (1 Q)|x x (7) N y |N + Q|y N y |N.

E = (1 Q)|y y Так как состояния |i и |j взаимно ортогональны, собственные значения каждого из операторов плотности (7) будут равны (1 q)N qN 1 =, 2 =.

(1 q)N + q N (1 q)N + q N Далее, так как x |y N = ( x |y )N = N, нетрудно видеть, что собственные значения N оператора- полусуммы E = 1 (E + E ), необходимые для подсчета величины Холево, равны 2x y (1 q)N 1 ± N · 1,2 =, (1 q)N + q N (8) qN 1 ± N · 3,4 =, (1 q)N + q N а с учетом (1) их можно выразить только через q и параметр процедуры N. Взаимная инфор мация Алисы и Боба равна qN IAB = 1 h(Q) = 1 h, (1 q)N + q N а значит, разность взаимных информаций между Алисой и Бобом и между Алисой и Евой IAB IAE = 1 h(Q) H(E ) + h(Q) = 1 H(E ) = 1 + i log i i= зависит только от собственных значений оператора E.

Длина финального ключа при использовании блочного исправления ошибок падает как из-за объединения битов исходной последовательности в блоки, так и из-за отбрасывания ча сти блоков, значения битов в которых оказались разными. Окончательное отношение длины секретного ключа к длине последовательности при использовании блоков длины N равно (1 q)N + q N r (1 H(E )).

(q, N ) = n N После максимизации по всем возможным длинам блоков (на практике нет существенной пользы от использования блоков длиной свыше 5) получаем (1 q)N + q N r (1 H(E )).

(q) = max (9) n N N На рисунке 2 штрихпунктирная линия соответствует зависимости длины секретного ключа при использовании метода блочного исправления ошибок. Как можно видеть из графика, этот метод способен увеличить критическую ошибку сильнее, чем метод внесения дополнительно го шума. Критическая ошибка при использовании блочного исправления ошибок возрастает примерно до 20 %, однако следует принимать во внимание, что для подобного увеличения критической ошибки нужно использовать блоки большой длины, что сильно уменьшает дли ну финального ключа.

СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 74 КРОНБЕРГ 1.3 Комбинирование методов Технологии внесения дополнительного шума и блочного исправления ошибок можно объ единить двумя способами. Эти способы отличаются порядком действий: можно сначала внести дополнительный шум в канал, а затем провести блочное исправление ошибок, либо наоборот:

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

Состояния Евы, получающиеся после измерения Боба с исправлением ошибок блоками по N бит и внесения дополнительного шума, задаются комбинацией состояний (5) и (7):

(1 q)N qN N x |N + N x |N + E = (1 p) |x |x (1 q)N + q N (1 q)N + q N (1 q)N qN N y |N + N y |N, |y |y +p (1 q)N + q N (1 q)N + q N (10) (1 q)N qN N y |N + N N E = (1 p) |y |y y | + (1 q)N + q N (1 q)N + q N (1 q)N qN N x |N + N x |N.

|x |x +p (1 q)N + q N (1 q)N + q N Собственные значения этих операторов (их матрицы проще всего выглядят в базисе {|0, |1, |0, |1 }, симметричном относительно векторов |i N и |i N, подобно базису N N N N на рисунке 1, построенному для векторов |i и |i ) равны 1 (1 q)N 1 4p(1 p)(1 2N ), 1± µ1,2 = 2 (1 q)N + q N qN 1 4p(1 p)(1 2N ).

1± µ3,4 = 2 (1 q)N + q N Собственные значения оператора E = 1 (E + E ) так же, как и в случае отсутствия шума, 2x y равны (8). В итоге для длины секретного ключа получаем (1 q)N + q N qN r 1h (i log i µi log µi ).

(q) = max + (11) (1 q)N + q N n N N i= На рисунке 2 штриховой линией показан график зависимости длины ключа от ошибки на приемной стороне при комбинировании методов предварительной обработки данных. Как может быть видно из этого графика, это позволяет добиться дополнительного увеличения длины секретного ключа. Критическая ошибка, до которой возможна генерация секретного ключа, при комбинировании методов оказывается равной приблизительно 23%, но, как и в слу чае блочного исправления ошибок, достигается лишь для больших длин блоков, не дающих большой практической пользы из-за малой длины конечного секретного ключа.

2 Протокол с фазово-временным кодированием Протокол с фазово-временным кодированием, предложенный в [8], использует 4 базиса, ко торые разделены на 2 группы: левые и правые. Для передачи состояний используется три временных окна, которые обозначаются как |1, |2, |3. Состояния из левого базиса являют ся комбинациями первых двух временных окон, состояния из правого базиса комбинацией второго и третьего окна (рисунок 3).

СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) РАСШИРЕНИЕ ОБЛАСТИ СЕКРЕТНОСТИ ± «Левые» базисы t ± «Правые» базисы Временные окна 1 2 Рис. 3. Конфигурация базисных состояний в протоколе с фазово-временным кодированием.

Существует две версии протокола с фазово-временным кодированием. Первая из них ис пользует ортогональные состояния внутри каждого базиса. Эти состояния равны 1 |0+L = (|1 |0+R = (| + |2 ), + |3 ), 2 1 +L +R = (|1 = (| |1 |2 ), |1 |3 ), 2 1 |0L = (|1 |0R = (| + i|2 ), + i|3 ), 2 1 |1L = (|1 |1R = (| i|2 ), i|3 ).

2 Как видно из приведенных формул, конфигурация состояний только в левых или только в правых базисах аналогична их расположению в протоколе BB84. На приемной стороне Боб случайным образом выбирает один из четырех базисов измерения: {+L, L, +R, R}. Наряду с информационным исходом он может получить отсчет в контрольном временном окне: ре зультат 3 для состояния из левого базиса и результат 1 для правого. Для примера, оператор измерения в базисе +L выглядит так:

+L +L I = M0 + M1 + Mc = (|1 + |2 )( 1| + 2|) + (|1 |2 )( 1| 2|) + |3 3|.

Неортогональная версия протокола с фазово-временным кодированием использует кон фигурацию векторов в каждой паре базисов, похожую на их расположение в протоколе SARG04 [6], а именно |0La = cos |1 |0Ra = cos | + sin |2 + sin |,, 2 2 2 La Ra |1 = cos |1 sin |2 |1 = cos |2 sin |,, 2 2 2 Lb Rb |0 = sin |1 cos |2 |0 = sin |2 cos |,, 2 2 2 Lb Rb |1 = sin |1 + cos |2 |1 = sin |2 + cos |,.

2 2 2 В этой версии угол между состояниями в каждом базисе равен. Цель такой конфигу рации противодействие PNS-атаке [1], возможной при не строго однофотонных источниках и потерях в канале связи.

На приемной стороне Боб предпринимает измерение с тремя исходами, которое при от сутствии ошибки в канале с некоторой вероятностью дает безошибочный результат, либо дает несовместный исход, когда конкретный результат получить не удалось. Также может быть СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 76 КРОНБЕРГ получен отсчет в контрольном временном окне. Так, для базиса La, с учетом того, что со стояния |0La и |0Lb ортогональны, получаем следующее разложение единицы:

L L L L I = M 0 a + M1 a + M ? a + Mc a, где |1La 1La | |0Lb 0Lb | L M0 a = =, 1 + cos 1 + cos |0La 0La | |1Lb 1Lb | L M1 a = =, 1 + cos 1 + cos L L L M? a = |1 1| + |2 2| M0 a M1 a, L Mc a = |3 3|.

Как показал анализ стойкости ортогональной [9] и неортогональной [7] версий протокола, при отсутствии отсчетов в контрольных временных окнах секретное распространение ключей возможно, когда ошибка на приемной стороне не превышает 50 %, что соответствует теорети ческому пределу. При увеличении числа контрольных отсчетов критическая величина ошибки снижается.

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

В этом разделе уже рассмотренные выше на примере BB84 методы предварительной обра ботки данных будут применены к протоколу с фазово-временным кодированием.

2.1 Схема оптимальной атаки Коллективная атака на протокол с фазово-временным кодированием со всеми подробно стями была рассмотрена в [7]. Напомним здесь основные выкладки этого построения.

Унитарное преобразование подслушивателя может быть расписано по временным окнам следующим образом:

1 1 UE |1 = |1 = |1 |1 + |2 |2 + |3 |3, 2 2 UE |2 = |2 = |1 |1 + |2 |2 + |3 |3, 3 3 UE |3 = |3 = |1 |1 + |2 |2 + |3 |3.

При отправлении базисных состояний |0La и |1La они преобразуются в состояния UE |0La = UE (cos |1 + sin |2 ) = |0La = 2 1 2 1 2 1 = |1 (cos |1 + sin |1 ) + |2 (cos |2 + sin |2 ) + |3 (cos |3 + sin |3 ), 2 2 2 2 2 UE |1La = UE (cos |1 sin |2 ) = |1La = 2 1 2 1 2 1 = |1 (cos |1 sin |1 ) + |2 (cos |2 sin |2 ) + |3 (cos |3 sin |3 ).

2 2 2 2 2 Операторы измерения Боба, отвечающие совместным исходам, записываются в этом базисе как 1 La sin2 |1 1| + cos2 |2 2| + sin cos (|1 2| + |2 1|), M0 = 1 + cos 2 2 2 1 La sin2 |1 1| + cos2 |2 2| sin cos (|1 2| + |2 1|).

M1 = 1 + cos 2 2 2 СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) РАСШИРЕНИЕ ОБЛАСТИ СЕКРЕТНОСТИ Состояния Евы после применения этих операторов равны † 0 MLa |0La 0La | MLa OK = TrE = 0La (1 2q) sin + q cos 0La |MLa |0La cos2 sin2 1 1 2 2 1 2 2 1 1 2 2 |1 1 | + |2 2 | + |1 2 | + |2 1 | + |2 1 | + |1 2 | + 2 1 + cos4 |2 2 | + sin4 |1 1 | + 1 2 + cos sin3 1 2 2 1 2 2 2 |1 1 | + |1 1 | + |1 2 | + |2 1 | + 2 + cos3 sin 1 1 1 1 1 2 2 |1 2 | + |2 1 | + |2 2 | + |2 2 |, 2 † 1 MLa |0La 0La | MLa Err = TrE = 0La q 0La |MLa |0La cos2 sin2 1 1 2 2 1 2 2 1 1 2 2 |1 1 | + |2 2 | |1 2 | |2 1 | |2 1 | |1 2 | + 2 1 + cos4 |2 2 | + sin4 |1 1 | 1 2 cos sin3 1 2 2 1 2 2 2 |1 1 | + |1 1 | + |1 2 | + |2 1 | 2 cos3 sin 1 1 1 1 1 2 2 |1 2 | + |2 1 | + |2 2 | + |2 2 |, 2 † 1 MLa |1La 1La | MLa OK = TrE = 1La (1 2q) sin + q cos 1La |MLa |1La cos2 sin2 1 1 2 2 1 2 2 1 1 2 2 |1 1 | + |2 2 | + |1 2 | + |2 1 | + |2 1 | + |1 2 | + 2 1 + cos4 |2 2 | + sin4 |1 1 | 1 2 cos sin3 1 2 2 1 2 2 2 |1 1 | + |1 1 | + |1 2 | + |2 1 | 2 cos3 sin 1 1 1 1 1 2 2 |1 2 | + |2 1 | + |2 2 | + |2 2 |, 2 † 0 MLa |1La 1La | MLa Err = TrE = 1La q 1La |MLa |1La cos2 sin2 1 1 2 2 1 2 2 1 1 2 2 |1 1 | + |2 2 | |1 2 | |2 1 | |2 1 | |1 2 | + 2 1 + cos4 |2 2 | + sin4 |1 1 | + 1 2 + cos sin3 1 2 2 1 2 2 2 |1 1 | + |1 1 | + |1 2 | + |2 1 | + 2 + cos3 sin 1 1 1 1 1 2 2 |1 2 | + |2 1 | + |2 2 | + |2 2 | 2 Будем использовать следующий ортонормированный базис для выписывания элементов приведенных матриц: {|µ1, |µ2, |1, |2 }, где векторы удовлетворяют соотношениям 1 µ1 |1 = 1 2q cos a = µ2 |2, 2 µ1 |2 = 1 2q sin a = µ2 |1, СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 78 КРОНБЕРГ 1 1 |2 = 1 2q cos b = 2 |1, 2 1 |1 = 1 2q sin b = 2 |2, 12 и параметры a и b выражаются через параметры перехватчика cos = 1 |2 и cos = 1 | как,.

a= b= 4 2 4 В свою очередь параметры q, и связаны соотношением 1 3q = (1 2q) cos + q cos.

Для краткости введем следующие обозначения:

1 2q cos 1 2q sin 1 + cos, m1 = sin (cos a + sin a) = 2 2 m2 = 1 2q cos sin (cos a sin a) = 1 2q sin 1 cos, 2 2 2 1 cos, n1 = q(sin sin b + cos cos b) = q 1 + cos + cos 2 2 n2 = q(sin2 cos b + cos2 sin b) = 1 + cos cos 1 cos, q 2 2 k1 = q(sin2 sin b cos2 cos b) = q 1 cos cos 1 + cos, 2 2 k2 = q(sin2 cos b cos2 sin b) = 1 cos cos q 1 + cos.

2 2 Матрицы плотности, соответствующие каждому из исходов Боба при посылке сигналов и 1 теперь можно записать как m2 m2 m1 n1 m1 n 1 2 1 m1 m1 m1 n1 m1 n OK =, n 0La 2 2 m1 n1 m1 n1 n1 n (1 2q) sin + q cos n m1 n2 m1 n2 n1 n2 m2 m2 m2 k1 m2 k 2 1 m2 m2 m2 k1 m2 k Err = 2 2, 0La m2 k1 m2 k1 k1 k1 k q m2 k2 m2 k2 k1 k2 k (12) m2 m2 m1 n1 m1 n 1 m2 m 1 m1 n1 m1 n OK m 1n m 1n =, n 1La 2 n1 n (1 2q) sin + q cos2 11 11 n m1 n2 m1 n2 n1 n2 m2 m2 m2 k1 m2 k 2 2 1 m2 m2 m2 k1 m2 k Err =.

1La m2 k1 m2 k1 k1 k1 k q m2 k2 m2 k2 k1 k2 k СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) РАСШИРЕНИЕ ОБЛАСТИ СЕКРЕТНОСТИ Для подсчета информации Холево требуется знать собственные значения трех матриц:

0La = P r(0|0)OK + P r(1|0)Err = 0La 0La m2 + m2 m2 m2 m1 n1 + m2 k1 m1 n2 + m2 k 1 2 1 m2 m2 m2 + m2 m1 n1 m2 k1 m1 n2 m2 k 1 2 1 =, n2 + k m1 n1 + m2 k1 m1 n1 m2 k1 n1 n2 + k1 k n2 + k m1 n2 + m2 k2 m1 n2 m2 k2 n1 n2 + k1 k2 1La = P r(1|1)OK + P r(0|1)Err = 1La 1La 2 + m2 2 m2 m1 n1 m2 k1 m1 n2 m2 k m1 m (13) 2 m2 m2 m2 + m2 m1 n1 + m2 k1 m1 n2 + m2 k 1 2 1 =, n2 + k m1 n1 m2 k1 m1 n1 + m2 k1 n1 n2 + k1 k n2 + k m1 n2 m2 k2 m1 n2 + m2 k2 n1 n2 + k1 k2 m1 + m2 m2 m2 0 2 1 2 m2 m2 + m 1 m 0 La = (0La + 1La ) = 1 2 1 2.

n2 + k 0 0 n1 n2 + k1 k 2 n2 + k 0 0 n1 n2 + k1 k2 Собственные значения матриц 0La и 1La совпадают и равны 1 + 4c2 4, 1± µ1,2 = где для краткости введены обозначения (1 2q) sin =, (1 2q) sin2 + q cos2 + q q(cos2 + 1) =, (1 2q) sin2 + q cos2 + q q(1 2q) sin cos c=, (1 2q) sin2 + q cos2 + q а собственные значения оператора La равны (1 ± cos ), 1,2 = 4 cos2 + cos2 sin 1± 3,4 =.

1 + cos Из приведенных выражений легко получить формулу для величины Холево ({0La, 1La }) = i log i + µ1 log µ1 + µ2 log µ2. (14) i= На рисунке 4 сплошными линиями приведены границы области секретности для протокола с фазово-временным кодированием на плоскости (Q, q) для значений угла между информаци онными состояниями внутри базиса = /2 и = /4.

2.2 Внесение дополнительного шума Посмотрим, как на состояния в пространстве Евы будет действовать дополнительный шум, внесенный Алисой и Бобом. Если без шума Ева стоит перед задачей различения состояний (13), СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 80 КРОНБЕРГ 0.5 0. no optimization no optimization by blocks by blocks by noise by noise 0.4 0. by blocks and noise by blocks and noise 0.3 0. 0.2 0. 0.1 0. 0.0 0. 0.00 0.05 0.10 0.15 0.20 0.25 0.30 0.00 0.05 0.10 0.15 0.20 0.25 0. а б Рис. 4. Границы области секретности протокола квантового распределения ключей с фазово-времен ным кодированием: (а) ортогональный случай, (б) значение угла = /4. Сплошными линиями пока заны зависимости критической ошибки от контрольных отсчетов без использования предварительной обработки данных, штрихпунктирными линиями при внесении дополнительного шума, пунктирны ми линиями после блочного исправления ошибок, штриховыми линиями после сочетания методов предварительной обработки данных.

то после внесения шума, подобно тому, как это происходит в протоколе BB84, состояния Евы будут равны 0La = (1 p) P r(0|0)OK + P r(1|0)Err + p P r(1|1)OK + P r(0|1)Err 0La 0La 1La 1La (15) 1La = (1 p) P r(1|1)OK + P r(0|1)Err + p P r(0|0)OK + P r(1|0)Err 1La 1La 0La 0La Как видно, оператор плотности La = 1 (0La + 1La ) будет иметь тот же вид, что и без внесения шума, а собственные значения частичных состояний (15) изменятся. Для нахождения этих собственных значений необходимо решить алгебраические уравнения четвертой степени.

Методы решения подобных уравнений хорошо известны.

На рисунке 4 штрихпунктирной линией показана область секретности протокола с фазово временным кодированием при использовании дополнительного шума.

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

Ошибка Боба при исправлении ошибки блоками длины N дается аналогичным (6) выра жением QN Q=. (16) (1 Q)N + QN В то же время из-за неортогональности состояний (12) операторы плотности Евы после измерения Боба уже не будут представляться в виде суммы ортогональных состояний, как это было в случае протокола BB84. Выражение, аналогичное (7), принимает вид E = (1 Q)(OK )N + Q(Err )N, 0 0 E = (1 Q)(OK )N + Q(Err )N, 1 1 СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) РАСШИРЕНИЕ ОБЛАСТИ СЕКРЕТНОСТИ где OK и Err даются выражениями (12).

i Собственные значения этих операторов и оператора плотности La = 1 (0La + 1La ) вычис ляются численно. На рисунке 4 пунктирной линией показана граница области секретности для протокола с фазово-временным кодированием после оптимизации по блокам, длина которых N принимает значения от 1 до 4.

2.4 Комбинирование методов Так же, как и в случае протокола BB84, будем рассматривать случай блочного исправления ошибок, после которого следует внесение дополнительного шума. При сочетании этих мето дов предварительной обработки данных состояния перехватчика будут даваться выражением, подобным (10):

E = (1 p) (1 Q)(OK )N + Q(Err )N + p (1 Q)(OK )N + Q(Err )N, 0 0 0 1 E = (1 p) (1 Q)(OK )N + Q(Err )N + p (1 Q)(OK )N + Q(Err )N.

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

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

Автор выражает благодарность профессору С. Н. Молоткову за постановку задачи и по мощь в подготовке этой работы.

Список литературы [1] Acin A., Gisin N., and Scarani V. Coherent-pulse implementations of quantum cryptography protocols resistant to photon-number-splitting attacks // Phys. Rev. A. 2004. Vol. 69, 012309.

[2] Bae J., Acin A. Key distribution from quantum channel using two-way communication protocols // Phys. Rev. A. 2007. Vol. 75, 012334.

[3] Bennett C.H., Brassard G. Quantum Cryptography: Public Key Distribution and Coin Tossing // Proc. of IEEE Int. Conf. on Comput. Sys. and Sign. Proces. Bangalore, India: 1984.

Pp. 175–179.

[4] Kraus B., Gisin N., Renner R. Lower and Upper Bounds on secret-Key Rate for Quantum Key Distribution Protocols Using One-Way classical communication // Phys. Rev. Lett. 2005.

Vol. 95, 080501.

[5] Maurer U. Secret key agreement by public discussion from common information // IEEE Trans.

Inf. Theory. 1993. Vol. 39, Pp. 733–742.

СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 82 КРОНБЕРГ [6] Scarani V., Acin A., Ribordy G., Gisin N. Quantum Cryptography Protocols Robust against Photon Number Splitting Attacks for Weak Laser Pulse Implementations // Phys. Rev. Lett.

2004. Vol. 92, 057901.

[7] Кронберг Д.А., Молотков С.Н. Двухпараметрическая квантовая криптография на вре менных сдвигах, устойчивая к атаке с расщеплением по числу фотонов // ЖЭТФ.

2009. Т. 136. С. 650–683.

[8] Кулик С.П., Молотков С.Н., Маккавеев А.П. Комбинированный метод фазово-временно го кодирования // Письма в ЖЭТФ. 2007. Т. 85. С. 354–359.

[9] Молотков С.Н. О криптографической стойкости системы квантовой криптографии с фа зово-временным кодированием // ЖЭТФ. 2008. Т. 134. С. 39–64.

[10] Молотков С.Н., Тимофеев А.В. Явная атака на ключ в квантовой криптографии (про токол BB84), достигающая теоретического предела ошибки Qc 11 % // Письма в ЖЭТФ. 2007. T. 85. С. 632–637.

[11] Холево А.С. Введение в квантовую теорию информации. М.: МЦНМО, 2002.

СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) УДК 514. ОЦЕНКА РАДИУСА ПОКРЫТИЯ МНОГОМЕРНОЙ ЕДИНИЧНОЙ СФЕРЫ МЕТРИЧЕСКОЙ СЕТЬЮ, ПОРОЖДЕННОЙ СФЕРИЧЕСКОЙ СИСТЕМОЙ КООРДИНАТ c 2011 г. Т. С. Майская tmayskaya@nes.ru Кафедра системного анализа 1 Введение В данной статье изучается радиус покрытия многомерной единичной сферы (сферы на правлений) метрической сетью, порождаемой сферическими координатами. Анализ радиуса покрытия этой сети представляет большой практический интерес в связи с тем, что исполь зование сферических координат до последнего времени являлось единственным реализуемым способом построения более-менее равномерного покрытия сферы (здесь мы отвлекаемся от мало изученных эффективных сетей, генерируемых адаптивными методами аппроксимации выпуклых компактных тел [2, 3]). Направления, порождаемые сферическими координатами на сфере, используются, в частности, в неадаптивных алгоритмах полиэдральной аппроксима ции выпуклых компактных тел (например, множеств достижимости динамических систем [7]) и т.д.

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

Пусть E m m-мерное евклидово пространство с обычными скалярным произведением, нормой и метрикой.

Рассмотрим сферическую систему координат в E m [1].

m x =r sin i, i= m1 (1) sin i при k = 2, 3,..., m 1, x = r cos k k i=k xm = r cos m1, в которой r 0, а сферические углы 1, 2,..., m2 изменяются в пределах 0 i и 0 m1 2.

Тогда единичная сфера (сфера направлений) S m1 E m задается соотношением (1) при r = 1. Пусть m1 m = sin i,..., cos k1 sin i,..., cos m1.

i=1 i=k Под сетью, порождаемой сферическими координатами на единичной сфере S m1, будем пони мать конечное подмножество S m1 :

MSph = { : i = si i, si = 0, 1,..., Si, i = 1, 2,..., m 2, m1 = l, l = 0, 1,..., L}, (2) Работа была частично поддержана ФЦП Научные и научно-педагогические кадры инновационной Рос сии (государственный контракт 2010-1.2.1-000-029-072) 84 МАЙСКАЯ где Si = i, i = 1,..., m 2, L = натуральные числа, причем углы i, i = 1,..., m 2, и удовлетворяют следующим условиям:

, i = 1,..., m 2, 0 i 0.

4 Под радиусом покрытия сферы S m1 произвольным конечным множеством M S m будем понимать величину M, S m1 := min : S m1 (M ), где (M ) = {1 + 2 : 1 M, 2 }.

m1 найдется M, что Заметим, что для любого S, то есть M образует -сеть на S m1 с = M, S m1.

Статья имеет следующую структуру. В разделе 2 формулируются основные результаты, связанные с построением верхней и нижней оценок радиуса покрытия сферы сетями рассмат риваемого типа (2). При этом показывается, что в асимптотике при стремлении угла к нулю эти оценки совпадают. В разделе 3 полученные оценки сравниваются с оценками для опти мальных сетей на единичной сфере. Полученные результаты конкретизируются для отдельных размерностей, в том числе и при m. В разделе 4 приводятся доказательства основных результатов, сформулированных в разделе 2.

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

Теорема 1. Для радиуса покрытия сети MSph, определенной в (2), справедлива следующая верхняя оценка:

m i MSph, S m1 2 m1 cos cos. (3) 2 i= Теорема 2. При выполнении условия, s = 1,..., m 2, 0 s m для радиуса покрытия сети MSph, определенной в (2), справедлива следующая нижняя оценка:

1 1 2 32 MSph, S m1 1 cos + 1 cos · 2... cos + cos 22 2 2 1 3 33 · + 1 cos... · cos + cos 2 2 2 1 m2 3m2 m · + 1 cos · cos + cos 2 2 2 1 3 · + 1 cos cos + cos. (4) 2 2 2 Доказательства этих теорем трудоемки, поэтому они отнесены в конец статьи.

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

СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) РАДИУС ПОКРЫТИЯ СФЕРЫ СЕТЬЮ, ПОРОЖДЕННОЙ СФЕРИЧЕСКОЙ СИСТЕМОЙ КООРДИНАТ Следствие 1. Пусть 1 = 2 =... = m2 =. Тогда 2 MSph, S m1 + O ( 2 + 2 )2.

(m 2) + = (5) 4 Доказательство. Из формулы (3), используя разложение в ряд Тейлора, сразу получаем при ближенную оценку m i MSph, S m1 2 m1 cos cos = 2 i= 2 + O 4 1 + + O = 2 m 1 (m 2) 1 = 8 2 + O 4 + O 4.

(m 2) + = 4 Для получения нижней оценки воспользуемся формулой (4). Заметим, что ее можно написать в следующем рекурсивном виде:

B1 = 1 cos ;

1 i 3i i Bi = Bi1 · + 1 cos, i = 2, 3,..., m 2;

cos + cos 2 2 2 1 3 M, S m1 2 Bm2 · + 1 cos cos + cos.

2 2 2 Используя разложение Тейлора, отсюда получаем:

+ O 4 ;

B1 = 5 2 2 + O 4 + O 4 + O 4, Bi = Bi1 · 1 i = 2, 3,..., m 2.

+ = Bi1 + 8 8 Отсюда сразу следует нижняя оценка радиуса покрытия:

52 MSph, S m1 + O 4 + O 2 Bm2 · 1 + = 8 2 · (m 2) + O 4 + O + O =2 + = 8 2 + O 4 + O 4 + O 2 2.

(m 2) + = 4 В следующем утверждении полученная оценка уточняется для случая =.

Обозначим через MSph S m1 сеть (2) мощности k, для которой 1 = 2 =... = m2 = k,m = =.

Следствие 2. Имеет место оценка m 2 m k,m m · MSph, S lim k =. (6) m k СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 86 МАЙСКАЯ Доказательство. Так как при малом угле из (2) следует m1 m 2 m Si · k=L = m1, i= то, используя утверждение Следствия 1, получаем:

2 MSph, S m k,m + O ( 2 + 2 )2 = (m 2) + = 4 2 m m (m 1) + O 4 · =.

m 4 k 3 Сравнение с оценками для оптимальных сетей Оценки, полученные в предыдущем разделе, позволяют сравнить сеть на S m1, порожден ную сферической системой координат, с оптимальной сетью, которая определяется следующим произвольная конечная сеть на S m1, ее мощность обозначим через |M |.

образом. Пусть M k,m Сеть на S m1 мощностью k называется оптимальной [4] и обозначается Mopt, если она имеет наименьший радиус покрытия среди сетей на сфере, имеющих ту же мощность, то есть k,m Mopt, S m1 = min M, S m1 : M S m1, |M | = k.

Рассмотрим также минимальное число точек в сети при фиксированном радиусе покрытия:

k,m kopt () := min k : Mopt, S m m. (7) Из [3] следуют асимптотические оценки для оптимальных сетей:

m m k,m Mopt, S m · · m lim k =, (8) m m k m lim m1 · kopt () = m · m1, (9) m m объем единичного шара в пространстве E m, m = (m rm )r где m = = mm (1+ m ) r= площадь поверхности единичного шара в пространстве E m, m плотность редчайшего по крытия E m единичными шарами [5].

Пусть kSph () := min{k : MSph, S m m k,m }. (10) Теорема 3. Имеют место оценки k,m Mopt, S m1 mm m1 m · lim = (11) 2m1 m k,m k MSph, S m и m mm m1 2m kopt () lim = m1. (12) m kSph () 0 m1 m1 (m 1) СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) РАДИУС ПОКРЫТИЯ СФЕРЫ СЕТЬЮ, ПОРОЖДЕННОЙ СФЕРИЧЕСКОЙ СИСТЕМОЙ КООРДИНАТ Доказательство. Из следствия 2 сразу получаем:

m 1 k,m m · MSph, S · lim k =2, (13) m1 m k m m1 (m 1) m1 m · kSph () = lim. (14) 2m Первая оценка теоремы следует из (13) и (8). Вторая оценка теоремы следует из (14) и (9).

Проанализируем выражения (11) и (12).

Для малых размерностей пространства оценки (11) и (12) принимают вид :

m 2 3 4 1 k,m Mopt,S m 2 4 3 23 4 0,70 0,56 0, lim 1 4 2 3 15 2 k,m 3 k MSph,S m1 (4) 3 m kopt () 23 5 8 0,49 0,17 0, lim 1 km () 3 2 3 15 2 3 3 12 0 Sph Из таблицы видно, что сеть, порожденная сферической системой координат, при m сильно уступает оптимальной сети. Хотя в трехмерном пространстве для покрытия единичной сферы требуется только в два раза большее число узлов, чем при использовании оптимальной сети, для пятимерного пространства узлов потребуется уже в 20 раз больше.

Покажем, что при увеличении размерности пространства сеть, порожденная сферической системой координат, становится неприемлемой для более-менее равномерного покрытия еди ничной сферы. Для этого рассмотрим асимптотическое поведение выражений (11) и (12) при m.

Теорема 4. Имеют место оценки k,m Mopt, S m 2e lim sup m · lim (15) k,m k MSph, S m m и m kopt () m m5 · · lim m · · e2.

lim sup m (16) 2 ln m 0 kSph () m m Доказательство. Сначала найдем оценку для m1. Учитывая, что m m =, m 1+ получаем: p p p 2p =, 2p+1, p 1;

1 = 2;

p! (p + 1)! p!

m = 2p:

p p!

2p 2 m = ;

=, = p 1 2 m1 2p1 p!

2 8 Здесь используются формулы 1 = 2, 2 =, 3 =, 4 =, 5 =, а также оценки для m, взятые 3 2 2 2 5 из [6]: 1 = 1, 2 = 27, 3, 4.

24 СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 88 МАЙСКАЯ m = 2p + 1: p! p 2p+ m = =.

p! p m1 2p Таким образом, m m, 2.

m В [6] показано, что m m ln m + m ln ln m + 5m, m 24.

Откуда получаем:

m m 7m ln m, 24.

Учитывая это, а также следующий известный факт:

lim n n = 1, n получаем:

k,m Mopt, S m lim sup m · lim = k,m k MSph, S m m mm m1 m1 · m· = lim sup 2m1 m m 7(m 1)m ln(m 1) m1 2m 2e · lim sup = 2 m m и m kopt () m m · · lim m lim sup m = 2 ln m 0 kSph () m mm m1 2m m m · · = lim sup m ln m m1 m1 (m 1) m m 7 m · 2m2 ln(m 1) m m · · lim sup m = m 2 ln m m1 (m 1) 2 m m 7 2 · ln(m 1) · m 2 7 · · e2.

= lim sup = m 4 ln m · (m 1) m m kopt () Из теоремы 4 видно, что при больших размерностях пространства выражение lim km () 0 Sph стремится к нулю со скоростью примерно mm, что говорит о крайней неэффективности ис пользования сферических координат для покрытия сферы при больших m.

4 Доказательства теорем 1 и Лемма 1. Для произвольных векторов m1 m MSph, 1 = sin i,..., cos k1 sin i,..., cos m i=1 i=k СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) РАДИУС ПОКРЫТИЯ СФЕРЫ СЕТЬЮ, ПОРОЖДЕННОЙ СФЕРИЧЕСКОЙ СИСТЕМОЙ КООРДИНАТ m1 m S m 2 = sin i,..., cos k1 sin i,..., cos m i=1 i=k справедливо (cos(1 1 ) 1) (cos(2 2 ) cos(2 + 2 )) + (cos(2 2 ) 1) 1, 2 =...

(cos(3 3 ) cos(3 + 3 )) + (cos(3 3 ) 1)...

(cos(m2 m2 ) cos(m2 + m2 )) + (cos(m2 m2 ) 1) (cos(m1 m1 ) cos(m1 + m1 )) + cos(m1 m1 ). (17) Доказательство.

m1 m 1, 2 = sin i sin i +... + cos k1 cos k1 sin i sin i +... + cos m1 cos m1.

i=1 i=k Применяя формулу косинуса разности углов для первых двух слагаемых, имеем:

m1 m 1, 2 = cos(1 1 ) sin i sin i + cos 2 cos 2 sin i sin i +... + i=2 i= m + cos k1 cos k1 sin i sin i +... + cos m1 cos m1.

i=k Далее воспользуемся формулой (cos( ) cos( + )), sin sin = для первого слагаемого:

m1 m1 m cos(1 1 ) sin i sin i = (cos(1 1 ) 1) sin i sin i + sin i sin i = i=2 i=2 i= m1 m = (cos(1 1 ) 1) (cos(2 2 ) cos(2 + 2 )) sin i sin i + sin i sin i.

i=3 i= В результате получим:

m = (cos(1 1 ) 1) (cos(2 2 ) cos(2 + 2 )) 1, 2 sin i sin i + i= m1 m + sin i sin i + cos 2 cos 2 sin i sin i +... + i=2 i= m + cos k1 cos k1 sin i sin i +... + cos m1 cos m1.

i=k СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 90 МАЙСКАЯ Опять применим формулу косинуса разности для второго и третьего слагаемых:

m 1, 2 = (cos(1 1 ) 1) (cos(2 2 ) cos(2 + 2 )) sin i sin i + i= m1 m + cos(2 2 ) sin i sin i +... + cos k1 cos k1 sin i sin i +... + cos m1 cos m1.

i=3 i=k Далее объединяем первое и второе слагаемые, вынося за скобку общий множитель m sin i sin i, i= получая:

m (cos(1 1 ) 1) (cos(2 2 ) cos(2 + 2 )) + cos(2 2 ) sin i sin i = i= m (cos(1 1 ) 1) (cos(2 2 ) cos(2 + 2 )) + cos(2 2 ) = sin i sin i + i= m + sin i sin i = i= (cos(1 1 ) 1) (cos(2 2 ) cos(2 + 2 )) + cos(2 2 ) = m1 m (cos(3 3 ) cos(3 + 3 )) · sin i sin i + sin i sin i.

i=4 i= Выражение для скалярного произведения примет вид:

(cos(1 1 ) 1) (cos(2 2 ) cos(2 + 2 )) + cos(2 2 ) 1, 2 = m (cos(3 3 ) cos(3 + 3 )) · sin i sin i + i= m1 m + sin i sin i + cos 3 cos 3 sin i sin i +... + i=3 i= m + cos k1 cos k1 sin i sin i +... + cos m1 cos m1.

i=k Действуя аналогично, то есть применяя поочередно формулы косинуса разности и произведе СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) РАДИУС ПОКРЫТИЯ СФЕРЫ СЕТЬЮ, ПОРОЖДЕННОЙ СФЕРИЧЕСКОЙ СИСТЕМОЙ КООРДИНАТ ния синусов, получаем в результате следующее выражение для скалярного произведения:

(cos(1 1 ) 1) (cos(2 2 ) cos(2 + 2 )) + (cos(2 2 ) 1) 1, 2 =...

(cos(3 3 ) cos(3 + 3 )) + (cos(3 3 ) 1)...

(cos(m3 m3 ) cos(m3 + m3 )) + (cos(m3 m3 ) 1) (cos(m2 m2 ) cos(m2 + m2 )) + (cos(m2 m2 ) 1) · sin m1 sin m1 + + sin m1 sin m1 + cos m1 cos m1.

Откуда получаем равенство (17).

Доказательство теоремы 1. Зафиксируем произвольные векторы 1 MSph, 2 S m1 :

m1 m 1 = sin i,..., cos k1 sin i,..., cos m1, i=1 i=k m1 m 2 = sin i,..., cos k1 sin i,..., cos m1.

i=1 i=k Для доказательства теоремы достаточно найти верхнюю оценку для квадрата нормы разности векторов 1 и 2.

Согласно равенству (17), 1 2 = 2 2 1, 2 = =22 (cos(1 1 ) 1) (cos(2 2 ) cos(2 + 2 )) + (cos(2 2 ) 1)...

(cos(3 3 ) cos(3 + 3 )) + (cos(3 3 ) 1)...

(cos(m2 m2 ) cos(m2 + m2 )) + (cos(m2 m2 ) 1) (cos(m1 m1 ) cos(m1 + m1 )) + cos(m1 m1 ). (18) i при i = 1, 2,..., m 2, то Для начала заметим, что так как 0 i, (cos(i i ) cos(i + i )) = sin i sin i i = 1, 2,..., m 2.

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

(cos(1 1 ) 1) (cos(2 2 ) + 1) + (cos(2 2 ) 1) 1, 2...

(cos(3 3 ) + 1) + (cos(3 3 ) 1)...

(cos(m2 m2 ) + 1) + (cos(m2 m2 ) 1) (cos(m1 m1 ) + 1) + cos(m1 m1 ), СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 92 МАЙСКАЯ а для квадрата нормы разности векторов 1 2 (1 cos(1 1 )) (cos(2 2 ) + 1) + (1 cos(2 2 )) 2...

(cos(3 3 ) + 1) + (1 cos(3 3 ))...

(cos(m2 m2 ) + 1) + (1 cos(m2 m2 )) (cos(m1 m1 ) + 1) + (1 cos(m1 m1 )).

Теперь наложим ограничение на разность углов:

i i i i i = 1,..., m 2;

m1 m,. (19) 2 2 2 Тогда 1 1 1 2 1 cos (1 + 1) + 1 cos 2...

22 1 3 1 m2 1 (1 + 1) + 1 cos... · (1 + 1) + 1 cos · (1 + 1) + 1 cos.

2 2 2 2 2 Упрощая полученное выражение, в итоге имеем:

m i 1 2 2 m1 cos cos. (20) 2 i= Итак, мы получили, что для произвольных векторов 1 MSph, 2 S m1, введенных в начале доказательства, для которых выполнено ограничение на разность углов (19) спра ведлива оценка (20). Из этого следует, что для произвольного вектора 2 S m1 всегда найдется такой вектор 1 MSph, что выполнена оценка (20). Таким образом, верхняя оценка (3) для радиуса покрытия доказана.

Доказательство теоремы 2. Зафиксируем произвольные векторы 1 MSph, 2 S m1 та ким же образом, как это было сделано в доказательстве теоремы 1. Пусть |i i | = i, i = 1,..., m 2;

|m1 m1 | = ;

2 2 (21) i i +, i = 1,..., m 2;

m1 +.

i 2 2 2 2 2 2 2 Тогда из формулы (17) получаем:

1 1 2 1 cos(2 + 2 ) + cos 1 1, 2 =... cos cos 2 2 2 1 3 cos(3 + 3 ) + cos 1...

cos 2 2 1 m2 m cos(m2 + m2 ) + cos 1 cos 2 2 1 cos cos(m1 + m1 ) + cos.

2 2 СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) РАДИУС ПОКРЫТИЯ СФЕРЫ СЕТЬЮ, ПОРОЖДЕННОЙ СФЕРИЧЕСКОЙ СИСТЕМОЙ КООРДИНАТ Заметим также, что i i + i = 2i ±, i = 1,..., m 2;

m1 + m1 = 2m1 ± ;

2 3i i 3i 3 2i ±, i = 1,..., m 2;

2m1 ± + +.

2 2 2 2 2 Следовательно, 3i 3i cos = cos, i = 1,..., m 2;

cos (i + i ) 2 3 cos = cos cos (m1 + m1 ).

2 Откуда получаем следующую оценку на скалярное произведение:

1 1 2 32 1 1 1, 2... cos cos + cos + cos 2 2 2 2 1 3 33 1...

cos + cos + cos 2 2 2 1 m2 3m2 m 1 cos + cos + cos 2 2 2 1 3 cos + cos + cos.

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

1 2 32 1 2 1 cos + 1 cos 2... cos + cos 2 2 2 1 3 33 + 1 cos...

cos + cos 2 2 2 1 m2 3m2 m + 1 cos cos + cos 2 2 2 1 3 + 1 cos cos + cos. (22) 2 2 2 Итак, мы получили, что для произвольных векторов 1 MSph, 2 S m1, введенных в начале доказательства, для которых выполнено ограничение (21), справедлива оценка (22).

Заметим, что вектор 2 S m1, для которого существует такой вектор 1 MSph, что выполняются ограничения (21), всегда существует. Зафиксируем такой вектор 2 S m1.

Покажем, что оценка (22) справедлива для любого вектора 1 MSph.

С этого момента будем считать, что выполнено следующее ограничение на углы i :

, i = 1,..., m 2, 0 i m Скалярное произведение векторов рассмотрим как функцию от (1,..., m1 ):

1, 2 = m1 m = sin i sin i +... + cos k1 cos k1 sin i sin i +... + cos m1 cos m1 = i=1 i=k = f (1,..., m1 ).

СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 94 МАЙСКАЯ Покажем, что максимум этой функции на множестве {i = si i, si = 0, 1,..., Si, i = 1, 2,..., m 2, m1 = l, l = 0, 1,..., L} (23) достигается на векторе (1,..., m1 ) таком, что i |i i | = i = 1,..., m 2;

m1 m1 =,.

2 Запишем необходимое условие экстремума по переменной 1 :

m = (cos 1 sin 1 sin 1 cos 1 ) f1 (1, 2,..., m1 ) sin i sin i = 0.

i= m1 Если i=2 sin i sin i = 0, то функция f не зависит от значения угла 1. Поэтому в этом случае можно брать любое значение 1, в частности такое, что |1 1 | =.

m1 i=2 sin i sin i = 0. Тогда Пусть sin(1 1 ) = 0 = 1 = 1.

С учетом (21) и (23) имеем:

1 |1 1 | =.

Запишем необходимое условие экстремума по переменной 2 :

f2 (1, 2, 2..., m1 ) = = (sin 1 sin 1 cos 2 sin 2 + cos 1 cos 1 cos 2 sin 2 sin 2 cos 2 ) m sin i sin i = 0.

i= m1 Если i=3 sin i sin i = 0, то функция f не зависит от значения угла 2. Поэтому в этом случае можно брать любое значение 2, в частности такое, что |2 2 | =.

m1 i=3 sin i sin i = 0. Тогда Пусть cos(1 1 ) cos 2 sin 2 sin 2 cos 2 = 0 = cos cos 2 sin 2 = sin 2 cos 2.

Покажем, что 1 2 cos cos 2 sin 2 = sin 2 cos 2 = 2 2 +.

2 2 Действительно, пусть cos 2 sin 2 sin 2 cos 2.

g(2 ) = cos Тогда если 2, то 2 2 1 2 sin 2 sin 2 + g 2 + = cos cos 2 + cos 2 2 2 2 2 1 2 cos sin 2 sin 2 + 2 + + cos cos = 0, 2 2 2 2 2 2 2 СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) РАДИУС ПОКРЫТИЯ СФЕРЫ СЕТЬЮ, ПОРОЖДЕННОЙ СФЕРИЧЕСКОЙ СИСТЕМОЙ КООРДИНАТ 2 1 2 g 2 cos 2 sin 2 sin = cos cos 2 = 2 2 2 1 2 1 2 2 1 sin 2 2 2 = cos sin + cos cos 2 2 2 2 2 2 2 1 2 1 2 1 sin cos sin + cos cos = 2 2 2 2 2 2 1 2 1 2 1 cos = cos sin + cos sin 2 2 2 2 2 1 1 1 2 0 1 2 cos 1 cos cos 1 cos = sin 0, 2 3 2 2 2 m 2 + Если 2, то 2 2 1 2 sin 2 sin 2 + g 2 + = cos cos 2 + cos 2 = 2 2 2 1 2 1 2 2 2 = cos 1 sin 2 + sin + cos cos 2 + 2 + + 2 2 2 2 2 2 2 1 2 1 2 cos 1 sin sin + cos + cos + = 2 2 2 2 2 2 1 2 1 2 2 1 = cos + 1 cos sin cos sin cos 2 2 2 2 2 2 1 2 sin 1 cos 0, 2 2 2 1 2 g 2 cos 2 sin 2 sin = cos cos 2 2 2 2 2 1 2 2 cos sin 2 sin cos cos = 0.

2 2 2 2 2 2 2 Мы получили, что g 2 + 2 0 и g 2 0. Откуда следует, что нуль функции 2 g(2 ) принадлежит указанному отрезку:

2 2 2 2 +.

2 Следовательно, 2 |2 2 | =.

Покажем, что аналогичный результат верен и в случае i, i = 3,..., m 1.

Пусть j |j j | =, j = 1,..., i 1.

Запишем необходимое условие экстремума по переменной i :

fi (1,..., i1, i, i+1,..., m1 ) = m sin i cos i = h(1,..., i1 ) cos i sin i sin k sin k = 0, k=i+ где i1 i h(1,..., i1 ) = sin k sin k + cos 1 cos 1 sin k sin k +... + k=1 k= + cos i2 cos i2 sin i1 sin i1 + cos i1 cos i1.

СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 96 МАЙСКАЯ С одной стороны, i1 i 1 ) h(1,..., i1 ) = cos (1 sin k sin k + cos 2 cos 2 sin k sin k +... + k=2 k= + cos i2 cos i2 sin i1 sin i1 + cos i1 cos i i1 i sin k sin k + cos 2 cos 2 sin k sin k +... + k=2 k= + cos i2 cos i2 sin i1 sin i1 + cos i1 cos i1 = i1 i = cos (2 2 ) sin k sin k + cos 3 cos 3 sin k sin k +... + k=3 k= + cos i2 cos i2 sin i1 sin i1 + cos i1 cos i1...

i sin i1 sin i1 + cos i1 cos i1 = cos.

С другой стороны, пользуясь тем, что, i = 1,..., m 2, 0 i m имеем i1 i h(1,..., i1 ) = sin k sin k + cos 1 cos 1 sin k sin k +... + k=1 k= + cos i2 cos i2 sin i1 sin i1 + cos i1 cos i1 = (cos(1 1 ) 1) (cos(2 2 ) cos(2 + 2 )) + (cos(2 2 ) 1) =...

1 (cos(3 3 ) cos(3 + 3 )) + (cos(3 3 ) 1)...

1 cos(i2 i2 ) cos(i2 + i2 ) + cos(i2 i2 ) 1 cos(i1 i1 ) cos(i1 + i1 ) + cos(i1 i1 ) i1 i1 i1 j j i j i+2 1 i+2=1 cos.

2(m 2) 2 8 8 j=1 j=1 j= Таким образом, 1 i h(1,..., i1 ) cos.

2 m1 Далее действуем аналогично случаю i = 2. Полагая k=i+1 sin k sin k = 0, имеем:

h(1,..., i1 ) cos i sin i sin i cos i = 0.

Покажем, что i i i h(1,..., i1 ) cos i sin i = sin i cos i = i i +, 2 СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) РАДИУС ПОКРЫТИЯ СФЕРЫ СЕТЬЮ, ПОРОЖДЕННОЙ СФЕРИЧЕСКОЙ СИСТЕМОЙ КООРДИНАТ где через m1 обозначен угол для того, чтобы не рассматривать отдельно случай i = m 1, который по сути ничем не отличается от остальных случаев.

Пусть g(i ) = h(1,..., i1 ) cos i sin i sin i cos i.

i i Тогда если 2, то 2 i i i sin i sin i + g i + = h(1,..., i1 ) cos i + cos i 2 2 i i i + +, h(1,..., i1 ) 2 2 2 i h(1,..., i1 ) cos sin i sin i + cos = 0, 2 2 i i i g i = h(1,..., i1 ) cos i sin i sin i cos i = 2 2 i i = h(1,..., i1 ) sin + h(1,..., i1 ) 1 sin i cos i 2 i i 1 i i i, h(1,..., i1 ) cos 2 2 2 22 i i i h(1,..., i1 ) sin + h(1,..., i1 ) 1 sin cos = 2 2 2 2 i i i 1 i i = h(1,..., i1 ) sin + h(1,..., i1 ) 1 cos sin 1 cos sin 0, 2 2 2 2 2 i i + Если 2, то 2 i i i sin i sin i + g i + = h(1,..., i1 ) cos i + cos i = 2 2 i i = h(1,..., i1 ) sin + h(1,..., i1 ) 1 sin i + cos i 2 i i 1 i + i + + i, h(1,..., i1 ) cos 2 2 2 2 2 i i i h(1,..., i1 ) sin + h(1,..., i1 ) 1 sin + cos + = 2 2 2 2 i i i 1 i i = h(1,..., i1 ) sin + 1 h(1,..., i1 ) cos sin sin 1 cos 0, 2 2 2 2 2 i i i g i = h(1,..., i1 ) cos i sin i sin i cos i 2 2 i i i, h(1,..., i1 ) 2 2 2 i h(1,..., i1 ) cos sin i sin i cos = 0.

2 2 Мы получили, что g i + i i 0 и g i 0. Откуда следует, что нуль функции g(i ) 2 принадлежит указанному отрезку:

i i i i i +.

2 Следовательно, i |i i | =.

СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 98 МАЙСКАЯ Таким образом, мы доказали, что для некоторого фиксированного вектора m1 m S m 2 = sin i,..., cos k1 sin i,..., cos m i=1 i=k и для любого вектора MSph существует такой вектор m1 m MSph, 1 = sin i,..., cos k1 sin i,..., cos m i=1 i=k что выполняется 2 1 2, причем i |i i | =, i = 1,..., m 2;

|m1 m1 | =.

2 Получили, что оценка (22) справедлива для любого вектора 1 MSph, а значит нижняя оценка (4) для радиуса покрытия доказана.

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

Список литературы [1] Торп Дж. Начальные главы дифференциальной геометрии. Изд. Платон: 1982.

[2] Лотов А. В., Бушенков В. А., Каменев Г. К., Черных О. Л. Компьютер и поиск компро мисса. Метод достижимых целей. М.: Наука, 1997.

[3] Каменев Г. К. Полиэдральная аппроксимация шара Методом Глубоких Ям с оптимальным порядком роста мощности гранной структуры. // В кн.: Тр. Межд конф. Численная гео метрия, построение расчетных сеток и высокопроизводительные вычисления. М.: ВЦ РАН, 2010. С. 47–52.

[4] Каменев Г. К. Оптимальные адаптивные методы полиэдральной аппроксимации выпуклых тел. М.: ВЦ РАН, 2007.

[5] Роджерс К. Укладки и покрытия. М.: Мир, 1968.

[6] Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. Т. 1. М.: Мир, 1990.

[7] Самсонов С. П. Восстановление выпуклого множества по его опорной функции с заданной точностью // Вестн. МГУ. Сер. 15. Вычисл. матем. и кибернетика. 1983. № 1. С. 68– 71.

СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) УДК 512.624. О КРИПТОАНАЛИЗЕ LILI-128, ОСНОВАННОМ НА ЧАСТИЧНОМ ОПРОБОВАНИИ И МОНОМИАЛЬНОЙ СОВМЕСТНОСТИ СИСТЕМ ПОЛИНОМИАЛЬНЫХ УРАВНЕНИЙ c 2011 г. А. С. Мелузов asmeluzov@cs.msu.ru, asmelouzov@mail.ru Кафедра математической кибернетики 1 Введение Задача решения систем полиномиальных булевых уравнений является актуальной для мно гих разделов математики. В теории конечных автоматов, теории кодирования и криптологии возникают задачи изучения и решения систем булевых уравнений. Задача решения произ вольной системы полиномиальных булевых уравнений является NP-трудной [1]. Но, посколь ку в теории NP-полных задач сложность оценивается в худшем случае, то теоретический и практический интерес представляет разработка эффективных алгоритмов для конкретных классов систем булевых уравнений.


Предлагаются различные методики, в том числе, построение с помощью алгоритма Бух бергера или алгоритмов F4 и F5, разработанных Ж.-К. Фажере [2, 3], базиса Грёбнера идеала, описываемого системой уравнений [4];

линеаризация системы с использованием дополнитель ных приемов повышения эффективности [5–10]. Для некоторых частных классов систем раз работаны алгоритмы решения, использующие быстрый обход дерева решений системы [11,12], а также ассоциативные принципы использования памяти [13].

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

В настоящей статье предлагается метод решения систем булевых уравнений, основанный на частичном опробовании и использовании мономиальной совместности редуцированных систем для определения ключа потокового шифра LILI-128 [15].

2 Описание шифратора LILI-128 и постановка задачи 2.1 Потоковый шифратор LILI- Потоковый шифратор LILI-128 состоит из двух фильтрующих генераторов (39-разрядный LFSRc (fc ) и 89-разрядный LFSRd (fd )), первый из которых управляет режимом работы вто рого. Ключом шифратора является начальное заполнение регистров сдвига фильтрующих генераторов, а в качестве гаммирующей последовательности используется выходная последо вательность второго фильтрующего генератора.

Первый фильтрующий генератор состоит из линейного регистра сдвига LFSRc и филь трующей функции fc. Выходная последовательность данного генераторов определяет число тактов (1, 2, 3 или 4), которое должен совершить второй фильтрующий генератор LFSRd (fd ).

При этом, элементы LILI-128 имеют следующие параметры:

линейный регистр обратной связи с полиномом обратных связей 39 • LFSRc 33 31 17 15 14 2 1;

100 МЕЛУЗОВ • фильтрующая функция управляющего генератора fc : GF(2)2 GF(4), fc = 2u12 + u20 + + 1. Значение функции fc на каждом такте работы шифратора определяет, сколько так тов работы совершит линейный регистр обратной связи второго фильтрующего генера тора;

линейный регистр обратной связи с полиномом обратных связей 89 • LFSRd 80 55 53 42 39 1;

• фильтрующая функция fd : GF(2)10 GF(2), которая в описании шифратора была за дана таблицей, но по таблице можно построить соответствующий полином степени 6:

fd (x0, x1, x3, x7, x12, x20, x30, x44, x65, x80 ) = = x12 + x7 + x3 + x1 + x80 x20 + x80 x7 + x65 x3 + x65 x0 + x44 x1 + x44 x0 + x30 x20 + + x80 x65 x12 + x80 x65 x7 + x80 x65 x3 + x80 x65 x1 + x80 x44 x7 + x80 x44 x3 + x80 x30 x20 + + x80 x30 x12 + x80 x30 x7 + x65 x44 x20 + x65 x44 x3 + x65 x30 x20 + x65 x30 x7 + x65 x30 x3 + + x80 x65 x44 x20 + x80 x65 x44 x7 + x80 x65 x44 x3 + x80 x65 x44 x0 + x80 x65 x30 x20 + + x80 x65 x30 x7 + x80 x65 x30 x1 + x80 x44 x30 x12 + x80 x44 x30 x3 + x65 x44 x30 x7 + + x65 x44 x30 x1 + x65 x30 x20 x12 + x65 x30 x20 x7 + + x80 x65 x44 x30 x7 + x80 x65 x44 x30 x3 + x80 x65 x30 x20 x12 + + x80 x65 x30 x20 x7 + x65 x44 x30 x20 x12 + x65 x44 x30 x20 x7 + + x80 x65 x44 x30 x20 x12 + x80 x65 x44 x30 x20 x7.

Схема работы шифратора приведена на рисунке 1.

1...... LFSRc fc 40...... LFSRd fd Рис. 1. Схема работы шифратора LILI-128.

Отметим здесь одну интересную особенность работы двух регистров LILI-128, доказанную в работе [14].

Лемма 1. После каждых c = 239 1 тактов работы регистра LFSRc, регистр LFSRd совершит ровно d = 5 · 238 1 тактов.

2.2 Описание атаки Пусть c(t) последовательность бит шифрованного текста, полученная в результате по битового сложения битов открытого текста u(t) и бит шифрующей последовательности (t), вырабатываемой шифратором. В таком случае, если нам известна последовательность c(t), 1 t m (например, передаваемая по незащищенному каналу связи), и, кроме того, известна последовательность бит открытого текста u(t), 1 t m, то мы можем восстановить биты шифрующей последовательности (t) = c(t) u(t), 1 t m (m количество известных соответствий бит открытого и шифрованного текста).

Задача состоит в восстановлении по известной части шифрующей последовательности ис ходного значения ключа LILI-128 (то есть исходного заполнения линейных регистров сдвига).

СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) О КРИПТОАНАЛИЗЕ LILI-128 Успешная реализация атаки, позволит восстановить шифрующую последовательность лю бой необходимой длины и, следовательно, по шифрованному тексту восстановить весь откры тый текст.

Существуют различные подходы к криптоанализу потоковых шифров и, в частности, LILI 128. В следующем разделе рассмотрены некоторые из них.

3 Существующие подходы к криптоанализу LILI- По вопросам, связанным с криптоанализом LILI-128, за прошедшее с момента опубликова ния описания шифратора время было опубликовано значительное число работ. Сами авторы шифратора в работе [15] утверждают, что оценка трудоемкости восстановления ключа по из вестным шифрованному и соответствующему ему открытому тексту не ниже 2112 операций.

Необходимо отметить, что в работе [16] была отмечена крайне низкая стойкость LILI- к атакам со связанными ключами, однако, значительно интереснее рассматривать другую атаку, не требующую доступа к самому шифратору.

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

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

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

Рассмотрим существующие подходы подробнее.

В работе [18] предложен алгебраический метод криптографического анализа LILI-128.

Предлагается строить систему булевых алгебраических уравнений от переменных ключа. Ос новная идея статьи заключается в том, чтобы не использовать имеющие алгебраическую сте пень 6 уравнения вида fd (Li (x1, x2,..., x89 )) = i, где L(x1, x2,..., x89 ) линейный оператор, определяемый полиномом обратных связей LFSRd, а i i-й бит гаммирующей последовательности (выходная последовательность фильтрующе го генератора LFSRd (fd )).

Вместо этого предлагается использовать уравнения одного из следующих трех видов:

fd (Li (x1, x2,..., x89 )) · g(Li (x1, x2,..., x89 )) = i · g(Li (x1, x2,..., x89 )), 0 = g(Li (x1, x2,..., x89 )), fd · g 0, i = 1, i i fd (L (x1, x2,..., x89 )) · g(L (x1, x2,..., x89 )) = 0, i = 0, где g аннигилятор функции f, подобранный таким образом, чтобы степень уравнения была не выше 4. В работе [18] обозначено, что для функции fd для любого значения i можно по строить 14 линейно независимых уравнений степени не выше 4. При любом значении бита гам мирующей последовательности для составления системы мы сможем использовать 14 линейно независимых уравнений. Благодаря такому подходу мы получим в 14 раз больше уравнений в системе. Кроме того, поскольку их степень не будет превышать 4, то максимальное количе ство мономов в построенной таким образом системе равно 4 221. Предполагается, i=1 i что для успешного применения метода линеаризации необходимо чтобы число уравнений было также примерно равно 221, то есть необходимое число бит открытого и шифрованного текста, которые должны быть известны, должно быть равно 221 /14. В результате, проводя полное опробование начального заполнения LFSRc (вариант А), и учитывая, что трудоемкость реше ния линейной системы уравнений методом Штрассена в соответствии с [19] составляет 7·T log2 СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 102 МЕЛУЗОВ битовых операций (или, по утверждению [18], на ЭВМ с 64-битной архитектурой регистров, 7 log2 7 тактов процессора), получим общую трудоемкость метода 239 ·7·T log2 7 2102 битовых 64 ·T операций.

В качестве альтернативы (вариант Б) предлагается взять гораздо более длинную последо вательность открытого и шифрованного текста и воспользоваться Леммой 1. Так за 239 такт работы первого регистра, второй будет сдвигаться ровно на 5 · 238 1 тактов. Тогда, выбирая в потоке известной гаммирующей последовательности биты, находящиеся на позици ях с номерами + (239 1) можно на их основе составить систему алгебраических урав нений без необходимости опробовать управляющий регистр. Трудоемкость такого подхода составит 7 · T log2 7 263 битовых операций и потребует знания примерно 257 бит открыто го/шифрованного текста, либо 218 бит с заданных определенным образом позиций.

Другой подход логический криптоанализ предложен в работе [20]. Авторы предлагают при фиксированном начальном заполнении первого (управляющего) фильтрующего генерато ра технику построения системы КНФ, решением которой является исходное заполнение LFSRd в случае, если предположение о начальном заполнении LFSRc и части LFSRd оказалось верно.

В работе предлагается использовать постоянно совершенствуемое программное обеспечения для решения SAT-проблемы (задачи выполнимости КНФ). Авторами отмечено, что при вер ном выборе заполнения управляющего регистра решение задачи выполнимости построенной КНФ занимает в среднем в 10 раз меньше времени, чем доказательство невыполнимости по строенной КНФ при неверно предположенном начальном заполнении LFSRc или части LFSRd.


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

Время, необходимое для поиска ключа потокового шифра LILI-128 авторы статьи оценива ют в 1025 секунд. Кроме приведенных подходов к криптоанализу потоковых шифров, широко Таблица 1. Зависимость между параметрами при использовании различных методов.

Метод Изв. шифр. послед. Трудоемкость Память 230 277,5 [21] 218 2102 [18], вариант А 257 263 [18], вариант Б 246 261 251, [14] 26,5 2128 26, Опробование, вариант А 245,5 289 26, Опробование, вариант Б известны корреляционные атаки на ключ по известной гаммирующей последовательности.

Наиболее успешной корреляционной атакой на LILI-128 является быстрая корреляционная атака, предложенная в работе [21]. Генерируемая вторым фильтрующим генератором после довательность распознается как линейный код с определенной вероятностью. Трудоемкость метода составляет 271 операций со строками матрицы размером 230 89 (то есть около 277, битовых операций).

В работе [14] использована техника time-memory tradeo применительно к рассматрива емой задаче криптоанализа. В данной работе предложен метод, который, по утверждению авторов, имеет трудоемкость около 248 ·, где трудоемкость работы алгоритма DES, тре бует 246 бит известной гаммирующей последовательности и использует около 251,48 бит памяти для хранения предварительно вычисленной таблицы возможных значений бит гаммирующей последовательности. Заявленная надежность метода при этом составляет около 0,9.

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

Для составления таблицы 1 использовалась оценка трудоемкости DES в 213 битовых опера ций. Последние строки таблицы соответствуют тривиальному опробованию регистров с после дующей проверкой на 89 битах гаммирующей последовательности (вариант А) и опробованию только регистра LFSRd с использованием Леммы 1 (вариант Б).

На рисунке 2 приведено расположение параметров, заданных в таблице 1 в пространстве трудоемкость (C)–размер известной шифрующей последовательности (m) в логарифмиче СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) О КРИПТОАНАЛИЗЕ LILI-128 m 250 260 270 280 290 2100 2110 2120 2130 C Рис. 2. Соотношение трудоемкости (C) и количества известных бит гаммирующей последовательно сти (m) в различных методах криптоанализа.

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

4 Частичное опробование и мономиальная совместность Введем сначала определение мономиальной совместности системы полиномиальных урав нений.

Определение. Система полиномиальных уравнений называется мономиально совместной, если система линейных уравнений, полученная из исходной системы путем переобозначения всех мономов степени не ниже 1 символами новых переменных (этот процесс называется лине аризацией системы), является совместной относительно новых переменных. И наоборот, если получаемая после переобозначения система линейных уравнений несовместна относительно новых переменных, то исходная система называется мономиально несовместной.

Для такого определения будет верным следующее утверждение.

Утверждение 1. Если система является мономиально несовместной, то она является несов местной и в обычном смысле.

Исходя из результатов исследования случайных систем булевых полиномиальных уравне ний, будут верны следующие лемма и теорема [23].

Лемма 2. Для любых z 0, l 1, T 1 верно, что вероятность совместности случайной системы линейных булевых уравнений, описываемой матрицей со сторонами T + l + z и T в 2z2 раз меньше вероятности совместности случайной системы линейных булевых уравнений, описываемой матрицей со сторонами T + l и T.

Теорема 1. Пусть, задано множество элементарных исходов множество систем из T по линомиальных уравнений степени не выше d над полем GF(2) от s неизвестных. Пусть n наибольшее среди целых положительных решений неравенства. Пусть случайная величи на, равная трудоемкости решения системы уравнений при опробовании k = s n переменных (заданных множеством X, |X| = k) и последующей проверке на мономиальную совместность, в предположении независимости и равномерного распределения коэффициентов при мономах системы.

Тогда математическое ожидание E() имеет верхнюю асимптотическую оценку O(2k T ).

Где коэффициент, зависящий от применяемого метода решения линейных систем.

СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 104 МЕЛУЗОВ 5 Метод определения ключа Перейдем к описанию вариации алгебраического подхода к криптоанализу LILI-128. Будем опробовать все возможные начальные заполнения управляющего генератора LFSRc, после чего будем строить системы полиномиальных уравнений в соответствии с методикой, предложенной Н. Куртуа в работе [18]. За счет использования анигилляторов, на каждый известный бит гаммирующей последовательности будем получать 14 линейно независимых уравнений степени не выше 4.

Будем определенным (описанным далее) образом выбирать параметр k число опробу емых переменных, а также некоторым образом сами эти переменные. При опробовании всех возможных значений выбранных переменных получим 2k редуцированных систем полиноми альных уравнений от n = 89 k переменных, степени не выше 4. Проверим каждую из по лученных систем на мономиальную совместность, используя для приведения к треугольному виду метод Штрассена [19]. Системы, несовместные мономиально, в силу утверждения 1, не имеют решения в обычном смысле, а значит соответствующие им предположения о значениях выбранных k переменных не приводят к решению системы и их можно не рассматривать. Для редуцированных систем, совместных мономиально, уже фактически проведена линеаризация, остается только проверить решение.

Приведем формальное описание предлагаемого алгоритма восстановления исходного за полнения регистров LILI-128 по известной гаммирующей последовательности.

Алгоритм 1. Перед началом работы выбирается параметр k и, соответственно, конкретные k бит LFSRd, которые будут опробоваться на третьем шаге.

1. Выбираем очередное значение начального заполнения LFSRc для опробования.

2. Зная управляющую выходную последовательность фильтрующего генератора LFSRc (fc ) и зная результат работы LFSRd (fd ), строим систему полиномиальных уравнений степени не выше 4 от 89 неизвестных, описывающую работу LFSRd (fd ).

3. Выбираем очередное значение опробуемых k переменных, подставляем выбранные зна чения в построенную на шаге 2 систему уравнений и получаем редуцированную систему уравнений. Если все варианты значений опробуемых переменных исследованы, перехо дим к шагу 1.

4. Проводим линеаризацию редуцированной системы уравнений, переобозначая все мономы степени 2 и выше новыми переменными. Выясняем, совместна ли полученная линеаризо ванная система, используя алгоритм Штрассена. Если несовместна переходим к шагу 3.

5. Решаем редуцированную систему любым методом.

6 Расчет трудоемкости метода Рассмотрим теперь вопрос трудоемкости предложенного метода криптоанализа. Посколь ку уравнения, получаемые при криптоанализе LILI-128, разнообразны и уже после нескольких тактов шифратора зависят от всех бит исходного заполнения регистра (ранее чем через тактов работы регистра LFSRd ), то при достаточно больших k (скажем, k 5) для оценки вероятности мономиальной совместности редуцированной системы случайную модель, приве денную в работе [23]. В таком случае, будет действовать лемма 2, а значит, можно оценить вероятность мономиальной совместности получаемых редуцированных систем в зависимости от величины параметра k, определяющего количество мономов в редуцированной системе, и числа уравнений в системе.

количество уравнений в редуцированной системе, n = 89 k число перемен Пусть T ных, от которых зависит редуцированная система, Sn,4 = 4 n максимально возможное i=1 i количество мономов в редуцированной системе (переменных в линеаризованной системе). Под ставляя в неравенство T Sn,d n + 2 из теоремы 1 указанные параметры, будем получать следующее неравенство:

T S(89k),4 (89 k) + 2, (1) СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) О КРИПТОАНАЛИЗЕ LILI-128 Тогда, если n и T удовлетворяют неравенству (1), то математическое ожидание трудоемкости решения (или доказательства отсутствия решений) каждой из редуцированных систем уравне ний можно оценить сверху как C(T )+ 21 ·2n, где C(T ) трудоемкость определения мономиаль n ной совместности системы с помощью алгоритма Штрассена. Действительно, в силу леммы 2, вероятность мономиальной совместности системы при заданных параметрах не превосходит 21 n и при этом, трудоемкость решения редуцированной системы в отношении которой выяснена ее мономиальная совместность, очевидно, не превосходит трудоемкости осуществления полного перебора 2n. В действительности же трудоемкость решения мономиально совместной редуци рованной системы гораздо ниже, поскольку в ходе проверки на мономиальную совместность уже получено решение линеаризованной системы и остается его лишь проверить.

Заметим, что поскольку на каждый известный бит гаммирующей последовательности при ходится 14 линейно независимых уравнений, то m число необходимых бит последовательно T сти равно 14. Таким образом, выбирая количество известных бит ключа и подставляя данное значение в неравенство (1), можно определять число переменных, которые следует опробо вать на шаге 3 Алгоритма 1. И наоборот, подставляя число опробуемых переменных в (1), можно определять необходимое для восстановления ключа число известных бит гаммирую щей последовательности. Перейдем теперь к оценке трудоемкости метода в целом. В качестве Таблица 2. Зависимость между параметрами метода.

k Известная гамма(m) Средняя трудоемкость Требуемая память (бит) 217,5 2100 242, 217,2 2103 242, 216,9 2105 242, 216,5 2110 241, 216,1 2115 241, 215,7 2117 240, 215,2 2122 240, 214,7 2124 239, 214,1 2130 239, оценки трудоемкости решения редуцированной системы уравнений будем использовать приве денную выше оценку математического ожидания трудоемкости решения (или доказательства отсутствия решений) редуцированной системы уравнений C(T ), где, в соответствии с [19] C(T ) = 7 · T log2 7 битовых операций. Всего таких редуцированных систем, в соответствии с Алгоритмом 1, необходимо решить не более 239 · 2k. Таким образом, общая трудоемкость предлагаемого метода в среднем составит не более 239 · 2k · 7 · T log2 7 битовых операций.

Заметим, что объем требуемой памяти для работы этого метода зависит от размера исход ной системы уравнений, который можно оценить как S89,4 · T = 4 89 25,1 · m i=1 i · 14 · m бит.

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

Данные по трудоемкости в таблице приведены в битовых операциях и могут быть умень шены на несколько двоичных порядков за счет распараллеливания обработки [18].

7 Заключение В настоящей работе предложено обобщение алгебраического метода криптоанализа шифра тора LILI-128. Обобщенный метод позволяет рассчитывать средние трудоемкости метода для объемов шифрующих последовательностей меньших, чем известные ранее. Получены средние трудоемкости для различных объемов известных шифрующих последовательностей.

На рисунке 3 приведен график зависимости трудоемкости от размеров известной гамми рующей последовательности. Звездой и пятиугольником на графике отмечены результаты, СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 106 МЕЛУЗОВ m 250 260 270 280 290 2100 2110 2120 2130 C Рис. 3. Соотношение трудоемкости (C) и количества известных бит гаммирующей последовательно сти (m).

полученные в работе [18]. Кривые линии на графике возможные значения трудоемкости и количества известной гаммы при различных параметрах метода, предлагаемого в настоя щей статье. Из графика хорошо видно, что предлагаемый метод обобщает результат, получен ный ранее и расширяет диапазон значений параметров, при которых возможен криптоанализ LILI-128.

Список литературы [1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

[2] Faug`re J.-C. A new ecient algorithm for computation Grebner bases (F4 ) // Journal of e o pure and applied algebra. 1999. Vol. 139, no. 1. Pp. 61–88.

[3] Faug`re J.-C. A new ecient algorithm for computation Grebner bases without reduction e o to zero (F5 ) // Proceedings of the 2002 international symposium on Symbolic and algebraic computation. 2002. Pp. 75–83.

[4] О’Ши Д., Кокс Д., Литтл Д. Идеалы, многообразия и алгоритмы. М.: Мир. 2000.

687 с.

[5] Courtois N., Meier W. Algebraic attacks on stream ciphers with linear feedback // Eurocrypt.

Springer, 2003. LNCS 2656. Pp. 345–359.

[6] Meier W., Pasalic E., Carlet C. Algebraic attacks and decompozition of boolean functions // Eurocrypt. Springer, 2004. LNCS 3027. Pp. 474–491.

[7] Armknecht F. On the existence of low-degree equations for algebraic attacks // Cryptology ePrint Archive: Report 2004/185. http://eprint.iacr.org/2004/185.

[8] Courtois N., Klimov A., Patarin J., Shamir A. Ecient Algorithms for Solving Overdened Systems of Multivariate Polynomial Equations // In B. Preneel, editor, Advances in Cryptology, EUROCRYPT 2000, volume 1807 of LNCS. Springer-Verlag, Berlin, 2000. Pp. 392–407.

[9] Courtois N., Pieprzyk J. Cryptanalysis of block chiphers with overdened systems of equations // Cryptology ePrint Archive, Report 2002/044, 2002.

[10] Courtois N., Pieprzyk J. Cryptanalysis of block chiphers with overdened systems of equations.

In Y. Zheng, editor // Advances in cryptology. Asiacrypt’2002. Proc. 8th Int. Conf. on the СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) О КРИПТОАНАЛИЗЕ LILI-128 Theory and Application of Cryptology and Information Security, volume 2501 of Lect. Notes Comput. Sci. Springer, 2002. Pp. 267–287.

[11] Semaev I. On solving sparse algebraic equations over nite elds I // Proceedings of WCC’07, 2007. INRIA. Pp. 361–370.

[12] Semaev I. On solving sparse algebraic equations over nite elds II. 2007. http://eprint.

iacr.org/2007/280.

[13] Мелузов А. С. Использование ассоциативных принципов обработки информации для по строения алгоритмов решения систем булевых уравнений // Журнал вычислительной математики и математической физики. 2010. Т. 50, № 11. С. 2028–2044.

[14] Markku-Juani Olavi Saarinen. A time-memory tradeo attack against LILI-128 // FSE 2002, LNCS 2365, Springer. Pp. 231-236.

[15] Dawson E., Clark A., Goliґc J., Millan W., Penna L., Simpson L. The LILI-128 keystream generator // Proc. of rst NESSIE workshop.

[16] Babbage S. Cryptanalysis of LILI-128 // Nessie project internal report. https://www.cosic.

esat.kuleuven.ac.be/nessie/reports/.

[17] Chepyzhov V., Johansson T., Smeets B. A simple algorithm for fast correlation attacks on stream ciphers // Fast Software Encryption, FSE’2000, to appear in Lecture Notes in Computer Science, Springer-Verlag, 2000.

[18] Courtois N. Algebraic Attacks on Stream Ciphers with Linear Feedback // Advances in Cryptology. EUROCRYPT 2003. Springer, 2003.

[19] Strassen V. Gaussian elimination is not optimal // Numerische Mathematik. 1969.

Vol. 13. Pp. 354–356.

[20] Логачев О. А., Смышляев С. В. Логический криптоанализ потокового шифра LILI-128 // Материалы 8-й Общероссийской конференции МаБИТ-09.

[21] Jonsson F., Johansson T. A Fast Correlation Attack on LILI-128. http://www.it.lth.se/ thomas/papers/paper140.ps.

[22] Колчин В. Ф. Случайные графы. М.: ФИЗМАТЛИТ, 2004. 256 с.

[23] Мелузов А. С. Построение эффектривных алгоритмов решения систем полиномиальных булевых уравнений методом опробования части переменных. Принято для публикации в журнал Дискретная математика, 2011.

СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) 108 СБОРНИК СТАТЕЙ МОЛОДЫХ УЧЕНЫХ факультета ВМК МГУ выпуск № 8 (2011 г.) УДК 517.977. МЕТОД БРОЙДЕНА ДЛЯ РЕШЕНИЯ ЗАДАЧ РАВНОВЕСНОГО ПРОГРАММИРОВАНИЯ c 2011 г. А. В. Ничипорчук anichiporchuk@gmail.com Кафедра оптимального управления Введение Распространенная постановка задач оптимизации, использующая функцию от одного аргу мента, нередко оказывается несостоятельной в проблемах с двумя и более конфликтующими сторонами к примеру, в различных игровых и экономических моделях. В таких случаях целесообразно совершить переход к равновесной постановке задачи. Пусть имеется некоторая функция (v, w), определенная на произведении Rn Rn. Необходимо найти точку v Rn, удовлетворяющую неравенству:

(v, w) w Rn.

(v, v ) (1) Такую точку называют равновесной точкой задачи (1). Проблема существования точек равновесия изучена достаточно хорошо и равносильна проблеме существования неподвижных точек v W (v) экстремального отображения W (v) функции (v, w) на Rn, определяемого из условия (v, W (v)) = min (v, w), v Rn, W (v) Rn.

n wR Такая постановка является обобщением оптимизационной постановки: если функция (v, w) не зависит от переменной v, то неравенство (1) фактически является определением точки минимума функции. Кроме того, к такой постановке сводится различные классы задач, например, седловые задачи и игры Нэша.

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

Метод Ньютона для задач равновесного программирования Этот метод является аналогом метода Ньютона для задач оптимизации. Ключевым во просом является построение удобного обобщения второй производной для функции (v, w).

В статье [1] был предложен следующий способ построения матрицы вторых производных.

Пусть функция (v, w) обладает следующими производными:

2 (v, w) 2 (v, w) (v, w) v, w Rn.

,,, w w v w Тогда вектор (v, w) w (v, v) =, w w=v являющийся сужением градиента функции (v, w) по переменной w, будем считать аналогом градиента функции, а матрицу 2 (v, w) 2 (v, w) v Rn, (v, v) = +, w2 v w w=v МЕТОД БРОЙДЕНА аналогом матрицы вторых производных. В случае существования обратного оператора (vk, vk ) получаем выражение для (k + 1)-го приближения метода Ньютона:

vk+1 = vk ( (vk, vk ))1 w (vk, vk ). (2) Метод Ньютона имеет более высокую скорость сходимости по сравнению с методами пер вого порядка, однако обладает и недостатками например, требует больших вычислительных затрат для обращения матрицы вторых производных, а также сходится локально то есть необходимо выбирать стартовую точку в определенной степени близко к решению. Попытка устранить данные недостатки приводит к рассмотрению квазиньютоновских методов, связан ных с заменой обращенной матрицы вторых производных на некоторую матрицу Ak. При выборе этой матрицы необходимо следить за сохранением симметричности при переходе от Ak к Ak+1, а также за близостью матрицы Ak к обращенной матрице вторых производных минимизируемой функции (то есть за соблюдением условия limk Ak ( (vk, vk ))1 = 0).

Для перехода от матрицы Ak к матрице Ak+1 предлагается использовать формулу вида:

Ak+1 = (Ak ), где матрица A0 задается как параметр метода.



Pages:     | 1 | 2 || 4 | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.