MathGroup Archive 2001

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

Search the Archive

Re: RSA and Fixed Exponents

  • To: mathgroup at
  • Subject: [mg29189] Re: RSA and Fixed Exponents
  • From: Ignacio Rodriguez <ignacio at>
  • Date: Sat, 2 Jun 2001 05:54:43 -0400 (EDT)
  • Sender: owner-wri-mathgroup at

The first thing you should do is avoid using EulerPhi in your code, as
this function is computationally impractical. If p and q are prime
numbers, then EulerPhi[p q] is given by (p-1)(q-1). Use this last form
instead. The strength of the RSA algorithm lies in that it is
impractical to calculate EulerPhi[p q] without knowing the values of p
and q.  As for the value of the exponent e, I would recommend a small
prime with as few binary 1s as possible, so exponenciation is faster.
F4 (65537) seems a good choice. In that case, your key generator should
give p and q and test if p-1 and q-1 are prime relative to e.

Flip at wrote:

> Hi All,
> I was wondering if someone could give me some direction on how best to do=
> 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 natura=
l way
> (like the current code).  I would also like for the code to allow users t=
o 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 (=
> 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 pro=
> Thank you for any inputs.


Ignacio Rodriguez Ramirez de Arellano
Unidad de RMN
Universidad Complutense
Paseo Juan XXIII, 1
Madrid 28040, Spain

Tel. 34-91-394-3288
Fax  34-91-394-3245
e-mail: ignacio at


  • Prev by Date: Re: plotting multiple polygons
  • Next by Date: Re: Compound Expressions
  • Previous by thread: RSA and Fixed Exponents
  • Next by thread: RE: Execute a Menu Item