4.3. Применения китайской теоремы об остатках.
Китайская теорема об остатках находит широкое применение в теории чисел и криптографии.
Применение Китайской теоремы об остатках в криптосистеме RSA.
В криптосистеме RSA при расшифровании требуется вычислить ydmod n, причем известно, что n=p∙q, где p, q – большие простые числа. Как было показано ранее, степень d, в которую требуется возвести шифрованный текст, можно понизить за счет использования теоремы Эйлера. Зная разложение числа n на простые сомножители и используя китайскую теорему об остатках, возможно еще более ускорить вычисления.
Сначала вычисляют:
r1=yd mod p=(y mod p)d mod (p–1)mod p,
r2=yd mod q=(y mod q)d mod (q–1)mod q.
Как читатель мог заметить, при вычислениях для ускорения возведения в степень используется теорема Ферма.
Получим систему сравнений
.
Решая ее по китайской теореме об остатках, получим решение .
Сложность возведения в степень с использованием китайской теоремы об остатках и теоремы Ферма составляет около 6k3 против 24k3 при использовании только теоремы Ферма (где k есть размерность числа n).
Пример.
Пусть в RSA
Требуется вычислить x=10029 mod 187.
Вычисляем:
r1=(100 mod 11)29 mod 10 mod 11=19 mod 11 = 1,
r2=(100 mod 17)29 mod 16 mod 17=1513 mod 17=2.
Cоставляем систему
Пользуясь Китайской теоремой об остатках, решаем эту систему.
-
mi
11
17
Mi
17
11
M’i
2
14
Получаем
Ответ: 10029 mod 187=155.
Схема разделения секрета на основе Китайской теоремы об остатках.
На основе китайской теоремы об остатках можно построить (n,k)–пороговую схему разделения секрета. Напомним основные принципы схем разделения секрета.
Пусть существует некая информация, которую следует сохранить в секрете, и имеется n участников, не доверяющих друг другу. Эти участники хотят, чтобы секретную информацию можно было получить только при условии того, что как минимум k участников из n собрались вместе.
(n,k)-пороговая схема разделения секрета – это схема разделения секретной информации между n участниками таким образом, чтобы только k из них (или более), собравшись вместе, могли получить этот секрет. Причем вероятность угадать верное значение секрета при наличии k–m долей секрета m>0 равна вероятности угадать верное значение секрета без обладания долей секрета. При этом все участники протокола равноправны.
Как правило, схемы разделения секрета состоят из 2-х фаз: фазы разделения, когда каждому участнику протокола выдается его доля секрета, и фаза восстановления, когда k или более любых участников, собрав свои доли, восстанавливают общий секрет.
Схема разделения секрета на основе китайской теоремы об остатках выглядит следующим образом:
Пусть N – общий секрет.
Разделение секрета:
Берем p1, p2,…, pn – различные простые числа.
Часть секрета, выдаваемая i-му участнику схемы, есть число xi, вычисляемое как xi≡N(mod pi).
Заметим, что числа p1, p2,…, pn должны быть такими, чтобы произведение любых k из них было больше, чем N. А это достигается, когда для всех i выполняется pi>.
Для того, чтобы k–1 участников не смогли восстановить секрет без k-го участника, необходимо, чтобы pi << .
Итак, относительно чисел p1, p2,…, pn должны выполняться условия:
< pi << .
Восстановление секрета:
Собравшись вместе, k участников составляют и решают систему сравнений .
Решив систему, участники получают общий секрет N.
- Теоретико-числовые методы в криптографии
- Аннотация.
- Предисловие
- Введение
- Глава 1. Основы теории чисел. §1. Теория делимости.
- 1.1. Основные понятия и теоремы.
- 1.2. Наибольший общий делитель.
- 1.3 Нок (наименьшее общее кратное)
- 1.4. Простые числа
- Решето Эратосфена
- 1.5. Единственность разложения на простые сомножители.
- 1.6. Асимптотический закон распределения простых чисел.
- §2. Функция Эйлера.
- 2.1. Мультипликативные функции.
- 2.2. Функция Эйлера.
- §3. Теория сравнений
- 3.1. Свойства сравнений:
- 3.2. Полная система вычетов.
- 3.3. Приведенная система вычетов
- 3.4. Обратный элемент.
- 3.5. Алгебраические структуры на целых числах.
- 3.6. Теоремы Эйлера и Ферма. Тест Ферма на простоту.
- Тест Ферма на простоту
- 3.7. Применение теоремы Эйлера в rsa:
- §4. Сравнения с одним неизвестным
- 4.1. Сравнения первой степени.
- 4.2. Система сравнений первой степени. Китайская теорема об остатках.
- 4.3. Применения китайской теоремы об остатках.
- 4.4. Сравнения любой степени по простому модулю.
- 4.5. Сравнения любой степени по составному модулю.
- §5. Теория квадратичных вычетов
- 5.1. Квадратичные вычеты по простому модулю.
- 5.2. Символ Лежандра. Символ Якоби.
- Свойства символа Лежандра:
- Свойства символа Якоби:
- 5.3. Тест на простоту Соловея-Штрассена.
- Тест Соловея-Штрассена:
- 5.4. Решение квадратичных сравнений по простому модулю.
- 5.5. Квадратичные сравнения по составному модулю.
- 5.6. Тест на простоту Миллера-Рабина.
- 5.7. Связь задач извлечения квадратных корней и факторизации по модулю rsa. Криптосистема Рабина.
- 5.8. Квадраты и псевдоквадраты.
- 5.9. Числа Блюма.
- §6. Первообразные корни и индексы. Порождающий элемент и дискретный логарифм.
- 6.1. Основные понятия и теоремы.
- 6.2. Существование первообразных корней по модулю p.
- 6.3. Первообразные корни по модулям pα, 2pα.
- 6.4. Нахождение первообразных корней по простому модулю.
- 6.5. Существование и количество первообразных корней.
- 6.6. Дискретные логарифмы.
- 6.7. Проблема Диффи-Хеллмана.
- 6.8. Условная стойкость шифра Эль Гамаля.
- §7. Построение доказуемо простых чисел общего и специального вида.
- 7.1. Теорема Сэлфриджа и доказуемо простые числа общего вида на основании полного разложения (n—1).
- 7.2. Теорема Поклингтона и доказуемо простые числа общего вида на основании частичного разложения (n—1).
- 7.3. Числа Ферма. Теорема Пепина.
- 7.4. Числа Мерсенна.
- 7.5. Теорема Диемитко и процедура генерации простых чисел заданной длины гост р 34.10-94.
- Глава 2. Алгебраические основы теории чисел.
- §1. Основные понятия алгебры.
- 1.1. Начальные понятия.
- 1.2. Делимость в кольцах.
- 1.3. Деление с остатком.
- 1.4. Основная теорема арифметики.
- §2. Конечные поля и неприводимые многочлены.
- §3. Кольца многочленов.
- 3.1. Кольца многочленов.
- 3.2. Кольцо многочленов Zp[X].
- 3.3. Конечные поля многочленов.
- Глава 3. Алгоритмы в криптографии и криптоанализе. §1. Элементы теории сложности.
- §2. Алгоритмы факторизации.
- 2.1. Метод пробных делений.
- 2.2. Метод Ферма.
- 2.3. Метод квадратичного решета.
- 2.6. Методы случайных квадратов.
- §3. Алгоритмы дискретного логарифмирования.
- 3.1. Метод прямого поиска.
- 3.2. Шаг младенца – шаг великана.
- 3.4. Алгоритм Полига-Хеллмана.
- 3.5. Алгоритм исчисления порядка (index-calculus algorithm).
- Задачи и упражнения.
- Упражнения к Главе 2.
- Ответы к упражнениям.
- 1. Пояснительная записка
- 1.1. Цели и задачи дисциплины
- 1.2. Требования к уровню освоения содержания дисциплины
- 2. Объем дисциплины и виды учебной работы
- 3. Тематический план изучения дисциплины
- 4. Содержание разделов дисциплины
- 6. Вопросы к экзаменам
- 7.Литература основная:
- Дополнительная:
- Оглавление