информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
За кого нас держат?Атака на Internet
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Sophos открывает Sandboxie 
 Большой вторник патчей от MS 
 И ещё раз об интернет-голосовании 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Ортогональные матрицы - вершина крипто! 06.02.03 14:36  Число просмотров: 3031
Автор: CP Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Добавлю, что предложенный вариант с матрицей требует ключа
> размером l^2, при длине сообщения l (в случае идеальных

Да нет - длина ключа зависит от периода генератора псевдослучайных
чисел. Для каждого блока - матрица своя, естественно, новенькая,
псевдослучайная!!!
Как известно, блоки лучше простого XOR'а тем, что они:
1) Размножают ошибки
2) Предотвращают чистую гамму от попадания в поток

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

ОРТОГОНАЛЬНЫЕ МАТРИЦЫ - ЭТО КВИНТЭССЕНЦИЯ И ВЕНЕЦ ВСЕЙ КРИПТОГРАФИИ!!!
Уж я то умею их получать =)))
Как вам такая ягодка, к примеру?
Каждые две любые строки или столбца имеют
четное число совпадающих единиц,
то - бишь скалярное произведение - нуль по модулю!

1 1 0 0 1 0 0 1 0 1
0 1 0 1 1 0 1 0 1 0
0 1 1 1 0 1 1 1 1 0
1 1 1 1 0 1 1 0 1 0
1 0 1 1 1 1 0 1 0 1
0 1 0 0 1 1 0 0 0 0
0 1 1 1 0 1 1 0 1 1
0 1 1 0 1 0 0 0 0 0
1 0 1 0 1 1 0 1 1 1
1 0 1 0 1 1 1 1 0 1
<theory>
ВСЁ ТОТ ЖЕ ГОСТ 26.12.02 21:16  
Автор: Lynx Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Я понимаю, что я слегка запоздал, но может кто-нибудь подскажет как в ГОСТ 28147-89 генерируется блок подстановки??? Или дайте ссылочку на подробное его описание... Заранее спасибо.
ВСЁ ТОТ ЖЕ ГОСТ 27.12.02 07:52  
Автор: cybervlad <cybervlad> Статус: Elderman
<"чистая" ссылка>
> Я понимаю, что я слегка запоздал, но может кто-нибудь
> подскажет как в ГОСТ 28147-89 генерируется блок
> подстановки??? Или дайте ссылочку на подробное его
> описание... Заранее спасибо.
Тайна сие есть великая ;)
Некоторые рекомендации можно найти на страничке у А.Винокурова (предыдущий оратор уже дал ссылку), но официально принцип выбора "сильных" таблиц не опубликован. Для сертифицированных СКЗИ таблицы выдает ФАПСИ (ключ делаешь сам).
ГОСТ 28147-89 26.12.02 22:50  
Автор: RElf <M> Статус: Member
<"чистая" ссылка>
> Я понимаю, что я слегка запоздал, но может кто-нибудь
> подскажет как в ГОСТ 28147-89 генерируется блок
> подстановки??? Или дайте ссылочку на подробное его
> описание... Заранее спасибо.

По ссылке:

Алгоритм шифрования ГОСТ 28147-89
10x 27.12.02 21:14  
Автор: Lynx Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Спасибо за информацию... Я уже скачал статью, но ещё не читал...
PS Wow, а тут реагируют даже быстрей чем на Доре :)))
Ортогональные матрицы - вершина крипто? 05.02.03 19:42  
Автор: Persicum Cyclamen Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Не могу я чего-йто врубится, зачем нужны всякие там
перестановки, подстановки, DES, GOST и прочая ерунда,
все новые и новые алгоритмы???

