x25519.c
Go to the documentation of this file.
1 /**
2  * @file x25519.c
3  * @brief X25519 function implementation
4  *
5  * @section License
6  *
7  * Copyright (C) 2010-2018 Oryx Embedded SARL. All rights reserved.
8  *
9  * This file is part of CycloneCrypto Open.
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public License
13  * as published by the Free Software Foundation; either version 2
14  * of the License, or (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, write to the Free Software Foundation,
23  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
24  *
25  * @author Oryx Embedded SARL (www.oryx-embedded.com)
26  * @version 1.9.0
27  **/
28 
29 //Switch to the appropriate trace level
30 #define TRACE_LEVEL CRYPTO_TRACE_LEVEL
31 
32 //Dependencies
33 #include "core/crypto.h"
34 #include "ecc/ec_curves.h"
35 #include "ecc/curve25519.h"
36 #include "ecc/x25519.h"
37 #include "debug.h"
38 
39 //Check crypto library configuration
40 #if (X25519_SUPPORT == ENABLED)
41 
42 
43 /**
44  * @brief X25519 function (scalar multiplication on Curve25519)
45  * @param[out] r Output u-coordinate
46  * @param[in] k Input scalar
47  * @param[in] u Input u-coordinate
48  * @return Error code
49  **/
50 
51 error_t x25519(uint8_t *r, const uint8_t *k, const uint8_t *u)
52 {
53  int_t i;
54  uint32_t b;
55  uint32_t swap;
56  X25519State *state;
57 
58  //Check parameters
59  if(r == NULL || k == NULL || u == NULL)
61 
62  //Allocate working state
63  state = cryptoAllocMem(sizeof(X25519State));
64  //Failed to allocate memory?
65  if(state == NULL)
66  return ERROR_OUT_OF_MEMORY;
67 
68  //Copy scalar
69  curve25519Import(state->k, k);
70 
71  //Set the three least significant bits of the first byte and the most
72  //significant bit of the last to zero, set the second most significant
73  //bit of the last byte to 1
74  state->k[0] &= 0xFFFFFFF8;
75  state->k[7] &= 0x7FFFFFFF;
76  state->k[7] |= 0x40000000;
77 
78  //Copy input u-coordinate
79  curve25519Import(state->u, u);
80 
81  //Implementations must mask the most significant bit in the final byte
82  state->u[7] &= 0x7FFFFFFF;
83 
84  //Implementations must accept non-canonical values and process them as
85  //if they had been reduced modulo the field prime (refer to RFC 7748,
86  //section 5)
87  curve25519Red(state->u, state->u);
88 
89  //Set X1 = 1
90  curve25519SetInt(state->x1, 1);
91  //Set Z1 = 0
92  curve25519SetInt(state->z1, 0);
93  //Set X2 = U
94  curve25519Copy(state->x2, state->u);
95  //Set Z2 = 1
96  curve25519SetInt(state->z2, 1);
97 
98  //Set swap = 0
99  swap = 0;
100 
101  //Montgomery ladder
102  for(i = CURVE25519_BIT_LEN - 1; i >= 0; i--)
103  {
104  //The scalar is processed in a left-to-right fashion
105  b = (state->k[i / 32] >> (i % 32)) & 1;
106 
107  //Conditional swap
108  curve25519Swap(state->x1, state->x2, swap ^ b);
109  curve25519Swap(state->z1, state->z2, swap ^ b);
110 
111  //Save current bit value
112  swap = b;
113 
114  //Compute T1 = X2 + Z2
115  curve25519Add(state->t1, state->x2, state->z2);
116  //Compute X2 = X2 - Z2
117  curve25519Sub(state->x2, state->x2, state->z2);
118  //Compute Z2 = X1 + Z1
119  curve25519Add(state->z2, state->x1, state->z1);
120  //Compute X1 = X1 - Z1
121  curve25519Sub(state->x1, state->x1, state->z1);
122  //Compute T1 = T1 * X1
123  curve25519Mul(state->t1, state->t1, state->x1);
124  //Compute X2 = X2 * Z2
125  curve25519Mul(state->x2, state->x2, state->z2);
126  //Compute Z2 = Z2 * Z2
127  curve25519Sqr(state->z2, state->z2);
128  //Compute X1 = X1 * X1
129  curve25519Sqr(state->x1, state->x1);
130  //Compute T2 = Z2 - X1
131  curve25519Sub(state->t2, state->z2, state->x1);
132  //Compute Z1 = T2 * a24
133  curve25519MulInt(state->z1, state->t2, CURVE25519_A24);
134  //Compute Z1 = Z1 + X1
135  curve25519Add(state->z1, state->z1, state->x1);
136  //Compute Z1 = Z1 * T2
137  curve25519Mul(state->z1, state->z1, state->t2);
138  //Compute X1 = X1 * Z2
139  curve25519Mul(state->x1, state->x1, state->z2);
140  //Compute Z2 = T1 - X2
141  curve25519Sub(state->z2, state->t1, state->x2);
142  //Compute Z2 = Z2 * Z2
143  curve25519Sqr(state->z2, state->z2);
144  //Compute Z2 = Z2 * U
145  curve25519Mul(state->z2, state->z2, state->u);
146  //Compute X2 = X2 + T1
147  curve25519Add(state->x2, state->x2, state->t1);
148  //Compute X2 = X2 * X2
149  curve25519Sqr(state->x2, state->x2);
150  }
151 
152  //Conditional swap
153  curve25519Swap(state->x1, state->x2, swap);
154  curve25519Swap(state->z1, state->z2, swap);
155 
156  //Retrieve affine representation
157  curve25519Inv(state->u, state->z1);
158  curve25519Mul(state->u, state->u, state->x1);
159 
160  //Copy output u-coordinate
161  curve25519Export(state->u, r);
162 
163  //Erase working state
164  cryptoMemset(state, 0, sizeof(X25519State));
165  //Release working state
166  cryptoFreeMem(state);
167 
168  //Successful processing
169  return NO_ERROR;
170 }
171 
172 #endif
void curve25519Inv(uint32_t *r, const uint32_t *a)
Modular multiplicative inverse.
Definition: curve25519.c:378
uint32_t z2[8]
Definition: x25519.h:53
#define cryptoFreeMem(p)
Definition: crypto.h:578
uint32_t t2[8]
Definition: x25519.h:55
error_t x25519(uint8_t *r, const uint8_t *k, const uint8_t *u)
X25519 function (scalar multiplication on Curve25519)
Definition: x25519.c:51
Debugging facilities.
void curve25519Mul(uint32_t *r, const uint32_t *a, const uint32_t *b)
Modular multiplication.
Definition: curve25519.c:189
#define cryptoAllocMem(size)
Definition: crypto.h:573
General definitions for cryptographic algorithms.
Invalid parameter.
Definition: error.h:45
uint32_t t1[8]
Definition: x25519.h:54
void curve25519Export(uint32_t *a, uint8_t *data)
Export an octet string.
Definition: curve25519.c:632
uint32_t z1[8]
Definition: x25519.h:51
Curve25519 elliptic curve (constant-time implementation)
Elliptic curves.
void curve25519SetInt(uint32_t *a, uint32_t b)
Set integer value.
Definition: curve25519.c:55
uint32_t x1[8]
Definition: x25519.h:50
X25519 function implementation.
signed int int_t
Definition: compiler_port.h:42
void curve25519Copy(uint32_t *a, const uint32_t *b)
Copy an integer.
Definition: curve25519.c:513
void curve25519Sqr(uint32_t *r, const uint32_t *a)
Modular squaring.
Definition: curve25519.c:315
void curve25519Red(uint32_t *r, const uint32_t *a)
Modular reduction.
Definition: curve25519.c:350
#define CURVE25519_A24
Definition: curve25519.h:41
void curve25519Add(uint32_t *r, const uint32_t *a, const uint32_t *b)
Modular addition.
Definition: curve25519.c:77
Success.
Definition: error.h:42
void curve25519MulInt(uint32_t *r, const uint32_t *a, uint32_t b)
Modular multiplication.
Definition: curve25519.c:275
error_t
Error codes.
Definition: error.h:40
void curve25519Sub(uint32_t *r, const uint32_t *a, const uint32_t *b)
Modular subtraction.
Definition: curve25519.c:128
uint32_t k[8]
Definition: x25519.h:48
uint32_t r
Definition: ndp.h:342
void curve25519Import(uint32_t *a, const uint8_t *data)
Import an octet string.
Definition: curve25519.c:611
void curve25519Swap(uint32_t *a, uint32_t *b, uint32_t c)
Conditional swap.
Definition: curve25519.c:532
X25519 working state.
Definition: x25519.h:46
#define cryptoMemset(p, value, length)
Definition: crypto.h:584
uint32_t u[8]
Definition: x25519.h:49
uint8_t b[6]
Definition: dtls_misc.h:130
uint32_t x2[8]
Definition: x25519.h:52
#define CURVE25519_BIT_LEN
Definition: curve25519.h:36