ShamirSharing CipherLab - 座標平面とバイトで追うシャミアの秘密分散

English

Day123 - 生成AIで作るセキュリティツール200

ShamirSharing CipherLabは、Shamirの秘密分散を座標平面とバイト表で試す教材です。まず「(2, n)を可視化する」で1個と2個のシェアを比べ、次に「(k, n)を手で追う」で一般のしきい値法を計算します。「バイトで見る」は文字列をバイトに変換して分け、「確かめる」は不正な入力やシェアの変更を調べます。

ShamirとBlakleyは1979年に秘密分散方式を独立に提案しました。本ツールが扱うのは、Shamirの多項式による方式です。ラグランジュ補間はその復元計算に使います。Blakleyの幾何学的な方式は扱いません。¹Blakleyの方式は、Day126 BlakleySharing CipherLabで、本ツールと同じ例を使って試せます。

Shamirの(k,n)しきい値法では、秘密情報sからn個のシェアを作り、n人に1個ずつ渡します。次の二つが条件です。

① n人のうちk人がシェアを持ち寄れば、秘密情報sを復元できます。

② k−1人がシェアを持ち寄っても、sを復元できません。さらに、sについての情報は一切わかりません。係数を0も含めて一様に選ぶと、k−1個から見た秘密候補はすべて同じ確率で残ります。

「(2, n)を可視化する」と「(k, n)を手で追う」のsには架空の数を、「バイトで見る」の短い文には練習用の文を入力してください。実際に使っているパスワード、シードフレーズ、鍵の分割や保管には、この教材を使わないでください。シェアの書式、印刷、QR、保管の方法は扱いません。

---

🌐 デモページ

👉 ShamirSharing CipherLabを開く

通常のブラウザーで開けます。HTMLファイルをfile://で直接開いても動作します。計算と入力はブラウザー内で完結し、外部には送信しません。

---

📸 スクリーンショット

以下はライトモードの画面です。画面右上の「◐」ボタンでダークモードに切り替えられます。

(2, n)を可視化する

(k, n)を手で追う

k−1個の候補

バイトで見る

確かめる

英語の同じ5状態はEnglish READMEに掲載しています。 スクリーンショットのバイト表は撮影時の係数で計算した一例です。実際に「バイトで見る」を開くたび、乱数係数とシェア値は変わります。

✨ できること

段階	操作	見えること
(2, n)を可視化する	1個のシェアから秘密候補を切り替え、2個目を加える	1点を通る複数の直線と、2点から決まる1本の式
(k, n)を手で追う	GF(p)で分散・復元し、k−1個の候補を重ねる	シェアの計算、ラグランジュ係数、秘密候補
バイトで見る	UTF-8の短い文をGF(2⁸)で分け、k個から戻す	バイトごとの多項式、XOR、選択数に応じた復元計算
確かめる	改ざん・x=0・足りない枚数の模型を比べる	検査なし、CRC-32、秘密中の指紋の違い

書籍と同じく、Dをディーラー、sを秘密情報、vᵢ=f(i)を番号iのシェアと呼びます。(k,n)は、n個のシェアを作り、そのうち任意のk個以上でsを復元する設定です。pは計算に使う素数で、p>max(s,n)とします。多項式の次数は最大k−1で、k=1は0次、k=2は1次、k=3は2次です。既定のk=3ではf(x)=s+a₁x+a₂x² (mod p)を使い、選んだ3点からラグランジュ補間でs=f(0)を求めます。

書籍でいうシェアは値vᵢです。本ツールのボタン#i (i,vᵢ)では、#iがシェア番号、括弧内が復元に使う「番号と値」の組です。冒頭の(k,n)は復元に必要な個数と作る個数で、点の座標とは異なります。たとえばn=7ならシェアは7個で、番号は#1～#7です。

「分散段階」の表では、f(i)に各番号を代入した計算式・合計・mod pの結果を示します。その下に、復元用の組(i,vᵢ)を番号順に並べます。n=7なら#1～#7の7個を作り、係数やpを変えると結果も更新されます。

「(k, n)を手で追う」タブの既定例はp=13, k=3, n=5, f(x)=5+4x+2x²です。復元用の組は(1,11), (2,8), (3,9), (4,1), (5,10)です。#1, #2, #3から計算するラグランジュ係数は(3,10,1)、各項の寄与は(7,2,9)で、和を13で割った余りが秘密5です。2個だけなら13個の候補が残ります。

係数は0も許します。そのため多項式は「次数k−1以下」と書きます。k=1を選ぶと全員のシェアが秘密そのものになり、「分けていない（ただのコピー）」ことがわかります。

(2, n)から始める理由

GF(13)は0〜12の13個の整数値を使う有限体です。足し算・引き算・掛け算の結果を13で割った余りに戻し、0以外の数で割るときは逆元を掛けます。13が素数なので、0以外の数には必ず逆元があります。「(2, n)を可視化する」ではp=13に固定し、f(x)=s+a₁x (mod 13)を使います。タブ冒頭の「前提知識」で、整数の世界で計算したシェアとの違いを説明します。

導入タブはp=13, n=5, s=5, a₁=4で始まり、f(x)=5+4x (mod 13)からシェアを作ります。「分散段階」では、ディーラーDがvᵢ=f(i)を計算して各管理人へ渡します。折りたたみを開くと、v₁=f(1)=(5+4×1) mod 13=9からv₅=f(5)=(5+4×5) mod 13=12まで、計算と配布先を確認できます。

「復元段階」は、初期状態で管理人#3の組(3,4)を選んでいます。シェアそのものは値v₃=4です。復元では管理人番号i（＝#i）とシェア値vᵢを組にして(i,vᵢ)と表します。たとえば(1,9)は管理人番号1（＝#1）とシェア9の組です。#3の1点だけなら、s=0としてa₁=10と決めた別の式も通ります。候補s=0～12のどれにも式が1本ずつあり、係数を一様に選べば候補の確率は変わりません。管理人#1の(1,9)を加えると、式はf(x)=5+4x (mod 13)に決まり、s=f(0)=5を復元できます。

ディーラーのsとa₁は折りたたみ内で変更できます。参加者が1個のシェアだけを持つ場面では、これらを知らないものとして考えます。座標平面は0始まりで、横がシェア番号x、縦がシェア値yです。マウスを重ねると座標(x,y)が表示されます。

1個のシェアを考える図では、普通の座標平面に(3,4)を通る3本の直線を描きます。各直線とy軸の交点はf(0)、つまり秘密候補sで、図では0・5・12と異なります。これは1点だけでは直線が決まらないことを示す図です。

GF(13)でもf₀(x)=10xとf₅(x)=5+4xは別の式です。どちらもf(3)=4ですが、f₀(0)=0、f₅(0)=5です。候補が複数あるのは1点だけでは式が決まらないためです。秘密候補sを選ぶと、a₁=(y−s)÷x (mod 13)からその点を通る式を求めます。s=0ならf(x)=10x (mod 13)で、x=0,1,2を代入した値は0,10,7です。画面の直線は関係をつかむための図です。GF(13)で式を評価できるのは整数のx=0～12だけで、線上の途中の位置に有限体の値はありません。

📚 『暗号技術のすべて』を片手に試す

『暗号技術のすべて』9.2節（P652–661）を開きながら、数値例をツールへ入力できます。最初に(2,n)の一次式を試し、続いて一般の(k,n)でシェアの作成と補間を追います。書籍の(3,5)の例も再現できます。

本書	ツールで試すこと
P652–654	(2,n)の一次式を最初のタブで試す。1個のシェアでは13個の秘密候補が残り、2個では1個に決まる。ディーラーDがシェアvᵢ=f(i)を各管理人に渡す過程も確認する。
P655–657	3点(a,A),(b,B),(c,C)の補間を、「(k, n)を手で追う」の(xᵢ,yᵢ)とλᵢ(0)に対応づける。2個だけ選んだときに残る候補と、3個選んだときの復元計算を比べる。
P658–659	本書の数値例を入力する。p=17, k=3, n=5, s=13, a₁=10, a₂=2とすると、f(1)…f(5)=8,7,10,0,11。#1, #3, #5を選んでs=13に戻ることを確認する。
P660–661	「確かめる」で、不正なシェアと検証の必要性を見る。本書のVSSなどの拡張は、このツールのCRCや指紋の模型とは機能が異なる。

