Пороговая схема. 1 страница

Будем говорить, что 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. Пусть , , где - различные простые числа. Доказать, что если сравнение имеет одно решение, то оно имеет четыре решения на промежутке .