Алгоритмы разложения чисел на множители для построения системы RSA

Оглавление
Введение
RSA
Выделение полного квадрата (Алгоритм Ферма)
Квадратичное решето
Поиск необходимого множества делителей
Алгоритмы факторизации Полларда (методы Монте-Карло)
Метод Монте-Карло 1: поиск цикла в рекуррентной последовательности
Метод Монте-Карло 2: (p-1)–алгоритм Полларда
Заключение
Список литературы
?

Пусть p — делитель числа m. Рассмотрим элементы последовательности (2) по модулю p (т.е. образы элементов bi при каноническом эпиморфизмеZm → Zp): c0 ≡ b0(mod p), c1 ≡ b1(mod p), c2 ≡ b2(mod p), ... (3) Так как в Zp меньше элементов, чем в Zm, то с большой вероятностью период последовательности (3) меньше, чем период последовательности (2). Следовательно, найдется пара индексов i, j такая, что ci = cj, bi ≠ bj. Это означает, что bi ≡ bj(modp), bi ≠ bj(modm). Отсюда вытекает, что (bi - bj) делится на p, но не делится на m. Следовательно, НОД(bi - bj, m) нетривиален, и нам удалось разложить m на множители. Итак, алгоритм Полларда 1 сводится к поиску цикла в бесконечной рекурсивной последовательности, состоящей из элементов конечного множества. При этом вместо того, чтобы сравнивать между собой два элемента, мы вычисляем наибольший общий делитель их разности и числа m. Алгоритм завершается, когда наибольший общий делитель нетривиален. Можно предложить 2 способа решения задачи поиска цикла в последовательности. Первый способ наиболее простой. Второй чуть-чуть сложнее, но зато более быстрый. Способ 1 Выполняется следующая последовательность сравнений: b0 ↔ b1b1 ↔ b3b2 ↔ b5b3 ↔ b7b4 ↔ b9. . . bi ↔ b2i+1. . . Рано или поздно мы дойдем до равенства двух элементов, поскольку расстояние между сравниваемыми элементами на каждом шаге увеличивается ровно на единицу; кроме того, левый элемент сдвигается вправо, так что он рано или поздно войдет в периодический участок последовательности. Выпишем алгоритм нахождения делителя. алгоритм факторизация1(вход: целое число m,| выход: целое число d): успех| дано: целое число m| надо: получить нетривиальный делитель d числа m| возвращаемое значение: true, если удалось разложить,| false в противном случаеначало| maxSteps := 1000000 // Максимальное число шагов| step := 0|| b0 := случайное число в интервале 0..m| b1 := mod(b0 * b0 + 1, m)| d := gcd(b1 - b0, m)|| циклпока step < maxSteps && d == 1 // ПокаНОДтривиален| |выполнять| | b0 = mod(b0 * b0 + 1, m) // Применяем отображение f| | b1 = mod(b1 * b1 + 1, m); // один раз к b0 и дважды| | b1 = mod(b1 * b1 + 1, m) // к b1| | d := gcd(b1 - b0, m)| | step := step + 1| конец_цикла|| вернуть (d != 1) // Успех := d нетривиаленконец_алгоритмаНа каждом шаге цикла мы трижды вычисляем значение отображения f. Небольшая модификация алгоритма позволяет делать это только один раз. Способ 2 Выполняется следующая бесконечная последовательность сравнений b0 ↔ b1b1 ↔ b2b1 ↔ b3b2 ↔ b4b2 ↔ b5b2 ↔ b6b2 ↔ b7b4 ↔ b8b4 ↔ b9b4 ↔ b10. . . b4 ↔ b15b8 ↔ b16b8 ↔ b17. . . b8 ↔ b31. . . Вся последовательность сравнений разбивается на серии. В очередной серии мы сравниваем элемент bs, где s — степень двойки, последовательно с элементами b2s, b2s+1, b2s+2, ..., b4s-1. Серия содержит 2s сравнений. Выпишем алгоритм. алгоритм факторизация2(вход: целое число m,| выход: целое число d): успех| дано: целое число m| надо: получить нетривиальный делитель d числа m| возвращаемое значение: true, если удалось разложить,| false в противном случаеначало| maxSteps := 19 // Максимальная длина серии 2^19| step := 0|| b0 := случайное число в интервале 0..m| b1 := mod(b0 * b0 + 1, m)| a := b1 // Первый элемент серии| seriesLength := 1 // Длина серии| d := gcd(b1 - b0, m)|| цикл пока step < maxSteps && d == 1 // пока НОД тривиален| | выполнять| | Инвариант:| | b0 - элемент последовательности с индексом,| | равным нулю или степени двойки| | a - элемент, индекс которого равен удвоенному индексу| | элемента b0 (или 1, если индекс b0 равен 0)| | seriesLength == удвоенному индексу элемента a| | d := gcd(b1 - b0, m)| | len := 0| || | циклпока d == 1 иlen < seriesLength| | | выполнять| | | b1 = mod(b1 * b1 + 1, m);| | | d := gcd(b1 - b0, m)| | | len := len + 1| | конец_цикла| || | b0 := a| | a := b1| | seriesLength := seriesLength * 2| конец_цикла|| вернуть (d != 1) // Успех := d нетривиаленконец_алгоритмаМетод Монте-Карло 2: (p-1)–алгоритм ПоллардаПусть m — целое число, которое мы раскладываем на множители. Оно представимо в виде произведения степеней простых чисел m = p1e1p2e2 ... pkekПредположим, что p1-1 представимо в виде произведения степеней простых чисел, причем каждая из этих степеней не очень велика. Более точно, существует N такое, что p1-1 = q1a1q2a2 ... qrar, q1a1 < N, q2a2 < N, ..., qrar < N. Рассмотрим всевозможные максимальные степени простых чисел, не превосходящие N. Например, пусть N = 20, тогда рассматриваются степени простых 16, 9, 5, 7, 11, 13, 17, 19. Обозначим эти степени простых через t1, t2, ..., ts. Выберем произвольное целое число b. Рассмотрим последовательность b0 = b, b1 = b0t1 (mod m),b2 = b1t2 (mod m), ..., bs = bs-1ts (mod m) Каждый раз, вычислив bi, вычисляем одновременно НОД(bi - 1, m). Утверждается, что с большой вероятностью на каком-то шаге этот НОД будет нетривиальным делителем N. Действительно, покажем, что p | НОД(bs - 1, m). Действительно, bs = bt1t2 ... tsи, поскольку по предположению, p1 - 1 | t1t2 ... ts, то есть t1t2 ... ts = (p1 - 1)g, то bs = bt1t2 ... ts = b(p1 - 1)g = (b(p1 - 1))g ≡ 1 (mod p1) по малой теореме Ферма. Значит, bs - 1 делится на p1, число m также делится на p1, следовательно, НОД(bs - 1, m) делится на p1. Проиллюстрируем алгоритм на простом примере. Возьмем N = 20. Выпишем все степени простых, не превосходящие 20: t1 = 16, t2 = 9, t3 = 5, t4 = 7,t5 = 11, t6 = 13, t7 = 17, t8 = 19. Попытаемся разложить на множители число m = 41779 = 41·1019. Выберем b = 2. Последовательно вычисляем 216 (mod 41779) ≡ 23757, gcd(23757 - 1, 41779) = 1,237579 (mod 41779) ≡ 7970, gcd(7970 - 1, 41779) = 1,79705 (mod 41779) ≡ 33580, gcd(33580 - 1, 41779) = 41. Мы получили нетривиальный делитель на третьем шаге, поскольку 41-1 = 8·5 делит (t1t2t3) = 16·9·5. ЗаключениеВ связи со схемой RSA возникает ряд алгоритмических задач. 1. Для генерации ключей нам надо уметь генерировать большие простые числа. Близкой задачей является проверка простоты целого числа. 2. Для взламывания ключа в RSA нужно уметь раскладывать целое число на множители (или, что практически то же самое, уметь вычислять функцию Эйлера). Взлом ключа может интересовать только преступников, но, с другой стороны, те, кто пытаются защитить информацию, должны быть уверены, что задача разложения на множители достаточно сложна. Список литературыRivest R. L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems (англ.) // Communications of the ACM. — New York, NY, USA: ACM, 1978. — Т. 21. — № 2, Feb. 1978. — С. 120—126. — ISSN 0001-0782. — DOI:10.1.1.40.5588Menezes A., P. van Oorschot, S. Vanstone. Handbook of Applied Cryptography. — CRC-Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications). — ISBN 0-8493-8523-7ВенбоМао.Современнаякриптография. Теорияипрактика = Modern Cryptography: Theory and Practice. — М.: Вильямс, 2005. — 768 с. — 2000 экз. — ISBN 5-8459-0847-7, ISBN 0-13-066943-1Фергюсон Н, Б. Шнайер.Практическаякриптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М.: Диалектика, 2004. — 432 с. — 3000 экз. — ISBN 5-8459-0733-0, ISBN 0-4712-2357-3Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = AppliedCryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4