1955年、ジョン・ナッシュは米国家安全保障局（NSA）に、自作の暗号化・復号装置の仕組みを送った。公開された手書き資料には、暗号文を装置内部に戻し、2種類の置換・ビット反転を切り替える回路が描かれている。
この記事では、原稿の12〜16ページに説明された回路の一般形を、Pythonの標準ライブラリだけで再現する。
注意：この実装は教育用の歴史的モデルであり、安全な暗号方式ではない。実際の秘密情報の保護には使用しないこと。当時のNSA内部評価も、この原理単独の安全性は限定的だとしている（原本18ページ）。
1. 原典と実装範囲
- 12ページ：送信側・受信側の回路図。P（Permuter-Reverser）、D（Decider）、A（Adder mod 2）、R（Retarder）。
- 13〜15ページ：1周期ごとの演算、暗号文のフィードバック、巡回置換、赤青の2種類の配線、ビット反転。
- 16ページ：鍵は2つの置換の選び方で決まり、鍵の候補数は
[n! × 2^(n+1)]²。 - 18ページ：NSAの内部評価。提案は興味深いが、安全性が限定的という判断。
原稿14ページの赤・青の矢印はある具体的な鍵の図示である。本プログラムはその図の配線を固定して転記したものではなく、ナッシュの一般的な定義に従う2つの巡回置換を鍵から作る。したがって「図と同じ固定鍵の再現」ではなく、「原稿の回路規則を満たす装置の実装」である。
2. 回路をビット単位で定義する
原稿の構成要素を次のように対応づける。
| 記号 | 構成要素 | この実装での処理 |
|---|---|---|
| D | Decider（選択器） | フィードバックされた暗号文のビットが0なら青、1なら赤の置換を選ぶ |
| P | Permuter-Reverser（置換・反転器） | 内部ビット列を巡回路に沿って移動・反転し、1ビットを出力、Dから1ビットを取り込む |
| A | Adder mod 2（加算器） | XORを計算し、その結果を次の周期で出力する |
| R | Retarder（遅延器） | 受信側で暗号文を1周期遅延させ、Pへ与える |
送信側で周期 i の平文ビットを p[i]、装置Pの出力を z[i]、送信ビットを c[i] とすると、以下の順で動く。
c[0] = 0 # Aの初期値（実装上の仮定）
z[i] = P.tick(c[i]) # c[i]をDとPにフィードバック
c[i+1] = p[i] XOR z[i] # Aは結果を次周期に送信
受信側はRによって c[i] を1周期遅らせてPに入力するため、同じ状態・同じ鍵なら同じ z[i] が得られる。従って p[i] = c[i+1] XOR z[i] となり、元の平文を復元できる。実装では受信側のAにも1周期の出力遅延を設け、最後の1ビットを終端処理で回収する。
この初期化では、平文Nビットに対して暗号文はN+1ビットになる。最初のビットはAの初期出力、最後のビットはAに残っている結果である。原文は通信開始時の初期値と終端処理を規定していないので、ここは実行可能にするための追加仕様である。
3. なぜ鍵の数が [n! × 2^(n+1)]² なのか
Pの記憶位置を 0, 1, ..., n とする。0 はDからの入力を受ける特別な位置である。
各置換はこの n+1 個の位置をすべて通る一つの巡回路とする。位置0を始点として固定すると、残りn個の並べ順は n! 通り。さらに、巡回路の各辺について「そのまま移動」か「0と1を反転する」かを選べるので、2^(n+1) 通りである。
置換1つ分の候補数 = n! × 2^(n+1)
青と赤、2つの置換を選ぶ鍵 = [n! × 2^(n+1)]²
これは原文16ページの数え方と対応する。ただし、鍵の候補数が大きいことは暗号強度の証明ではない。また、このプログラムは入力しやすいようパスワードから鍵を決定的に生成するが、その変換もナッシュの原文にはない。パスワードのエントロピーと理論上の鍵候補数は別物である。
Pの更新規則は次のとおりである。
- Dの値に応じて、青または赤の巡回路を選択する。
- 巡回路の最終位置にあったビットを、必要なら反転してPの出力とする。
- その他のビットを巡回路に沿って移動し、各辺の設定に応じて反転する。
- 記憶位置0にDのビットを格納する。
この規則は、原稿15ページの「Dの数字は選択を決めた後で最初の位置に入り、2つの置換はともに全位置を巡回する」という説明に対応している。
4. 実行方法
Python 3.10以降を使用する。追加パッケージは不要。
# 標準ライブラリだけで検証
python nash1955.py selftest
# 巡回路・反転規則と最初の12周期を表示
python nash1955.py demo
# UTF-8テキストを暗号化
python nash1955.py encrypt --key 'example' --text 'こんにちは'
# 上の出力を復号（下記は動作確認済みの出力例）
python nash1955.py decrypt --key 'example' --token 'NASH55:6:121:11dd765e36fb1144c0bf2477857b2280'
復号結果は こんにちは となる。encrypt の --n はDの入力位置以外の記憶位置数で、デフォルトは6。鍵を変えると巡回路と反転規則が変わる。
プログラムからは encrypt(data: bytes, password: str, n=6) と decrypt(token: str, password: str) を直接呼べる。暗号文は NASH55:n:ビット数:16進数 という独自の教育用フォーマットで出力する。
5. 自動同期は常に成立するのか
ナッシュは別の手紙で、この装置が自動同期し、散発的な伝送エラーから回復すると主張した。しかし、原稿の「青・赤の置換がそれぞれ全位置を巡る」だけでは、任意の切り替え系列に対する状態の収束は保証されない。
具体例として、位置が 0,1,2 の3つで、青が (0,1,2)、赤が (0,2,1) の巡回路だとする。Dが 0,1,0,1,... と交互に切り替わる場合、位置1と2に存在する初期状態の差がこの2位置の間を移動し続けることがある。両置換が単独では全位置を一巡するにもかかわらず、混合した操作では状態が消えない。
この反例は selftest に入れてある。通常の同一初期状態からの暗号化・復号が一致することと、異なる内部状態から必ず再同期することは、別の性質である。
暗号文の改ざん検知、メッセージ認証、nonce、現代的な安全性証明も備えていない。ナッシュの発想を実験するためのプログラムであって、実用的な暗号ライブラリの代わりにはならない。
6. ソースコード全文（nash1955.py）
以下は配布する nash1955.py と完全に同一の内容。途中の関数・テスト・CLI処理を省略していない。
#!/usr/bin/env python3
"""1955年ジョン・ナッシュの暗号化・復号装置を再現する教育用モデル。
出典: NSA公開書簡 nash_letters1.pdf, 12〜16ページ。
実用暗号として使用しないこと。初期値・パスワード変換・通信終端は独自の実装規約。
python nash1955.py encrypt --key 'example' --text 'こんにちは'
python nash1955.py decrypt --key 'example' --token 'NASH55:...'
python nash1955.py demo
python nash1955.py selftest
"""
from __future__ import annotations
import argparse
import hashlib
import random
from dataclasses import dataclass
MAGIC = "NASH55"
DEFAULT_N = 6 # Dから入力を受ける最初の場所を除く記憶位置の数
MAX_N = 64 # 教育用CLIの計算量を制限
@dataclass(frozen=True)
class Cycle:
"""長さn+1の巡回路。flip[i]はroute[i]から次へ移るときの反転。"""
route: tuple[int, ...] # (0, ...): 0がD入力を受ける特別な場所
flip: tuple[int, ...] # 最後の反転ビットはPからの出力に作用
def __post_init__(self) -> None:
m = len(self.route)
if m < 2 or self.route[0] != 0 or set(self.route) != set(range(m)):
raise ValueError("routeは0で始まる全記憶位置の巡回路にする")
if len(self.flip) != m or any(bit not in (0, 1) for bit in self.flip):
raise ValueError("flipは記憶位置と同数の0/1を指定する")
class ByteStream:
"""パスワードから置換を再現可能に作るための決定的なバイト列。
これは原文にない補助機能で、暗号学的安全性は保証しない。
"""
def __init__(self, password: str) -> None:
self.seed = hashlib.sha256(
b"nash1955-educational-v1\0" + password.encode("utf-8")
).digest()
self.counter = 0
self.pool = b""
def get(self, count: int) -> bytes:
while len(self.pool) < count:
block = hashlib.sha256(
self.seed + self.counter.to_bytes(8, "big")
).digest()
self.pool += block
self.counter += 1
result, self.pool = self.pool[:count], self.pool[count:]
return result
def below(self, upper: int) -> int:
"""剰余バイアスを避けた[0, upper)の整数。"""
if upper <= 0:
raise ValueError("upper must be positive")
size = max(1, ((upper - 1).bit_length() + 7) // 8)
domain = 1 << (size * 8)
cutoff = domain - domain % upper
while True:
value = int.from_bytes(self.get(size), "big")
if value < cutoff:
return value % upper
def derive_cycles(password: str, n: int) -> tuple[Cycle, Cycle]:
"""2つの(n+1)-巡回置換と各辺の反転を生成する。
原文の鍵空間は [n! * 2^(n+1)]^2。パスワード変換は独自の補完。
"""
if not 1 <= n <= MAX_N:
raise ValueError(f"nは1〜{MAX_N}にする")
if not password:
raise ValueError("空の鍵は指定できない")
rng = ByteStream(password)
cycles = []
for _ in range(2):
tail = list(range(1, n + 1))
# 特別な記憶位置0を先頭に固定した巡回置換はn!通り。
for i in range(len(tail) - 1, 0, -1):
j = rng.below(i + 1)
tail[i], tail[j] = tail[j], tail[i]
flips = tuple(rng.below(2) for _ in range(n + 1))
cycles.append(Cycle((0, *tail), flips))
return cycles[0], cycles[1]
class Permuter:
"""P: Dが選んだ巡回置換・反転を実行し、1ビット出し入れする。"""
def __init__(self, cycles: tuple[Cycle, Cycle]) -> None:
if len(cycles[0].route) != len(cycles[1].route):
raise ValueError("2つの置換の記憶位置数が異なる")
self.cycles = cycles
# 原文に初期値の指定がないため、双方とも0でそろえる。
self.state = [0] * len(cycles[0].route)
def tick(self, d: int) -> int:
if d not in (0, 1):
raise ValueError("Dには0または1が必要")
rule = self.cycles[d] # D=0:青、D=1:赤
route, flip = rule.route, rule.flip
old = self.state
updated = [0] * len(old)
for i in range(len(route) - 1):
updated[route[i + 1]] = old[route[i]] ^ flip[i]
emitted = old[route[-1]] ^ flip[-1]
# 古い数字を取り出したのち、Dの数字を最初の記憶位置に置く。
updated[0] = d
self.state = updated
return emitted
class Sender:
"""送信側。Aはその周期で計算した和を次周期に出力する。"""
def __init__(self, cycles: tuple[Cycle, Cycle]) -> None:
self.permuter = Permuter(cycles)
self.adder_pending = 0 # Aの初期出力。原文で未指定。
self.finished = False
def tick(self, clear_bit: int) -> int:
if self.finished or clear_bit not in (0, 1):
raise ValueError("送信終了後、または0/1以外の入力")
wire_bit = self.adder_pending
p_bit = self.permuter.tick(wire_bit) # 暗号文をDへ帰還
self.adder_pending = clear_bit ^ p_bit
return wire_bit
def finish(self) -> int:
"""Aに残った最後の1ビットを送信する（Pは動かさない）。"""
if self.finished:
raise ValueError("finishを2回呼べない")
self.finished = True
return self.adder_pending
class Receiver:
"""受信側。Rで暗号文を1周期遅らせ、Aも1周期遅れて出力。"""
def __init__(self, cycles: tuple[Cycle, Cycle]) -> None:
self.permuter = Permuter(cycles)
self.retarder: int | None = None
self.adder_pending: int | None = None
self.finished = False
def tick(self, wire_bit: int) -> int | None:
if self.finished or wire_bit not in (0, 1):
raise ValueError("受信終了後、または0/1以外の入力")
if self.retarder is None:
self.retarder = wire_bit
return None
p_bit = self.permuter.tick(self.retarder) # 前周期の暗号文
old_output = self.adder_pending
self.adder_pending = wire_bit ^ p_bit
self.retarder = wire_bit
return old_output
def finish(self) -> int | None:
if self.finished or self.retarder is None:
raise ValueError("finishの呼び出し順序が不正")
self.finished = True
return self.adder_pending
def byte_bits(data: bytes):
"""バイト列を上位ビットから順に並べる。"""
for value in data:
for shift in range(7, -1, -1):
yield (value >> shift) & 1
def pack_bits(bits: list[int]) -> bytes:
"""末尾を0で右詰め（右側パディング）してバイト列へ。"""
out = bytearray()
current = 0
for pos, bit in enumerate(bits):
current = (current << 1) | bit
if pos % 8 == 7:
out.append(current)
current = 0
if len(bits) % 8:
out.append(current << (8 - len(bits) % 8))
return bytes(out)
def unpack_bits(data: bytes, bit_length: int) -> list[int]:
if bit_length < 0 or len(data) != (bit_length + 7) // 8:
raise ValueError("ビット長とデータ長が一致しない")
bits = list(byte_bits(data))
if any(bits[bit_length:]):
raise ValueError("未使用のパディングビットが0ではない")
return bits[:bit_length]
def encrypt(data: bytes, password: str, n: int = DEFAULT_N) -> str:
"""平文バイト列 -> NASH55:n:ビット数:16進表記。"""
sender = Sender(derive_cycles(password, n))
ciphertext = [sender.tick(bit) for bit in byte_bits(data)]
ciphertext.append(sender.finish()) # Aの遅延ぶん、平文より1ビット長い
return f"{MAGIC}:{n}:{len(ciphertext)}:{pack_bits(ciphertext).hex()}"
def decrypt(token: str, password: str) -> bytes:
"""送信側と同じ初期状態・同じ2種類の巡回置換で復号する。"""
fields = token.strip().split(":")
if len(fields) != 4 or fields[0] != MAGIC:
raise ValueError("暗号文形式はNASH55:n:bit_length:hex")
try:
n, bit_length = int(fields[1]), int(fields[2])
raw = bytes.fromhex(fields[3])
except ValueError as exc:
raise ValueError("暗号文の数値または16進表記が不正") from exc
if bit_length < 1 or (bit_length - 1) % 8:
raise ValueError("暗号文は平文のビット数+1でなければならない")
ciphertext = unpack_bits(raw, bit_length)
if ciphertext[0] != 0:
raise ValueError("Aの初期出力ビットが一致しない")
receiver = Receiver(derive_cycles(password, n))
plaintext_bits = []
for bit in ciphertext:
recovered = receiver.tick(bit)
if recovered is not None:
plaintext_bits.append(recovered)
last = receiver.finish()
if last is not None:
plaintext_bits.append(last)
if len(plaintext_bits) != bit_length - 1:
raise AssertionError("内部復号ビット数の不整合")
return pack_bits(plaintext_bits)
def demo(password: str = "demo", n: int = DEFAULT_N) -> None:
"""各周期の送信側の内部値と暗号化・復号を表示する。"""
message = "Nash 1955 / ナッシュ"
cycles = derive_cycles(password, n)
print("原文に対応する巡回路（0がDからの入力位置）")
for d, rule in enumerate(cycles):
print(f"D={d}: route={rule.route}, flip={rule.flip}")
print("\n先頭の12周期: i / 平文x / D=送信ビットc / P出力z / 次の送信ビット")
p = Permuter(cycles)
old_sum = 0
for i, x in enumerate(list(byte_bits(message.encode("utf-8")))[:12]):
d = old_sum
z = p.tick(d)
old_sum = x ^ z
print(f"{i:2d} {x} {d} {z} {old_sum}")
token = encrypt(message.encode("utf-8"), password, n)
print("\n暗号文:", token)
print("復号結果:", decrypt(token, password).decode("utf-8"))
def selftest() -> None:
"""境界条件、再現性、Unicode、周期の遅延、同期の限界をテスト。"""
for n in (1, 2, 3, 6, 12):
key = f"test_{n}"
for payload in (b"", b"\0", b"\xff", b"\x00\xff", bytes(range(256)),
"こんにちは、Nash!".encode("utf-8")):
token = encrypt(payload, key, n)
assert decrypt(token, key) == payload
assert int(token.split(":")[2]) == 8 * len(payload) + 1
assert encrypt(payload, key, n) == token
for length in (1, 2, 7, 64, 128):
payload = random.Random(n * 1000 + length).randbytes(length)
assert decrypt(encrypt(payload, key, n), key) == payload
# 一つの置換を繰り返せば全位置を巡回しても、切替時の収束は保証されない。
# route=(0,1,2) の後に route=(0,2,1) を選ぶと、位置1と2にある
# 初期状態の差は位置0へ移らず、永久に残り得る。
c0 = Cycle((0, 1, 2), (0, 0, 0))
c1 = Cycle((0, 2, 1), (0, 0, 0))
p0, p1 = Permuter((c0, c1)), Permuter((c0, c1))
p1.state[1] = 1
for i in range(100):
p0.tick(i % 2)
p1.tick(i % 2)
assert p0.state != p1.state
valid = encrypt(b"test", "key")
try:
decrypt(valid.replace("NASH55:", "WRONG:"), "key")
except ValueError:
pass
else:
raise AssertionError("壊れたフォーマットを拒否しなかった")
print("selftest: OK (往復・長さ・再現性・不正入力・非収束例)")
def main() -> None:
parser = argparse.ArgumentParser(
description="1955年ナッシュ暗号装置の教育用モデル（安全な暗号ではありません）"
)
actions = parser.add_subparsers(dest="command", required=True)
enc = actions.add_parser("encrypt", help="UTF-8文字列を暗号化")
enc.add_argument("--key", required=True, help="教育用のパスワード")
enc.add_argument("--text", required=True, help="暗号化する文字列")
enc.add_argument("--n", type=int, default=DEFAULT_N,
help="Pの記憶位置の数（D入力位置を除く。既定6）")
dec = actions.add_parser("decrypt", help="暗号文を復号")
dec.add_argument("--key", required=True)
dec.add_argument("--token", required=True, help="NASH55:n:bit_length:hex")
example = actions.add_parser("demo", help="回路内部の動作例を表示")
example.add_argument("--key", default="demo")
example.add_argument("--n", type=int, default=DEFAULT_N)
actions.add_parser("selftest", help="組み込みテスト")
args = parser.parse_args()
try:
if args.command == "encrypt":
print(encrypt(args.text.encode("utf-8"), args.key, args.n))
elif args.command == "decrypt":
print(decrypt(args.token, args.key).decode("utf-8"))
elif args.command == "demo":
demo(args.key, args.n)
else:
selftest()
except (ValueError, UnicodeDecodeError) as exc:
parser.exit(2, f"error: {exc}\n")
if __name__ == "__main__":
main()
7. 動作確認
python nash1955.py selftest は次の事項を検証する。
- 空の平文、1バイト、日本語のUTF-8、0〜255の全バイト値、さまざまな長さのランダムなバイト列の往復。
- 暗号文が常に平文のビット数+1となること。
- 同じパスワード・初期化なら再現可能であること。
- 不正なフォーマットを拒否すること。
- 2つの巡回置換を切り替えた場合の非収束反例。
確認した実行結果：
selftest: OK (往復・長さ・再現性・不正入力・非収束例)
原稿そのものに書かれている仕様は「P・D・A・Rの動作と鍵の数え方」であり、パスワードからの鍵の生成、初期状態のゼロ埋め、暗号文のヘッダー、終端処理は今回のプログラムに固有の仕様である。この区別をなくして「1955年の装置を完全復刻した」と呼ぶのは正確ではない。