Таблицы Сойги: первый клеточный автомат?
Был ли первый клеточный автомат предназначен для шифрования и/или вызова ангелов?
Обычно история клеточных автоматов начинается с классического исследования фон Нейманом самовоспроизводящихся систем в 1950-х годах. Несмотря на явное влияние дискретных автоматов Тьюринга, это была первая статья, в которой использовалась сетка ячеек в разных состояниях, где каждая ячейка меняла каждый такт часов в соответствии с фиксированным универсальным правилом. Даже Стивен Вольфрам, кажется, думает так: «Несмотря на их очень простую конструкцию, ничего похожего на общие клеточные автоматы, кажется, не рассматривали до 1950-х годов».
Но, может быть, фон Неймана отодвинули на несколько столетий.
книга Сойги
книга Сойги книга раннего Нового времени. Он принадлежал доктору Джону Ди, елизаветинскому ученому, фокуснику и правительственному советнику (посмотрите занимательную книгу Лесли А. Ратледжа «Джон Ди: консультант королевы Елизаветы I»). Он упомянул об этом в нескольких местах, но личность произведения была утеряна на долгие годы. В 1994 году Дебора Харкнесс провела несколько хороших научных расследований и нашла копии в Оксфордской Бодлеанской библиотеке и Британской библиотеке (поданные под альтернативным, неочевидным названием). Работа содержит различные части астрологии, каббалы, списки сверхъестественных имен и формул призыва. . В конце 36 квадратов 36×36, по-видимому, случайных букв, помеченных созвездиями (дважды), планетами, стихиями и словом «magistri».
Примером может служить первый квадрат Овна:
ndizbdizbdizbdizbdizbdizbdizbdizbdiz
isrlytrlytrlytrlytrlytrlytrlytrlytrl
scucbxibaxibaxibaxibaxibaxibaxibaxib
roernmhggdokqsrnplfdfzlyqsrnplfdfzly
aqbtxdnxytybscuefnutohqtauiducisohqt
mppimcqsgbadzelbhsekfkhaczlaysrfqegb
mozlirdziqxthkceykubhpxqzbnpmreuhkyr
aqucmqablnmsqgitgqrnygdxppcsuiteybat
rdbectiqhsukhmhaigzpmffzrcfumhageqxl
smagikasqpkbkdnpyypeciupgiumlepuuhco
icdmhpoctzmamcqmxozgizygnzydqbrhbksy
nrpbkgusdecdroaofquyabaidensadyzdphd
nhurxymrpslatyqlctenpporpsxkqaabfrtm
iymqsgsbrfnpingrodkefrbtzunasipptbxd
sgsauykreueflkyiessnuiqqummzuarcyris
rscdbamqbyuxcnnzgauelfsaydrlrmqzatrf
ausmacpfddbzedshmzyuciipmcucudxpodyx
mtcpolmesmabgkkzohdbezlmlzysesfrbfaz
mslmnbonicdgnamyfktkupaothdzgahyrrmy
aucpceedolaidfogmikbygguleshmzkobtuo
rhhusntmnbcmciexdoskopumkukzohpdgbyf
sqelpcydsksusrqsmniaqmtubybbqeffiqto
iglhusgkkbumregaoxactulrnnqyhkxxasdt
nxclrfiamaydyuyqlsirgcobpctgosfzcxtd
nmbnhlfcpogkoengrflopqlygikyfuxpqsdi
icednbhhufiaqbpuiucrcttgnzmxxmugyktr
slbfppxzyxactkgcmtlolqqdshrimlrsgqqo
ryrrcsfbazcfxbirzxcryhxtclorznhzigyf
aatbeiurmysofdobbzehdnmslhtbbpxpyyoo
mzxrqfyicbufhieqypsqapbuclqyrcarkoyf
mynhxxorokmeyagyozuhfrnlzngehhftsyoo
aapxnmnhtsuuoixoypkzhyebbpuuzkxlpmne
rmofpbpxlpkmnzzqtzmyzaghgxmthplhudsn
sufhurcanfmlkpngbbogfckzimlqefnymcxe
ilclrermmecoszpurnexxsshouctnuencfzg
nbebtnhrzgieiozyidknmrfkfysdsetxsohm
Это похоже на многие другие магические книги раннего Нового времени: сам Джон Ди известен среди герметиков своими «Енохианскими квадратами». Как именно должны были использоваться квадраты Сойги, по-видимому, неясно; Сам Ди пытался спросить архангела Уриэля, хороша ли книга, но ему сказали, что она выше его допуска.
Следующим этапом истории является то, что квадраты Сойги были реконструированы Джимом Ридсом. Он нашел правило для их создания: ключевое слово используется для заполнения левого края (слово пишется сверху вниз, за которым следует само в обратном порядке, в правильном порядке, в обратном порядке и т. д. — в приведенном выше примере слово «нисрам »). Каждая ячейка зависит от ячейки слева и над собой: буква слева определяет, на сколько шагов вперед в алфавите нужно двигаться от буквы выше.
L (я, j) = [L(i-1,j)+f(L(i,j-1))] mod 23, если L(i,j) — это буква в строке i и столбце j. f() — явно произвольный список значений. Верхняя строка генерируется L(1,j)= [L(1,j-1)+f(L(1,j-1))] мод 23, взяв левую букву за верхнюю.
Нанесение результата в виде цвета, а не букв, дает следующий шаблон:
Автомат Сойги
Круто то, что это, по сути, одномерный клеточный автомат с 23 состояниями, в котором время идет слева направо. Динамика сильно хаотична (класс 3), что создает явно случайное распределение букв. Существует небольшое смещение из-за верхнего граничного условия: вдоль вершины есть два состояния аттрактора, одно состоит из повторений «дизб» и одно из повторений «ой». Аттрактор oy стремится создать треугольник из повторяющихся «oy». Но даже если ключевое слово просто «а», шаблон будет хаотичным (как показано на изображении вверху).
Использование такого рода правил обычно приводит к псевдослучайному поведению: почти любая таблица переходов f() будет работать. У некоторых есть треугольные срезы вдоль верхней части повторяющихся узоров, но большинство, кажется, приближается к равномерному распределению частоты букв.
То, что динамика в общем случае является случайной для автоматов со многими состояниями, хорошо известно.
Менее очевидно, что это также приведет к равномерному распределению состояний. Однако, если взглянуть на таблицу переходов T(i,j), обозначающую, какую букву можно получить, если буквы i и j находятся слева и сверху, единообразие становится более очевидным: каждая строка представляет собой круговой сдвиг алфавита, поэтому общее количество экземпляров каждой полученной буквы одинаково. Случайная матрица перехода давала бы одни буквы чаще, чем другие. По-прежнему существует проблема, заключающаяся в том, что в некоторых матрицах, подобных этой, могут быть подмножества букв, переставленные друг в друга (представьте себе такую, в которой четные буквы превращаются в четные, а нечетные — в нечетные), поэтому некоторые ключевые слова будут вызывать неравномерное распределение. Но, по-видимому, эргодичность является общей для этого класса автоматов.
Для чего это было хорошо?
Почему составитель придумал это правило? Ридс сравнивает ее с другими таблицами букв той же эпохи, и совершенно ясно, что Soyga действительно намного более продвинута, чем другие таблицы. Большинство из них имеют очень простые повторяющиеся или зигзагообразные узоры. Ратледж отмечает, что некоторые из таблиц Ди имели грубо случайные узоры, напоминающие человека, произвольно заполняющего их от руки. Большинство этих таблиц предназначались для магического использования: для изготовления талисманов или поиска священных имен для выполнения магических заклинаний ангелов. .
Однако мне интересно, была ли цель криптографической: средневековые и ранние современные шифры использовали таблицы исправления. Тритемий Стеганография упоминается у Сойги и сам по себе является очевидным трактатом о магии, который на самом деле содержит криптографические работы.
Сокрытие шифровального ключа в виде волшебной таблицы сегодня кажется довольно рациональным в качестве прикрытия, но, учитывая, насколько более чувствительной была тогда магия (из-за нее и Тритемиус, и Ди попали в беду), это немного похоже на использование нелегальной порнографии в качестве прикрытия. способ сокрытия ключей шифрования: не совсем осторожный метод, если кто-то подглядывает.
Soyga могла быть методом создания новых таблиц, которые были гораздо более случайными, чем таблица Trithemius. Он обеспечивает равномерное распределение букв практически без рисунка. Возьмите первые 23 строки и столбца в качестве прямой таблицы, и вы получите нечто гораздо более устойчивое к криптоанализу.
Но учитывая, что шифр Виженера считался невзламываемым, была ли необходимость в чем-то еще? Я подозреваю, что стремление изобретать новые методы шифрования всегда было сильным: если у вас есть крутая идея, основанная на вашей собственной области знаний, вы ее предложите (в конце концов, если ты его нельзя сломать, оно должно быть нерушимым!).
На самом деле использование преобразования предыдущего столбца похоже на шифр с автоключом. Первый настоящий шифр с автоключом был предложен Кардано в 1556 г. тонкости, но первый полезный он был изобретен в 1564 году Джован Баттиста Белласо. Виженер опубликовал один из них в 1586 году. Liber Soyga была упомянута Ди в 1583 году. Мог ли автомат Сойги быть результатом того, что кто-то работал над методом автоключа, возможно, ему пришла в голову блестящая идея применять его снова и снова к самому себе? Казалось бы, соответствует времени.
Конечно, граница между криптографией и ангельским общением могла быть размытой. Возможно, таблицы рассматривались как и то, и другое: достаточно продвинутая криптография неотличима от магии.
Размещенно от Anders3 17 апреля 2014 г., 12:06