Есть датчик случайных нулей и единиц,
наполняем ими матрицу так,
чтобы она была ортогональной
(это надо уметь конечно,
так как невырожденные матрицы большого размера - редки,
но умеючи это делать легко )
Потом умножаем сообщение на матрицу и все - привет!
Умножаем на транспонированную - обратно плайн-текст.
Вот такая линейная алгебра по модулю II
Ортогональные матрицы - вершина крипто? 05.02.03 20:16  
Автор: tatar_0x4e Статус: Member
<"чистая" ссылка>
> Есть датчик случайных нулей и единиц,
А где он есть??? Покажите мне его, пожалуйста...
> наполняем ими матрицу так,
> чтобы она была ортогональной
> (это надо уметь конечно,
> так как невырожденные матрицы большого размера - редки,
> но умеючи это делать легко )
> Потом умножаем сообщение на матрицу и все - привет!
> Умножаем на транспонированную - обратно плайн-текст.
> Вот такая линейная алгебра по модулю II
Зачем умножать? Если бы была истинно случайная последовательность длиной с сообщение, было бы достаточно поксорить ей это сообщение. При условии использования такой последовательности только один раз получаем т.н. абсолютно стойкий шифр. Классика от Шеннона :)

Читать здесь:

http://www.cs.ucla.edu/~jkong/research/security/shannon1949.pdf
Ортогональные матрицы - вершина крипто? 06.02.03 13:10  
Автор: SerpentFly <Vadim Smirnov> Статус: Member
<"чистая" ссылка>
Добавлю, что предложенный вариант с матрицей требует ключа размером l^2, при длине сообщения l (в случае идеальных шифров Шеннона всего l для длины l). Если же шифровать блоками, то есть использовать одну и ту же матрицу для шифрования более чем одного сообщения, то шифр становиться неустойчивым к атаке по открытому тексту. Надо только набрать необходимое число уравнений l^2 в общем случае, а на самом деле даже меньше, поскольку у нас есть условие ортогональности. Ну и наконец если уравнений опять будет не хватать для единственного решения, то остаток можно осилить перебором или даже прикрутить динамическое программирование с разбиением на подмножества.
Ортогональные матрицы - вершина крипто! 06.02.03 14:36  
Автор: CP Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Добавлю, что предложенный вариант с матрицей требует ключа
> размером l^2, при длине сообщения l (в случае идеальных

Да нет - длина ключа зависит от периода генератора псевдослучайных
чисел. Для каждого блока - матрица своя, естественно, новенькая,
псевдослучайная!!!
Как известно, блоки лучше простого XOR'а тем, что они:
1) Размножают ошибки
2) Предотвращают чистую гамму от попадания в поток

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

ОРТОГОНАЛЬНЫЕ МАТРИЦЫ - ЭТО КВИНТЭССЕНЦИЯ И ВЕНЕЦ ВСЕЙ КРИПТОГРАФИИ!!!
Уж я то умею их получать =)))
Как вам такая ягодка, к примеру?
Каждые две любые строки или столбца имеют
четное число совпадающих единиц,
то - бишь скалярное произведение - нуль по модулю!

1 1 0 0 1 0 0 1 0 1
0 1 0 1 1 0 1 0 1 0
0 1 1 1 0 1 1 1 1 0
1 1 1 1 0 1 1 0 1 0
1 0 1 1 1 1 0 1 0 1
0 1 0 0 1 1 0 0 0 0
0 1 1 1 0 1 1 0 1 1
0 1 1 0 1 0 0 0 0 0
1 0 1 0 1 1 0 1 1 1
1 0 1 0 1 1 1 1 0 1
Есть одно требование, которое совсем не выполняется при обычном умножении 06.02.03 14:56  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
Невозможность получения ключа (кроме прямого перебора) при любом известном количестве пар: текст-шифртекст. Получить обратную при таком раскладе можно по одной паре
Есть одно требование, которое совсем не выполняется при обычном умножении 06.02.03 18:03  
Автор: CP Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Невозможность получения ключа (кроме прямого перебора) при
> любом известном количестве пар: текст-шифртекст. Получить
> обратную при таком раскладе можно по одной паре
Получить матрицу преобразования можно не по одной паре,
а по N парам - ну и хрен с ней, матрицы то все разные, у каждого
ьлока своя, а наполняет их криптоустойчивый генератор.
И матрица - это же не кусок гаммы в чистом виде, это его
очччень далекая производнпя.
Есть одно требование, которое совсем не выполняется при обычном умножении 06.02.03 20:25  
Автор: SerpentFly <Vadim Smirnov> Статус: Member
<"чистая" ссылка>
Итак мы пришли к тому что все опять упирается в генератор гаммы, который генерит последовательность на основе некоторго ключа. Из последоваетльности каким-то образом строиться ортогональная матрица. Сразу вопрос, насколько детерминирован процесс получения ортогональной матрицы из гаммы? Не может ли получиться двух разных матриц из одной и той же последовательности?

