информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Страшный баг в WindowsЗа кого нас держат?Где водятся OGRы
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Все их предыдущие конкурсы были не сложными - те или иные варианты подстановочного. 30.10.03 12:16  Число просмотров: 3269
Автор: dikiy Статус: Незарегистрированный пользователь
<"чистая" ссылка>
<theory>
Thawte Crypto Challenge IV 30.10.03 09:20  
Автор: dikiy Статус: Незарегистрированный пользователь
<"чистая" ссылка>
http://www.thawte.com/cryptochallenge/

Призы - цифровая камера и 10 книг Митника.
Чтобы получить текст четвертого задания, нужно зарегестрироваться. Вот оно:
==================
mfcus gcm dzo wk rbujfpfj.nkxob yvahlrmjof wt ljcu bcbclkvt xigq buzg emxbuj coyjpwv wizz wpz wzwepnf qi i bwdo.dzxfwkfodf ewmrya dvsvmyb,gfbs,gnapjcudozzmsw boe hdmthmm.siovmsfg dsfcwja xwqiqyrvhh,efdjulamazav,iiq f tbujppdq bpborwf,emlei fwgqycngtb tznlx vp tvefjaf.
==================

Распределение отлично от равномерного, скорее всего какой-то вариант подстановочного кода. В тексте встречаются одиночные буквы (i & f); в английском, на сколько понимаю, из одной буквы состоит только артикль "a". Значит, или пробелы расставлены неверно, либо зашифорвано несколькими алфавитами. Немного поигравшись с первым вариантом, приступил ко второму.

Длина сообщения - 268 символ, число кранто 2, 4, 67, 134. Предположил, что используются 4 алфавита. Разделил сообщение на группы по 4 символа, каждый получившийся столбец рассматривал раздельно. Вот частоты:
  => 7      => 12     => 8   f => 6
j => 6    v => 7    p => 5   z => 5
w => 6    f => 5    b => 5     => 4
m => 4    b => 4    m => 4   j => 4
f => 4    a => 3    w => 4   d => 3
z => 4    , => 3    e => 4   o => 3
a => 3    r => 3    g => 4   q => 3
b => 3    c => 2    c => 3   i => 3
c => 3    w => 2    d => 3   m => 3
o => 3    e => 2    u => 3   w => 3
s => 3    z => 2    i => 3   y => 3
t => 3    i => 2    h => 2   u => 3
d => 3    . => 2    l => 2   k => 2
x => 3    m => 2    , => 2   l => 2
y => 3    o => 2    n => 2   . => 2
l => 2    p => 2    o => 2   p => 2
q => 1    q => 2    r => 2   s => 2
h => 1    t => 2    a => 2   v => 2
i => 1    u => 2    f => 2   b => 2
k => 1    d => 1    s => 1   x => 2
e => 1    s => 1    t => 1   g => 2
n => 1    n => 1    q => 1   h => 2
g => 1    k => 1    v => 1   n => 1
          g => 1    x => 1   e => 1
          j => 1             t => 1
                             c => 1

---

Убил целый день рабочего времени, ничего конкретного не достигнув. Есть у кого другие идеи? Может кто уже работал над этим - поделитесь.
Thawte Crypto Challenge IV (update) 30.10.03 14:01  
Автор: dl <Dmitry Leonov>
Отредактировано 30.10.03 14:40  Количество правок: 5
<"чистая" ссылка>
> Распределение отлично от равномерного, скорее всего
> какой-то вариант подстановочного кода. В тексте встречаются
> одиночные буквы (i & f); в английском, на сколько понимаю,
> из одной буквы состоит только артикль "a". Значит, или
> пробелы расставлены неверно, либо зашифорвано несколькими
> алфавитами. Немного поигравшись с первым вариантом,
> приступил ко второму.

1. Пробел тоже может быть закодированным символом. Хотя если какой-то символ встречается чаще всего, то это скорее, он и есть.
2. Существует ведь формула примерной оценки числа используемых алфавитов.

(S(Li*Li-1))/(N*(N-1))

Если результат больше 0,066, до подстановка, скорее всего, одноалфавитная.

где S - сумма по всему алфавиту, Li - сколько раз встретилась в сообщении i-я буква, N - число букв в сообщении.

В нашем случае, если я нигде не промахнулся, имеем 0.039, что говорит о многоалфавитной подстановке (по крайней мере, граница между 3 и 4 алфавитами - 0.047, а тут значение сильно меньше). В первой задаче у них использовалось кодирование по таблице Вижинера, возможно, и тут аналогичный случай.

Кстати, я бы уточнил, что, если считать пробелы и знаки препинания некодированными, то получаем не 268 символов, а 228 сиволов в сообщении.
btw, у формулы есть название? В онлайне мб книга найдется с... 23.12.03 09:47  
Автор: dikiy Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> 2. Существует ведь формула примерной оценки числа
> используемых алфавитов.
>
> (S(Li*Li-1))/
> (N*(N-1))
>
> Если результат больше 0,066, до подстановка, скорее всего,
> одноалфавитная.

btw, у формулы есть название? В онлайне мб книга найдется с описаловом?

PS: А челлендж уже закончился. Его я не раскатал, к сожалению. Оказалось, что полиалфавитный код Цезаря.
Q = 0.0450830513902232 30.10.03 14:35  
Автор: dikiy Статус: Незарегистрированный пользователь
<"чистая" ссылка>
перепроверил 30.10.03 15:05  
Автор: dl <Dmitry Leonov>
<"чистая" ссылка>
Если не учитывать знаки препинания и брать только 26 алфивитных символов, то
S=2038, N=228, результат 0.0393770770538681
На 29 символах:
S=3000, N=268, результат 0.0419252054335066

Кстати, имеет смысл расписать таблицу частот на 4 и 6 алфавита, но без учета знаков препинания и пробелов.
(и я) перепроверил 30.10.03 15:12  
Автор: dikiy Статус: Незарегистрированный пользователь
Отредактировано 30.10.03 15:15  Количество правок: 1
<"чистая" ссылка>
> Если не учитывать знаки препинания и брать только 26
> алфивитных символов, то
> S=2038, N=228, результат 0.0393770770538681
> На 29 символах:
> S=3000, N=268, результат 0.0419252054335066

Хоть убей, не получается твой результат. Нашел у себя ошибочку, лишний символ в алфавит добавлялся, но все равно не сходится.
foreach (keys %count) { $num += $count{$_}; $sum += $count{$_}*$count{$_} - 1; } print "Q = ${\($sum/($num*$num-1))} (A=${\(scalar keys %count)} S=$sum N=$num)\n";
Q = 0.0450969745067736 (A=29 S=3239 N=268)

> Кстати, имеет смысл расписать таблицу частот на 4 и 6
> алфавита, но без учета знаков препинания и пробелов.

На 4 алфавита я приводил в первом посте, данные касательно пробелов в нем можно просто проигнорировать. А вот если имелось в виду выкидывать пробелы/знаки пунктуации ДО разбиения на 4/6 алфавитов? Можно попробовать..
(и я) перепроверил 30.10.03 15:18  
Автор: dl <Dmitry Leonov>
Отредактировано 30.10.03 15:21  Количество правок: 1
<"чистая" ссылка>
> > Если не учитывать знаки препинания и брать только 26
> > алфивитных символов, то
> > S=2038, N=228, результат 0.0393770770538681
> > На 29 символах:
> > S=3000, N=268, результат 0.0419252054335066
>
> Хоть убей, не получается твой результат. Нашел у себя
> ошибочку, лишний символ в алфавит добавлялся, но все равно
> не сходится.

Кажется, скобки потерялись (в формуле суммирования я напорол, каюсь):

