RSA暗号・楕円曲線暗号・耐量子計算機暗号の違い：鍵の大きさ・速さ・量子コンピュータへの耐性・移行を比較

どんなときに使うか

RSA暗号

既存の証明書やシステムとの互換性が必要なとき。署名の検証が速いので、検証する側が多い用途にも向きますが、耐量子計算機暗号への移行の計画が必要です。

楕円曲線暗号

現在の新しいシステムで、鍵交換や署名を短い鍵と小さなデータで行いたいとき。ICカードや組込み機器にも向きます。量子コンピュータに備えて、ハイブリッド方式への移行を考えます。

耐量子計算機暗号(ML-KEM・ML-DSA)

長いあいだ秘密にしておく必要のあるデータを守るとき。今記録された暗号文が将来解読される「ハーベスト・ナウ、ディクリプト・レイター」に備えて、まず鍵交換からハイブリッド方式で取り入れます。

理解度チェック

1. 大規模な誤り耐性量子コンピュータが実現したとき、ショアのアルゴリズムによって安全性が大きく損なわれると考えられている暗号はどれか。
2. 大規模な量子コンピュータがまだ実現していない段階から、耐量子計算機暗号への移行を急ぐ理由として、最も適切なものはどれか。
3. 教科書どおりのRSA暗号(平文 m をそのまま c = m^e mod n とする方式)を、パディングを付けずに実際の通信に使うことの問題点として、正しいものはどれか。

暗号技術の基礎と応用の練習問題へ

関連する用語の解説

RSA暗号

1977年にリベスト、シャミア、エーデルマンが考案した公開鍵暗号。大きな2つの素数 p、q の積 n と公開指数 e を公開鍵とし、e × d ≡ 1 (mod (p − 1)(q − 1)) を満たす d を秘密鍵とする。暗号化は c = m^e mod n、復号は m = c^d mod n で行う。n の素因数分解が難しいことが安全性の根拠で、暗号化と署名の両方に使える。実際には、OAEPやPSSのような乱数を含むパディングと組み合わせて使う。

楕円曲線暗号

有限体の上の楕円曲線の点の演算を使う公開鍵暗号の総称。曲線上の点Gを秘密の整数k倍した点 kG から k を求める問題(楕円曲線上の離散対数問題)の難しさに安全性の根拠を置く。同じ安全性ならRSA暗号よりずっと短い鍵で済み、256ビットの鍵で、RSA暗号の3072ビットと同程度(128ビット相当)の安全性の目安とされる。鍵交換のECDH・ECDHEや、署名のECDSA・EdDSAに使われ、曲線にはP-256やCurve25519などが広く使われる。ショアのアルゴリズムで破られるため、耐量子計算機暗号への移行の対象になる。

耐量子計算機暗号

量子コンピュータでも効率よく解けないと考えられている数学の問題(格子の問題、ハッシュ関数など)に安全性の根拠を置く暗号。従来のコンピュータで動作し、ショアのアルゴリズムで破られる RSA暗号や楕円曲線暗号を置き換えるために使われる。

ML-KEM

米国のNISTが2024年8月にFIPS 203として標準化した、格子に基づく鍵カプセル化メカニズム(KEM)。Module-Lattice-Based Key-Encapsulation Mechanism の略で、CRYSTALS-Kyberをもとにしている。小さな誤りを加えた連立一次方程式から秘密を求めるModule-LWE問題の難しさに安全性の根拠を置き、量子コンピュータでも効率よく解けないと考えられている。ML-KEM-512、ML-KEM-768、ML-KEM-1024の3つのパラメータセットがある。TLSなどで、ECDHEの鍵交換を置き換えたり、組み合わせたりするために使われる。

ショアのアルゴリズム

大きな整数の素因数分解や離散対数問題を、量子フーリエ変換で周期を求めることによって多項式時間で解く量子アルゴリズム。1994年にピーター・ショアが発表した。RSA暗号や楕円曲線暗号を破れるが、実行には大規模な誤り耐性量子コンピュータが必要になる。

ディフィー・ヘルマン鍵交換

公開された通信路だけを使って、2者が共有の秘密を作る方法。1976年にディフィーとヘルマンが発表した。素数 p と生成元 g を公開し、AさんとBさんが秘密の値 a、b から g^a mod p、g^b mod p を作って送り合い、それぞれ相手の値を自分の秘密の値で累乗して、同じ g^(ab) mod p を得る。安全性は離散対数問題の難しさに基づく。楕円曲線の上で行うものをECDH、接続ごとに使い捨ての値を使うものをDHE・ECDHEと呼び、後者では前方秘匿性が得られる。相手を確かめる機能はないので、署名や証明書と組み合わせて中間者攻撃を防ぐ。

クリプトアジリティ

暗号のアルゴリズムや鍵長が安全でなくなったときに、システムを大きく作り直さずに別の方式へ入れ替えられる性質。どこでどの暗号を使っているかの一覧(インベントリ)を持ち、アルゴリズムを設定やプロトコルの交渉で選べるようにし、データの形式にアルゴリズムの識別子を含めることで高める。MD5やSHA-1、短い鍵のRSA暗号からの移行や、耐量子計算機暗号への移行で重視されている。

公開鍵暗号

暗号化と復号に、対になる別々の鍵(公開鍵と秘密鍵)を使う暗号方式。公開鍵は誰に知られてもよく、秘密鍵は本人だけが持つ。鍵の配送が楽になる一方、計算が重いので、データ本体の暗号化には共通鍵暗号と組み合わせて使う。RSAや楕円曲線暗号が代表的。

関連する比較

• CPUとGPUの違い：構造・得意な処理・用途を比較CPUとGPUを、設計の目的・コア数・実行モデル・キャッシュ・メモリ帯域・分岐・データ転送・得意な処理の観点で表にして比較します。
• I2C・SPI・UARTの違い：配線・速度・使い分けを比較I2C、SPI、UARTを、配線の数・クロック・速度・接続形態・アドレス・誤り検出・マイコンでの主な用途の観点で表にして比較します。
• VerilogとVHDLの違い：2つのハードウェア記述言語を比較VerilogとVHDLを、成り立ち・文法・型・大文字小文字・検証機能・使われる分野・選び方の観点で表にして比較します。
• NVMeとSATAのSSDの違い：速度・インターフェース・選び方NVMeとSATAのSSDを、インターフェース・速度・遅延・コマンドキュー・形状・消費電力・互換性・価格・向いている人の観点で表にして比較します。
• MCUとMPUの違い：マイコンとマイクロプロセッサを比較MCUとMPUを、集積度・クロック・メモリ・OS・リアルタイム性・消費電力・起動時間・コスト・用途の観点で表にして比較します。
• プロセスとスレッドの違い：メモリ・切り替え・使い分けを比較プロセスとスレッドを、メモリ・作成のコスト・コンテキストスイッチ・通信・分離・同期・用途の観点で表にして比較します。