ctidh.c File Reference

#include <string.h>
#include <assert.h>
#include "ctidh.h"
#include "isogeny_walks.h"
#include "../common/primes.h"
#include "../common/int64mask.h"
#include "../common/elligator.h"
#include "../common/random.h"
#include "../common/fp/fp-counters.h"

Include dependency graph for ctidh.c:

Go to the source code of this file.

Functions
void	fulltorsion_points (fp u, fp const a)
void	action (public_key *out, public_key const *in, private_key const *priv)
bool	csidh (public_key *out, public_key const *in, private_key const *priv)

Variables
const public_key	base = {.A = {0}, .seed = ELLIGATOR_SEED}

Function Documentation

action()

void action	(	public_key *	out,
		public_key const *	in,
		private_key const *	priv )

Definition at line 176 of file ctidh.c.

{
// #if !defined(_M1_) && !defined(_M2_) && !defined(_M3_) && !defined(_M4_) && !defined(_M5_)
//   printf("\nNOT using radical 3-isogenies (action).\n\n");
// #else
//   printf("\nUsing 2^%ld radical 3-isogenies.\n\n", batch_start[0] - 1);
// #endif
 
  init_counters();
 
  proj A;
  fp_copy(A.x, in->A);
  fp_copy(A.z, fp_1);
 
  proj A24;
  xA24(&A24, &A);
 
  proj Points[2];
  fp seed;
  fp_set(seed, in->seed);
  fp_enc(seed, seed);
  elligator_seeded(&Points[0], &Points[1], &A24, (const fp *)seed);
 
  clearpublicprimes(&Points[0], &A24);
  clearpublicprimes(&Points[1], &A24);
 
  // clear ells replaced by radical 3-isogenies
  for (int16_t j = 0; j < batch_start[0]; j++)
  {
      xMUL_dac(&Points[0], &A24, 0, &Points[0], primes_dac[j], primes_daclen[j], primes_daclen[j]);
      xMUL_dac(&Points[1], &A24, 0, &Points[1], primes_dac[j], primes_daclen[j], primes_daclen[j]);
  }
  // clear ells not used in the keyspace
  for (int16_t j = batch_stop[primes_batches - 1] + 1; j < primes_num; j++)
  {
    xMUL_dac(&Points[0], &A24, 0, &Points[0], primes_dac[j], primes_daclen[j], primes_daclen[j]);
    xMUL_dac(&Points[1], &A24, 0, &Points[1], primes_dac[j], primes_daclen[j], primes_daclen[j]);
  }
 
  // collect primes not used in the key ...
  int16_t unused[batch_stop[primes_batches - 1] + 1];
 
  int16_t u = 0;
  int16_t e = 0;
  int16_t w = 0;
  for (e = 0; e <= batch_stop[primes_batches - 1]; e++)
  {
#ifdef ENABLE_CT_TESTING
        VALGRIND_MAKE_MEM_DEFINED(&u, sizeof(int16_t));
        VALGRIND_MAKE_MEM_DEFINED(&e, sizeof(int16_t));
        VALGRIND_MAKE_MEM_DEFINED(&w, sizeof(int16_t));
#endif
 
    unused[u] = e;
 
    int64_t mov = -int64mask_equal((int64_t)e, (int64_t)priv->ells[w]);
 
    fp t1, t2;
    t1[0] = u;
    t2[0] = u + 1;
    fp_cmov(&t1, (const fp *)&t2, 1 - mov);
    u = t1[0];
 
    t1[0] = w;
    t2[0] = w + 1;
    fp_cmov(&t1, (const fp *)&t2, mov);
    w = t1[0];
  }
 
  // ... and remove them from our points
  int16_t tmp_b = 0;
  for (u = 0; u <= batch_stop[primes_batches - 1] - WOMBATKEYS; u++)
  {
    int16_t t = unused[u];
    if (t > batch_stop[tmp_b])
      tmp_b++;
 
    int64_t dac = lookup(t, primes_dac);
    int64_t daclen = lookup(t, primes_daclen);
 
    xMUL_dac(&Points[0], &A24, 0, &Points[0], dac, daclen, batch_maxdac[tmp_b]);
    xMUL_dac(&Points[1], &A24, 0, &Points[1], dac, daclen, batch_maxdac[tmp_b]);
  }
 
 
  proj ramifications[2 * WOMBATKEYS] = {0};
  int inner,
      block = 0, // current size of ramifications
      pos,       // index of the current small odd prime to be processed
      k = 0;     // strategy element
 
  int64_t moves = 0, // required for reaching an torsion-(l_pos) point
      xmul_counter[WOMBATKEYS] = {0},
          Plen = 0;
  (void)pos;
 
  int8_t swap = 0;
 
  proj_copy(&ramifications[0], (const proj *)&Points[0]); // point on E[\pi + 1]
  proj_copy(&ramifications[1], (const proj *)&Points[1]); // point on E[\pi - 1]
 
  int16_t current_batch = 0; //primes_batches - 1;
  int16_t current_batch_inner = batch_numkeys[current_batch];
 
  proj Points_[2 * WOMBATKEYS] = {0};
 
  // #pragma unroll WOMBATKEYS
  //int64_t tmp_cost = fpmul+fpsqr;
  for (int i = WOMBATKEYS - 1; i >= 0; i--)
  {
    if ((WOMBATKEYS - i - 1) > batch_keybounds_stop[current_batch])
    {
      current_batch++;
      current_batch_inner = batch_numkeys[current_batch];
    }
 
 
    uint16_t flip_index = WOMBATKEYS - i -1;
    uint16_t current_ell_index = priv->ells[flip_index];
    uint64_t current_ell = lookup(current_ell_index, primes);
    // 0 -> dummy, 1 -> + direction, 2 -> - direction
    int64_t direction = priv->directions[flip_index];
 
    uint64_t lowerend_ell = primes[batch_start[current_batch] + batch_numkeys[current_batch] - current_batch_inner];
    uint64_t upperend_ell = primes[batch_stop[current_batch] - current_batch_inner + 1];
 
 
    // conditional swap based on direction
    swap = -int64mask_equal(direction, (int64_t)2);
    proj_cswap(&ramifications[0+ 2 * block], &ramifications[1+ 2 * block], swap);
 
    tmp_b = primes_batches-1;
    while (moves < i)
    {
      block += 1;
 
      proj_copy(&ramifications[0 + 2 * block], (const proj *)&ramifications[0 + 2 * (block - 1)]); // point on E[\pi + 1]
      proj_copy(&ramifications[1 + 2 * block], (const proj *)&ramifications[1 + 2 * (block - 1)]); // point on E[\pi - 1]
 
      // #pragma unroll
      for (inner = moves; inner < (moves + strategy[k]); inner++)
      {
        pos = WOMBATKEYS - inner -1;
        while (pos < batch_keybounds_start[tmp_b])
          tmp_b--;
 
        int64_t dac = lookup(priv->ells[pos], primes_dac);
        int64_t daclen = lookup(priv->ells[pos], primes_daclen);
 
        if(moves + strategy[k] < i)
        {
          xMUL_dac(&ramifications[0 + 2 * block], &A24, 0, &ramifications[0 + 2 * block], dac, daclen, batch_maxdac[tmp_b]);
          xMUL_dac(&ramifications[1 + 2 * block], &A24, 0, &ramifications[1 + 2 * block], dac, daclen, batch_maxdac[tmp_b]);
        }
        else { // current block
          xMUL_dac(&ramifications[0 + 2 * block], &A24, 0, &ramifications[0 + 2 * block], dac, daclen, batch_maxdac[tmp_b]);
        }
      }
 
      xmul_counter[block] = strategy[k]; // the k-th element is used for next iteration on moves
      moves += strategy[k];              // moves is incremented
      k += 1;
    } 
 
    // how many points should be evaluated?
    Plen = 2 * block;
 
 
    proj Anew;
    proj_copy(&Anew, &A);
    for (int j = 0; j < Plen; j++)
    {
      // backup for the dummy case
      proj_copy(&Points_[j], &ramifications[j]);
    }
 
    xISOG_matryoshka(&Anew, Points_, Plen, &ramifications[0 + 2 * block], current_ell, lowerend_ell, upperend_ell);
 
 
    // copy back
    proj_cmov(&A, &Anew, -int64mask_nonzero(direction));
    xA24(&A24, &A);
 
 
    for (int j = 0; j < Plen; j++)
    {
      proj_cmov(&ramifications[j], &Points_[j], -int64mask_nonzero(direction));
 
      // in case of dummy, we still need to "remove" degree
      
      int64_t dac = lookup(current_ell_index, primes_dac);
      int64_t daclen = lookup(current_ell_index, primes_daclen);
 
      xMUL_dac(&ramifications[j], &A24, 0, &ramifications[j], dac, daclen, batch_maxdac[current_batch]);
    }
 
 
    // Configuring for the next iteration
    moves -= xmul_counter[block];
    xmul_counter[block] = 0;
    block -= 1;
    // swap back based on direction
    proj_cswap(&ramifications[0+ 2 * block], &ramifications[1+ 2 * block], swap);
 
    current_batch_inner--;
  }
 
#if defined(_M0_)
    fp_inv(A.z);
    fp_mul2(&A.x, (const fp *)&A.z);
    fp_copy(out->A, A.x);
#else
    isogeny_walks_3_fp(out->A, A, priv->radical_length, priv->radical_direction);
#endif
 
}

