- cypherpunks-legacy - lists.cpunks.org

number theory number theory
by catalyst-remailer＠netcom.com 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- All right, a number theory discussion! >The integer N is prime if: > 2^N - 2 > --------- > N is an integer. Well, this is false. The above formula is derived from Fermat's Little Theorem, or Euler's Generalization of Fermat's Little Theorem. a^(n-1) = 1 mod n, n prime, gcd(a,n) = 1 ==> a^n = n mod n a^n - n = kn, for k some integer (a^n - n)/n = k, for k some integer now sub in a = 2. However, the converse of this is not true (n isn't necessarily prime if it satifies the formula). Composities that satisfy this are called pseudoprimes. For example, for a = 2, n = 341 satisfies the relation, so 341 is a pseudoprime base 2. Now it works "most" of the time, and in fact one method of testing large integers for primality is to choose a whole bunch of a's and plug in n. If a^(n-1) mod n != 1, the number is composite and can be rejected. But, if a^(n-1) mod n == 1, you can only be 50% sure n is prime. (Roughly speaking; Phil Karn notes that the PGP docs indicate a 50%, I've seen proofs that this pseudoprime test fails 50% of the time, etc. But these are upper bounds; the real percentage seems much lower and I haven't seen a tighter bound on it). There is a "strong psuedoprime" test, in which failure occurs for at least 25% of integers in the range, thus the probability that a composite will pass is at most 25%. Even better is Lucas' test, but it runs a bit slow. However, you can be unlucky and pick a Carmichael number, which will pass the pseudoprime test for all bases relatively prime to n (for all a such that gcd(a,n) = 1). Ray Cromwell advises to choose n = 561, the smallest Carmichael number (an excellent choice!) Carmichael numbers exist, they are relatively rare, formulas exists for generating some of them... Eric Hughes mentions that 1729 is the next Carmichael number... not quite true. 1105 is the next Carmichael number. (But congrats Eric for even remembering the third one!) ;) Now, some other topics: > For any number n which is prime, (2^n)-1 is also prime (Mersenne's > theorem). Hm... some confusion here. A Mersenne prime is of this form (2^n) - 1 where n is prime, but not all number this formula generates are primes. Mersenne primes are related to perfect numbers. An example of a composite of this form: for n = 11, 2^11 - 1 = 2047 = 23 * 89 > For any number n (2^(2^n))+1 is prime. (I might have that wrong, I > don't remember exactly) Well, no. These number are Fermat numbers, and while the first 5 (n=0 to n=4) but Euler showed that the Fermat number for n=5 is composite. As an aside, Fermat numbers satisfy the pseudoprime test. > For any number n, if the square root of (n!)+1 is an integer, it is > also prime. (This is interesting, but rather useless in practice) A couple of issues here: I think you may be remembering a different theorem, a consequence of Wilson's theorem. Wilson's theorem says: for any prime p, (p-1)! = -1 mod p The theorem I think you are referring to is: if P is the product of the remainders relatively prime to m, then P = +/- 1 mod m; +/- = plus or minus The congruence is +1 except in three cases: 1) m = 4 2) m = p^b (m is a power of an odd prime) 3) m = 2p^b (m is twice the power of an odd prime) I'm still trying to either prove or disprove your claim! Two followups relating the the original formula posted: > For any number a, 1<a<=n, n! mod a == 0; therefore, n!+1 mod a == 1. > n!+1 is prime. Prime numbers don't have integral square roots. Good analysis, except for the "n! + 1 is prime" part. The only thing you can say is n!+1 has no factors <= n. For example, n = 4, n!+1 = 25 = 5 * 5. > Well, it was quoted from memory, so it's possible that I made an > error, but it seems to work as stated... > For example : > (4!+1)^(1/2)=5 > (5!+1)^(1/2)=11 > (7!+1)^(1/2)=71 > I can't find a value which produces a result that is a non-prime > integer. (Of course that doesn't prove that there isn't one.) Still working on this... ;) -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLanNNYOA7OpLWtYzAQF10wP9GExbaoloiXqFe7AtXb/UzUHXhW3VDC1b mfD0RhgK2i0Dr05RW5FCvj/9i7Jxhrd3E26hTe5g4WckvIcvp+GWhE/5fkdtVMA9 THutX1ukGO/5qCxSRT4hVCeXStAz7tunkF3fcEQjPe8pSSvKxN8tw/wIZzclRDRx JDE4HYRhAz0= =OW8h -----END PGP SIGNATURE-----

4 4

