Описание основных переменных и функций электронной подписи на базе шифра Эль-Гамаля. 
Пример работы программы

Функции:

int pprime (int number) — подбор простого числа P.

int vozved (int a, int chislo, int p) — функция быстрого возведения в степень.

int vzprost (int a, int b) — проверка на взаимную простоту.

int evklid (int a, int b) — обощенный алгоритм Евклида:? * d mod p = 1.

Переменные:

int m, P, q, G, x, y, k, r, u, s, kmin1, rez, rez1, result.

Краткое описание криптографического протокола «Электронные деньги»

Вначале дадим более точную постановку задачи. Имеются три участника: банк, покупатель и магазин. Покупатель и магазин имеют соответствующие счета в банке, и покупатель хочет купить некоторый товар в магазине. Покупка осуществляется в виде трехступенчатого процесса:

• 1) Покупатель снимает нужную сумму со своего счета в банке
• 2) Покупатель «пересылает» деньги в магазин
• 3) Магазин сообщает об этом в банк, соответствующая сумма денег зачисляется на счет магазина, а покупатель забирает товар (или последний ему доставляется).

Наша цель — разработать такую схему, чтобы Она была надежна Чтобы банк не знал, кто купил товар, т. е. была сохранена анонимность обычных денег.

Банк имеет следующую информацию: секретные числа P, Q, c и открытые.

N = P * Q,.

d = c ^ -1 mod (P — 1) * (Q — 1). (5.9).

Допустим, покупатель решил израсходовать некоторую заранее оговоренную с банком сумму (например, 100 $). (Мы сначала рассмотрим случай, когда может использоваться банкнота только одного номинала (скажем, 100 $).) Покупатель генерирует число n, которое он не будет посылать в банк. Затем он генерирует случайно число r, взаимно простое с N, и вычисляет число.

n' = (n * r ^ d) mod N. (5.11).

Число n' покупатель отправляет в банк.

Банк вычисляет число.

s' = n' ^ c mod N (5.12).

и отправляет s' обратно покупателю (не забыв при этом снять 100 $ с его счета).

Покупатель находит число r ^ - 1 mod N и вычисляет.

s = (s' * r ^ -1) mod N. (5.13).

Заметим, что с учетом соотношений (5.12), (5.11) и (5.9) имеем.

s = n' ^ c * r ^ -1 = (n * r^d)^c * r ^ -1 = n ^ c mod N,.

т.е. мы получили подпись банка к n (см. (5.10)), но самого числа n ни банк, ни кто-либо другой не видел. Вычисление (5.12) называется «слепой подписью», так как реальное сообщение (n) подписывающий не видит и узнать не может.

Таким образом, покупатель имеет число n, которое никому не известно и никогда не передавалось по каналам связи, и подпись банка s, совпадающую с вычисленной по (5.10). Покупатель формирует банкноту и предъявляет ее в магазине, чтобы купить товар. Магазин отправляет эту банкноту в банк для проверки. Прежде всего, банк проверяет правильность подписи (эту проверку мог бы сделать и магазин, использую открытые ключи банка). Но кроме этого банк хранит все номера возвратившихся к нему банкнот и проверяет, нет ли числа n в этом списке. Если n есть в списке, то платеж не принимается (кто-то пытается использовать банкноту повторно), и банк сообщает об этом магазину. Если же все проверки прошли успешно, то банк добавляет 100 $ на счет магазина, а магазин отпускает товар покупателю.

В данной системе для борьбы с мультипликативным свойством системы RSA мы используем внесение избыточности в сообщение. Допустим, что длина модуля N — 1024 бита. Такой же может быть и длина числа n. Будем записывать (случайно выбираемый) номер банкноты только в младшие 512 бит n, а в старшие 512 бит n запишем некоторое фиксированное число. Это фиксированное число может нести полезную информацию, такую, как номинал банкноты и наименование банка (с помощью 512 бит можно представить строку из 64 символов ASCII). Теперь банк при предъявлении банкноты будет обязательно проверять наличие фиксированного заголовка в параметре n и отвергать банкноту в случае его отсутствия. Вероятность того, что при перемножении двух чисел по модулю N результат совпадает с ними в 512 битах пренебрежимо мала. Поэтому получить фальшивую банкноту по формуле (5.14) не удается.

n₃^c = (n₁n₂) ^ c = s₃ mod N, (5.14).