cat source.c
/* mastersearch.c May 3, 1987 */
/* Steps a user through generation of primes which it then uses to create
a masterkey and totient function value of the masterkey.  It then generates
a series of modular inverses (modulo the totient value) which are the
encryption/decryption keys for an rsa function for that masterkey  */

/* Includes euc(). Euc() is a function that implements
Euclid's algorithm and is used to test for relative primality */

char *xero = "0000000000000" ;
char *one =  "0000000000001" ;
char *max =  "9999999999999" ;
char q[400] ;
main() /* Interacts with user to generate a masterkey
 and a series of encryption/decryption pairs     */
{       char *x, *y, *z, *malloc() ;
        char f1, f2 ;
        x = malloc(15) ;
        y = malloc(15) ;
        z = malloc(15) ;
        copy(xero,x) ;
        copy(xero,y) ;
        copy(xero,z) ;
        f1 = 'y' ;
        while( f1 == 'y')
        {       prime(x) ;
                printf("first prime is %s",x) ;
                prime(y) ;
                printf("second prime is %s",y) ;
                copy(x,z) ;
                multiply(z,y,max) ;
                printf("\nMasterkey is %s",z) ;
                sub(x,one) ;
                sub(y, one) ;
                multiply(x,y,max) ;
                printf("totient is %s",x) ;
                f2 = 'y' ;
                while(f2 == 'y' )
                {       printf("\n Enter encryption key. ") ;
                        scanf("\n %s",y) ;
                        pad(y) ;
                        printf("\n encryption key is %s",y) ;
                        if(euc(x,y) == 1 )
                        {       inv(y,x,z) ;
                                printf(" decryption key is %s",z) ;
                        }
                        else printf("\n Non prime relative to totient") ;
                        printf("Continue this search? y/n \n") ;
                        scanf("\n%c",&f2) ;
                }
                printf("\nAnother search? y/n\n") ;
                scanf("\n %c",&f1) ;
        }
}















euc(u,v) /* Evaluates the greatest common factor of u and v */
/* returns a 1 if that is the gcf, otherwise, returns a 0   */
char *u, *v ;
{       char *i, *j, *a, *z, *malloc() ;
        i = malloc(15) ;
        j = malloc(15) ;
        a = malloc(15) ;
        z = malloc(15) ;
        copy(u,j) ;
        copy(v,i) ;
        if(strcmp(u,v) > 0)
        {       copy(u,i) ;
                copy(v,j) ;
        }
        copy(one,a) ;
        while(strcmp(a,xero) > 0 )
        {       copy(i,a) ;
                residue(a,j) ;
                copy(j,z) ;
                copy(a,j) ;
                copy(z,i) ;
        }
        if(strcmp(z,one) == 0 ) return(1) ;
        else return(0) ;
}
/* requires prime.f, search.f, rsa.f, inv.f and mathset.f to run */

/* prime.f May 3, 1987 */
prime(h) /* Interacts with user to generate a prime suitable to be a factor in the
the product that becomes the masterkey.  Called twice, generates two factors */
char *h ;
{       char *x, *y, *z, *malloc() ;
        char f1, f2 ;
        x = malloc(15) ;
        y = malloc(15) ;
        z = malloc(15) ;
        copy(xero,x) ;
        copy(xero,y) ;
        copy(xero,z) ;
        f1 = 'y' ;
        while( f1 == 'y')
        {       printf("\nEnter a prime number seed.") ;
                scanf("\n %s",x) ;
                printf("\nEnter a starting number") ;
                scanf("\n %s",y) ;
                printf("\n") ;
                pad(x) ;
                pad(y) ;
                printf("seed is %s, starting search at  %s\n", x,y) ;
                f2 = 'y' ;
                while(f2 == 'y' )
                {       search(y,x,z) ;
                        printf("%s is a prime, new search starts at  %s \n", z,y) ;
                        add(y,one) ;
                        printf("Continue this search? y/n \n") ;
                        scanf("\n%c",&f2) ;
                }
                printf("\nAnother search? y/n\n") ;
                scanf("\n %c",&f1) ;
        }
        copy(z,h) ;
}

