Cryptopals is a least priority thing I'm enjoying somewhat consistently; hence it has crazy lags. I started #8 in 2024 and here it is; every time I opened the file with the code it was like someone you knew long ago and now hardly recognize. But that's quite an exercise (and maybe a skill) too. That explains why the code sometimes looks funny even to myself; but if I take the time to groom it further I will just never finish as I progress as a developer more often than I open the file. Another explanation needed is about some mistakes preserved in the comments: primarily this code is for me to reflect when I stumble onto it later, and those help me to follow & recollect the things. It doesn't look like I will finish the set, but #57 is here.
use std::collections::HashMap;
use num_bigint::{BigUint, RandBigInt};
use num_traits::{Num, One, Zero};
use rand::{
rngs::OsRng,
seq::SliceRandom
};
const G: &'static str = "4565356397095740655436854503483826832136106141639563487732438195343690437606117828318042418238184896212352329118608100083187535033402010599512641674644143";
const Q: &'static str = "236234353446506858198510045061214171961";
fn biguint_from_str_decimal(s: &str) -> BigUint {
BigUint::from_str_radix(s, 10).unwrap()
}
fn main() {
let zero = BigUint::zero();
let one = BigUint::one();
let p = biguint_from_str_decimal("7199773997391911030609999317773941274322764333428698921736339643928346453700085358802973900485592910475480089726140708102474957429903531369589969318716771");
println!("the number of bits `p` takes:");
println!("{}", p.bits());
let j = biguint_from_str_decimal("30477252323177606811760882179058908038824640750610513771646768011063128035873508507547741559514324673960576895059570");
let g = biguint_from_str_decimal(G);
let q = biguint_from_str_decimal(Q);
println!("the number of bits `q` takes:");
println!("{}", q.bits());
assert!(&j * &q == &p - &one);
/*
> You don't need to factor it all the way. Just find a bunch of factors
smaller than, say, 2^16. There should be plenty. (Friendly tip: maybe
avoid any repeated factors. They only complicate things.) */
/* During debugging I took the advice on the small
factors. Until then I went with `HashMap`, and created
it `from([2])` (which wasn't the bright idea from a few
angles).
The logic was that doesn't participate in other small
factors, so "let's just add it here".
I wanted to go the complicated case to play with the
degree of each factor. But due to a mistake I had to
debug, I just checked that starting from $329$ all the
factors are degree $1$, and switched to `HashSet`
starting from that number to not change the code I've
already debugged. Not taking the suggested short-cut
should be an educatory refresher on CRT.
I didn't thought though that I brutely sieve here and
starting factoring from a number after the
tiny/repeating factors will introduce additional
factors (here it's one) which absorbs those repeating
and brings all the complications we were adviced to
avoid. So it's easier to sieve properly;
but then repeating factors are still dropped. */
let mut factors: HashMap<usize, usize> = HashMap::new();
let mut factoring = j.clone();
/* obvious optimization is replace the range for
the primes; then drop `rayon` in */
for m in 2..2usize.pow(16) {
if &factoring % m == zero {
*factors.entry(m).or_default() += 1;
// with `HashSet` it was the following
// let _new = factors.insert(m);
// debug_assert!(_new);
factoring /= m;
}
}
let mut factors = factors.into_iter().filter_map(
|(factor, degree)|
if degree == 1 {Some(factor)} else {None}
).collect::<Vec<_>>();
println!("{} factors will be used:", factors.len());
println!("{:?}", &factors);
/*
> ...we can use these to recover Bob's secret key using
the Pohlig-Hellman algorithm for discrete logarithms... */
let bob_key_priv = OsRng::default()
/* Actually it doesn't make sense to care about drawing
the zero since it's plainly improbable, but this is the
exclusion thing I still do; in the end of the day let's
hope the secret is a non-zero type. Earlier challenges
show that a correct way is to generate everything and
then check zero (in fact all trivial/special cases)
specifically. */
// .gen_biguint_below(&p)
.gen_biguint_range(
/* Continuing the previous note, this exclusion
always was mostly a joke or over caution; it was
cute to see I did this more than an year ago, and
just recently asked in a randomness dedicated group
if this ever makes any sense: they just reassured it
does not! */
// &BigUint::from(2u8).pow(80),
&one,
/* To me this is an interesting part of the
exercise! It designed so that the key is taken from
`q` which makes sense if think about it. But the
exercise is an opportunity to try what would happen
if we draw from `p`. Usually it's not that
interesting since an EC group would have a handful
of small order subgroups which without cofactor
clearance will be cycling pretty quick. But here we
have 512-bit field with somewhat sizeable factors.
#drawFromP */
// &p
&q
);
/* I guess over `q` I could try an arithmetic
MAC algorithm in this exercise. :notsure: */
let _bob_key_pub = g.modpow(
&bob_key_priv,
/* At some point I got confused in experimentaion.
#modulusConfusion #drawFromP */
// &q
&p
);
// assert_eq!(_bob_key_pub, g.modpow(
// &bob_key_priv,
// &q
// ));
let order = &p - &one;
let k_guess = |r: usize| -> (BigUint, BigUint, usize) {
/*
> 1. Take one of the small factors j. Call it r. We want to find an
element h of order r. ... */
assert_eq!(&order % r, zero);
let r_cofactor = (&order)/r;
assert_eq!(&r_cofactor % &q, zero);
let h = loop {
/* it's like cofactor clearing but for
a tiny factor instead of a proper */
let t = OsRng::default().gen_biguint_range(
&one, &p
).modpow(&r_cofactor, &p);
if
// dbg!(
&t
// )
> &one {break t;}
};
assert!(
&h.modpow(&BigUint::from(r), &p) == &one,
"we must be in a subgroup `r`"
);
/*
> 2. You're Eve. Send Bob h as your public key. Note that h is not a
valid public key! There is no x such that h = g^x mod p. ... */
let eve_key_pub = &h;
/*
> 3. Bob will compute:
>
> K := h^x mod p
>
> Where x is his secret key and K is the output shared secret. Bob
then sends back (m, t), with:
>
> m := "crazy flamboyant for the rap enjoyment"
t := MAC(K, m) */
let x = &bob_key_priv;
let k = eve_key_pub.modpow(
x,
&p
// #modulusConfusion
// &q
);
let t = mac::the(&k);
/*
> 4. ...
>
> ...there are only r possible values
of K that Bob could have generated. We can recover K by doing a
brute-force search over these values until t = MAC(K, m). */
let mut k_guessed = h.clone(); // could fail on additive identity, but we have kind of protection while drawing (instead of with types)
for _ in 0..r { // subgroup size should be $r-1$
if &t == &mac::the(&k_guessed) {
break;
}
k_guessed = (&k_guessed * &h)
// #modulusConfusion
// % &q;
% &p;
}
// let k_guessed = (0..r).into_par_iter().position_any(|guess| {
// &mac(&h.modpow(&guess.into(), &p)) == &t
// }).unwrap();
assert_eq!(
t, mac::the(&k_guessed),
"step \"4.\" encountered a problem with `r`:{}, `x`:{}, `t`:{:?}, `x % r`:{}", r, x, t, (x % r)
);
// let x_mod_r = (0..r).into_par_iter().position_any(
// |i| &k_guessed == &h.modpow(&i.try_into().unwrap(), //&r.into())
// ).unwrap();
/* degree of $h$ when it becomes equal to K */
let x_mod_r = {
let mut h_runner = one.clone();
let mut x_runner = 0;
while &k_guessed != &h_runner {
x_runner += 1;
h_runner = (h_runner * &h)
// #modulusConfusion
// % &q;
% &p;
};
x_runner
};
println!("{r} was chosen as another factor");
// dbg!(x_mod_r);
// dbg!(&bob_key_priv % r);
assert_eq!(
BigUint::from(x_mod_r),
&bob_key_priv % r
);
(k_guessed.into(), r_cofactor, x_mod_r)
};
/*
> 5. ... */
// let mut factors = factors.into_iter();
factors.shuffle(&mut OsRng);
let mut accumulated = one.clone();
let mut kk = Vec::new();
while &accumulated < &q {
let r = factors.pop().unwrap();
kk.push((r, k_guess(r)));
accumulated *= r;
}
// > ...reassemble Bob's secret key using the Chinese Remainder Theorem.
let product_factors_chosen = BigUint::from(
kk.iter().map(|&(f, ..)| f).product::<usize>()
);
let bob_key_priv_guessed = dbg!(kk.into_iter().map(
|(factor, (_, _cofactor, x_mod_factor))| {
let cofactor = &product_factors_chosen / factor;
// dbg!(
x_mod_factor * &cofactor * cofactor.modinv(
&BigUint::from(factor)
).unwrap()
// )
}
)
// .reduce(<BigUint as core::ops::Add>::add)).unwrap()
.sum::<BigUint>())
% product_factors_chosen;
// #drawFromP
// let mut bob_key_priv_guessed = bob_key_priv_guessed % &p;
// while dbg!(&bob_key_priv_guessed) >= &p {bob_key_priv_guessed *= bob_key_priv_guessed.clone();}
debug_assert_eq!(bob_key_priv, &bob_key_priv % &q);
// dbg!(dbg!(&bob_key_priv % &q) == dbg!(
// dbg![&bob_key_priv_guessed]
// // .modpow(&j, &p)
// % &q
// ));
println!("the Private key");
println!("{}", bob_key_priv);
// let variants_left = factors_cloned.into_iter().fold(p / q, |dived, factor| dived / factor);
// dbg!(variants_left);
assert!(bob_key_priv == bob_key_priv_guessed);
println!("The private key have been guessed correctly.");
// a tiny remnant I decided to keep of an experiment
// let bob_key_pub = mac(&bob_key_priv);
// if bob_key_pub == mac(&bob_key_priv_guessed) {println!("CORRECT");}
// else {println!("guessing FAILED");}
}
/// I remember I wanted to try something I either won't as
/// MAC is absolutely lateral here -- main point is just
/// grind the value out of a small set of possible. But to
/// play with 512-bit numbers and when I had a mistake in
/// the core thing I settled here with the most boring
/// variant. Still, again, this doesn't impact anything.
///
/// The options I considered for fun were quite different
/// to see another approaches.
/// https://docs.rs/cmac/latest/cmac/struct.CmacCore.html
/// https://docs.rs/dbl/0.3.2/dbl/trait.Dbl.html
/// https://docs.rs/threefish/latest/threefish/struct.Threefish512.html
mod mac {
use hmac::{digest::{
consts::U32, generic_array::GenericArray
}, Mac};
pub fn the(
k: &num_bigint::BigUint,// m: &[u8]
) -> GenericArray<u8, U32> /* BigUint */ {
// let k = k % &p;
// let mut t =
// <blake2::Blake2bMac::<blake2::digest::consts::U64> as blake2::digest::Mac>::new_from_slice(&k.to_bytes_le()).unwrap();
// blake2::digest::Update::update(&mut t, m);
// blake2::digest::Mac::finalize(t).into_bytes().to_vec()
// g.modpow(k, &p)
// let k = k % &q; // 128 bits
// let k_bytes = &k.to_bytes_le();
// let k_bytes =
// [k_bytes.as_slice(), &[0].repeat(16 - k_bytes.len())].concat();
// dbg!(k_bytes.len());
let mut mac = hmac::Hmac::<sha2::Sha256>::
new_from_slice(k.to_bytes_le().as_slice()).unwrap();
mac.update(b"crazy flamboyant for the rap enjoyment");
mac.finalize().into_bytes()
}
}
Top comments (0)