Шифр "Солитера"

[vitus_wagner]

Я уже когда-то писал про разработанный Брюсом Шнайером шифр Solitaire. Хочется довести его до криптосистемы, пригодной для использования партизанами в лесу (у которых нет газеты с колонкой бриджевых партий в качестве канала распространения ключей).

Изначально я позиционировал этот шифр в "Императрицу Кэт", где он использовался (с подачи Кэт, которой ничто не мешает иметь в ЛЭТ какую-нибудь книгу по истории криптографии с описанием этого шифра) иргантийскими партизанами, имеющими технологический уровень примерно перед началом Промышленной Революции, в то вреия как у их противника есть спутник связи и компьютеры. Правда, там людораки явно недооценивают иргантийцев и для Штрк Мрнт было шоком, когда Ашги Пуш достал из шкафа винтовку с оптическим прицелом местного производства.

Вообще говоря, ничто не мешает использовать этот шифр персонажам "Ясмины". Особенно агентуре Раджива Дасса. Потому что в радиорубках крейсеров и самолётов можно и что-то энигмоподобное держать. Хотя там я пока не уточнял чем именно шифруются радиопередачи. В принципе, для шифровки радиограмм и "решётка" сойдет.

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

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

Поэтому нужен шифр с plausible deniability участия тебя в сети шифрованной переписки. "Солитер" подходит для этого идеально, поскольку наличие у человека в кармане колоды карт, хоть в Англии начала XIX века, хоть в России начала XX - это не повод ему что либо инкриминировать. Но нужна возможность удобного хранения (в памяти человека) и распространиения ключей. Поэтому ключи должны быть фразами на естественном языке.

Вознмкает следующая идея:

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

Рассмотрение пробела как символа очевидно для высокотехнологичных людораков, но явно усложнит задачу криптоанализа как для Ашги Пуша, так и для английских и российских спецслужб прошлых веков, противостящих пришельцам из будущего.

Далее, берем ключевую фразу и ставим ее буквам в соответсвие карты по этой панграмме. Если нам попалась буква, которая в панграмме встречается несколько раз, то берем первое еще неиспользованное вхождение. Если попалась буква, которой соответствует карта, уже попавшая в ключевую последовательность, мы ее просто пропускаем. Поэтому скорее всего ключевые фразы, которые надо будет запоминать, будут длиннее 52 символов. Но они могут быть, например, стихотворными.

Панграмму тоже придется выучить наизусть.

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

Comments

[borisk]

Есть интересная книга Лео Маркса, "Шёлк и цианид", об английской агентуре Сопротивления в Европе.

Так вот, у них резервный шифр использовал в качестве ключа стихотворение. Для надёжности агенту рекомендовалось написать стихотворение самому — так выяснилось, что в Сопротивлении доля приличных поэтов значительно выше среднего ;)

[kouzdra]

Карманный чисто механический вариант Энигма имела

[vitus_wagner]

Но если у тебя его при обыске найдут в кармане - ты спалился.

[kouzdra]

С блокнотом таже проблема

[vitus_wagner]

Да. Чем и ценнен "Солитер".

[vlad_suh]

А если в качестве блокнота использовать какую-либо общедоступную книгу, стойкость сильно упадёт?

[toshische.livejournal.com]

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

[ald1976]

52 кода на 26/33 буквы - слишком малая избыточность. Такое моментально взломается частотным анализом, даже вручную, без компьютера. Если, конечно, не ограничиться только короткими сообщениями длиной не больше 52 символов [но это неюзабельно, обычно нужно передавать что-то более длинное].

Ну и симметричный ключ легко добыть ректо-термальным способом, так что надо иметь много таких ключей и часто [в идеале каждый ключ одноразовый] их менять.

[vitus_wagner]

Читайте статью Шнайера по ссылке. Там исходная перестановка 52 карт - это ключ. Который с помощьюб определенных манипуляций с колодой раскручивается в бесконечную гамму. То есть сколько есть в сообщении символов, столько гаммы и будет.

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

[ald1976]

Так уже лучше, но:

1. 52! - это ключ длиной менее 256 бит, по нынешним временам маловато;
2. непонятно, как на коленке и без компьютера использовать этот ключ для кодирования/декодирования за приемлемое время; алгоритм должен быть хоть сколь-нибудь сложным, а на коленке разве что отксорить этим ключом опен-текст, чего не предложил бы не только Шрайер, но даже школьник-двоечник. В "криптономиконе" что-то подобное было, там алгоритм реализовывался через тасовку колоды особым образом.
3. даже идеальный ключ надо менять довольно часто, если при каждой смене писать/учить новый стишок - криптограф повесится.

[vitus_wagner]

Ну там скорее 224. Но этого более чем достаточно для симметричного шифра. Вот берем openssl и смотрим, какие длинны ключа она поддерживае для rc4 (ближайшего аналога Solitaire) - Не более 128 бит. А для AES поддерживюатся 128/192/256. Ну то есть ни одного симметричного шифра с более чем 256-битным ключом я что-то в обиходе не вижу.

[ald1976]

Так AES уже 20+ лет. С тех пор вычислительные мощности подросли.

Да и заинтересованным лицам интересно искусственно придерживать криптостойкость на меньшем уровне, чем следовало бы.

Хотя вообще все это игры в неуловимого Джо. Который нафиг никому не нужен и может хоть открытым текстом коммуницировать. А если станет кому нужен, так его сломают, просто хакнув [посетив квартирку с помощью старой доброй отмычки и поставив в ней жучков] его комп и перехватив весь ввод с клавиатуры и портов.

Если какой-то Джо будет замечен в любви к сильной криптографии - у него есть неплохие шансы стать кому-то интересным :)

[vitus_wagner]

"Солитер" таким образом не хакнешь. Он делается на бумажке, а не на компе. Кстати рекомендую еще ознакомиться с тем что такое PBKDF, и каким образом она затрудняет подбор пассфразы. В данном случае алгоритм вывода перестановки колоды из пассфразы является типичным PBKDF.

[ald1976]

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

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

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

В жизни - тоже так себе проблема. Партизаны и подпольщики всех времен прекрасно ее решали и отнюдь не она была их проблемным местом в борьбе за победу.

[slobin]

Витус довольно невнятно пишет, но я надеюсь, что он имел в виду нечто другое. Шифруем "Солитером", а вот КЛЮЧ для генерации начальной перестановки порождаем как Витус написал. Насколько я понимаю, в оригинале (я, кстати, Шнайера не читал, я читал непосредственно Криптономикон; одно из немногих художественных произведений, где небольшой, но значимый отрывок написан на perl)... так вот, в оригинале ключ предполагалось таскать с собой в кармане в виде заранее перетасованной колоды. Но вопрос смены ключа там был по сюжету не актуален (равно как и вопрос, что делать, если полиция оказалась достаточно внимательной, чтобы заметить, что у двоих подозреваемых в карманах были колоды карт с одинаковым раскладом).

Витусу: 1) ты осознаёшь, что применение Солитера требует ДОФИГА внимательности и аккуратности на КАЖДУЮ букву? Интересно, сколько времени на одну букву будет уходить после пары дней тренировки? 2) Ты осознаёшь, что RC4 (а Солитер -- это RC4 с недвоичным константами) ломается именно на слабостях генерации ключа? Там содержательная проблема в том, что "последовательность символов" и "перестановка" -- величины как бы разных размерностей. Последовательностей символов k^n, а перестановок k!. И что хочешь делай, отображение одного в другого будет кривым. Правда, ломается оно на технике XXI века. Ладно, пойду почитаю собственно Шнайера (а не Криптономикон), может быть, он на эти вопросы отвечает.

... Настойчивость, усидчивость и прилежание ...

[vitus_wagner]

