/*
  Author:  Pate Williams (c) 1997

  Goldwasser-Micali probabilistic encryption.
  See "Handbook of Applied Cryptography" by
  Alfred J. Menezes et al 8.7.1 Section pages
  307 - 308.
*/

#include <stdio.h>
#include <time.h>
#include "lip.h"

#define CRT_SIZE 8

void Garner(long t, verylong *zm, verylong *zv, verylong *zx)
/* solution of the Chinese remaider theorem */
{
  long i, j;
  verylong za = 0, zb = 0, zu = 0, zC[CRT_SIZE];

  for (i = 0; i < CRT_SIZE; i++) zC[i] = 0;
  for (i = 1; i < t; i++) {
    zone(&zC[i]);
    for (j = 0; j <= i - 1; j++) {
      zinvmod(zm[j], zm[i], &zu);
      zmulmod(zu, zC[i], zm[i], &za);
      zcopy(za, &zC[i]);
    }
  }
  zcopy(zv[0], &zu);
  zcopy(zu, zx);
  for (i = 1; i < t; i++) {
    zsub(zv[i], *zx, &za);
    zmulmod(za, zC[i], zm[i], &zu);
    zone(&za);
    for (j = 0; j <= i - 1; j++) {
      zmul(za, zm[j], &zb);
      zcopy(zb, &za);
    }
    zmul(za, zu, &zb);
    zadd(*zx, zb, &za);
    zcopy(za, zx);
  }
  zfree(&za);
  zfree(&zb);
  zfree(&zu);
  for (i = 0; i < CRT_SIZE; i++) zfree(&zC[i]);
}

void GM_gen_keys(long length, verylong *zn,
                 verylong *zp, verylong *zq,
                 verylong *zy)
/* generates the public key pair (n, y) and
   private key pair (p, q) */
{
  verylong za = 0, zb = 0, zm[2], zv[2];

  zm[0] = zm[1] = zv[0] = zv[1] = 0;
  zrstarts(time(NULL));
  zrandomprime(length, 5l, zp, zrandomb);
  zrandomprime(length, 5l, zq, zrandomb);
  zmul(*zp, *zq, zn);
  do zrandomb(*zp, &za); while (zjacobi(za, *zp) != - 1);
  do zrandomb(*zq, &zb); while (zjacobi(zb, *zq) != - 1);
  zcopy(za, &zv[0]);
  zcopy(zb, &zv[1]);
  zcopy(*zp, &zm[0]);
  zcopy(*zq, &zm[1]);
  Garner(2l, zm, zv, zy);
  zfree(&za);
  zfree(&zb);
  zfree(&zm[0]);
  zfree(&zm[1]);
  zfree(&zv[0]);
  zfree(&zv[1]);
}

void GM_encryption(char *m, long t, verylong zn,
                   verylong zy, verylong *zc)
{
  long i;
  verylong zx = 0, zxs = 0;

  for (i = 0; i < t; i++) {
    do zrandomb(zn, &zx); while (zscompare(zx, 0l) == 0);
    zsq(zx, &zxs);
    if (m[i] == 1)
      zmulmod(zy, zxs, zn, &zc[i]);
    else
      zmod(zxs, zn, &zc[i]);
  }
  zfree(&zx);
  zfree(&zxs);
}

void GM_decryption(char *m, long t, verylong zp, verylong *zc)
{
  long i;

  for (i = 0; i < t; i++)
    if (zjacobi(zc[i], zp) == 1) m[i] = 0; else m[i] = 1;
}

int main(void)
{
  char i, m[8] = {1, 0, 1, 0, 1, 0, 1, 0}, n[8];
  verylong zc[8], zn = 0, zp = 0, zq = 0, zy = 0;

  printf("message before encryption\n");
  for (i = 0; i < 8; i++) {
    printf("%d ", m[i]);
    zc[i] = 0;
  }
  printf("\n");
  GM_gen_keys(64l, &zn, &zp, &zq, &zy);
  GM_encryption(m, 8l, zn, zy, zc);
  GM_decryption(n, 8l, zp, zc);
  printf("message after decryption\n");
  for (i = 0; i < 8; i++) {
    printf("%d ", n[i]);
    zfree(&zc[i]);
  }
  printf("\n");
  zfree(&zn);
  zfree(&zp);
  zfree(&zq);
  zfree(&zy);
  return 0;
}