/*
  Author:  Pate Williams (c) 1997

  Exercise 12.6
  "Suppose Bob receives some ciphertext which was
  encrypted with the Blum-Goldwasser Probabilistic
  Public-key Cryptosystem. The original plaintext
  consisted of English text. Each alphabetic
  character was converted to a bitstring of length
  five in an obvious way: A -> 00000, B -> 00001,
  ..., Z -> 11001. The plaintext consisted of 236
  alphabetic characters, so a bitstring of length
  1180 resulted. This bitstring was then encrypted.
  The resulting ciphertext was then converted to
  a hexadecimal representation, to save space. The
  final string of 295 hexadecimal characters is
  presented in Table 12.4. Also, s_1181 = 20291 is
  part of the ciphertext, and n = 29893 is Bob's
  public key. Bob's secret factorization of n is
  n = pq, where p = 167 and q = 179. Your task is
  to decrypt the given ciphertext and restore the
  original plaintext." -Douglas R. Stinson-
*/

#include <stdio.h>

#define BITS_PER_LONG   32
#define BITS_PER_LONG_1 31
#define SIZE 256

long exp_mod(long x, long b, long n)
/* returns x ^ b mod n */
{
  long a = 1l, s = x;

  while (b != 0) {
    if (b & 1l) a = (a * s) % n;
    b >>= 1;
    if (b != 0) s = (s * s) % n;
  }
  return a;
}

long get_bit(long i, long *sieve)
{
  long b = i % BITS_PER_LONG;
  long c = i / BITS_PER_LONG;

  return (sieve[c] >> (BITS_PER_LONG_1 - b)) & 1;
}

long Extended_Euclidean(long b, long n)
{
  long b0 = b, n0 = n, t = 1, t0 = 0, temp, q, r;

  q = n0 / b0;
  r = n0 - q * b0;
  while (r > 0) {
    temp = t0 - q * t;
    if (temp >= 0) temp = temp % n;
    else temp = n - (- temp % n);
    t0 = t;
    t = temp;
    n0 = b0;
    b0 = r;
    q = n0 / b0;
    r = n0 - q * b0;
  }
  if (b0 != 1) return 0;
  else return t % n;
}

long Chinese_Remainder(long r, long *a, long *m)
{
  long i, N = 1, M[SIZE], y[SIZE], x = 0;

  for (i = 0; i < r; i++) N *= m[i];
  for (i = 0; i < r; i++) {
    M[i] = N / m[i];
    y[i] = Extended_Euclidean(M[i], m[i]);
    x += (a[i] * M[i] * y[i]) % N;
  }
  return x;
}

int main(void)
{
  long ciphertext[18] = {0xe1866663, 0xf17fdbd1,
                         0xdc8c8fd2, 0xeebc36ad,
                         0x7f53795d, 0xba3c9ce2,
                         0x2dc9a9c7, 0xe2a56455,
                         0x501399ca, 0x6b98aed2,
                         0x2c346a52, 0x9a09c193,
                         0x6c61ecde, 0x10b43d22,
                         0x6ec683a6, 0x69929f2f,
                         0xfb912bfa, 0x96a83021};
  long p = 167, q = 179, l1 = 1181, s1 = 20291;
  long a1, a2, b1, b2, s0;
  long n = p * q, p1 = p - 1, q1 = q - 1;
  long a[2], m[2], r = 2, bits = 18 * BITS_PER_LONG;
  long bit[5], i = 0, j, k, z;

  a1 = exp_mod((p + 1) / 4, l1, p1);
  a2 = exp_mod((q + 1) / 4, l1, q1);
  b1 = exp_mod(s1, a1, p);
  b2 = exp_mod(s1, a2, q);
  a[0] = b1;
  a[1] = b2;
  m[0] = p;
  m[1] = q;
  s0 = Chinese_Remainder(r, a, m);
  for (j = 0; j < bits / 5; j++) {
    for (k = 0; k < 5; k++) {
      s1 = (s0 * s0) % n;
      s0 = s1;
      z = s1 & 1;
      bit[k] = z ^ get_bit(i++, ciphertext);
    }
    z = bit[0];
    for (k = 1; k < 5; k++)
      z = z * 2 + bit[k];
    printf("%c", z + 'A');
    if ((j + 1) % 20 == 0) printf("\n");
  }
  return 0;
}