Комбинированный алгоритм гомоморфного шифрования

Дьяченко Александр Сергеевич

Комбинированный алгоритм гомоморфного шифрования

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

Общественные науки в целом

Дипломы

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

ID: 587d364d5f1be77c40d58c09

UUID: 63786cb7-782e-4694-967e-f5af16b0c2d6

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

Опубликовано: почти 8 лет назад

Просмотры: 100

Дьяченко Александр Сергеевич

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

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

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

Скачать - 720725 bytes

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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ И СИСТЕМ Дьяченко Александр Сергеевич Выпускная квалификационная работа бакалавра Комбинированный алгоритм гомоморфного шифрования Направление 010300 Фундаментальные информатика и информационные технологии Научный руководитель, кандидат физ.-мат. наук, доцент Мисенов Б. А. Санкт-Петербург 2016

Оглавление Введение ................................................................................................................... 2 ГЛАВА 1. Постановка задачи, определение требований и обзор существующих методов.......................................................................................... 4 1.1 Общая постановка задачи ................................................................... 4 1.2 Основные определения........................................................................ 4 1.3 Обзор существующих методов........................................................... 5 1.3.1 Криптосистема RSA..................................................................... 5 1.3.2 Криптосистема Эль – Гамаля...................................................... 6 1.3.3 Криптосистема Пэйе .................................................................... 7 1.3.4 Криптосистема Гольдвассер – Микали ..................................... 8 1.3.5 Криптосистема Меркла – Хеллмана .......................................... 9 1.3.6 Алгоритм Полига – Хеллмана .................................................. 10 1.3.7 Криптосистема Бенало .............................................................. 11 ГЛАВА 2. Предлагаемый метод частично гомоморфного шифрования......... 12 2.1 Введение в предлагаемую систему .................................................. 12 2.2 Основные положения и генерация ключа ....................................... 14 2.3 Шифрование и дешифрование ......................................................... 15 2.4 Пример ................................................................................................ 17 2.5 Предлагаемые параметры и анализ безопасности .......................... 18 2.7 Производительность .......................................................................... 21 Заключение ............................................................................................................ 22 Список использованной литературы ................................................................... 23

Введение Проблема защиты информации, исключающего возможности прочтения ее посторонним лицом, волновала человеческий ум еще с давних времен. Так, еще на заре человеческой цивилизации утечка информации об убитом животном, могла оставить без пищи целое первобытное племя. Таким образом, с зарождением человеческой цивилизации было сформировано умение сообщать информацию одним людям так, чтобы другие не имели к ней доступа. В качестве примера, можно привести священные писания древнего Египта и древней Индии [1]. С начала XV века начинается использование примитивных методов относительно содержания шифруемых текстов, например, использовались методы кодирования стеганографии. Так, большинство изобретаемых методов шифрования текста сводилось к многоалфавитной подстановке или перестановке. Применялись такие методы шифрования, как, шифр Цезаря, состоящий в замене каждой буквы алфавита на другую букву, отстоящую от нее в алфавите на определенное число позиций. Впоследствии начинают появляться печатные работы, в которых были обобщены и сформулированы на тот момент алгоритмы шифрования является труд “Полиграфия” немецкого аббата Иоганна Трисемуса. В этом труде он описал два важных открытия: способ заполнения полибианского квадрата и шифрование пар букв. В XIX веке было сформулировано главное требование к криптографическим системам, которое остается актуальным и по нынешнее время: секретность шифра должна быть основана на секретности ключа, но не алгоритма. Так же в этом веке механизировали роторные криптосистемы, которые позволили организовать более высокую криптостойкость [2]. Одной из первых подобных систем, стала механическая машина. Практическое распространение роторные машины получили только в XX веке. В 1917 году Эдвардом Хеберном была разработана немецкая шифровальная машина, более известная как Enigma. Более активно она 2

использовалась во времена второй мировой войны. Так же были изобретены такие роторные устройства, как Sigaba, Typex и Orange. Первые криптоатаки стали возможны лишь в 40-х годах с появлением первых ЭВМ. В 70-е годы с помощью производительных и компактных машин, стало возможным применять на практике блочные шифры, появилась возможность применять первые классы криптосистем. В 1978 году был принят стандарт шифрования DES, его автором был Хорст Фейстел, именно он описал модель блочных шифров на основе которой были построены другие, более стойкие криптосистемы. Так же в 70-е годы произошел инновационный прорыв в области криптографии, появились асимметричные криптосистемы, которые в свою очередь не требовали передачи секретного ключа между сторонами. С появлением асимметричной криптографии человечеству стало доступно сразу два новых направления, такие как, системы электронной цифровой подписи и электронных денег. На рубеже XX века стали появляться новые направления в области криптографии: квантовая криптография, вероятностное шифрование и другие. Актуальной остается, и задача по совершенствованию симметричных криптосистем. 3

