1 /*
2 * Copyright (C) 2017 - This file is part of libecc project
3 *
4 * Authors:
5 * Ryad BENADJILA <ryadbenadjila@gmail.com>
6 * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr>
7 * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr>
8 *
9 * Contributors:
10 * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr>
11 * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr>
12 *
13 * This software is licensed under a dual BSD and GPL v2 license.
14 * See LICENSE file at the root folder of the project.
15 */
16 #include <libecc/libarith.h>
17
18 /* Declare our Miller-Rabin test implemented
19 * in another module.
20 */
21 ATTRIBUTE_WARN_UNUSED_RET int miller_rabin(nn_src_t n, const unsigned int t, int *check);
22
23 #ifdef FP_EXAMPLE
main(int argc,char * argv[])24 int main(int argc, char *argv[])
25 {
26 nn p;
27 fp x, x_sqrt1, x_sqrt2;
28 fp_ctx ctx;
29 int ret, ret_sqr, isone, check, cmp;
30 x.magic = x_sqrt1.magic = x_sqrt2.magic = WORD(0);
31 ctx.magic = WORD(0);
32 FORCE_USED_VAR(argc);
33 FORCE_USED_VAR(argv);
34
35 while (1) {
36 /* Get a random prime p of maximum 521 bits */
37 ret = nn_init(&p, 0); EG(ret, err);
38 while (1) {
39 /* x = random with max size ~= (NN_MAX_BIT_LEN / 3) bytes.
40 * This size limit is infered from the NN arithmetic primitives
41 * maximum working size. See nn.h for more information about this.
42 */
43 ret = nn_get_random_maxlen
44 (&p, (u16)((NN_MAX_BIT_LEN / 3) / 8)); EG(ret, err);
45
46 /* p = 1 is a marginal prime we don't want to deal with */
47 ret = nn_isone(&p, &isone); EG(ret, err);
48 if(isone){
49 continue;
50 }
51
52 /* Check primality of p, and choose it if it is prime */
53 ret = miller_rabin(&p, 100, &check); EG(ret, err);
54 if(check == 1){
55 break;
56 }
57 }
58 nn_print("Prime p", &p);
59 /* Initialize our Fp context from p */
60 ret = fp_ctx_init_from_p(&ctx, &p); EG(ret, err);
61 /* Initialize x and its square roots */
62 ret = fp_init(&x, &ctx); EG(ret, err);
63 ret = fp_init(&x_sqrt1, &ctx); EG(ret, err);
64 ret = fp_init(&x_sqrt2, &ctx); EG(ret, err);
65
66 /* Get a random value in Fp */
67 ret = fp_get_random(&x, &ctx); EG(ret, err);
68 /* Compute its square in Fp */
69 ext_printf("Random before squaring:\n");
70 fp_print("x", &x);
71 ext_printf("Random after squaring:\n");
72 ret = fp_sqr(&x, &x); EG(ret, err);
73 nn_print("x^2", &(x.fp_val));
74
75 ret_sqr = fp_sqrt(&x_sqrt1, &x_sqrt2, &x);
76
77 if (ret_sqr == 0) {
78 /* Square roots found!, check them! */
79 fp_print("sqrt1", &x_sqrt1);
80 ret = fp_sqr(&x_sqrt1, &x_sqrt1); EG(ret, err);
81 ret = fp_cmp(&x, &x_sqrt1, &cmp); EG(ret, err);
82 if (cmp == 0) {
83 ext_printf("First found square OK!\n");
84 } else {
85 ext_printf("First found square NOK: square "
86 "is not the expected value ...\n");
87 }
88 fp_print("sqrt2", &x_sqrt2);
89 ret = fp_sqr(&x_sqrt2, &x_sqrt2); EG(ret, err);
90 ret = fp_cmp(&x, &x_sqrt2, &cmp); EG(ret, err);
91 if (cmp == 0) {
92 ext_printf("Second found square OK!\n");
93 } else {
94 ext_printf("Second found square NOK: square "
95 "is not the expected value ...\n");
96 }
97
98 } else {
99 if (ret_sqr == -1) {
100 /* This should not happen since we have forged our square */
101 ext_printf("Value n has no square over Fp\n");
102 ext_printf("(Note: this error can be due to "
103 "Miller-Rabin providing a false "
104 "positive prime ...)\n");
105 ext_printf("(though this should happen with "
106 "negligible probability))\n");
107 nn_print("Check primality of p =", &p);
108 /* Get out of the main loop */
109 break;
110 } else {
111 /* This should not happen since we have forged our square */
112 ext_printf("Tonelli-Shanks algorithm unkown "
113 "error ...\n");
114 ext_printf("(Note: this error can be due to "
115 "Miller-Rabin providing a false "
116 "positive prime ...)\n");
117 ext_printf("(though this should happen with "
118 "negligible probability))\n");
119 nn_print("Check primality of p =", &p);
120 /* Get out of the main loop */
121 break;
122 }
123 }
124 }
125
126 return 0;
127 err:
128 ext_printf("Error: unkown error ...\n");
129 return -1;
130 }
131 #endif
132