![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Будем говорить, что t участников (законных пользователей) к -хранят секрет с (
), если
1.каждый знает некоторую информацию (частичный секрет)
неизвестную любому другому участнику;
2.секрет с может быть легко вычислен на основе любых к частичных секретов
3.знание любых к – 1 частичных секретов не дает такой возможности.
Множество , удовлетворяющее этим условиям, называется (к,t)-пороговой схемой.
Приведем способ построения пороговой схемы на основе теории сравнений.
Пусть зафиксированы числа к, t ().
Пусть различные натуральные попарно взаимно простые числа (
).
Обозначим через наименьшее произведение k различных модулей, а через
наибольшее произведение к – 1 различных модулей, т.е.
Модули следует выбирать так, чтобы
Случайным образом выберем число с такое, что
В качестве секретов участников возьмем наименьшие неотрицательные вычеты секрета с по модулям
, т.е.
Каждому участнику сообщаем
Построенное выше множество является (к,t)-пороговой схемой.
Пример 1. Предположим, что абоненты и
решили установить скрытую связь без передачи ключей. Для этого абоненты выбрали простое число
, абонент А выбирает секретный ключ
, абонент
выбирает секретный ключ
. Осуществить передачу сообщения
от абонента
абоненту
.
Решение. Абонент , решая сравнение
, находит свой второй секретный ключ
; абонент
, решая сравнение
, находит свой второй секретный ключ
. Затем абонент
шифрует сообщение
своим первым секретным ключом и передаёт шифрованное сообщение абоненту
:
. Абонент
, получив сообщение
, шифрует его своим первым секретным ключом и передаёт абоненту
:
. Абонент
шифрует сообщение
своим вторым секретным ключом и передает абоненту
:
. Получив это сообщение, абонент
расшифровывает его при помощи своего второго ключа:
.
Пример 2. Предположим, что абоненты и
решили установить скрытую связь с открытым ключом. Пусть
- простые числа абонента
,
,
- простые числа абонента
, телефонные книги абонентов
и
имеют вид:
,
;
,
. Осуществить передачу секретного сообщения
от абонента
к абоненту
и секретного сообщения
от абонента
к абоненту
.
Решение. Решая сравнение , абонент
находит секретный ключ
. Решая сравнение
, абонент
находит секретный ключ
. Абонент
шифрует сообщение
открытым ключом абонента
и отправляет шифрованное сообщение абоненту
:
. Получив сообщение
, абонент
расшифровывает его своим секретным ключом:
. Абонент
шифрует сообщение
открытым ключом абонента
и отправляет зашифрованное сообщение абоненту
:
. Далее абонент
расшифровывает полученное сообщение
своим секретным ключом:
.
Пример 3. Предположим, что абоненты и
решили установить скрытую связь с открытым ключом с электронной подписью. Пусть
- простые числа абонента
,
,
- простые числа абонента
, телефонные книги абонентов
и
имеют вид:
,
;
,
. Осуществить передачу сообщения
с электронной подписью от абонента
к абоненту
.
Решение. Решая сравнения и
, абоненты
и
находят свои секретные ключи
,
. Так как
, то абонент
сначала шифрует сообщение
открытым ключом абонента
:
, а затем шифрует сообщение
своим секретным ключом:
и отправляет сообщение
абоненту
. Абонент
получив сообщение
сначала расшифровывает его открытым ключом абонента
:
, а затем расшифровывает сообщение
своим секретным ключом:
.
Пример 4. Используя наименьший положительный первообразный корень по модулю и случайные числа
,
, создайте сеансовый ключ для двух пользователей
и
.
Решение. Наименьшим первообразным корнем по модулю является число
. Пользователь
выбирает случайное число
, вычисляет
и отправляет сообщение
абоненту
. Абонент
выбирает случайное число
, вычисляет
и отправляет сообщение
абоненту
. Далее абонент
вычисляет
, абонент
вычисляет
. Число
является общим ключом абонентов
и
.
Ответ: 10.
Пример 5. Проверьте, что модули
,
,
и частичные секреты
,
,
,
,
образуют (3,5)-пороговую схему, а также найдите секрет
.
Решение. Так как , то модули
,
, пригодны для реализации пороговой схемы. Система сравнений
имеет единственное решение
. Кроме того,
для любого
. Знание каких-либо двух частичных секретов
не позволяет восстановить секрет
. Следовательно, множество
образует (3,5)-пороговую схему.
Ответ: .
9.1. Применить модулярное шифрование к словам ALGEBRA и NUMBER, отождествляя латинский алфавит с
, если:
1)
2) .
9.2. Найти обратные преобразования к шифрам из предыдущей задачи и применить их для дешифрования.
9.3. Объясните необходимость условия при модулярном шифровании
.
9.4. Покажите, что композиция двух модулярных шифров ,
, где
, будет снова модулярным шифром.
9.5. Как обратить композицию двух модулярных шифров ?
9.6. Пусть :
,
:
- модулярные шифры. Найдите все значения параметров
, для которых
.
9.7. Отождествляя латинский алфавит с и применяя RSA-шифрование с параметрами
,
, зашифровать слова ALGEBRA и NUMBER и дешифровать сообщение «17, 26, 12, 12, 9».
9.8. Приняв ,
, зашифруйте сообщение
. Путем дешифрования убедитесь в корректности работы RSA-криптосистемы с выбранными параметрами. Используйте RSA-криптосистему для подписи сообщения и проверьте его подлинность.
9.9. Вычислите секретный ключ для открытого ключа в следующих двух случаях:
,
.
9.10. Пусть и
- взаимно обратные RSA-преобразования. Покажите, что
для любого
, а не только для
.
9.11. Докажите, что RSA-преобразования при фиксированном образуют группу относительно операции их композиции.
9.12. Обосновать нестойкость RSA-криптосистемы, если по ошибке вместо взяли
.
9.13. Показать, что кроме двух очевидных решений сравнение
имеет еще два решения
,
.
9.14. Покажите, что, зная , легко факторизовать RSA-модуль
.
9.15. Подпишите сообщение и проверьте подлинность, если
,
.
9.16. Покажите, что сообщение является неподвижным (
) в RSA-криптосистеме с параметрами
Найдите все неподвижные сообщения.
9.17. Покажите, что в RSA-криптосистеме с параметрами имеется
неподвижных сообщений
,
, где
.
9.18. Пусть . Зашифруйте сообщение
по системе Рабина. Путем дешифрования убедитесь в корректности работы криптосистемы Рабина с выбранными параметрами.
9.19. Предположим, что абоненты и
решили установить секретную переписку с использованием системы Рабина. Для этого они выбрали простые числа
вида
, модуль
и договорились, что будут обмениваться лишь такими сообщениями
, для которых
и
является квадратичным вычетом по модулям
и
. Докажите, что в этом случае дешифрование осуществляется однозначно.
9.20. Пусть , где
- различные простые числа вида
. Доказать эквивалентность условий:
1) существует эффективный алгоритм решения сравнения ;
2) существует эффективный алгоритм факторизации модуля .
9.21. Пусть ,
, где
- различные простые числа. Доказать, что если сравнение
имеет одно решение, то оно имеет четыре решения на промежутке
.
Дата публикования: 2015-11-01; Прочитано: 528 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!