October 22nd, 2016

Ягодка

Криптография и свобода. Пятилетка пышных похорон. Глава 3. Логарифмические подстановки. Часть 1.

Оригинал взят у kolkankulma в Криптография и свобода. Пятилетка пышных похорон. Глава 3. Логарифмические подстановки. Часть 1.
Оригинал взят у mikhailmasl в Криптография и свобода. Пятилетка пышных похорон. Глава 3. Логарифмические подстановки. Часть 1.
 
Глава 3
Логарифмические подстановки
                В этой главе давайте отложим в сторону лирические и понятные всем отступления про обстановку в стране в то время. Мои рассуждения об этом субъективны, кто-то может соглашаться с ними, кто-то, наоборот, считать те времена образцом для подражания на фоне современной криминализации страны. В этой книге я старался следовать криптографически-философскому принципу Шеннона: в шифре чередовать не похожие друг на друга операции перемешивания и сдвига. В качестве операций сдвига – главы, отображающие общую ситуацию в СССР и в КГБ в те, теперь уже далекие времена, а в роли перемешивания выступают главы, в которых много говорится о математике, криптографии или программировании. Сейчас начнется очередная «перемешивающая» глава.    
                Шифратор «Ангстрем-3» был построен в полном соответствии с этим принципом Шеннона: регистр сдвига над Z/256 (операции сдвига), усложненный подстановкой из S256, типичным перемешивающим преобразованием. Перемешивающее преобразование дает столь необходимое в криптографии размножение различий в блоках открытого текста. В общефилософских книгах по криптографии, типа упоминавшейся выше книги Брюса Шнайера «Прикладная криптография», употребляется даже термин «лавинный эффект». Вот соответствующая цитата оттуда.
«… Это называется лавинным эффектом. DES спроектирован так, чтобы как можно быстрее добиться зависимости каждого бита шифртекста от каждого бита открытого текста и каждого бита ключа.»
 
                Насколько я представляю себе DES, нигде, ни в одной книге, не было дано точных математических оценок этого «лавинного эффекта». DES так спроектирован и все. А почему он так спроектирован? Остается лишь догадываться, да строить статистические эксперименты, которые подтверждают: да «лавинный эффект» безусловно есть.
                Вся прелесть «Ангстрема-3» в том, что в нем для оценки подобного «лавинного эффекта» на 4 факультете и в Спецуправлении еще в конце 70-х годов был разработан строгий математический аппарат, опирающийся на алгебру, на теорию групп, колец и полей. Об этих результатах я уже упоминал в предыдущей главе, посвященной шифрам на новой элементной базе, вот, вкратце, их суть.
 
1.       В шифрах, использующих операции в кольце Z/256 и подстановки p из S256, лавинный эффект определяется матрицей частот встречаемости разностей переходов ненулевых биграмм P(p) размера 255x255.
2.       Лавинный эффект будет тем лучше, чем меньше нулей в этой матрице. Хорошими следует считать такие подстановки, матрицы которых, возведенные в квадрат, не содержат нулей.
3.       При случайном и равновероятном выборе подстановки из всей симметрической группы S256, общее количество подстановок в которой составляет огромную величину 256! – произведение всех чисел от 1 до 256, вероятность выбрать хорошую подстановку стремится к 1.
4.       Существуют примеры самых плохих подстановок, это линейные подстановки.
5.       Теоретически подсчитано минимально возможное количество нулей в матрице P(p).
 
Вопрос же о том, существуют ли подстановки с минимально возможным числом нулей в матрице P(p), оставался открытым до конца 1983 года.
 
*****
 
-          Работайте дома. Если Вы будете часто здесь появляться, то диссертации не напишите.
 
Так напутствовал меня мой научный руководитель Б.А., который сам заканчивал 4 факультет в числе первых его выпускников, а сейчас уже защитил докторскую диссертацию и жил в мире групп, колец и полей. Это был бальзам на мою душу! Нет этого бессмысленного высиживания до 6 часов вечера, пустых разговоров ни о чем, нет смертельно опасной столовой-травиловки. Мысли раскрепощены, нет интеллектуального насилия, все проблемы, казавшиеся неразрешимыми, вдруг как-то сами стали успешно разрешаться. А что за проблемы?
Итак, мои творческие планы связаны с шифрами на новой элементной базе. Это новая тема и непаханое поле для деятельности. Основное отличие этих шифров от традиционных балалаек – наличие в них подстановки (или даже нескольких подстановок) из S256. Эти подстановки определяют криптографические качества шифров, они же дают возможность строить очень простые и высокоскоростные схемы, поэтому фундаментальные исследования шифров на новой элементной базе нужно начинать с изучения подстановок. Нужно постараться получить наиболее полную картину их свойств, ответить на типовые вопросы, например:
 
-          какие подстановки считать приемлемыми, а какие неприемлемыми для использования в шифрах на новой элементной базе и почему;
-          как описать какие-то особенные классы подстановок и в чем будет их особенность;
-          как лучше использовать подстановку в схеме, где ее целесообразнее расположить и почему;
 
И, наконец, надо попробовать дать ответ на конкретный практический вопрос: а что же делать со схемой «Ангстрем-3»? Как ее модернизировать, чтобы, сохранив простоту и высокую скорость реализации, обеспечить гарантированную стойкость?
Когда я поведал о своих замыслах Б.А., он сразу же стал пытаться приделывать к подстановкам теорию групп. Он витал в групповых облаках, а моей задачей было приземлять его фантазии на грешную подстановочную землю. И, в общем, такой дуэт оказался достаточно успешным.
Для начала мы попытались описать какой-нибудь класс подстановок p, для которого было бы гарантировано, что показатель 2-транзитивности множества Gp минимален и равен 3. Я надеюсь, что читатель припоминает упоминавшуюся ранее в этой книге матрицу частот встречаемости разностей переходов ненулевых биграмм P(p) и условие достижения 2-транзитивности за 3 шага: эта матрица, возведенная в квадрат, не должна содержать нулей. Я пытался описать класс подстановок, у которых полностью ненулевые средние строка и столбец, наличие такого «креста» дает гарантию того, что квадрат матрицы будет полностью положительным, без нулей. Б.А. сразу же стал пытаться найти и пристроить к этой ситуации какие-то аналогии из известных ему экзотических групп. Несколько попыток оказались безрезультатными и моей задачей было обоснование того, что этот класс групп совсем непригоден. Своего рода тотальное опробование всех подстановок, каким-то пусть даже косвенным образом связанных с изначальными. Б.А., как умудренный опытом рыболов, выискивал места, где могли водиться хорошие подстановки, а я закидывал в этих местах свою блесну.
И вот однажды клюнула такая подстановка, о которой даже сейчас, спустя 20 лет, я вспоминаю с нескрываемым удовольствием. Читатель, наверное, помнит про мое обещание привести один очень красивый результат про подстановки с минимальным числом нулей в матрице P(p). Настало время исполнить обещанное.
Пусть N – такое число, что N+1 – простое, q - примитивный элемент в поле Галуа GF(N+1), т.е. образующий элемент циклической мультипликативной группы этого поля.
Пусть p - преобразование множества Z/N вида:
 
p(х) = logq(qx+rÅr), еслиqx+rÅr¹0,
p(х) = logqr, еслиqx+rÅr=0,
 
где r - произвольный ненулевой элемент поля GF(N+1), r – произвольный элемент из Z/N, Å - операция сложения в поле GF(N+1). Тогда преобразование p является взаимно-однозначным на множестве Z/N, т.е. является подстановкой из симметрической группы SN.
Это утверждение достаточно очевидно, поскольку q - примитивный элемент поля GF(N+1), т.е. множество значений q,q2,…,qN совпадает со множеством {1,2,…,N} – мультипликативной группой поля GF(N+1), а логарифмирование – операция, обратная возведению в степень. Все проблемы с нулем подправляются вторым условием: p(х) =logqr, если qx+rÅr=0.
Такие подстановки естественно назвать логарифмическими, а точку х0, при которой p0) = logqrвыколотой точкой логарифмической подстановки p.
Здесь и всюду далее нам будут встречаться два разных типа арифметических операций сложения и вычитания: в кольце Z/N и в поле GF(N+1). Операции в кольце Z/N будем обозначать обычными символами “+” и “-“, а операции в поле GF(N+1) – Å  и ㊀ соответственно.
 
Теорема 1.
Пусть p – логарифмическая подстановка, х1¹х2, х12ÎZ/N, i – произвольный ненулевой элемент кольца Z/N. 
Тогда если ни одна из точек х1+i,x12+i,x2 не является выколотой, то p1+i)- p(x1)¹ p2+i)- p(x2).
Доказательство.
Предположим, что p1+i)- p(x1)= p2+i)- p(x2), тогда qp(х1+i)- p(x1)=qp(х2+i)- p(x2).
Поскольку все точки не являются выколотыми, то отсюда вытекает, что (qх1+i+rÅr)(qх2+rÅr)=(qх2+i+rÅr)(qх1+rÅr).
Раскрывая скобки и сокращая одинаковые члены в левой и правой частях равенства, получаем
 r (qx1+i+rÅqx2+r)= r(qx2+i+rÅqx1+r)
Поскольку r - ненулевой элемент, то отсюда вытекает, что
qx1+r(qi㊀ 1)= qx2+r(qi㊀ 1)
Поскольку i – произвольный ненулевой элемент Z/N, а q - примитивный элемент GF(N+1), то qi¹1, откуда вытекает, что х12.■
 
Теорема 2. Пусть p – логарифмическая подстановка.
Тогда для любого ненулевого значения iÎZ/N\{0} из условия, что ни одна из точек x, x+i не является выколотой вытекает, что p(х+i)- p(x) ¹ i.
Доказательство.
Пусть p(х+i)- p(x) = i. Тогда qp(х+i)- p(x)= qi, откуда qx+r+iÅr=qi(qx+rÅr), следовательно, r=rqi. Отсюда следует, что i=0. ■
 
Раскинулось поле широко! Операции возведения в степень и логарифмирования в конечном поле позволили ловко избавиться от неопределенности в разности значений подстановки и легко, просто элементарно решить задачу построения матрицы P(p) с минимальным числом нулей. Заметим, что если в определении логарифмических подстановок отказаться от условия, что r - произвольный ненулевой элемент поля GF(N+1), то при r=0 мы получаем обычные линейные подстановки, у которых число нулей в P(p) максимально!
Осталось совсем чуть-чуть: разобраться с выколотой точкой.
Для произвольного ненулевого фиксированного iÎZ/N рассмотрим отображение множества Z/N в Z/N вида:
mi(х) = p(х+i)- p(х),
где p - логарифмическая подстановка. Тогда, в силу теоремы 1, количество различных значений в множестве {mi(х), xÎZ/N\{x0,x0-i}}равно мощности этого множества, т.е.N-2, причем, в силу теоремы 2, это множество в точности совпадает с {Z/N\{i}}. В частности, при любом i¹N/2 существует такое значение х,
xÎZ/N\{x0,x0-i}, что mi(х)=N/2.  
Теорема 3. Пусть p – логарифмическая подстановка.
Тогда если при некотором i¹N/2 в i-ой строке матрицы P(p) справедливо piN/2>1, то эта строка не содержит нулевых элементов.
Доказательство.
В силу теоремы 2 достаточно доказать, что pii¹0. Условие piN/2>1означает, что либо mi0)=N/2, либо mi0-i)=N/2. Зафиксируем то, которое равно N/2, а другое оставшееся значение обозначим через m. Суммируя, как и ранее мы уже делали в этой книге, значения mi(х) по всем xÎZ/N, получаем:
N/2(N-1) – i + m + N/2 = 0.
Отсюда вытекает, что m=i, следовательно, pii¹0. ■
 
По коням! Пора заняться средней строчкой.
Начнем с самого любимого элемента – pN/2,N/2. Ранее мы уже отмечали, что этот элемент должен быть всегда четным (рассуждения для случая N=2n легко обобщаются для произвольного четного N). Следовательно, в логарифмической подстановке возможны только два значения pN/2,N/2: 0 или 2. Допустим, что pN/2,N/2=2. В силу теоремы 2 эти значения может давать только выколотая точка x0 и x0+N/2, т.е. 
p0+N/2)- p0)= p0+N/2+N/2)- p0+N/2)= p0)- p0+N/2)=N/2.
Отсюда вытекает, что 2p0+N/2)=2p0).
Рассмотрим два случая.
1.       r=1, следовательно, p0)=0. Тогда p0+N/2)=N/2. Имеем:
qp(х0+N/2)= qN/2Þ qx0+N/2+rÅr=qN/2 Þ qN/2(1㊀ qx0+r)= rÞ qN/2(1År)= rÞ 2qN/2 = 1.
Возводя обе части последнего равенства в квадрат и учитывая, что qN=1, получаем такое равенство возможно только в тривиальном поле из 3 элементов.
2.       r¹1, следовательно, p0) =N/2, p0+N/2)=0, откуда
qp(х0+N/2)= 1Þ qx0+N/2+rÅr=1Þ r(1㊀ qN/2)= 1Þ qN/2= 1㊀ r-1.
Возводя это равенство в квадрат, получаем значение r:
r=2-1
С учетом условия p0) =N/2 получаем: logq2-1 = N/2, откуда 2-1 =qN/2Þ2-2 =1. Такое также возможно только в тривиальном поле из 3 элементов.
Следовательно, во всех реальных практически значимых случаях pN/2,N/2=0. Тогда найдется по крайней мере одна строка i, в которой pN/2,i³2, и по теореме 3 в ней не будет нулей. Общее число нулей в такой матрице, с учетом уже упоминавшейся ее симметричности, будет равно N-3. Это минимально возможное количество нулей и оно оказалось достижимым!
Заметим, что подстановка, обратная к логарифмической, также будет логарифмической. Действительно, если p(х) = logq(qx+rÅr), то qp (х)= qx+rÅr, откуда
х= logq(qp (х)-rÅr1), где r1 = (㊀ r)q-r. Следовательно, p-1p(х) = logq(qp (х)-rÅr1). При этом qp (х)-rÅr1=(qx+rÅr)q-rÅr1=qx ¹ 0. Для случая х=х0 справедливо: p0)= logqr, при этом qx0=(㊀ r)q-r, откуда х0 = p-1p0) = logq((㊀ r)q-r) = logqr1

Collapse )


Ягодка

Криптография и свобода. Пятилетка пышных похорон. Глава 3. Логарифмические подстановки. Часть 2.

Оригинал взят у kolkankulma в Криптография и свобода. Пятилетка пышных похорон. Глава 3. Логарифмические подстановки. Часть 2.
Оригинал взят у mikhailmasl в Криптография и свобода. Пятилетка пышных похорон. Глава 3. Логарифмические подстановки. Часть 2.
 
Осталось построить в явном виде логарифмическую подстановку. Заметим, что условие N+1 – простое число выполняется для практически очень важного случая N=256, следовательно, логарифмические подстановки заведомо существуют при N=256. Условию N+1 - простое число удовлетворяет также N=16 и именно для этого значения мы сейчас и построим логарифмические подстановки, предоставляя заинтересованному читателю возможность построить логарифмические подстановки при N=256 самостоятельно.
В качестве примитивного элемента поля GF(17) выберем q=3, а также положим r=1, r=0. Составим таблицу степеней значения q:
 
i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
qi
1
3
9
10
13
5
15
11
16
14
8
7
4
12
2
6
 
Используя эту таблицу, построим логарифмическую подстановку p
 
х
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
p(х)
14
12
3
7
9
15
8
13
0
6
2
10
5
4
1
11
 
и ее матрицу Р(p)
 
 

Collapse )


Ягодка

Криптография и свобода. Пятилетка пышных похорон. Глава 3. Логарифмические подстановки. Часть 3.

Оригинал взят у kolkankulma в Криптография и свобода. Пятилетка пышных похорон. Глава 3. Логарифмические подстановки. Часть 3.
Оригинал взят у mikhailmasl в Криптография и свобода. Пятилетка пышных похорон. Глава 3. Логарифмические подстановки. Часть 3.
  
 1234567891011121314

15

10121121111111111
2111111121111111
3210111111211111
4111021211111111
5111201112111111
6211110111111211
7111211011121111
8121111101111121
9111121110112111
10112111111011112
11111111211102111
12111111112120111
13111112111111012
14111111121111111
15111111111211210
 
Это подстановка с минимально возможным числом нулей в матрице Р(p).
 
Это был, пожалуй, мой самый красивый математический результат. Но, к большому сожалению, логарифмические подстановки так и не нашли достойного применения в криптографии. Почему? Да очень просто – их мало. Помните фразу про долговременные ключи-подстановки в дисковых шифраторах: «Их не опробуют. Их покупают.» Если в схемы типа «Ангстрем-3» мы будем ставить только логарифмические подстановки, то опробование всевозможных вариантов подобных подстановок сведется к опробованию всего лишь трех элементов: q - примитивного элемента в поле Галуа GF(257), r - произвольного ненулевого элемента поля GF(257) и r – произвольного элемента из Z/256. Это – копейки, совершенно ничтожная, по криптографическим меркам, величина. Если же выбирать подстановку случайно и равновероятно из всей симметрической группы S256, то общее число опробуемых вариантов будет совершенно астрономической величиной 256!, намного превосходящей психологически недосягаемую в криптографии величину 10100.
Но для шифров на новой элементной базе логарифмические подстановки позволили полнее представить общую картину того «лавинного эффекта», к достижению которого так стремятся криптографы всего мира.
Для меня же это означало еще и то, что путь к защите диссертации был открыт, несмотря на пессимистические прогнозы Степанова и проповедуемый им «патриотизм к отделу». Но на Степанова они подействовали не как на ученого, а как на администратора: красивый математический результат получен вышедшим из под его контроля сотрудником «на стороне», на кафедре криптографии Высшей Школы КГБ. Незамедлительно последовали выводы: наказать, чтобы не высовывался и чтобы другим неповадно было изменять родному отделу! Впрочем, об этом чуть ниже.

Collapse )



Ягодка

Воровство госчиновником 100 миллионов долларов не относится к частной жизни

Оригинал взят у santalusia в Воровство госчиновником 100 миллионов долларов не относится к частной жизни
Оригинал взят у maxvl в Суд обязал «Новую газету» опровергнуть статью о связи Сечина с суперъяхтой «Принцесса Ольга»

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

Суд также обязал удалить статью с сайта газеты. Представители Сечина  заявили, что автор в форме «скрытого утверждения» распространил недостоверную и порочащую Сечина информацию.Эта публикация не является общественно значимой, так как «Сечин непубличный человек и не является влиятельным общественным деятелем», — заявили представители главы «Роснефти».

Как утверждала «Новая газета», на яхте стоимостью не менее 100 миллионов долларов регулярно отдыхала Ольга Сечина — предполагаемая жена Игоря Сечина. Аренда такой яхты, по оценкам специалистов, может стоить до миллиона долларов в неделю.

В опубликованной 31 июля тексте под заголовком «Секрет «Принцессы Ольги. Как руководитель „Роснефти“ Игорь Сечин связан с одной из самых роскошных яхт в мире?» газета сопоставила фотографии и данные геолокации из инстаграмма Ольги Сечиной с фотографиями суперъяхты «Принцесса Ольга» и данными от ее перемещениях. Яхты на фотографиях Сечиной оказалась похожа на одну из самых дорогих яхт мира.

Смотрите также: «Принцесса Ольга» длиной 86 метров. Что известно о предполагаемой яхте Сечиных

После этой публикации Ольга Сечина подала иск к «Новой газете» с требованием удалить публикацию с сайта газеты и уничтожить все печатные номера с текстом расследования. По ее мнению, автор расследования Роман Анин и главный редактор «Новой газеты» Дмитрий Муратов нарушили ее право на неприкосновенность частной жизни. «Роснефть» назвала расследование «заказной кампанией».

Смотрите также: Корректор Сечин. Как глава «Роснефти» воюет с журналистами

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

Останкинский суд Москвы обязал газету «Ведомости» удалить с сайта издания статью уничтожить остатки тиража номера газеты со статьей.

«Роснефть» также попросила взыскать с РБК репутационный вред в размере 3,124 миллиарда рублей за статью «Сечин попросил правительство защитить “Роснефть” от ВР».В материале РБК говорится, что Сечин попросил правительство ограничить права покупателей приватизируемых акций «Роснефти». После публикации статьи в «Роснефти» назвали ее ложной, ни на чем не обоснованной и потребовали опровергнуть.


https://tvrain.ru/news/olgi_net-418668/



Ягодка

Юрий Ларичев о Русской истории

Оригинал взят у karhukallio в Юрий Ларичев о Русской истории
Оригинал взят у westaluk в Поговорим о Русской истории.
Оригинал взят у yar46 в Поговорим о Русской истории.
Так уж случилось, что мы в родной истории гости. От нас самих зависит как шаг за шагом приблизиться к истокам и стать родной истории полноправными хозяевами.
Всем гостям здравия.

ПУТЕВОДИТЕЛЬ ПО ЖУРНАЛУ YAR46
Буквы русской Азбуки как наша история
Просвещение славян по слову лорда Горинга
Документы великая сила, но без буквы они…
Кого просвещал Кирилл и что создал
Глаголица и кириллица как инструмент политики
Письменность славян и регион Рюген
Кратко о памяти Кирилла и Мефодия
Просвещение славян от Римской империи
Легенда о Глаголице. Часть 1. Письмо славян
Легенда о Глаголице. Часть 2. Внешняя политика
Легенда о Глаголице, Часть 3. Контакт и русская Азбука
«Двадцатью четырьмя рунами [началами, архетипами], давая им форму и образ, смешивая их и комбинируя различными способами, Род сотворил всё то, что есть, что имеет форму и всё то, что будет её иметь. Именно с помощью этих рун Род, да будет Он благословен, утвердил Своё Имя Возвышенное и Незыблемое».
Это формулировка полевого генома и русской национальной идеи. Национальная идея у нас всегда была, да стёрли нам память.
А те два знака, которых недоставало у каббалистов (22 священных буквы против 24 русских), обозначают Род, Геном. Древнейший славянский бог.
От русских волхвов не осталось книг, потому что исконная языческая праведная (до ВЕДная) вера славян слишком внутренняя, слишком сложная. Она для избранных. Это даже не вера, а строгая уверенная наука живого языка (волновая генетика) без брехливого суеверного мифотворчества идеологии властвования. Её трудно изложить в виде священного писания, да и не нужно. И можно исчерпывающе записать на трамвайном билете. Не на бумаге, на небесах она записана. Что от людей ― в книжках. Что от Бога ― в инстинктах. А таинственная гиперборейская Русь ушла в вечность. Автор строк Юрий Ларичев.