# ASN.1 integer question for DSA

I'm trying to implement own DSA signature check as per guide at this site page 20 in python.

kp = 0x8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec0736ee31c80291
kq = 0xc773218c737ec8ee993b4f2ded30f48edace915f
kg = 0x626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802
ky = 0x19131871d75b1612a819f29d78d1b0d7346f7aa77bb62a859bfd6c5675da9d212d3a36ef1672ef660b8c7c255cc0ec74858fba33f44c06699630a76b030ee333

sh = 0xa9993e364706816aba3e25717850c26c9cd0d89d
sr = 0x8bac1ab66410435cb7181f95b16ab97c92b341c0
ss = 0x41e2345f1f56df2458f426d155b4ba2db6dcd8c8

w = pow(ss, -1, kq)
u1 = (sh * w ) % kq
u2 = (sr * w ) % kq
v = ((pow(kg, u1, kp) * pow(ky, u2, kp)) % kp) % kq
print("v", hex(v), v)

print("signature is (r = v):", sr == v)


it gives true and works as expected. then knowing private key, I've decided to export key to OpenSSL with

key = DSA.construct((ky, kg, kp, kq, kx))
print(key.exportKey())


and then got public key, generated certificate and signed "abc" from example and verification in OpenSSL is also valid. I've also used openssl asn1parse in attempt to get r and s from new signature.

929:d=5 hl=2 l= 9 cons: SEQUENCE
931:d=6 hl=2 l= 7 prim: OBJECT :dsaWithSHA1 940:d=5 hl=2 l= 46 prim: OCTET STRING [HEX DUMP]:302C02140977C4B483B4C9E9620BA2679EBB7A03D020FB3B02143E6E3616A1034D4D24E387A5FDC5FB77DD8362A4

I've tried to use 0x0977C4B483B4C9E9620BA2679EBB7A03D020FB3B as r and 0x3E6E3616A1034D4D24E387A5FDC5FB77DD8362A4 as s and it doesn't work. What should be done to get r and s from this octet string?

UPDATE 1: what is NOT working

kp = 0x8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec0736ee31c80291
kq = 0xc773218c737ec8ee993b4f2ded30f48edace915f
kg = 0x626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802
ky = 0x19131871d75b1612a819f29d78d1b0d7346f7aa77bb62a859bfd6c5675da9d212d3a36ef1672ef660b8c7c255cc0ec74858fba33f44c06699630a76b030ee333

sh = 0xa9993e364706816aba3e25717850c26c9cd0d89d
sr = 0x0977C4B483B4C9E9620BA2679EBB7A03D020FB3B
ss = 0x3E6E3616A1034D4D24E387A5FDC5FB77DD8362A4

w = pow(ss, -1, kq)
u1 = ( sh * w ) % kq
u2 = ( sr * w ) % kq
v = ((pow(kg, u1, kp) * pow(ky, u2, kp)) % kp) % kq
print("v", hex(v), v)

print("signature is (r = v):", sr == v)


I've checked sha1 digest in signature and it is the same

  662:d=5  hl=4 l= 263 cons:      cont [ 0 ]
666:d=6  hl=2 l=  24 cons:       SEQUENCE
668:d=7  hl=2 l=   9 prim:        OBJECT            :contentType
679:d=7  hl=2 l=  11 cons:        SET
681:d=8  hl=2 l=   9 prim:         OBJECT            :pkcs7-data
692:d=6  hl=2 l=  28 cons:       SEQUENCE
694:d=7  hl=2 l=   9 prim:        OBJECT            :signingTime
705:d=7  hl=2 l=  15 cons:        SET
707:d=8  hl=2 l=  13 prim:         UTCTIME           :220606200747Z
722:d=6  hl=2 l=  35 cons:       SEQUENCE
724:d=7  hl=2 l=   9 prim:        OBJECT            :messageDigest
735:d=7  hl=2 l=  22 cons:        SET
737:d=8  hl=2 l=  20 prim:         OCTET STRING      [HEX DUMP]:A9993E364706816ABA3E25717850C26C9CD0D89D
...
929:d=5  hl=2 l=   9 cons:      SEQUENCE
931:d=6  hl=2 l=   7 prim:       OBJECT            :dsaWithSHA1
940:d=5  hl=2 l=  46 prim:      OCTET STRING      [HEX DUMP]:302C02140977C4B483B4C9E9620BA2679EBB7A03D020FB3B02143E6E3616A1034D4D24E387A5FDC5FB77DD8362A4


Key seems to be the same as well

    0:d=0  hl=3 l= 240 cons: SEQUENCE
