Sign a message -- the message itself, not a hash -- with a given
    private key.

    Input private key must be hex, NOT WIF.  Use wiftohex() found in
    .bitcoin in order to get the hex private key and whether it is
    (or rather, its public key is) compressed.

    'iscompressed' is True/False bool for whether or not to indicate
    compression on the public key that corresponds to the input
    private key hex.

    'iscompressed' is not defaulted to True like it is in most other
    functions, because it really matters whether you use it. All
    software implementations treat uncompressed and compressed keys as
    entirely different, and a valid message signature will NOT
    validate if the public key compression is not correct. Whereas for
    transaction signatures, only the r-value is checked, message
    signature validation additionally checks/verifies public key
    compression. So you must manually set it!

    Also, note that message signatures are an entirely different
    format from DER-encoded transaction signatures.

    Sample message, which includes the quotation marks, and has a new
    line and 4 spaces after the new line:

    "You miss 100% of the shots you don't take.  -- Wayne Gretzky"
        -- Michael Scott

    >>> msg = '"You miss 100% of the shots you don\\'t take.  -- Wayne Gretzky"\\n    -- Michael Scott'
    >>> p = 'c05694a7af0e01dceb63e5912a415c28d3fc823ca1fd3fa34d41afde03740466'
    >>> k = 4 # chosen by fair dice roll, guaranteed to be random
    >>> signmsg(msg,p,True,k)
    'H+ST2/HBDYDzWB5JBJMLFATMbBOQDuB1hHT6lKvoxM0TBxoLMWsgrFmA3CGam/poUZPl/PukXCrYBzuwMW3Tyyo='

    Your software should then translate that data set into something akin to:

    -----BEGIN BITCOIN SIGNED MESSAGE-----
    "You miss 100% of the shots you don't take.  -- Wayne Gretzky"
        -- Michael Scott
    -----BEGIN BITCOIN SIGNATURE-----
    Address: 1AuZ7wby1rUVzwFvFgySeTFS7JcHN2TeGs

    H+ST2/HBDYDzWB5JBJMLFATMbBOQDuB1hHT6lKvoxM0TBxoLMWsgrFmA3CGam/poUZPl/PukXCrYBzuwMW3Tyyo=
    -----END BITCOIN SIGNATURE-----

def signmsg(msg,priv,iscompressed,k=0):
    '''
    Sign a message -- the message itself, not a hash -- with a given
    private key.

    Input private key must be hex, NOT WIF.  Use wiftohex() found in
    .bitcoin in order to get the hex private key and whether it is
    (or rather, its public key is) compressed.

    'iscompressed' is True/False bool for whether or not to indicate
    compression on the public key that corresponds to the input
    private key hex.

    'iscompressed' is not defaulted to True like it is in most other
    functions, because it really matters whether you use it. All
    software implementations treat uncompressed and compressed keys as
    entirely different, and a valid message signature will NOT
    validate if the public key compression is not correct. Whereas for
    transaction signatures, only the r-value is checked, message
    signature validation additionally checks/verifies public key
    compression. So you must manually set it!

    Also, note that message signatures are an entirely different
    format from DER-encoded transaction signatures.

    Sample message, which includes the quotation marks, and has a new
    line and 4 spaces after the new line:

    "You miss 100% of the shots you don't take.  -- Wayne Gretzky"
        -- Michael Scott

    >>> msg = '"You miss 100% of the shots you don\\'t take.  -- Wayne Gretzky"\\n    -- Michael Scott'
    >>> p = 'c05694a7af0e01dceb63e5912a415c28d3fc823ca1fd3fa34d41afde03740466'
    >>> k = 4 # chosen by fair dice roll, guaranteed to be random
    >>> signmsg(msg,p,True,k)
    'H+ST2/HBDYDzWB5JBJMLFATMbBOQDuB1hHT6lKvoxM0TBxoLMWsgrFmA3CGam/poUZPl/PukXCrYBzuwMW3Tyyo='

    Your software should then translate that data set into something akin to:

    -----BEGIN BITCOIN SIGNED MESSAGE-----
    "You miss 100% of the shots you don't take.  -- Wayne Gretzky"
        -- Michael Scott
    -----BEGIN BITCOIN SIGNATURE-----
    Address: 1AuZ7wby1rUVzwFvFgySeTFS7JcHN2TeGs

    H+ST2/HBDYDzWB5JBJMLFATMbBOQDuB1hHT6lKvoxM0TBxoLMWsgrFmA3CGam/poUZPl/PukXCrYBzuwMW3Tyyo=
    -----END BITCOIN SIGNATURE-----
    '''

    omsg = msg

    # Stripping carraige returns is standard practice in every
    # implementation I found, including Bitcoin Core
    msg = msg.replace("\r\n","\n")

    msg1 = hexstrlify(bytearray("\x18Bitcoin Signed Message:\n",'utf-8'))
    msg2 = tovarint(len(msg))
    msg3 = hexstrlify(bytearray(msg,'utf-8'))
    msg = hash256(msg1 + msg2 + msg3)


    sig = sign(msg,priv,k)

    # Bitcoin message signature format doesn't use DER leading '00's
    # Although, r/s must be 64-char, so they are zfilled to that
    rlen = 2*int(sig[6:8],16)
    r = sig[8:8+(rlen)].lstrip("0").zfill(64)
    slen = 2*int(sig[10+(rlen):12+(rlen)],16)
    s = sig[12+(rlen):(12+(rlen)+(slen))].lstrip("0").zfill(64)

    pubkey = privtopub(priv,iscompressed)
    for i in range(4):
        prefix = 27 + i
        if iscompressed:
            prefix = prefix + 4
        o = base64.b64encode(unhexlify(dechex(prefix,1) + r + s))
        if str(o)[:2] == "b'": # Fuck you, Python 3
            o = str(o)[2:-1]
        if verifymsg(omsg,o) == pubkey:
            return o

    raise Exception("Unknown failure. This method should never reach the end.")