<jupyter_start><jupyter_text>**Schnorr Digital Signature Algorithm (EC SSA)**  Setupbtclib is needed: let's install/update it and import straight away some of its functions<jupyter_code>!pip install --upgrade btclib

from hashlib import sha256 as hf

from btclib.numbertheory import mod_inv
from btclib.curve import mult
from btclib.curve import secp256k1 as ec<jupyter_output>Requirement already up-to-date: btclib in /Users/ferdi/Git/myforks/btclib (2020.12)
Requirement already satisfied, skipping upgrade: dataclasses_json in /Users/ferdi/Git/myforks/bbt/venv/lib/python3.8/site-packages (from btclib) (0.5.2)
Requirement already satisfied, skipping upgrade: marshmallow-enum<2.0.0,>=1.5.1 in /Users/ferdi/Git/myforks/bbt/venv/lib/python3.8/site-packages (from dataclasses_json->btclib) (1.5.1)
Requirement already satisfied, skipping upgrade: marshmallow<4.0.0,>=3.3.0 in /Users/ferdi/Git/myforks/bbt/venv/lib/python3.8/site-packages (from dataclasses_json->btclib) (3.9.1)
Requirement already satisfied, skipping upgrade: typing-inspect>=0.4.0 in /Users/ferdi/Git/myforks/bbt/venv/lib/python3.8/site-packages (from dataclasses_json->btclib) (0.6.0)
Requirement already satisfied, skipping upgrade: stringcase<2.0.0,==1.2.0 in /Users/ferdi/Git/myforks/bbt/venv/lib/python3.8/site-packages (from dataclasses_json->btclib) (1.2.0)
Requirement already satisfied, skipping upg[...]<jupyter_text>For this exercise we use secp256k1 as elliptic curve and SHA256 as hash function:<jupyter_code>print(ec)<jupyter_output>Curve
 p   = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
 a   = 0
 b   = 7
 x_G = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
 y_G = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
 n   = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
 h = 1<jupyter_text>Normally, hf is chosen such that its output size is roughly equal to the size of ec.n, since the overall security of the signature scheme will depend on the smallest of the two; however, the ECDSA standard support all combinations of sizes<jupyter_code>print(hf().digest_size)
print(ec.nsize)<jupyter_output>32
32<jupyter_text>**Digital Signature Protocol** 1. Key generationPrivate key (generated elsewhere, a fixed value here):<jupyter_code>q = 0x18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725
assert 0 < q < ec.n, "Invalid private key"
print("q:", q)
print("Hex(q):", hex(q))<jupyter_output>q: 11253563012059685825953619222107823549092147699031672238385790369351542642469
Hex(q): 0x18e14a7b6a307f426a94f8114701e7c8e774e7f9a47e2c2035db29a206321725<jupyter_text>Corresponding Public Key:<jupyter_code>Q = mult(q)
print("PubKey:", "02" if (Q[1] % 2 == 0) else "03", hex(Q[0]))<jupyter_output>PubKey: 02 0x50863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352<jupyter_text>Signature (DSA) MessageMessage to be signed and its hash value:<jupyter_code>msg = "Paolo is afraid of ephemeral random numbers"

h_bytes = hf(msg.encode()).digest()
# hash(msg) must be transformed into an integer modulo ec.n:
h = int.from_bytes(h_bytes, 'big') % ec.n
assert h != 0
print("h:", hex(h))<jupyter_output>h: 0x9788fd27b3aafd1bd1591a1158ce2d8bdc37ab4040dddb64e64d17616e69ce2b<jupyter_text>Deterministic Ephemeral keyThe Ephemeral key k must be kept secret and never reusedA good choice is to use a deterministic key: `k = hf(q||msghd)` different for each msg, private because of q<jupyter_code>k_bytes = hf(q.to_bytes(32, 'big') + msg.encode()).digest()
k = int.from_bytes(k_bytes, 'big') % ec.n
assert k != 0
print("eph k:", hex(k))<jupyter_output>eph k: 0xc2ddd3b2037595043d5892733372cd9c8f18b7b14162cbcd0504ca2f3d5d7b4a<jupyter_text>Signature Algorithm<jupyter_code>K = mult(k)

r = K[0] % ec.n
# if r == 0 (extremely unlikely for large ec.n) go back to a different ephemeral key
assert r != 0

s = ((h + r*q)*mod_inv(k, ec.n)) % ec.n
# if s1 == 0 (extremely unlikely for large ec.n) go back to a different ephemeral key
assert s != 0