3:d=1  hl=3 l= 168 cons:  SEQUENCE
6:d=2  hl=2 l=   7 prim:   OBJECT            :dsaEncryption
15:d=2  hl=3 l= 156 cons:   SEQUENCE
18:d=3  hl=2 l=  65 prim:    INTEGER           :8DF2A494492276AA3D25759BB06869CBEAC0D83AFB8D0CF7CBB8324F0D7882E5D0762FC5B7210EAFC2E9ADAC32AB7AAC49693DFBF83724C2EC0736EE31C80291
85:d=3  hl=2 l=  21 prim:    INTEGER           :C773218C737EC8EE993B4F2DED30F48EDACE915F
108:d=3  hl=2 l=  64 prim:    INTEGER           :626D027839EA0A13413163A55B4CB500299D5522956CEFCB3BFF10F399CE2C2E71CB9DE5FA24BABF58E5B79521925C9CC42E9F6F464B088CC572AF53E6D78802
174:d=1  hl=2 l=  67 prim:  BIT STRING
0000 - 00 02 40 19 13 18 71 d7-5b 16 12 a8 19 f2 9d 78   [email protected].[......x
0010 - d1 b0 d7 34 6f 7a a7 7b-b6 2a 85 9b fd 6c 56 75   ...4oz.{.*...lVu
0020 - da 9d 21 2d 3a 36 ef 16-72 ef 66 0b 8c 7c 25 5c   ..!-:6..r.f..|%\
0030 - c0 ec 74 85 8f ba 33 f4-4c 06 69 96 30 a7 6b 03   ..t...3.L.i.0.k.
0040 - 0e e3 33


and private as well

    0:d=0  hl=3 l= 198 cons: SEQUENCE
3:d=1  hl=2 l=   1 prim:  INTEGER           :00
6:d=1  hl=3 l= 168 cons:  SEQUENCE
9:d=2  hl=2 l=   7 prim:   OBJECT            :dsaEncryption
18:d=2  hl=3 l= 156 cons:   SEQUENCE
21:d=3  hl=2 l=  65 prim:    INTEGER           :8DF2A494492276AA3D25759BB06869CBEAC0D83AFB8D0CF7CBB8324F0D7882E5D0762FC5B7210EAFC2E9ADAC32AB7AAC49693DFBF83724C2EC0736EE31C80291
88:d=3  hl=2 l=  21 prim:    INTEGER           :C773218C737EC8EE993B4F2DED30F48EDACE915F
111:d=3  hl=2 l=  64 prim:    INTEGER           :626D027839EA0A13413163A55B4CB500299D5522956CEFCB3BFF10F399CE2C2E71CB9DE5FA24BABF58E5B79521925C9CC42E9F6F464B088CC572AF53E6D78802
177:d=1  hl=2 l=  22 prim:  OCTET STRING      [HEX DUMP]:02142070B3223DBA372FDE1C0FFC7B2E3B498B260614

• An online ASN.1 decoder confirms you got the decoding right. One possibility is that your sh is not the same as OpenSSL's. It's surprisingly hard to get OpenSSL to DSA-sign 3 bytes after hashing them with SHA-1 exactly once! Another possibility is that somehow OpenSSL does not use the same key as you do.
– fgrieu
Commented Jun 8, 2022 at 9:23
• To me "and it doesn't work" doesn't really cover the error... What exactly are you trying to do and how? Commented Jun 8, 2022 at 17:10
• The key is consistent: $p$ is prime, $q$ is prime, $p\bmod q=1$, $g^q\bmod p=1$, $g^x\bmod p=y$. The hash is the SHA-1 of abc in ASCII. The issue could be that what's signed is not abc in ASCII, but a larger data block including the SHA-1 of abc in ASCII, the signing time, and possibly other stuff. How exactly was that signature obtained?
– fgrieu
Commented Jun 8, 2022 at 19:58
• I've performed following sequence after export of the key to dsa-priv.key: first I've got a public key openssl dsa -in dsa-priv.key -outform der -pubout -out dsa-pub.key then I've generated a cert file: openssl req -new -x509 -key dsa-priv.key -out dsacert.pem then I've signed a sample.dat with abc inside using private key and certfile openssl smime -sign -in ../sample.dat -out sample.test -signer dsacert.pem -inkey dsa-priv.key -outform pem. Yes, I have impression signing time somehow considered. Commented Jun 8, 2022 at 21:01
• (@fgrieu) Yes openssl smime -sign -outform pem does CMS/PKCS7 SignedData which by default computes the signature over signedAttributes which includes the data digest, contentType, signingTime, and (sometimes? mostly-useless) smimeCapabilities (and re-encoded without the implicit tagging used in the message). Use -noattr to get a signature over only the data. Compare crypto.stackexchange.com/questions/87009/… . Commented Jun 8, 2022 at 23:58

• $$(p,q,g)$$ = (0x8df2…0291, 0xc773…915f, 0x626d…8802) are a consistent set of DSA-1024 parameters: $$\|p\|=1024\,$$, $$\|q\|=160\,$$, $$p$$ and $$q$$ are prime, $$p\bmod q=1\,$$, $$1, $$g^q\bmod p=1\,$$.
• $$y$$ = 0x1913…e333 is a consistent public key value for these parameters: $$1, $$y^q\bmod p=1$$.
• $$y$$ is consistent with the private key value $$x$$ = 0x2070…0614 : $$g^x\bmod p=y\,$$.
• $$h$$ = 0xa999…d89d is the SHA-1 hash of the 3-byte bytestring coding the three characters abc per UTF-8 (or ASCII extended to 8 bits by adding a high-order bit at zero, or any of the many 8-bit character sets compatible with ASCII).
• $$(r,s)$$ = (0x0977…FB3B,0x3E6E…62A4) is the pair of ASN.1-decorated integers in the bytestring 302C02140977…62A4 and is consistent with being a DSA signature per the above parameters: $$0 and $$0.
• except for lacking the range check for $$r$$ and $$s$$, the python code for the signature verification is correct.
The reason why the signature $$(r,s)$$ does not check is that it's not a signature of the 3-byte bytestring coding the three characters abc per UTF-8, but of a more complex message, including the signingTime field. See dave_thompson_085's comment which explains why, and suggests a modifier that may help towards the difficult goal of controlling what OpenSSL actually signs.