I sent this to <steven@echoync.com> but the address bounced. in any case I thougt I would cc: the list. this is a fun article to read, and I encourage everyone here to check it out. ------- Forwarded Message To: steven@echoync.com Subject: wisecrackers feedback Date: Tue, 27 Feb 96 18:12:02 -0800 From: "Vladimir Z. Nuri" <vznuri@netcom.com> hello, I'm a cypherpunk subscriber. I liked your wired article on the cpunks ("wisecrackers") a lot. I thought I would mention some things: 1. you didn't seem to address the issue that factoring has not been proven to be difficult. a fast factoring algorithm is not ruled out by any existing mathematical theories, although no one expects that one exists. in other words, it is purely mathematician consensus that insists that factoring is a hard problem. hence RSA has not actually been proven to be a secure way of encoding information. its only secure because no one knows how to factor numbers quickly, and everyone is pretty confident that such a capability does not exist, although no one has proven it (yet). RSA rests on the difficulty of undoing a "trapdoor function" and as far as I know, there is no proof that any operation used for cryptography is intrinsically difficult to undo. (there are proofs that some functions are "intrinsically difficult" but they can't be used for crypto, because what you need in crypto is some operation that "is difficult when you don't have secret information, but is easy when you do."-- that is, not "always difficult". that's a trapdoor function, such as that used in RSA-- the secret knowledge makes the operation possible, whereas without it, it is "computationally impossible", i.e. possible in theory but not practice.) in fact there have been very incremental improvements in factoring algorithms. but no one can say, "factoring number [x] takes exactly [y] years" because no one knows what is the optimal factoring algorithm-- they only know the best one that has been *found* to date. (which is the quadratic sieve you mention). the question of whether factoring really is difficult is interesting to study. there is a whole class of computer problems called "NP" that can be shown to be "difficult" in an equivalent way. whether they are truly "difficult" is an open question. surprisingly, factoring has not yet been proven to be in this "NP" class, despite that many other problems have been. also, some mathematicians say that people have been trying to factor numbers since the dawn of time (well, at least since the greeks) so that if there was a good algorithm, we would probably have found it by now. I would argue against this position, saying that computers are a very recent invention on the horizon of human knowledge. the study of algorithmic complexity did not really begin in earnest until the 70's or so, again an extremely recent blip of time in regards to the history of human mathematical thought. 2. I think you were overplaying what Morris said to Zimmermann at the end. it made for good drama but I suspect the truth is more mundane. the fact that he asked "how much would the NSA spend for [x]" (where here [x] is "break PGP keys"). does not imply that they can actually do [x]. rather, what it implies is that their first inclination is to assume that something is theoretically possible, and then determine how much it would cost to do [x]. then, they determine whether the stategic results of obtaining [x] are worth its cost. in other words, the NSA has to approach all cryptoanalysis from this basic point: can we justify the cost based on the stategic value of the intelligence. they have to make this choice all the time as to where they invest their resources based on the payoff. their first question is, "what is the strategic value of cracking [x] code". I believe that they are run internally such that projects that are feasible and that they have the money are not actually carried out just because they are possible-- the strategic value has to be determined. what Morris was asking Zimmerman was, "how much would it be worth to an attacker to be able to read PGP messages". the NSA might well come to the conclusion that nobody important is using PGP and therefore trying to break it to read their messages is a waste of time. my opinion is that what was implied by Morris's position. frankly, I think the threat of prosecution against Zimmermann suggests the NSA may not be able to break the RSA cypher at certain key lengths no matter how much of our tax money they burn trying. 3. a group broke a 384 bit PGP key a little while ago. I was surprised how little coverage this got. perhaps it was due to the choice of keys. some are more "respectable" than others. <g> Paul Leyland and Jim Gillogly (Derek Atkins maybe?) were involved as well as some cpunks. anyway, keep up the good work. (heh. loved the description of the media outlets as "bottom feeders"). bye ------- End of Forwarded Message