December 2003 - cypherpunks-legacy

Re: Patent infringement (fwd)
by Brian Beker 17 Dec '03

17 Dec '03

---------- Forwarded message ---------- Date: Fri, 20 May 1994 13:43:10 -0700 (PDT) From: Netcom Support <support(a)netcom.com> To: david(a)sternlight.com Cc: Brian Beker <beker(a)netcom.com> Subject: Re: Patent infringement [Deleted; copy of Mr. Sternlight's original letter of complaint about my PGP2.3a key in my .plan file] You should take the matter up with him; we thank you for your information and opinions but will be taking no further action at this time. If you wish to pursue this matter legally you should have RSADSI's lawyers contact him directly. ___________________________________________________________________________ Support support(a)netcom.com Technical Support Staff NETCOM On-line Communication Services

1 0

Re: Complaint against beker@netcom.com (fwd)
by Brian Beker 17 Dec '03

17 Dec '03

With this and the previous response to Mr. Sternlight from Netom, this matter is for now laid to rest. Brian Beker ---------- Forwarded message ---------- Date: Fri, 20 May 1994 13:46:29 -0700 (PDT) From: Netcom Support <support(a)netcom.com> To: david(a)sternlight.com Cc: Brian Beker <beker(a)netcom.com> Subject: Re: Complaint against beker(a)netcom.com David Sternlight writes: > From strnlght Thu May 19 12:31:19 1994 > Return-Path: <strnlght> > Received: by netcom.com (8.6.8.1/SMI-4.1/Netcom) > id MAA01913; Thu, 19 May 1994 12:30:20 -0700 > From: strnlght (David Sternlight) > Message-Id: <199405191930.MAA01913(a)netcom.com> > Subject: Complaint against beker(a)netcom.com > To: support (Netcom Support) > Date: Thu, 19 May 1994 12:30:18 -0700 (PDT) > In-Reply-To: <199405191033.EAA29745(a)spot.Colorado.EDU> from "Richard Johnson" at May 19, 94 04:33:51 am > Reply-To: david(a)sternlight.com > X-Mailer: ELM [version 2.4 PL23] > MIME-Version: 1.0 > Content-Type: text/plain; charset=US-ASCII > Content-Transfer-Encoding: 7bit > Content-Length: 6613 > > I mailed a complaint to netcom support. At the suggestion of the netcom > support person I spoke to on the phone, I sent a copy to the user in > question as well. > > That user posted a copy of the complaint to a newsgroup without my > permission. This is, of course, a violation of my copoyright. Thus he has > compounded his violation of RSADSI's patent in PGP with a violation of my > copyright in my e-mail. > > By trying to make what should be a private matter between the user and > netcom support, and myself and netcom support into a public cause celebre, > and generate pressure mail on netcom support such as that below, I believe > the user in question has further violated his agreement, and request netcom > to take appropriate action. This time I have a personal interest in seeing > this resolved. Postng another person's email, while annoying, is not necessarily a violation of copyright in our eyes. Again, we have no intention of taking action at this time; if you want to pursue the matter legally, then have your lawyer talk to him. ___________________________________________________________________________ Support support(a)netcom.com Technical Support Staff NETCOM On-line Communication Services

1 0

RSA's "Sink Clipper" poster
by snyderra＠dunx1.ocs.drexel.edu 17 Dec '03

17 Dec '03

Got home today, and found a poster tube attached to my doorknob. Inside I found a poster from RSADSI ("Because some things are better left unread.") with the picture of a ship going down and the words "Sink Clipper!" on it. It's not a bad poster, saying how Clipper "allows government to eavesdrop on the communications of criminals, suspects, and unfortunately, law-abiding citizens alike," and lists what you can do to stop it. (Boycott, write Washington, and, of course, buy only real RSA products :-) ) It's a pretty good poster. I believe I got it because I inquired of their various products and PEM services a while back. I don't know what their policy is, but I don't suppose it'd hurt to mail info(a)rsa.com and ask. Bob -- Bob Snyder N2KGO MIME, RIPEM mail accepted snyderra(a)dunx1.ocs.drexel.edu finger for RIPEM public key When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.

1 0

Re: FAQ: Where to get PGP latest version
by wcs＠anchor.ho.att.com 17 Dec '03

17 Dec '03

Mike Johnson's list of where to get PGP has teh following: > Platforms | Released | Version | Notes & restrictions > | by | | Other restrictions may apply. >-------------------------------------------------------------------------- > Dos & Unix | MIT | 2.5 | Uses RSAREF 2.0. Not for use in any > | | BETA | application that you get paid for. > | | | Patents licensed for personal use only. > | | | Not for export from the USA or Canada. >-------------------------------------------------------------------------- The export situation is far better than that, actually. There used to be *two* reasons you couldn't export RSAREF. One was that the U.S. Government threatens people who do export crypto, though they have to catch you to enforce it. The other was that the RSAREF license documents said you couldn't export it or use it outside the US/Canada, which means you'd be violating their copyright if you used it in, say, Europe, where US copyrights are enforceable. The current RSAREF license, however, does not forbid export or use outside the US/Canada - it only says that it ay be subject to export laws and recommends consulting a lawyer if you want to export it. This means that, if a copy were to find its way out of the US, it would be perfectly legal to use it within the other terms of the license, which would make it possible to do things like, say, compile it along with a PGP-2.5-bones library. (The alternative approach would be to get someone to rewrite it from scratch outside the US, and make sure it was a good clone.) While I don't have enough lawyers, guns, and money to go exporting it myself, I must say I'd be *shocked* to find it appearing on, say, ftp.funet.fi in the near future :-) Bill Stewart

1 0

Re: D-H key exchange - how does it work?
by wcs＠anchor.ho.att.com 17 Dec '03

17 Dec '03

Eric Hughes, replying to somebody, says: > It takes hours and hours of searching to find > a 1024 bit strong prime on a workstation. Granted, you don't need to change > very often perhaps, but some people would like to change every day. > If they really want to change that often, they can buy a dedicated > machine. There's no good cryptographic reason to change that often, > if the modulus is large enough. In addition, changing the modulus can > have unpleasant effects on traffic analysis, if not done properly. For basic PGP mail, there's no need to change keys that often. There are other applications, though, that tend to want new keypairs on each transaction, and looking for strong primes would make them much more annoying, if strong primes matter with the current factoring algorithms... Bill

1 0

Is my DH exchange secure?
by catalyst-remailer＠netcom.com 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- nelson(a)sgi.com describes some of the precautions required to use DH exchange safely: ** begin quoted text *** The prime p wants to be chosen with a little care, and the "random" numbers a and b may want to be "selected" to eliminate certain undesirable values. I'll explain below. Within the field Z_p (the set of integers 0..p-1) where p is prime, there are elements whose successive powers make up all the elements of the field Z_p. These numbers are called "primitive" elements or "generators" of the field Z_p. That is, if g is a generator of the field Z_p, then the successive powers g, g^2, g^3, ... g^(p-2), g^(p-1) mod p include all the p-1 non-zero elements of Z_p. The set of unique numbers produced by taking succesive powers mod p of an element m of Z_p is a group, the "multiplicative span" of m, which is a subgroup of Z_p. The number of elements in the group generated by m is called the "order" of m. Primitive elements of Z_p have order p-1. Not all of the elements of Z_p are primitive. Some elements of Z_p have very small orders. At least one element will have order 2. Given that p is prime, the orders of the elements of Z_p will all have values that are products of some or all of the prime factors of p-1. Since p is prime (and p=2 is not interesting ;-), p-1 will contain the factor 2. An small example may make this point clear. Let p == 11. The prime factors of p-1 are 2 and 5. Hence we expect the orders of the elements of Z_11 to be 2, 5, or 10. By enumerating the groups of the elements of Z_11 we see this is so (for Z_11). E.g. Element Ring Order - ------ ----------------------------- ----- 1 1 1 2 2, 4, 8, 5, 10, 9, 7, 3, 6, 1 10 3 3, 9, 5, 4, 1 5 4 4, 5, 9, 3, 1 5 5 5, 3, 4, 9, 1 5 6 6, 3, 7, 9, 10, 5, 8, 4, 2, 1 10 7 7, 5, 2, 3, 10, 4, 6, 9, 8, 1 10 8 8, 9, 6, 4, 10, 3, 2, 5, 7, 1 10 9 9, 4, 3, 5, 1 5 10 10, 1 2 There are 4 primitive elements in Z_11, 2, 6, 7, & 8. The orders of all the elements are as predicted by Euler. Now, let us imagine that Alice and Bob have chosen 11 as their prime and 7 as "g", their generator. Following the steps outlined above: > Alice generates a random number a. say 3 > Bob generates a random number b. say 5. > Bob tells alice g^b, Alice tells Bob g^a. 10 2 > Alice knows a and g^b, and thus generates g^(ab) trivially. 10 > Similarly, Bob knows g^a and b, and trivially generates g^(ab). also 10. > An interceptor only knows g^a and g^b, and because the discrete log > problem is hard cannot get a or b easily, and thus cannot generate g^(ab). Except that the interceptor, evil Eve, took g^a and g^b and tested them for short order, and found that one of them, g^b, had a very short order indeed. So, without knowing a or b, Eve knows that g^(ab) is one of a very few numbers, the elements of the group of g^b. She can now try the elements of that group until, by exhaustion, she finds the value that reveals the key g^(ab). > g^(ab) is now a shared secret of Alice and Bob. And Eve, too. Some primes produce lots and lots of elements with small orders. For example, Z_37 has 12 primitives, 6 elements of order 18, and all the rest have order 9 or less. So, is DH all wet (insecure)? No. There are some simple steps to prevent this problem. First, pick p to minimize the number of elements with small order. This means that we need to know the factorization of p-1. Of course, factoring large numbers is a hard problem, but there are several ways to pick p with known factorization of p-1. The simplest seems to be to pick p such that (p-1)/2 is prime; that is, such that p-1 has two factors, 2 and (p-1)/2. Now, all the elements of Z_p will have orders of either 2, or (p-1)/2, or p-1. There are other methods, that permit other small orders, but we won't explore them here. Second, after "randomly" choosing a, and computing g^a, Alice takes the additional step of making sure that the order of g^a is not small (i.e. is more than 2). If g^a is of small order, she picks another random a, and repeats the process. This is trivial indeed. Bob does likewise for his numbers b and g^b. Since Alice and Bob have eliminated the small groups, Eve will never encounter a g^a or g^b number whose order is less than (p-1)/2, and given that (p-1)/2 is a _very_ large prime number, Eve won't live long enough to try all of the elements of groups of that order. I haven't checked to see if the RSAREF code takes these precautions. *** end quoted text *** I wrote a Diffie-Hellman exchange program as an extension to PGP Tools. It uses the PGP MPILIB and does up to 1024-bit key exchange, then MD5's the shared secret to get an IDEA key. I took most of the precautions above. - From the DHEX10A manual (csn.org) >To use DH, we need a modulus n and a generator g. Unlike an RSA modulus, >which is a product of two primes, a DH modulus must be prime. (n-1)/2 must >also be prime. This makes the moduli slightly painful to find, but they can >be reused indefinitely. DHEX tests a modulus by first testing both n and >(n-1)/2 with fastsieve. Only if both pass is slowtest used. It still took >me a whole day to find the 1024-bit modulus in the demo. There is also a >512-bit modulus there. > >To find the generator, we need the factors of n-1. They are 2 and (n-1)/2. >For each factor f, we compute ((g^((n-1)/f)) mod n). If this is 1 for >either factor, the number is NOT a generator. Generators are easy to find, >usually in one to three tries. The one precaution I did not take is: (from discussion above) >Second, after "randomly" choosing a, and computing g^a, Alice takes the >additional step of making sure that the order of g^a is not small (i.e. >is more than 2). If g^a is of small order, she picks another random a, >and repeats the process. This is trivial indeed. Bob does likewise for >his numbers b and g^b. Does the careful choosing of n and g eliminate this problem, or do I need to modify my Diffie-Hellman code to check g^a for short order? How do you check a number for short order? Pr0duct Cypher -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLd1CL8GoFIWXVYodAQGnhAP+KI+w8ihQCrwKorBpkshwxBOLStIsC1uo 0e/weUyl6SqIaPCvPbYdhoKXfwpMkLxTJLvwb0wCZPtrfUDWJiCao4H7dV8VCh/q ksWDYdVBpxupdMni+vkbuewQz105FaSTz1tHXiy1hgWYO+/OrHXy2r3WEEx8+zcF ZqDMDbdvToU= =sZT1 -----END PGP SIGNATURE-----

2 1

Some 1024-bit DH moduli, and a program to generate them
by Phil Karn 17 Dec '03

17 Dec '03

Here are some randomly generated 1024-bit Diffie-Hellman moduli, along with the smallest generator for each. Each modulus p is a strong prime, i.e., both p and (p-1)/2 are prime. I've appended the generating program, which uses the GNU gmp library. On a 486-66 DX2 running BSDI 1.1, it generally runs in less than an hour though of course the actual run time is probably a Poisson distributed random variable. It turns out that almost any amount of sieving is worthwhile given the cost of the Miller-Rabin test and that the density of 1024-bit strong primes is on the order of only one every 500,000 or so. Before running this again I'd probably decrease the large number sieve size to perhaps 1 million and make the small number sieve as large as possible, rather than keep them the same size. --Phil a4788e2184b8d68bfe02690e4dbe485b17a80bc5f21d680f1a8413139734f7f2b0db4e253750018aad9e86d49b6004bbbcf051f52fcb66d0c5fca63fbfe634173485bbbf7642e9df9c74b85b6855e94213b8c2d89162abeff43424350e96be41edd42de99a6961638c1dac598bc90da069b50c414d8eb8652adcff4a270d567f Generator = 5 de9b707d4c5a4633c0290c95ff30a605aeb7ae864ff48370f13cf01d49adb9f23d19a439f753ee7703cf342d87f431105c843c78ca4df639931f3458fae8a94d1687e99a76ed99d0ba87189f42fd31ad8262c54a8cf5914ae6c28c540d714a5f6087a171fb74f4814c6f968d72386ef356a05180c3bec7ddd5ef6fe76b0531c3 Generator = 2 97dd36c5a63213d5c9a6ab0e1dac722053e6f398beb699dcbaa17368406c9efe2d2b29ccd78fd6faa497d096e07854ea57cf51a621c8a7f01175d39c9b25cda8225b3b4318cfa7d42cf81437272d8d4a8bbb8450fe257a0554bf3c9e53f3c8fdfd7f5effe88885ebd1c36b7e3216e3b19b65a42ea07fe53d4e403d0a3235307f Generator = 5 97f64261cab505dd2828e13f1d68b6d3dbd0f313047f40e856da58cb13b8a1bf2b783a4c6d59d5f92afc6cff3d693f78b23d4f3160a9502e3efaf7ab5e1ad5a65e554313828da83b9ff2d941dee95689fadaea0936addf1971fe635b20af470364603c2de059f54b650ad8fa0cf70121c74799d7587132be9b999bb9b787e8ab Generator = 2 fc642ddf24aa0d3fc50f4bac2f616d1e556c413373fcf4e1188f1f416473d2ac447abba857f8f8d3ab63ba9ee5762b47c59e3048e19f05d84a161e46d319c78fae02779fb6e35a165902633a76fefec77d75c0703818a37fb1bff6613b63ebac287449a9f8a101a3b33769f6cc7a3576f06283e1d45738a88380ee3e85607523 Generator = 2 d4bd8e44f0a05dcb319025b47ff7da8702665c3d1b2a8518a0d46073b499014b6ad8655569cd1655766747cb1e5e1a1fa8a275fd83bc02297784c00952d04bb6b50f79ba9befb1696a85908221a4765880d6dc0680d2ac5c136cfe694255972cebf1f1239beee5b168054ea2b2c08a91b6f22e8bf14153d26f69999a1782990f Generator = 5 da76402bdddbb5dda51f79dae442fe010688b652825ffecb6a04ec6e368a95ef35e729bc30e947ce19d7fa6946c7939d6c62791d9ac705f1509d496e10fbc7795e8197129a09283f5faf8636152c151c5f3910b06e485456fae1df094cb4da07f86e67054be8f2f0b94010d91fcd7fb66d03c57e1bea80839d874856b567403b Generator = 2 f47bddad1d4cf2f8c14985b954e6a9dbd79bd72ee40691c288d34e922a4ffd5486d39fec4e9f6dd64f0b6e9b16b628e44602f701e736d735996b03163f7c6a63152e3d0a7f04f5a6490f2b845340e015dc3c63bd5f9e7d3aaf4c49cc4fa97ff19fa8446ceb7dc2ab632cc6ebccce60163eb1b7930afbcbf077726ffce904a583 Generator = 2 c292efe525ea4315de43b0c620448009100cbf68a83c948f72809bee0c77c13e166fb6264355bcfb8c4457291f82f080bf6ca8328fa52c1b1e4a8cce696026222db8d1122923d2072bde6e373b6a92acfe1c5107512ffaadd35fe5ef74e61dc025436b3715d07bb382f8d2e114dabe57b8b574aeb20fb9d287105d98d130792b Generator = 2 bd36e0fa98b48c678052192bfe614c0b5d6f5d0c9fe906e1e279e03a935b73e47a334873eea7dcee079e685b0fe86220b90878f1949bec73263e68b1f5d1529a2d0fd334eddb33a1750e313e85fa635b04c58a9519eb2295cd8518a81ae294bec10f42e3f6e9e90298df2d1ae470dde6ad40a301877d8fbbabdedfced5fe5fbf Generator = 7 /* Generate a prime suitable for use as a Diffie-Hellman modulus, * i.e., (p-1)/2 is also prime. Also find a generator. * P. Karn, April 1994. */ #include <stdio.h> #include <gnu/gmp.h> #define PLEN 1024 /* 1024 bits */ #define SEARCHSPACE 5000000 /* Search range beyond starting point */ #define SIEVESIZE (SEARCHSPACE/2) /* Sieve only includes odd numbers */ #define BIT_SET(a,n) ((a)[(n)>>5] |= 1 << ((n) & 31)) #define BIT_CLEAR(a,n) ((a)[(n)>>5] &= ~(1 << ((n) & 31))) #define BIT_TEST(a,n) ((a)[(n)>>5] & (1 << ((n) & 31))) unsigned long Smallsieve[SIEVESIZE/32]; long generator(MP_INT *p); /* Construct sieve of prime numbers [3...SIEVESIZE*2] (odd numbers only) */ smallsieve(void) { int j,k,p; memset(Smallsieve,0,sizeof Smallsieve); for(k=0;k < SIEVESIZE;k++){ if(BIT_TEST(Smallsieve,k)) continue; /* 2*k+3 is composite */ p = 2*k+3; /* The next small prime */ for(j=k+p;j<SIEVESIZE;j += p){ BIT_SET(Smallsieve,j); /* Mark all multiples of p */ } } } main(argc,argv) int argc; char *argv[]; { MP_INT p,q,start,g,f,two,tmp; unsigned long sieve[SIEVESIZE/32]; char *cp; int i,j,k; memset(sieve,0,sizeof(sieve)); mpz_init(&p); mpz_init(&q); mpz_init(&start); mpz_init(&f); mpz_init(&tmp); mpz_init_set_ui(&two,2); printf("Generating small prime numbers...\n"); smallsieve(); /* Generate random starting point for subprime search, * and ensure that it's odd */ if(argc < 2){ printf("Generate random starting point\n"); mpz_random(&p,PLEN/32); } else { printf("Using specified starting point\n"); mpz_set_str(&p,argv[1],0); mpz_mod_2exp(&p,&p,PLEN); } /* starting q = (p-1)/2 */ mpz_div_2exp(&start,&p,1); if((mpz_get_ui(&start) & 1) == 0) mpz_sub_ui(&start,&start,1); printf("Start q search at\n"); cp = mpz_get_str(NULL,16,&start); fputs(cp,stdout); free(cp); printf("\n"); /* p = 2*start + 1 */ mpz_mul_2exp(&p,&start,1); mpz_add_ui(&p,&p,1); /* Sieve out q's and p's with small factors */ printf("Sieving from starting point to q+%d...\n",SEARCHSPACE); for(i=0;i<SIEVESIZE;i++){ int s,r; /* Get next small prime */ if(BIT_TEST(Smallsieve,i)) continue; s = 2*i+3; /* r = start mod s */ r = mpz_mmod_ui(NULL,&start,s); k = s - r; /* start+k is first entry divisible by s */ if(k == s) k = 0; /* s divides start */ if(k & 1) /* start+k even? */ k += s; /* Make start+k odd, and k even */ /* The sieve omits the even numbers */ k >>= 1; for(;k < SIEVESIZE;k += s){ BIT_SET(sieve,k); /* s divides start+2*k */ } /* r = p mod s */ r = mpz_mmod_ui(NULL,&p,s); k = s - r; /* p+k is first entry divisible by s */ if(k == s) k = 0; /* s divides p */ while(k & 3) k += s; /* The sieve omits the numbers divisible by 4 */ k >>= 2; for(;k < SIEVESIZE;k += s){ BIT_SET(sieve,k); /* s divides p+2*k */ } } printf("Sieve done, checking remaining candidates...\n"); for(k=0;k<SIEVESIZE;k++){ if(BIT_TEST(sieve,k)) continue; /* Definitely composite, skip */ /* Candidate prime */ printf("test prime candidate at start+%d\n",2*k); mpz_add_ui(&q,&start,2*k); if(!mpz_probab_prime_p(&q,1)) continue; printf("q passed Rabin-Miller test...\n"); /* p = 2*q + 1 */ mpz_mul_2exp(&p,&q,1); mpz_add_ui(&p,&p,1); if(!mpz_probab_prime_p(&p,1)) continue; printf("p passed Rabin-Miller test...\n"); break; } if(k == SIEVESIZE){ printf("Failed to find a strong prime\n"); exit(1); } printf("Found modulus p =\n"); cp = mpz_get_str(NULL,16,&p); fputs(cp,stdout); free(cp); printf("\n"); /* Find g, primitive root mod p */ printf("Finding generator\n"); i = generator(&p); printf("Generator g = %d decimal\n",i); } /* Find smallest primitive root (generator) for strong prime p using * algorithm on p. 209 of Schneier. Since we know (p-1)/2 is prime, * we know the factorization of p-1: it's simply 2 * (p-1)/2. * This makes our job *much* easier. */ long generator(p) MP_INT *p; { MP_INT g,tmp,q; int i; mpz_init(&g); mpz_init(&tmp); mpz_init(&q); mpz_sub_ui(&q,p,1); mpz_div_2exp(&q,&q,1); /* q = (p-1)/2 */ /* Try 2. No need to test 2^2 mod p != 1 :-) */ printf("Trying 2"); mpz_set_ui(&g,2); mpz_powm(&tmp,&g,&q,p); /* tmp = 2^q mod p */ if(mpz_cmp_ui(&tmp,1) != 0){ mpz_clear(&g); mpz_clear(&tmp); mpz_clear(&q); return 2; /* 2 is primitive */ } /* Try small primes starting with 3 */ for(i=0;i<SIEVESIZE;i++){ /* Get next small prime */ if(BIT_TEST(Smallsieve,i)) continue; printf(" %d",2*i+3); mpz_set_ui(&g,2*i+3); /* g = trial generator */ mpz_powm(&tmp,&g,&q,p); /* tmp = g^q mod p */ if(mpz_cmp_ui(&tmp,1) == 0) continue; /* g is not primitive */ /* This test can't possibly fail for small values of g, * but it's here for completeness anyway */ mpz_powm_ui(&tmp,&g,2,p); /* tmp = g^2 mod p */ if(mpz_cmp_ui(&tmp,1) == 0) continue; /* g is not primitive */ break; /* Passes both tests */ } printf("\n"); mpz_clear(&g); mpz_clear(&tmp); mpz_clear(&q); if(i == SIEVESIZE){ printf("Could not find a small generator\n"); return -1; } return(2*i+3); }

1 0

Digital signature standard
by Bradley W. Dolan 17 Dec '03

17 Dec '03

AP reported on 5/20/94: >The federal government will begin using computer-generated >signatures to verify the identities of people submitting bids, >contracts and other information electronically. [...] > It is up to people outside the government to decide whether >they want to use the standard, which produces the electronic signature. >Government agencies that currently use some other method of electronic >verification will have to switch to the new standard on Dec. 1, said >Miles Smid, manager of security and technology for the institutes. >[...] > >[The standard employs] a 320-bit number that makes up the >electronic signature. The government computer then compares >the signature against the person's public key, which would be stored in >a government database. Brad bdolan(a)well.sf.ca.us

1 0

Re: Is my DH exchange secure?
by hfinney＠shell.portal.com 17 Dec '03

17 Dec '03

With a strong prime, there is no need to use generators, as Eric implied. Looking at Phil's list, we see 2's and 5's being chosen as generators. Even for those cases where 2 is not a generator, it has period (n-1)/2. This is just as good, from what I understand. Finding the discrete log depends on the size of the modulus, not on the size of the group, unless the size of the group is drastically less than the size of the modulus. That is why the DSA uses a modulus of 512 bits and a group of size 160 bits. Even a group this small provides all the security associated with a 512 bit modulus. (Caveat: I haven't been able to find my reference to this, but I read it a few weeks ago in a crypto paper, and I am confident it is standard number theory/cryptography.) In the case of a 1024 bit strong prime, non-generators (other than 1 and -1) have period of size 1023 bits, just as good for all prac- tical purposes. For what I was calling "strongish" primes, which are about 100 times easier to find (primes of the form kq+1, where q is prime and k is around 100), I think it is also unnecessary to check for generator-hood. Non-generators are overwhelmingly likely to have periods greater than 1000 bits in size, which provides all the security of the 1024 bit modulus. Putting this together, secure Diffie-Hellman is much easier to do than the more careful implementations require. Picking a strongish prime need not take much longer than choosing an RSA key of twice the size (e.g. it takes about as long to choose a strongish 1024 bit prime as to create a 2048 bit RSA key). Then pick a random element as the base for the DH exponentiation, choose your x's and y's at random, and go. Adding the extra checks really doesn't increase the security. Hal

