-/*\r
- *\r
- * bn_modfs.c\r
- *\r
- * Some Modular Arithmetic Functions.\r
- *\r
- * Copyright (C) Lenka Fibikova 2000\r
- *\r
- *\r
- */\r
-\r
-\r
-#include <stdio.h>\r
-#include <stdlib.h>\r
-#include <assert.h>\r
-\r
-#include "bn_modfs.h"\r
-\r
-#define MAX_ROUNDS 10\r
-\r
-int BN_smod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx)\r
-{\r
- int r_sign;\r
-\r
- assert(rem != NULL && m != NULL && d != NULL && ctx != NULL);\r
-\r
- if (d->neg) return 0;\r
- r_sign = m->neg;\r
-\r
- if (r_sign) m->neg = 0;\r
- if (!(BN_div(NULL,rem,m,d,ctx))) return 0;\r
- if (r_sign) \r
- {\r
- m->neg = r_sign;\r
- if (!BN_is_zero(rem))\r
- {\r
- rem->neg = r_sign;\r
- BN_add(rem, rem, d);\r
- }\r
- }\r
- return 1;\r
-}\r
-\r
-int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx) \r
-{\r
- assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL);\r
-\r
- if (!BN_sub(r, a, b)) return 0;\r
- return BN_smod(r, r, m, ctx);\r
-\r
-}\r
-\r
-int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx) \r
-{\r
- assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL);\r
-\r
- if (!BN_add(r, a, b)) return 0;\r
- return BN_smod(r, r, m, ctx);\r
-\r
-}\r
-\r
-int BN_mod_sqr(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)\r
-{\r
- assert(r != NULL && a != NULL && p != NULL && ctx != NULL);\r
-\r
- if (!BN_sqr(r, a, ctx)) return 0;\r
- return BN_div(NULL, r, r, p, ctx);\r
-}\r
-\r
-int BN_swap(BIGNUM *x, BIGNUM *y)\r
-{\r
- BIGNUM *c;\r
-\r
- assert(x != NULL && y != NULL);\r
-\r
- if ((c = BN_dup(x)) == NULL) goto err;\r
- if ((BN_copy(x, y)) == NULL) goto err;\r
- if ((BN_copy(y, c)) == NULL) goto err;\r
- BN_clear_free(c);\r
- return 1;\r
-\r
-err:\r
- if (c != NULL) BN_clear_free(c);\r
- return 0;\r
-}\r
-\r
-\r
-int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx) \r
-{\r
- BIGNUM *x, *y, *y2;\r
- BN_ULONG m;\r
- int L;\r
-\r
- assert(a != NULL && p != NULL && ctx != NULL);\r
-\r
- x = ctx->bn[ctx->tos]; \r
- y = ctx->bn[ctx->tos + 1]; \r
- y2 = ctx->bn[ctx->tos + 2]; \r
-\r
- ctx->tos += 3;\r
-\r
- if (!BN_smod(x, a, p, ctx)) goto err;\r
- if (BN_is_zero(x)) \r
- {\r
-\r
- ctx->tos -= 3;\r
- return 0;\r
- }\r
-\r
- if (BN_copy(y, p) == NULL) goto err;\r
- L = 1;\r
-\r
- while (1)\r
- {\r
- if (!BN_rshift1(y2, y)) goto err;\r
- if (BN_cmp(x, y2) > 0)\r
- {\r
- if (!BN_sub(x, y, x)) goto err;\r
- if (BN_mod_word(y, 4) == 3)\r
- L = -L; \r
- }\r
- while (BN_mod_word(x, 4) == 0)\r
- BN_div_word(x, 4);\r
- if (BN_mod_word(x, 2) == 0)\r
- {\r
- BN_div_word(x, 2);\r
- m = BN_mod_word(y, 8);\r
- if (m == 3 || m == 5) L = -L; \r
- }\r
- if (BN_is_one(x)) \r
- {\r
- ctx->tos -= 3;\r
- return L;\r
- }\r
- \r
- if (BN_mod_word(x, 4) == 3 && BN_mod_word(y, 4) == 3) L = -L;\r
- if (!BN_swap(x, y)) goto err;\r
-\r
- if (!BN_smod(x, x, y, ctx)) goto err;\r
-\r
- }\r
-\r
-\r
-err:\r
- ctx->tos -= 3;\r
- return -2;\r
-\r
-}\r
-\r
-int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) \r
-/* x^2 = a (mod p) */\r
-{\r
- int ret;\r
- BIGNUM *n0, *n1, *r, *b, *m;\r
- int max;\r
-\r
- assert(x != NULL && a != NULL && p != NULL && ctx != NULL);\r
- assert(BN_cmp(a, p) < 0);\r
-\r
- ret = BN_legendre(a, p, ctx);\r
- if (ret < 0 || ret > 1) return 0;\r
- if (ret == 0)\r
- {\r
- if (!BN_zero(x)) return 0;\r
- return 1;\r
- }\r
-\r
- n0 = ctx->bn[ctx->tos]; \r
- n1 = ctx->bn[ctx->tos + 1]; \r
- ctx->tos += 2;\r
-\r
- if ((r = BN_new()) == NULL) goto err;\r
- if ((b = BN_new()) == NULL) goto err;\r
- if ((m = BN_new()) == NULL) goto err;\r
-\r
-\r
- if (!BN_zero(n0)) goto err;\r
- if (!BN_zero(n1)) goto err;\r
- if (!BN_zero(r)) goto err;\r
- if (!BN_zero(b)) goto err;\r
- if (!BN_zero(m)) goto err;\r
-\r
- max = 0;\r
-\r
- do{\r
- if (max++ > MAX_ROUNDS) goto err; /* if p is not prime could never stop*/\r
- if (!BN_add_word(m, 1)) goto err;\r
- ret = BN_legendre(m, p, ctx);\r
- if (ret < -1 || ret > 1) goto err;\r
-\r
- }while(ret != -1);\r
-\r
- if (BN_copy(n1, p) == NULL) goto err;\r
- if (!BN_sub_word(n1, 1)) goto err;\r
-\r
- while (!BN_is_odd(n1))\r
- {\r
- if (!BN_add_word(r, 1)) goto err;\r
- if (!BN_rshift1(n1, n1)) goto err;\r
- }\r
-\r
- if (!BN_mod_exp_simple(n0, m, n1, p, ctx)) goto err;\r
-\r
- if (!BN_sub_word(n1, 1)) goto err;\r
- if (!BN_rshift1(n1, n1)) goto err;\r
- if (!BN_mod_exp_simple(x, a, n1, p, ctx)) goto err;\r
-\r
- if (!BN_mod_sqr(b, x, p, ctx)) goto err;\r
- if (!BN_mod_mul(b, b, a, p, ctx)) goto err;\r
-\r
- if (!BN_mod_mul(x, x, a, p, ctx)) goto err;\r
-\r
- while (!BN_is_one(b))\r
- {\r
- \r
- if (!BN_one(m)) goto err;\r
- if (!BN_mod_sqr(n1, b, p, ctx)) goto err;\r
- while(!BN_is_one(n1))\r
- {\r
- if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;\r
- if (!BN_add_word(m, 1)) goto err;\r
- }\r
-\r
- if (!BN_sub(r, r, m)) goto err;\r
- if (!BN_sub_word(r, 1)) goto err;\r
- if (r->neg) goto err;\r
-\r
- if (BN_copy(n1, n0) == NULL) goto err;\r
- while(!BN_is_zero(r))\r
- {\r
- if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;\r
- if (!BN_sub_word(r, 1)) goto err;\r
- }\r
-\r
- if (!BN_mod_mul(n0, n1, n1, p, ctx)) goto err;\r
- if (BN_copy(r, m) == NULL) goto err;\r
- if (!BN_mod_mul(x, x, n1, p, ctx)) goto err;\r
- if (!BN_mod_mul(b, b, n0, p, ctx)) goto err;\r
- }\r
-\r
-\r
-#ifdef TEST\r
- BN_mod_sqr(n0, x, p, ctx);\r
- if (BN_cmp(n0, a)) goto err;\r
-#endif\r
-\r
- if (r != NULL) BN_clear_free(r);\r
- if (b != NULL) BN_clear_free(b);\r
- if (m != NULL) BN_clear_free(m);\r
- ctx->tos -= 2;\r
- return 1;\r
-err:\r
- if (r != NULL) BN_clear_free(r);\r
- if (b != NULL) BN_clear_free(b);\r
- if (m != NULL) BN_clear_free(m);\r
- ctx->tos -= 2;\r
- return 0;\r
-}\r
+/*
+ *
+ * bn_modfs.c
+ *
+ * Some Modular Arithmetic Functions.
+ *
+ * Copyright (C) Lenka Fibikova 2000
+ *
+ *
+ */
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include "bn_modfs.h"
+
+#define MAX_ROUNDS 10
+
+
+int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
+/* x^2 = a (mod p) */
+ {
+ int ret;
+ BIGNUM *n0, *n1, *r, *b, *m;
+ int max;
+
+ assert(x != NULL && a != NULL && p != NULL && ctx != NULL);
+ assert(BN_cmp(a, p) < 0);
+
+ ret = BN_kronecker(a, p, ctx);
+ if (ret < 0 || ret > 1) return 0;
+ if (ret == 0)
+ {
+ if (!BN_zero(x)) return 0;
+ return 1;
+ }
+
+ BN_CTX_start(ctx);
+ n0 = BN_CTX_get(ctx);
+ n1 = BN_CTX_get(ctx);
+ if (n1 == NULL) goto err;
+
+ if ((r = BN_new()) == NULL) goto err;
+ if ((b = BN_new()) == NULL) goto err;
+ if ((m = BN_new()) == NULL) goto err;
+
+
+ if (!BN_zero(n0)) goto err;
+ if (!BN_zero(n1)) goto err;
+ if (!BN_zero(r)) goto err;
+ if (!BN_zero(b)) goto err;
+ if (!BN_zero(m)) goto err;
+
+ max = 0;
+
+ do
+ {
+ if (max++ > MAX_ROUNDS) goto err; /* if p is not prime could never stop*/
+ if (!BN_add_word(m, 1)) goto err;
+ ret = BN_kronecker(m, p, ctx);
+ if (ret < -1 || ret > 1) goto err;
+ }
+ while (ret != -1);
+
+ if (BN_copy(n1, p) == NULL) goto err;
+ if (!BN_sub_word(n1, 1)) goto err;
+
+ while (!BN_is_odd(n1))
+ {
+ if (!BN_add_word(r, 1)) goto err;
+ if (!BN_rshift1(n1, n1)) goto err;
+ }
+
+ if (!BN_mod_exp_simple(n0, m, n1, p, ctx)) goto err;
+
+ if (!BN_sub_word(n1, 1)) goto err;
+ if (!BN_rshift1(n1, n1)) goto err;
+ if (!BN_mod_exp_simple(x, a, n1, p, ctx)) goto err;
+
+ if (!BN_mod_sqr(b, x, p, ctx)) goto err;
+ if (!BN_mod_mul(b, b, a, p, ctx)) goto err;
+
+ if (!BN_mod_mul(x, x, a, p, ctx)) goto err;
+
+ while (!BN_is_one(b))
+ {
+ if (!BN_one(m)) goto err;
+ if (!BN_mod_sqr(n1, b, p, ctx)) goto err;
+ while(!BN_is_one(n1))
+ {
+ if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;
+ if (!BN_add_word(m, 1)) goto err;
+ }
+
+ if (!BN_sub(r, r, m)) goto err;
+ if (!BN_sub_word(r, 1)) goto err;
+ if (r->neg) goto err;
+
+ if (BN_copy(n1, n0) == NULL) goto err;
+ while(!BN_is_zero(r))
+ {
+ if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;
+ if (!BN_sub_word(r, 1)) goto err;
+ }
+
+ if (!BN_mod_mul(n0, n1, n1, p, ctx)) goto err;
+ if (BN_copy(r, m) == NULL) goto err;
+ if (!BN_mod_mul(x, x, n1, p, ctx)) goto err;
+ if (!BN_mod_mul(b, b, n0, p, ctx)) goto err;
+ }
+
+
+#ifdef TEST
+ BN_mod_sqr(n0, x, p, ctx);
+ if (BN_cmp(n0, a)) goto err;
+#endif
+
+ if (r != NULL) BN_clear_free(r);
+ if (b != NULL) BN_clear_free(b);
+ if (m != NULL) BN_clear_free(m);
+ BN_CTX_end(ctx);
+ return 1;
+err:
+ if (r != NULL) BN_clear_free(r);
+ if (b != NULL) BN_clear_free(b);
+ if (m != NULL) BN_clear_free(m);
+ BN_CTX_end(ctx);
+ return 0;
+ }
projects / openssl.git / blobdiff