/* search,f May 3, 1987 */
search(h,p,r) /* Generates primes given initial 13 digit numberstring greater */
/* than 2 but less than second 13 digit numberstring which must be a prime    */
/* Based on theorem 101(Hardy & Wright), generates numbers of the form h*p + 1*/
/* and tests them for primality conditions 2^h != 1 and 2^(n -1) ==1(mod n)   */
/* Result is returned in location referenced by last argument.                */
char *h, *p, *r ;
{       char *n, *e, *f, *malloc() ;
        char *two = "0000000000002" ;
        n = malloc(15) ;
        e = malloc(15) ;
        f = malloc(15) ;
        while(strcmp(h,p) < 0)
        {       
                copy(one,f);
                multiply(f,h,max) ;
                multiply(f,p,max) ;
                copy(f,n) ;
                add(n,one) ;
                copy(two,e) ;
                rsa(e,h,n) ;
                if(strcmp(e,one) != 0)
                {       copy(two,e) ;
                        rsa(e,f,n) ;
                        if(strcmp(e,one) == 0)
                        {       copy(n,r) ;
                                return(1) ;
                        }
                        add(h,one) ;
                }
        }
}
/* requires frsa.c and mathset.c to run */

/* rsa.f May 3, 1987 */
rsa(m,e,n) /* Raises m to the e th power modulo n.  Leaves result in m. */
char *m, *e, *n ;
{       char *j, *z, *l  ;
        j = q + 180 ;
        z = q + 195 ;
        l = q + 210 ;
        copy(e,j) ;
        copy(one,z) ;
        copy(m,l) ;
        while(strcmp(xero,j) < 0 )
        {       if(halve(j) == 1) multiply(z,l,n) ;
                multiply(l,l,n) ;
        }
        copy(z,m) ;
}

/* inv.f May 3, 1987 */
inv(u,v,w) /* This function generates the modular inverse through a process
which was developed using bc and avoids reentrant code. Inverter4 is the
name of the bc script which this function was developed from.      */
char *u , *v, *w ;
{
        char *a[15],*b[15],*x[15],*y[15],*k[15],*z[15] ;
        char *r , *t , *s , *f, *malloc() ;
        int i, j ;
        r = malloc(15) ;
        t = malloc(15) ;
        s = malloc(15) ;
        f = malloc(15) ;
        j = 0 ;
        for( i = 0 ; i < 15 ; i++) a[i] = malloc(15) ;
        for( i = 0 ; i < 15 ; i++) b[i] = malloc(15) ;
        for( i = 0 ; i < 15 ; i++) x[i] = malloc(15) ;
        for( i = 0 ; i < 15 ; i++) y[i] = malloc(15) ;
        for( i = 0 ; i < 15 ; i++) k[i] = malloc(15) ;
        for( i = 0 ; i < 15 ; i++) z[i] = malloc(15) ;
        copy(u,r) ;
        copy(v,t) ;
        while(strcmp(r,one) > 0)
        {
                copy(r,a[j]) ;
                copy(t,b[j]) ;
                copy(b[j],r) ;
                residue(r,a[j]) ;
                copy(r,s) ;
                copy(a[j],r) ;
                sub(r,s) ;
                copy(b[j],x[j]) ;
                divide(x[j],a[j]) ;
                add(x[j],one) ;
                copy(one,y[j]) ;
                copy(b[j],f) ;
                residue(f,r) ;
                while(strcmp(f,xero) > 0 )
                {
                        copy(b[j],t) ;
                        divide(t,r) ;
                        add(t,one) ;
                        multiply(x[j],t,v) ;
                        multiply(y[j],t,v) ;
                        add(y[j],one) ;
                        multiply(y[j],one,v) ;
                        copy(b[j],f) ;
                        residue(f,r) ;
                        sub(r,f) ;
                        copy(b[j],f) ;
                        residue(f,r) ;
                }
                copy(a[j],t) ;
                j = j + 1 ;
        }
















        j = j - 1 ;
        copy(x[j],z[j]) ;
        copy(y[j],k[j]) ;
        if ( j == 0)
        {       copy(z[0],w) ;
                return ;
        }
        while( j > 0 )
        {
                i = j ;
                j = j - 1 ;
                copy(z[i],z[j]) ;
                multiply(z[j],x[j],v);
                while(strcmp(z[j],k[i]) < 0) add(z[j],v) ;
                sub(z[j],k[i] ) ;
                multiply(z[j],one,v) ;
                copy(z[i],k[j] ) ;
                multiply(k[j],y[j],v) ;
        }
copy(z[0],w) ;
}

/* mathset.f may 3, 1987 */
/* mathset includes divide(p,h),residue(p,h),sub(p,h),multiply(p,h,r) and
the fundamental functions which these call: copy,pad,add,halve and mod   */
/* version of May 2, 1987, developed while debugging minvert.c           */
divide(p,h) /* Divides p by h. Leaves result in p. */
char *p, *h  ;
{       char *j, *k, *l, *r ;
        j = q + 135 ;
        k = q + 150 ;
        l = q + 165 ;
        r = q + 180 ;
        copy(one,j) ;
        copy(xero,r) ;
        copy(h,k) ;
        copy(p,l) ;
        while(strcmp(k,l) <= 0)
        {       while(strcmp(k,l) <= 0)
                {       add(k,k) ;
                        add(j,j) ;
                }
                halve(k) ;
                halve(j) ;
                add(r,j) ;
                mod(l,k) ;
                copy(h,k) ;
                copy(one,j) ;
        }
        copy(r,p) ;
}