ツールの初期値は操作しやすいGF(13)の別例です。本書の数値例を試した後は「既定の例に戻す」で戻せます。

📖 使い方

1. 「(2, n)を可視化する」の分散段階を開き、ディーラーがv₁…vₙを計算して各管理人へ渡す流れを確認します。復元段階の①ではシェアを1個選び、同じ点を通る直線の切片を切り替えます。②で2個目を選ぶと、式と秘密が1つに決まります。
2. 「(k, n)を手で追う」ではp, k, n, s, a₁…を設定し、分散段階の表で代入式と各シェアを読みます。係数は手で入力するか、「係数を乱数で決める」で選び直せます。
3. 復元段階の①でk−1個のシェアを選び、秘密候補を切り替えるか「全部を重ねる」を押します。②でk個選ぶと、ラグランジュ補間の表とf(0)が表示されます。整数のxで求めたGF(p)の値と、実数上の曲線のガイドを区別して読みます。
4. 「バイトで見る」ではUTF-8で32バイト以内の文を入力し、2≤k≤n≤8で分けます。バイト位置を選んで係数と各シェアの計算を確認します。復元段階では0個からシェアを選び、k個未満の式と、k個揃ったときの補間表を比べます。
5. 「確かめる」では、シェアの変更、x=0、枚数不足の固定例を見ます。改ざんのカードでは検査を切り替えます。3つのカードは固定のMEET AT DAWNを使い、「バイトで見る」に入力した文には連動しません。

画面右上の「?」には、操作手順、活用例、GF(2⁸)の掛け算の固定例、入力と保存の扱いをまとめました。しきい値法の根拠と出典は、ヘルプ内の「座学」を開いて読めます。

「バイトで見る」で増える処理

本書P652–661はGF(p)の数でShamir方式を説明します。「バイトで見る」は、その考え方をPC上の短い文字列へ広げる教材です。GF(2⁸)は256で割った余りの計算ではなく、AESと同じ既約多項式を使う有限体です。画面にも各段階の説明を置きました。

1. 入力した文をUTF-8へ変換します。日本語などは1文字が複数バイトになるため、上限は文字数ではなく32バイトです。
2. 各バイト位置jの元の値sⱼから、別々の多項式Fⱼ(X)を作ります。係数はcrypto.getRandomValuesから各列で独立に選びます。同じ番号iで計算した値を全バイト分並べたものがシェア#iです。画面でバイト位置を選ぶと、その回の係数と#1〜#nの計算結果を追えます。
3. 復元段階でシェアを1個ずつ選びます。既定のk=3なら、先頭バイトの未知数はs₀, a₁,₀, a₂,₀の3個です。1個のシェアからは式が1本、2個からは2本しか得られず、s₀は00～FFのどれにもなれます。3個揃うと各シェア番号からλᵢ(0)を計算し、シェア値との積をXORして先頭バイトを戻します。同じ補間係数を残りのバイト位置にも適用します。
4. 復元結果をまず16進で表示します。正しいUTF-8なら文としても表示し、制御文字はエスケープします。文字表示だけで復元結果を判断しないためです。

GF(2⁸)では足し算がXORで、掛け算には既約多項式z⁸+z⁴+z³+z+1を使います。固定例{57}×{13}={FE}の8回の掛け算と、表示専用のlog/exp表の説明はヘルプにあります。この固定例は、画面で作るシェアの乱数係数とは連動しません。シェアのファイル形式や保管・受け渡しは、この教材の範囲に含めていません。

0x11Bとバイトごとの式

(k,n)=(3,5)なら、バイト位置jごとにFⱼ(X)=sⱼ⊕a₁,ⱼX⊕a₂,ⱼX²を作ります。sⱼは元のバイト、a₁,ⱼとa₂,ⱼは独立に選んだ乱数です。X=1,2,3,4,5を代入したFⱼ(i)が、各シェア#iのj列になります。k=3がFⱼの次数の上限を2にし、n=5が評価する番号の個数を5にします。画面の表は暗号学的乱数を毎回引き直すため、開くたびに値が変わります。

計算方法だけを示す固定例では、s₀={4D}、a₁,₀={57}、a₂,₀={13}とします。#2の列0はX={02}、X²={04}を代入し、{57}·{02}={AE}、{13}·{04}={4C}を求めて、{4D}⊕{AE}⊕{4C}={AF}です。#4なら{57}·{04}={47}、{13}·{10}={2B}なので{4D}⊕{47}⊕{2B}={21}です。ここに置いた係数は説明用で、画面が引いた乱数とは異なります。

このFⱼ(X)と、バイトの掛け算に使う法多項式m(z)=z⁸+z⁴+z³+z+1は別の式です。Xはシェア番号を代入する変数で、zは1バイトをビット列から多項式へ読み替えるための記号です。たとえばバイト0x57はz⁶+z⁴+z²+z+1を表します。Fⱼ(2)のX²やa₂,ⱼX²を計算する際に、バイト同士の積をm(z)で割った余りへ戻します。Fⱼ(X)全体をm(z)で割るわけではありません。

m(z)の係数が1の次数は8、4、3、1、0です。次数8から0までの係数を並べると1 0001 1011₂、16進数では0x11Bです。8ビットの値を左へ1ビットずらして最上位ビットがあふれたときは、z⁸≡z⁴+z³+z+1 (mod m)を使います。この下位8ビットが0x1Bで、実装の還元処理に現れます。

法多項式には8次の既約多項式を選びます。m(z)で割った余りの集合が256個の元を持ち、0以外の元に逆元ができるためです。逆元があれば、シェアの復元で使うラグランジュ補間の分母を割れます。8の素因数は2だけなので、z²⁵⁶≡z (mod m)とgcd(m,z¹⁶−z)=1の二条件で既約性を検証できます。GF(2)では引き算もXORなので、z¹⁶ mod m=0x5Eからz¹⁶−z=0x5Cとなります。ユークリッド互除法の余りは0x37→0x05→0x01で、最大公約数は1です。

8次の既約多項式はほかにもあります。本ツールがこの式を採用した理由は、NIST FIPS 197の4.2節で定めるAESのGF(2⁸)と同じ掛け算を示すためです。AESの暗号化手順をシェアの作成に使うという意味ではありません。

🔬 仕組みと限界

GF(p)ではλᵢ(0) = Πⱼ≠ᵢ xⱼ/(xⱼ−xᵢ)、s = Σᵢ λᵢ(0)yᵢです。GF(2⁸)でも同じ補間を行いますが、足し引きはXORです。バイトの掛け算と0x11Bの関係は前節で説明しました。表示するlog/exp表の生成元{03}はSLIP-39の参照実装で使われ、{03}の位数255と{02}の位数51は付属テストでも検算します。

実データの分割・復元には、表引きをしない8回のシフトとマスクによる掛け算を使います。CVE-2023-25000は表引きのタイミングが問題になった実例です。ただしJavaScriptの実行環境で定数時間は保証できません。教育用のブラウザー実装であり、実運用の秘密分散器ではありません。

CRC-32は書き写しの誤りを見つけられますが、書き換えた人がCRCを再計算すれば通ります。秘密に付けたSHA-256の先頭4バイトは、戻った値の不一致を高い確率で見つけますが、悪いシェアの持ち主を特定しません。改ざん者は元の秘密を知らないため、任意の文を狙って復元させることはできず、ずらす量だけを決められます。この模型でDAWN→DUSKを見せられるのは、観客に元の秘密が見えているためです。

座学の出典は画面の各節に一次資料・二次資料を分けて示しました。Shamirの原論文は Communications of the ACM 22(11), 612–613 (1979), DOI:10.1145/359168.359176です。Blakleyの原論文は Safeguarding Cryptographic Keys（1979）, DOI:10.1109/MARK.1979.8817296で、本文を確認しました。ラグランジュ補間はHAC 12.71と、IPUSIRON『暗号技術のすべて』9.2節（P652–661）をあわせて参照できます。Tompa & Wollの本文は未確認で、書誌の年・号は資料間で1988年1(2)と1989年1(3)に割れています。

