A concise write-up on Cryptopals challenge #48. See <https://dev.to/skaunov/cryptopals-challenge-48-solution-5dam> for context.

Cargo.toml

[package]
name = "challenges-47"
version = "0.1.0"
edition = "2021"

[dependencies]
rsa = "*"
rand = "*"
num-traits = "*"
num-bigint-dig = "*"

main.rs

use rsa::{PublicKey, RsaPrivateKey, RsaPublicKey, PaddingScheme, BigUint, PublicKeyParts};
use num_traits::{pow::Pow, Zero};

#[derive(Debug, Clone)]
/// Define intervals which are iteratively computed guess after guess.
struct IntervalM {start: BigUint, finish: BigUint}
impl IntervalM {
    /// Create new interval if provided boundaries doesn't give an empty interval.
    pub fn new(start: &BigUint, finish: &BigUint) -> Result<Self, ()> {
        if start > finish {Err(())}
        else {Ok(Self{start: start.clone(), finish: finish.clone()})}
    }
    /// Update interval if provided values narrow current width of the interval.
    pub fn update(&mut self, start: &BigUint, finish: &BigUint) -> () {
        if start < &self.start {
            println!("#log: start value is outside of current bounds");
        }
        else if finish > &self.finish {
            println!("#log: finish value is outside of current bounds");
        }
        else {
            self.start = start.clone();
            self.finish = finish.clone();
        }
    }
}

