diff options
author | Christian Grothoff <christian@grothoff.org> | 2015-07-02 19:58:35 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2015-07-02 19:58:35 +0000 |
commit | fece22eebf8c8d54e79d05f748019e7234823828 (patch) | |
tree | f875095ec8a2918a263f273a71b721654cfba612 /src/util/crypto_ecc_dlog.c | |
parent | ed53a24f07a861edf7edd327c04fc7a23111e3c4 (diff) | |
download | gnunet-fece22eebf8c8d54e79d05f748019e7234823828.tar.gz gnunet-fece22eebf8c8d54e79d05f748019e7234823828.zip |
-adding ecc dlog support
Diffstat (limited to 'src/util/crypto_ecc_dlog.c')
-rw-r--r-- | src/util/crypto_ecc_dlog.c | 196 |
1 files changed, 196 insertions, 0 deletions
diff --git a/src/util/crypto_ecc_dlog.c b/src/util/crypto_ecc_dlog.c new file mode 100644 index 000000000..34f3c203d --- /dev/null +++ b/src/util/crypto_ecc_dlog.c | |||
@@ -0,0 +1,196 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | Copyright (C) 2012, 2013, 2015 Christian Grothoff (and other contributing authors) | ||
4 | |||
5 | GNUnet is free software; you can redistribute it and/or modify | ||
6 | it under the terms of the GNU General Public License as published | ||
7 | by the Free Software Foundation; either version 3, or (at your | ||
8 | 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 | General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU General Public License | ||
16 | along with GNUnet; see the file COPYING. If not, write to the | ||
17 | Free Software Foundation, Inc., 59 Temple Place - Suite 330, | ||
18 | Boston, MA 02111-1307, USA. | ||
19 | */ | ||
20 | |||
21 | /** | ||
22 | * @file util/crypto_ecc_dlog.c | ||
23 | * @brief ECC discreate logarithm for small values | ||
24 | * @author Christian Grothoff | ||
25 | * | ||
26 | * TODO: | ||
27 | * - support negative factors | ||
28 | */ | ||
29 | #include "platform.h" | ||
30 | #include <gcrypt.h> | ||
31 | #include "gnunet_crypto_lib.h" | ||
32 | #include "gnunet_container_lib.h" | ||
33 | |||
34 | |||
35 | /** | ||
36 | * Name of the curve we are using. Note that we have hard-coded | ||
37 | * structs that use 256 bits, so using a bigger curve will require | ||
38 | * changes that break stuff badly. The name of the curve given here | ||
39 | * must be agreed by all peers and be supported by libgcrypt. | ||
40 | */ | ||
41 | #define CURVE "Ed25519" | ||
42 | |||
43 | |||
44 | /** | ||
45 | * | ||
46 | */ | ||
47 | static void | ||
48 | extract_pk (gcry_mpi_point_t pt, | ||
49 | gcry_ctx_t ctx, | ||
50 | struct GNUNET_PeerIdentity *pid) | ||
51 | { | ||
52 | gcry_mpi_t q_y; | ||
53 | |||
54 | GNUNET_assert (0 == gcry_mpi_ec_set_point ("q", pt, ctx)); | ||
55 | q_y = gcry_mpi_ec_get_mpi ("q@eddsa", ctx, 0); | ||
56 | GNUNET_assert (q_y); | ||
57 | GNUNET_CRYPTO_mpi_print_unsigned (pid->public_key.q_y, | ||
58 | sizeof (pid->public_key.q_y), | ||
59 | q_y); | ||
60 | gcry_mpi_release (q_y); | ||
61 | } | ||
62 | |||
63 | |||
64 | /** | ||
65 | * Internal structure used to cache pre-calculated values for DLOG calculation. | ||
66 | */ | ||
67 | struct GNUNET_CRYPTO_EccDlogContext | ||
68 | { | ||
69 | unsigned int max; | ||
70 | unsigned int mem; | ||
71 | struct GNUNET_CONTAINER_MultiPeerMap *map; | ||
72 | gcry_ctx_t ctx; | ||
73 | |||
74 | }; | ||
75 | |||
76 | |||
77 | /** | ||
78 | * Do pre-calculation for ECC discrete logarithm for small factors. | ||
79 | * | ||
80 | * @param max maximum value the factor can be | ||
81 | * @param mem memory to use (should be smaller than @a max), must not be zero. | ||
82 | * @return @a max if dlog failed, otherwise the factor | ||
83 | */ | ||
84 | struct GNUNET_CRYPTO_EccDlogContext * | ||
85 | GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max, | ||
86 | unsigned int mem) | ||
87 | { | ||
88 | struct GNUNET_CRYPTO_EccDlogContext *edc; | ||
89 | unsigned int K = ((max + (mem-1)) / mem); | ||
90 | gcry_mpi_point_t g; | ||
91 | struct GNUNET_PeerIdentity key; | ||
92 | gcry_mpi_point_t gKi; | ||
93 | gcry_mpi_t fact; | ||
94 | unsigned int i; | ||
95 | |||
96 | edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext); | ||
97 | edc->max = max; | ||
98 | edc->mem = mem; | ||
99 | |||
100 | edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2, | ||
101 | GNUNET_NO); | ||
102 | |||
103 | GNUNET_assert (0 == gcry_mpi_ec_new (&edc->ctx, | ||
104 | NULL, | ||
105 | CURVE)); | ||
106 | g = gcry_mpi_ec_get_point ("g", edc->ctx, 0); | ||
107 | GNUNET_assert (NULL != g); | ||
108 | fact = gcry_mpi_new (0); | ||
109 | gKi = gcry_mpi_point_new (0); | ||
110 | for (i=0;i<=mem;i++) | ||
111 | { | ||
112 | gcry_mpi_set_ui (fact, i * K); | ||
113 | gcry_mpi_ec_mul (gKi, fact, g, edc->ctx); | ||
114 | extract_pk (gKi, edc->ctx, &key); | ||
115 | GNUNET_assert (GNUNET_OK == | ||
116 | GNUNET_CONTAINER_multipeermap_put (edc->map, | ||
117 | &key, | ||
118 | (void*) (long) i + 1, | ||
119 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | ||
120 | } | ||
121 | gcry_mpi_release (fact); | ||
122 | gcry_mpi_point_release (gKi); | ||
123 | gcry_mpi_point_release (g); | ||
124 | return edc; | ||
125 | } | ||
126 | |||
127 | |||
128 | /** | ||
129 | * Calculate ECC discrete logarithm for small factors. | ||
130 | * | ||
131 | * @param edc precalculated values, determine range of factors | ||
132 | * @param input point on the curve to factor | ||
133 | * @return `edc->max` if dlog failed, otherwise the factor | ||
134 | */ | ||
135 | unsigned int | ||
136 | GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc, | ||
137 | gcry_mpi_point_t input) | ||
138 | { | ||
139 | unsigned int K = ((edc->max + (edc->mem-1)) / edc->mem); | ||
140 | gcry_mpi_point_t g; | ||
141 | struct GNUNET_PeerIdentity key; | ||
142 | gcry_mpi_point_t q; | ||
143 | unsigned int i; | ||
144 | unsigned int res; | ||
145 | void *retp; | ||
146 | |||
147 | g = gcry_mpi_ec_get_point ("g", edc->ctx, 0); | ||
148 | GNUNET_assert (NULL != g); | ||
149 | q = gcry_mpi_point_new (0); | ||
150 | |||
151 | res = edc->max; | ||
152 | for (i=0;i<=edc->max/edc->mem;i++) | ||
153 | { | ||
154 | if (0 == i) | ||
155 | extract_pk (input, edc->ctx, &key); | ||
156 | else | ||
157 | extract_pk (q, edc->ctx, &key); | ||
158 | retp = GNUNET_CONTAINER_multipeermap_get (edc->map, | ||
159 | &key); | ||
160 | if (NULL != retp) | ||
161 | { | ||
162 | res = (((long) retp) - 1) * K - i; | ||
163 | fprintf (stderr, | ||
164 | "Got DLOG %u\n", | ||
165 | res); | ||
166 | } | ||
167 | if (i == edc->max/edc->mem) | ||
168 | break; | ||
169 | /* q = q + g */ | ||
170 | if (0 == i) | ||
171 | gcry_mpi_ec_add (q, input, g, edc->ctx); | ||
172 | else | ||
173 | gcry_mpi_ec_add (q, q, g, edc->ctx); | ||
174 | } | ||
175 | gcry_mpi_point_release (g); | ||
176 | gcry_mpi_point_release (q); | ||
177 | |||
178 | return res; | ||
179 | } | ||
180 | |||
181 | |||
182 | /** | ||
183 | * Release precalculated values. | ||
184 | * | ||
185 | * @param edc dlog context | ||
186 | */ | ||
187 | void | ||
188 | GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc) | ||
189 | { | ||
190 | gcry_ctx_release (edc->ctx); | ||
191 | GNUNET_CONTAINER_multipeermap_destroy (edc->map); | ||
192 | GNUNET_free (edc); | ||
193 | } | ||
194 | |||
195 | /* end of crypto_ecc_dlog.c */ | ||
196 | |||