/*
  Author:  Pate Williams (c) 1997

  Exercise
  "4.7 This exercise exhibits what is called a
  protocol failure. Suppose Bob has an RSA
  Cyyptosystem with a large modulus n for which
  the factorization cannot be found in a
  reasonable amount of time. Suppose Alice sends
  a message to Bob represnting each alphabetic
  character as an integer between 0 and 25, and
  then encrypting each residue modulo 26 as a
  separate plaintext character.
  (a) describe how Oscar can easily decrypt a
  message that is encrypted in this way.
  (b) Illustrate the attack by decrypting the
  following ciphertext (which was encrypted
  using a RSA Cryptosystem with n = 18721 and
  b = 25) without factoring the modulus:
  365, 0, 4845, 14930, 2608, 2608, 0."
  -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson pages 158-159.
*/

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

struct data {long c; long l;};

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 fcmp(const void *d1, const void *d2)
{
  struct data *data1 = (struct data *) d1;
  struct data *data2 = (struct data *) d2;

  if (data1->l < data2->l) return - 1;
  if (data1->l > data2->l) return + 1;
  return 0;
}

void decrypt(long b, long length,
             long n, long *c)
{
  long i;
  struct data d[26], e, *p;

  /* create a table of possible ciphertext values */
  for (i = 0; i < 26; i++) {
    d[i].c = 'a' + i;
    d[i].l = exp_mod(i, b, n);
  }
  /* sort the table on the ciphertext value */
  qsort(d, 26, sizeof(struct data), fcmp);
  printf("the possible cipher characters are as follows:\n");
  for (i = 0; i < 26; i++) {
    printf("%c %5ld ", d[i].c, d[i].l);
    if ((i + 1) % 4 == 0) printf("\n");
  }
  printf("\nthe decrypted message is as follows:\n");
  for (i = 0; i < length; i++) {
    e.c = 'a';
    e.l = c[i];
    p = bsearch(&e, d, 26, sizeof(struct data), fcmp);
    if (!p) {
      fprintf(stderr, "fatal error\n");
      fprintf(stderr, "binary search failed\n");
      exit(1);
    }
    printf("%c", p->c);
  }
}

int main(void)
{
  long b = 25, i, n = 18721;
  long c[7] = {365, 0, 4845, 14930, 2608, 2608, 0};
  long length = 7;

  printf("b = %5ld n = %5ld\n", b, n);
  printf("the ciphertext is as follows:\n");
  for (i = 0; i < length; i++)
    printf("%5ld ", c[i]);
  printf("\n");
  decrypt(b, length, n, c);
  return 0;
}