foreach (keys %count) { $num += $count{$_}; $sum += $count{$_}*$count{$_} - 1; $sum += $count{$_}*($count{$_} - 1); } print "Q = ${\($sum/($num*$num-1))} (A=${\(scalar keys %count)} S=$sum N=$num)\n"; print "Q = ${\($sum/($num*($num-1)))} (A=${\(scalar keys %count)} S=$sum N=$num)\n";



> Q = 0.0450969745067736 (A=29 S=3239 N=268)
>
> > Кстати, имеет смысл расписать таблицу частот на 4 и 6
> > алфавита, но без учета знаков препинания и пробелов.
>
> На 4 алфавита я приводил в первом посте, данные касательно
> пробелов в нем можно просто проигнорировать. А вот если
> имелось в виду выкидывать пробелы/знаки пунктуации ДО
> разбиения на 4/6 алфавитов? Можно попробовать..

Угу, именно так.
(и я) перепроверил 31.10.03 12:06  
Автор: dikiy Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> > > Кстати, имеет смысл расписать таблицу частот на 4
> и 6
> > > алфавита, но без учета знаков препинания и
> пробелов.
> >
> > На 4 алфавита я приводил в первом посте, данные
> касательно
> > пробелов в нем можно просто проигнорировать. А вот
> если
> > имелось в виду выкидывать пробелы/знаки пунктуации ДО
> > разбиения на 4/6 алфавитов? Можно попробовать..
>
> Угу, именно так.

Не в пользу этого варианта говорит то, что одиночные символы попадают в одну группу, как при разбиении на 4, иак и на 6.
Как всегда веселая задача, где алгоритм неизвестен. 30.10.03 10:56  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
<"чистая" ссылка>
> http://www.thawte.com/cryptochallenge/
>
> Распределение отлично от равномерного, скорее всего
> какой-то вариант подстановочного кода. В тексте встречаются
> одиночные буквы (i & f); в английском, на сколько понимаю,
> из одной буквы состоит только артикль "a". Значит, или
> пробелы расставлены неверно, либо зашифорвано несколькими
> алфавитами. Немного поигравшись с первым вариантом,
> приступил ко второму.

Частотный анализ, явно не катит - слишком по-детски. Если б это было так, кто-нибудь уже бы расшифровал минут за 10.
Распределение... маловато буковок, чтобы однозначно утверждать. При любом шифровании может получиться что угодно, вплоть до "все пробелы".
Частотный анализ летит к черту уже при добавлении индекса, ну и, разумеется, берется остаток от деления на размер алфавита. А ведь можно и в степень возводить...
А, если нехитрую перестановку добавить, для усложнения лексического анализа...

> Убил целый день рабочего времени, ничего конкретного не
> достигнув. Есть у кого другие идеи? Может кто уже работал
> над этим - поделитесь.
Все их предыдущие конкурсы были не сложными - те или иные варианты подстановочного. 30.10.03 12:16  
Автор: dikiy Статус: Незарегистрированный пользователь
<"чистая" ссылка>
А такую подстановочку не проверяли... 31.10.03 10:13  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 31.10.03 10:14  Количество правок: 1
<"чистая" ссылка>
Символы беруться парами. К порядковому номеру четного добавляется порядковый номер нечетного, умноженный на количество символов в алфавите. Табличка, правда, до тысячи пар может вырасти.
А такую подстановочку не проверяли... 31.10.03 12:08  
Автор: dikiy Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Символы беруться парами. К порядковому номеру четного
> добавляется порядковый номер нечетного, умноженный на
> количество символов в алфавите. Табличка, правда, до тысячи
> пар может вырасти.

А это что за метод?
А такую подстановочку не проверяли... 31.10.03 13:35  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
<"чистая" ссылка>
> > Символы беруться парами. К порядковому номеру четного

Пара на пару заменяется.

> > добавляется порядковый номер нечетного, умноженный на
> > количество символов в алфавите. Табличка, правда, до
> тысячи
> > пар может вырасти.
>
> А это что за метод?
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach