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

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

Свойство полного гомоморфизма в математической записи можно представить следующим образом:

Концепция полностью гомоморфного шифрования (Fully Homomorphic Encryption) была разработана в 1978 году авторами алгоритма шифрования RSA – Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом. Разработка велась совместно с Майклом Дертузосом. Они предположили возможность проведения операций над зашифрованными данными без потребности в их расшифровке.

В то время все попытки создания полностью гомоморфной криптосистемы не увенчались успехом. Разработанные криптосистемы Эль-Гамаля, Гольдвассер – Микали, Пайе обладали гомоморфизмов лишь по одной операции (были частично гомоморфными).

Настоящим прорывом в исследовании полностью гомоморфного шифрования является публикация диссертации Крейга Джентри в 2009 году с названием «Fully Homomorphic Encryption based on Ideal Lattices», в которой он представил модель полностью гомоморфной криптосистемы. С того времени появилось большое количество работ, в которых предлагаются разные модификации схемы Джентри для повышения производительности. Одновременно с разработкой модификаций для уже существующей схемы полностью гомоморфного шифрования (ПГШ) ученые ведут активные поиски альтернативных способов построения полностью гомоморфных криптосистем, например, использование симметричного шифрования вместо шифрования с открытым ключом, полиномов от одной или многих переменных, а также матричных полиномов.

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

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

Гомоморфное шифрование также находит применение в поисковых системах, где оно используется для обеспечения «приватного поиска». В данном случае поисковый сервер получает от пользователей зашифрованные запросы, которые он не может расшифровать, не зная ключа пользователя. Результаты поиска также предоставляются пользователю в зашифрованном виде. Наконец, гомоморфное шифрование используется в системах электронного голосования, в частности, при применении подписи вслепую.

1. Криптосистема Крейга Джентри

В 2009 году исследователь из IBM Крейг Джентри в своей диссертации «Fully Homomorphic Encryption based on Ideal Lattices» доказал возможность полного гомоморфного шифрования и предложил свою схему. Рассмотрим эту схему на примере вычислений в Z₂, то есть в вычислениях над битами.

В качестве секретного ключа выберем произвольное целое нечетное число p, оно будет иметь вид .

Пусть требуется зашифровать бит . Для этого построим число z по правилу , где r­ – произвольное число. Такое построение значит, что . Шифрование заключается в том, что m сопоставляется число , где q – произвольно. Число c отправляется на вычисления [6].

Рассмотрим процесс расшифровки. Пусть есть число c, шифрующее неизвестный бит m. Предполагается, что p – секретный ключ – нам известен. Тогда,

.

Параметр r называется «шумом» или «ошибкой». Для того чтобы получить исходный бит, необходимо вычислить:

.

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

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

1. Шифрование на гомоморфизме колец полиномов

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

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

Первый этап шифрования – сопоставление полинома исходному числу. Пусть у нас есть число , сопоставим ему полином , где коэффициенты a_1, … ,a_k выбираются случайно. Аналогично сопоставим числу полином b (x). Заметим, что свободные члены полиномов и равны и соответственно.

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

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

1. Анализ реализации выбранного алгоритма шифрования

1. Реализация алгоритма в приложении

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

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

1. По заранее выбранной степени сопоставляемого операндам полинома, для каждого операнда генерируется и ставится в соответствие определенный полином для операнда a и для операнда b, коэффициенты a_1, … , a_m и b_1, … , b_n выбираются случайно, причем a₀ = a и b₀ = b.

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

3. Клиент проводит операцию шифрования с использованием шифрующего полинома. Происходит отображение , другими словами, проводится замена переменной x на c(y) в сгенерированных полиномах. Результатом выполнения операции шифрования является два полинома, полученных с помощью замены переменных.

4. Данные зашифрованные полиномы, а также операция, которая должна быть выполнена над ними, отправляются на сервер.

5. На сервере происходит выполнение операции над полиномами, результатом которой является результирующий полином.

6. Сервер отправляет клиенту, полученный результирующий полином.

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

1. Анализ криптостойкости алгоритма

Для того чтобы всесторонне изучить выбранный алгоритм гомоморфного шифрования в процессе выполнения данного дипломного проекта, было решено оценить такое криптографическое свойство как криптостойкость – это способность алгоритма шифрования противостоять криптоанализу. Для оценки криптостойкости алгоритма рассмотрим три наиболее распространённые атаки на алгоритмы:

• атака методом полного перебора;

• атака на основе подобранного шифртекста;

• атака на основе подобранного открытого текста.

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

В рассматриваемом алгоритме секретным ключом является сгенерированный полином . Следовательно, для того, чтобы реализовать атаку методом полного перебора, злоумышленнику требуется перебрать все возможные комбинации . Количество чисел, которые будут входить в машинное множество целых чисел, зависит от реализации типа целых числе и от используемых библиотек, а также ограничено объемом оперативной памяти. В процессе реализации алгоритма для дипломного проекта для вычислений использовался тип BigInteger (System.Numerics) на языке C#, а для генерации начальных коэффициентов полиномов использовался тип Int32, который позволяет хранить 2³² различных значений. При использовании данной конфигурации, атака методом полного перебора осуществить практически невозможно. Следовательно, можно сделать вывод о том, что данный алгоритм устойчив к атакам методом полного перебора.

Рассмотрим следующие два типа атак на криптографические алгоритмы, такие как: атака на основе подобранного шифртекста и атака на основе подобранного открытого текста.

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

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

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

Список файлов ВКР