Разработка программного средства, решающее проблему факторизации

МИНИСТЕРСТВО ПО РАЗВИТИЮ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И КОММУНИКАЦИЙ РЕСПУБЛИКИ УЗБЕКИСТАН
ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНИ МУХАММАДА АЛЬ-ХОРЕЗМИ

ПРАКТИЧЕСКАИЕ РАБОТЫ № 3-4
По предмету: Криптография 2


Выполнил: Пулатов Бекзод
Проверила: Shamshiyeva Barno Maxmudjanovna

Ташкент – 2023 г.

Практическая работа № 2
Тема: Разработка программного средства, решающее проблему факторизации
Цель работы: Формирование знаний и навыков по алгоритму Ферма и Ро-алгоритму, а также по разработке программного средства по этим алгоритмам.
Задание
Разложите на множители с помощью алгоритмов ферма и -алгоритм Полларда.

№	N
12	2173

Алгоритм Ферма:

1. Найдем ближайшее целое число квадратный корень из 2173.

√2173 ≈ 46.6 (ближайшее целое число - 47)

2. Вычислим квадраты последовательности целых чисел, начиная с 47:

47² = 2209, 48² = 2304, 49² = 2401.

3. Найдем разность между квадратом каждого числа и 2173:

2209 - 2173 = 36, 2304 - 2173 = 131, 2401 - 2173 = 228.

4. Из этих разностей выберем те, которые являются квадратами целых чисел:

36 = 6², 228 = 15².

5. Разложим число 2173 на множители:

2173 = 47 + 15 = 62
2173 = (47 + 6) (47 - 6)
2173 = 53 * 41
Алгоритм ρ-алгоритма Полларда:

1. Выберем начальное случайное число x0 = 2.

2. Вычислим последовательность чисел xi = xi-1² - 1 mod 2173, где i - порядковый номер числа в последовательности.

3. Вычислим наибольший общий делитель значения модуля и разности элементов последовательности в двух случайных точках:

d1 = gcd(2173, x10 - x7) = gcd(2173, 555) = 1

d2 = gcd(2173, x11 - x6) = gcd(2173, 293) = 1

4. Если НОД(d1, 2173) или НОД(d2, 2173) != 1, то можно разложить заданное число на множители:

2173 = d1 * (2173/d1) = 1 * 2173 = 2173

5. Если НОД(d1, 2173) или НОД(d2, 2173) == 1, то необходимо выбрать новое начальное число и продолжить алгоритм. В данном случае, можно выбрать другое случайное число и повторить шаги 2-4.

По результатам выполнения алгоритма Полларда мы не получаем новых разложений числа 2173 на множители, поэтому можем сделать вывод, что это число простое.

Ответ: 2173 простое число.

Практическая работа № 3

Тема: Разработка программного средства, решающее задачу дискретного логарифмирования
Цель работы: Формирование знаний и навыков по разработке программного средства и решению задач по алгоритму Полига-Хеллмана.
Задание
Найдите х с помощью алгоритма Полига - Хеллмана.
Варианты:

№	Уравнение
12

Алгоритм Полига-Хеллмана:

1. Выбираем простое число p и генератор g группы Zp.
2. Выбираем случайное число x и вычисляем y = g^x mod p.
3. Выполняем обмен сообщениями с другими пользователями, каждый из которых выбирает случайное число k и отправляет yk mod p.
4. Вычисляем общий ключ, используя yk, полученный от каждого из пользователей: K = (y1^k1 y2^k2 ... yt^kt) mod p, где t - число пользователей.
5. Используем общий ключ для симметричного шифрования сообщений.

Для нахождения х из условия 9^x = 19 mod 53 необходимо выполнить следующие шаги:

1. Выберем простое число p, для простоты можно взять p = 53.
2. Выберем генератор g группы Zp, таким генератором может быть 2, 3 или 5. Для простоты можно взять g = 2.
3. Вычисляем порядок группы Zp, который равен p-1 = 52.
4. Найдем характеристику простого числа p, которая обозначается как s = 2^β, где β - наибольшее целое число, такое что p-1 делится на 2^β. В нашем случае, s = 4, так как 52 делится на 4.
5. Разделяем число x на s битовых блока: x = x3x2x1x0.
6. Вычисляем последовательность чисел a1, a2, a3 ...:
a0 = g^((p-1)/s) mod p = 2^13 mod 53 = 47
a1 = a0^2 mod p = 31
a2 = a1^2 mod p = 50
a3 = a2^2 mod p = 45
7. Далее, преобразуем число y = 19 в s-ичную систему счисления:
y = 00 10 21 30
8. Разложим каждый из блоков числа y на простые множители:
00 не имеет делителей, 10 = 25, 21 = 37, 30 = 235
9. Выбираем k1, k2, k3, k4 и решаем систему уравнений:
x3k1 + x2k2 + x1k3 + x0k4 ≡ 0 (mod 4)
x3k1 + x2k2 + x1k3 + x0k4 ≡ 1 (mod 2)
x3k1 + x2k2 + x1k3 + x0k4 ≡ 1 (mod 7)
x3k1 + x2k2 + x1k3 + x0k4 ≡ 0 (mod 5)
Решением данной системы уравнений будет: k1 = 3, k2 = 0, k3 = 0, k4 = 3.
10. Вычисляем x:
x = x3k1 + x2k2 + x1k3 + x0k4 = 313 + 04 + 02 + 31 = 42.

Ответ: x = 42.