ハッシュと暗号の可視化

SHA-256 がハッシュ値を作るまでの 64 ラウンドを 1 つずつ、RSA の鍵の生成・暗号化・復号を途中の計算ごとに見せます。1 ビットの違いで値が大きく変わる雪崩効果や、小さい鍵が素因数分解で破られる様子も確かめられます。

ハッシュ値を求める文字列

UTF-8 で 3 バイト（24 ビット）・1 ブロック

SHA-256 ハッシュ値（256 ビット = 16 進数 64 文字）

ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad

①パディング

メッセージの後ろに 1 ビット（0x80 = 10000000）と 0 を付け、最後の 8 バイトにメッセージのビット数を書いて、全体を 512 ビット（64 バイト）のブロックに区切ります。

メッセージ
区切りの 1 ビット（0x80）
0 埋め
メッセージのビット数（64 ビット）

ブロック 1

61a62b63c80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000018

②メッセージスケジュール

ブロックを 32 ビットずつの 16 語 W[0]〜W[15] に分け、残りの W[16]〜W[63] を次の式で作ります。σ はビットを回転・シフトして XOR を取る関数で、ブロックのどのビットも後ろの語に混ざっていくようにします。

W[t] = σ1(W[t−2]) + W[t−7] + σ0(W[t−15]) + W[t−16]（mod 2³²）

色の濃い 16 語がブロックそのもの、薄い 48 語が式で作った語です。押すとそのラウンドへ移ります。

③圧縮関数（64 ラウンド）

作業変数 a〜h に今のハッシュ値（最初のブロックでは初期値 H0）を入れ、64 ラウンドかき混ぜます。各ラウンドでは a と e だけが新しい値になり、ほかは 1 つずつ隣へずれます。色の付いたマスは、前のラウンドから変わったビットです。

ラウンド0 / 64

a6a09e667

bbb67ae85

c3c6ef372

da54ff53a

e510e527f

f9b05688c

g1f83d9ab

h5be0cd19

ラウンドの前です。a〜h には、このブロックの前のハッシュ値が入っています。

H0 = 6a09e667 bb67ae85 3c6ef372 a54ff53a 510e527f 9b05688c 1f83d9ab 5be0cd19

④ハッシュ値の更新

64 ラウンドの後の a〜h を、ブロックの前のハッシュ値に足します（mod 2³²）。最後のブロックの結果をつなげたものが SHA-256 のハッシュ値です。

	前のハッシュ値		64 ラウンド後		新しいハッシュ値
H0	6a09e667	+	506e3058	=	ba7816bf
H1	bb67ae85	+	d39a2165	=	8f01cfea
H2	3c6ef372	+	04d24d6c	=	414140de
H3	a54ff53a	+	b85e2ce9	=	5dae2223
H4	510e527f	+	5ef50f24	=	b00361a3
H5	9b05688c	+	fb121210	=	96177a9c
H6	1f83d9ab	+	948d25b6	=	b410ff61
H7	5be0cd19	+	961f4894	=	f20015ad

⑤雪崩効果

入力を 1 ビット変えるだけで、ハッシュ値はおよそ半分（128 ビット前後）のビットが変わります。似た入力から似たハッシュ値が出ないので、ハッシュ値から入力を推測したり、同じハッシュ値になる別の入力を作ったりできません。

変えるビット7 / 23

0 バイト目: 01100001「a」 → 01100000「`」

元の入力: ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad

1 ビット変えた入力: 89f900390e14d37c405c75244fb086aa35b54c0fb6ec3638c1c21451d4743d11

変わったビット112/ 256（43.8%）

①鍵を作る

2 つの素数 p, q を選び、n = p × q と φ(n) = (p − 1)(q − 1) を計算します。公開指数 e は φ(n) と共通の約数を持たない数にし、e × d を φ(n) で割ると 1 余る d（秘密指数）を求めます。(n, e) が公開鍵、(n, d) が秘密鍵です。

素数 p, q の大きさ

公開指数 e

φ(n) と共通の約数を持つ e や、φ(n) 以上の e は使えません（教科書の例では φ(n) = 3120 が 3 で割り切れ、65537 は φ(n) より大きい）。

p: 616 ビット・素数
q: 536 ビット・素数
n: 3,23312 ビット・p × q
φ(n): 3,12012 ビット・(p − 1)(q − 1)
e: 175 ビット・公開指数
d: 2,75312 ビット・秘密指数

公開鍵（誰に見せてもよい）

(n, e)

秘密鍵（自分だけが持つ）

(n, d)

d の求め方（拡張ユークリッド互除法）

φ(n) と e で割り算を繰り返しながら、各行で r = s·φ(n) + t·e が成り立つように s, t を更新します。r が 1 になった行の t が、e·t ≡ 1（mod φ(n)）を満たします。負なら φ(n) を足して d にします。

商 q	余り r	s	t
	3120	1	0
	17	0	1
183	9	1	-183
1	8	-1	184
1	1	2	-367
8	0	-17	3120

確かめ: e × d mod φ(n) = 1

②暗号化と復号

文字列を UTF-8 のバイト列にし、n より小さい数に収まるように 1 バイトずつの数 m に分けます。暗号化は c = m^e mod n、復号は m = c^d mod n です。

暗号化する文字列

バイト	平文 m	暗号文 c = m^e mod n	復号 c^d mod n
48H	72	3000	72✓
65e	101	1313	101✓
6cl	108	745	108✓
6cl	108	745	108✓
6fo	111	2185	111✓
21!	33	1853	33✓

復号した文字列: Hello!

色の付いた暗号文は、同じ平文から同じ暗号文になったものです。このように何も手を加えない RSA（教科書 RSA）では、暗号文を見るだけで「同じ文字が使われている」ことが分かってしまいます。実際の RSA では、暗号化の前に乱数を混ぜる（OAEP）ので、同じ平文でも毎回違う暗号文になります。

暗号化: 72^17 mod n

指数を 2 進数（5 ビット）にし、上の桁から順に「2 乗する」「その桁が 1 なら底（72）を掛ける」を繰り返します（繰り返し二乗法）。5 回ほどの掛け算で済むので、指数が大きくてもすぐ計算できます。

桁	2 乗	掛けた後
1	1	72
0	1951	—
0	1160	—
0	672	—
1	2197	3000

結果: 3000

復号: c^d mod n

指数を 2 進数（12 ビット）にし、上の桁から順に「2 乗する」「その桁が 1 なら底（3000）を掛ける」を繰り返します（繰り返し二乗法）。12 回ほどの掛け算で済むので、指数が大きくてもすぐ計算できます。

桁	2 乗	掛けた後
1	1	3000
0	2561	—
1	2197	2146
0	1524	—
1	1282	1963
1	2866	1453
0	60	—
0	367	—
0	2136	—
0	733	—
0	611	—
1	1526	72

結果: 72

③公開鍵から秘密鍵を破ってみる

RSA の安全性は「n から p と q を求める（素因数分解する）のが難しい」ことに頼っています。p と q が分かれば、①と同じ計算で d が求まります。ここではポラードのロー法で n の素因数分解を試みます（最大 10 秒）。必要な計算の回数は、小さい方の素因数の平方根（この鍵ではおよそ 8 回）くらいです。

使い方

「ハッシュ（SHA-256）」では、入力した文字列のハッシュ値ができるまでを、パディング・メッセージスケジュール・64 ラウンドの圧縮関数の順に見られます。ラウンドは 1 つずつ進めたり戻したりできます。
「雪崩効果」では、入力の好きなビットを 1 つだけ変えて、ハッシュ値がどれだけ変わるかを確かめられます。
「公開鍵暗号（RSA）」では、素数の大きさを選んで鍵を作り、文字列を暗号化・復号します。表の行を押すと、そのブロックのべき乗の計算を 1 手ずつ表示します。
「n を素因数分解する」で、公開鍵だけから秘密鍵を求めてみられます。素数を大きくすると見つからなくなります。

ハッシュ関数とは

ハッシュ関数は、どんな長さのデータからも決まった長さの値（SHA-256 なら 256 ビット）を作る関数です。同じ入力からは必ず同じ値が出る一方、ハッシュ値から元の入力を求めることや、同じハッシュ値になる別の入力を見つけることは、現実的な時間ではできないように作られています。ファイルが改ざんされていないかの確認、パスワードの保存（実際には専用の遅いハッシュ関数を使います）、デジタル署名、ブロックチェーンなどに使われています。

RSA のしくみ

RSA は、暗号化に使う鍵（公開鍵）と復号に使う鍵（秘密鍵）が別々の暗号です。e × d ≡ 1（mod φ(n)）となるように d を選ぶと、オイラーの定理から (m^e)^d ≡ m（mod n）が成り立ち、暗号化した値を秘密鍵で元に戻せます。n は公開されていますが、n から p と q を求める素因数分解が非常に難しいため、φ(n) も d も分かりません。

注意事項

計算はすべてブラウザの中で行い、入力した文字列や鍵はどこにも送信・保存しません。
RSA の鍵は学習用の小さいもので、パディング（OAEP）も使っていません。実際の暗号化や署名には使わないでください。実際の RSA では n が 2048 ビット以上の鍵を使います。
SHA-256 は FIPS 180-4 のとおりに計算しており、結果は他のツールのハッシュ値と一致します。