応用情報技術者 2013年秋期午前2 問38

問題文

非常に大きな数の素因数分解が困難なことを利用した公開鍵暗号方式はどれか。

選択肢

ア：AES

イ：DSA

ウ：IDEA

エ：RSA（正解）

非常に大きな数の素因数分解が困難なことを利用した公開鍵暗号方式【午前2 解説】

要点まとめ

結論：非常に大きな数の素因数分解の困難さを利用する公開鍵暗号方式はRSAである。
根拠：RSAは大きな合成数の素因数分解問題の計算困難性に安全性を依存している。
差がつくポイント：AESやIDEAは共通鍵暗号、DSAは離散対数問題に基づくため、素因数分解とは無関係である。

正解の理由

RSAは、2つの大きな素数の積である合成数を公開鍵として用い、その素因数分解が極めて困難であることを安全性の根拠としています。これにより、秘密鍵を知らずに暗号文を解読することが難しくなっています。選択肢の中でこの特徴を持つのはエ: RSAのみです。

よくある誤解

AESやIDEAは公開鍵暗号ではなく共通鍵暗号であり、素因数分解の困難性とは無関係です。DSAは離散対数問題を基にしているため、RSAとは異なる数学的基盤を持ちます。

解法ステップ

公開鍵暗号方式の特徴を理解する（公開鍵と秘密鍵の役割）。
RSAの安全性の根拠が「大きな数の素因数分解の困難さ」であることを確認。
AESやIDEAは共通鍵暗号であるため除外。
DSAは離散対数問題に基づく公開鍵暗号であり、素因数分解とは無関係。
よって、素因数分解の困難さを利用するのはRSAであると判断。

選択肢別の誤答解説

ア: AES
共通鍵暗号方式であり、素因数分解の困難性は関係ない。
イ: DSA
離散対数問題に基づく公開鍵暗号方式で、素因数分解とは異なる数学的問題を利用。
ウ: IDEA
共通鍵暗号方式であり、素因数分解の困難性は利用しない。
エ: RSA
大きな数の素因数分解の困難さを安全性の根拠とする公開鍵暗号方式。

補足コラム

RSAは1977年にロナルド・リベスト、アディ・シャミア、レナード・アデルマンによって発明されました。現在でも広く使われており、電子署名やSSL/TLS通信の基盤技術として重要です。素因数分解の困難性は量子コンピュータの発展により将来的に脅かされる可能性があり、ポスト量子暗号の研究が進められています。