OSX/libsecurity_cryptkit/ckutils/giantDvt/giantDvt.c

   1 /*
   2  * Copyright (c) 1998,2011,2014 Apple Inc. All Rights Reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24
  25 #include "giantIntegers.h"
  26 #include "ckutilities.h"
  27 #include "feeFunctions.h"
  28 #include "feeDebug.h"
  29 #include <stdlib.h>
  30 #include "ckutilsPlatform.h"
  31 #include <stdio.h>
  32 #include <time.h>
  33
  34 #define LOOPS_DEF       100
  35 #define MAX_SIZE_DEF    32
  36 #define LOOP_NOTIFY     100
  37
  38 /* quick test to show modg(1,g) broken */
  39 #define MODG1_TEST_ENABLE       1
  40
  41 static void usage(char **argv)
  42 {
  43         printf("usage: %s [options]\n", argv[0]);
  44         printf("   Options:\n");
  45         printf("   l=loops    (default = %d)\n", LOOPS_DEF);
  46         printf("   x=maxBytes (default = %d)\n", MAX_SIZE_DEF);
  47         printf("   s=seed\n");
  48         printf("   h(elp)\n");
  49         exit(1);
  50 }
  51
  52 /*
  53  * ...min <= return <= max
  54  */
  55 static int genRand(int min, int max)
  56 {
  57
  58     /* note random() only yields a 31-bit number... */
  59
  60     if(max == min)                      /* avoid % 1 ! */
  61         return(max);
  62     else
  63         return(min + (RAND() % (max-min+1)));
  64 }
  65
  66 /*
  67  * Fill buffer with random data, random size from 1 to maxSize.
  68  * Returns size of random data generated.
  69  */
  70 static unsigned fillData(unsigned maxSize,
  71         unsigned char *data,
  72         int evenOnly)
  73 {
  74         unsigned        *ip;
  75         unsigned        intCount;
  76         unsigned        residue;
  77         unsigned char   *cp;
  78         int             i;
  79         unsigned        size;
  80
  81         size = genRand(1, maxSize);
  82         if(evenOnly) {
  83                 size &= ~1;
  84                 if(size == 1) {
  85                         size = 2;
  86                 }
  87         }
  88         intCount = size >> 2;
  89         ip = (unsigned *)data;
  90         for(i=0; i<intCount; i++) {
  91                 *ip++ = RAND();
  92         }
  93
  94         residue = size & 0x3;
  95         cp = (unsigned char *)ip;
  96         for(i=0; i<residue; i++) {
  97                 *cp++ = (unsigned char)RAND();
  98         }
  99         return size;
 100 }
 101
 102 /*
 103  * create a giant with random size and data. *Buf is mallocd and
 104  * uninitialized and will change here.
 105  */
 106 static giant genGiant(unsigned maxBytes, unsigned char *buf)
 107 {
 108         int size = fillData(maxBytes, buf, 0);
 109         int i;
 110         giant g;
 111
 112         g = giant_with_data(buf, size);
 113
 114         /* set random sign; giant_with_data() is always positive */
 115         i = RAND();
 116         if(i & 1) {
 117                 g->sign = -g->sign;
 118         }
 119
 120         /* avoid zero data - too many pitfalls with mod and div */
 121         if(isZero(g)) {
 122                 g->sign = 1;
 123                 g->n[0] = 0x77;
 124         }
 125         return g;
 126 }
 127
 128 static int testError()
 129 {
 130         char resp[100];
 131
 132         printf("Attach via debugger for more info.\n");
 133         printf("a to abort, c to continue: ");
 134         gets(resp);
 135         return (resp[0] != 'c');
 136 }
 137
 138 /* g := |g1| */
 139 static void gabs(giant g)
 140 {
 141         if(g->sign < 0) {
 142             g->sign = -g->sign;
 143         }
 144 }
 145
 146 /*
 147  * Individual tests. API is identical for all tests.
 148  *
 149  * g1, g2 : giants with random data, size, and sign. Tests do not modify
 150  *           these.
 151  * scr1, scr2 : scratch giants, big enough for all conceivable ops. Can
 152  *           be modified at will.
 153  * Return : 0 for sucess, 1 on error.
 154  */
 155
 156 static int compTest(giant g1, giant g2, giant scr1, giant scr2)
 157 {
 158         gtog(g1, scr1);         // scr1 := g1
 159         gtog(scr1, scr2);
 160         if(gcompg(g1, scr2)) {
 161                 printf("gtog/gcompg error\n");
 162                 return testError();
 163         }
 164         return 0;
 165 }
 166
 167 static int addSubTest(giant g1, giant g2, giant scr1, giant scr2)
 168 {
 169         gtog(g1, scr1);         // scr1 := g1
 170         addg(g2, scr1);         // scr1 := g1 + g2
 171         subg(g1, scr1);         // scr1 := g1 + g2 - g1 =? g2
 172         if(gcompg(g2, scr1)) {
 173                 printf("addg/subg error\n");
 174                 return testError();
 175         }
 176         return 0;
 177 }
 178
 179 #define LARGEST_MUL     0xffff
 180
 181 static int mulTest(giant g1, giant g2, giant scr1, giant scr2)
 182 {
 183         int randInt = genRand(1, LARGEST_MUL);
 184         int i;
 185         int rtn = 0;
 186
 187         int_to_giant(randInt, scr1);    // scr1 := randInt
 188         gtog(g1, scr2);                 // scr2 := g1
 189         mulg(scr1, scr2);               // scr2 := g1 * randInt
 190
 191         /* now do the same thing with multiple adds */
 192         int_to_giant(0, scr1);          // scr1 := 0
 193         for(i=0; i<randInt; i++) {
 194                 addg(g1, scr1);         // scr1 += g1
 195         }                               // scr1 =? g1 * randInt
 196         if(gcompg(scr1, scr2)) {
 197                 printf("g1        : "); printGiantHex(g1);
 198                 printf("randInt   : 0x%x\n", randInt);
 199                 printf("good prod : "); printGiantHex(scr1);
 200                 printf("bad prod  : "); printGiantHex(scr2);
 201                 printf("mulg error\n");
 202                 rtn = testError();
 203         }
 204         return rtn;
 205
 206 }
 207
 208 static int squareTest(giant g1, giant g2, giant scr1, giant scr2)
 209 {
 210         gtog(g1, scr1);
 211         mulg(g1, scr1);                 // scr1 := g1 * g1
 212         gtog(g1, scr2);
 213         gsquare(scr2);                  // scr2 =? g1 * g1
 214         if(gcompg(scr1, scr2)) {
 215                 printf("gsquare error\n");
 216                 return testError();
 217         }
 218         return 0;
 219 }
 220
 221 static int lshiftTest(giant g1, giant g2, giant scr1, giant scr2)
 222 {
 223         int maxShift = (scr1->capacity - abs(g1->sign) - 1) *
 224                          GIANT_BITS_PER_DIGIT;
 225         int shiftCnt = genRand(1, maxShift);
 226         giant scr3 = borrowGiant(scr1->capacity);
 227         int rtn = 0;
 228
 229         gtog(g1, scr1);                 // scr1 := g1
 230         gshiftleft(shiftCnt, scr1);     // scr1 := (g1 << shiftCnt)
 231
 232         gtog(g1, scr2);                 // scr2 := g1
 233         if(shiftCnt <= 30) {
 234             int multInt = (1 << shiftCnt);
 235             int_to_giant(multInt, scr3);   // scr3 := (1 << shiftCnt)
 236         }
 237         else {
 238             int_to_giant(1, scr3);      // scr3 := 1;
 239             gshiftleft(shiftCnt, scr3); // scr3 := (1 << shiftCnt)
 240         }
 241         mulg(scr3, scr2);               // scr2 := g1 * (1 << shiftCnt);
 242         if(gcompg(scr1, scr2)) {
 243                 printf("shiftCnt %d 0x%x\n", shiftCnt, shiftCnt);
 244                 printf("g1   : "); printGiantHex(g1);
 245                 printf("scr1 : "); printGiantHex(scr1);
 246                 printf("scr2 : "); printGiantHex(scr2);
 247                 printf("gshiftleft error\n");
 248                 rtn = testError();
 249         }
 250         returnGiant(scr3);
 251         return rtn;
 252 }
 253
 254 static int rshiftTest(giant g1, giant g2, giant scr1, giant scr2)
 255 {
 256         int maxShift = bitlen(g1) - 1;
 257         int shiftCnt;
 258         giant scr3 = borrowGiant(scr1->capacity);
 259         int rtn = 0;
 260
 261         /* special case, can't have g1 = 1 */
 262         if(maxShift == 0) {
 263                 #if     FEE_DEBUG
 264                 printf("...rshiftTest: tweaking g1 = 1\n");
 265                 #endif
 266                 g1->n[0] = 2;
 267                 shiftCnt = 1;
 268         }
 269         else {
 270                 shiftCnt = genRand(1, maxShift);
 271         }
 272         gtog(g1, scr1);                 // scr1 := g1
 273         gabs(scr1);                     // scr1 := |g1|
 274         gtog(scr1, scr2);               // scr2 := |g1|
 275         gshiftright(shiftCnt, scr1);    // scr1 := (|g1| >> shiftCnt)
 276
 277         if(shiftCnt <= 30) {
 278             int multInt = (1 << shiftCnt);
 279             int_to_giant(multInt, scr3);   // scr3 := (1 << shiftCnt)
 280         }
 281         else {
 282             int_to_giant(1, scr3);      // scr3 := 1;
 283             gshiftleft(shiftCnt, scr3); // scr3 := (1 << shiftCnt)
 284         }
 285         divg(scr3, scr2);               // scr2 := g1 / (1 << shiftCnt);
 286         if(gcompg(scr1, scr2)) {
 287                 printf("shiftCnt %d 0x%x\n", shiftCnt, shiftCnt);
 288                 printf("g1   : "); printGiantHex(g1);
 289                 printf("scr1 : "); printGiantHex(scr1);
 290                 printf("scr2 : "); printGiantHex(scr2);
 291                 printf("gshiftright error\n");
 292                 rtn = testError();
 293         }
 294         returnGiant(scr3);
 295         return rtn;
 296 }
 297
 298 static int divTest(giant g1, giant g2, giant scr1, giant scr2)
 299 {
 300         gtog(g1, scr1);         // scr1 := g1
 301         mulg(g2, scr1);         // scr1 := g1 * g2
 302         gtog(g2, scr2);         // scr2 := g2
 303         gabs(scr2);             // scr2 := |g2|
 304         divg(scr2, scr1);       // scr1 := (g1 * g2) / |g2|
 305
 306         /* weird case - if g2 is negative, this result is -g1! */
 307         if(g2->sign < 0) {
 308             scr1->sign = -scr1->sign;
 309         }
 310         if(gcompg(scr1, g1)) {
 311             printf("g1 : "); printGiantHex(g1);
 312             printf("g2 : "); printGiantHex(g1);
 313             printf("scr1 : "); printGiantHex(scr1);
 314             printf("divTest error\n");
 315             return testError();
 316         }
 317         return 0;
 318 }
 319
 320 #define LARGEST_MOD_MUL 0x40
 321
 322 static int modTest(giant g1, giant g2, giant scr1, giant scr2)
 323 {
 324         int randInt = genRand(1, LARGEST_MOD_MUL);
 325         giant scr3 = borrowGiant(scr1->capacity);
 326         /* debug only */
 327         giant scr4 = borrowGiant(scr1->capacity);
 328         /* end debug */
 329         int rtn = 0;
 330
 331         int_to_giant(randInt, scr1);    // scr1 := rand
 332         gtog(g1, scr2);
 333         gabs(scr2);                     // scr2 := |g1|
 334
 335         /* current modg can't deal with g mod 1 ! */
 336         if((scr2->sign == 1) && (scr2->n[0] == 1)) {
 337                 #if     MODG1_TEST_ENABLE
 338                 /* assume that this is legal... */
 339                 #if     FEE_DEBUG
 340                 printf("..modTest: g1 = 1, no tweak\n");
 341                 #endif
 342                 #else
 343                 printf("..modTest: tweaking g1 = 1\n");
 344                 scr2->n[0] = 0x54;
 345                 #endif  MODG1_TEST_ENABLE
 346         }
 347         /* end modg workaround */
 348
 349         gtog(g2, scr3);
 350         gabs(scr3);                     // scr3 := |g2|
 351
 352         /* this will only work if randInt < |g1| */
 353         if(gcompg(scr1, scr2) >= 0) {
 354             #if FEE_DEBUG
 355             printf("..modTest: tweaking rand, > g1 = "); printGiantHex(g1);
 356             printf("                            g2 = "); printGiantHex(g2);
 357             printf("                          rand = "); printGiantHex(scr1);
 358             #endif
 359             modg(scr2, scr1);           // scr1 := rand mod g1
 360             if(gcompg(scr1, scr2) >= 0) {
 361                 printf("simple modg error\n");
 362                 return testError();
 363             }
 364         }
 365
 366         mulg(scr2, scr3);               // scr3 := |g1 * g2|
 367         addg(scr1, scr3);               // scr3 := (|g1 * g2|) + rand
 368         gtog(scr3, scr4);
 369         modg(scr2, scr3);               // scr3 := scr3 mod |g1| =? rand
 370         if(gcompg(scr1, scr3)) {
 371                 printf("g1 : "); printGiantHex(g1);
 372                 printf("g2 : "); printGiantHex(g2);
 373                 printf("rand : 0x%x\n", randInt);
 374                 printf("randG : "); printGiantHex(scr1);
 375                 printf("scr4 : "); printGiantHex(scr4);
 376                 printf("mod  : "); printGiantHex(scr3);
 377                 printf("modTest error\n");
 378                 rtn = testError();
 379         }
 380         returnGiant(scr3);
 381         returnGiant(scr4);
 382         return rtn;
 383
 384
 385 }
 386
 387 #if     MODG1_TEST_ENABLE
 388 /* quickie test to demonstrate failure of modg(1, g). Known failure
 389  * as of 10 Apr 1998.
 390  * modg(1,g) fixed on 13 Apr 1998, so this should now work.
 391  */
 392 static int modg1Test(giant g1, giant scr1, giant scr2)
 393 {
 394         /* test mod(x, 1) */
 395         scr1->n[0] = 1;
 396         scr1->sign = 1;
 397         gtog(g1, scr2);
 398         modg(scr1, scr2);
 399         if(!isZero(scr2)) {
 400                 printf("g1 : "); printGiantHex(g1);
 401                 printf("g1 mod 1 : "); printGiantHex(scr2);
 402                 return testError();
 403         }
 404         return 0;
 405 }
 406 #endif  MODG1_TEST_ENABLE
 407
 408 static int mulOnesTest(giant g1, giant g2, giant scr1, giant scr2)
 409 {
 410         int i;
 411         int rtn = 0;
 412         giant gOnes = borrowGiant(scr1->capacity);
 413
 414         /* set up a giant with all ones data */
 415         gOnes->sign = abs(g1->sign);
 416         for(i=0; i<gOnes->sign; i++) {
 417                 gOnes->n[i] = (giantDigit)(-1);
 418         }
 419
 420         gtog(gOnes, scr1);              // scr1 := gOnes
 421         mulg(g1, scr1);                 // scr1 := gOnes * g1
 422
 423         gtog(g1, scr2);
 424         mulg(gOnes, scr2);
 425
 426         if(gcompg(scr1, scr2)) {
 427                 printf("good prod : "); printGiantHex(scr1);
 428                 printf("bad prod  : "); printGiantHex(scr2);
 429                 printf("mulOnesTest error\n");
 430                 rtn = testError();
 431         }
 432         return rtn;
 433
 434 }
 435
 436 int main(int argc, char **argv)
 437 {
 438         int             arg;
 439         char            *argp;
 440         giant           g1;             // init'd randomly
 441         giant           g2;             // ditto
 442         giant           scr1;           // scratch
 443         giant           scr2;           // ditto
 444         unsigned char   *buf;
 445         int             loop;
 446
 447         int             loops = LOOPS_DEF;
 448         int             seedSpec = 0;
 449         unsigned        seed = 0;
 450         unsigned        maxSize = MAX_SIZE_DEF;
 451
 452         initCryptKit();
 453
 454         #ifdef  macintosh
 455         seedSpec = 1;
 456         seed = 0;
 457         argc = 1;
 458         maxSize = 8;
 459         #endif
 460
 461         for(arg=1; arg<argc; arg++) {
 462                 argp = argv[arg];
 463                 switch(argp[0]) {
 464                     case 'x':
 465                         maxSize = atoi(&argp[2]);
 466                         break;
 467                     case 'l':
 468                         loops = atoi(&argp[2]);
 469                         break;
 470                     case 's':
 471                         seed = atoi(&argp[2]);
 472                         seedSpec = 1;
 473                         break;
 474                     case 'h':
 475                     default:
 476                         usage(argv);
 477                 }
 478         }
 479         buf = malloc(maxSize);
 480
 481         if(!seedSpec) {
 482                 time_t  tim;
 483                 time(&tim);
 484                 seed = (unsigned)tim;
 485         }
 486         SRAND(seed);
 487
 488         /*
 489          * Scratch giants, big enough for anything
 490          */
 491         scr1 = newGiant(4 * maxSize * GIANT_BYTES_PER_DIGIT);
 492         scr2 = newGiant(4 * maxSize * GIANT_BYTES_PER_DIGIT);
 493
 494         printf("Starting giants test: seed %d\n", seed);
 495         for(loop=0; loop<loops; loop++) {
 496
 497             if((loop % LOOP_NOTIFY) == 0) {
 498                 printf("..loop %d\n", loop);
 499             }
 500
 501             g1 = genGiant(maxSize, buf);
 502             g2 = genGiant(maxSize, buf);
 503
 504             #if 1
 505             if(compTest(g1, g2, scr1, scr2)) {
 506                     exit(1);
 507             }
 508             if(addSubTest(g1, g2, scr1, scr2)) {
 509                     exit(1);
 510             }
 511             #endif
 512             #if 1
 513             if(mulTest(g1, g2, scr1, scr2)) {
 514                     exit(1);
 515             }
 516             #endif
 517             #if 1
 518             if(squareTest(g1, g2, scr1, scr2)) {
 519                     exit(1);
 520             }
 521             if(lshiftTest(g1, g2, scr1, scr2)) {
 522                     exit(1);
 523             }
 524             if(modTest(g1, g2, scr1, scr2)) {
 525                     exit(1);
 526             }
 527             if(rshiftTest(g1, g2, scr1, scr2)) {
 528                     exit(1);
 529             }
 530             /* these all use divide....*/
 531             if(divTest(g1, g2, scr1, scr2)) {
 532                     exit(1);
 533             }
 534             #if MODG1_TEST_ENABLE
 535             if(modg1Test(g1, scr1, scr2)) {
 536                 exit(1);
 537             }
 538             #endif
 539             #endif 0
 540             if(mulOnesTest(g1, g2, scr1, scr2)) {
 541                 exit(1);
 542             }
 543             freeGiant(g1);
 544             freeGiant(g2);
 545         }
 546
 547         printf("...giantDvt complete\n");
 548         return 0;
 549 }