## 定義 公開鍵暗号方式(public key cryptography)は、暗号化・署名検証に使う鍵と、復号・署名生成に使う鍵が異なる非対称暗号プリミティブで、ランダムオラクルモデルでは「トラップドア一方向置換」としてモデル化される。実用されている構成は主に 2 系統の数学的困難性に依拠する。1 つは**素因数分解**で、大きな合成数を素因数に分解する困難性を利用する RSA(Rivest・Shamir・Adleman)が代表例だ。RSA は暗号化 C ≡ M^e (mod N)、復号 M ≡ C^d (mod N) という単純な代数構造を持つが、この代数構造ゆえに乗法準同型性を持ち、生の RSA は単体では安全でない。実用には OAEP(Optimal Asymmetric Encryption Padding、暗号化用)や PKCS #1/#7(署名用)によるランダム化・パディングが必須となる。もう 1 つは**離散対数**で、素数 p を法とする原始根の冪乗が一方向関数になることを利用する。Diffie-Hellman 鍵確立(1976 年、最初に発表された公開鍵方式)は、双方が一時鍵 g^{R_A}、g^{R_B} を交換し共通のセッション鍵 g^{R_A R_B} を導出する方式で、一時鍵を使えば前方安全性・後方安全性を得られるが、認証機構がないため中間者攻撃に弱い。ElGamal 署名・DSA(Digital Signature Algorithm)は離散対数上の署名方式で、その楕円曲線版である ECDSA が暗号通貨や銀行スマートカードの標準になっている。**楕円曲線暗号(ECC)**は同等の安全性をより短い鍵長で達成でき、ペアリングを使う identity-based cryptosystem(公開鍵=利用者の識別子)にも応用される。公開鍵と利用者を結びつけるには認証局(CA)が発行する証明書が使われ、この仕組みの上に TLS(旧 SSL、1995 年に Kocher と ElGamal が開発)のような実プロトコルが構築される。TLS 1.3(2019 年)は Diffie-Hellman による前方安全性を必須化した。その他、コード署名・PGP/GPG・QUIC も同じ数学的基盤の上に構築される。しきい値暗号(threshold cryptography、鍵を n 人に分散し k 人で復号・署名)や盲署名(blind signature、David Chaum のデジタル現金への応用)は特殊用途プリミティブとして位置づけられる。非対称暗号は同等の安全性を得るのに対称鍵の 2 倍以上のブロック長を要し、Peter Shor のアルゴリズムにより量子計算機が実用化すれば素因数分解・離散対数の双方が容易になるとされる。ただし実際に破られる大半の原因は数学的暗号解読ではなく、乱数生成器の欠陥や副チャネル攻撃(タイミング解析・電力解析)による実装レベルの不備である。(Source: [[@2020__Wiley__Security Engineering 3e - Chapter 5 Cryptography]], ch.5 §5.7〜§5.7.9) ## 横断的知見 - **第5章が数学的基盤として説明するTLS用の公開鍵証明書は、第20章が示すHSM API攻撃の脅威モデルに含まれる具体的な資産の1つである**: 第5章はTLS(旧SSL)を認証局が発行する証明書の上に構築されるプロトコルとして数学的側面から説明するにとどまるが、第20章は、多くのウェブサイトのSSL/TLS秘密鍵が開発者のノートPCに置かれたりクラウド事業者にメモリダンプで抽出されたりしないよう、HSMで保護されていると述べる。これは、本conceptが扱う公開鍵暗号の数学的安全性(素因数分解・離散対数の困難性)が保たれていても、その鍵をどこにどう保管するか(HSMのAPI設計、[[HSM APIセキュリティ]]参照)という運用レベルの課題が独立に存在することを、2つの章を突き合わせて初めて具体的に確認できる。(Source: [[@2020__Wiley__Security Engineering 3e - Chapter 5 Cryptography]] ch.5 §5.7, [[@2020__Wiley__Security Engineering 3e - Chapter 20 Advanced Cryptographic Engineering]] ch.20 §20.5) - **Security Engineering 3e 第5章がRSAを「暗号化・復号の代数構造」として提示する記述と、Mathematics for Computer Science 第8章がRSAを「合同算術(Zn)とEulerの定理から導出する対象」として提示する記述は、同じRSAという方式について相補的な抽象度を与える**: 前者はRSAを C ≡ M^e (mod N)・M ≡ C^d (mod N) という代数構造として天下り的に示し、乗法準同型性ゆえに生のRSAが単体では安全でないためOAEP・PKCS #1/#7によるパディングが実務上必須になるという運用上の注意に主眼を置く。後者は、RSAが Euler の定理 k^φ(n) ≡ 1 (mod n) から出発して初めて「なぜ暗号化・復号の往復が元のメッセージに戻るのか」を証明し、さらに秘密鍵 d の生成に拡張互除法(Pulverizer、[[最大公約数]]参照)が使われることや、素因数分解の困難性という予想がRSAの安全性の根拠であること自体をSAT問題への還元で具体的に論証する。2つの章を突き合わせることで、RSAという1つの暗号方式について「そもそもなぜ正しく動くか(数学的正当性、MCS第8章)」と「実装・運用でなぜ生の代数構造のままでは安全でないか(Security Engineering第5章)」という異なる問いへの答えが揃う。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] ch.8 §8.10〜§8.11, [[@2020__Wiley__Security Engineering 3e - Chapter 5 Cryptography]] ch.5 §5.7) ## 未解決の問い - 量子計算機の実用性について、著者は量子暗号・量子情報理論そのものに強い懐疑を表明している(Bell 検定の代替解釈への言及を含む)。この立場は本書刊行(2020 年)以降の量子計算研究の進展と照らしてどう評価されるか。後続章・後続ソースでの検証が必要。 - 楕円曲線離散対数問題に対するより高速なアルゴリズムの発見(小標数曲線に対する 2013 年の進展など)が、実務上の鍵長選択にどう影響したか、本章は示唆にとどめている。 - ~~TLS の実装レベルの脆弱性...鍵管理・HSMの実装運用は第20章が担う~~ → 第20章はHSM APIへの攻撃(xor-to-null-key攻撃・差分プロトコル攻撃)を詳述するが、それらは主に銀行のPIN/対称鍵管理を対象としており、TLS秘密鍵の保護に特化したHSM API攻撃の具体例までは踏み込んでいない。TLS秘密鍵に対するHSM API攻撃の実例が別途あるかは未解決のまま残る。 - Mathematics for Computer Science 第8章は、素因数分解が多項式時間で解けないという未証明の予想がRSAの安全性の根拠だと述べ、SAT問題への還元でこの予想の「裏付け」(SATが多項式時間で解けるなら素因数分解も解ける)は示すが、量子計算機(Shorのアルゴリズム)による素因数分解の効率化には触れていない。Security Engineering 3e 第5章は Shor のアルゴリズムに言及し著者が量子計算の実用性に懐疑的な立場を示すが、数学的な素因数分解予想そのものの記述はMCS第8章の方が詳しい。2つのソースの記述を統合した「RSAの安全性の根拠と量子計算機の脅威」の全体像は未整理のまま残る。 ## 関連 - [[@2020__Wiley__Security Engineering 3e - Chapter 5 Cryptography]] — RSA・Diffie-Hellman・ElGamal・DSA・楕円曲線暗号・認証局・TLS の詳細 - [[@2020__Wiley__Security Engineering 3e - Chapter 20 Advanced Cryptographic Engineering]] — TLS秘密鍵をHSMで保護する実務 - [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] — Eulerの定理からのRSAの数学的導出、SAT問題への還元による安全性の議論 - [[ランダムオラクルモデル]] — トラップドア一方向置換としての公開鍵暗号のモデル化 - [[ブロック暗号設計原則]] — 対称鍵暗号との鍵長比較の対比先 - [[HSM APIセキュリティ]] — 公開鍵基盤の鍵material保護に使われるHSMのAPI層の脆弱性 - [[合同算術]] — RSAの正当性の証明に使われるEulerの定理・環Znの基礎理論 - [[最大公約数]] — RSAの秘密鍵生成に使われる拡張互除法(Pulverizer) ## 出典 - Ross Anderson, *Security Engineering: A Guide to Building Dependable Distributed Systems*, 3rd Edition, John Wiley & Sons, 2020, Chapter 5, §5.7. - Ross Anderson, *Security Engineering: A Guide to Building Dependable Distributed Systems*, 3rd Edition, John Wiley & Sons, 2020, Chapter 20, §20.5. - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 8, §8.10〜§8.12.