1 0

*Here they come
by Gary Jeffers 17 Dec '03

17 Dec '03

Peter Murphy asks for some clarifications. In "DEATH TO STATISTS", I, of course, exclude minarchists from the term "statists". For "DEATH TO STATISTS", I should have substituted "DEATH TO LEFT WING STATISTS" as they are the kind that particularly infuriate me. A PC would not be equivalent to a left wing statist. A PC would have more characteristics that a left wing statist. I have not figured out the exact recipe for such monsters yet. Would "DEATH TO PC'S" violate campus speech codes? Anyway, I think that its important to let them know that we really don't approve of them. They disapprove of so many things & are go aggressive about showing their disapproval & intolerance that I think its only fair. Incidentally, I think that people should be aware of the debt that we owe NEWSWEEK with respect to the "POLITICALLY CORRECT". In their Dec. 24, 1990 issue, NEWSWEEK attacked the politically correct enforcers. It was their "THOUGHT POLICE" issue & it devoted at least 10 pages to their abuses. That issue collectivized the term "POLITICALLY CORRECT". Before that issue, the "POLITICALLY CORRECT" were nameless & nearly invisible monsters. NEWSWEEK gave us a collectivized sneer word that we could attack them with. I don't know why the term "THOUGHT POLICE" didn't catch on big. Sorry to be so late in replying. Yours Truly, Gary Jeffers PUSH EM BACK! PUSH EM BACK! WWWAAAYYY BBBAAACCCKK! BBBEEEAAATTT STATE !

1 0