lc4.c

//Compile with: gcc lc4.c -o lc4
//Run with no arguments for help.
//If you're going to use this other than to practice pen+paper crypto (you shouldn't, use gpg) then replace the rand() call with arc4random() and link with -lbsd.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

char state[6][6], I, J;

//char (e.g. a) to int (e.g. 10)
char ctoi (char c) {
  if (c == '#')                 return 0;
  if (c == '_')                 return 1;
  if ((c >= '2') && (c <= '9')) return c - '0';
  if ((c >= 'a') && (c <= 'z')) return (c - 'a') + 10;

  printf("ERROR: '%c' is not a permitted character.\n", c);
  exit(1);
}

//int (e.g. 10) to char (e.g. a)
char itoc (char i) {
  if (i == 0)                 return '#';
  if (i == 1)                 return '_';
  if ((i >= 2) && (i <= 9))   return i + '0';
  if ((i >= 10) && (i <= 35)) return (i - 10) + 'a';

  printf("ERROR: '%c' is not a valid encoding of any character.\n", i);
  exit(1);
}

void print_state () {
  for (char i = 0; i < 6; ++i) {
    for (char j = 0; j < 6; ++j)
      printf("%c", itoc(state[i][j]));
    printf(" ");
  }
  printf("i=%d j=%d\n", I, J);
}

void init_state (const char* key) {
  for (char i = 0; i <= 35; ++i)
    state[i/6][i%6] = ctoi(key[i]);
  I = 0;
  J = 0;
  printf(" init state: ");
  print_state();
}

//c is unencoded (e.g. 'a' rather than 10)
void find_where_char_appears (char c, char* row, char* col) {
  char c_enc = ctoi(c);
  for (char i = 0; i < 6; ++i)
    for (char j = 0; j < 6; ++j)
      if (state[i][j] == c_enc)
        { *row = i; *col = j; return; }

  printf("ERROR: Invalid state: Does not contain %c.\n", c);
  exit(1);
}

void right_rotate (char r, char* c, char x, char* y) {
  //rotate
  static char buf[6];
  for (char col = 0; col < 6; ++col)
    buf[col] = state[r][col?(col-1):5];
  for (char col = 0; col < 6; ++col)
    state[r][col] = buf[col];
  //keep marker atop moved cell
  *c = (*c+1)%6;
  if (x == r) *y = (*y+1)%6;
  if (I == r)  J = ( J+1)%6;
}

void down_rotate (char* r, char c, char* x, char y) {
  //rotate
  static char buf[6];
  for (char row = 0; row < 6; ++row)
    buf[row] = state[row?(row-1):5][y];
  for (char row = 0; row < 6; ++row)
    state[row][y] = buf[row];
  //keep marker atop moved cell
  *x = (*x+1)%6;
  if (c == y) *r = (*r+1)%6;
  if (J == y)  I = ( I+1)%6;
}

//the_char and the return value are unencoded (e.g. 'a' rather than 10)
char encrypt_char (char the_char) {
  char r, c;
  find_where_char_appears(the_char, &r, &c);
  char x = (r + state[I][J]/6) % 6;
  char y = (c + state[I][J]%6) % 6;
  char c_encrypted_encoded = state[x][y];
  right_rotate( r, &c,  x, &y);
  down_rotate (&r,  c, &x,  y);
  I = (I + c_encrypted_encoded/6) % 6;
  J = (J + c_encrypted_encoded%6) % 6;
  printf("%c->%c, state: ", the_char, itoc(c_encrypted_encoded));
  print_state();
  return itoc(c_encrypted_encoded);
}

//pt and the return value are unencoded (e.g. "foo" rather than [15,24,24])
//return value must be free()d, and is nul-terminated
char* encrypt_string (const char* pt) {
  size_t len = strlen(pt);
  char* ciphertext = malloc(len+1);
  ciphertext[len] = '\0';
  for (char* ct = ciphertext; *pt; ++pt, ++ct)
    *ct = encrypt_char(*pt);
  return ciphertext;
}

//% doesn't behave as I wish for negatives
char mod6 (char c) {
  c %= 6;
  return (c<0) ? 6+c : c;
}

