Can This RSA code be made cleaner?
- To: mathgroup at smc.vnet.net
- Subject: [mg37735] Can This RSA code be made cleaner?
- From: "flip" <flip_alpha at safebunch.com>
- Date: Sun, 10 Nov 2002 05:38:40 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Hello,
please excuse my basic Mathematica coding skills as I am only a casual user and wish
I could write thing like Stan Wagon, David Wagner or Roam Maeder (maybe some
day).
Anyway, I have the following snippet from some RSA code I have and was
wondering if it could be made cleaner. Sometimes, an "e" cannot be found
for the p and q, but I just rerun it. Maybe this should be automatic also,
but I am concerned that it may run forever.
Any hints as to how to make this more efficient are appreciated. The "n"
represents the number of digits in n = pq. I like all of the printouts as
this code is meant to help teach the method (RSA).
Thank you.
(*RSA Code Snippet Follows *)
Needs["NumberTheory`NumberTheoryFunctions`"]
RandomPrime[d_] := NextPrime[Random[Integer, {10^(d - 1), 10^d}]]
findE[p_, q_] := Module[{res, n = p q, phi = EulerPhi[n]},
res = Random[Integer, {p, n}];
While[GCD[res, phi] != 1,
res = Random[Integer, {p, n}]];
res]
PubPrivKey[nDigits_] := Module[{l, p, q, n, d, e, publicKey, privateKey},
Clear[l, p, q, n, d, e, publicKey, privateKey];
l = Floor[N[nDigits/2]];
p = RandomPrime[l];
Print["p = ", p];
q = RandomPrime[l];
Print["q = ", q];
n = p q; Print["n = pq = ", n];
phi = EulerPhi[n]; Print["phi = ", phi];
e = findE[p, q]; Print["Coprime to phi = e = ", e];
d = PowerMod[e, -1, phi]; Print["Modular inverse d = ", d];
publicKey = {d, n}; Print["Public Key = {d,n} = ", {d, n}];
privateKey = {e, n}; Print["Private Key = {e,n} = ", {e, n}];
{publicKey, privateKey}]
{$PublicKey, $PrivateKey} = PubPrivKey[10]