Лабораторные и практики / 10_ЛР / 10-2_ЛР
.pdfМИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА» (СПбГУТ)
_____________________________________________________________________________
Кафедра информационной безопасности телекоммуникационных систем Дисциплина «Основы криптографии с открытыми ключами»
Лабораторная работа 10-2
«Исследование протокола скрытого определения местоположения точек интереса мобильного пользователя с учетом типа POI»
Выполнила: |
студ. гр. |
|
. |
.
Проверил: |
проф. Яковлев В.А.. |
Санкт-Петербург
2021
Цель лабораторной работы
Закрепить теоретические знания студентов по разделу: “Гомоморфное шифрование”. Ознакомиться с протоколом скрытого определения точек интереса мобильного пользователя на основе изученных алгоритмов криптосистем Пэйе и Рабина.
Исходные данные
Выбор ячейки производится следующим образом: координата = 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, 2 , так, чтобы |
|||||||||||
2 |
∙ 100 < |
< 4 |
, |
где |
|
= |
. |
Числа , |
выбрать, исходя из |
||||||
1 |
|
2 |
|
1 |
|
|
|
2 |
2 |
2 |
|
2 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
диапазона: |
> √ 2 |
∙ 100, |
|
< √ 4 |
. |
|
|
|
|||||||
|
2 |
|
1 |
|
|
|
2 |
|
|
1 |
|
|
|
|
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
, = ∏ , ,2( 12) .
=1
2. Вторичное шифрование POIs и дополнительное шифрование для координаты на втором открытом ключе.
Для каждого = {1,2, … , } выбирается |
– |
целое число из множества |
||||||
|
|
|
|
|
|
|
2 |
|
и вычисляется = { , , … , }: |
|
|
|
|
||||
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
2 |
( 2). |
|||
|
= ( |
|
) ∏ ′ |
, |
||||
|
||||||||
|
|
|
|
|
|
2 |
=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.Как производится шифрование и расшифрование в криптосистеме Пэйе?
Шифрование:
Предположим, что необходимо зашифровать открытый текст , где
|
. Выбираем случайное число k |
и вычисляем криптограмму: |
|
|
|
( ) = = gm ∙ ( 2)
Дешифрование:
= ( 2)
4.Как производится шифрование и расшифрование в криптосистеме Рабина?
= ш = ( ) − открытый ключ;= р = (, ) − закрытый ключ;= ;
ϵ (0, 1, 2, … , − 1);
Шифрование:
|
= 2mod , |
= 1, 2, … ; |
|
|
|
10