id: Гость   вход   регистрация
текущее время 15:11 28/03/2024
Автор темы: Гость, тема открыта 12/11/2007 10:59 Печать
Категории: криптография, алгоритмы
http://www.pgpru.com/Форум/Криптография/ОценитеБлочныйШифр
создать
просмотр
ссылки

Оцените блочный шифр


Шифрование

========================= a: 01 02 03 04 – Исходные данные.
b: 05 06 07 08 – Пароль.
c: 56 08 30 64 – Случайные данные.
d: 61 14 37 72 – Произведение случайных данных и пароля.
e: 62 16 38 76 – Произведение исходных данных с случайными.
f: 61 14 37 72 62 16 38 76 – Зашифрованные данные.
; Ключ сохроняем простым дописыванием перед шифротекстом.


Расшифрование

========================= f: 61 14 37 72 62 16 38 76 – Зашифрованные данные.
g: 61 14 37 72 – Отделяем ключ (первые четыре байта).
b: 05 06 07 08 – Минус пароль.
c: 56 08 30 64 – Получаем случайные данные.
f: 62 16 38 76 – Вычитаем из шифротекста случайные.
a: 01 02 03 04 – Получаем исходные.


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


 
На страницу: 1, 2, 3 След.
Комментарии
— unknown (12/11/2007 13:52, исправлен 12/11/2007 13:56)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Каждый раз шифруя одинаковый текст одинаковым паролем выход будет разный

Рандомизированное хэширование? В данном случае непрактично.

Ну у вас тут для наглядности сложение по модулю 256, можно было бы и простой xor сделать

d = b + c (mod 256)
e = a + c (mod 256)

f = d || e

Возьмём два блока:

d_1 – e_1 (mod 256) = b_1 – a_1 (mod 256)

d_2 – e_2 (mod 256) = b_2 – a_2 (mod 256)

Но пароль то общий для всех блоков:

b_1 = b_2

d_1 – d_2 – e_2 – e_2 (mod 256) = a_1 – a_2 (mod 256)

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

Про стойкость к известным и подобранным тестам говорить не стоит.
Число раундов ничего не изменит: все операции линейные.

В практической реализации размер ключа можно существенно увеличить

До размера исходного текста и больше одного раза не использовать :-)
— Вий (12/11/2007 14:22, исправлен 12/11/2007 14:26)   профиль/связь   <#>
комментариев: 510   документов: 110   редакций: 75
Оцените блочный шифр

Эх, не криптограф я конечно, но что-то мне напомнило в этом примере давно описанную Циммерманом историю

В начале 70-х, ещё учась в колледже, я придумал, как тогда полагал, блестящую шифровальную схему. Простой поток псевдослучайных чисел объединялся с потоком открытого текста, производя шифртекст. Это должно было сделать его устойчивым к любому статистическому анализу, не позволяя взломать шифр даже самым могучим разведслужбам. Я почувствовал такое самодовольство!

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


Это конечно не камень в Ваш адрес, а просто интересная информация
— Гость_2 (12/11/2007 20:30)   <#>

Да одинаков.

Пожалуйста поясните.

Я не претендую на создание серьезного блочного шифра
— unknown (12/11/2007 22:17, исправлен 12/11/2007 22:29)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Последняя строка должна конечно выводиться вот-так:

(d_1 – e_1) – (d_2 – e_2) (mod n)= (b_1 – a_1) – (b_2 – a_2)(mod n)

d_1 – e_1 – d_2 + e_2 (mod n) = b_1 – a_1 – b_2 + a_2(mod n)

Т.к. пароли одинаковые, то b_1 – b_2 = 0

А разность между открытыми текстами в блоках можно вычислить по d и е:

a_2 – a_1(mod n) = d_1 – d_2 – e_1 + e_2 (mod n)

С точки зрения современной криптографии шифр взломан: происходит полная утечка разностей открытого текста в шифртексте: всю информацию об открытом тексте
Вы выдаёте противнику.

Пусть размер ключа (пароля) и ширина блока (n) – даже неизвестны. но их число небольшое, легко перебрать на компьютере от 0 до тысяч битов.
Ведь мы перебираем не сами ключи (2n), а их вероятный размер n.

