RSA and Fixed Exponents
- To: mathgroup at smc.vnet.net
- Subject: [mg29175] RSA and Fixed Exponents
- From: Flip at safebunch.com
- Date: Fri, 1 Jun 2001 04:15:37 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Hi All,
I was wondering if someone could give me some direction on how best to do the
following.
I have coded up RSA encrytption/decryption in Mathematica (using some of my own stuff
plus S. Wagon and others).
Here is the code
In[1]:=
Needs["NumberTheory`NumberTheoryFunctions`"]
In[2]:=
RandomPrime[d_] := NextPrime[Random[Integer, {10^(d - 1), 10^d}]]
In[3]:=
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]
In[19]:=
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}]
Here is my question:
The RSA Algorithm can now be stated as:
Find two large primes p,q. Let the modulus n be n=pq,
Choose a public exponent, e (will be fixed at e = 65537),
less than n and relatively prime to (p-1)(q-1).
Calculate d, the private exponent,
d  e-1 mod (p-1)(q-1) (the inverse of e mod (p-1)(q-1))
The pair (n, e) is the public key, and (n, d) is the private key.
The primes p and q must be kept secret or destroyed.
Encryption of m is c = me mod n.
Decryption of c is m = cd mod n.
I would like for the code to allow th user to allow finding e in a natural way
(like the current code). I would also like for the code to allow users to fix e
(say, for example to F4, the fifth Fermat number = 65537).
When e is fixed, one has to take a bit more care when selecting p and q (might
have to try a few times before a valid p and q are found as
GCD[e,(n-1)(p-1)]have to relatively prime (GCD = 1).
Can someone give me pointers on how it would be best to approach this problem.
Thank you for any inputs.