Ok, everybody can have efdtt.c.gz as their public key! Here is the algorithm: Choose a j such that 256^j is a large enough random space for you to feel secure, and factors of that order will be hard to find in a composite number. Pick a random number, R < 256^j Find q = nextprime(256^j - R) Find k = decimal representation of efdtt.c.gz Find p = nextprime(k*256^(j+1)/q) Verify that (p-1)(n-1) is relatively prime to your public exponent, if not, try a few public exponents, or start over with a new random number. Compute n=pq, this is the public key modulus. Verify that n/256^(j+1) = k in case there was a large (>256) gap in the primes. If it fails, try p=nextprime(k*256^(j+2)/q). n can be converted to hex and gunzipped to the efdtt.c source code. Go compute your private exponent d, then destroy p, q and R. Let everybody know your public key and what it can be used for ;-) Attached is a sample program to illustrate the key generation. Feed efdtt.c.gz to its standard input. For j=32 (256 bit random number), it takes about 1-1/2 minutes on my 266MHz G3. Be sure to use your own random number, not the one in the code. _________________________________________________________________ Get your FREE download of MSN Explorer at http://explorer.msn.com ----- End forwarded message ----- -- -- http://www.lemuria.org -- http://www.Nexus-Project.net -- --vkogqOf2sHV7VnPd Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="public.c" #include <gmp.h> #include <stdio.h> /* J is j * 8 to use powers of 2 instead of 256 */ /* R is your random number, don't use the one shown * if this is really going to produce your public key */ #define J 256L #define R "8741288239734901231012300419439827747721239184132" main () { mpz_t a, q, p, n, k; unsigned long c; mpz_init (q); mpz_init (p); mpz_init (n); mpz_init (k); mpz_init (a); while ((c = getchar ()) != EOF) { mpz_mul_ui (k, k, 256L); mpz_add_ui (k, k, c); } printf ("k is:\n"); mpz_out_str (stdout, 10, k); printf ("\n\nq is:\n"); mpz_set_str (q, R, 0); mpz_set_ui (p, 1L); mpz_mul_2exp (p, p, J); mpz_sub (q, p, q); mpz_nextprime (q, q); mpz_out_str (stdout, 10, q); printf ("\n\np is:\n"); /* over-expanding should guarantee an answer */ mpz_mul_2exp (a, k, J + 16L); mpz_tdiv_q (p, a, q); mpz_nextprime (p, p); mpz_out_str (stdout, 10, p); printf ("\n\nn is:\n"); mpz_mul (n, p, q); mpz_out_str (stdout, 10, n); printf ("\n\n65537 gcd (p-1)(q-1) is:\n"); mpz_sub_ui (p, p, 1L); mpz_sub_ui (q, q, 1L); mpz_mul (a, p, q); mpz_gcd_ui (a, a, 65537L); mpz_out_str (stdout, 10, a); printf ("\n\nn/256^34 is:\n"); mpz_set_ui (q, 1L); mpz_mul_2exp (q, q, J + 16L); mpz_tdiv_q (q, n, q); mpz_out_str (stdout, 10, q); printf ("\n\n difference from k is:\n"); mpz_sub (k, k, q); mpz_out_str (stdout, 10, k); printf ("\n"); } --vkogqOf2sHV7VnPd Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename=keys k is: 489791971139294721492890070820155569620855660960671152212956498742039672112756515508187293741821313343828432787304645596036261708404238649106578165524494163400608981624770671588151402810099681387253505295523873528607505025404055656640662917263299188105134143828382070106290368480093502782669567301116939263880957511639706827141547209129803084934032419725412566483604334931280689111374224553996188329634360332732653261350171222703208193468891532899326692623514903323012432164895187708186345355697953671882383578250883882558619759274176822251124822180272439609500079726934520797625058937758586291699109806463439054605698740756573226324905651996790831494040667293495224230225078284196001746999337737330711700914242699218902328035406113882295732383384553898452229896017081749832945397093734240256603444289486458831879575367414145067878143633157580402523817166917607364019003392000 q is: 115792089237316195423570984999946619613535083434628263620017756260191890456207 p is: 32099006620584818867758043683692909179157113078856802328307357725679404828875458036112204440028287258720600878846414464221802919598857755802551492120960491443536919941289105406159302962848983801052659527723163782414700203964980283244265254677334683288229164946558372183147626488962268484716538959807411260791234028030592489974438867729461987791791553884810951540842460393345315628177603284809889244563826187850440471139025472057683483388847187895555835840248034326855258817994192035983332746563490378241602993686226024065423242879590873464950086580106928582897514901915848883068408264220378135988671718732214067062726547117458692721591359406370200290314624754063127400960094087895867637742075025483639428201109722721079724930178043745028933885128829906698168853154318706644966851186313088493594654968888582627071463897569198911359861742320383875823857580617071265625042430280842643 n is: 3716811039039960706457524364949523842483974709176236306917175996062120032369708610745538218545522531664764465328423063494363196237644912389564475489661364952303184692294444935724490425975207070376229471778973717896788807789416839263843979568326381262723493245674672893710695001177760276359941234091237449113769973392194789233069068685293909686054825572223619425889488695186536175849988709242777545311678609308300767119865148164828450064163356019724173532529678780021610811588427801992612303262463310985388919921159292894103158798781854907467097518709574773757761042400077263602354838379849589374059901729799489357305145264298609194342967597564222428418510955996385751370907147998230866973978555948242731998082064388086263087200167120592207556402931775017115750800793843162008617148122395051131879332692680935185080661392002417411017976827918323597340834406580075343884328073239968728524701751479392305371080458252121291682088279177666443938518065897649635101 65537 gcd (p-1)(q-1) is: 1 n/256^34 is: 489791971139294721492890070820155569620855660960671152212956498742039672112756515508187293741821313343828432787304645596036261708404238649106578165524494163400608981624770671588151402810099681387253505295523873528607505025404055656640662917263299188105134143828382070106290368480093502782669567301116939263880957511639706827141547209129803084934032419725412566483604334931280689111374224553996188329634360332732653261350171222703208193468891532899326692623514903323012432164895187708186345355697953671882383578250883882558619759274176822251124822180272439609500079726934520797625058937758586291699109806463439054605698740756573226324905651996790831494040667293495224230225078284196001746999337737330711700914242699218902328035406113882295732383384553898452229896017081749832945397093734240256603444289486458831879575367414145067878143633157580402523817166917607364019003392000 difference from k is: 0 --vkogqOf2sHV7VnPd--