Метод Касиски

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск


Метод Каси́ски (Метод Кази́ского) — метод криптоанализа полиалфавитных шифров, таких как шифр Виженера. Разработан независимо Фридрихом Касиски и Чарльзом Бэббиджем.

История[править | править вики-текст]


В 1863 году Фридрих Вильгельм Касиски опубликовал свой 95-страничный труд «Die Geheimschriften und die Dechiffrirkunst»(«Тайнопись и искусство дешифрирования», оригинал рукописи находится в библиотеке в Мюнхене). Это была книга об атаках на шифры, созданные с помощью полиалфавитной замены. В этой книге Касиски описывает свое крупное открытие в криптоанализе, а именно - алгоритм, известный всем как «Тест Касиски»[1] или «Тест Казисского»[2]. Этот алгоритм позволял взламывать шифр Виженера, взлом которого считался невозможным на протяжении 400 лет. Открытие Касиски уступает по важности только работе Аль-Кинди, известного как "философ арабского мира".[3], который открыл метод частотного анализа для дешифрования текста.

Однако за десть лет до Касиски успеха во взломе шифра Вижинера добился Чарльз Бэббидж. Бэббидж сделал своё открытие в 1854 году, но о нем так никто и не узнал, потому что Бэббидж так и не опубликовал его. Это обнаружилось только в двадцатом веке, когда ученые принялись разбирать его многочисленные заметки. Так почему же Бэббидж не сообщил о том, что сумел взломать этот имеющий столь важное значение шифр? Несомненно, была у него такая привычка — бросать незавершенными значительные и многообещающие начинания и не сообщать о своих открытиях. Имеется, однако, и другое объяснение. Бэббидж сделал свое открытие вскоре после того, как разразилась Крымская война, и в одной из теорий было выдвинуто предположение, что оно давало Британии явное преимущество над Россией, её противником. Вполне возможно, что британская секретная служба потребовала от Бэббиджа сохранить свою работу в секрете, тем самым обеспечив себе девятилетнюю фору перед остальным миром.[1] Так или иначе, взлом шифра Виженера закреплен за Касиски. «Метод Касиски» открыл путь и к другим полиалфавитным решениям, которые до сих пор используют правительства разных стран. Его труд признан величайшей книгой криптологии.


Достижения Чарльза Бэббиджа и Фридриха Касиски показали, что шифр Виженера небезопасен. Это открытие повлекло смятение у криптографов того времени, ведь они теперь не могли гарантировать секретность. И почти на полвека криптоанализ обрел контроль в коммуникационной войне. Криптографы не могли придумать ничего нового, что повлекло рост интереса у широкой публики к шифрам. В конце концов был найден шифр на замену шифра Виженера - так называемый шифр Бейла.[1]

Описание[править | править вики-текст]

Идея метода основана на том, что ключи являются периодическими, а в естественном языке существуют часто встречающиеся буквосочетания: биграммы и триграммы. Это наводит на мысль, что повторяющиеся наборы символов в шифротексте - повторения популярных биграмм и триграмм исходного текста.

Метод Касиски позволяет криптоаналитику найти длину ключевого слова, используемого в полиалфавитном шифре. Как только длина ключевого слова обнаружена, криптоаналитик выстраивает зашифрованный текст в n колонках, где n — длина ключевого слова. Тогда каждую колонку можно рассматривать как зашифрованный моноалфавитным шифром текст, который можно подвергнуть частотному анализу.

Метод Касиски заключается в поиске групп символов, которые повторяются в зашифрованном тексте. Группы должны состоять из не менее чем трех символов. Тогда расстояния между последовательными возникновениями групп, вероятно, будут кратны длине ключевого слова. Предполагаемая длина ключевого слова кратна наибольшему общему делителю всех расстояний.

Причина, по которой метод работает — это то, что если две группы символов повторяются в исходном тексте и расстояние между ними является кратным длине ключевого слова, то буквы ключевого слова выровняются с обеими группами.

Сложность метода Касиски состоит в необходимости поиска повторяющихся строк. Это сложно сделать вручную, но значительно проще на компьютере. Однако метод требует вмешательства человека, так как некоторые совпадения могут оказаться случайными, что приведет к тому, что наибольший общий делитель всех расстояний будет равен 1. Криптоаналитик должен выяснить, какие длины являются подходящими. И, в конечном итоге, человек должен проверить правильность подобранного периода исходя из осмысленности расшифрованного текста.

