✨ まず素数とは何か？おさらい
素数（prime number）とは、「1と自分自身以外では割り切れない、2以上の整数」のことです。
素数の例：
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47...
4は「2×2」なので素数ではない。6は「2×3」なので素数ではない。など。
素数は古代ギリシャの時代から研究されてきた数学の基礎概念です。興味深いことに、素数は無限に存在することが2300年前のユークリッドによって証明されているのに、その分布には今も解明されていない謎が残っています（「リーマン予想」は現代数学最大の未解決問題のひとつ）。
素数って学校で習ったけど、暗号となんの関係があるの？
素数の「謎の分布」が、実は巨大な数を素因数分解することを難しくしているんだよ。RSA暗号はそこを利用しているんだよ🐾
🔸 素因数分解がなぜ難しいのか
素因数分解とは、「ある整数を素数の積として表すこと」です。
- 12 = 2 × 2 × 3（簡単）
- 100 = 2 × 2 × 5 × 5（簡単）
- 77 = 7 × 11（少し考えれば解ける）
- 3233 = 61 × 53（かなり大変）
数が大きくなるほど、素因数分解は爆発的に難しくなります。現在知られている最良のアルゴリズムでも、桁数に対して指数関数的に時間がかかるため、十分に大きな数は「実用的に解けない」とされています。
🔢 どのくらい難しい？（RSA-2048の場合）
- nは617桁の巨大な数
- 世界最速のスーパーコンピュータを使っても、素因数分解には宇宙の年齢（138億年）を遥かに超える時間がかかると推定
- 現在確認されている最大の素因数分解記録はRSA-250（829ビット、2020年）
🔸 RSAに使う素数はどう選ぶ？安全な素数の条件
RSAに使う素数は「ただ大きければよい」のではなく、いくつかの重要な条件があります：
-
十分に大きいこと
2048ビットのRSAなら、p と q はそれぞれ約1024ビット（309桁）程度必要です。 -
p と q の大きさが近すぎないこと
p ≈ q の場合、フェルマー分解法という攻撃で比較的簡単に因数分解できてしまいます。実際には p と q の大きさに一定の差を設けます。 -
p-1 と q-1 が大きな素因数を含むこと（強素数）
「ポラード・ロー法」などの攻撃への対策。最近はこの条件より鍵長の確保が優先される傾向にあります。 -
真にランダムに生成されること
予測可能なパターンで生成された素数は、攻撃者に狙われます。暗号論的に安全な乱数生成器（CSPRNG）を使います。
素数の生成方法にも気をつけないといけないんだね。難しそう…
普通のアプリやウェブサービスを使う分には、ライブラリが全部やってくれるから心配しなくていいね。でも暗号システムを自分で実装するときは絶対に既存の信頼できるライブラリを使うこと！自作は危険ね🐾
🔸 RSAへの実際の攻撃手法と対策
| 攻撃手法 | 内容 | 対策 |
|---|---|---|
| 素因数分解攻撃 | nを直接因数分解してp, qを求める | 鍵長2048ビット以上を使用 |
| フェルマー分解法 | p と q が近い場合に有効 | p と q の差を十分に取る |
| タイミング攻撃 | 処理時間の差から秘密鍵を推測 | 定時間実装・ブラインド処理 |
| 選択暗号文攻撃 | 特定の暗号文の復号結果から推測 | OAEPパディングを使用 |
| 量子コンピュータ攻撃 | ショアのアルゴリズムで効率的に素因数分解 | 耐量子暗号（格子暗号等）へ移行 |
⚠️ 量子コンピュータへの備え
将来の量子コンピュータはショアのアルゴリズムによってRSAを多項式時間で解読できる可能性があります。NISTは2024年に耐量子暗号（格子ベース暗号のML-KEM、ML-DSA等）を標準化しました。現時点でRSAは安全ですが、長期保存データは将来的に耐量子暗号への移行が推奨されます。
📌 まとめ：素数がRSAの要である理由
- 素数は「1と自分以外で割り切れない数」。無限に存在し、分布に規則性がない
- 2つの素数の積（n = p × q）は作るのは簡単でも、分解するのは超困難
- この「非対称性」がRSA暗号の安全性の源
- 安全な素数の条件：十分な大きさ・差・真の乱数で生成すること
- 現在のRSAへの実用的な攻撃は知られていないが、量子コンピュータへの備えが進んでいる
2300年前から研究されてきた「素数」が、現代の暗号を守っている——これって、なんか壮大でロマンを感じるね🐾 次はRSA暗号全体の構造と安全性についてまとめを見てみてね！