/*
  Author:  Pate Williams (c) 1997

  Exercise IV.2.3
  "Suppose that the plaintexts and the ciphertexts
  consist of trigraph message units, but while
  plaintexts are written in the 27-letter alphabet
  (consisting of A-Z and blank = 26), ciphertexts
  are written in the 28-letter alphabet obtained
  by adding the symbol "/" (with numerical
  equivalent 27) to the alphabet. We require that
  each user A choose n_A between 27 ^ 3 = 19683
  and 28 ^ 3 = 21952, so that the a plaintext
  trigraph in the 27-letter alphabet corresponds
  to a residue P modulo n_A, and then
  C = P ^ e_A mod n_A corresponds to a ciphertext
  trigraph in the 28-letter alphabet.
  (a) If your deciphering key is
  K_D = (n, d) = (21853, 20787), decipher the
  message "YSNAUOZHXXH ".
  (b) If in part (a) you know phi(n) = 21280,
  find (1) e = d ^ - 1 mod phi(n) and (2) the
  factorization of n." -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 96.
*/

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

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

long cipher_translate(char c)
{
  if (c >= 'A' && c <= 'Z') return c - 'A';
  if (c == ' ') return 26;
  return 27;
}

char plain_translate(long p)
{
  if (p < 26) return (char) (p + 'A');
  return ' ';
}

int main(void)
{
  char ciphertext[16] = "YSNAUOZHXXH ";
  char plaintext[16];
  long M = 27, N = 28, d = 20787, n = 21583;
  long a, c, e, i, m, p, phi = 21280, q;

  for (i = 0; i < strlen(ciphertext); i += 3) {
    c = N * N * cipher_translate(ciphertext[i])
      + N * cipher_translate(ciphertext[i + 1])
      + cipher_translate(ciphertext[i + 2]);
    p = exp_mod(c, d, n);
    plaintext[i] = plain_translate(p / (M * M));
    p %= M * M;
    plaintext[i + 1] = plain_translate(p / M);
    plaintext[i + 2] = plain_translate(p % M);
    plaintext[i + 3] = '\0';
  }
  printf("%s\n", ciphertext);
  printf("%s\n", plaintext);
  e = Extended_Euclidean(d, phi);
  printf("d = %ld\n", d);
  printf("e = %ld\n", e);
  /* factor n */
  m = phi / 2;
  for (;;) {
    a = rand() % phi;
    p = exp_mod(a, m, n);
    if (p != 1) break;
  }
  p = gcd(n, p - 1);
  q = n / p;
  printf("n = %ld = %ld * %ld\n", n, p, q);
  return 0;
}