Base58 encodes characters by appending a prefix, treating the bytes as a big endian number and writing that big endian number in base 58.
Therefore, specific prefixes can pin down the most significant "digits" in Base58.
The python script b58_prefix.py in the scripts directory of the Tezos repo can help find those prefixes. Note that to run it you will ...
It shouldn't make a difference how you pick k, deterministically or not. It's random and is supposed to be kept secret by the signer, so there's no way to tell what k was used by just looking at the signature.
Tezos expects exactly 64 bytes for a secp256k1 signature
Per this question you ...
Base58 prefixes will always produce a prefixed output for a set length of output. So the input address is 20 bytes + the 3 byte prefix gives a 36 char long address with tz1.
You calculate these prefixes by guess and check.
The immediate problem seems to be that you are not getting signatures in "lower S" form. This seems better:
I cannot vouch for the correctness of the code generally.
Not a direct answer, but workaround
python-ecdsa lib generates non-deterministic signatures by default (see more at https://tools.ietf.org/html/rfc6979#section-3.2). Each time you run your code you get a new result.
I've experienced this issue and eventually switched to secp256k1 package (there were several extra reasons for that):
You must sign transactions from tz2 addresses with secp256k1. Eztz's sign function uses Ed25519, so that wont work. Easiest would probably be to just replace libsodium in eztz with something like bitcoinjs-lib.