RustでRSAの素因数を解読する
RSA暗号
RSA（Rivest-Shamir-Adleman）暗号[1]は、公開鍵暗号方式[2]の一つで、データの暗号化と署名に使用されます。この方式は、ロナルド・リベスト[3][4]、アディ・シャミア[5]、レオナード・アデルマン[6]によって1977年に「A Method for Obtaining Digital Signatures and Public-Key Cryptosystems[7]」という論文として発表されました。RSAは、公開鍵と秘密鍵をキーペアとして、任意のデータを暗号化・復号化します。
RSAは、公開鍵と秘密鍵をキーペアとして、データの暗号化と復号化、デジタル署名の生成と検証に使用することができます。公開鍵は誰でも利用でき、メッセージを暗号化するために使用されますが、対応する秘密鍵は所有者だけが保持し、暗号文を復号するために使用されます。また、秘密鍵を使ってメッセージに署名し、その署名を公開鍵で検証することができるため、メッセージの真正性と送信者の認証を確立することを可能にします。この特性により、SSL/TLSなどのセキュアプロトコルや電子商取引、デジタル証明書の発行など、多くのセキュリティアプリケーションに活用されています。
RSA暗号は、主に素因数分解の難しさ、つまり桁数が大きい合成数を素因数分解するのが現実的に非常に困難であるという数学的な問題に依存しています[8]。桁数が大きい合成数というのは、公開鍵の一部である
実際に解読を行う前に、まずは鍵生成の過程について見ていきます。
鍵生成
RSAの鍵生成は、まず2つの大きな素数
この鍵生成を簡単なRustプログラムで実証してみます。
素数生成器
指定されたビット数を持つ大きな素数を生成します。あくまで概念実証を目的としているため、フェルマー[9]を使用していますが、より正確な結果を得るためにはミラー–ラビン素数判定法[10]を使うことが推奨されます。
フェルマーによる素数判定法は、確率的な方法で素数を判定する手法の一つです。この方法では、ある数が素数である確率的な確認を行いますが、完全な決定法ではないため、誤判定をする場合があります。フェルマーの小定理によると、もし
これを素数判定に利用するために、指定した数
この条件が満たされない場合、
fn is_probable_prime(n: &BigUint, k: usize) -> bool {
if n <= &BigUint::one() {
return false;
}
if n == &BigUint::from(2u32) || n == &BigUint::from(3u32) {
return true;
}
if n.is_even() {
return false;
}
let mut rng = thread_rng();
for _ in 0..k {
let a = rng.gen_biguint_range(&BigUint::from(2u32), n);
if a.modpow(&(n - BigUint::one()), n) != BigUint::one() {
return false;
}
}
true
}
fn generate_prime(bits: u64) -> BigUint {
let mut rng = thread_rng();
loop {
let candidate = rng.gen_biguint(bits);
if candidate.bits() < bits as u64 {
continue;
}
if is_probable_prime(&candidate, 50) {
return candidate;
}
}
}
鍵生成
RSA公開鍵と秘密鍵を生成する関数を実装します。出力として、素数
-
generate_prime(bits / 2)で2つの素数p q p q n -
n = p * q n - オイラーのトーシェント関数[11]
φ(n) = (p-1)(q-1) - 公開指数
e 65537に設定します[12]。 -
e φ(n) d mod_inverse関数を使用して求めます。
fn mod_inverse(a: &BigUint, m: &BigUint) -> Option<BigUint> {
let a_int = BigInt::from(a.clone());
let m_int = BigInt::from(m.clone());
let (g, s, _) = extended_gcd_bigint(&a_int, &m_int);
if g != BigInt::one() {
return None;
}
let mut result = s % &m_int;
if result < BigInt::zero() {
result += &m_int;
}
Some(result.to_biguint().unwrap())
}
fn generate_rsa_keys(bits: u64) -> (BigUint, BigUint, BigUint, BigUint) {
let p = generate_prime(bits / 2);
let q = generate_prime(bits / 2);
let n = &p * &q;
// φ(n) = (p-1)(q-1)
let phi_n = (&p - BigUint::one()) * (&q - BigUint::one());
let e = BigUint::from(65537u32); // Common public exponent (e)
// Compute the private exponent (d)
let d = mod_inverse(&e, &phi_n).expect("Failed to compute modular inverse");
(n.clone(), e.clone(), n, d)
}
RSAの暗号化および復号化を行う関数を実装します。上述したように、暗号化は
fn encrypt(message: &BigUint, e: &BigUint, n: &BigUint) -> BigUint {
if message >= n {
panic!("Message is too large for the key size");
}
message.modpow(e, n)
}
fn decrypt(ciphertext: &BigUint, d: &BigUint, n: &BigUint) -> BigUint {
ciphertext.modpow(d, n)
}
これをRustプログラムとして実装すると下記のようになります。
fn main() {
let bits = 512; // Bit length for the RSA modulus (n)
println!("Generating RSA keys with {}-bit modulus...", bits);
let (n, e, _, d) = generate_rsa_keys(bits);
println!("Public key (e, n):");
println!("e = {}", e);
println!("n = {}", n);
println!("\nPrivate key (d, n):");
println!("d = {}", d);
let message = BigUint::from(1234u32);
println!("\nOriginal message: {}", message);
let encrypted = encrypt(&message, &e, &n);
println!("Encrypted message: {}", encrypted);
let decrypted = decrypt(&encrypted, &d, &n);
println!("Decrypted message: {}", decrypted);
assert_eq!(message, decrypted, "Decryption failed!");
println!("\nVerification successful: original message matches decrypted message");
}
素因数分解を用いたRSA鍵の解読
ここまで、RSA暗号の安全性が大きな桁数の素因数分解に基づいていることがわかりました。ここからは、実際に素因数分解を用いてRSA公開鍵の
素因数分解を効率的に行うためのアルゴリズムには、単純な試し割り法から高度なアルゴリズムまでさまざまなものがあります。小さな数に対しては試し割り法が有効ですが、大きな数に対しては計算量が膨大になるため、より高度なアルゴリズムを選択する必要があります。
試し割り法
試し割り法は、2から順に素数で割っていくことで整数の素因数を求める基本的な方法です。計算量は
fn factorize(mut n: u64) -> Vec<u64> {
let mut factors = Vec::new();
while n % 2 == 0 {
factors.push(2);
n /= 2;
}
let mut i = 3;
while i * i <= n {
while n % i == 0 {
factors.push(i);
n /= i;
}
i += 2;
}
if n > 1 {
factors.push(n);
}
factors
}
楕円曲線法
楕円曲線法（Elliptic Curve Method：ECM）は、楕円曲線上での点の計算を使用して、与えられた数の因数を見つけることで素因数分解を行います。
楕円曲線法は、まず入力
ここで、
次に、選ばれた楕円曲線上での点を計算します。楕円曲線上の点は、整数のペア
最後の段階では、楕円曲線上で点の加算を繰り返し、その結果として得られる点を基に最大公約数（GCD）を計算します。これにより、次の式に基づいて
ここで、
楕円曲線法は、並列計算に適したアルゴリズムです。点の加算操作は独立して行えるため、複数の計算を同時に実行することで、計算時間を大幅に短縮できます。特に、複数の異なる楕円曲線を同時に使用することが可能で、各スレッドやプロセスが別々の曲線で点の加算を行うことでより並列化の恩恵を受けやすくなります。
Rustを用いた家庭用CPUによるRSA32の解読
このエクスペリメンタルでは、Rustとrayonを使用した並列の楕円曲線法を用いて、家庭用CPUの計算力のみでRSA32の公開鍵の係数
クレートを作成します。
cargo new experimental-01 --bin
依存関係を追加します。
[dependencies]
num-bigint = { version = "0.4", features = ["rand"] }
num-traits = "0.2"
num-integer = "0.1.46"
rand = "0.8.5"
rsa = "0.9.7"
rayon = "1.10.0"
clap = { version = "4.5.31", features = ["derive"] }
楕円曲線法によるFactorizerの実装
楕円曲線法のコンセプトに従ってファクトライザを実装します。
点
楕円曲線法における点を表す構造体を定義します。
#[derive(Clone, Debug)]
struct Point {
x: BigUint,
y: BigUint,
}
GCDの計算
拡張ユークリッド[13]の互除法を使用して、与えられた2つの整数
fn extended_gcd(a: &BigInt, b: &BigInt) -> (BigInt, BigInt, BigInt) {
if b.is_zero() {
(a.clone(), BigInt::one(), BigInt::zero())
} else {
let (g, x, y) = extended_gcd(b, &(a % b));
(g, y.clone(), x - (a / b) * y)
}
}
逆数の計算
与えられた
fn modinv(a: &BigUint, n: &BigUint) -> Option<BigUint> {
let a_int = BigInt::from(a.clone());
let n_int = BigInt::from(n.clone());
let (g, x, _) = extended_gcd(&a_int, &n_int);
if g != BigInt::one() {
return None; // g is a nontrivial factor
}
let mut inv = x % &n_int;
if inv.is_negative() {
inv += &n_int;
}
inv.to_biguint()
}
楕円曲線上の点の2倍を計算
楕円曲線上の点
ここで、Pointは点の座標
fn point_double(P: &Point, a: &BigUint, n: &BigUint) -> Result<Point, BigUint> {
if P.y.is_zero() {
return Err(BigUint::zero());
}
let three = BigUint::from(3u32);
let two = BigUint::from(2u32);
let numerator = (three * &P.x * &P.x + a) % n;
let denominator = (two.clone() * &P.y) % n;
let g = denominator.gcd(n);
if g > BigUint::one() && g < *n {
return Err(g);
}
let inv = modinv(&denominator, n).ok_or(denominator.clone())?;
let lambda = (numerator * inv) % n;
let x_r = (&lambda * &lambda + n - (two * &P.x) % n) % n;
let y_r = ((&lambda * ((&P.x + n - &x_r) % n)) + n - &P.y) % n;
Ok(Point { x: x_r, y: y_r })
}
2つの楕円曲線上の点を加算
2つの楕円曲線上の点 Errとして返します。
fn point_add(p: &Point, q: &Point, a: &BigUint, n: &BigUint) -> Result<Point, BigUint> {
if p.x == q.x && p.y == q.y {
return point_double(p, a, n);
}
// lambda = (y2 - y1) / (x2 - x1) mod n.
let numerator = if q.y >= p.y {
(&q.y - &p.y) % n
} else {
((&q.y + n) - &p.y) % n
};
let denominator = if q.x >= p.x {
(&q.x - &p.x) % n
} else {
((&p.x + n) - &q.x) % n
};
let g = denominator.gcd(n);
if g > BigUint::one() && g < *n {
return Err(g);
}
let inv = modinv(&denominator, n).ok_or(denominator.clone())?;
let lambda = (numerator * inv) % n;
let x_r = (&lambda * &lambda + n + n - &p.x - &q.x) % n;
let y_r = ((&lambda * ((&p.x + n - &x_r) % n)) + n - &p.y) % n;
Ok(Point { x: x_r, y: y_r })
}
楕円曲線の点のスカラー倍を計算
与えられた楕円曲線の点 Errとして返します。
fn scalar_mul(P: &Point, k: &BigUint, a: &BigUint, n: &BigUint) -> Result<Point, BigUint> {
let mut result: Option<Point> = None;
let mut addend = P.clone();
let mut k_bits = k.clone();
while !k_bits.is_zero() {
if &k_bits & BigUint::one() == BigUint::one() {
result = match result {
None => Some(addend.clone()),
Some(r) => match point_add(&r, &addend, a, n) {
Ok(sum) => Some(sum),
Err(factor) => return Err(factor),
},
};
}
k_bits >>= 1;
if k_bits.is_zero() {
break;
}
addend = match point_double(&addend, a, n) {
Ok(dbl) => dbl,
Err(factor) => return Err(factor),
};
}
result.ok_or_else(|| BigUint::zero())
}
エラトステネスの篩による素数列の生成
与えられた上限 limit までの素数をエラトステネスの篩を使ってリストとして返します。
fn small_primes_up_to(limit: u64) -> Vec<u64> {
let mut sieve = vec![true; (limit + 1) as usize];
let mut primes = Vec::new();
if limit >= 1 {
sieve[1] = false;
}
for num in 2..=limit as usize {
if sieve[num] {
primes.push(num as u64);
let mut multiple = num * num;
while multiple <= limit as usize {
sieve[multiple] = false;
multiple += num;
}
}
}
primes
}
楕円曲線法の試行
楕円曲線法を1回試み、与えられた数 Some(factor) を返し、見つからなかった場合は None を返します。
fn ecm_attempt(n: &BigUint, seed: u64) -> Option<BigUint> {
let mut rng = StdRng::seed_from_u64(seed);
let x = rng.gen_biguint_range(&BigUint::one(), n);
let y = rng.gen_biguint_range(&BigUint::one(), n);
let a = rng.gen_biguint_range(&BigUint::one(), n);
let p = Point {
x: x.clone(),
y: y.clone(),
};
let b1: u64 = 1000; // Stage-1 bound.
let primes = small_primes_up_to(b1);
let mut q = p;
for &p in &primes {
let mut pp = p;
while pp <= b1 {
let exp = BigUint::from(pp);
match scalar_mul(&q, &exp, &a, n) {
Ok(r) => {
q = r;
}
Err(factor) => {
if factor > BigUint::one() && factor < *n {
return Some(factor);
}
}
}
pp *= p;
}
}
None
}
ファクトライザ
楕円曲線法を用いて、与えられた数
pub fn factorize_ecm(n: BigUint) -> Vec<BigUint> {
if n == BigUint::one() {
return vec![n];
}
for &p in &small_primes_up_to(10000) {
let p_big = BigUint::from(p);
if &n % &p_big == BigUint::zero() {
return vec![p_big.clone(), (&n / &p_big)];
}
}
let seeds: Vec<u64> = (0..1000).collect();
if let Some(factor) = seeds.par_iter().find_map_any(|&seed| ecm_attempt(&n, seed)) {
let other = &n / &factor;
let mut factors = factorize_ecm(factor);
factors.extend(factorize_ecm(other));
return factors;
}
vec![n]
}
実際にRSA32を解読してみる
さっそく実装したファクトライザを使用してRSA32を素因数分解します。パラメータとして解読する鍵のビット数、並列化のスレッド数を指定できるようにします。ビット数は、家庭用CPUでは32ビットが最も安定します。
#[derive(Parser, Debug)]
struct Args {
/// The bits of RSA key-pair to factorize with
#[clap(long, short, default_value_t = 32)]
bits: usize,
/// The number of threads for parallel factorization
#[clap(long, short, default_value_t = 16)]
num_threads: usize,
}
エントリは下記のようになります。
fn main() {
let args = Args::parse();
let mut rng = OsRng;
rayon::ThreadPoolBuilder::new()
.stack_size(8 * 1024 * 1024)
.num_threads(args.num_threads)
.build_global()
.expect("failed to create the threadpool");
println!("Generating a {}-bit RSA key pair...", args.bits);
let private_key = RsaPrivateKey::new(&mut rng, args.bits).expect("Cannot generate private key");
let public_key = RsaPublicKey::from(&private_key);
let n = BigUint::from_bytes_be(&public_key.n().to_bytes_be());
println!("RSA Modulus (N): {}", n);
let rsa_primes = private_key.primes();
let p = BigUint::from_bytes_be(&rsa_primes[0].to_bytes_be());
let q = BigUint::from_bytes_be(&rsa_primes[1].to_bytes_be());
println!("Expected Factors (p, q): ({}, {})", p, q);
println!("Running factorizer...");
let start = Instant::now();
let factors = factorizer::factorize_ecm(n);
println!("Factors: {:?}", factors);
println!("Factorizer took {:?}", start.elapsed());
if factors.len() == 1 {
println!("Factorization failed");
} else {
let mut expected = [&p, &q];
let mut actual = [&factors[0], &factors[1]];
expected.sort();
actual.sort();
assert_eq!(expected, actual, "cannot verify factors");
println!("OK. Factors are correct!");
}
}
これを実行してみます。
cargo run -- --bits=32 --num_threads=16
ランダムに生成されたRSAの係数
Generating a 32-bit RSA key pair...
RSA Modulus (N): 3359727781
Expected Factors (p, q): (58427, 57503)
Running factorizer...
Factors: [57503, 58427]
Factorizer took 7.9826219s
OK. Factors are correct!
Rustの最適化を活用してみます。
[profile.release]
lto = true
codegen-units = 1
opt-level = 3
cargo run --release -- --bits=32 --num_threads=16
最適化によって5-7秒程度に縮まりました。
Generating a 32-bit RSA key pair...
RSA Modulus (N): 2800796003
Expected Factors (p, q): (51659, 54217)
Running factorizer...
Factors: [54217, 51659]
Factorizer took 5.5216837s
OK. Factors are correct!
B1パラメータの最適化
楕円曲線法におけるb1は、第1段階（Stage 1）で使用される素数の上限を決定する滑らかさの境界値（smoothness bound）です。この値を大きくすると、より大きな素因数を持つ数を効率的に分解できる可能性が高まりますが、比例して計算コストも増加します。
このb1をパラメータとして指定できるようにしてみます。
-fn ecm_attempt(n: &BigUint, seed: u64) -> Option<BigUint> {
+fn ecm_attempt(n: &BigUint, seed: u64, b1: u64) -> Option<BigUint> {
-pub fn factorize_ecm(n: BigUint) -> Vec<BigUint> {
+pub fn factorize_ecm(n: BigUint, b1: u64) -> Vec<BigUint> {
#[derive(Parser, Debug)]
struct Args {
/// The bits of RSA key-pair to factorize with
#[clap(long, short, default_value_t = 32)]
bits: usize,
/// The number of threads for parallel factorization
#[clap(long, short, default_value_t = 16)]
num_threads: usize,
+ /// The stage 1 smoothness bound (B1) for ECM.
+ #[clap(long, short, default_value_t = 1000)]
+ stage1: u64,
}
RSA32を
cargo run --release -- --bits=32 --num_threads=16 --stage1=100
実行時間がわずか87ミリ秒（10x）になりましたが、正答率が損なわれていることがわかります。このb1はパラメータは--bits幅に応じて最適な値を指定することで、正答率とパフォーマンスの間でバランスを取ることができます。
Generating a 32-bit RSA key pair...
RSA Modulus (N): 3450068801
Expected Factors (p, q): (61153, 56417)
Running factorizer...
Factors: [56417, 61153]
Factorizer took 87.5654ms
OK. Factors are correct!
Generating a 32-bit RSA key pair...
RSA Modulus (N): 3341702863
Expected Factors (p, q): (57559, 58057)
Running factorizer...
Factors: [3341702863]
Factorizer took 53.3025ms
Factorization failed
RSA512とその先
楕円曲線法は、中小規模の素因数を見つけることに非常に長けています。一方で、RSA512などの非常に桁数の大きい素因数分解には向いていません。特に、楕円曲線法（ECM）では、各試行でランダムに楕円曲線と初期点を選び、曲線の群の位数が目標とする素因数
現在は非推奨となっているRSA512は、1999年にRSA Laboratoriesによって、凡そ半年をかけて解読されました[14][8:1]。これには、一般数体篩法（General Number Field Sieve：GNFS）[15]が使われました。一般数体篩法は大きな桁数を持つ整数の素因数分解について、高効率を有するアルゴリズムのひとつです。ただし、これには計算の複雑性や、事前準備に多くの時間を費やす必要があるという点があります。
使われたコンピュータの種類は、160台の175～400MHzのSGIとSunのワークステーション、8台の250MHz SGI Origin 2000プロセッサ、120台の300-450MHzのPentium2 PC、4台の500MHz Digital/Compaq CPUとなっている[14:1]。
また、量子ビットによるショアのアルゴリズム[16]などのトピックも非常に興味深いです。
-
RC4（Rivest Cipher 4）の作者としても知られています。 ↩︎
-
https://en.wikipedia.org/wiki/Miller–Rabin_primality_test ↩︎
-
これは一般的な公開指数で、比較的安全な選択とされています。 ↩︎
-
https://internet.watch.impress.co.jp/www/article/1999/0827/rsa.htm ↩︎ ↩︎
Discussion