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 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