В стойком шифре никаких разностей открытого текста в шифртексте быть не может. Но в данном случае, перебирая все значения n, мы найдём такое n, при котором
разности a_2 – a_1 (mod n) будут существенно отличаться от случайных значений. Так мы найдём n. Затем можно составить таблицу разностей частот
скажем для английского или русского теста или вероятных щифруемых заголовков или последовательностей ascii-символов
и попробуем найти блоки с подходящими разностями. Так мы найдём хотя бы в одном блоке a_1, тогда b_1=d_1 – c_1 mod (n).
Если угадали точно, то такой пароль/ключ теперь можно извлечь из любого блока для сравнения, ведь все значения b должны быть равны и вскрыть всю шифрограмму.

Если шифр элементарно вскрывается только на основе шифртекста, то о нём лучше сразу забыть. Ведь настоящий шифр должен быть устойчив к гораздо более
сильным атакам: например с известным открытым текстом (если противник знает хотя бы один блок со значением "a", то нахождение "d" для него ещё более тривиально).
Устойчивость к подобраным открытым текстам тоже обязательна: если зашифровать одни нули, то он тоже должен быть стоек, в отличие от того, что
Вы предлагаете. Я уже не говорю про связанные ключи и устойчивость к серьёзным видам криптоанализа.

Тип обратимой операции неважен, взлом будет примерно такой же, чтобы Вы не выбрали для своей схемы: сложение по модулю любого числа, XOR – это всё линейные операции, сами по себе для шифрования непригодные, если не используются в составе специально подобранных конструкций (блоков диффузии, нелинейного смешения операций разных алгебраических групп и т, д, )

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

Если хотите понять устройство блочных шифров то изучите хотя-бы в общем виде такие простые шифры как ГОСТ, DES, затем blowfish, IDEA и RC5, а напоследок AES. Неспроста ведь дизайн шифров
развивался в определённом направлении, шансов сделать здесь какое-то открытие просто по незнанию осталось мало.
— Гость (13/11/2007 01:35)   <#>
Хм... мысль такая в голову пришла: криптография, симметричная, вся... – она основана на security via obscurity? Я так понимаю, нет математического доказательства невзламываемости того же хотя бы AES за число итераций, меньшее чем... чтобы полностью свести взлом алгоритма к проблеме мощностей компьютера? Более сложный вопрос (сразу говорю, что от криптографии я далёк, но математику изучал): в связи с тем, что шифрование – это, как правило обратимая функция типа F(a,b)->c, где "а" – текст, а "b" – пароль, обычно много меньший по размеру чем сам текст, обязательно для шифротекста энтропия будет порядка той же что была в открытом тексте, а "эффективная сложность" шифротекста будет эквивалентна сложности пароля. Это приводит к тому, что симметричное крипто представляет собой некую очень сложную технически функцию, отображающую открытый текст в шифротекст, но её "эффективная мощность" не велика, то есть пространство образов довольно бедное по сравнению с произвольным отображением открытого текста на шифтротекст, где пароль порядка длины текста, или банально, шифроблокнот. В этом смысле вся защита сводится к тому, что сложно детально исследовать и найти симметрии в этой функции, позволяющие ломать... но, однако, можно сказать что они зведомо есть(?). Эх, как бы реализовать в виде слов всю эту кашу что в голове... вот так наверное: стойкость шифра, использующего пароль некоторой длины, не может превышать стойкость одноразового блокнота, применённого к (открытому) тексту с длиной, равной длине пароля. Здесь одноразовый блокнот понимается как функция, мощность образа которой не слабее чем прообраза... собственно, мне кажется что применяя пароль вместо блокнота, можно точно оценить границу понижения криптостойкости как функцию пароля. Правда, терзают меня сомнения... что криптосила всех реальных криптоалгоритмов с паролем далека от той границы... так как действия пароля на кусок открытого текста слабее его шифрования одноразовым блокнотом.

Наверно, больше похоже на бред, но интересно услышать, далёк ли я от понимания происходящего?
— Гость (13/11/2007 01:39)   <#>
s/как функцию пароля/как функцию длины пароля/
— SATtva (13/11/2007 02:01)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
криптография, симметричная, вся... – она основана на security via obscurity?

Скажете тоже... Для полинезийского пигмея устройство лампочки накаливания — это тоже obscurity, но не из-за сложности самого устройства, а только потому что он в школе не учился.

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

обязательно для шифротекста энтропия будет порядка той же что была в открытом тексте

Это в данном случае называется условной энтропией. Условие — знание Вами пароля.

Наверно, больше похоже на бред, но интересно услышать, далёк ли я от понимания происходящего?