Примеры[править | править вики-текст]

Шифрование полиалфавитным шифром с периодом 4[править | править вики-текст]

Пусть шифруется следующий текст. Шифрование происходит без учета знаков препинания и различия строчных и прописных букв. Пробелы оставлены в тексте, чтобы его удобно было читать, при шифровании же пробелы были опущены:[4]

Игры различаются по содержанию характерным особенностям а также по тому какое место они занимают в жизни детей их воспитании и обучении Каждый отдельный вид игры имеет многочисленные варианты Дети очень изобретательны Они усложняют и упрощают известные игры придумывают новые правила и детали Например сюжетно ролевые игры создаются самими детьми но при некотором руководстве воспитателя Их основой является самодеятельность Такие игры иногда называют творческими сюжетно ролевыми играми Разновидностью сюжетно ролевой игры являются строительные игры и игры драматизации В практике воспитания нашли свое место и игры с правилами которые создаются для детей взрослыми К ним относятся дидактические подвижные и игры забавы В основе их лежит четко определенное программное содержание дидактические задачи и целенаправленное обучение. Для хорошо организованной жизни детей в детском саду необходимо разнообразие игр так как только при этих условиях будет обеспечена детям возможность интересной и содержательной деятельности Многообразие типов видов форм игр неизбежно как неизбежно многообразие жизни которую они отражают как неизбежно многообразие несмотря на внешнюю схожесть игр одного типа модели


Воспользуемся полиалфавитным шифром с периодом 4:

АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ   - чистый алфавит
ЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЖЗИ   - 1-й алфавит
ГАЭЪЧФСОЛИЕВЯЬЩЦУРНКЗДБЮЫШХТПМЙЖ   - 2-й алфавит
БФЗЪНАУЖЩМЯТЕШЛЮСДЧКЭРГЦЙЬПВХИЫО   - 3-й алфавит
ПЪЕРЫЖСЬЗТЭИУЮЙФЯКХАЛЦБМЧВНШГОЩД   - 4-й алфавит

Зашифрованное сообщение:

