MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

RSA and Fixed Exponents

  • To: mathgroup at
  • Subject: [mg29175] RSA and Fixed Exponents
  • From: Flip at
  • Date: Fri, 1 Jun 2001 04:15:37 -0400 (EDT)
  • Sender: owner-wri-mathgroup at

Hi All,

I was wondering if someone could give me some direction on how best to do the

I have coded up RSA encrytption/decryption in Mathematica (using some of my own stuff
plus S. Wagon and others).

Here is the code 


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}]];

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.

  • 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