Реализация алгоритма гомоморфного шифрования

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

1. Области применения гомоморфного шифрования

1.1. Криптографическая защита смарт-карт

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

1.2 Облачные системы

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

Гомоморфное шифрование — это средство, которое позволит работать с зашифрованными данными, также, как и с открытыми.

1.3. Обфускация для защиты программных продуктов

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

2.  Обзор некоторых систем гомоморфного шифрования.

Говоря о гомоморфном шифровании, можно привести в пример такие схемы, как:

• Somewhat Homomorphic Encryption.
• Схема гомоморфного шифрования на основе матриц.
• Схема полного гомоморфного шифрования на основе матричных полиномов.

В каждой гомоморфной криптосистеме можно выделить некоторые общие алгоритмы

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

• Генерация ключей процесс создания открытого ключа (openKey) и секретного ключа (secretKey)
• Алгоритм шифрования позволяет осуществить шифрование открытого текста(AlgEncrypt)
• Алгоритм дешифрования заключается в расшифровке шифрованного текста (AlgDecrypt)
• Гомоморфное вычисление

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

C=AlgEncrypt(openKey, O)                                                                                                      (1)

Алгоритм дешифрования является обратным алгоритму шифрования.

O=AlgDecrypt(secretKey, C)                                                                                                    (2)

Принцип гомоморфного вычисления заключается в том, что пользуясь некой математической функцией M() и двумя текстами t1, t2 в результате мы получаем шифрованный текст С, при этом

C=Estimation(M(), t1, t2)                                                                                                       (3)

O=Decrypt(secretKey,C)=M(O1,O2)                                                                                             (4)

Некоторые описываемые алгоритмы обладают высокой математической сложностью, что осложняет программирование данных математических вкладок. Мы представим анализ одной из схем, а именно Somewhat Homomorhic Encryprion.

3.  Схема Somewhat Homomorphic Encryption

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

• Число должно быть много больше N;
• Число должно быть взаимно простым с N.

Этапы шифрования:

1) Выбор числа N

Группа целых чисел, с которыми будет способна работать криптосистема генерируется как, группа вычетов по модулю N. Таким образом в качестве открытого текста могут выступать числа от 0 до N.

2) Генерация ключей (KeyGeneration)

1.Секретный ключ - secretKey.

Генерируется случайное число secretKey, такое что secretKey >> N и НОД(secretKey, N) = 1.  В нашей реализации накладывается еще одно условие: secretKey не может быть больше 2^31, так как мы использовали тип данных “int”

2.Открытый ключ - openKey.

Открытым ключом является набор больших чисел {p₁,p₂,..,p_n} таких что p_i mod N=2e_i, где e_i числа намного меньше N. В нашей реализации n является константой и равняется 100.

3) Шифрование (Encrypt)

Алгоритм шифрования принимает на вход открытый текст m и открытый ключ openKey. Из набора openKey случайным образом выбирается 50 элементов pi и суммируются с m. Таким образом шифрованный текст = m + i = 050pi

4) Дешифрование (Decrypt)

Алгоритм дешифрования принимает на вход шифрованный текст c и секретный ключ secretKey. Открытый текст m = (с mod seceretKey) mod N.

5) Операции над шифрованным текстом (Estimation)

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

Достоинства данной схемы:

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

Минусы данной схемы:

• Данная схема оперирует с числами из группы вычетов некоторого числа N, что означает, что множество открытых текстов - конечное.
• В данной схеме доступна только операция сложения.

4. Заключение

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