Падіння у невагомість
Головна » C++ Builder: аффинный шифр и его реализация

C++ Builder: аффинный шифр и его реализация

В данной заметке я планирую кратко рассказать об аффинном шифре, а также о реализации программы шифрования и дешифрования на C++ Builder.

В качестве примера буду использовать латинский алфавит. Так что если вы нуждаетесь в шифровании кириллических символов, то, прежде всего, учтите, что кириллица содержит большее количество букв.

Начну, пожалуй, с того, что аффинная криптосистема определяется при помощи двух целых чисел: a и b. При этом 0 ≤ а, b ≤ 25. Верхняя граница обусловлена количеством букв в латинском алфавите (для тех, кто не в курсе – их 26). Кроме того, эти числа взаимно просты. В таком шифре заменой для буквы а будет jа + b (mod 26). При этом j представляет собой вес места расположения буквы в алфавите. Здесь нам предстоит работать с числовыми кодами букв. Отмечу, что все арифметические действия выполняются по модулю числа 26 (это количество букв в латинском алфавите). К примеру, если а = 3 и b = 5, то получаем следующее соответствие для числовых кодов букв (см. таблицу ниже).

0 1 2 3 4 5 6 7 8 9 10 11 12
5 8 11 14 17 20 23 0 3 6 9 12 15
13 14 15 16 17 18 19 20 21 22 23 24 25
18 21 24 1 4 7 10 13 16 19 22 25 2

Когда декодируем числа в буквы, получим следующее соответствие для букв (см. таблицу ниже).

a b c d e f g h i j k l m
f i l o r u x a d g j m p
n o p q r s t u v w x y z
s v y b e h k n q t w z c

Таким образом, исходное сообщение noteverysteambathissauna зашифруется в svkrqrezhkrfpifkadhhfnsf.

Условие взаимной простоты пары чисел а и b необходимо для обеспечения биективности отображения f(а) = jа + b. Если мы рассмотрим отображение 10a+1, где данное условие не выполняется, то буквы a и n обе отображаются в b и, следовательно, b может быть расшифрована и как a, и как n. С другой стороны, нет числового кода отображаемого в o, и, следовательно, o не требуется в алфавите подстановок. Легко найти все пары букв, отображаемых в одну и ту же букву так же, как и все буквы, не требующиеся в алфавите подстановок.

В общем, с теорией покончено. Перейдем к практике.

Первым делом создаем массив, содержащий латинский алфавит (путем посимвольного разбиения строки):

sh="abcdefghijklmnopqrstuvwxyz";
for(int i=1;i<27;i++)
 alf[i]=sh.SubString(i,1);

где alf [] – латинский алфавит.

Далее переходим к созданию массива соответствующих кодирующих букв:

for(int j=1;j<27;j++)
 {
  if((b+a*(j-1))>25)
  {int f=(b+a*(j-1))/26;
  shifr[j]=alf[b+1+a*(j-1)-26*f];
  }
  else shifr[j]=alf[b+1+a*(j-1)];
 }

где shifr [] – шифрующий алфавит.

