The associate value function, written avf(), derives an auxiliary scalar from the x-coordinate of an ephemeral public key in the MQV key-exchange algorithm. The NIST variant keeps the lower half of the order-sized x value and sets the next bit. section 4.2.1 section 4.5
Let n be the order of the base point G and f = ceil(log₂(n)/2). The mathematical operation is avf(x) = (x mod 2^f) + 2^f. In implementation, masking supplies x mod 2^f, then setting bit f adds 2^f. section 4.2.1 section 4.2.2
A direct implementation follows this flow:
- Compute f from the binary size of the base-point order, using the halfway position rounded upward. section 4.2.2
- Build a mask with its lower f bits set. section 4.2.2
- AND the input x with the mask, set bit f in the result, and clear the temporary mask. section 4.2.2
Role inside MQV
Alice forms s_A = k_e,A + avf(P_e,A.x)k_s,A. Bob forms U_B = P_e,B + avf(P_e,B.x)P_s,B; Alice then derives the shared point s_AU_B. The corresponding calculation on Bob’s side produces the same point. section 4.2.1
Listing 4.6 Associate value function
void avf(mpz_t z, mpz_t x, BASE_SYSTEM bse)
{
long f, i;
mpz_t mask;
mpz_init(mask);
f = (mpz_sizeinbase(bse.order, 2) >> 1) + 1; #1
for(i=0; i<f; i++) #2
mpz_setbit(mask, i); #2
mpz_and(z, x, mask); #3
mpz_setbit(z, f); #4
mpz_clear(mask);
}
The C/GMP listing maps the formula directly to binary-size calculation, mask construction, masking, halfway-bit setting, and cleanup. section 4.2.2
