Материал: 10-2_ЛР

, = ∏ , ,2( 12) .

=1

2. Вторичное шифрование POIs и дополнительное шифрование для координаты на втором открытом ключе.

=1

Вычисление криптограмм R:

Рисунок 9. Вычисление криптограмм .

После того, как сервер вычислил криптограммы R, он посылает их пользователю в качестве ответа на полученный запрос.

Получение ответа

Пользователь получает ответ от сервера в виде = { 1, 2, … , }:

Рисунок 10. Получение пользователем криптограмм .

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

В нашем случае выбираем криптограмму 2.

6

Рисунок 11. Выполнение алгоритма дешифрования.

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

Для вычисления координат и типа POI переводим d в двоичную форму (длиной 8 бит):

= 100 = 011001002

Первые три бита содержат первую координату, следующие три бита – вторую координату, последние два бита – тип точки интереса. При этом к значениям каждой группы битов нужно добавить 1. Таки образом видим, что ближайший банкомат (t = 1) находится в ячейке: {4; 2}.

7

Видим, что полученное значение совпадает с данными на карте:

Рисунок 12. Проверка по карте.

Попробуем расшифровать криптограмму полученную от сервера, порядковый номер которой не равен второй координате = 2:

Рисунок 13. Попытка расшифровки криптограммы с индексом ≠ .

8

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

Повторим процедуру скрытого определения POIs для остальных типов POIs (при использовании тех же ключевых данных). Получаем следующие результаты:

Ближайшая велосипедная парковка: (5, 2) Ближайшая аптека: (5, 3)

Ближайшее отделение почты: (5, 5)

Видим, что полученные значения также совпадают с данными на карте:

Рисунок 14. Проверка по карте.

9

Контрольные вопросы

1. Что такое гомоморфное шифрование?

2. Какими гомоморфными свойствами обладает данная система шифрования?

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

( ( 1) ∙ ( 2) 2) = ( 1 + 2)

Второе свойство: при дешифровании криптограммы, возведенной в

степень , будет получено произведение открытого текста и

показателя степени :

((( )) ) 2 = ∙

3.Как производится шифрование и расшифрование в криптосистеме Пэйе?

Шифрование:

Предположим, что необходимо зашифровать открытый текст , где

( ) = = gm ∙ ( 2)

Дешифрование:

= ( 2)

4.Как производится шифрование и расшифрование в криптосистеме Рабина?

= ш = ( ) − открытый ключ;= р = (, ) − закрытый ключ;= ;

ϵ (0, 1, 2, … , − 1);

Шифрование:

10