Cryptopals 챌린지 #33: Diffie-Hellman 구현

여느 때와 마찬가지로 무언가를 가르쳐준 도전 과제를 처리한 후에는 내 솔루션이 다른 솔루션과 어떻게 다른지 살펴보았습니다. 그리고 이번에는 내 것이 다소 독특한 것으로 판명되었습니다.

아니요, 좋지 않습니다(우수하지도 않습니다). =) 사람들이 modexp 부분을 어떻게 해결하는지 보고 싶었고 Rust 솔루션에 관심이 있었습니다. 내가 연 것은 bigint 크레이트의 modpow 기능을 사용하는 것뿐이었습니다.

결국 그것은 "당신 자신의 modexp를 작성하라"고 말했고, 그것은 연습의 유용한 부분으로 느껴졌습니다. 그래서 저는 crypto_bigint 크레이트를 사용하고 이 특정 연습을 위한 함수를 구성했습니다. 느리고 192바이트 정수로 작업이 제한되지만 여전히 이 문제를 해결하도록 영감을 줄 수 있습니다. (또한 충분히 큰 숫자의 경우 초과 비트에 문제가 있어야 합니다. 피하려면 더 큰 bigint 유형을 사용할 수 있습니다.)

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은 더 보편적이지만 다른 크레이트로 생성된 이 값을 테스트하기 위해 여전히 값을 얻을 수 있습니다. 그것들을 만드는 것을 잊지 마세요 U1536 .

고용from_be_hex하기 위해 복사하여 붙여넣으려면 다음과 같습니다.
a:000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006ED80FFACE4DF443C2E9A56155272B9004E01F5DABE5F2181A603DA3EB
b:000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005737DF12ECACC95FF94E28463B3CD1DE0C674CB5D079BD3F4C037E48FF
modulus:000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001D6329F1C35CA4BFABB9F5610000000000