Simple private key derivation in 2 signatures with the same "k" nonce (python)

[mcdouglasx]

This is an educational example, the K nonce must always be Random, do not sign real messages using this script.


We first sign the two different messages using the following script.

message 1 = "Hello, BitcoinTalk"

message 2 = "Hello, BitcoinTalk  2"

Code:

import hashlib
import random
import binascii

################################################################################################

privKey = 2457876789644357800744426

message = "Hello, BitcoinTalk"

nonce= 64338999543366

################################################################################################

Pcurve = 115792089237316195423570985008687907853269984665640564039457584007908834671663
Acurve = 0
Bcurve = 7
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
GPoint = (Gx, Gy)
N = 115792089237316195423570985008687907852837564279074904382605163141518161494337

def modinv(a, b):
    lm, hm = 1, 0
    low, high = a % b, b
    while low > 1:
        ratio = high // low
        nm, new = hm - lm * ratio, high - low * ratio
        lm, low, hm, high = nm, new, lm, low
    return lm % b

def ECAdd(a, b):
    if a == 'infinity':
        return b
    if b == 'infinity':
        return a
    if a[0] == b[0] and a[1] == -b[1] % Pcurve:
        return 'infinity'
    if a[0] == b[0] and a[1] == b[1]:
        return ECDouble(a)

    LambdaAdd = ((b[1] - a[1]) * modinv((b[0] - a[0]), Pcurve)) % Pcurve
    x = (LambdaAdd * LambdaAdd - a[0] - b[0]) % Pcurve
    y = (LambdaAdd * (a[0] - x) - a[1]) % Pcurve
    return (x, y)

def ECDouble(a):
    if a == 'infinity':
        return 'infinity'
    LambdaDouble = ((3 * a[0] * a[0] + Acurve) * modinv((2 * a[1]), Pcurve)) % Pcurve
    x = (LambdaDouble * LambdaDouble - 2 * a[0]) % Pcurve
    y = (LambdaDouble * (a[0] - x) - a[1]) % Pcurve
    return (x, y)

def ECMultiply(GenPoint, privKeyHex):
    if privKeyHex == 0 or privKeyHex >= N:
        raise Exception("Invalid Private Key")
    privKeyBin = str(bin(privKeyHex))[2:]
    Q = 'infinity'
    for i in privKeyBin:
        Q = ECDouble(Q)
        if i == "1":
            Q = ECAdd(Q, GenPoint)
    return Q


def signECDSA(privKeyDec, message):
    Q = ECMultiply(GPoint, privKeyDec)
    hash_message = hashlib.sha256(message.encode()).digest()
    k = nonce#random.randint(1, N - 1)
    r = (ECMultiply(GPoint, k)[0] % N) % N
    s = (modinv(k, N) * (int.from_bytes(hash_message, 'big') + r * privKeyDec)) % N
    return r, s, hash_message

privKeyHex = int(privKey)
pubKey = ECMultiply(GPoint, privKeyHex)
pubKeyX, pubKeyY = pubKey

r, s, hash_message = signECDSA(privKeyHex, message)

print("message hash:",(hashlib.sha256(message.encode()).digest()).hex())
print("r:", hex(r)[2:])
print("s:", hex(s)[2:])

Once the corresponding signatures and hashes are obtained, we place them in the following script to derive the private key.

Code:

import hashlib

Pcurve = 115792089237316195423570985008687907853269984665640564039457584007908834671663
Acurve = 0
Bcurve = 7
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
GPoint = (Gx, Gy)
N = 115792089237316195423570985008687907852837564279074904382605163141518161494337

def modinv(a, b):
    lm, hm = 1, 0
    low, high = a % b, b
    while low > 1:
        ratio = high // low
        nm, new = hm - lm * ratio, high - low * ratio
        lm, low, hm, high = nm, new, lm, low
    return lm % b

#msg 1
hash1 = int( "6eb1db1a144d94df76be0d2d2721df7839aff7b5899873a1ed9013f3fbbbd0d0" ,16)
r1 = int( "bda653c3ebcbbfd1d550462d4030c140bafc4ed9ca17d32ac598a7cedb942947" ,16)
s1 = int( "7ebff2f8199f0700e80297659424ca7eda26dde1afc1d226c08c377896b0ebda" ,16)

#msg 2
hash2 = int( "619e86eb7f8689b2b1ed260be14fcab2b2b31ae5e6a7df5e393ec4e272bd6f37" ,16)
r2 = int( "bda653c3ebcbbfd1d550462d4030c140bafc4ed9ca17d32ac598a7cedb942947" ,16)
s2 = int( "f37ba9033df153303c893a029b7aa80b3eb0e1d6099b14133661658455375487" ,16)





k = ((hash1 - hash2) * modinv((s1 - s2), N)) % N

privKey = ((s1 * k - hash1) * modinv(r1, N)) % N

print("Private Key:", privKey)

[krashfire]

This is an educational example, the K nonce must always be Random, do not sign real messages using this script.


We first sign the two different messages using the following script.

message 1 = "Hello, BitcoinTalk"

message 2 = "Hello, BitcoinTalk  2"

Code:

import hashlib
import random
import binascii

################################################################################################

privKey = 2457876789644357800744426

message = "Hello, BitcoinTalk"

nonce= 64338999543366

################################################################################################

Pcurve = 115792089237316195423570985008687907853269984665640564039457584007908834671663
Acurve = 0
Bcurve = 7
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
GPoint = (Gx, Gy)
N = 115792089237316195423570985008687907852837564279074904382605163141518161494337

def modinv(a, b):
    lm, hm = 1, 0
    low, high = a % b, b
    while low > 1:
        ratio = high // low
        nm, new = hm - lm * ratio, high - low * ratio
        lm, low, hm, high = nm, new, lm, low
    return lm % b

def ECAdd(a, b):
    if a == 'infinity':
        return b
    if b == 'infinity':
        return a
    if a[0] == b[0] and a[1] == -b[1] % Pcurve:
        return 'infinity'
    if a[0] == b[0] and a[1] == b[1]:
        return ECDouble(a)

    LambdaAdd = ((b[1] - a[1]) * modinv((b[0] - a[0]), Pcurve)) % Pcurve
    x = (LambdaAdd * LambdaAdd - a[0] - b[0]) % Pcurve
    y = (LambdaAdd * (a[0] - x) - a[1]) % Pcurve
    return (x, y)

def ECDouble(a):
    if a == 'infinity':
        return 'infinity'
    LambdaDouble = ((3 * a[0] * a[0] + Acurve) * modinv((2 * a[1]), Pcurve)) % Pcurve
    x = (LambdaDouble * LambdaDouble - 2 * a[0]) % Pcurve
    y = (LambdaDouble * (a[0] - x) - a[1]) % Pcurve
    return (x, y)

def ECMultiply(GenPoint, privKeyHex):
    if privKeyHex == 0 or privKeyHex >= N:
        raise Exception("Invalid Private Key")
    privKeyBin = str(bin(privKeyHex))[2:]
    Q = 'infinity'
    for i in privKeyBin:
        Q = ECDouble(Q)
        if i == "1":
            Q = ECAdd(Q, GenPoint)
    return Q


def signECDSA(privKeyDec, message):
    Q = ECMultiply(GPoint, privKeyDec)
    hash_message = hashlib.sha256(message.encode()).digest()
    k = nonce#random.randint(1, N - 1)
    r = (ECMultiply(GPoint, k)[0] % N) % N
    s = (modinv(k, N) * (int.from_bytes(hash_message, 'big') + r * privKeyDec)) % N
    return r, s, hash_message

privKeyHex = int(privKey)
pubKey = ECMultiply(GPoint, privKeyHex)
pubKeyX, pubKeyY = pubKey

r, s, hash_message = signECDSA(privKeyHex, message)

print("message hash:",(hashlib.sha256(message.encode()).digest()).hex())
print("r:", hex(r)[2:])
print("s:", hex(s)[2:])

Once the corresponding signatures and hashes are obtained, we place them in the following script to derive the private key.

Code:

import hashlib

Pcurve = 115792089237316195423570985008687907853269984665640564039457584007908834671663
Acurve = 0
Bcurve = 7
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
GPoint = (Gx, Gy)
N = 115792089237316195423570985008687907852837564279074904382605163141518161494337

def modinv(a, b):
    lm, hm = 1, 0
    low, high = a % b, b
    while low > 1:
        ratio = high // low
        nm, new = hm - lm * ratio, high - low * ratio
        lm, low, hm, high = nm, new, lm, low
    return lm % b

#msg 1
hash1 = int( "6eb1db1a144d94df76be0d2d2721df7839aff7b5899873a1ed9013f3fbbbd0d0" ,16)
r1 = int( "bda653c3ebcbbfd1d550462d4030c140bafc4ed9ca17d32ac598a7cedb942947" ,16)
s1 = int( "7ebff2f8199f0700e80297659424ca7eda26dde1afc1d226c08c377896b0ebda" ,16)

#msg 2
hash2 = int( "619e86eb7f8689b2b1ed260be14fcab2b2b31ae5e6a7df5e393ec4e272bd6f37" ,16)
r2 = int( "bda653c3ebcbbfd1d550462d4030c140bafc4ed9ca17d32ac598a7cedb942947" ,16)
s2 = int( "f37ba9033df153303c893a029b7aa80b3eb0e1d6099b14133661658455375487" ,16)





k = ((hash1 - hash2) * modinv((s1 - s2), N)) % N

privKey = ((s1 * k - hash1) * modinv(r1, N)) % N

print("Private Key:", privKey)

this flaw is a known flaw in old software. most version these days dont have these flaws. as k =will always be random.randint in the code these days

[mcdouglasx]

this flaw is a known flaw in old software. most version these days dont have these flaws. as k =will always be random.randint in the code these days

Many people prefer their own codes, and since error is human, a little reminder never hurts.

[krashfire]

this flaw is a known flaw in old software. most version these days dont have these flaws. as k =will always be random.randint in the code these days

Many people prefer their own codes, and since error is human, a little reminder never hurts.

ah ok.. yeah... i was wondering why you put up old flaws...but yeah.. i get it now. you are right.