/*
  Author:  Pate Williams (c) 1997

  Exercise IV.2.2
  "Try to break the code whose enciphering key is
  (n_A, e_A) = (536813567, 3602561). Use a computer
  to factor n_A using the stupidest known algorithm,
  i.e., dividing by all odd numbers 3, 5, 7, ....
  If you don't have a computer available, try to
  guess a prime factor of n_A by trying special
  classes of prime numbers. After factoring n_A,
  find the deciphering key. Then decipher the
  message BNBPPKZAVQZLBJ, under the assumption
  that the plaintext consists of 6-letter blocks
  in the usual 26-letter alpahabet (converted to
  an integer between 0 and 26 ^ 6 - 1 in the
  usual way) and the ciphertext consists of
  7-letter blocks in the same alphabet. It should
  be clear from this exercise that even a 29-bit
  choice of n_A is far too small." -Neal Koblitz-
  See "A Course in Number Theory and Crpytography"
  by Neal Koblitz second edition page 96.
*/

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

int main(void)
{
  char ciphertext[32] = "BNBPPKZAVQZLBJ";
  char plaintext[32];
  long N = 26, d, e = 3602561l, n = 536813567l;
  long i, j, p, q, phi, x, y;
  verylong zd = 0, ze = 0, zn = 0, zx = 0, zy = 0;
  verylong zphi = 0;

  zintoz(n, &zn);
  zpstart2();
  p = zpnext();
  while (zsmod(zn, p) != 0) p = zpnext();
  q = n / p;
  phi = n + 1 - p - q;
  zintoz(e, &ze);
  zintoz(phi, &zphi);
  zinvmod(ze, zphi, &zd);
  d = ztoint(zd);
  printf("n = %ld = %ld * %ld\n", n, p, q);
  printf("e = %ld\n", e);
  printf("d = %ld\n", d);
  for (i = 0, j = 0; i < strlen(ciphertext); i += 7, j += 6) {
    x = pow(N, 6) * (ciphertext[i] - 'A')
      + pow(N, 5) * (ciphertext[i + 1] - 'A')
      + pow(N, 4) * (ciphertext[i + 2] - 'A')
      + pow(N, 3) * (ciphertext[i + 3] - 'A')
      + N * N * (ciphertext[i + 4] - 'A')
      + N * (ciphertext[i + 5] - 'A')
      + ciphertext[i + 6] - 'A';
    zintoz(x, &zx);
    zexpmod(zx, zd, zn, &zy);
    y = ztoint(zy);
    plaintext[j] = y / pow(N, 5) + 'A';
    y %= (long) pow(N, 5);
    plaintext[j + 1] = y / pow(N, 4) + 'A';
    y %= (long) pow(N, 4);
    plaintext[j + 2] = y / pow(N, 3) + 'A';
    y %= (long) pow(N, 3);
    plaintext[j + 3] = (char) (y / (N * N) + 'A');
    y %= N * N;
    plaintext[j + 4] = (char) (y / N + 'A');
    plaintext[j + 5] = (char) (y % N + 'A');
    plaintext[j + 6] = '\0';
  }
  printf("%s\n", ciphertext);
  printf("%s\n", plaintext);
  zfree(&zd);
  zfree(&ze);
  zfree(&zn);
  zfree(&zx);
  zfree(&zy);
  zfree(&zphi);
  return 0;
}