#!/usr/bin/env python3
import math, random, hashlib

# variable names as in FIPS 186-3
def test(p, q, g, msg, x, y, k, r_must_be, s_must_be, hash_ptr):
    L=math.ceil(math.log(p, 2))
    N=math.ceil(math.log(q, 2))
    print ("L, N", L, N)

    # p and q - prime numbers
    # $g=h^{(p-1)/q} \pmod p$, where h is any number and 1<h<p-1
    # (g has order q mod p)

    # $p-1$ must be divisible by $q$
    assert divmod(p-1, q)[1]==0

    assert x<q
    assert k<q
    assert r_must_be<q
    assert s_must_be<q

    m1 = hash_ptr
    m1.update(msg)
    z=int.from_bytes(m1.digest()[0:N//8], 'big')
    
    # sign

    r=divmod(pow(g, k, p), q)[1]
    s=divmod((z + x*r) * pow(k, -1, q), q)[1]

    #print ("r", hex(r))
    #print ("s", hex(s))
    assert r==r_must_be
    assert s==s_must_be

    # verify
    # we use here only g, p, q, y, z, r, s

    w=pow(s, -1, q) # mod inverse of s mod q
    u1=divmod(z*w, q)[1] # IOW, u1=z/s mod q
    #print ("u1", hex(u1))
    u2=divmod(r*w, q)[1] # IOW, u2=r/s mod q
    #print ("u2", hex(u2))
    v=divmod(divmod(pow(g, u1, p) * pow(y, u2, p), p)[1], q)[1] # IOW, v=g^{z/s} * y^{r/s}

    assert r==v # signature is valid

# from cryptography.io test vectors
# [mod = L=1024, N=160, SHA-1]

p = 0xa8f9cd201e5e35d892f85f80e4db2599a5676a3b1d4f190330ed3256b26d0e80a0e49a8fffaaad2a24f472d2573241d4d6d6c7480c80b4c67bb4479c15ada7ea8424d2502fa01472e760241713dab025ae1b02e1703a1435f62ddf4ee4c1b664066eb22f2e3bf28bb70a2a76e4fd5ebe2d1229681b5b06439ac9c7e9d8bde283
q = 0xf85f0f83ac4df7ea0cdf8f469bfeeaea14156495
g = 0x2b3152ff6c62f14622b8f48e59f8af46883b38e79b8c74deeae9df131f8b856e3ad6c8455dab87cc0da8ac973417ce4f7878557d6cdf40b35b4a0ca3eb310c6a95d68ce284ad4e25ea28591611ee08b8444bd64b25f3f7c572410ddfb39cc728b9c936f85f419129869929cdb909a6a3a99bbe089216368171bd0ba81de4fe33
msg = bytes.fromhex("3b46736d559bd4e0c2c1b2553a33ad3c6cf23cac998d3d0c0e8fa4b19bca06f2f386db2dcff9dca4f40ad8f561ffc308b46c5f31a7735b5fa7e0f9e6cb512e63d7eea05538d66a75cd0d4234b5ccf6c1715ccaaf9cdc0a2228135f716ee9bdee7fc13ec27a03a6d11c5c5b3685f51900b1337153bc6c4e8f52920c33fa37f4e7")
x = 0xc53eae6d45323164c7d07af5715703744a63fc3a
y = 0x313fd9ebca91574e1c2eebe1517c57e0c21b0209872140c5328761bbb2450b33f1b18b409ce9ab7c4cd8fda3391e8e34868357c199e16a6b2eba06d6749def791d79e95d3a4d09b24c392ad89dbf100995ae19c01062056bb14bce005e8731efde175f95b975089bdcdaea562b32786d96f5a31aedf75364008ad4fffebb970b
k = 0x98cbcc4969d845e2461b5f66383dd503712bbcfa
r_must_be = 0x50ed0e810e3f1c7cb6ac62332058448bd8b284c0
s_must_be = 0xc6aded17216b46b7e4b6f2a97c1ad7cc3da83fde

test(p, q, g, msg, x, y, k, r_must_be, s_must_be, hashlib.sha1())

# from cryptography.io test vectors
# [mod = L=3072, N=256, SHA-512]

p = 0xc1d0a6d0b5ed615dee76ac5a60dd35ecb000a202063018b1ba0a06fe7a00f765db1c59a680cecfe3ad41475badb5ad50b6147e2596b88d34656052aca79486ea6f6ec90b23e363f3ab8cdc8b93b62a070e02688ea877843a4685c2ba6db111e9addbd7ca4bce65bb10c9ceb69bf806e2ebd7e54edeb7f996a65c907b50efdf8e575bae462a219c302fef2ae81d73cee75274625b5fc29c6d60c057ed9e7b0d46ad2f57fe01f823230f31422722319ce0abf1f141f326c00fbc2be4cdb8944b6fd050bd300bdb1c5f4da72537e553e01d51239c4d461860f1fb4fd8fa79f5d5263ff62fed7008e2e0a2d36bf7b9062d0d75db226c3464b67ba24101b085f2c670c0f87ae530d98ee60c5472f4aa15fb25041e19106354da06bc2b1d322d40ed97b21fd1cdad3025c69da6ce9c7ddf3dcf1ea4d56577bfdec23071c1f05ee4077b5391e9a404eaffe12d1ea62d06acd6bf19e91a158d2066b4cd20e4c4e52ffb1d5204cd022bc7108f2c799fb468866ef1cb09bce09dfd49e4740ff8140497be61
q = 0xbf65441c987b7737385eadec158dd01614da6f15386248e59f3cddbefc8e9dd1
g = 0xc02ac85375fab80ba2a784b94e4d145b3be0f92090eba17bd12358cf3e03f4379584f8742252f76b1ede3fc37281420e74a963e4c088796ff2bab8db6e9a4530fc67d51f88b905ab43995aab46364cb40c1256f0466f3dbce36203ef228b35e90247e95e5115e831b126b628ee984f349911d30ffb9d613b50a84dfa1f042ba536b82d5101e711c629f9f2096dc834deec63b70f2a2315a6d27323b995aa20d3d0737075186f5049af6f512a0c38a9da06817f4b619b94520edfac85c4a6e2e186225c95a04ec3c3422b8deb284e98d24b31465802008a097c25969e826c2baa59d2cba33d6c1d9f3962330c1fcda7cfb18508fea7d0555e3a169daed353f3ee6f4bb30244319161dff6438a37ca793b24bbb1b1bc2194fc6e6ef60278157899cb03c5dd6fc91a836eb20a25c09945643d95f7bd50d206684d6ffc14d16d82d5f781225bff908392a5793b803f9b70b4dfcb394f9ed81c18e391a09eb3f93a032d81ba670cabfd6f64aa5e3374cb7c2029f45200e4f0bfd820c8bd58dc5eeb34
msg = bytes.fromhex("494180eed0951371bbaf0a850ef13679df49c1f13fe3770b6c13285bf3ad93dc4ab018aab9139d74200808e9c55bf88300324cc697efeaa641d37f3acf72d8c97bff0182a35b940150c98a03ef41a3e1487440c923a988e53ca3ce883a2fb532bb7441c122f1dc2f9d0b0bc07f26ba29a35cdf0da846a9d8eab405cbf8c8e77f")
x = 0x150b5c51ea6402276bc912322f0404f6d57ff7d32afcaa83b6dfde11abb48181
y = 0x6da54f2b0ddb4dcce2da1edfa16ba84953d8429ce60cd111a5c65edcf7ba5b8d9387ab6881c24880b2afbdb437e9ed7ffb8e96beca7ea80d1d90f24d546112629df5c9e9661742cc872fdb3d409bc77b75b17c7e6cfff86261071c4b5c9f9898be1e9e27349b933c34fb345685f8fc6c12470d124cecf51b5d5adbf5e7a2490f8d67aac53a82ed6a2110686cf631c348bcbc4cf156f3a6980163e2feca72a45f6b3d68c10e5a2283b470b7292674490383f75fa26ccf93c0e1c8d0628ca35f2f3d9b6876505d118988957237a2fc8051cb47b410e8b7a619e73b1350a9f6a260c5f16841e7c4db53d8eaa0b4708d62f95b2a72e2f04ca14647bca6b5e3ee707fcdf758b925eb8d4e6ace4fc7443c9bc5819ff9e555be098aa055066828e21b818fedc3aac517a0ee8f9060bd86e0d4cce212ab6a3a243c5ec0274563353ca7103af085e8f41be524fbb75cda88903907df94bfd69373e288949bd0626d85c1398b3073a139d5c747d24afdae7a3e745437335d0ee993eef36a3041c912f7eb58
k = 0xb599111b9f78402cefe7bde8bf553b6ca00d5abaf9a158aa42f2607bf78510bc
r_must_be = 0xa40a6c905654c55fc58e99c7d1a3feea2c5be64823d4086ce811f334cfdc448d
s_must_be = 0x6478050977ec585980454e0a2f26a03037b921ca588a78a4daff7e84d49a8a6c

test(p, q, g, msg, x, y, k, r_must_be, s_must_be, hashlib.sha512())

# https://www.ietf.org/rfc/rfc6979.txt

# A.2.1.  DSA, 1024 Bits

p = 0x86F5CA03DCFEB225063FF830A0C769B9DD9D6153AD91D7CE27F787C43278B447E6533B86B18BED6E8A48B784A14C252C5BE0DBF60B86D6385BD2F12FB763ED8873ABFD3F5BA2E0A8C0A59082EAC056935E529DAF7C610467899C77ADEDFC846C881870B7B19B2B58F9BE0521A17002E3BDD6B86685EE90B3D9A1B02B782B1779
q = 0x996F967F6C8E388D9E28D01E205FBA957A5698B1
g = 0x07B0F92546150B62514BB771E2A0C0CE387F03BDA6C56B505209FF25FD3C133D89BBCD97E904E09114D9A7DEFDEADFC9078EA544D2E401AEECC40BB9FBBF78FD87995A10A1C27CB7789B594BA7EFB5C4326A9FE59A070E136DB77175464ADCA417BE5DCE2F40D10A46A3A3943F26AB7FD9C0398FF8C76EE0A56826A8A88F1DBD
x = 0x411602CB19A6CCC34494D79D98EF1E7ED5AF25F7
y = 0x5DF5E01DED31D0297E274E1691C192FE5868FEF9E19A84776454B100CF16F65392195A38B90523E2542EE61871C0440CB87C322FC4B4D2EC5E1E7EC766E1BE8D4CE935437DC11C3C8FD426338933EBFE739CB3465F4D3668C5E473508253B1E682F65CBDC4FAE93C2EA212390E54905A86E2223170B44EAA7DA5DD9FFCFB7F3B

k = 0x7BDB6B0FF756E1BB5D53583EF979082F9AD5BD5B
r_must_be = 0x2E1A0C2562B2912CAAF89186FB0F42001585DA55
s_must_be = 0x29EFB6B0AFF2D7A68EB70CA313022253B9A88DF5
test(p, q, g, b"sample", x, y, k, r_must_be, s_must_be, hashlib.sha1())

k = 0x562097C06782D60C3037BA7BE104774344687649
r_must_be = 0x4BC3B686AEA70145856814A6F1BB53346F02101E
s_must_be = 0x410697B92295D994D21EDD2F4ADA85566F6F94C1
test(p, q, g, b"sample", x, y, k, r_must_be, s_must_be, hashlib.sha224())

k = 0x519BA0546D0C39202A7D34D7DFA5E760B318BCFB
r_must_be = 0x81F2F5850BE5BC123C43F71A3033E9384611C545
s_must_be = 0x4CDD914B65EB6C66A8AAAD27299BEE6B035F5E89
test(p, q, g, b"sample", x, y, k, r_must_be, s_must_be, hashlib.sha256())

k = 0x95897CD7BBB944AA932DBC579C1C09EB6FCFC595
r_must_be = 0x07F2108557EE0E3921BC1774F1CA9B410B4CE65A
s_must_be = 0x54DF70456C86FAC10FAB47C1949AB83F2C6F7595
test(p, q, g, b"sample", x, y, k, r_must_be, s_must_be, hashlib.sha384())

k = 0x09ECE7CA27D0F5A4DD4E556C9DF1D21D28104F8B
r_must_be = 0x16C3491F9B8C3FBBDD5E7A7B667057F0D8EE8E1B
s_must_be = 0x02C36A127A7B89EDBB72E4FFBC71DABC7D4FC69C
test(p, q, g, b"sample", x, y, k, r_must_be, s_must_be, hashlib.sha512())

# https://www.ietf.org/rfc/rfc6979.txt

# A.2.2.  DSA, 2048 Bits

p = 0x9DB6FB5951B66BB6FE1E140F1D2CE5502374161FD6538DF1648218642F0B5C48C8F7A41AADFA187324B87674FA1822B00F1ECF8136943D7C55757264E5A1A44FFE012E9936E00C1D3E9310B01C7D179805D3058B2A9F4BB6F9716BFE6117C6B5B3CC4D9BE341104AD4A80AD6C94E005F4B993E14F091EB51743BF33050C38DE235567E1B34C3D6A5C0CEAA1A0F368213C3D19843D0B4B09DCB9FC72D39C8DE41F1BF14D4BB4563CA28371621CAD3324B6A2D392145BEBFAC748805236F5CA2FE92B871CD8F9C36D3292B5509CA8CAA77A2ADFC7BFD77DDA6F71125A7456FEA153E433256A2261C6A06ED3693797E7995FAD5AABBCFBE3EDA2741E375404AE25B
q = 0xF2C3119374CE76C9356990B465374A17F23F9ED35089BD969F61C6DDE9998C1F
g = 0x5C7FF6B06F8F143FE8288433493E4769C4D988ACE5BE25A0E24809670716C613D7B0CEE6932F8FAA7C44D2CB24523DA53FBE4F6EC3595892D1AA58C4328A06C46A15662E7EAA703A1DECF8BBB2D05DBE2EB956C142A338661D10461C0D135472085057F3494309FFA73C611F78B32ADBB5740C361C9F35BE90997DB2014E2EF5AA61782F52ABEB8BD6432C4DD097BC5423B285DAFB60DC364E8161F4A2A35ACA3A10B1C4D203CC76A470A33AFDCBDD92959859ABD8B56E1725252D78EAC66E71BA9AE3F1DD2487199874393CD4D832186800654760E1E34C09E4D155179F9EC0DC4473F996BDCE6EED1CABED8B6F116F7AD9CF505DF0F998E34AB27514B0FFE7
x = 0x69C7548C21D0DFEA6B9A51C9EAD4E27C33D3B3F180316E5BCAB92C933F0E4DBC
y = 0x667098C654426C78D7F8201EAC6C203EF030D43605032C2F1FA937E5237DBD949F34A0A2564FE126DC8B715C5141802CE0979C8246463C40E6B6BDAA2513FA611728716C2E4FD53BC95B89E69949D96512E873B9C8F8DFD499CC312882561ADECB31F658E934C0C197F2C4D96B05CBAD67381E7B768891E4DA3843D24D94CDFB5126E9B8BF21E8358EE0E0A30EF13FD6A664C0DCE3731F7FB49A4845A4FD8254687972A2D382599C9BAC4E0ED7998193078913032558134976410B89D2C171D123AC35FD977219597AA7D15C1A9A428E59194F75C721EBCBCFAE44696A499AFA74E04299F132026601638CB87AB79190D4A0986315DA8EEC6561C938996BEADF

k = 0x888FA6F7738A41BDC9846466ABDB8174C0338250AE50CE955CA16230F9CBD53E
r_must_be = 0x3A1B2DBD7489D6ED7E608FD036C83AF396E290DBD602408E8677DAABD6E7445A
s_must_be = 0xD26FCBA19FA3E3058FFC02CA1596CDBB6E0D20CB37B06054F7E36DED0CDBBCCF
test(p, q, g, b"sample", x, y, k, r_must_be, s_must_be, hashlib.sha1())

k = 0x5A12994431785485B3F5F067221517791B85A597B7A9436995C89ED0374668FC
r_must_be = 0x2016ED092DC5FB669B8EFB3D1F31A91EECB199879BE0CF78F02BA062CB4C942E
s_must_be = 0xD0C76F84B5F091E141572A639A4FB8C230807EEA7D55C8A154A224400AFF2351
test(p, q, g, b"sample", x, y, k, r_must_be, s_must_be, hashlib.sha512())