Отображение схем из обратимых элементов на множество натуральных чисел

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 00:08, 19 декабря 2017.
Open book.svg Авторство
Р. С. Чистяков
Согласовано: 19 декабря 2017 года

Введение

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

В качестве альтернативного способа задания подстановки можно обратиться к схемам из обратимых элементов. Классическими обратимыми элементами являются инвертор (), элемент Фейнмана () [Источник 2], элемент Тоффоли ()[Источник 3]. В работах [Источник 4], [Источник 5] показано, что, используя базис из этих элементов, можно реализовать любую булеву подстановку. При этом, если такую схему зеркально отобразить, полученная схема будет реализовывать обратную подстановку. Таким образом, любая схема определяет одновременно прямую и обратную подстановки.

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

Общие сведения

Пусть — количество линий, на которых строится схема. Тогда число различных доступных для использования элементов определяется формулой

Выпишем все доступные элементы в некотором зафиксированном порядке. Таким образом, каждому элементу соответствует некоторое число – его номер, не превышающее . На рисунках 1 и 2 представлены пронумерованные обратимые элементы для случаев 3 и 4 линий. Принцип нумерации будет описан позднее.

Рисунок 1 — Нумерация элементов на трёх линиях
Рисунок 2 — Нумерация элементов на четырёх линиях

Принцип кодирования

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

Кодирование элементов

Предлагаемый способ кодирования элементов является однозначным (каждому числу соответствует ровно одна схема, и каждой схеме соответствует единственное число), однако не позволяет кодировать схемы, имеющие на конце элемент с номером 0 (при записи числа , соответствующего схеме, в -ичной системе счисления на первом месте не может находиться 0). Такое ограничение можно считать допустимым, поскольку этот элемент – инвертор нулевой линии, применение которого на выходе схемы не несёт практической криптографической ценности.

Разобьём все элементы на две группы – элементы и (суммарно их ровно , так что они будут иметь номера ) и элементы (будут иметь номера ).

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

которое и будет его номером. Пример кодирования номеров элементов из первой группы приведён на рисунке 3.

Рисунок 3 — Кодирование элементов первой группы

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

где – сдвиг относительно первой группы.

Рисунок 4 — Сравнение "рисунков" входов в подгруппах

Код относительного положения входов для конкретного элемента определяется по формуле

где – линия относительного положения «верхнего» входа, – расстояние между входами. На рисунке 5 приведён пример кодирования номеров элементов из второй группы.

Рисунок 5 — Кодирование элементов второй группы

Кодирование схемы

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

Декодирование схемы

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

Теперь необходимо интерпретировать полученные числа – определить элементы, которым они соответствуют. Здесь применяются различные подходы для чисел, меньших (первая группа элементов) и чисел .

Числа из первой группы раскладываем по модулю , получаем:

где — номер линии, содержащей вход данного элемента, – номер линии, содержащей его выход. Если они совпадают, то это элемент , расположенный на линии с номером , иначе – элемент .

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

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

Другой способ – итеративный. Вначале полагаем , далее, на каждом шаге к прибавляем 1, из вычитаем , где – номер шага. Алгоритм останавливается, когда выполняется условие:

Полученное – относительное положение входа, находящегося на линии с меньшим номером (будем называть его «верхним» входом), – расстояние (количество линий) между входами.

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


где и – номера линий, содержащих входы элемента.

Пример

Пусть схема на 4 линиях закодирована числом , тогда

Имеем

То есть схема состоит из 7 элементов с номерами: . Рассмотрим элементы из первой группы – те, номера которых меньше . Разложим их по модулю :



На данный момент имеем:

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


Таким образом, мы получили набор элементов: . Приведя к в виду, где первое число означает номер выхода, а остальные – номера входов, получаем: . Это схема, изображённая на рисунке 6.

Рисунок 6 — Полученная в примере схема

Источники

  1. Wu CK., Varadharajan V. Public Key Cryptosystems Based on Boolean Permutations and Their Applications. International Journal of Computer Mathematics, vol.74, 2000, pp. 167-184.
  2. Feynman R.P. Quantum Mechanical Computers. Optics News, Vol. 11(2), 1985, pp. 11-20.
  3. Toffoli T. Reversible Computing. Automata, Languages and Programming (Series: Lecture Notes in Computer Science). Springer Berlin Heidelberg, Vol. 85, 1980, pp. 632-644.
  4. Shende V.V., Prasad A.K., Markov I. L. and Hayes J.P. Synthesis of Reversible Logic Circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.22(6), 2003, pp. 710-722.
  5. Закаблуков Д.В., Жуков А.Е. Исследование схем из обратимых логических элементов. Информатика и системы управления в XXI веке: Сборник трудов №9 молодых ученых, аспирантов и студентов. – М.: МГТУ им. Н.Э. Баумана, 2012, С. 148-157.