improve documentation with usage examples

[Dustin-Ray]

I understand that this library is a work in progress, and a substantial amount of effort and work has and continues to go into bringing awesome functionality to life. So this isn't at all a criticism, but the documentation for public-facing apis, particularly in the modular math department, feels lacking. This has made it difficult to get started with the library.

Rust has one of the best documentation systems I've had the pleasure of using so far. If the code for some of the functions in the API is considered stable, and would benefit from documentation, Id like to propose that we begin to add usage examples. This will enhance the library by:

1. Improving readability of the public facing apis
2. speeding up onboarding to those who may be switching from other arbitrary-precision libraries by reducing the work of searching the code base
3. improve safety by documenting best practices in the usage examples
4. increase efficiency for the same reason as above. someone who needs a strong, constant-time library but might not have as much experience with advanced algorithms such as montgomery reduction, would benefit from having the documentation point them directly to the best tool for the job.

I fully acknowledge that this only makes sense if the functions we want to document are stable. If things are still developing and will dramatically change soon, we should we wait for stability. If it makes sense to do all of this, I volunteer as tribute for this task if no one else feels strongly compelled. Here is a sample of some of my work from my own cryptosystem Ive built as an academic exercise in cryptographic algorithm design:

/// # Schnorr Signatures
/// Signs a [`Message`] under passphrase pw.
///
/// ## Algorithm:
/// * `s` ← kmac_xof(pw, “”, 512, “K”); s ← 4s
/// * `k` ← kmac_xof(s, m, 512, “N”); k ← 4k
/// * `𝑈` ← k*𝑮;
/// * `ℎ` ← kmac_xof(𝑈ₓ , m, 512, “T”); 𝑍 ← (𝑘 – ℎ𝑠) mod r
///
/// ## Arguments:
/// * key: &[`KeyPair`], : reference to KeyPair.
/// * d: u64: encryption security strength in bits. Can only be 224, 256, 384, or 512.
///
/// ## Assumes:
/// * Some(key.priv_key)
///
/// ## Usage
/// ```
/// use capycrypt::{
///     Signable,
///     KeyPair,
///     Message,
///     sha3::aux_functions::byte_utils::get_random_bytes,
///     curves::EdCurves::E448};
/// // Get random 5mb
/// let mut msg = Message::new(get_random_bytes(5242880));
/// // Get a random password
/// let pw = get_random_bytes(64);
/// // Generate a signing keypair
/// let key_pair = KeyPair::new(&pw, "test key".to_string(), E448, 512);
/// // Sign with 512 bits of security
/// msg.sign(&key_pair, 512);
/// ```
fn sign(&mut self, key: &KeyPair, d: u64) {
    self.d = Some(d);
    let s: Integer = bytes_to_big(kmac_xof(&key.priv_key, &[], 512, "K", d)) * 4;
    let s_bytes = big_to_bytes(s.clone());

    let k: Integer = bytes_to_big(kmac_xof(&s_bytes, &self.msg, 512, "N", d)) * 4;

    let u = EdCurvePoint::generator(SELECTED_CURVE, false) * k.clone();
    let ux_bytes = big_to_bytes(u.x);
    let h = kmac_xof(&ux_bytes, &self.msg, 512, "T", d);
    let h_big = bytes_to_big(h.clone());
    //(a % b + b) % b
    let z = ((k - (h_big * s)) % u.r.clone() + u.r.clone()) % u.r;
    self.sig = Some(Signature { h, z })
}

If there's a good reason not to do this right now, we can close this issue and move on. But I didnt see this in the current issues list and feel it would greatly benefit current and new users of the library. Thanks for your consideration, sorry for the long message.

[fjarri]

What methods do you think would benefit from usage examples? Just a few examples (sorry for the repetition). Or, alternatively, for what usage scenarios it is unclear how to perform them, so that an example is needed?

Also if I may criticize your example a little:

• There is no need to specify the types in the docstring when they are already available in the function signature.
• If d can only take a few possible values, an enum may be a better choice.
• "Assumes: Some(key.priv_key)" is not great from the usability perspective, this should be enforced by the types.

[tarcieri]

We've had several requests to improve documentation on this library and I agree it's a general problem. But I'm left feeling like @fjarri that I'm not sure what specific kinds of documentation would be helpful, and I've generally had trouble getting straight answers out of people as to what specific improvements they'd like to see.

There are already several toplevel usage examples. Some inline ones would probably make sense, but identifying where would be a first step.

[Dustin-Ray]

Also if I may criticize your example a little:

• There is no need to specify the types in the docstring when they are already available in the function signature.
• If d can only take a few possible values, an enum may be a better choice.
• "Assumes: Some(key.priv_key)" is not great from the usability perspective, this should be enforced by the types.

Thank you so much for this, this is very helpful to me as I learn best practices. Im building out a cryptosystem as an academic project and if you felt inclined I would invite you to give feedback on the rest of the repo :D

What methods do you think would benefit from usage examples? Just a few examples (sorry for the repetition). Or, alternatively, for what usage scenarios it is unclear how to perform them, so that an example is needed?

I dont know if this is helpful to you both but maybe the perspective I can share is someone who is coming from num-bigint /rug and is unfamiliar with crypto-bigint, specifically for modular multiplication and reduction.

Eventually I was able to come up with this:

let product_mod_p = montgomery_reduction(&a.mul_wide(&b), &Modulus::MODULUS, Modulus::MOD_NEG_INV);

The documentation for this function reads:

"Algorithm 14.32 in Handbook of Applied Cryptography https://cacr.uwaterloo.ca/hac/about/chap14.pdf"

And thats it, so here are the questions I had to answer on my own, that robust documentation may be able to address:

1. Is this function constant or variable time?
2. Is the result still in montgomery space or is another transformation required?
3. How to instantiate the modulus?
4. Why use this over const_rem?
5. How is R being determined and is it the best choice with respect to the modulus in this case?
6. Is this function even the best choice for modular reduction? Is there something else in the library that might work better for a different situation?

Ultimately Im looking at a repo like dalek and seeing more text than code almost. I absolutely respect the value of intent revealing code but Im questioning if its safe to assume that someone who wants to take advantage of the benefits of crypto-bigint should be expected to answer the above questions on their own.

This is only one example, the rest of the standard operations (+, - etc) were simple enough to figure out. As I work with this library more I can pinpoint additional functions that may present similar questions regarding their usage.

What methods do you think would benefit from usage examples? Just a few examples (sorry for the repetition). Or, alternatively, for what usage scenarios it is unclear how to perform them, so that an example is needed?

Sorry for the essay, but my answer to this on my own work is usually "anything directly facing the caller should probably have an example of how we expect someone to use our library". Hope this helps and thanks again for taking the time to engage.

[tarcieri]

To answer this question:

Is this function constant or variable time?

https://github.com/RustCrypto/crypto-bigint#goals

Constant-time by default. Variable-time functions are explicitly marked as such.

I'm not sure if that's not clear enough or what. We can explicitly document that every function which doesn't end with *_vartime is constant time, but I think that gets overly redundant at some point.

[Dustin-Ray]

I'm not sure if that's not clear enough or what. We can explicitly document that every function which doesn't end with *_vartime is constant time, but I think that gets overly redundant at some point.

I only bring it up because some functions do actually explicitly label themselves as constant time in the documentation, such as add_mod for example:

"Computes self + rhs mod p in constant time."

To a newcomer, this may suggest that a function could be variable time if it is not labelled as such in the documentation. But, I do agree with you that the readme is very clear and should be fine.

[fjarri]

Honestly I wasn't even aware that montgomery_reduction() is public. I thought the public API is DynResidue/Residue. Which I always considered to be a confusing name for numbers in Montgomery space :) (and it doesn't help that it's put two level deep in crypto_bigint::modular::runtime_mod). So I guess that's one scenario - "How do I make my modulo operations faster?". montgomery_reduction() is more of a hazmat-type API, you really need to know what you're doing if you're touching it (and maybe we should hide it after all - since as you noticed there's no clear way of obtaining the necessary constants).

anything directly facing the caller should probably have an example of how we expect someone to use our library

I would disagree with that, most methods in crypto-bigint at least either mimic the methods of built-in integers or correspond to well-known mathematical operations. What we need is some tutorial answering to questions "how do I do <...>" (like the Montgomery example above).

I only bring it up because some functions do actually explicitly label themselves as constant time in the documentation, such as add_mod for example:
"Computes self + rhs mod p in constant time."

This should be fixed.

[Dustin-Ray]

Honestly I wasn't even aware that montgomery_reduction() is public. I thought the public API is DynResidue/Residue. Which I always considered to be a confusing name for numbers in Montgomery space :) (and it doesn't help that it's put two level deep in crypto_bigint::modular::runtime_mod).

As a newcomer looking for a simple mul mod I dont know how I would ever have found this to be honest, and this is probably due to my own relative inexperience, but it doesnt seem terribly unrealistic to anticipate a 1:1 API with num-bigint for example when other operations in crypto-bigintseem to have such a mapping. (fully acknowledge the open mul mod issue)

I only bring it up because some functions do actually explicitly label themselves as constant time in the documentation, such as add_mod for example:
"Computes self + rhs mod p in constant time."

This should be fixed.

If you'd like someone to help with this I can open a PR and track down all the places where this is happening. Thanks for the attention to this.

So I guess that's one scenario - "How do I make my modulo operations faster?".

Agreed. Also, if DynResidue/Residue should be the correct way to achieve a modular reduction, showing it in action would be greatly beneficial. The documentation here appears to be substantially more concrete but an example demonstrating how DynResidue/Residue can be used to carry out a modular reduction would be fantastic.

[tarcieri]

DynResidue/Residue. Which I always considered to be a confusing name for numbers in Montgomery space :)

Open to better names... that one came from quite a bit of bikeshedding.

and it doesn't help that it's put two level deep in crypto_bigint::modular::runtime_mod

We can probably re-export the contents of both modules under crypto_bigint::modular which would be a purely additive change.

Perhaps we could remove pub from each of the modules in the next breaking release as well, which would fully flatten out those modules.

[Dustin-Ray]

I only bring it up because some functions do actually explicitly label themselves as constant time in the documentation, such as add_mod for example:
"Computes self + rhs mod p in constant time."

This should be fixed.

Here is a simple PR that should address the documentation inconsistency.

[Dustin-Ray]

Would something like this format be beneficial?

    /// Computes self / rhs, returns the quotient, remainder.
    /// ### Usage:
    /// ```
    /// use crypto_bigint::{U448, NonZero};
    /// 
    /// let a = U448::from(8_u64);
    /// let b = NonZero::new(U448::from(4_u64)).unwrap();
    /// let res = a.div_rem(&b);
    /// 
    /// assert!(res.0 == U448::from(2_u64));
    /// assert!(res.1 == U448::ZERO);
    /// ```
    pub fn div_rem(&self, rhs: &NonZero<Self>) -> (Self, Self) {
        // Since `rhs` is nonzero, this should always hold.
        let (q, r, _c) = self.ct_div_rem(rhs);
        (q, r)
    }

This example is helpful in this case because it is relatively easy to get started with a Uint, but it is unclear how to get a Nonzero. I needed to search the entire repo for an example in a unit test to find this:

let b = NonZero::new(U448::from(4_u64)).unwrap();

If we like this format, I can move through the rest of the repo where this might help, specifically in cases where the operation is happening on a type outside that of Self. An example of this sort might be redundant if you've already obtained the type needed in the operation.

[fjarri]

I would argue that this is one of those methods where a usage example is not necessary. The information on how to create a NonZero is trivially obtained by clicking on NonZero in the argument list, proceeding to https://docs.rs/crypto-bigint/latest/crypto_bigint/struct.NonZero.html , and then looking at the first three methods. That is the beauty of doing things through types.

[Dustin-Ray]

I would argue that this is one of those methods where a usage example is not necessary. The information on how to create a NonZero is trivially obtained by clicking on NonZero in the argument list, proceeding to https://docs.rs/crypto-bigint/latest/crypto_bigint/struct.NonZero.html , and then looking at the first three methods. That is the beauty of doing things through types.

I wont disagree, but its hard for me to get onboard with the idea that following that sequence of steps you just mentioned is easier than simply hovering over the function in an ide and having the correct, safe usage presented to you immediately.

Specifically, I struggled here because there is a new() and also a from() on the NonZero type. How do I know which one to use? Why is new() the correct usage to instantiate a NonZero while from() is used to instantiate other types like U448 for example? (I have the answer to this question now, but only after quite a bit of searching and work)

Im sympathetic to the argument though that if we're sacrificing ease of use to ensure that the user is absolutely sure about what theyre doing by guiding them through the docs in this way youve mentioned and forcing them to find the correct answers to those questions on their own, then maybe that does make more sense over what Im suggesting. I could see it increasing understanding of the library as a whole in some way I guess.

[tarcieri]

@drcapybara I think your example could be OK, however it shouldn't use unwrap, but instead something like: NonZero::new(...).map { |b| a.div_rem(&b) }

[Dustin-Ray]

@drcapybara I think your example could be OK, however it shouldn't use unwrap, but instead something like: NonZero::new(...).map { |b| a.div_rem(&b) }

heres a preliminary PR extending this pattern to some of the functions in div. could use some review if it makes sense

[ZettaScript]

I wanted to implement some toy cryptosystem and tried to use this crate because I needed prime-order integer rings.

• Let's use Integer.
• Oh, it's a trait, so let's use Uint instead.
• Nice, Uint::random_mod is perfect!
• Ok, I have to use DynResidue to do exponentiation.
• But... DynResidue hasn't any random functions and does not impl TryFrom<Uint>. I'm stuck.
• Reading this issue I learn that Residue is not what I thought...
• Stop spending time, u64 will be enough.

Even if it's unclear how items should be documented further, it's always helpful to have textbook examples to demonstrate how to use the basic features (maybe a textbook RSA or DH). When a crate's types are not self-explanatory, the first thing I do is jump to the examples folder in the Git repo.

[Dustin-Ray]

(maybe a textbook RSA or DH)

Heres a blinded RSA protocol I wrote and was hoping to get into the docs here but I dont think I should be using const for the parameters:

use crypto_bigint::modular::ConstMontyParams;
use crypto_bigint::{const_monty_form, impl_modulus, Uint, U128, U64};
use crypto_bigint::{rand_core::OsRng, NonZero, RandomMod};
use rand::Rng;

pub fn main() {
    // RSA public exponent
    let e: U128 = Uint::from(65537_u64);

    // obtained from crypto_primes::generate_safe_prime(Some(32))
    let p: U64 = Uint::from_be_hex("ECAF5ED6493129D7");
    let q: U64 = Uint::from_be_hex("98E1FD7AE92F68F3");

    // p * q
    const N: &str = "8D5910CC89AFF00D40B1ADB4D0230F15";
    impl_modulus!(Modulus, U128, N);

    // Euler's totient
    let phi = (p - U64::ONE).widening_mul(&(q - U64::ONE));

    // private decryption and signing key
    let secret_d = e.inv_mod(&phi).expect("Modular inverse does not exist");

    // super secret message
    let message = U128::from(42_u64);
    let m = const_monty_form!(message, Modulus);

    // sign the message
    let s = m.pow(&secret_d);

    // verify the signature, without reducing
    assert_eq!(m, s.pow(&e), "verification failed");

    // public key modulus
    let n = &NonZero::new(U128::from_be_hex(N)).unwrap();

    // prover commits to c = z^e * m mod n for
    // some random non-zero z
    let z_rand = U128::random_mod(&mut OsRng, n);
    let z = const_monty_form!(z_rand, Modulus);
    let c = z.pow(&e).mul(&m);

    // Soundness error = 1/2^k
    let k = 20;
    for _ in 0..k {
        // Prover picks a random r_i and keeps it secret
        let r_i_rand = U128::random_mod(&mut OsRng, n);
        let r_i = const_monty_form!(r_i_rand, Modulus);
        // d = r^e mod n is publicly known
        let d = r_i.pow(&e);

        // Verifier picks a random bit b_i
        let b_i = OsRng.gen::<bool>();
        // Prover reveals r_i
        let z_i = if !b_i { r_i } else { r_i * s * z };

        // if b = 0, Prover reveals r_i and verifier checks that
        // r_i^e = d
        if !b_i {
            assert_eq!(d, z_i.pow(&e),);
        // b_i = 1. Verifier checks that u^e = d * c mod n
        } else {
            assert_eq!(d * c, z_i.pow(&e))
        }
    }
}

This shows basic usage of the updated traits. This crate has made a lot of progress towards usability in the last few versions but I share your sentiments as well about usage examples. Hopefully this can help you out a bit @ZettaScript . Maybe someone can rework my example here to be a more correct example, Im a bit short on time these days.