print("r:", hex(r))
print("s:", hex(s))<jupyter_output>r: 0xac32d9a5d37c92d103fff8135ea7032b8e9da4a25f547cda8f2216fe49c1d53f
s: 0xb0f50ced477d3bdc23e7efc01d158402a90f27fe916c5358595c2170136e6b9c<jupyter_text>Signature verification (DSA)<jupyter_code>w = mod_inv(s, ec.n)
u = (h*w) %ec.n
v = (r*w) %ec.n
assert u != 0
assert v != 0
U = mult(u)
V = mult(v, Q)
x, y = ec.add(U, V)
print(r == x %ec.n)<jupyter_output>True<jupyter_text>Malleated Signature<jupyter_code>sm = ec.n - s
print("     r:", hex(r))
print("   *sm:", hex(sm))<jupyter_output>r: 0xac32d9a5d37c92d103fff8135ea7032b8e9da4a25f547cda8f2216fe49c1d53f
   *sm: 0x4f0af312b882c423dc18103fe2ea7bfc119fb4e81ddc4ce366763d1cbcc7d5a5<jupyter_text>Malleated Signature verification:<jupyter_code>w = mod_inv(sm, ec.n)
u = (h*w) %ec.n
v = (r*w) %ec.n
assert u != 0
assert v != 0
U = mult(u)
V = mult(v, Q)
x, y = ec.add(U, V)
print(r == x %ec.n)<jupyter_output>True<jupyter_text>Humongous mistake  MessageMessage to be signed and its hash value:<jupyter_code>msg2 = "and Paolo is right to be afraid"

h_bytes = hf(msg2.encode()).digest()
# hash(msg) must be transformed into an integer modulo ec.n:
h2 = int.from_bytes(h_bytes, 'big') % ec.n
assert h2 != 0
print("h2:", hex(h2))<jupyter_output>h2: 0x7adb91982ec03ef87efcae7f0199aefa231d8855e0bd03319460e58c0bd18049<jupyter_text>The mistake Reuse the same ephemeral deterministic key as the previous message:<jupyter_code>k2 = k #very bad! Never reuse the same ephemeral key!!!
print("eph k :", hex(k))
print("eph k2:", hex(k2))<jupyter_output>eph k : 0xc2ddd3b2037595043d5892733372cd9c8f18b7b14162cbcd0504ca2f3d5d7b4a
eph k2: 0xc2ddd3b2037595043d5892733372cd9c8f18b7b14162cbcd0504ca2f3d5d7b4a<jupyter_text>Signature Algorithm<jupyter_code>K2 = mult(k2)

r = K2[0] % ec.n
# if r == 0 (extremely unlikely for large ec.n) go back to a different ephemeral key
assert r != 0

s2 = ((h2 + r*q)*mod_inv(k2, ec.n)) %ec.n
# if s2 == 0 (extremely unlikely for large ec.n) go back to a different ephemeral key
assert s2 != 0

# bitcoin canonical 'low-s' encoding
if s2 > ec.n/2: s2 = ec.n - s2

print(" r:", hex(r))
print("s2:", hex(s2))<jupyter_output>r: 0xac32d9a5d37c92d103fff8135ea7032b8e9da4a25f547cda8f2216fe49c1d53f
s2: 0x4b7371273e661e420991dee123eff736264e5a5854767b7d8e2b70a331b4dca6<jupyter_text>Signature verification<jupyter_code>w = mod_inv(s2, ec.n)
u = (h2*w) %ec.n
v = (r*w) %ec.n
assert u != 0
assert v != 0
U = mult(u)
V = mult(v, Q)
x, y = ec.add(U, V)
print(r == x %ec.n)<jupyter_output>True<jupyter_text>ExerciseBecause of this mistake is now possible to calculate the private key from the 2 signatures.<jupyter_code><jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11498205741626795, 'fraction_numerical': 0.1320275119617225, 'mean_word_length': 6.374862183020948, 'pattern_counts': {'":': 0, '<': 55, '<?xml version=': 0, '>': 58, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 11, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '16', 'dir': 'jupyter-structured-clean-dedup', 'id': '497773', 'license': 'MIT', 'n_tokens_mistral': 3364, 'n_tokens_neox': 2878, 'n_words': 625, 'path': 'ipynb/SSA.ipynb', 'repo_name': 'fametrano/bbt', 'size': '6688'}