1 /* 2 3 Copyright 2011, 2016, 2018 Free Software Foundation, Inc. 4 5 This file is part of the GNU MP Library test suite. 6 7 The GNU MP Library test suite is free software; you can redistribute it 8 and/or modify it under the terms of the GNU General Public License as 9 published by the Free Software Foundation; either version 3 of the License, 10 or (at your option) any later version. 11 12 The GNU MP Library test suite is distributed in the hope that it will be 13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General 15 Public License for more details. 16 17 You should have received a copy of the GNU General Public License along with 18 the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ 19 20 #include <stdio.h> 21 #include <stdlib.h> 22 23 #include <time.h> 24 25 #ifdef __unix__ 26 # include <unistd.h> 27 # include <sys/time.h> 28 #endif 29 30 #include "gmp.h" 31 32 #include "hex-random.h" 33 34 /* FIXME: gmp-impl.h included only for mpz_lucas_mod */ 35 /* #include "gmp-impl.h" */ 36 #if defined (__cplusplus) 37 extern "C" { 38 #endif 39 40 #define mpz_lucas_mod __gmpz_lucas_mod 41 __GMP_DECLSPEC int mpz_lucas_mod (mpz_ptr, mpz_ptr, long, mp_bitcnt_t, mpz_srcptr, mpz_ptr, mpz_ptr); 42 43 #if defined (__cplusplus) 44 } 45 #endif 46 47 static gmp_randstate_t state; 48 49 static void 50 mkseed (mpz_t seed) 51 { 52 FILE *f = fopen ("/dev/urandom", "rb"); 53 if (f) 54 { 55 unsigned char buf[6]; 56 size_t res; 57 58 setbuf (f, NULL); 59 res = fread (buf, sizeof(buf), 1, f); 60 fclose (f); 61 62 if (res == 1) 63 { 64 mpz_import (seed, sizeof(buf), 1, 1, 0, 0, buf); 65 return; 66 } 67 } 68 69 #ifdef __unix__ 70 { 71 struct timeval tv; 72 mpz_t usec; 73 mpz_init (usec); 74 75 gettimeofday (&tv, NULL); 76 mpz_set_ui (seed, tv.tv_sec); 77 mpz_set_ui (usec, tv.tv_usec); 78 /* usec fits in 20 bits, shift left to make it 48 bits. */ 79 mpz_mul_2exp (usec, usec, 28); 80 mpz_xor (seed, seed, usec); 81 82 mpz_clear (usec); 83 } 84 #else 85 mpz_set_ui (seed, time (NULL)); 86 #endif 87 } 88 89 void 90 hex_random_init (void) 91 { 92 mpz_t seed; 93 char *env_seed; 94 95 mpz_init (seed); 96 97 env_seed = getenv ("GMP_CHECK_RANDOMIZE"); 98 if (env_seed && env_seed[0]) 99 { 100 mpz_set_str (seed, env_seed, 0); 101 if (mpz_cmp_ui (seed, 0) != 0) 102 gmp_printf ("Re-seeding with GMP_CHECK_RANDOMIZE=%Zd\n", seed); 103 else 104 { 105 mkseed (seed); 106 gmp_printf ("Seed GMP_CHECK_RANDOMIZE=%Zd (include this in bug reports)\n", seed); 107 } 108 fflush (stdout); 109 } 110 else 111 mpz_set_ui (seed, 4711); 112 113 gmp_randinit_default (state); 114 gmp_randseed (state, seed); 115 116 mpz_clear (seed); 117 } 118 119 char * 120 hex_urandomb (unsigned long bits) 121 { 122 char *res; 123 mpz_t x; 124 125 mpz_init (x); 126 mpz_urandomb (x, state, bits); 127 gmp_asprintf (&res, "%Zx", x); 128 mpz_clear (x); 129 return res; 130 } 131 132 char * 133 hex_rrandomb (unsigned long bits) 134 { 135 char *res; 136 mpz_t x; 137 138 mpz_init (x); 139 mpz_rrandomb (x, state, bits); 140 gmp_asprintf (&res, "%Zx", x); 141 mpz_clear (x); 142 return res; 143 } 144 145 char * 146 hex_rrandomb_export (void *dst, size_t *countp, 147 int order, size_t size, int endian, unsigned long bits) 148 { 149 char *res; 150 mpz_t x; 151 mpz_init (x); 152 mpz_rrandomb (x, state, bits); 153 gmp_asprintf (&res, "%Zx", x); 154 mpz_export (dst, countp, order, size, endian, 0, x); 155 mpz_clear (x); 156 return res; 157 } 158 159 void hex_random_op2 (enum hex_random_op op, unsigned long maxbits, 160 char **ap, char **rp) 161 { 162 mpz_t a, r; 163 unsigned long abits; 164 unsigned signs; 165 166 mpz_init (a); 167 mpz_init (r); 168 169 abits = gmp_urandomb_ui (state, 32) % maxbits; 170 171 mpz_rrandomb (a, state, abits); 172 173 signs = gmp_urandomb_ui (state, 1); 174 if (signs & 1) 175 mpz_neg (a, a); 176 177 switch (op) 178 { 179 default: 180 abort (); 181 case OP_SQR: 182 mpz_mul (r, a, a); 183 break; 184 } 185 186 gmp_asprintf (ap, "%Zx", a); 187 gmp_asprintf (rp, "%Zx", r); 188 189 mpz_clear (a); 190 mpz_clear (r); 191 } 192 193 void 194 hex_random_op3 (enum hex_random_op op, unsigned long maxbits, 195 char **ap, char **bp, char **rp) 196 { 197 mpz_t a, b, r; 198 unsigned long abits, bbits; 199 unsigned signs; 200 201 mpz_init (a); 202 mpz_init (b); 203 mpz_init (r); 204 205 abits = gmp_urandomb_ui (state, 32) % maxbits; 206 bbits = gmp_urandomb_ui (state, 32) % maxbits; 207 208 mpz_rrandomb (a, state, abits); 209 mpz_rrandomb (b, state, bbits); 210 211 signs = gmp_urandomb_ui (state, 3); 212 if (signs & 1) 213 mpz_neg (a, a); 214 if (signs & 2) 215 mpz_neg (b, b); 216 217 switch (op) 218 { 219 default: 220 abort (); 221 case OP_ADD: 222 mpz_add (r, a, b); 223 break; 224 case OP_SUB: 225 mpz_sub (r, a, b); 226 break; 227 case OP_MUL: 228 mpz_mul (r, a, b); 229 break; 230 case OP_GCD: 231 if (signs & 4) 232 { 233 /* Produce a large gcd */ 234 unsigned long gbits = gmp_urandomb_ui (state, 32) % maxbits; 235 mpz_rrandomb (r, state, gbits); 236 mpz_mul (a, a, r); 237 mpz_mul (b, b, r); 238 } 239 mpz_gcd (r, a, b); 240 break; 241 case OP_LCM: 242 if (signs & 4) 243 { 244 /* Produce a large gcd */ 245 unsigned long gbits = gmp_urandomb_ui (state, 32) % maxbits; 246 mpz_rrandomb (r, state, gbits); 247 mpz_mul (a, a, r); 248 mpz_mul (b, b, r); 249 } 250 mpz_lcm (r, a, b); 251 break; 252 case OP_AND: 253 mpz_and (r, a, b); 254 break; 255 case OP_IOR: 256 mpz_ior (r, a, b); 257 break; 258 case OP_XOR: 259 mpz_xor (r, a, b); 260 break; 261 } 262 263 gmp_asprintf (ap, "%Zx", a); 264 gmp_asprintf (bp, "%Zx", b); 265 gmp_asprintf (rp, "%Zx", r); 266 267 mpz_clear (a); 268 mpz_clear (b); 269 mpz_clear (r); 270 } 271 272 void 273 hex_random_op4 (enum hex_random_op op, unsigned long maxbits, 274 char **ap, char **bp, char **cp, char **dp) 275 { 276 mpz_t a, b, c, d; 277 unsigned long abits, bbits; 278 unsigned signs; 279 280 mpz_init (a); 281 mpz_init (b); 282 mpz_init (c); 283 mpz_init (d); 284 285 if (op == OP_POWM) 286 { 287 unsigned long cbits; 288 abits = gmp_urandomb_ui (state, 32) % maxbits; 289 bbits = 1 + gmp_urandomb_ui (state, 32) % maxbits; 290 cbits = 2 + gmp_urandomb_ui (state, 32) % maxbits; 291 292 mpz_rrandomb (a, state, abits); 293 mpz_rrandomb (b, state, bbits); 294 mpz_rrandomb (c, state, cbits); 295 296 signs = gmp_urandomb_ui (state, 3); 297 if (signs & 1) 298 mpz_neg (a, a); 299 if (signs & 2) 300 { 301 mpz_t g; 302 303 /* If we negate the exponent, must make sure that gcd(a, c) = 1 */ 304 if (mpz_sgn (a) == 0) 305 mpz_set_ui (a, 1); 306 else 307 { 308 mpz_init (g); 309 310 for (;;) 311 { 312 mpz_gcd (g, a, c); 313 if (mpz_cmp_ui (g, 1) == 0) 314 break; 315 mpz_divexact (a, a, g); 316 } 317 mpz_clear (g); 318 } 319 mpz_neg (b, b); 320 } 321 if (signs & 4) 322 mpz_neg (c, c); 323 324 mpz_powm (d, a, b, c); 325 } 326 else 327 { 328 unsigned long qbits; 329 bbits = 1 + gmp_urandomb_ui (state, 32) % maxbits; 330 qbits = gmp_urandomb_ui (state, 32) % maxbits; 331 abits = bbits + qbits; 332 if (abits > 30) 333 abits -= 30; 334 else 335 abits = 0; 336 337 mpz_rrandomb (a, state, abits); 338 mpz_rrandomb (b, state, bbits); 339 340 signs = gmp_urandomb_ui (state, 2); 341 if (signs & 1) 342 mpz_neg (a, a); 343 if (signs & 2) 344 mpz_neg (b, b); 345 346 switch (op) 347 { 348 default: 349 abort (); 350 case OP_CDIV: 351 mpz_cdiv_qr (c, d, a, b); 352 break; 353 case OP_FDIV: 354 mpz_fdiv_qr (c, d, a, b); 355 break; 356 case OP_TDIV: 357 mpz_tdiv_qr (c, d, a, b); 358 break; 359 } 360 } 361 gmp_asprintf (ap, "%Zx", a); 362 gmp_asprintf (bp, "%Zx", b); 363 gmp_asprintf (cp, "%Zx", c); 364 gmp_asprintf (dp, "%Zx", d); 365 366 mpz_clear (a); 367 mpz_clear (b); 368 mpz_clear (c); 369 mpz_clear (d); 370 } 371 372 void 373 hex_random_bit_op (enum hex_random_op op, unsigned long maxbits, 374 char **ap, unsigned long *b, char **rp) 375 { 376 mpz_t a, r; 377 unsigned long abits, bbits; 378 unsigned signs; 379 380 mpz_init (a); 381 mpz_init (r); 382 383 abits = gmp_urandomb_ui (state, 32) % maxbits; 384 bbits = gmp_urandomb_ui (state, 32) % (maxbits + 100); 385 386 mpz_rrandomb (a, state, abits); 387 388 signs = gmp_urandomb_ui (state, 1); 389 if (signs & 1) 390 mpz_neg (a, a); 391 392 switch (op) 393 { 394 default: 395 abort (); 396 397 case OP_SETBIT: 398 mpz_set (r, a); 399 mpz_setbit (r, bbits); 400 break; 401 case OP_CLRBIT: 402 mpz_set (r, a); 403 mpz_clrbit (r, bbits); 404 break; 405 case OP_COMBIT: 406 mpz_set (r, a); 407 mpz_combit (r, bbits); 408 break; 409 case OP_CDIV_Q_2: 410 mpz_cdiv_q_2exp (r, a, bbits); 411 break; 412 case OP_CDIV_R_2: 413 mpz_cdiv_r_2exp (r, a, bbits); 414 break; 415 case OP_FDIV_Q_2: 416 mpz_fdiv_q_2exp (r, a, bbits); 417 break; 418 case OP_FDIV_R_2: 419 mpz_fdiv_r_2exp (r, a, bbits); 420 break; 421 case OP_TDIV_Q_2: 422 mpz_tdiv_q_2exp (r, a, bbits); 423 break; 424 case OP_TDIV_R_2: 425 mpz_tdiv_r_2exp (r, a, bbits); 426 break; 427 } 428 429 gmp_asprintf (ap, "%Zx", a); 430 *b = bbits; 431 gmp_asprintf (rp, "%Zx", r); 432 433 mpz_clear (a); 434 mpz_clear (r); 435 } 436 437 void 438 hex_random_scan_op (enum hex_random_op op, unsigned long maxbits, 439 char **ap, unsigned long *b, unsigned long *r) 440 { 441 mpz_t a; 442 unsigned long abits, bbits; 443 unsigned signs; 444 445 mpz_init (a); 446 447 abits = gmp_urandomb_ui (state, 32) % maxbits; 448 bbits = gmp_urandomb_ui (state, 32) % (maxbits + 100); 449 450 mpz_rrandomb (a, state, abits); 451 452 signs = gmp_urandomb_ui (state, 1); 453 if (signs & 1) 454 mpz_neg (a, a); 455 456 switch (op) 457 { 458 default: 459 abort (); 460 461 case OP_SCAN0: 462 *r = mpz_scan0 (a, bbits); 463 break; 464 case OP_SCAN1: 465 *r = mpz_scan1 (a, bbits); 466 break; 467 } 468 gmp_asprintf (ap, "%Zx", a); 469 *b = bbits; 470 471 mpz_clear (a); 472 } 473 474 void 475 hex_random_str_op (unsigned long maxbits, 476 int base, char **ap, char **rp) 477 { 478 mpz_t a; 479 unsigned long abits; 480 unsigned signs; 481 482 mpz_init (a); 483 484 abits = gmp_urandomb_ui (state, 32) % maxbits; 485 486 mpz_rrandomb (a, state, abits); 487 488 signs = gmp_urandomb_ui (state, 2); 489 if (signs & 1) 490 mpz_neg (a, a); 491 492 *ap = mpz_get_str (NULL, 16, a); 493 *rp = mpz_get_str (NULL, base, a); 494 495 mpz_clear (a); 496 } 497 498 void hex_random_lucm_op (unsigned long maxbits, 499 char **vp, char **qp, char **mp, 500 long *Q, unsigned long *b0, int *res) 501 { 502 mpz_t m, v, q, t1, t2; 503 unsigned long mbits; 504 505 mpz_init (m); 506 mpz_init (v); 507 mpz_init (q); 508 mpz_init (t1); 509 mpz_init (t2); 510 511 *Q = gmp_urandomb_ui (state, 14) + 1; 512 513 do 514 { 515 mbits = gmp_urandomb_ui (state, 32) % maxbits + 5; 516 517 mpz_rrandomb (m, state, mbits); 518 *b0 = gmp_urandomb_ui (state, 32) % (mbits - 3) + 2; 519 /* The GMP implementation uses the exponent (m >> b0) + 1. */ 520 /* mini-gmp implementation uses the exponent (m >> b0) | 1. */ 521 /* They are the same (and are used) only when (m >> b0) is even */ 522 mpz_clrbit (m, *b0); 523 /* mini-gmp implementation only works if the modulus is odd. */ 524 mpz_setbit (m, 0); 525 } 526 while (mpz_gcd_ui (NULL, m, *Q) != 1); 527 528 if (*Q == 1 || gmp_urandomb_ui (state, 1)) 529 *Q = - *Q; 530 531 #if (__GNU_MP_VERSION == 6 && (__GNU_MP_VERSION_MINOR > 1 || __GNU_MP_VERSION_PATCHLEVEL > 9)) 532 *res = mpz_lucas_mod (v, q, *Q, *b0, m, t1, t2); 533 #else 534 *b0 = 0; 535 #endif 536 537 gmp_asprintf (vp, "%Zx", v); 538 gmp_asprintf (qp, "%Zx", q); 539 gmp_asprintf (mp, "%Zx", m); 540 541 mpz_clear (m); 542 mpz_clear (v); 543 mpz_clear (q); 544 mpz_clear (t1); 545 mpz_clear (t2); 546 } 547 548 void 549 hex_mpq_random_str_op (unsigned long maxbits, 550 int base, char **ap, char **rp) 551 { 552 mpq_t a; 553 unsigned long abits; 554 unsigned signs; 555 556 mpq_init (a); 557 558 abits = gmp_urandomb_ui (state, 32) % maxbits; 559 560 mpz_rrandomb (mpq_numref (a), state, abits); 561 mpz_rrandomb (mpq_denref (a), state, abits); 562 mpz_add_ui (mpq_denref (a), mpq_denref (a), 1); 563 564 mpq_canonicalize (a); 565 signs = gmp_urandomb_ui (state, 2); 566 if (signs & 1) 567 mpq_neg (a, a); 568 569 *ap = mpq_get_str (NULL, 16, a); 570 *rp = mpq_get_str (NULL, base, a); 571 572 mpq_clear (a); 573 } 574