Для шифрования и дешифрования нужна функция PowerMod[m,e,n] = m^e (mod n), где m, e, n - очень большие целые числа.
Для генерации ключей нужна процедура генерации очень больших простых целых чисел и функция вычисления наибольшего общего делителя.
Вот программка на Mathematica 8 генерирующая ключи для RSA с примером шифрования и дешифрования:
(* Генерируем простое число размером bitsCount разрядов *)
MyRandomPrime[bitsCount_] := NextPrime[RandomInteger[{2^(bitsCount-1),2^bitsCount}]];
(* Генерируем один из вариантов ключей. Вариант может быть неудачным *)
GenerateRandomKeyVariant[bitsCount_] := Module[{p,q,e,n,d,f,x,k},
p = MyRandomPrime[bitsCount/2];
q = MyRandomPrime[bitsCount/2];
e = MyRandomPrime[bitsCount];
n = p q;
f = (p-1) (q-1);
{x,{d,k}} = ExtendedGCD[e,f];
Return[{p,q,e,n,d,f,k}];
];
(* Генерируем ключи. Просто перебираем варианты до первого удачного. *)
GenerateKey[bitsCount_]:=Module[{p,q,e,n,d,f,k},
{p,q,e,n,d,f,k} = GenerateRandomKeyVariant[bitsCount];
While[d<0,{p,q,e,n,d,f,k} = GenerateRandomKeyVariant[bitsCount];];
Return[{e,n,d}];
];
(* Пример использования. Генерируем ключи длиной 256 разрядов*)
{e,n,d} = GenerateKey[256]
(* Получаем что-то вот такое: *)
{106474780081756000849443530376385002811553039013608684548473063572334466703629,
59222289060328681086701519045552968082786829153713768742253207685947641051833,
191011303451374405811626717837027403073810972106220097519518873217160081729}
(* Процедуры шифрования и дешифрования.*)
Encrypt[m_] := PowerMod[m,e,n];
Decrypt[s_] := PowerMod[s,d,n];
(* Проверяем *)
Encrypt[Decrypt[1234567890]] == 1234567890
Decrypt[Encrypt[1234567890]] == 1234567890
True
True
В зависимости от контекста, два числа e, n - публичный ключ, d - приватный. Или наоборот d, n - публичный, e - приватный. Завист от того что требуется шифрование сообщения или подпись сообщения.
