基本情報技術者 2011年 春期 午前（科目A） 問42
問題文
非常に大きな数の素因数分解が困難なことを利用した公開鍵暗号方式はどれか。
選択肢
ア：AES
イ：DSA
ウ：IDEA
エ：RSA（正解）
🔒 解説は解答すると表示されます
素因数分解に基づく公開鍵暗号【午前解説】
正解の理由
正解は エ（RSA）です。RSAは鍵生成で二つの大きな素数 を選び、合成数 を公開します。公開鍵は 、秘密鍵は で、 を満たします。暗号の安全性は、与えられた から元の素因数 を効率よく見つけられないこと（整数の素因数分解の困難性）に依存しています。そのため問題文の「非常に大きな数の素因数分解が困難なことを利用した公開鍵暗号方式」に該当します。
解法ステップ
- 問題文のキーワード――ここでは「素因数分解」――をまず探す。
- 暗号方式ごとの基盤（素因数分解／離散対数／共通鍵）を対応付ける。
- 該当する方式を選び、他の選択肢が何を基盤にしているかで検証して除外する。
選択肢別の誤答解説
- ア: AES
- 誤り。AES（Advanced Encryption Standard）はブロック暗号の共通鍵方式で、公開鍵暗号ではありません。鍵は送信前に共有する必要があります。
- イ: DSA
- 誤り。DSA（Digital Signature Algorithm）は署名アルゴリズムで、離散対数問題（例: 素体上の離散対数）が安全性の根拠です。素因数分解を直接利用しません。
- ウ: IDEA
- 誤り。IDEA は共通鍵ブロック暗号（かつ対称鍵暗号）であり、公開鍵暗号や素因数分解を利用する方式ではありません。
- エ: RSA
- 正解。RSA は合成数 の素因数分解の困難性に基づく公開鍵暗号方式です。
よくある誤解
- RSA と DSA を混同する誤解: DSA は「署名」に特化し、離散対数問題に基づくため「素因数分解」を根拠としません。
- 公開鍵＝全て同じ種類の問題に基づく: 公開鍵暗号でも「素因数分解」以外に「離散対数」や「格子問題」など別の難問を基盤にする方式があります。
- AES/IDEA を公開鍵だと勘違いする: AES や IDEA は共通鍵（対称）暗号であり、公開鍵暗号ではありません。
補足コラム
RSA は暗号化・署名の両方に使えますが、実務では大きなデータの直接暗号化に用いることは少なく、代わりに共通鍵を RSA で安全に配送してから対称鍵暗号で通信する「ハイブリッド暗号」が一般的です。近年は量子計算の進展により、Shor のアルゴリズムが実用化されれば素因数分解に基づく RSA の安全性は根本的に破られます。現在の実用的推奨鍵長は少なくとも 2048 ビット以上です。
FAQ
Q: RSA と DSA の違いを一言で教えてください。
A: RSA は素因数分解の困難性を利用する公開鍵暗号で暗号化・署名に使え、DSA は離散対数問題に基づく署名専用のアルゴリズムです。
A: RSA は素因数分解の困難性を利用する公開鍵暗号で暗号化・署名に使え、DSA は離散対数問題に基づく署名専用のアルゴリズムです。
Q: AES や IDEA には素因数分解は関係ありますか？
A: ありません。AES/IDEA は共通鍵（対称）暗号で、素因数分解や離散対数といった数学的難問に依存しません。
A: ありません。AES/IDEA は共通鍵（対称）暗号で、素因数分解や離散対数といった数学的難問に依存しません。
Q: RSA はもう安全ではないですか？
A: 現在の古典コンピュータに対しては、十分な鍵長（例: 2048 ビット以上）を使えば現実的な攻撃は困難です。ただし量子耐性がないため、将来の量子コンピュータに備えた耐量子暗号への移行が検討されています。
A: 現在の古典コンピュータに対しては、十分な鍵長（例: 2048 ビット以上）を使えば現実的な攻撃は困難です。ただし量子耐性がないため、将来の量子コンピュータに備えた耐量子暗号への移行が検討されています。
関連キーワード: 公開鍵暗号、RSA、素因数分解、整数因数分解、離散対数問題、DSA、AES、IDEA、ハイブリッド暗号、量子耐性、RSA-2048、鍵長
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！