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

Терехов Антон Юрьевич

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

Распространённая на данный момент система с открытым ключом RSA основана на задаче факторизации, которая находится под угрозой решения при использовании квантовых компьютеров. Криптосистемы, основанные на задаче о ранце, могут оказаться хорошей альтернативой. В данной статье исследуется ранцевая криптосистема Меркла-Хеллмана, одна из первых криптосистем с открытым ключом. На настоящий момент известна атака этой системы, работающая за полиномиальное время, однако не каждый полиномиальный алгоритм возможно выполнить за разумное время. В статье описываются алгоритмы и детали реализации этой атаки, а также эмпирические оценки времени её работы.

Математика

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d362f5f1be77c40d588df

UUID: 629d756c-cb1c-40cf-a318-fe5719cd870f

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 347

Терехов Антон Юрьевич

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 211577 bytes

Поделиться работой

Правительство Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Санкт-Петербургский государственный университет» Кафедра информационно-аналитических систем Терехов Антон Юрьевич Ранцевая криптосистема с открытым ключом Бакалаврская работа Научный руководитель: д. т. н., профессор Крук Е. А. Рецензент: тьютор Ханов А. Р. Санкт-Петербург 2016

SAINT-PETERSBURG STATE UNIVERSITY Sub-Department of Analytical Information Systems Anton Terekhov Knapsack public key cryptosystem Graduation Thesis Scientific supervisor: professor Eugine Krouk Reviewer: tutor Arthur Khanov Saint-Petersburg 2016

Оглавление Введение 4 1. Проблемы ранцевых криптосистем 5 2. Криптосистема Меркла-Хеллмана 6 3. Атака Шамира на криптосистему Меркла-Хеллмана 8 4. Целочисленное решение системы линейных неравенств 4.1. Обзор метода . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2. Сведение задачи к меньшим . . . . . . . . . . . . . . . . . 4.3. Поиск преобразования . . . . . . . . . . . . . . . . . . . . 4.4. Оптимизация поиска преобразования . . . . . . . . . . . . 4.5. Изменение базиса . . . . . . . . . . . . . . . . . . . . . . . 12 12 13 17 21 25 5. Численный эксперимент 28 Заключение 30 Список литературы 31 3

Введение В данной работе будут рассмотрены альтернативы для используемых в наше время криптосистем с открытым ключом, а именно криптосистемы, основанные на задаче о рюкзаке. Один из вариантов такой системы предложили Ральф Меркл и Мартин Хеллман [5]. В данных системах открытым ключом является последовательность объектов (весов), в самом простом случае это последовательность натуральных чисел. Отправитель вычисляет сумму только тех объектов, которые соответствуют единицам в сообщении, представленном в бинарном виде, далее эта сумма пересылается адресату. В общем случае задача восстановления сообщения по вышеуказанной сумме NP-полная задача. Однако секретным ключом являются параметры прямого и обратного преобразований весов, преобразование строится таким образом, чтобы в обычном виде задача по расшифровке была сложна, а в преобразованном виде решалась быстро. 4

1. Проблемы ранцевых криптосистем Указанный выше вид криптосистем был изобретён уже давно. Однако для системы Меркла-Хеллмана был найден полиномиальный алгоритм нахождения секретного ключа (параметров преобразования) Ади Шамиром [7]. Данная атака системы использует метод решения целочисленного линейного программирования, рассмотренного Хендриком Ленстра [3]. Стоит заметить, что и вышеуказанная атака, и алгоритм целочисленного линейного программирования были рассмотрены лишь с теоретической точки зрения, полиномиальная сложность этих алгоритмов доказана, однако не были рассмотрены реализации этих алгоритмов. Также существует обобщение системы, при котором объектами являются вектора чисел, варианты таких криптосистем рассмотрели Роберт Мак-Элис [4] и Харальд Нидеррайтер [6]. Эти способы появились из теории кодов, исправляющих ошибки. Слабым местом этих систем являются используемые в них методы кодирования и декодирования, определённые свойства которых позволяют провести атаку второго рода, то есть по открытому ключу получить закрытый. Для препятствования этим проблемам, в данных системах используют довольно большой по памяти открытый ключ, что мешает их активному использованию. 5

2. Криптосистема Меркла-Хеллмана Идея криптосистемы заключается в следующем. Открытым ключом является последовательность из n натуральных чисел a1 , a2 , a3 , . . . an . Сторона А для передачи сообщения в битовом виде x1 , x2 , x3 , . . . xn , xi ∈ n ∑ {0, 1} вычисляет сумму соответствующих произведений sum = ai xi i=1 (можно считать, выполняется скалярное произведение векторов) и посылает по открытому каналу результат. Для расшифровки сообщения сторона В должна решить обратную задачу, известную, как задача о ранце: по сумме весов некоторых объектов, а также по весам всех объектов определить объекты, участвующие в сумме. В общем виде данная задача является NP-полной, а при некоторых наборах весов ответов может быть даже несколько. (Например, в случае набора весов {2, 3, 5}). В случае, когда для каждого 1 < i ⩽ n выполняется строгое неравенство i−1 ∑ ′ aj < a′i (последовательность a′1 , a′2 , a′3 , . . . a′n в таком случае называj=1 ется супервозрастающей), то существует следующее решение, работающее за полиномиальное время. Изначально инициализируется переменная sum′ , равная полученной по каналу связи сумме. В ходе алгоритма из неё будут вычитаться веса, соответствующие единицам в дешифрованном сообщении. Рассматриваются веса a′i в порядке убывания, в том случае, когда текущая сумма sum′ меньше, чем a′i , то, очевидно, i-й объект не входит в ответ. Если же сумма sum′ больше или равна текущего i−1 ∑ ′ веса a′i , то он обязан входить в ответ, иначе aj < a′i ⩽ sum′ , и даже j=1 все оставшиеся объекты не обеспечат нужную сумму. Для перехода к следующему весу нужно добавить текущий объект в ответ и вычесть из суммы текущий вес. Однако для несанкционированной стороны С решение данной задачи должно быть сформулировано в общем виде. Для этого случайn ∑ ным образом берутся два числа: M > a′i и W : (W, M ) = 1, а такi=1 −1 же число W , являющееся обратным к W по модулю M . При замене ai = a′i W −1 mod M веса ai оказываются равномерно распределёнными по модулю M , а операции на стороне А практически не усложняют6

