- cypherpunks-legacy - lists.cpunks.org

public key of Lady Ada ???
by catalyst-remailer＠netcom.com 17 Dec '03

17 Dec '03

Where is the public pgp key of Lady Ada?

1 0

Wow, intelligent remailer
by danisch＠ira.uka.de 17 Dec '03

17 Dec '03

Wow, what an intelligent remailer: I sent a ping to remail(a)hacktic.nl and he answered "PONG" Did they employ a human to do the remailing job? (The Netherlands, you know...) Hadmut

2 1

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: Unicorn vs. tmp@netcom
by joshua geller 17 Dec '03

17 Dec '03

> To Black Unicorn: > Despite your protestation, "I also don't like to be a bully", it seems > to me that your pursuit of this case was predicated on your ability to > be a bully and an insider. Like your colleagues Cantor and Seigel, you > emitted flamebait and then pretended offense at the inevitable flames. > You taunted tmp@netcom about his illness, reminding him at least three > times in one message to take his medicine. did uni do this too? I thought that was me. of course, it very commonly occurs that things that I think I he done turn out to actually been done by someone else. josh

1 0

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

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

No Subject
by anonymous＠extropia.wimsey.com 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- Hello again. I have been too busy to post very much to the net recently, but I'm still here. As an experiment, I wanted to hack PGP 2.3A to produce and use 2048-bit keys. There was nothing sophisticated about this hack. I just changed MAX_BIT_PRECISION in mpilib.h to 4096, upgraded the POOLSIZE in random.c to 1024, and changed the version number to "2.3b" in pgp.c so I would know when I am running the hacked version. Generating 2048 bit keys is very painful, because over 260 bytes need to be typed for the pool. It took over five minutes to generate the key after the pool was full. Once created, though, encryption and decryption are not significantly slower than with 1024 bit keys, at least not on my 486DX2/66 running Linux 1.0. It only took 3 seconds to encrypt pgpdoc1.txt (using -ea) and 8 seconds to decrypt the result. Of course, the large keys created with "2.3b" are not compatible with any other version. I attempted to use the PSEUDORANDOM compiling flag, but pgp refused to link. I suppose I should put some more effort into resolving this problem. I am sending this note out for those who would like to play with big keys, but did not want to take the time to hunt through the source looking for the necessary values to change. Please treat this as an *experiment*. It is entirely possible that "2.3b" is potentially insecure, because I have not made any attempt to locate all of the memory-erasing routines that clean up after key generation and encryption and confirm that they erase all of the new memory used. I hope that the more sophisticated cypherpunks will not sneer too much at my feeble beginner's efforts. I would like to hear from anyone who performs this experiment, perhaps with a more sophisticated hack, and does timing tests on other machines, especially slower machines like 386's and 68020's. Lady Ada -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLd53bKXNQdJx1hMZAQHaEwQApOWGq0P+OqsgYolbZrjaIWhrghhV9KcY X5DqgKK8NLdND1aR17JVwUEQeo3eFok6NTjioiLg4sIQdTQNOX8Nd9bQgMxswyyi EIe/6Ki9YrxlArteUoc0zy7MaB0V1sxH3CdvEQmLnr8XKU03pnD7FCZXedjhic93 +Tt4fNrNGYk= =LmWA -----END PGP SIGNATURE-----

1 0

"Email-Firewalls" / Instant Corporate PGP
by Vincent.Cate＠FURMINT.NECTAR.CS.CMU.EDU 17 Dec '03

17 Dec '03

Companies like the idea of firewall machines to protect the security of their internal nets. I bet they would also like something called an "email-firewall". Names are important. :-) I think of the email-firewall as a slightly modified anonymous-remailer. Outsiders could send encrypted mail to the remailer and it would decrypt it and send it on to the right person inside the company over internal (more secure) nets. The email-firewall could also encrypt outgoing mail when it was going to a person who either had a listed PGP key or who was working at another company with an email-firewall. Also, this remailer would not make the mail anonymous. Corporations need security, not anonimity. Each company would only need to buy one copy of ViaCrypt PGP. For a company this cost is, of course, negligible. With this people inside the company would not need to deal with the encryption directly. They getting encrypted mail would not take anything new, and sending might take a slight change. Of course this is only a step towards true end-to-end encryption, but it is easy and far better than what they have now. Also, it fits with the way companies work. There is a security guard at the entrance to the plant, but once inside people generally trust each other and don't worry about security. With this, internal mail is still like postcards, but external would have an envelope. I thought about this after making a short script (below) so that mail to vac+pgp(a)cs.cmu.edu (the low security envelope) would be decrypted automatically. This also needed the following line in my .maildelivery: Addr vac+pgp pipe ? /usr/vac/pgp/incoming I am not going to make the "email-firewall" at this time, but thought I would throw the idea out. Has anyone done this? Let me know if you do. One question. How do I extract 2 public keys into one ASCII keyblock? Now that I want to make 2 keys FTPable ... -- Vince #!/bin/csh -f # # Vince Cate setenv PGPPATH /usr/vac/pgp setenv PGPPASS "not really vinces passphrase" cd $PGPPATH cat > mailtmp.asc egrep 'Date:|From:|Subject:|To:' mailtmp.asc > mailtmp echo " " >> mailtmp pgp -f < mailtmp.asc >> mailtmp /usr/ucb/mail -s "Was encrypted" vac < mailtmp exit 0

1 0

U.S. Card info sites?
by David Merriman 17 Dec '03

17 Dec '03

I'm looking for any ftp sites that have any information on the proposed U.S. Card, similar to what the cypherpunks site has on Clipper. Thanks. Dave Merriman

1 0