References public_key::A, batch_keybounds_start, batch_keybounds_stop, batch_maxdac, batch_numkeys, batch_start, batch_stop, private_key::directions, elligator_seeded, private_key::ells, fp_1, fp_cmov, fp_copy, fp_enc, fp_inv, i, isogeny_walks_3_fp(), j, primes, primes_dac, primes_daclen, private_key::radical_direction, private_key::radical_length, public_key::seed, strategy, swap(), xA24, xISOG_matryoshka, and xMUL_dac.

Here is the call graph for this function:

csidh()

bool csidh	(	public_key *	out,
		public_key const *	in,
		private_key const *	priv )

Definition at line 394 of file ctidh.c.

{
  if (!validate(in))
  {
    fp_random(out->A);
    return false;
  }
  action(out, in, priv);
  return true;
}

References public_key::A, action, fp_random, and validate.

fulltorsion_points()

void fulltorsion_points	(	fp	u,
		fp const	a )

Definition at line 103 of file ctidh.c.

{
    proj Tp, Tm, Pp[batch_stop[primes_batches - 1] + 1], Pm[batch_stop[primes_batches - 1] + 1], A;
    int j;
 
    // Convert curve to projective Montgomery form (A' + 2C : 4C)
    fp_copy(A.x, a);
    fp_set1(A.z);
    fp_add(A.z, A.z, A.z); // 2C
    fp_add(A.x, A.x, A.z); // A' + 2C
    fp_add(A.z, A.z, A.z); // 4C
 
    fp_set0(u); // u <- 0
    uint8_t boolp = 0, boolm = 0;
 
    do
    {
 
#ifdef ENABLE_CT_TESTING
        VALGRIND_MAKE_MEM_DEFINED(&A, sizeof(proj));
        VALGRIND_MAKE_MEM_DEFINED(&boolp, sizeof(uint8_t));
        VALGRIND_MAKE_MEM_DEFINED(&boolm, sizeof(uint8_t));
        VALGRIND_MAKE_MEM_DEFINED(&Tp, sizeof(proj));
        VALGRIND_MAKE_MEM_DEFINED(Pp, sizeof(proj) * (batch_stop[primes_batches - 1] + 1 - batch_start[0]));
        VALGRIND_MAKE_MEM_DEFINED(Pm, sizeof(proj) * (batch_stop[primes_batches - 1] + 1 - batch_start[0]));
#endif
 
        fp_add(u, u, fp_1); // u <- u + 1 ... Recall, 1 must be in Montgomery domain
        elligator_seeded(&Tp, &Tm, &A, (const fp *)u);
 
        clearpublicprimes(&Tp, &A);
        clearpublicprimes(&Tm, &A);
        // clear ells replaced by radical 3-isogenies
        for (j = 0; j < batch_start[0]; j++)
        {
            xMUL_dac(&Tp, &A, 0, &Tp, primes_dac[j], primes_daclen[j], primes_daclen[j]);
            xMUL_dac(&Tm, &A, 0, &Tm, primes_dac[j], primes_daclen[j], primes_daclen[j]);
        }
        // clear ells not used in the keyspace
        for (j = batch_stop[primes_batches - 1] + 1; j < primes_num; j++)
        {
            xMUL_dac(&Tp, &A, 0, &Tp, primes_dac[j], primes_daclen[j], primes_daclen[j]);
            xMUL_dac(&Tm, &A, 0, &Tm, primes_dac[j], primes_daclen[j], primes_daclen[j]);
        }
 
        // Checking if Tp is an order (p+1)/(2^e)
        proj_copy(&Pp[0], &Tp);
        cofactor_multiples(Pp, A, 0, batch_stop[primes_batches - 1] + 1);
        boolp = 1;
        for (j = batch_start[0]; j < (int)(batch_stop[primes_batches - 1] + 1); j++)
            boolp &= (1 - fp_iszero(Pp[j].z));
 
        if (1 - boolp)
            continue;
 
        // ---> This can be removed for wd1 style
        // Checking if Tm is an order (p+1)/(2^e)
        proj_copy(&Pm[0], &Tm);
        cofactor_multiples(Pm, A, 0, batch_stop[primes_batches - 1] + 1);
 
        boolm = 1;
        for (j = batch_start[0]; j < (int)(batch_stop[primes_batches - 1] + 1); j++)
            boolm &= (1 - fp_iszero(Pm[j].z));
 
        if (1 - boolm)
            continue;
        // <---
    } while ((1 - boolp) | (1 - boolm));
 
    fp_dec(u, (uint64_t *const)u);
}

References a, batch_start, batch_stop, cofactor_multiples, elligator_seeded, fp_1, fp_add, fp_copy, fp_dec, j, primes_dac, primes_daclen, and xMUL_dac.

Variable Documentation

base

const public_key base = {.A = {0}, .seed = ELLIGATOR_SEED}

Definition at line 29 of file ctidh.c.

{.A = {0}, .seed = ELLIGATOR_SEED}; /* A = 0 */