September 6th, 2016

Ягодка

Кому мерещится предательство, пусть вспомнит, как и кого предал он сам

Оригинал взят у matholimp в Кому мерещится предательство, пусть вспомнит, как и кого предал он сам
Я намеренно воздержался от записей в ЖЖ как 19 августа (которое дружно отпраздновали практически все «демократы»), так и 22. Как и четверть века назад, эти дни я провёл на огороде посреди дикого леса (в 1991г. в Юрихе в Ивановской области, а 2016 – в Кольканкульме на Карельском перешейке) и не стремился на митинги или баррикады.
Первые сообщения о ГКЧП не вызвали у меня желания выступить в поддержку какой-либо из сторон. Янаев, Крючков, Язов и другие ГКЧПисты не вызывали у меня ни малейших симпатий, но и к противоположной стороне сочувствия у меня тоже не было. В конфликте Ельцина с Горбачёвым я всегда поддерживал сторону второго, но и его позиция не была мне близкой.
Вплоть до самого конца 1991г. я оставался сторонником сохранения СССР и даже наивно пытался убедить в этом своих многочисленных балтийских друзей. Весной 1990г. я шёл на выборы народных депутатов РСФСР с программой, включавшей переустройство СССР по принципу снизу вверх. В противоположность Горбачёву, поднявшему статус мелких автономий до союзных республик, я считал оптимальной более сбалансированную структуру административно-территориального деления, в которой из состава РСФСР в отдельную союзную республику выделялась бы её азиатская часть, а Балтия, Кавказ (включая северный) и Средняя Азия объединялись бы в федеративные республики. Я был (и остаюсь) противником приватизации госсобственности, но считал необходимым переориентировать её с военных нужд на социальные. Я предлагал разделить бесконтрольный «общак» госбюджета на многочисленные целевые фонды с тем, чтобы каждый налогоплательщик мог сам выбирать направление для поступления своих отчислений (вплоть до «точечного»: на поддержку конкретной школы или транспортного маршрута) и отслеживать затем их использование.
Подобно Явлинскому и ещё очень многим, я мог бы сейчас говорить, как прекрасно мы жили бы сейчас, если бы реализовалась именно моя программа. Единомышленниками мы были только по отношению к КПСС, но после свержения партийной власти каждый хотел пойти своей дорогой. Нелепо годы спустя обвинять бывших соратников по общей борьбе в том, что конечные цели с самого начала у нас были разные.
А противники и их сторонники пытаются переписать историю, у которой пока ещё много живых свидетелей. Появляются многочисленные запоздалые интервью, в которых ГКЧПистов представляют бескорыстными защитниками страны. Нет, защищали они только собственные кресла, которых должны были лишиться после подписания нового союзного договора. Об этом говорят их собственные признания по делу ГКЧП и мемуары, написанные уже после амнистии. Фактически же именно путч ГКЧП отвратил большинство советских граждан от собственной страны. В декабре 1991г. в поддержку рухнувшей страны выступили считанные единицы: народный депутат Бабурин да карликовая партия Травкина.

Ягодка

Криптография и свобода. Колея. Глава 4. Шифры на новой элементной базе.

Оригинал взят у kolkankulma в Криптография и свобода. Колея. Глава 4. Шифры на новой элементной базе.
Оригинал взят у mikhailmasl в Криптография и свобода. Колея. Глава 4. Шифры на новой элементной базе.
 
