CRYPTOGRAPHY / EDUCATION

RSAしくみラボ素数から鍵を作り、暗号の仕組みをたどる

公開鍵と秘密鍵はどうつながり、なぜ素因数分解が鍵の安全性に関わるのでしょうか。小さな数で鍵生成、暗号化、復号、秘密鍵の再構成を試し、計算過程を確かめる学習アプリです。

RSAしくみラボを試す

学び方: 6ステップのコースと実験ラボ
比較対象: 3種類の素因数分解アルゴリズム
用途と範囲: 教育用raw RSA・最大48bit

RSAしくみラボで学べること

RSAしくみラボは、2つの素数から公開鍵・秘密鍵を作り、短いメッセージを暗号化して元に戻すまでを体験する教材です。数式と入力値、計算結果を照らし合わせ、鍵の各値が何に使われているかを追えます。

「はじめてコース」で一連の流れを学び、「実験ラボ」で素因数分解の方法や鍵長を変えて比較します。公開情報だけから素因数を見つけ、秘密鍵を再構成する操作を通して、分解の難しさと鍵の関係を確かめられます。

学習用の教科書的RSA（raw RSA）です。実用的な暗号化ツールではなく、実際の秘密情報の暗号化には使用できません。

鍵と計算はどうつながる？

RSAでは、公開してよい鍵で暗号化し、秘密にしておく鍵で復号します。アプリでは次の関係を、値を選び、計算を進める操作とともに確認できます。

素数から鍵の土台へ: 異なる素数 p と q を選び、積 n = p × q と φ(n) = (p − 1)(q − 1) を計算します。 n は公開鍵にも含まれる値で、剰余計算で割る数になります。
公開鍵と秘密鍵: φ(n) と互いに素な公開指数 e を選び、 e × d を φ(n) で割った余りが1になる秘密指数 d を求めます。公開鍵は (n, e)、秘密鍵は (n, d) です。
文字列を暗号化・復号: 入力した文字列をUTF-8のバイト列から整数ブロック m に変換し、 m^e を n で割った余りを暗号文 c にします。復号では c^d を n で割った余りを求め、ブロックから元の文字列へ戻します。画面の計算過程を追うと、文字と数式の対応を確認できます。
素因数分解と秘密鍵: 公開された n を分解して p と q が分かると、 φ(n) と e から d を計算できます。秘密鍵再構成の操作では、このつながりを使って暗号文を復号します。

はじめてコースの6ステップ

「はじめてコース」を開き、順に操作します。各ステップでは「解説を進む／戻る」で計算の説明をたどれます。

素数選択：「素数を選ぶ」。 2つの素数を選びます。合成数や同じ素数の組み合わせが使えない理由も確認します。
鍵生成：「鍵を作る」。 素数の積、φ(n)、公開指数、秘密指数を順に確認し、公開鍵と秘密鍵ができる過程を追います。
暗号化：「暗号化する」。 短いメッセージを入力し、UTF-8バイト列から整数ブロック、暗号文へ変わる様子を見ます。日本語や絵文字も使えますが、上限はUTF-8で128バイトです。
復号：「元に戻す」。 秘密鍵で暗号文を復号し、元の文字列へ戻ることを確認します。暗号化と復号で使う指数の違いに注目します。
秘密鍵再構成：「秘密を探す」。 公開鍵と暗号文を手がかりに素因数分解し、得られた素数から秘密鍵を作り直して復号します。
鍵長比較：「大きさを比べる」。 16〜32bitの鍵長で分解にかかる時間を比べます。同じRSAでも、扱う数の大きさで探索の負担が変わることを観察します。

実験ラボで3つの方法を比べる

「実験ラボ」では、鍵長を16〜48bitの4bit刻み、探索制限時間を1〜10秒、試行回数を1〜5回で指定できます。素数の生成方式は「ランダム」と「平方根付近の隣接素数」を切り替えられます。

試し割り法: 候補の数で順番に割り、割り切れる因数を探します。仕組みを追いやすい基本的な方法で、鍵長を増やしたときに調べる候補がどう増えるかを観察できます。
フェルマー法: n = x² − y² となる組を探し、 (x − y)(x + y) に分解します。 2つの素数が近いと見つけやすいため、生成方式を切り替えると鍵長以外の条件も結果に関わることが分かります。
ポラード・ロー法: 数列の繰り返しと最大公約数を利用して因数を探します。単純な試し割りと異なる探索を行うため、同じ条件で時間や成功数を比べ、方法による得意・不得意を確かめます。

結果はグラフと集計表で確認できます。成功時の中央値だけでなく、成功数／総試行数、時間切れ、各試行の経過時間や探索回数も見比べてください。探索は途中で中断できます。

探索回数が数える処理はアルゴリズムごとに異なります。回数だけで速さを判断せず、同じ端末・条件で測った時間と成功数も合わせて読みます。

鍵長と素因数分解の難しさ

鍵長は、素数の積 n を2進数で表したときの長さです。 bit数が増えると扱う数は大きくなり、一般に分解の負担も増えます。ただし、このラボでも素数の近さやアルゴリズムによって所要時間は変わり、長い鍵が毎回必ず遅くなるとは限りません。

比較するときは生成方式、探索制限時間、試行回数をそろえ、鍵長を変えます。時間切れは「今回の条件と制限時間では見つからなかった」という結果であり、分解できないことの証明ではありません。計測値には端末性能やブラウザの状態も影響します。

本アプリの上限は48bitで、分解の過程を観察するための小さな鍵です。実用で使う2048bit以上のRSAとは規模も実装条件も異なります。ここでの成功・失敗や時間を、現実のRSA暗号の解読可能性と直接同一視したり、そのまま外挿したりしないでください。

学習用実装の制限事項

教科書的RSA（raw RSA）。 OAEPなどのパディングを行わず、同じ鍵と同じ平文ブロックからは同じ暗号文ができます。実用的な暗号化ツールではありません。
実際の秘密情報には使用できません。 パスワード、個人情報、機密文書などを入力・暗号化せず、学習用の短文を使ってください。
鍵長は最大48bit。 メッセージもUTF-8で最大128バイトに制限されます。文字数とバイト数は異なり、日本語や絵文字は複数バイトになります。
乱数は実験の再現用。 シード付き疑似乱数を使い、暗号学的に安全な鍵生成は行いません。
計算はブラウザ内で完結。 探索にはWeb Workerを使います。入力や結果は永続保存されず、ページを再読み込みすると初期状態に戻ります。
実験結果は実用RSAの解読可能性を示しません。 小さな鍵と3種類の方法での観察結果です。現実のRSAの安全性を評価するための判定ツールではありません。

小さな素数から試す

鍵を作り、計算をたどる

はじめてコースで一連の流れを確認したら、実験ラボで条件を変えて比較できます。実際の秘密情報を含まない例文で試してください。