Logo    
Деловая газета CitCity.ru CITKIT.ru - все об Open Source Форумы Все публикации Учебный центр Курилка
CitForum    CITForum на CD    Подписка на новости портала Море(!) аналитической информации! :: CITFORUM.RU
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

23.05.2017

Google
WWW CITForum.ru
С Новым годом!
2004 г.

Математика криптологии

В. Масол, д.ф-м.н, Издательский Дом "Комиздат"

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

– Джентельмены не читают чужих писем,- заявил госсекретарь США Стимсон в 1929 г., узнав о том, что “черный кабинет” госдепартамента США занимался раскрытием шифрованных дипломатических телеграмм многих стран. Он немедленно упразднил упомянутый кабинет. Однако, являясь в 1940 г. военным министром, Стимсон заметно смягчился и простил раскрытие японских шифров (подробнее об этом и других исторических фактах см. В работе [1]).

Период до 1949 г. называют эпохой донаучной криптологии, поскольку достижения тех времен основаны в большей мере на интуиции и “вере”, не подкрепленных доказательствами. Последние впервые появились в публикации 1949 г. К. Шеннона [2]. Он доказал в ней, в частности, невозможность раскрытия случайного шифра Г. Вернама, введенного в работе [3], без знания секретного ключа.

В свою очередь, идеология криптографии с открытыми (несекретными) ключами впервые была изложена в 1976 г. У. Диффи и М. Хеллманом в работе [4]. В ней авторы показали, что секретная связь возможна без передачи секретного ключа между отправителем и получателем.

Благодаря ставшими уже классическими статьям [2 и 4], криптология состоялась как математическая наука.

К. Шеннон выделил в своей работе два общих принципа, используемых в практических шифрах: рассеивание и перемешивание. Достижение рассеивания и перемешивания осуществляется посредством реализации перестановок символов открытого текста, а также подстановок, заменяющих символы открытого текста на другие символы, из того же алфавита. Конкретный вид как перестановок, так и подстановок определяют секретные ключи. Один из примеров криптоалгоритма, разработанного в соответствии с указанными принципами К.Шеннона, является стандарт шифрования данных (DES), принятый в США в июле 1977 г. в качестве Федерального стандарта. В этом стандарте открытый текст Х, криптограмма Y и ключ Z -- двоичные последовательности длиной М = 64, N = 64 и K = 56 соответственно. Так как M = N, то DES является подстановкой в алфавите, содержащем 264 символов. Полное описание криптоалгоритма DES можно найти практически в любом учебнике по криптографии (например [5]), опубликованном после 1977 г.

С момента принятия Федерального стандарта DES и по сей день, он остается в центре внимания криптоаналитиков. Используемые при этом математические методы частично изложены в упоминавшейся ранее книге [5]. К ним А. Конхайм (автор книги [5]) относит методы теории вероятностей и математической статистики, линейной алгебры, теории групп и теории сложности. Более десяти лет стандарт DES оправдывал надежды его защитников. По состоянию на январь 1988 г. наиболее быстрый из известных вариантов криптоанализа этого стандарта предполагал выполнение 2K-1 процедур шифрования, т. е. практически предполагалось осуществление перебора всех вариантов. Первые сообщения о том, что теоретически возможно вскрыть стандарт DES за число операций, меньшее, чем 2K-1, появились в 1990 г., а соответствующие публикации в 1993 г. Так в работе [6] показано, что методом разностного криптоанализа перебор вариантов можно снизить до 247. Данный подход, как выяснилось со временем, был известен разработчикам стандарта DES. Однако противодействия этому методу, заложенные ими в криптосистему DES, при некоторых обстоятельствах, указанных авторами работы [6], удается обойти. Линейный криптографический анализ, предложенный в работе [7], основан на вероятностной оценке числа линейных соотношений между открытым текстом, шифртекстом и битами ключа, которые содержат информацию о ключе. Для успешной атаки на стандарт DES метод линейного криптоанализа требует 243 зашифрованных текстов (см. [7]).

