Сегодня уже трудно представить себе, как люди жили когда-то без столь удобного и полезного инструмента, как локальные сети. Однако знало человечество и такие времена. Впервые идея связать несколько независимо работающих компьютеров в единую распределенную вычислительную систему посетила светлые головы инженеров еще в середине 60-х годов XX века. А если говорить более конкретно, то первый успешный эксперимент по передаче дискретных пакетов данных между двумя компьютерами провел в 1965 году молодой исследователь из лаборатории Линкольна Массачусетского технологического института Лари Роберте. Алгоритмы передачи данных, предложенные Робертсом, во многом послужили основой для построенной в 1969 году по инициативе американского «Агентства перспективных научных исследований» (Advanced Research Projects Agency, ARPA) глобальной вычислительной сети ARPANet, а она впоследствии, объединившись с несколькими другими существовавшими на тот момент сетями, стала фундаментом, на котором вырос современный Интернет. Однако и широко использовавшиеся в те времена многотерминальные системы, в которых пользователям предоставлялся доступ к одному головному многофункциональному компьютеру посредством нескольких конечных устройств удаленного подключения — терминалов — по принципу разделения процессорного времени, и глобальные сети, объединявшие между собой мейнфреймы крупных вычислительных центров и лабораторий, являлись лишь предтечей локальных сетей в их нынешнем понимании. Существенный толчок в направлении развития малых локальных сетей дало бурное развитие во второй половине 70-х годов настольных персональных компьютеров. И в авангарде этого процесса стояла фирма Xerox.

Персональные компьютеры Xerox Star были весьма и весьма популярны в начале 80-х годов, во-первых, благодаря сочетанию низкой стоимости и достаточно высокой производительности, во-вторых, потому, что работали они под управлением первой в мире операционной системы с оконным графическим интерфейсом, предоставлявшей пользователю возможность максимально комфортно взаимодействовать с ресурсами ЭВМ, и, наконец, по той простой причине, что разработчики предусмотрели возможность включения нескольких машин Xerox Star в единую сеть. Именно инженер-исследователь фирмы Xerox Роберт Меткалф впервые предложил стандарт организации малых локальных сетей Ethernet, который широко используется при проектировании подобных систем до сих пор. Тем не менее, несмотря на очевидные достоинства персональных компьютеров от Xerox, они были вскоре окончательно вытеснены с рынка изделиями корпорации IBM, впитавшими в себя все перспективные разработки и лучшие технические решения предшественников. Большие производственные мощности этой компании позволили снизить цены на персональные компьютеры до возможного минимума, и конкурировать с IBM PC стало практически невозможно. Количество локальных сетей росло в геометрической прогрессии, что вскоре привело к необходимости разработки четких стандартов архитектуры распределенных вычислительных систем. Действительно, одна из основных задач локальных сетей заключается не только в передаче данных и организации общего доступа к тем или иным периферийным устройствам, но также и в обеспечении совместной работы оборудования различных производителей. Это, естественно, означает необходимость унификации и стандартизации подходов к построению локальных сетей. Именно в 80-х годах окончательно сформировались основные стандарты распределенных вычислительных систем, такие как Ethernet, Token Ring, ArcNet, FDDI и некоторые другие. Все эти стандарты, а также многие смежные вопросы, связанные с теоретическими и практическими аспектами построения локальных сетей, мы подробно рассмотрим на страницах этой книги.

80-е годы можно назвать эпохой расцвета локальных сетей, поскольку как крупные, так и малые предприятия быстро оценили выгоды от использования этой перспективной технологии. Действительно, локальные сети позволяли осуществлять быстрый обмен данными между различными подразделениями и отделами фирмы, заметно уменьшив объем циркулирующей внутри предприятия бумажной документации. Это позволяло, во-первых, экономить на накладных расходах, а во-вторых, существенно повышало производительность труда. В сочетании с уже существовавшей тогда возможностью передавать данные на значительные расстояния по информационным каналам глобальной сети использование подобных технологий открывало широчайшие возможности не только для оптимизации бизнеса и расширения информационного пространства, но и для осуществления межкорпоративного взаимодействия.

