Welcome to mirror list, hosted at ThFree Co, Russian Federation.

github.com/mRemoteNG/PuTTYNG.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/primecandidate.c
diff options
context:
space:
mode:
Diffstat (limited to 'primecandidate.c')
-rw-r--r--primecandidate.c445
1 files changed, 0 insertions, 445 deletions
diff --git a/primecandidate.c b/primecandidate.c
deleted file mode 100644
index cf55919e..00000000
--- a/primecandidate.c
+++ /dev/null
@@ -1,445 +0,0 @@
-/*
- * primecandidate.c: implementation of the PrimeCandidateSource
- * abstraction declared in sshkeygen.h.
- */
-
-#include <assert.h>
-#include "ssh.h"
-#include "mpint.h"
-#include "mpunsafe.h"
-#include "sshkeygen.h"
-
-struct avoid {
- unsigned mod, res;
-};
-
-struct PrimeCandidateSource {
- unsigned bits;
- bool ready, try_sophie_germain;
- bool one_shot, thrown_away_my_shot;
-
- /* We'll start by making up a random number strictly less than this ... */
- mp_int *limit;
-
- /* ... then we'll multiply by 'factor', and add 'addend'. */
- mp_int *factor, *addend;
-
- /* Then we'll try to add a small multiple of 'factor' to it to
- * avoid it being a multiple of any small prime. Also, for RSA, we
- * may need to avoid it being _this_ multiple of _this_: */
- unsigned avoid_residue, avoid_modulus;
-
- /* Once we're actually running, this will be the complete list of
- * (modulus, residue) pairs we want to avoid. */
- struct avoid *avoids;
- size_t navoids, avoidsize;
-
- /* List of known primes that our number will be congruent to 1 modulo */
- mp_int **kps;
- size_t nkps, kpsize;
-};
-
-PrimeCandidateSource *pcs_new_with_firstbits(unsigned bits,
- unsigned first, unsigned nfirst)
-{
- PrimeCandidateSource *s = snew(PrimeCandidateSource);
-
- assert(first >> (nfirst-1) == 1);
-
- s->bits = bits;
- s->ready = false;
- s->try_sophie_germain = false;
- s->one_shot = false;
- s->thrown_away_my_shot = false;
-
- s->kps = NULL;
- s->nkps = s->kpsize = 0;
-
- s->avoids = NULL;
- s->navoids = s->avoidsize = 0;
-
- /* Make the number that's the lower limit of our range */
- mp_int *firstmp = mp_from_integer(first);
- mp_int *base = mp_lshift_fixed(firstmp, bits - nfirst);
- mp_free(firstmp);
-
- /* Set the low bit of that, because all (nontrivial) primes are odd */
- mp_set_bit(base, 0, 1);
-
- /* That's our addend. Now initialise factor to 2, to ensure we
- * only generate odd numbers */
- s->factor = mp_from_integer(2);
- s->addend = base;
-
- /* And that means the limit of our random numbers must be one
- * factor of two _less_ than the position of the low bit of
- * 'first', because we'll be multiplying the random number by
- * 2 immediately afterwards. */
- s->limit = mp_power_2(bits - nfirst - 1);
-
- /* avoid_modulus == 0 signals that there's no extra residue to avoid */
- s->avoid_residue = 1;
- s->avoid_modulus = 0;
-
- return s;
-}
-
-PrimeCandidateSource *pcs_new(unsigned bits)
-{
- return pcs_new_with_firstbits(bits, 1, 1);
-}
-
-void pcs_free(PrimeCandidateSource *s)
-{
- mp_free(s->limit);
- mp_free(s->factor);
- mp_free(s->addend);
- for (size_t i = 0; i < s->nkps; i++)
- mp_free(s->kps[i]);
- sfree(s->avoids);
- sfree(s->kps);
- sfree(s);
-}
-
-void pcs_try_sophie_germain(PrimeCandidateSource *s)
-{
- s->try_sophie_germain = true;
-}
-
-void pcs_set_oneshot(PrimeCandidateSource *s)
-{
- s->one_shot = true;
-}
-
-static void pcs_require_residue_inner(PrimeCandidateSource *s,
- mp_int *mod, mp_int *res)
-{
- /*
- * We already have a factor and addend. Ensure this one doesn't
- * contradict it.
- */
- mp_int *gcd = mp_gcd(mod, s->factor);
- mp_int *test1 = mp_mod(s->addend, gcd);
- mp_int *test2 = mp_mod(res, gcd);
- assert(mp_cmp_eq(test1, test2));
- mp_free(test1);
- mp_free(test2);
-
- /*
- * Reduce our input factor and addend, which are constraints on
- * the ultimate output number, so that they're constraints on the
- * initial cofactor we're going to make up.
- *
- * If we're generating x and we want to ensure ax+b == r (mod m),
- * how does that work? We've already checked that b == r modulo g
- * = gcd(a,m), i.e. r-b is a multiple of g, and so are a and m. So
- * let's write a=gA, m=gM, (r-b)=gR, and then we can start by
- * dividing that off:
- *
- * ax == r-b (mod m )
- * => gAx == gR (mod gM)
- * => Ax == R (mod M)
- *
- * Now the moduli A,M are coprime, which makes things easier.
- *
- * We're going to need to generate the x in this equation by
- * generating a new smaller value y, multiplying it by M, and
- * adding some constant K. So we have x = My + K, and we need to
- * work out what K will satisfy the above equation. In other
- * words, we need A(My+K) == R (mod M), and the AMy term vanishes,
- * so we just need AK == R (mod M). So our congruence is solved by
- * setting K to be R * A^{-1} mod M.
- */
- mp_int *A = mp_div(s->factor, gcd);
- mp_int *M = mp_div(mod, gcd);
- mp_int *Rpre = mp_modsub(res, s->addend, mod);
- mp_int *R = mp_div(Rpre, gcd);
- mp_int *Ainv = mp_invert(A, M);
- mp_int *K = mp_modmul(R, Ainv, M);
-
- mp_free(gcd);
- mp_free(Rpre);
- mp_free(Ainv);
- mp_free(A);
- mp_free(R);
-
- /*
- * So we know we have to transform our existing (factor, addend)
- * pair into (factor * M, addend * factor * K). Now we just need
- * to work out what the limit should be on the random value we're
- * generating.
- *
- * If we need My+K < old_limit, then y < (old_limit-K)/M. But the
- * RHS is a fraction, so in integers, we need y < ceil of it.
- */
- assert(!mp_cmp_hs(K, s->limit));
- mp_int *dividend = mp_add(s->limit, M);
- mp_sub_integer_into(dividend, dividend, 1);
- mp_sub_into(dividend, dividend, K);
- mp_free(s->limit);
- s->limit = mp_div(dividend, M);
- mp_free(dividend);
-
- /*
- * Now just update the real factor and addend, and we're done.
- */
-
- mp_int *addend_old = s->addend;
- mp_int *tmp = mp_mul(s->factor, K); /* use the _old_ value of factor */
- s->addend = mp_add(s->addend, tmp);
- mp_free(tmp);
- mp_free(addend_old);
-
- mp_int *factor_old = s->factor;
- s->factor = mp_mul(s->factor, M);
- mp_free(factor_old);
-
- mp_free(M);
- mp_free(K);
- s->factor = mp_unsafe_shrink(s->factor);
- s->addend = mp_unsafe_shrink(s->addend);
- s->limit = mp_unsafe_shrink(s->limit);
-}
-
-void pcs_require_residue(PrimeCandidateSource *s,
- mp_int *mod, mp_int *res_orig)
-{
- /*
- * Reduce the input residue to its least non-negative value, in
- * case it was given as a larger equivalent value.
- */
- mp_int *res_reduced = mp_mod(res_orig, mod);
- pcs_require_residue_inner(s, mod, res_reduced);
- mp_free(res_reduced);
-}
-
-void pcs_require_residue_1(PrimeCandidateSource *s, mp_int *mod)
-{
- mp_int *res = mp_from_integer(1);
- pcs_require_residue(s, mod, res);
- mp_free(res);
-}
-
-void pcs_require_residue_1_mod_prime(PrimeCandidateSource *s, mp_int *mod)
-{
- pcs_require_residue_1(s, mod);
-
- sgrowarray(s->kps, s->kpsize, s->nkps);
- s->kps[s->nkps++] = mp_copy(mod);
-}
-
-void pcs_avoid_residue_small(PrimeCandidateSource *s,
- unsigned mod, unsigned res)
-{
- assert(!s->avoid_modulus); /* can't cope with more than one */
- s->avoid_modulus = mod;
- s->avoid_residue = res % mod; /* reduce, just in case */
-}
-
-static int avoid_cmp(const void *av, const void *bv)
-{
- const struct avoid *a = (const struct avoid *)av;
- const struct avoid *b = (const struct avoid *)bv;
- return a->mod < b->mod ? -1 : a->mod > b->mod ? +1 : 0;
-}
-
-static uint64_t invert(uint64_t a, uint64_t m)
-{
- int64_t v0 = a, i0 = 1;
- int64_t v1 = m, i1 = 0;
- while (v0) {
- int64_t tmp, q = v1 / v0;
- tmp = v0; v0 = v1 - q*v0; v1 = tmp;
- tmp = i0; i0 = i1 - q*i0; i1 = tmp;
- }
- assert(v1 == 1 || v1 == -1);
- return i1 * v1;
-}
-
-void pcs_ready(PrimeCandidateSource *s)
-{
- /*
- * List all the small (modulus, residue) pairs we want to avoid.
- */
-
- init_smallprimes();
-
-#define ADD_AVOID(newmod, newres) do { \
- sgrowarray(s->avoids, s->avoidsize, s->navoids); \
- s->avoids[s->navoids].mod = (newmod); \
- s->avoids[s->navoids].res = (newres); \
- s->navoids++; \
- } while (0)
-
- unsigned limit = (mp_hs_integer(s->addend, 65536) ? 65536 :
- mp_get_integer(s->addend));
-
- /*
- * Don't be divisible by any small prime, or at least, any prime
- * smaller than our output number might actually manage to be. (If
- * asked to generate a really small prime, it would be
- * embarrassing to rule out legitimate answers on the grounds that
- * they were divisible by themselves.)
- */
- for (size_t i = 0; i < NSMALLPRIMES && smallprimes[i] < limit; i++)
- ADD_AVOID(smallprimes[i], 0);
-
- if (s->try_sophie_germain) {
- /*
- * If we're aiming to generate a Sophie Germain prime (i.e. p
- * such that 2p+1 is also prime), then we also want to ensure
- * 2p+1 is not congruent to 0 mod any small prime, because if
- * it is, we'll waste a lot of time generating a p for which
- * 2p+1 can't possibly work. So we have to avoid an extra
- * residue mod each odd q.
- *
- * We can simplify: 2p+1 == 0 (mod q)
- * => 2p == -1 (mod q)
- * => p == -2^{-1} (mod q)
- *
- * There's no need to do Euclid's algorithm to compute those
- * inverses, because for any odd q, the modular inverse of -2
- * mod q is just (q-1)/2. (Proof: multiplying it by -2 gives
- * 1-q, which is congruent to 1 mod q.)
- */
- for (size_t i = 0; i < NSMALLPRIMES && smallprimes[i] < limit; i++)
- if (smallprimes[i] != 2)
- ADD_AVOID(smallprimes[i], (smallprimes[i] - 1) / 2);
- }
-
- /*
- * Finally, if there's a particular modulus and residue we've been
- * told to avoid, put it on the list.
- */
- if (s->avoid_modulus)
- ADD_AVOID(s->avoid_modulus, s->avoid_residue);
-
-#undef ADD_AVOID
-
- /*
- * Sort our to-avoid list by modulus. Partly this is so that we'll
- * check the smaller moduli first during the live runs, which lets
- * us spot most failing cases earlier rather than later. Also, it
- * brings equal moduli together, so that we can reuse the residue
- * we computed from a previous one.
- */
- qsort(s->avoids, s->navoids, sizeof(*s->avoids), avoid_cmp);
-
- /*
- * Next, adjust each of these moduli to take account of our factor
- * and addend. If we want factor*x+addend to avoid being congruent
- * to 'res' modulo 'mod', then x itself must avoid being congruent
- * to (res - addend) * factor^{-1}.
- *
- * If factor == 0 modulo mod, then the answer will have a fixed
- * residue anyway, so we can discard it from our list to test.
- */
- int64_t factor_m = 0, addend_m = 0, last_mod = 0;
-
- size_t out = 0;
- for (size_t i = 0; i < s->navoids; i++) {
- int64_t mod = s->avoids[i].mod, res = s->avoids[i].res;
- if (mod != last_mod) {
- last_mod = mod;
- addend_m = mp_unsafe_mod_integer(s->addend, mod);
- factor_m = mp_unsafe_mod_integer(s->factor, mod);
- }
-
- if (factor_m == 0) {
- assert(res != addend_m);
- continue;
- }
-
- res = (res - addend_m) * invert(factor_m, mod);
- res %= mod;
- if (res < 0)
- res += mod;
-
- s->avoids[out].mod = mod;
- s->avoids[out].res = res;
- out++;
- }
-
- s->navoids = out;
-
- s->ready = true;
-}
-
-mp_int *pcs_generate(PrimeCandidateSource *s)
-{
- assert(s->ready);
- if (s->one_shot) {
- if (s->thrown_away_my_shot)
- return NULL;
- s->thrown_away_my_shot = true;
- }
-
- while (true) {
- mp_int *x = mp_random_upto(s->limit);
-
- int64_t x_res = 0, last_mod = 0;
- bool ok = true;
-
- for (size_t i = 0; i < s->navoids; i++) {
- int64_t mod = s->avoids[i].mod, avoid_res = s->avoids[i].res;
-
- if (mod != last_mod) {
- last_mod = mod;
- x_res = mp_unsafe_mod_integer(x, mod);
- }
-
- if (x_res == avoid_res) {
- ok = false;
- break;
- }
- }
-
- if (!ok) {
- mp_free(x);
- continue; /* try a new x */
- }
-
- /*
- * We've found a viable x. Make the final output value.
- */
- mp_int *toret = mp_new(s->bits);
- mp_mul_into(toret, x, s->factor);
- mp_add_into(toret, toret, s->addend);
- mp_free(x);
- return toret;
- }
-}
-
-void pcs_inspect(PrimeCandidateSource *pcs, mp_int **limit_out,
- mp_int **factor_out, mp_int **addend_out)
-{
- *limit_out = mp_copy(pcs->limit);
- *factor_out = mp_copy(pcs->factor);
- *addend_out = mp_copy(pcs->addend);
-}
-
-unsigned pcs_get_bits(PrimeCandidateSource *pcs)
-{
- return pcs->bits;
-}
-
-unsigned pcs_get_bits_remaining(PrimeCandidateSource *pcs)
-{
- return mp_get_nbits(pcs->limit);
-}
-
-mp_int *pcs_get_upper_bound(PrimeCandidateSource *pcs)
-{
- /* Compute (limit-1) * factor + addend */
- mp_int *tmp = mp_mul(pcs->limit, pcs->factor);
- mp_int *bound = mp_add(tmp, pcs->addend);
- mp_free(tmp);
- mp_sub_into(bound, bound, pcs->factor);
- return bound;
-}
-
-mp_int **pcs_get_known_prime_factors(PrimeCandidateSource *pcs, size_t *nout)
-{
- *nout = pcs->nkps;
- return pcs->kps;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-16 02:51:59 +0300