0Pricing
Cryptology Academy · レッスン

教科書的RSAと安全でない理由

可鍛性、小さい指数への攻撃、e=3の脆弱性を実演します。

「教科書的RSAと安全でない理由」はCoddyKit上の無料Cryptology Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCryptology Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Cryptology Academyコースには全4レッスンが含まれています。

ようこそ

教科書RSA（生のモジュラーべき乗）は、複数の重大な脆弱性を抱えています。このレッスンでは、それぞれの攻撃を検討し、なぜパディングが必須なのかを理解します。

決定性を利用した攻撃

教科書RSAは決定的です。つまり、Enc(M)は常に同じCを生成します。攻撃者は候補となるメッセージを暗号化し、対象の暗号文と比較できます。これにより、候補が少ないメッセージ空間では機密性が破られます。

可鍛性

RSAには乗法的可鍛性があります。Enc(M1) × Enc(M2) = Enc(M1×M2) mod n が成り立つため、攻撃者は暗号文にEnc(2) = 2^eを掛けることで、鍵を知らなくても平文を2倍にできます。

小さいメッセージへの攻撃（e=3）

e=3かつM < n^(1/3)の場合、C = M^3 mod n = M^3（モジュラー還元なし）となります。Cの立方根を求めれば、Mを直接得られます。必ずパディング付きRSAを使用し、Mが十分な大きさになるようにしてください。

Coppersmith攻撃

Coppersmithは、e=3で攻撃者がMの大部分を知っている場合（例：M = YYYY-MM-DD...[unknown portion]）、多項式の因数分解によって未知のビットを復元できることを示しました。短いパディング付き平文は脆弱です。

Håstadのブロードキャスト攻撃

同じMを、e=3の受信者3者に送信した場合、中国剰余定理（CRT）により、C1、C2、C3からM^3 mod (n1×n2×n3)を特定できます。立方根を直接求めればMが得られます。e=3で同じ平文を複数の受信者に暗号化してはいけません。

Franklin-Reiter関連メッセージ攻撃

2つのメッセージM1とM2が線形関係（M2 = aM1+b）にあり、同じ鍵で暗号化されている場合、その関係を悪用してM1とM2を復元できます。ランダムバイトによるパディングでこの攻撃を防げます。

共通法攻撃

2台のサーバーがnを共有し、GCD(e1,e2)=1を満たす異なるe1、e2を使用して、同じMを暗号化している場合、拡張ユークリッドの互除法を使ってMを復元できます。エンティティ間で法を共有してはいけません。

RSA復号に対するタイミング攻撃

RSAの復号時間は秘密鍵のビットに依存します（square-and-multiplyの動作がビットごとに異なるためです）。Kocherは1996年に、復号時間を測定して秘密鍵を復元するタイミング攻撃を発表しました。対策はブラインディングです。

RSAブラインディングによる防御

復号の前に、C' = C × r^e mod n（ランダムなブラインディング係数r^eを掛ける）を計算します。M' = C'^d mod nを計算し、M = M' × r^(-1) mod nを求めます。これでタイミングはMではなくrに依存するため、攻撃者に見えるのはノイズを含む測定結果だけになります。

根本的な対策：ランダム化パディング

教科書RSAに対するすべての攻撃には、共通する対策があります。それがランダム化パディングです。PKCS#1 v1.5はランダム性を追加し、OAEPは証明可能な安全性を実現しました。適切なパディングを使用すれば、上記の攻撃はいずれも機能しません。

クイックチェック

攻撃者が、暗号文に特定のメッセージが含まれているかどうかを検証できるのは、教科書RSAのどの性質によるものですか？

まとめ

教科書RSAは非常に危険で、安全ではありません。次はPKCS#1 v1.5パディングについて、その設計と利用方法、そしてそれを破ったBleichenbacher攻撃を学びます。

よくある質問

「教科書的RSAと安全でない理由」レッスンは無料ですか？

はい。「教科書的RSAと安全でない理由」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Cryptology Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Cryptology Academyコースには全4レッスンが含まれています。

「教科書的RSAと安全でない理由」で何を学びますか？

可鍛性、小さい指数への攻撃、e=3の脆弱性を実演します。 ブラウザで直接実行するハンズオンコードでCryptology Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Cryptology Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCryptology Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

「教科書的RSAと安全でない理由」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCryptology Academyレッスンでコードを書いて実行できますか？

はい。すべてのCryptology Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 教科書的RSAと安全でない理由
  2. PKCS#1 v1.5パディングとBleichenbacher攻撃
  3. OAEP：最適非対称暗号化パディング
  4. デジタル署名のためのRSA-PSS
← Cryptology Academyに戻る