ГЛАВА 1. Постановка задачи, определение требований и обзор существующих методов 1.1 Общая постановка задачи Цель работы состоит в разработке оптимального подхода к получению частично гомоморфного алгоритма шифрования. Для достижения поставленной цели необходимо решить следующие задачи:  провести анализ предметной области;  исследовать существующие решения;  сформулировать требования к своей системе решения поставленной задачи;  сформировать алгоритм шифрования, удовлетворяющий предъявленным требованиям. 1.2 Основные определения В данном разделе, используем λ для обозначения уровня криптостойкости системы. Определим гомоморфную криптосистему как ξ = (KeyGenξ, Encξ, Decξ, Evalξ) – это есть соответственно четверка вероятностных полиномиальных шагов.  Генерация ключа – алгоритм (evk, sk) ← KeyGenξ (Iλ) принимает на вход параметр криптостойкости λ, выдает соответственно открытый ключ для вычисления evk и секретный ключ sk для шифрования и расшифрования.  Шифрование – алгоритм с ← Encξ (sk, m) принимает на вход секретный ключ sk и сообщение открытого текста в размере одного бита m ∈ {0,1} и выдает соответствующий шифротекст c. 4

 Дешифрование – алгоритм m* ← Decξ (sk, с) принимает на вход секретный ключ sk, шифротекст c и выдает сообщение открытого текста m* ∈ {0,1}.  Гомоморфное вычисление – алгоритм сf ← Eval (f, с1 , …. , сl) получает на вход ключ для вычисления evk, функцию f : {0,1}l →{0,1} и набор из l шифротекстов с1 , …. , сl и выдает шифротекст сf . 1.3 Обзор существующих методов 1.3.1 Криптосистема RSA Рассматриваемая криптосистема RSA [3] является одной из самых популярных, упоминается во многих источниках, связанных с безопасностью данных. Сама система использует открытый ключ. Также эта частично гомоморфная система использует односторонние функции, они же обладают свойствами:  Если известно, то f (x) вычислить просто.  Если известно y = f (x), то для вычисления x нет простого, то есть более эффективного пути. Алгоритм криптографической системы RSA обладает сложностью, сравнимой со сложностью «задачи факторизации» произведения двух больших простых чисел. Шифрование подразумевает сложность, которую можно обозначить как возведение в степень большого числа. Дешифрование, приемлемое по длительности подразумевает вычисление функции Эйлера от указанного большого числа. Чтобы достичь такого требования, т.е. приемлемого времени, необходимо обладать информацией о разложимости этого числа на простые множители. В алгоритме RSA, каждый участник системы располагает как открытыми ключом (public key), так и закрытым ключом (private key). Причем каждый такой ключ состоит из пары целых чисел, и каждый участник системы в праве создавать как открытый, так и закрытый ключ. Кроме того, следует отметить правило, что закрытый ключ 5

необходимо держать в секрете и его нельзя никому разглашать, открытый же ключ можно публиковать и сообщать кому угодно. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются взаимно обратными, то есть:  для каждых допустимых пар открытого и закрытого ключей (p, s);  существуют соответствующие функции шифрования Ep (x) и расшифрования Ds (x) такие, что для каждых сообщений m ∈ M, где M – множество допустимых сообщений, m = Ds (Ep (m)) = Ep (Ds (m)). Пусть n – модуль RSA, а e – открытый ключ шифрования. Тогда функция шифрования будет иметь вид: E(x) = xe mod n. Покажем гомоморфизм по умножению: E(m1) * E(m2) = m1e * m2e mod n = (m1m2)e mod n = E(m1m2). 1.3.2 Криптосистема Эль – Гамаля Криптографическая схема Эль-Гамаля [4] основана на сложности в вычислении дискретных логарифмов в конечном поле. Можно сказать, что данный алгоритм относится к числу тех, которые принадлежат к числу вероятностного шифрования. Схему можно найти в широком использовании алгоритмов электронной подписи и непосредственно в шифровании.Так же можно отметить, что алгоритм обладает свойством ре-рандомизации. В 1985 году это схема была предложена Эль-Гамалем. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана. Сообщение M должно быть меньше числа p. Сообщение шифруется следующим образом: 1. Выбирается сессионный ключ – случайное целое число такое, что 1 < k < p-1. 6