ся (просто изменяются используемые веса, причём не изменяется порядок максимального веса, которым оценивается сложность алгоритма дешифрования). На стороне В полученная сумма sum′ умножается на W по модулю M , в итоге получается sum = sumW mod M = n n ∑ ∑ ′ −1 ai W W mod M = a′i . Таким образом с помощью секретного клюi=1 i=1 ча задача свелась к полиномиальной. При реализации, кроме домножения на W −1 используется также перестановка весов, при расшифровке применяется обратная. Остаётся указать способ построения чисел W и M , а также способ построения супервозрастающей последовательности. Пусть необходимо построить ключи для некоторого количества объектов n. Вес a′1 выбирается случайным образом из равномерного распределения целых чисел по отрезку [1, 2n ]. Следующий вес a′2 выбирается равномерно из отрезка [1 ∗ 2n + 1, 2 ∗ 2n ], следующий за ним a′3 выбирается из [3 ∗ 2n + 1, 4 ∗ 2n ] и так далее; a′i выбирается из отрезка [(2i−1 −1)∗2n +1, 2i−1 ∗2n ]. При таких распределениях условие супервозрастаемости, очевидно, будет выполнятся, так как нижняя граница каждого отрезка в точности равна увеличенной на единицу сумме всех правых границ предыдущих отрезков. Число M при этом выбирается из отрезка [22n+1 + 1, 22n+2 − 1], а число W выбирается случайно из отрезка [2, M − 2] до тех пор, пока не будет взаимно просто с M . 7

3. Атака Шамира на криптосистему МерклаХеллмана Атака основана на нахождении чисел W и M по открытому ключу, переводящих веса a1 , a2 , a3 , . . . an в супервозрастающую последовательность (с точностью до перестановки), причём не обязательно в исходную. Реализуется это с учётом того, что свойство супервозрастаемости последовательности {a′i }ni=1 оставляет свои следы в последовательi ∑ n ′ ности {ai }i=1 . Очевидно, что каждая из сумм sumi = aj не менее, 2sum′i < sum′i+1 a′1 = sum′1 j=1 чем в два раза больше предыдущей из-за свойства ′ n супервозрастаемости. Отсюда следует, что < sum < 2M n−1 n−1 . 2 Аналогично получаются оценки для остальных элементов последова′ −1 mod M и a′i < M , тельности a′i < sum′i < 2M n−i . Так как ai = ai W то a′i = ai W mod M , и, подставляя в наши неравенства и разделив их 1 на M , получаем ai W M mod 1 < 2n−i (здесь под операцией модуля рассматривается нецелочисленное взятие по модулю). При рассмотрении функции вещественного аргумента fi (x) = ai x mod 1 при x ∈ (0, 1), мы увидим пилообразный график, состоящий из ai склонов, расстояние между которыми будет a1i (рис. 1). Легко заметить, что производная fi (x) 1 0 1 x Рис. 1: График функции fi (x) функции fi (x) равна ai во всех точках, кроме точек разрыва. Поэтому 8

для функции f1 (x), соответствующей минимальному числу a′1 в супервозрастающей последовательности, неизвестное при атаке значение W M будет близко к одному из минимумов этой функции (например, к i-му f(W ai W i 1 M) M mod 1 − = = < 2n−1 минимуму с координатой ai1 ): W M a1 a1 a1 a1 . Аналогично неравенства будут выполняться и для a2 , a3 и a4 (номера минимумов для соответствующих функций назовём j, k и l). Стоит заметить, что из-за перестановки, описанной в предыдущем разделе, при атаке неизвестно, каким элементам открытого ключа соответствуют a′1 , a′2 , a′3 и a′4 . Эта проблема решается перебором всех четвёрок весов объектов из открытого ключа. Таким образом далее будем считать, что a1 , a2 , a3 и a4 соответствуют первым четырём элементам супервозрастающей последовательности, причём пусть ai1 будет больше, чем aj2 , ak3 и al4 , а a2 , a3 и a4 будут отсортированы по возрастанию соответствующих им весов в закрытом ключе (рис. 2). Тем самым, минимум функции f1 будет j ближайшим к искомому значению W M , а минимум a2 соответствует либо первому, либо второму элементу супервозрастающей последовательно1 сти, следовательно расстояние между ним и W M будет меньше 2n−2 a2 , а так как минимум ai1 ближе всех к W M , то и расстояние между этими дву1 мя минимумами будет меньше 2n−2 a2 . В таком случае можно написать неравенства для i, j, k и l: i j 1 − ⩽ n−2 a1 a2 2 a2 k 1 i − ⩽ n−3 0⩽ a1 a3 2 a3 i j 1 − ⩽ n−4 0⩽ a1 a4 2 a4 1 ⩽ i ⩽ a1 − 1 0⩽ 1 ⩽ j ⩽ a2 − 1 1 ⩽ k ⩽ a3 − 1 1 ⩽ l ⩽ a4 − 1 Решая данную систему при всех размещениях весов a1 , a2 , a3 , . . . an , 9