//the_char and the return value are unencoded (e.g. 'a' rather than 10)
char decrypt_char (char the_char) {
  char the_char_encoded = ctoi(the_char);
  char x, y;
  find_where_char_appears(the_char, &x, &y);
  char r = mod6(x - state[I][J]/6);
  char c = mod6(y - state[I][J]%6);
  char c_decrypted_encoded = state[r][c];
  right_rotate( r, &c,  x, &y);
  down_rotate (&r,  c, &x,  y);
  I = (I + the_char_encoded/6) % 6;
  J = (J + the_char_encoded%6) % 6;
  printf("%c->%c, state: ", the_char, itoc(c_decrypted_encoded));
  print_state();
  return itoc(c_decrypted_encoded);
}

//pt and the return value are unencoded (e.g. "foo" rather than [15,24,24])
//return value must be free()d, and is nul-terminated
char* decrypt_string (const char* ct) {
  size_t len = strlen(ct);
  char* plaintext = malloc(len+1);
  plaintext[len] = '\0';
  for (char* pt = plaintext; *ct; ++pt, ++ct)
    *pt = decrypt_char(*ct);
  return plaintext;
}

//*nonce will be assigned a pointer which must be free()d
//return value must be free()d
char* encrypt_message (const char* key, char** nonce, const char* signature, const char* plaintext) {
  //generate nonce
  size_t nonceSz = 6;
  *nonce = malloc(nonceSz+1);
  (*nonce)[nonceSz] = '\0';
  for (int i = 0; i < nonceSz; ++i)
    (*nonce)[i] = itoc(rand()%36);
  //encrypt
  init_state(key);
  free(encrypt_string(*nonce));
  char* ct_msg = encrypt_string(plaintext);
  char* ct_sig = encrypt_string(signature);
  //append the signature ciphertext to the message ciphertext
  size_t msglen = strlen(ct_msg);
  size_t siglen = strlen(ct_sig);
  ct_msg = realloc(ct_msg, msglen+siglen+1);
  memcpy(ct_msg+msglen, ct_sig, siglen+1);
  free(ct_sig);
  return ct_msg;
}

//return value must be free()d
char* decrypt_message (const char* key, const char* nonce, const char* signature, const char* ciphertext) {
  //decrypt
  init_state(key);
  free(encrypt_string(nonce));
  char* plaintext = decrypt_string(ciphertext);

  //verify the signature
  char* sig = plaintext + (strlen(plaintext) - strlen(signature));
  if (strcmp(sig, signature)) {
    printf("ERROR: Signature doesn't match.\n");
    exit(1);
  }
  return plaintext;
}

int main (int argc, char** argv) {
  srand(time(NULL));

  if ((argc != 4) && (argc != 5)) {
    printf("Usage:\n"\
           "  (encrypt) %s key sig msg\n"\
           "  (decrypt) %s key sig msg nonce\n"\
           "The key and signature are secret and reusable (rekey after 46,000 messages).\n"\
           "The signature doesn't match if the ciphertext is modified.\n"\
           "The nonce and ciphertext are public, the nonce may not be reused.\n"\
           "The alphabet is [#_23456789abcdefghijklmnopqrstuvwxyz].\n"
           "Keys are a permutation of the alphabet, selected uniformly at random. e.g. xv7ydq#opaj_39rzut8b45wcsgehmiknf26l.\n"\
           "Signatures and messages are restricted to the alphabet, notably the alphabet does not contain upper case letters or spaces.\n"\
           "Example: %s \"xv7ydq#opaj_39rzut8b45wcsgehmiknf26l\" \"#rubberducky\" \"this_is_a_test_of_lc4\"\n"\
           "Example: %s \"xv7ydq#opaj_39rzut8b45wcsgehmiknf26l\" \"#rubberducky\" \"r3qicv_iypnlnywas3_qn#rwmtwlwhwuu\" \"bw6ib7\" \n"\
           , argv[0], argv[0], argv[0], argv[0]);
  } else {
    char* key = argv[1];
    char* sig = argv[2];
    char* msg = argv[3];
    if (argc == 4) { //encrypt
      char* nonce = NULL;
      char* ciphertext = encrypt_message(key, &nonce, sig, msg);
      printf("nonce: %s\n", nonce);
      printf("ciphertext: %s\n", ciphertext);
      free(nonce);
      free(ciphertext);
    } else if (argc == 5) { //decrypt
      char* nonce = argv[4];
      char* plaintext = decrypt_message(key, nonce, sig, msg);
      printf("plaintext: %s\n", plaintext);
      free(plaintext);
    }
  }

  return 0;
}