RSA暗号とは

Q: なぜ p と q を秘密にする必要があるのですか?

p と q が分かれば (p − 1)(q − 1) を計算でき、公開されている e から d を求められるからです。n は公開されているので、安全性は n を素因数分解する難しさに頼っています。

Q: RSA暗号でファイルを直接暗号化しないのはなぜですか?

RSA暗号で一度に暗号化できるのは n より小さな数だけで、計算も共通鍵暗号よりずっと重いからです。実際には、ファイルはAESなどの共通鍵暗号で暗号化し、その共通鍵だけを公開鍵で守るハイブリッド暗号方式を使います。

あーるえすえーあんごう

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のような乱数を含むパディングと組み合わせて使う。

「RSA暗号」は、2分野の10問の練習問題に出てきます(暗号技術の基礎と応用, 量子コンピュータのハードウェアなど)。

この用語の分野: 暗号技術の基礎と応用

小さな数での例

p = 5、q = 11 なら n = 55、(p − 1)(q − 1) = 40 です。e = 3 とすると、3 × 27 = 81 ≡ 1 (mod 40) なので d = 27 です。平文 m = 7 は 7³ = 343 ≡ 13 (mod 55) と暗号化され、13^27 mod 55 を計算すると7に戻ります。

鍵長と安全性

NIST SP 800-57 の表では、2048ビットの n が112ビット相当、3072ビットが128ビット相当の安全性の目安とされています。同じ安全性で比べると、楕円曲線暗号よりずっと長い鍵と署名が必要で、鍵の生成や署名の計算も重くなります。公開指数には、計算が速く済む65537(2^16 + 1)がよく使われます。

使われ方の変化

かつてのTLSでは、クライアントが作った鍵の材料をサーバのRSA公開鍵で暗号化して送る鍵交換が広く使われましたが、前方秘匿性がないため、TLS 1.3では廃止されました。現在のRSA暗号は、主に証明書やソフトウェアの署名に使われています。大規模な量子コンピュータが実現するとショアのアルゴリズムで破られるため、耐量子計算機暗号への移行が進められています。

RSA暗号の練習問題に挑戦

RSA暗号の仕組みを小さな数で確かめる。素数 p = 5、q = 11 から n = pq を作り、公開指数を e = 3 とする。φ(n) = (p − 1)(q − 1) として、e × d ≡ 1 (mod φ(n)) を満たす秘密指数 d(0 < d < φ(n))はどれか。

答えと解説を見る

正解：B. 27

n = 5 × 11 = 55、φ(n) = 4 × 10 = 40 です。3 × d を40で割った余りが1になる d を探すと、3 × 27 = 81 = 2 × 40 + 1 なので、d = 27 です。公開鍵は (n, e) = (55, 3)、秘密鍵は d = 27 で、p と q を知らないと φ(n) が分からず、d を求められないことが安全性の根拠になります。実際のRSA暗号では、p と q はそれぞれ1000ビットを超える大きな素数で、e には65537がよく使われます。

RSA暗号で、公開鍵を n = 55、e = 3 とする。平文 m = 7 を c = m^e mod n で暗号化したときの暗号文 c はどれか。

答えと解説を見る

正解：A. 13

7³ = 343 で、343 = 6 × 55 + 13 なので、c = 13 です。この公開鍵に対応する秘密指数は d = 27(p = 5、q = 11、φ(n) = 40 で、3 × 27 ≡ 1)で、13^27 mod 55 を計算すると、元の平文の7に戻ります。暗号化は公開鍵だけでできますが、復号には d が必要です。

よくある質問

なぜ p と q を秘密にする必要があるのですか?

p と q が分かれば (p − 1)(q − 1) を計算でき、公開されている e から d を求められるからです。n は公開されているので、安全性は n を素因数分解する難しさに頼っています。

RSA暗号でファイルを直接暗号化しないのはなぜですか?