[openssl-users] Testing OpenSSL based solution

[Dave Thompson]

> From: openssl-users On Behalf Of Marcus Vinicius do Nascimento
> Sent: Tuesday, May 12, 2015 16:50

> I did some quick research and found this:
http://en.wikipedia.org/wiki/Digital_Signature_Algorithm
> If my understanding is correct, the public key is (p, q, g, y).

You might want to look at the actual standard, FIPS 186, free from NIST 
and referred to by wikipedia as well as easily searchable. The current 
version is revision -4, but the basic logic of DSA hasn't changed since 
"-0" (although the sizes used have increased).

Standardly a DSA public key is (parameters, y) where parameters is 
(p, q, g {, seed, counter}) where the optional fields in the parameters 
allow verification of the parameter generation process. OpenSSL does 
not use that option, so it uses only p,g,q and y. See below.

> The private key would be x, such that y = g^x mod p.
> Is there some way to generate both public and private keys using OpenSSL, 
> based on p, q, g and y?

You cannot recover the private key from the public key for any 
secure PKC scheme used with appropriate sizes. DSA is a secure 
scheme, and DSS and these test cases use appropriate sizes.

> De: openssl-users Em nome de Marcus Vinicius do Nascimento
> Enviada em: terça-feira, 12 de maio de 2015 17:06

> I tried using Y as the public key, but ssl seems not to accept that.
> From the FIP file: <snip>
> So I tried reformatting Y to pass it to PEM_read_bio_DSAPrivateKey.
> Converting Y to Base64 = <snip> 
> Reformatting in PEM format = "-----BEGIN DSA PRIVATE KEY----- <snip>
[doesn't work]

As above, the public key requires all of p,q,g and y, not just y. 
The private key would require x as well, and you don't have x.

For public keys for _all_ algorithms in files including PEM 
OpenSSL uses the format standardized by X.509 called 
SubjectPublicKeyInfo or SPKI for short, which is an ASN.1 
sequence containing an AlgorithmIdentifier which is a(nother) 
sequence containing an OID identifying the algorithm and an 
optional parameters field whose type depends on the algorithm,
followed by a BITSTRING containing a nested encoding of the 
public key value relative to the parameters for that algorithm.

For DSA, the OID identifies DSA, the parameters are a sequence 
of three INTEGERs for p,g,q, and the nested key encoding is 
just an INTEGER. All elements in ASN.1 use a "TLV" (tag, length,
value) encoding, and INTEGER (thus) consists of a tag octet of 02 
specifying integer, a length whose length itself varies depending 
on the length it encodes, and a value field which for INTEGER is 
a _signed_ big-endian binary number. Since the particular y
you tried to encode below happens to have a magnitude size of 
1024 bits, a multiple of 8, it requires a leading sign octet of 00.
So does g in this case, and p and q by design (they are specified with 
magnitude sizes which are multiples of 8, and indeed of 32).

See rfc 5280 for the generic SPKI format, and rfc 3279 (referenced there) 
for the specifics for several algorithms including DSA.

Note that the PEM type is just "BEGIN/END PUBLIC KEY"  (no DSA) 
because as above the format handles all algorithms.