Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
pinkforest opened this issue Apr 3, 2024 · 1 comment

Comments

@pinkforest
Copy link

pinkforest commented Apr 3, 2024

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
Copy link
Member

tarcieri commented Apr 4, 2024

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants