Алгоритм шифрования RSA основывается на следующей процедуре:
Генерация двух различных простых чисел p и q.
Вычисление n=pq и φ=(p-1)(q-1).
Поиск целого числа e, 1<e<φ, такого, что НОД(e,φ)=1.
Сообщение в этой системе представлено в виде числа, принадлежащего интервалу [0,n-1].
Шифруемый текст каким-нибудь способом преобразовывается в такие сообщения (числа, принадлежащие интервалу [0,n-1]).
Чтобы зашифровать текст, для каждого сообщения m, необходимо вычислить c=me mod n.
Для дешифровки текста выполняется следующая процедура: найти такое d, чтобы ed=1 mod φ, затем для каждого зашифрованного сообщения c вычислить m=cd mod n.
Существуют такие значения e и m, что me mod n=m.
Сообщения m, для которых me mod n=m, будем называть открытыми.
Проблема выбора e состоит в том, что не должно быть слишком много открытых сообщений.
К примеру, пусть p=19 и q=37.
Тогда n=19*37=703 и φ=18*36=648.
Если выберем e=181, то, несмотря на то, что НОД(181,648)=1, окажется, что все возможные сообщения
m (0≤m<n-1) будут открытыми после вычисления me mod n.
Для любого верного выбора e существуют некоторые открытые сообщения.
Важно, чтобы число таких открытых сообщений было минимальным.
Дано: p=1009 и q=3643.
Найдите сумму всех значений e, 1<e<φ(1009,3643) и НОД(e,φ)=1, для которых число открытых сообщений будет минимальным.