2. Вычисляются числа a = gk mod p и b = yk M mod p. 3. Пара чисел (a, b) является шифротекстом. Нетрудно заметить, что длина шифротекста в схеме Эль – Гамаля длиннее исходного сообщения M вдвое. Дешифровка происходит следующим образом. Зная закрытый ключ x, исходное сообщение можно вычислить из шифротекста (a, b) по формуле: M = b (ax)-1 mod p. При этом нетрудно проверить, что (ax)-1 ≡ g-kx (mod p) и поэтому b (ax)-1 ≡ (yk M)*g-xk ≡ (gxk M)*g-xk ≡ M (mod p). Так же для практических вычислений больше подходит следующая формула: M = b(ax)-1 mod p = b * a(p1-x) mod p. 1.3.3 Криптосистема Пэйе Алгоритм Пэйе [5] был впервые предложен в 1999 году, ученым Паскалем Пэйе. Суть его подхода состоит в поиске корня остатка от деления по модулю с описанием сложности такого алгоритма. А также описана применимость алгоритма в криптографических целях и указаны некоторые нюансы обеспечения безопасности криптосистемы. Однако позднее, в ходе изучения данного алгоритма, было показано, что оригинальная схема криптосистемы, перестает быть уязвимой к атакам подобного рода. Далее покажем работу алгоритма Пэйе с точки зрения генерации ключей, шифрования и дешифрования. Генерация ключей происходит следующим образом: 1. Выбираются два больших простых числа p и q, такие что gcd (pq, (p-1) (q-1) ) = 1. 2. Вычисляется n = pq и λ = lcm (p-1, q-1). 3. Выбирается случайное целое число g, такое что g ∈ Z*n2. 4. Вычисляется μ = (L (gλ mod n2))-1 mod n, где L(u) = 𝑢−1 𝑛 . Где открытым ключом является пара (n, g), а закрытым ключом пара (λ, μ). Далее покажем шифрование, которое основано на следующих правилах: 7

1. Предположим, что необходимо зашифровать открытый текст m, m ∈ Zn. 2. Выбираем случайное число r, r ∈ Z*n. 3. Вычисляем шифротекст c = gm * rn mod n2. Дешифровка: 1. Принимаем шифротекст c ∈ Z*n2. 2. Вычисляем исходное сообщение m = L (cλ mod n2) * μ mod n. 1.3.4 Криптосистема Гольдвассер – Микали Криптографическая система с открытым ключом, которая была разработана в 1982 году [6]. Данная система является первой вероятностной схемой шифрования с открытым ключом. Однако эта криптосистема проявила себя неэффективной, так как шифротекст может быть более длинным, чем шифруемое сообщение. Алгоритм шифрует текст сообщения бит за битом, причем сложность работы, связанная с поиском отдельного зашифрованного бита в тексте c, должна принадлежать множеству QRN. С точки зрения генерации ключей, шифрования и дешифрования, причем будем использовать такие понятия как, «участник 1» и «участник 2», которые и будут обмениваться сообщениями. Для того чтобы сгенерировать ключ, «участнику 1» необходимо выполнить следующие операции: 1. Выбрать два случайных числа p и q, которые будут удовлетворять условию |p| = |q| бит. 2. Вычислить значение N = pq. 3. Далее извлекаем случайное целое число 𝒚 𝒚 𝒑 𝒒 y, которое будет удовлетворять условию ( )= ( )= -1. 4. Описать пару (N, y,) в качестве открытого ключа, а пару (p, q), использовать как закрытый ключ. 8

Чтобы послать «участнику 1» зашифрованное сообщение m = b1b2…bl, «участник 2» выполняет следующие операции: for (i = 1, 2…, l) { x ← U Z*N; if (bi = = 0) ci ← x2 (mod N); else ci ← yx2 (mod N); } В данном фрагменте «участник 1» посылает сообщение «участнику 2» EN (m) ← (c1, c2, …. , cl). Получив кортеж (c1, c2,…., cl) «участник 1» выполняет следующую процедуру: for (i = 1, 2…, l) { if ( ci ∈ QRN ) bi ← 0; bi ← 1; } set m ← (b1, b2, …., bl). 1.3.5 Криптосистема Меркла – Хеллмана Криптосистема Меркла – Хеллмана [7] была основана в 1978 году. Эта система является одной из первых с открытым ключом. В ее основу была положена «задача о рюкзаке», но она оказалась криптографически нестойкой и в следствии этого не обрела должной популярности. Далее мы рассмотрим математическое описание алгоритма. Генерация ключа: Для того чтобы зашифровать n – битное сообщение, выберем возрастающую последовательность из n ненулевых натуральных чисел такую, что w = (w1, w2, …, wn). Далее случайным образом выберем целые взаимно простые числа q и r, что q> ∑𝑛𝑖=1 𝑤 i . Число q здесь выбирается таким образом, 9

чтобы гарантировать уникальность шифротекста. Если оно будет хотя бы чуть меньше, то может возникнуть ситуация, где одному шифротексту может соответствовать несколько открытых текстов. Далее рассмотрим последовательность β = (β1, β2, …, βn), где каждый элемент этой последовательности вычисляется по формуле βi = rwi mod q. Тогда как β и будет открытым ключом, а закрытый ключ образует последовательность (w, q, r). Шифрование: Для того, чтобы зашифровать сообщение, необходимо вычислить число c, которое и будет являться шифротекстом с = ∑𝑛𝑖=1 𝛼i 𝛽 i . Дешифровка: После того как полученный текст был зашифрован, получатель должен определить биты сообщения, которые удовлетворяли бы данной формуле с = ∑𝑛𝑖=1 𝛼i 𝛽 i . При этом, стоит заметить, что если бы βi было выбрано случайным, то такая задача была бы неразрешима, таким образом Дешифрование будет происходить только в том случае, если закрытый ключ (w, q, r) известен. Далее получатель зашифрованного сообщения вычисляет ć ≡ cs (mod q). Из этого тождества следует, что ć ≡ cs ≡ ∑𝑛𝑖=1 𝛼i 𝛽 i s (mod q), а из того , что rs mod q = 1 и βi = rwi mod q. Тогда ć ≡ ∑𝑛𝑖=1 𝛼i 𝑤 i (mod q), так как значение ∑𝑛𝑖=1 𝛼i 𝑤 i , находится в интервале [0, q-1]. Таким образом получателю сообщения необходимо определить αi. 1.3.6 Алгоритм Полига – Хеллмана Алгоритм Полига – Хеллмана [8] был опубликован в 1978 году, американскими математиками Рональдом Сильвером и Стивеном Полигом. Предложенный алгоритм является детерминированным и одной из особенность этого метода криптографии является то, что для простых чисел специального вида можно находить логарифм за полиномиальное время. Пусть задано сравнение вида ax ≡ b (mod p), а также известно разложение числа 10

p-1 на простые множители p-1 = ∏𝑘𝑖=1 𝑞i αi, где необходимо найти число x, 0 ≤ x <p-1, которое удовлетворяло бы ax ≡ b (mod p). Суть в том, чтобы найти x по модулям qi αi для всех i, для этого необходимо решить сравнение (ax)(p-1)/q ≡ b(p1)/q . 1.3.7 Криптосистема Бенало В заключении первой главы, опишем еще один алгоритм шифрования. В данной криптосистеме открытым ключом является модуль m, тогда как функция шифрования сообщения x представлена в виде Ԑ(x) = gxrc mod m, для случайного r ∈ {0, …, m-1}. Тогда гомоморфное свойство этого алгоритма будет проявляться в виде: Ԑ(x1) * Ԑ(x2) = (gx1r1c) (gx2r2c) = gx1+x2(r1r2)c = Ԑ(x1+x2 mod c). 11

ГЛАВА 2. Предлагаемый метод частично гомоморфного шифрования 2.1 Введение в предлагаемую систему Удивительно, но два десятилетия спустя после открытия схем шифрования с ассиметричным ключом в запасе криптографии все еще остается очень мало схем ассиметричного шифрования. Следовательно, поиск новых таких схем является непростой задачей. Более того, поиск таких схем зачастую выглядит безнадежным – большинство найденных схем либо оказываются взломанными, либо не переживают сравнения с RSA. Схема, которая предлагается в работе, использует целое n являющееся произведением простых p и q. Однако, она во многом отличается от RSA. Рассмотрим основные отличия предлагаемой схемы: 1. данные шифруются при экспоненциальной сложности вместо возведения в степень; 2. используется специальная «лазейка» для расшифровки; 3. защищенность схемы строится некоторым другим способом; 4. обладает некоторыми «алгебраическими» свойствами, которые могут оказаться полезными в практических применениях. Коротко прокомментируем эти различия: первое может дать большое преимущество в средах, с большим объемом оперативной памяти – в таких средах возможно большое ускорение операций экспоненциации. Второе – очевидно представляет интерес, в виду упомянутого вначале факта о небольшом количестве существующих схем. Без погружения в технические детали упомянем только, что «функция с лазейкой» получается путем помещения небольших простых множителей в q-1 и p-1. Чтобы понять, что значит третье отличие, нужно заметить, что если можно разложить на множители mod n, то криптосистему и RSA можно взломать. Однако, остается не совсем ясным можно ли принимать криптосистему RSA в качестве 12

эквивалента по устойчивости к взломам. По этой причине, гипотеза того, что RSA безопасно, стала обособленным предположением, формально более сильным чем указанное разложение. Предлагаемая криптосистема относится к другой гипотезе, также формально более сильной, чем разложение и известной как гипотеза большей остаточности. Это может помочь понять, как эти различные гипотезы соотносятся. И, наконец, поясним алгебраические свойства предлагаемой схемы с помощью примера: предположим, что кто-то хочет снять незначительное количество u с баланса m некоторого счета; также предположим, что баланс дан в зашифрованной форме E(m) и, что служащий, выполняющий операцию не имеет доступа к расшифровке. Криптосистема, которая предлагается в данной работе решает проблему, вычисляя E(m)/E(u) mod n, что является шифрованием нового баланса m-u. Возможность выполнять алгебраические операции такие как сложение или вычитание, имея дело только с криптограммами, имеет потенциальное применение в нескольких контекстах: 1. в схемах голосования можно получить суммарный результат, не расшифровывая индивидуальные голоса; 2. в сфере водяных знаков, это позволяет добавить метку, к зашифрованным данным. Тем не менее, в этих примерах часто требуется зашифровать данные из небольшого множества S и, как хорошо известно, детерминированные криптосистемы вроде RSA не имеют здесь большого успеха: чтобы расшифровать E(a) злоумышленник может просто сравнить зашифрованный текст со всеми имеющимися, и восстановить исходный текст. Чтобы преодолеть эту сложность, необходимо использовать вероятностное шифрование, в котором каждый открытый текст имеет много соответственных шифров, зависящих от некоторого случайного параметра, выбранного во время шифрования. Такой выбор должен сделать невозможным вскрытие исходного текста, даже если шифруются данные из очень малого множества. Это сильное требование носит название «семантической безопасности». Как 13

дальнейшее отличие от RSA, криптосистема, предложенная в данной работе, имеет очень естественную вероятностную версию, с доказанной семантической безопасностью. Вероятностные гомоморфные схемы шифрования, предложенные до настоящего момента, имеют один серьезный недостаток – плохую пропускную способность. Требуется несколько килобит, чтобы зашифровать всего несколько битов. Как было упомянуто предлагаемый подход является практикоориентированным. При этом основания системы, генерация ключей, шифрование и дешифровка предлагаются с учетом эффективности. Также проводится анализ безопасности на неформальном уровне и выводятся минимальные параметры. 2.2 Основные положения и генерация ключа Пусть σ бесквадратное нечетное B-гладкое число, где B – небольшое целое и пусть n=pq RSA модуль, такой, что ϕ(n) делится на σ и является простым по отношению к ϕ(n)/σ. Обычно, считается что B 10-битное целое и n имеет длину по меньшей мере 768 бит. Пусть g будет элементом, чей мультипликативный порядок по модулю n это большой множитель σ. Введем n и g, p и q и σ оставим в секрете. Сообщение m меньшее чем σ зашифровано gm mod n; дешифрование производится, используя простые множители σ. Генерация модуля выглядит следующим образом: выберем семейство pi из k малых нечетных различных простых чисел, где k четное. Пусть u = 𝑘 2 ∏𝑖=1 𝑝i, υ = ∏𝑘𝑘 2 +1 𝑝i и σ = uυ = ∏𝑘𝑖=1 𝑝i. Выберем два больших простых числа a и b таких что, p = 2au + 1 и q = 2bυ + 1 простые и пусть n = pq. Однако, время подобной генерации резко возрастает с увеличением модуля: a должно быть выбрано в правильном диапазоне, и протестировано на простоту, так же, как и p = 2au+1, до тех пор, пока оба теста одновременно не 14

дадут положительный результат. Вместо этого, предлагается сгенерировать a, b, v, u независимо от требований к простоте p, q, и использовать пару 24 – битных «настраиваемых простых» p' и q' (не используемых в процессе шифрования), таких, что, p = 2aup' +1 и q = 2bυq' +1 простые. Чтобы избежать интерференции с механизмом шифрования, рекомендуется убедиться, что НОК(p' q', σ) = 1 и p' ≠ q'. На практике такой подход немного медленнее, чем у RSA генерация такого же по размеру ключа. Чтобы выбрать g можно взять случайное число и убедиться, что оно имеет порядок ϕ(n)/4. Основная идея состоит в том, чтобы убедиться, что g не pi-я степень для каждого i ≤ k, проверяя, что 𝑔 ϕ(n) p𝑖 ≠ 1mod n. Вероятность 1 1 𝑝𝑖 𝑝𝑖 успеха: 𝜋 = ∏𝑘𝑖=1(1 − ), чей логарифм: ln(𝜋) ≃ − ∑𝑘𝑖=1 . Если pi первыми k простыми, это может быть вычислено как –ln ln 𝑘 и результаты являются достаточно приемлемыми для общей вероятности в вид 𝜋 ≅ 1/ ln 𝑘. Другой метод состоит в выборе для каждого индекса i ≤ k, случайного gi до тех пор, пока оно не является степенью pi-ого. С очень высокой вероятностью 𝑔 = ∏𝑘𝑖=1 𝑔𝑖 σ/pi имеет порядок ϕ(n)/4. 2.3 Шифрование и дешифрование Шифрование состоит из единичной модульной экспоненциации: сообщение m, меньшее чем σ, шифруется как gm mod n. Важно отметить, что знание σ не требуется. Нижняя граница (предпочтительно степень двойки) является достаточной, но остается неясным, насколько важно для безопасности схемы хранить σ в секрете. Тем не менее, если σ секретно, необходимы некоторые меры предосторожности [9], [10]. Также, вообще говоря, нет причины, по которой pi-ые должны быть простыми. Схема будет работать, с учетом соответствующих изменений, если pi-ые взаимно просты. Следовательно, они могут быть выбраны как степени простых, что поможет увеличить вариативность схемы. 15

Дешифрование основывается на китайской теореме об остатках [11]. Пусть pi-ые, 1≤ i ≤k являются простыми множителями σ. Алгоритм вычисляет mi = m mod pi, и получает результат используя китайскую теорему об остатках. Чтобы найти mi, имея зашифрованный текст c = gm mod n, алгоритм вычисляет ci = 𝑐 ϕ(n) pi mod n, что является в точности 𝑔 следующих несложных вычислений, где yi = 𝑔 (𝑚𝑖+𝑦𝑖𝑝𝑖)ϕ(n) 𝑝𝑖 =𝑔 𝑚𝑖ϕ(n) 𝑝𝑖 𝑔 𝑦𝑖ϕ(n) = 𝑔 𝑚𝑖ϕ(n) 𝑝𝑖 𝑚𝑖 ϕ(n) pi mod n. Это вытекает из (𝑚−𝑚𝑖) 𝑝𝑖 :ci = 𝑐 ϕ(n) 𝑝𝑖 =𝑔 𝑚ϕ(n) 𝑝𝑖 = 𝑚𝑜𝑑 𝑛. Сравнивая этот результат со всеми возможными степенями 𝑔 𝑗ϕ(n) 𝑝𝑖 можно найти верное значение mi. Другими словами, это можно записать следующим псевдокодом: for j = 0 to pi – 1 until ci = 𝑔 𝑗ϕ(n) 𝑝𝑖 𝑚𝑜𝑑 𝑛. Исходный текст m таким образом, может быть вычислен следующей процедурой: for i = 1 to k { ϕ(n) 𝑚𝑜𝑑 𝑝𝑖 𝑛 let ci = 𝑐 for j = 0 to pi – 1 { if ci == 𝑔 𝑗ϕ(n) 𝑝𝑖 mod n let mi = j} } x = ChinaReminder ({mi}, {pi}) Основная операция, использующаяся в этом алгоритме – экспоненциация по модулю, сложности log 3 (𝑛) повторенная меньше, чем: kpk < log(𝑛)𝑝𝑘 ≅ log(𝑛)𝑘 log(𝑘) < log 2 (𝑛) log log(𝑛) раз. Дешифрование соответственно занимает log 5 (𝑛) log log(𝑛) битовых операций. Это очевидно хуже, чем log 3 (𝑛) сложности RSA, но шифрование может быть оптимизированно если таблица запоминает все возможные значения 16

t[i, j] = 𝑔 𝑗ϕ(n)/𝑝𝑖 для 1 ≤ i ≤ k, 1 ≤ j ≤ i: значение mi для исходного сообщения m mod pi находится по таблице, как только вычислено с сохранять все 𝑔 𝑗ϕ(n) 𝑝𝑖 ϕ(n) 𝑝𝑖 mod n. Необязательно . Любая хэш-функция, которая различает 𝑔 𝑗ϕ(n) 𝑝𝑖 и𝑔 𝑗′ϕ(n) 𝑝𝑖 для j ≠ j’ подойдет. В практических терминах будет достаточно нескольких байт, например, приблизительно 2|pi| бит из каждого t[i, j]. Также возможно использование хэш-функций, которые не различают необходимое значение находится по таблице хэшей 𝑔 2𝑙 𝑗ϕ(n) 𝑝𝑖 значения 𝑔 𝑗ϕ(n) 𝑝𝑖 : , для l = 1,2… до тех пор, пока не пропадет неопределенность. 2.4 Пример Генерация ключа для k = 6, p = 21211 = 2 * 101 * 3 * 5 * 7 + 1, q = 928643 = 2* 191 * 11 * 13 * 17 + 1, n = 21211 * 928643 = 19697446673 и g = 131 дают таблицу: i=1 i=2 i=3 i=4 i=5 i=6 j=0 0001 0001 0001 0001 0001 0001 j=1 1996 6544 1967 6273 6043 0372 j=2 9560 3339 4968 7876 4792 7757 j=3 9400 1765 8720 0262 3397 j=4 5479 6701 7994 0136 0702 j=5 6488 8651 6291 4586 j=6 2782 4691 0677 8135 j=7 9489 1890 3902 j=8 8537 6878 5930 j=9 2312 2571 6399 j = 10 7707 7180 6592 j = 11 8291 9771 j = 12 0678 0609 17

