Skip to content

Instantly share code, notes, and snippets.

@AlexanderKud

AlexanderKud/kangaroo.rs

Forked from d0nutptr/kangaroo.rs
Created January 6, 2025 01:44
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save AlexanderKud/1cf7b0126e6649f4fbaa53c10f335e38 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save AlexanderKud/1cf7b0126e6649f4fbaa53c10f335e38 to your computer and use it in GitHub Desktop.
Download ZIP
Pollard's Kangaroo Method Algorithm
Raw
kangaroo.rs
extern crate rand;
extern crate num;
use kangaroo::rand::Rng;
use num::ToPrimitive;
use num::{Integer, Zero, One};
use std::collections::HashMap;
use std::sync::Mutex;
#[derive(Debug)]
pub struct DiscreteLogParameters {
pub prime: num::BigInt,
pub generator: num::BigInt,
pub result: num::BigInt,
}
#[derive(Debug)]
struct JumpParameters {
jump_count: num::BigInt,
jump_group: num::BigInt,
}
#[derive(Debug)]
struct JumpResult {
position: num::BigInt,
distance_jumped: num::BigInt,
}
lazy_static! {
static ref POWER_MOD_MAP: Mutex<HashMap<(num::BigInt, num::BigInt, num::BigInt), num::BigInt>> = Mutex::new(HashMap::with_capacity(1_000));
}
pub fn calculate_discrete_log(params: &DiscreteLogParameters) -> Option<num::BigInt> {
let jump_params: JumpParameters = get_bounds(&params);
let tame_initial_offset: u32 = {
let mut rng = rand::thread_rng();
let result: num::BigInt = (num::BigInt::from(rng.gen::<u32>() as i64) % (&params.prime - 1)) + 1;
result.to_u32().unwrap()
};
println!("Performing tame jumps...");
let tame_jumps = perform_tame_jumps(&num::BigInt::from(tame_initial_offset as i64), &params, &jump_params);
println!("Performing wild jumps...");
let wild_jumps = perform_wild_jumps(&params, &jump_params);
for i in wild_jumps.keys() {
if tame_jumps.contains_key(i) {
//we mod by the cardinality of the group which is totient(prime) = prime - 1
//because the result is technically: x + k * totient(prime)
let mut result = (tame_initial_offset
+ tame_jumps.get(i).unwrap()
- wild_jumps.get(i).unwrap()) % (&params.prime - 1);
result = result + &params.prime - 1;
result = result % (&params.prime - 1);
return Some(result);
}
}
return None;
}
fn perform_tame_jumps(tame_initial_offset: &num::BigInt, params: &DiscreteLogParameters, jump_params: &JumpParameters) -> HashMap<num::BigInt, num::BigInt> {
let mut jumps = HashMap::with_capacity(&jump_params.jump_count.to_usize().unwrap() + 1);
let tame_initial_position = calculate_initial_tame_location(tame_initial_offset, &params);
let mut previous_position = tame_initial_position;
let mut total_distance = num::BigInt::zero();
let mut iterator = num::BigInt::one();
while iterator <= jump_params.jump_count {
let result = calculate_jump(&previous_position, &params, &jump_params);
previous_position = result.position;
total_distance = total_distance + result.distance_jumped;
jumps.insert(previous_position.clone(), total_distance.clone());
iterator = iterator + 1;
}
return jumps;
}
fn perform_wild_jumps(params: &DiscreteLogParameters, jump_params: &JumpParameters) -> HashMap<num::BigInt, num::BigInt> {
let mut jumps = HashMap::with_capacity(jump_params.jump_count.to_usize().unwrap() + 1);
let mut previous_position = params.result.clone();
let mut total_distance = num::BigInt::zero();
let mut iterator = num::BigInt::one();
while iterator <= jump_params.jump_count {
let result = calculate_jump(&previous_position, &params, &jump_params);
let position = result.position.clone();
previous_position = position;
total_distance = total_distance + result.distance_jumped;
jumps.insert(previous_position.clone(), total_distance.clone());
iterator = iterator + 1;
}
return jumps;
}
fn calculate_initial_tame_location(tame_initial_offset: &num::BigInt, discrete_params: &DiscreteLogParameters) -> num::BigInt {
power_mod(&discrete_params.generator, tame_initial_offset, &discrete_params.prime)
}
fn calculate_jump(previous_position: &num::BigInt, discrete_params: &DiscreteLogParameters, jump_params: &JumpParameters) -> JumpResult {
let jump_power = previous_position % &jump_params.jump_group;
let distance = &num::BigInt::one() << jump_power.to_usize().unwrap(); //2 ^ jump_power
let new_position = (previous_position
* power_mod(&discrete_params.generator,
&distance,
&discrete_params.prime))
% &discrete_params.prime;
return JumpResult {
position: new_position,
distance_jumped: distance
};
}
/* left for posterity
pub fn big_power(base: &num::BigInt, power: &num::BigInt) -> num::BigInt {
if power.is_zero() {
num::BigInt::one()
}
else if power.eq(&num::BigInt::from(1)) {
base.clone()
} else {
let new_base = base * base;
let new_power = power >> 1;
let base_modifier = if power.is_even() { num::BigInt::one() } else { base.clone() };
base_modifier * big_power(&new_base, &new_power)
}
}
*/
pub fn power_mod(base: &num::BigInt, power: &num::BigInt, group: &num::BigInt) -> num::BigInt {
let map_key = (base.clone(), power.clone(), group.clone());
let has_entry = POWER_MOD_MAP.lock().unwrap().contains_key(&map_key);
let result = if power.eq(&num::BigInt::one()) {
base.clone()
} else if has_entry {
POWER_MOD_MAP.lock().unwrap().get(&map_key).unwrap().clone()
} else {
let new_base = (base * base) % group;
let new_power = power >> 1;
let base_modifier = if power.is_even() { num::BigInt::one() } else { base.clone() };
base_modifier * power_mod(&new_base, &new_power, group)
} % group;
if !has_entry {
POWER_MOD_MAP.lock().unwrap().insert((base.clone(), power.clone(), group.clone()), result.clone());
}
return result;
}
/// Returns a result that is guaranteed to be sqrt(value) <= x < 2 * sqrt(value)
fn rough_sqrt(value: &num::BigInt) -> num::BigInt {
let result = value.clone();
let bits = log_2_floor(&result);
result >> (bits >> 1).to_usize().unwrap()
}
fn log_2_floor(value: &num::BigInt) -> num::BigInt {
num::BigInt::from(value.bits() as i64 - 1)
}
fn get_bounds(params: &DiscreteLogParameters) -> JumpParameters {
let jump_count = rough_sqrt(&params.prime);
let jump_group = log_2_floor(&params.prime);
return JumpParameters {
jump_count,
jump_group
};
}
Raw
main.rs
#[macro_use]
extern crate lazy_static;
use std::env;
mod kangaroo;
extern crate num;
enum CliParams {
Generator = 1,
Prime = 2,
Result = 3,
}
fn main() {
let result = get_parameters();
match result {
Some(params) => {
let discrete_log = kangaroo::calculate_discrete_log(&params);
match discrete_log {
Some(log) => println!("{}", log),
None => println!("-1")
};
},
_ => {},
}
}
fn get_parameters() -> Option<kangaroo::DiscreteLogParameters> {
let params: Vec<String> = env::args().collect();
//execution path + 3 cli parameters
if params.len() == 4 {
return Some(kangaroo::DiscreteLogParameters {
prime: params[CliParams::Prime as usize].parse::<num::BigInt>().unwrap(),
generator: params[CliParams::Generator as usize].parse::<num::BigInt>().unwrap(),
result: params[CliParams::Result as usize].parse::<num::BigInt>().unwrap(),
});
} else {
print_help();
return None;
}
}
fn print_help() {
println!("Calculates discrete logs using Kangaroo Method from Pollard");
println!("Solves log_<base>(<result>) = `x` for multiplicative group mod <prime>");
println!("Expects 32 bit integers for all parameters\n");
println!("Usage: kangaroo <base> <prime> <result>");
println!("Returns 32 integer result if successful, -1 otherwise.");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment