Взлом XOR-шифра

[Rad-X]

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

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

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

Ключ тот же? 19 символов? И считали по формуле из статьи с википедии?

[Rad-X]

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

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

Что значит при выборке с разным шагом?

[s-andriano]

Проверил на других длинах файлов:
72 Кб - уверенно различаются оба варианта
0.8 Кб - по первому варианту заметно вырос разброс, но в принципе выделить можно, по второму варианту разброс существенно растет с ростом периода - обнаруживать становится трудно.

[s-andriano]

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

Ключ тот же? 19 символов? И считали по формуле из статьи с википедии?

Да. Да. Да.

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

Что значит при выборке с разным шагом?

прошел по указанной Вами ссылке. Оттуда - по ссылке на шифр Виженера http://ru.wikipedia.org/wiki/%D0%A8%...B5%D1%80%D0%B0, там раздел "Криптоанализ" пункт 1.
Задумка этого метода в том, что если мы берем каждый n-й симовл, где n - длина ключа, выбираем лишь буквы, проксоренные одним и тем же символом, а потому индекс должен соответствовать таковому же в исходном файле. Недостаток - существенно снижается объем данных, по которым проводится статистика.

[Rad-X]

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

прошел по указанной Вами ссылке. Оттуда - по ссылке на шифр Виженера http://ru.wikipedia.org/wiki/%D0%A8%...B5%D1%80%D0%B0, там раздел "Криптоанализ" пункт 1.
Задумка этого метода в том, что если мы берем каждый n-й симовл, где n - длина ключа, выбираем лишь буквы, проксоренные одним и тем же символом, а потому индекс должен соответствовать таковому же в исходном файле. Недостаток - существенно снижается объем данных, по которым проводится статистика.

Благодарю, сейчас буду пробовать

[s-andriano]

uses debug;

procedure WriteToFile(fname : string; var buf : array of byte; len : longint);
var f : file;
begin
  assign(f, fname);
  rewrite(f,1);
  blockwrite(f, buf, len);
  close(f);
end;

function GetRepIndex(var buf : array of byte; len, step : longint) : extended;
var
  i : longint;
  ind : array[0..31]of longint;
  sum : extended;
begin
  fillchar(ind, sizeof(ind), 0);
  sum := 0;
  for i := 0 to (len-1) div step do
    inc(ind[buf[i*step] and 31]);
  for i := 0 to 31 do
    sum := sum + ind[i]/1*(ind[i]-1);
  result := sum/((len-1) div step)/((len-1) div step - 1);
end;

const cod : string = 'сложениепомодулюдва';
var
  f : file;
  buf,buf2,buf3 : ^array[0..1999999]of byte;
  i,j,len,len2 : longint;
  cod2 : array[0..255]of byte;
  lencod : longint;
begin
  getmem(buf, sizeof(buf^));
  getmem(buf2, sizeof(buf2^));
  getmem(buf3, sizeof(buf3^));
  lencod := length(cod);
  for i := 0 to lencod-1 do begin
    cod2[i] := byte(cod[i+1]) - 224;
    writeln(cod2[i]);
  end;
  assign(f,'xor-crypt.txt');    // 0.8 Kb
//  assign(f,'xc2_geogen.txt');   // 72 Kb
//  assign(f,'02 Камень слёз.txt');  // 1.9 Mb
  reset(f,1);
  len := filesize(f);
  blockread(f, buf^, len);
  close(f);
// приводим к нижнему регистру
  for i := 0 to len-1 do
    if buf^[i] > 191 then
      if buf^[i] < 224 then
        inc(buf^[i], 32);
// индекс после приведения к нижнему регистру - больше нормы из-за включения в статистику пробелов
  writeln(' index: ', GetRepIndex(buf^, len, 1):1:4);
// выбираем только кирилицу, остальное пропускаем
  len2 := 0;
  for i := 0 to len-1 do
    if buf^[i] > 223 then begin
      buf2^[len2] := buf^[i];
      inc(len2);
    end;
// вот тут искомая статистика для рассматриваемого файла
  writeln(' index: ', GetRepIndex(buf2^, len2, 1):1:4);
// для контроля записываем, что получилось
  WriteToFile('xor-crypt_1.txt', buf^, len);
  WriteToFile('xor-crypt_2.txt', buf2^, len2);
// кодируем
  for i := 0 to len2-1 do begin
    buf2^[i] := buf2^[i] xor cod2[i mod lencod];
  end;
  writeln;

  WriteToFile('xor-crypt_3.txt', buf2^, len2);
// подсчет при самокодировании с разным смещением
  for j := 0 to 40 do begin
    for i := 0 to len2-1 do begin
      buf3^[i] := buf2^[i] xor buf2^[(i+j) mod len2];
    end;
    writeln('ofs ',j:2,' index: ', GetRepIndex(buf3^, len2, 1):1:4);
  end;
// подсчет для закодированного файла с разным шагом выборки
  for j := 1 to 41 do begin
    writeln('ofs ',j:2,' index: ', GetRepIndex(buf2^, len2, j):1:4);
  end;

  freemem(buf3, sizeof(buf3^));
  freemem(buf2, sizeof(buf2^));
  freemem(buf, sizeof(buf^));
end.

[Rad-X]

Спасибо за код, воспользуюсь если вдруг.
Вот что у меня получилось для текста с около 90 тысячами русских символов. Всплески есть, но они слишком малы.


Попробую второй способ, с шагом

[s-andriano]

Почему же малы?
Посчитайте матожидание и дисперсию для прочих результатов (выбросив "попадания"), и убедитесь, что "попадания" лежат явно вне доверительного интервала.
Т.е. их можно вполне надежно детектировать.

[Rad-X]

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

Почему же малы?
Посчитайте матожидание и дисперсию для прочих результатов (выбросив "попадания"), и убедитесь, что "попадания" лежат явно вне доверительного интервала.
Т.е. их можно вполне надежно детектировать.

Хм, хорошие метод, можно будет пользоваться для того чтобы ловить "попадания".

Однако с шагом у меня проблемы, упорно выдает вот это

Я просто беру первый символ, и ксорю его со вторым, второй символ с четвертым, третий с шестым, для шага два? Ведь так?

[s-andriano]

Не так.
Во втором варианте ничего ксорить не нужно - просто выбираем 0,2,4,6,8..., потом 0,3,6,9..., 0,4,8,12... символы и по ним считаем индекс.
Еще один момент - коль скоро мы при кодировании выбрасываем все некириллические символы, то точно так же нам нужно делать и при "прореживании". Т.е. выкидывать не просто n символов, а n кириллических символов.

Вдогонку: у меня надежно детектируется период при 72кб файле по уровню двух ср.кв.откл. На 0.8 кб, правда, много выбросов как в ту, так и в другую сторону (в смысле, и пропуск периода 19 и срабатывание вне периода), но это объяснимо - мало данных.
Вся проверка - только на длине ключа 19 символов. Думаю, при коротких ключах в 2-3 символа провести границу будет сложнее.