j = 13 7337 j = 14 6892 j = 15 3370 Таблица 1. Результаты генерации ключа Где элемент {i, j} содержит 𝑔 𝑗ϕ(n) 𝑝𝑖 mod n mod 10000. Шифрование: Сообщение m = 202, с = gm mod n = 131202 mod 19697446673 = 519690214 Дешифрование: Экспоненциацией получаем: 1. с ϕ(n) 𝑝1 mod n mod 10000 = 1966 ϕ(n) 2. с 𝑝2 mod n mod 10000 = 3339 3. с ϕ(n) 𝑝3 mod n mod 10000 = 2782 4. с ϕ(n) 𝑝4 mod n mod 10000 = 7994 5. с ϕ(n) 𝑝5 mod n mod 10000 = 1890 Откуда, по таблице: 1. m mod 3 = table (1966) = 1 2. m mod 5 = table (3339) = 2 3. m mod 7 = table (2782) = 6 4. m mod 11 = table (7994) = 4 5. m mod 13 = table (1890) = 7 И, по китайской теореме об остатках: m = 202. 2.5 Предлагаемые параметры и анализ безопасности Предлагается брать σ> 2160 и |n| = 768 бит, что есть минимальный размер модуля. Если найдено разложение n, то становятся известны a и b, а также ϕ(n). Следовательно, схема взломана. Однако, схема не обязательно является 18

эквивалентной разложению. На самом деле стойкость схемы в большей мере зависит от наличия, так называемых оракулов, которые могут сказать, является ли случайное число x pi-ой степенью mod n для i=1…k. Эта проблема известна как проблема высокой остаточности, и на текущий момент является неразрешимой. Рассматривая эту версию схемы в предложенной работе, нет доказательства эквивалентности этой проблемы криптостойкости текущей схемы, но и вероятного вектора атаки также не было найдено. Также, эффективные методы факторизации, такие как квадратичное сито и NFS не получают преимуществ от знания того, что u (или υ) делится на p-1 (или q-1). Теперь рассмотрим размер σ. Чтобы избежать расчета дискретных логарифмов методом маленьких-гигантских шагов, нужно взять σ достаточно большим, 2160 это минимум. Это может быть достигнуто перестановкой первых 30 нечетных простых, которые дадут примерно 2 160.45. Также можно выбрать 16 последовательных простых из 10 бит. Так как таких простых 75, то энтропия 53 бита. Есть дальнейшие сложности, когда σ известна. Отметим, ϕ(n) что: 4𝑎𝑏 = ∏𝑘 𝑖=1 𝑝𝑖 𝜖= − 𝑝+𝑞−1 𝜎 = 𝑛−𝑝−𝑞+1 𝜎 , следовательно, 4ab отличается от n/σ только на . Числитель имеет размер |𝑛| 2 , следовательно, если он не превосходит знаменатель на большое число бит, то 𝑎𝑏 известно и шифрование взломано. Когда точное разложение множителей σ на u и υ известно, предыдущий анализ можно продвинуть дальше. Сокращая соотношение 𝑛 = (2𝑎𝑢 + 1)(2𝑏𝜐 + 1) mod u находим, что n = 2bυ + 1 mod u и можем вычислить, d = b mod u. Похожим образом, можно вычислить c = a mod υ. Пусть a = 𝑟𝜐 + 𝑐 и 𝑏 = 𝑠𝑢 + 𝑑, r и s, неизвестны, тогда используя тот факт, что 𝜎 = 𝑢𝜐, получаем выражение: 𝑛 = (2𝑟𝜐𝑢 + 2𝑐𝑢 + 1)(2𝑠𝑢𝜐 + 2𝑑𝑢 + 1) = 4𝑟𝑠𝜎 2 + 2𝜎[𝑟(2𝑑𝜐 + 1) + 𝑠(2𝑐𝑢 + 1)] + (2𝑐𝑢 + 1)(2𝑑𝜐 + 1), которое в свою очередь имеет форму: 𝑛 = 4𝑟𝑠𝜎 2 + 2𝜎(𝛼𝑟 + 𝛽𝑠) + 𝛾. 19