СЪСШ ЩГЖИСЮБЩЫРО ФЧ РЛЫОУУПЦЛЫ ЦЙУБЭЫФСЮДЯ ЛКЧААЮЦЩДХИЯ Б ХЙЕУЖ ШЩ ЧЙХК ЯПУЩА УОРЧЙ ЧЬЩ ЬЙЬЩУЙЙЧ Е ПЛЖЮС ЧАХОИ ЩЦ ЛЩДФСНБЮСЛ Щ ЙККЦЖЦЛЩ ЭЙСНШТ ЩЧЫОВХЮДИ ЗЗН ЛЪЯД ЛЕЖОН ЕЮЧЪЛМСРТЖЦЬВЖ ЛГСЗЙЬЧШ НФЧЗ ЧЮАЮЕ ЛЖЙКУАХЙНАИЕЬВ ЙЦЛ ККФЩУЮИЙЧ З ЬЦСЙВГЫХ СОЗЖЪНШШО ЛЪЯД ЦСЗНКЕШЛГЫХ ЦЩЗШО ЦСПЛЛТП С ЧАХЙВЩ ЮЙЦСЗХФС КЗСАХЦЩ СЙФФЗШО ЛЪЯД РЛЬНГЫХЪЖ ДПХЛЕЗ НФЧГХЛ ШЙ ШУЩ ЮОЕЛХЧУЛУ ЩКЯЙЛЩНКЫЭА ЕЧРЮЗЫГЧЖФЖ ЩЦ ЧРШЙЛЩМ ДЛВОЖЫРО КЙЯЛЫОЖЧЖФПШЙЪНХ ХЙЕЩЖ СЪСШ СЬЛРНГ ШПРТЗПЗН ЧЕЧУЦЖЪЕЩУС РЫСОНШЙ ЩЩТЖЛТЕЗ СЪСПХЛ СПРЬЛЕСЧШЙЪНХЩ ЪЙУЖЫЬЛ ЯЧВАЕЧИ ЩРЩТ ОЕФЖЫХЪЖ ДХЩЩЩХОВХЮДФ ЩРЩТ Щ ЗМУВ ЫЩГЕПЫЛЖПЯЛЩ Е ШУБЭЫЛЯЖ ЛЩДФСНБЮСЖ ШПБВЩ КЛЩА УОРЧЙ С ЛЪЯД Р ЮЯЙЭЩИЙЯЩ ЭЧНЛЯДФ ДЙРЧБЩЫРО ЫФЖ НЖЫФМ ЕРУЛКФТЕЗ У ЬЩУ ЧНШЙЪЖЧКИ ЧЩЫЙЕЧЗАФДЭСФ ЮЙНЭЩСЦТА З СЪСШ РГФПЛТ З ЙЪЬЛЕО ЛР ИОСЩХ АФЧЭЧ ЩЮЯОЧАИОЬШЙО ЦСЙМУБУХЬЛЖ ЪЩНЖЩСБЮСФ НЗНГЯХСЮАКУЛА ЬЙЧБМС Л ГЖФФШПШУБЕФФШЮЧФ ЛЪЬЮАЮСФ НИИ ДЛЯЧЫЛ ЙЩЪБЮСОЛЕЙЬШЙТ СЩЬЦЛ НЖЫФМ Е НФЧКУЩЕ КЙЧК ЮОЩФЦЧЧЩУЧ УБЬЦЩЛЪЩГЖЗО ЛЪЯ ЫГЯ ЭЙЕ ЧЙФПЯЙ ШУЩ ОЫЛР АЪВЛЕСЖР ЪЬЧАХ ЧААКШФЦЖЦГ НЖЫЖЕ ЕЧОЕЙПЬЛКЫП ЩЮЫФСЖЪЬЛТ С РЛЫОУУПЫФТГЦЩМ ЫОЖЧЖФПШЙЪНЩ УЦЩЪЙЧАСПРЛА ХСЦЛЕ ЛЛНЙЛ ЗЛЯХ ЛЪЯ ЦФЩЬКФУЮЧ ЕБЭ ЦФЩЬКФУЮЧ ЯШЙМЩЛЪЩГЖЗО СЩЬЦЛ ЯЙЫЩСАЗ ЩШЗ ЧНСППГЫХ УГЯ ЮОЛЖЪОСШЙ ХЬЛРЧЩФЯЙОЩЖ ЦФДУЧНСД ЦГ ЗЮОЫШЩЗ РРЙПФДХЕ ЛЪЯ ЧЧШЙМЩ ЧЗШГ ЕЙНФТЗ

Воспользуемся методом Касиски для того, чтобы расшифровать это сообщение. Но предварительно подсчитаем число появлений каждой буквы в шифротексте. Эти данные приведем в таблице, где i в первой строке означает букву алфавита, а fi во второй строке – это число появлений этой буквы в шифротексте. Всего в нашем шифротексте имеется L = 1036 букв.

i А Б В Г Д Е Ж З И Й К Л М Н О П
fi 26 15 11 21 20 36 42 31 13 56 23 70 10 33 36 25
i Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
fi 28 54 15 36 45 32 31 57 35 72 32 35 27 11 30 28
  • Группа СЪС встречается в позициях 1, 373, 417, 613. Соответствующие расстояния равны

373 - 1 = 372 = 4 * 3 * 31

417 - 373 = 44 = 4 * 11

613 - 417 = 196 = 4 * 49.

Наибольший общий делитель равен 4. Делаем вывод, что период кратен 4.

  • Группа ЩГЖ встречается в позициях 5, 781, 941. Соответствующие расстояния равны

781 - 5 = 776 = 8 * 97

941 - 781 = 160 = 32 * 5.

Делаем вывод, что период кратен 8, что не противоречит выводу для предыдущей группы (кратен 4).

  • Группа ЫРО встречается в позициях 13, 349, 557. Соответствующие расстояния равны

349 - 13 = 336 = 16 * 3 * 7

557 - 349 = 208 = 16 * 13.

Делаем вывод, что период кратен 4.

Правдоподобным является предположение, что период равен 4.

Далее текст подвергается частотному анализу.

Шифрование с помощью секретного слова[править | править вики-текст]

Посмотрим на следующий зашифрованный текст:[5]

UTPDHUG NYH USVKCG МУСЕ FXL KQIB. WX RKU GI TZN, RLS BHZLXMSNP KDKS; СЕВ Ш HKEWIBA, YYM SRB PER SBS, JV UPL О UVADGR HRRWXF. JV ZTVOOV УН ZCQU У UKWGEB, PL UQFB Р FOUKCG, TBF RQ VHCF R KPG, 0U КЕТ ZCQU MAW QKKW ZGSY, ЕР PGM QKETK UQEB DER EZRN, MCYE, MG UCTESVA, WP КЕТ ZCQU MAW KOIJS, LCOV NTHDNV JPNUJVB Ш GGV RWX ONKCGTHKFL XG VKD, ZJM VG CCI MVGD JPNUJ, RLS EWVKJT ASGUCS MVGD; DDK VG NYH PWUV CCHIIY RD DBQN RWTH PFRWBBI VTTK VCGNTGSF FL IAWU XJDUS, HFP VHSF, RR LAWEY QDFS RVMEES FZB СНН JRTT MVGZP UBZN FD ATIIYRTK WP КЕТ HIVJCI; TBF BLDPWPX RWTH ULAW TG VYCHX KQLJS US DCGCW OPPUPR, VG KFDNUJK GI JIKKC PL KGCJ lAOV KFTR GJFSAW KTZLZES WG RWXWT VWTL WP XPXGG, CJ EPOS VYC BTZCUW XG ZGJQ PMHTRAIBJG WMGEG. JZQ DPB JVYGM ZCLEWXR:CEB lAOV NYH JIKKC TGCWXE UHE JZK. WX VCULD YTTKETK WPKCGVCWIQT PWVY QEBFKKQ, QNH NZTTWIREL IAS VERPE ODJRXGSPTC EKWPTGEES, GMCG TTVVPLTEEJ; YCW WV NYH TZYRWH LOKU MU AWO, KEPM VG BLTP VQN RD DSGG AWKWUKKPL KGCJ, XY GPP KPG ONZTT ICUJCHLSE KET DBQHJTWUG. DYN MVCK ZT MEWCW HTWE ED JL, GPU YAE CH LQ! PGR UE, YH MWPP RXE CDJCGOSE, XMS UZGJQJL, SXVPN HBG!

Исследуем расстояния между сочетаниями WX. Некоторые из расстояний равны 9, 21, 66, 30. Какие-то совпадения могут оказаться случайными, а какие-то содержат информацию о длине ключа. Вычислим НОД (попарно):

НОД(30,66) = 6

НОД(9,66) = 3

НОД(9,30) = 3

НОД(21,66) = 3

Однако, маловероятно, что длина состоит всего лишь из трех букв, поэтому предположим числа 9 и 21 случайными и будем считать длину ключа равной 6.

Далее берется каждая шестая буква шифротекста и применяется частотный анализ - определяется первая буква ключа, за ней вторая и так далее. Определение буквы происходит с помощью построения гистограммы. Сравниваем частоту повторяемости каждой шестой буквы, начиная с первой, со среднестатистической (см. рисунок). Таким образом находим, что ключевое слово "crypto".

Исходный текст (отрывок из произведения Чарльза Диккенса "Рождественская песнь в прозе.Святочный рассказ с привидениями"):

Scrooge was better than his word. He did it all, and infinitely more; and to Tiny Tim, who did not die, he was a second father. He became as good a friend, as good a master, and as good a man, as the good old city knew, or any other good old city, town, or borough, in the good old world. Some people laughed to see the alteration in him, but he let them laugh, and little heeded them; for he was wise enough to know that nothing ever happened on this globe, for good, at which some people did not have their fill of laughter in the outset; and knowing that such as these would be blind anyway, he thought it quite as well that they should wrinkle up their eyes in grins, as have the malady in less attractive forms. His own heart laughed: and that was quite enough for him. He had no further intercourse with Spirits, but lived upon the Total Abstinence Principle, ever afterwards; and it was always said of him, that he knew how to keep Christmas well, if any man alive possessed the knowledge. May that be truly said of us, and all of us! And so, as Tiny Tim observed, God bless Us, Every One!

Примеры реализации[править | править вики-текст]

Реализация на языке СИ:

#include <stdio.h>
#include <string.h>
#include <malloc.h> 

int l[500];
int nods[500];
int nl=0;


int nod(int a,int b)
{
    int i;
    for (i=a;i>1;--i)
        if ((a%i==0)&&(b%i==0)) return i;
    return 1;
}



int main()
{    
    char *s=(char *)calloc(1,sizeof(char));
    char fname[100];
    char c;
    unsigned int n=0,i,j,keylen;
    FILE *f;
    printf("file name: ");
    scanf("%s",fname);
    f=fopen(fname,"r");
    if (f==NULL){
            printf("file not found\n");
            return 1;
    }
    
    for (i=0;i<500;++i)
        nods[i]=0;

    
    while (!feof(f))
        if (fread(&c,1,1,f)){     
            s[n++]=c;              
            s=(char *)realloc(s,n+1);
        }

    s[n]='\0';

    char str1[4],str2[4];
    
    for (i=0;i<strlen(s);++i)
    {
        str1[0]=s[i];
        str1[1]=s[i+1];
        str1[2]=s[i+2];
        str1[3]='\0';
        
        for (j=i+1;j<strlen(s);++j)
        {
            str2[0]=s[j];
            str2[1]=s[j+1];
            str2[2]=s[j+2];
            str2[3]='\0';
            
            if (!strcmp(str1,str2)) l[nl++]=j-i;
            
        }
    }
    
    for (i=0;i<nl;++i)
        for (j=i+1;j<nl;++j)
            nods[nod(l[i],l[j])]++;


    keylen=0;
    for (i=2;i<500;++i)
        if (nods[keylen]<nods[i]) keylen=i;
        
    printf("%d\n",keylen);
    
    free(s);
    return 0;
}

Реализация на языке С#:

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

namespace Rasstoyanie
{
    class Program
    {
        private class Pair//класс пары, нужен для подсчета в конце
        {
            public int Index { get; set; }//индекс элемента в массиве
            public int Value { get; set; }//значение элемента в массиве
        }
        public static int digramLength = 3;//количество символов, которое должно совпадать
        public static int gcd(int a, int b)
        {
            if (b == 0)
            {
                return a;
            }
            else
            {
                return gcd(b, a % b);
            }
        }
       
        static void Main(string[] args)
        {

            string text = File.ReadAllText("text.txt", Encoding.GetEncoding(1251));//считываем текст
            List<int> repeatCount = new List<int>();//массив, который содержит все длины
            //заполняем этот массив, ища расстояние между одинаковыми триграммами
            for (int i = 0; i < text.Length - digramLength + 1; i++)
            {
                string temp = text.Substring(i, digramLength);
                for (int j = i + 1; j < text.Length - digramLength + 1; j++)
                {
                    string temp2 = text.Substring(j, digramLength);
                    if(temp.Equals(temp2))
                    {
                        repeatCount.Add(j - i);
                    }
                }
            }
            int[] nods = new int[5000];//массив для подсчета количества НОД
            //В случае если НОД двух расстояний равен q, то увеличваем nods[q] на 1
            for (int i = 0; i < repeatCount.Count; ++i)
                for (int j = i + 1; j < repeatCount.Count; ++j)
                    nods[gcd(repeatCount[i], repeatCount[j])]++;
            nods[0] = 0;
            //загоняем все в новый массив, чтобы удобно отсортировать
            List<Pair> ans= new List<Pair>();
            for (int i = 2; i < 500; ++i)
            {
                ans.Add(new Pair()
                {
                    Index = i,
                    Value = nods[i]
                });
            }
            IEnumerable<Pair> anss = ans.OrderByDescending(p => p.Value).Take(10);//сортируем и берем первые 10 результатов
            string stringAns = "";
            //выводим ответ
            foreach (var s in anss)
            {
                if(s.Value>0)
                {
                    stringAns += s.Index + " ";
                }
            }
            File.WriteAllText("ans.txt", stringAns);
        }
    }
}

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • Габидулин Э. М., А. С. Кшевецкий, А. И. Колыбельников. Защита информации. — МФТИ, 2011. — 262 с.
  • Н. Смарт. Криптография. — Техносфера, 2005. — 526 с.
  • С. Сингх. Тайная история шифров и их расшифровки. — Астрель, 2006. — 447 с. [1]
  • Tilborg H.C.A. Fundamentals of Cryptography. A Professional Reference and Interactive Tutorial. — Kluwer, 1999. — 503 с.
  • Menezes A.J., Oorschot P.C., Vanstone S.A. Handbook of Applied Cryptography. — CRC Press, 1996. — 816 с. [2]

Ссылки[править | править вики-текст]