SSN Quandary (was: CreditCard info)
by Garth Brown 17 Dec '03

17 Dec '03

---------- | From: "Pat Farrell" <pfarrell(a)netcom.com> | | I'm sure that you are correct. I talked just this past Friday to | David Banistar at EPIC/CPSR on this. But the law seems to | be mostly ignored, as is the fact that SSN's are not unique. | | The key is, what do we do about it? I routinely refuse to give my SSN to agencies that have no government affiliation. I've been hassled for this stance, and frequently refused service/credit. My phone company demanded an exorbitant deposit because I wouldn't give them my SSN when signing for service. I am greatly disturbed by the amount of personal information currently available on an individual, and accessible with keys as simple as SSN, full name, and mother's maiden name. I, however, have no clue what to do other than continue to refuse to supply data whenever possible. garthB> ------------------------------------------------------------------------------ Garth S. Brown, Semaphore Corporation 122 South Jackson Street, Suite 350 garthb(a)semaphore.com Seattle, Washington 98104 InterNIC WHOIS: GB(31) -Public key available via finger of garthb(a)semaphore.com -PGP2.6 Key fingerprint = 65 0E 48 A1 F7 38 DB 03 3F 77 77 9E B5 53 2E 96 ------------------------------------------------------------------------------ All problems can be solved with the proper application of high explosives.

1 0

