RC2のπテーブルはどのように作成されたか

RC2のπテーブルはどのように作られたか

リサーチノート · 暗号理論

ロン・リベストが設計したRC2暗号のキー・スケジューリングに含まれる256個の数値はπに由来すると言われていましたが、その方法は公開されていませんでした。πの数字を3桁ずつ使用するカードシャッフルが、RC2の2つのテーブルを完全に再現することがわかりました。

RC2のテーブルには256個のエントリがあります。このグリッドは、πの数字を3桁ずつ使用して0から255までの数値をシャッフルすることで再構築されています。カードがリベストが公開したテーブルと一致すると、そのカードは暗くなります。

256/256一致

RC2のキー・スケジューリング・テーブルであるPITABLEは、このページでπから再構築されました。シャッフル方法はこちら

要約

質問

RFC 2268では、RC2の256バイトテーブルPITABLEは「PIの数字に基づいている」とされていますが、その方法は示されていません。また、同じ文書にある2番目のテーブルの起源も不明です。1996年、RSA Data Securityのエンジニアが、このテーブルがどのようにπから生成されたのかを公に問いかけました。

回答

πの10進数から導かれるフィッシャー–イェーツ・シャッフルは、両方のテーブルを正確に再現します。各ドローでは3桁が読み取られ、結果に偏りが出るようなドローは破棄されます。PITABLEは先頭の3から始まり、2番目のテーブルは4桁後に始まります。

確信度

元の方法である可能性が非常に高いですが、リベストがどのようにその規則に至ったかは文書化されていません。広範な調査でも、これ以前の公開された回答は見つかっていません。これはRC2のセキュリティには影響しません。

1質問

RC2は、ロン・リベストが1980年代後半に設計したブロック暗号です。キーを、実際に暗号化に使用されるより長い内部キーに変換するために、各バイトは固定テーブルを通過します。これは0から255までの数値が並べ替えられたものです。RC2の実装はすべて同じ256個の数値を持っています。

このようなテーブルは、設計者が原理的には弱点を隠すことができる場所です。暗号学者は、そのようなテーブルをπのような公開定数から導出し、その導出方法を示すことで、誰でもテーブルを再構築でき、手作業で選ばれたものではないことを確認できるようにすることで、その疑念を防ぎます。これらは「袖の中には何もない（nothing-up-my-sleeve）」数値として知られており、導出が公開されている場合にのみ安心感を与えます。

RC2は定数を名付けましたが、その導出方法は公開しませんでした。リベストの仕様であるRFC 2268では、このテーブルを「PIの数字に基づいた『ランダムな』バイトの配列」と呼び、方法を示さずに印刷しています[1]。1996年にこの暗号のコードが流出した際、RC2を所有していたRSA Data Securityのエンジニアは、テーブルがπからどのように生成されたのかを公に未解決の問題としてリストアップしました[2]。回答はなく、LibTomCryptのような一部の実装では、流出したコードのコメント「probably derived somehow from pi」がそのまま残っています[3][4]。セクション5にその経緯が記されています。このノートは、テーブルを正確に再現する構築方法を示します。

2回答

0から255までの番号が付けられた256枚のカードが順番に並べられていると想像してください。2番目のカードから最後のカードまで、各カードを、それ以前の任意の位置にあるカードと交換します。これがフィッシャー–イェーツ・シャッフルであり、公平にシャッフルするための標準的な方法であり、秘密ではありませんでした。公開されていなかったのは、ランダム性がどこから来たかです。カードは、πの10進数を各ドローで正確に3桁ずつ読み取り、最初の3から開始すると、テーブルが完全に再現されます。図1に最初のステップを示します。

シャッフル、ステップバイステップ

Shuffle21712024919625221181237

Published21712024919625221181237

256個の位置のうち最初の8個を10進数で示しています。すべて256個が一致します。

このアニメーションにはJavaScriptが必要です。最初のステップは次のとおりです。314を読むので、カード1は場所314 mod 2 = 0と交換されます。159を読むので、カード2は場所159 mod 3 = 0と交換されます。265を読むので、カード3は場所265 mod 4 = 1と交換されます。そして続きます。

図1。 構築の最初の9ステップと、その結果。各ステップで、πの次の3桁が新しいカードの配置を決定します。利用可能な場所の数で割った余りです。

