Category: компьютеры

Category was added automatically. Read all entries about "компьютеры".

Криптография и свобода. Loading... Глава 5. Фанат.

 
Глава 5
Фанат
 
Я наконец-то дорвался до компьютера! Еще первое знакомство с IBM PC XT привело меня в неописуемый восторг, стало ясно: вот именно то, к чему я привязался надолго, может быть на всю оставшуюся жизнь. Первый (игровой) этап обучения пройден, все чаще стало появляться желание реализовать все свои замыслы на РС. А это, в первую очередь, шифры на новой элементной базе, им было отдано почти десять лет жизни, появилась уверенность, какое-то подсознательное чувство, что на этом пути можно находить элегантные и очень надежные криптографические решения. С помощью РС легко сделать ключом случайную подстановку в шифре типа «Ангстрем-3», а тогда все мыслимые подходы к анализу такого шифра становятся невероятно трудоемкими, глухими, а все положительные качества – скорость и простота реализации – сохраняются. Такой регистр сдвига с неизвестной подстановкой можно использовать и для многих других криптографических целей, например, в качестве генератора случайных чисел или для функции хеширования.
Разные напыщенные начальники всегда вызывали у меня чувство неприязни, гораздо приятнее иметь дело со специалистами, людьми, отличающимися профессионализмом, преданностью своей профессии, умом, талантом, настойчивостью. А тут самому пришлось стать пусть небольшим, но начальничком, у которого в подчинении свыше 20 человек. В условиях Спецуправления 8 Главного управления КГБ это значит только и делай, что руководи, давай указания, проверяй, ругайся, разделяй и властвуй. Ну уж нет, эта суета не по мне, я сам в такие начальники никогда не лез. Но должность маленького начальничка дала две неоценимые по тем временам вещи: свой, истинно персональный компьютер и отдельный кабинет, в котором кроме меня был еще один настоящий начальник, а я - его зам. Никакой кучи народа в комнате, никто не претендует на твой компьютер, начальник (настоящий) очень любит разделять и властвовать и избавил меня от этой напасти. Я остался наедине с РС, с самым что ни на есть персональным компьютером, в спокойной и почти уединенной обстановке, сам себе режиссер. Никакая сила уже не могла оттянуть меня от моей любимой игрушки.
Сначала я погрузился в язык Assembly. Какими-то правдами и неправдами был добыт оригинал книги Питера Нортона «Программирование на языке ассемблера» с кучей примеров. Толстенная книга, но когда наглядно видишь на экране, что все запрограммировал верно, результат совпал, появляется азарт. Методика одна и та же, что в математике, что в программировании: от простейших вещей ко все более и более сложным, стараясь не перескакивать через этапы и все досконально понять. Но программирование интереснее тем, что результат конкретен и нагляден, его можно чуть ли не потрогать руками, тогда как в математике теоремы абстрактные, в них очень легко упустить какую-то цепочку при доказательстве и не заметить, что движешься в неверном направлении. В программировании уход в сторону, какие-то непонятные «глюки» выявляются гораздо быстрее, этот процесс эмоционально более интересен.
Как изменилась жизнь! Вместо скучного досиживания до 6 вечера дежурный офицер чуть ли не насильно отгонял меня от компьютера в 9 вечера, когда объект закрывался. У меня был суперсовременный по тем временам Laptop с плазменным экраном, первое подобие нынешних Notebook, только без автономного питания, но размером почти такой же, чуть побольше. Его можно было даже засунуть в сумку – невероятно для тех времен, когда еще свежи были в памяти тапочки, надеваемые на сапоги в комнате, где стояло советское чудо вычислительной техники – «Рута-110». Поражали возможности: жесткий диск – 40 Мб, это же огромная величина! Сколько программ можно на него записать! 286 процессор – насколько более быстрый, по сравнению с IBM PC XT. Сколько же на нем всего напахать можно! Да здесь какой угодно шифратор сделать можно, не связываясь ни с каким заводом, все в твоих руках.
Заработали первые ассемблеровские программы: оказывается сравнительно легко сделать свои прерывания в DOS, программировать ввод-вывод, лазить по оперативной памяти. Наигравшись вдоволь с Assembly, я занялся его старшим братом – языком С, тогда еще без всяких плюсов. 
Математик любит искать во всем логику, закономерности, разумность. Если ее не хватает в реальной жизни, то компьютер, операционная система, языки программирования дополняют этот дефицит, служат своего рода отдушиной, тем сказочным миром, который помогает легче переносить уродливость мира реального. Следовательно, чем более иррациональным будет повседневное бытие, тем больше будет тяга к компьютеру, к его удивительно логичному и разумному поведению, осмысленным действиям, внутренней логике, виртуальной действительности. Там нет тупых и невежественных генералов, очередей за мясом, совхозов и овощебаз, общественной работы и субботников, там только четкие и понятные критерии, TRUE и FALSE, единица и ноль. А специалист по компьютерам, хороший программист всегда будет востребован, при любом правителе, любой идеологии, любых начальниках. Отсюда уже недалеко и до свободы, до реальной свободы, когда пропадает этот инстинктивный трепет перед важными надутыми начальниками, не освоившими толком даже компьютерных игр.
Сидящий напротив мой начальник все время гадал: сколько нужно времени, чтобы я «сломался», ну или хотя бы мне надоел компьютер: месяц? полгода? год? Своего рода приложение к теме «Экстракт». Но все его прогнозы оказались с «глюками», компьютер засасывал меня все больше и больше. После того, как были запрограммированы и отлажены алгоритмы, реализующие шифры на новой элементной базе, захотелось сделать к ним удобный интерфейс. Ну а это уже такой простор, просто вселенная! И еще, конечно же, хотелось, чтобы мой компьютерный фанатизм принес кому-то реальную пользу, чтобы моими программами пользовались, чтобы вся эта огромная работа не пропала даром. А вот это уже в системе Спецуправления 8 ГУ КГБ СССР сделать было намного сложнее, ибо там с незапамятных времен действовали негласные правила: не высовывайся! будь как все! не проявляй лишней инициативы, она наказуема! Короче, в триаде чиновник-офицер-специалист можно было спорить только о том, что поставить на первое место: чиновника или офицера. В дальнейшем сама жизнь присудила золотую медаль (с зеленью) чиновнику, а все недовольные таким раскладом специалисты попросту разбежались кто куда. Тогда же, в конце 80-х годов, у меня еще была какая-то наивная вера в справедливость, в то, что эта система способна адекватно воспринимать те компьютерные программы и усилия по их внедрению, которые стали моим призванием, всем смыслом жизни. Как говорил Александр Солженицын, тоже, кстати, имевший отношение к криптографии, «Бодался теленок с дубом».

