/***************************************************************** ** Cracking linear congruence generators ** ** using the algorithm of ** ** Joan B. Plumstead: ** ** Inferring a sequence generated by a linear congruence. ** ** Proc. 23rd IEEE symposium on the Foundations of Computer ** ** Science (1982), 153-159. ** ** ** ** Input is taken from the file `zuftab', up to MAXNR numbers. ** ** ** ** Implementation: Klaus Pommerening, Nov 5, 1992 ** *****************************************************************/ #include #include #include #define MAXNR 32 #define MAXLG 1024 void printMP(char *description, MP_INT *x) { printf("%s", description); mpz_out_str(stdout, 10, x); printf("\n"); } unsigned PlumA(unsigned n, MP_INT x[], MP_INT *a) /*************************************************************** ** Calculates a possible multiplicator a. ** ** Input: a list x of n+1 lcg-generated numbers ** ** Return value: last used index if successful, ** ** 0 else ** ***************************************************************/ { MP_INT y, e, e0, z, r, s; unsigned t; int rc; if (n <= 0) {mpz_set_ui(a,0); return 0;} mpz_init(&y); mpz_sub(&y,&x[1],&x[0]); printMP("difference: ",&y); if (!(mpz_cmp_ui(&y,0))) {mpz_set_ui(a,1); mpz_clear(&y); return 1;} if (n <= 1) {mpz_set_ui(a,0); mpz_clear(&y); return 0;} mpz_init_set(&e,&y); printMP("gcd: ", &e); mpz_sub(&y,&x[2],&x[1]); printMP("difference: ",&y); mpz_init_set(&z,&y); rc = 0; mpz_init(&e0); mpz_init(&r); mpz_init(&s); for (t = 2; t <= n; t++) { mpz_gcdext(&e0,&r,&s,&e,&y); if (mpz_cmp_ui(&e0,0) < 0) { mpz_neg(&e0,&e0); mpz_neg(&r,&r); mpz_neg(&s,&s); } printMP("gcd: ", &e0); if (!(mpz_cmp(&e0,&e))) {rc = t; t = n;} else if (t == n) { printf("End of list. No success.\n"); rc = 0;} else { mpz_set(&e,&e0); mpz_sub(&y,&x[t+1],&x[t]); printMP("difference: ",&y); mpz_mul(&r,&r,&z); mpz_mul(&s,&s,&y); mpz_add(&z,&r,&s); } } if (rc) mpz_div(a,&z,&e); else mpz_set_ui(a,0); printMP("multiplicator: ",a); mpz_clear(&s); mpz_clear(&r); mpz_clear(&e0); mpz_clear(&z); mpz_clear(&e); mpz_clear(&y); return rc; } unsigned PlumM(unsigned n, MP_INT x[], MP_INT *a, MP_INT *m, int *rc) /*************************************************************** ** Calculates a possible module m, given a possible ** ** multiplicator a. ** ** Input: a list x of n+1 lcg-generated numbers and a. ** ** Return value: last used index if successful, ** ** 0 else ** ** rc indicates success: 0 -- m is the correct module, ** ** 1 -- the returned m might be a ** ** multiple of the true m ** ***************************************************************/ { MP_INT mx, mx2, y, yy; unsigned j; if (n <= 1) {mpz_set_ui(m,0); *rc = 1; return 0;} *rc = 0; mpz_init(&y); mpz_sub(&y,&x[1],&x[0]); if (mpz_cmp_si(&y,0) > 0) mpz_init_set(&mx,&x[1]); else mpz_init_set(&mx,&x[0]); printMP("new maximum: ", &mx); mpz_init(&yy); j = 2; do { if (j > n) *rc = 1; else { mpz_mul(&yy,a,&y); printMP("predicted difference: ", &yy); mpz_sub(&y,&x[j],&x[j-1]); printMP("true difference: ", &y); if (mpz_cmp(&x[j],&mx) > 0) mpz_set(&mx,&x[j]); printMP("new maximum: ", &mx); j++; } } while (!mpz_cmp(&yy,&y) && !(*rc)); if (*rc) {mpz_set_ui(m,0); return j-1;} mpz_sub(&yy,&yy,&y); mpz_abs(m,&yy); printMP("new module: ", m); mpz_mmod(a,a,m); printMP("new multiplicator: ", a); mpz_init(&mx2); mpz_mul_ui(&mx2,&mx,2); while ((mpz_cmp(m,&mx2) > 0) && !(*rc)) { if (j > n) {*rc = 1; j = 1;} else { mpz_mul(&yy,a,&y); mpz_mmod(&yy,&yy,m); printMP("predicted difference: ", &yy); mpz_sub(&y,&x[j],&x[j-1]); printMP("true difference: ", &y); if (mpz_cmp(&x[j],&mx) > 0) mpz_set(&mx,&x[j]); printMP("new maximum: ", &mx); mpz_sub(&yy,&yy,&y); mpz_abs(&yy,&yy); if (mpz_cmp_si(&yy,0)) { mpz_gcd(m,m,&yy); printMP("new module: ", m); mpz_mmod(a,a,m); printMP("new multiplicator: ", a); } j++; } } mpz_clear(&yy); mpz_clear(&y); mpz_clear(&mx); mpz_clear(&mx2); return j-1; } void main() { MP_INT u[MAXNR]; MP_INT a, b, m, x; FILE *infile; unsigned n, i, rc, q, j; char *buf = (char *) malloc(MAXLG); int fail; if (!(infile = fopen("zuftab", "r"))) { fprintf(stderr,"File doesn't exist.\n"); exit(1);} n = 0; while((fgets(buf,MAXLG-1,infile)) && (n < MAXNR)) { mpz_init_set_str(&u[n],buf,10); n++;} fclose(infile); mpz_init(&a); if (n) {n--; rc = PlumA(n,u,&a);} else rc = 1; if (!rc) {printf("No multiplicator found.\n"); exit(1);} printf("Multiplicator found from %d members,\n", rc+1); printMP("namely: ",&a); mpz_init(&m); rc = PlumM(n,u,&a,&m,&fail); printf("Module guessed from %d members;\n", rc+1); if (fail) printMP("a multiple of the module is: ", &m); else printMP("the module is: ", &m); mpz_init(&b); mpz_mul(&b,&a,&u[0]); mpz_sub(&b,&u[1],&b); if (mpz_cmp_ui(&m,0)) mpz_mmod(&b,&b,&m); printMP("Increment: ", &b); rc = 1; mpz_init_set(&x,&u[0]); for (i = 0; i < n; i++) { mpz_mul(&x,&a,&x); mpz_add(&x,&x,&b); if (mpz_cmp_ui(&m,0)) mpz_mmod(&x,&x,&m); if (mpz_cmp(&x,&u[i+1])) { printf("The %d-th member is wrongly predicted.\n",i+1); printMP("predicted: ", &x); printMP("instead of: ", &u[i+1]); printf("The guessed parameters are not correct.\n"); rc = 0; } } if (rc) { printf("The known numbers are correctly predicted.\n"); printf("Predict more numbers? How many: "); scanf("%d", &q); for (j = 0; j < q; j++) { mpz_mul(&x,&a,&x); mpz_add(&x,&x,&b); if (mpz_cmp_ui(&m,0)) mpz_mmod(&x,&x,&m); printMP("prediction ", &x); } } mpz_clear(&a); mpz_clear(&m); mpz_clear(&b); mpz_clear(&x); for (i = 0; i <= n; i++) mpz_clear(&u[i]); exit(0); }