Compares the message and input signature, and outputs what the
    corresponding public key is that would make that message/signature
    pair valid.

    I didn't set it to take in a pubkey and output True/False because
    sometimes it is useful to have the resulting key, even if the
    msg/sig pair is invalid.
    (And not just in the signmsg() function above.)

    Also, worth remembering that message signatures are an entirely
    different format than DER-encoded transaction signatures.

    >>> msg = '"You miss 100% of the shots you don\\'t take.  -- Wayne Gretzky"\\n    -- Michael Scott'
    >>> sig = 'H+ST2/HBDYDzWB5JBJMLFATMbBOQDuB1hHT6lKvoxM0TBxoLMWsgrFmA3CGam/poUZPl/PukXCrYBzuwMW3Tyyo='
    >>> x = verifymsg(msg,sig)
    >>> pub = '022587327dabe23ee608d8504d8bc3a341397db1c577370389f94ccd96bb59a077'
    >>> x == pub
    True

def verifymsg(msg,sig):
    '''
    Compares the message and input signature, and outputs what the
    corresponding public key is that would make that message/signature
    pair valid.

    I didn't set it to take in a pubkey and output True/False because
    sometimes it is useful to have the resulting key, even if the
    msg/sig pair is invalid.
    (And not just in the signmsg() function above.)

    Also, worth remembering that message signatures are an entirely
    different format than DER-encoded transaction signatures.

    >>> msg = '"You miss 100% of the shots you don\\'t take.  -- Wayne Gretzky"\\n    -- Michael Scott'
    >>> sig = 'H+ST2/HBDYDzWB5JBJMLFATMbBOQDuB1hHT6lKvoxM0TBxoLMWsgrFmA3CGam/poUZPl/PukXCrYBzuwMW3Tyyo='
    >>> x = verifymsg(msg,sig)
    >>> pub = '022587327dabe23ee608d8504d8bc3a341397db1c577370389f94ccd96bb59a077'
    >>> x == pub
    True
    '''

    msg = msg.replace("\r\n","\n")
    # Again, standard convention to remove returns

    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 = hexstrlify(base64.b64decode(sig))

    r = int(sig[2:66],16)
    s = int(sig[66:],16)

    prefix = int(sig[:2],16)
    if prefix > 30:
        out_compressed = True
        prefix = prefix - 4
    else:
        out_compressed = False
    prefix = prefix - 27

    m = int(N*prefix) if prefix > 1 else 0
    x = (r + int(m//2)) % N
    a = (pow_mod(x, 3, P) + 7) % P
    b = pow_mod(a, ((P+1)//4), P)
    if (b % 2) != prefix:
        y = (-b % P)
    else:
        y = b

    x, y = dechex(x,32), dechex(y,32)
    pubkey = "04" + x + y

    negative_msg = dechex((N - int(msg,16)),32)
    modinv_r = dechex(modinv(r, N),32)
    pubkey = multiplypub(
                   addpubs(
                     multiplypub(pubkey,dechex(s,32),False),
                     privtopub(negative_msg,False),False),
                   modinv_r,False)

    if out_compressed:
        pubkey = compress(pubkey)
    return strlify(pubkey)