Да всё Вы правильно говорите, только ничего нового тут нет. Криптология, как и другие "оборонительные" дисциплины, занимается (и будет заниматься) вечной борьбой брони и снаряда. Традиционная криптография издревле старалась большой секрет (открытый текст) превратить в малый (ключ или способ преобразования), что невозможно сделать без потерь в теоретико-информационной стойкости. (Одноразовый блокнот, который Вы назвали, — единственный алгоритм, не подверженный этому правилу, но именно потому, что там "уменьшения секрета" не происходит, и размер ключа равен открытому тексту.)
— unknown (13/11/2007 09:08, исправлен 13/11/2007 09:11)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Наверно, больше похоже на бред, но интересно услышать, далёк ли я от понимания происходящего?

Это не бред. Это вольный пересказ основ современной криптографии, математически описанных Клодом Шенноном в конце 40-х годов XX века. Эти основы являются фундаментом, а ни как не опровержением современной криптографии, которая вся построена на том, что кроме информационно-теоритической стойкости (перед которой все алгоритмы нестойки, кроме одноразового блокнота), существует ещё и вычислительная стойкость. Которая должна быть выше атаки грубой силой 2256, а не 20, как в Вашем случае.

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

На самом деле это тоже обычное дело даже в инженерной практике: нельзя создать абсолютно надёжный самолёт, мост или даже атомный реактор. Приходиться подразумевать вероятность ошибки в конструкции, даже и фатальной. Главное чтобы она была приемлемо мала.
— unknown (13/11/2007 09:22, исправлен 13/11/2007 09:22)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Это приводит к тому, что симметричное крипто представляет собой некую очень сложную технически функцию, отображающую открытый текст в шифротекст, но её "эффективная мощность" не велика, то есть пространство образов довольно бедное по сравнению с произвольным отображением открытого текста на шифтротекст, где пароль порядка длины текста, или банально, шифроблокнот.

Блочный шифр работает с блоками: в зависимости от размера блока и ключа мощность функции будет 2128 или 2256, так что "пространство образов" никакое не "бедное", если в функции нет дефектов.
— unknown (13/11/2007 09:27, исправлен 13/11/2007 09:34)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
(если противник знает хотя бы один блок со значением "a", то нахождение "d" для него ещё более тривиально).

s/"d"/"b"// (нахождение пароля "b")
— SATtva (13/11/2007 13:16)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
На самом деле это тоже обычное дело даже в инженерной практике: нельзя создать абсолютно надёжный самолёт, мост или даже атомный реактор.

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

Есть здесь и сходство с крипто. Если перефразировать Райвеста, можно сделать сколь угодно стойкий шифр, но хитрость заключается в том, чтобы он был стойким, простым и быстрым. Опять же, используя избыточное число раундов или дополнительных внутренних конструкций, удлинив ключ до десятков килобит, можно на порядки повысить стойкость шифра, но только ценой стоимости вычислений.
— Гость (13/11/2007 20:47)   <#>
"пространство образов" никакое не "бедное", если в функции нет дефектов.

Отсутствие дефектов – сильное требование :) Ведь мы знаем и образ и прообраз. Хочется получить шифротекст с максимальной энтропией... то есть равнораспределённый по частотам, используя терминологию... В физике хорошо известно, что идеального белого шума не бывает... вот отсюда всё и идёт (я так понимаю...).
— Гость (13/11/2007 20:57)   <#>
Дело же ещё в том, что к криптографии, современной, предъявляются довольно жёсткие методы. Например, если противник имеет чёрный ящик на вход которого он может посылать любой текст, и изучать шифротекст, то он не должен быть способным вычислить пароль или найти его слабости... беда же в том что одни и тем же паролем шифроваться может огромное число блоков, и в этом могут проявиться закономерности самого пароля (что математически вполне естественно)... а увидев закономерности, теоретически можно и сам пароль воссстановить. Более того, мне кажется что можно строго математически показать, что существует такое нереальное число известных входов и соответствующих им выходам из чёрного ящика, после которых можно будет заведомо восстановить пароль! То есть... крипто глубоко математически основано не идеологии security via obscurity и нехватке мощностей, в самом своём фундаменте. Похоже на правду?
— Гость (13/11/2007 21:02)   <#>
s/жёсткие методы/жёсткие требования/
— Гость (13/11/2007 21:03)   <#>
Я здесь не спорю про объективно техническую сторону дела, я про сам матфундамент... про теорию.
На страницу: 1, 2, 3 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3