/*
  Author:  Pate Williams (c) 1997

  Exercise
  "4.6 Two samples of RSA cipertext are presented in
  Tables 4.1 and 4.2. Your task is to decrypt them.
  The public parameters of the system are n = 18923
  and b = 1261 (for Table 4.1) and n = 31313 and
  b = 4913 (for Table 4.2)." -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson pages 157-158.
*/

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

#define BITS_PER_LONG   32l
#define BITS_PER_LONG_1 31l

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, 0l, sieve);
  set_bit(1l, 0l, sieve);
  set_bit(2l, 1l, 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, 0l, sieve);
      i += inc;
    }
    c += 2;
    while (!get_bit(c, sieve)) c++;
  } while (c * c <= n);
}

long factor(long n, long *sieve)
/* factor using trial division */
{
  int found = 0;
  long p = 0, s = sqrt(n);

  while (!found && p <= s) {
    while (!get_bit(p, sieve)) p++;
    found = n % p == 0;
    if (!found) p++;
  }
  return 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 = 1l, s = x;

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

int main(void)
{
  char abc[26] = "abcdefghijklmnopqrstuvwxyz";
  long b[2] = {1261l, 4913l};
  long n[2] = {18923l, 31313l};
  long c[2][32] = {{12423l, 11524l,  7243l,  7459l,
                    14303l,  6127l, 10964l, 16399l,
                     9792l, 13629l, 14407l, 18817l,
                    18830l, 13556l,  3159l, 16647l,
                     5300l, 13951l,    81l,  8986l,
                     8007l, 13167l, 10022l, 17213l,
                     2264l,   961l, 17459l,  4101l,
                     2999l, 14569l, 17183l, 15827l},
                   { 6340l,  8309l, 14010l,  8936l,
                    27358l, 25023l, 16481l, 25809l,
                    23614l,  7135l, 24996l, 30590l,
                    27570l, 26486l, 30388l,  9395l,
                    27584l, 14999l,  4517l, 12146l,
                    29421l, 26439l,  1606l, 17881l,
                    25774l,  7647l, 23901l,  7372l,
                    25774l, 18436l, 12056l, 13547l}};
  long i, j, sieve[10000], m, p, q;
  long a, bi, ni, phi, t;

  Sieve(n[1], sieve);
  for (i = 0; i < 2; i++) {
    bi = b[i];
    ni = n[i];
    p = factor(ni, sieve);
    q = ni / p;
    printf("p = %5ld q = %5ld n = %5ld\n", p, q, ni);
    phi = (p - 1) * (q - 1);
    a = Extended_Euclidean(bi, phi);
    printf("a = %5ld b = %5ld\n", a, bi);
    printf("%5ld * %5ld mod %5ld = %5ld\n", a, bi,
           phi, (a * bi) % phi);
    for (j = 0; j < 32; j++) {
      m = exp_mod(c[i][j], a, ni);
      if (c[i][j] != exp_mod(m, bi, ni))
        printf("*error*\in RSA\n");
      t = m / 676l;
      m = m % 676l;
      printf("%c", abc[t]);
      t = m / 26l;
      m = m % 26l;
      printf("%c", abc[t]);
      printf("%c", abc[m]);
      if ((j + 1) % 8 == 0) printf("\n");
    }
    printf("\n");
  }
  return 0;
}