crypto_ecc_dlog.c (9600B)
1 /* 2 This file is part of GNUnet. 3 Copyright (C) 2012, 2013, 2015 GNUnet e.V. 4 5 GNUnet is free software: you can redistribute it and/or modify it 6 under the terms of the GNU Affero General Public License as published 7 by the Free Software Foundation, either version 3 of the License, 8 or (at your option) any later version. 9 10 GNUnet is distributed in the hope that it will be useful, but 11 WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 Affero General Public License for more details. 14 15 You should have received a copy of the GNU Affero General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. 17 18 SPDX-License-Identifier: AGPL3.0-or-later 19 */ 20 21 /** 22 * @file util/crypto_ecc_dlog.c 23 * @brief ECC addition and discreate logarithm for small values. 24 * Allows us to use ECC for computations as long as the 25 * result is relativey small. 26 * @author Christian Grothoff 27 */ 28 29 #include "platform.h" 30 #include <gcrypt.h> 31 #include "gnunet_util_lib.h" 32 33 34 /** 35 * Internal structure used to cache pre-calculated values for DLOG calculation. 36 */ 37 struct GNUNET_CRYPTO_EccDlogContext 38 { 39 /** 40 * Maximum absolute value the calculation supports. 41 */ 42 unsigned int max; 43 44 /** 45 * How much memory should we use (relates to the number of entries in the map). 46 */ 47 unsigned int mem; 48 49 /** 50 * Map mapping points (here "interpreted" as EdDSA public keys) to 51 * a "void * = long" which corresponds to the numeric value of the 52 * point. As NULL is used to represent "unknown", the actual value 53 * represented by the entry in the map is the "long" minus @e max. 54 */ 55 struct GNUNET_CONTAINER_MultiPeerMap *map; 56 57 /** 58 * Context to use for operations on the elliptic curve. 59 */ 60 gcry_ctx_t ctx; 61 }; 62 63 64 struct GNUNET_CRYPTO_EccDlogContext * 65 GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max, 66 unsigned int mem) 67 { 68 struct GNUNET_CRYPTO_EccDlogContext *edc; 69 int K = ((max + (mem - 1)) / mem); 70 71 GNUNET_assert (max < INT32_MAX); 72 GNUNET_assert (mem <= UINT32_MAX / 2); 73 edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext); 74 edc->max = max; 75 edc->mem = mem; 76 edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2, 77 GNUNET_NO); 78 for (int i = -(int) mem; i <= (int) mem; i++) 79 { 80 struct GNUNET_CRYPTO_EccScalar Ki; 81 struct GNUNET_PeerIdentity key; 82 83 GNUNET_CRYPTO_ecc_scalar_from_int (K * i, 84 &Ki); 85 if (0 == i) /* libsodium does not like to multiply with zero */ 86 GNUNET_assert ( 87 0 == 88 crypto_core_ed25519_sub ((unsigned char *) &key, 89 (unsigned char *) &key, 90 (unsigned char *) &key)); 91 else 92 GNUNET_assert ( 93 0 == 94 crypto_scalarmult_ed25519_base_noclamp ((unsigned char*) &key, 95 Ki.v)); 96 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, 97 "K*i: %d (mem=%u, i=%d) => %s\n", 98 K * i, 99 mem, 100 i, 101 GNUNET_i2s (&key)); 102 GNUNET_assert (GNUNET_OK == 103 GNUNET_CONTAINER_multipeermap_put (edc->map, 104 &key, 105 (void *) (long) i + max, 106 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); 107 } 108 return edc; 109 } 110 111 112 int 113 GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc, 114 const struct GNUNET_CRYPTO_EccPoint *input) 115 { 116 unsigned int K = ((edc->max + (edc->mem - 1)) / edc->mem); 117 int res; 118 struct GNUNET_CRYPTO_EccPoint g; 119 struct GNUNET_CRYPTO_EccPoint q; 120 struct GNUNET_CRYPTO_EccPoint nq; 121 122 { 123 struct GNUNET_CRYPTO_EccScalar fact; 124 125 memset (&fact, 126 0, 127 sizeof (fact)); 128 sodium_increment (fact.v, 129 sizeof (fact.v)); 130 GNUNET_assert (0 == 131 crypto_scalarmult_ed25519_base_noclamp (g.v, 132 fact.v)); 133 } 134 /* make compiler happy: initialize q and nq, technically not needed! */ 135 memset (&q, 136 0, 137 sizeof (q)); 138 memset (&nq, 139 0, 140 sizeof (nq)); 141 res = INT_MAX; 142 for (unsigned int i = 0; i <= edc->max / edc->mem; i++) 143 { 144 struct GNUNET_PeerIdentity key; 145 void *retp; 146 147 GNUNET_assert (sizeof (key) == crypto_scalarmult_BYTES); 148 if (0 == i) 149 { 150 memcpy (&key, 151 input, 152 sizeof (key)); 153 } 154 else 155 { 156 memcpy (&key, 157 &q, 158 sizeof (key)); 159 } 160 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, 161 "Trying offset i=%u): %s\n", 162 i, 163 GNUNET_i2s (&key)); 164 retp = GNUNET_CONTAINER_multipeermap_get (edc->map, 165 &key); 166 if (NULL != retp) 167 { 168 res = (((long) retp) - edc->max) * K - i; 169 /* we continue the loop here to make the implementation 170 "constant-time". If we do not care about this, we could just 171 'break' here and do fewer operations... */ 172 } 173 if (i == edc->max / edc->mem) 174 break; 175 /* q = q + g */ 176 if (0 == i) 177 { 178 GNUNET_assert (0 == 179 crypto_core_ed25519_add (q.v, 180 input->v, 181 g.v)); 182 } 183 else 184 { 185 GNUNET_assert (0 == 186 crypto_core_ed25519_add (q.v, 187 q.v, 188 g.v)); 189 } 190 } 191 return res; 192 } 193 194 195 void 196 GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccScalar *r) 197 { 198 crypto_core_ed25519_scalar_random (r->v); 199 } 200 201 202 void 203 GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc) 204 { 205 GNUNET_CONTAINER_multipeermap_destroy (edc->map); 206 GNUNET_free (edc); 207 } 208 209 210 void 211 GNUNET_CRYPTO_ecc_dexp (int val, 212 struct GNUNET_CRYPTO_EccPoint *r) 213 { 214 struct GNUNET_CRYPTO_EccScalar fact; 215 216 GNUNET_CRYPTO_ecc_scalar_from_int (val, 217 &fact); 218 crypto_scalarmult_ed25519_base_noclamp (r->v, 219 fact.v); 220 } 221 222 223 enum GNUNET_GenericReturnValue 224 GNUNET_CRYPTO_ecc_dexp_mpi (const struct GNUNET_CRYPTO_EccScalar *val, 225 struct GNUNET_CRYPTO_EccPoint *r) 226 { 227 if (0 == 228 crypto_scalarmult_ed25519_base_noclamp (r->v, 229 val->v)) 230 return GNUNET_OK; 231 return GNUNET_SYSERR; 232 } 233 234 235 enum GNUNET_GenericReturnValue 236 GNUNET_CRYPTO_ecc_add (const struct GNUNET_CRYPTO_EccPoint *a, 237 const struct GNUNET_CRYPTO_EccPoint *b, 238 struct GNUNET_CRYPTO_EccPoint *r) 239 { 240 if (0 == 241 crypto_core_ed25519_add (r->v, 242 a->v, 243 b->v)) 244 return GNUNET_OK; 245 return GNUNET_SYSERR; 246 } 247 248 249 enum GNUNET_GenericReturnValue 250 GNUNET_CRYPTO_ecc_pmul_mpi (const struct GNUNET_CRYPTO_EccPoint *p, 251 const struct GNUNET_CRYPTO_EccScalar *val, 252 struct GNUNET_CRYPTO_EccPoint *r) 253 { 254 if (0 == 255 crypto_scalarmult_ed25519_noclamp (r->v, 256 val->v, 257 p->v)) 258 return GNUNET_OK; 259 return GNUNET_SYSERR; 260 } 261 262 263 enum GNUNET_GenericReturnValue 264 GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccPoint *r, 265 struct GNUNET_CRYPTO_EccPoint *r_inv) 266 { 267 struct GNUNET_CRYPTO_EccScalar s; 268 unsigned char inv_s[crypto_scalarmult_ed25519_SCALARBYTES]; 269 270 GNUNET_CRYPTO_ecc_random_mod_n (&s); 271 if (0 != 272 crypto_scalarmult_ed25519_base_noclamp (r->v, 273 s.v)) 274 return GNUNET_SYSERR; 275 crypto_core_ed25519_scalar_negate (inv_s, 276 s.v); 277 if (0 != 278 crypto_scalarmult_ed25519_base_noclamp (r_inv->v, 279 inv_s)) 280 return GNUNET_SYSERR; 281 return GNUNET_OK; 282 } 283 284 285 void 286 GNUNET_CRYPTO_ecc_rnd_mpi (struct GNUNET_CRYPTO_EccScalar *r, 287 struct GNUNET_CRYPTO_EccScalar *r_neg) 288 { 289 GNUNET_CRYPTO_ecc_random_mod_n (r); 290 crypto_core_ed25519_scalar_negate (r_neg->v, 291 r->v); 292 } 293 294 295 void 296 GNUNET_CRYPTO_ecc_scalar_from_int (int64_t val, 297 struct GNUNET_CRYPTO_EccScalar *r) 298 { 299 unsigned char fact[crypto_scalarmult_ed25519_SCALARBYTES]; 300 uint64_t valBe; 301 302 GNUNET_assert (sizeof (*r) == sizeof (fact)); 303 if (val < 0) 304 { 305 if (INT64_MIN == val) 306 valBe = GNUNET_htonll ((uint64_t) INT64_MAX); 307 else 308 valBe = GNUNET_htonll ((uint64_t) (-val)); 309 } 310 else 311 { 312 valBe = GNUNET_htonll ((uint64_t) val); 313 } 314 memset (fact, 315 0, 316 sizeof (fact)); 317 for (unsigned int i = 0; i < sizeof (val); i++) 318 fact[i] = ((unsigned char*) &valBe)[sizeof (val) - 1 - i]; 319 if (val < 0) 320 { 321 if (INT64_MIN == val) 322 /* See above: fact is one too small, increment now that we can */ 323 sodium_increment (fact, 324 sizeof (fact)); 325 crypto_core_ed25519_scalar_negate (r->v, 326 fact); 327 } 328 else 329 { 330 memcpy (r, 331 fact, 332 sizeof (fact)); 333 } 334 } 335 336 337 /* end of crypto_ecc_dlog.c */