Криптография и другие вычисления на детских логических машинах

Электрическая игрушка «Детская логическая машина» (ДЛМ) представляет собой устройство, позволяющее решать несложные логические задачи про приведённым в настоящей инструкции рисункам и описаниям программ.

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

На коробке предупреждение, что игрушка только для детей 13-15 лет. Читайте статью с осторожностью, если не попадаете в указанный диапазон.

Пользоваться игрушкой предполагалось так. Сначала прочитать инструкцию:

Потом «запрограммировать» машину:

А потом играть:

В инструкции есть примерно десяток игр (даже викторина с карточками). Но что если ребёнок захотел придумать свою собственную? На этот счёт в руководстве никаких пояснений нет. Значит, нам придётся разобраться с машиной самостоятельно.

Реверс-инжиниринг

Внутреннее устройство ДЛМ в инструкции не приводится, есть только такая картинка:

К слову сказать, на Западе существовала похожая машина (чисто механическая), вот там было всё видно, потому что не было закрытого корпуса. А чтобы понять, как работает ДЛМ, пришлось заглянуть к ней «под капот». Оказалось, что она одновременно «вычисляет» 7 выражений вида А’&Б’&В’, для каждого из «столбцов программирования», где A’ — это или 0, или 1, или A, или not A, в зависимости от установленных штырьков. Выбрать значения входов АБВ можно сразу для всех столбцов с помощью тумблеров справа.

Когда установлены 1 или 0 для входных сигналов АБВ, штырьки толкают пружинку внутри машины, соединяя цепи столбцов. Если установлены оба штырька, пружинка будет проводить ток в любом случае. Если установлен только левый штырёк, то цепь замкнётся при выборе 1 для соответствующего входа (эквивалентно тому, что в выражении используется прямое значение операнда), а если левый — то цепь замкнётся при выборе 0 (операнд инвертирован).

Выходы этих 7 «вычислителей» можно подключать к 4 лампочкам, объединяя цепи с помощью «монтажного или».

Машина, как аналог микросхем серии 7400

Посмотрим, как ДЛМ можно использовать для конструирования логических цепей. Попробуем повторить классический набор микросхем 7400. Правда входов у машины всего три, поэтому прямых аналогов не получится. Но довольно легко сконструировать такие логические элементы, как НЕ, И-НЕ, ИЛИ-НЕ.

Самое простое это конечно же инвертор (операция НЕ). Каждый из входов А, Б, В влияет только на один выход, чтобы получилось что-то вроде O=!А & 1 & 1. Единицы здесь означают, что Б и В не участвуют в вычислениях, что достигается установкой двух штырьков на пересечении входных линий Б и В и выходной линии 1.

Чтобы получился элемент И-НЕ, нужно перемножить входные сигналы с помощью И, а затем их инвертировать. Так как выходной сигнал машина инвертировать не умеет, то можно взять ещё одну машину, пусть она инвертирует. Но гораздо лучше преобразовать функцию, которую нужно выполнить: !(A & Б & В) = !А | !Б | !В. Тогда три столбца одной машины мы используем для отрицания, а присоединяем выходы с них к одной лампочке.

С ИЛИ-НЕ получается такая же ситуация. !(А | Б | В) = !А & !Б & !В. Это выражение можно вычислить, задействовав только один столбец.

Самое сложное — это операция исключающее или (XOR). XOR складывает (без учёта переполнения) входные биты, а результат в итоге будет «истиной», если на входе нечётное число единиц.

А^Б^В = А&Б&В | !А&!Б&В | !А&Б&!В | А&!Б&!В

Подвыражения считаются с помощью четырёх столбцов и выводятся на одну лампочку.

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

RS-триггер

Простейшие триггеры умеют хранить один бит информации. RS-триггер работает асинхронно и управляется двумя входами. Один записывает единицу, другой записывает ноль.

Q1 = !(А | Q2) = !А & !Q2

Q2 = !(Б | Q1) = !Б & !Q1

Тут без двух машин не обойтись. Ведь инвертировать выходной сигнал мы не можем (транзисторов и реле в машине нет). Поэтому придётся передавать выходной сигнал с одной машины на другую. Одна машина будет вычислять Q1 (прямой выход), а вторая — Q2 (инвертированный). Коммутировать их придётся с помощью оператора, который посмотрит на лампочку и переключит тумблер (хотя подошёл бы и моторчик с пружинкой). Это даже хорошо, что выход и вход следующей машины не связаны электрически, в релейных компьютерах для этого используются или дополнительные реле, или диоды, чтобы ток не протекал от выходов одной цепи, к выходам другой.

