[626] in cryptography@c2.net mail archive
Re: RPK?
daemon@ATHENA.MIT.EDU (Hal Finney)
Tue Apr 22 15:03:11 1997
Date: Tue, 22 Apr 1997 09:54:07 -0700
From: Hal Finney <hal@rain.org>
To: cryptography@c2.net
I had the impression from what I have read on elliptic curves that the
reason (or a reason?) they are so fast is because there is no equivalent
to the fast factor-base discrete log attack which applies to fields
based on prime integers. So the difficulty of breaking the logarithms
is exponential in the bit length, and hence sizes in the 100-200 bit
range are practical. Is this right?
Apparently that does not apply to RPK. Even though it is based on a
different field, of order 2^n, according to their web page there are
efficient attacks on discrete logs which sound similar to those in prime
fields. So sizes must be similar to RSA moduli, 500-1000 bits at least.
I don't know what the speed of arithmetic in a field of size, say,
2^512 would be compared to in one with a size which is a 512 bit prime.
It looks like RPK has some speedups using tables.
As far as Diffie-Hellman signatures, that term when used strictly refers
to the key exchange algorithm and not to encryption or signatures.
However as Colin says it might be used loosely to refer to the whole
class of discrete log cryptosystems, in which there are a lot of signature
algorithms.
I have seen a blinded form of at least the Schnorr signature algorithm.
I have a reference which suggests that it is used in Chaum and Pederson,
"Wallet databases with observers," Crypto 92. The basic idea is that
the signature is generated cooperatively between the signer and the
person who will end up with it, and two blinding factors are used such
that the non-signer can mathematically transform the values from the
signer so that he still preserves the verification relationship. I
have a one-page writeup on it which I will include below.
I don't think this trick works for all discrete log signatures. I have
never seen a blinded form of the DSS, for example, and I wasn't able
to come up with one. Whether it is possible depends on the details of
the mathematical relationships in a given signature.
Hal
=====
Schnorr signature (variable names from Schneier where applicable):
Keying:
Signer has public parameters prime p, with generator "a" of subgroup
of order q (where q divides p-1). Secret key is exponent s, public
key is v = a^(-s) mod p.
Signing message m:
1. Signer chooses random r < q, computes x = a^r mod p.
2. Signer computes e = hash(m, x)
3. Signer computes y = r + s*e mod q. Signature is (e, y).
4. Verifier computes x' = a^y * v^e. (x' should be equal to x above).
Confirms that e = hash(m, x').
Schnorr cooperative signature:
In this algorithm, Signer never sees message m. He cooperates with the
Verifier to produce a valid signature on m. However it is still not a
fully blind signature.
1. Signer chooses random r < q, computes x = a^r mod p, sends x to Verifier.
2. Verifier computes e = hash(m, x), sends to Signer.
3. Signer computes y = r + s*e mod q, sends signature (e, y) to Verifier.
4. Verifier confirms that x = a^y * v^e. If so (e, y) is a good Schnorr
signature.
This is not fully blinded because Signer sees e and y although he did not see
m.
Schnorr blind signature (the primed variables are only seen by Verifier):
1. Signer chooses random r < q, computes x = a^r mod p, sends x to Verifier.
2a. Verifier chooses two random blinding factors i and j, computes
x' = x^i * a^j.
2b. Verifier computes e' = hash(m', x') and e = e'/i mod q, sends e to Signer.
3. Signer computes y = r + s*e mod q, sends (e, y) to Verifier.
4a. Verifier confirms that x = a^y * v^e, so Signer did his part right.
4b. Verifier computes y' = i*y + j mod q.
4c. Now (e', y') is a Schnorr signature on m', as can be verified by:
x'' = a^y' * v^e'
= a^(i*y + j) * v^(e*i)
= (a^y)^i * a^j * (v^e)^i
= (a^y * v^e)^i * a^j
= x^i * a^j
= x'
and therefore e' = hash(m', x') = hash (m', x'')
and the signature is confirmed.
This is a fully blind signature; e', y' and m' are unlinkable by the
signer to the values he saw, e and y.
