crypto_ecc_dlog.c (9492B)
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 "gnunet_util_lib.h" 31 32 33 /** 34 * Internal structure used to cache pre-calculated values for DLOG calculation. 35 */ 36 struct GNUNET_CRYPTO_EccDlogContext 37 { 38 /** 39 * Maximum absolute value the calculation supports. 40 */ 41 unsigned int max; 42 43 /** 44 * How much memory should we use (relates to the number of entries in the map). 45 */ 46 unsigned int mem; 47 48 /** 49 * Map mapping points (here "interpreted" as EdDSA public keys) to 50 * a "void * = long" which corresponds to the numeric value of the 51 * point. As NULL is used to represent "unknown", the actual value 52 * represented by the entry in the map is the "long" minus @e max. 53 */ 54 struct GNUNET_CONTAINER_MultiPeerMap *map; 55 56 }; 57 58 59 struct GNUNET_CRYPTO_EccDlogContext * 60 GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max, 61 unsigned int mem) 62 { 63 struct GNUNET_CRYPTO_EccDlogContext *edc; 64 int K = ((max + (mem - 1)) / mem); 65 66 GNUNET_assert (max < INT32_MAX); 67 GNUNET_assert (mem <= UINT32_MAX / 2); 68 edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext); 69 edc->max = max; 70 edc->mem = mem; 71 edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2, 72 GNUNET_NO); 73 for (int i = -(int) mem; i <= (int) mem; i++) 74 { 75 struct GNUNET_CRYPTO_EccScalar Ki; 76 struct GNUNET_PeerIdentity key; 77 78 GNUNET_CRYPTO_ecc_scalar_from_int (K * i, 79 &Ki); 80 if (0 == i) /* libsodium does not like to multiply with zero */ 81 GNUNET_assert ( 82 0 == 83 crypto_core_ed25519_sub ((unsigned char *) &key, 84 (unsigned char *) &key, 85 (unsigned char *) &key)); 86 else 87 GNUNET_assert ( 88 0 == 89 crypto_scalarmult_ed25519_base_noclamp ((unsigned char*) &key, 90 Ki.v)); 91 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, 92 "K*i: %d (mem=%u, i=%d) => %s\n", 93 K * i, 94 mem, 95 i, 96 GNUNET_i2s (&key)); 97 GNUNET_assert (GNUNET_OK == 98 GNUNET_CONTAINER_multipeermap_put (edc->map, 99 &key, 100 (void *) (long) i + max, 101 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); 102 } 103 return edc; 104 } 105 106 107 int 108 GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc, 109 const struct GNUNET_CRYPTO_EccPoint *input) 110 { 111 unsigned int K = ((edc->max + (edc->mem - 1)) / edc->mem); 112 int res; 113 struct GNUNET_CRYPTO_EccPoint g; 114 struct GNUNET_CRYPTO_EccPoint q; 115 struct GNUNET_CRYPTO_EccPoint nq; 116 117 { 118 struct GNUNET_CRYPTO_EccScalar fact; 119 120 memset (&fact, 121 0, 122 sizeof (fact)); 123 sodium_increment (fact.v, 124 sizeof (fact.v)); 125 GNUNET_assert (0 == 126 crypto_scalarmult_ed25519_base_noclamp (g.v, 127 fact.v)); 128 } 129 /* make compiler happy: initialize q and nq, technically not needed! */ 130 memset (&q, 131 0, 132 sizeof (q)); 133 memset (&nq, 134 0, 135 sizeof (nq)); 136 res = INT_MAX; 137 for (unsigned int i = 0; i <= edc->max / edc->mem; i++) 138 { 139 struct GNUNET_PeerIdentity key; 140 void *retp; 141 142 GNUNET_assert (sizeof (key) == crypto_scalarmult_BYTES); 143 if (0 == i) 144 { 145 memcpy (&key, 146 input, 147 sizeof (key)); 148 } 149 else 150 { 151 memcpy (&key, 152 &q, 153 sizeof (key)); 154 } 155 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, 156 "Trying offset i=%u): %s\n", 157 i, 158 GNUNET_i2s (&key)); 159 retp = GNUNET_CONTAINER_multipeermap_get (edc->map, 160 &key); 161 if (NULL != retp) 162 { 163 res = (((long) retp) - edc->max) * K - i; 164 /* we continue the loop here to make the implementation 165 "constant-time". If we do not care about this, we could just 166 'break' here and do fewer operations... */ 167 } 168 if (i == edc->max / edc->mem) 169 break; 170 /* q = q + g */ 171 if (0 == i) 172 { 173 GNUNET_assert (0 == 174 crypto_core_ed25519_add (q.v, 175 input->v, 176 g.v)); 177 } 178 else 179 { 180 GNUNET_assert (0 == 181 crypto_core_ed25519_add (q.v, 182 q.v, 183 g.v)); 184 } 185 } 186 return res; 187 } 188 189 190 void 191 GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccScalar *r) 192 { 193 crypto_core_ed25519_scalar_random (r->v); 194 } 195 196 197 void 198 GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc) 199 { 200 GNUNET_CONTAINER_multipeermap_destroy (edc->map); 201 GNUNET_free (edc); 202 } 203 204 205 void 206 GNUNET_CRYPTO_ecc_dexp (int val, 207 struct GNUNET_CRYPTO_EccPoint *r) 208 { 209 struct GNUNET_CRYPTO_EccScalar fact; 210 211 GNUNET_CRYPTO_ecc_scalar_from_int (val, 212 &fact); 213 crypto_scalarmult_ed25519_base_noclamp (r->v, 214 fact.v); 215 } 216 217 218 enum GNUNET_GenericReturnValue 219 GNUNET_CRYPTO_ecc_dexp_mpi (const struct GNUNET_CRYPTO_EccScalar *val, 220 struct GNUNET_CRYPTO_EccPoint *r) 221 { 222 if (0 == 223 crypto_scalarmult_ed25519_base_noclamp (r->v, 224 val->v)) 225 return GNUNET_OK; 226 return GNUNET_SYSERR; 227 } 228 229 230 enum GNUNET_GenericReturnValue 231 GNUNET_CRYPTO_ecc_add (const struct GNUNET_CRYPTO_EccPoint *a, 232 const struct GNUNET_CRYPTO_EccPoint *b, 233 struct GNUNET_CRYPTO_EccPoint *r) 234 { 235 if (0 == 236 crypto_core_ed25519_add (r->v, 237 a->v, 238 b->v)) 239 return GNUNET_OK; 240 return GNUNET_SYSERR; 241 } 242 243 244 enum GNUNET_GenericReturnValue 245 GNUNET_CRYPTO_ecc_pmul_mpi (const struct GNUNET_CRYPTO_EccPoint *p, 246 const struct GNUNET_CRYPTO_EccScalar *val, 247 struct GNUNET_CRYPTO_EccPoint *r) 248 { 249 if (0 == 250 crypto_scalarmult_ed25519_noclamp (r->v, 251 val->v, 252 p->v)) 253 return GNUNET_OK; 254 return GNUNET_SYSERR; 255 } 256 257 258 enum GNUNET_GenericReturnValue 259 GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccPoint *r, 260 struct GNUNET_CRYPTO_EccPoint *r_inv) 261 { 262 struct GNUNET_CRYPTO_EccScalar s; 263 unsigned char inv_s[crypto_scalarmult_ed25519_SCALARBYTES]; 264 265 GNUNET_CRYPTO_ecc_random_mod_n (&s); 266 if (0 != 267 crypto_scalarmult_ed25519_base_noclamp (r->v, 268 s.v)) 269 return GNUNET_SYSERR; 270 crypto_core_ed25519_scalar_negate (inv_s, 271 s.v); 272 if (0 != 273 crypto_scalarmult_ed25519_base_noclamp (r_inv->v, 274 inv_s)) 275 return GNUNET_SYSERR; 276 return GNUNET_OK; 277 } 278 279 280 void 281 GNUNET_CRYPTO_ecc_rnd_mpi (struct GNUNET_CRYPTO_EccScalar *r, 282 struct GNUNET_CRYPTO_EccScalar *r_neg) 283 { 284 GNUNET_CRYPTO_ecc_random_mod_n (r); 285 crypto_core_ed25519_scalar_negate (r_neg->v, 286 r->v); 287 } 288 289 290 void 291 GNUNET_CRYPTO_ecc_scalar_from_int (int64_t val, 292 struct GNUNET_CRYPTO_EccScalar *r) 293 { 294 unsigned char fact[crypto_scalarmult_ed25519_SCALARBYTES]; 295 uint64_t valBe; 296 297 GNUNET_assert (sizeof (*r) == sizeof (fact)); 298 if (val < 0) 299 { 300 if (INT64_MIN == val) 301 valBe = GNUNET_htonll ((uint64_t) INT64_MAX); 302 else 303 valBe = GNUNET_htonll ((uint64_t) (-val)); 304 } 305 else 306 { 307 valBe = GNUNET_htonll ((uint64_t) val); 308 } 309 memset (fact, 310 0, 311 sizeof (fact)); 312 for (unsigned int i = 0; i < sizeof (val); i++) 313 fact[i] = ((unsigned char*) &valBe)[sizeof (val) - 1 - i]; 314 if (val < 0) 315 { 316 if (INT64_MIN == val) 317 /* See above: fact is one too small, increment now that we can */ 318 sodium_increment (fact, 319 sizeof (fact)); 320 crypto_core_ed25519_scalar_negate (r->v, 321 fact); 322 } 323 else 324 { 325 memcpy (r, 326 fact, 327 sizeof (fact)); 328 } 329 } 330 331 332 /* end of crypto_ecc_dlog.c */