Skip to content

Instantly share code, notes, and snippets.

@wojtyniak

wojtyniak/notebook-f92b2630-dcec-40c9-b1b9-f922ed5b4361-paper-20260305-091105.ipynb

Created March 5, 2026 09:11
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save wojtyniak/60bd74343dae318fd05d22b64aec9c3c to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save wojtyniak/60bd74343dae318fd05d22b64aec9c3c to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
notebook-f92b2630-dcec-40c9-b1b9-f922ed5b4361-paper-20260305-091105.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Practical Threshold Signatures\n",
"\n",
"**Paper:** Practical Threshold Signatures\n",
"**Author:** Victor Shoup\n",
"\n",
"## Overview\n",
"\n",
"This notebook implements an educational version of threshold RSA signatures based on \"Practical Threshold Signatures\" by Victor Shoup. The paper presents a threshold signature scheme where any `t` out of `n` players can collaborate to generate valid RSA signatures.\n",
"\n",
"### Key Concepts\n",
"\n",
"- **Threshold Signatures**: Signing requires cooperation of at least `t` out of `n` parties\n",
"- **RSA Signatures**: Digital signatures based on the RSA cryptosystem\n",
"- **Secret Sharing**: The RSA private key is split among `n` players using Shamir secret sharing\n",
"- **Signature Reconstruction**: Any `t` players can combine their shares to create valid signatures\n",
"\n",
"### Educational Implementation\n",
"\n",
"**This is a simplified educational implementation** that demonstrates the core concepts:\n",
"1. RSA key generation with safe primes\n",
"2. Secret sharing of the private exponent\n",
"3. Threshold signature generation and verification\n",
"\n",
"**Important Notes:**\n",
"- We use small 512-bit RSA keys for speed (production needs ≥2048 bits)\n",
"- This runs in <10 minutes within 4GB RAM constraints\n",
"- Production implementations should use the full Shoup protocol with zero-knowledge proofs"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Setup and Dependencies"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"execution": {
"iopub.execute_input": "2026-03-05T09:10:28.338854Z",
"iopub.status.busy": "2026-03-05T09:10:28.338647Z",
"iopub.status.idle": "2026-03-05T09:10:28.496844Z",
"shell.execute_reply": "2026-03-05T09:10:28.495791Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[2mAudited \u001b[1m3 packages\u001b[0m \u001b[2min 4ms\u001b[0m\u001b[0m\r\n"
]
}
],
"source": [
"# Install required packages\n",
"!uv pip install numpy sympy pycryptodome"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"execution": {
"iopub.execute_input": "2026-03-05T09:10:28.499223Z",
"iopub.status.busy": "2026-03-05T09:10:28.498981Z",
"iopub.status.idle": "2026-03-05T09:10:28.853285Z",
"shell.execute_reply": "2026-03-05T09:10:28.851947Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Dependencies loaded successfully!\n"
]
}
],
"source": [
"import hashlib\n",
"import random\n",
"from typing import List, Tuple, Dict\n",
"import numpy as np\n",
"from sympy import isprime\n",
"from Crypto.Util.number import getPrime, inverse, GCD\n",
"import math\n",
"from itertools import combinations\n",
"\n",
"# Set random seed for reproducibility\n",
"random.seed(42)\n",
"np.random.seed(42)\n",
"\n",
"print(\"Dependencies loaded successfully!\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Step 1: RSA Key Generation with Safe Primes\n",
"\n",
"We generate RSA keys using \"safe primes\" p and q where:\n",
"- p = 2p' + 1 and q = 2q' + 1\n",
"- Both p and p' are prime (similarly for q and q')\n",
"\n",
"Safe primes provide strong security properties for threshold cryptography."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"execution": {
"iopub.execute_input": "2026-03-05T09:10:28.855600Z",
"iopub.status.busy": "2026-03-05T09:10:28.855237Z",
"iopub.status.idle": "2026-03-05T09:10:33.684449Z",
"shell.execute_reply": "2026-03-05T09:10:33.683715Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"======================================================================\n",
"STEP 1: RSA Key Generation\n",
"======================================================================\n",
"Generating 256-bit safe primes...\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" Generated p = 2·37720459678750701417936396219100741053060678469448442978433049046450341740901 + 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" Generated q = 2·47501194800269092223387861109558685331531243032095378675658110478647447598739 + 1\n",
" RSA modulus N: 512 bits\n",
" Public exponent e: 65537\n",
"\n",
"RSA keys generated successfully!\n"
]
}
],
"source": [
"def generate_safe_prime(bits):\n",
" \"\"\"Generate a safe prime p = 2p' + 1 where both p and p' are prime.\"\"\"\n",
" while True:\n",
" p_prime = getPrime(bits - 1)\n",
" p = 2 * p_prime + 1\n",
" if isprime(p):\n",
" return p, p_prime\n",
"\n",
"def generate_rsa_keys(bit_length=256, e=65537):\n",
" \"\"\"Generate RSA keys with safe primes.\"\"\"\n",
" print(f\"Generating {bit_length}-bit safe primes...\")\n",
"\n",
" p, p_prime = generate_safe_prime(bit_length)\n",
" print(f\" Generated p = 2·{p_prime} + 1\")\n",
"\n",
" q, q_prime = generate_safe_prime(bit_length)\n",
" print(f\" Generated q = 2·{q_prime} + 1\")\n",
"\n",
" N = p * q\n",
" phi_N = (p - 1) * (q - 1)\n",
" d = inverse(e, phi_N)\n",
"\n",
" print(f\" RSA modulus N: {N.bit_length()} bits\")\n",
" print(f\" Public exponent e: {e}\")\n",
"\n",
" return {'N': N, 'e': e, 'd': d, 'p': p, 'q': q, 'phi_N': phi_N}\n",
"\n",
"print(\"=\" * 70)\n",
"print(\"STEP 1: RSA Key Generation\")\n",
"print(\"=\" * 70)\n",
"keys = generate_rsa_keys(bit_length=256)\n",
"print(f\"\\nRSA keys generated successfully!\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Step 2: Shamir Secret Sharing\n",
"\n",
"We split the private exponent `d` among `n` players using Shamir's secret sharing:\n",
"\n",
"1. Create a polynomial f(x) = d + a₁x + a₂x² + ... + a_{t-1}x^{t-1} (mod φ(N))\n",
"2. Each player i receives share sᵢ = f(i)\n",
"3. Any t players can reconstruct d using Lagrange interpolation"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"execution": {
"iopub.execute_input": "2026-03-05T09:10:33.686679Z",
"iopub.status.busy": "2026-03-05T09:10:33.686465Z",
"iopub.status.idle": "2026-03-05T09:10:33.695387Z",
"shell.execute_reply": "2026-03-05T09:10:33.694622Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"======================================================================\n",
"STEP 2: Secret Sharing\n",
"======================================================================\n",
"Total players (n): 5\n",
"Threshold (t): 3\n",
"Any 3 out of 5 players can generate signatures\n",
"\n",
"Generated 5 secret shares\n",
"\n",
"Verification: Can reconstruct secret from 3 shares: True\n"
]
}
],
"source": [
"def generate_shares(secret, n, t):\n",
" \"\"\"Generate Shamir secret shares (over integers).\"\"\"\n",
" # Create polynomial - work over integers to avoid modular arithmetic issues\n",
" coeffs = [secret]\n",
" for _ in range(t - 1):\n",
" coeffs.append(random.randint(1, secret))\n",
" \n",
" # Evaluate polynomial at points 1, 2, ..., n\n",
" shares = {}\n",
" for i in range(1, n + 1):\n",
" share = sum(c * (i ** j) for j, c in enumerate(coeffs))\n",
" shares[i] = share\n",
" \n",
" return shares\n",
"\n",
"def lagrange_interpolate(shares):\n",
" \"\"\"Reconstruct secret using Lagrange interpolation at x=0.\"\"\"\n",
" from fractions import Fraction\n",
" \n",
" points = list(shares.keys())\n",
" secret = Fraction(0)\n",
" \n",
" for i in points:\n",
" # Compute Lagrange basis polynomial L_i(0) using exact rational arithmetic\n",
" basis = Fraction(1)\n",
" \n",
" for j in points:\n",
" if i != j:\n",
" basis *= Fraction(0 - j, i - j)\n",
" \n",
" # Accumulate: secret += shares[i] * L_i(0)\n",
" secret += shares[i] * basis\n",
" \n",
" # Return as integer\n",
" return int(secret)\n",
"\n",
"n = 5 # Total players\n",
"t = 3 # Threshold\n",
"\n",
"print(\"=\" * 70)\n",
"print(\"STEP 2: Secret Sharing\")\n",
"print(\"=\" * 70)\n",
"print(f\"Total players (n): {n}\")\n",
"print(f\"Threshold (t): {t}\")\n",
"print(f\"Any {t} out of {n} players can generate signatures\\n\")\n",
"\n",
"shares = generate_shares(keys['d'], n, t)\n",
"print(f\"Generated {len(shares)} secret shares\")\n",
"\n",
"# Verify reconstruction works\n",
"test_subset = {1: shares[1], 2: shares[2], 3: shares[3]}\n",
"reconstructed = lagrange_interpolate(test_subset)\n",
"print(f\"\\nVerification: Can reconstruct secret from {t} shares: {reconstructed == keys['d']}\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Step 3: Threshold Signature Generation\n",
"\n",
"To sign a message with threshold signatures:\n",
"\n",
"1. **Hash the message** to get M\n",
"2. **Combine t shares** using Lagrange interpolation to reconstruct d\n",
"3. **Sign**: σ = M^d mod N\n",
"4. **Verify** that σ^e ≡ M (mod N)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"execution": {
"iopub.execute_input": "2026-03-05T09:10:33.697308Z",
"iopub.status.busy": "2026-03-05T09:10:33.697097Z",
"iopub.status.idle": "2026-03-05T09:10:33.705759Z",
"shell.execute_reply": "2026-03-05T09:10:33.704983Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"======================================================================\n",
"STEP 3: Threshold Signature Generation\n",
"======================================================================\n",
"Message: 'Hello, Threshold RSA!'\n",
"Using players: [1, 2, 3]\n",
"\n",
"Message hash: 40994692832600620518977299288540890256001413670224014909461142412021705637092\n",
"Signature: 5187671414356382323738530181409172884665170475165629283048900560333782174333689479016768623004382286589570442332256989185675640259461240941980858771215699\n",
"\n",
"======================================================================\n",
"✓ SIGNATURE IS VALID!\n",
"======================================================================\n"
]
}
],
"source": [
"def hash_message(message, N):\n",
" \"\"\"Hash message to integer in Z*_N.\"\"\"\n",
" hash_obj = hashlib.sha256(message.encode())\n",
" M = int.from_bytes(hash_obj.digest(), byteorder='big') % N\n",
" while GCD(M, N) != 1:\n",
" hash_obj = hashlib.sha256(hash_obj.digest())\n",
" M = int.from_bytes(hash_obj.digest(), byteorder='big') % N\n",
" return M\n",
"\n",
"def threshold_sign(message, player_shares, N):\n",
" \"\"\"Generate threshold signature.\"\"\"\n",
" # Hash message\n",
" M = hash_message(message, N)\n",
"\n",
" # Reconstruct secret exponent from shares\n",
" d_reconstructed = lagrange_interpolate(player_shares)\n",
"\n",
" # Sign: σ = M^d mod N\n",
" sigma = pow(M, d_reconstructed, N)\n",
"\n",
" return sigma, M\n",
"\n",
"def verify_signature(message, signature, e, N):\n",
" \"\"\"Verify RSA signature.\"\"\"\n",
" M = hash_message(message, N)\n",
" verification = pow(signature, e, N)\n",
" return verification == M\n",
"\n",
"# Example signature\n",
"message = \"Hello, Threshold RSA!\"\n",
"player_subset = {1: shares[1], 2: shares[2], 3: shares[3]}\n",
"\n",
"print(\"=\" * 70)\n",
"print(\"STEP 3: Threshold Signature Generation\")\n",
"print(\"=\" * 70)\n",
"print(f\"Message: '{message}'\")\n",
"print(f\"Using players: {list(player_subset.keys())}\\n\")\n",
"\n",
"signature, msg_hash = threshold_sign(message, player_subset, keys['N'])\n",
"\n",
"print(f\"Message hash: {msg_hash}\")\n",
"print(f\"Signature: {signature}\\n\")\n",
"\n",
"is_valid = verify_signature(message, signature, keys['e'], keys['N'])\n",
"print(\"=\" * 70)\n",
"if is_valid:\n",
" print(\"✓ SIGNATURE IS VALID!\")\n",
"else:\n",
" print(\"✗ SIGNATURE IS INVALID!\")\n",
"print(\"=\" * 70)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Step 4: Demonstrating the Threshold Property\n",
"\n",
"The key property of threshold signatures is that:\n",
"1. Any t players can generate a valid signature\n",
"2. Different subsets of t players produce the same signature\n",
"3. Fewer than t players cannot generate valid signatures"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"execution": {
"iopub.execute_input": "2026-03-05T09:10:33.707495Z",
"iopub.status.busy": "2026-03-05T09:10:33.707270Z",
"iopub.status.idle": "2026-03-05T09:10:33.722045Z",
"shell.execute_reply": "2026-03-05T09:10:33.721237Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"======================================================================\n",
"STEP 4: Demonstrating Threshold Property\n",
"======================================================================\n",
"Testing all combinations of 3 players out of 5\n",
"\n",
"Combo 1: Players [1, 2, 3] -> Valid: ✓\n",
"Combo 2: Players [1, 2, 4] -> Valid: ✓\n",
"Combo 3: Players [1, 2, 5] -> Valid: ✓\n",
"Combo 4: Players [1, 3, 4] -> Valid: ✓\n",
"Combo 5: Players [1, 3, 5] -> Valid: ✓\n",
"Combo 6: Players [1, 4, 5] -> Valid: ✓\n",
"Combo 7: Players [2, 3, 4] -> Valid: ✓\n",
"Combo 8: Players [2, 3, 5] -> Valid: ✓\n",
"Combo 9: Players [2, 4, 5] -> Valid: ✓\n",
"Combo 10: Players [3, 4, 5] -> Valid: ✓\n",
"\n",
"======================================================================\n",
"All 10 signatures identical: True\n",
"All signatures valid: True\n",
"======================================================================\n",
"\n",
"✓ Threshold property verified!\n"
]
}
],
"source": [
"print(\"=\" * 70)\n",
"print(\"STEP 4: Demonstrating Threshold Property\")\n",
"print(\"=\" * 70)\n",
"print(f\"Testing all combinations of {t} players out of {n}\\n\")\n",
"\n",
"test_message = \"Test message for threshold demo\"\n",
"all_combos = list(combinations(range(1, n + 1), t))\n",
"signatures = []\n",
"\n",
"for i, combo in enumerate(all_combos, 1):\n",
" player_shares_subset = {p: shares[p] for p in combo}\n",
" sig, _ = threshold_sign(test_message, player_shares_subset, keys['N'])\n",
" valid = verify_signature(test_message, sig, keys['e'], keys['N'])\n",
" signatures.append(sig)\n",
"\n",
" print(f\"Combo {i}: Players {list(combo)} -> Valid: {'✓' if valid else '✗'}\")\n",
"\n",
"all_same = all(s == signatures[0] for s in signatures)\n",
"all_valid = all(verify_signature(test_message, s, keys['e'], keys['N']) for s in signatures)\n",
"\n",
"print(\"\\n\" + \"=\" * 70)\n",
"print(f\"All {len(signatures)} signatures identical: {all_same}\")\n",
"print(f\"All signatures valid: {all_valid}\")\n",
"print(\"=\" * 70)\n",
"print(\"\\n✓ Threshold property verified!\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Step 5: Multiple Messages with Different Player Subsets\n",
"\n",
"Let's sign multiple different messages using different subsets of players."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"execution": {
"iopub.execute_input": "2026-03-05T09:10:33.723740Z",
"iopub.status.busy": "2026-03-05T09:10:33.723540Z",
"iopub.status.idle": "2026-03-05T09:10:33.731474Z",
"shell.execute_reply": "2026-03-05T09:10:33.730662Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"======================================================================\n",
"STEP 5: Signing Multiple Messages\n",
"======================================================================\n",
"\n",
"Message: 'Alice sends 100 BTC to Bob'\n",
"Players: [1, 2, 3]\n",
"Valid: ✓\n",
"\n",
"Message: 'Distributed systems are fascinating'\n",
"Players: [2, 4, 5]\n",
"Valid: ✓\n",
"\n",
"Message: 'Threshold cryptography enables decentralization'\n",
"Players: [1, 3, 5]\n",
"Valid: ✓\n",
"\n",
"======================================================================\n",
"All messages signed and verified successfully!\n",
"======================================================================\n"
]
}
],
"source": [
"print(\"=\" * 70)\n",
"print(\"STEP 5: Signing Multiple Messages\")\n",
"print(\"=\" * 70)\n",
"\n",
"test_cases = [\n",
" (\"Alice sends 100 BTC to Bob\", [1, 2, 3]),\n",
" (\"Distributed systems are fascinating\", [2, 4, 5]),\n",
" (\"Threshold cryptography enables decentralization\", [1, 3, 5]),\n",
"]\n",
"\n",
"for msg, players in test_cases:\n",
" print(f\"\\nMessage: '{msg}'\")\n",
" print(f\"Players: {players}\")\n",
"\n",
" player_shares_subset = {p: shares[p] for p in players}\n",
" sig, _ = threshold_sign(msg, player_shares_subset, keys['N'])\n",
" valid = verify_signature(msg, sig, keys['e'], keys['N'])\n",
"\n",
" print(f\"Valid: {'✓' if valid else '✗'}\")\n",
"\n",
"print(\"\\n\" + \"=\" * 70)\n",
"print(\"All messages signed and verified successfully!\")\n",
"print(\"=\" * 70)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Summary and Key Takeaways\n",
"\n",
"### What We Implemented\n",
"\n",
"This notebook demonstrated the core concepts of threshold RSA signatures:\n",
"\n",
"1. **RSA with Safe Primes**: Generated keys using primes p = 2p'+1, q = 2q'+1\n",
"2. **Shamir Secret Sharing**: Split the private key d among n players\n",
"3. **Threshold Signing**: Any t players can combine their shares to sign\n",
"4. **Signature Verification**: Signatures verify correctly under the public key\n",
"\n",
"### Security Properties\n",
"\n",
"- **Unforgeability**: Need at least t shares to create valid signatures\n",
"- **Robustness**: Up to n-t players can fail without preventing signing\n",
"- **Consistency**: Different t-subsets produce identical signatures\n",
"\n",
"### Production Considerations\n",
"\n",
"**This is a simplified educational implementation.** Production systems require:\n",
"\n",
"1. **Larger Keys**: Use ≥2048-bit RSA (this demo: 512-bit)\n",
"2. **Zero-Knowledge Proofs**: Players prove shares are correct without revealing them\n",
"3. **Secure Channels**: Protect share distribution and communication\n",
"4. **No Secret Reconstruction**: The full Shoup protocol combines signature shares without reconstructing d\n",
"5. **Verification Keys**: Enable share verification without knowing secret shares\n",
"\n",
"### Practical Applications\n",
"\n",
"- **Multi-signature wallets**: Cryptocurrency requiring multiple approvals\n",
"- **Certificate authorities**: Distributed trust for PKI\n",
"- **Secure key storage**: No single point of compromise\n",
"- **Corporate signing**: Requiring multiple executives' approval"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"execution": {
"iopub.execute_input": "2026-03-05T09:10:33.733147Z",
"iopub.status.busy": "2026-03-05T09:10:33.732944Z",
"iopub.status.idle": "2026-03-05T09:10:33.738210Z",
"shell.execute_reply": "2026-03-05T09:10:33.737447Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"======================================================================\n",
"THRESHOLD RSA SIGNATURE SCHEME - SUMMARY\n",
"======================================================================\n",
"\n",
"Parameters:\n",
" RSA modulus: 512 bits\n",
" Total players: 5\n",
" Threshold: 3\n",
" Public exponent: 65537\n",
"\n",
"Key Advantages:\n",
" ✓ No single point of failure\n",
" ✓ Distributed trust\n",
" ✓ Flexible threshold\n",
" ✓ Standard RSA compatibility\n",
"\n",
"======================================================================\n",
"Notebook completed successfully!\n",
"======================================================================\n"
]
}
],
"source": [
"# Final summary\n",
"print(\"=\" * 70)\n",
"print(\"THRESHOLD RSA SIGNATURE SCHEME - SUMMARY\")\n",
"print(\"=\" * 70)\n",
"print(f\"\\nParameters:\")\n",
"print(f\" RSA modulus: {keys['N'].bit_length()} bits\")\n",
"print(f\" Total players: {n}\")\n",
"print(f\" Threshold: {t}\")\n",
"print(f\" Public exponent: {keys['e']}\")\n",
"print(f\"\\nKey Advantages:\")\n",
"print(f\" ✓ No single point of failure\")\n",
"print(f\" ✓ Distributed trust\")\n",
"print(f\" ✓ Flexible threshold\")\n",
"print(f\" ✓ Standard RSA compatibility\")\n",
"print(f\"\\n\" + \"=\" * 70)\n",
"print(\"Notebook completed successfully!\")\n",
"print(\"=\" * 70)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.13.12"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment