diff options
Diffstat (limited to 'src/util')
-rw-r--r-- | src/util/Makefile.am | 8 | ||||
-rw-r--r-- | src/util/crypto_ecc_dlog.c | 196 | ||||
-rw-r--r-- | src/util/test_crypto_ecc_dlog.c | 116 |
3 files changed, 320 insertions, 0 deletions
diff --git a/src/util/Makefile.am b/src/util/Makefile.am index 916a588fa..13a16448b 100644 --- a/src/util/Makefile.am +++ b/src/util/Makefile.am | |||
@@ -76,6 +76,7 @@ libgnunetutil_la_SOURCES = \ | |||
76 | crypto_symmetric.c \ | 76 | crypto_symmetric.c \ |
77 | crypto_crc.c \ | 77 | crypto_crc.c \ |
78 | crypto_ecc.c \ | 78 | crypto_ecc.c \ |
79 | crypto_ecc_dlog.c \ | ||
79 | crypto_ecc_setup.c \ | 80 | crypto_ecc_setup.c \ |
80 | crypto_hash.c \ | 81 | crypto_hash.c \ |
81 | crypto_hash_file.c \ | 82 | crypto_hash_file.c \ |
@@ -271,6 +272,7 @@ check_PROGRAMS = \ | |||
271 | test_crypto_eddsa \ | 272 | test_crypto_eddsa \ |
272 | test_crypto_ecdhe \ | 273 | test_crypto_ecdhe \ |
273 | test_crypto_ecdh_eddsa \ | 274 | test_crypto_ecdh_eddsa \ |
275 | test_crypto_ecc_dlog \ | ||
274 | test_crypto_hash \ | 276 | test_crypto_hash \ |
275 | test_crypto_hash_context \ | 277 | test_crypto_hash_context \ |
276 | test_crypto_hkdf \ | 278 | test_crypto_hkdf \ |
@@ -421,6 +423,12 @@ test_crypto_eddsa_LDADD = \ | |||
421 | libgnunetutil.la \ | 423 | libgnunetutil.la \ |
422 | $(LIBGCRYPT_LIBS) | 424 | $(LIBGCRYPT_LIBS) |
423 | 425 | ||
426 | test_crypto_ecc_dlog_SOURCES = \ | ||
427 | test_crypto_ecc_dlog.c | ||
428 | test_crypto_ecc_dlog_LDADD = \ | ||
429 | libgnunetutil.la \ | ||
430 | $(LIBGCRYPT_LIBS) | ||
431 | |||
424 | test_crypto_ecdhe_SOURCES = \ | 432 | test_crypto_ecdhe_SOURCES = \ |
425 | test_crypto_ecdhe.c | 433 | test_crypto_ecdhe.c |
426 | test_crypto_ecdhe_LDADD = \ | 434 | test_crypto_ecdhe_LDADD = \ |
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 | |||
diff --git a/src/util/test_crypto_ecc_dlog.c b/src/util/test_crypto_ecc_dlog.c new file mode 100644 index 000000000..a594e5795 --- /dev/null +++ b/src/util/test_crypto_ecc_dlog.c | |||
@@ -0,0 +1,116 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | Copyright (C) 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/test_crypto_ecc_dlog.c | ||
23 | * @brief testcase for ECC DLOG calculation | ||
24 | * @author Christian Grothoff | ||
25 | * | ||
26 | * TODO: | ||
27 | * - test negative numbers | ||
28 | */ | ||
29 | #include "platform.h" | ||
30 | #include "gnunet_util_lib.h" | ||
31 | #include <gcrypt.h> | ||
32 | |||
33 | |||
34 | /** | ||
35 | * Name of the curve we are using. Note that we have hard-coded | ||
36 | * structs that use 256 bits, so using a bigger curve will require | ||
37 | * changes that break stuff badly. The name of the curve given here | ||
38 | * must be agreed by all peers and be supported by libgcrypt. | ||
39 | */ | ||
40 | #define CURVE "Ed25519" | ||
41 | |||
42 | /** | ||
43 | * Maximum value we test dlog for. | ||
44 | */ | ||
45 | #define MAX_FACT 1000000 | ||
46 | |||
47 | /** | ||
48 | * Maximum memory to use, sqrt(MAX_FACT) is a good choice. | ||
49 | */ | ||
50 | #define MAX_MEM 1000 | ||
51 | |||
52 | |||
53 | static void | ||
54 | test_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc) | ||
55 | { | ||
56 | gcry_mpi_t fact; | ||
57 | gcry_ctx_t ctx; | ||
58 | gcry_mpi_point_t q; | ||
59 | gcry_mpi_point_t g; | ||
60 | unsigned int i; | ||
61 | unsigned int x; | ||
62 | |||
63 | GNUNET_assert (0 == gcry_mpi_ec_new (&ctx, NULL, CURVE)); | ||
64 | g = gcry_mpi_ec_get_point ("g", ctx, 0); | ||
65 | GNUNET_assert (NULL != g); | ||
66 | q = gcry_mpi_point_new (0); | ||
67 | fact = gcry_mpi_new (0); | ||
68 | for (i=0;i<10;i++) | ||
69 | { | ||
70 | x = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, | ||
71 | MAX_FACT); | ||
72 | gcry_mpi_set_ui (fact, x); | ||
73 | gcry_mpi_ec_mul (q, fact, g, ctx); | ||
74 | if (x != | ||
75 | GNUNET_CRYPTO_ecc_dlog (edc, | ||
76 | q)) | ||
77 | { | ||
78 | fprintf (stderr, | ||
79 | "DLOG failed for value %u\n", | ||
80 | x); | ||
81 | GNUNET_assert (0); | ||
82 | } | ||
83 | } | ||
84 | gcry_mpi_release (fact); | ||
85 | gcry_mpi_point_release (g); | ||
86 | gcry_mpi_point_release (q); | ||
87 | gcry_ctx_release (ctx); | ||
88 | } | ||
89 | |||
90 | |||
91 | int | ||
92 | main (int argc, char *argv[]) | ||
93 | { | ||
94 | struct GNUNET_CRYPTO_EccDlogContext *edc; | ||
95 | |||
96 | if (! gcry_check_version ("1.6.0")) | ||
97 | { | ||
98 | FPRINTF (stderr, | ||
99 | _ | ||
100 | ("libgcrypt has not the expected version (version %s is required).\n"), | ||
101 | "1.6.0"); | ||
102 | return 0; | ||
103 | } | ||
104 | if (getenv ("GNUNET_GCRYPT_DEBUG")) | ||
105 | gcry_control (GCRYCTL_SET_DEBUG_FLAGS, 1u , 0); | ||
106 | GNUNET_log_setup ("test-crypto-ecc-dlog", | ||
107 | "WARNING", | ||
108 | NULL); | ||
109 | edc = GNUNET_CRYPTO_ecc_dlog_prepare (MAX_FACT, | ||
110 | MAX_MEM); | ||
111 | test_dlog (edc); | ||
112 | GNUNET_CRYPTO_ecc_dlog_release (edc); | ||
113 | return 0; | ||
114 | } | ||
115 | |||
116 | /* end of test_crypto_ecc_dlog.c */ | ||