正確に書き出すと、構築はアルゴリズム1です。破棄ステップはドローを公平に保ちます。利用可能な場所の数が1,000を均等に割り切れない場合、上位の値（例えば240個の場所がある場合に960から999）に入るドローは破棄され、3桁が再度読み取られます。シャッフル全体でこれは21回発生し、そのうち2回はπの762番目の10進数にある「ファインマン・ポイント」として知られる6つの9の連続で発生します[a]。合計でシャッフルは828桁を使用します。

アルゴリズム1。 PITABLEの構築

入力: d = 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, …
       (πの10進数)

rand(n):
  ループ
    x ← dの次の3桁   // 0…999
    if x < n · ⌊1000 / n⌋:
      return x mod n
    // それ以外の場合はxを破棄

S ← [0, 1, …, 255]
for i ← 2 to 256:
  j ← rand(i)
  swap S[j], S[i − 1]
return S                // = PITABLE

なぜ隠されたままだったのか。 2014年、リベストは彼のMD2ハッシュ関数がπテーブルを同じシャッフルで構築していることを確認しました[5]。しかし、MD2は各ドローが必要とする最小限の桁数しか読み取りません。選択肢が10個までなら1桁、100個までなら2桁、それ以降は3桁です。RC2に適用すると、MD2の正確な規則は256個のエントリのうち1つしか一致せず、偶然よりも良いものではないため、明白なテストではテーブルが無関係であると示唆されたでしょう。必要な唯一の変更は、毎回3桁を読むことです。

3検証

アルゴリズム1は、RFC 2268のPITABLEを256個すべての位置で再現します。図2は、これをブラウザ上で、5つのもっともらしい代替案とともに実行し、すべての出力を公開されたテーブルと比較します。

この方法はリベストのテーブルを再現するか？

代替案：

…256個の位置が公開されたテーブルと一致
公開されたテーブルと同じ数異なる数16進数で表示、RFCに印刷されている通り

この図にはJavaScriptが必要です。再現スクリプトは、同じ比較と表1の制御を実行します。

図2。 各方法は、このページで、整数算術で計算されたπとeを使用して実行され、その256個の出力はRFC 2268に印刷されたテーブルと位置ごとに比較されます。ランダムなシャッフルは約1つの位置と一致するでしょう。

この一致は、広範な検索で偶然見つかるようなものではありません。256個の数値の順列は約10^507通りあります。この規則を見つけた検索では、約100,000個の候補（4桁のソース、数値を描画する7つの方法、6つのシャッフル順序、300の開始点、およびテーブルとその逆の両方）を試しましたが、完全に一致したのは1つだけでした。それは最も単純なものです。桁ソースや各ドローの幅を変更するバリアントは、偶然レベルにまで低下します。破棄ステップを削除すると、最初の112回のドローは変更されず、29個の初期位置はドリフトする前に一致したままです（表1）。

表1。アルゴリズム1および近隣の代替案によって再現されたPITABLEの位置。

表1の16進数方法は、2026年10月17日に「RC2 PITABLEはどのようにpiの数字から生成されたか」と尋ねられた際に、GoogleのAI Overviewがそれを説明したため含まれています。その作業例は24 3f 6aから始まりますが、公開されたテーブルはd9 78 f9から始まります。

結果は発見後2回再現されました。1つはRFCからの1段落の説明のみで、最初のものにアクセスせずに書かれた別の実装によるもので、もう1つは独自のπ計算とRFCの新しいコピーを使用した3番目の実装によるものです。

42番目のテーブル

RFC 2268のセクション6には、0から255までの別の置換、RFCのTable[]（ここではバージョンテーブルと呼ばれる）が印刷されています。これはRC2-CBCのRC2Versionパラメータとして1から255ビットの実効キー長をエンコードしており、PKCS #5および関連標準で使用されています[6]。RFCは、それが「キー展開フェーズに現れるテーブルと同じではない」と述べているだけです[1]。これは、πの5桁目（5926…）から始まるアルゴリズム1を、最初の桁からではなく開始したものです。これは256個すべての位置で一致し、21回の破棄ドローで828桁を使用しました。したがって、RFCの両方のテーブルは、2つの開始点から実行される1つのジェネレーターによって生成できます。

4.12番目のテーブルが他に見られる場所

同じ256バイトはRC2以外でも見られます。Lotus NotesとそのサーバーであるDominoは、パスワードを256バイトの「マジックテーブル」でハッシュしており、パスワード回復ツールは4世代のフォーマット（Notes 5ハッシュからNotes 8.5 IDファイルまで）でこれを持っています[7]。Quarkslabは2013年に、この配列がOpenSSLのRC2コード内のものであることを指摘しました[8]。これはPITABLEではなくバージョンテーブルなので、上記のシャッフルはNotesパスワードの背後にあるテーブルも説明しています（図3）。これはセクション5の歴史と一致します。RC2はLotusのために設計されました。

bd 56 ea f2 a2 f1 ac 2a b0 93 d1 9c 1b 33 fd d0 …

• Lotus Notesの「マジックテーブル」、パスワード回復ツールが持つもの
• RFC 2268 §6、RC2のバージョンテーブル
• アルゴリズム1、πの5桁目（5926…）から開始

256バイトの最初の16バイト。3つのソースすべてがすべての位置で一致しています。

図3。 1つのテーブル、3つの場所。Lotus–RC2の同一性はQuarkslabによるもので、πへのステップはセクション4から導かれます。

5テーブルが説明されなかった経緯

1. 1987–89年
   リベストがRC2を設計 Lotusのため、Notesにエクスポート可能な暗号化が必要でした。
2. 1996年
   コードが流出 sci.cryptに「probably derived somehow from pi」というコメントとともに投稿されました。RSAのRobert Baldwinが、誰がそれを知ることができるのかを公に尋ねました。
3. 1998年
   RFC 2268 両方のテーブルを「PIの数字に基づいている」と印刷し、方法を示しませんでした。
4. 2013年
   Hacker NewsとCryptography Stack Exchangeでのコメント MD2とRC2のテーブルがまだ説明されていないことを指摘しました。
5. 2014年
   MD2のテーブル リベストからのメールで説明されました。RC2に適用すると、偶然にしか一致しません。

5.1エクスポート可能な暗号、1987–1989年

1980年代、米国は強力な暗号の輸出を武器と同様に管理しており、国家安全保障局（NSA）が技術審査を行っていました。Lotus Developmentは、Ray Ozzieの会社Iris Associatesが開発した暗号化機能を内蔵したビジネスアプリケーションNotesを販売する準備をしており、標準的な暗号であるDESを使用しても輸出ライセンスを取得できませんでした。Steven Levyの記述によると、NSAは1987年半ばに代替案の評価に同意しました。Lotusはリベストを雇い、彼は数週間でRC2を設計しました。Lotusはその作業に支払い、RSA Data Securityが権利を保有しました[9]。（リベストの1997年のドラフト仕様には「Created 1987」と日付が付けられており、1998年の共著論文では設計日は1989年とされています[1][10]）。

［画像: Ray Ozzieが地図を背景に話している］

図4。 Lotus Notesの作成者であるRay Ozzie。NSAとの輸出交渉を主導しました（2011年撮影）。

リベストはNSAに設計を提出し、NSAは「いくつか微調整」を求めました。交渉を主導したOzzieは、リベストに当然の質問をしました。

「彼らがそれを弱めるようなことをしていないと、どうやってわかるのですか？」
Ray OzzieからRon Rivestへ、Levy[9]による回想

リベストはその提案を技術的に健全だと判断し、採用しました。Levyの記述では、それらが何であったかは述べられていません。

［画像: フォート・ミード、メリーランド州にあるNSA本部の航空写真］

図5。 NSA本部、フォート・ミード、メリーランド州。同庁は商用暗号の輸出を審査しました。

5.2秘密と開示、1989–1998年

1989年、NSAはキー長を32ビットに制限したRC2のエクスポートライセンスをLotusに口頭で提供しました。1992年、Software Publishers Associationを通じて交渉された合意により、最大40ビットのキーを持つRC2またはその姉妹であるRC4を使用した小売ソフトウェアの迅速な輸出承認が得られました[11]。その条件は、RSAとそのライセンシーが設計を秘密にすることでした[9]。RC2は、テーブルを含む内部構造が公開されないまま、世界中の商用製品に搭載されました。

［画像: RSAコードと「this shirt is classified as a munition and may not be exported from the United States」という文字が印刷されたTシャツ］

図6。 当時の輸出規制に対する抗議Tシャツ。RSAコードが印刷され、「munitionとして分類されており、米国から輸出できません」と宣言されていました。

/

• 256エントリの置換テーブル、おそらくπから何らかの方法で派生
  */
  static const unsigned char permute[256] = {
  217,120,249,196,
  25,221,181,237,
  40,233,253,121,
  74,160,216,157,
  198,126, 55,131,
  43,118, 83,142,
  ...

図7。 1996年1月、sci.cryptに匿名で投稿されたソースのテーブル（抜粋、行は折り返し）。[3]

1996年1月29日、RC2のソースコードがUsenetグループsci.cryptに匿名で投稿されました。デバッグツールへの言及から、リバースエンジニアリングされたことが示唆されました。4日後、RSA Data SecurityのRobert Baldwinは、暗号に関する未解決の技術的問題リストをcypherpunksメーリングリストに投稿しました。最初の質問はテーブルに関するものでした。

「置換がPIの数字の何らかのシーケンスに基づいているかどうかをどのように判断できますか？」
R. W. Baldwin, “RC2 technical questions”, 1996年2月2日[2]

スレッドに回答はありませんでした。1998年3月、リベストはRC2をRFC 2268として公開し、構築方法を示さずにテーブルを完全に印刷しました[1]。同年に彼が共著した論文では、テーブルが「πの展開から導出された」とだけ述べられています[10]。

5.3関連テーブル、2014年に説明

リベストのMD2ハッシュ関数には、その仕様によると「piの数字から構築された」独自の256バイト置換が含まれており[12]、これも長年説明されていませんでした。2013年、Hacker NewsとCryptography Stack Exchangeのコメント投稿者は、MD2とRC2の両方のテーブルが説明されていないことを指摘しました[13]。2014年、Stack ExchangeのユーザーがリベストからMD2の構築方法をメールで入手し、投稿しました[5]。私たちは、それをRC2に適用した公開された作業を見つけられませんでした。

［画像: Ron Rivestの肖像］

図8。 RC2とMD2の設計者、Ron Rivest。

6考察

3つの主張を区別すると役立ちます。計算によって確立されたこと： アルゴリズム1は公開された両方のテーブルを正確に再現しており、公開スクリプトで誰でも確認できます。強く支持されているが証明されていないこと： これがテーブルが元々作成された方法、またはそれに非常に近い方法であるということです。両方のテーブルのすべてのエントリに一致する短い規則があり、その近隣のバリアントが失敗する場合、他の方法では説明が困難であり、その規則はリベスト自身の文書化されたMD2シャッフルに1つの変更を加えたものです。確立されていないこと： リベストがどのようにそれに到達したか、彼がこれに落ち着く前に他の規則や開始点を試したかどうかを含みます。テーブルだけではそれを教えてくれません。

最後の点は、「袖の中には何もない」という問題に関係します。256個のエントリは1つずつ選ばれたわけではありません。それらはπに適用された短い規則から導かれています。これは、エントリごとに選ばれたテーブルよりも意図的な選択の余地を大幅に減らしますが、完全に排除するわけではありません。設計者は、原理的にはいくつかの単純な規則や開始点を試して、1つを保持した可能性があります。2番目のテーブルの異なる開始点は、そのような選択が行われたことを示しています。ここにあるものは何も、NSAの1987年の変更が何であったか、またはそれがこのテーブルに触れたかどうかを教えてくれません。

この結果はRC2のセキュリティには影響しません。この暗号は長い間非推奨となっていますが、古いPKCS #12証明書ファイルにはまだ存在しており、公開テーブルの起源を知っても、それが弱くなることも強くなることもありません。リベストはおそらく常に方法を知っていたでしょう。ここでの主張は、それが公開されていなかったというだけです。

以前の作業の検索は、1996年のcypherpunksアーカイブとsci.cryptの議論の一部（Google Groupsの検索はレート制限されていました）、1998年の設計論文、日本の政府のCRYPTREC評価、Cryptography Stack Exchange、Hacker News、GitHub、X、IACR ePrint、および中国語、ロシア語、日本語での検索をカバーしました。質問が何度か尋ねられ、一度も回答されていないことがわかりました。Semantic Scholarと印刷のみのソースは完全に検索できなかったため、到達できなかったソースに以前の説明が存在する可能性があります。修正は歓迎され、ここにクレジットされます。

7方法に関する注記

この結果は、正確に検証可能な回答を持つ、長年放置されてきた問題に対処するためのAIエージェントの使用に関する実験から生まれました。2026年10月、Anthropicは、そのモデルClaudeがNIST楕円曲線シードを1997年と1998年のタイムスタンプでシードされた標準Cライブラリ乱数ジェネレーターにたどったと報告しました[14][15]。私は、長年未解決の質問を収集し、解決策が自己検証できるかどうかでランク付けし、最も有望なものをAIコーディングエージェントに割り当てるパイプラインを設定しました。

RC2のテーブルが最初の結果でした。エージェントであるClaudeは、リベストのπテーブルの1つが説明されていた場合、もう1つも同じ方法で説明できる可能性があると推論し、3桁の規則を見つけました。OpenAIのCodexは、セクション3で説明されている独立した2番目の実装を書き、その後の他の「πから導出された」テーブルのスキャンで2番目のRC2テーブルを見つけました。これらのどれも信頼に頼る必要はありません。リポジトリのスクリプトはπを計算し、RFCに対して両方のテーブルを1秒未満でチェックします。

注記

1. a.ファインマン・ポイントは、πの762番目の10進数から始まる999999のシーケンスです。アルゴリズム1は、240個の場所の中から選択する際にこれに到達し、960以上の値はすべて破棄されるため、両方の999が破棄されます。

参考文献

1. [1]R. L. Rivest. A Description of the RC2(r) Encryption Algorithm. RFC 2268, March 1998. Also see the earlier draft-rivest-rc2desc-00 (1997), dated “Created 1987”.
2. [2]R. W. Baldwin. RC2 technical questions. Cypherpunks mailing list, 2 February 1996.
3. [3]Anonymous. RC2 source code, posted to sci.crypt, 29 January 1996. Archived copy in the funet cryptography collection.
4. [4]LibTomCrypt. src/ciphers/rc2.c, line 34 (accessed 18 October 2026).
5. [5]mikeazo. Answer to “How is the MD2 hash function S-table constructed from Pi?”, quoting an email from R. L. Rivest. Cryptography Stack Exchange, question 11935, 2 August 2014.
6. [6]K. Moriarty, B. Kaliski, A. Rusch. PKCS #5: Password-Based Cryptography Specification Version 2.1. RFC 8018, January 2017, Appendix B.2.3.
7. [7]hashcat, tools/test_modules/lib/lotus.py (modes 8600, 8700, 9100); John the Ripper, lotus5 and lotus85 formats.
8. [8]Quarkslab. Have you ever played with Domino? 19 December 2013.
9. [9]S. Levy. Crypto: How the Code Rebels Beat the Government, Saving Privacy in the Digital Age. Viking, 2001.
10. [10]L. R. Knudsen, V. Rijmen, R. L. Rivest, M. J. B. Robshaw. On the Design and Security of RC2. Fast Software Encryption, LNCS 1372, 1998, pp. 206–221.
11. [11]RSA Laboratories. What is RC2? In Frequently Asked Questions about Today’s Cryptography, 1998 (archived mirror).
12. [12]B. Kaliski. The MD2 Message-Digest Algorithm. RFC 1319, April 1992.
13. [13]andrewcooke. Comment on Hacker News, 24 December 2013. See also the comments on question 11935 cited above.
14. [14]Anthropic. Claude reveals ECDSA curve origins. 16 October 2026.
15. [15]F. Valsorda. The NIST Elliptic Curves Seeds Bounty Has Been Claimed. 16 October 2026.
16. [16]K. Hamadeh. rc2-pi-tables: reproduction script and table data. GitHub, 2026. MIT licence.

このノートの引用

Hamadeh, K. (2026). How RC2’s π table was made. https://khalidhamadeh.com/writing/rc2-pi-table

コードとデータ。 再現スクリプトと両方のテーブルは github.com/khalid-hamadeh/rc2-pi-tables にあります[16]。

画像（Wikimedia Commons経由、リサイズおよびグレースケール表示）。図4：Ray Ozzie, Joi Ito, 2011, CC BY 2.0。図5：NSA本部, National Security Agency, パブリックドメイン。図6：Munitions T-shirt, Adam Back, CC0。図8：Ronald L. Rivest, Ronald L. Rivest, CC BY-SA 4.0。

改訂履歴。 2026年10月17日：初版公開。2026年10月18日：暗号の歴史を追加、アニメーションウォークスルーを追加、フォーマットを改訂、計算されたものと推測されたものの区別を明確化。

著者について。 Khalid HamadehはHarbor Software GroupのHead of Growthであり、サイドでソフトウェアを開発しています。このノートは、正確に検証可能な回答を持つ古いパズルの検索から生まれました。その他の執筆