🚀 go-pugleaf

    Hi, I've been looking at implementing RSA encrpytion and have found that
    generating the initial keys is a somewhat tricky.  The only algorithm
    I have found for generation the public key is:

    N = x*y
    p*s mod (x-1)(y-1) = 1

    and solve for p. :(

    Is there an easy way to solve this problem ?

It's straightforward to do this with Euclid's algorithm.
See for example Knuth vol. 2.  (Look in the index under Euclid). 
Most other algorithm books or number theory books should explain
this algorithm also.

In article <avalon.712399566@coombs> avalon@coombs.anu.edu.au (Darren Reed) writes:

   Hi, I've been looking at implementing RSA encrpytion and have found that
   generating the initial keys is a somewhat tricky.  The only algorithm
   I have found for generation the public key is:

   N = x*y
   p*s mod (x-1)(y-1) = 1

   and solve for p. :(

   Is there an easy way to solve this problem ?

   If anyone can give me some clues on how to do this, it would be great
   (or even where to look for some clues :).


D.E. Knuth, _The Art of Computer Programming, Vol.2 Seminumerical
Algorithms_, 1980.

Hans Riesel, _Prime Numbers and Computer Methods of Factorization_,
1985.  (Or something like that -- my copy is at home so I may have got
the title slightly wrong.)

Both of these have good introductions to RSA and RSA-like encryption
methods.  Both should be available in a good university library; Knuth
at least is still in print and I'd argue strongly that every
programmer should own a copy of all three of his volumes.


Paul
--
Paul Leyland <pcl@oxford.ac.uk>          | Hanging on in quiet desperation is
Oxford University Computing Service      |     the English way.
13 Banbury Road, Oxford, OX2 6NN, UK     | The time is come, the song is over.
Tel: +44-865-273200  Fax: +44-865-273275 | Thought I'd something more to say.

In article <avalon.712399566@coombs>, avalon@coombs.anu.edu.au (Darren Reed) writes:
>Hi, I've been looking at implementing RSA encrpytion and have found that
>generating the initial keys is a somewhat tricky.  The only algorithm
>I have found for generation the public key is:

[find large primes x and y]
>N = x*y
>p*s mod (x-1)(y-1) = 1
>
>and solve for p. :(
>
>Is there an easy way to solve this problem ?

p*s = 1 + c * (x-1) * (y-1)

Pick a value for c other than zero.

You are now solving for p and s.  Try to factor 1 + c * (x-1) * (y-1). You
don't have to factor it completely, just enough so that p and s are  both
large (greater than N ** 0.33333, for example).  If you can't, start over
with a different c.

I know this algorithm will work, but I cannot guarantee that it will be 
cryptographically strong.

Here's a better one.  I haven't taken the time to understand it myself; it's
from Phillip Zimmermann's PGP.  Context:  p=x, q=y, e=p, d=s.

First find a small e which has no factors in common with (p-1)*(q-1).
Then use inv(d, e, (p-1)*(q-1)) below to find d.  

void inv(unitptr x,unitptr a,unitptr n)
    /* Euclid's algorithm extended to compute multiplicative inverse.
       Computes x such that a*x mod n = 1, where 0<a<n */
{
    /*    The variable u is unnecessary for the algorithm, but is 
        included in comments for mathematical clarity. 
    */
    short i;
    unit y[MAX_UNIT_PRECISION], temp[MAX_UNIT_PRECISION];
    unit gcopies[3][MAX_UNIT_PRECISION], vcopies[3][MAX_UNIT_PRECISION];
#define g(i) (  &(gcopies[i][0])  )
#define v(i) (  &(vcopies[i][0])  )
/*    unit ucopies[3][MAX_UNIT_PRECISION]; */
/* #define u(i) (  &(ucopies[i][0])  ) */
    mp_move(g(0),n); mp_move(g(1),a);
/*    mp_init(u(0),1); mp_init(u(1),0); */
    mp_init(v(0),0); mp_init(v(1),1);
    i=1;
    while (testne(g(i),0))
    {    /* we know that at this point,  g(i) = u(i)*n + v(i)*a  */    
        mp_udiv( g(iplus1), y, g(iminus1), g(i) );
        mp_mult(temp,y,v(i)); mp_move(v(iplus1),v(iminus1)); mp_sub(v(iplus1),temp);
    /*    mp_mult(temp,y,u(i)); mp_move(u(iplus1),u(iminus1)); mp_sub(u(iplus1),temp); */
        i = iplus1;
    }
    mp_move(x,v(iminus1));
    if (mp_tstminus(x))
        mp_add(x,n);
    mp_burn(g(iminus1));    /* burn the evidence on the stack...*/
    mp_burn(g(iplus1));
    mp_burn(v(0));
    mp_burn(v(1));
    mp_burn(v(2));
    mp_burn(y);
    mp_burn(temp);
#undef g
#undef v
}    /* inv */

Keith Lewis             klewis@mitre.org          "Mr. Cheap"
I don't dance to music; music dances to me.  Email me for my corrected PGP key.
The above may not (yet) represent the opinions of my employer.

avalon@coombs.anu.edu.au (Darren Reed) writes:
: Hi, I've been looking at implementing RSA encrpytion and have found that
: generating the initial keys is a somewhat tricky.  
: 
: If anyone can give me some clues on how to do this, it would be great
: (or even where to look for some clues :).

The principal challenge is in finding the two prime numbers that
constitute (most of) the private key.  Though there are restrictive
guidelines for choosing these if you're really concerned about security,
choosing random primes will work.
There are plenty of "bignum" packages that will help you do that,
including the widely available GNU Multiple Precision package
"gmp".  Look for gmp-1.2.tar.Z at your favorite FTP site.

mrr@scss3.cl.msu.edu (Mark Riordan) writes:

>The principal challenge is in finding the two prime numbers that
>constitute (most of) the private key.  Though there are restrictive
>guidelines for choosing these if you're really concerned about security,
>choosing random primes will work.
>There are plenty of "bignum" packages that will help you do that,
>including the widely available GNU Multiple Precision package
>"gmp".  Look for gmp-1.2.tar.Z at your favorite FTP site.

If you don't have a favorite FTP site and can't get archie to find it
for you, try ones of these that is nearest you (please avoid transoceanic
network links):

aeneas.mit.edu                        pub/gnu/gmp-1.2.tar.Z
aix370.rrz.uni-koeln.de               .disk2/gnu/gmp-1.2.tar.Z
alex.stacken.kth.se                   disk1/gnu/gmp-1.2.tar.Z
ashley.cs.widener.edu                 pub/src/gnu/gmp-1.2.tar.Z
cl-next2.cl.msu.edu                   bignum/gmp-1.2.tar.Z
clover.csv.warwick.ac.uk              pub/gnu/gmp-1.2.tar.Z
cnam.cnam.fr                          pub/Gnu/gmp-1.2.tar.Z
crl.dec.com                           pub/gnu/gmp-1.2.tar.Z
cs.ubc.ca                             mirror2/gnu/gmp-1.2.tar.Z
cs.ubc.ca                             pub/archive/gnu/gmp-1.2.tar.Z
dsrbg2.informatik.tu-muenchen.de      pub/GNU/gmp/gmp-1.2.tar.Z
du9ds3.uni-duisburg.de                pub/gnu/gmp-1.2.tar.Z
f.ms.uky.edu                          pub2/gnu/gmp-1.2.tar.Z
forwiss.uni-passau.de                 pub/unix/gnu/gmp-1.2.tar.Z
freja.diku.dk                         gnu/gmp-1.2.tar.Z
ftp.uni-kl.de                         pub1/packages/gnu/gmp/gmp-1.2.tar.Z
ftp.uni-kl.de                         pub2/packages/gnu/gmp/gmp-1.2.tar.Z
ftp.uu.net                            packages/gnu/gmp-1.2.tar.Z
ftp.waseda.ac.jp                      pub/GNU/prep/gmp-1.2.tar.Z
gatekeeper.3com.com                   mirrors/gnu/gmp-1.2.tar.Z
gatekeeper.dec.com                    .1/GNU/gmp-1.2.tar.Z
geocub.greco-prog.fr                  pub/Gnu/gmp-1.2.tar.Z
gmdzi.gmd.de                          gnu/gmp-1.2.tar.Z
hpb.mcc.ac.uk                         pub/gnu/gmp-1.2.tar.Z
hpcsos.col.hp.com                     mirrors/GNU/gmp-1.2.tar.Z
ifi.uio.no                            gnu/gmp-1.2.tar.Z
iraun1.ira.uka.de                     gnu/gmp-1.2.tar.Z
iros1.iro.umontreal.ca                pub/Internet/gnu/gmp-1.2.tar.Z
isfs.kuis.kyoto-u.ac.jp               GNU/gmp-1.2.tar.Z
iskut.ucs.ubc.ca                      pub/gnu/gmp-1.2.tar.Z
isy.liu.se                            src/gnu/gmp-1.2.tar.Z
jaguar.cs.utah.edu                    gnustuff/gmp-1.2.tar.Z
karazm.math.uh.edu                    pub/Gnu/gmp-1.2.tar.Z
miki.cs.titech.ac.jp                  GNU/gmp-1.2.tar.Z
mizar.docs.uu.se                      pub/gnu/gmp-1.2.tar.Z
nic.funet.fi                          pub/gnu/gmp-1.2.tar.Z
nic.switch.ch                         software/sources/gnu/gmp-1.2.tar.Z
nuri.inria.fr                         gnu/gmp-1.2.tar.Z
oskgate0.mei.co.jp                    free/gnu/gmp-1.2.tar.Z
pdq.coe.montana.edu                   pub/mirrors/prep-gnu/gmp-1.2.tar.Z
plaza.aarnet.edu.au                   gnu/gmp-1.2.tar.Z
pprg.eece.unm.edu                     pub/gnu/gmp-1.2.tar.Z
psuvax1.cs.psu.edu                    pub/src/gnu/gmp-1.2.tar.Z
qiclab.scn.rain.com                   pub/gnu/gmp-1.2.tar.Z
rena.dit.co.jp                        pub/GNU/libs/gmp-1.2.tar.Z
reseq.regent.e-technik.tu-muenchen.de informatik.public/GNU/gmp/gmp-1.2.tar.Z
rs3.hrz.th-darmstadt.de               pub/gnu/gmp-1.2.tar.Z
rzsun2.informatik.uni-hamburg.de      pub/gnu/gmp-1.2.tar.Z
sh.wide.ad.jp                         GNU/gmp-1.2.tar.Z
sics.se                               pub/gnu/gmp-1.2.tar.Z
sifon.cc.mcgill.ca                    pub/gnu/gmp-1.2.tar.Z
slembe.ifi.uio.no                     gnu/gmp-1.2.tar.Z
src.doc.ic.ac.uk                      gnu/gmp-1.2.tar.Z
svin02.info.win.tue.nl                pub/gnu/gmp-1.2.tar.Z
swdsrv.edvz.univie.ac.at              gnu/gmp-1.2.tar.Z
switek.uni-muenster.de                pub/gnu/gmp-1.2.tar.Z
theta.iis.u-tokyo.ac.jp               GNU/gmp-1.2.tar.Z
toklab.ics.osaka-u.ac.jp              GNU/prep/gmp-1.2.tar.Z
tupac-amaru.informatik.rwth-aachen.de pub/gnu/gmp-1.2.tar.Z
ugle.unit.no                          pub/gnu/gmp-1.2.tar.Z
uhunix2.uhcc.hawaii.edu               mirrors/gnu/gmp-1.2.tar.Z
utsun.s.u-tokyo.ac.jp                 ftpsync/prep/gmp-1.2.tar.Z
van-bc.wimsey.bc.ca                   pub/crypto/bignum/gmp-1.2.tar.Z
van-bc.wimsey.bc.ca                   pub/crypto/gmp-1.2.tar.Z
walhalla.germany.eu.net               pub/gnu/gmp-1.2.tar.Z
walton.maths.tcd.ie                   src/gnu/gmp-1.2.tar.Z
wnoc-fuk.wide.ad.jp                   pub/GNU/prep/gmp-1.2.tar.Z
wuarchive.wustl.edu                   mirrors2/gnu/gmp-1.2.tar.Z
-- 
/***********************************************************************\
| Phil Howard  ---  KA9WGN  ---  pdh@netcom.com   |   "The problem with |
| depending on government is that you cannot depend on it" - Tony Brown |
\***********************************************************************/

In article <skyhawk.712690763@milton> skyhawk@u.washington.edu writes:
:In some recent message, mrr@scss3.cl.msu.edu (Mark Riordan) writes:
:>avalon@coombs.anu.edu.au (Darren Reed) writes:
:>: Hi, I've been looking at implementing RSA encrpytion and have found that
:>: generating the initial keys is a somewhat tricky.  
:>
:>The principal challenge is in finding the two prime numbers that
:>constitute (most of) the private key.  Though there are restrictive
:>guidelines for choosing these if you're really concerned about security,
:>choosing random primes will work.
 
I have posted repeatedly that the restrictions are not necessary.

:Okay, I'll bite.  What are the restrictive guidelines?  All I could find was:
:  p-1 and q-1 should have large prime factors
 
This will be true for arbitrary large primes p & q.

:  gcd(p-1,q-1) should be small
 
This reduces the number of stationary points.

:  p and q should differ in length by a few decimal digits
 
OK, but not really necessary.

: I used:   p = 2xy + 1  (x and y are pseudoprimes)
:
:Pick two psuedoprimes, crank out a candidate for p, and test for primality.
 
You are misusing the term 'pseudoprime'. What you mean is 'probable prime'.
A 'pseudoprime' is actually a probable prime that is composite, e.g. a
Carmichael number.

It is not really necessary that x & y be prime. Further, I recommend
that you make p a strong probable prime.

:Loop until p is prime, repeat for q.  Is this a reasonable method?
 
Expensive.

:Is there something else that should be done to get good p and q?
 
Yes. I have repeatedly discussed the procedure for doing so. 
Briefly:

Select an inteval(s) near the size you want, e.g. 10^100. (and say 10^102)
Sieve out composites divisible by small primes.
Select two strong probable primes p & q such that p-q is reasonably
large (at least 10^25). [This defeats difference of squares methods].
ECM makes restrictions on p-1 and q-1 useless.

--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"

In article <1992Aug2.145532.4657@linus.mitre.org> bs@faron.mitre.org (Robert D. Silverman) writes:

! Select an inteval(s) near the size you want, e.g. 10^100. (and say 10^102)
! Sieve out composites divisible by small primes.
! Select two strong probable primes p & q such that p-q is reasonably
! large (at least 10^25). [This defeats difference of squares methods].
! ECM makes restrictions on p-1 and q-1 useless.

A recipe for RSA-keys:
	- Take the 10-sided dice from a Dungeons&Dragons package.
	- Throw it 100 times to get p1, then 102 times to get q1.
	(Now you have truly random numbers, not pseudo-random.)
	- Tell Mathematica version 2 the following:
		p = p1
		q = q1
		While[!PrimeQ[p], p++]
		While[!PrimeQ[q], q++]

It will only take a minute or two depending on your computer. For 
added security you could use numbers around 150 digits. Even that wouldn't
take very long (tested). Sounds a good way to pass time. Perhaps I'll do it the
next time I get bored.
--
...............................................................................
Ari Huttunen                                         You don't miss water
                                                       until the well runs dry.

Ari.Huttunen@hut.fi (Ari Juhani Huttunen) writes:

>A recipe for RSA-keys:
>	- Take the 10-sided dice from a Dungeons&Dragons package.
>	- Throw it 100 times to get p1, then 102 times to get q1.
>	(Now you have truly random numbers, not pseudo-random.)
>	- Tell Mathematica version 2 the following:
>		p = p1
>		q = q1
>		While[!PrimeQ[p], p++]
>		While[!PrimeQ[q], q++]

Hi!

True, you'll get truly random numbers 'p' and 'q' to start with, but the
resulting '++':ed prime numbers are not randomly distributed among primes,
because they'll have much harder time hitting the greater of any pair of
twin primes, than the smaller - for an example.  This may have some bad
effects in the generation of RSA keys, since some primes being preceded
by longer-than-average run of composite numbers are sometimes of special
arithmetic form ( P = factorial(x)+1 comes to mind).  Also, knowing the
uneven distribution of seeds might help an offender to break the cipher
more easily.

terveisin: Risto Lankinen
-- 
Risto Lankinen / risto@tuura.icl.fi ***************************************
Software designer, Systems Division *  1                              2   *
ICL Personal Systems, Helsinki, FIN * 2 +1 is PRIME!  Now working on 2 +1 *
"Aren't buglets fun?" Anon.OS/2-fan ***************************************