С течением времени стандарты, позволявшие объединять компьютеры в локальные сети, постепенно оптимизировались, увеличивалась пропускная способность каналов связи, эволюционировало программное обеспечение, росла скорость передачи данных. Вскоре локальные сети стали использоваться не только для пересылки между несколькими компьютерами текста и различных документов, но также для передачи мультимедийной информации, такой как звук и изображение. Это открыло возможность организации внутри локальной сети систем видеоконференцсвязи, позволявших пользователям такой системы общаться в режиме реального времени «напрямую», физически находясь в различных помещениях, выполнять совместное редактирование текстов и таблиц, устраивать «виртуальные презентации». Уже сейчас системы компьютерной видеосвязи широко используются крупными коммерческими предприятиями, где служат для организации связи между различными отделами, в военных комплексах для быстрой передачи информации между несколькими абонентами и целыми подразделениями, а в последнее время — и в домашних «настольных» системах, в качестве средства организации досуга. Среди достоинств KB С можно упомянуть относительно низкую стоимость эксплуатации по сравнению с иными существующими на сегодняшний день системами коммуникаций, их многофункциональность, сравнительную легкость в использовании. В процессе работы абоненты видеоконференции в общем случае видят на экранах своих мониторов изображения собеседника и свое собственное, что необходимо для осуществления визуального контроля установленного соединения. Изображение динамически обновляется со скоростью от 0,5 кадра/с до 15-25 кадров/с в зависимости от скорости (пропускной способности) канала связи и загрузки канала данными. Участники для проведения переговоров используют миниатюрные видеокамеры и микрофоны с достаточно хорошими характеристиками. Речь для передачи по каналу связи оцифровывается. Основными достоинствами компьютерной видеосвязи являются возможности совместной работы с документами и интегрированной информацией (текст, графика, изображение, получаемое с видеокамер участников), а также дистанционный запуск программных приложений на компьютере собеседника. Изображения, получаемые с помощью видеокамер, могут передаваться не только в динамическом режиме (живое видео), но и в статическом. В последнем случае абонент выбирает необходимый кадр, захватывает и передает его по каналу связи в виде файла. В этом случае время передачи кадра не является критичным, и он может быть сформирован и передан со значительно более высоким качеством. Таким образом, участники подобного сеанса видеосвязи видят друг друга, могут разговаривать в дуплексном режиме, передавать цветные изображения графических документов и объектов, снимаемых видеокамерой, совместно редактировать документы, а также документировать процесс переговоров и результаты с помощью видеомагнитофонов и цветных принтеров. В итоге можно сделать вывод о том, что видеоконференцсвязь с успехом заменяет телефон, цветной факс и обеспечивает возможность записи сеанса или его части на видеомагнитофон для последующего анализа или демонстрации третьим лицам, не участвовавшим в сеансе видеосвязи.

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

Наконец, в начале 90-х годов XX века удешевление и расширение ассортимента конечного оборудования позволили локальным сетям выйти за пределы коммерческого сектора рынка. Появились небольшие домашние и частные локальные сети, объединявшие несколько компьютеров в одной семье или в пределах одного дома. В последнее время доля малых локальных сетей заметно выросла по отношению к общему количеству работающих в мире распределенных вычислительных систем, что, впрочем, не удивительно, поскольку такие локальные сети позволяют совместно использовать различные устройства, например принтеры, сканеры, цифровые камеры, а также организовывать подключение к Интернету через единственный канал связи, а значит — экономить на оборудовании и комплектующих. Не говоря уже о том, что практически все современные игры имеют возможность одновременного участия в игровом процессе нескольких пользователей, для чего опять же необходима локальная сеть. Таким образом, локальная сеть — это распределенная вычислительная система, позволяющая всем подключенным к ней компьютерам — узлам или рабочим станциям — обмениваться данными, а также совместно использовать различные аппаратные и программные ресурсы.

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

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