y a′4 M a′3 M a′2 M a′1 M 0 k a3 l a4 j i a2 a1 W M x α+ε 1 Рис. 2: Графики функций fi (x) вблизи точки W M будут получены точки, рядом с которыми может находится точка W M, причём одна из них точно будет рядом с W M , а другие могут находится ′ рядом с другими, но подходящими для атаки значениями W ′ M . Пусть после решения линейной системы неравенств в целых числах α = ai1 , тогда искомое число v = W M должно находиться в интервале (α, α + ε), где α + ε — самая близкая точка разрыва к α среди всех точек разрыва всех функций fi , больших α. На этом интервале все функции принимают вид отрезков, их количество равно n, поэтому существует не более n(n−1) точек их пересечения. Если отсортировать абсциссы всех 2 точек пересечения, то они разбивают интервал (α, α + ε) на интервалы (lk , rk ), количество которых не превышает n2 , а значения a′i = fj (v) на их протяжении идут в одном и том же порядке (так как отрезки в этих точках не пересекаются). На каждом из отрезков можно записать порядка n неравенств для обеспечения свойства супервозрастаемости, 10

а именно: fπ(i) (v) > i−1 ∑ fπ(j) (v), i ∈ 2..n j=1 n ∑ fi (v) < 1, i=1 где π(j) — перестановка, соответствующая порядку значений fj (v) на текущем интервале (lk , rk ), а сами функции fj (v) представляются в виде fj (v) = aj v − cj , где cj — номер наибольшего минимума функции fj (v), меньшего α. Заметим, что данные неравенства будут линейно зависеть от v. Дополнительное ускорение процесса можно получить, заметив, что последнее неравенство одинаково для всех интервалов (lk , rk ), а это значит, что α + ε можно уменьшить до решения этого неравенства, тем самым уменьшив количество интервалов. После решения этой простой системы на данном отрезке, получается отрезок для значений W M , причём если отношение любых двух целых чисел W и M попадает в этот отрезок, то веса {ai }ni=1 после преобразования a′i = ai W mod M будут образовывать супервозрастающую последовательность. Для нахождения таких чисел можно разложить границы отрезка в цепные дроби, взять цепную дробь наименьшей длины, которая будет между двумя получившимися, и преобразовать её в обычную дробь, числителем и знаменателем которой будут соответственно W и M . При этом часто получаются значения W и M по длине меньше, чем исходные. 11

4. Целочисленное решение системы линейных неравенств При выполнении атаки наибольшую часть процессорного времени занимает решение системы линейных неравенств. В этом разделе будет разобран алгоритм решения, предложенный Ленстра, а так же его оптимизации при применении к поставленной задаче. 4.1. Обзор метода Задача ставится следующим образом. Пусть n — количество неизвестных. Система линейных неравенств задаётся целочисленной матрицей A размера m × n и целочисленным вертикальным вектором b длины m. Решениями данной системы являются целочисленные вектора x, удовлетворяющие неравенству Ax ⩽ b. Стоит заметить, что коэффициенты матриц A и b могут быть и рациональными, поведение алгоритма от этого не изменится. По сути, решением системы является пересечение многогранника, задаваемого матрицами A и b, и целочисленной сетки в n-мерном пространстве. Строки матрицы A при этом задают направление нормальных векторов к граням, то есть задают поворот грани, а элементы вектора b задают смещение граней вдоль этих направлений от центра координат. В процессе решения находится невырожденное линейное преобразование пространства τ , при котором многогранник приобретает так называемую сферическую форму (имеется в виду тот факт, что существует два шара с общим центром, один из которых содержит многогранник, а другой содержится внутри многогранника, причём отношение радиусов этих шаров зависит только от размерности n). В том случае, если многогранник имеет нулевой объём, такого τ не существует, вместо этого производится сведение задачи к меньшей задаче, по размерности равной размерности многогранника. При преобразовании τ целочисленная сетка и её базис деформируются, углы между базисными векторами становятся отличными от прямых. Далее этот базис 12

преобразовывается к почти ортогональному виду с помощью операций замены векторов местами и целочисленного прибавления одного вектора к другому, что соответствует умножению на унимодулярную матрицу. ”Почти ортогональность” здесь означает то, что отношение детерминанта матрицы, состоящей из базисных векторов, к произведению их длин больше некоторой константы, зависящей только от размерности n; по сути это отношение объёма параллелепипеда, натянутого на базисные вектора, к объёму такого параллелепипеда при условии, что все вектора ортогональны между собой. Таким образом, исходная задача про пересечение многогранника и целочисленной сетки переходит в эквивалентную ей задачу пересечения сферического многогранника и сетки с почти ортогональным базисом. В этом случае если самая близкая к центру шаров точка сетки попадает в многогранник, то задача решена; пересечение сетки и многогранника найдено. В противном случае сетка не пересекается с внутренним шаром, поэтому она достаточно крупна и может пересекать внешний шар в зависящем только от размерности n константном количестве гиперплоскостей, образованных фиксированным коэффициентом при самом длинном базисном векторе. Это сводит задачу к нескольким аналогичным задачам более низкой размерности. При реализации атаки необходимо найти все решения линейной системы неравенств, так что сводить задачу к меньшим нужно и в случае попадания ближайшей точки сетки в многогранник. 4.2. Сведение задачи к меньшим Рассмотрим сведение задачи к меньшим более формально. Обозначим за K = {x ∈ Rn : Ax ⩽ b} исходный многогранник, в методе решения линейных уравнений имеется условие на его ограниченность, но при рассматриваемой атаке оно выполняется. Пусть также L = τ Zn — целочисленная сетка после преобразования. Решение задачи сводится к нахождению пересечения множеств τ K и L. Очевидно, что единичная матрица I — матрица базисных векторов сетки Zn , поэтому τ I — 13