С известными α, β, γ. Сокращая на mod σ2 ,, получаем 𝛿 = 𝛼𝑟 + 𝛽𝑠 𝑚𝑜𝑑 𝜎, заметим, что пара r, s лежит на двумерной решетке, определенной: 𝐿 = {(𝑥, 𝑦)|𝛼𝑥 + 𝛽𝑦 = 𝛿 𝑚𝑜𝑑 𝜎}. Также, легко увидеть, что α и β ограничены 2*σ, а γ ограниченна 4*σ2. Из этого получаем: 𝑟𝑠 ≤ 𝑛 4𝜎 2 ≤ 𝑟𝑠 + 𝑟 + 𝑠 + 1 = (𝑟 + 1)(𝑠 + 1). Следовательно пара (r, s) лежит очень близко к границе кривой C с уравнением 𝑥𝑦 = 𝑛 4𝜎 2 . Точнее, расстояние между парой (r, s) и кривой не превышает √2. Это определяет геометрическую область, включающую (r, s). Также, обычно, процедура генерации ключа накладывает ограничения, которые сокращают диапазон возможных параметров. По этой причине кривую можно заменить линией 𝑥 + 𝑦 = √𝑛 2𝜎 , чтобы вычислить площадь A. Что √𝑛 приводит к приближению: 𝑂( ). Количество точек на сетке L на этой области 𝜎 измеряется отношением размера A и определитель: √𝑛 2𝜎 . Для обеспечения безопасности необходимо убедиться, что это множество за границей поиска, что можно выразить следующим соотношением: 𝑛 ≫ 𝜎 4 . Заметим, что отношение |𝑛| 𝜎 - скорость роста криптосхемы. Разумеется, необходимо сделать ее настолько низкой, насколько возможно. С другой стороны, имея ввиду все выше сказанное, необходимо чтобы соотношение |𝑛| 4 − 𝜎 было достаточно большим. Асимптотически это достижимо если скорость роста больше 4. Для реальных приложений можно принять во внимание эвристическую границу, |𝑛| 4 − 𝜎 ≥ 128, что сопоставимо с ранее предложенными минимальными параметрами. Большие параметры, дают незначительное улучшение в скорости роста. 20

2.7 Производительность Несмотря на скорость роста криптосистема довольно эффективна: шифрование требует возведения постоянно 768 битного числа в 160-битную степень. Несколько пакетных и пред-обработочных приемов могут ускорить это вычисление, что является небольшим преимуществом над RSA. Дешифрование несколько более сложно, так как требуется k экспоненциаций. Но их число может быть сокращено несколькими способами. Во-первых, во время вычисления 𝑐 ϕ(n)/𝑝𝑖 для каждого i возможно сохранить вначале 𝑐 ′ = 𝑐 4𝑎𝑏 𝑚𝑜𝑑 𝑛 и возвести 𝑐′ в последовательные степени 𝜎 𝑝𝑖 таким образом, что последующие экспоненциации будут включать в себя 160битные степени. Проводя сбор данных по количеству модульных перемножений, полученных в результате работы схемы |n| = 768 и выбором шестнадцати 10битных простых показывает, что общее количество модульных перемножений снижается до 2352: 912 для вычисления c’ и 1440 для оставшегося. Однако, часть с «умножением» также может быть амортизирована. Результирующая нагрузка ниже, чем требуется для пары RSA шифровок с похожим модулем. К сожалению, есть один недостаток в уменьшении значения k: в случае 30 простых необходимо хранить 1718 различных хэш-значений t[i, j]. Хэширование по двум байтам является достаточным, и результирует в общее требование по памяти равное 4 килобайтам. В случае использования 16 простых необходимо хэшировать по 3 байта, что ведет к потреблению памяти в 100 килобайт. Однако, как было упомянуто ранее размер хэш-таблицы может быть значительно сокращен по цене незначительного прироста в процессорном времени. Другое ускорение может быть получено путем раздельного выполнения дешифровки mod p и mod q, чтобы получить преимущество операндов меньшего размера. Только это сокращает нагрузку в четыре раза. 21

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

Список использованной литературы 1. Бауэр Ф. Расшифрованные секреты. Методы и принципы криптологии. М.: Мир, 2007, 550 c. 2. Жельников В. Становление науки криптологии // Кpиптография от папируса до компьютера. – М.: ABF, 1996, 335 с., ISBN 5-87484-0540. 3. Rivest R. L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems.,15 4. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. 11.5.2 The ElGamal signature scheme //Handbook of applied cryptography.,794 5. Варновский Н. П., Шокуров А. В. Гомоморфное шифрование Труды ИСП РАН, 2007, С. 27–36. 6. Мао В. Современная криптография: Теория и практика, М.: Вильямс, 2005, 768 с. ISBN 5-8459-0847-7 7. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C., М.: Триумф, 2002., 816 с. , 3000 экз. — ISBN 5-89392-055-4. 8. J. Hoffstein, J. Pipher, J. H. Silverman. An Introduction to Mathematical Cryptography. - Springer, 2008., 524 с., ISBN 978-0-387-77993-5. 9. M. Rabin, Digitized signaturm and public-key functions as intractable as factorization, MIT/LCS/TR- 212, MIT Laboratory for Computer Science, 1979. 10. A. Shamir, MA for paranoids, CryptoBytes, vol. 1-3, pp. 1-4, 1995. 11. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии., М.: МЦНМО, 2003., 328 с.,1000 экз.,ISBN 5-94057-103-4. 23

Рецензии:

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

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

Отзывы:

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