Branch data     Line data    Source code

       1                 :             : /* Curve25519 (Montgomery form)
       2                 :             :  * Daniel Beer <dlbeer@gmail.com>, 18 Apr 2014
       3                 :             :  *
       4                 :             :  * This file is in the public domain.
       5                 :             :  */
       6                 :             : 
       7                 :             : #include "c25519.h"
       8                 :             : 
       9                 :             : #ifndef COMPACT_DISABLE_X25519
      10                 :             : const uint8_t c25519_base_x[F25519_SIZE] = {9};
      11                 :             : 
      12                 :             : /* Double an X-coordinate */
      13                 :         508 : static void xc_double(uint8_t *x3, uint8_t *z3,
      14                 :             :                       const uint8_t *x1, const uint8_t *z1)
      15                 :             : {
      16                 :             :         /* Explicit formulas database: dbl-1987-m
      17                 :             :          *
      18                 :             :          * source 1987 Montgomery "Speeding the Pollard and elliptic
      19                 :             :          *   curve methods of factorization", page 261, fourth display
      20                 :             :          * compute X3 = (X1^2-Z1^2)^2
      21                 :             :          * compute Z3 = 4 X1 Z1 (X1^2 + a X1 Z1 + Z1^2)
      22                 :             :          */
      23                 :         508 :         uint8_t x1sq[F25519_SIZE];
      24                 :         508 :         uint8_t z1sq[F25519_SIZE];
      25                 :         508 :         uint8_t x1z1[F25519_SIZE];
      26                 :         508 :         uint8_t a[F25519_SIZE];
      27                 :             : 
      28                 :         508 :         f25519_mul__distinct(x1sq, x1, x1);
      29                 :         508 :         f25519_mul__distinct(z1sq, z1, z1);
      30                 :         508 :         f25519_mul__distinct(x1z1, x1, z1);
      31                 :             : 
      32                 :         508 :         f25519_sub(a, x1sq, z1sq);
      33                 :         508 :         f25519_mul__distinct(x3, a, a);
      34                 :             : 
      35                 :         508 :         f25519_mul_c(a, x1z1, 486662);
      36                 :         508 :         f25519_add(a, x1sq, a);
      37                 :         508 :         f25519_add(a, z1sq, a);
      38                 :         508 :         f25519_mul__distinct(x1sq, x1z1, a);
      39                 :         508 :         f25519_mul_c(z3, x1sq, 4);
      40                 :         508 : }
      41                 :             : 
      42                 :             : /* Differential addition */
      43                 :        1016 : static void xc_diffadd(uint8_t *x5, uint8_t *z5,
      44                 :             :                        const uint8_t *x1, const uint8_t *z1,
      45                 :             :                        const uint8_t *x2, const uint8_t *z2,
      46                 :             :                        const uint8_t *x3, const uint8_t *z3)
      47                 :             : {
      48                 :             :         /* Explicit formulas database: dbl-1987-m3
      49                 :             :          *
      50                 :             :          * source 1987 Montgomery "Speeding the Pollard and elliptic curve
      51                 :             :          *   methods of factorization", page 261, fifth display, plus
      52                 :             :          *   common-subexpression elimination
      53                 :             :          * compute A = X2+Z2
      54                 :             :          * compute B = X2-Z2
      55                 :             :          * compute C = X3+Z3
      56                 :             :          * compute D = X3-Z3
      57                 :             :          * compute DA = D A
      58                 :             :          * compute CB = C B
      59                 :             :          * compute X5 = Z1(DA+CB)^2
      60                 :             :          * compute Z5 = X1(DA-CB)^2
      61                 :             :          */
      62                 :        1016 :         uint8_t da[F25519_SIZE];
      63                 :        1016 :         uint8_t cb[F25519_SIZE];
      64                 :        1016 :         uint8_t a[F25519_SIZE];
      65                 :        1016 :         uint8_t b[F25519_SIZE];
      66                 :             : 
      67                 :        1016 :         f25519_add(a, x2, z2);
      68                 :        1016 :         f25519_sub(b, x3, z3); /* D */
      69                 :        1016 :         f25519_mul__distinct(da, a, b);
      70                 :             : 
      71                 :        1016 :         f25519_sub(b, x2, z2);
      72                 :        1016 :         f25519_add(a, x3, z3); /* C */
      73                 :        1016 :         f25519_mul__distinct(cb, a, b);
      74                 :             : 
      75                 :        1016 :         f25519_add(a, da, cb);
      76                 :        1016 :         f25519_mul__distinct(b, a, a);
      77                 :        1016 :         f25519_mul__distinct(x5, z1, b);
      78                 :             : 
      79                 :        1016 :         f25519_sub(a, da, cb);
      80                 :        1016 :         f25519_mul__distinct(b, a, a);
      81                 :        1016 :         f25519_mul__distinct(z5, x1, b);
      82                 :        1016 : }
      83                 :             : 
      84                 :           2 : void c25519_smult(uint8_t *result, const uint8_t *q, const uint8_t *e)
      85                 :             : {
      86                 :             :         /* Current point: P_m */
      87                 :           2 :         uint8_t xm[F25519_SIZE];
      88                 :           2 :         uint8_t zm[F25519_SIZE] = {1};
      89                 :             : 
      90                 :             :         /* Predecessor: P_(m-1) */
      91                 :           2 :         uint8_t xm1[F25519_SIZE] = {1};
      92                 :           2 :         uint8_t zm1[F25519_SIZE] = {0};
      93                 :             : 
      94                 :           2 :         int i;
      95                 :             : 
      96                 :             :         /* Note: bit 254 is assumed to be 1 */
      97                 :           2 :         f25519_copy(xm, q);
      98                 :             : 
      99         [ +  + ]:         512 :         for (i = 253; i >= 0; i--) {
     100                 :         508 :                 const int bit = (e[i >> 3] >> (i & 7)) & 1;
     101                 :         508 :                 uint8_t xms[F25519_SIZE];
     102                 :         508 :                 uint8_t zms[F25519_SIZE];
     103                 :             : 
     104                 :             :                 /* From P_m and P_(m-1), compute P_(2m) and P_(2m-1) */
     105                 :         508 :                 xc_diffadd(xm1, zm1, q, f25519_one, xm, zm, xm1, zm1);
     106                 :         508 :                 xc_double(xm, zm, xm, zm);
     107                 :             : 
     108                 :             :                 /* Compute P_(2m+1) */
     109                 :         508 :                 xc_diffadd(xms, zms, xm1, zm1, xm, zm, q, f25519_one);
     110                 :             : 
     111                 :             :                 /* Select:
     112                 :             :                  *   bit = 1 --> (P_(2m+1), P_(2m))
     113                 :             :                  *   bit = 0 --> (P_(2m), P_(2m-1))
     114                 :             :                  */
     115                 :         508 :                 f25519_select(xm1, xm1, xm, bit);
     116                 :         508 :                 f25519_select(zm1, zm1, zm, bit);
     117                 :         508 :                 f25519_select(xm, xm, xms, bit);
     118                 :         508 :                 f25519_select(zm, zm, zms, bit);
     119                 :             :         }
     120                 :             : 
     121                 :             :         /* Freeze out of projective coordinates */
     122                 :           2 :         f25519_inv__distinct(zm1, zm);
     123                 :           2 :         f25519_mul__distinct(result, zm1, xm);
     124                 :           2 :         f25519_normalize(result);
     125                 :           2 : }
     126                 :             : #endif