Re: Problem in draft FIPS `CRYPTOGRAPHIC SERVICE CALLS'
by koontzd＠lrcs.loral.com 17 Dec '03

17 Dec '03

It appears to be an attempt to formalize the interface to the Tessera card. The file cryptcal.txt can be found on csrc.ncsl.nist.gov

1 0

RE: CreditCard info
by sidney＠taurus.apple.com 17 Dec '03

17 Dec '03

[various people speculated about legality of a company requiring your SSN] There's a Social Security Number FAQ posted regularly on alt.privacy, and also available from the usual usenet FAQ sites. It says that government agencies in the U.S. have restrictions regarding asking for and using your SSN, but private sector organizations do not. There's a lot more detail, but I don't need to repeat it here. -- sidney <sidney(a)apple.com>

1 0

RE: CreditCard info
by rah＠shipwright.com 17 Dec '03

17 Dec '03

At 11:49 PM 8/7/94 -0500, Brian Lane wrote: > ....in 10 years all >newborns will have a small uP implanted into their hand(ala Demolition >Man) that will keep track of all their electronic data. Scares the crap >out of me. We just had thread about that. I had brought up Gerry O'Neill's old book "2081", which had a discussion of buying things by picking them up and walking away with them (everything, including you, had an identifying transponder). There was some talk about Xerox PARC's work with transponders in their "Ubiquitous Computing" office concept. What I didn't understand was how to implement Esther Dyson's idea about people owning all their personal information and protecting all that "property" with strong crypto. Paradoxically, I bet both these ideas (transponders and personal information as property through strong crypto) can work together. Cheers, Bob Hettinga ----------------- Robert Hettinga (rah(a)shipwright.com) "There is no difference between someone Shipwright Development Corporation who eats too little and sees Heaven and 44 Farquhar Street someone who drinks too much and sees Boston, MA 02331 USA snakes." -- Bertrand Russell (617) 323-7923

1 0

Digicash address?
by Adam Shostack 17 Dec '03

17 Dec '03

Could someone send me contact information for David Chaum's Digicash company? An email address would be great... Thanks in advance, Adam

2 1

Looking for info on PGP enabling mail apps. . . .
by Garth Brown 17 Dec '03

17 Dec '03

i'm looking for info on enabling automatic PGP signing of mail messages from PINE and ELM. Perhaps i'm babbling about something in a FAQ i missed, in which case i'll filter flames to /dev/null. =) thanks garthB> ------------------------------------------------------------------------------ Garth S. Brown, Semaphore Corporation 122 South Jackson Street, Suite 350 garthb(a)semaphore.com Seattle, Washington 98104 InterNIC WHOIS: GB(31) -Public key available via finger of garthb(a)semaphore.com -PGP2.6 Key fingerprint = 65 0E 48 A1 F7 38 DB 03 3F 77 77 9E B5 53 2E 96 ------------------------------------------------------------------------------ All problems can be solved with the proper application of high explosives.

2 1

Anonymous Transport Agents (Was: Latency vs. Reordering)
by Jeff Gostin 17 Dec '03

17 Dec '03

hughes(a)ah.com (Eric Hughes) writes: > Simulating any of the salient features of a link encryptor over the > Internet is an interesting exercise, particularly in regard to price > negotiation with your service provider. I'm about to branch into the limits of my knowledge on this particular topic: I run a DOS site under a heavily modified version of Waffle (1.65 base), so the Unix-ish transport mechanisms are a tad out of my realm of knowledge. With that in mind... Suppose an encryption-savvy mail transport agent, say ESMTP, was developed. Further suppose that part of handshaking protocol for this transport protocol included an ENCRYPTED reverse lookup on IP identities to check that the message is actually coming from where it claims it's coming from. Suppose again that the results of this lookup were only checked for correctness (boolean), and then discarded WITHOUT LOGGING, or at least with minimal logging. If the reverse lookup was TRUE (IE: the sending machine was who it said it was), the message was accepted. If it failed, the message would be accepted, and then sent to the bit bucket. In this model, one could provide anonymous transportation of anonymous mail FOR EVERY MACHINE ON INTERNET providing that the original message wasn't forged. All that would be required (beyond running ESMTP) is an encrypted version of the return address (a la Soda remailer) to be placed some predetermined place in the message. This seems too easy: What am I missing? Have I actually come up with a way to do this? --Jeff -- ====== ====== +----------------jgostin(a)eternal.pha.pa.us----------------+ == == | The new, improved, environmentally safe, bigger, better,| == == -= | faster, hypo-allergenic, AND politically correct .sig. | ==== ====== | Now with a new fresh lemon scent! | PGP Key Available +---------------------------------------------------------+

2 1

PGP BUG/FEATURE: multi-platform keys
by nobody＠alumni.cco.caltech.edu 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- Recently I have received two keys that were unusable without modification (from wonderer and Sameer) because they were not prepared using canonical text. I had to replace all the carriage returns by hand (this is the workaround for mac users who receive PC keys). Why is non-canonical text even an option in pgp? Who would use it except by mistake? As long as I'm at it, here are some more macPGP2.3 bugs, for those who care. Trying to decrypt a message signed by a key I don't have causes a serious crash requiring reboot. Trying to select cancel in a signature dialogue just raises the same dialogue box instead of cancelling. I'm running on a powerbook 145 under system 7.0.1. Eternal!Optimist(a)anon.penet.fi (copyright 1993, Eternal Optimist [Ha Ha Ha]) 0) 0) =:()]-< <na26436(a)anon.penet.fi> -----BEGIN PGP SIGNATURE----- Version: 2.3 iQCVAgUBLNe7R4jvfLxJbYYtAQFFHQP7BCqn1JKaI09wBrWnjOF73CPz7GetaC/y XL8zqhmzDdrGdLbWB/vBDgXW7z+2EJHazbvqaUhq1GQw8bq+opC2fe4mXcw2x3Y+ wliLy1CWDtfl24L8ah//nLQMtttfG4kXjiB8JqUnS7US+W3vvH3AXxi+wZb5W2qi 7gPXMErUCUA= =Ew/6 -----END PGP SIGNATURE-----

1 0

Re: Latency vs. Reordering (Was: Remailer ideas (Was: Re: Latency vs. Reordering))
by jdd＠aiki.demon.co.uk 17 Dec '03

17 Dec '03

In message <199408080514.WAA28015(a)netcom7.netcom.com> "Timothy C. May" writes: > Jim Dixon writes: > (quoting Hal Finney) > > > If this idea seems valid, it suggests that the real worth of a network of > > > remailers is to try to assure that there are at least some honest ones > > > in your path. It's not to add security in terms of message mixing; a > > > single remailer seems to really provide all that you need. > > > > Yes, in an ideal world. Each additional remailer introduces another > > chance of being compromised. > > No, I'm afraid you have this backwards. A remailer cannot introduce > a chance of increase the chance of being compromised. There are at least two models of remailer networks being kicked around. In what I have called RemailerNet, if a gateway is compromised, then some degree of traffic analysis is possible, and other parts of the system become less secure. Security increases when there are two remailers handling your traffic, because then neither should know the identity of both sender and receiver. Whether the addition of more intervening remailers increases the security of the system in RemailerNet is a complex question. In the second model of remailer networks, I also believe that using more than two remailers and the random selection of remailers decreases the security of the system if there is regular traffic between correspondents. To argue this at all, one would need a much clearer model with all of the assumptions spelled out in detail. For the argument to be interesting, the model would have to be realistic. My personal impression is that the second model is highly insecure in cases where there is regular traffic between two parties and some third party has significant resources. -- Jim Dixon

1 0