暗号初心者です。というか算数苦手です。ChatGPT の力を借りながら ed25519 に対応したシャミアの秘密計算をやります。シャミアの秘密分散法 (Shamir’s Secret Sharing) は、多項式を用いた数学的な手法で、秘密情報を複数のシェアに分割し、それらのうち一定数以上のシェアが集まったときに元の秘密情報を復元できるようにする方法です。
環境
- python 3.10
- FastAPI
- HTML（tailwind）
コード準備
まずは以下のライブラリを pip install -r requirements.txt からインストールしてください。
fastapi
uvicorn
pycryptodome
pydantic
symbol-sdk-python
ライブラリを活用して秘密計算部分を作成します。
from Crypto.Protocol.SecretSharing import Shamir
def split_private_key_for_shamir(key: str) -> list[bytes]:
"""
秘密鍵をシャミア向けに分割する(ライブラリの仕様上 16bytes 迄しか扱えないため)
"""
if len(key) != 64:
raise ValueError("The key must be a 64-character hex string.")
key_bytes1 = bytes.fromhex(key[:32])
key_bytes2 = bytes.fromhex(key[32:])
return [key_bytes1, key_bytes2]
def generate_shamir_keys(key: str) -> list[tuple[int, int, str]]:
"""
シャミアの秘密分散法を使って秘密鍵を分割する
"""
# 秘密鍵を分割
splited_key = split_private_key_for_shamir(key)
# シャミアの秘密分散法を使って秘密鍵を分割
shamirs = [Shamir.split(3, 5, k, None) for k in splited_key]
# splited_key の index と シャミアの index + 分割された秘密鍵
r: list[tuple[int, int, str]] = []
# 保管用の配列を作成
for i, shamir in enumerate(shamirs):
[r.append((i, idx, s.hex())) for idx, s in shamir]
return r
def recover_shamir_keys(shares: list[tuple[int, int, str]]) -> str:
"""
シェアから復元する
"""
s1 = []
s2 = []
for i, idx, s in shares:
if i == 0:
s1.append((idx, bytes.fromhex(s)))
continue
if i == 1:
s2.append((idx, bytes.fromhex(s)))
continue
raise Exception(f"Invalid index: {i}")
k1 = Shamir.combine(s1, None)
k2 = Shamir.combine(s2, None)
return f"{k1.hex().upper()}{k2.hex().upper()}"
テストできるように簡単に API 化と操作用の HTML を用意してみます。
from fastapi import FastAPI, HTTPException
from pydantic import BaseModel
from typing import List, Tuple
from server.service.key import ${なにか適当なキー生成ライブラリを使ってくださいな}
from server.service.shamir import generate_shamir_keys, recover_shamir_keys
from fastapi.responses import FileResponse
import os
app = FastAPI()
class KeyShares(BaseModel):
shares: List[Tuple[int, int, str]]
@app.post("/generate_shamir_keys")
def generate_keys():
key = generate_new_private_key()
try:
shamir_keys = generate_shamir_keys(key)
return {"original_key": key, "shamir_keys": shamir_keys}
except ValueError as e:
raise HTTPException(status_code=400, detail=str(e))
@app.post("/recover_shamir_keys")
def recover_keys(key_shares: KeyShares):
try:
recovered_key = recover_shamir_keys(key_shares.shares)
return {"recovered_key": recovered_key}
except Exception as e:
raise HTTPException(status_code=400, detail=str(e))
script_dir = os.path.dirname(os.path.abspath(__file__))
static_dir = os.path.join(script_dir, "static", "index.html")
@app.get("/")
async def read_root():
return FileResponse(static_dir)
後は遊ぶための HTML を用意します
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Shamir Secret Sharing</title>
<script src="https://cdn.tailwindcss.com"></script>
</head>
<body class="bg-gray-100 min-h-screen flex items-center justify-center p-4">
<div
class="bg-white p-8 rounded shadow-md w-full max-w-4xl min-h-64 flex flex-col items-center justify-center gap-4"
>
<h1 class="text-2xl font-bold mb-4">Shamir Secret Sharing</h1>
<button
id="generate-key-button"
class="bg-blue-500 hover:bg-blue-700 text-white font-bold py-2 px-4 rounded mb-4"
>
Generate Key
</button>
<div id="original-key-container" class="mb-4 hidden w-full">
<p class="font-bold">Original Key:</p>
<p id="original-key" class="bg-gray-200 p-2 overflow-hidden overflow-ellipsis rounded"></p>
</div>
<div id="shamir-keys-container" class="flex flex-col gap-2 w-full hidden">
<label class="font-bold">Shamir Keys:</label>
</div>
<button
id="recover-key-button"
class="bg-green-500 hover:bg-green-700 text-white font-bold py-2 px-4 rounded mt-4 hidden"
>
Recover Key
</button>
</div>
<div id="shamir-keys-container" class="flex flex-col gap-2 hidden">
<label class="font-bold">Shamir Keys:</label>
</div>
<button
id="recover-key-button"
class="bg-green-500 hover:bg-green-700 text-white font-bold py-2 px-4 rounded mt-4 hidden"
>
Recover Key
</button>
</div>
<script>
document
.getElementById("generate-key-button")
.addEventListener("click", async () => {
const response = await fetch("/generate_shamir_keys", {
method: "POST",
});
const data = await response.json();
document
.getElementById("original-key-container")
.classList.remove("hidden");
document.getElementById("original-key").innerText = data.original_key;
const shamirKeysContainer = document.getElementById("shamir-keys-container");
shamirKeysContainer.innerHTML = '<label class="font-bold">Shamir Keys:</label>';
console.log(data.shamir_keys)
data.shamir_keys.forEach((key, index) => {
const inputContainer = document.createElement("div");
inputContainer.classList.add("flex", "items-center");
const input = document.createElement("input");
input.type = "text";
input.value = `${key[0]} ${key[1]} ${key[2]}`;
input.classList.add(
"flex-1",
"bg-gray-200",
"p-2",
"rounded",
"mr-2"
);
inputContainer.appendChild(input);
shamirKeysContainer.appendChild(inputContainer);
});
document
.getElementById("shamir-keys-container")
.classList.remove("hidden");
document
.getElementById("recover-key-button")
.classList.remove("hidden");
});
document
.getElementById("recover-key-button")
.addEventListener("click", async () => {
const inputs = document.querySelectorAll(
"#shamir-keys-container input"
);
const shares = Array.from(inputs).map((input) => {
if (input.value === "") {
return null;
}
const [i, idx, s] = input.value.split(" ");
return [parseInt(i), parseInt(idx), s];
}).filter((share) => share !== null);
console.log("start recover key", shares)
const response = await fetch("/recover_shamir_keys", {
method: "POST",
headers: {
"Content-Type": "application/json",
},
body: JSON.stringify({ shares }),
});
const data = await response.json();
alert(`Recovered Key: ${data.recovered_key}`);
});
</script>
</body>
</html>
試す
早速試してみましょう。鍵とシェアを作成できました。 tuple(int, int, str) となっていますが、本来は tuple(int, str) です。ただし、 ed25519 の鍵が長い為２つに分割しており、この API Server がそれぞれで復元できるように1つ値を追加しています。
試しに復元してみましょう。
問題ありませんでした。また、生成された計5個×2のシェアのうち、それぞれで3つ以上のシェアを保持していれば、元の鍵は復元出来るはずです。ということで２つ消してみて復元しみましょう。
これも問題ないですね。では最後、2つ以上のシェアを消してみましょう。
正しく、復元されずに別の鍵が生成されました。実験成功！... だと思います。
解説
シャミアの秘密分散法を、多項式の例を用いてさらにわかりやすく説明します。ここでは、秘密情報を隠すために二次多項式 $y = ax^2 + bx + c$ を使用します。
秘密を決める
秘密情報を1つの数字（例えば、42）とします。
多項式を作る
秘密情報を「定数項」として多項式を作成します。例えば、秘密情報が c であり、ランダムな係数 a と b を使って次のような多項式を作ります：
y = ax^2 + bx + c
例えば、$a = 3, b = 5, c = 42$ の場合、多項式は次のようになります：
y = 3x^2 + 5x + 42
シェアを作る
x にいろいろな値を代入してシェアを作ります。例えば、次のようになります：
- $x = 1$ のとき: $y = 3(1)^2 + 5(1) + 42 = 50$ → シェアは (1, 50)
- $x = 2$ のとき: $y = 3(2)^2 + 5(2) + 42 = 68$ → シェアは (2, 68)
- $x = 3$ のとき: $y = 3(3)^2 + 5(3) + 42 = 96$ → シェアは (3, 96)
- $x = 4$ のとき: $y = 3(4)^2 + 5(4) + 42 = 134$ → シェアは (4, 134)
- $x = 5$ のとき: $y = 3(5)^2 + 5(5) + 42 = 182$ → シェアは (5, 182)
シェアを配る
これらのシェアを各人に分配します。例えば、5人にそれぞれ (1, 50), (2, 68), (3, 96), (4, 134), (5, 182) を配ります。
秘密を復元する
- 秘密を復元するには、3つ以上のシェアが必要です。例えば、シェア
(1, 50), (2, 68), (3, 96)が集まったとします - これらのシェアを使って元の多項式を復元するために、ラグランジュ補間法を用います
- ラグランジュ補間法を使うと、多項式の各係数を求めることができます
ラグランジュ補間法の具体例
ラグランジュ補間法を使って、多項式 $y = ax^2 + bx + c$ を復元する方法を簡単に説明します。
- シェアのセット:
(1, 50), (2, 68), (3, 96) - ラグランジュ多項式の計算:
L(x) = \sum_{i=1}^{3} y_i \prod_{j=1, j \ne i}^{3} \frac{x - x_j}{x_i - x_j}
- $L_1(x)$ は $x = 1$ のときの項
- $L_2(x)$ は、$x = 2$ のときの項
- $L_3(x)$ は、$x = 3$ のときの項
各係数の計算
- 上記の式にシェアの値を代入して、各係数を計算します
- 結果として、元の多項式 $y = 3x^2 + 5x + 42$ が復元されます
まとめ
上記のように多項式を用いて 2つ以下のシェアでは多項式を完全に復元できないため、秘密が漏れない or 3つ以上のシェアが集まると、多項式が完全に復元でき、秘密が分かる といった仕組みになっています。
ブロックチェーンの秘密鍵への活用を想定して書いていますが、実際に使う際にはこの生成されたシェアをどうやって安全に分割して管理するのか、一部を誰かに預けてしまっても良いものか？等色々悩みどころがあると思いますので、何か良い使い方があれば是非教えて下さい。
コード全体は以下のレポジトリへ格納しました。