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 &#61626;  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.

```

• Prev by Date: Re: OOP in Mathematica
• Next by Date: RE: Execute a Menu Item
• Previous by thread: Re: Re: OOP in Mathematica
• Next by thread: Re: RSA and Fixed Exponents