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