Collapse )

Криптография и свобода. Loading... Глава 4. Криптографические верхи не хотят, а низы не могут…

 
Глава 4
Криптографические верхи не хотят, а низы не могут…
Кибернетика – буржуазная лженаука – вылезла из своего змеиного гнезда и в конце 80-х годов поползла травить своим ядом чистые умы математиков Спецуправления 8 Главного Управления КГБ СССР. Увлечение персональными компьютерами приобрело повальный характер, причем начальный игровой этап быстро прошел. Персональные компьютеры и программное обеспечение к ним были буржуазными, идеологически вредными, но очень удобными и доступными. Они произвели очередной взрыв в советском криптографическом омуте, но только гораздо более сильный, чем открытые ключи или схема DES. Людей невозможно стало оторвать от PC, теоремы и абстрактные споры - вторичны. Что делать криптографическому начальству?
Логичный ответ – создавать боевые шифры, реализуемые с помощью персональных компьютеров – отметаем не то, что с порога, а за много верст до него. Это с помощью персональных компьютеров наших вероятных противников создавать военные шифры? Товарищ Сталин, слышите, что тут без Вас стало твориться в любимой Вами криптографии?
Ну а не военные? Например, коммерческие, как и американцы? Вроде бы и советский стандарт шифрования для этого сделали?
У меня есть своя точка зрения на то, для чего сделали советский стандарт шифрования. Как там говорил Никита Сергеевич Хрущев: «Покажем Кузькину мать Америке»? Кажется так. Долгое время в гонке вооружений между СССР и США действовал принцип: око за око, зуб за зуб. Сделали американцы новый стратегический бомбардировщик – дадим на него свой советский ответ. Сделали открытую криптосхему DES, взбудоражили советское криптографическое начальство, заставили его напрячься – получите в ответ советский открытый стандарт шифрования, слегка переделанный из вашего DES. Пусть теперь ваше криптографическое начальство напрягается! Вот вам наша криптографическая «Кузькина мать»! По крайней мере, если кто-то станет мне говорить, что тогда, в 1979 году, когда принималось решение о создании советского стандарта шифрования, заботились о коммерческой криптографии, то разрешите усомниться в такой трогательной и заблаговременной заботе о будущих российских банкирах.
Почти 10 лет создавали советский стандарт шифрования, в основном перестраховываясь от выдачи каких-то таинственных криптографических секретов. За эти 10 лет в стране много интересных вещей случилось, к концу уже зазвучали слова «перестройка», «хозрасчет», «гласность» и кое-что еще. Но мышление советского криптографического начальства по-прежнему оставалось идеологически кристально чистым: коммерческая криптография противоречит учению великого Сталина.  А уж о том, чтобы с помощью «буржуазной лженауки» офицеры Спецуправления работали во благо каких-то коммерсантов, не могло быть даже самых отдаленных помыслов.
                И вот, помимо воли начальства, в низах - повальное увлечение персональными компьютерами. Куда, в какое криптографическое русло его направить?
                Первоначально, естественно, - на автоматизацию криптографического анализа советских балалаек. Пускай на PC считают различные статистики. Но очень скоро выяснилось, что импортные PC гораздо умнее советских монстров – ЭВМ, и на них можно делать намного более интересные криптографические задачи, а именно: использовать их в качестве шифровальной техники с практически неограниченными возможностями для реализации оригинальных криптосхем, для построения удобного интерфейса, для выработки ключей и т.п. А для чего и для кого? Кто будет конечным потребителем такой чисто программной продукции, использующей в качестве элементной базы стандартные персональные компьютеры зарубежного производства?
                Начальство не могло дать на это никакого вразумительного ответа, только традиционные заклинания про криптографические результаты, которые сейчас «нельзя получить на кончике пера», имея в виду опять же использование PC для тупых задач перебора ключей или сбора статистики при анализе древних военных схем. А компьютерные фанаты плодились в Спецуправлении с ужасающей быстротой, это, в основном, были молодые ребята, закончившие Высшую Школу КГБ, и проводившие за компьютером все рабочее время, часто даже оставаясь и после работы. Необходимого выхода для их фанатизма тогда в Спецуправлении не находилось. Они находили себе друзей-программистов на стороне, в открытом мире, полулегально подрабатывали в появившихся коммерческих фирмах, но развернуться по-настоящему для создания серьезных коммерческих шифров, которые смогли бы быть конкурентоспособными на мировых рынках, никто так и не смог. Такое было невозможно в принципе во времена СССР.
                Эти ребята вызывали у меня уважение и чувство зависти: они свои результаты видят на экране, могут их проверить и чуть ли не потрогать руками. А мои теоремы и методы криптографического анализа почти всегда абстрактны, удовольствия от их получения у меня в последнее время возникало все меньше и меньше. Тянуло в фанаты. 

