序章

現在，インターネットでは公開鍵暗号方式のRSA暗号が広く使われています。鍵の非対称性を持ち，共通鍵暗号方式と比較して暗号化・復号の計算量が大きい代わりに，事前の鍵交換が不要(いわゆる鍵配送問題を回避できる)という特徴があります。この暗号の安全性は素因数分解の計算複雑性に依存し*，既知の一般的な巨大数(100桁程度以上)に対する最も高速な素因数分解のアルゴリズムである一般数体篩法(いっぱんすうたいふるいほう; GNFS)の計算量オーダーは， $$O\!\Bigl(\exp\!\bigl(\bigl((64/9)^{1/3}+o(1)\bigr)\,(\log n)^{1/3}\,(\log\log n)^{2/3}\bigr)\Bigr).$$ と見積もられています(準指数時間，nは分解対象)。現在主に利用されているのは RSA-1024 や RSA-2048，RSA-4096 で，それぞれ1024ビット，2048ビット，4096ビットの合成数により構成されています。(より直感的には，それぞれ10進法で155桁，309桁，617桁程度の素数が利用されています。とても想像できないほど巨大な数ですね。) 素数生成のプロセスが完全にランダムであるという仮定の下では，基本的にビット数が大きくなるほど強度が高くなる一方で，計算量が大きくなり暗号化や復号，検証にかかる時間が増えるため，安全性と処理時間はトレードオフの関係にあります。 1990年代までは512ビットの合成数(78桁の素数の積)を用いるRSA-512も一般に利用されていましたが，1999年にオランダCWIを中心としたチームが300台のコンピュータを使用して6か月で分解に成功し，以降は完全に廃止されました。ただし米国の暗号輸出規制など歴史的背景経緯により，一部のサーバーやブラウザには512ビットのRSAによる暗号化通信の実装が残され，2015年にはFREAK攻撃と呼ばれるダウングレード攻撃のリスクがあることが判明しています。ここでは，実際に78桁程度の素数を利用して手動でRSA-512の秘密鍵・公開鍵を作成し，さらに逆に公開鍵の合成数(modulus)を一般数体篩法により素因数分解します。 *2025年現在，RSA暗号が素因数分解問題と同値であるかは厳密には未証明です。

素数探索

