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
Top comments (0)