Collapse )

Криптография и свобода. Loading... Глава 2. Бормотуха.

 
Глава 2
Бормотуха
Предсказателей и гадалок в 5 отделе хватало, особенно среди «криптографических законодателей». Прогнозные исследования – очень модная тема: как будет развиваться вычислительная техника? Как это отразится на криптографии? На оценках стойкости? Как будут развиваться методы криптографического анализа? И много иных подобных «как». В основном все сводилось к угадыванию желаний криптографического начальства. А оно пожелало, в частности, новые требования к шифраппаратуре. 
Тут надо немного посвятить читателя в основы криптографического анализа. С чего он начинается? С предъявляемых к этой аппаратуре криптографических и инженерно-криптографических требований, т.е. нормативного документа, определяющего, в каких случаях результаты проведенного криптографического и инженерно-криптографического анализа считать опасными для дальнейшей эксплуатации аппаратуры, а в каких – нет. Например, когда удалось построить наглядный пример вскрытия шифра, подобный тому, который описывался для шифра типа «Ангстрем-3» при Т=16 – это заведомо опасный результат. Но такие ситуации встречаются на практике очень редко, а в большинстве случаев результаты криптографического анализа носят абстрактный характер: трудоемкость Q метода определения секретного ключа составляет столько-то двоичных операций, при этом надежность P (вероятность правильного определения ключа) – такая-то. Минимальное отношение Q/P по всем рассмотренным методам криптоанализа является оценкой стойкости шифровальной аппаратуры.
С незапамятных времен (с начала 60-х годов) действовали единые криптографические и инженерно-криптографические требования, по которым опасной считалась оценка стойкости ниже, чем 1025. По тем временам, да и по этим тоже, этого вполне хватало, чтобы говорить о гарантированной стойкости: опробование такого количества вариантов не по силам даже современным компьютерам. Но криптографическое начальство, напуганное страшилками про нейрокомпьютеры и эффект сверхпроводимости, а также бурным научно-техническим прогрессом на Западе, решило подстраховаться: создать новые требования к перспективной шифраппаратуре, в которых не было бы никаких четких оценок и в любом случае можно было бы сказать, что мы все знали и предвидели.
По новым требованиям оценка стойкости измерялась почти по Эйнштейну: не в Q/P, а во времени. Во времени максимальной эксплуатации. Ну, да это бог с ним, со временем, хоть в погонных метрах мерить эту стойкость, главное нововведение было в двух коэффициентах: a и b. b - ежегодные темпы роста производительности вычислительной техники, тут еще с натяжкой можно было как-то предположить конкретные цифры - 1-2 порядка в год, хотя, очевидно, не каждый год сохраняются подобные темпы. Вся хитрая чиновничья казуистика заключалась в коэффициенте a - ожидаемый ежегодный прогресс криптографических методов анализа. Это примерно то же, что и количество чертей на конце булавочной иголки, сколько это будет – одному Богу известно.
Одну старую «балалайку» в НИИ автоматики проанализировали по новым требованиям. Как там считали коэффициент a - не знаю, скорее всего откопали все старые отчеты и разделили общее количество сброшенных порядков на время, которое эта «балалайка» эксплуатировалась. В итоге общая оценка стойкости получилась 100 лет, эту цифру официально записали в отчете. На следующий год в 5 отдел пришел молодой парень, свежим взглядом нашел статаналог и по старым, добрым требованиям «уронил» оценку стойкости до 1021. Больше старых «балалаек» по новым требованиям не анализировали, так спокойнее будет жить.
Но любимой темой для гаданий был прогноз развития ЭВМ. Под это дело была даже открыта специальная НИР «Экстракт», злыми языками, ничего не понимавшими в техническом прогрессе, окрещенная бормотухой. Как скажется на криптографии развитие ЭВМ – вот главный вопрос, на который должна была дать ответ эта НИР в середине 80-х годов теперь уже прошлого века. Источником разведданных для НИР «Экстракт» служили, в основном, публикации в газете «За рубежом» про различные технические сенсации на Западе, которые аккуратно переписывались и, естественно, засекречивались.
Исходная точка отсчета в НИР «Экстракт» была такова: всемогущее американское Агентство Национальной Безопасности скупает все мировые компьютеры, распараллеливает их и запускает для перебора ключей к советским «балалайкам». Сколько они смогут сделать операций в год? Сколько еще порядков нужно накинуть для подстраховки?
Броня крепка и танки наши быстры. Советская криптография всю свою сознательную жизнь была исключительно военной, обслуживала только высшее руководство СССР, правительство, важные министерства типа министерства иностранных дел, войска. Психология и мышление советского высшего криптографического начальства также были исключительно военными, да к тому же еще идеологически кристально чистыми. Слова «коммерческая криптография», «рынок», «прибыль» для него даже во второй половине 80-х годов были контрреволюционными (по крайней мере, в официальных документах), за которые товарищ Сталин справедливо делал известно что. Так было, так есть, так будет всегда!
А жизнь-то менялась. Персональные компьютеры дешевели, их становилось все больше и больше, и не за горами было то время, когда они станут неотъемлемым бытовым атрибутом, наподобие телевизора или холодильника. Запрограммировать на РС криптографический алгоритм не так уж и сложно, а отсюда уже один шаг и до массовой, гражданской криптографии, была бы только в ней потребность. А тут модемы и первые компьютерные сети стали появляться…
Остановиться бы тогда, в конце 80-х годов, снять с глаз темные очки и оглядеться вокруг на окружающую действительность. Была же ведь реальная возможность побороться за мировые рынки сбыта наукоемкой криптографической продукции, программ и алгоритмов, была возможность даже в каком-то смысле стать законодателями криптографической моды. Были и идеи (те же шифры на новой элементной базе), были и отличные молодые специалисты, с ходу освоившие все нехитрые программистские премудрости и готовые выдавать конкурентоспособную продукцию. Не было одного: желания руководства реально поддержать это направление. Разговоров про необходимость использования компьютеров было выше крыши, море совещаний, партийных собраний, оперативок, но если речь заходила о каких-то реальных делах – глухая стена. Так тише, спокойнее, меньше ответственности.
Дело еще и в том, что советская электронная промышленность того времени просто по определению не могла выпускать ничего похожего на западные РС. Как, мы советские криптографы попадем в зависимость от враждебного нам запада? А если они нам закладок понаставят, или эмбарго какое введут? Наша электроника хоть и с танк размером, да и ломается постоянно, но это – своя, отечественная! А запад – загнивает и постоянно стоит над пропастью. Наверное, смотрит, что мы там делаем.
Но РС открывали перед криптографами колоссальные возможности. Программируешь самостоятельно любой необходимый алгоритм, нет этой противной и поглощающей все силы зависимости от промышленности, от заводов. Надежность западных персональных компьютеров намного выше, чем советской техники, поэтому сам собой почти отпадает вопрос об инженерно-криптографическом анализе: РС практически никогда не ломаются. Любое изменение в алгоритме – Upgrade – тоже нет необходимости связываться с заводом, достаточно перепрограммировать алгоритм. Универсальность, надежность, потенциально большой спрос – вот что сулило использование РС в криптографии, а точнее – решение криптографических проблем с помощью РС.
Дремучий консерватизм наверху и реальное понимание внизу – вот краткая характеристика отношений к РС в конце 80-х годов. А, впрочем, почему только в конце 80-х? Разве мало было затем предложений запретить использование импортного программного обеспечения? Спустя почти 20 лет по-прежнему какой-нибудь депутат иногда выступает с таким предложением. Чудесные люди! «Windows для чайников» – в массы!
Кроме того, учитывая универсальность задач, которые можно решать с помощью персонального компьютера, многие сразу же поняли, что это потенциальный «запасной аэродром» на случай каких-то непредвиденных перемен в тихой и спокойной жизни государевых криптографов. Ведь специальность криптографа весьма экзотическая, так ли легко будет найти другую работу в случае каких-то катаклизмов? Раньше, во времена полного господства государственной собственности, зарплата офицера КГБ была в среднем в 2 раза выше, чем у обычного инженера, но вот появились кооперативы, первые частные предприятия, на которых те же инженеры, не обремененные доходящей иногда до абсурда воинской дисциплиной, стали зарабатывать намного больше офицеров КГБ. Так что у высокого начальства был еще один повод опасаться РС: с ними слишком вольнолюбивыми могут стать подчиненные офицеры-математики, будут заглядываться на сторону. Как тут не вспомнить степановскую теорию патриотизма к отделу!
Вадим Евдокимович Степанов внезапно умер. Еще в пятницу я с ним здоровался, а в понедельник утром сообщили эту трагическую новость. Тромб сердечных кровеносных сосудов, почти мгновенная смерть. Это был, несмотря ни на что, человек, своим интеллектом и образованностью сильно выделявшийся среди остальных, даже среди начальников 8 ГУ. Его кончина не могла не вызвать перемен в жизни 5 отдела, административная удавка, которой он сдерживал многих, ослабла. Это сказалось, в частности, на мне: без лишнего шума, опять-таки, особо и не интересуясь моим мнением, меня отправили в другой отдел с повышением, на должность заместителя начальника отделения. Но тут уже я сильно не переживал, после того насилия, в результате которого меня лишили возможности остаться в Высшей Школе КГБ, я был готов свалить из 5 отдела куда угодно.

Collapse )

Криптография и свобода. Loading... Глава 1. Rub berries body.

 
Глава 1
Rub berries body
 
«Из математика легко подготовить программиста, а вот из программиста математика – сложнее» - так любил говорить Б.А., мой научный руководитель. Истинно так! Только каков конкретный алгоритм подготовки программиста из математика-криптографа? С чего, по выражению Великого Вождя, начать?
С компьютерных игр. Пусть наиграется до посинения, до тех пор, пока пар из ушей не повалит, после этого – клиент готов. Дальше до всего остального, если есть голова на плечах, додумается сам. Главное – чтобы компьютер имел, как принято выражаться, дружеский интерфейс, а по-простому, по-советски – не заставлял бы тебя долбать дырки в перфоленте, не стращал бы своими кастрюлями-накопителями, не ломался и был бы доступен без записей и очередей практически в любое время, т.е. был бы на самом деле персональным. Математику, прошедшему через алгебру и ТВИСТ, разобраться в какой-то там DOS или языках программирования совсем нетрудно, а компьютер, после проведенных вместе с ним битв против шамуса или арканоида, - лучший боевой друг.
Несомненно, это была вражеская диверсия: в Теоретический отдел Спецуправления 8 Главного управления КГБ СССР практически одновременно с появлением там первых РС были запущены компьютерные игры. Работа встала, начался первый и самый основной этап освоения компьютерной грамотности – наиграться до посинения. Все теоретики, алгебраисты и вероятностники, молодые и старые, активные и пассивные, обсуждали одну и ту же научную проблему: как в Space Quest-2 пройти болото с кикиморой.
 
-          Палку взять на берегу пробовали?
-          Сколько раз, не помогает.
-          Нырни поглубже и обойди ее.
-          Глубже не ныряется.
-          Должна же быть дорога в обход болота.
-          Да нет там никакой другой дороги, только через болото!
-          Пугнуть ее чем-то надо.
-          Пробовали, не помогает.
 
Это была одна из первых игр-бродилок, в которых команды человечку-путешественнику по неведомой планете надо было набирать по-английски на клавиатуре. Успешно были пройдены все первые уровни, а вот на этом проклятом болоте кикимора всякий раз нагло проглатывала отважного странника. И весь 5 отдел никак не мог ничем ему помочь.
Забыты научные распри и споры, наступило всеобщее единение в борьбе с этой буржуйской вражиной. Научный подход: пронумерованы все предыдущие попытки, идет анализ возможных вариантов, дискуссии и дебаты, рисуются схемы проходимых лабиринтов, криптографы яростно пытаются применить самый известный и самый надежный метод криптографического анализа – метод тотального опробования, не остаются в стороне и другие достижения современной криптографической мысли – методы согласования, гомоморфизмов, статистических аналогов, и все они направлены против одного и того же противника, воспринимаемого уже не как абстрактный «вероятный противник», а как самый ни на есть настоящий – кикимора из болота в Space Quest 2 и те, кто ее придумал. В конце концов человеческий разум победил!
Где-то спустя примерно неделю после первой попытки, когда, казалось, тотально были опробованы все мыслимые криптографами методы, кто-то обратил внимание на кусты, растущие около болота.
 
-          Ягоды с кустов есть пробовали?
-          Не помогает.
-          А если натереть ими тело?
 
Rub berries body.  Волшебные слова, истина в последней инстанции! Человек, сказавший их первым, заслуженно стал героем дня, его поздравляли, жали руку, желали дальнейших творческих успехов. После этих слов запах ягод отпугнул кикимору и она сочла человечка несъедобным. Всеобщее ликование и радость: победа, добытая в трудной и упорной борьбе!
Это был, пожалуй, пик экстаза компьютерных игр в отделе. Ажиотаж пошел на спад, хотя тетрисоманы еще долго крутили-вертели свои загогулины, пытаясь установить новый абсолютный рекорд. Но в конце концов свершилось то, что и должно было свершиться: игры стали надоедать. Может, запрограммировать что-нибудь? Алгоритм какой или метод? Вот так персональные компьютеры стали лучшими друзьями всего прогрессивного человечества, в том числе и советских криптографов. По крайней мере, в Теоретическом отделе Спецуправления 8 ГУ КГБ СССР.

Collapse )

Криптография и свобода. Колея. Глава 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 )