modexp.c 6.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236
  1. /* ===================================================================
  2. *
  3. * Copyright (c) 2018, Helder Eijs <helderijs@gmail.com>
  4. * All rights reserved.
  5. *
  6. * Redistribution and use in source and binary forms, with or without
  7. * modification, are permitted provided that the following conditions
  8. * are met:
  9. *
  10. * 1. Redistributions of source code must retain the above copyright
  11. * notice, this list of conditions and the following disclaimer.
  12. * 2. Redistributions in binary form must reproduce the above copyright
  13. * notice, this list of conditions and the following disclaimer in
  14. * the documentation and/or other materials provided with the
  15. * distribution.
  16. *
  17. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18. * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19. * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  20. * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  21. * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  22. * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  23. * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  24. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  25. * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  26. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  27. * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28. * POSSIBILITY OF SUCH DAMAGE.
  29. * ===================================================================
  30. */
  31. #include <stddef.h>
  32. #include <string.h>
  33. #include <assert.h>
  34. #include <stdio.h>
  35. #include <stdlib.h>
  36. #include "common.h"
  37. #include "endianess.h"
  38. FAKE_INIT(modexp)
  39. #include "mont.h"
  40. #include "modexp_utils.h"
  41. /** Multiplication will be replaced by a look-up **/
  42. /** Do not change this value! **/
  43. #define WINDOW_SIZE 4
  44. /*
  45. * Modular exponentiation. All numbers are
  46. * encoded in big endian form, possibly with
  47. * zero padding on the left.
  48. *
  49. * @param out The memory area where to store the result
  50. * @param base Base number, strictly smaller than the modulus
  51. * @param exp Exponent
  52. * @param modulus Modulus, it must be odd
  53. * @param len Size in bytes of out, base, exp, and modulus
  54. * @param seed A random seed, used for avoiding side-channel
  55. * attacks
  56. * @return 0 in case of success, the appropriate error code otherwise
  57. */
  58. EXPORT_SYM int monty_pow(
  59. uint8_t *out,
  60. const uint8_t *base,
  61. const uint8_t *exp,
  62. const uint8_t *modulus,
  63. size_t len,
  64. uint64_t seed)
  65. {
  66. unsigned i, j;
  67. size_t exp_len;
  68. int res;
  69. MontContext *ctx = NULL;
  70. uint64_t *powers[1 << WINDOW_SIZE] = { NULL };
  71. uint64_t *power_idx = NULL;
  72. ProtMemory *prot = NULL;
  73. uint64_t *mont_base = NULL;
  74. uint64_t *x = NULL;
  75. uint64_t *scratchpad = NULL;
  76. uint8_t *buf_out = NULL;
  77. struct BitWindow_LR bit_window;
  78. if (!base || !exp || !modulus || !out)
  79. return ERR_NULL;
  80. if (len == 0)
  81. return ERR_NOT_ENOUGH_DATA;
  82. /* Allocations **/
  83. res = mont_context_init(&ctx, modulus, len);
  84. if (res)
  85. return res;
  86. for (i=0; i<(1 << WINDOW_SIZE); i++) {
  87. res = mont_number(powers+i, 1, ctx);
  88. if (res) goto cleanup;
  89. }
  90. res = mont_number(&power_idx, 1, ctx);
  91. if (res) goto cleanup;
  92. res = mont_from_bytes(&mont_base, base, len, ctx);
  93. if (res) goto cleanup;
  94. res = mont_number(&x, 1, ctx);
  95. if (res) goto cleanup;
  96. res = mont_number(&scratchpad, SCRATCHPAD_NR, ctx);
  97. if (res) goto cleanup;
  98. buf_out = (uint8_t*)calloc(1, mont_bytes(ctx));
  99. if (NULL == buf_out) {
  100. res = ERR_MEMORY;
  101. goto cleanup;
  102. }
  103. /** Result is initially 1 in Montgomery form **/
  104. mont_set(x, 1, ctx);
  105. /** Pre-compute powers a^0 mod n, a^1 mod n, a^2 mod n, ... a^(2^WINDOW_SIZE-1) mod n **/
  106. mont_copy(powers[0], x, ctx);
  107. mont_copy(powers[1], mont_base, ctx);
  108. for (i=1; i<(1 << (WINDOW_SIZE-1)); i++) {
  109. mont_mult(powers[i*2], powers[i], powers[i], scratchpad, ctx);
  110. mont_mult(powers[i*2+1], powers[i*2], mont_base, scratchpad, ctx);
  111. }
  112. res = scatter(&prot, (const void**)powers, 1<<WINDOW_SIZE, mont_bytes(ctx), seed);
  113. if (res) goto cleanup;
  114. /** Ignore leading zero bytes in the exponent **/
  115. exp_len = len;
  116. for (i=0; i<len && *exp==0; i++) {
  117. exp_len--;
  118. exp++;
  119. }
  120. /* If exponent is 0, the result is always 1 */
  121. if (exp_len == 0) {
  122. memset(out, 0, len);
  123. out[len-1] = 1;
  124. res = 0;
  125. goto cleanup;
  126. }
  127. bit_window = init_bit_window_lr(WINDOW_SIZE, exp, exp_len);
  128. /** Left-to-right exponentiation with fixed window **/
  129. for (i=0; i < bit_window.nr_windows; i++) {
  130. unsigned index;
  131. for (j=0; j<WINDOW_SIZE; j++) {
  132. mont_mult(x, x, x, scratchpad, ctx);
  133. }
  134. index = get_next_digit_lr(&bit_window);
  135. gather(power_idx, prot, index);
  136. mont_mult(x, x, power_idx, scratchpad, ctx);
  137. }
  138. /** Transform result back into big-endian, byte form **/
  139. res = mont_to_bytes(out, len, x, ctx);
  140. cleanup:
  141. mont_context_free(ctx);
  142. for (i=0; i<(1 << WINDOW_SIZE); i++) {
  143. free(powers[i]);
  144. }
  145. free(power_idx);
  146. free_scattered(prot);
  147. free(mont_base);
  148. free(x);
  149. free(scratchpad);
  150. free(buf_out);
  151. return res;
  152. }
  153. #ifdef MAIN
  154. int main(void)
  155. {
  156. uint16_t length;
  157. uint8_t *base, *modulus, *exponent, *out;
  158. int result;
  159. size_t res;
  160. res = fread(&length, 2, 1, stdin);
  161. assert(res == 2);
  162. base = malloc(length);
  163. modulus = malloc(length);
  164. exponent = malloc(length);
  165. out = malloc(length);
  166. res = fread(base, 1, length, stdin);
  167. assert(res == length);
  168. res = fread(modulus, 1, length, stdin);
  169. assert(res == length);
  170. res = fread(exponent, 1, length, stdin);
  171. assert(res == length);
  172. assert(res == length);
  173. res = fread(out, 1, length, stdin);
  174. result = monty_pow(out, base, exponent, modulus, length, 12);
  175. free(base);
  176. free(modulus);
  177. free(exponent);
  178. free(out);
  179. return result;
  180. }
  181. #endif
  182. #ifdef PROFILE
  183. int main(void)
  184. {
  185. uint8_t base[256], exponent[256], modulus[256], out[256];
  186. unsigned length = 256, i, j;
  187. for (i=0; i<256; i++) {
  188. base[i] = (uint8_t)i | 0x80 | 1;
  189. exponent[i] = base[i] = modulus[i] = base[i];
  190. }
  191. base[0] = 0x7F;
  192. for (j=0; j<50; j++) {
  193. monty_pow(out, base, exponent, modulus, length, 12);
  194. }
  195. }
  196. #endif