December 2003 - cypherpunks-legacy

Computational Complexity
by mpd＠netcom.com 17 Dec '03

17 Dec '03

Perry E. Metzger writes: > Ahem. He was proposing a mechanism that will work in log(n) > time. All current known methods are subexponential. As you > SHOULD know, a log function will eventually be smaller than > a subexponential one if you only let N grow large enough. > This is baby complexity theory. I find it astonishing that I > should even have to mention it. As I read it, he simply asked (and quite nicely at that) if such a algorithm might exist, and asked if there were any references to it in the literature. Now clearly he was hoping that such a mechanism might offer the opportunity to binary search the key space efficiently and perhaps those hopes were misplaced, but I don't think the idea was so off the wall as to be deserving of the ridicule you heaped upon it. Far weirder things have been proposed on this list. > Thats not what he was proposing. Obviously one can build > such an algorithm given a factoring algorithm, and we know > of exponential factoring algorithms. That wasn't the idea. > His notion was that there might be a CHEAP algorithm to do > this. I think the key word here is "might." Hope springs eternal, even in cryptology. :) -- Mike Duvos $ PGP 2.6 Public Key available $ mpd(a)netcom.com $ via Finger. $

1 0

Some observations on xMODn...
by Jim choate 17 Dec '03

17 Dec '03

I propose to clarify with a little mathematics as best I can what I was, and am, asking... To those this material appears obvious too please feel free to delete. As I understand it MOD is a function which returns the remainder of a number (x) when divided by another number (n). As an example: 5mod3=2 ie 3 will go into 5 a single time and there will be a left over of 2. 11mod3=2 ie 3 will go into 11 a total of 3 times and there will be 2 left over. I propose there is a periodicity in the mod function: n 0 1 2 3 4 5 6 7 8 9 10 11 12 nmod5 0 1 2 3 4 0 1 2 3 4 0 1 2 this can be simplified into a generic formula for a sequence: rem = (kn)+i |big # |big # | | |i=0 |k=0 What this formual does is give you the sequence of any given remainder for xmodn. In a generic algorithm it appears as such: n = some number for k = 0 to "some really big number" for i = 0 to "some really big number" rem=(k*n)+i next i next k >From p.282 on Schneier the RSA encryption algorithm is given as: e c = m (mod n) i i In my notation this reduces to: rem = (kn)+i | | | | | n=0 |i=0 What I am asking is that since the numbers we are looking at are very large there should (to the way I am thinking at the moment) some means of detecting a sequence of patterns of periodicity related to the difference between the actual key and the key we just select randomly. Specificaly what I am asking for is some reference to some work in this area. I don't know what it is called, it doesn't appear in any books that I have looked at. Thanks for any help you may be able to provide...

1 0

Re: Perry vs. the Math Teacher
by Jeff Gostin 17 Dec '03

17 Dec '03

perry(a)imsi.com (Perry E. Metzger) writes: > the result applicable to factoring, I feel rather sad. Its depressing > commentary on what cypherpunks has become. Go figger. It's become a haven of learning, where the more learned teach those willing to learn, instead of the self-congratulatory elitist squad I was told it once was. That's why *I'm* here, to learn from those who know more than I do. I am VERY willing to learn what others have to teach. They know more than I do, and there's some very knowledgeable people here. I've recieved some very nice replies to my earlier question about what O(f(x)) meant, including one from you, Mike McNally, Bill O'Hanlon, and Douglas Sinclair (thanx guys!! If anyone else sent anything, I haven't recieved it yet, but you do have my thanx, in advance!). This only proves that there are people who are only too willing to teach if someone shows they are willing to listen, and learn. The moral of the story is this: Someone had to teach you at one time, didn't they Perry? One is well-advised to remember, and be humbled by, the fact that they weren't born knowing everything. Flames in e-mail, please. Constructive replies always welcome. --Jeff -- +------------------------------------+---------------------------------------+ | Jeff Gostin jgostin(a)eternal.pha.pa.us | +------------------------------------+---------------------------------------+ | "The risk... is that our vision is too small, our dreams not large enough" | | -Jim Seymour | +------------------------------------+---------------------------------------+

5 4

Re: Crypto export legislation defeated in House Intelligence Cmte.
by Bill Frezza 17 Dec '03

17 Dec '03

On 6/17 John said: <If you have any ideas on just how to do this, I'd sure be interested. We've been talking to all the involved people, from NSA "special assistant to the director" to the White House to the Justice Dept to the Intelligence Committee staff to the senators and representatives who are fighting this battle. If they have something that they won't tell us, claiming the info is classified, what do you recommend that we do to change their minds?> I recommend that we give up the battle and go fight the real war. We are totally outgunned if we stick to this approach and are wasting our time. What the entire net community should do is focus it's energies on chopping NSA's budget, period. That's what these guys really care about after all. Let's go on the offense rather than play a losing defense. Make them squirm in appropriation committee hearings, embarrass them for their intelligence failures, and put them on notice that we are going to hit back where it hurts. And don't even bother raising the "freedom of encryption" or free trade issues. Forget it. It's going to happen anyway and they can't stop it. Focus on defecit reduction and downsizing the intelligence community in the wake of the collapse of the Soviet Union. Keep the attack very broad and avoid specific "national security" issues. Get the investigative journalists to write exposes on the huge spending black hole these guys have created. Whine about all the other worthy things taxpayer money can be spent on <gag> if we stop giving it to spooks and weirdos. Of course, this strategy may be tough for the EFF if you are simultaneously urging increased government involvement in the "Information Superhighway". Regards, Bill Frezza DigitaLiberty

1 0

Bumper Sticker
by nobody＠shell.portal.com 17 Dec '03

17 Dec '03

I saw a bumper sticker: I love my country but fear my government. Rat

1 0

Re: Crypto export legislation defeated in House Intelligence Cmte.
by gtoal＠an-teallach.com 17 Dec '03

17 Dec '03

: I recommend that we give up the battle and go fight the real war. We are : totally outgunned if we stick to this approach and are wasting our time. : What the entire net community should do is focus it's energies on chopping : NSA's budget, period. That's what these guys really care about after all. There was quite an interesting quotation in one of the British papers recently from Ames, the CIA spy who was caught - he said that the intelligence infrastructure in the US was a self-serving bureaucracy. I forget the exact wording, but it was the sort of thing you'd imagine the head of any big organisation like that would want to say but was never in a position to be able to - of course, now Ames can say what he likes :-) I wonder if he's available for interviews by the Cypherpunk Press ;-) G

2 1

Notes on xmodn...
by Jim choate 17 Dec '03

17 Dec '03

n 0 1 2 3 4 5 6 7 8 9 10 nmod5 0 1 2 3 4 0 1 2 3 4 0 mult5 0 0 0 0 0 1 1 1 1 1 2 mod3 0 1 2 0 1 2 0 1 2 0 1 mult3 0 0 0 1 1 1 2 2 2 3 3 mod3mod5 0 1 2 0 1 2 0 1 2 0 1 mult 3/5 0 0 0 0 0 0 0 0 0 0 0 mod5mod3 0 1 2 0 1 0 1 2 0 1 0 mult 5/3 0 0 0 1 1 0 0 0 0 1 0 I am interested in the behaviour of the modamodb and mult a/b. I have been unable to find any kind of work along this line...

1 0

(None)
by Jeff Gostin 17 Dec '03

17 Dec '03

Dave Otto <dave(a)marvin.jta.edd.ca.gov> writes: > ! While they are aware that software for secure encryption is > ! available from non-US, they are making a best effort to prevent > ! a standard from emerging, while hoping that some escrowed > ! encryption scheme will gain acceptance. This is a critically dangerous statement of intent. What we are seeing here the the US government running scared when they consider the fact that they won't be able to pry into our lives without asking permission (IE: for our keys) first. Now it all makes sense. If ever they've sealed their own fate, now is the most damnable time. If only they realized how zealously we will guard our encryption rights before saying something so incriminating, perhaps they would have come up with a better excuse. I don't get active in many things, but, alas, my time of complacency is over. If the pen is mightier than the sword, perhaps a Bic will level Congress. --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

Let us attack Clipper
by Ben.Goren＠asu.edu 17 Dec '03

17 Dec '03

No, not with words, as we're all so fond of doing. Instead, I suggest that the NSA or others provide free access to an EES system on the 'net, for any and all to attempt attacks. They could hook up a workstation or two with a couple Tessera cards, and provide anonymous login access. All functions should be permitted as they will be in a final implementation. This is an inexpensive way that EES advocates can permit access to the system for analysis. It would be only for research purposes--there'd be no way to encrypt a phone conversation, and anybody would have to be stupid to encrypt sensitive data with an NSA-owned machine, even assuming you could get the data to the computer securely in the first place. To the NSA agent who is surely subscribed: if Clipper is so great, prove it. If you won't disclose the Skipjack algorithm (but why not if it's secure?), at least provide access to test its implementation. b& -- Ben.Goren(a)asu.edu, Arizona State University School of Music net.proselytizing (write for info): Protect your privacy; oppose Clipper. Voice concern over proposed Internet pricing schemes. Stamp out spamming. Finger ben(a)tux.music.asu.edu for PGP 2.3a public key.

2 1

Another Cellular Victim
by Duncan Frissell 17 Dec '03

17 Dec '03

I'm watching (presumably) OJ being persued live on CNN. They report that he was tracked via his cellphone use. What this country needs is a good anonymous cellphone net. DCF "When entrenching tools are outlawed, only outlaws will have entrenching tools." --- WinQwk 2.0b#1165

2 1