Криптономикон, часть 1 - Стивенсон Нил Таун. Страница 46
Что с цепью? Ее положение, определяемое как C, начинается с 0, достигает единицы, когда в фатальную позицию перемещается следующее звено, потом двойки и так далее. Цепь движется синхронно с зубцами звездочки в центре заднего колеса. У звездочки n зубцов, так что после второго полного оборота заднего колеса Q снова = 0, но C теперь = 2n. В следующий раз C = 3n и так далее. Однако не забывайте, что цепь — не бесконечная прямая линия, а замкнутая петля, имеющая всего l позиций; при C = l, она возвращается к началу цикла, и C снова принимает нулевое значение. Так что при вычислении C следует прибегнуть к арифметике остатков: то есть если в цепи сто звеньев (l = 100), а общее число перемещенных звеньев — 135, то значение C не 135, а 35. Как только вы получаете число, больше или равное l, вы просто последовательно вычитаете l, пока результат не станет меньше l. Математики обозначают эту операцию mod l. Так что последовательные значения C, всякий раз как заднее колесо возвращается в положение Q = 0, равны:
Ci = n mod l, 2n mod l, 3n mod l, …, in mod l
где i = (1, 2, 3, … 8 ?),
меньше или больше в зависимости от того, насколько близкое к бесконечности время Тьюринг намерен ехать на велосипеде. Через некоторое время Уотерхаузу начинает казаться, что они и впрямь едут бесконечно.
Цепь сваливается, когда велосипед достигает состояния (Q = 0, C = 0). В свете вышесказанного это происходит, когда l (которое просто означает число оборотов, совершенных задним колесом) достигает некоего гипотетического значения, при котором in mod l = 0, или, говоря по-человечески, когда некое число, кратное n (такое, как, например, 2n, 3n, 395n или 109 948 368 443n), оказывается в то же время кратным l. Вообще-то это может быть любое из так называемых общих кратных, но с практической точки зрения важно только первое — наименьшее общее кратное, или НОК, поскольку именно оно будет достигнуто первым и вызовет падение цепи.
Если, скажем, у звездочки двадцать зубцов (n = 20), а в цепи сто звеньев (l = 100), то после первого поворота колеса мы имеем C = 20, после двух поворотов C = 40, потом 60, 80 и 100. Однако поскольку мы ищем остаток от деления на 100, значение надо изменить на ноль. Таким образом, после пяти оборотов колеса мы достигли состояния (Q = 0, C = 0) и цепь Тьюринга сваливается. За пять оборотов колеса он проезжает всего десять метров, поэтому при таких значениях l и n велосипед практически бесполезен. Разумеется, все это верно лишь в том случае, если Тьюринг такой дурак, чтобы начать движение из состояния спадения цепи. Если же он начинает крутить педали, когда велосипед находится в состоянии (Q = 0, C = 1), то C принимает значения 21, 41, 61, 81, 1, 21, … и так до бесконечности, и цепь не свалится никогда. Однако это вырожденное состояние, где «вырожденное» для математика означает «невыносимо скучное». В теории, если Тьюринг будет всякий раз выставлять нужное состояние, прежде чем бросить велосипед на улице, никто не сможет его украсть — цепь свалится через первые же десять метров.
Если же в цепи Тьюринга сто одно звено (l = 101), то после пяти оборотов мы имеем C = 100, а после шести C = 19, тогда
C = 39, 59, 79, 99, 18, 38, 58, 78, 98, 17, 37, 57, 77, 97, 16, 36, 56, 76, 96, 15, 35, 55, 75, 95, 14, 34, 54, 74, 94, 13, 33, 53, 73, 93, 12, 32, 52, 72, 92, 11, 31, 51, 71, 91, 10, 30, 50, 70, 90, 9, 29, 49, 69, 89, 8, 28, 48, 68, 88, 7, 27, 47, 67, 87, 6, 26, 46, 66, 86, 5, 25, 45, 65, 85, 4, 24, 44, 64, 84, 3, 23, 43, 63, 83, 2, 22, 42, 62, 82, 1, 21, 41, 61, 81, 0.
Так что состояние (Q = 0, C = 0) не будет достигнуто и цепь не свалится, пока колесо не совершит сто один оборот. За сто один оборот велосипед Тьюринга успевает проехать по дороге пятую часть километра, что совсем не так плохо. Значит, велосипед работающий. Однако в отличие от вырожденного случая его нельзя привести в такое состояние, чтобы цепь не спадала совсем. Это легко доказать, просмотрев приведенный список значений C и убедившись, что все возможные значения — все числа от одного до ста — в нем присутствуют. Это означает, что с какого бы значения C Тьюринг ни начал крутить педали, рано или поздно он придет к фатальному C = 0 и цепь свалится.
Разница между вырожденным и невырожденным случаем заключена в свойствах использованных чисел. Комбинация (n = 20, l = 101) принципиально отличается от комбинации (n = 20, l = 100). Главная разница в том, что 20 и 101 — «взаимно простые», т. е. у них нет общих делителей. Это означает, что их наименьшее общее кратное, их НОК — большое число и равняется собственно l x n, т. е. 20 x 101 = 2020. А вот НОК ста и двадцати — всего 100. У велосипеда с l = 101 длинный период — он проходит через множество различных состояний, прежде чем вернуться к исходному, а у велосипеда с l = 100 — короткий, всего из нескольких состояний. Предположим, что велосипед Тьюринга — шифромашина, основанная на алфавитной замене, т. е. заменяет каждую из двадцати шести букв английского алфавита какой-то другой буквой. A открытого текста может стать T шифртекста, B — F, C — M и так дальше до Z. Сам по себе такой шифр до смешного прост, взломать его — детская забава. Однако предположим, что схема замены меняется от буквы к букве. Первая буква открытого текста шифруется с помощью одного алфавита замены, вторая — с помощью другого, третья — с помощью третьего и так далее. Это называется полиалфавитный шифр.
Предположим, что велосипед Тьюринга генерирует свой алфавит для каждого из состояний. Тогда состоянию (Q = 0, C = 0) будет соответствовать, например, такой алфавит замены:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Q G U W B I Y T F K V N D O H E P X L Z R C A S J M
а состоянию (Q = 180, C = 15) — такой:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B O R I X V G Y P F J M T C Q N H A Z U K L D S E W
Никакие две буквы не будут зашифрованы одним и тем же алфавитом замены, пока велосипед не вернется в исходное состояние (Q = 0, C = 0) и цикл не пойдет с начала. То есть это периодическая полиалфавитная система. Теперь, если период у машины короткий, она часто повторяет саму себя и в качестве шифровальной системы тоже годится исключительно для детской забавы. Чем длиннее период (чем больше взаимно простых чисел в него встроено), тем реже используется один и тот же алфавит замены и тем выше устойчивость шифра.
Трехдисковая «Энигма» — система именно такого типа (то есть периодическая полиалфавитная). Ее барабаны подобно приводу в велосипеде Тьюринга заключают в себе циклы в циклах. Ее период равен 17 576, то есть алфавит замены, которым зашифрована первая буква сообщения, не повторится до 17 577-й буквы. Однако в «Акуле» немцы добавили четвертый барабан, увеличив период до 456 976. В начале каждого сообщения диски ставятся в различные, случайным образом выбранные исходные положения. Поскольку ни в одном немецком сообщении нет 450 000 знаков, «Энигма» никогда не повторяет один и тот же алфавит замены в пределах отдельного сообщения. Вот почему немцы считают ее неуязвимой.
Над головами пролетает звено транспортных самолетов, направляясь, по всей видимости, к аэропорту в Бедфорде. Самолеты издают странно музыкальный диатонический гул, словно волынки, играющие две мелодии разом. Это напоминает Лоуренсу об еще одном феномене, связанном с велосипедным колесом и шифрмашиной «Энигма».
— Ты знаешь, почему самолеты так гудят? — спрашивает он.