Private Key Generation from Passwords/phrases

Matthias Bruestle mbruestle at
Tue Jan 9 10:45:46 EST 2007


I am thinking about this since last night. On the web I haven't found
much and I want to go in a different direction as I have found.

Say I want to have 112bit security, i.e. as secure as 3DES. For this I
would choose (as everybody writes) 224bit ECC (or Tipsy Curve
Cryptosystem/TCC as I prefer, because the European Citizen Card is also
called ECC officially). With the Passwords I would have to provide so
much entropy, that a bruteforce attack needs as much time as 3DES to get
the same security. (Higher value of ECC key ignored.)

When I look at benchmarks ratio of the number of 3DES operations and of
point multiplications is about 4000:1, so I have gained here about 2^12
bits. (Processing of Password with a hash function is so fast that it
can be ignored unless the procession is artificially extended.) I am
aware that a DES unit is cheaper than an ECC unit and that for DES there
are special implementations for key search possible, so the gain might
be even more.

Lets assume the key is only very seldom regenerated. Then we could add a
short fragment of real entropy to the passwords and throw it away after
our first key generation. If a point multiplication takes around 4ms
then we can brute force on one day 2^24 keys. So if the user is willing
to wait for one day for his key recreation than he can add 3 random
bytes to his passwords and throw them away.

If we add this together, than we have already 2^36 bits of security from
our goal of 2^112 bits. The remaining necessary entropy is then 2^76
bits which would have then to be provided by the passwords/phrase. That
means the necessary length is reduced by about one third.

What do you think about this?


Matthias Bruestle, Managing Director
Phone +49 (0) 91 19 55 14 91, Fax +49 (0) 91 19 55 14 97
MaskTech GmbH, Nordostpark 16, 90411 Nuernberg, Germany

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list