one ecc key-pair for both encryption and signature?
Robert J. Hansen
rjh at sixdemonbag.org
Mon Jan 10 16:07:54 CET 2022
>> Likewise, Edwards DSA can be tortured into becoming a Curve25519 key.
>> But once you do that, *you're no longer using Edwards DSA*.
>
> Can you be more specific why this is a problem?
I apologize in advance for sounding grumpy (I am, it's been an annoying
day so far) and condescending (which I'm trying not to be, but...).
=====
I used to volunteer at my old elementary school. Due to budget cutbacks
they had to eliminate their math program for gifted students, so I came
in once every few weeks to talk to kids who should've been in gifted
mathematics and try to keep their inspiration alive. I loved these
kids: they were the best.
One of my standard questions to them, early on each year, was "are
addition and subtraction the same thing, just looked at differently?"
And that's a great question to ask kids -- heck, even some adults! --
because it forces us to ask what it means to be the same thing.
Ultimately, we start talking about not just what addition and
subtraction do, but what the *nature* of them are. And ultimately we
discover that addition and subtraction are two different things. The
nature of addition is that it's both commutative (A + B) and associative
(A + (B + C) = (A + B) + C). But subtraction is neither commutative nor
associative.
And that means that although each addition problem can be converted into
a subtraction problem, and vice-versa, addition and subtraction are not
the same, not at all. They're not "the same thing just looked at
differently". The existence of a way to make one act like the other
does not mean the same inputs can be used for both.
=====
With me on the elementary-school algorithm theory? Please re-read that
a few times, because I'm about to give *exactly the same lesson* except
now I'm going to make it unnecessarily harder by talking about DSA and
Elgamal keys.
=====
A public key is not just a large prime number. It's an entire
mathematical structure, of which a large prime number (or point on an
elliptic curve, or what-have-you) is only one of many different components.
For a DSA key you have to choose a hash algorithm H, key length L, a
modulus N such that N < L and N <= len(H), an N-bit prime q, an L-bit
prime p such that p-1 is a multiple of q, an integer randomly
distributed among {2, p-2}, and finally, let g be h^((p-1)/q). Once
you've done all of this, write down the triplet (p, q, g): these are
your DSA parameters. Now choose an integer randomly distributed among
{1, q-1} and compute y = g^x modulo p. Your private key is x, your
public key is y.
Now you're saying, "why can't I use the same x and y for Elgamal? I
mean, they're both computing discrete logs over a finite field..."
An Elgamal public key is closely related but different. For Elgamal,
you need a cyclic group G of order q with generator g, an integer x
randomly selected from {1, q-1}, and h = g^x. Your public key is (G, q,
g, h) and your private key is x.
You can see some similarities there. In both algorithms you need to
select some random numbers, and you could view y = g^x modulo p as being
a special case of h = g^x, and if you torture things enough you can
*probably* create a one-to-one mapping between DSA signature keys and
Elgamal encryption keys, what computer scientists call an isomorphism...
... *but that's not going to let you use the same key for both, because
they're different algorithms*.
Or, as I said:
>> Likewise, Edwards DSA can be tortured into becoming a Curve25519 key.
>> But once you do that, *you're no longer using Edwards DSA*.
There is no possible universe in which "your public key is y, and oh,
hey, post these parameters" can be used as "your public key is these
four numbers". The fact one can be converted into the other via some
kind of complex number-theoretic mapping does not mean they can ever be
made directly interchangeable in algorithms that depend on keys having
specific mathematical structures.
(Disclaimers: I'm not a cryptographer. I am at best a cryptographic
engineer. There are other people on this list far better suited than I
to talk about the deeper mathematics of cryptography. Thanks to
Wikipedia for having easily-available terse descriptions of these
algorithms. Standard Wikipedia disclaimers apply: if you need
authoritative descriptions look elsewhere, like the _Handbook of Applied
Cryptography_.)
More information about the Gnupg-users
mailing list