Главная страница

Статьи

Программы

Ссылки

Форум

О сайте

RSA - это алгоритм шифрования. От первых букв создателей Rivest Shamir Adleman. В его основе лежит математические вычисления.

Вначале выбираются два больших (для надёжности) простых числа p и q. Потом вычисляется n - их произведение (n = pq). Затем вычисляется phi = (p-1)(q-1). Потом вычисляется e - любое число взаимно простое с phi. Затем вычисляется d - обратный элемент к e по модулю phi. N и e хранятся открыто. Phi и d скрываются. Для зашифровки нужна пара (n,e). Для дешифровки нужна пара (n,d). Поэтому p, q и phi лучше уничтожить.

Теперь объясню математические тонкости. Простое число - число делящееся Только на себя и 1 (например 31, 37). Взаимно простые числа a и b - числа, которые не имеют общих делителей (например 10, 11). Обратный элемент к a по модулю b вычисляется по расширенному алгоритму Эвклида. Суть его в следующем: он находит числа c, alpha и betta. На входе у него числа a и b. C - Наибольший общий делитель чиел (НОД) a и b. Alpha и betta удовлетворяют следующему правилу:

alpha*a + betta*b = c.

В большинстве случаев alpha и betta имеют противоположные знаки. Сам алгоритм можно найти у Кнута (Исскуство программирования, т.2, издательство Addison-Wesley, алгоритм 4.5.2.X, страницы 386- 387). Для RSA a = phi, b = e. d = betta.

Потом берётся текст, и по таблице превращается в числа (у меня берётся таблица ASCII). Т.е. например мы взяли таблицу ASCII и нам нужно зашифровать Hello, world! то последовательность блоков будет следующяя: 72-101-108-108-111-44-32-119-111-114-108-100-33. Затем каждый блок шифруется по правилу:

E(b) = pow(b,e) mod n.

Здесь E(b) - функция шифрования. B - блок. N - число, которое мы выбрали. Быстрее и эффективнее будет вычислять остаток по следующему алгоритму:

1. Создаётся переменная result = 1.
2. Начинается цикл eраз:
3. result = (result*a) % n.

Здесь вычисляется pow(a,e)%n.

Функция дешифрования:

D(b) = pow(b,d) mod n.

Возникает вопрос: как записывать большие числа p, q, n, e, phi, d?

Есть хорошая книжка: Символьный C++, К.Ш.ТАН, В.-Х.Стиб, Й.Харди, издательство Мир. Там описывается класс Verylong, который позволяет сохранять очень большие числа. Основная идея такова: числа записываются текстом в char*.

Расширенный алгоритм Эвклида.

Класс Verylong.

Исходник.

Назад, на рубрику Статьи.