/*
  Author:  Pate Williams (c) 1997

  Exercise IV.2.1
  "Suppose that the following 40-letter alphabet
  is used for all plaintexts and ciphertexts:
  A-Z with numerical equivalents 0-25, blank = 26,
  . = 27, ? = 28, $ = 29, the numerals 0-9 with
  numerical equivalents 30-39. Suppose that
  plaintext message units are digraphs and
  ciphertext message units are trigraphs (i.e.,
  k = 2, l = 3, 40 ^ 2 < n_A < 40 ^ 3 for all n_A).
  (a) Send the message "SEND $7500" to a user
  whose enciphering key is (n_A, e_A) = (2047, 179).
  (b) Break the code by factoring n_A and then
  computing the deciphering key (n_A, d_A)."
  -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 95.
*/

#include <stdio.h>
#include <string.h>

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

struct factor {long expon, prime;};

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;
}

void set_bit(long i, long v, long *sieve)
{
  long b = i % BITS_PER_LONG;
  long c = i / BITS_PER_LONG;
  long mask = 1 << (BITS_PER_LONG_1 - b);

  if (v == 1)
    sieve[c] |= mask;
  else
    sieve[c] &= ~mask;
}

void Sieve(long n, long *sieve)
{
  long c, i, inc;

  set_bit(0l, 0, sieve);
  set_bit(1l, 0, sieve);
  set_bit(2l, 1, sieve);
  for (i = 3; i <= n; i++)
    set_bit(i, i & 1, sieve);
  c = 3;
  do {
    i = c * c, inc = c + c;
    while (i <= n) {
      set_bit(i, 0, sieve);
      i += inc;
    }
    c += 2;
    while (!get_bit(c, sieve)) c++;
  } while (c * c <= n);
}

void factor(long n, long *sieve, struct factor *f,
            long *count)
/* factor using trial division */
{
  int one = 0;
  long e, p = 2;

  *count = 0;
  while (!one) {
    while (!get_bit(p, sieve)) p++;
    if (n % p == 0) {
      e = 0;
      do {
        e++;
        n = n / p;
      } while (n % p == 0);
      f[*count].expon = e;
      f[*count].prime = p;
      *count = *count + 1;
      one = n == 1;
    }
    p++;
  }
}

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 exp_mod(long x, long b, long n)
/* returns x ^ b mod n */
{
  long a = 1, s = x;

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

long gcd(long a, long b)
{
  long r;

  while (b != 0)
    r = a % b, a = b, b = r;
  return a;
}

char cipher_translate(long c)
{
  if (c < 26) return (char) (c + 'A');
  if (c >= 30 && c <= 39) return (char) (c - 30 + '0');
  if (c == 26) return ' ';
  if (c == 27) return '.';
  if (c == 28) return '?';
  return '$';
}

long plain_translate(char p)
{
  if (p >= 'A' && p <= 'Z') return p - 'A';
  if (p >= '0' && p <= '9') return p - '0' + 30;
  if (p == ' ') return 26;
  if (p == '.') return 27;
  if (p == '?') return 28;
  else return 29;
}

int main(void)
{
  char ciphertext[32];
  char plaintext[16] = "SEND $7500";
  long N = 40, c, d, e = 179, i, j, n = 2047, p, q;
  long count, phi, sieve[256];
  struct factor f[32];

  Sieve(n, sieve);
  for (i = 0, j = 0; i < strlen(plaintext); i += 2, j += 3) {
    p = N * plain_translate(plaintext[i])
      + plain_translate(plaintext[i + 1]);
    c = exp_mod(p, e, n);
    ciphertext[j] = cipher_translate(c / (N * N));
    c %= N * N;
    ciphertext[j + 1] = cipher_translate(c / N);
    ciphertext[j + 2] = cipher_translate(c % N);
    ciphertext[j + 3] = '\0';
  }
  printf("%s\n", plaintext);
  printf("%s\n", ciphertext);
  factor(n, sieve, f, &count);
  p = f[0].prime;
  q = f[1].prime;
  printf("n = %ld = %ld * %ld\n", n, p, q);
  phi = n + 1 - p - q;
  d = Extended_Euclidean(e, phi);
  printf("e = %ld\n", e);
  printf("d = %ld\n", d);
  for (i = 0, j = 0; i < strlen(ciphertext); i += 3, j += 2) {
    p = N * N * plain_translate(ciphertext[i])
      + N * plain_translate(ciphertext[i + 1])
      + plain_translate(ciphertext[i + 2]);
    c = exp_mod(p, d, n);
    plaintext[j] = cipher_translate(c / N);
    plaintext[j + 1] = cipher_translate(c % N);
    plaintext[j + 2] = '\0';
  }
  printf("%s\n", ciphertext);
  printf("%s\n", plaintext);
  return 0;
}