residue(p,h) /* Replaces p with the residue of p mod h */
char *p, *h  ;
{       char *j, *k, *l, *r ;
        j = q + 255 ;
        k = q + 270 ;
        l = q + 285 ;
        r = q + 300 ;
        copy(one,j) ;
        copy(xero,r) ;
        copy(h,k) ;
        copy(p,l) ;
        while(strcmp(k,l) <= 0)
        {       while(strcmp(k,l) <= 0)
                {       add(k,k) ;
                        add(j,j) ;
                }
                halve(k) ;
                halve(j) ;
                add(r,j) ;
                mod(l,k) ;
                copy(h,k) ;
                copy(one,j) ;
        }
        copy(l,p) ;
}












sub(p,h) /* Subtracts number at h from number at p, leaves result at p. */
char *p, *h ;
{       int i, borrow ;
        borrow = 0 ;
        for (i = 12 ; i > -1   ; --i)
        {       *(p + i) = *(p + i) - borrow ;
                if(*(p + i) < *(h + i))
                {       *(p + i) = 10 + *(p + i) - *(h + i) + '0' ;
                        borrow = 1 ;
                }
                else
                {       *(p + i) = *(p + i) - *(h + i) + '0' ;
                        borrow = 0 ;
                }
        }
return(borrow) ;
}

pad(p) /* Expands a numberstring shorter than 13 digits to a 13 digit length */
char *p ;
{       char *c;
        int i,j ;
        c = q + 120 ;
        for (i = 12, j = strlen(p) - 1 ; j > -1   ; --i, --j)
        *(c + i) = *(p + j) ;
        while( i > -1)  *(c + i--) = '0' ;
        copy(c,p) ;
}
copy(p,h) /* Copies the numberstring at p to location h. */
char *p, *h ;
{
        int i ;
        char c ;
        for (i = 0 ; i < 13   ; ++i)
        *(h + i) = *(p + i) ;
}
add(p,h) /* Adds numberstring at h to the one at p.  Result remains in p. */
char *p, *h ;
{       int i, carry ;
        char c ;
        carry = 0 ;
        for (i = 12 ; i > -1   ; --i)
        {       c = ((*(h + i) + *(p + i) - '0' - '0' + carry) % 10 )+ '0' ;
                carry = (*(h + i) + *(p + i) - '0' - '0' + carry) / 10  ;
                *(p + i) = c ;
        }
        return(carry) ;
}
halve(p) /* Halves the number at p. If it was odd, returns integer 1, else 0. */
char *p ;
 {      int i, carry ;
        char c ;
        carry = 0 ;
        for (i = 0 ; i < 13   ; ++i)
        {       c = ((*(p + i) - '0' + carry) / 2 ) + '0' ;
                carry = ((*(p + i) - '0' + carry ) % 2) * 10 ;
                *(p + i) = c ;
        }
        return(carry / 10 ) ;
}








mod(p,h) /* Converts number at p to that number modulo value of number at h. */
char *p, *h ;
{       int i, borrow ;
        while(strcmp(p,h) >= 0)
        {       borrow = 0 ;
                for (i = 12 ; i > -1   ; --i)
                {       *(p + i) = *(p + i) - borrow ;
                        if(*(p + i) < *(h + i))
                        {       *(p + i) = 10 + *(p + i) - *(h + i) + '0' ;
                                borrow = 1 ;
                        }
                        else
                        {       *(p + i) = *(p + i) - *(h + i) + '0' ;
                                borrow = 0 ;
                        }
                }
        }
return(borrow) ;
}





multiply(p,h,m) /* Multiplies p by h modulo m. Leaves result in p. */
char *p, *h, *m ;
{       char *j, *k, *l ;
        j = q + 225 ;
        k = q + 240 ;
        l = q + 255 ;
        j = "0000000000000" ;
        copy(xero,j) ;
        copy(p,k) ;
        copy(h,l) ;
        while(strcmp(xero,l) < 0)
        {       if(halve(l) == 1)
                {       add(j,k) ;
                        mod(j,m) ;
                }
                add(k,k) ;
                mod(k,m) ;
        }
copy(j,p) ;
}

$