Соответствие потока данных тем или иным правилам теория информации описывает как наличие статистических автокорреляций или информационной избыточности в потоке. Такие данные всегда будут иметь больший объем, чем эквивалентные, но не соответствующие никаким правилам (например, упакованные), т. е. помехозащищенность достигается не бесплатно. Существование "бесплатных" средств повышения помехозащищенности каналов противоречит, ни много, ни мало, Второму Началу термодинамики (доказательство этого утверждения требует глубоких знаний в области теории информации и термодинамики, и поэтому здесь не приводится).

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

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

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

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

Трехкратное копирование, таким образом, позволяет восстанавливать данные, но имеет слишком уж высокую избыточность. Эти примеры, кроме простоты, любопытны -тем, что демонстрируют нам практически важную классификацию избыточных кодов: бывают коды, которые только обнаруживают ошибки, а бывают и такие, которые позволяют их восстанавливать. Далеко не всегда коды второго типа могут быть построены на основе кодов первого типа. Во многих случаях, например при передаче данных по сети, целесообразно запросить повтор испорченного пакета, поэтому коды, способные только обнаруживать ошибки, практически полезны и широко применяются.

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

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

Самая распространенная из таких более сложных схем — это CRC (Cyclic Redundancy Code, циклический избыточный код). При вычислении CRC разрядности N выбирают число R требуемой разрядности и вычисляют остаток от деления на R блока данных (рассматриваемого как единое двоичное число), сдвинутого влево на N битов. Двоичное число, образованное блоком данных и остатком, делится на R, и этот факт можно использовать для проверки целостности блока (но не для восстановления данных при ошибке!).

Способность контрольной суммы обнаруживать ошибки логичнее измерять не в количестве ошибочных битов, а в вероятности необнаружения ошибки. При использовании CRC будут проходить незамеченными лишь сочетания ошибок, удовлетворяющие весьма специальному условию, а именно такие, вектор ошибок (двоичное число, единичные биты которого соответствуют ошибочным битам принятого блока, а нулевые — правильно принятым) которых делится на R. При случайном распределении ошибок вероятность этого может быть грубо оценена как 1/R, поэтому увеличение разрядности контрольной суммы в сочетании с выбором простых R обеспечивает достаточно быстрый и дешевый способ проверки целостности даже довольно длинных блоков. 32- разрядный CRC обеспечивает практически полную гарантию того, что данные не были повреждены, а 8-разрядный — уверенность, достаточную для многих целей. Однако ни четность, ни CRC не могут нам ничем помочь при восстановлении поврежденных данных.

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

Рис. 1.9. Параллельная четность

Широко известный и применяемый код Хэмминга (Hamming code) находится в близком родстве с параллельной четностью. Его теоретическое обоснование несколько менее очевидно, чем у предыдущего алгоритма, но в реализации он, пожалуй, даже проще [Берлекэмп 1971]. Идея алгоритма состоит в том, чтобы снабдить блок данных несколькими битами четности, подсчитанными по различным совокупностям битов данных. При выполнении неравенства Хэмминга (1.1) сформированный таким образом код обеспечивает обнаружение и исправление одиночных ошибок либо гарантированное обнаружение (но не исправление!) двойных ошибок. Важно подчеркнуть гарантию обнаружения, в отличие от всего лишь высокой вероятности обнаружения при использовании CRC.

d + р+1<= 2р, (1.1)

где d — количество битов данных, р — разрядность контрольного кода.

Код, использующий d и р, при которых выражение (1.1) превращается в равенство, называют оптимальным кодом Хэмминга.

Часто оказывается целесообразно сочетать упаковку данных с их избыточным кодированием. Наиболее удачным примером такой целесообразности опять-таки являются тексты на естественных языках: статистический анализ такого текста показывает очень высокий, более чем двукратный, уровень избыточности. С одной стороны, это слишком "много для большинства практически применяемых способов цифровой передачи и кодирования данных, а с другой — правила формирования этой избыточности слишком сложны и плохо формализованы для использования в современных программно-аппаратных комплексах. Поэтому для длительного хранения или передачи по низкоскоростным линиям целесообразно упаковывать текстовые данные и снабжать их простыми средствами избыточности, например CRC.