матрица базисных векторов модуля L над кольцом Z. Любой другой базис этой сетки может быть представлен в виде M (τ I), где M — унимодулярная матрица, так как она обязана быть целочисленной и обратимой, обратная матрица также должна быть целочисленной. Модуль детерминанта такой матрицы равен единице, из этого следует, что для каждого из базисов L, модуль детерминанта матрицы, состоящей из его векторов, зависит только от L и не зависит от базиса; обозначим эту величину за d(L). Пусть базис (b1 , b2 , . . . , bn ) сетки L будет найденным почти ортогональным базисом: n ∏ |bi | ⩽ c1 d(L). i=1 Также, для всех базисов выполняется обратное неравенство: n ∏ |bi | ⩾ d(L). i=1 Докажем следующую лемму: Лемма 1 Для любой точки x ∈ Rn найдётся такая ближайшая к ней точка y ∈ L, что выполняется неравенство: (

2 ) 2

b2 b1 |x − y|2 ⩽

+ . . . +

2 2 2 Доказательство. Доказательство леммы проводится индукцией по n. Для n = 1 доказательство очевидно. Пусть лемма верна для n − 1. Докажем её для n. Для этого рассмотрим сетку меньшей размерности { } n−1 ∑ L′ = x ∈ Rn : x = αi bi , αi ∈ Z , i=1 а также гиперплоскость в которой она находится: } { n−1 ∑ βi bi , βi ∈ R . H ′ = x ∈ Rn : x = i=1 14

Обозначим за h расстояние от точки bn до гиперплоскости H, причём h ⩽ |bn |. Заметим, что сетка L содержится в объединении гиперплоскости H ′ и всех параллельных ей, находящихся на расстоянии, кратном h. Из этого следует, что существует такое число m, что расстояние от x − mbn до гиперплоскости H ′ не превосходит h2 . Этот вектор x − mbn можно разложить на сумму x = x1 +x2 , где x1 ∈ H ′ , x2 ∈ H ′⊥ . В качестве искомой точки y возьмём сумму mbn и ближайшей точки y ′ сетки L′ к точке x1 , воспользовавшись индукционным предположением. В итоге имеем: (

2 ) 2

bn−1

; |x1 − y ′ | ⩽

+ . . . +

2 2 2

|x − y|2 = |x1 − y ′ |2 + |x2 |2 ⩽ (

2 ) ( )2

bn−1

+ h ⩽ ⩽

+ . . . +

2 2 2

2 (

)

⩽

+ . . . +

, 2 2 2 что и требовалось доказать. ■ Для удобства перенумеруем номера базисных векторов так, чтобы последний базисный вектор bn был самым длинным. В этом случае доказанное неравенство можно ослабить и упростить, а именно: |x − y| ⩽ 1√ n|bn |. 2 Также легко показать, что выполняется неравенство d(L) = hd(L′ ). Из него можно вывести следующее: n ∏ ′ |bi | ⩽ c1 d(L) = c1 hd(L ) ⩽ c1 h i=1 n−1 ∏ |bi |, i=1 из чего следует, что |bn | ⩽ c1 h. Для оценки количества задач, к которым сводится исходная, осталось рассмотреть полученный при преобразовании τ сферический мно15

гогранник. Его сферичность означает, что существуют точка p и радиусы r и R такие, что: B(p, r) ⊂ τ K ⊂ B(p, R), причём Rr ⩾ c2 . С помощью результатов полученных выше можно доказать теорему: Теорема 1 Количество меньших задач, к которым сводится исход√ ная, зависит только от размерности n и не превышает c1c2 n + 1. Доказательство. При работе алгоритма возникает два случая. Первый — когда ближайшая к p точка y сетки L попадает во внутренний шар, а следовательно и в многогранник. В данном случае задача считается решённой. Второй случай — когда точка y не попадает во внутренний шар, а это значит, что |y − p| ⩾ r. Используя ранее выведенные неравенства получаем: 1√ 1√ n|bn | ⩽ nc1 h; 2√ 2 c1 n 2R ⩽ h. c2 c2 R ⩽ r ⩽ |y − p| ⩽ Из этого следует, что внешний √шар, а следовательно и многогранник, пересекаются не более чем с c1c2 n + 1 указанными выше гиперплоскостями, в которых находится сетка L, так как√ расстояния между ними равны h; таким образом задача сводится к c1c2 n + 1 меньшим, а так как коэффициенты c1 и c2 зависят только от n, то и количество меньших задач зависит только от n, что и требовалось доказать. ■ При реализации данного алгоритма для атаки стоит отметить несколько моментов. Первый момент — при нахождении преобразования τ не обязательно вычислять радиусы вышеуказанных шаров. При нахождении ближайшей точки y можно проверять её принадлежность многограннику, а не внутреннему шару. Остаётся проблемой нахождение количества гиперплоскостей, которые необходимо рассмотреть. Заметим, что объём се16

чения многогранника гиперплоскостью как функция от сдвига секущей гиперплоскости является выпуклой. При нахождении коэффициента m при bn в разложении по базису точки y, m задаёт смещение центральной гиперплоскости, центральной в том смысле, что либо точка p лежит в этой гиперплоскости, либо она находится между центральной гиперплоскостью и одной из её соседних. Вместе с фактом положительности объёма многогранника и выпуклости функции это означает, что если некоторое сечение нецентральной гиперплоскости в объёме даёт ноль, то пересечение с многогранником всех следующих гиперплоскостей за рассматриваемой в том же направлении от центральной будет пустым. Эта оптимизация позволяет не вычислять радиусы, а так же не решать заведомо пустые задачи. Второй момент — для реализации атаки необходимо не только выдавать ответ на вопрос, имеет ли данная система линейных неравенств целочисленное решение, но и находить все эти решения. В этом случае ничего не остаётся, кроме как переходить ко всем меньшим задачам и в случае попадания точки y в многогранник, притом оценки на количество задач становятся неверными. Однако эти системы линейных неравенств построены таким образом, что подавляющее большинство из них не имеет решения. 4.3. Поиск преобразования В этой главе будет рассмотрен способ нахождения такого линейного обратимого преобразования τ , что многогранник переходит в сферический вид. Общая идея состоит в том, чтобы найти достаточно большой по объёму симплекс внутри многогранника, и преобразовать его к правильной форме. Из того, что симплекс большой (формально это будет показано далее) будет следовать, что многогранник ограничен пересечением двух подобных симплексов, а искомыми шарами будут шар вписанный в первый симплекс, и шар, описанный около пересечения двух симплексов. В первой части алгоритма находится произвольный симплекс, вер17

шинами которого являются вершины многогранника. Легко показать, что любой такой симплекс будет содержаться в многограннике, в силу выпуклости последнего. В качестве первой вершины v0 выбирается любая вершина многогранника (находится с помощью обычного линейного программирования с произвольной целевой функцией), а далее запускается итеративный процесс по поиску остальных вершин. Пусть уже выбраны d + 1 вершина: v0 , v1 , v2 , . . . , vd , причём вектора v1 − v0 , v2 − v0 , . . . , vd − v0 линейно независимы и образуют подпространство { d } ∑ V = αi (vi − v0 ), αi ∈ R . i=1 Для следующей вершины симплекса подходят только те v, для которых указанные вектора, а также новый вектор v − v0 будут тоже линейно независимы, то есть такие v, что (v − v0 ) ∈ / V . Для нахождения таких v строятся n − d пар линейно независимых линейных функций (в каждой паре одна равняется другой, умноженной на −1), равных нулю на V ; далее запускается процесс линейного программирования по ним. Например, можно взять n − d векторов, дополняющих вектора v1 − v0 , v2 − v0 , . . . , vd − v0 до базиса, и взять функции как скалярные произведения на эти вектора. В некоторых случаях данный итеративный процесс прекращается до того, как будут набраны все n + 1 вершин симплекса, а именно тогда, когда на некотором шаге ни одна функция не даст вершины v такой, что (v − v0 ) ∈ / V . Это произойдёт в том и только том случае, когда весь многогранник содержится в множестве V + v0 , а это значит, что его размерность меньше n, и его объём является нулевым. Как говорилось ранее, в этом случае совершается преобразование к задаче с размерностью, равной размерности многогранника, или, что то же самое, с размерностью пространства V , равной d. Для этого берётся матрица, состоящая из векторов v1 −v0 , v2 −v0 , . . . , vd −v0 , и каждый из её столбцов домножается на некоторое число так, что матрица становится целочисленной, обозначим её за W ; заметим, что её размерность равна n × d, а все её столбцы линейно независимы. Далее с помощью построения 18

Эрмитовой нормальной формы [1] можно получить матрицы U и K такие, что U W = K, где U — унимодулярная матрица, а матрица K — целочисленная матрица размерности n × d, причём под её диагональю (при i > j) все элементы нулевые. Так как матрица U унимодулярная, то и матрица U −1 тоже унимодулярная, а это значит, что столбцы u1 , u2 , . . ., un матрицы U −1 образуют базис сетки Zn . Более того, первые d столбцов матрицы U −1 являются базисом пространства V , так как W = U −1 K, все строки матрицы K ниже строки с номером d являются нулевыми, а V содержит все вектора-столбцы матрицы W . Возвращаясь к исходной задаче, необходимо найти пересечение целочисленной сетки с многогранником, что в данном случае можно записать в следующем виде: найти такие x, что x= n ∑ αi ui ∈ K ⊂ v0 + V, αi ∈ Z. i=1 Здесь x можно разложить в виде суммы x = v0 + x′ , где x′ ∈ V . Так как столбцы u1 , u2 , . . ., ud образуют базис пространства V , то коэффициенты разложения вектора x′ при векторах ud+1 , ud+2 , . . ., un нулевые, поэтому коэффициенты при разложении x при этих же векторах равны аналогичным коэффициентам у вектора v0 , которые можно легко найти. Если хоть один из них не целый, то множество v0 + V не пересекается с целочисленной сеткой. Иначе, подставляя в систему неравенств d n ∑ ∑ Ax ⩽ b x = yi ui + αi ui , где αi — полученные целые коэффициi=1 i=d+1 енты, получаем целочисленную систему линейных неравенств относительно d целочисленных переменных y1 , y2 , . . ., yd . Вторая часть алгоритма увеличивает найденный в первой части симплекс, причём увеличение происходит не до максимального по объёму симплекса, а пока его можно увеличить хотя бы в полтора раза. Симплекс увеличивается итеративно, путём замены некоторой его вершины на одну из вершин многогранника. Легко заметить, что не изменяющиеся на конкретной итерации вершины симплекса лежат в одной гиперплоскости, а объём симплекса с этими фиксированными верши19

нами линейно зависит от расстояния между меняющейся вершиной и указанной гиперплоскостью. То есть при выбранных фиксированных n вершинах симплекса максимальное увеличение его объёма достигается при выборе на место последней вершины самой дальней вершины многогранника от гиперплоскости с фиксированными вершинами. На каждой итерации перебирается вершина, которая может меняться, находится нормаль к гиперплоскости, запускается линейное программирование вдоль и против этой нормали, вершина заменяется на найденную, если увеличение объёма не меньше, чем в полтора раза. Очевидно, что данный процесс конечен, более того, количество итераций полиномиально, так как объём симплекса растёт не менее, чем экспоненциально, и ограничен конечным объёмом многогранника. После конца итеративного процесса имеем финальный симплекс. Также легко заметить, что все вершины многогранника, а следовательно и все точки многогранника, находятся от гиперплоскости каждой грани не дальше, чем в полтора раза увеличенная соответствующая высота. Данные условия показывают, что многогранник находится внутри пересечения n пар полупространств, в каждой паре полупространства ограничены параллельными гиперплоскостями, которые также параллельны соответствующей грани финального симплекса, а полупространства направлены друг на друга. Это пересечение можно представить в виде пересечения двух больших (и не обязательно равных) симплексов, подобных финальному, а коэффициенты подобия зависит только от размерности пространства (рис. 3). А это значит, что после преобразования, переводящего финальный симплекс к правильному виду (а в месте с ним и два больших, так как они подобны), отношение c2 радиусов вписанного шара в финальный симплекс и описанного шара около пересечения двух больших, будет зависеть только от n. Остаётся только составить само преобразование τ . Очевидно, его можно получить перемножив матрицу векторов-рёбер правильного симплекса на обратную матрицу ( ) v1 − v0 v2 − v0 . . . vn − v0 −1 векторов-рёбер финального симплекса. 20

y x Рис. 3: Зелёным отмечен исходный многогранник, синим — финальный симплекс, красным — два больших симплекса, серым — их пересечение. 4.4. Оптимизация поиска преобразования При использовании данного алгоритма поиска преобразования для атаки, указанные выше итеративные процессы в обеих частях алгоритма являются довольно громоздкими, так как на каждой из n итераций необходимо искать (или пересчитывать) дополняющие до базиса вектора, а также хотя бы раз запускать линейное программирование. В данной конкретной задаче можно существенно упростить алгоритм, взяв во внимание вид многогранника. Для понимания формы исходного многогранника рассмотрим систе- 21

му линейных уравнений, его задающих. j 1 i − ⩽ n−2 a1 a2 2 a2 i k 1 0⩽ − ⩽ n−3 a1 a3 2 a3 i j 1 0⩽ − ⩽ n−4 a1 a4 2 a4 0⩽ 1 ⩽ i ⩽ a1 − 1 1 ⩽ j ⩽ a2 − 1 1 ⩽ k ⩽ a3 − 1 1 ⩽ l ⩽ a4 − 1 Последние четыре пары неравенств задают легко представляемую коробку; затем она пересекается с фигурой, заданной первыми тремя парами неравенств. Для определения формы второй фигуры рассмотрим её сечения гиперплоскостью i = t при разных значениях t. После переноса слагаемого с i через знаки неравенств в каждой паре и домножения на отрицательный коэффициент, данные пары неравенств принимают следующий вид: 1 a2 a2 i − n−2 ⩽ j ⩽ i a1 2 a1 a3 1 a3 i − n−3 ⩽ k ⩽ i a1 2 a1 a4 1 a4 i − n−4 ⩽ l ⩽ i. a1 2 a1 Как видно из неравенств, в сечении получается достаточно маленький прямоугольный параллелепипед, причём при изменении i на ∆i, всё сечение сдвигается на aa21 ∆i по j, на aa13 ∆i по k и на aa41 ∆i по l. Таким образом первые три пары неравенств задают узкую, бесконечную призму, направляющей которой является вектор (a1 , a2 , a3 , a4 )T . Для представления всего многогранника в целом, необходимо пересечь данную призму с коробкой. Рассмотрим более детально пересечение бесконечной приз22

мы и четырёх гиперплоскостей, соответствующих левым неравенствам в последних четырёх парах (для других четырёх неравенств ситуация аналогичная). Координаты по i точек грани, создаваемой отсечением от бесконечной призмы такой гиперплоскостью, лежат на довольно небольшом отрезке. Для того, чтобы это понять, перепишем неравенства выше уже для i, подставив j = 1, k = 1, l = 1: ( ) a1 a1 1 ⩽i⩽ 1 + n−2 a2 a2 2 ( ) a1 1 a1 ⩽i⩽ 1 + n−3 a3 a3 2 ( ) a1 a1 1 ⩽i⩽ 1 + n−4 a4 a4 2 Также, отсечение гиперплоскостью i = 1 даёт отрезок нулевой длины: 1 ⩽ i ⩽ 1. Если самый правый из этих четырёх отрезков не пересекается со всеми остальными, то в итоге многогранником является четырёхмерный параллелепипед, в ином случае будет почти он, только для одной пары сторон вместо одной будет несколько граней. Остаётся заметить, что первый исход наиболее вероятен, так как для пересечения указанных отрезков необходимо, чтобы разность между некоторыми двумя из значений a1 , a2 , a3 и a4 была порядка 24 (считая, что порядок этих чисел — 2n ), и вероятность этого события крайне мала. Во втором случае после преобразования многогранника к сферической форме получится многогранник, близкий к параллелепипеду, так как его стороны, состоящие из нескольких граней будут почти плоскими из-за сильной вытянутости исходного многогранника. Так как в случае четырёхмерного параллелепипеда всего 16 вершин, а во всех остальных случаях вершин не сильно больше, обе части алгоритма поиска преобразования τ можно модернизировать, используя предподсчёт вершин. При известных вершинах найти n + 1 из них, которые не лежат в одной гиперплоскости — задача простая. Вторая часть алгоритма также упрощается. Пусть p1 , p2 , . . . , pverts — все вершины исходного многогранника, их количество равно verts; пусть также 23

( ) R = p1 − v0 p2 − v0 . . . pverts − v0 , а S —это n столбцов из матрицы R, соответствующих рёбрам текущего симплекса. Легко показать, T что столбцы матрицы S −1 — являются нормалями к гиперплоскостям соответствующих граней, а их модуль такой, что скалярное произведение этой нормали с произвольным вектором-ребром равно отношению текущей высоты симплекса и расстояния от конца этого ребра до гиперплоскости, содержащей сторону; как раз это и используется на каждой итерации во второй части алгоритма. Поэтому на каждой итерации вычисляется S −1 R, далее находится самое большое по модулю число в этой матрице, заменяется соответственная вершина, пересчитывается матрица S. Когда все элементы матрицы S −1 R будут по модулю меньше полутора, необходимо попытаться поменять вершину v0 , для этого в качестве нулевой вершины выбирается другая, пересчитываются матрицы S и R, запускается далее итерационный процесс. Отдельно стоит рассмотреть процесс предподсчёта вершин. Все неравенства в поставленной задаче — парные, более того, при всех трансформациях исходной задачи (преобразование τ , сведение задачи к меньшим, сведение задачи к меньшей в случае нулевого объёма многогранника) они также остаются парными. Ввиду этого можно решать подругому поставленную задачу: необходимо найти целочисленные решения x системы c ⩽ Ax ⩽ b; число строк матрицы A уменьшается вдвое. Для нахождения всех вершин n-мерного многогранника необходимо перебрать все сочетания из n граней, построить матрицу A′ из строк матрицы A, являющихся нормалями к этим граням, обратить A′ и домножить её на соответствующий вектор b′ (при стандартной задаче Ax ⩽ b). При парной постановке задачи не только уменьшается количество строк, из которых надо брать сочетания, но также отсутствуют повторяющиеся вычисления, так как для пары параллельных граней есть общая нормаль, которую не надо подставлять несколько раз в матрицу A′ . Более того, в исходной задаче, когда её размерность максимальна и равна четырём, обычно достаточно обращать матрицу всего четыре раза, так как три направления граней при нахождении вершин точно известны (направления из первых трёх пар неравенств). 24

Перед предподсчётом вершин после трансформаций исходной задачи может сложиться ситуация, когда две строки матрицы A отличаются только домножением на скаляр. В этом случае их можно объединить, при этом также снизится число сочетаний строк матрицы A в переборе. Также после нахождения всех вершин может оказаться так, что некоторые пары неравенств выполняются строго для всех вершин, а значит, и для всех точек многогранника. Такие неравенства в дальнейшем рассмотрении не нужны, так как не изменяют многогранник. Для эффективности перебора на следующих стадиях алгоритма такие пары неравенств нужно удалять. Так как часто многогранником будет являться параллелепипед, можно уменьшить количество меньших задач, к которым сводится исходная. Дело в том, что при указанном преобразовании τ , к правильному виду преобразовывается некоторый симплекс внутри параллелепипеда, центр шаров при этом оказывается не в его середине (что уменьшает радиус внутреннего шара и увеличивает радиус внешнего). Дополнительной проблемой преобразования симплекса к правильному виду является то, что при некоторых размерностях (например при n = 2) его вершины имеют иррациональные координаты, что не подходит для нашей задачи; приходится использовать приближение координат симплекса, например с помощью подходящих дробей. Есть альтернативный вариант, решающий вышеуказанные проблемы: преобразовывать к правильному виду не симплекс, а весь многогранник. Конечно, это стоит делать, когда в него вписан не только симплекс, но и соответствующий параллелепипед, что легко проверяется путём подстановки в систему n ∑ неравенств точки v0 + pi − v0 . В этом случае многогранник превраi=1 щается в гиперкуб, координаты которого, очевидно, рациональные, а отношения радиусов внутреннего и внешнего шаров лучше. 4.5. Изменение базиса Нераскрытой осталась только одна часть алгоритма — преобразование базиса к почти ортогональному виду. Общий план данной ча25

сти таков. Пусть b1 , b2 , . . . , bn — текущий базис сетки. Преобразование любого базиса сетки к любому другому, как отмечалось ранее, эквивалентно линейному преобразованию, которому соответствует унимодулярная матрица. А это, в свою очередь, значит, что в базисе можно только менять местами вектора и прибавлять один базисный вектор, умноженный на целое число, к другому. Итак, рассмотрим обычную ортогонализацию Грамма-Шмидта для рассматриваемого базиса. Обозначим за b′i проекцию вектора bi на ортогональное дополнение пространства, образованного предшествующими векторами b1 , b2 , . . . , bi−1 . Также обозначим используемые в ортогонализации коэффициенты (bi , b′j ) µij = ′ ′ , (bj , bj ) причём b′i = bi − i−1 ∑ µij b′j . j=1 В статье Ленстра [2] доказано, что для базиса условие почти ортогональности выполняется, если выполняются следующие неравенства: |µij | ⩽ 0.5, 1⩽j<i⩽n 3 |b′i + µii−1 b′i−1 |2 ⩾ |b′i−1 |2 , 1 < i ⩽ n. 4 Второе неравенство здесь означает, что вектор b′i + µii−1 b′i−1 , являющийся проекцией bi на ортогональное дополнения пространства векторов b1 , b2 , . . . , bi−2 , превосходит по длине три четверти проекции вектора bi−1 на то же пространство. Достигаются данные условия путём итеративного процесса, также указанного в статье [2]: на каждом его шаге неравенства выполняются при i, j ⩽ k, при некотором k. Если для следующего k не выполняется первое неравенство при i = k, j = k − 1, то к вектору bk прибавляется столько векторов bk−1 , чтобы оно выполнялось. Если далее второе неравенство выполняется, то исправляется первое неравенство для всех остальных j, иначе вектора bk и bk−1 меняются местами. Одновременно 26

со всеми операциями пересчитываются текущие значения для коэффициентов µij , векторов bi , а так же квадратов длин векторов b′i . Однако для задачи линейного целочисленного программирования (в части нахождения ближайшей точки сетки к центру шаров) необходимо также знать вектора b′i , поэтому в реализации они также пересчитываются. 27

5. Численный эксперимент Так как подавляющую часть вычислительного процесса занимает решение системы линейных неравенств, будет рассмотрена эффективность именно этого алгоритма. Ввиду большого количества работы с матрицами, а также из-за своей сложности, алгоритм был реализован на языке Python 2.6. Эксперимент проходил следующим образом: вычислялось среднее время работы для каждого из рассматриваемых длин ключа. Для каждой длины было взято три случайных публичных ключа, для каждого из них десять раз случайно выбирались четыре элемента и для них решалась система линейных неравенств. В итоге для каждого n было получено среднее время решения t. Так как при атаке необходимо перебрать все четвёрки весов из n (с учётом порядка), то общее время атаки оценивается временем T = n4 t. Для исследования асимптотики T предположим, что T = γnα (так как алгоритм является полиномиальным). Если взять натуральный логарифм от обеих частей, получим равенство: ln(T ) = αln(n) + ln(γ), а учитывая оценку для T получаем: ln(n4 t) = αln(n) + ln(γ) 4ln(n) + ln(t) = αln(n) + ln(γ) ln(t) = (α − 4)ln(n) + ln(γ). Стоит заметить, что нельзя брать логарифм от размерной величины, однако здесь вместо ln(t) имеется в виду ln( tt0 ), где t0 равняется одной секунде. Аналогичные рассуждения применяются и к T , а коэффициент γ при таких условностях безразмерен. Таким образом логарифм времени решения системы линейных неравенств должен линейно зависеть от логарифма длины ключа. Поэтому интересующий нас коэффициент α легко найти с помощью линейной аппроксимации графика ln(t) от ln(n) (рис. 4). 28

Рис. 4: Графики ln(t) от ln(n) и их линейные аппроксимации Линейная аппроксимация выдала коэффициент наклона a = (1.67 ± 0.18), а также смещение прямой b = (−4.5±0.6). Стоит заметить, что при отбросе из рассмотрения первых трёх точек (отклонение могло внести то, что эти точки соответствуют небольшим значениям n), остальные гораздо лучше ложатся на прямую. Второй раз полученные коэффициенты равны a = (2.07 ± 0.10), b = (−6.0 ± 0.4). Таким образом решение системы линейных неравенств выполняется за квадратичное время, а показатель у самой атаки равен 6. Остаётся отметить, что данная атака легко распараллеливается: решения систем линейных неравенств независимы и могут вычисляться на разных ядрах процессора. Для предлагаемых Мерклом и Хеллманом n = 100 при количестве ядер порядка 104 вычисления займут порядка 108 операций, что выполняется сравнительно быстро. 29

Заключение В итоге было показано, что система Меркла-Хеллмана действительно ненадёжна на практике. При продолжении её изучения можно рассматривать модификации, например, когда множество весов разбито на несколько частей, в каждой из которых веса образуют супервозрастающую последовательность только по своему модулю. Однако гораздо более широкий простор действий открывают ранцевые криптосистемы с объектами-векторами. Например, ключ в системе Нидеррайтера (одной из таких систем) обязан быть большим по памяти для обеспечения стойкости системы, это происходит вследствие малого веса используемых ошибок, и это возможно исправить. Для дальнейших исследований можно сформулировать следующую задачу: изучить основанные на теории кодирования ранцевые криптосистемы с объектами-векторами при разных способах кодирования и различных заданиях множества допустимых ошибок. 30

Список литературы [1] Kannan Ravindran, Bachem Achim. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix // SIAM Journal on Computing. –– 1979. –– Vol. 8, no. 4. –– P. 499–507. [2] Lenstra A. K., Lenstra H. W. Jr., Lovász Lászlo. Factoring polynomials with rational coefficients // Math. Ann. –– 1982. –– Vol. 261. –– P. 515– 534. [3] Lenstra H. W. Jr. Integer programming with a fixed number of variables // Math. Oper. Res. –– 1983. –– Vol. 8. –– P. 538–548. [4] McEliece R. J. A Public-Key Cryptosystem Based On Algebraic Coding Theory // Deep Space Network Progress Report. –– 1978. –– Vol. 44. –– P. 114–116. [5] Merkle Ralph C., Hellman Martin E. Hiding information and signatures in trapdoor knapsacks // IEEE Transactions on Information Theory. –– 1978. –– Vol. 24, no. 5. –– P. 525–530. [6] Niederreiter Harald. Knapsack-type cryptosystems and algebraic coding theory // Problems of Control and Information Theory. –– 1986. –– Vol. 15, no. 2. –– P. 159–166. [7] Shamir Adi. A polynomial-time algorithm for breaking the basic MerkleHellman cryptosystem // IEEE Transactions on Information Theory. –– 1984. –– Vol. 30, no. 5. –– P. 699–704. 31

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв