Война в Украине

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

Криптография

Материал из Urbanculture
Версия от 12:37, 25 февраля 2013; Xlikam (обсуждение | вклад) (Исправил определения + переписал квантовую криптографию)

Перейти к: навигация, поиск
Штирлиц смотрит на криптографов с каким-то презрением в глазах
Ылчу — флфхзпг цфосерюш кргнсе, тулпзрВзпгВ жоВ фзнузхрсм тзузтлфнл жлтоспгхлъзфнлш тузжфхгелхзозм фс феслп тугелхзояфхесп, е ессуцйзррюш флогш жоВ тзузжгъл тулнгксе, угфтсуВйзрлм, жсрзфзрлм. Ылчусп хгнйз ргкюегзхфВ оБдгВ лрчсупгщлВ, тзузжгегзпгВ е кгнуюхсп елжз ф щзояБ фнуюхя сх тсфхсусррлш ёогк зи фсжзуйлпсз. Сдюърс ылчусегрлз туслкесжлхфВ кгпзрсм лфшсжрюш дцне, чугк лол лш ъгфхзм лрюпл дцнгепл лол нспдлргщлВпл, фсфхгеоВБьлпл ноБъ ылчуг, нсхсуюш псйзх дюхя рзфнсоянс л гоёсулхп лш тулпзрзрлВ псйзх угколъгхяфВ.|[1]

Тот, кто понял что здесь написано, понял суть криптографии.

Основные понятия

Открытый текст — исходный текст, сообщение как таковое.

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

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

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

Расшифровывание — действие, обратное шифрованию: получение открытого текста из шифрата. Не стоит путать с дешифровкой.

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

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

Поручитель — человек, подтверждающий принадлежность данного публичного ключа кому-либо. Поручитель является аналогом нотариуса. Поручителю должно оказываться доверие, а его публичный ключ должен быть известен изначально, чтобы с помощью ЭЦП можно было убедиться, что подтверждение выписано поручителем, а не кем-то ещё. Формируются цепочки поручителей разных уровней, в которых публичный ключ следующего подписан предыдущим. У основания стоят поручители с мировым именем, например Verisign. Поручители являются одним из способом гарантировать принадлежность открытого ключа этому человеку, а без этого невозможно направить сообщение, которое мог бы прочитать только он, или надежно подтвердить авторство его сообщения.

Хеш-функция — алгоритм, превращающий данные (например, текст) в число (хеш-значение). Число может быть довольно большим, например для md5 это 128-битное число. Криптографическая хеш-функция — это хеш-функция, для которой не существует эффективного способа подобрать такие исходные данные, для которых бы она выдавала заранее выбранный результат. Для некоторых хеш-функций (например, crc32) это требование удается обойти, тогда функция считается взломанной и больше не используется в криптографии. Если появляется алгоритм генерации нескольких текстов, дающих одинаковое хеш-значение, то функцию тоже считают взломанной (например, md5). Криптографическую хеш-функцию можно рассматривать как необратимое шифрование без ключа. Хеш-функции применяются в криптографии для уменьшения размера текста перед его подписыванием ЭЦП и для безопасного хранения паролей, при котором можно проверить соответствие введенного пароля сохраненному, но нельзя узнать сам сохраненный пароль.

Ключ, как правило, можно «приладить» к хеш-функция в виде соли — строки, соединяемой с открытым текстом перед применением хеш-функции. Это бывает полезно для затруднения подбора исходного текста с помощью словарей популярных паролей и таблиц вида текст — хеш-значение. При атаках в качестве такой таблицы может использоваться google. В этом можно убедиться, поискав 202cb962ac59075b964b07152d234b70 — значение хеш-функции md5 для «123». А если использовать соль «wabranes», то md5(wabranes|123) = «477de9d90eaed5064a303698244dc685» уже не находится в гугле (за исключением, возможно, этой страницы).

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

История

Вовсе времена существовали способы доставки сообщений между враждующими сторонами. Со временем шифры стремительно развивались.

Древние шифры

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

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

Более продвинутым является греческий шифр «Скитала», он же шифр древней Спарты. На цилиндр наматывалась лента папируса, на которой записывался текст — вдоль цилиндра построчно. Оставшееся незанятым место заполнялось всяким хламом. Если текст не вмещался на одну ленту, использовалась следующая. Если теперь снять ленту с цилиндра, на ней получится внешне бессмысленный набор символов.

Пример:

 _________________________________________
     |  |   |   |   |   |   |
     |  | Э | Т | О | Ш | И |  
     |__| Ф | Р | Д | Р | Е |__ 
        | В | Н | Е | Й | С |  |
        | П | А | Р | Т | Ы |  |
        |   |   |   |   |   |  |
 _________________________________________

Результат: «ЭФВПТРНАОДЕРШРЙТИЕСЫ». Для дешифровки нужно знать диаметр цилиндра. Это пример перестановочного шифра в котором буквы текста меняются местами по заданному алгоритму.

Асимметричное шифрование

Пример закрытого ключа
Пример открытого ключа из той же пары

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

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

Обмен публичными ключами. Уязвимость. Сертификация и сеть доверия.

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

Допустим, существует третья заинтересованная сторона, которая предоставит вам свой ключ вместо ключа вашего корреспондента, а ему в свою очередь такой же фиктивный свой ключ вместо вашего. Тогда эта третья сторона сможет расшифровать ваше сообщение, подменить его тем же самым исходным текстом, только зашифрованным настоящим публичным ключом вашего корреспондента, и переслать ему. Он же, обладая вашим фиктивным ключом (который ему заботливо подсунули), шифрует для вас ответ, также достающийся третьей стороне, которая преспокойно добывает исходный текст и шифрует его вашим настоящим ключом. В результате хитрых манипуляций окажется, что вся сложность перехвата сводится не к криптоанализу и созданию идентичных хэшей электронной подписи, что почти невозможно,[2] а к банальной подмене, что вполне реализуемо — было бы сильное желание. Такая атака называется Man-in-the-middle.

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

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

Квантовая криптография

Новое направление в криптографии, основанное не на математических методах, как обычная а на принципах квантовой механики. Чтобы понять, как оно работает, надо знать квантовую механику и прочий, связанный с нею матан. Но если на пальцах, то работает оно на принципе неопределённости, согластно которому две квантовые величины невозможно измерить с заданной точностю, а только лишь одну на выбор, состояние другой в этом случае может быть каким угодно. Это значает что при попытке перехвата заданного отправителем состояния частицы третьей стороной, её состояние будет изменено, тем самым теоретически мы получаем абсолютно (в буквальном смысле этого слова!) защищёный канал передачи данных, полностью исключающий перехват и можем безнаказанно гонять через него секретные данные а любое перехват будет однаружен мгновенно. Причём у перехватчика информация согластно тому-же принципу будет меняться произвольным, непредсказуемым образом, то есть воостановить её он не сможет. Кроме того невозможно получить полную информацию о квантовом объекте, и следовательно, невозможно его скопировать и подменить на другой, тем самым подмена данных тоже исключается. Опыты по созданию подобной системы ведутся с середины 80-х с определёнными успехами, но до создания полноценной системы пока ещё далеко.

Стеганография

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

Наиболее часто для сокрытия инфы используются графические файлы. Существуют множество разных по своей сложности методов сокрытия, но наиболее простым является так называемый метод битовых плоскостей. Суть его заключается в следующем. Как известно любое изображение представляет собой совокупность точек. Каждая точка полноцветного изображения кодируется комбинацией из 3-х байт, задающих уровень красного(R), зелёного(G) и голубого цветов(B) — RGB. Если в этой комбинации изменить самый последний бит, или пару — тройку битов, цвет хоть и получится отличным от исходного, но настолько незначительно, что даже самый острый глаз не заметит никакой разницы. Это и используется для того, чтобы путём изменения битов точек встроить в изображение любой произвольный скрытый текст, который предварительно ещё и шифруется, после чего можно спокойно передавать такую картинку, не представляющую из себя никакой ценности для ФСБ, ЦРУ, M6, Моссада (нужное подчеркнуть) через обычный открытый источник. Стеганографированные картинки нельзя обрабатывать в графическом редакторе, иначе скрытая информация будет разрушена. С осторожностью их надо загружать на файловые хостинги, поскольку они тоже при загрузке могут обрабатывать изображения.

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

Примечания

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

    Кто так и не понял: это шифр Цезаря со смещением на три буквы вправо.
  2. даже при слабом ключе это очень долго, весьма дорого и при длине асимметричного ключа более 1024 бит пока не реализуемо, ведущие криптоаналитики гарантируют это