Взлом XOR-шифра - Помощь студентам

Rad-X · 03.05.2013, 15:02

Здравствуйте, пишу программу для взлома XOR шифра.
Прочитал по этому поводу в "Прикладной криптографии" Брюса Шнайера.

Там описан следующий алгоритм:

"Предположим,что открытый текст использует английский язык.Более того,пусть длина ключа любое небольшое число байт.Ниже описано,как взломать этот шифр:

1.Определим длину ключа с помощью процедуры,известной как ПОДСЧЕТ СОВПАДЕНИЙ.
Применим операцию XOR к шифротексту,используя в качестве ключа сам шифротекст с различными смещениями,и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа,то совпадет свыше 6 процентов байтов. Если нет,то будут совпадать меньше чем 0.4 процента( считая,что обычный ASCII текст кодируется случайным ключом,для других типов открытых текстов числа будут другими). Это называется показателем совпадений. Минимальное смещение от одного значения,кратного длине ключа,к другому и есть длина ключа.

2. Сместим шифротекст на эту длину и проведем операцию XOR для смещенного и оригинального шифротекстов.Результатом операции будет удаление ключа и получение открытого текста,подвергнутого операции XOR с самим собой,смещенным на длину ключа. Так как в английском языке на один байт приходится 1.3 бита действительной информации,существующая значительная избыточность позволяет определить способ шифрования."

Немного не понимаю, что мы считаем совпадающими байтами? Совпадения между строкой шифротекста и полученной строкой? Или только в полученной строке?

Нашел на википедии статью http://ru.wikipedia.org/wiki/%D0%98%...BD%D0%B8%D0%B9

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

Может дело в том, что шифрую только 32 буквы русского алфавита? Но ведь при смещении кратном длине ключа всплески должны быть, но их нету.

Пишу на C++

s-andriano · 03.05.2013, 16:48

Если верить статье по приведенной Вами ссылке, то не 0.4%, а 4%.
А разницу между 4% и 6% на не очень длинном тексте уловить будет затруднительно.
Я бы оценил минимальную длину текста в 3000-10000 знаков.

Rad-X · 03.05.2013, 19:22

Ну там же написано сместить и ксорить. Вот я сместил строку, отксорил с исходной, и считаю совпадения ксоровской с исходной строкой, ведь так?

У меня строка длинной около 500 символов и после той процедуры которую я описал выше, для всех 500-та смещений получается одинаковый индекс совпадений - 5,4%

вот код:

Код:

void encryptnokey()
{
    FILE *in,*out,*key;
    fopen_s(&in,"out.txt","rb");
    fopen_s(&out,"encryptnotkey.txt","wb");
    char textorg[20000],text[20000];
    int lenorg=0,len=0;
    
    while(!(feof(in)))  //считываем из файла и удаляем все лишние символы кроме русских
    {    unsigned char c;
        c=fgetc(in);
        textorg[lenorg]=c;
        if ((c>191)&&(c<256)) {text[len]=c;len++;}
        lenorg++;
        if (feof(in)) break;
    }
 
    len--;
    lenorg--;
 
    int det=0,all=0;
    double max=0;
    
  srand(time(0));
 
    for(int i=0;i<len/2;i++)
    {
        int ind[32],indxr[32];
    double indsum=0;
 
        for(int j=0;j<32;j++)
        {
        ind[j]=0;
        indxr[j]=0;
        }
 
 
        for(int j=0;j<(len);j++)
        {
            unsigned char c,k,xr;
 
            c=text[i];
            k=text[(j+i)%len];
        //    k=text[rand()%len];   
            int reg=2;
            
            if ((c>191)&&(c<224)) {c-=192; reg=1;}  /*приводим все символы к одинаковому коду, учитывая заглавные*/
            if ((c>223)&&(c<256)) {c-=224; reg=0;}
 
            if ((k>191)&&(k<224)) {k-=192;}
            if ((k>223)&&(k<256)) {k-=224;}  
            
            xr=(c^k); //получаем отксоренный символ 
            
            if (c==xr) indsum++; //подсчитываем совпавшие символоы
            
            all++;
        
        }
 
 
        cout<<"Смещение "<<i<<". Индекс совпадений "<<(indsum/(len))<<"  "<<endl;
       
        
       det=0;
        all=0;
        indsum=0;
 
    }
 
 
}

Шифрую вот эту строку:
"Ниже описано, как взломать этот шифр:
1. Определим длину ключа с помощью процедуры, известной как подсчет совпадений. Применим операцию XOR к шифротексту, используя в качестве ключа сам шифротекст с различными смещениями, и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа, то совпадет свыше 6 процентов байтов. Если нет, то будут совпадать меньше чем 0.4 процента (считая, что обычный ASCII текст кодируется случайным ключом, для других типов открытых текстов числа будут другими). Это называется показателем совпадений. Минимальное смещение от одного значения, кратного длине ключа, к другому и есть длина ключа."
Ключ:
"сложениепомодулюдва"
После ксора получаю:
"Ьгиг лвафпгв, ддщ йщпммсщт ычгъ эзъь:
1. Алгоъбйиэ пеоию восщм я лэзрэюю юыарайыхф, жлмбвщукл ксб бибьяаэ явмлупыйкй. Юыжкааай ббйюдега XOR о ъиеыафазщчь, жэбкшчщчэ в ылщгфяка еетщд влт ькфбеьгпьъ ф яолемджеик сэочгиечйз, ж гаавьццвеэ ъадкнмесчдл еувмя. Зсъг мгоеянво эвбкоумэ кбльле йгнвл жеъдл, мк уоудовая щзфцй 6 бфээыйроу копчгк. Аюед гбб, щр есдвщ яизвибпьр вбючжб хеэ 0.4 дюиуиечп (яыжцуф, йцм оррщлюд ASCII ъаеяю дкчгочзтаф янцъимвха дпньри, жло пюхжеэ чзбвм кббоярыд щлмфяжз шжэед тшъчр дбшнойе). Хчб гмйяслыцуя юеджвнъадла яксдюазнщв. Воиедедтбаб взыэзнщо аф лйелма лгддоумэ, кбльллож бджбл ошхйд, и дбшнийю а аюьр кпыжю ойюжл."

s-andriano · 03.05.2013, 21:13

Я не силен в С и не могу понять нескольких вещей.
1. Если Вы переводите символы к одному регистру, то почему у Вас и до и после ксора фигурируют символы в обоих регистрах? Как вообще получены те абзацы, которые содержатся в сообщении №3?
2. Почему в результате ксора кириллические символы переходят в кириллические. По идее они должны переходить в символы (включая служебные) из первой половины таблицы.
3. Вы пытаетесь все сделать в одном цикле - и привести к нужному регистру, и проксорить, но в таком подходе, минимум, два недостатка:
- Вы многократно выполняете одну и ту же работу,
- Вы лишаетесь возможности проконтролировать промежуточный результат.

Rad-X · 03.05.2013, 21:41

Цитата:

Сообщение от s-andriano

Я не силен в С и не могу понять нескольких вещей.
1. Если Вы переводите символы к одному регистру, то почему у Вас и до и после ксора фигурируют символы в обоих регистрах? Как вообще получены те абзацы, которые содержатся в сообщении №3?
2. Почему в результате ксора кириллические символы переходят в кириллические. По идее они должны переходить в символы (включая служебные) из первой половины таблицы.
3. Вы пытаетесь все сделать в одном цикле - и привести к нужному регистру, и проксорить, но в таком подходе, минимум, два недостатка:
- Вы многократно выполняете одну и ту же работу,
- Вы лишаетесь возможности проконтролировать промежуточный результат.

В приведенном коде я пытаюсь только посчитать индекс совпадений или что-то в этом роде.
Функция перевода в шифрованный текст в другом месте. И работает она верно, проверял в ручную. Причем я шифрую только русские буквы, пропуская нерусские символы и служебные.
Служебные символы не получаются, потому что я привожу все русские символы к коду от 0 до 31, а при ксоре таких чисел, числа большие 31 не получатся, ну а потом перевожу в обратный вид.

s-andriano · 03.05.2013, 21:56

Я тут тоже набросал небольшую программку, которая делает некоторые подготовительные действия.
Длина Вашего абзаца 638 символов.
Из них 515 - символов кириллицы.
Посчитанный по этому файлу индекс = 5.12%
Для проверки взял другой файл объемом 72100 символов, из которых 57761 - кириллица.
Индекс по нему = 5.72%, что гораздо ближе к таблице по Вашей ссылке.

Вопрос остается: как Вы получаете проксоренный код, ведь, судя по числу букв 32, в нем должны быть исключительно буквы одного регистра. А у Вас - разного. Подозреваю, что это первая ошибка.

Rad-X · 03.05.2013, 23:25

Как вы считаете индекс?

Цитата:

Сообщение от s-andriano

Вопрос остается: как Вы получаете проксоренный код, ведь, судя по числу букв 32, в нем должны быть исключительно буквы одного регистра. А у Вас - разного. Подозреваю, что это первая ошибка.

Нет, я привожу все буквы к одному и тому же. Т.е. символ "а" и "А" имеют одинаковый код - 0, или "я" и "Я" - 31.
Соответственно после ксора "а" и к примеру "Я" получится "я", тоже самое и если сменить регистр.

Цитата:

Сообщение от s-andriano

Я тут тоже набросал небольшую программку, которая делает некоторые подготовительные действия.
Длина Вашего абзаца 638 символов.
Из них 515 - символов кириллицы.
Посчитанный по этому файлу индекс = 5.12%
Для проверки взял другой файл объемом 72100 символов, из которых 57761 - кириллица.
Индекс по нему = 5.72%, что гораздо ближе к таблице по Вашей ссылке.

И все-таки, вы посчитали один индекс, а там нужно считать индекс с различными смещениями, после чего ловить нужно смещение.

s-andriano · 04.05.2013, 10:10

Цитата:

Сообщение от Rad-X

Как вы считаете индекс?

Привожу символы к диапазону 0-31.
Прохожу весь текст и на каждый символ увеличиваю значение того из 32 счетчиков, который соответствует данному числу.
Суммирую произведения самого счетчика на него же без 1 (32 слагаемых).
Делю на N*(N-1), где N - длина текста.

Цитата:

Нет, я привожу все буквы к одному и тому же. Т.е. символ "а" и "А" имеют одинаковый код - 0, или "я" и "Я" - 31.
Соответственно после ксора "а" и к примеру "Я" получится "я", тоже самое и если сменить регистр.

Да, я это понял. Но есть сомнения, что это подходит для анализа. Мне кажется, в анализе должны участвовать исключительно 32 кода без различия на большие и малые буквы.

Цитата:

Сообщение от Rad-X

И все-таки, вы посчитали один индекс, а там нужно считать индекс с различными смещениями, после чего ловить нужно смещение.

Я попытался пройти дальше, но не преуспел в этом.
1. Ксорил зашифрованный текст с самим собой с разными смещениями и считал индекс: при 0-м смещении получал 100%, а при всех других - в районе 3.3%. Особенностей не обнаружил.
2. Подсчитывал индекс по проксоренному тексту с разным шагом (т.е. каждый второй, каждый третий...). В среднем индекс 5.4-5.5%, и особенностей также выявить не удалось.

Rad-X · 04.05.2013, 11:43

Цитата:

Сообщение от s-andriano

Да, я это понял. Но есть сомнения, что это подходит для анализа. Мне кажется, в анализе должны участвовать исключительно 32 кода без различия на большие и малые буквы.

Ну, ведь у меня и участвует только 32 кода, проверив на регистр я привожу одну и ту же букву к одному и тому же коду.
Я же написал,что "а" и "А" у меня будут иметь одинаковые код, без различий из-за регистра.

Цитата:

Сообщение от s-andriano