Все известные форматы представления изображений (как неподвижных, так и движущихся) можно разделить на растровые и векторные.

В векторном формате изображение разделяется на примитивы -- прямые линии, многоугольники, окружности и сегменты окружностей, параметрические кривые, залитые определенным цветом или шаблоном, связные области, набранные определенным шрифтом отрывки текста и т. д. (рис. 1.5). Для пересекающихся примитивов задается порядок, в котором один из них перекрывает другой. Некоторые форматы, например, PostScript, позволяют задавать собственные примитивы, аналогично тому, как в языках программирования можно описывать подпрограммы. Такие форматы часто имеют переменные и условные операторы и представляют собой полнофункциональный (хотя и специализированный) язык программирования.

Рис. 1.5. Двухмерное векторное изображение

Каждый примитив описывается своими геометрическими координатами. Точность описания в разных форматах различна, нередко используются числа с плавающей точкой двойной точности или с фиксированной точкой и точностью до 16-го двоичного знака.

Координаты примитивов бывают как двух-, так и трехмерными. Для трехмерных изображений, естественно, набор примитивов расширяется, в него включаются и различные поверхности — сферы, эллипсоиды и их сегменты, параметрические многообразия и др. (рис. 1.6).

Рис. 1.6. Трехмерное векторное изображение

Двухмерные векторные форматы очень хороши для-представления чертежей, диаграмм, шрифтов (или, если угодно, отдельных букв шрифта) и отформатированных текстов. Такие изображения удобно редактировать — изображения и их отдельные элементы легко поддаются масштабированию и другим преобразованиям. Примеры двухмерных векторных форматов — PostScript, PDF (Portable Document Format, специализированное подмножество PostScript), WMF (Windows MetaFile), PCL (Printer Control Language, система команд принтеров, поддерживаемая большинством современных лазерных и струйных печатающих устройств). Примером векторного представления движущихся изображений является MacroMedia Flash. Трехмерные векторные форматы широко используются в системах автоматизированного проектирования и для генерации фотореалистичных изображений методами трассировки лучей и т. д.

Однако преобразование реальной сцены (например, полученной оцифровкой видеоизображения или сканированием фотографии) в векторный формат представляет собой сложную и, в общем случае, неразрешимую задачу. Программы-векторизаторы существуют, но потребляют очень много ресурсов, а качество изображения во многих случаях получается низким. Самое же главное — создание фотореалистичных (фотографических или имитирующих фотографию) изображений в векторном формате, хотя теоретически и, возможно, на практике требует большого числа очень сложных примитивов. Гораздо более практичным для этих целей оказался другой подход к оцифровке изображений, который использует большинство современных устройств визуализации: растровые дисплеи и многие печатающие устройства.

В растровом формате изображение разбивается на прямоугольную матрицу элементов, называемых пикселами (слегка искаженное PICture ELement — этемент картинки). Матрица называется растром. Для каждого пиксела определяется его яркость и, если изображение цветное, цвет. Если, как это часто бывает при оцифровке реальных сцен или преобразовании в растровый формат (растеризации) векторных изображений, в один пиксел попали несколько элементов, их яркость и цвет усредняются с учетом занимаемой площади. При оцифровке усреднение выполняется аналоговыми контурами аналого-цифрового преобразователя, при растеризации — алгоритмами анти-алиасинга.

Размер матрицы называется разрешением растрового изображения. Для печатающих устройств (и при растеризации изображений, предназначенных для таких устройств) обычно задается неполный размер матрицы, соответствующей всему печатному листу, а количество пикселов, приходящихся на вертикальный или горизонтальный отрезок длиной 1 дюйм; соответствующая единица так и называется — точки на дюйм (DPI, Dots Per Inch).

