1 // Pairing-Based Calculator. 2 // Mainly for demonstration purposes. 3 // 4 // It's times like these I wish C had garbage collection. 5 6 #include <string.h> 7 #include <ctype.h> 8 #include <stdarg.h> 9 #include <unistd.h> //for getopt 10 #include "pbc.h" 11 #include "pbc_z.h" 12 #include "pbc_fp.h" 13 14 #include "misc/darray.h" 15 #include "misc/symtab.h" 16 17 char *pbc_getline(const char *); 18 19 enum { 20 t_none = 0, 21 t_id, 22 t_int, 23 t_string, 24 t_comma, 25 t_lparen, 26 t_rparen, 27 t_add, 28 t_sub, 29 t_mul, 30 t_div, 31 t_set, 32 t_pow, 33 t_unk, 34 t_function, 35 t_pairing, 36 t_element, 37 t_field, 38 t_err, 39 }; 40 41 enum { 42 pe_expect_factor = 100, 43 pe_expect_rparen, 44 pe_arglist, 45 re_varnotfound = 200, 46 re_badlvalue, 47 re_funnotfound, 48 re_unimplemented, 49 re_badargcount, 50 re_badarg, 51 re_fieldmismatch, 52 }; 53 54 static int option_echo = 0; 55 56 static field_t Z; 57 58 static int tok_type; 59 //TODO: dynamic allocation: 60 static char word[1024]; 61 62 struct id_s { 63 char *data; 64 int alloc; 65 }; 66 typedef struct id_s *id_ptr; 67 68 id_ptr id_new(char *id) { 69 id_ptr res = pbc_malloc(sizeof(struct id_s)); 70 res->alloc = strlen(id) + 1; 71 res->data = pbc_malloc(res->alloc); 72 strcpy(res->data, id); 73 return res; 74 } 75 76 void id_delete(id_ptr id) { 77 pbc_free(id->data); 78 pbc_free(id); 79 } 80 81 struct tree_s { 82 int type; 83 void *data; 84 darray_t child; 85 }; 86 typedef struct tree_s *tree_ptr; 87 88 tree_ptr tree_new(int type, void *data) { 89 tree_ptr res = pbc_malloc(sizeof(struct tree_s)); 90 res->type = type; 91 res->data = data; 92 darray_init(res->child); 93 return res; 94 } 95 96 static void delete_child(void *p) { 97 tree_delete(p); 98 } 99 100 void tree_delete(tree_ptr t) { 101 darray_forall(t->child, delete_child); 102 darray_clear(t->child); 103 switch(t->type) { 104 case t_id: 105 case t_string: 106 case t_function: 107 case t_int: 108 id_delete(t->data); 109 break; 110 } 111 pbc_free(t); 112 } 113 114 static char *currentline; 115 static char *lexcp; 116 117 118 static void lex(void) { 119 char c; 120 if (!lexcp) { 121 tok_type = t_none; 122 return; 123 } 124 c = *lexcp++; 125 skipwhitespace: 126 for (;;) { 127 if (!strchr(" \t\r\n", c)) break; 128 if (!c) { 129 tok_type = t_none; 130 return; 131 } 132 c = *lexcp++; 133 } 134 135 //comments start with '#' and end at a newline 136 if (c == '#') { 137 for (;;) { 138 c = *lexcp++; 139 if (!c) { 140 tok_type = t_none; 141 return; 142 } 143 if (c == '\n') break; 144 } 145 goto skipwhitespace; 146 } 147 148 //strings 149 if (c == '"') { 150 tok_type = t_string; 151 int i = 0; 152 for (;;) { 153 c = *lexcp++; 154 if (!c) { 155 //string continues on next line 156 word[i++] = '\n'; 157 pbc_free(currentline); 158 currentline = pbc_getline(NULL); 159 if (!currentline) break; 160 if (option_echo) puts(currentline); 161 lexcp = currentline; 162 c = *lexcp++; 163 } 164 if (c == '"') { 165 break; 166 } 167 word[i++] = c; 168 } 169 word[i] = '\0'; 170 return; 171 } 172 173 if (isdigit(c)) { 174 tok_type = t_int; 175 word[0] = c; 176 177 int i = 1; 178 for (;;) { 179 c = *lexcp++; 180 if (isdigit(c)) { 181 word[i++] = c; 182 } else { 183 word[i] = '\0'; 184 lexcp--; 185 break; 186 } 187 } 188 return; 189 } 190 191 if (isalpha(c) || c == '_') { 192 tok_type = t_id; 193 word[0] = c; 194 195 int i = 1; 196 for (;;) { 197 c = *lexcp++; 198 if (isalnum(c) || c == '_') { 199 word[i++] = c; 200 } else { 201 word[i] = '\0'; 202 lexcp--; 203 break; 204 } 205 } 206 return; 207 } 208 209 switch(c) { 210 case ',': 211 tok_type = t_comma; 212 break; 213 case '=': 214 tok_type = t_set; 215 break; 216 case '^': 217 tok_type = t_pow; 218 break; 219 case '*': 220 tok_type = t_mul; 221 break; 222 case '/': 223 tok_type = t_div; 224 break; 225 case '+': 226 tok_type = t_add; 227 break; 228 case '-': 229 tok_type = t_sub; 230 break; 231 case '(': 232 tok_type = t_lparen; 233 break; 234 case ')': 235 tok_type = t_rparen; 236 break; 237 default: 238 tok_type = t_unk; 239 break; 240 } 241 } 242 243 static int lastparseerror; 244 static void setparseerror(int i) { 245 lastparseerror = i; 246 } 247 248 static tree_ptr parsesetexpr(void); 249 250 static tree_ptr parseexprlist(tree_ptr t) { 251 tree_ptr c; 252 lex(); // expect lparen 253 if (tok_type == t_rparen) { 254 lex(); 255 return t; 256 } 257 c = parsesetexpr(); 258 if (!c) return NULL; 259 darray_append(t->child, c); 260 for (;;) { 261 if (tok_type == t_rparen) { 262 lex(); 263 return t; 264 } 265 if (tok_type != t_comma) { 266 setparseerror(pe_arglist); 267 return NULL; 268 } 269 lex(); //expect comma 270 c = parsesetexpr(); 271 if (!c) return NULL; 272 darray_append(t->child, c); 273 } 274 } 275 276 static tree_ptr parseprimitive(void) { 277 tree_ptr t; 278 switch(tok_type) { 279 id_ptr id; 280 case t_id: 281 id = id_new(word); 282 lex(); 283 if (tok_type == t_lparen) { 284 if (parseexprlist(t = tree_new(t_function, id))) { 285 return t; 286 } 287 tree_delete(t); 288 return NULL; 289 } else { 290 return tree_new(t_id, id); 291 } 292 case t_string: 293 lex(); 294 return tree_new(t_string, id_new(word)); 295 case t_lparen: 296 lex(); 297 t = parsesetexpr(); 298 if (!t) return NULL; 299 if (tok_type != t_rparen) { 300 tree_delete(t); 301 setparseerror(pe_expect_rparen); 302 return NULL; 303 } 304 lex(); 305 return t; 306 case t_int: 307 id = id_new(word); 308 lex(); 309 return tree_new(t_int, id); 310 default: 311 setparseerror(pe_expect_factor); 312 return NULL; 313 } 314 } 315 316 static tree_ptr parsepow(void) { 317 tree_ptr t1; 318 t1 = parseprimitive(); 319 if (tok_type == t_pow) { 320 tree_ptr t2, res; 321 lex(); 322 t2 = parseprimitive(); 323 if (!t2) { 324 tree_delete(t1); 325 return NULL; 326 } 327 res = tree_new(t_function, id_new("pow")); 328 darray_append(res->child, t1); 329 darray_append(res->child, t2); 330 return res; 331 } 332 return t1; 333 } 334 335 static tree_ptr parsefactor(void) { 336 tree_ptr t; 337 if (tok_type == t_sub) { 338 lex(); 339 t = parsefactor(); 340 if (!t) return NULL; 341 tree_ptr t1 = tree_new(t_function, id_new("neg")); 342 darray_append(t1->child, t); 343 return t1; 344 } 345 346 t = parsepow(); 347 return t; 348 } 349 350 static tree_ptr parseterm(void) { 351 tree_ptr t1, t2, res; 352 res = parsefactor(); 353 if (!res) return NULL; 354 for (;;) { 355 switch(tok_type) { 356 case t_mul: 357 lex(); 358 t2 = parsefactor(); 359 if (!t2) { 360 tree_delete(res); 361 return NULL; 362 } 363 t1 = tree_new(t_function, id_new("mul")); 364 darray_append(t1->child, res); 365 darray_append(t1->child, t2); 366 res = t1; 367 break; 368 case t_div: 369 lex(); 370 t2 = parsefactor(); 371 if (!t2) { 372 tree_delete(res); 373 return NULL; 374 } 375 t1 = tree_new(t_function, id_new("div")); 376 darray_append(t1->child, res); 377 darray_append(t1->child, t2); 378 res = t1; 379 break; 380 default: 381 return res; 382 } 383 } 384 } 385 386 static tree_ptr parseexpr(void) { 387 tree_ptr t1, t2, res; 388 res = parseterm(); 389 if (!res) { 390 return NULL; 391 } 392 for (;;) { 393 switch(tok_type) { 394 case t_add: 395 lex(); 396 t2 = parseterm(); 397 if (!t2) { 398 tree_delete(res); 399 return NULL; 400 } 401 //t1 = tree_new(t_add, NULL); 402 t1 = tree_new(t_function, id_new("add")); 403 darray_append(t1->child, res); 404 darray_append(t1->child, t2); 405 res = t1; 406 break; 407 case t_sub: 408 lex(); 409 t2 = parseterm(); 410 if (!t2) { 411 tree_delete(res); 412 return NULL; 413 } 414 //t1 = tree_new(t_sub, NULL); 415 t1 = tree_new(t_function, id_new("sub")); 416 darray_append(t1->child, res); 417 darray_append(t1->child, t2); 418 res = t1; 419 break; 420 default: 421 return res; 422 } 423 } 424 } 425 426 static tree_ptr parsesetexpr(void) { 427 tree_ptr t1, t2, res; 428 t1 = parseexpr(); 429 if (!t1) return NULL; 430 if (tok_type == t_set) { 431 lex(); 432 t2 = parsesetexpr(); 433 if (!t2) { 434 tree_delete(t1); 435 return NULL; 436 } 437 res = tree_new(t_set, NULL); 438 darray_append(res->child, t1); 439 darray_append(res->child, t2); 440 return res; 441 } 442 return t1; 443 } 444 445 static void print_tree(tree_ptr t) { 446 id_ptr id; 447 int i; 448 if (!t) { 449 printf("NULL"); 450 return; 451 } 452 switch (t->type) { 453 case t_set: 454 print_tree(t->child->item[0]); 455 printf(" = "); 456 print_tree(t->child->item[1]); 457 break; 458 case t_id: 459 id = t->data; 460 printf("%s", id->data); 461 break; 462 case t_function: 463 id = t->data; 464 printf("%s(", id->data); 465 for (i=0; i<t->child->count; i++) { 466 print_tree(t->child->item[i]); 467 if (i < t->child->count - 1) printf(", "); 468 } 469 printf(")"); 470 break; 471 default: 472 printf("?!?"); 473 break; 474 } 475 } 476 477 static symtab_t var; 478 static symtab_t builtin; 479 480 struct val_s { 481 int type; 482 void *data; 483 }; 484 typedef struct val_s *val_ptr; 485 486 static int lastruntimeerror; 487 static val_ptr newruntimeerror(int i) { 488 val_ptr res = pbc_malloc(sizeof(struct val_s)); 489 lastruntimeerror = i; 490 res->type = t_err; 491 res->data = int_to_voidp(i); 492 return res; 493 } 494 495 val_ptr val_new(int type, void *data) { 496 val_ptr res = pbc_malloc(sizeof(struct val_s)); 497 res->type = type; 498 res->data = data; 499 return res; 500 } 501 502 static void val_print(val_ptr v) { 503 pairing_ptr pairing; 504 field_ptr field; 505 element_ptr e; 506 switch (v->type) { 507 case t_element: 508 e = v->data; 509 element_out_str(stdout, 0, e); 510 printf("\n"); 511 break; 512 case t_pairing: 513 pairing = v->data; 514 printf("pairing: G1bits=%d G2bits=%d GTbits=%d\n", 515 pairing_length_in_bytes_x_only_G1(pairing) * 8, 516 pairing_length_in_bytes_x_only_G2(pairing) * 8, 517 pairing_length_in_bytes_GT(pairing) * 8); 518 break; 519 case t_field: 520 field = v->data; 521 field_out_info(stdout, field); 522 break; 523 case t_string: 524 printf("%s", (char *) v->data); 525 break; 526 default: 527 printf("val type %d unknown\n", v->type); 528 break; 529 } 530 } 531 532 val_ptr val_copy(val_ptr v) { 533 val_ptr res = pbc_malloc(sizeof(struct val_s)); 534 res->type = v->type; 535 if (v->type == t_element) { 536 //current policy: always clear elements, always copy elements 537 res->data = pbc_malloc(sizeof(element_t)); 538 element_ptr e = v->data; 539 element_init(res->data, e->field); 540 element_set(res->data, e); 541 } else if (v->type == t_string) { 542 res->data = pbc_strdup(v->data); 543 } else { 544 res->data = v->data; 545 } 546 547 return res; 548 } 549 550 void val_delete(val_ptr v) { 551 switch(v->type) { 552 case t_element: 553 //current policy: always clear elements, always copy elements 554 element_clear(v->data); 555 pbc_free(v->data); 556 break; 557 case t_string: 558 pbc_free(v->data); 559 break; 560 case t_err: 561 break; 562 case t_pairing: 563 break; 564 case t_field: 565 break; 566 default: 567 printf("val_delete: case %d not handled: memory leak\n", v->type); 568 break; 569 } 570 pbc_free(v); 571 } 572 573 struct fun_s { 574 val_ptr (*f)(darray_ptr); 575 int arity; 576 int type[32]; //TODO: replace with darray? who needs more than 32 args? 577 }; 578 579 typedef val_ptr (*fun)(darray_ptr); 580 581 static val_ptr check_arg(darray_ptr arg, int n, ...) { 582 va_list ap; 583 int i; 584 val_ptr res = NULL; 585 586 va_start(ap, n); 587 if (arg->count != n) { 588 printf("expect %d argument(s)\n", n); 589 res = newruntimeerror(re_badargcount); 590 } else for (i=0; i<n; i++) { 591 int t = va_arg(ap, int); 592 val_ptr vp = arg->item[i]; 593 if (vp->type != t) { 594 printf("arg not type %d\n", t); 595 return newruntimeerror(re_badarg); 596 break; 597 } 598 } 599 600 va_end(ap); 601 return res; 602 } 603 604 static val_ptr f_pairing_get_group( 605 field_ptr (*get_group)(pairing_ptr p), darray_ptr arg) { 606 val_ptr res; 607 res = check_arg(arg, 1, t_pairing); 608 if (res) return res; 609 val_ptr a0 = arg->item[0]; 610 pairing_ptr pairing = a0->data; 611 res = val_new(t_field, get_group(pairing)); 612 return res; 613 } 614 615 static val_ptr f_pairing_G1(darray_ptr arg) { 616 field_ptr getG1(pairing_ptr p) { return p->G1; } 617 return f_pairing_get_group(getG1, arg); 618 } 619 620 static val_ptr f_pairing_G2(darray_ptr arg) { 621 field_ptr getG2(pairing_ptr p) { return p->G2; } 622 return f_pairing_get_group(getG2, arg); 623 } 624 625 static val_ptr f_pairing_GT(darray_ptr arg) { 626 field_ptr getGT(pairing_ptr p) { return p->GT; } 627 return f_pairing_get_group(getGT, arg); 628 } 629 630 static val_ptr f_pairing_Zr(darray_ptr arg) { 631 field_ptr getZr(pairing_ptr p) { return p->Zr; } 632 return f_pairing_get_group(getZr, arg); 633 } 634 635 static val_ptr f_random(darray_ptr arg) { 636 val_ptr res; 637 res = check_arg(arg, 1, t_field); 638 if (res) return res; 639 val_ptr a0 = arg->item[0]; 640 field_ptr f = a0->data; 641 element_ptr e = pbc_malloc(sizeof(element_t)); 642 element_init(e, f); 643 element_random(e); 644 res = val_new(t_element, e); 645 return res; 646 } 647 648 static val_ptr f_order(darray_ptr arg) { 649 val_ptr res; 650 res = check_arg(arg, 1, t_field); 651 if (res) return res; 652 val_ptr a0 = arg->item[0]; 653 field_ptr f = a0->data; 654 655 element_ptr e = pbc_malloc(sizeof(element_t)); 656 element_init(e, Z); 657 element_set_mpz(e, f->order); 658 res = val_new(t_element, e); 659 return res; 660 } 661 662 static val_ptr f_unary( 663 void (*unary)(element_ptr, element_ptr), darray_ptr arg) { 664 val_ptr res; 665 res = check_arg(arg, 1, t_element); 666 if (res) return res; 667 val_ptr a0 = arg->item[0]; 668 element_ptr e0 = a0->data; 669 element_ptr e = pbc_malloc(sizeof(element_t)); 670 element_init(e, e0->field); 671 unary(e, e0); 672 res = val_new(t_element, e); 673 return res; 674 } 675 676 static val_ptr f_bin_op( 677 void (*binop)(element_ptr, element_ptr, element_ptr), 678 darray_ptr arg) { 679 val_ptr res; 680 res = check_arg(arg, 2, t_element, t_element); 681 if (res) return res; 682 val_ptr a0 = arg->item[0]; 683 val_ptr a1 = arg->item[1]; 684 element_ptr e0 = a0->data; 685 element_ptr e1 = a1->data; 686 if (e0->field != e1->field) { 687 printf("field mismatch!\n"); 688 return newruntimeerror(re_fieldmismatch); 689 } 690 element_ptr e = pbc_malloc(sizeof(element_t)); 691 element_init(e, e0->field); 692 binop(e, e0, e1); 693 res = val_new(t_element, e); 694 return res; 695 } 696 697 698 static val_ptr f_add(darray_ptr arg) { 699 return f_bin_op(element_add, arg); 700 } 701 702 static val_ptr f_mul(darray_ptr arg) { 703 return f_bin_op(element_mul, arg); 704 } 705 706 static val_ptr f_sub(darray_ptr arg) { 707 return f_bin_op(element_sub, arg); 708 } 709 710 static val_ptr f_div(darray_ptr arg) { 711 return f_bin_op(element_div, arg); 712 } 713 714 static val_ptr f_inv(darray_ptr arg) { 715 return f_unary(element_invert, arg); 716 } 717 718 static val_ptr f_neg(darray_ptr arg) { 719 return f_unary(element_neg, arg); 720 } 721 722 static val_ptr f_pow(darray_ptr arg) { 723 val_ptr res; 724 res = check_arg(arg, 2, t_element, t_element); 725 if (res) return res; 726 val_ptr a0 = arg->item[0]; 727 val_ptr a1 = arg->item[1]; 728 element_ptr e0 = a0->data; 729 element_ptr e1 = a1->data; 730 element_ptr e = pbc_malloc(sizeof(element_t)); 731 mpz_t z; 732 mpz_init(z); 733 element_to_mpz(z, e1); 734 element_init(e, e0->field); 735 element_pow_mpz(e, e0, z); 736 res = val_new(t_element, e); 737 mpz_clear(z); 738 return res; 739 } 740 741 static pairing_ptr current_pairing; 742 static val_ptr f_pairing(darray_ptr arg) { 743 val_ptr res; 744 if (arg->count != 2) { 745 printf("expect two arguments\n"); 746 return newruntimeerror(re_badargcount); 747 } 748 val_ptr a0 = arg->item[0]; 749 val_ptr a1 = arg->item[1]; 750 if (a0->type != t_element) { 751 printf("arg 1 not element!\n"); 752 return newruntimeerror(re_badarg); 753 } 754 if (a1->type != t_element) { 755 printf("arg 2 not element!\n"); 756 return newruntimeerror(re_badarg); 757 } 758 pairing_ptr p; 759 element_ptr e0 = a0->data; 760 element_ptr e1 = a1->data; 761 p = e0->field->pairing; 762 if (e0->field != p->G1) { 763 printf("arg 1 not from G1!\n"); 764 return newruntimeerror(re_badarg); 765 } 766 if (e1->field != p->G2) { 767 printf("arg 2 not from G2!\n"); 768 return newruntimeerror(re_badarg); 769 } 770 element_ptr e = pbc_malloc(sizeof(element_t)); 771 element_init(e, p->GT); 772 pairing_apply(e, e0, e1, p); 773 res = val_new(t_element, e); 774 return res; 775 } 776 777 static val_ptr execute_tree(tree_ptr t) { 778 darray_t arg; 779 id_ptr id; 780 fun fn; 781 int i; 782 val_ptr res, v; 783 tree_ptr t1, t2; 784 785 switch (t->type) { 786 case t_id: 787 id = t->data; 788 v = symtab_at(var, id->data); 789 if (!v) { 790 return newruntimeerror(re_varnotfound); 791 } 792 return val_copy(v); 793 case t_set: 794 t1 = t->child->item[0]; 795 if (t1->type != t_id) { 796 return newruntimeerror(re_badlvalue); 797 } 798 t2 = t->child->item[1]; 799 v = execute_tree(t2); 800 if (v->type == t_err) return v; 801 id = t1->data; 802 // clear what's there first 803 if ((res = symtab_at(var, id->data))) { 804 val_delete(res); 805 } 806 symtab_put(var, v, id->data); 807 v = symtab_at(var, id->data); 808 return val_copy(v); 809 case t_function: 810 id = t->data; 811 fn = symtab_at(builtin, id->data); 812 if (!fn) { 813 return newruntimeerror(re_funnotfound); 814 } 815 darray_init(arg); 816 for (i=0; i<t->child->count; i++) { 817 v = execute_tree(t->child->item[i]); 818 if (v->type == t_err) { 819 darray_forall(arg, (void (*)(void *)) val_delete); 820 return v; 821 } 822 darray_append(arg, v); 823 } 824 res = fn(arg); 825 for (i=0; i<arg->count; i++) { 826 val_delete(arg->item[i]); 827 } 828 darray_clear(arg); 829 return res; 830 case t_int: 831 id = t->data; 832 char *cp; 833 mpz_t z; 834 mpz_init(z); 835 for (cp = id->data; *cp; cp++) { 836 mpz_mul_ui(z, z, 10); 837 mpz_add_ui(z, z, *cp - '0'); 838 } 839 element_ptr e = pbc_malloc(sizeof(element_t)); 840 element_init(e, Z); 841 element_set_mpz(e, z); 842 mpz_clear(z); 843 return val_new(t_element, e); 844 case t_string: 845 id = t->data; 846 return val_new(t_string, pbc_strdup(id->data)); 847 default: 848 return newruntimeerror(re_unimplemented); 849 } 850 } 851 852 static void parseline(void) { 853 val_ptr v; 854 855 tree_ptr t; 856 lex(); 857 if (tok_type == t_none) return; 858 t = parsesetexpr(); 859 if (0) { 860 print_tree(t); 861 printf("\n"); 862 } 863 if (t) { 864 v = execute_tree(t); 865 if (v) { 866 if (v->type == t_err) { 867 printf("runtime error (error code = %d)\n", lastruntimeerror); 868 } else { 869 if (t->type != t_set) val_print(v); 870 } 871 val_delete(v); 872 } 873 tree_delete(t); 874 } else { 875 printf("parse error (error code = %d)\n", lastparseerror); 876 } 877 } 878 879 static char *aparam = 880 "type a\n" 881 "q 8780710799663312522437781984754049815806883199414208211028653399266475630880222957078625179422662221423155858769582317459277713367317481324925129998224791\n" 882 "h 12016012264891146079388821366740534204802954401251311822919615131047207289359704531102844802183906537786776\n" 883 "r 730750818665451621361119245571504901405976559617\n" 884 "exp2 159\n" 885 "exp1 107\n" 886 "sign1 1\n" 887 "sign0 1\n"; 888 889 static char *dparam = 890 "type d\n" 891 "q 625852803282871856053922297323874661378036491717\n" 892 "n 625852803282871856053923088432465995634661283063\n" 893 "h 3\n" 894 "r 208617601094290618684641029477488665211553761021\n" 895 "a 581595782028432961150765424293919699975513269268\n" 896 "b 517921465817243828776542439081147840953753552322\n" 897 "k 6\n" 898 "nk 60094290356408407130984161127310078516360031868417968262992864809623507269833854678414046779817844853757026858774966331434198257512457993293271849043664655146443229029069463392046837830267994222789160047337432075266619082657640364986415435746294498140589844832666082434658532589211525696\n" 899 "hk 1380801711862212484403205699005242141541629761433899149236405232528956996854655261075303661691995273080620762287276051361446528504633283152278831183711301329765591450680250000592437612973269056\n" 900 "coeff0 472731500571015189154958232321864199355792223347\n" 901 "coeff1 352243926696145937581894994871017455453604730246\n" 902 "coeff2 289113341693870057212775990719504267185772707305\n" 903 "nqr 431211441436589568382088865288592347194866189652\n"; 904 905 static char *eparam = 906 "type e\n" 907 "q 7245986106510086080714203333362098431608853335867425877960916928496629182991629664903654100214900946450053872786629995869445693724001299041657434948257845644905153122838458864000479326695430719258600053239930483226650953770354174712511646273516974069245462534034085895319225452125649979474047163305307830001\n" 908 "r 730750862221594424981965739670091261094297337857\n" 909 "h 13569343110918781839835249021482970252603216587988030044836106948825516930173270978617489032334001006615524543925753725725046733884363846960470444404747241287743773746682188521738728797153760275116924829183670000\n" 910 "a 7130970454025799000067946137594446075551569949583815943390108723282396973737794273397246892274981883807989525599540630855644968426794929215599380425269625872763801485968007136000471718335185787206876242871042697778608875139078711621836858237429403052273312335081163896980825048123655535355411494046493419999\n" 911 "b 7169309004853894693616698536183663527570664411678352588247044791687141043489072737232715961588288238022010974661903752526911876859197052490952065266265699130144252031591491045333807587788600764557450846327338626261289568016170532652061787582791926724597362401398804563093625182790987016728290050466098223333\n" 912 "exp2 159\n" 913 "exp1 135\n" 914 "sign1 1\n" 915 "sign0 1\n"; 916 917 static char *fparam = 918 "type f\n" 919 "q 205523667896953300194896352429254920972540065223\n" 920 "r 205523667896953300194895899082072403858390252929\n" 921 "b 40218105156867728698573668525883168222119515413\n" 922 "beta 115334401956802802075595682801335644058796914268\n" 923 "alpha0 191079354656274778837764015557338301375963168470\n" 924 "alpha1 71445317903696340296199556072836940741717506375\n"; 925 926 static char *gparam = 927 "type g\n" 928 "q 503189899097385532598615948567975432740967203\n" 929 "n 503189899097385532598571084778608176410973351\n" 930 "h 1\n" 931 "r 503189899097385532598571084778608176410973351\n" 932 "a 465197998498440909244782433627180757481058321\n" 933 "b 463074517126110479409374670871346701448503064\n" 934 "k 10\n" 935 "nk 1040684643531490707494989587381629956832530311976146077888095795458709511789670022388326295177424065807612879371896982185473788988016190582073591316127396374860265835641044035656044524481121528846249501655527462202999638159773731830375673076317719519977183373353791119388388468745670818193868532404392452816602538968163226713846951514831917487400267590451867746120591750902040267826351982737642689423713163967384383105678367875981348397359466338807\n" 936 "hk 4110127713690841149713310614420858884651261781185442551927080083178682965171097172366598236129731931693425629387502221804555636704708008882811353539555915064049685663790355716130262332064327767695339422323460458479884756000782939428852120522712008037615051139080628734566850259704397643028017435446110322024094259858170303605703280329322675124728639532674407\n" 937 "coeff0 67343110967802947677845897216565803152319250\n" 938 "coeff1 115936772834120270862756636148166314916823221\n" 939 "coeff2 87387877425076080433559927080662339215696505\n" 940 "coeff3 433223145899090928132052677121692683015058909\n" 941 "coeff4 405367866213598664862417230702935310328613596\n" 942 "nqr 22204504160560785687198080413579021865783099\n"; 943 944 static pairing_t pairing_A, pairing_D, pairing_E, pairing_F, pairing_G; 945 946 static void set_pairing_groups(pairing_ptr p) { 947 symtab_put(var, val_new(t_field, p->G1), "G1"); 948 symtab_put(var, val_new(t_field, p->G2), "G2"); 949 symtab_put(var, val_new(t_field, p->GT), "GT"); 950 symtab_put(var, val_new(t_field, p->Zr), "Zr"); 951 symtab_put(var, val_new(t_pairing, p), "current_pairing"); 952 current_pairing = p; 953 } 954 955 static val_ptr f_init_pairing(darray_ptr arg) { 956 val_ptr res; 957 958 res = check_arg(arg, 1, t_pairing); 959 if (res) return res; 960 961 val_ptr a0 = arg->item[0]; 962 pairing_ptr p = a0->data; 963 set_pairing_groups(p); 964 return NULL; 965 } 966 967 static val_ptr f_nextprime(darray_ptr arg) { 968 mpz_t p; 969 val_ptr res; 970 971 res = check_arg(arg, 1, t_element); 972 if (res) return res; 973 val_ptr a0 = arg->item[0]; 974 element_ptr e0 = a0->data; 975 if (e0->field != Z) { 976 printf("arg not integer!\n"); 977 return newruntimeerror(re_badarg); 978 } 979 element_ptr e = pbc_malloc(sizeof(element_t)); 980 element_init(e, Z); 981 mpz_init(p); 982 element_to_mpz(p, e0); 983 mpz_nextprime(p, p); 984 element_set_mpz(e, p); 985 res = val_new(t_element, e); 986 mpz_clear(p); 987 return res; 988 } 989 990 static val_ptr f_brute_force_dlog(darray_ptr arg) { 991 val_ptr res; 992 res = check_arg(arg, 2, t_element, t_element); 993 if (res) return res; 994 val_ptr a0 = arg->item[0]; 995 val_ptr a1 = arg->item[1]; 996 element_ptr e0 = a0->data; 997 element_ptr e1 = a1->data; 998 if (e0->field != e1->field) { 999 printf("arg field mismatch!\n"); 1000 return newruntimeerror(re_badarg); 1001 } 1002 element_ptr e = pbc_malloc(sizeof(element_t)); 1003 element_init(e, Z); 1004 element_dlog_brute_force(e, e0, e1); 1005 res = val_new(t_element, e); 1006 return res; 1007 } 1008 static val_ptr f_pollard_rho(darray_ptr arg) { 1009 val_ptr res; 1010 res = check_arg(arg, 3, t_element, t_element, t_field); 1011 if (res) return res; 1012 val_ptr a0 = arg->item[0]; 1013 val_ptr a1 = arg->item[1]; 1014 val_ptr a2 = arg->item[2]; 1015 element_ptr e0 = a0->data; 1016 element_ptr e1 = a1->data; 1017 if (e0->field != e1->field) { 1018 printf("arg field mismatch!\n"); 1019 return newruntimeerror(re_badarg); 1020 } 1021 field_ptr f = a2->data; 1022 element_ptr e = pbc_malloc(sizeof(element_t)); 1023 element_init(e, f); 1024 element_dlog_pollard_rho(e, e0, e1); 1025 res = val_new(t_element, e); 1026 return res; 1027 } 1028 1029 static val_ptr f_zz(darray_ptr arg) { 1030 mpz_t p; 1031 val_ptr res; 1032 res = check_arg(arg, 1, t_element); 1033 if (res) return res; 1034 val_ptr a0 = arg->item[0]; 1035 element_ptr e0 = a0->data; 1036 if (e0->field != Z) { 1037 printf("arg not integer!\n"); 1038 return newruntimeerror(re_badarg); 1039 } 1040 field_ptr f = pbc_malloc(sizeof(field_t)); 1041 mpz_init(p); 1042 element_to_mpz(p, e0); 1043 field_init_fp(f, p); 1044 res = val_new(t_field, f); 1045 mpz_clear(p); 1046 return res; 1047 } 1048 1049 static val_ptr f_gen_A(darray_ptr arg) { 1050 mpz_t rbits, qbits; 1051 pairing_ptr p; 1052 val_ptr res; 1053 res = check_arg(arg, 2, t_element, t_element); 1054 if (res) return res; 1055 val_ptr a0 = arg->item[0]; 1056 val_ptr a1 = arg->item[1]; 1057 element_ptr e0 = a0->data; 1058 if (e0->field != Z) { 1059 printf("arg not integer!\n"); 1060 return newruntimeerror(re_badarg); 1061 } 1062 element_ptr e1 = a1->data; 1063 if (e1->field != Z) { 1064 printf("arg not integer!\n"); 1065 return newruntimeerror(re_badarg); 1066 } 1067 mpz_init(rbits); 1068 mpz_init(qbits); 1069 element_to_mpz(rbits, e0); 1070 element_to_mpz(qbits, e1); 1071 //TODO: check rbits and qbits aren't too big 1072 pbc_param_t param; 1073 pbc_param_init_a_gen(param, mpz_get_ui(rbits), mpz_get_ui(qbits)); 1074 p = pbc_malloc(sizeof(pairing_t)); 1075 pairing_init_pbc_param(p, param); 1076 res = val_new(t_pairing, p); 1077 mpz_clear(rbits); 1078 mpz_clear(qbits); 1079 pbc_param_clear(param); 1080 return res; 1081 } 1082 1083 static val_ptr f_fromZZ(darray_ptr arg) { 1084 val_ptr res; 1085 res = check_arg(arg, 2, t_element, t_field); 1086 if (res) return res; 1087 val_ptr a0 = arg->item[0]; 1088 val_ptr a1 = arg->item[1]; 1089 element_ptr e = a0->data; 1090 field_ptr f = a1->data; 1091 if (e->field != Z) { 1092 printf("arg not integer!\n"); 1093 return newruntimeerror(re_badarg); 1094 } 1095 element_ptr e1 = pbc_malloc(sizeof(element_t)); 1096 element_init(e1, f); 1097 element_set_mpz(e1, e->data); 1098 res = val_new(t_element, e1); 1099 return res; 1100 } 1101 1102 static val_ptr f_fromstr(darray_ptr arg) { 1103 val_ptr res; 1104 res = check_arg(arg, 2, t_string, t_field); 1105 if (res) return res; 1106 val_ptr a0 = arg->item[0]; 1107 val_ptr a1 = arg->item[1]; 1108 field_ptr f = a1->data; 1109 element_ptr e1 = pbc_malloc(sizeof(element_t)); 1110 element_init(e1, f); 1111 element_set_str(e1, a0->data, 0); 1112 res = val_new(t_element, e1); 1113 return res; 1114 } 1115 1116 /* I'll probably never finish this :( 1117 static val_ptr f_index_calculus(darray_ptr arg) { 1118 val_ptr res; 1119 res = check_arg(arg, 2, t_element, t_element); 1120 if (res) return res; 1121 val_ptr a0 = arg->item[0]; 1122 val_ptr a1 = arg->item[1]; 1123 element_ptr e0 = a0->data; 1124 element_ptr e1 = a1->data; 1125 element_ptr e = pbc_malloc(sizeof(element_t)); 1126 mpz_t x, g, h, q1; 1127 1128 //TODO: check e0, e1 are from an integer mod ring 1129 mpz_init(x); 1130 mpz_init(g); 1131 mpz_init(h); 1132 mpz_init(q1); 1133 1134 mpz_sub_ui(q1, e0->field->order, 1); 1135 1136 element_init(e, Z); 1137 element_to_mpz(g, e0); 1138 element_to_mpz(h, e1); 1139 pbc_mpz_index_calculus(x, g, h, q1); 1140 element_set_mpz(e, x); 1141 res = val_new(t_element, e); 1142 mpz_clear(x); 1143 mpz_clear(g); 1144 mpz_clear(h); 1145 mpz_clear(q1); 1146 return res; 1147 } 1148 */ 1149 1150 int main(int argc, char **argv) { 1151 for (;;) { 1152 int c = getopt(argc, argv, "e"); 1153 if (c == -1) break; 1154 switch (c) { 1155 case 'e': 1156 option_echo = 1; 1157 break; 1158 default: 1159 fprintf(stderr, "unrecognized option: %c\n", c); 1160 break; 1161 } 1162 } 1163 1164 symtab_init(var); 1165 symtab_init(builtin); 1166 1167 pairing_init_set_str(pairing_A, aparam); 1168 pairing_init_set_str(pairing_D, dparam); 1169 pairing_init_set_str(pairing_E, eparam); 1170 pairing_init_set_str(pairing_F, fparam); 1171 pairing_init_set_str(pairing_G, gparam); 1172 symtab_put(var, val_new(t_pairing, pairing_A), "A"); 1173 symtab_put(var, val_new(t_pairing, pairing_D), "D"); 1174 symtab_put(var, val_new(t_pairing, pairing_E), "E"); 1175 symtab_put(var, val_new(t_pairing, pairing_F), "F"); 1176 symtab_put(var, val_new(t_pairing, pairing_G), "G"); 1177 1178 set_pairing_groups(pairing_A); 1179 1180 symtab_put(builtin, f_init_pairing, "init_pairing"); 1181 symtab_put(builtin, f_pairing_G1, "get_G1"); 1182 symtab_put(builtin, f_pairing_G2, "get_G2"); 1183 symtab_put(builtin, f_pairing_GT, "get_GT"); 1184 symtab_put(builtin, f_pairing_Zr, "get_Zr"); 1185 symtab_put(builtin, f_random, "random"); 1186 symtab_put(builtin, f_random, "rand"); 1187 symtab_put(builtin, f_random, "rnd"); 1188 symtab_put(builtin, f_order, "order"); 1189 symtab_put(builtin, f_order, "ord"); 1190 symtab_put(builtin, f_neg, "neg"); 1191 symtab_put(builtin, f_sub, "sub"); 1192 symtab_put(builtin, f_add, "add"); 1193 symtab_put(builtin, f_pow, "pow"); 1194 symtab_put(builtin, f_mul, "mul"); 1195 symtab_put(builtin, f_inv, "inv"); 1196 symtab_put(builtin, f_inv, "invert"); 1197 symtab_put(builtin, f_div, "div"); 1198 symtab_put(builtin, f_pairing, "pairing"); 1199 symtab_put(builtin, f_nextprime, "nextprime"); 1200 symtab_put(builtin, f_brute_force_dlog, "element_dlog_brute_force"); 1201 symtab_put(builtin, f_pollard_rho, "element_dlog_pollard_rho"); 1202 //symtab_put(builtin, f_index_calculus, "index_calculus"); 1203 symtab_put(builtin, f_zz, "ZZ"); 1204 symtab_put(builtin, f_gen_A, "gen_A"); 1205 symtab_put(builtin, f_fromZZ, "fromZZ"); 1206 symtab_put(builtin, f_fromstr, "fromstr"); 1207 1208 field_init_z(Z); 1209 1210 fprintf(stderr, "pbc\n"); 1211 1212 for (;;) { 1213 currentline = pbc_getline(NULL); 1214 if (!currentline) break; 1215 if (option_echo) puts(currentline); 1216 lexcp = currentline; 1217 parseline(); 1218 free(currentline); 1219 } 1220 return 0; 1221 } 1222