🔄 Day070と先行例との関係

観点	Day070 VisualCryptography CipherLab	Day123 ShamirSharing CipherLab
方式	Naor・Shamirの視覚暗号（1994）	Shamirのしきい値法（1979）
秘密	白黒画像の画素	GF(p)の数、GF(2⁸)のバイト
戻し方	2枚を重ねて目で見る	ラグランジュ補間で計算する
扱うしきい値	(2,2)を体験	(k,n)を変え、k−1枚の候補を描く
シェアの大きさ	画素が広がり、重ねるとコントラストが落ちる	秘密と同じ大きさ（理想的）

観点	調べた範囲の先行例	この教材で追加する体験
可視化	動画・スライド・Wolframの図	秘密候補を重ね、補間後の式と比べる
手計算	codex32のGF(32)用の紙の道具	小さなGF(p)で補間表を追い、GF(2⁸)へ移る
落とし穴	多くの実装は拒否や検査を行う	わざと無防備な模型と守る実装を並べる

先行例の調査は網羅的ではありません。Day070は画像、Day123は数とバイトで、別の方式を体験します。

🎯 ユースケース

このツールならではの使い方：

• 数学の授業：学習者が(1,11)(2,8)を固定し、13本の候補を重ねる。候補が1本も優先されない理由を目で追える。
• 有限体の入門：f(x)=5+4x+2x²の整数値21,35とGF(13)の値8,9を並べる。余りから秘密が漏れる場合と漏れない場合を比較できる。
• 実装レビューの演習：係数の抽選範囲に0を含める理由と、x=0をシェア番号として受け付けない理由を調べる。
• 謎解き・CTFの題材：作者が公開値だけの問題を作り、参加者がλ=(3,10,1)から秘密5を計算する。本物の認証情報は使わない。
• プログラミングの授業：2枚を素の実装へ渡すと2DB1…の誤ったバイトが出る例から、しきい値とUTF-8の検査を設計する。

ほかに、『暗号技術のすべて』9.2節（P652–661）の副読、Day070の視覚暗号との比較、Day118 SHA-256 Byte Inspectorで指紋の仕組みの学習、Day029 OTP Animationと情報理論的安全性を比べる教材にも使えます。

本物の秘密を紙に分けて保管するときは、Day124 Scatter Seedsを使えます。Shamir方式で紙のシェアを作り、すべての組み合わせで復元を検査してから印刷します。

🔒 入力と実装上の注意

• 保存：言語と明暗のみ。入力した文や係数をlocalStorageやURLに置かない。
• 通信：アプリの計算は外部通信を行わず、connect-src 'none'のCSPを設定。
• 入力：UTF-8で32バイト、GF(p)の値は0以上p未満。IMEの変換中は再計算しない。
• 復元：本物の補間関数はx=0、重複x、k未満、長さ不一致を拒否。無防備な模型は別ファイルに分離。
• 限界：異なる分割から混ぜたシェアの正しさや、誰が改ざんしたかはこの教材だけでは証明しない。

🧪 テスト

Node.js 22以上でnpm testを実行します。依存パッケージは不要です。GitHub Actionsでもpushとpull requestの両方で実行します。python test/interface.browser.pyはPython Playwrightがある環境でChromium・Firefoxを使い、file://の操作と320/390/1280pxを検査します。

範囲	主な検査
A GF(2⁸)	65,536組の掛け算一致、FIPS 197の2例、逆元255個、生成元の位数
B GF(p)	既定の5シェア、3組のλ、13候補、係数の抽選範囲、整数値、k=1
C 分割と補間	固定乱数の既知共有、10組すべての3-of-5復元、ランダム往復
D 落とし穴	改ざん・CRC・指紋、x=0、k不足、固定ベクターの全項目
E 静的・UI	CSP、保存項目、禁止API、日英辞書、SHA-256の原本一致、画面幅と操作