Я попытался пройти дальше, но не преуспел в этом.
1. Ксорил зашифрованный текст с самим собой с разными смещениями и считал индекс: при 0-м смещении получал 100%, а при всех других - в районе 3.3%. Особенностей не обнаружил
2. Подсчитывал индекс по проксоренному тексту с разным шагом (т.е. каждый второй, каждый третий...). В среднем индекс 5.4-5.5%, и особенностей также выявить не удалось.

Вот я тоже до этого дошел, и результаты те же. И поэтому написал на форум

s-andriano · 04.05.2013, 12:12

А я провел рефакторинг, обнаружил ошибку, - оказывается, я как для отладки ограничил перекодируемую часть буфера 20 символами, так и осталось.
Исправил.
Теперь результат следующий:
1. ксор с самим собой с разными смещениями:

Код:

ofs  0 index: 1.0000
ofs  1 index: 0.0316
ofs  2 index: 0.0316
ofs  3 index: 0.0314
ofs  4 index: 0.0315
ofs  5 index: 0.0314
ofs  6 index: 0.0315
ofs  7 index: 0.0314
ofs  8 index: 0.0314
ofs  9 index: 0.0314
ofs 10 index: 0.0314
ofs 11 index: 0.0314
ofs 12 index: 0.0314
ofs 13 index: 0.0315
ofs 14 index: 0.0314
ofs 15 index: 0.0315
ofs 16 index: 0.0314
ofs 17 index: 0.0316
ofs 18 index: 0.0314
ofs 19 index: 0.0330
ofs 20 index: 0.0314
ofs 21 index: 0.0316
ofs 22 index: 0.0314
ofs 23 index: 0.0315
ofs 24 index: 0.0314
ofs 25 index: 0.0315
ofs 26 index: 0.0314
ofs 27 index: 0.0314
ofs 28 index: 0.0314
ofs 29 index: 0.0314
ofs 30 index: 0.0314
ofs 31 index: 0.0314
ofs 32 index: 0.0315
ofs 33 index: 0.0314
ofs 34 index: 0.0315
ofs 35 index: 0.0314
ofs 36 index: 0.0316
ofs 37 index: 0.0314
ofs 38 index: 0.0330
ofs 39 index: 0.0314
ofs 40 index: 0.0316

как видим, разброс при несовпадении довольно мал: от 3.14 до 3.16%, а при попадании - увеличивается до 3.3%.
Не слишком много, но вполне детектируемо.

2. При выборке с разным шагом - здесь результаты различаются очень отчетливо:

Код:

ofs  2 index: 0.0346
ofs  3 index: 0.0346
ofs  4 index: 0.0346
ofs  5 index: 0.0347
ofs  6 index: 0.0347
ofs  7 index: 0.0348
ofs  8 index: 0.0347
ofs  9 index: 0.0346
ofs 10 index: 0.0347
ofs 11 index: 0.0347
ofs 12 index: 0.0346
ofs 13 index: 0.0346
ofs 14 index: 0.0347
ofs 15 index: 0.0347
ofs 16 index: 0.0348
ofs 17 index: 0.0347
ofs 18 index: 0.0345
ofs 19 index: 0.0549
ofs 20 index: 0.0348
ofs 21 index: 0.0348
ofs 22 index: 0.0347
ofs 23 index: 0.0346
ofs 24 index: 0.0347
ofs 25 index: 0.0346
ofs 26 index: 0.0347
ofs 27 index: 0.0347
ofs 28 index: 0.0347
ofs 29 index: 0.0345
ofs 30 index: 0.0348
ofs 31 index: 0.0346
ofs 32 index: 0.0348
ofs 33 index: 0.0346
ofs 34 index: 0.0348
ofs 35 index: 0.0350
ofs 36 index: 0.0344
ofs 37 index: 0.0346
ofs 38 index: 0.0547
ofs 39 index: 0.0347
ofs 40 index: 0.0348
ofs 41 index: 0.0347

Не попали - от 3.44% до 3ю48%,
попали - 5.47%-5.49%.

Но это все при объеме файла 1.9 Мб.

