[tahoe-dev] Uniformity of 'semi-private' keys

[David-Sarah Hopwood]

Re:
> [http://allmydata.org/trac/pycryptopp/ticket/13 pycryptopp#13]

Oh, right, this is basically the idea I was asked about at the hacker
party in June 2008 (the one where the whiteboard fell on Meredith).

Shawn Willden wrote:
# The issue I referred to has to do not with the generation of y, but of
# the multiplication of x by y (mod q), and the subsequent use of xy as
# the signing key. The problem is that the distribution of xy mod q
# values is not uniform.

Both DSA and ECDSA work in a prime subgroup, i.e. g generates a
subgroup of prime order q.

For any prime q and any x in [2, q-1], then 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, then 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.


PS. can I have a login on the allmydata Trac?

-- 
David-Sarah Hopwood ⚥