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-2024 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 2.4.0
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 #if (CRYPTO_STATIC_MEM_SUPPORT == DISABLED)
59  X25519State *state;
60 #else
61  X25519State state[1];
62 #endif
63 
64  //Check parameters
65  if(r == NULL || k == NULL || u == NULL)
67 
68 #if (CRYPTO_STATIC_MEM_SUPPORT == DISABLED)
69  //Allocate working state
70  state = cryptoAllocMem(sizeof(X25519State));
71  //Failed to allocate memory?
72  if(state == NULL)
73  return ERROR_OUT_OF_MEMORY;
74 #endif
75 
76  //Copy scalar
77  curve25519Import(state->k, k);
78 
79  //Set the three least significant bits of the first byte and the most
80  //significant bit of the last to zero, set the second most significant
81  //bit of the last byte to 1
82  state->k[0] &= 0xFFFFFFF8;
83  state->k[7] &= 0x7FFFFFFF;
84  state->k[7] |= 0x40000000;
85 
86  //Copy input u-coordinate
87  curve25519Import(state->u, u);
88 
89  //Implementations must mask the most significant bit in the final byte
90  state->u[7] &= 0x7FFFFFFF;
91 
92  //Implementations must accept non-canonical values and process them as
93  //if they had been reduced modulo the field prime (refer to RFC 7748,
94  //section 5)
95  curve25519Red(state->u, state->u);
96 
97  //Set X1 = 1
98  curve25519SetInt(state->x1, 1);
99  //Set Z1 = 0
100  curve25519SetInt(state->z1, 0);
101  //Set X2 = U
102  curve25519Copy(state->x2, state->u);
103  //Set Z2 = 1
104  curve25519SetInt(state->z2, 1);
105 
106  //Set swap = 0
107  swap = 0;
108 
109  //Montgomery ladder
110  for(i = CURVE25519_BIT_LEN - 1; i >= 0; i--)
111  {
112  //The scalar is processed in a left-to-right fashion
113  b = (state->k[i / 32] >> (i % 32)) & 1;
114 
115  //Conditional swap
116  curve25519Swap(state->x1, state->x2, swap ^ b);
117  curve25519Swap(state->z1, state->z2, swap ^ b);
118 
119  //Save current bit value
120  swap = b;
121 
122  //Compute T1 = X2 + Z2
123  curve25519Add(state->t1, state->x2, state->z2);
124  //Compute X2 = X2 - Z2
125  curve25519Sub(state->x2, state->x2, state->z2);
126  //Compute Z2 = X1 + Z1
127  curve25519Add(state->z2, state->x1, state->z1);
128  //Compute X1 = X1 - Z1
129  curve25519Sub(state->x1, state->x1, state->z1);
130  //Compute T1 = T1 * X1
131  curve25519Mul(state->t1, state->t1, state->x1);
132  //Compute X2 = X2 * Z2
133  curve25519Mul(state->x2, state->x2, state->z2);
134  //Compute Z2 = Z2 * Z2
135  curve25519Sqr(state->z2, state->z2);
136  //Compute X1 = X1 * X1
137  curve25519Sqr(state->x1, state->x1);
138  //Compute T2 = Z2 - X1
139  curve25519Sub(state->t2, state->z2, state->x1);
140  //Compute Z1 = T2 * a24
141  curve25519MulInt(state->z1, state->t2, CURVE25519_A24);
142  //Compute Z1 = Z1 + X1
143  curve25519Add(state->z1, state->z1, state->x1);
144  //Compute Z1 = Z1 * T2
145  curve25519Mul(state->z1, state->z1, state->t2);
146  //Compute X1 = X1 * Z2
147  curve25519Mul(state->x1, state->x1, state->z2);
148  //Compute Z2 = T1 - X2
149  curve25519Sub(state->z2, state->t1, state->x2);
150  //Compute Z2 = Z2 * Z2
151  curve25519Sqr(state->z2, state->z2);
152  //Compute Z2 = Z2 * U
153  curve25519Mul(state->z2, state->z2, state->u);
154  //Compute X2 = X2 + T1
155  curve25519Add(state->x2, state->x2, state->t1);
156  //Compute X2 = X2 * X2
157  curve25519Sqr(state->x2, state->x2);
158  }
159 
160  //Conditional swap
161  curve25519Swap(state->x1, state->x2, swap);
162  curve25519Swap(state->z1, state->z2, swap);
163 
164  //Retrieve affine representation
165  curve25519Inv(state->u, state->z1);
166  curve25519Mul(state->u, state->u, state->x1);
167 
168  //Copy output u-coordinate
169  curve25519Export(state->u, r);
170 
171  //Erase working state
172  osMemset(state, 0, sizeof(X25519State));
173 
174 #if (CRYPTO_STATIC_MEM_SUPPORT == DISABLED)
175  //Release working state
176  cryptoFreeMem(state);
177 #endif
178 
179  //Successful processing
180  return NO_ERROR;
181 }
182 
183 #endif
signed int int_t
Definition: compiler_port.h:49
General definitions for cryptographic algorithms.
#define cryptoAllocMem(size)
Definition: crypto.h:765
#define cryptoFreeMem(p)
Definition: crypto.h:770
void curve25519SetInt(uint32_t *a, uint32_t b)
Set integer value.
Definition: curve25519.c:57
__weak_func void curve25519Mul(uint32_t *r, const uint32_t *a, const uint32_t *b)
Modular multiplication.
Definition: curve25519.c:191
__weak_func void curve25519Sqr(uint32_t *r, const uint32_t *a)
Modular squaring.
Definition: curve25519.c:317
void curve25519Sub(uint32_t *r, const uint32_t *a, const uint32_t *b)
Modular subtraction.
Definition: curve25519.c:130
void curve25519Export(uint32_t *a, uint8_t *data)
Export an octet string.
Definition: curve25519.c:634
void curve25519Copy(uint32_t *a, const uint32_t *b)
Copy an integer.
Definition: curve25519.c:515
void curve25519Inv(uint32_t *r, const uint32_t *a)
Modular multiplicative inverse.
Definition: curve25519.c:380
void curve25519Red(uint32_t *r, const uint32_t *a)
Modular reduction.
Definition: curve25519.c:352
void curve25519Import(uint32_t *a, const uint8_t *data)
Import an octet string.
Definition: curve25519.c:613
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
void curve25519MulInt(uint32_t *r, const uint32_t *a, uint32_t b)
Modular multiplication.
Definition: curve25519.c:277
Curve25519 elliptic curve (constant-time implementation)
#define CURVE25519_BIT_LEN
Definition: curve25519.h:38
#define CURVE25519_A24
Definition: curve25519.h:43
Debugging facilities.
Elliptic curves.
error_t
Error codes.
Definition: error.h:43
@ NO_ERROR
Success.
Definition: error.h:44
@ ERROR_OUT_OF_MEMORY
Definition: error.h:63
@ ERROR_INVALID_PARAMETER
Invalid parameter.
Definition: error.h:47
uint8_t u
Definition: lldp_ext_med.h:213
uint8_t b
Definition: nbns_common.h:104
uint8_t r
Definition: ndp.h:346
#define osMemset(p, value, length)
Definition: os_port.h:135
X25519 working state.
Definition: x25519.h:49
uint32_t z2[8]
Definition: x25519.h:55
uint32_t t2[8]
Definition: x25519.h:57
uint32_t z1[8]
Definition: x25519.h:53
uint32_t t1[8]
Definition: x25519.h:56
uint32_t x1[8]
Definition: x25519.h:52
uint32_t u[8]
Definition: x25519.h:51
uint32_t k[8]
Definition: x25519.h:50
uint32_t x2[8]
Definition: x25519.h:54
error_t x25519(uint8_t *r, const uint8_t *k, const uint8_t *u)
X25519 function (scalar multiplication on Curve25519)
Definition: x25519.c:53
X25519 function implementation.