Мыслящие существа способны проявлять очень сложные формы поведения, обладая сознанием, механизмы которого мы понимаем очень смутно. Подумайте, например, как вы планируете маршрут поездки по городу, чтобы выполнить массу дел. В плохо освещенном помещении вам удается распознавать границы предметов и избегать столкновений. Вы можете сосредоточиться на беседе с одним собеседником на шумной вечеринке, где много людей говорит одновременно. Ни одна из этих задач не имеет четкого алгоритмического решения. Планирование маршрута относится к классу NP-полных задач. Передвижение в темноте подразумевает принятие решения на основе неполной и нечеткой зрительной информации. Выделение речи одного человека из множества разговоров требует умения улавливать полезную информацию в шуме и отфильтровать нужные сообщения из общей какофонии.
Эти и подобные им проблемы привлекают внимание исследователей в области искусственного интеллекта, которые стремятся улучшить наши представления о разуме человека. В частности, создаются интеллектуальные системы, которые подражают некоторым аспектам поведения человека. Ерман, Ларк и Хайес-Рот указывали, что 'интеллектуальные системы отличаются от традиционных рядом признаков (не все из них обяэательны):
• способностью достигать целей, меняющихся во времени;
• способностью усваивать, использовать и преобразовывать знания;
• способностью оперировать с разнообразными подсистемами, варьируя используемые методы;
• интеллектуальным взаимодействием с пользователями и другими системами;
• самостоятельным распределением ресурсов и концентрацией внимания' [1].
Реализация в системе хотя бы одного из этих требований уже является непростой задачей. Еще сложнее сделать интеллектуальную систему для использования в некоторых специфических прикладных областях, например, в медицинской диагностике и диспетчеризации авиарейсов: такие системы должны, как минимум, не причинять вреда, а искусственный интеллект практически ничего не знает о здравом смысле.
Успехи энтузиастов в этой области несколько преувеличены; но, тем не менее, искусственный интеллект дал немало хороших практических идей, в частности представление знаний, концепция информационной доски и экспертные системы [2]. В данной главе рассматриваются подходы к созданию интеллектуальной системы расшифровки криптограмм на основе метода информационной доски, в достаточной степени моделирующего человеческий способ решения задачи. Как мы увидим, методы объектно-ориентированного проектирования очень хорошо работают в этой области.
11.1. Анализ
Определение границ предметной области
Как сказано во врезке, мы намерены заняться криптоанализом - процессом преобразования зашифрованного текста в обычный. В общем случае процесс дешифровки является чрезвычайно сложным и не поддается даже самым мощным научным методам. Существует, например, стандарт шифрования DES (Data Encryption Standard, алгоритм шифрования с закрытым ключом, в котором используются многочисленные подстановки и перестановки), который, по-видимому, свободен от слабых мест и устойчив ко всем известным методам взлома. Но наша задача значительно проще, поскольку мы ограничимся шифрами с одной подстановкой.
В качестве первого шага анализа попробуйте решить (только честно, не заглядывая вперед!) следующую криптограмму записывая, каждый ваш шаг:
Q AZWS DSSC KAS DXZNN DASNN
Подсказка: буква w соответствует букве v исходного текста. Перебор всех возможных вариантов совершенно лишен смысла. Предполагая, что алфавит содержит 26 прописных английских букв, получим 26! (около 4.03х1026) возможных комбинаций. Следовательно, нужно искать другой метод решения, например, использовать знания о структуре слов и предложений и делать правдоподобные допущения. Как только мы исчерпаем явные решения, мы сделаем наиболее вероятное предположение и будем продвигаться дальше. Если обнаружится, что предположение приводит к противоречию или заводит в тупик, мы вернемся назад и сделаем другую попытку.
Требования к системе криптоанализа
Криптография 'изучает методы сокрытия данных от посторонних' [3]. Криптографические алгоритмы преобразовывают сообщения (исходный текст) в зашифрованный текст (криптограмму) и наоборот.
Одним из наиболее общеупотребительных (еще со времен Древнего Рима) криптографических алгоритмов является подстановка. Каждая буква в алфавите исходного текста заменяется другой буквой. Например, можно циклически сдвинуть все буквы алфавита: буква A заменяется на B, B на C, a Z на A. Тогда следующий исходный текст:
CLOS is an object-oriented programming language
превращается в криптограмму:
DMPT jt bo pckfdu-psjfoufe qsphsbnnjoh mbohvbhf
Чаще всего замена делается менее тривиальным образом. Например, A заменяется на G, B на J и т.д. Рассмотрим следующую криптограмму:
PDG TBCER CQ TCK AL S NGELCH QZBBR SBAJG
Подсказка: буква C в этой криптограмме соответствует букве O исходного текста.
Существенно упрощает задачу предположение о том, что для шифрования текста использован алгоритм подстановки, поскольку в общем случае процесс дешифровки не будет столь тривиальным. В процессе расшифровки приходится использовать метод проб и ошибок, когда мы делаем предположение о замене и рассматриваем его следствия. Удобно, например, начать расшифровку с предположения о том, что одно- и двухбуквенные слова в криптограмме соответствуют наиболее употребительным словам английского языка (I, a, or, it, in, of, on). Подставляя эти предполагаемые буквы в другие слова, мы можем догадаться о вероятном значении других букв. Например, если трехбуквенное слово начинается с литеры O, то это могут быть слова one, our, off.
Знание фонетики и грамматики также может способствовать дешифровке. Например, следование подряд двух одинаковых литер с очень малой вероятностью может означать qq. Наличие в окончании слова буквы g позволяет сделать предположение о наличии суффикса ing. На еще более высоком уровне абстракции логично предположить, что словосочетание it is более вероятно, чем if is. Необходимо учитывать и структуру предложения: существительные и глаголы. Если выясняется, что в предложении есть глагол, но нет существительного, которое с ним связано, то нужно отвергнуть сделанные ранее предположения н начать поиск заново.
Иногда приходится возвращаться назад, если сделанное предположение вступает в противоречие с другими предположениями. Например, мы допустили, что некоторое двухбуквенное слово соответствует сочетанию or, что в дальнейшем привело к противоречию. В этом случае мы должны вернуться назад и попытаться использовать другой вариант расшифровки этого слова, например, on.
Требования к нашей системе: по данной криптограмме, в предположении, что использована простая подстановка, найти эту подстановку и (главное) восстановить исходный текст.
