- cypherpunks-legacy@lists.ogf.org

Re: Suggest splitting things up
by John W Noerenberg 03 Dec '92

03 Dec '92

At 1:22 PM 12/2/92 -0800, John Draper wrote: >To Cypherpunks: > >Greetings, Back on-line again, after wading through about 225 messages >that has accumulated in the last 4 days. The volume of messages >is really getting high, and perhaps we might want to try and break >them up into the following proposed lists. Sounds like a fine idea. john noerenberg jwn2(a)qualcomm.com noerenberg.j (Applelink) =========================================================== Do not uselessly lament your luck that is giving way, your work that has failed, your life's plans that have all ended in despair. Like a man long prepared, like a man of courage, bid her farewell, the Alexandria that leaves you. -- "The God Abandons Anthony", Constantine Peter Cavafy [1911] ===========================================================

4 4

enjoy enjoy
by Fan Li TAI 03 Dec '92

03 Dec '92

Hiya, Below's something I found... I know you all have been swamped with mail... but this one is in the spirit of things, I think... Found it in Life... ____begin____ From: sherman@.cs.umbc.edu (Dr. Alan Sherman) Subject: Superpolylogarithmic Subexponential Functions Newsgroups: rec.music.dementia Announcing: Technical Report TRCS-91-17, University of Maryland Baltimore County. A preliminary version of this paper appeared in two parts in {\it SIGACT News}, {\bf 22}:1 (winter 1991), Whole Number~78, 65--73, and {\bf 22}:2 (spring 1991), Whole Number~79, 51--56. On Superpolylogarithmic Subexponential Functions Alan T. Sherman Computer Science Department University of Maryland Baltimore County Baltimore, Maryland 21228 and Institute for Advanced Computer Studies University of Maryland College Park College Park, Maryland 20742 June 21, 1990 (revised April 1, 1991) Abstract A superpolylogarithmic subexponential function is any function that asymptotically grows faster than any polynomial of any logarithm but slower than any exponential. We present a recently discovered nineteenth-century manuscript about these functions, which in part because of their applications in cryptology, have received considerable attention in contemporary computer science research. Attributed to the little-known yet highly-suspect composer/mathematician Maria Poopings, the manuscript can be sung to the tune of ``Supercalifragilisticexpialidocious'' from the musical Mary Poppins. In addition, we prove three ridiculous facts about superpolylogarithmic subexponential functions. Using novel extensions to the popular DTIME notation from complexity theory, we also define the complexity class SuperPolyLog/SubExp, which consists of all languages that can be accepted within deterministic superpolylogarithmic subexponential time. We show that this class is notationally intractable in the sense that it cannot be conveniently described using existing terminology. Surprisingly, there is some scientific value in our notational novelties; moreover, students may find this paper helpful in learning about growth rates, asymptotic notations, cryptology, and reversible computation. Keywords. Algorithms, asymptotic notation, complexity theory, cryptography, cryptology, DTIME, mathematical humor, Maria Poopings, Mary Poppins, musical computer science, reversible computation, Supercalifragilisticexpialidocious, superpolylogarithmic subexponential functions, SuperPolyLog/SubExp. --- lyrics --- Superpolylogarithmic Subexponential Functions (Sung to the tune of ``Supercalifragilisticexpialidocious.'') Um diddle diddle diddle, um diddle ay! Um diddle diddle diddle, um diddle ay! Superpolylogarithmic subexponential functions! Faster than a polylog but slower than exponential. Even though they're hard to say, they're truly quintessential. Superpolylogarithmic subexponential functions! Um diddle diddle diddle, um diddle ay! Um diddle diddle diddle, um diddle ay! For Alice to send a message through to Bob when Eve's eavesdropping, do use a trapdoor one-way function---not a one-key mapping. First take a message x, let's say, and raise it to the e; then mod it out by p times q but keep these secretly. Oh! (Chorus) Um diddle diddle diddle, um diddle ay! Um diddle diddle diddle, um diddle ay! The process takes but poly-time and appears to be secure: why even just a single bit is one over polylog pure. Though Alice thinks that Eve must spend time at least exponential, by using Lenstra's elliptic curves, Eve splits n subexponentially. Oh! (Chorus) Um diddle diddle diddle, um diddle ay! Um diddle diddle diddle, um diddle ay! we remove the heat with water but there's a better strategy. Since thermodynamics does not apply when info is not doomed, the laws of physics don't require that power be consumed. Oh! (Chorus) Um diddle diddle diddle, um diddle ay! Um diddle diddle diddle, um diddle ay! Now Bennett said in `73, to run a program P, you simulate the program P, but do so reversibly. The problem with this method is that space is exponential, so trade off time to save on space---this really is essential! Oh! (Chorus) Um diddle diddle diddle, um diddle ay! Um diddle diddle diddle, um diddle ay! Did you know if you invert one, you get a funtionential subexporithmic logapolyrepus? But that's quite a singularity! So, If you are in an oral exam and cannot find the way, just summon up these words and then you've got a lot to say. But better use them carefully or you could fail the test. A professor once asked me, ``What do you call functions that grow faster than any polylogarithm but slower than exponential?'' There're, Superpolylogarithmic subexponential functions! Superpolylogarithmic subexponential functions! Superpolylogarithmic subexponential functions! Superpolylogarithmic subexponential functions! --- end of lyrics --- Note: See paper for detailed performance notes and mathematical proofs by anagramming.

1 0

Re: Suggest splitting things up
by Richard Childers 03 Dec '92

03 Dec '92

>>Greetings, Back on-line again, after wading through about 225 messages >>that has accumulated in the last 4 days. The volume of messages >>is really getting high, and perhaps we might want to try and break >>them up into the following proposed lists. >Sounds like a fine idea. "I aggree." So do I, but a digest ( 225 / 4 == 56.25 messages per day, concatenated into one giant digest of messages, sans headers ) would also make the traffic manageable, while preserving the ability for the various groups to benefit from one another's divergent, but relevant, insights into the overall process and its possible applications. Even if you split the list into multiple 'sub-topical' lists, you'll be 'swamped' with N times the maintenance ( and I suspect maintenance is already a bit of a hassle, with bounce messages and the like 'deluging' the hapless administrative staff with a 'rain' of problems ), as well as 'flooded' with N times as many subscribe and unsubscribe requests ... and will probably still contemplate a digest format eventually. (-: An interactive direct mail option should be preserved, in fact, it would remain the primary entity ... all that's needed is to add some sort of alias that evaluates to a queue to the list, then write a script to read the queue ( with some queue management to avoid race conditions ), strip out all but trivial header information and '> ' those left behind, and generate email to those individuals whom have transferred themselves from the primary alias to the secondary digestifier-and-remailer. There's a thing called majordomo(a)greatcircle.com that does this, I think. I don't know if it's public domain, but it does a lot of this, firewalls and firewalls-digest are both served by it, and I think it also provides archival services and such. ( There are others, also. ) My $0.02. -- richard

1 0

bank protocol run through
by Karl L. Barrus 03 Dec '92

03 Dec '92

I find it useful to work through a protocol by hand a few times to really see what's going on. Here is an example of the digital bank protocol. It is meant for people who are curious to see if it works, as educational material for new subscribers, or general interest. I'm choosing relatively small numbers to use: in a real implementation, they would be much much larger. OK, let's start! ---------------------------------------- On the bank's side, it chooses the primes p = 2038074743 and q = 2038074947 and so the public key n = pq = 4153749073821763621 also phin = Euler totient function of n = (p-1)(q-1) = 4153749069745613932 The bank decides to make people use the exponent 5 (it's just easier to tell if GCD[5, phin] is 1) 1) Alice chooses a random x, r. She hashes x to yield fx x = 3141526535 r = 5772156649 fx = 2718281828 Here, I just picked the value of the hash function from the mathematical air, so to speak. Alice computes B = r^5 fx mod n = (5772156649^5 2718281828) mod 4153749073821763621 = 592088213321408342 -> B = PowerMod[r^5 fx, 1, n] in Mathematica Alice sends B to the bank. 2) The bank takes fifth root of B. Or, it raises B to the power that is the inverse of 5 mod n. To find the inverse of 5 mod n, compute inv1 = 5^(-1) mod phin = 5^(-1) mod 4153749069745613932 = 1661499627898245573 The bank can do this since it knows the factorization of n. -> inv1 = PowerMod[5, -1, phin] in Mathematica So, to take the fifth root: D = B^inv1 mod n = (592088213321408342 ^ 1661499627898245573) mod 4153749073821763621 = 1189395596986402260 -> D = PowerMod[B, inv, n] in Mathematica Just as a check: D^5 mod n = = (1189395596986402260 ^ 5) mod 4153749073821763621 = 592088213321408342 = B So we're OK. -> Mod[D^5, n] in Mathematica Bank sends Alice D. 3) Alice extracts C by dividing D by r. Or, she solves the following equation for C: D = C r mod n, or 1189395596986402260 = C 5772156649 mod 4153749073821763621 This can be solved by multiplying D by the inverse of r mod n, and taking the result mod n. You don't need to know the factors of n. As a technical note, there will be only one solution since GCD[D,n] = 1, which is usually true since n only has two factors p and q. The bank is in trouble if GCD[D, n] != 1 since that means n can be factored by the information in D. inv2 = r^(-1) mod n = 5772156649 ^ (-1) mod 4153749073821763621 = 3900656075651054436 -> inv2 = PowerMod[r, -1, n] in Mathematica So, C = (D inv2) mod n = (1189395596986402260 3900656075651054436) mod 4153749073821763621 = 3844350519262422248 -> C = Mod[D inv2, n] in Mathematica Just as a check: C r mod n = = (3844350519262422248 5772156649) mod 4153749073821763621 = 1189395596986402260 = D So we're OK. -> Mod[C r, n] in Mathematica So now Alice has x = 3141526535 and C = 3844350519262422248 4) Alice pays Bob by giving him (x, C) 5) Bob verifies that C = fx ^ (1/5) mod n. Or, he verifies that fx = C^5 mod n C^5 mod n = = 3844350519262422248 ^ 5 mod 4153749073821763621 = 2718281828 which does indeed equal f(3141526535) = 2718281828 where f is our hashing function. So Alice isn't cheating by sending a bogus (x, C) But Bob must also send (x, C) to the bank to verify Alice isn't trying to spend the money more than once! ---------------------------------------- So there it is, with numbers and Mathematica statements for those who have access to Mathematica. Hopefully, the numbers are large enough to convince people it didn't work out by chance. Now, the code to perform the math must be written, as well as the scripts to support the bank. Has anyone used the RSAREF routines, or should we stick to what's supplied with PGP? I haven't thought that far ahead. Like I said earlier, I'll pick up work on this in a few weeks. --- /-----------------------------------\ | Karl L. Barrus | | barrus(a)tree.egr.uh.edu (NeXTMail) | | elee9sf(a)menudo.uh.edu | \-----------------------------------/

1 0

uh oh, o-o
by peter honeyman 03 Dec '92

03 Dec '92

the following remarks were transcribed from today's live satellite broadcast from sun on object oriented technologies, hosted by john gage. in his introductory remarks, he said: I found something else that a number of you probably have read already, it's in a way relevant to this, about searching through large archives. This is John Gilmore, Sun employee number five. [Holding up to the camera last Saturday's NYT article.] This is John in his normal confrontational stance with the National Security Agency. John wanted two textbooks on cryptanalysis that were classified, then declassified briefly, then reclassified. Using good search techniques, using what Bob Kahn would call "knowledge robots" or "knowbots", objects searching for your bibliographic material on the net, John found them in a public library and that made the NSA very upset. For about three days there was a fight, this was in Saturday's New York Times, there was a fight until Tuesday of this week, yesterday, they declassified these books. So using object technology in some rough sense to pore through enormous amounts of information is a topic that may sound futuristic but it's very, very real, we think, and we'll talk about that. enjoy. peter

1 0

digital banking, file formats, etc.
by Karl L. Barrus 03 Dec '92

03 Dec '92

This is a run through of Hal Finney's summary of the bank protocol. Here is what I envision the digital bank working like, with rough sketches of file formats, conspicuously similar to the remailer's :-): 1) Alice chooses x, r Alice computes B = r^3 * f(x) mod n Alice sends the following message to the bank via an anonymous remailer :: withdraw <account name> <B = r^3 * f(x) mod n> Reply-To: <an anonymous remailer> <remailing request to Alice encrypted with appropriate remailer public key> In the final version, this message will be encrypted as well 2) Bank computes D = B^(1/3) checks <account name> for balance, withdraws if ok Bank sends to appropriate remailer :: Encrypted: PGP <remailing request included in Alice's mail> <D> 3) Alice computes C = f(x)^(1/3) by dividing D by r. Alice gives Bob (x, C) - via anonymous mail, presumably :-) 4) Bob wants to verify (x, C) Bob mails to Bank via anonymous remailer :: verify <x> <C> Reply-To: <an anonymous remailer> <remailing request to Bob encrypted with appropriate remailer public key> In the final version, this message will be encrypted as well 5) Bank checks x to see if its been used Bank sends back to remailer :: Encrypted: PGP <remailing request included in Bob's mail> <usage status: used or unused> 6) Bob accepts the "cash" Bob sends to bank via anonymous remailer :: deposit <account name> <x> <C> Reply-To: <an anonymous remailer> <remailing request for Bob encrypted with appropriate remailer public key> 7) Bank checks x, C, account name; if everything OK, deposit Bank replies via anonymous remailer :: Encrypted: PGP <remailing request included in Bob's mail> <message indicating deposit accepted or rejected> Alice and Bob may send message to and receive messages from the bank via anonymous remailers. Or more than one... During the testing/development phase, account names and balances can be made public (available via finger command or something like that) for verification. Account names can be hashes of some user chosen string (Email address plus random text, etc.) Customers must be able to choose: two random numbers x, r compute: f(x) r^3 * f(x) mod n f(x)^(1/3) or C^3 solve: D = C r mod n for C Bank must be able to solve: D^3 mod n for D So, PGP has routines which can generate random number, calculate hashes, and be modified slightly to perform the necessary math. The Bank will be supported by a host of scripts and the math performing PGP routines. Sometime later I will post a run through of the digital bank protocol (all numbers and done with Mathematica) as an example for those who are interested in an example of the protocol. Any input or comments or help will be welcome. Or, if someone else is further along than me, I volunteer! Unfortunately, since the end of the semester draws near, I will be unable to work on this very much for the next few weeks. Besides, I've got to go pick up the O'Reilly and Associates Perl book to move this project along... --- /-----------------------------------\ | Karl L. Barrus | | barrus(a)tree.egr.uh.edu (NeXTMail) | | elee9sf(a)menudo.uh.edu | \-----------------------------------/

1 0

No Subject
by nobody＠rosebud.ee.uh.edu 03 Dec '92

03 Dec '92

This is a test post of a triple-remailed message, all encrypted. Sent at Wed Dec 2 16:17:47 GMT 1992 (Signed) Guess Who?

1 0

Suggest splitting things up
by crunch＠netcom.com 03 Dec '92

03 Dec '92

To Cypherpunks: Greetings, Back on-line again, after wading through about 225 messages that has accumulated in the last 4 days. The volume of messages is really getting high, and perhaps we might want to try and break them up into the following proposed lists. a) PGP Development - a mailing list has already been set up, but is reserved exclusivly for those doing the actual coding work. b) Digital money - A lot of traffic seems to contain this subject, which is all very interesting, but doesn't apply to me because money is something I never seem to have anyway. c) Key management and collaboration - for discussion on various key exchange methodology. Anyway, this is just a thought. And might help to cut down traffic. One also might consider setting up a newsgroup. JD

2 1

Information wanted
by centaur＠netcom.com 02 Dec '92

02 Dec '92

Hello there! I'm interested in getting information on the cypherpunk movement. Could y'all perhaps e-mail me back with your manifesto and suchlike things? Much obliged! Paul --

1 0

Help with the contents of the Cypherpunks Mail Archive
by hugh＠domingo.teracons.com 02 Dec '92

02 Dec '92

As I said I would at the last 'in person' meeting I am starting up a mail archive of usefull things for old and new Cypherpunks. At first we will have a few files that can requested over email, ftp and more complex files sturctures might come later. The most important files that needs to get built are the FAQ (Frequently Asked Questions), the Glossary and the bibliographys. These need to be done keeping in mind who we want to reach, the programmer new to crypto systems and useage. This is a group effort, if you have a good definition of a word send it to me, I will likely use it! If you think you can do a great job of describeing one of the questions from the FAQ in a page or so, whip it out and send it to me! I will compile/edit what ever comes my way into the right place in the archive files. Once we have a good FAQ then when new folks join the list we can send them the FAQ to read and get them up to speed that much faster. This will mean that we will have just repetition on the main list and therefore a better signal to noise ratio! So, go over the list at the end of this email message and see if there is anything you want to tackle, and if there is write some of that English code! ||ugh Daniel Keeper of the archive for now... Propsed contents of the Cypherpunks mail archive. Glossory Bibliography Beginers Anotated Bibliography by Subject FAQ --- A beginers guide to Cypherpunking What is the cypherpunks list all about? Why do I need crypto? What is privacy? What are public keys? What is the differences between DES & RSA? Why can't I just use rot13? Why is generateing random numbers hard? Why do crypto in software insted of hardware? Why is this crypto stuff still legal? What journals are there on this subject? What are the good beginer books on crypto systems? What is the NSA and why does everyone seem to hate them? What is crypto anarchy? Is all I need to crypt my email? What are remailers and DC-Nets? What can I do? Sources Remailer sources Random number generators & testers

2 1