dh.c 5.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233
  1. /* -*- mode:c; c-file-style:"k&r"; c-basic-offset: 4; tab-width:4; indent-tabs-mode:nil; mode:auto-fill; fill-column:78; -*- */
  2. /* vim: set ts=4 sw=4 et tw=78 fo=cqt wm=0: */
  3. /* dh.c
  4. *
  5. * Copyright (C) 2006-2014 wolfSSL Inc.
  6. *
  7. * This file is part of CyaSSL.
  8. *
  9. * CyaSSL is free software; you can redistribute it and/or modify
  10. * it under the terms of the GNU General Public License as published by
  11. * the Free Software Foundation; either version 2 of the License, or
  12. * (at your option) any later version.
  13. *
  14. * CyaSSL is distributed in the hope that it will be useful,
  15. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  17. * GNU General Public License for more details.
  18. *
  19. * You should have received a copy of the GNU General Public License
  20. * along with this program; if not, write to the Free Software
  21. * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  22. */
  23. #include <stddef.h>
  24. #include <stdint.h>
  25. #include "integer.h"
  26. #include "dh.h"
  27. #include "error-crypt.h"
  28. /*
  29. * source
  30. * http://fastapprox.googlecode.com/svn/trunk/fastapprox/src/fastonebigheader.h
  31. */
  32. static inline float
  33. fastlog2 (float x)
  34. {
  35. union { float f; uint32_t i; } vx = { x };
  36. union { uint32_t i; float f; } mx = { (vx.i & 0x007FFFFF) | 0x3f000000 };
  37. float y = vx.i;
  38. y *= 1.1920928955078125e-7f;
  39. return y - 124.22551499f
  40. - 1.498030302f *mx.f
  41. - 1.72587999f / (0.3520887068f + mx.f);
  42. }
  43. static inline float
  44. fastlog (float x)
  45. {
  46. return 0.69314718f *fastlog2 (x);
  47. }
  48. static inline float
  49. fastpow2 (float p)
  50. {
  51. float offset = (p < 0) ? 1.0f : 0.0f;
  52. float clipp = (p < -126) ? -126.0f : p;
  53. int w = clipp;
  54. float z = clipp - w + offset;
  55. union { uint32_t i; float f; } v = { (uint32_t) ( (1 << 23) *(clipp + 121.2740575f + 27.7280233f / (4.84252568f - z) - 1.49012907f *z) ) };
  56. return v.f;
  57. }
  58. static inline float
  59. fastpow (float x,
  60. float p)
  61. {
  62. return fastpow2 (p *fastlog2 (x));
  63. }
  64. #define XPOW(x,y) fastpow((x),(y))
  65. #define XLOG(x) fastlog((x))
  66. #ifndef min
  67. static inline word32 min(word32 a, word32 b)
  68. {
  69. return a > b ? b : a;
  70. }
  71. #endif /* min */
  72. void InitDhKey(DhKey *key)
  73. {
  74. (void)key;
  75. key->p.dp = 0;
  76. key->g.dp = 0;
  77. }
  78. void FreeDhKey(DhKey *key)
  79. {
  80. (void)key;
  81. mp_clear(&key->p);
  82. mp_clear(&key->g);
  83. }
  84. static word32 DiscreteLogWorkFactor(word32 n)
  85. {
  86. /* assuming discrete log takes about the same time as factoring */
  87. if (n<5)
  88. return 0;
  89. else
  90. return (word32)(2.4 *XPOW((double)n, 1.0/3.0) *
  91. XPOW(XLOG((double)n), 2.0/3.0) - 5);
  92. }
  93. int _DkRandomBitsRead (void *buffer, int size);
  94. static int GeneratePrivate(DhKey *key, byte *priv, word32 *privSz)
  95. {
  96. int ret;
  97. word32 sz = mp_unsigned_bin_size(&key->p);
  98. sz = min(sz, 2 * DiscreteLogWorkFactor(sz * BIT_SIZE) / BIT_SIZE + 1);
  99. ret = _DkRandomBitsRead(priv, sz);
  100. if (ret < 0)
  101. return ret;
  102. priv[0] |= 0x0C;
  103. *privSz = sz;
  104. return 0;
  105. }
  106. static int GeneratePublic(DhKey *key, const byte *priv, word32 privSz,
  107. byte *pub, word32 *pubSz)
  108. {
  109. int ret = 0;
  110. mp_int x;
  111. mp_int y;
  112. if (mp_init_multi(&x, &y, 0, 0, 0, 0) != MP_OKAY)
  113. return MP_INIT_E;
  114. if (mp_read_unsigned_bin(&x, priv, privSz) != MP_OKAY)
  115. ret = MP_READ_E;
  116. if (ret == 0 && mp_exptmod(&key->g, &x, &key->p, &y) != MP_OKAY)
  117. ret = MP_EXPTMOD_E;
  118. if (ret == 0 && mp_to_unsigned_bin(&y, pub) != MP_OKAY)
  119. ret = MP_TO_E;
  120. if (ret == 0)
  121. *pubSz = mp_unsigned_bin_size(&y);
  122. mp_clear(&y);
  123. mp_clear(&x);
  124. return ret;
  125. }
  126. int DhGenerateKeyPair(DhKey *key, byte *priv, word32 *privSz,
  127. byte *pub, word32 *pubSz)
  128. {
  129. int ret = GeneratePrivate(key, priv, privSz);
  130. return (ret != 0) ? ret : GeneratePublic(key, priv, *privSz, pub, pubSz);
  131. }
  132. int DhAgree(DhKey *key, byte *agree, word32 *agreeSz, const byte *priv,
  133. word32 privSz, const byte *otherPub, word32 pubSz)
  134. {
  135. int ret = 0;
  136. mp_int x;
  137. mp_int y;
  138. mp_int z;
  139. if (mp_init_multi(&x, &y, &z, 0, 0, 0) != MP_OKAY)
  140. return MP_INIT_E;
  141. if (mp_read_unsigned_bin(&x, priv, privSz) != MP_OKAY)
  142. ret = MP_READ_E;
  143. if (ret == 0 && mp_read_unsigned_bin(&y, otherPub, pubSz) != MP_OKAY)
  144. ret = MP_READ_E;
  145. if (ret == 0 && mp_exptmod(&y, &x, &key->p, &z) != MP_OKAY)
  146. ret = MP_EXPTMOD_E;
  147. if (ret == 0 && mp_to_unsigned_bin(&z, agree) != MP_OKAY)
  148. ret = MP_TO_E;
  149. if (ret == 0)
  150. *agreeSz = mp_unsigned_bin_size(&z);
  151. mp_clear(&z);
  152. mp_clear(&y);
  153. mp_clear(&x);
  154. return ret;
  155. }
  156. int DhSetKey(DhKey* key, const byte* p, word32 pSz, const byte* g, word32 gSz)
  157. {
  158. if (key == NULL || p == NULL || g == NULL || pSz == 0 || gSz == 0)
  159. return BAD_FUNC_ARG;
  160. /* may have leading 0 */
  161. if (p[0] == 0) {
  162. pSz--; p++;
  163. }
  164. if (g[0] == 0) {
  165. gSz--; g++;
  166. }
  167. if (mp_init(&key->p) != MP_OKAY)
  168. return MP_INIT_E;
  169. if (mp_read_unsigned_bin(&key->p, p, pSz) != 0) {
  170. mp_clear(&key->p);
  171. return ASN_DH_KEY_E;
  172. }
  173. if (mp_init(&key->g) != MP_OKAY) {
  174. mp_clear(&key->p);
  175. return MP_INIT_E;
  176. }
  177. if (mp_read_unsigned_bin(&key->g, g, gSz) != 0) {
  178. mp_clear(&key->g);
  179. mp_clear(&key->p);
  180. return ASN_DH_KEY_E;
  181. }
  182. return 0;
  183. }