Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
|
Как всегда веселая задача, где алгоритм неизвестен. 30.10.03 10:56 Число просмотров: 3902
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> http://www.thawte.com/cryptochallenge/
>
> Распределение отлично от равномерного, скорее всего
> какой-то вариант подстановочного кода. В тексте встречаются
> одиночные буквы (i & f); в английском, на сколько понимаю,
> из одной буквы состоит только артикль "a". Значит, или
> пробелы расставлены неверно, либо зашифорвано несколькими
> алфавитами. Немного поигравшись с первым вариантом,
> приступил ко второму.
Частотный анализ, явно не катит - слишком по-детски. Если б это было так, кто-нибудь уже бы расшифровал минут за 10.
Распределение... маловато буковок, чтобы однозначно утверждать. При любом шифровании может получиться что угодно, вплоть до "все пробелы".
Частотный анализ летит к черту уже при добавлении индекса, ну и, разумеется, берется остаток от деления на размер алфавита. А ведь можно и в степень возводить...
А, если нехитрую перестановку добавить, для усложнения лексического анализа...
> Убил целый день рабочего времени, ничего конкретного не
> достигнув. Есть у кого другие идеи? Может кто уже работал
> над этим - поделитесь.
|
|
<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
|
> > Символы беруться парами. К порядковому номеру четного
Пара на пару заменяется.
> > добавляется порядковый номер нечетного, умноженный на
> > количество символов в алфавите. Табличка, правда, до
> тысячи
> > пар может вырасти.
>
> А это что за метод?
|
|
|
подробно о проекте
Анализ криптографических сетевых...
