Computers & Security, vol.7, N1, 1988, с.83-87. А. Саломаа.
Криптосистемы с открытым ключом на базе теории формальных языков.
Описывается новая криптосистема с открытым ключом на базе теории
формальных языков: повторяющихся морфизмов и подстановок. Система
оценивается с различных точек зрения. Ключевые слова:
Криптосистемы, Открытые ключи. 1. Введение. В последние годы
значительно возросли исследования в криптографии, и тому две
главных причины. Во-первых, это плодотворная концепция открытых
ключей, интересная сама по себе и нашедшая применение в ряде
новых приложений. Во-вторых, возросшие требования по защите
данных. Если раньше криптография применялась в "негативных" целях
(связь во время военных действий, преступные действия и др.), то
сейчас возникает много "положительных" аспектов ег применения.
Очевидно, что диапазон применений будет возрастать с развитием
электронной почты и подобных систем. При этом очень важно, чтобы
доступ к информационной системе имели только законные лица. С
этой целью используются два разных метода: контроль за доступом и
шифрование данных. В последнем случае доступ ограничивается при
помощи секретных паролей. Контроль за доступом имеет существенные
недостатки: он слабо защищгн от действий квалифицированных
злоумышленников, возникает проблема физической защиты внешних
носителей информации, что непрактично в больших инф. системах.
Шифрование данных, с другой стороны, имеет ряд преимуществ. Цель
статьи - обсудить специфическую криптосистему, предложенную в [3]
и исследованную в [2] и [4]. [Рассматривается традиционная модель
передачи сообщения по каналу, подверженному перехвату (шифрование
симметричным ключом). Переход к концепции открытых ключей.]
Рассмотрим более подробно криптосистемы с открытым ключом: 1)
начинают с трудной проблемы Р; 2) выбирают лггкую подпроблему Р1;
3) "перетасовывают" Р1 таким образом, что полученная проблема Р2
очень "похожа" на проблему Р. Используют Р2 в качестве открытого
ключа шифрования; 4) получение Р1 из Р2 является секретной
лазейкой; 5) законный пользователь системы способен дешифровать,
решая лггкую проблему Р1. Для остальных - решение Р2 равносильно
решению трудной проблемы Р. В системах ранцевого типа или RSA
проблема Р относится к теории чисел, а в описанной ниже системе -
к теории формальных языков. Дадим основные определения для
понимания этой системы. Имеется конечное множество (алфавит),
элементами которого являются буквы. Конечные цепочки букв
называются словами. По техническим причинам рассматривается также
пустое слово , не имеющее букв. Множество всех слов по
обозначается *. Подмножества * (конечные или бесконечные) - это
языки. В принципе, язык состоит скорее из предложений, но можно
ввести знаки пунктуации и пробела, тогда предложение будет словом
(в нашем понимании). Морфизм - это отображение h: * -- *,
удовлетворяющее уравнению h(w w )= h(w )h(w ) для всех слов w и w
. (Математически подготовленный читатель заметит, что морфизм -
это гомоморфизм свободного моноида, генерируемого ). Видно, что
морфизм h полностью определяется значениями h(a), где a пробегает
по всем букувам . Например, если ={a, b, c} и h(a)= aba, h(b)= и
h(c)= cab, то h(abc)= abacab и h(baab)= abaaba. Конечная
подстановка похожа на морфизм, но в этом случае несколько слов
(конечно много) могут быть приписаны каждой букве. Следовательно,
слово отображается в несколько слов. Например, если (a)={ab, abb}
и (b)={ba, baa}, то (ab)={abba, abbaa, abbba, abbbaa}. Более
подробную информацию о теории формальных языков и криптосистемах
с открытыми ключами можно найти в [2]. Система, описанная ниже,
основана на части теории формальных языков - L-системах. 2.
Описание криптосистемы. Пусть - алфавит. Рассмотрим два морфизма
h и h : * -- * и непустое слово w в *. Мы говорим, что четвгрка
G=( , h , h , w) обратно детерминирована, если условие (w)i i
...i = (w)j j ...j , для i и j в {h , h } (1) всегда
подразумевает условие i i ...i = j j ...j . (2) Иными словами,
(1) показывает, что два слова над в разных частях уравнения
равны, тогда как (2) показывает, что m=n и два слова над
алфавитом (h ,h ) в разных частях уравнения равны. В терминах
L-систем четвгрка G=( ,h ,h ,w) является DTOL-системой. Условие
обратной детерминированности означает, что конечный результат
всегда однозначно определяет последовательность используемых
таблиц (подстановок). Очевидный путь для получения обратной
детерминированности - включение в специальной буквы t ("индикатор
табуляции") с порождениями t - t0, 0 - 0, 1 - 1, в h , t - t1, 0
- 0, 1 - 1, в h . Обратно детерминированные DTOL-системы G могут
использоваться как классические криптосистемы: последовательность
битов i i ...i шифруется как слово над (w)h h ...h . Затем G
сохраняется в тайне. В противном случае нет разницы между
(законным) дешифрованием и (незаконным) криптоанализом.
Посмотрим, как такая классическая криптосистема может быть
преобразована в систему с открытым ключом. Интуитивно, это
означает, что DTOL-система G "скрыта" в TOL-системе H с более
мощным алфавитом. Законный получатель может получить расшифровку,
используя секретную лазейку для восстановления G из H.
Криптоаналитик должен прповодить сложный грамматический разбор
относительно H. Иными словами, пусть будет алфавитом гораздо
большей мощности, чем . Обычно состоит из 5 букв, а из 200. Пусть
g: * - * будет морфизмом, который отображает каждую букву в букву
или пустое слово таким образом, что g (a) - непустое для всех
букв a из . Определим две конечные подстановки и на *. При этом
(d) - это конечное непустое подмножество g (h (g(d))) для всех d
в , i=0,1. Интуитивно, морфизм g разделяет буквы на потомки букв
и холостые символы, которые отображаются в пустое слово .
Окончательно выбираем слово u из g (w). Четвгрка Н=( , , ,u)
образует открытый ключ шифрования. Шифрование последовательности
i i ...i битов происходит путгм выбора произвольного слова из
(конечного) множества (u) (3) секретная лазейка состоит из
элементов , h ,h , w и g. Фактически g - это важнейший элемент,
так как другие элементы можно получить из g и открытого ключа. Из
определений следует, что если является словом из множества (3),
то g( )=(w)h h ...h . Таким образом, знание секретной лазейки
сводит дешифрование к простой задаче грамматического разбора
DTOL-системы G. В терминах L-систем H - это TOL-система. Перед
шифрованием открытый текст разбивается на блоки. Блоки могут быть
разной длины, но не очень большими, иначе шифртекст будет слишком
длинным по сравнению с открытым. Обычно блоки шифртекста
разделяются граничной меткой #. Системы G и H могут иметь не два
морфизма и подстановки, а больше. Например, если шифруется
открытый текст десятичных знаков, используется 10 морфизмов и
подстановок. Пример. DTOL-система G определена через w=ab и два
морфизма h : a - ab, b - b h : a - a, b - ba. Присутствует
обратная детерминированность, так как последний морфизм является
h в случае, когда просматриваемое слово заканчивается b. (Также
верно и то, что последний морфизм - это h , если просматриваемое
слово имеет подслово b ). Определим ={c ,c ,c ,c ,c } и g как g(c
)=g(c )=a, g(c )=b, g(c )=g(c )= . Выберем u=c c c и определим
две подстановки и как Мы закончили определение открытого ключа
шифрования H=( , , ,u). 3. Обсуждение: свойства криптосистемы По
существу мы имеем дело с лггкой задачей грамматического разбора
системы G, противопоставленной сложной задаче грамматического
разбора H-систем. Преимущество обсуждаемой криптосистемы в
сложности отыскания ключа дешифрования из ключа шифрования, так
как нельзя распознать "кандидата", котрый действительно являлся
бы ключом дешифрования. Подход криптоаналитика следующий.
"Мусорные" (junk) буквы могут создать только мусорные буквы
(тогда как немусорные буквы создают оба типа букв). Таким
образом, формируя "транзитивные замыкания" аналитик может
получить всех возможных кандидатов для множества мусорных букв.
После этого легче получить лежащие в основе морфизмы, так как
принимаются во внимание только реальные потомки. Предположим, что
аналитик способен найти DTOL-систему G', такую, что известная
TOL-система получаемва из G' по правилам, определгнным в разделе
2. Конечно криптоаналитик не знает, является ли G' первоначальной
DTOL-системой G'', использованной создателем криптосистемы.
Однако можно пролучить следующий результат. Пусть имеются
описанные выше G' и G''. Если G' "обратно детерминирована"
(недвусмысленная) (раздел 3), то она приводит к тем же
результатам дешифрования, что и G'. Напротив, если она не
является обратно детерминированной, то возможно большое число
рашифровок, особенно если открытый текст разделгн на много
блоков.