Сумматор

Однобитный полный сумматор — это схема, которая складывает три бита. Почему три? Два — это биты числа, а третий — перенос от сложения более младших битов. Значит результат может принимать значения от 0 до 3. Закодировать его можно двумя битами — битом суммы и битом переноса.

Если взять несколько однобитных сумматоров, можно складывать числа соответствующей разрядности.

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

Осталось придумать формулу для бита переноса. Он не возникает, только если все операнды равны нулю, либо только один из них равен единице. Иначе говоря, бит переноса устанавливается, когда хотя бы два входных бита равны единице. То есть C = А&Б | А&В | Б&В. Для вычисления этого выражения нужно запрограммировать всего три столбца машины.

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

АЛУ

Арифметико-логические устройства микропроцессоров обычно кроме сложения, умеют ещё выполнять побитовые операции отрицания, «и», «или», «исключающего или» с двумя операндами. Ну кроме отрицания, оно работает с одним операндом.

Все эти действия может выполнять одновременно одна машина. Для однобитных операндов. То есть для восьмибитных чисел машин понадобится восемь. Итого, полноценное восьмибитное АЛУ можно сделать всего из шестнадцати ДЛМ — восемь для сложения и восемь для остальных действий.

CRC1

Перейдём к криптографическим алгоритмам. CRC (cyclic redundancy check) используется для контроля за ошибками в каналах связи. Для этого к сообщению добавляются несколько хитро посчитанных битов, которые позволяют определить, изменилось ли сообщение в процессе передачи. Чем больше битов, тем большее количество ошибок можно обнаружить. А иногда и исправить.

Мы будем считать простейший вариант — CRC1. Он же — бит чётности. С помощью CRC1 можно определить, что в сообщении изменилось некоторое нечётное число битов. Если же поменялось чётное число битов, то ошибка обнаружена не будет.

Бит чётности используется, например, при последовательной передаче данных (RS-232, COM-порт, вот это вот всё). Поэтому многие микропроцессоры содержат встроенные возможности для его вычисления. Например, в процессорах семейства x86 есть отдельный флаг, который устанавливается, если в результате вычислений получилось чётное число ненулевых битов.

Чтобы посчитать CRC1, можно выполнить операцию XOR над всеми входными битами. Так как у логической машины только три входа, каждая их них может посчитать XOR для трёх битов: X = А ^ Б ^ В.

Чтобы вычислить CRC для более длинного сообщения, придётся составить целый каскад из ДЛМ (хорошо, что XOR — ассоциативная операция). Таким образом, для сообщения длиной N, CRC1 можно посчитать, имея всего N/2 машин:

Если же вычислять результат последовательно, поручая каждой следующей машине объединить промежуточный итог и два очередных бита сообщения, то машин всё равно понадобится примерно N/2. Мистика.

Ксорка

Простейшее шифрование с помощью XOR работает так: <выходное сообщение>=<входное сообщение> XOR <ключ>. Чтобы расшифровать сообщение обратно, нужно сделать то же самое. Ведь A XOR B XOR B = A.

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

Можно ли запустить на ней Doom?

Чтобы запустить Doom, проще всего построить какой-нибудь компьютер, на котором эта игра уже работает.

ДЛМ выпускалась с 1984 года. Мой экземпляр выпуска 1987 года имеет заводской номер 9924. Следовательно, за три года было выпущено примерно 10 тысяч машин. Вторая моя машина сделана в 1989 году. А ещё раньше, минимум с середины 70х, выпускалась похожая Детская вычислительная машина. Наверное, общее их число можно оценить примерно в 100000.

Каждая машина заменяет штук 30 транзисторов, поэтому если собрать их все, можно построить «процессор» из трёх миллионов транзисторов. Из этого получится довольно «мощный» процессор (в Z80 транзисторов было всего 8500).

А вот как для запуска Doom сделать ОЗУ, дисплей, и где взять столько операторов для переключения тумблеров, вы узнаете в следующей статье (но это не точно).