Форум программистов, компьютерный форум, киберфорум
Криптография
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.53/34: Рейтинг темы: голосов - 34, средняя оценка - 4.53
0 / 0 / 0
Регистрация: 20.05.2015
Сообщений: 15

Криптоанализ текста, зашифрованного методом простой замены

20.05.2015, 01:42. Показов 6756. Ответов 11
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Нужна помощь с задачкой. тема: расшифровать шифр простой замены. Она из сборника Жданова и Куденковой. Уже второй день бьюсь, но получается какая-то абра кадабра. может кто сталкивался или обладает "Волшебной" программой, буду очень благодарен)) вариант 17. (вроде первое слово ОНА, а дальше просто капец - не могу ничего понять. Слишком много букв, которые повторяются примерно одинаковое кол-во раз.)

56 67 92 18 58 39 99 27 87 67 56 25 56 80 67 10 17 92 39 62 25 56 27 24 95 56 31 95 46 27 73 56 31 17 58 39 58 67 95 58 92 56 95 40 24 40 17 92 39 62 69 39 40 17 56 67 58- 56 18 99 92 46 67 56 87, 69 56 69 39 36 80 17 92 67 27 39 40 87 56 17 58 73 40. 25 56 39 73 56 10 17 92, 56 43 92 80 40 10, 95 56 23 80 40 23 17 40 24 40 25 46 92 69 14 95 67 27 73 95 73 58 87 67 56 73 58. 69 39 58 69 56 95 46 27 23 25 46 92 67 10 17 56 38 58 73 95 92 58 56 38 58 46 73 40 67 92 10. 25 46 92 18 56 46 56 69 92 25 27 17 62 73 56 69 24 80 58 39 62 18 14 17 56 25 46 58 69 58 17 92 95 56 58 87 67 56 43 58 39 73 69 56, 23 17 40 24 40 46 40 24 18 58 23 40 17 92 39 62. 56 80 67 40 95 56 18 17 40 23 56 80 40 46 10 73 58 87 43 58 80 69 27 87 67 58 80 58 17 10 87 73 46 58 67 92 46 56 69 56 95 67 40 87 40 95 58 73 58 92 73 14 39 10 38 58 95 46 40 73 67 56 25 56 69 73 56 46 58 67 67 14 87 67 40 39 73 40 69 17 58 67 92 10 87 92 67 39 73 46 27 95 73 56 46 40 56 67 92 39 56 69 58 46 99 58 67 67 56 73 56 38 67 56 24 67 40 17 92, 24 40 38 58 87 25 46 92 99 17 92. 25 56 67 10 73 92 10 67 58 92 87 58 17 92, 80 17 10 38 58 23 56 95 56 67 95 46 58 73 67 56 25 46 58 80 67 40 24 67 40 38 58 67 14 69 39 58 71 73 92 99 73 27 95 92-67 56 56 73 67 92 82 71 73 56 23 56 92 67 58 73 46 58 18 56 69 40 17 56 39 62.
67 58 25 46 56 99 17 56 92 87 92 67 27 73 14, 95 40 95 56 67 27 69 92 80 58 17 51 58 17 62 92 82 67 58 17 58 23 95 56 23 56 92 71 95 24 56 73 92 38 58 39 95 56 23 56 25 27 73 58 99 58 39 73 69 92 10- 73 46 92 25 27 17 62 73 40 25 56 25 46 40 69 56 87 27 18 56 46 73 27, 27 39 14 25 40 67 67 14 58 38 58 46 73 56 69 56 31 27 31 87 56 31 73 27 87 18 17 58 46 56 69, 17 40 87 25 56 38 58 95, 25 58 46 58 95 17 36 38 40 73 58 17 58 31 92 95 67 56 25 56 95. 73 46 92 69 14 25 27 95 17 14 82 71 95 46 40 67 40 69 69 92 80 58 69 58 46 73 92 95 40 17 62 67 14 82 25 46 10 87 56 27 23 56 17 62 67 92 95 56 69-56 67 92 39 40 87 14 58, 67 92 95 40 95 56 31 56 99 92 18 95 92…
18 56 80 46 56 39 73 92 46 40 80 92, 56 67 25 56 69 73 56 46 92 17 25 46 56 39 58 18 10 25 56 17 36 18 92 69 99 27 36 39 10 51 92 73 40 73 27: “38 73 56 56 80 92 67 38 58 17 56 69 58 95 25 56 39 73 46 56 92 17, 80 46 27 23 56 31 24 40 69 39 58 23 80 40 46 40 24 17 56 87 40 73 62 39 87 56 43 58 73”. 92, 25 56 82 17 56 25 40 69 25 56 25 17 58 38 27 39 73 46 40 99 92 17 27 69 24 67 40 95 73 56 23 56, 38 73 56 67 40 25 40 46 67 92 95 80 56 17 43 58 67 18 80 92 73 58 17 62 67 56 39 73 56 10 73 62 67 40 99 27 82 58 46 58, 80 56 39 73 40 17 95 92 67 43 40 17 92 24 25 46 92 99 92 73 14 82 67 40 80 95 56 17 58 67 56 87 67 56 43 58 67.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
20.05.2015, 01:42
Ответы с готовыми решениями:

Задача: Криптоанализ текста, зашифрованного методом простой замены
Помогите решить задачку. :) Весь форум обошёл, решения этого варианта так и не нашёл, может кто ещё помнит как это делается и поможет. ...

Криптоанализ шифра простой замены
Помогите расшифровать шифр. Зашифровано с помощью шифра замены. Каждой букве алфавита соответствует двузначное число. 65 27,67 40 58 34...

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

11
601 / 468 / 73
Регистрация: 22.01.2009
Сообщений: 1,180
Записей в блоге: 1
20.05.2015, 04:06
а информации о пробелах точно нет? или форум как-то съел их?

Добавлено через 5 минут
а, все, нашел сборник, там они есть. на всякий случай, на будущее -- вставляйте, пожалуйста, с тегом code. Чтоб они не съедались наверняка
0
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
20.05.2015, 04:49
Цитата Сообщение от SVaz Посмотреть сообщение
вроде первое слово ОНА
ОНИ

В Google валяются расшифровки почти всех заданий этого сборника: "они бесшумно поднялись по узкой крутой лесенке и оказались в салоне..."

А так, рекомендую перевод из двухсимвольной кодировки в односимвольную
Миниатюры
Криптоанализ текста, зашифрованного методом простой замены  
2
601 / 468 / 73
Регистрация: 22.01.2009
Сообщений: 1,180
Записей в блоге: 1
20.05.2015, 06:05
блин, не успел. вот мой черновик:
Кликните здесь для просмотра всего текста
PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
<?php
 