fn main() {
    let mut rng = rand::thread_rng();

    // "this time generate a 768 bit modulus" https://cryptopals.com/sets/6/challenges/48
    let bits = 768;
    let private_key = RsaPrivateKey::new(
        &mut rng, bits
    ).unwrap();
    let public_key = RsaPublicKey::from(&private_key);
    
    // Modulus and exponent values will be used a lot. The name is chosen in favor of used in [bleichenbacher98].
    let n = public_key.n();
    let e = public_key.e();
    
    /*  "Build an oracle function, just like you did in the 
last exercise, but have it check for plaintext[0] == 0 and plaintext[1] == 2." [cryptopals] */
    let oracle = |ct: Vec<u8>| -> bool {
        /* Crates own method is protected from most naive attempts to make an oracle, and needs either modification of the crate to delete basic protection, or quite 
        sophisticated methods to get relevant for oracle response. */
            // let pt = private_key.decrypt(
            //     PaddingScheme::new_pkcs1v15_encrypt(), &ct
            // ).unwrap_or_else(|x| {vec![1, 0]});
        // Let's stick to the most naive way to construct the oracle.
        let mut pt = BigUint::from_bytes_be(&ct).modpow(
            private_key.d(), n
        ).to_bytes_be();
            /* Sorry for some patchy hard coding here. Sometimes resulting big number is represented by less number of bytes that is expected in cipher system. It's not 
            the best way to extend the vector, though it's small and works for the challenge. */
        if pt.len() < 96 {pt = [vec![0; 96-pt.len()], pt].concat()};
        if pt[0] == 0 && pt[1] == 2 {true}
        else {false}
    };

    /* " PKCS1.5-pad a short message, like "kick it, CC", and call it "m". Encrypt to to get "c". "  [cryptopals]*/
    let m = b"kick it, CC";
    let c = public_key.encrypt(
        &mut rng, 
        PaddingScheme::new_pkcs1v15_encrypt(), 
        m
    ).unwrap();
    let c_biguint = BigUint::from_bytes_be(&c);

    // https://docs.rs/rsa/latest/rsa/struct.RsaPublicKey.html#impl-PublicKeyParts-for-RsaPublicKey
    // "Recall that k is the length of n in bytes." [bleichenbacher98]
    let B: BigUint = BigUint::new(vec![2]).pow(8 * (public_key.size() - 2));
    /* "search for the smallest positive integer s1 ≥ n/(3B)" [bleichenbacher98] */
    let mut s_1 = n / (3usize * &B) 
        // next check is commented out in spite of just adding 1 as it's always `true` as {n=p*q}, which aren't divisible by 3
        // if n % (3usize * &B) != BigUint::zero() {s_1 += 1usize;} 
        + 1usize;
    
    // We will heavily use "RSA multiplication" to get {c'} which will be checked against the oracle.
    let multiplication_rsa = |s: &BigUint| (&c_biguint * s.modpow(e, n)) % n;
    let mut c_prime = multiplication_rsa(&s_1);
    
    // basic test of oracle and correctness of set up
    let checkOracle = oracle(c);
    println!("**naive** oracle check: {checkOracle}");
    
    let mut counter_liveness = 0;
    while !oracle(c_prime.to_bytes_be()) {
        s_1 += 1usize;
        c_prime = multiplication_rsa(&s_1);

        counter_liveness += 1;
        // #48 takes _much_ longer to iterate in search for conforming value, so a liveness indicator is here
        if (counter_liveness % 1000 == 0) {println!("{counter_liveness}");}
    }
    println!("**I found `s_1`!!**");
    println!("{s_1}");

    // generating possible intervals and reducing them to one
    let mut intervals: Vec<IntervalM> = vec![];
        // compensate for initial increment `s_i` in the initial run of the loop
    let mut s_i = s_1 - 1usize;
    while intervals.len() != 1 {
        s_i += 1usize;
        println!("`r` range is following");
        let dividend = 2usize * &B * &s_i - 3usize * &B + 1usize;
        let mut r_from = ((&dividend) / n) + ((dividend % n != BigUint::zero()) as usize);
        let r_to = ((3usize * &B - 1usize) * &s_i - 2usize * &B) / n;
        println!("{r_from}, {r_to}");

            // sorry for a clumsy hack for range here
        for r_an in r_from.to_string().parse::<usize>().unwrap()..=r_to
            .to_string().parse::<usize>().unwrap() 
        {
            let dividend = 2usize * &B + r_an * n;
            let start = ((&dividend) / &s_i) + ((dividend % &s_i != BigUint::zero()) as usize);
            let finish = (3usize * &B - 1usize + r_an * n) / &s_i;
            let res = IntervalM::new(&start, &finish);
            match res {
                Ok(interval) => intervals.push(interval),
                Err(()) => {}
            }
        }
        println!("{intervals:?}");

        intervals.retain(|interval| {
            interval.start <= 3usize * &B && interval.finish >= 2usize * &B
        });
    }

    // after we singled out an interval, we come the step "c" of [bleichenbacher98]
    let mut r_cStep;
    let mut interval_single = intervals[0].clone();
    let mut s_left;
    let mut s_right;
    // shrink the interval to single value
    while &interval_single.start != &interval_single.finish {
        let dividend = &interval_single.finish * &s_i - 2usize * &B;
        r_cStep = 2usize * &dividend / n + ((dividend % n != BigUint::zero()) as usize);
        let dividend = 2usize * &B + &r_cStep * n;
        s_left = &dividend / &interval_single.finish 
            + ((dividend % &interval_single.finish != BigUint::zero()) as usize);
        s_right = (3usize * &B + &r_cStep * n) / &interval_single.start;
        s_i = s_left;
        // try `s_i` until it hit the bound calculated for it
        while !oracle(multiplication_rsa(&s_i).to_bytes_be()) {
            s_i += 1usize;
            // if all `s_i` are tried, then try next _r_
            if s_i > s_right.clone() {
                r_cStep += 1usize;
                let dividend = 2usize * &B + &r_cStep * n;
                s_left = &dividend / &interval_single.finish 
                    + ((dividend % &interval_single.finish != BigUint::zero()) as usize);
                s_right = (3usize * &B + &r_cStep * n) / &interval_single.start;
                s_i = s_left.clone().max(s_i /* + 1usize */);
            }
        }
        
        println!("binary search; conforming *s_i*");
        println!("{s_i}");

        let dividend = &interval_single.start * &s_i - 3usize * &B + 1usize;
        let r_from = &dividend / n + ((dividend % n != BigUint::zero()) as usize);
        let r_to = (&interval_single.finish * &s_i - 2usize * &B) / n;
        println!("`r` range: {r_from}, {r_to}");
            // that clumsy range hack again
        let r_diff = (r_to - &r_from).to_string().parse::<usize>().unwrap();
        for r_plus in 0..=r_diff {
            let r_an = &r_from + r_plus;
            let dividend = 2usize * &B + &r_an * n;
            let interval_r_start = &dividend / &s_i + 
                ((&dividend % &s_i != BigUint::zero()) as usize);
            let interval_r_finish = (3usize * &B - 1usize + &r_an * n) / &s_i;
            interval_single.update(&interval_r_start, &interval_r_finish);
        }
    }
    
    println!("{s_i}|final *s_i*");
    let solution = interval_single.start % n;
    println!("{solution}|the solution");
    bignumToText(solution);
}
// [cryptopals]: https://cryptopals.com/sets/6/challenges/47

fn bignumToText(solution: BigUint) -> () {
    let solution_msg = solution.to_bytes_be();
    println!("{solution_msg:?}");
    let solution_str = String::from_utf8_lossy(&solution_msg);
    print!("{solution_str}");
}

// [bleichenbacher98]: https://archiv.infsec.ethz.ch/education/fs08/secsem/bleichenbacher98.pdf