Ну хорошо, положим алгоритм детерминирован. Вместо простого наложения гаммы используем умножение на матрицу, ну да бог с ним. Очевидные минусы:

1) Для каждого блока нужно l^2 гаммы в отличии от простого l при наложении гаммы(XOR). Соответственно генератор начинает повторяться на шифртекстах меньшей длины. Не очень это хорошо, но если период большой, то это не столь существенно.

2) Насколько трудоемок алгоритм генерации ортогональной матрицы? Это дополнительные операции, а шифратор кроме всего должен еще и быстро работать.

3) Умножение матрицы на вектор значительно более трудоемкая операция, для одного блока имеем l^2 операций, вместо l при простом наложении.

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

Результат, придумали сложно реализуемую схему (как программно так и аппаратно) ничего не выиграв в стойкости, зато на прядок проиграв в быстродействии.
Есть одно требование... 07.02.03 14:14  
Автор: CP Статус: Незарегистрированный пользователь
<"чистая" ссылка>

1) Сначала tatar_0x4e дoнимал меня XOR, а теперь
и ты туда же. Про уязвимости XOR, почему это
самый слабый машинный шифр - написано в любой книжке.
И нефига меня одноразовым блокнотом бесить.
Имеются ввиду ведь обычные псевдослучайные числа.

2) Да, устойчивость конкретной реализции будет зависить
от датчика случайных чисел. Но:
он может быть любым, съемным и заменяемым, их может быть несколько,
они могут чередоваться или складываться. Короче -
это внешнее. И потом - гамма входит в матрицу очень запутанным образом.
и не обязательно l^2 брать - можно больше можно меньше
а если вообще ничего не брать - алгоритм выдаст единичную матрицу-
тоже рабочую и тоже ортогональную - она будет
переводить плайн-текст в плайн-текст =).

3) Ортогональные матрицы - это не просто алгоритм типа
DES, GOST и т.д. Это сущностное содержание любого блочного
алгоритма, предельный переход. Поэтому очень заманчиво
уметь получать их в явном виде. При этом степень сокрытия возрастет 1000x.
Откуда это число? Да так оно и есть. Что такое несколько раундов
DES? Кто "вспоминал" забытый пароль Виндовс - знает, что DES -
детский лепет, тьфу, за пару секунд ломается

4) Атака плайн-текст и выбранный шифротекст - А НЕТ ТАКОГО.
Берем матрицу 256x256, умножаем на единичный вектор -
получаем последний столбец - а остальные 255 - что - не нужны больше?

5) Быстродействие - медленное - ну и что? За все надо платиь.
Для предельно возможного сокрытия - можно подождать. Програмные
реализации - все медленные. Скажем, на один такт регистра с
обратными связями приходится двадцать строк С. Ну и фигли?
Подальше положишь - поближе возмешь. Скажем, на моей допотопной
тачке RSA за пару минут несколько метров перелопачивает.
С одной стороны - медленно ужасно - а с другой - это
же метры - миллионы буковок!!! А мой пинкод - всегото
пара-другая цифр. Быстродействие - шифропанкам не указ!!!!!!!!!!
Им чтоб интересно было и нестандартно!
Ну да, конечно... 07.02.03 23:27  
Автор: tatar_0x4e Статус: Member
Отредактировано 07.02.03 23:36  Количество правок: 1
<"чистая" ссылка>
>
> 1) Сначала tatar_0x4e дoнимал меня XOR, а теперь
> и ты туда же. Про уязвимости XOR, почему это
> самый слабый машинный шифр - написано в любой книжке.
> И нефига меня одноразовым блокнотом бесить.
> Имеются ввиду ведь обычные псевдослучайные числа.
>
Я тебя не донимал :) Просто сказал, что при условии одноразового использования ключа равного по длине сообщению и хорошей последовательности случайных чисел XOR сработает отлично. Как и любая другая операция - можешь складывать гамму с сообщением - никаких проблем. Тот же абсолютно стойкий одноразовый блокнот.
Кстати, ты это признал написав, что для каждого блока матрица своя. Ну и чудненько, только таким образом мы всего-то получаем усложненный одноразовый блокнот о чем тебе тут толкуют уже который день.
Ты его усложнил, поздравляю, но при условии что у каждого блока матрикс свой и используется только один раз, сущность не меняется - ксора достаточно для обеспечения безопасности. ТЫ ИЗОБРЕЛ ОДНОРАЗОВЫЙ БЛОКНОТ.

> 2) Да, устойчивость конкретной реализции будет зависить
> от датчика случайных чисел. Но:
> он может быть любым, съемным и заменяемым, их может быть
> несколько,
> они могут чередоваться или складываться. Короче -
> это внешнее. И потом - гамма входит в матрицу очень
> запутанным образом.
> и не обязательно l^2 брать - можно больше можно меньше

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

> а если вообще ничего не брать - алгоритм выдаст
> единичную матрицу-
> тоже рабочую и тоже ортогональную - она будет
> переводить плайн-текст в плайн-текст =).
>


> 3) Ортогональные матрицы - это не просто алгоритм типа
> DES, GOST и т.д. Это сущностное содержание любого
> блочного
> алгоритма, предельный переход. Поэтому очень заманчиво
> уметь получать их в явном виде. При этом степень
> сокрытия возрастет 1000x.
> Откуда это число? Да так оно и есть. Что такое несколько
> раундов
> DES? Кто "вспоминал" забытый пароль Виндовс - знает, что
> DES -
> детский лепет, тьфу, за пару секунд ломается

Твое творение тоже за пару секунд сломается, если пароль в словаре есть. Возможно возникнет некоторая тормозня из-за операции умножения, хотя вряд ли большая чем для DES.

>
> 4) Атака плайн-текст и выбранный шифротекст - А НЕТ ТАКОГО.
> Берем матрицу 256x256, умножаем на единичный вектор -
> получаем последний столбец - а остальные 255 - что - не
> нужны больше?
>

Как это нет, когда ключ получается по решением системы из 256 уравнений(атака открытый текст/выбранный шифротекст, если ключ не одноразовый то получить такие пары дело времени и умеренного терпения). Если же ключ одноразовый, то у тебя - ОДНОРАЗОВЫЙ БЛОКНОТ.

> же метры - миллионы буковок!!! А мой пинкод - всегото
> пара-другая цифр. Быстродействие - шифропанкам не
> указ!!!!!!!!!!
> Им чтоб интересно было и нестандартно!

Бог в помощь шифропанкам, кто бы они ни были...
Kxe... Сорри :) 08.02.03 01:49  
Автор: tatar_0x4e Статус: Member
<"чистая" ссылка>
Насчет 256 уравнений в предыдущем посте я погорячился, в запарке писал. На самом деле ломается элементарно. Ответь мне на один только вопрос - почему ты настаиваешь именно наортогональныхматрицах???? Чем все остальные плохи? ;)
Kxe... Сорри :) 13.02.03 21:06  
Автор: Persicum Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Насчет 256 уравнений в предыдущем посте я погорячился, в
> запарке писал. На самом деле ломается элементарно. Ответь
> мне на один только вопрос - почему ты настаиваешь именно на
>ортогональныхматрицах???? Чем все остальные плохи? ;)

А вот и хрен тебе!!!
Нужно 256 уравнений, и не все даже подойдут,
а только линейно-независимые!!!

>Чем все остальные плохи? ;)
А тем, что матрицу при расшифровке ненужно обращать,
а нужно тока транспонировать...
И вообще, где ты собрался брать эти "остальные"?
Вероятность того, что случайная матрица
не вырождена, исчезающе мала и равна 2^(-N).
Так что получатьортогональныематрицы -
целое "тайное" исскуссство, попробуй и сам поймешь
Kxe... Сорри :) 08.02.03 11:08  
Автор: SerpentFly <Vadim Smirnov> Статус: Member
<"чистая" ссылка>
Да человек в курсе математики наверное впервые с ними столкнулся, понравилось ему что перемножение A*Aт = E. Ну и конечно то что ортогональная матрица невырождена, то есть потери информации не будет. А вот теория информации и тероия алгоритмов у нас пока что хромает, видимо до нужного курса еще не доучился :-).
1






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2019 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach