Estimated precision for MULT product & input handling to prevent overflow ?

[pinkforest]

Hello - just learning to use this library + handle the fixed precision and initialize correctly I think :)

Let's say per NIST.SP.800-56Br2 - Appendix C.2 - Deterministic Prime-Factor Recovery

The recommendation is to do the below as first step:

1. Let a = (de – 1) × GCD(n – 1, de – 1).

The de produt would require (d: private exponent) MULT (e: public exponent)

Questions re: this library

1. Should this not use regular MULT * to get de and instead something else ?

2. How should the precision be estimated given MULT here is d 2048 bits & e can be 2.pow(16) <=> 2.pow(256)

3. If it's calculated / estimated somehow for d*e mult product precision - where it should be initialized at ?

• A. Do we either need to zero-pad d and e and initialize it before or ?

• B Should BoxedUint::from_be_bytes_pad(hexstr, bits) zero with "maximum length" instead of check "exact length" input ?

This would overflow if I naively do

rsa test case given as an example re: associated inputs

let a1 = &d * &e - &one;

e: public exponent == BoxedUint::from(65536 as u32);
n: modulus == BoxedUint::from_be_hex("d397b84d98a4c26138ed1b695a8106ead91d553bf06041b62d3fdc50a041e222b8f4529689c1b82c5e71554f5dd69fa2f4b6158cf0dbeb57811a0fc327e1f28e74fe74d3bc166c1eabdc1b8b57b934ca8be5b00b4f29975bcc99acaf415b59bb28a6782bb41a2c3c2976b3c18dbadef62f00c6bb226640095096c0cc60d22fe7ef987d75c6a81b10d96bf292028af110dc7cc1bbc43d22adab379a0cd5d8078cc780ff5cd6209dea34c922cf784f7717e428d75b5aec8ff30e5f0141510766e2e0ab8d473c84e8710b2b98227c3db095337ad3452f19e2b9bfbccdd8148abf6776fa552775e6e75956e45229ae5a9c46949bab1e622f0e48f56524a84ed3483b", 2048) - 256 bytes / 2048 bits
d: private exponent == BoxedUint::from_be_hex("c4e70c689162c94c660828191b52b4d8392115df486a9adbe831e458d73958320dc1b755456e93701e9702d76fb0b92f90e01d1fe248153281fe79aa9763a92fae69d8d7ecd144de29fa135bd14f9573e349e45031e3b76982f583003826c552e89a397c1a06bd2163488630d92e8c2bb643d7abef700da95d685c941489a46f54b5316f62b5d2c3a7f1bbd134cb37353a44683fdc9d95d36458de22f6c44057fe74a0a436c4308f73f4da42f35c47ac16a7138d483afc91e41dc3a1127382e0c0f5119b0221b4fc639d6b9c38177a6de9b526ebd88c38d7982c07f98a0efd877d508aae275b946915c02e2e1106d175d74ec6777f5e80d12c053d9c7be1e341", 2048) - 256 bytes / 2048 bits

Sidenote - It's interesting that overflow doesn't get triggered when d is not a ref and gets moved.

let a1 = d * &e - &one;

[tarcieri]

See #312 for some previous discussion about widening semantics.

The main strategy we currently provide to prevent overflow is widening multiplication, where the result is the size of the sum of the input sizes.

I'd have to look through this particular algorithm in a bit more depth to determine what the best strategy would be for this use case.