>> You understand that in principle, it is *always* possible to compute the
>> private key from the public one, right? It is impossible to prevent
>> this. All you can do is make it ludicrously expensive to do it.
>
> It is always possible to *find by exhaustive exploration* of the key
> space a private key that would match a public key. But that is not
> computation.

No, that's computation. Given an input, it produces a correct output by 
a deterministic procedure. That's more or less the definition of a 
computable function.

For most algorithms, you can do something faster than that. For example, 
for RSA, you just need to factorise a very large composite number. There 
are algorithms for doing this much faster than an exhaustive search of 
all possible bit patterns. (Although still in the same complexity class.)

It is always /possible/, and often it's less expensive than it 
theoretically could be. The important point is for it to be too 
expensive to be practical.

(The definition of "practical" varies depending on how valuable whatever 
the key protects actually is, of course...)

> DES was used as an illustration. Moreover, the 3*56 bits of 3DES have a
> lower entropy (so, 3*56 bits is *not* 168, at least in cryptography) due
> to issue in the model.

How do you work that one out?

> I agree that there is better than 3DES, but it is one of the few
> algorithms required (and then accepted) everywhere which also can have
> dedicated hardware.

AES is widely supported (though perhaps not quite as widely as DES), and 
I'm sure there are plenty of hardware implementations.

Post a reply to this message