blumgold.c

应用密码学手册-英文版,学习密码学和网络安全的好资料。

/*
  Author:  Pate Williams (c) 1997

  Blum-Goldwasser probabilistic public-key
  encryption. See "Handbook of Applied
  Cryptography" by Alfred J. Menezes et al
  editors 8.56 Algorithm page 309.
*/

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

#define BITS_PER_CHAR 8l

long get_bit(char *buffer, long n)
{
  long b = n % BITS_PER_CHAR, w = n / BITS_PER_CHAR;

  return (buffer[w] >> b) & 1;
}

void set_bit(char *buffer, long i, long n)
{
  long b = n % BITS_PER_CHAR, w = n / BITS_PER_CHAR;

  if (i == 1)
    buffer[w] |= (char) (1 << b);
  else
    buffer[w] &= (char) ~(1 << b);
}

long get_bits(char *buffer, long h, long i)
{
  long j, k = i * h, w = 0;

  for (j = 0; j < h; j++) {
    w |= get_bit(buffer, k + j);
    if (j < h - 1) w <<= 1;
  }
  return w;
}

void set_bits(char *buffer, long c, long h, long i)
{
  long j, h1 = h - 1, k = h * i;

  for (j = 0; j < h; j++) {
    set_bit(buffer, (c >> h1) & 1, k + j);
    c <<= 1;
  }
}

void bg_gen_key(long length, verylong *za, verylong *zb,
                verylong *zn, verylong *zp, verylong *zq)
/* key generation for Blum-Goldwasser
   probabilistic public key encryption */
{
  long p_length = length / 2, q_length = length - p_length;
  verylong zd = 0;

  zrstarts(time(NULL));
  do {
    zrandomprime(- p_length, 4, zp, zrandomb);
    zrandomprime(- q_length, 4, zq, zrandomb);
  } while (zcompare(*zp, *zq) == 0);
  do {
    zrandomb(*zp, za);
    zrandomb(*zq, zb);
    zexteucl(*zp, za, *zq, zb, &zd);
  } while (zscompare(zd, 1) != 0);
  zmul(*zp, *zq, zn);
  zfree(&zd);
}

void bg_encrypt(char *inp, char *out, long h, long t,
                verylong zn, verylong *zxt)
/* k = z2log(n), h = z2logs(k), t is the
   the number of h bit units in the input buffer */
{
  long c, i, m, p;
  verylong zr = 0, zt = 0, zx0 = 0, zx1 = 0;

  zrandomb(zn, &zr);
  zmulmod(zr, zr, zn, &zx0);
  for (i = 0; i < t; i++) {
    zmulmod(zx0, zx0, zn, &zx1);
    p = zslowbits(zx1, h);
    m = get_bits(inp, h, i);
    c = m ^ p;
    set_bits(out, c, h, i);
    zcopy(zx1, &zx0);
  }
  zmulmod(zx1, zx1, zn, zxt);
  zfree(&zr);
  zfree(&zt);
  zfree(&zx0);
  zfree(&zx1);
}

void bg_decrypt(char *inp, char *out, long h, long t,
                verylong za, verylong zb,
                verylong zn, verylong zp,
                verylong zq, verylong zxt)
{
  long c, i, m, p, t1 = t + 1;
  verylong zd1 = 0, zd2 = 0, zp1 = 0, zq1 = 0, zt1 = 0, zt2 = 0;
  verylong zu = 0, zv = 0, zx0 = 0, zx1 = 0;

  zsadd(zp, - 1l, &zp1);
  zsadd(zq, - 1l, &zq1);
  zsadd(zp, + 1l, &zu);
  zsadd(zq, + 1l, &zv);
  zsdiv(zu, 4l, &zt1);
  zsdiv(zv, 4l, &zt2);
  zsexpmod(zt1, t1, zp1, &zd1);
  zsexpmod(zt2, t1, zq1, &zd2);
  zexpmod(zxt, zd1, zp, &zu);
  zexpmod(zxt, zd2, zq, &zv);
  zmul(zv, za, &zt1);
  zmul(zt1, zp, &zd1);
  zmul(zu, zb, &zt2);
  zmul(zt2, zq, &zd2);
  zaddmod(zd1, zd2, zn, &zx0);
  for (i = 0; i < t; i++) {
    zmulmod(zx0, zx0, zn, &zx1);
    p = zslowbits(zx1, h);
    c = get_bits(inp, h, i);
    m = p ^ c;
    set_bits(out, m, h, i);
    zcopy(zx1, &zx0);
  }
  zfree(&zd1);
  zfree(&zd2);
  zfree(&zp1);
  zfree(&zq1);
  zfree(&zt1);
  zfree(&zt2);
  zfree(&zu);
  zfree(&zv);
  zfree(&zx0);
  zfree(&zx1);
}

int main(void)
{
  char e_inp[8] = "abcd", d_out[8], e_out[8];
  double time;
  long h, k, i, length = 128, t;
  clock_t time0;
  verylong za = 0, zb = 0, zn = 0, zp = 0, zq = 0, zxt = 0;

  time0 = clock();
  do {
    bg_gen_key(length, &za, &zb, &zn, &zp, &zq);
    time = (clock() - time0) / (double) CLK_TCK;
    printf("key bit length: %4ld total time required: %lf\n", length, time);
    length += 128l;
  } while (length <= 512l);
  bg_gen_key(128l, &za, &zb, &zn, &zp, &zq);
  k = z2log(zn);
  h = z2logs(k);
  t = BITS_PER_CHAR * strlen(e_inp) / h;
  if (BITS_PER_CHAR * strlen(e_inp) % h != 0) t++;
  for (i = 0; i < strlen(e_inp) * BITS_PER_CHAR; i++)
    set_bit(e_out, get_bit(e_inp, i), i);
  printf("%s %s\n", e_inp, e_out);
  for (i = 0; i < t; i++)
    set_bits(e_out, get_bits(e_inp, h, i), h, i);
  printf("%s %s\n", e_inp, e_out);
  bg_encrypt(e_inp, e_out, h, t, zn, &zxt);
  printf("%s %s\n", e_inp, e_out);
  bg_decrypt(e_out, d_out, h, t, za, zb, zn, zp, zq, zxt);
  d_out[strlen(e_inp)] = '\0';
  printf("%s %s\n", e_inp, d_out);
  zfree(&za);
  zfree(&zb);
  zfree(&zn);
  zfree(&zp);
  zfree(&zq);
  zfree(&zxt);
  return 0;
}