Quote:


orolan wrote on Apr 1^st, 2003 at 8:58pm:


No orolan.  Not better.  I know it's off the subject completely, but the RSA encryption algorithm is a bit of long lasting technology that has not been cracked.  It is, however, based on the belief that P != NP (i.e., the set of problems solvable in deterministic Polynomial time is not equal to the set of problems solvable in Nondeterministic Polynomial time).  The statement P != NP is based on belief, and not on fact.  It has not been proven that there is no efficient algorithm for factoring large positive integers.  It has also not been proven that there does exist such an algorithm.  Thus, the belief that RSA encryption (as used by PGP and others) is absolutely safe is a dangerous one at best.  A good general reference on the matter is "Computers and Intractibility" by Garey and Johnson.

This is just to demonstrate that some technologies exist that people put an unfounded amount of faith in other than just the polygraph.  These technologies can still be valuable and useful to the people who use them.  The art of making gross generalizations on subjects where the artist has a lack of expertise should be left to the politicians, in my humble opinion.

By the way, I have found this site and this subject in general very interesting and informative.  I personally find lie detector tests an affront to my right to privacy.  Thanks George.

orolan wrote on Jun 3^rd, 2003 at 12:44am:


No, RSA PKC has not been "cracked" though increasingly larger but still small key sizes have been broken by bruteforce keyspace searches. What is remarkable is the advance in pure hardware power and configurable hardware. Us techie types tend to fixate on key length and such but that isn't where the threat is. The threat, my friend, is from mundane things, typically money oriented. For example, I had some unknown person clone one of my credit cards (a cottage industry it seems) and a fake card (and probably ID) was generated. All these folks had to do was swipe the magnetic stripe and email the bitstream to their buds in Australia. The next day they hit up all the Jewelry stores in the QVC Mall.  BTW, they didn't even need a PIN to do that. This country badly needs ways to authenticate identity and I really don't understand why that is such an anathema.

As for the NSA, I don't much care whether they have cracked RSA or not. My guess is they they don't worry too much about it. There are far simpler ways for them to do their job. 

-Marty

Fair enough.  Yes, cracking 128 bit encryption requires far more computing power than 64 bit, and if I were going to use a public-private key encryption system, I would certainly choose the highest number of bits possible, but the main point is that if someone develops an efficient factorization algorithm (say O(lg n) where n is the number being factored) then the number of bits used is irrelevant.  Actually, the beauty of RSA (and similar public-private key schemes) is not that they are hard to crack conceptually, but rather that doing so requires a prohibitive amount of computing power per instance.  Why does it take so much computing power?  Only because no one has yet publicly proven that P = NP, and it's a very widely held BELIEF that P != NP.  The person that can prove it either way gets at least 1 miliion dollars (offered by the Clay Mathematics Institute -- see http://www.claymath.org/Millennium_Prize_Problems and look for P vs NP) though the solution would potentially be worth billions to the private sector since it impacts all of the physical sciences -- reading encrypted e-mail is the least interesting application in my opinion.

If memory serves (and it generally doesn't anymore) a grad student in California cracked an instance of 40-bit encryption in ~4 days back in the late 90's.  I'll take your word that a 64-bit instance was cracked in ~4 years with a bunch of computers (probably a distributed environment running a variation of the quadratic sieve factorizer -- see http://mathworld.wolfram.com/QuadraticSieve.html for a detailed explanation) but as you also point out, the NSA may very well have a factorizer in hand that works in P time (O(n^x), x some constant, n = the number of digits or bits in the number) that is capable of breaking any public-private key encryption system, and simply has kept the public ignorant of the fact.  The main point is that we don't know simply because the possible existence of such a thing can not be proven or disproven.  There are actually a lot of similarities between polygraphs and many number-theoretical assertions, algorithms, and open problems.

At any rate, some technological innovations can be considered nothing more than tools that have some inherent value to the people that use them (like polygraphs for polygraphers and number theoretical conjectures for encryption algorithm designers), even if the actual value is not necessarily as great as what most people believe it to be.  That's really the extent of the point I was trying to make.  Well, that, and one of my pet peaves happens to be gross generalizations like "In today's world no technology is safe for more than a few months.".  The encryption algorithms that rely on a NP-Complete problem have been safe since their inception because of their very nature.

On the subject of PGP encryption, note that AntiPolygraph.org uses it. Our PGP public key is included on our contact page.

Marty wrote on Jun 3^rd, 2003 at 7:46am:


When I interviewed at NSA for an analyst position (man, I really would have liked working there), I had a very interesting conversation regarding encryption.  Suffice it to say that I'm convinced there are serious limits to what that organization can do, as well as impressive capabilities.  They have a tough mission.

My exposure to encryption has been limited to a good book by Schneier (Applied Cryptography).  But even I know that you want to use a bona-fide one-way hash for digest purposes

Skeptic

Don't kid yourself guys, there is no such thing as privacy.