Теоретические работы [6 и 7] послужили толчком к совершенствованию известных и созданию новых криптографических схем. Этот период в развитии криптографии нашел свое отображение в монографии [8], перевод которой на русский язык в настоящее время готовится в Издательском доме “Вильямс” (www.williamspublishing.com). В частности, в этой работе помещено детальное описание криптоалгоритма RC5, являющегося, по мнению специалистов, весьма удачным и таким, который после незначительных модификаций мог бы сменить стандарт DES.

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

В связи со сказанным более острым становится вопрос о том, что понимать под надежностью криптографического алгоритма. От чего в точности он защищает? Ответ на поставленный вопрос ищется, в частности, в рамках различных математических теорий. Принимая во внимание тот факт, что в большинстве случаев криптосистемы являются булевыми функциями, т. е. функциями, отображающими наборы из n битов в наборы из m битов, создатели указанных систем стремятся к тому, чтобы эти функции имели равномерно распределенный выход и тем самым “уничтожали” статистические закономерности открытого текста, обеспечивая, таким образом, криптосистеме надежность в теоретико-информационном смысле. В свою очередь, стандарт DES и возможные его приемники, к которым специалисты относят криптоалгоритмы RC6 (незначительная модификация упоминавшегося ранее RC5), MARS, Twofish, Serpent и Rijndael, считаются надежными в вычислительном смысле.

Различные толкования понятия надежности можно объяснить, обратившись к правилу для криптографов, сформулированному еще в XIX веке Керкхоффом (Kerckhoffs) в его книге “La Cryptographic militare”: криптоаналитику противника известен весь механизм шифрования, кроме значения секретного ключа. Для криптографа, придерживающегося этого правила, понятие надежности алгоритма становится, таким образом, динамически изменяющимся, зависящим от криптоаналитических возможностей противника в различные моменты времени.

Формирование понятия надежности, изобретение линейного криптоанализа в ответ на принятие стандарта DES -- все это может служить примерами проявления взаимосвязи двух составных частей криптологии. В свою очередь криптография с открытым ключом послужила толчком к раскрытию многих криптосистем. Чтобы объяснить это явление, обратимся снова к работе К. Шеннона [2]. В ней автор рекомендует конструировать такие шифры, чтобы раскрытие любого из них было эквивалентно решению задачи, о которой известно, что для ее решения требуется большой объем работы. Эта рекомендация помогла авторам работы [4] предложить криптографию, не использующую передачи секретного ключа. Их метод построен на применении односторонней функции и односторонней функции с потайным ходом. Определения и примеры этих функций, а также собственно алгоритм шифрования можно найти практически в каждом учебнике по криптографии, вышедшем после 1977 г., в частности [5, 8, 10, 11 и др. ]. Доказательство стойкости криптосистемы с открытым ключом могло бы состоять в обосновании того факта, что любой алгоритм раскрытия этой системы требует неприемлемо большого объема вычислений. Ни одна из систем с открытым ключом не удовлетворяет этому критерию стойкости. Хотя существуют такие криптосистемы, в отношении которых доказано, что их стойкость эквивалентна сложности решения задачи разложения целого числа n на простые множители. По мнению многих специалистов, указанная задача является крайне сложной для больших значений числа n. Вполне естественно, что поиски труднорешаемых математических задач могут привести к доказательству того, что задача, считавшаяся трудной и на этом основании использовавшаяся в криптоалгоритме, в действительности не является таковой и, следовательно, криптосистема, построенная на ней, вполне раскрываемая.

Ранее мы коснулись содержания учебников по криптографии, опубликованных после 1977 г. Для читателя, заинтересовавшегося данной тематикой, добавим к сказанному, что как учебники, так и справочные пособия по криптографии последних лет содержат, как правило, сведения о классическом шифровании с секретными ключами, о шифровании с открытыми ключами и о применениях криптографии. Различие между монографиями обусловлено различными научно-педагогическими интересами их авторов. Так, в работе [5] значительное место уделено математическим методам криптоанализа, в [11] - криптографии с открытыми ключами, в [8] - применениям криптографии (в частности, к безопасному общению в сети интернет), в [12] - программной реализации на языке Java алгоритмов криптографии с открытыми ключами и иллюстрациям их применения в задачах аутентификации информации, цифровой подписи и т. д.

Математические методы криптологии, их программно-алгоритмическая реализация и сферы приложений, освещенные в перечисленной учебно-справочной литературе, сохранят, по-видимому, свою актуальность в ближайшие десятилетия. Безусловно, она пополнится в случае смены криптоалгоритма DES описанием нового Федерального стандарта, расширенной подачей разностного и линейного криптографического анализа, исследованиями нелинейных булевых функций, наметившимися в работе [13].

Литература

1. D.Kahn. The Codebreakers, The Story of Secret Writing.-- New York: Screbner, 1996.

2. K.Э. Шеннон. Теория связи в секретных системах (В кн.: Шеннон К.Э. Работы по теории информации и кибернетике).- М.: ИЛ, 1963.- С. 333–402.

3. G.S.Vernam. Cipher printing telegraph systems for secret wire and radio telegraphic communications //J.Amer. Inst. Elec. Eng.-1926.- v. 55.- Р.109–115.

4. W.Diffie and M.E.Hellman. New directions in cryptography //IEEE Trans. Informat. Theory.- 1976.- Nov., v. IT-22.- P. 644–654.

5. A.G. Konheim. Cryptography: A Primer //John Willy & Sons.- New York, 1981.

6. E. Biham and A. Shamir. Differential Cryptanalysis of the Data Encryption Standart.- New York: Springer-Verlag, 1993.

7. M. Matsui. Linear Criptanalysis Method for DES Cipher. Proseedings, EUROCRYPT’93; published by Springer-Verlag.

8.** W. Stallings. Cryptography and Network security. Principles and Practice. Second Edition. Upper Saddle River, NJ: Prentice Hall, 1999.

9. P. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS and other systems. - Lect. Notes Comput. Sci.- v. 1109.- Р. 104–113.

10. О.В. Вербіцький. Вступ до криптології.-Львів: Видавництво науково-технічної літератури, 1998.

11. A. Salomaa. Public - Key Cryptography.- New York: Springer-Verlag, 1996.

12.** J. Jaworski and P. Perrone. Java Security Handbook.- SAMS Publishing, 2000.

13. K. Nyberg. Differentially uniform mappings for cryptography. - Lect. Notes Comput. Sci.- v. 765.- Р. 55–64.


** Готовится перевод на русский язык в Издательском доме “Вильямс”. (www.williamspublishing.com)

Размещение рекламы — тел. +7 495 4119920, ICQ 232284597

Подписка на новости IT-портала CITForum.ru
(библиотека, CITKIT.ru, CitCity)

Новые публикации:

24 декабря

CITKIT.ru:

  • Новогодние поздравления
  • Сергей Кузнецов. Цикл Операционные системы: Ностальгия по будущему:

  • Алексей Федорчук. OpenSolaris 2008.11 Release

  • Сергей Голубев:

  • Евгений Чайкин aka StraNNik (Блогометки):

    17 декабря

  • С.Д.Кузнецов. Базы данных. Вводный курс

    10 декабря

    CITKIT.ru:

  • OpenSolaris 2008.11 Release

  • Альтернативные ОС: две грустные истории (С.Кузнецов)
  • Nokia N810 — доведение до ума
  • CitCity:

  • Платформа 2009: заоблачные перспективы Microsoft

    4 декабря

  • Лекция С.Д.Кузнецова Понятие модели данных. Обзор разновидностей моделей данных

    CITKIT.ru:

  • OpenSolaris 2008.11 Release. Первые впечатления

  • Linux vs FreeBSD: продолжим "Священные войны"?

  • Nokia N810 as is

  • Индульгенция для FOSS

  • Друзья СПО'2008

    26 ноября

  • Нечеткое сравнение коллекций: семантический и алгоритмический аспекты

    CitCity:

    CITKIT.ru:

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • 19 ноября

  • Проблемы экономики производства крупных программных продуктов

  • Язык модификации данных формата XML функциональными методами

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Заметки к книге:

  • FreeBSD: монтирование сменных устройств и механизм HAL
  • Текстовый редактор ee

    12 ноября

  • Правило пяти минут двадцать лет спустя, и как флэш-память изменяет правила (Гоц Грейф, перевод: Сергей Кузнецов)

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:
  • OSS в России: взгляд правоведа (В.Житомирский)

  • Новая статья из цикла С.Голубева "Железный марш":

    29 октября

  • О некоторых задачах обратной инженерии

  • Веб-сервисы и Ruby

  • Тестирование web-приложений с помощью Ruby

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

  • PuppyRus Linux - беседа с разработчиком (С.Голубев)

  • Сергей Кузнецов. Заметка не про Linux

    22 октября

  • Обзор методов описания встраиваемой аппаратуры и построения инструментария кросс-разработки

    CITKIT.ru:

  • Сергей Кузнецов. Почему я равнодушен к Linux

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • Что надо иметь
    3. Базовые познания

    CitCity:

  • Управление IT-инфраструктурой на основе продуктов Microsoft

    15 октября

  • Методы бикластеризации для анализа интернет-данных

    CitCity:

  • Разъемы на ноутбуках: что они дают и зачем их так много?
  • AMD Puma и Intel Centrino 2: кто лучше?

    CITKIT.ru:

  • Новый цикл статей С.Голубева
    Железный марш:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    8 октября

  • Автоматизация тестирования web-приложений, основанных на скриптовых языках
  • Опыт применения технологии Azov для тестирования библиотеки Qt3

    Обзоры журнала Computer:

  • SOA с гарантией качества
  • Пикоджоуль ватт бережет
  • ICT и всемирное развитие

    CitCity:

  • Пиррова победа корпорации Microsoft

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Статья из архива:

  • Я живу в FreeBSD (Вадим Колонцов)

    Новые Блогометки:

  • Перекройка шаблона Blogger или N шагов к настоящему
  • Blogger. Comment style
  • Screenie или глянцевый снимок экрана

    2 октября

    CITKIT.ru:

  • Сага о FreeBSD (А. Федорчук)

    Zenwalk: пакет недели

  • Банинг — интеллектуальное развлечение (С.Голубев)

    CitCity:

    25 сентября

  • Клермонтский отчет об исследованиях в области баз данных

    CITKIT.ru:

  • Пользователям просьба не беспокоиться... (В.Попов)

  • Снова про ZFS: диск хорошо, а два лучше
  • Командная оболочка tcsh (А.Федорчук)

    Zenwalk: пакет недели

    17 сентября

  • T2C: технология автоматизированной разработки тестов базовой функциональности программных интерфейсов
  • Технология Azov автоматизации массового создания тестов работоспособности

    CITKIT.ru:

  • FreeBSD: ZFS vs UFS, и обе-две — против всех (А.Федорчук)

    Zenwalk: пакет недели

  • Дачнет — практика без теории (С.Голубев)

    10 сентября

  • За чем следить и чем управлять при работе приложений с Oracle
  • Планировщик заданий в Oracle
    (В.Пржиялковский)

    CITKIT.ru:

  • Microsoft: ответный "боян" (С.Голубев)

  • Причуды симбиоза, или снова "сделай сам" (В.Попов)

  • Файловые системы современного Linux'а: последнее тестирование
  • Zsh. Введение и обзор возможностей
    (А.Федорчук)

    Описания пакетов Zenwalk: Zsh, Thunar, Thunar-bulk-rename, Xfce4-places-plugin, Xfce4-fsguard-plugin

    Блогометки:

  • Google Chrome
  • Лончер для ASUS Eee PC 701

    3 сентября

    CITKIT.ru:

  • Заметки о ядре (А.Федорчук):

    Добавлены описания пакетов Zenwalk: Galculator, Screenshot, Gnumeric, Pidgin

    В дискуссинном клубе:

  • И еще о Википедии и Google Knol

  • Лекция для начинающего линуксоида (С.Голубев)

    26 августа

  • Транзакционная память (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Открыт новый проект Zenwalk: пакет недели

  • Статья Текстовые процессоры и их быстродействие: конец еще одной легенды?

    21 августа

    CITKIT.ru:

  • Почему школам следует использовать только свободные программы (Ричард Столлман)
  • Беседа Сергея Голубева с учителем В.В.Михайловым

  • Википедия или Гуглезнание? Приглашение к обсуждению (Алексей Федорчук)
  • Народная энциклопедия от Google (StraNNik)

  • Обзор Mandriva 2009.0 Beta 1 Thornicrofti
  • Новичок в Линукс: Оптимизируем Mandriva 2008.1

  • Книга Zenwalk. Приобщение к Linux:

    13 августа

    CitCity:

  • Мирный Atom на службе человеку. Обзор платы Intel D945GCLF с интегрированным процессором
  • Обзор процессоров Intel Atom 230 на ядре Diamondville

  • iPhone - год спустя. Скоро и в России?

    CITKIT.ru:

  • Интермедия 3.4. GRUB: установка и настройка (из книги Zenwalk. Приобщение к Linux)

    6 августа

  • СУБД с хранением данных по столбцами и по строкам: насколько они отличаются в действительности? (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Интермедия 2.2. Что неплохо знать для начала (из книги Zenwalk. Приобщение к Linux)

  • И снова про шрифты в Иксах (А.Федорчук)

  • 20 самых быстрых и простых оконных менеджеров для Linux

  • Дело о трех миллиардах (С.Голубев)

    30 июля

  • OLTP в Зазеркалье (Пересказ: С. Кузнецов)

    CitCity:

  • Будущее BI в облаках?
  • Тиражные приложения и заказная разработка. Преимущества для заказчика
  • Дискуссия со сторонниками заказной разработки

    CITKIT.ru:

  • Новые главы книги Zenwalk. Приобщение к Linux:
  • Глава 8. Пакеты: средства установки, системы управления, системы построения
  • Глава 9. Zenwalk: репозитории, пакеты, методы установки

    23 июля

    CITKIT.ru:

  • Все против всех. 64 vs 32, Intel vs AMD, tmpfs vs ext3
  • Две головы от Intel

  • Zenwalk: обзор штатных приложений (глава из книги "Zenwalk. Приобщение к Linux")

  • Нормально, Григорий...

    16 июля

    Обзоры журнала Computer:

  • Перспективы и проблемы программной инженерии в XXI веке
  • Большие хлопоты с большими объемами данных
  • Перспективы наноэлектроники

    CITKIT.ru:

  • Интермедия о лицензиях (А.Федорчук. "Zenwalk. Приобщение к Linux")

  • Есть ли будущее у KDE?

  • Linux в школе: альтернативный вариант в задачах

  • Шифр (приключения агента Никодима)

    10 июля

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия вступительная. Linux или GNU/Linux? Как вас теперь называть?
  • Глава 5. Среда Xfce
  • Глава 6. Xfce: приложения и плагины

  • ZUR (Zenwalk User Repository) FAQ

    2 июля

  • Персистентность данных в объектно-ориентированных приложениях (С. Кузнецов)

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия 1.2. Дорога к Zenwalk'у. Период бури и натиска
  • Интермедия 3.3. Немного о Linux'е и "железе"
  • Глава 4. Настройка: инструментами и руками
  • Интермедия 4.1. Zenpanel и конфиги: поиски корреляции

  • Интервью с Жан-Филиппом Гийоменом, создателем дистрибутива Zenwalk

  • Linux в школе: первые итоги (С. Голубев)

    25 июня

    CITKIT.ru:

  • Zenwalk. Приобщение к Linux (А. Федорчук)

  • Логика и риторика (С.Голубев)

  • Технология Tru64 AdvFS

  • Ханс Райзер предлагает отвести полицейских к телу Нины

    18 июня

  • Проекты по управлению данными в Google (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • ОС и поддержка "железа": мифы и реальность (А. Федорчук)

  • Linux в школе: другие дистрибутивы

  • Пинок (С. Голубев)

    4 июня

  • Ландшафт области управления данными: аналитический обзор (С. Кузнецов)

    CITKIT.ru:

  • Linux в школе: слово заинтересованным лицам

  • SlackBuild: пакеты своими руками

  • Linux от компании Novell. Установка и обзор openSUSE Linux

    Все публикации >>>




  • IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

    Информация для рекламодателей PR-акции, размещение рекламы — тел. +7 495 4119920, ICQ 232284597 Пресс-релизы — pr@citcity.ru
    Послать комментарий
    Информация для авторов
    Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
    Copyright © 1997-2000 CIT, © 2001-2007 CIT Forum
    Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...