Study/Cycles/RSA
Материал из ProgSchool
RSA
Лекции
- Решение диофантовых уравнений вида ax = by + 1
- Алгоритм быстрого возведения в степень, Малая теорема Ферма
- Функция Эйлера, RSA
- Цифровая подпись
- Шифрование в быту: что происходит внутри повседневных программ во время шифрования данных
Задачи
Алгоритм быстрого возведения в степень (2)
Даны три числа: A, B, C. Надо найти остаток от деления на C числа AB
Материалы: статья в Википедии
Прикрутить алгоритм быстрого возведения в степень к BigInteger. (2)
Материалы: документация по BigInteger
Проверить эффективность и правильность своей программы можете на следующем примере: http://projecteuler.net/problem=48
Универсальный алгоритм возведения в степень для Integer и BigInteger. (2)
Бонус задача для тех, кто понимает, о чём речь.
Иными словами, основной ход алгоритма у вас должен присутстовать в единственном экземпляре и индивидуальные обёртки для классов Integer и BigInteger для арифметических операций.
Решение ax = by + 1 в целых числах. (4)
Нужно решить уравнение в целых числах, где x и y - неизвестные.
Шифрование и дешифрование строки текста методом RSA. (6)
Нужно аккуратно объединить решения предыдущих задач. Добавить преобразование текста в подходящие для обработки числа.
Для определённости поставим задачу так:
- Исполняемый файл работает в одном из трёх режимов:
- На вход подаётся открый ключ и строка текста. Надо получить число, являющееся зашифрованной строкой.
- На вход подаётся секретный ключ и число. Надо получить из числа исходную строку.
- Пусть даны 2 простых числа p и q - сомножители числа n, а также e - показатель степени, входящий в открытый ключ. Нужно сгенерировать секретный ключ.
- Режимы переключаются аргументом командной строки.
- Справка по аргументам выдаётся при запуске с аргументом --help, -h, либо при запуске программы без аргументов.