$data = <<<D
56 67 92`18 58 39 99 27 87 67 56`25 56 80 67 10 17 92 39 62`25 56`27 24 95 56 31`95 46 27 73 56 31`17 58 39 58 67 95 58`92`56 95 40 24 40 17 92 39 62`69`39 40 17 56 67 58-56 18 99 92 46 67 56 87,69 56`69 39 36`80 17 92 67 27`39 40 87 56 17 58 73 40.25 56 39 73 56 10 17 92,56 43 92 80 40 10,95 56 23 80 40`23 17 40 24 40`25 46 92 69 14 95 67 27 73`95`73 58 87 67 56 73 58.69 39 58`69 56 95 46 27 23`25 46 92 67 10 17 56`38 58 73 95 92 58`56 38 58 46 73 40 67 92 10.25 46 92 18 56 46 56 69`92`25 27 17 62 73 56 69`24 80 58 39 62`18 14 17 56`25 46 58 69 58 17 92 95 56 58`87 67 56 43 58 39 73 69 56,23 17 40 24 40`46 40 24 18 58 23 40 17 92 39 62.56 80 67 40 95 56`18 17 40 23 56 80 40 46 10`73 58 87`43 58 80 69 27 87`67 58 80 58 17 10 87`73 46 58 67 92 46 56 69 56 95`67 40`87 40 95 58 73 58 92`73 14 39 10 38 58 95 46 40 73 67 56 25 56 69 73 56 46 58 67 67 14 87`67 40 39 73 40 69 17 58 67 92 10 87`92 67 39 73 46 27 95 73 56 46 40`56 67 92`39 56 69 58 46 99 58 67 67 56`73 56 38 67 56`24 67 40 17 92,24 40`38 58 87`25 46 92 99 17 92.25 56 67 10 73 92 10`67 58`92 87 58 17 92,80 17 10`38 58 23 56`95 56 67 95 46 58 73 67 56`25 46 58 80 67 40 24 67 40 38 58 67 14`69 39 58`71 73 92`99 73 27 95 92-67 56`56 73`67 92 82`71 73 56 23 56 92`67 58`73 46 58 18 56 69 40 17 56 39 62.
67 58`25 46 56 99 17 56`92`87 92 67 27 73 14,95 40 95`56 67`27 69 92 80 58 17`51 58 17 62`92 82`67 58 17 58 23 95 56 23 56`92`71 95 24 56 73 92 38 58 39 95 56 23 56`25 27 73 58 99 58 39 73 69 92 10-73 46 92`25 27 17 62 73 40`25 56`25 46 40 69 56 87 27`18 56 46 73 27,27 39 14 25 40 67 67 14 58`38 58 46 73 56 69 56 31`27 31 87 56 31`73 27 87 18 17 58 46 56 69,17 40 87 25 56 38 58 95,25 58 46 58 95 17 36 38 40 73 58 17 58 31`92`95 67 56 25 56 95.73 46 92`69 14 25 27 95 17 14 82`71 95 46 40 67 40`69`69 92 80 58`69 58 46 73 92 95 40 17 62 67 14 82`25 46 10 87 56 27 23 56 17 62 67 92 95 56 69-56 67 92`39 40 87 14 58,67 92 95 40 95 56 31`56 99 92 18 95 92…
18 56 80 46 56 39 73 92`46 40 80 92,56 67`25 56 69 73 56 46 92 17`25 46 56`39 58 18 10`25 56 17 36 18 92 69 99 27 36 39 10`51 92 73 40 73 27:“38 73 56`56 80 92 67`38 58 17 56 69 58 95`25 56 39 73 46 56 92 17,80 46 27 23 56 31`24 40 69 39 58 23 80 40`46 40 24 17 56 87 40 73 62`39 87 56 43 58 73”.92,25 56 82 17 56 25 40 69`25 56`25 17 58 38 27 39 73 46 40 99 92 17 27`69`24 67 40 95`73 56 23 56,38 73 56`67 40 25 40 46 67 92 95`80 56 17 43 58 67`18 80 92 73 58 17 62 67 56`39 73 56 10 73 62`67 40`99 27 82 58 46 58,80 56 39 73 40 17`95 92 67 43 40 17`92 24`25 46 92 99 92 73 14 82`67 40 80`95 56 17 58 67 56 87`67 56 43 58 67.
D;
 
preg_match_all('~(\d\d)\s*,~', $data, $m);
$stat = [];
foreach ($m[0] as $v) {
    if (!isset($stat[$v])) $stat[$v] = 0;
    $stat[$v]++;
}
arsort($stat);
print_r($stat);
 
/*
[`92`] => 5
[`69`] => 3
[`95`] => 1
 
[`25 56`] => 3
[`67 58`] => 2
[`67 40`] => 2
[`92 24`] => 1
[`92 82`] => 1
[`56 73`] => 1
[`56 67`] => 1
 
 
*/
 
// 67 67 56 27 67 69 56 
//- 56 12.089201877934
//- 58 8.3333333333333
//- 92 7.3943661971831
//- 67 7.2769953051643
// 73 6.4553990610329
// 40 6.3380281690141
// 17 5.5164319248826
// 46 5.1643192488263
// 95 4.5774647887324
// 25 3.8732394366197
// 69 3.8732394366197
// 39 3.6384976525822
// 27 3.169014084507
// 87 2.6995305164319
// 80 2.5821596244131
// 10 1.9953051643192
// 38 1.7605633802817
// 23 1.7605633802817
// 24 1.6431924882629
// 18 1.6431924882629
// 62 1.5258215962441
// 14 1.5258215962441
// 99 1.4084507042254
// 31 0.93896713615023
// 43 0.82159624413146
// 82 0.82159624413146
// 36 0.46948356807512
// 71 0.46948356807512
// 51 0.23474178403756
 
// 67 56 13
// 25 56 13
// 73 56 13
// 56 69 12
// 67 40 11
// 95 56 11
// 25 46 11
// 58 67 10
// 38 58 10
// 39 73 10
// 17 92 10
// 67 92 10
// 56 67 9
// 56 25 9 -- ложное
// 58 17 9
// 92 67 8
// 46 40 8
// 46 58 8
// 46 92 8
// 40 17 8
// 17 56 8
// 23 56 8
// 17 58 8
// 46 56 7
// 69 56 7
// 58 46 7
// 73 58 7
// 73 46 7
// 56 39 7
 
// [67 56] => 6
// [56 31] => 6
// [39 62] => 5
// [23 56] => 4
// [67 58] => 4
// [56 69] => 4
// [17 92] => 4
// [17 56] => 3
// [14 82] => 3
// [24 40] => 3
// [67 40] => 3
// [92 10] => 3
// [67 92] => 3
// [25 56] => 3
 
$dict = [
    '56' => 'о', // 'а'
    '67' => 'н',
    '92' => 'и',
    '58' => 'е',
    '40' => 'а',
    '73' => 'т',
    '43' => 'ж',
    '39' => 'с',
    '87' => 'м',
    '14' => 'ы',
    '17' => 'л',
    '95' => 'к',
    '69' => 'в',
    '80' => 'д',
    '24' => 'з',
    '25' => 'п',
    '46' => 'р',
    '62' => 'ь',
    '10' => 'я',
    '23' => 'г',
    '27' => 'у',
    '31' => 'й',
    '38' => 'ч',
    '18' => 'б',
    '36' => 'ю',
    '99' => 'ш',
    '71' => 'э',
    '82' => 'х',
    '51' => 'ц',
    ];
 
$data = strtr($data, $dict);
$data = preg_replace('~([а-я])\s+(?=[а-я])~u', '$1', $data);
echo $data;
exit();
 
$letters_stat = [
'о' => 9.28,
'а' => 8.66,
'е' => 8.10,
'и' => 7.45,
'н' => 6.35,
'т' => 6.30,
'р' => 5.53,
'с' => 5.45,
'л' => 4.32,
'в' => 4.19,
'к' => 3.47,
'п' => 3.35,
'м' => 3.29,
'у' => 2.90,
'д' => 2.56,
'я' => 2.22,
'ы' => 2.11,
'ь' => 1.90,
'з' => 1.81,
'б' => 1.51,
'г' => 1.41,
'й' => 1.31,
'ч' => 1.27,
'ю' => 1.03,
'х' => 0.92,
'ж' => 0.78,
'ш' => 0.77,
'ц' => 0.52,
'щ' => 0.49,
'ф' => 0.40,
'э' => 0.17,
'ъ' => 0.04,
];
 
preg_match_all('~\d\d~', $data, $matches);
$encoded = '';
foreach ($matches[0] as $m) {
    $encoded .= chr((int)$m);
}
 
for ($i = 1, $len = strlen($encoded); $i < $len; $i++) {
    $c = $encoded[$i];
    if ($encoded[$i-1] === $c) echo ord($c), " ";
}
echo "\n";
 
$stat = [];
for ($i = 0, $len = strlen($encoded); $i < $len; $i++) {
    $c = $encoded[$i];
    if (!isset($stat[$c])) $stat[$c] = 0;
    $stat[$c]++;
}
 
$stat2 = [];
for ($i = 1, $len = strlen($encoded); $i < $len; $i++) {
    $c = $encoded[$i-1] . $encoded[$i];
    if (!isset($stat2[$c])) $stat2[$c] = 0;
    $stat2[$c]++;
}
 
 
foreach ($stat as $letter => $count) {
    $stat[$letter] = $count / strlen($encoded) * 100;
}
 
// foreach ($stat2 as $letter => $count) {
//  $stat2[$letter] = $count / strlen($encoded) * 100;
// }
 
arsort($stat);
arsort($stat2);
 
foreach ($stat as $k => $v) {
    echo ord($k) . ' ' . $v . "\n";
}
 
echo "\n";
 
foreach ($stat2 as $k => $v) {
    echo ord($k[0]) . ' ' . ord($k[1]) . ' ' . $v . "\n";
}
 
// $codes = array_keys($stat);
// $letters = array_keys($letters_stat);
// $letters = array_slice($letters, 0, sizeof($codes));
 
// $decode_table = array_combine($codes, $letters);
 
// $decoded = '';
// for ($i = 0, $len = strlen($encoded); $i < $len; $i++) {
//  $decoded .= $decode_table[$encoded[$i]];
// }
 
// echo $decoded;

Не по теме:

было просто интересно



Добавлено через 11 минут
ну да, ответ такой же. правда я анализировал почти все вручную, сначала несколько букв (2-3) определяются по статистике, 'о', 'н', одно-и двухбуквенные сочетания, затем 'и', зная расположение пробелов, поскольку 'и' -- довольно распростаненный союз. 'е' -- опять же статистика, далее последнее слово 'но?ен' -- либо 'ж', либо 'в', но последний вариант довольно быстро отпал. дальше 'а' -- по статистике, там довольно резкий перепад для оставшихся букв, ну а дальше как-то само собой, тупо вчитывался и проверял сочетания в конечном тексте.
Вероятно, мой алгоритм не идеален, не слишком крут и не поддается автоматизации, но надеюсь, такое объяснение хоть чем-то поможет ТС.
2
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
20.05.2015, 06:54
Цитата Сообщение от NEbO Посмотреть сообщение
и не поддается автоматизации
На тему "автоматизации" я видел множество статей и ни одной пригодной для русского текста программы.

Не по теме:

Для английского нашел одну - сделанную "через это место": Alkindus

Миниатюры
Криптоанализ текста, зашифрованного методом простой замены  
0
601 / 468 / 73
Регистрация: 22.01.2009
Сообщений: 1,180
Записей в блоге: 1
20.05.2015, 08:15
не знаю, я конечно атаками по статистике не занимался, но на первый взгляд, при наличии хорошей базы слов, генетикой с fitness(X) = recognized_words/total_words, скрещивание -- перестановки хромосом с вероятностью, соответствующей статистике букв (и, вероятно, двубуквенных сочетаний, они, как я понимаю, даже важнее) должно это неплохо решаться, на "обычных" текстах. Одно только странно -- как производить мутацию, ведь явно заменять, например, 'а' на 'ы' -- это бред. Поэтому может это и не самая хорошая модель.
Однако, возможно, имитация отжига здесь подойдет, или муравьиного роя...
А еще есть более "человеческий" алгоритм, когда мы знаем границу слов, взять, скажем, все слова из текста до n-букв (слишком длинные слова могут иметь огромное количество словоформ, да и написаны быть в "авторском стиле") и получить что-то вроде n-мерного судоку. делается предположение а (37=о), делается предположение б (54=е). проверяется на соответствие шаблонам в базе наличие слов с таким шаблоном (можно опять же проверять в первую очередь только "маленькие" по длине слова), и тут же либо эти предположения отвергаются, либо получается ограниченный набор букв для предположения в. Аналогично, с учетом ограничений, делается предположение в, вероятно, с учетом статистики тех букв, которые можно предположить, ну и так далее. После 5-6 таких предположений в глубину, на мой взгляд, наверняка обнаружится либо несоответствие, либо вероятность верности этих предположений будет будет оооочень близка к 1. То есть что-то вроде эдакого МВГ, как в задаче о ферзях. То есть реально в глубину нет смысла заползать очень далеко, а перебрать даже 33^5 ой степени вариантов (хотя очевидно, что не потребуется проверять, скажем, мягкий знак как самую часто встречающуюся букву) вполне реально.
А без знания границ слов можно взять отжиг. Нужна база 2-3 буквенных сочетаний и вероятность по ним, и спускаться в глубину после нахождения минимальной вероятности сочетания букв в тексте с вероятностью, равной этой "минимальной статистике", или как-то учитывать разницу "минимальной статистики" от предыдущей итерации и текущей...

Не по теме:

Да, под утро язык заплетовывается, и я не совсем понимаю о чем я, просто набор каких-то абстрактных идей:)


