Аффинный шифр

Итак новая задачка c# и Аффинный шифр (немного познакомиться поближе можно на вики).

Заранее прошу прощение за плохой код. Исходный код на github.

Начнём из далека - с реализации расширенного алгоритма Евклида:

        private void ExtendedEuclide(int a, int b, out int x, out int y, out int d)

        {

            //a*x+b*y=nod(a,b)=d

            int q;//частное

            x = 1;

            y = 0;

            int x2 = 1;

            int x1 = 0;

            int y1 = 1;

            int y2 = 0;

            int r;//остаток

            while (b > 0)

            {

                q = a / b;

                //r = a - q * b;

                r = a % b;

                x = x2 - q * x1;

                y = y2 - q * y1;

                a = b;

                b = r;

                x2 = x1; x1 = x; y2 = y; y1 = y;

            }

            d = a;

            x = x2;

            y = y2;

        }

Итак  имеем 

a и b - 2 числа у которых необходимо найти наибольший общий делитель(nod)

x и y кратности a и b. 

d - НОД.

q - частное от деления a и b.

r - остаток от деления a и b.

Этот алгоритм нам понадобится дважды.

Дл

Необходимым условием для шифрования аффинным шифром - является взаимная простота между числом a (которое по своей сути - сдвиг между буквами) и размером алфавита. 

Для проверки на взаимную простоту необходимо чтобы НОД между a и m  = 1 (НОД (a,m)=1), то есть в наших обозначениях 

ExtendedEuclide(int a, int m, out int x, out int y, out int d)

d должен равняться 1.

После этого я генерирую из существующего алфавита - зашифрованный.

        private void CreateAlphabet(int a, int b, string alphabet)

        {

            eMod = null;

            shifr = null;

            alf = new string[alphabet.Length];

            x = new int[alphabet.Length];

            eMod = new int[alphabet.Length];

            shifr = new string[alphabet.Length];

            for (int i = 0; i < alphabet.Length; i++)

            {

                alf[i] = alphabet.Substring(i, 1);

                x[i] = i;

            }

            for (int i = 0; i < alphabet.Length; i++)

            {

                eMod[i] = (a * x[i] + b) % alphabet.Length;

            }

            for (int i = 0; i < alphabet.Length; i++)

            {

                shifr[i] = alf[eMod[i]];

            }

        }

Где

        string[] alf = new string[] {}; // алфавит как массив  букв string

        int[] x = new int[] { }; // x номер буквы

        int[] eMod = new int[] { };// зашифрованные номера букв (3x+4)mod26

        string[] shifr = new string[] { }; //зашифрованный алфавит - буквы шифротекста

После этого уже можно шифровать любой текст из алфавита.

        private void EncryptText(string text)

        {

            int[] codename = new int[text.Length];//зашифрованный номер буквы сообщения (3x+4)mod26

            

            char[] strToChar = text.ToCharArray(); //массив букв сообщения которое нужно зашифровать, проверка  пробелов

            for (int i = 0; i < strToChar.Length; i++)

            {

                if (strToChar[i] == ' ')

                {

                    strToChar[i] = '_';

                }

            }

            for (int i = 0; i < text.Length; i++)

            {

                if (strToChar[i] == '_')

                {

                    codename[i] = alf.Length-1;

                }

                else

                {

                    codename[i] = Convert.ToByte(strToChar[i] - shift); // номер буквы сообщения для шифрования в исходном алфавите

                }

            }

        }

Зашифрованный текст будет содержаться в массиве shifr[].

shift - сдвиг буквы, если мы, например имеем первой буквой алфавит русскую большую буква "А", то сдвиг соответственно будет равен 1040. Здесь мы просто подставляем вместо наших букв номер буквы из зашифрованного словаря.

С расшифровкой всё намного сложнее. И вики тут явно неполна.

        private void DecryptText(string text)

        {

            int aMinusOne, z, d;

            ExtendedEuclide(a, strAlph.Length, out aMinusOne, out z,out d);

            if (aMinusOne <= 0)

            {

                aMinusOne = aMinusOne + strAlph.Length;

            }

            int[] codename = new int[text.Length];//y

            int[] dMod = new int[text.Length]; //зашифрованный алфавит - буквы шифротекста

            char[] strToChar = text.ToCharArray();

            for (int i = 0; i < text.Length; i++)

            {

                if (strToChar[i] == '_')

                {

                    codename[i] = alf.Length - 1;

                    continue;

                }

                codename[i] = Convert.ToByte(strToChar[i] - shift);

            }

            for (int i = 0; i < text.Length; i++)

            {

                if ((codename[i] - b)<0 div="">

                {

                    dMod[i] = (aMinusOne * (codename[i] - b+strAlph.Length)) % strAlph.Length;

                    continue;

                }

                dMod[i] = (aMinusOne * (codename[i] - b)) % strAlph.Length;               

            }

        }

В вики этого нет:

1.

                aMinusOne = aMinusOne + strAlph.Length;

Дело в том что когда мы получаем обратное по модулю число, то оно может получиться отрицательным, для того чтобы далее его использовать к нему необходимо прибавить длину алфавита.

2.

                if ((codename[i] - b)<0 div="">

                {

                    dMod[i] = (aMinusOne * (codename[i] - b+strAlph.Length)) % strAlph.Length;

                    continue;

                }

у нас может получится отрицательным и значение 9*(y-4), при y<4 .="" div="">

Для исправления этой оплошности также необходимо к полученному числу прибавить длину алфавита.

Не забываем проверить  пробел и заменить его на правильный символ.

В задании была ещё сделать аффинный реккурентый шифр, но я так и не нашёл чёткого определения.

p.s.

Скорее всего выложу приложение для WP8 на github'е.