Для черно-белой печати обычно достаточно 300 или 600 DPI. Однако принтеры, в отличие от растровых терминалов, не умеют манипулировать яркостью отдельной точки, поэтому изменения яркости приходится имитировать, разбивая изображение на квадратные участки и регулируя яркость относительным количеством черных и белых (или цветных и белых при цветной печати) точек в этом участке. Для получения таким способом приемлемого качества фотореалистичных изображений 300 DPI заведомо недостаточно, и даже бытовым принтерам приходится использовать гораздо более высокие разрешения, вплоть до 2400 DPI.

Вторым параметром растрового изображения является разрядность одного пиксела, которую называют цветовой глубиной. Для черно-белых изображений достаточно одного бита на пиксел, для градаций яркости серого или цветовых составляющих изображения необходимо несколько битов (рис. 1.7). В цветных изображениях пиксел разбивается на три или четыре составляющие, соответствующие разным цветам спектра. В промежуточных данных, используемых при оцифровке и редактировании растровых изображений, цветовая глубина достигает 48 или 64 бит (16 бит на цветовую составляющую). Яркостный диапазон современных Мониторов, впрочем, позволяет ограничиться 8-ю битами, т. е. 256 градациями, на одну цветовую составляющую: большее количество градаций просто незаметно глазу.

Рис. 1.7. Растровое изображение

Наиболее широко используемые цветовые модели — это RGB (Red, Green, Blue — красный, зеленый, синий, соответствующие максимумам частотной характеристики светочувствительных пигментов человеческого глаза), CMY (Cyan, Magenta, Yellow — голубой, пурпурный, желтый, дополнительные к RGB) и CMYG — те же цвета, но с добавлением градаций серого. Цветовая модель RGB используется в цветных кинескопах и видеоадаптерах, CMYG — в цветной полиграфии.

В различных графических форматах используется разный способ хранения пикселов. Два основных подхода — хранить числа, соответствующие пикселам, одно за другим, или разбивать изображение на битовые плоскости -сначала хранятся младшие биты всех пикселов, потом — вторые и так далее. Обычно растровое изображение снабжается заголовком, в котором указано его разрешение, глубина пиксела и, нередко, используемая цветовая модель.

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

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

MIDI-файлы имеют малый объем и, при наличии аппаратного синтезатора, не требуют ресурсов центрального процессора для воспроизведения, поэтому их часто используют в качестве фонового озвучивания игровых программ и Web-страниц. К недостаткам этого формата следует отнести тот факт, что качество его воспроизведения определяется качеством синтезатора, которое у дешевых звуковых карт оставляет желать лучшего, и то, что далеко не всякий звук можно воспроизвести таким способом.

Задача преобразования реального звука в MIDI сродни задаче векторизации растрового изображения и другим задачам распознавания образов, и в общем виде не разрешима.

Оцифрованный звук, напротив, является результатом простого осуществления аналого-цифрового преобразования реального звука. Характеристиками такого звука являются частота дискретизации, разрешение АЦП и количество каналов — моно или стерео.

В современных локальных сетях используются различные технологии подключения, различное оборудование и различные среды передачи данных. Еще несколько лет назад практически единственным возможным вариантом было объединение компьютеров на основе медного сетевого кабеля с пропускной способностью не более 10 Мбит/с, позже появились сети, в которых в качестве среды передачи информации стали использовать оптическое волокно, активно развиваются беспроводные локальные сети, в которых информация передается посредством инфракрасного излучения или широкополосных радиосигналов. Эволюция сетевых технологий обусловлена, в первую очередь, совершенствованием самих компьютеров. Специалистами подсчитано, что мощность процессоров современных ПК удваивается каждые 18 месяцев, соответственно, растет и трафик, передаваемый по линиям компьютерных коммуникаций (трафиком называется общий суммарный поток информации через один сетевой компьютер). Вместе с тем наиболее узкое место в любой распределенной вычислительной системе — это устаревшее оборудование, поскольку уже довольно давно специалистами по компьютерным сетям было сформулировано простое правило: максимальная пропускная способность локальной сети равна максимальной пропускной способности ее самого медленного компонента. Из этого можно сделать вполне справедливый вывод, что эволюция сетевых стандартов во многом определяется ростом информационных потоков и производительности компьютеров, причем кривая роста производительности локальных сетей уже сейчас становится похожа на экспоненту: сети с пропускной способностью в 100 Мбит/с появились спустя 15 лет после возникновения 10-мегабитных сетей, сетевые системы с пропускной способностью в 1 Гбит/с были разработаны через 5 лет после 100-мегабитных сетей, первые проекты сетей со скоростью передачи данных в 10 Гбит/с родились спустя еще 2 года (рис. 1.1).

П роизводител ьность локальных сетей

10 Гбит/с

Рис. 1.1. Рост производительности локальных сетей

Тем не менее, несмотря на стремительное совершенствование сетевых технологий, они все же не поспевают за ростом вычислительной мощности современных персональных компьютеров. Для обоснования этого утверждения специалистами приводится два аргумента: во-первых, компьютеры, работающие в сети с вполне современной конфигурацией, обеспечивающей скорость передачи данных до 100 Мбит/с, принципиально способны обрабатывать намного большие потоки входящих и исходящих данных, во-вторых, современные приложения, такие как, например, Microsoft Office XP, способны полностью «утилизировать» эту пропускную способность под собственные потребности.

Разработчики программного обеспечения также стараются идти в ногу со временем. В офисных приложениях, программах обработки баз данных, прочих Intranet-приложениях в последнее время намечается устойчивая тенденция к обеспечению установки, деинсталляции, запуска и совместного использования программ в локальной сети, в них реализуется механизм хранения документов и баз данных на сетевых серверах, использования общих программных компонентов. В то же время с каждой новой версией прикладных программ растет и объем создаваемых этими программами файлов. А для пересылки и обработки таких документов требуется высокая скорость передачи данных.

Аналогичного курса стараются придерживаться и разработчики операционных систем. В частности, в ОС Microsoft Windows XP поддержка локальных сетей организована на небывало высоком уровне. Существует уверенность, что и в системных платформах последующих поколений будут совершенствоваться технологии приема и передачи управляемых мультимедийных потоков, поддержка видеоконференций, совместной работы с файлами. В частности, технология .NET демонстрирует нам очевидные перспективы дальнейшего сращивания локальных сетей с Интернетом. Основное предназначение Microsoft.NET — еще более тесная интеграция операционной системы с сетевыми технологиями и унификация применяемых для работы с сетью стандартов. Если раньше пользователь Интернета являлся просто «приемником» и «передатчиком» информации, то с появлением .NET он становится интегрированным участником сетевой среды. Прежде всего проект .NET ориентирован на электронную коммерцию и создание многофункциональных сетевых служб, а также на предоставление пользователю более широкого спектра возможностей в Интернете.

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

Научной основой всех методов упаковки является теория информации: данные, в которых имеются статистические автокорреляции, называются избыточными или имеющими низкую энтропию. Устранив эти автокорреляции, т. е. повысив энтропию, объем данных можно уменьшить без потери смысла, а зачастую и с возможностью однозначно восстановить исходные данные. Методы повышения энтропии, которые не позволяют по упакованному потоку восстановить исходный, называются необратимыми, приблизительными или сжимающими с потерями (losing compression). Соответственно, методы, которые позволяют это сделать, называются обратимыми, точными, или сжимающими без потерь (losless compression).

Один из первых методов упаковки был предложен задолго до разработки современной теории информации; в 1844 году Сэмюэл Морзе построил первую линию проволочного телеграфа. Система кодировки букв, известная как Азбука Морзе (табл. 1.4), использовала для представления различных букв алфавита посылки различной длины, при этом длина посылки зависела от частоты использования соответствующего символа в английском языке. Часто встречающиеся символы кодировались более короткими последовательностями.

Таблица 1.4. Русская азбука Морзе

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

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

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

