Re: RSA and Fixed Exponents
- To: mathgroup at smc.vnet.net
- Subject: [mg29189] Re: RSA and Fixed Exponents
- From: Ignacio Rodriguez <ignacio at sgirmn.pluri.ucm.es>
- Date: Sat, 2 Jun 2001 05:54:43 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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 safebunch.com wrote:
> 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 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 (=
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 pro=
blem.
>
> Thank you for any inputs.
--
=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=
=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0
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 sgirmn.pluri.ucm.es
=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=
=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0=B0