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

Цель лабораторной работы

Закрепить теоретические знания студентов по разделу: “Гомоморфное шифрование”. Ознакомиться с протоколом скрытого определения точек интереса мобильного пользователя на основе изученных алгоритмов криптосистем Пэйе и Рабина.

Исходные данные

Выбор ячейки производится следующим образом: координата = 5 + 1,

координата = ( + ) 5 + 1,

где – номер студента по журналу, – день выполнения лабораторной работы.

Получаем:

= 5 + 1 = 6 5 + 1 == ( + ) 5 + 1 = (22 + 6) 5 + 1 =

Ход работы

Генерация ключей

Выбираем два больших простых числа 1, 1, таких что 1 = 1 1 > , где= max( , ) – самое большое целое число из базы данных сервера, содержащей информацию о ближайших POIs. С учетом того, что = 14700, 1 > 14700. Числа 1, 1 выбрать из диапазона 122-160.

Также необходимо, чтобы все сгенерированные числа удовлетворяли условию: 4 = 3, где – сгенерированное простое число.

1 = 1271 = 139

1 = 1 1 = 127 139 = 17653

2 = 2167192 = 5638163

2 = 2 2 = 216719 5638163 = 1221897047197

2

Рисунок 1. Проверка соответствия чисел , заданным условиям.

Рисунок 2. Проверка соответствия чисел , заданным условиям.

Генерируем числа 1 из множества 12 и 2 из множества 22 , удовлетворяющие условию:

gcd ( 2 − 1 , ) = 1.

3

Рисунок 3. Генерация чисел , .

1 = 611668912 = 921337909203197645943869

Рисунок 4. Проверка соответствия чисел , заданным условиям.

Таким образом, имеем следующие ключи:

Рисунок 5. Сгенерированные ключи.

Формирование запроса

1. Шифрование POI типа на первом открытом ключе

Для каждого {1, 2, … , } пользователь выбирает случайное целое число1 и вычисляет криптограммы :

(1, 1) = 11 1( 12) если == { (0, 1) = 10 1( 12) если ≠ ,

где – тип точек интереса, про который пользователь запрашивает информацию.

Вычисляем криптограммы с при = 1:

4

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

2. Шифрование координаты своей ячейки на втором открытом ключе.

Для каждого ′ {1, 2, … , } пользователь выбирает случайное целое число′ 2 и вычисляет криптограммы ′′:

(1, 2) = 21′′ 2( 22) если = ′ = { (0, 2) = 20′′ 2( 22) если ≠ ,

где – первая координата ячейки, в которой находится пользователь. Вычисляем криптограммы ′ :

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

3. Шифрование координаты своей ячейки на втором открытом ключе

Далее пользователь выбирает случайное целое число 2 и вычисляет еще одну криптограмму :

= (, 2) = 2 2 ( 22),

где – вторая координата ячейки, в которой находится пользователь. Вычисляем криптограмму :

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

Все полученные криптограммы пользователь отправляет на сервер в качестве запроса.

Генерация ответа сервера

1. Шифрование значений POIs для всех ячеек на первом открытом ключе.

Вычисляется С,, где {1, 2, … , }, {1, 2, … , }:

5