Szyfr liniowy problem

Mam dziwny poblem z szyfrem liniowym.
Wzór na szyfrowanie jest nastepujacy:
C(x) = a * x + b (mod M)
Wzór na deszyfrowanie:
D(y) = a^{-1 * y - a}-1 * b (mod M)
a, b - losowe liczby tworzące klucz, należące do pierscienia Z_26
a^-1 - element odwrotny w pierscieniu
a musi byc odwracalne, czyli NWD(a, 26) = 1 (bo inaczej nie mozna uzyc powyzszego wzoru).

Aby operacje byly wykonywane w pierscieniu Z_26 odejmuje od kodu ASCII 97, czyli kod 'a'. Potem po wyliczeniu z powrotem dodaje 97, aby wyswietlic to jako normalny kod ASCII, a nie jako liczbe w Z_26.

Co jest wazne:

• piszac numbers[a] uzyskuje element odwrotny do a w pierscieniu Z_26. Jezeli taki element nie istnieje to numbers[a] jest rowne -1.

Sprawdzilem, ze elementy odwrorne sa generowane prawidlowo (w sensie iloczyn elementu odwrotnego i elementu daje 1 w pierscieniu Z_26).

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

/* zalozenie - obsluga malych liter bez spacji */

#define M 26
#define MSGSIZE 20

int nwd(int a, int b)
{
  while (a != b) {
    if(a > b)
      a = a - b;
    else
      b = b - a;
  }
  return a;
}

int main(int argc, char** argv)
{
  int numbers[M];
  char msg[MSGSIZE];
  // tablica liczb odwracalnych w pierscieniu Z_m
  int* odwracalne = NULL;
  int j = 0; // ilosc elementow odwracalnych

  // generate Z_m
  numbers[0] = -1;
  for(int i = 1; i < M; ++i)
    if(nwd(i, M) != 1)
      numbers[i] = -1;
    else {  
      for(int j = 1; j < M; ++j)
	if( (i * j % M ) == 1 ) {
	  numbers[i] = j; // wpisz liczbe odwrotna
	  continue;
	}
      if( (odwracalne = realloc(odwracalne, ( (j + 1) * sizeof(int)))) == NULL ) {
	perror("Malloc error!\n");
	exit(1);
      }
      odwracalne[j] = i;
      ++j;
    }
    
  // choose number a /in Z_m <=> NWD(a, m) = 1
  // wybrano odwracalne a i dowolne b
  srand(time(NULL));
  int tmp = (int)(rand() / (RAND_MAX + 1.0) * j);
  int a = numbers[odwracalne[tmp]];
  // choose number b in Z_m
  int b = (int)(rand() / (RAND_MAX + 1.0) * M);
  printf("a: %d\nb: %d\n", a, b);  

  printf("Podaj wiadomosc do zaszyfrowania: ");
  scanf("%19s", msg);
    
  for(int i = 0; i < strlen(msg); ++i) {
    msg[i] = msg[i] - 97; // przejdz do pierscienia
    msg[i] = (a * msg[i] + b) % M; // przekoduj
    msg[i] = msg[i] + 97; // wroc do ASCII
  }

printf("Zaszyfowany: %s\n", msg);
  
  for(int i = 0; i < strlen(msg); ++i) {
    // wroc do pierscienia
    msg[i] = msg[i] - 97;
    // odkoduj: numbers[a] - element odwrotny do a
    if(numbers[a] == -1) {
      printf("Blad!\n");
      exit(1);
    }
    msg[i] = (numbers[a] * msg[i] - numbers[a] * b) % M;
    // wroc do ASCII
    msg[i] = msg[i] + 97;
  }
  
  printf("Po odszyfrowaniu: %s\n", msg);
  free(odwracalne);
    
  return 0;
}

Co zauwazylem:

• dla kazdej litery jest takie same przeklamanie

Czasemi dziala:

[margor@t61p szyfr_liniowy]$ ./crypt 
a: 11
b: 11
Podaj wiadomosc do zaszyfrowania: dupa
Po zaszyfrowaniu: sxul
Po odszyfrowaniu: dupa

Przykladowe przeklamanie:

a: 15
b: 19
Podaj wiadomosc do zaszyfrowania: mazda
Po zaszyfrowaniu: rtemt
Po odszyfrowaniu: Sa`Ja
a: 23
b: 6
Podaj wiadomosc do zaszyfrowania: samiec
Po zaszyfrowaniu: egwiua
Po odszyfrowaniu: YamieI

Nie widzę co robię źle (ale podejrzewam przesunięcia ASCII). Będę wdzięczny za pomoc.

podejrzewam, że wyrażenie

numbers[a] * msg[i] - numbers[a] * b

dla niektórych wartości może być ujemne, stąd przesunięcia

Dzięki, tu się rzeczywiście zaczyna źródło problemu. Przykładowo dla sztywno ustawionego b = 1jest dużo lepiej. Ale zmniejsza to losowość klucza i tak się nie powinno tego obchodzić. Poza tym przekłamania i tak zdarzają się.

Rozwiązanie: sprowadzić ujemną liczbę do pierścienia, czyli dodawać do skutku aż będzie dodatnia i śmiga aż miło.