00001 #include "system.h"
00002 #include "mpbarrett.h"
00003 #include "mp.h"
00004 #include "popt.h"
00005 #include "debug.h"
00006
00007 static int _debug = 0;
00008
00009 static int Zmpbinv_w(const mpbarrett* b, size_t xsize, const mpw* xdata, mpw* result, mpw* wksp)
00010 {
00011 size_t ysize = b->size+1;
00012 size_t ubits, vbits;
00013 int k = 0;
00014
00015 mpw* u = wksp;
00016 mpw* v = u+ysize;
00017 mpw* A = v+ysize;
00018 mpw* B = A+ysize;
00019 mpw* C = B+ysize;
00020 mpw* D = C+ysize;
00021
00022 mpsetx(ysize, u, xsize, xdata);
00023 mpsetx(ysize, v, b->size, b->modl);
00024 mpsetw(ysize, A, 1);
00025 mpzero(ysize, B);
00026 mpzero(ysize, C);
00027 mpsetw(ysize, D, 1);
00028
00029 for (k = 0; mpeven(ysize, u) && mpeven(ysize, v); k++) {
00030 mpdivtwo(ysize, u);
00031 mpdivtwo(ysize, v);
00032 }
00033
00034 if (mpeven(ysize, u))
00035 (void) mpadd(ysize, u, v);
00036
00037 if (_debug < 0)
00038 fprintf(stderr, " u: "), mpfprintln(stderr, ysize, u);
00039 if (_debug < 0)
00040 fprintf(stderr, " v: "), mpfprintln(stderr, ysize, v);
00041 if (_debug < 0)
00042 fprintf(stderr, " A: "), mpfprintln(stderr, ysize, A);
00043 if (_debug < 0)
00044 fprintf(stderr, " B: "), mpfprintln(stderr, ysize, B);
00045 if (_debug < 0)
00046 fprintf(stderr, " C: "), mpfprintln(stderr, ysize, C);
00047 if (_debug < 0)
00048 fprintf(stderr, " D: "), mpfprintln(stderr, ysize, D);
00049
00050 ubits = vbits = MP_WORDS_TO_BITS(ysize);
00051
00052 do {
00053 while (mpeven(ysize, v)) {
00054 mpsdivtwo(ysize, v);
00055 vbits -= 1;
00056 if (mpodd(ysize, C)) {
00057 (void) mpaddx(ysize, C, b->size, b->modl);
00058 (void) mpsubx(ysize, D, xsize, xdata);
00059 }
00060 mpsdivtwo(ysize, C);
00061 mpsdivtwo(ysize, D);
00062 if (_debug < 0)
00063 fprintf(stderr, "-->> v: "), mpfprintln(stderr, ysize, v);
00064 }
00065
00066 if (ubits >= vbits) {
00067 mpw* swapu;
00068 size_t swapi;
00069
00070 if (_debug < 0)
00071 fprintf(stderr, "--> (swap u <-> v)\n");
00072 swapu = u; u = v; v = swapu;
00073 swapi = ubits; ubits = vbits; vbits = swapi;
00074 swapu = A; A = C; C = swapu;
00075 swapu = B; B = D; D = swapu;
00076 }
00077
00078 if (!((u[ysize-1] + v[ysize-1]) & 0x3)) {
00079 if (_debug < 0)
00080 fprintf(stderr, "--> (even parity)\n");
00081 mpadd(ysize, v, u);
00082 mpadd(ysize, C, A);
00083 mpadd(ysize, D, B);
00084 } else {
00085 if (_debug < 0)
00086 fprintf(stderr, "--> (odd parity)\n");
00087 mpsub(ysize, v, u);
00088 mpsub(ysize, C, A);
00089 mpsub(ysize, D, B);
00090 }
00091 if (_debug < 0)
00092 fprintf(stderr, " v: "), mpfprintln(stderr, ysize, v);
00093 if (_debug < 0)
00094 fprintf(stderr, " C: "), mpfprintln(stderr, ysize, C);
00095 if (_debug < 0)
00096 fprintf(stderr, " D: "), mpfprintln(stderr, ysize, D);
00097 vbits++;
00098 } while (mpnz(ysize, v));
00099
00100 #ifdef NOTYET
00101 if (!mpisone(ysize, u))
00102 return 0;
00103 #endif
00104
00105 if (result) {
00106 mpsetx(b->size, result, ysize, A);
00107
00108 if (*A & 0x80000000)
00109 (void) mpneg(b->size, result);
00110
00111 while (--k > 0)
00112 mpadd(b->size, result, result);
00113 }
00114
00115 fprintf(stderr, "=== EXIT: "), mpfprintln(stderr, b->size, result);
00116 fprintf(stderr, " u: "), mpfprintln(stderr, ysize, u);
00117 fprintf(stderr, " v: "), mpfprintln(stderr, ysize, v);
00118 fprintf(stderr, " A: "), mpfprintln(stderr, ysize, A);
00119 fprintf(stderr, " B: "), mpfprintln(stderr, ysize, B);
00120 fprintf(stderr, " C: "), mpfprintln(stderr, ysize, C);
00121 fprintf(stderr, " D: "), mpfprintln(stderr, ysize, D);
00122
00123 return 1;
00124 }
00125
00126 static int Ympbinv_w(const mpbarrett* b, size_t xsize, const mpw* xdata, mpw* result, mpw* wksp)
00127 {
00128 size_t ysize = b->size+1;
00129 int k;
00130 mpw* u1 = wksp;
00131 mpw* u2 = u1+ysize;
00132 mpw* u3 = u2+ysize;
00133 mpw* v1 = u3+ysize;
00134 mpw* v2 = v1+ysize;
00135 mpw* v3 = v2+ysize;
00136 mpw* t1 = v3+ysize;
00137 mpw* t2 = t1+ysize;
00138 mpw* t3 = t2+ysize;
00139 mpw* u = t3+ysize;
00140 mpw* v = u+ysize;
00141
00142 mpsetx(ysize, u, xsize, xdata);
00143 mpsetx(ysize, v, b->size, b->modl);
00144
00145
00146 for (k = 0; mpeven(ysize, u) && mpeven(ysize, v); k++) {
00147 mpdivtwo(ysize, u);
00148 mpdivtwo(ysize, v);
00149 }
00150
00151 if (_debug < 0)
00152 fprintf(stderr, " u: "), mpfprintln(stderr, ysize, u);
00153 if (_debug < 0)
00154 fprintf(stderr, " v: "), mpfprintln(stderr, ysize, v);
00155
00156
00157 mpsetw(ysize, u1, 1);
00158 if (_debug < 0)
00159 fprintf(stderr, " u1: "), mpfprintln(stderr, ysize, u1);
00160 mpzero(ysize, u2);
00161 if (_debug < 0)
00162 fprintf(stderr, " u2: "), mpfprintln(stderr, ysize, u2);
00163 mpsetx(ysize, u3, ysize, u);
00164 if (_debug < 0)
00165 fprintf(stderr, " u3: "), mpfprintln(stderr, ysize, u3);
00166
00167 mpsetx(ysize, v1, ysize, v);
00168 if (_debug < 0)
00169 fprintf(stderr, " v1: "), mpfprintln(stderr, ysize, v1);
00170 mpsetw(ysize, v2, 1);
00171 (void) mpsub(ysize, v2, u);
00172 if (_debug < 0)
00173 fprintf(stderr, " v2: "), mpfprintln(stderr, ysize, v2);
00174 mpsetx(ysize, v3, ysize, v);
00175 if (_debug < 0)
00176 fprintf(stderr, " v3: "), mpfprintln(stderr, ysize, v3);
00177
00178 if (mpodd(ysize, u)) {
00179 mpzero(ysize, t1);
00180 if (_debug < 0)
00181 fprintf(stderr, " t1: "), mpfprintln(stderr, ysize, t1);
00182 mpzero(ysize, t2);
00183 mpsubw(ysize, t2, 1);
00184 if (_debug < 0)
00185 fprintf(stderr, " t2: "), mpfprintln(stderr, ysize, t2);
00186 mpzero(ysize, t3);
00187 mpsub(ysize, t3, v);
00188 if (_debug < 0)
00189 fprintf(stderr, " t3: "), mpfprintln(stderr, ysize, t3);
00190 goto Y4;
00191 } else {
00192 mpsetw(ysize, t1, 1);
00193 if (_debug < 0)
00194 fprintf(stderr, " t1: "), mpfprintln(stderr, ysize, t1);
00195 mpzero(ysize, t2);
00196 if (_debug < 0)
00197 fprintf(stderr, " t2: "), mpfprintln(stderr, ysize, t2);
00198 mpsetx(ysize, t3, ysize, u);
00199 if (_debug < 0)
00200 fprintf(stderr, " t3: "), mpfprintln(stderr, ysize, t3);
00201 }
00202
00203 do {
00204 do {
00205 if (mpodd(ysize, t1) || mpodd(ysize, t2)) {
00206 mpadd(ysize, t1, v);
00207 mpsub(ysize, t2, u);
00208 }
00209 mpsdivtwo(ysize, t1);
00210 mpsdivtwo(ysize, t2);
00211 mpsdivtwo(ysize, t3);
00212 Y4:
00213 if (_debug < 0)
00214 fprintf(stderr, " Y4 t3: "), mpfprintln(stderr, ysize, t3);
00215 } while (mpeven(ysize, t3));
00216
00217
00218 if (!(*t3 & 0x80000000)) {
00219 if (_debug < 0)
00220 fprintf(stderr, "--> Y5 (t3 > 0)\n");
00221 mpsetx(ysize, u1, ysize, t1);
00222 if (_debug < 0)
00223 fprintf(stderr, " u1: "), mpfprintln(stderr, ysize, u1);
00224 mpsetx(ysize, u2, ysize, t2);
00225 if (_debug < 0)
00226 fprintf(stderr, " u2: "), mpfprintln(stderr, ysize, u2);
00227 mpsetx(ysize, u3, ysize, t3);
00228 if (_debug < 0)
00229 fprintf(stderr, " u3: "), mpfprintln(stderr, ysize, u3);
00230 } else {
00231 if (_debug < 0)
00232 fprintf(stderr, "--> Y5 (t3 <= 0)\n");
00233 mpsetx(ysize, v1, ysize, v);
00234 mpsub(ysize, v1, t1);
00235 if (_debug < 0)
00236 fprintf(stderr, " v1: "), mpfprintln(stderr, ysize, v1);
00237 mpsetx(ysize, v2, ysize, u);
00238 mpneg(ysize, v2);
00239 mpsub(ysize, v2, t2);
00240 if (_debug < 0)
00241 fprintf(stderr, " v2: "), mpfprintln(stderr, ysize, v2);
00242 mpzero(ysize, v3);
00243 mpsub(ysize, v3, t3);
00244 if (_debug < 0)
00245 fprintf(stderr, " v3: "), mpfprintln(stderr, ysize, v3);
00246 }
00247
00248
00249 mpsetx(ysize, t1, ysize, u1);
00250 mpsub(ysize, t1, v1);
00251 mpsetx(ysize, t2, ysize, u2);
00252 mpsub(ysize, t2, v2);
00253 mpsetx(ysize, t3, ysize, u3);
00254 mpsub(ysize, t3, v3);
00255
00256 if (*t1 & 0x80000000) {
00257 mpadd(ysize, t1, v);
00258 mpsub(ysize, t2, u);
00259 }
00260
00261 if (_debug < 0)
00262 fprintf(stderr, "-->Y6 t1: "), mpfprintln(stderr, ysize, t1);
00263 if (_debug < 0)
00264 fprintf(stderr, " t2: "), mpfprintln(stderr, ysize, t2);
00265 if (_debug < 0)
00266 fprintf(stderr, " t3: "), mpfprintln(stderr, ysize, t3);
00267
00268 } while (mpnz(ysize, t3));
00269
00270 if (!(mpisone(ysize, u3) && mpisone(ysize, v3)))
00271 return 0;
00272
00273 if (result) {
00274 while (--k > 0)
00275 mpadd(ysize, u1, u1);
00276 mpsetx(b->size, result, ysize, u1);
00277 }
00278
00279 fprintf(stderr, "=== EXIT: "), mpfprintln(stderr, b->size, result);
00280 fprintf(stderr, " u1: "), mpfprintln(stderr, ysize, u1);
00281 fprintf(stderr, " u2: "), mpfprintln(stderr, ysize, u2);
00282 fprintf(stderr, " u3: "), mpfprintln(stderr, ysize, u3);
00283 fprintf(stderr, " v1: "), mpfprintln(stderr, ysize, v1);
00284 fprintf(stderr, " v2: "), mpfprintln(stderr, ysize, v2);
00285 fprintf(stderr, " v3: "), mpfprintln(stderr, ysize, v3);
00286 fprintf(stderr, " t1: "), mpfprintln(stderr, ysize, t1);
00287 fprintf(stderr, " t2: "), mpfprintln(stderr, ysize, t2);
00288 fprintf(stderr, " t3: "), mpfprintln(stderr, ysize, t3);
00289
00290 return 1;
00291 }
00292
00298 static int Xmpbinv_w(const mpbarrett* b, size_t xsize, const mpw* xdata, mpw* result, mpw* wksp)
00299 {
00300
00301
00302
00303
00304
00305
00306
00307 size_t ysize = b->size+1;
00308
00309 mpw* u = wksp;
00310 mpw* v = u+ysize;
00311 mpw* A = v+ysize;
00312 mpw* B = A+ysize;
00313 mpw* C = B+ysize;
00314 mpw* D = C+ysize;
00315
00316 mpsetx(ysize, u, b->size, b->modl);
00317 mpsetx(ysize, v, xsize, xdata);
00318 mpsetw(ysize, A, 1);
00319 mpzero(ysize, B);
00320 mpzero(ysize, C);
00321 mpsetw(ysize, D, 1);
00322
00323 if (_debug < 0)
00324 fprintf(stderr, " u: "), mpfprintln(stderr, ysize, u);
00325 if (_debug < 0)
00326 fprintf(stderr, " v: "), mpfprintln(stderr, ysize, v);
00327 if (_debug < 0)
00328 fprintf(stderr, " A: "), mpfprintln(stderr, ysize, A);
00329 if (_debug < 0)
00330 fprintf(stderr, " B: "), mpfprintln(stderr, ysize, B);
00331 if (_debug < 0)
00332 fprintf(stderr, " C: "), mpfprintln(stderr, ysize, C);
00333 if (_debug < 0)
00334 fprintf(stderr, " D: "), mpfprintln(stderr, ysize, D);
00335
00336 do {
00337 while (mpeven(ysize, u))
00338 {
00339 mpdivtwo(ysize, u);
00340
00341 if (mpodd(ysize, A) || mpodd(ysize, B))
00342 {
00343 (void) mpaddx(ysize, A, xsize, xdata);
00344 (void) mpsubx(ysize, B, b->size, b->modl);
00345 }
00346
00347 mpsdivtwo(ysize, A);
00348 mpsdivtwo(ysize, B);
00349 }
00350 while (mpeven(ysize, v))
00351 {
00352 mpdivtwo(ysize, v);
00353
00354 if (mpodd(ysize, C) || mpodd(ysize, D))
00355 {
00356 (void) mpaddx(ysize, C, xsize, xdata);
00357 (void) mpsubx(ysize, D, b->size, b->modl);
00358 }
00359
00360 mpsdivtwo(ysize, C);
00361 mpsdivtwo(ysize, D);
00362 }
00363 if (mpge(ysize, u, v))
00364 {
00365 if (_debug < 0)
00366 fprintf(stderr, "--> 5 (u >= v)\n");
00367 (void) mpsub(ysize, u, v);
00368 (void) mpsub(ysize, A, C);
00369 (void) mpsub(ysize, B, D);
00370 if (_debug < 0)
00371 fprintf(stderr, " u: "), mpfprintln(stderr, ysize, u);
00372 if (_debug < 0)
00373 fprintf(stderr, " A: "), mpfprintln(stderr, ysize, A);
00374 if (_debug < 0)
00375 fprintf(stderr, " B: "), mpfprintln(stderr, ysize, B);
00376 }
00377 else
00378 {
00379 if (_debug < 0)
00380 fprintf(stderr, "--> 5 (u < v)\n");
00381 (void) mpsub(ysize, v, u);
00382 (void) mpsub(ysize, C, A);
00383 (void) mpsub(ysize, D, B);
00384 if (_debug < 0)
00385 fprintf(stderr, " v: "), mpfprintln(stderr, ysize, v);
00386 if (_debug < 0)
00387 fprintf(stderr, " C: "), mpfprintln(stderr, ysize, C);
00388 if (_debug < 0)
00389 fprintf(stderr, " D: "), mpfprintln(stderr, ysize, D);
00390 }
00391
00392 } while (mpnz(ysize, u));
00393
00394 if (!mpisone(ysize, v))
00395 return 0;
00396
00397 if (result)
00398 {
00399 mpsetx(b->size, result, ysize, D);
00400
00401 if (*D & 0x80000000)
00402 (void) mpadd(b->size, result, b->modl);
00403
00404 }
00405
00406 fprintf(stderr, "=== EXIT: "), mpfprintln(stderr, b->size, result);
00407 fprintf(stderr, " u: "), mpfprintln(stderr, ysize, u);
00408 fprintf(stderr, " v: "), mpfprintln(stderr, ysize, v);
00409 fprintf(stderr, " A: "), mpfprintln(stderr, ysize, A);
00410 fprintf(stderr, " B: "), mpfprintln(stderr, ysize, B);
00411 fprintf(stderr, " C: "), mpfprintln(stderr, ysize, C);
00412 fprintf(stderr, " D: "), mpfprintln(stderr, ysize, D);
00413 return 1;
00414 }
00415
00416 static const char * dsa_q = "a1b35510319a59825c721e73e41d687ffe351bc9";
00417 static const char * dsa_s[] = {
00418 "22e917d8a47462c09748e00aebbab5fd93793495",
00419 "0476b30eb86899c6785fad4f7a62e43d59481273",
00420 "8adbca132a0e6a2d2ee5bb2cd837b350c9f8db42",
00421
00422 "026efa7a5a60d29921ec93f503b5c483d131d8c4",
00423 "2e4ec3c986b5a1f8f77b0b9f911d4e1b0ed8d869",
00424
00425 "259e4859e65c2528d3c35eaf2717d8963c834e94",
00426 "45462b3534c2ff7a13f232a4e6e4460c61b2e232",
00427 "0a73e678141aea7b4e5195afb7db3e9ec00f9f85",
00428 NULL
00429 };
00430
00431 static const char * dsa_w_good[]= {
00432 "8b2eeda5fd34067c248bc3262e28f5668e64500b",
00433 "98f6a05c5cc17c2e48faad178d2c21c0bcca694b",
00434 "8ec91350f3237ee249ea009143f692d4cc2f8d2e",
00435
00436 "7db9e81c6f60fdd29243f67b70af7d1d14c9c703",
00437 "6bdc316aef981e45c47dabab904a31747d349eec",
00438
00439 "6d1eaa6c78ad945a1de7bc369f7992e9df3735d9",
00440 "79dc6adee7817e7dc248cfeb4b358e933af6de01",
00441 "2659140a40cb05e85c536a299327addb0a762b8a",
00442 NULL
00443 };
00444
00445 static const char * dsa_w_bad[] = {
00446 "e97b9895cb99acf9c819a4b24a0b8ce6902f3442",
00447 "f7434b4c2b2722abec888ea3a90eb940be954d82",
00448 "ed15be40c189255fed77e21d5fd92a54cdfa7165",
00449
00450 "dc06930c3dc6a45035d1d8078c92149d1694ab3a",
00451 "ca28dc5abdfdc4c3680b8d37ac2cc8f47eff8323",
00452
00453 "cb6b555c47133ad7c1759dc2bb5c2a69e1021a10",
00454 "d82915ceb5e724fb65d6b177671826133cc1c238",
00455 "2659140a40cb05e85c536a299327addb0a762b8a",
00456 NULL
00457 };
00458
00459 static struct poptOption optionsTable[] = {
00460 { "debug", 'd', POPT_ARG_VAL, &_debug, -1, NULL, NULL },
00461 POPT_AUTOHELP
00462 POPT_TABLEEND
00463 };
00464
00465 int
00466 main(int argc, const char * argv[])
00467 {
00468 poptContext optCon = poptGetContext(argv[0], argc, argv, optionsTable, 0);
00469 mpbarrett q;
00470 mpnumber s;
00471 size_t qsize;
00472 mpw* qtemp;
00473 mpw* qwksp;
00474 int rc;
00475 int i;
00476
00477 while ((rc = poptGetNextOpt(optCon)) > 0) {
00478 switch (rc) {
00479 default:
00480 break;
00481 }
00482 }
00483
00484 mpbzero(&q); mpbsethex(&q, dsa_q);
00485 qsize = q.size;
00486 qtemp = malloc((13*qsize+13) * sizeof(*qtemp));
00487 qwksp = qtemp+2*qsize;
00488
00489 for (i = 0; i < 9; i++) {
00490 if (dsa_s[i] == NULL) break;
00491 fprintf(stderr, "================================================== %d\n", i);
00492 fprintf(stderr, " s: %s\n", dsa_s[i]);
00493 mpnzero(&s); mpnsethex(&s, dsa_s[i]);
00494
00495 fprintf(stderr, "-------------------------------------------------- %d\n", i);
00496 rc = Xmpbinv_w(&q, s.size, s.data, qtemp, qwksp);
00497 fprintf(stderr, "beecrypt: "); mpfprintln(stderr, qsize, qtemp);
00498
00499 fprintf(stderr, "-------------------------------------------------- %d\n", i);
00500 rc = Ympbinv_w(&q, s.size, s.data, qtemp, qwksp);
00501 fprintf(stderr, " Knuth: "); mpfprintln(stderr, qsize, qtemp);
00502
00503 fprintf(stderr, "-------------------------------------------------- %d\n", i);
00504 rc = Zmpbinv_w(&q, s.size, s.data, qtemp, qwksp);
00505 fprintf(stderr, " Brent: "); mpfprintln(stderr, qsize, qtemp);
00506
00507 fprintf(stderr, "-------------------------------------------------- %d\n", i);
00508 fprintf(stderr, " q: %s\n", dsa_q);
00509 fprintf(stderr, " s: %s\n", dsa_s[i]);
00510 fprintf(stderr, " GOOD: %s\n", dsa_w_good[i]);
00511 fprintf(stderr, " BAD: %s\n", dsa_w_bad[i]);
00512 }
00513
00514 return 0;
00515
00516 }