Сам же процесс кодировки полученной строки может быть выполнен так:

  for(int i;i

где len – длина исходной строки;


ich [] – исходный массив символов;


kod [] – результирующий массив символов. 


Вот и все, собственно говоря. Пост о дешифровке создам в другой раз (если нужно, ессно).


UPD


Пост о дешифровке аффинного шрифта находится здесь.
Попередній запис X-фактор кастинг в Одессе
Наступний запис Укрпочта и Bon prix: дружба?..

femil

Пов’язані записи

43 коментарі до “C++ Builder: аффинный шифр и его реализация”

  2. Собсно берётся всё, что выше… (код дорабатывается, так что это черновик)

    #include
#include
main()
{
int a,b,i,j,len;
 char sh, str, alf[i], shifr[i], ich[i], kod[i]; 
  sh="abcdefghijklmnopqrstuvwxyz";
  str="abc";
  a=3; b=4;
  for (i=1; i<27; i++)
    alf[i]=sh.SubString(i,1);//разделение строки на символы
  for (j=1; j25)
  {int f=(b+a*(j-1))/26;
  shifr[j]=alf[b+1+a*(j-1)-26*f];
  }
  else shifr[j]=alf[b+1+a*(j-1)];
 }
 for(i; i<len+1; i++) 
   ich[i]=str.SubString(i,1);
  for(i=1; i<len+1; i++)
  {
   for(j=1; j<27; j++)
   {
    if(ich[i]==alf[j])
    {
            kod[i]=shifr[j];
            j++;
            printf();//при a=3, b=4 abc=EHK
    }
   }
  }
}

    1. Ммм…. вы уверены?
      Только что погуглила – первый результат http://msdn.microsoft.com/ru-ru/library/362314fe.aspx. Все же попробуйте расширить строковый тип данных.

        1. Тогда с маленькой попробуйте. Должен ведь работать)

          Оу, нашла еще один момент – где определение длины строки? Например, такое:

            int len=str.Length();

        2. или (еще вариант) вместо разбиения строки при помощи SubString использовать прямое обращение к элементу массива, например

          alf[i]=sh[i]

          &&

          ich[i]=str[i];

          в строках 11 и 19 соответственно.

  5. a=3; b=4;
    len=str.Length; // определение длины строки
    Console.Write(len);
    for (i = 1; i < 27; i++)
    {
    alf[i] = sh[i];//sh.SubString(i,1); //разделение строки на символы
    for (j = 1; j 25)
    {
    int f = (b + a * (j – 1)) / 26;
    shifr[i] = alf[b + 1 + a * (j – 1) – 26 * f];
    }
    else shifr[i] = alf[Math.Abs(b + 1 + a * (j – 1))];

    в последней строке индекс выходит за границы массива, что бы это могло значить?

    ps
    С предыдущими вопросами разобрался – стандарт C# (в CodeBlox) действительно не поддерживает строки, однако в MS Visual Studio 2010 есть. Сейчас в этой среде и работаю.

    1. > в последней строке индекс выходит за границы массива, что бы это могло значить?

      Дык, как объявили массив, такого он и размера – ноль и в Африке ноль. Либо пропишите определенное количество символов изначально (например так:

      String alf [26],shifr[26],sh,str2;

      ), либо объявите динамический массив – я о них писала где-то здесь

  6. Он был объявлен. Динамический массив не помогает, в случае, когда строка закомментирована индекс выходит за границы в строке shifr[i] = alf[b + 1 + a * (j – 1) – 26 * f];.

    int a, b, i, j, len; //a,b- ключи, i,j- счетчики, len- длина исходной строки
    char [] sh = {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘i’, ‘j’,’k’,’l’,’m’,’n’,’o’,’p’,’q’,’r’,’s’,’t’,’u’,’v’,’w’,’x’,’y’,’z’};
    char [] str = {‘a’,’b’,’c’};
    char [] alf = {‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘};
    //char [] shifr = {‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘};
    char [] shifr = new char[26];
    char [] ich = {‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘};
    char [] kod = {‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘};
    /* sh- строка для создания алфавита, str-строка которая шифруется, alf-алфавит, shifr-шифр.алфавит, ich – исх. символы, kod – кодир.символы
    */
    a=3; b=4;
    len=str.Length; // определение длины строки
    Console.Write(len);
    for (i = 1; i < 27; i++)
    {
    alf[i] = sh[i];//sh.SubString(i,1); //разделение строки на символы
    for (j = 1; j 25)
    {
    int f = (b + a * (j – 1)) / 26;
    shifr[i] = alf[b + 1 + a * (j – 1) – 26 * f];
    }

    else shifr[i] = alf[b + 1 + a * (j – 1)];
    //Console.Write(alf);
    }
    }
    for(i=1; i<len+1; i++) //кодировка строки
    ich=str;//.SubString(i,1);
    for(i=1; i<len+1; i++)
    {
    for(j=1; j<27; j++)
    {
    if(ich[i]==alf[j])
    {
    kod[i]=shifr[j];
    j++;
    Console.Write(kod);//при a=3, b=4 abc=EHK

    Он был объявлен. Динамический массив не помогает, в случае, когда строка закомментирована индекс выходит за границы в строке shifr[i] = alf[b + 1 + a * (j – 1) – 26 * f];.

    1. В приведенном вами коде я динамического массива не вижу. Мало того, я не понимаю зачем вы используете такого рода конструкцию:
      char [] alf = {‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘};
      и да – вам нужно 26 элементов, а в конструкции их меньше. Посчитайте. Отсюда и переполнение в первом же цикле.

  7. ОГРОМНОЕ Вам человеческое спасибо, что отзывались!

    Привожу полный рабочий код, может кому пригодится;)

    using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(«KEY:»);
int a, b, i, j, len; //a,b- ключи, i,j- счетчики, len- длина исходной строки
Console.WriteLine(«A:»);
a = Convert.ToInt32(Console.ReadLine());
Console.WriteLine(«B:»);
b = Convert.ToInt32(Console.ReadLine());

char[] sh = { ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘i’, ‘j’, ‘k’, ‘l’, ‘m’, ‘n’, ‘o’, ‘p’, ‘q’, ‘r’, ‘s’, ‘t’, ‘u’, ‘v’, ‘w’, ‘x’, ‘y’, ‘z’ };
//char[] str ; //;// = { ‘a’, ‘b’, ‘c’, ‘d’, ‘e’ };
char[] alf = { ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘,};
char[] shifr = { ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘ };
char[] ich = { ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘ };
char[] kod = { ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘ };
string str; // строка, в которую считываем сообщение
Console.WriteLine(«Message:»);
str = Console.ReadLine();

//a = 3; b = 4;
len = str.Length; // определение длины строки и её вывод
Console.WriteLine(«Lenght of your message:»);
Console.WriteLine(len);

//char[] str2 = new char[len];
for (i = 0; i < 26; i++)

alf[i] = sh[i]; //посимвольная передача алфавита
for (j = 0; j < 26; j++)
{
shifr[j] = alf[(b + a * (j)) % 26]; // формула по которой происходит шифрование
}
Console.WriteLine("ALF:");
Console.WriteLine(alf);
Console.WriteLine("SHIFR:");
Console.WriteLine(shifr);

for (i = 0; i < len; i++) //кодировка строки
ich[i] = str[i];
for (i = 0; i < len+1; i++)
{
for (j = 0; j < 26; j++)
{
if (ich[i] == alf[j])
{
kod[i] = shifr[j];
j++;
} //if
} //for
} //for
Console.WriteLine("KOD:");
Console.WriteLine(kod); //при a=3, b=4 abc=ehk

for (int x = 0; x < 26; x++) // дешифровка: сборка шифр алфавита
alf[x] = sh[x];

for (int y = 0; y < 26; y++)
{
shifr[y] = alf[(b + a * (y)) % 26];
}
for (int x = 0; x < len; x++) // непосредственно дешифровка
ich[x] = kod[x];
for (int x = 0; x < len + 1; x++)
{
for (int y = 0; y < 26; y++)
{
if (ich[x] == shifr[y])
{
kod[x] = alf[y];
y++;

}
}
}
// for (int x = 0; x < len+1; x++)
// str2[len-1] = kod[x];
Console.WriteLine("DEKOD:");
//Console.Write(str2);
Console.WriteLine(kod);
Console.ReadLine();
} //main
}
}

    ps
    Постараюсь больше не тревожить... Разве что другие шифры разбирать будете;)

      1. Ну просто мне говорили, что их различие заключается в том, что в аффинном рекуррентном шифре для каждого символа открытого текста вычисляется новое ключевое значение на основе предыдущего.

        1. Вы точно говорите о шифре подстановки (которым является аффинный)?
          Просто вот это

          для каждого символа открытого текста вычисляется новое ключевое значение на основе предыдущего

          совсем не вяжется с данным видом шифров.

          1. Вот что я сказал это и есть отличие аффинного рекуррентного шифра от аффинного шифра.

          2. Я так полагаю что вы мне ничем не можете помочь???

          3. Выкладывайте СВОИ наработки, уточните что на основе чего генерируется в вашем таинственном “Афинном рекуррентном шифре”. Или вы предлагаете разобраться в чем-то что “вам сказали” да ещё и программу написать?

          4. Да, мне надо в этом разобраться и написать программу. Но дело в том, что я не силен в программировании(((

          5. Еще раз: аффинный шифр является одним из шифров подстановки – алфавит шифрации един для любого шифруемого символа, т.е. он не изменяется в процессе шифрования. То, о чем вы говорите, это не аффинный шифр.

            Я так полагаю что вы мне ничем не можете помочь???

            И как уже ниже сказали: для того, чтоб помочь – нужно видеть, что уже сделано.

  9. Здравствуйте)Помогите пожалуйста. Вроде делала все как у Вас в инструкции, но почему-то неправильно работает(
    Алфавит почему-то не как у Вас(не смотря на то, что а=3,b=5, без одной буквы, и в закодированном слове буквы тоже не все..
    пишу на с++ в code::blocks

    #include 
#include 
using namespace std;

int main()
{
   string sh ="abcdefghijklmnopqrstuvwxyz";
    int i,j,a,b,f,len;
  string alf[26],shifr[26],ich[26],str1,kod[26];

cout << sh << 'n';
    for(int i=1;i<27;i++)
        alf[i]=sh.substr(i,1);

a=3; b=5;

    for(int j=1;j25)
        {
            int f=(b+a*(j-1))/ 26;
            shifr[j]=alf[b+1+a*(j-1)-26*f];
        }
        else shifr[j]=alf[b+1+a*(j-1)];
    }

for(int j=1;j<27;j++)
    cout << shifr[j];

cout << "n" <> str1;
len = str1.length();

cout << "v texte " << len <<" simvolov"<< 'n';
cout << "shifr:"<< 'n';

  for(int i=1;i<(len+1);i++)
    ich[i]=str1.substr(i,1);
  for(int i=1;i<len+1;i++)
  {
    for(int j=1;j<27;j++)
    {
        if(ich[i]==alf[j])
        {
            kod[i]=shifr[j]; //cout << kod[i];
            j++;
        }
    }
  }

for(int i=1;i<len;i++)
  cout << kod[i];

    return 0;
}

    Скриншот выполнения:
    http://s017.radikal.ru/i431/1412/ff/c9cfdf6889db.png

  10. Глючно отобразился код, жалко, что нельзя отредактировать сообщение. Попробую код без тега:
    #include
    #include
    using namespace std;

    int main()
    {
    string sh =”abcdefghijklmnopqrstuvwxyz”;
    int i,j,a,b,f,len;
    string alf[26],shifr[26],ich[26],str1,kod[26];

    cout << sh << 'n';
    for(int i=1;i<27;i++)
    alf[i]=sh.substr(i,1);

    a=3; b=5;

    for(int j=1;j25)
    {
    int f=(b+a*(j-1))/ 26;
    shifr[j]=alf[b+1+a*(j-1)-26*f];
    }
    else shifr[j]=alf[b+1+a*(j-1)];
    }

    for(int j=1;j<27;j++)
    cout << shifr[j];

    cout << "n" << "vvedi text bez probelov: " <> str1;
    len = str1.length();

    cout << "v texte " << len <<" simvolov"<< 'n';
    cout << "shifr:"<< 'n';

    for(int i=1;i<(len+1);i++)
    ich[i]=str1.substr(i,1);
    for(int i=1;i<len+1;i++)
    {
    for(int j=1;j<27;j++)
    {
    if(ich[i]==alf[j])
    {
    kod[i]=shifr[j]; //cout << kod[i];
    j++;
    }
    }
    }

    for(int i=1;i<len;i++)
    cout << kod[i];

    return 0;
    }

      1. Доброй ночи. К сожалению, исходники погибли вместе со старым винтом ((( Сейчас уже копирую исходник сразу к записи, но старые утеряны безвозвратно ;(

        1. огромная печаль((…может быть у вас где-нибудь завалялся расширенный алгоритм евклида?(на с++) или другие шифры =) попытка не пытка..может мне повезет =)

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

          3. (((
            к сожалению, нету.

            Про метод Гронсфельда написала, потому что нашла реализованным. Надо, наверно, пост о нем наваять =)

  13. Подскажите что не так с программой?
    #include
    #include
    #include

    using namespace std;

    int main();
    {

    int a,b,i,j,len;
    String sh, str, alf[i], shifr[i], ich[i], kod[i];
    sh=”abcdefghijklmnopqrstuvwxyz”;
    for (int i=1; i<27; i++)
    alf[i]=sh.SubString(i,1); //разделение строки на символы
    str="abc";
    a=3; b=5;

    for ( int j=1; j25)
    int f=(b+a*(j-1))/26;
    shifr[j]=alf[b+1+a*(j-1)-26*f];
    }
    else shifr[j]=alf[b+1+a*(j-1)];
    }
    for(int i; i<len+1; i++)
    ich[i]=str.SubString(i,1);
    for(int i=1; i<len+1; i++)
    {
    for(int j=1; j<27; j++)
    {
    if(ich[i]==alf[j])
    {
    kod[i]=shifr[j];
    j++;
    printf();//при a=3, b=5 abc=EHK
    }
    }
    }

    {

    for(int i=1;i<len;i++)
    cout << kod[i];

    return 0;
    }
    Выводит ошибку expected unqualified id before '{' token

    1. String sh, str, alf[i], shifr[i], ich[i], kod[i];
      Вот здесь у вас динамические массивы, но созданы они неверно. Либо создавайте правильно, либо сразу указывайте размерность.

Залишити відповідь