「素因数分解は事実上不可能」——この前提の上に、私たちが日々使う暗号技術は成り立っています。けれどその”不可能”の境界線は、時代とともにじわじわと動いています。今回取り上げるrusqsieveは、Rustで実装されたSIQS（自己初期化型二次篩法）による素因数分解ライブラリです。もとはブラウザの不正ログイン対策として生まれたこの実装は、いまやiPad上で240ビットの数字をわずか数秒、ノートPC一台で97桁の合成数までも解き切ります。開発したのは、本記事の筆者自身。その内側から見えた景色を、ご紹介します。
rusqsieveは、Rustで実装されたSIQS（自己初期化型二次篩法）による整数因数分解ライブラリである。WebAssembly版は複数のWeb Workerから並列実行でき、192〜288ビットの平衡RSA型半素数に最適化されている。iPad Air（M3）では192ビットを0.5秒未満、224ビットを3秒未満、240ビットを約6秒、256ビットを約20秒で解く。ノートPC1台では320ビット（97桁）を約33分で完走し、192コアのサーバではRSA-110（110桁）を366.12秒で解いた。開発の出発点は、ブラウザの不正ログイン対策に使うProof of Work（PoW）だった。
From: 
世界最速のブラウザ素因数分解を目指して・rusqsieve
【編集部解説】
あなたのブラウザで今すぐ試せます↓
一次資料としての立場について
本記事には少し変わった成り立ちがあります。ご紹介するrusqsieveの開発者は、本記事の筆者である私自身です。編集部の記事は通常「私たち」の視点で書きますが、今回は開発の当事者にしか見えない部分があるため、一部を「私」の一人称で書かせていただきます。
純粋なRustという選択
rusqsieveのGitHubリポジトリの説明文には、「pure-Rust」「portable to WASM」という言葉が並びます。実際にCargo.tomlを確認すると、本体の依存クレートは一つもありません。
これは地味に見えて、実は重要な設計判断です。Rustのコードを Web ブラウザで動かす場合、wasm-bindgenというJavaScript連携用のライブラリを使うのが一般的です。しかしrusqsieveは、あえてそこに頼っていません。入力は数値、出力も数値——DOM操作やJavaScriptオブジェクトとのやり取りを必要としない、純粋な計算ライブラリだからこそ、wasm32-unknown-unknownという素のターゲットにコンパイルするだけで済みます。
私にとってこれは、「ネイティブでもWasmでもC ABIでも、同じコードが同じように動く」という安心感につながっています。JavaScript連携層が薄いということは、監査すべき表面積が小さいということでもあります。
コンシューマ端末という「現実」の中の最前線
要約で示した数字は、どれもスーパーコンピュータの話ではありません。iPad Air（M3）、あるいは一般的なノートPC——店頭で買える機材の話です。
この「現実の端末でどこまでいけるか」という視点は、innovaTopiaが以前取り上げた別の挑戦とも重なります。同じ『サマーウォーズ』の2056桁のRSA暗号に触発され、単純な試し割り法で挑んだ自作ツールの記事です。あちらは10桁ならほぼ瞬時、20桁で約7秒でした。そして実際に2056桁を入力すると、画面は動かなくなったといいます。30桁を超えたあたりからは現実的な時間内に終わらなくなるだろう、というのが執筆者自身の見立てです。
rusqsieveはSIQSという、もっと洗練されたアルゴリズムを使っています。同じ「ブラウザで、消費者向け端末で」という土俵に立ちながら、ノートPC1台で97桁の合成数を33分ほどで解き切ります。桁数にして3倍強、しかし体感としては「一生終わらない」から「コーヒーを一杯飲む間に終わる」への転換です。ハードウェアの進歩だけでは、この差は説明がつきません。アルゴリズムの選択がどれほど効くかを、同じ媒体の中の2つの記事が図らずも示しています。
これは、量子コンピュータの話ではありません
一点、誤解のないよう留保を置かせてください。rusqsieveが扱っているのは192〜320ビット程度の合成数です。実際にインターネット通信を守っている2048ビット（約617桁）のRSA鍵とは、桁も現実性もまったく異なります。
また、これは量子コンピュータの話でもありません。ショアのアルゴリズムは量子ビットという全く別の計算資源を使いますが、rusqsieveが使っているSIQSは、あくまで古典的なコンピュータの上で動くアルゴリズムです。量子コンピュータとRSA暗号の関係については、以前の記事で詳しく扱っていますので、そちらをご参照ください。
rusqsieveが示しているのは、「量子コンピュータを使わずとも、消費者向け端末上のブラウザだけで、素因数分解の実務的な境界をどこまで押し広げられるか」という、もう一つの最前線です。
PoWとしての意味——「掛け算」で効かせる設計
rusqsieveが向き合っているのは、量子コンピュータとは別の、もっと足元にある脅威です。そもそも、なぜこの実装が必要だったのか。出発点はサインイン処理の防御でした。
PoW方式のRSAチャレンジは、正規のユーザーにはブラウザというサンドボックスの中で解いてもらうことが前提です。ここで問題になるのが、攻撃者がブラウザの外——ネイティブコードや、より強力なハードウェア——で同じアルゴリズムを走らせたときに、正規ユーザーよりも大幅に速く解けてしまうケースです。それが起きると、PoWが課しているはずのコストは実質的に骨抜きになります。私がrusqsieveの開発でもっとも意識したのは、ここでした。ブラウザの中でとにかく高速に動くこと自体が、攻撃者が「ブラウザを避けて速く解く」ことで得られる相対的な優位性を縮め、PoWを実効あるものにする、という考え方です。
その裏付けとして、v0.4.1ではx86-64のSSE2/AVX2向けとWasm SIMD128向けの両方に、並行してSIMD高速化を実装しています。ネイティブだけを磨いてブラウザ版を置き去りにするのではなく、両方の実行環境を同じだけ最適化する方針です。なお、ネイティブとWasmを同一条件で比較した数値は元記事には示されていませんが、私の実測では、コンシューマPCでは同コア数で1.2倍程度の、ほぼ同速度で動作するといっても過言ではない WebAssembly パフォーマンスが得られています。
ただ、このPoW単体で攻撃者を止められるわけではありません。実運用では、フルブラウザがないと成立しない複雑なログインフォームと組み合わせて使われています。このスキームの核心は、3つの要素の掛け算にあります。第一に、ヘッドレスブラウザを用意して複雑なログインフォームを実際に動かすコスト。第二に、レートリミットを回避するためにレジデンシャルプロキシでIPアドレスを”洗浄”し続けるコスト。第三に、224〜256ビットのRSAチャレンジ——正規ユーザーなら数秒から20秒ほどで終わる計算——を、サインイン試行のたびに解き直すコストです。
このどれか一つだけなら、資金力のある攻撃者にとっては突破可能な、単なる出費に過ぎません。しかし3つを同時に、何千回、何万回という試行のたびに満たし続けなければならないとなると話が変わります。複雑なフォームを解釈できるブラウザ環境、まっさらな住宅用IP、そして毎回の計算待ち時間——この3つの掛け算になっていることが、このスキームの「ミソ」です。
ただし、GitHubのドキュメントにもある通り、PoWは認証そのものではなく、あくまで「資源の価格付け」です。パスキーやTOTP、レートリミットといった本来の認証・防御手段を置き換えるものではなく、それらの上に積む追加の一枚として位置づけられています。
まとめに代えて
rusqsieveは、GitHub上ではまだスター数一桁の、知る人ぞ知る小さなプロジェクトです。ですが、依存ゼロのRustコードが、ネイティブでもWasmでも同じ土俵で走り、iPadの上で数秒、ノートPCの上で数十分という検証可能な数字を積み重ねている事実は、宣伝文句ではなく実測値として確認できます。ECMを持たない、定数時間ではない、NFSの代替ではない——できないことも含めて開発者自身がGitHub上で明記している点も、この記事を書く判断材料になりました。
【関連記事】
素因数分解の”難しさ”というテーマは、以前『サマーウォーズ』を通じてもご紹介しました。
同じ因数分解というテーマに、試し割り法という別のアプローチで挑んだ記事もあります。
WebAssemblyという技術そのものについては、以前W3Cの3.0発表を機にご紹介しました。
【編集部後記】
私たちが日々使う暗号は、遠い専門家だけの話に思えるかもしれません。けれど今回のように、ブラウザに数字を入力し、数秒後に素因数が現れる瞬間を目にすると、その「難しさ」が急に手触りのあるものに変わります。境界線がどこにあるのかは、私たちも更新し続けるほかありません。非営利団体が公開する一本のOSSが、その更新に確かな一歩を刻むこともあります。よろしければ、ぜひご自身の手でデモをお試しください。
【参考動画】
【用語解説】
SIQS（Self-Initializing Quadratic Sieve）
大きな合成数を素因数分解するための古典的アルゴリズムの一種。RSA型半素数に対して比較的効率がよく、現実的な大きさの数の分解で広く使われる手法。
平衡半素数（Balanced Semiprime）
2つの素数の掛け算でできた数（半素数）のうち、掛け合わせた2つの素数の桁数がほぼ同じもの。RSA暗号の鍵に使われる形。
WebAssembly（Wasm）
ブラウザ上でネイティブに近い速度でプログラムを実行するためのバイナリ形式。Rustなど各種言語のコードをコンパイルして配布できる。
wasm-bindgen
RustなどのコードをWebAssemblyにコンパイルする際、JavaScriptとの連携（DOM操作やオブジェクトの受け渡し）を担うライブラリ。
C ABI
C言語の関数呼び出し規約に準拠したインターフェース。プログラミング言語の違いを越えて共通の方法で呼び出せる、事実上の標準的な連携方式。
PoW（Proof of Work）
処理の実行前に一定の計算作業を要求する仕組み。計算コストを課すことで大量アクセスや不正試行を抑制する目的で使われる。
ECM（Elliptic Curve Method）
素因数分解アルゴリズムの一種。比較的小さな素因数を見つけるのに強く、SIQSとは得意な入力の形が異なる。
NFS（Number Field Sieve）
現在知られている中で最も効率のよい汎用素因数分解アルゴリズム。SIQSより大きな数（400ビット以上など）で優位に立つ。
ヘッドレスブラウザ（Headless Browser）
画面表示を伴わずに動作するブラウザソフト。自動テストやスクレイピング、ボットによる自動操作などに使われる。
レジデンシャルプロキシ（Residential Proxy）
一般家庭のインターネット回線経由に見せかけて通信を中継するプロキシサービス。IPアドレスに基づく検知・制限を回避する目的で使われることがある。
一般社団法人生活情報基盤研究機構（Menhera®）
rusqsieveの開発元。情報技術・情報基盤の研究開発を通じて個人の自由と生活の豊かさに資することを掲げる一般社団法人。「Menhera」は同機構の登録商標。AS63806の運用や、JPNICのIPアドレス管理指定事業者（LIR）としての活動も行う。
https://www.menhera.or.jp/
【参考リンク】
rusqsieve 公式デモ（ブラウザ）（外部）
ブラウザ上で実際に素因数分解を試せる公開デモ。整数の直接入力や、指定ビット数のRSA型半素数の生成にも対応する。
rusqsieve GitHubリポジトリ（外部）
rusqsieveのソースコード、ベンチマーク手順、設計文書を公開するリポジトリ。Apache-2.0/MPL-2.0のデュアルライセンス。
crates.io（Rustパッケージレジストリ）（外部）
Rustのパッケージレジストリ上の配布ページ。cargo installまたはcargo addで導入できる。
docs.rs（APIドキュメント）（外部）
rusqsieveのRust API仕様書。関数・型定義を自動生成ドキュメントの形で確認できる。
Menhera.org（開発元公式サイト）（外部）
開発チーム「一般社団法人生活情報基盤研究機構」の公式サイト。関連プロジェクトの発表も掲載されている。
GitHub Issues（不具合報告・提案）（外部）
バグ報告や質問、機能提案を投稿できるIssueトラッカー。オープンソースとして外部からの関わりを受け付けている。
【参考記事】
GitHub README — metastable-void/rusqsieve（外部）
「pure-Rust」「portable to WASM」という設計思想、PoWの位置づけなど、編集部解説の技術的根拠として使用。
Cargo.toml — metastable-void/rusqsieve（外部）
本体クレートに外部依存が存在しないことの直接確認に使用。「純粋なRust」という主張の検証根拠となった。
Smooth Subsum Search: A heuristic for practical integer factorization — arXiv（外部）
二次篩法は今も100桁程度までの数に対する最効率な汎用手法とされる。SIQSより高速な新手法を提案する論文。
