common/mbedtls/ecc_point_compression.c

   1 /*
   2 * Not original to the mbedtls library. Taken from
   3 * https://github.com/mwarning/mbedtls_ecp_compression
   4 * to solve mbedtls' lack of support for elliptic point
   5 * compression and decompression
   6 *
   7 * Released under CC0 1.0 Universal License
   8 */
   9
  10 /*
  11 * This is all about mbedtls_ecp_decompress() and mbedtls_ecp_compress()
  12 *
  13 * Perform X25519 / Curve25519 point compression and decompression for mbedtls.
  14 * As of mbedtls 2.5.1, mbedtls does not support decompression yet.
  15 *
  16 */
  17
  18 #define MBEDTLS_ALLOW_PRIVATE_ACCESS
  19
  20 #include "ecc_point_compression.h"
  21
  22 int mbedtls_ecp_decompress(
  23     const mbedtls_ecp_group *grp,
  24     const unsigned char *input, size_t ilen,
  25     unsigned char *output, size_t *olen, size_t osize
  26 ) {
  27     int ret;
  28     size_t plen;
  29     mbedtls_mpi r;
  30     mbedtls_mpi x;
  31     mbedtls_mpi n;
  32
  33     plen = mbedtls_mpi_size(&grp->P);
  34
  35     *olen = 2 * plen + 1;
  36
  37     if (osize < *olen)
  38         return (MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL);
  39
  40     if (ilen != plen + 1)
  41         return (MBEDTLS_ERR_ECP_BAD_INPUT_DATA);
  42
  43     if (input[0] != 0x02 && input[0] != 0x03)
  44         return (MBEDTLS_ERR_ECP_BAD_INPUT_DATA);
  45
  46     // output will consist of 0x04|X|Y
  47     memcpy(output, input, ilen);
  48     output[0] = 0x04;
  49
  50     mbedtls_mpi_init(&r);
  51     mbedtls_mpi_init(&x);
  52     mbedtls_mpi_init(&n);
  53
  54     // x <= input
  55     MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary(&x, input + 1, plen));
  56
  57     // r = x^2
  58     MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&r, &x, &x));
  59
  60     // r = x^2 + a
  61     if (grp->A.p == NULL) {
  62         // Special case where a is -3
  63         MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&r, &r, 3));
  64     } else {
  65         MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&r, &r, &grp->A));
  66     }
  67
  68     // r = x^3 + ax
  69     MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&r, &r, &x));
  70
  71     // r = x^3 + ax + b
  72     MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&r, &r, &grp->B));
  73
  74     // Calculate square root of r over finite field P:
  75     //   r = sqrt(x^3 + ax + b) = (x^3 + ax + b) ^ ((P + 1) / 4) (mod P)
  76
  77     // n = P + 1
  78     MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&n, &grp->P, 1));
  79
  80     // n = (P + 1) / 4
  81     MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&n, 2));
  82
  83     // r ^ ((P + 1) / 4) (mod p)
  84     MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&r, &r, &n, &grp->P, NULL));
  85
  86     // Select solution that has the correct "sign" (equals odd/even solution in finite group)
  87     if ((input[0] == 0x03) != mbedtls_mpi_get_bit(&r, 0)) {
  88         // r = p - r
  89         MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&r, &grp->P, &r));
  90     }
  91
  92     // y => output
  93     ret = mbedtls_mpi_write_binary(&r, output + 1 + plen, plen);
  94
  95 cleanup:
  96     mbedtls_mpi_free(&r);
  97     mbedtls_mpi_free(&x);
  98     mbedtls_mpi_free(&n);
  99
 100     return (ret);
 101 }
 102
 103 int mbedtls_ecp_compress(
 104     const mbedtls_ecp_group *grp,
 105     const unsigned char *input, size_t ilen,
 106     unsigned char *output, size_t *olen, size_t osize
 107 ) {
 108     size_t plen;
 109
 110     plen = mbedtls_mpi_size(&grp->P);
 111
 112     *olen = plen + 1;
 113
 114     if (osize < *olen)
 115         return (MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL);
 116
 117     if (ilen != 2 * plen + 1)
 118         return (MBEDTLS_ERR_ECP_BAD_INPUT_DATA);
 119
 120     if (input[0] != 0x04)
 121         return (MBEDTLS_ERR_ECP_BAD_INPUT_DATA);
 122
 123     // output will consist of 0x0?|X
 124     memcpy(output, input, *olen);
 125
 126     // Encode even/odd of Y into first byte (either 0x02 or 0x03)
 127     output[0] = 0x02 + (input[2 * plen] & 1);
 128
 129     return (0);
 130 }