Глава 4
Шифры на новой элементной базе
 
                Про шифры на новой элементной базе я уже несколько раз упоминал в этой книге, но в основном абстрактно: были заложены основы, велись теоретические разработки. А как пощупать их руками? Что в них было действительно нового?
                Здесь надо немного окунуться в ту «докомпьютерную» эпоху. Что такое микропроцессор – представление об этом было весьма расплывчатое. Что-то такое, что реализовано с помощью никому тогда не ведомого процессора, но только очень маленького, размером с копеечную монету. Живьем микропроцессор мало кто видел, только общие сведения: способен выполнять некоторые операции с двоичными векторами, достаточно быстро по сравнению с типовыми логическими элементами. Один раз, еще в Высшей Школе КГБ, нам, рассказывая про микропроцессоры того времени, сказали, что их стоимость сравнима со стоимостью золота, сопоставимого по весу с микропроцессором.
                Сначала, как только я пришел на работу в отдел Степанова, там загорелись идеей создать специализированный криптографический процессор, ориентированный на выполнение определенных криптографических преобразований. Что это должны быть за преобразования – тоже не было единого мнения. Преобразования для системы с открытым распределением ключей? Или для симметричного шифрования, без которого система с открытым распределением ключей теряет всю свою эффективность? В общем, начальный период создания криптографического процессора прошел в абстрактных криптографических спорах, которые были спущены на грешную землю одним простым вопросом, заданным спорщикам инженером, приглашенным из Зеленоградского завода Ангстрем, на котором предполагалось изготавливать эти процессоры:
 
                - А какой толщины должен быть слой лакового покрытия вашего процессора?
 
                Все криптографы сразу же выпали в полный осадок. Ответить на вопрос о толщине слоя лакового покрытия никто не смог, абстрактный криптографический процессор, рожденный в умах теоретиков, так там и остался.
                Но идеи шифров, реализуемых с не с помощью какого-то надуманного криптографического микропроцессора, а с помощью начинавших появляться в то время самых обычных микропроцессоров для портативной бытовой электроники, оказались весьма живучими. Все очень просто: есть выпускаемые промышленностью микропроцессоры, выполняющие стандартные арифметические операции, их производительность невелика, но они очень дешевы. Задача криптографов - приспособить эти стандартные процессоры для выполнения криптографических преобразований. Не гора должна идти к Магомету, а Магомет к горе.  
Однажды к нам в гости пожаловали ребята из НИИ Автоматики. Это был один из ведущих институтов Министерства радиоэлектронной промышленности, который занимался разработкой шифрующих устройств и в котором работало много выпускников 4 факультета. В теории 8 управление КГБ должно было выполнять только экспертные функции, разработку шифраторов должна была проводить промышленность, но в реальной жизни все тесно переплеталось, наш отдел постоянно выдавал какие-то идеи для новых схем, масса людей писала на этом диссертации, поэтому провести четкую грань между разработкой и экспертизой часто было невозможно.
Эти ребята тоже занимались разработкой шифров на новой элементной базе. Но они были практиками, для них первичным было «железо», реально существующие в то время микропроцессоры, под которые надо было придумать криптосхему, в которой все преобразования осуществляются не с традиционными битами, а сразу с байтами, 8-мерными двоичными векторами.
 
-          Мы постарались придумать максимально простую для реализации криптосхему. Вы можете прикинуть оценки ее стойкости?
 
Ребята молодые, может быть старше меня года на 3 - 4. Один из них уже начальник сектора, пишет диссертацию. Эта тема – шифры на новой элементной базе – интересует многих. На 4 факультете кафедра математики подготовила два солидных отчета о проведенных исследованиях по аналогичной теме, несколько человек уже защитились. Новое, перспективное направление, что же оно из себя представляло?
Здесь я вынужден извиниться перед читателем этой книги, не имевшим ранее никаких дел с математикой. Сейчас придется немного залезть в теорию групп и теорию подстановок, со своими специфическими терминами: симметрическая группа, циклическая подстановка, свойство 2-транзитивности и т.п. Может быть неискушенный читатель пробежит эту часть «по-диагонали», не вдаваясь особо в подробности и не забивая себе в голову всех этих премудростей. Но в математике, как и в любой другой области науки, иногда удается получить красивый результат, и, чтобы оценить его красоту, надо немного вникнуть в детали, подробности, предшествующие его получению. Так что читатель, окунувшийся в начинающиеся ниже математические дебри (не такие уж и сложные, как может показаться на первый взгляд!), в конце концов будет вознагражден одной красивой «изюминкой». 
Большинство традиционных электронных шифраторов реализовано с помощью «балалаек», работающих с битами. В этих «балалайках» в ячейки регистра сдвига могут быть записаны только два элемента – 0 или 1, такой регистр сдвига называется регистром сдвига над полем GF(2) - полем Галуа из двух элементов. Операции с битами тоже весьма простые: сложение и умножение по модулю 2, а также отрицание. Все методы анализа подобных «балалаек» ориентированы на двоичные операции, на операции в поле GF(2).
Если же мы вместо битов переходим к байтам, то появляется много нового. Традиционные операции с байтами можно осуществлять несколькими способами. Например, сложение и вычитание могут быть с переносом или без переноса, т.е. или это будут операции в кольце вычетов по модулю 256, или покоординатное сложение бит. Но самое интересное обобщение происходит с операцией отрицания. Отрицание (инверсия) бита – это фактически подстановка на множестве из 2 элементов. Когда всего 2 элемента, то мощность симметрической группы S2 составляет всего 2! = 2, всего две подстановки: тривиальная единичная (ничего не меняется) и инверсия, когда 0 переходит в 1, а 1 – в 0. Мощность же симметрической группы S256 составляет 256! – совершенно фантастическое число. Введение подстановки в регистр сдвига, работающий с байтами, а не с битами, переворачивает все привычные методы криптографического анализа. Совершенно другие операции, а следовательно, нужны и другие подходы к анализу и оценке стойкости таких схем, чем те, которые использовались в традиционных двоичных «балалайках».
С чего начала кафедра математики на 4 факультете? С самого простейшего преобразования, осуществляемого с n-мерными двоичными векторами, с преобразования типа (Gp)k, где G – группа, порожденная циклическим сдвигом (G = <g>, g =(0,1,…,2n-1)-циклическая подстановка), p - некоторая фиксированная подстановка из S2n, а k – некоторое целое число. 
Если здесь перейти от математических терминов из теории групп к обычной криптографической терминологии, то преобразование типа (Gp)k – это следующий узел.
 
  
 

Преобразования типа (Gp)- это, фактически множество подстановок вида gx1p gx2p… gxkp, и задачей кафедры математики было обосновать какие-то свойства подобного множества, найти их зависимости от подстановки p. Типичная криптографическая ситуация – когда в таком узле входное слово x1,x2,…xkявляется ключевым параметром, требуется найти подходы к его определению по нескольким известным переходам в реализуемой подстановке.
Кафедра начала с изучения группы <g, p >, т.е. группы, порожденной двумя подстановками: циклическим сдвигом g и фиксированной произвольной подстановкой p. Это естественное обобщение преобразования (Gp)k, предельный случай. Свойства группы <g, p > дают ответ на вопрос, что в принципе можно ожидать от нашего преобразования при увеличении длины k до бесконечности. Можем ли мы таким путем получить все подстановки или же есть какие-то запреты?
Оказалось, что если случайно и равновероятно выбрать из всей симметрической группы фиксированную подстановку p, то с вероятностью, близкой к 1, группа
<g, p > будет совпадать со всей симметрической группой, т.е. запретов не будет. Те подстановки p
, для которых это не так, очень часто легко определяются, например,
p
=g, а также любая линейная подстановка, реализующая преобразование вида
p(x) = ax+b, где a и b – фиксированные элементы из Z/2n.
Дальше, естественно, стали возникать вопросы: а как скоро мы сможем достичь симметрической группы? Какова будет мощность слоя (Gp)k при некотором значении k, например, при k=2 или при k=3? При каком k множество (Gp)k станет
2-транзитивным, т.е. по имеющимся в нем подстановкам любая пара (y1,y2), в которой y1¹y2, сможет перейти в любую пару (z1,z2), в которой z1¹z2? Что в общем случае можно будет сказать про обобщение 2-транзитивности – m-транзитивность?
За свойство 2-транзитивности взялись основательно, чувствовалось, что здесь могут быть интересные криптографические зацепки: если 2-транзитивность отсутствует, то появляются запреты переходов биграмм текста, широкое поле деятельности для криптоаналитика. Например, если p - упомянутая выше линейная подстановка, то для любой пары (y1,y2) будет справедливо соотношение:
p(y1)- p(y2) =  (ay1+b) - (ay2+b) = a(y1-y2)
В этом случае при применении подстановки p сохраняется соотношение между разностями знаков, а поэтому кратной транзитивности заведомо не будет.
А если p - не линейная, а произвольная подстановка? При каком минимальном значении k множество (Gp)k может достичь свойства 2-транзитивности? Всего имеется 2n(2n-1) различных пар (z1,z2), в которых z1¹z2, а количество различных подстановок в (Gp)k не превосходит (2n)k. Следовательно, свойства 2-транзитивности можно достичь только при k³2. Можно ли при k=2?
Рассмотрим множество подстановок (Gp)2. Это множество реализует всевозможные преобразования произвольного значения t в значение s по формуле
s = p (p (t+x1)+x2) при всевозможных x1,x2. Если бы это множество было 2-транзитивным, то для любых заранее фиксированных s1,s2, t1,t2 , в которых s1¹s2 и t1¹t2, система уравнений:
s1 = p (p (t1+x1)+x2)
s2 = p (p (t2+x1)+x2)
имела бы решение относительно x1,x2, а, следовательно, поскольку p - подстановка, то и система
s1 = p (t1+x1)+x2            (1)
s2 = p (t2+x1)+x2
имела бы решение для любых заранее фиксированных s1,s2, t1,t2, в которых s1¹s2 и t1¹t2
Отсюда, вычитая одно уравнение из другого, мы приходим к одной очень важной криптографической характеристики подстановки p - матрице частот встречаемости разностей переходов ненулевых биграмм P(p) размера (2n-1)x(2n-1), а именно, на пересечении i-ой строки и j-го столбца в этой матрице стоит значение pij - число решений системы уравнений относительно x и y:
x-y = i                         (2)
p(x) - p(y) = j
где i, j ¹ 0.
Если при каких-то i, j ¹ 0 pij =0, то это означает, что при заранее фиксированных s1,s2, t1,t2, в которых s1¹s2 и t1¹t2, а также t1-t2 = i, s1-s2 = j, система (1) заведомо не имеет решения, ибо в противном случае имела бы решение и система (2).
Заметим, что pij = p(2n-i)(2n-j). Действительно, каждому решению (x1,y1) системы (2) можно поставить во взаимно однозначное соответствие решение (x2,y2)=(y1,x1)  системы
x-y = 2n-i
p(x) - p(y) = 2n-j
если домножить на –1 оба уравнения (2).
Из системы (2) очевидно вытекает, что число ее решений равно числу значений y, при которых
p(y+i) - p(y) = j           (3)
Если каждому решению (x1,y1) системы (2) поставить во взаимно-однозначное соответствие пару (x2,y2) = (p-1(x1),p-1(y1)), то такая пара будет решением системы
x-y = j                         (4)
p-1(x) - p-1(y) = i
Следовательно, число решений системы (2) будет равно числу значений y, при которых
p-1(y+j) - p-1(y) = i           (5)
Из (3) очевидно вытекает, что сумма всех элементов pij в i-ой строке при любом i равна 2n. Аналогично, из (5) вытекает, что сумма всех элементов pij в j-ом столбце при любом j равна 2n.
Поскольку размер P(p) равен (2n-1)x(2n-1), то из условия, что сумма всех элементов pij в i-ой строке при любом i равна 2n следует, что если бы P(p) не содержала нулей, то в любой ее строке все элементы были бы равны 1, кроме одного, равного 2. Аналогично получаем, что в этом случае в любом столбце должны быть все элементы 1, кроме одного, равного 2.
Если при некотором y выполняется
p(y+2n-1) - p(y) = 2n-1,     (6)
то, поскольку 2n–2n-1 = 2n-1, то (6) будет справедливо и при значении y1 = y+2n-1. Таким образом, элемент p(2n-1)(2n-1) не может быть нечетным.
Предположим, что некоторая i-я строка целиком ненулевая. Это означает, что среди значений j0,j1,…,j2n-1, получаемых по формуле
jk =p(k+i)- p(k)             (7)
содержатся все ненулевые элементы из Z/2n, а какой-то один элемент встретился ровно 2 раза.
Просуммируем соотношение (7) по всем k от 0 до 2n-1. Поскольку p - подстановка, то в правой части суммы получается 0, следовательно, сумма всех значений jkтакже должна быть нулевой.
Но среди j0,j1,…,j2n-1 содержатся все ненулевые элементы из Z/2n, а какой-то один элемент встретился ровно 2 раза. Поскольку сумма (по модулю 2n) всех ненулевых элементов кольца Z/2n равна 2n-1(2n-1) = 2n-1, то элементом, встретившимся два раза, должно быть 2n-1.
Тогда, в силу свойства pij = p(2n-i)(2n-j) для любого значения i должно выполняться
pi2n-1 = p(2n-i)2n-1 = 2
и при i¹2n-1 получается, что в 2n-1 столбце как минимум 2 элемента равны 2. Следовательно, если некоторая i-я строка при i¹2n-1 целиком ненулевая, то 2n-1 столбец заведомо содержит хотя бы один нулевой элемент, т.е. множество (Gp)2 не является 2-транзитивным ни при какой подстановке p.
И еще отсюда сразу же вытекает, что общее число нулей в матрице P(p) не может быть меньше, чем 2n-3. В этом случае в матрице ровно две ненулевых строки, расположенных симметрично друг от друга, а в средней строке с номером 2n-1 ровно одно нулевое значение посередине: p(2n-1)(2n-1) = 0.
Подобными же методами легко показать, что в общем случае множество (Gp)k является 2-транзитивным при k>2 в том и только том случае, когда матрица P(p)k-1 не содержит нулей. В частности, множество (Gp)3 является 2-транзитивным тогда и только тогда, когда матрица P(p)2 не содержит нулей.
 
Стало ясно, в каком направлении вести математические раскопки теории шифров на новой элементной базе: изучать матрицы P(p) для различных подстановок p. Здесь сразу же выделялись плохие подстановки – это линейные преобразования вида
p(x) = ax+b
В этом случае при любом фиксированном i¹0 система (2) имеет решение только при одном значении j¹0, такая матрица заведомо не будет положительной ни в какой степени и свойство 2-транзитивности недостижимо. Число нулей у такой матрицы будет максимальным.
А можно ли построить подстановки с минимально возможным числом нулей в матрице P(p)? Этот вопрос уже гораздо интереснее, простого и тривиального ответа на него нет. Пока. Но в следующих главах этой книги ситуация проясниться и в конечном итоге получится очень красивый результат.
 
Но это больше теоретические дебри. С точки зрения практического применения гораздо важнее знать, чего можно ожидать от матрицы P(p) при случайном и равновероятном выборе p. И здесь были доказаны очень важные теоремы о том, что в среднем ненулевых элементов в этой матрице будет примерно 2/3, что с вероятностью, близкой к 1, при случайном и равновероятном выборе p матрица P(p)2 небудет содержать нулевых элементов, а группа <g,p> будет совпадать с симметрической. В общем, все то, что требуется для использования подстановки p в качестве случайного разового ключа.
 
Вот такая была предыстория работ по шифрам на новой элементной базе. А ребята из НИИ Автоматики, по мотивам всех этих результатов, придумали следующую схему блочного шифра, работающего на основе байтового регистра сдвига и использующего только самые типовые операции с байтами, которые заложены в архитектуру появлявшихся тогда микропроцессоров. Эту схему назвали
«Ангстрем-3». 
 

В ней два регистра сдвига, работающих с байтами. В первый регистр сдвига длиной 8 байт записывается 8-байтовый блок открытого текста, во второй – ключ, или как его еще можно здесь назвать входное слово, длины Т для первого регистра. Схема крутится Т тактов, после чего заполнение первого регистра выдается в качестве 8 байтового блока шифртекста. Типичный блочный шифр, все операции сложения – в кольце Z/256, реализация – изумительно простая, если писать программу, то это буквально две-три строки. 
Но программы будут позже, а пока, в 1980 году, эту схему предполагалось реализовывать аппаратно, с помощью типовых микропроцессоров, работающих с байтами. Идеи подстановки-ключа тоже появятся позже, первоначально предполагалось p выбрать и зафиксировать. А главный вопрос, который интересовал НИИ Автоматики – до какого предела можно уменьшать значение Т, количество тактов, которые должна отработать схема для зашифрования одного блока. Чем меньше Т, тем выше скорость шифрования, а это было для них определяющим фактором.
 
-          Нельзя ли выбрать Т=16?
 
Нужно подумать.
Так начиналась моя осмысленная работа в Теоретическом отделе. Перед глазами - чистая тетрадь, отчеты 4 факультета и НИИ Автоматики, сиди и думай, нельзя ли выбрать Т=16.           
 
Collapse )


Ягодка

Владимир Войнович

Оригинал взят у vuoriensaari в Владимир Войнович
Оригинал взят у karhu53 в Владимир Войнович
16 июня 1981 года указом генерального секретаря ЦК КПСС Леонида Брежнева писатель Владимир Войнович был лишен советского гражданства. Как это было обставлено, почему он уехал из СССР, зачем вернулся в 1990-м и чего он ждет от будущего, писатель рассказал Зое Световой.


Владимир Войнович. Фото: Юрий Белинский / ТАСС

— Как вы узнали, что вы больше — не советский гражданин?

— Я тогда уже жил в Мюнхене. Утром этого дня мне позвонил журналист Марио Корти с радио «Свобода». Он сообщил, что меня лишили гражданства, и хотя я этого ожидал, мне на самом деле стало жутко обидно. До этого меня как только ни ругали и ни проклинали — говорили, что я такой-сякой, враг народа, шакал, таракан. Сравнивали со всеми отвратительными животными и насекомыми, и я это все как-то пропускал мимо ушей, я знал, чего от них можно ожидать. Но тут почему-то сильно обиделся и разозлился. И написал Брежневу письмо: «Господин Брежнев, вы мои заслуги оценили незаслуженно высоко, я не подрывал престиж Советского Союза, потому что у Советского Союза благодаря усилиям его руководителей и вашему личному вкладу никакого престижа нет». И я написал что-то вроде того «нисколько не сомневаюсь, что ваши указы в скором времени будут отменены, но у меня нет уверенности, что так же скоро кончится бумажный дефицит, и, думаю, моим читателям по-прежнему придется сдавать в макулатуру 20 кг ваших произведений, чтобы получить одну мою книгу о Чонкине. Тогда был такой порядок — можно было сдать 20 кг макулатуры и за это получить право купить одну дефицитную книгу.

Collapse )



Ягодка

Уникальный по объёму клад римских монет.

Оригинал взят у imatran в Уникальный по объёму клад римских монет.
Оригинал взят у janis60 в Уникальный по объёму клад римских монет.
img914

В Испании при строительстве водопровода был найден клад, состоящий из нескольких десятков тысяч бронзовых и посеребренных монет,
отчеканенных в Римской империи III-IV веков. На монетах изображены императоры Максимиан и Константин.
Общий вес клада, который хранился в 19 закопанных амфорах, составляет порядка 600 килограммов.
Интересно, что монеты, судя по всему, были спрятаны практически сразу после чеканки и вообще не находились в обращении.
Благодаря этому они сохранились в прекрасном состоянии.
Ученые предполагают, что клад принадлежал не частному лицу, а какому-то учреждению или командованию военной крепости.
Возможно, он предназначался для выплаты жалования солдатам или чиновникам, а в амфорах монеты, вероятно, были спрятаны перед
нападением врага.
Либо же это было стационарное хранилище денег, защищенное от возможных грабителей.
Историки подчеркивают, что это самое большое однородное собрание монет Римской империи.
[Spoiler (click to open)]

Оригинал взят у villmanstrand в Уникальный по объёму клад римских монет.Оригинал взят у ieriki в Уникальный по объёму клад римских монет.