Re: How to make money fast (in science fiction)

Rich Weyand skreiv:

> It is generally understood that sooner or later the difficulty of
factoring 
> the products of large primes will be mathematically solved, at which
time the 
> whole RSA encryption mechanism will break down.

It is certainly not "generally understood" (which implies that most 
"understands" this and those who think otherwise are lacking in 
understanding)

There's a perfectly good chance that it'll turn out that factoring large 
numbers is a genuinely hard problem, i.e. that we'll get a mathemathical 
proof for the lower bound on the computation, in which case RSA will 
never be "solved". (though offcourse the largest brute-forcable key 
keeps growing with available computer-power)

> With it will go all of on-line credit card sales, secure websites, 
 > interbank etfs, etcetcetc.

True, sorta. It depends. For example, if factoring large numbers is 
shown practical, but knapsack and elliptical curve problems are 
unaffected it's not a huge deal to switch algorithms. The typical 
web-browser has sup****t for half a dozen cryptosystems already, adding 
one more and deprecating the older unsafe ones would neither be new nor 
revolutionary. (though it would be a scramble and a period of chaos if 
the discovery was sudden and unexpected)

> The timing of this mental breakthrough is necessarily unpredictable.

Sometimes we get clues. People find ways that are -still- unpractical, 
but which are significantly faster than brute-force, which is for 
example currently the case for md5-hashes. (there are practical 
-collisions- for md5, but not practical duplication as far as I know, 
solving: Find a string that md5-hashes to X is still practically 
unsolvable even though Find two strings that are different but hashes to 
the same value, is practical)

These are warning-signs. Everyone with a clue is migrating away from 
md5, but most people don't have any reason to be really panicky about it.

> As an undergrad he invents a new method of encryption that does not
depend on 
> the difficulty of factoring the product of large primes, in which few
people 
> show an interest because the existing method is entrenched.

And because we already have a sprinkling of public-key crypto which is 
independent of the strength of factoring.

> For his PhD thesis, he publishes the seminal paper on a mathematical
method 
> for the fast, automated factoring of the products of large primes. 
Basically, 
> with a PC and a couple minutes you could break the public key of any
encrypted 
> communications, reconstructing the private keys therefrom.  The world is

> facing the complete breakdown of all methods of secure communications.

It's serious. But you're overstating it.

First, this has no influence whatsoever on crypto which does not use 
public-key-crypto. A AES-link using PSK is precisely as secure as it was 
before. Second, you're assuming that all the OTHER public-key 
cryptosystems are ALSO dependent on the complexity of factoring primes, 
which just plain ain't the case.

> He sells the patent on his new method to Microsoft/Visa/Oracle/Whoever
for $10 
> billion in cash and stock.  They think they're getting a hell of a deal
-- and 
> they are -- 

Atleast in those parts of the world that allow patents on pure maths.

I don't think that:

"Hi I've discovered method number 9 of implementing public-key crypto 
without dependance on the complexity of factoring large numbers"

is all that likely to sell to anyone for $10 billion.

Not even if factoring large numbers becomes known to be practical, 
people would be much more likely to simply switch to one of the many 
already known algorithms that don't depend on factoring.


	Eivind Kjørstad