solitaire.texi

   1 @node Solitaire
   2 @unnumbered Пасьянс (шифр Solitaire)
   3
   4 @url{https://www.schneier.com/solitaire.html, Алгоритм Solitaire}
   5 (пасьянс) изобретён @url{https://www.schneier.com/, Брюсом Шнайером}
   6 специально по запросу Нила Стивенсона для его книги "Криптономикон". Его
   7 вопросом было изобретение возможности обмена зашифрованными сообщениями
   8 в тяжелейших условиях, когда невозможно пользоваться какими-либо
   9 подручными средствами в виде электроники или других компрометирующих
  10 устройств, не вызывая подозрений.
  11
  12 Шнайер придумал как для этого можно использовать обычную игральную
  13 колоду карт. Очень доступная и дешёвая вещь, которая не привлечёт
  14 особого внимания полицию.
  15
  16 Сама по себе колода используется как генератор псевдослучайных чисел,
  17 вывод которого необходимо сложить по модулю 26 с цифровыми значениями
  18 букв алфавита. Алгоритм очень легко запоминается, прост,
  19 криптографически достаточно стоек, можно без проблем выполнить и на
  20 компьютере.
  21
  22 Использоваться должна полная колода карт: 4 масти по 13 карт каждой и
  23 два различимых джокера. Интересный и очень полезный факт
  24 @verb{|2 * 13 = 26|}: столько же, сколько и букв в латинском алфавите.
  25
  26 Всего колода (ключ) может иметь
  27 @verb{|((4 * 13) + 2)! = 54! ~ 2.31 * 10^71|} значений.
  28
  29 @strong{Шифрование/дешифрование}
  30
  31 @enumerate
  32 @item
  33 Уберите @strong{все} знаки пунктуации. Их можно заменить буквенными
  34 эквивалентами. Все буквы переведите в один регистр.
  35 @item
  36 Переведите буквы в их численное представление: @verb{|A=1, B=2, ..., Z=26|}
  37 @item
  38 Сгенерируйте последовательность псевдослучайных чисел по алгоритму
  39 Solitaire. Длина должна быть равна длине открытого текста.
  40 @item
  41 Поочерёдно сложите каждое числовое представление буквы открытого текста
  42 с этой случайной последовательностью по модулю 26.
  43 @item
  44 Преобразуйте получившиеся числа в буквенное представление: получите
  45 шифротекст.
  46 @item
  47 Для дешифрования необходимо проделать всё то же самое, только вместо
  48 сложения, использовать вычитание случайной последовательности из
  49 шифротекста.
  50 @end enumerate
  51
  52 @strong{Пример}
  53
  54 Мы хотим зашифровать сообщение @verb{|DO NOT USE PC|}. В криптографии
  55 любят разбивать сообщения на группы по пять символов:
  56
  57 @verbatim
  58 DONOT USEPC
  59 @end verbatim
  60
  61 Преобразуем в численный вид:
  62
  63 @verbatim
  64 4 15 14 15 20    21 19 5 16 3
  65 @end verbatim
  66
  67 Используйте Solitaire для генерирования ключевой последовательности
  68 (случайной последовательности, зависящей от ключа). Предположим что мы
  69 получили:
  70
  71 @verbatim
  72 KDWUP ONOWT
  73 @end verbatim
  74
  75 Преобразуем в численный вид:
  76
  77 @verbatim
  78 11 4 23 21 16    15 14 15 23 20
  79 @end verbatim
  80
  81 Сложим их по модулю 26 (если сумма больше 26, то тогда необходимо
  82 вычесть 26 из результата (1 + 1 = 2, 26 + 1= 27 - 26 = 1):
  83
  84 @verbatim
  85 15 19 11 10 10    10 7 20 13 23
  86 @end verbatim
  87
  88 Преобразуем этот шифротекст в буквенное представление:
  89
  90 @verbatim
  91 OSKJJ JGTM
  92 @end verbatim
  93
  94 Это сообщение можно передать собеседнику. Собеседник использует
  95 Solitaire для получения ключевой последовательности. Если все правила её
  96 генерирования совпадают, то его последовательность тоже получится
  97 @verb{|KDWUP ONOWT|}.
  98
  99 Ему необходимо преобразовать шифротекст в численное представление и
 100 вычесть из него числа ключевой последовательности по модулю 26 (то есть,
 101 если первое число больше или равно второму, то добавьте к первому 26
 102 (22 - 21=21, 1 - 22=5)):
 103
 104 @verbatim
 105 4 15 14 15 20    21 19 5 16
 106 @end verbatim
 107
 108 Преобразуйте получившуюся последовательность в буквенное представление:
 109
 110 @verbatim
 111 DONOT USEPC
 112 @end verbatim
 113
 114 @strong{Генерирование случайных чисел}
 115
 116 Каждая карта имеет своё собственно число. От 1 (туз) до 13 (король), от
 117 14 до 26, итд. Сначала одна масть, затем другая, итд. Необходимо
 118 условиться какой порядок мастей будет идти. Разницы никакой -- главное
 119 чтобы обе стороны договорились об этом. Шнайер предлагает правила
 120 бриджа: трефы (♣), бубны (♦), черви (♥), пики (♠).
 121
 122 Также джокеры необходимо отличать друг от друга. Условимся и назовём
 123 одного джокера как A, а другого как B.
 124
 125 Для удобства колоду лучше иметь не перемешанную. Сначала туз треф, потом
 126 двойка треф,..., король треф, туз бубен,..., король пик, джокер A,
 127 джокер B.
 128
 129 Чтобы получить одну букву "вывода" из Solitaire проделайте следующее:
 130
 131 @enumerate
 132 @item Найдите джокера A. Переместите на одну карту вниз. То есть,
 133 поменяйте местами с картой под ним. Если он внизу колоды, то поместите
 134 его наверх.
 135
 136 @item Найдите джокера B. Переместите на две карты вниз. Если он внизу
 137 колоды, то значит его необходимо поместить под первую карту сверху.
 138 Колода это зацикленная структура. Если колода до первого пункта была
 139 такой:
 140
 141 @verbatim
 142 A 7 2 B 9 4 1
 143 @end verbatim
 144
 145 то, после второго пункта она должна быть такой:
 146
 147 @verbatim
 148 7 A 2 9 4 B 1
 149 @end verbatim
 150
 151 А если была такой:
 152
 153 @verbatim
 154 3 A B 8 9 6
 155 @end verbatim
 156
 157 то станет:
 158
 159 @verbatim
 160 3 A 8 B 9 6
 161 @end verbatim
 162
 163 @item Сделайте тройной отрез (triple cut). То есть, обменяйте карты над
 164 верхним джокером и под нижним.
 165
 166 Если колода была такая:
 167
 168 @verbatim
 169 2 4 6 B 5 8 7 1 A 3 9
 170 @end verbatim
 171
 172 то станет:
 173
 174 @verbatim
 175 3 9 B 5 8 7 1 A 2 4 6
 176 @end verbatim
 177
 178 Помните, что джокеры и карты между ними места не меняют.
 179
 180 Если колода была такой:
 181
 182 @verbatim
 183 B 5 8 7 1 A 3 9
 184 @end verbatim
 185
 186 то станет:
 187
 188 @verbatim
 189 3 9 B 5 8 7 1 A
 190 @end verbatim
 191
 192 Если была такой:
 193
 194 @verbatim
 195 B 5 8 7 1 A
 196 @end verbatim
 197
 198 то на этом шаге не изменится.
 199
 200 @item Сделайте отрез с отсчётом (count cut). Посмотрите на нижнюю карту.
 201 Преобразуйте в число от 1 до 53. (если ♣, то число показано на карте;
 202 если ♦, то значение @verb{|+13|}; если джокер, то значение @verb{|= 53|}).
 203 Отсчитайте от верхней карты такое количество карт и поместите их над
 204 последней картой.
 205
 206 Если колода была такая:
 207
 208 @verbatim
 209 7...cards...4 5...cards...8 9
 210 @end verbatim
 211
 212 а @verb{|4|} является девятой картой, то колода станет такой:
 213
 214 @verbatim
 215 5...cards...8 7...cards...4 9
 216 @end verbatim
 217
 218 Если нижней картой является джокер, то колода останется неизменной.
 219
 220 @item Найдите выходную карту (output card). Посмотрите на верхнюю карту.
 221 Преобразуйте в число то 1 до 53. Отсчитайте столько же карт (верхняя
 222 карта является первой). Запишите/запомните карту до которой дошёл счёт.
 223
 224 @item Преобразуйте карту (числовое значение) в буквенное представление.
 225 Так как в алфавите 26 букв, то трефы (♣) от 1-13, бубны (♦) от 14-26,
 226 черви (♥) от 1-13, пики (♠) от 14-26.
 227 @end enumerate
 228
 229 Для получение следующего символа ключевой последовательности просто
 230 повторите все шаги.
 231
 232 @strong{Начальное состояние колоды}
 233
 234 Начальное состояние колоды перед генерирование ключевой
 235 последовательности является, по сути, ключом шифрования. Стойкость
 236 алгоритма основана полностью на стойкости (качестве) ключа. Алгоритм
 237 может быть известен любой полиции, но вся сила заключена в ключе.
 238 Как это применимо и к любому другому серьёзному "боевому" алгоритму.
 239 @strong{Ключевание} колоды -- самая ответственная часть.
 240
 241 @itemize
 242 @item
 243 В идеале лучше иметь две идентичные как можно более случайно
 244 перемешанные колоды. Одна идёт отправителю, а другая получателю
 245 сообщений. Но полиция может найти колоды -- это опасно.
 246 @item
 247 Использовать сторонний независимый источник и правила перемешивания
 248 колоды относительно его. Например газеты или журналы.
 249 @item
 250 Использовать парольную фразу для ключевания колоды. Просто используйте
 251 алгоритм Solitaire, только вместо пятого шага (output card) произведите
 252 ещё один отрез с отсчётом (count cut) -- то есть ещё один четвёртый шаг
 253 повторно, только в качестве числа отсчёта используйте символ из
 254 парольной фразы. И так повторяйте для каждого символа парольной фразы.
 255 @end itemize
 256
 257 @strong{Пример использования}
 258
 259 Первый выходной символ:
 260
 261 @itemize
 262 @item
 263 @verbatim
 264 1 2 3 4 ... 52 A B
 265 @end verbatim
 266
 267 @item
 268 @verbatim
 269 1 2 3 4 ... 52 B A
 270 @end verbatim
 271
 272 @item
 273 @verbatim
 274 1 B 2 3 4 ... 52 A
 275 @end verbatim
 276
 277 @item
 278 @verbatim
 279 B 2 3 4 ... 52 A 1
 280 @end verbatim
 281
 282 @item
 283 @verbatim
 284 2 3 4 ... 52 A B 1
 285 @end verbatim
 286
 287 @item пятый шаг производит выходной символ, так как наверху 2, то
 288 отсчитайте до 4 -- это и есть выход.
 289 @end itemize
 290
 291 Второй выходной символ:
 292
 293 @itemize
 294 @item
 295 @verbatim
 296 2 3 4 ... 49 50 51 52 B A 1
 297 @end verbatim
 298
 299 @item
 300 @verbatim
 301 2 3 4 ... 49 50 51 52 A 1 B
 302 @end verbatim
 303
 304 @item
 305 @verbatim
 306 A 1 B 2 3 4 ... 49 50 51 52
 307 @end verbatim
 308
 309 @item
 310 @verbatim
 311 51 A 1 B 2 3 4 ... 49 50 52
 312 @end verbatim
 313
 314 @item
 315 Пятый шаг производит выход. Наверху карта 51, отсчёт 51-ой карты
 316 даёт карту 49.
 317
 318 @end itemize
 319
 320 @strong{Заметки по применению}
 321
 322 @itemize
 323 @item @strong{Никогда} не используйте один и тот же ключ для шифрования
 324 двух различных сообщений.
 325 @item Шифруйте достаточно короткие сообщения, не более нескольких тысяч
 326 символов.
 327 @item Как и все потоковые шифры, одна ошибка приводит к сбою всего
 328 алгоритма и дешифровать сообщение уже не получится. Желательно всегда
 329 дважды зашифровать сообщение, чтобы убедиться в отсутствии ошибок.
 330 @item Весь процесс Solitaire может быть обращён. Если вы оставите хотя
 331 бы что-то (записи, какую-то часть колоды), то полиция может обратить
 332 весь процесс шифрования.
 333 @item Пытайтесь всё делать в своей голове, иметь как можно меньше
 334 записей. Если полиция врывается, то перемешайте колоду. Если на бумаге
 335 вы имеет записи, то лучше всего сжечь их. Папиросная бумага может быть
 336 сожжена без пепла.
 337 @end itemize