Практически все методы криптографии сводятся к преобразованию данных в набор из конечного количества символов и осуществлению над этими символами двух основных операций: подстановки и перестановки. Подстановка состоит в замене одних символов на другие. Перестановка состоит в изменении порядка символов. В качестве символов при этом могут выступать различные элементы сообщения — так, при шифровании сообщений на естественных языках подстановке и перестановке могут подвергаться как отдельные буквы, так и слова или даже целые предложения (как, например, в аллегорических изложениях магических и священных текстов). В современных алгоритмах этим операциям чаще всего подвергаются блоки последовательных битов. Некоторые методики можно описать как осуществление операции подстановки над полным сообщением.

Подстановки и перестановки производятся по определенным правилам. При этом надежда возлагается "на то, что эти правила и/или используемые в них параметры известны только автору и получателю шифрованного сообщения и неизвестны посторонним лицам. В докомпьютерную эру старались засекретить обе составляющие процесса шифрования. Сейчас для шифрования, как правило, используют стандартные алгоритмы, секретность же сообщения достигается путем засекречивания используемого алгоритмом параметра, ключа (key).

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

К примеру, сообщение на естественном языке, зашифрованное подстановкой отдельных букв, уязвимо для частотного анализа: основываясь на том факте, что различные буквы встречаются в текстах с разной частотой, взломщик легко- и с весьма высокой достоверностью- может восстановить таблицу подстановки. Существуют и другие примеры неудачных алгоритмов, которые сохраняют в неприкосновенности те или иные присутствовавшие в сообщении автокорреляции — каждый такой параметр можно использовать как основу для восстановления текста сообщения или обнаружения ключа.

Устойчивость шифра к поиску автокорреляций в сообщении называется криптостойкостыо алгоритма. Даже при использовании удачных в этом смысле алгоритмов, если взломщик знает, что исходные (нешифрованные) данные удовлетворяют тому или иному требованию, например, содержат определенное слово или снабжены избыточным кодом, он может произвести полный перебор пространства ключей: перебирать все значения ключа, допускаемые алгоритмом, пока не будет получено удовлетворяющее требованию сообщение. При использовании ключей достаточно большой разрядности такая атака оказывается чрезмерно дорогой, однако прогресс вычислительной техники постоянно сдвигает границу "достаточности" все дальше и дальше. Так, сеть распределенных вычислений Bovine в 1998 году взломала сообщение, зашифрованное алгоритмом DES с 56-разрядным ключом за 56 часов работы [www.distributed.net]!

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

Важно подчеркнуть, впрочем, что количество двоичных разрядов ключа является лишь оценкой объема пространства ключей сверху, и во многих ситуациях эта оценка завышена. Некоторые алгоритмы в силу своей природы могут использовать только ключи, удовлетворяющие определенному условию — например, RSA использует простые Числа. Это резко сужает объем работы по перебору, поэтому для обеспечения сопоставимой криптостойко-сти разрядность ключа RSA должна быть намного больше, чем у алгоритмов, допускающих произвольные ключи.

Низкая криптостойкость может быть обусловлена не только алгоритмом шифрования, но и процедурой выбора ключа: если ключ может принимать любые двоичные значения заданной разрядности, но реально для его выбора используется страдающий неоднородностью генератор псевдослучайных чи-:ел, мы можем значительно сократить объем пространства, которое реально аолжен будет перебрать взломщик наших сообщений (вопросы генерации завномерно распределенных псевдослучайных чисел обсуждаются во втором гоме классической книги [Кнут 2000]). Еще хуже ситуация, когда в качестве ключа используются "легко запоминаемые" слова естественного языка: в этом случае реальный объем пространства ключей даже довольно большой разрядности может измеряться всего лишь несколькими тысячами различных значений.

Современные алгоритмы шифрования делятся на два основных класса: с секретным и с публичным ключом (кажущееся противоречие между термином "публичный ключ" и приведенными выше рассуждениями будет разъяснено далее).