まずは512ビットの半素数(2つの素数の積で表される合成数)を作成するため，Rustでその半分の長さである256ビットの素数を準備します。基本的には，「任意の大きさの整数を作成」→「素数判定(試し割り)」→「素数判定(フェルマー法・ミラーラビンの素数判定法)」を繰り返します。初めに，暗号学的に安全な乱数を生成します。ここで，2以外の素数は必ず奇数であるため，最後のビットが0の場合は1に置き換えていることに注意してください。 ```Rust let mut rng = OsRng; let mut candidate = rng.gen_bigint(bits as u64); candidate.set_bit((bits - 1) as u64, true); candidate.set_bit(0, true); ``` ※任意精度の整数型としてBigIntを使用しています。次に，生成した数を小さな素数で試しに除算して，簡易的にフィルターを行います。 ```Rust const SMALL_PRIMES: &[u64] = &[3, 5, 7, 11, 13, 17, 19, 23, 29, 31]; for &p in SMALL_PRIMES.iter() { let p_big = BigInt::from(p); if n == &p_big { return true; } if n % &p_big == BigInt::zero() { return false; } } ```
フィルターを通り抜けた整数に対して，さらに確率的アルゴリズムであるフェルマーテスト，およびミラーラビンの素数判定法を利用して素数性を確認します。 ```Rust fn fermat_test(n: &BigInt, k: u32) -> bool { let two = BigInt::from(2); let three = BigInt::from(3); if n < &three { return n != &BigInt::from(2); } let mut rng = thread_rng(); let n_minus_one = n - BigInt::one(); for _ in 0..k { let a = rng.gen_bigint_range(&two, &n_minus_one); if a.modpow(&n_minus_one, n) != BigInt::one() { return true; } } false } ``` ```Rust fn miller_rabin_primality_test(n: &BigInt, k: u32) -> bool { if *n < BigInt::from(2u32) { return false; } if *n == BigInt::from(2u32) || *n == BigInt::from(3u32) { return true; } if n.is_even() { return false; } let one = BigInt::one(); let n_minus_one = n - &one; let mut d = n_minus_one.clone(); let mut r = 0; while d.is_even() { d >>= 1; r += 1; } let mut rng = OsRng; 'witness_loop: for _ in 0..k { let a = rng.gen_bigint_range(&BigInt::from(2u32), &(n_minus_one)); let mut x = a.modpow(&d, n); if x == one || x == n_minus_one { continue; } for _ in 1..r { x = x.modpow(&BigInt::from(2u32), n); if x == n_minus_one { continue 'witness_loop; } } return false; } true } ```
なお，フェルマーテストはフェルマーの小定理を応用したものですが，合成数にも関わらず全ての試行で小定理を満たしてしまう特殊な数(カーマイケル数)が存在します。ここでは，ミラーラビンの素数判定法と組み合わせることで偽陽性の確率を無視できるほど小さくしています。加えて，それぞれkを大きくすれば偽陽性の確率は小さくなりますが，その分処理時間が長くなる点に注意してください。最後に，生成した素数が「都合の良い数」( $ gcd(e, (p-1)(q-1)) = 1 $ を満たす)かどうかを判定します。具体的には，「生成した素数から1を減じた数」と「公開指数e」が同じ約数を持っている場合，不適当と判断して生成を最初からやり直します。 ```Rust if (candidate.clone() - BigInt::one()).gcd(e) != BigInt::one() { return false; } ``` なお，公開指数eには計算上の都合から65537が利用されることが多いです。公開指数の正体や理論的背景は[こちら](http://post1.s105.xrea.com/)がとても詳しいですので，興味があればご覧ください。

公開鍵・秘密鍵の作成

ここでは，生成した二つの素数を利用して，RSAの公開鍵及び秘密鍵を作成します。まずp, qから必要な係数を求めて，opensslが読み取れるASN.1形式で保存します。 ```Rust // p, q: 素数 let (p, q) = generate_rsa_primes(bits, &e); println!("p = {}", p); println!("q = {}", q); // n = pq (半素数) let n = &p * &q; // phi = (p-1)(q-1) let phi = (&p - BigInt::one()) * (&q - BigInt::one()); // d = pow(e, -1, phi) let e_int = BigInt::from(e.clone()); let phi_int = BigInt::from(phi.clone()); let d_int = modinv(&e_int, &phi_int).unwrap(); let d = d_int.to_bigint().unwrap(); // exp1 = d % (p-1) let exp1 = &d % (&p - BigInt::one()); // exp2 = d % (q-1) let exp2 = &d % (&q - BigInt::one()); // coeff = pow(q, -1, p) let q_int = BigInt::from(q.clone()); let p_int = BigInt::from(p.clone()); let coeff_int = modinv(&q_int, &p_int).unwrap(); let coeff = coeff_int.to_bigint().unwrap(); // ASN.1形式のファイル作成 let mut cnf = NamedTempFile::new().unwrap(); let content = format!( r#"asn1=SEQUENCE:private_key [private_key] version = INTEGER:0 n = INTEGER:0x{:x} e = INTEGER:0x{:x} d = INTEGER:0x{:x} p = INTEGER:0x{:x} q = INTEGER:0x{:x} exp1 = INTEGER:0x{:x} exp2 = INTEGER:0x{:x} coeff = INTEGER:0x{:x} "#, n, e, d, p, q, exp1, exp2, coeff, ); cnf.write_all(content.trim_start().as_bytes()).unwrap(); ```
次に，CNFファイルをopensslでDER形式に変換します。なお，{CNF-fp}には作成したCNFファイルのパス，{der-fp}には適当に保存用のパスを入れてください。 ```Bash openssl asn1parse -genconf {CNF-fp} -noout -out {der-fp} ```
そして最後に，DER形式のファイルから秘密鍵・公開鍵を生成します。 ```Bash openssl pkey -inform DER -in {der-fp} -out rsa-512bit-secret.pem openssl rsa -in rsa-512bit-secret.pem -pubout -out rsa-512bit-public.pem ```
こうして，無事に二つの素数から公開鍵と秘密鍵を生成できました！

一般数体篩法による素因数分解

以上の手順により生成した公開鍵から，今度は半素数を抽出して素因数分解を行うことにより，秘密鍵を復元してみます。冒頭で述べた通り，現在100桁以上の半素数に対して最速の素因数分解アルゴリズムは一般数体篩法です。ここでは，GGNFSをラップしたyafu(Yet Another Factorization Utility)で素因数分解を行います。参考までに，実験環境のCPUはi9 12900K，メモリは128GBです。セットアップ手順は[こちら](https://inaz2.hatenablog.com/entry/2016/01/14/230032)の記事を参考にしてください。以下のコマンドで分解が行えます。今回はRustからラップして処理状況を監視します。 ```Bash yafu-x64 nfs({分解対象}) -v -gnfs -noecm -threads {スレッド数} -logfile nfs.log ```
一般数体篩法による素因数分解が始まりました。

まずは，多項式選択と呼ばれる事前処理が行われています。具体的には，「小さい係数と根の性質を両立する"できるだけ良質な"多項式ペア」を探索しています。ここでの多項式選択が，後の「篩(sieving)」にかかる時間を大きく左右します。手元の環境では約140 CPU時間(実時間で69,112秒/20時間弱)を費やして16384個のエントリを生成し，その中で最も"良質な"以下の多項式が選択されました。 ```MarkDown hashtable: 16384 entries, 0.25 MB polynomial selection complete R0: -2055752729091053370382682567618 R1: 78342791118801263 A0: -2310436318581358451173074711152257200920787 A1: 24591457966004190108068816315009515 A2: 239441610325993425380188433 A3: -3863616659046710783 A4: -2127237534 A5: 180 skew 128208289.05, size 6.694e-015, alpha -8.865, combined = 3.437e-012 rroots = 1 elapsed time of 69112.6625 seconds exceeds 84375 second deadline; poly select done best poly: # norm 8.094728e-015 alpha -8.865382 e 3.437e-012 rroots 1 ```
そして次に，一般数体篩法で最も時間のかかる処理である「篩」(ふるい; sieving)が始まりました。これは選んだ多項式に対し，多数の「滑らか数」(多項式値が基底素数以下で分解可能な数)を集める作業です。

CPUの負荷が大きい一方で，メモリの使用量は1.4G～1.6GB程度と比較的少なめでした。手元の環境では一つの関係式を集めるのにかかる時間は0.085sec程度で，トータル約1048 CPU時間(実時間で424572秒/118時間弱)を費やしました。なお一度目の処理で45,017,477個の関係式を得たとき，うち7,282,327個が衝突し，不足分を再収集→重複の削除を繰り返して，最終的に50,019,646個(約5000万個)の関係式から4,656,702 x 4,656,929 (1349.7MB)の疎行列を得ています。

次に線形代数処理のフェーズです。フィルタリング後の巨大なスパース行列に対して，モジュラー2乗での零空間解を求めます。

12スレッドにも関わらずCPU使用率は600%前後と比較的低い水準でした。進捗状況の表示があるためか，意外と一瞬で終わったように感じます。

このフェーズには，約50 CPU時間(実時間で32314秒/約9時間)を費やしました。最後は，平方根計算です。線形代数で得られた線形結合をもとに，数体上と整数上で「平方根」を計算し，最終的に因数を得ます。比較的軽い処理になります。

そして，ついに素因数が見つかりました！！ ```MarkDown prp78 = 114074412250002386035870107165565243295980490218055634076503210269823844723171 prp77 = 57934657929081935858894052249826581143971385836860384154513016876406227070047 ```

ここまで全部合計して1238.837 CPU時間(core-hours)，実時間で526,530秒(146時間)です。途中のデバッグを含めると，計7日間を費やしています。

最後に

本記事では，手動で素数を発見して512bitのRSA暗号を生成した上で，さらにモジュラスとなる半素数を一般数体篩法により1240 CPU時間で素因数分解しました。もはやRSA-512は個人レベルの攻撃者によって復号可能であり，十分な安全性を保つことができないため，絶対に使用してはならないことをご理解頂けたかと思います。参考程度に，消費電力は300W/150時間で約1,500円程度になります。この計算量は，AWSのEC2で処理した場合，0.05 USD/vCPU-Hour，1 USD=¥144.60と仮定して，約8,965円にあたります。最後まで記事をご覧いただき有難うございました！

参考文献

“RSA暗号体験入門（第3章）.” post1.s105.xrea.com,http://post1.s105.xrea.com/ ももいろテクノロジー. “YAFUを使って大きな数を素因数分解してみる.” ももいろテクノロジー, 14 Jan. 2016,https://inaz2.hatenablog.com/entry/2016/01/14/230032 Gilchrist, Jeff. “Beginners Guide to NFS factoring using GGNFS and MSIEVE.”gilchrist.great-site.net,https://gilchrist.great-site.net/jeff/factoring/nfs_beginners_guide.html Kawanabe, Hiroki. “素因数分解プログラム GGNFS の性能測定.” Bachelor’s thesis,Tokyo University of Technology, 2007,http://meta.ccs.ee.tut.ac.jp/ich/thesis/papers/ugrad/2007/kawanabe2007.pdf 注: 厳密には半素数が511ビットであるためRSA-511にあたりますが，差異は無視できるほど小さいため，ここではRSA-512とさせていただきます。

【GNFS】高校生が1240コア時間で512bit RSAを分解してみた！