/*
  Author:  Pate Williams (c) 1997

  Exercise III.1.5
  "You are trying to cryptanalyze an affine
  transformation of single-letter message
  units in a 37-letter alphabet. This alphabet
  includes the numerals 0-9, which are labeled
  by themselves (i.e., by the integers 0-9).
  The letters A-Z have the numerical equivalents
  10-35, respectively, and blank = 36. You
  intercept the ciphertext "OH7F86BB46R3267O266B9".
  You know that the plaintext ends with the
  signature "007". What is the message?"
  -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 62.
*/

#include <stdio.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;
}

int main(void)
{
  char ciphertext[32] = "OH7F86BB46R3627O266BB9";
  char plaintext[32];
  long A[2][2], B[2], C[2][2], a, b, c, d, i, p;

  A[0][0] = '0' - '0', A[0][1] = 1;
  A[1][0] = '7' - '0', A[1][1] = 1;
  B[0] = 'B' - 'A' + 10, B[1] = '9' - '0';
  d = (A[0][0] * A[1][1] - A[0][1] * A[1][0]) % 37;
  if (d < 0) d += 37;
  d = Extended_Euclidean(d, 37);
  if (d == 0)
    printf("determinant is zero, solution does not exist\n");
  else {
    C[0][0] = (d * A[1][1]) % 37;
    C[1][1] = (d * A[0][0]) % 37;
    C[0][1] = - (d * A[0][1]) % 37;
    C[1][0] = - (d * A[1][0]) % 37;
    a = (C[0][0] * B[0] + C[0][1] * B[1]) % 37;
    b = (C[1][0] * B[0] + C[1][1] * B[1]) % 37;
    if (a < 0) a += 37;
    if (b < 0) b += 37;
    printf("a = %ld\n", a);
    printf("b = %ld\n", b);
    a = Extended_Euclidean(a, 37);
    for (i = 0; i < strlen(ciphertext); i++) {
      if (ciphertext[i] <= '9')
        c = ciphertext[i] - '0';
      else if (ciphertext[i] <= 'Z')
        c = ciphertext[i] - 'A' + 10;
      else c = 36;
      p = (a * (c - b)) % 37;
      if (p < 0) p += 37;
      if (p < 10)
        plaintext[i] = (char) (p + '0');
      else if (p < 36)
        plaintext[i] = (char) (p + 'A' - 10);
      else plaintext[i] = ' ';
    }
    plaintext[strlen(ciphertext)] = '\0';
    printf("%s\n", ciphertext);
    printf("%s\n", plaintext);
  }
  return 0;
}