03.05.2013, 15:02	#1
Rad-X Пользователь Регистрация: 13.02.2011 Сообщений: 14	Взлом XOR-шифра Здравствуйте, пишу программу для взлома XOR шифра. Прочитал по этому поводу в "Прикладной криптографии" Брюса Шнайера. Там описан следующий алгоритм: "Предположим,что открытый текст использует английский язык.Более того,пусть длина ключа любое небольшое число байт.Ниже описано,как взломать этот шифр: 1.Определим длину ключа с помощью процедуры,известной как ПОДСЧЕТ СОВПАДЕНИЙ. Применим операцию XOR к шифротексту,используя в качестве ключа сам шифротекст с различными смещениями,и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа,то совпадет свыше 6 процентов байтов. Если нет,то будут совпадать меньше чем 0.4 процента( считая,что обычный ASCII текст кодируется случайным ключом,для других типов открытых текстов числа будут другими). Это называется показателем совпадений. Минимальное смещение от одного значения,кратного длине ключа,к другому и есть длина ключа. 2. Сместим шифротекст на эту длину и проведем операцию XOR для смещенного и оригинального шифротекстов.Результатом операции будет удаление ключа и получение открытого текста,подвергнутого операции XOR с самим собой,смещенным на длину ключа. Так как в английском языке на один байт приходится 1.3 бита действительной информации,существующая значительная избыточность позволяет определить способ шифрования." Немного не понимаю, что мы считаем совпадающими байтами? Совпадения между строкой шифротекста и полученной строкой? Или только в полученной строке? Нашел на википедии статью http://ru.wikipedia.org/wiki/%D0%98%...BD%D0%B8%D0%B9 Пробовал разные варианты реализовывать, и просто индекс совпадений и взаимный индекс, результаты получаются не те, которые нужны. Может дело в том, что шифрую только 32 буквы русского алфавита? Но ведь при смещении кратном длине ключа всплески должны быть, но их нету. Пишу на C++

03.05.2013, 19:22	#3
Rad-X Пользователь Регистрация: 13.02.2011 Сообщений: 14	Ну там же написано сместить и ксорить. Вот я сместил строку, отксорил с исходной, и считаю совпадения ксоровской с исходной строкой, ведь так? У меня строка длинной около 500 символов и после той процедуры которую я описал выше, для всех 500-та смещений получается одинаковый индекс совпадений - 5,4% вот код: Код: void encryptnokey() { FILE in,out,key; fopen_s(&in,"out.txt","rb"); fopen_s(&out,"encryptnotkey.txt","wb"); char textorg[20000],text[20000]; int lenorg=0,len=0; while(!(feof(in))) //считываем из файла и удаляем все лишние символы кроме русских { unsigned char c; c=fgetc(in); textorg[lenorg]=c; if ((c>191)&&(c<256)) {text[len]=c;len++;} lenorg++; if (feof(in)) break; } len--; lenorg--; int det=0,all=0; double max=0; srand(time(0)); for(int i=0;i<len/2;i++) { int ind[32],indxr[32]; double indsum=0; for(int j=0;j<32;j++) { ind[j]=0; indxr[j]=0; } for(int j=0;j<(len);j++) { unsigned char c,k,xr; c=text[i]; k=text[(j+i)%len]; // k=text[rand()%len]; int reg=2; if ((c>191)&&(c<224)) {c-=192; reg=1;} /приводим все символы к одинаковому коду, учитывая заглавные/ if ((c>223)&&(c<256)) {c-=224; reg=0;} if ((k>191)&&(k<224)) {k-=192;} if ((k>223)&&(k<256)) {k-=224;} xr=(c^k); //получаем отксоренный символ if (c==xr) indsum++; //подсчитываем совпавшие символоы all++; } cout<<"Смещение "<<i<<". Индекс совпадений "<<(indsum/(len))<<" "<<endl; det=0; all=0; indsum=0; } } Шифрую вот эту строку:* "Ниже описано, как взломать этот шифр: 1. Определим длину ключа с помощью процедуры, известной как подсчет совпадений. Применим операцию XOR к шифротексту, используя в качестве ключа сам шифротекст с различными смещениями, и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа, то совпадет свыше 6 процентов байтов. Если нет, то будут совпадать меньше чем 0.4 процента (считая, что обычный ASCII текст кодируется случайным ключом, для других типов открытых текстов числа будут другими). Это называется показателем совпадений. Минимальное смещение от одного значения, кратного длине ключа, к другому и есть длина ключа." Ключ: "сложениепомодулюдва" После ксора получаю: "Ьгиг лвафпгв, ддщ йщпммсщт ычгъ эзъь: 1. Алгоъбйиэ пеоию восщм я лэзрэюю юыарайыхф, жлмбвщукл ксб бибьяаэ явмлупыйкй. Юыжкааай ббйюдега XOR о ъиеыафазщчь, жэбкшчщчэ в ылщгфяка еетщд влт ькфбеьгпьъ ф яолемджеик сэочгиечйз, ж гаавьццвеэ ъадкнмесчдл еувмя. Зсъг мгоеянво эвбкоумэ кбльле йгнвл жеъдл, мк уоудовая щзфцй 6 бфээыйроу копчгк. Аюед гбб, щр есдвщ яизвибпьр вбючжб хеэ 0.4 дюиуиечп (яыжцуф, йцм оррщлюд ASCII ъаеяю дкчгочзтаф янцъимвха дпньри, жло пюхжеэ чзбвм кббоярыд щлмфяжз шжэед тшъчр дбшнойе). Хчб гмйяслыцуя юеджвнъадла яксдюазнщв. Воиедедтбаб взыэзнщо аф лйелма лгддоумэ, кбльллож бджбл ошхйд, и дбшнийю а аюьр кпыжю ойюжл." Последний раз редактировалось Stilet; 04.05.2013 в 11:23.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Разгадка шифра	saivs	Общие вопросы Delphi	6	15.04.2013 18:28
Реализация книжного шифра!!!	InnaSidorenko	Помощь студентам	1	20.11.2012 21:23
Анализ блочного шифра на криптостойкость	kaarol	Фриланс	1	13.02.2012 20:36
Реализация шифра Плейфера в Delphi	ALUKARD2011	Помощь студентам	3	14.10.2011 15:56
Криптоанализ шифра Виженера	kalbim	Помощь студентам	3	17.05.2011 22:27

03.05.2013, 16:48	#2
s-andriano Старожил Регистрация: 08.04.2012 Сообщений: 3,229	Если верить статье по приведенной Вами ссылке, то не 0.4%, а 4%. А разницу между 4% и 6% на не очень длинном тексте уловить будет затруднительно. Я бы оценил минимальную длину текста в 3000-10000 знаков.

03.05.2013, 21:13	#4
s-andriano Старожил Регистрация: 08.04.2012 Сообщений: 3,229	Я не силен в С и не могу понять нескольких вещей. 1. Если Вы переводите символы к одному регистру, то почему у Вас и до и после ксора фигурируют символы в обоих регистрах? Как вообще получены те абзацы, которые содержатся в сообщении №3? 2. Почему в результате ксора кириллические символы переходят в кириллические. По идее они должны переходить в символы (включая служебные) из первой половины таблицы. 3. Вы пытаетесь все сделать в одном цикле - и привести к нужному регистру, и проксорить, но в таком подходе, минимум, два недостатка: - Вы многократно выполняете одну и ту же работу, - Вы лишаетесь возможности проконтролировать промежуточный результат.

03.05.2013, 21:56	#6
s-andriano Старожил Регистрация: 08.04.2012 Сообщений: 3,229	Я тут тоже набросал небольшую программку, которая делает некоторые подготовительные действия. Длина Вашего абзаца 638 символов. Из них 515 - символов кириллицы. Посчитанный по этому файлу индекс = 5.12% Для проверки взял другой файл объемом 72100 символов, из которых 57761 - кириллица. Индекс по нему = 5.72%, что гораздо ближе к таблице по Вашей ссылке. Вопрос остается: как Вы получаете проксоренный код, ведь, судя по числу букв 32, в нем должны быть исключительно буквы одного регистра. А у Вас - разного. Подозреваю, что это первая ошибка.