make exptmod algorithms private?

[minad]

Does it make sense to make the exptmod algorithms private, i.e., the mp_reduce* functions in 2.0? Are they useful by itself? Some of these functions look as if they are more of internal use, but I might be wrong. The same applies maybe to some of the prime functions. Could someone enlighten me? @czurnieden

[sjaeckel]

I just wanted to say "I think there are even more currently public functions which could be private" but after having a look it seems like there's only the reduce stuff left

mp_err mp_reduce_setup(mp_int *a, const mp_int *b) MP_WUR;
mp_err mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu) MP_WUR;
mp_err mp_montgomery_setup(const mp_int *n, mp_digit *rho) MP_WUR;
mp_err mp_montgomery_calc_normalization(mp_int *a, const mp_int *b) MP_WUR;
mp_err mp_montgomery_reduce(mp_int *x, const mp_int *n, mp_digit rho) MP_WUR;
bool mp_dr_is_modulus(const mp_int *a) MP_WUR;
void mp_dr_setup(const mp_int *a, mp_digit *d);
mp_err mp_dr_reduce(mp_int *x, const mp_int *n, mp_digit k) MP_WUR;
bool mp_reduce_is_2k(const mp_int *a) MP_WUR;
mp_err mp_reduce_2k_setup(const mp_int *a, mp_digit *d) MP_WUR;
mp_err mp_reduce_2k(mp_int *a, const mp_int *n, mp_digit d) MP_WUR;
bool mp_reduce_is_2k_l(const mp_int *a) MP_WUR;
mp_err mp_reduce_2k_setup_l(const mp_int *a, mp_int *d) MP_WUR;
mp_err mp_reduce_2k_l(mp_int *a, const mp_int *n, const mp_int *d) MP_WUR;

maybe also those

mp_err mp_prime_fermat(const mp_int *a, const mp_int *b, bool *result) MP_WUR;
mp_err mp_prime_miller_rabin(const mp_int *a, const mp_int *b, bool *result) MP_WUR;
mp_err mp_prime_strong_lucas_selfridge(const mp_int *a, bool *result) MP_WUR;
mp_err mp_prime_frobenius_underwood(const mp_int *N, bool *result) MP_WUR;

[sjaeckel]

your opinion? @czurnieden @nijtmans @karel-m

[nijtmans]

Well Tcl doens't use any of those, so no objection from me ;-)

[minad]

Some of those reduction functions are useful externally I think. But I have to look more into it.

My problem is that I don't have that much knowledge of the theory behind those functions and the API somehow exposes technical details.

I think in particular those _2k and 2k_l functions look redundant or could maybe hidden behind a common API.

Then there is the issue that some of the reduce functions mutate their input. They should instead take another argument.

But I think someone with more background knowledge could judge better. Ping @czurnieden

[czurnieden]

Yes, if the input can be calculated, that is not dependent on user input, that function can go private. If we do it we should deprecate them formally, some people might use them directly, for some reason or another.
But we have to check carefully, which needs a day or two, at least for me.

For the primetests:

• mp_prime_strong_lucas_selfridge can go private.

• mp_prime_frobenius_underwood has been implemented for MP_8BIT. I have to check if it makes sense for MP_16BIT, otherwise it can go completely. It can be replaced with an "extra strong" Lucas test which is not related to the "strong" Lucas test if implemented with the start values Q = 1 and P = 3 but I have to check that. (vid.: "Frobenius Pseudoprimes", John Grantham). If that is correct the "extra strong" Lucas test can be used as an optional addition to the the other tests in our primality tests. The runtime is about 80% of that of the "strong" Lucast test. Anticipating your question: no, the "extra strong" Lucas test cannot replace the "strong" Lucas test. (Note: Nicely's version has a bug. It checks for (D/N) == 1 instead of (D/N) == -1).

• mp_prime_fermat does not get used at all in LTM. Need to check if it is much(!) faster than Miller-Rabin, otherwise it can go completely. (Some of the other libs (GMP, OpenSSL, PGP, libgcrypt, etc. p. p. ) use a Fermat test, some don't)

• mp_prime_miller_rabin is quite useful on its own, for example if somebody wants to build a small (memory-wise) deterministic prime test (I think I have done something like that in my sieve branch?) or roll their own small (memory-wise) pseudoprime-test. It should stay public.

[czurnieden]

The mp_montgomery* functions get used in LibTomCrypt (Computing ECC stuff).

[czurnieden]

As mp_reduce got used in older versions of LibTomCrypt in ecc.c I found two users: Bitfighter but they have updated by now and the five year old mb-linux-msli using an old version of uCLinux which uses an old version of dropbear which uses an old version of LibTomCrypt. The hardware it was written for still exists but it is unknown if they still use that codebase.
Ask them?
I doubt we would get an answer ;-)

I haven't found anything regarding the rest of the mp_reduce* functions and as there are no technical reasons against it we should make them all private.

[minad]

@czurnieden would you like to/have time to prepare two PRs regarding this issue for discussion? Maybe one for primes and one for reduce.

I think we should address this before the next releases but there is no hurry here.

[czurnieden]

@czurnieden would you like to/have time to prepare two PRs regarding this issue for discussion?

Feared that ;-)

It's a bit of work, so let me outline first for the early complains.

Primetests:

• mp_prime_strong_lucas_selfridge: make private
• mp_prime_frobenius_underwood: deprecate and mark for deletion (mp_prime_strong_lucas_selfridge uses int32_t so MP_16BIT can handle it)
• mp_prime_fermat: deprecate and mark for deletion (Ruby wraps that function but doesn't seem to use it anywhere)
• mp_prime_miller_rabin: don't touch

Reducing:

• All of them with the exception of the *montgomery* stuff: make private.

So far, so good?

[minad]

Feared that ;-)

You don't have to do it ;) I would also work on it if the time of release approaches, but right now I am very busy with other unrelated stuff. But then - I am also no expert in those things.

Let's first discuss the primetest, or start with that. I think we might even want to keep mp_prime_fermat because it is so simple, e.g., if you want a slimmed down version. How can one use the other prime tests if they are made private, e.g., the strong lucas selfridge? I actually have no idea how things should look.

typedef enum {
    ...
} mp_prime_test;

mp_err mp_is_prime(mp_prime_test, int trials, const mp_int*);

Or maybe only expose

mp_err mp_is_prime(int trials, const mp_int*); // just use "the best" prime test being around?

Regarding deprecation - in develop we can just remove the stuff. And after that backport the deprecations to 1.x, see #418.

[minad]

@sjaeckel You know much more about the crypto stuff and how things are used there. Do you have an idea on what should be exposed and how the API should look like?

[czurnieden]

The "reduce" part is simple, see #465 if I haven't missed anything. (To slow. Again ;-) )

I think we might even want to keep mp_prime_fermat because it is so simple, e.g., if you want a slimmed down version.

The Miller-Rabin test is not much slower and not much more complex, but safer by a magnitude or two.
It would only make sense if the numbers get really big, somewhere in the hundred thousand or even million bits range.

How can one use the other prime tests if they are made private, e.g., the strong lucas selfridge?

You don't.

Or maybe only expose […] mp_prime_is_prime

Yes, exactly.

The Miller-Rabin tests is an exception because you can build a safe probable-prime-test with it alone and have a smaller but also slower prime-test.

The rest belongs together, hard to use them individually and if you try you'll end with something resembling our mp_prime_is_prime but not as good.

Regarding deprecation - in develop we can just remove the stuff.

Now, that is a method to my liking! ;-)

And after that backport the deprecations to 1.x, see #418.

Ah, ok.