[tahoe-dev] [pycryptopp] #13: [EC]DSA "semi-private"/intermediate keys (was: DSA "semi-private"/intermediate keys)

pycryptopp trac at allmydata.org
Sat Jan 9 04:48:58 UTC 2010

#13: [EC]DSA "semi-private"/intermediate keys
Reporter:  warner       |           Owner:       
    Type:  enhancement  |          Status:  new  
Priority:  major        |         Version:  0.5.1
Keywords:               |   Launchpad_bug:       

Comment(by davidsarah):

 Replying to [comment:3 swillden]:
 > My concern is that {{{x*y mod q}}} is not uniformly distributed, even if
 x and y are uniformly distributed.

 This was discussed in [http://allmydata.org/pipermail/tahoe-
 dev/2009-May/001798.html on tahoe-dev] but should be recorded here:

 ECDSA can work on elliptic curves over either GF(p) or GF(2^m^) [or
 GF(p^m^) but I don't think that's a standardised option]. When the curve
 is over GF(p), ECDSA is specified to use a prime subgroup, say of order q.
 Ordinary DSA also uses a prime subgroup of order q.

 For any prime q and any x in [2, q-1], the function that maps y to xy mod
 q, for y in [1, q-1], is a permutation. Therefore, except for the special
 cases of x = 1 or y = 1 which should have negligable probability,
 multiplying by a random [EC]DSA private key should yield another random
 [EC]DSA private key. So there should be no problem with the uniformity of
 private keys in this scheme, ''provided'' that only curves over GF(p) are
 used in the case of ECDSA.

 Note that this only addresses the specific concern that Shawn had; public
 key crypto is difficult to analyse and there could be other attacks.

Ticket URL: <http://allmydata.org/trac/pycryptopp/ticket/13#comment:4>
pycryptopp <http://allmydata.org/trac/pycryptopp>
Python bindings for the Crypto++ library

More information about the tahoe-dev mailing list