/**************************************************************************/
/* Bianca                                                                 */
/*                                                                        */
/*       CMSC443                                                          */
/*                                                                        */
/*                                                                        */
/*  Project 9-1                                                           */
/*                                                                        */
/*  This program is a simulation of secure sign-on into a computer        */
/*   system using a zero-knowledge proof system, which employs            */
/*   quadratic residues in a modulo system.  The (prime) modulus is       */
/*   now defined as 101 (I was having problems with arrays of larger      */
/*   sizes, but this can easily be changed according to whatever the      */
/*   machine it is running on can handle.  Also, the number of trials     */
/*   required to prove authenticity is defined as ten, but this too can   */
/*   easily be changed.                                                   */
/*                                                                        */
/*  As in the handout from class, in this project, x is used to denote    */
/*   the modulus, u is used to denote the random number picked by the     */
/*   user, z is used to denote u squared, w is used to denote the secret  */
/*   password of the user, and v is used to denote the value the user may */
/*   be asked to enter into the system.                                   */
/*                                                                        */
/*  I did not receive any help in writing this project.                   */
/*                                                                        */
/*  This second mailing is an interactive project where the user actually */
/*   has a secret key and uses it to prove their authenticity.            */
/*   y is 23, and my secret password is 15. (23 squared is 15 mod 101.)   */
/*                                                                        */
/**************************************************************************/

/* Include libraries */

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

/* Define the number of trials and the modulus for the modulo system */

#define TRIALS 10
#define x 101

/* Global variables: y and w for password control, QR array for the GetY
      function */

int y = 23;

main()
{
float prob = 1;   /* To keep track of updated probability of insecure entry */
int u, v, z;      /* Variables for the user-system dialogue */
int i;            /* Index variable */

printf("This is a Zero-Knowledge System sign-on.\n\n");
printf("x is %d, y is %d.\n", x, y);
srand((short) clock() );   /* Seed the random number generator */

for (i=0; i<TRIALS; i++)   /* Perform an authenticity trial the specified
                               number of times */
  {
  printf("Enter your new z.\n");
  scanf("%d", &z);
  z = z%x;

  if(rand()%2)             /* Randomly pick one of two tests on each trial. */
                           /* This trial asks for v to be calculated using
                                the password. */
    {
    printf("Use your password to calculate v =  u*w.  Enter v.\n");
    scanf("%d", &v);
    printf("v squared is %d, y*z is %d.\n\n", (v*v)%x, (y*z)%x);
    if( ((v*v)%x) != ((y*z)%x) )
      {
      printf("Your attempt to sign on fails.\n");
      exit(1);
      } 
    printf("This trial successful.\n");
    prob *= .5;  /* Update the probability of unsecure entry. */
    printf("Your authenticity is sure with probability %f.\n\n", prob);
    }
  else                      /* This trial asks for the user to reveal
                                the square root of their z. */
    {
    printf("Enter the square root of the z. (The u you picked originally.)\n");
    scanf("%d", &u);
    printf("u squared is %d, z is %d.\n\n", (u*u)%x, z);
    if( ((u*u)%x) != z )
      {
      printf("Your attempt to sign on fails.\n");
      exit(1);
      }
    prob *= .5;  /* Update the probability of unsecure entry. */
    printf("This trial is successful.\n");
    printf("Your identity is sure with probability %f.\n\n", prob);
    }
  }

printf(" %d trials successfully completed.\n", TRIALS);

}  /* End of Main */
/*
void MakeQR(void)  /* This function makes an array which, for all members
                       of the integers mod x, tells whether they are relatively
                       composite to x, relatively prime to x but not quadratic
                       residues, or actually are quadratic residues.  A zero
                       denotes relative compositness to x, a two denotes being
                       a quadratic residue, and a one denotes relative 
                       primality to x but not a quadratic residue. These values
                       are stored in the global QR array. 
{
int a,b,c,bb;      /* Index variables 

for(a=1; a<=x; a++)/* Initialize the array to ones.
   QR[a] = 1;

for(a=1; a<=x; a++)/* Then go through the array and put the zeroes in their
                       proper places.
   {
   b = a;
   c = x;

   again:
   if( (b%c)==0 ) /* If the number is a factor of x, it is relatively
                      composite to x.
     QR[b] = 0;
   else if ( (b%c) == 1 ) /* Also, if the number divides (x-1), it is 
                              relatively prime to x.
           QR[b] = 1;
   else                   /* If their relationship is not apparent, use the
                              Euclidean algorithm to reduce the numbers down
                              and try once again to derive their relation. 
      {
      bb=b;
      b = c%b;
      c = bb;
      goto again;
      } 
  }

for (a=1; a<=x; a++)     /* Go through the array once again, and mark the
                             quadratic residues.
    if ( (QR[a] > 0) && (QR[(a*a)%x] > 0) )
         QR[(a*a)%x] = 2;

} /* End of Function GetQR 

void GetY (void)  /* This function picks a new and valid w, y password pair
                      each time the program is run. 
{
w = rand() %x;    /* w is simply a random number in the mod x system.
if( (w == 0) || (QR[w]==0) ) /* But if it is zero, this is not a secure
                                 password -- pick a new one.
   GetY();
printf("Secret password w is %d.\n", w);
y = (w*w)%x;      /* Form the y from the w.

} /* End of GetY Function 
*/