C размерностями там все не так страшно. Если мы рассматриваем кодирование перестановки 52 карт последовательностью 26 букв латинского алфавита, получаем что нам нужно такой n, чтобы

52! <=26ⁿ. Это n получается даже меньше 52 - 48.

Хотя описанный мной алгоритм, видимо, не будет оптимальным и потребует использвания фраз более чем из 48 букв. Надо поискать алгоритм получше.

Возможность взлома на слабостях генерации ключа актуальна для Ирганто где у противника есть компьютеры, но не для сюжетов про попаданцев, где противники просто к такому уровню не готовы. То есть идею с панграммой я придумал как раз для того, чтобы сделать распределение последовательностей более равномерным.

[kouzdra]

Энигмов-ского типа шифры потому кстати и не применялись, что одна ошибка рушит всё остальное.

Нужна машинка, которая не ошибается

Ну и кстати представление о нестойкости старых шифров - заблуждение.

Большая часть переписки Луи ХIV - это Россиньоль и ко - не расшифрована до сих пор.

Хотя известно, что это какой-то вид номенклаторных шифров

[vitus_wagner]

Вероятно на это дело не выделялись значительные ресурсы.

[kouzdra]

Довольно значительные. Историкам эта переписка интересна.

Тут какая засада - обычные методы криптоанализа к ним просто неприменимы напрямую - потому что они ориентированы на алфавитное кодирование, а специфически тема забыта с 19 века.

У Кана есть история как во время сухого закона долбились о бутлегерские шифры - сломали наконец, но нескоро.

А это и были кустарные номенклаторные шифры.

Россиньоль же был профессионалом и криптоаналитиком, т.е. уязвимости знал отлично

[burbilog]

Малоюзабельно. Не нужно изобретать велосипед, есть такая великолепная штука, как Rasterschlüssel 44 . Его с диким трудом ломали в Блетчли-парк и только потому, что немцы налажали с применением шифра -- было всего несколько типов поперечных планок для типографской печати шифра, что сильно ухудшило шифр.

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

Потом все уничтожается и никаких улик.

[burbilog]

Да, по хорошему надо бы колонки перемешать, можно их нумеровать 1, 2, 3 и так далее вначале везде где 0, потом где 1 и т.п., будут более-менее перемешаны. Для докомпьютерной эпохи это абсолютно криптостойко будет.

[vitus_wagner]

4 цифры секрета? 10000 вариантов? Если известен алгоритм, ломается перебором даже без компьютера. Сажаешь 100 девочек, каждой даешь диапазон в 100 вариантов ключа. За несколько часов получаешь все 10000 вариантов расшифровки и один из них оказывается содержащим осмысленный текст.

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

Кстати, интересно, сколько существует решеток заданного размера. Очевидно, что не любая последовательность бит длины n² является корректной решеткой с размером стороны n. Во-первых единичных бит должно быть ровно четверть, во-вторых, они должны быть размещены так, чтобы при повортах на 90, 180 и 270 друг на друга не накладываться.

Получается что надо брать треугольник в четверть квадрата и заполнять его цифрами от 0 до 3. А потом где 0 прорещать дырочки, единички копировать во второй треугольник, двойки в третий, тройки в 4-й. Получается n²/2 бит.

То есть решетка 8x8 это всего 32 бита ключа, 10x10 - 50. И ведь еще нужен случайный паддинг последнего блока, что при длине блока в 100 символов уже заметно усложняет жизнь.

То есть решетка 10x10 эквивалента одинарному DES, который ломается на устройстве, носимом в кармане любым представителем высокой цивилизации, будь он попаданец из нашего времени или инопланетный агрессор. А ведь у DES блок 8 символов, а не 100.

[burbilog]

Я для примера взял 4. Но даже так за несколько часов вы не получите 100 вариантов, это будет намного дольше. Я пробовал когда-то сам на бумаге, процесс небыстрый. Фактически вы предполагаете, что они безошибочно сделают по решетке за пару минут (все равно рабочий день больше 3 часов не получится -- дольше внимание невозможно будет удерживать, усталость приведет к массе ошибок). Возьмите ручку, включите таймер и попробуйте решетку 24 на 25 вручную вычислить.

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

Можно взять больше цифр, количество цифр в salt и в secret не влияет на трудоемкость вычисления, вообще. Или, что намного лучше, пустить второй поток цифр под первым (т.е. два salt, два секрета) и прореживать ряд вверху, глядя на то, четная или нечетная цифра в нижнем ряду. Т.е. вычисляем верхнюю цифру, потом нижнюю, если нижняя четная, верхнюю зачеркиваем, генерим столько, сколько нужно для полного заполнения, минус вычеркнутые.

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

То есть решетка 10x10 эквивалента одинарному DES

Решетка в RS44 была 24 на 25.

[vitus_wagner]

По-моему решетка не может быть а) не квадратной б) с нечетной стороной.

Она же должна при повороте на 90° правильно совмещаться сама с собой и после 4 поворотов обеспечить покрытие дырочками всех 100% квадратиков.

[burbilog]

Витус! Вы абсолютно не поняли принцип этого шифра. Если делать поворотную решетку, как бы вы ее не генерили, сломается она на раз. Поворотные решетки никакого смысла не имеют, это детская забава.

Смысл RS44 в том, что plaintext в решетку пишется горизонтально от стартовой ячейки, а шифр читается вертикально, причем столбики шифра читаются вразброс, в соответствии с номерами колонок. Ну и расшифровывается обратно -- шифр пишем вертикально начиная с заданной стартовой колонки в соответствии с нумерацией колонок, потом читаем текст горизонтально. Соотношение сторон тут не очень важно, важно только, чтобы текста было минимум 40 символов (для решетки 24 на 25). Если текста мало, последние два слова удваиваются, за ними добавляются случайные слова, чтобы было достаточно текста для перемешивания.

Это не игрушка, а реальный шифр, причем я где-то читал, что при правильном исполнении он будет посильнее DES.

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

[vythe]

А можно простыми словами пояснить для чайников? Даже неловко спрашивать, но очень любопытно.

С той частью, которую вы тут описываете, всё понятно - вам нужен "неугадываемый" ключ, но чтобы его было легко запомнить. Берём легко запоминаемую фразу и преобразуем её в красивый ключ некоторой цифровой магией. Угу. Непонятно насчёт самого солитера.

Из описания самого Шнайера, часть первая, в сокращении:
1) возьмите хитро-подготовленный ключ в 52 карты (одноразовый!);
2) некоей цифровой магией сгенерируйте из него ключ нужной длины;
3) зашифруйте своё сообщение, изменяя каждую его букву одной буквой из большого ключа.

Что непонятно:
* имеет ли значение хитровывернутость процедуры в (1)? Если враг знает исходную "партию бриджа" (или стихотворение, как у вас), он уже всё сломал. Если он не знает исходную фразу, то как бы без разницы - угадывать исходную фразу или сразу угадывать ключ в 52 карты, они по длине и содержанию одинаковые;

* если шифруемое сообщение меньше 52 знаков, то есть ли вообще смысл в (2)?

* имеет ли значение хитровывернутость процедуры в (2) или её можно заменить чем-то попроще? Если враг знает метод генерации большого ключа из ключа-52, то сложность того метода ему без разницы, а если не знает - то достаточно выбрать такой метод генерации, чтобы его с первой попытки не угадали.

И отдельно непонятно, почему в "солитере" не используется предыдущая зашифрованная буква - сначала полностью строится большой ключ, потом он применяется к заданному тексту. Такое упрощение никак не ухудшает секретность?

[vitus_wagner]

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

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

У "Солитера" ключом является перестановка колоды из 52 карт, т.е. эффективная длина ключа равна log₂(52!) = 225 бит. При этом все состояния колоды равновероятны, так что перебор не облегчишь.

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

