基本情報技術者 2017年 秋期 午前（科目A） 問38

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

要点まとめ

• 結論：非常に大きな整数の素因数分解の困難性を基礎とする公開鍵暗号方式はエ RSAです。
• 根拠：RSA は公開鍵 $(n,e)$ と秘密鍵 $d$ を、合成数 $n=pq$ の因数分解が困難なことに依存して生成します。
• 差がつくポイント：AES は共通鍵暗号、DH/DSA は離散対数問題が基礎であり、問題の文言と一致するのは RSA だけです。

正解の理由

よくある誤解

• 「公開鍵＝RSA」と単純化し、他の公開鍵方式の基礎問題を混同する点。DH・DSA は離散対数問題が基礎です。
• 「AES も公開鍵暗号だ」と誤認する点。AES は共通鍵（対称）暗号で公開鍵暗号には該当しません。
• 「RSA は無敵」と考える点。鍵長やパディング、量子計算機の影響などで安全性は相対的に変化します。

解法ステップ

1. 問題文のキーワードを探す：「素因数分解が困難」→ 整数因数分解問題。
2. 各方式の基礎問題を確認：RSA→因数分解、DH/DSA→離散対数、AES→共通鍵暗号。
3. 一致するものを選ぶ：整数因数分解問題を基にするのは RSA のみ。
4. 余力があれば、RSA の公開鍵・秘密鍵の構成式や利用上の注意点を確認して確信を得る。

選択肢別の誤答解説

• ア: AES
  • 説明：AES は対称鍵（共通鍵）ブロック暗号で、鍵の共有が必要です。素因数分解問題とは無関係です。
• イ: DH
  • 説明：Diffie–Hellman（DH）は鍵共有プロトコルで、離散対数問題（有限体や楕円曲線上の離散対数）が基礎です。因数分解は使用しません。
• ウ: DSA
  • 説明：Digital Signature Algorithm（DSA）は電子署名方式で、離散対数問題を基礎とします。素因数分解が基礎ではありません。
• エ: エ RSA
  • 説明：RSA は大きな合成数 $n=pq$ の素因数分解が難しいことを安全性の根拠とする公開鍵暗号方式です。公開鍵 $(n,e)$、秘密鍵 $d$ によって暗号化と復号（あるいは署名と検証）を行います。典型的には 2048 ビット以上の $n$ が推奨されます。

補足コラム

• 鍵生成の概略：大きな素数 $p,q$ を選び $n=pq$、$\phi (n)=(p-1)(q-1)$ を計算、公開指数 $e$ を選び、$d$ を $ed\equiv 1(\mathrm{mod}\phi (n))$ で求めます。
• 実運用：RSA 単体で大量のデータを暗号化するのは効率が悪いため、実務では RSA で共通鍵を安全に交換し、その共通鍵で AES 等の対称鍵暗号を使う「ハイブリッド暗号」が一般的です。
• パディングと安全性：RSA は適切なパディング（例：OAEP）なしでは安全性が損なわれることがあります。
• 量子コンピュータの影響：ショアのアルゴリズムにより量子計算機が十分実用化されると RSA の安全性は破られるため、将来は格子暗号などポスト量子暗号が注目されます。

# 小さな素数でRSAの概念を確認（実運用には使用不可）
p, q = 61, 53
n = p * q
phi = (p-1)*(q-1)
e = 17
d = pow(e, -1, phi)
m = 65  # 平文（数値）
c = pow(m, e, n)   # 暗号化
m_recovered = pow(c, d, n)  # 復号
print(n, e, d, c, m_recovered)

FAQ