Вообщем, тема довольно интересная, правда я, на данный момент, не вижу в этом особого смысла на практике (даже когда делаешь что-то лично для себя, и это что-то делать явно не неделю, в этом должна быть какая-то цель, имхо). Впрочем, если в нашей суровой реальности это где-то хоть как-то можно применить -- расскажите, вероятно, мое отношение к этому изменится, тогда можем подумать об этом вместе, или же я сам как-нибудь вернусь к этой теме
1
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
20.05.2015, 13:59
Цитата Сообщение от NEbO Посмотреть сообщение
это где-то хоть как-то можно применить
Формально, для текста возможны ровно две операции: подстановка (замена) и перестановка (перемешивание). Так что любой потоковый или блочный шифр реализует именно их (на уровне байт или бит). И классические ("ручные") шифры - удобная модель и testpad для теоретиков. Для остальных, думаю, такое же развлечение, как разгадывание кроссвордов, например.

Что до выбора способа оптимизации, IMHO, это почти не имеет значения - вдали от "резонанса" чувствительность любой модели будет очень мала, а вблизи - сойдется почти любая. Критичен именно выбор фитнесс-функции.

Как показывают мои эксперименты с большими словарями, ориентироваться при пробах ключа на точные совпадения почти бессмысленно. И, судя по литературе, переход от биграмм к N-grams более высокого порядка "не стоит выделки".

Но (в тех редких случаях), когда границы слов известны, перебор по словарю может быть очень эффективен.

Ну и, конечно, не стоит пренебрегать выделением гласных - используя SVD или метод Сухотина-Шеворошкина.

Добавлено через 4 часа 50 минут
Цитата Сообщение от gazlan Посмотреть сообщение
Критичен именно выбор фитнесс-функции.
Решил, что следует пояснить подробнее.

Пусть имеется набор (вектор) целых чисел 1..N (назовем его "ключ"), произвольно перемешанных и их требуется отсортировать.

Известно множество алгоритмов сортировки и достичь цели можно используя любой из них. Критично, что для элементов ключа существует лексикографическая упорядоченность (они образуют алфавит): элементы ключа уникальны и при попарном их предъявлении, всегда существует возможность указать порядок следования - кто кому предшествует.

Иными словами, задана фитнесс-функция f(k) и операция сравнения элементов ki и kj --> S(f(ki) , f(kj)), позволяющая установить порядок их следования. Для целых чисел можно, например, принять, что f(k) - тождественная функция: f(k) = k.

Поскольку "жизнь не по учебникам", фитнесс-функция f может работать не всегда корректно, иногда возвращая неверное значение f(k) = k + https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbf{\varepsilon}. Но если f выдает правильные значения чаще, чем ошибочные, после некоторого числа итераций будет получен "почти правильно" отсортированный ключ.

Назовем такую сортировку прямой (элементы ключа могут быть сравнены непосредственно).

Может случиться так, что операция сравнения элементов ki и kj неопределена или невозможна. Тем не менее, ключ все еще может быть отсортирован, если существует фитнесс-функция F сравнения ключей "в целом" (не поэлементно).

Назовем такую сортировку непрямой (косвенной) (сравниваются НЕ элементы ключа, а сами ключи в целом - фитнесс-функция F вычисляется интегрально для всего ключа).

Иными словами, при непрямой сортировке предъявляются два ключа и спрашивается, какой из них "более сортирован". При тех же допущениях о вероятностном характере работы фитнесс-функция F, если F выдает правильные значения чаще, чем ошибочные, после некоторого числа итераций будет получен "почти правильно" отсортированный ключ (процесс "сходится" к правильному ключу).

Заметьте, что алгоритм сортировки во всех этих рассуждениях не участвует вовсе, достаточно его осуществимости.

Так вот, то что я до сих пор стыдливо называл "непрямой сортировкой" и есть дешифровка подстановочного шифра.

Следовательно, необходимые условия дешифровки:
  • Осуществимость сравнения двух ключей в целом
  • Вычислимость фитнесс-функции от ключа
  • Корректность работы фитнесс-функции
И если последнее условие не выполняется (фитнесс-функция не является правильной мерой корректности ключа), все прочее уже не имеет значения.
2
601 / 468 / 73
Регистрация: 22.01.2009
Сообщений: 1,180
Записей в блоге: 1
20.05.2015, 15:00
хм. А имеет ли на право существования какая-то такая идея.
суть алгоритма дешифровки -- это минимизация энтропии (в общем плане, т.е. как меры неопределенности). Соответственно это и будет фитнесс-функцией.
Дабы определить энтропию текста из n-символов, определяется энтропия от 1го, 2х, 3х и так далее символов. Мне видится это как-то так: составляются шаблоны T=A1,A2,...,Ai, в которой Ai=Aj тогда и только тогда, когда на позициях i и j стоят одинаковые символы. Ну то есть, например, шаблон AAB будет соответствовать последовательностям 'нне', 'aao', 'кку' и так далее. Производится частотный анализ на обучающей выборке (большом количестве текстов), при котором устанавливается, насколько "хорошо" данный шаблон идентифицирует последовательность букв. Ну то есть, если для шаблона ABC понятно, что он почти ничего не определит, но например, ABB определяет символы точнее (и, по-моему, очевидно, что дело не только в меньшем количестве комбинаций символов, подходящих под данный шаблон). Соответственно, считаем, что "энтропия" S шаблона ABB S(ABB) меньше, чем S(ABC). Постепенно находя S для шаблонов n-ой длины, отсеиваем те из них, у которых S велико (функция S должна быть составлена таким образом, чтобы их должно быть заведомо больше), и по сути, принимается просто равной 1. Это делается для того, чтобы все влезло в базу.
Далее, очевидно, что сама S мерности n мало (если вообще) связана с S мерности n-1, зато отдельные слова по многом независимы друг от друга. Поэтому суммарную St можно считать как некоторую функцию от S(1 word)+S(2 word)+S(3 word)+... Поэтому при частотном анализе также необходимо учитывать и разрыв слов (при анализе текста на исходном языке нам это известно в любом случае).
Под "энтропией слова" можно понимать статистические выбросы для количества слов, подходящих под данный шаблон (собственно, из них и складывается сама эта "энтропия шаблона"), таким образом получается правило для вычисления S от всего текста.
Оператор суммы для S(S1,S2) предлагаю определить как S1*S2/(S1+S2), сами же функции для вычисления S(word) и S(template) еще нужно уточнить, там есть свои ньюансы при анализе выбросов (в частности, не очень ясно, какой можно взять доверительный интервал).
В итоге фитнесс-функция будет сводиться к минимизации этой "энтропии текста", с учетом вероятных границ слов и всего такого. Далее можно использовать либо генетику, либо еще что-то, для организации перебора, а возможно и рассмотрение этих шаблонов в качестве классификаторов (наподобие метода Виолы-Джонса), или что-то в этом роде.
Не знаю, насколько понятно изъяснился мой сонный мозг, просто что-то стало реально интересно, и интересно, вообще стоит ли рассматривать подобные методы. Поскольку опыта анализа всяких шифров и текстов у меня толком нет (разве что только что-то самое простое)
1
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
20.05.2015, 16:44
Цитата Сообщение от NEbO Посмотреть сообщение
суть алгоритма дешифровки - это минимизация энтропии (в общем плане, т.е. как меры неопределенности)
Энтропия не имеет отношения к "определенности" и, вообще, к семантике текста. Это чисто техническая характеристика - коэффициент использования системы кодов (степень заполнения тары при транспорте информации). В частности, шенноновская (Ho) энтропия эквивалентна для любых анаграмм (в шифре простой замены, энтропии исходного и зашифрованного текста совпадают). Математически, шифрование - это просто поворот вектора в кодовом пространстве, а дешифровка - отыскание угла поворота. (Если вам встречались кодовые замки, где не требуется носить с собой механический ключ, а достаточно правильно повернуть циферблат или колесико, то вы легко представите такой поворот).

Фактически, сравнивая с произвольным равновероятным текстом ("белым шумом"), легко видеть, что осмысленность достигается введением "запрещенных состояний" - ограничений на длину слова (и ее подчиненностью закону Ципфа), асимметрией кратностей использования символов и их комбинаций, запретом на определенные комбинации итп.

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

Это замечательно решило бы проблемы не только машинного перевода и криптографии, но и означало бы прогресс в сжатии текстовой информации. К сожалению, премии пока остаются невостребованными.

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

Не по теме:

Можете сравнить с гораздо более простой и много лучше определенной игрой в шахматы. В шашках же, насколько мне известно, не удалось достичь и этого.

1
-30 / 27 / 1
Регистрация: 14.03.2015
Сообщений: 805
08.06.2015, 04:26
gazlan, подскажите пожалуйста хорошую книгу об основах криптографии.
0
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
08.06.2015, 05:29
Цитата Сообщение от gogaloh Посмотреть сообщение
хорошую книгу
Это зависит от вашего уровня. Совсем вводные это Кан, Дэвид "Взломщики кодов" и Сингх "Книга шифров. Тайная история шифров и их расшифровки". Популярно об основах (по алфавиту, различной сложности, статьи и книги):
  • Аграновский, Хади "Практическая криптография, алгоритмы и их программирование"
  • Баpичев "Совpеменные кpиптогpафические методы защиты инфоpмации"
  • Баpичев "Криптография без секретов"
  • Брассар "Современная криптология"
  • Винокуров "Криптография, ее истоки и место в современном обществе"
  • Винокуров "Серия выпусков по криптографии для 'iNFUSED BYTES Online'"
  • Винокуров "Цикл статей по криптографии"
  • Винокуров "Как устроен блочный шифр"
  • Винокуров "Шифрование и шифры"
  • Гарднер "От мозаик Пенроуза к надежным шифрам"
  • Гомес "Математики, шпионы и хакеры"
  • Дориченко, Ященко "25 этюдов о шифрах"
  • Жданов, Куденкова "Криптоанализ классических шифров"
  • Жельников "Кpиптогpафия от папиpуса до компьютеpа"
  • Ларин "Защита информации советских партизан и подпольщиков"
  • Ларин "Советская шифровальная служба в годы Великой Отечественной войны"
  • Масленников "Практическая криптография"
  • Масленников "Криптография и свобода"
  • Ожиганов "Основы криптоанализа симметричных шифров"
  • Панасенко "Алгоритмы шифрования. Справочник"
  • Рябко, Фионов "Криптографические методы защиты информации"
  • Саломаа "Криптография с открытым ключом"
  • Семьянов "Почему криптосистемы ненадежны"
  • Синельников "Шифры и революционеры России"
  • Синельников "Шифры советской разведки"
  • Скляров "Искусство защиты и взлома информации"
  • Смарт "Криптография"
  • Смит "Аутентификация. От паролей до открытых ключей"
  • Соболева "История шифровального дела в России"
  • Соколов, Степанюк "Защита от компьютерного терроризма"
  • Столлингс "Криптография и защита сетей. Принципы и практика"
  • Токарева "Об истории криптографии в России"
  • Фейстель "Криптография и компьютерная безопасность"
  • Фергюсон, Шнайер "Практическая криптография"
  • Шнайер "Курс самоподготовки по криптоанализу блочных шифров"
  • Шнайер "Прикладная криптография"
  • Шнайер "Слабые места криптографических систем"
  • Ященко "Введение в криптографию"
  • Ященко "Основные понятия криптографии"

Возможно, стоит начать со Шнайера - "Прикладная криптография" для понимания основ, Соболева и Токарева просто увлекательны :-)
6
-30 / 27 / 1
Регистрация: 14.03.2015
Сообщений: 805
08.06.2015, 11:55
gazlan, спаси тебя Боже.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
08.06.2015, 11:55
Помогаю со студенческими работами здесь

Расшифровать текст методом простой замены
Здравствуйте! Бьюсь уже несколько дней, но не могу расшифровать этот чертов текст, кто может помочь с расшифровкой или хотя бы куда копать?...

Расшифровать текст, зашифрованный методом простой замены
Здравствуйте. Помогите расшифровать текст, зашифрованный методом простой замены. 32 буквы в алфавите, е заменяет ё. Пробелы не указаны. ...

Расшифровать текст, зафифрованный методом простой замены
Ошл дешыосчм ьэыюяы ъсоыфщыуъы ьэсрюямохяи рсцюяохясшиъзс эмфщсэз Оюсшсъъыц. Щз ъс яышичы ъс фъмсщ, ъмючышичы ыъм осшхчм, ъы ъмщ рмус...

Криптоанализ шифротекста, полученного методом простой замены
Здравствуйте! Помогите пожалуйста! Я думаю, это в ваших силах. Задание: написать программу для криптоанализа шифротекста. При...

Дешифровщик текста, зашифрованного методом Цезаря
Здравствуйте. В универе задали написать прогу, которая расшифровывает заранее зашифрованный методом Цезаря текст. Реализовал проверку на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru