^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /* mpi-mod.c - Modular reduction
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) * Copyright (C) 1998, 1999, 2001, 2002, 2003,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * 2007 Free Software Foundation, Inc.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * This file is part of Libgcrypt.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #include "mpi-internal.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) #include "longlong.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) /* Context used with Barrett reduction. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) struct barrett_ctx_s {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) MPI m; /* The modulus - may not be modified. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) int m_copied; /* If true, M needs to be released. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) int k;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) MPI y;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) MPI r1; /* Helper MPI. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) MPI r2; /* Helper MPI. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) MPI r3; /* Helper MPI allocated on demand. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) void mpi_mod(MPI rem, MPI dividend, MPI divisor)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) mpi_fdiv_r(rem, dividend, divisor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) /* This function returns a new context for Barrett based operations on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) * the modulus M. This context needs to be released using
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) * _gcry_mpi_barrett_free. If COPY is true M will be transferred to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) * the context and the user may change M. If COPY is false, M may not
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) * be changed until gcry_mpi_barrett_free has been called.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) mpi_barrett_t mpi_barrett_init(MPI m, int copy)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) mpi_barrett_t ctx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) MPI tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) mpi_normalize(m);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) ctx = kcalloc(1, sizeof(*ctx), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) if (!ctx)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) if (copy) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) ctx->m = mpi_copy(m);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) ctx->m_copied = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) ctx->m = m;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) ctx->k = mpi_get_nlimbs(m);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) tmp = mpi_alloc(ctx->k + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) /* Barrett precalculation: y = floor(b^(2k) / m). */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) mpi_set_ui(tmp, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) mpi_lshift_limbs(tmp, 2 * ctx->k);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) mpi_fdiv_q(tmp, tmp, m);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) ctx->y = tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) ctx->r1 = mpi_alloc(2 * ctx->k + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) ctx->r2 = mpi_alloc(2 * ctx->k + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) return ctx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) void mpi_barrett_free(mpi_barrett_t ctx)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) if (ctx) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) mpi_free(ctx->y);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) mpi_free(ctx->r1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) mpi_free(ctx->r2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) if (ctx->r3)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) mpi_free(ctx->r3);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) if (ctx->m_copied)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) mpi_free(ctx->m);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) kfree(ctx);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) /* R = X mod M
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) * Using Barrett reduction. Before using this function
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) * _gcry_mpi_barrett_init must have been called to do the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) * precalculations. CTX is the context created by this precalculation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) * and also conveys M. If the Barret reduction could no be done a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) * straightforward reduction method is used.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) * We assume that these conditions are met:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) * Input: x =(x_2k-1 ...x_0)_b
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) * m =(m_k-1 ....m_0)_b with m_k-1 != 0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) * Output: r = x mod m
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) void mpi_mod_barrett(MPI r, MPI x, mpi_barrett_t ctx)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) MPI m = ctx->m;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) int k = ctx->k;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) MPI y = ctx->y;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) MPI r1 = ctx->r1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) MPI r2 = ctx->r2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) int sign;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) mpi_normalize(x);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) if (mpi_get_nlimbs(x) > 2*k) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) mpi_mod(r, x, m);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) sign = x->sign;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) x->sign = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) /* 1. q1 = floor( x / b^k-1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) * q2 = q1 * y
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) * q3 = floor( q2 / b^k+1 )
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) * Actually, we don't need qx, we can work direct on r2
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) mpi_set(r2, x);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) mpi_rshift_limbs(r2, k-1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) mpi_mul(r2, r2, y);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) mpi_rshift_limbs(r2, k+1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) /* 2. r1 = x mod b^k+1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) * r2 = q3 * m mod b^k+1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) * r = r1 - r2
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) * 3. if r < 0 then r = r + b^k+1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) mpi_set(r1, x);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) if (r1->nlimbs > k+1) /* Quick modulo operation. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) r1->nlimbs = k+1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) mpi_mul(r2, r2, m);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) if (r2->nlimbs > k+1) /* Quick modulo operation. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) r2->nlimbs = k+1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) mpi_sub(r, r1, r2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) if (mpi_has_sign(r)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) if (!ctx->r3) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) ctx->r3 = mpi_alloc(k + 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) mpi_set_ui(ctx->r3, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) mpi_lshift_limbs(ctx->r3, k + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) mpi_add(r, r, ctx->r3);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) /* 4. while r >= m do r = r - m */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) while (mpi_cmp(r, m) >= 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) mpi_sub(r, r, m);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) x->sign = sign;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) void mpi_mul_barrett(MPI w, MPI u, MPI v, mpi_barrett_t ctx)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) mpi_mul(w, u, v);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) mpi_mod_barrett(w, w, ctx);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags