Cryptopals challenge #33: Implement Diffie-Hellman

As usual, after dealing with a challenge, which taught me something, I looked around to see how my solution differs from others. And this time mine turned out to be rather unique.

No, it's not good (and even not excellent). =) I wanted to see how people solved modexp part, and I was interested in Rust solutions. All I opened were using modpow function of bigint crate.

After all it said "write your own modexp", and it felt as a useful part of the exercise. So I employed crypto_bigint crate, and constructed a function for this particular exercise. It's slow and limited to work with 192 bytes integers, but it's still capable to inspire you to tackle this challenge. (Also it should have a problem with exceed bit for big enough numbers, you can take a bigger bigint type if you want to avoid it.)

use crypto_bigint::{
    U1536, Checked, NonZero, Random, 
    rand_core::OsRng, Encoding, U3072
};
use sha3::{Sha3_256, Digest};

fn main() {
    let p = U1536::from_be_hex("ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff");
    let g = U1536::from(2u64);

    let a = U1536::random(&mut OsRng);
    let a_big = modexp(g, a, p);
    let b = U1536::random(&mut OsRng);
    let b_big = modexp(g, b, p);

    let s = modexp(b_big, a, p);

    println!("{s}");

    let mut hasher = Sha3_256::new();
    hasher.update(s.to_be_bytes());
    let result = hasher.finalize();
    println!("{result:?}");
}

fn modexp(
    base: U1536, exponent: U1536, modulus: U1536
) -> U1536 {
    if modulus == U1536::ONE {return U1536::ZERO;}

    let modulus_ch = Checked::new(modulus);
    /* This algorithm is mostly based on Wikipedia
    listing, and the next line is to test the 
    assertion they have. `unwrap`s below turned out 
    to be much more useful during debuggig. */
    (modulus_ch - Checked::new(U1536::ONE)) 
        * (modulus_ch - Checked::new(U1536::ONE));

    let mut result = Checked::new(U3072::ONE);

    let mut base = U1536::from(base);
    let mut base = base % NonZero::new(modulus)
        .unwrap();

    let mut base = U3072::from_be_bytes(
        pad192(base)
    );
    let mut base = Checked::new(base);

    let mut modulus = U3072::from_be_bytes(
        pad192(modulus)
    );

    let mut exponent = exponent;
    while exponent > U1536::ZERO {
        if exponent % NonZero::new(U1536::from(
            2u64
        )).unwrap() == U1536::ONE {
            result = Checked::new(
                (result * base).0.unwrap() 
                    % NonZero::new(modulus)
                        .unwrap()
            );
        }
        exponent >>= 1;
        base = Checked::new(
            (base * base).0.unwrap() 
                % NonZero::new(modulus).unwrap()
        );
    }
    /* It should be checked that excessive bytes are 
    zero, but today we omit the check. They really 
    should after `% p` */
    U1536::from_be_slice(
        result.0.unwrap().to_be_bytes()[192..]
            .into()
    )
}

fn pad192(uint_192: U1536) -> [u8; 384] {
    let mut res: [u8; 384] = [0; 384];
    res[192..].copy_from_slice(
        &uint_192.to_be_bytes()
    );
    res
}

fn at Rosetta is more ubiquitous, but you still can get the values from there to test this one, created with another crate. Don't forget to make them U1536.

If you want to copy-paste them to employ from_be_hex, here they are:
a:000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006ED80FFACE4DF443C2E9A56155272B9004E01F5DABE5F2181A603DA3EB
b:000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005737DF12ECACC95FF94E28463B3CD1DE0C674CB5D079BD3F4C037E48FF
modulus:000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001D6329F1C35CA4BFABB9F5610000000000

Blog

Cryptopals challenge #33: Implement Diffie-Hellman

skaunov

Join Our Newsletter. No Spam, Only the good stuff.

Related