期待値はtest/vectors.jsonを読み込みます。固定乱数はi番目のバイトが(37·i+11) mod 256です。これはテスト専用で、画面の分割にはcrypto.getRandomValuesを使います。

📁 ディレクトリー構造

各行の#以降は役割です。作業用の.work/はGitに含めません。

|-- .github/workflows/test.yml # Node 22のCI
|-- LICENSE # MITライセンス
|-- README.md # 日本語の説明とハブ用YAML
|-- README.en.md # 英語の説明
|-- package.json # テストコマンド
|-- index.html # 4タブの画面とCSP
|-- style.css # 座標平面と画面の配色・レイアウト
|-- theme-init.js # 最初の描画の前に明暗を決める
|-- messages.js # 日英の辞書
|-- app.js # DOM、復元表、候補図と実数曲線
|-- intro.js # (2,n)の一次式と秘密候補の直線図
|-- gf-core.js # 有限体と補間の純関数
|-- pitfalls.js # 無防備な実装の模型と検査
|-- sha256-core.js # Day118由来の指紋用SHA-256
|-- test/core.test.js # 既知値と計算のテスト
|-- test/structure.test.js # CSPと辞書などの静的テスト
|-- test/theme-init.test.js # 明暗の初期判定と読み込み位置のテスト
|-- test/readme.test.js # 日英READMEとファイル一覧のテスト
|-- test/interface.browser.py # file://と画面操作のブラウザーテスト
|-- test/vectors.json # 参照実装から写した期待値
|-- assets/ja/light/hand.png # 日本語・ライトの手計算
|-- assets/ja/light/intro.png # 日本語・ライトの(2,n)導入
|-- assets/ja/light/bytes.png # 日本語・ライトのバイト表
|-- assets/ja/light/pitfalls.png # 日本語・ライトの落とし穴
|-- assets/ja/light/candidates.png # 日本語・ライトの候補
|-- assets/ja/dark/hand.png # 日本語・ダークの手計算
|-- assets/ja/dark/intro.png # 日本語・ダークの(2,n)導入
|-- assets/ja/dark/bytes.png # 日本語・ダークのバイト表
|-- assets/ja/dark/pitfalls.png # 日本語・ダークの落とし穴
|-- assets/ja/dark/candidates.png # 日本語・ダークの候補
|-- assets/en/light/hand.png # 英語・ライトの手計算
|-- assets/en/light/intro.png # 英語・ライトの(2,n)導入
|-- assets/en/light/bytes.png # 英語・ライトのバイト表
|-- assets/en/light/pitfalls.png # 英語・ライトの落とし穴
|-- assets/en/light/candidates.png # 英語・ライトの候補
|-- assets/en/dark/hand.png # 英語・ダークの手計算
|-- assets/en/dark/intro.png # 英語・ダークの(2,n)導入
|-- assets/en/dark/bytes.png # 英語・ダークのバイト表
|-- assets/en/dark/pitfalls.png # 英語・ダークの落とし穴
|-- assets/en/dark/candidates.png # 英語・ダークの候補

💻 動作環境

最近のChromium・Firefoxで確認しています。file://でも動作します。スクリーンショットとブラウザーテストにはPython Playwrightを使いました。アプリ本体は外部ライブラリー、WebAssembly、外部フォントを使いません。

📄 ライセンス

MIT Licenseです。sha256-core.jsは同じ作者のDay118から、先頭のMIT表示を含めて同じバイト列で取り込みました。

---

🛠️ このツールについて

本ツールは、「生成AIで作るセキュリティツール200」プロジェクトの一環として開発されました。 このプロジェクトでは、AIの支援を活用しながら、セキュリティに関連するさまざまなツールを制作・公開しています。

🔗 プロジェクトの案内

Footnotes

1. Blakleyの方式（1979）は、各シェアを超平面とし、所定数の超平面の交点から秘密を求めます。以前のDay070 VisualCryptography CipherLabは、NaorとShamirの視覚暗号（1994）を使い、画像のシェアを重ねて目で復元します。複数のシェアを使う点は共通ですが、Blakley方式とは別の構成です。 ↩