Алгоритмы- с секретным ключом, в свою очередь, делятся на потоковые (stream) и блочные (block). Потоковые алгоритмы обычно используют подстановку символов без их перестановки. Повышение криптостойкости при этом достигается за счет того, что правила подстановки зависят не только от самого заменяемого символа, но и от его позиции в потоке.

Примером простейшего — и в то же время абсолютно не поддающегося взлому — потокового алгоритма является система Вернама или одноразовый блокнот (рис. 1.10). Система Вернама основана на ключе, размер которого равен размеру сообщения или превосходит его. При передаче двоичных данных подстановка осуществляется сложением по модулю 2 (операцией исключающего или) соответствующих битов ключа и сообщения.

Рис. 1.10. Система Вернама

Если ключ порожден надежным генератором случайных чисел (например, правильно настроенным оцифровщиком теплового шума), никакая информация об автокорреляциях в исходном тексте сообщения взломщику не поможет: перебирая полное пространство ключей, взломщик вынужден будет проверить все сообщения, совпадающие по количеству символов с исходным, в том числе и все сообщения, удовлетворяющие предполагаемому автокорреляционному соотношению.

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

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

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

В системах цифровой связи широкое применение получили блочные алгоритмы, выполняющие над блоками данных фиксированной длины последовательности -- иногда довольно сложные — перестановок, подстановок и других операций, чаще всего двоичных сложений данных с ключом по какому-либо модулю. В операциях используются компоненты ключевого слова относительно небольшой разрядности.

Например, широко применяемый блочный алгоритм DES шифрует 64-битные блоки данных 56-битным ключом. Полное описание алгоритма приводится в документе [NBS FIPS PUB 46, 1977]. Русский перевод этого документа может быть найден в приложениях к книге [Дейтел 1987]. Для современной вычислительной техники полный перебор 56-битного пространства — "семечки", поэтому сейчас,все большее распространение получают алгоритмы с большей разрядностью ключа — Blowfish, IDEAL и др. [Анин 2000].

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

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

Двухключевые схемы шифрования намного сложнее в разработке, чем схемы с секретным ключом: требуется найти преобразование, не поддающееся обращению при помощи применявшегося в нем публичного ключа, но такое, чтобы с применением приватного ключа его все-таки можно было обратить. Известные криптоустойчивые схемы основаны на произведениях простых чисел большой разрядности, дискретных логарифмах и эллиптических кривых. Наиболее широкое применение получил разработанный в 1977 г. алгоритм RSA [www.rsa.com FAQ].

Известные двухключевые алгоритмы требуют соответствия ключей весьма специфическим требованиям, поэтому для достижения криптостойкости, сопоставимой с блочными алгоритмами, необходимо использовать ключи намного большей разрядности. Так, снятые в 2000 году ограничения Министерства торговли США устанавливали ограничения разрядности ключа, который мог использоваться в экспортируемом за пределы США программном обеспечении: для схем с секретным ключом устанавливался предел, равный 48 битам, а для схем с открытым — 480.

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

Такая схема делает практичной частую смену секретных ключей: так, в протоколе SSH ключ генерируется на каждую сессию [www.cs.hut.fi SSH]; в протоколе виртуальных приватных сетей IPSEC время жизни ключа ограничено восемью часами [redbooks.ibm.com sg245234.pdf].

Еще более широкое применение двухключевые схемы нашли в области аутентификации и электронной подписи. Электронная подпись представляет собой контрольную сумму сообщения, зашифрованную приватным ключом отправителя. Каждый обладатель соответствующего публичного ключа может проверить аутентичность подписи и целостность сообщения. Это может использоваться для проверки аутентичности как сообщения, так и самого отправителя. Использование в качестве контрольной суммы обычного CRC (см. разд. Контрольные суммы) невозможно, потому что генерация сообщения с заданным CRC не представляет вычислительной сложности. Для применения в электронной подписи были разработаны специальные алгоритмы вычисления контрольных сумм, затрудняющие подбор сообщения с требуемой суммой [RFC 1320, RFC 1321].