Реализация ЭЦП на основе алгоритма RSA Асимметричные криптографические системы основаны на односторонних функциях с секретом. Односторонней функцией с секретом называется функция y=f(x, k), которая легко вычисляется при заданном x, причём при заданном секрете k аргумент x по заданному y восстановить просто, а при неизвестном k – сложно. На первом этапе создания электронной подписи с помощью алгоритма RSA генерируются два ключа — открытый (public) и секретный (private), вместе открытый и соответствующий ему секретный ключи образуют пару ключей (keypair). Открытый ключ не требуется сохранять в тайне, он используется для шифрования данных. Если сообщение было зашифровано открытым ключом, то расшифровать его можно только соответствующим секретным ключом. Сначала выбираются два больших простых числа p и q и вычисляется их произведение n = p⸱q, после чего, с помощью функции Эйлера для числа n: φ(n) = (p – 1)⸱(q − 1), вычисляются секретная и открытая экспоненты, являющиеся частями секретного и открытого ключей соответственно. Далее для вычисления открытой экспоненты необходимо выбрать число e, взаимно простое с φ(n) и удовлетворяющее неравенству 1 < e < φ(n). Для секретной необходимо вычислить число d для которого справедливо: e⸱d ≡ 1 (mod φ(n)). Открытым ключом будут являться числа (e,n), а (d,n) – секретным, так же числа p и q должны храниться в секрете. Криптосистема RSA позволяет шифровать сообщения, представленные в виде целого числа, большего 0, но меньшего (n-1). Каждый символ переводится в число, к примеру A = 01, B = 02, . . . , Z = 26. То есть сообщение m ∈ [0, n-1]. Тогда зашифрованный текст получается путем возведения сообщения m в степень e модулю n: s = m^e (mod n). Для дешифрования число s возводится в степень d по модулю n: s^d (mod n) = m. Т. е. дешифрование зашифрованного сообщения m дает m: D(E(m)) = m, D - decryption , E – encryption (1) Тот же результат мы получим и если сначала сообщение дешифруется, а затем шифруется: E(D(m)) = m (2) Шифрование и дешифрование — это фактически одна и та же операция только с возведением в разные степени. Построение ключей, казалось бы, чуть более сложным, но на самом деле мы выбираем пару чисел взаимно обратных по некоторому модулю, и основная хитрость системы RSA состоит в том, что число n открытый ключ, а φ(n), по которому находятся e и d, никому не известное число, и чтобы его узнать нужно знать разложение числа n на множители. Если n достаточно велико разложение на множители довольно сложная задача. Воспользуемся описанным в [1] доказательством и продемонстрируем правильность алгоритма дешифрования с использованием тождества Эйлера и Ферма: для любого целого числа (сообщения) m, которое является относительно простым для n, m φ(n)≡ 1 (mod n). (3) φ(n) = φ(p)⸱ φ(q) = (p - 1)⸱(q - 1) = n – (p + q) + 1. (4) Поскольку d относительно простое по отношению к φ(n), оно имеет мультипликативное обратное e в кольце целых чисел по модулю φ(n): e⸱d ≡ 1 (mod φ(n)). (5) Теперь мы докажем, что уравнения (1) и (2) справедливы (то есть, что дешифрование работает правильно, если e и d выбраны как указано выше). D(E(m)) ≡ (E(m))^d ≡ (me)^d(mod n) = m^ e·d (mod n) E(D(m)) ≡ (D(m))^e ≡ (md)^e(mod n) = me·d (mod n) m^e·d ≡ m k·φ(n)+1 (mod n) (∀ k ∈ Z). Из (3) мы видим, что для всех m таких, что p не делит m m^(p-1) ≡ 1 (mod p) и поскольку (p – 1) делит φ(n), m^(k·φ(n)+1) ≡ m (mod p). Это тривиально верно, когда m ≡ 0 (mod p), так что это равенство фактически выполняется для всех m. Аналогично рассуждая о q, получаем m^(k·φ(n)+1) ≡ m (mod q). Вместе последние два уравнения подразумевают, что для всех m m^(e·d) ≡ m^(k·φ(n)+1) ≡ m (mod n). Это подразумевает (1) и (2) для всех m, 0 ≤ m < n. Следовательно, E и D являются обратными перестановками.