Стихотворые цитаты хороши тем, в них трудно перепутать слово или букву. Поэтому их легко можно передавать из уст в уста.

Впрочем случаи бывают разные.

Помнится один мой знакомый поставил на сервер пароль necrozoopedofil, а через полгода понадобилось туда зайти с консоли и мы с beldmit долго гадали какая же у нашего коллеги сексвальная ориентация - некропедозоофил или некрозоопедофил.

[vythe]

С этим всё понятно, я немного другое спрашиваю. У "Солитера" есть две содержательных части: генерация ключа-52 и генерация "большого ключа" из имеющегося ключа-52. Соответственно и два вопроса:

1) будет ли ключ-52 из "Солитера" чем-то лучше любой другой процедуры, выдающей случайную строку из 52 букв? В частности, алгоритм из книжки берёт строку партии бриджа из газеты - т.е., врагу она вполне доступна, и преобразует её в другую аналогичную строку. Есть ли в этом действии какой-то смысл для надёжности? (если забыть, что расклады бриджа публиковали отсортированными)

2) есть ли какая-то польза от хитроумной генерации большого ключа, или достаточно взять любой алгоритм, хотя бы и просто повтор ключа-52 по кругу?

[vitus_wagner]

"большой ключ" называется "гаммой".

Ключ из Солитера вообще говоря хуже случайной строки из 52 букв. Он примерно эквивалентен случайной строке из 48 букв. (разница непринципиальная). Но он хорош тем что представляет собой готовую затравку для механического (основанного на раскладывании пасьянса) алгоритма для разворачивания ключа в гамму, длина которой равна длине сообщения.

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

Просто циклическое повторение ключа дает слишком регулярную структуру гаммы, и методы криптанализа для этого случая давно разработаны.

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

Режимы ECB и CBC, в которых через алгоритм шифрования пропускается непосредтсвенно открытый текст, используются редко и считаются не слишком надежными.

Обычно применяется гаммирование с обратной связью - OFB ии CFB. Т.е. там для вычилсения следующего блока гаммы к предыдущему подмешивается либо открытый (OFB) либо шифрованный (CFB) предыдущий блок. При этом основой алгоритма вычисления следующего гаммы является шифрование предыдущего блока гаммы. Чистое гаммирование (CTR) я встречал довольно редко, и обычно в сочетании с алгоритмом шифрования ГОСТ 28147-89.

[vythe]

Погодите, а разве метод генерации гаммы в Солитере как-то зависит от "затравки", от способа генерации ключа?

Метод генерации ключа в "книжной" версии довольно заморочистый, и я пытаюсь понять - нужен ли онр вообще, добавляет ли он надёжности, в сравнении с более простыми методами или вообще в сравнении с использованием исходной "партии бриджа".

То же самое с генерацией гаммы. Понятно, что самые простые методы, вроде циклического повтора, настоящие учёные могут распознать и вскрыть, но "чуть менее" простые способы могут сэкономить шифровальщику силы без особой потери надёжности. Или метод Солитера как-то уникально хорош?

Опять же, если мы говорим о коротких сообщениях, типа сто-двести символов - проявится ли там циклическая структура гаммы? А на длинных сообщениях шифровальщик сдохнет...

[igus]

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

Существенным, я бы сказал фатальным недостатком "Солитера" является отсутствие синхропосылки. Шнайер как-то сосредотачивается на одноразовых ключах, предлагая их брать из бриджевых колонок, хотя сам же указывает на угрозу полного перебора спецслужбами всех опубликованных бриджевых партий. В случае же пассфраз: держать в памяти сотни стихотворений, да ещё и не запутаться в порядке их применения - нет, это жить не будет, нужна синхропосылка. Дабы избежать перекрытий (точнее, свести их вероятность к незначимой), синхропосылка должна быть задействована способом, ортогональным к раскрутке гаммы. Единственное, что мне тут приходит в голову - складывать её с пассфразой и формировать стартовую раскладку из результата, но провести криптоанализ такой схемы мне слабо.

Дополнительной проблемой применения "Солитера" русскими социал-демократами будет кириллица. Шнайер по существу использует тот факт, что мощность алфавита гаммы ровно вдвое больше мощности алфавита открытого текста, редукция 52 до 26 не приводит к ухудшению качества гаммы. А вот как 52 карты смэппить на 36 букв русского алфавита - отдельная нетривиальная задача. Хотя... Если расширить алфавит до 39 символов, добавив в него пробел, точку и запятую, то можно мэппить 3 карты в 4 буквы.

UPD: Про мапинг 3 в 4 фигню написал, так не получится.

[vitus_wagner]

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

Правда я не совсем понимаю, чем плох циклический сдвиг от 1 до 52 по алфавиту из менее чем 52 символов.

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

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

[igus]

Правда я не совсем понимаю, чем плох циклический сдвиг от 1 до 52 по алфавиту из менее чем 52 символов.

Вот у тебя есть хорошая гамма с равномерным распределением на алфавите 1-52. Если ты накладываешь её на открытый текст по модулю 36, это криптоэквивалентно наложению гаммы 1-36, но с неравномерным распределением: 14 символов будут иметь вероятность появления 2/52, остальные 22 символа - 1/52. Чем плоха неравномерно распределённая гамма, пояснять, надеюсь, не надо.

Кстати, вот еще одна идея уменьшения избыточности - заменяем буквы их кодами в азбуке Морзе.

Тут ты приходишь к необходимости шифровать двоичную последовательность гаммой с алфавитом из 52 символов. 52=13*2^2, без потери равномерности ты можешь редуцировать 52 символа до 4 (с каждой карты брать только масть), как-то жирновато получается. Можно выкинуть из колоды, например, двойки, тем самым сократив алфавит до 48=3*16, редукция в 3 раза - это уже более-менее приемлемо, и 4 бита - это больше среднего размера символа в морзянке, так что даже несмотря на большую редукцию гаммы шифр получается менее трудоёмким. Но вот как уменьшение объёма колоды повлияет на стойкость шифра, я оценить не смогу.

[vitus_wagner]

Про азбуку Морзе - это было не про шифрование, а про раскрутку ключа из фразы.

Причем, видимо не для Солитера, а для какого либо другого ручного алгоритма, где именно двоичное представление удобно для последующих операций.

[vitus_wagner]

36 букв? Так надо взять тогда колоду из 36 карт (в смысле без двоек-пятерок). Такая колода достаточно часто применяется и подозрений сама по себе не вызовет.

[igus]

Математической моделью "Солитера" является группа подстановок на множестве из 54 элементов, каждая манипуляция с колодой - это какая-то подстановка из этой группы. Очевидно, что подстановки эти выбраны не от балды, а так, чтобы они обладали определенным свойствами, обеспечивающими в итоге стойкость шифра. Как я уже писал, теория групп подстановок никогда не была моей сильной стороной, я её хоть и сдал на пятёрку, но даже тогда не нутрил, а уж сейчас, когда всё забылось, я не буду даже пытаться понять, что это за свойства и сохранятся ли они при переходе к 38-карточной колоде.

Кстати, стандартная 36-карточная колода не содержит джокеров. Впрочем, их можно заменить полосками бумаги, кусочками ткани, листочками с ближайшего дерева и т.п., так будет даже удобнее, сильно упрощается операция "Find the A/B joker".

[ramendik]

У меня появился вопрос про Драконочку.

Не возникнет ли у кого-то из попаданцев желания найти где-то племянника Типу-Султана и выстроить ему подводную лодку.

Просто чтобы капитан Немо был.

[vitus_wagner]

Там вот такой вариант задуман, но еще в основной текст не включен.

[ramendik]

Тоже вариант :)