Доклада "математическая теория криптографии", датированного 1 сентября 1945 года. Затем он был рассекречен, и в 1949 году опубликован в техническом журнале корпорации Bell System




Скачать 44,35 Kb.
НазваниеДоклада "математическая теория криптографии", датированного 1 сентября 1945 года. Затем он был рассекречен, и в 1949 году опубликован в техническом журнале корпорации Bell System
страница2/2
Дата04.02.2016
Размер44,35 Kb.
ТипДоклад
1   2

6. Алгебра секретных систем.

Если имеются две секретные системы Т и R, их часто можно комбинировать различными способами для получения новой секретной системы S. Если T и R имеют одну и ту же область (пространство сообщений), то можно образовать своего рода "взвешенную сумму"

S = рТ + qR,

где p + q = 1. Эта операция состоит, во-первых, из предварительного выбора систем T или R с вероятностями p и q. Этот выбор является частью ключа S. После того, как этот выбор сделан, системы T или R применяются в соответствии с их определениями. Полный ключ S должен указывать, какая из систем T или R выбрана и с каким ключом используется выбранная система.

Если Т состоит из отображений Т1,...,Тm с вероятностями p1,...,pm, a R - из R1,...,Rk с вероятностями q1,...,qk, то система S = рТ + qR состоит из отображений Т1,...,Тm,R1,...,Rk с вероятностями pp1,...,ppm,qq1,...,qqk соответственно. Обобщая далее, можно образовать сумму нескольких систем

S = p1Т + p2R + ... + pmU, pi = 1.

Заметим, что любая система T может быть записана как сумма фиксированных операций

T = p1Т1 + p2T2 + ... + pmTm,

где Ti - определенная операция шифрования в системе T, соответствующая выбору ключа i, причем вероятность такого выбора равна pi.

Второй способ комбинирования двух секретных систем заключается в образовании "произведения", как показано схематически на рис. 3.



Рис 3. Произведение двух систем S = RT.

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

S = RT.

Ключ системы S состоит как из ключа системы T, так и из ключа системы R, причем предполагается, что эти ключи выбираются соответственно их первоначальным вероятностям и независимо. Таким образом, если m ключей системы T выбирается с вероятностями

p1,p2,...,pm,

а n ключей системы R имеют вероятности

p'1,p'2,...,p'n,

то система S имеет самое большее mn ключей с вероятностями pip'j. Во многих случаях некоторые из отображений RiTj будут одинаковыми и могут быть сгруппированы вместе, а их вероятности при этом сложатся.

Произведение шифров используется часто: например, после подстановки применяют перестановку или после перестановки - код Виженера, или же применяют код к тексту и зашифровывают результат с помощью подстановки, перестановки, дробным шифром и т.д.


Можно заметить, что такое умножение, вообще говоря, некоммутативно (т.е. не всегда RS = SR), хотя в частных случаях (таких, как подстановка и перестановка) коммутативность имеет место. Так как наше умножение представляет собой некоторую операцию, оно по определению ассоциативно, т.е. R(ST) = (RS)T = RST. Кроме того, верны законы

p(p'T + q'R) + qS = pp'T + pq'R + qS

(взвешенный ассоциативный закон для сложения);

T(pR + qS) = pTR + qTS
(pR + qS)T = pRT + qST

(право- и левосторонние дистрибутивные законы), а также справедливо равенство

p1T + p2T + p3R = (p1 + p2)T + p3R.

Следует подчеркнуть, что эти операции комбинирования сложения и умножения применяются к секретным системам в целом. Произведение двух систем TR не следует смешивать с произведением отображений в системах TiRj, которое также часто используется в настоящей работе. Первое является секретной системой, т.е. множеством отображений с соответствующими вероятностями; второе является фиксированным отображением. Далее, в то время как сумма двух систем pR + qT является системой, сумма двух отображений не определена. Системы T и R могут коммутировать, в то время как конкретные Rj и Ti не коммутируют. Например, если R - система Бофора данного периода, все ключи которой равновероятны, то, вообще говоря,

RiRjRjRi,

но, конечно, произведение RR не зависит от порядка сомножителей; действительно

RR = V

является системой Виженера того же самого периода со случайным ключом. С другой стороны, если отдельные отображения Ti и Rj двух систем T и R коммутируют, то и системы коммутируют.

Системы, у которых пространства M и E можно отождествить (этот случай является очень частым, если последовательности букв преобразуются в последовательности букв), могут быть названы эндоморфными. Эндоморфная система T может быть возведена в степень Tn.

Секретная система T, произведение которой на саму себя равно T, т.е. такая, что

TT = T,

будет называться идемпотентной. Например, простая подстановка, транспозиция с периодом p, система Виженера с периодом p (все с равновероятными ключами) являются идемпотентными.

Множество всех эндоморфных секретных систем, определенных в фиксированном пространстве сообщений, образует "алгебраическую систему", т.е. некоторый вид алгебры, использующей операции сложения и умножения. Действительно, рассмотренные свойства сложения и умножения можно резюмировать следующим образом:

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

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

T = p1A + p2B + ... + prS + p'X, pi = 1,

где A,B,...,S в данном случае - известные типы шифров с их априорными вероятностями pi, а p'X соответствует возможности использования совершенно нового неизвестного шифра.
1   2

Похожие:

Доклада \"математическая теория криптографии\", датированного 1 сентября 1945 года. Затем он был рассекречен, и в 1949 году опубликован в техническом журнале корпорации Bell System iconПрограмма дисциплины «Теория вероятностей и математическая статистика» для направления 523100-Бизнес-информатика вторая ступень высшего профессионального образования
Курс «Теория вероятностей и математическая статистика» рассчитан на студентов второго года обучения бакалавриата факультета бизнес-информатики...
Доклада \"математическая теория криптографии\", датированного 1 сентября 1945 года. Затем он был рассекречен, и в 1949 году опубликован в техническом журнале корпорации Bell System iconСправочник по состоянию на 01. 07. 2012 года
Ереване. С 1988 жил и работал в Москве. Активно участвовал в движении кинообразования (был членом Правления Ассоциации деятелей кинообразования...
Доклада \"математическая теория криптографии\", датированного 1 сентября 1945 года. Затем он был рассекречен, и в 1949 году опубликован в техническом журнале корпорации Bell System iconСправочник по состоянию на 01. 07. 2012 года
Ереване. С 1988 жил и работал в Москве. Активно участвовал в движении кинообразования (был членом Правления Ассоциации деятелей кинообразования...
Доклада \"математическая теория криптографии\", датированного 1 сентября 1945 года. Затем он был рассекречен, и в 1949 году опубликован в техническом журнале корпорации Bell System icon2 Более того, рассказ отвечает и на вопросы, зачем Минцловой был нужен «мистический треугольник» ипочему она внезапно исчезла
Андрея Белого (Борис Бугаев, 1880-1934) и Вячеслава Иванова (1866-1949). Семнадцатого августа 1910 года Минцлова загадочно исчезла...
Доклада \"математическая теория криптографии\", датированного 1 сентября 1945 года. Затем он был рассекречен, и в 1949 году опубликован в техническом журнале корпорации Bell System iconМатематическая теория оболочек
Предмет и задачи теории оболочек. Математическая и прикладная теория оболочек. Основы тензорного анализа двумерных поверхностей в....
Доклада \"математическая теория криптографии\", датированного 1 сентября 1945 года. Затем он был рассекречен, и в 1949 году опубликован в техническом журнале корпорации Bell System iconКонтрольная работа №11 Теория вероятностей, математическая статистика и случайные процессы
Гмурман В. Е. Теория вероятностей и математическая статистика. Учебное пособие для вузов – 10-е издание, стереотипное – Москва: Высшая...
Доклада \"математическая теория криптографии\", датированного 1 сентября 1945 года. Затем он был рассекречен, и в 1949 году опубликован в техническом журнале корпорации Bell System iconПрограмма по дисциплине «Теория вероятностей и математическая статистика»
«Теория вероятностей и математическая статистика» разработана в соответствии с Государственным стандартом образования РФ (ЕН. Общие...
Доклада \"математическая теория криптографии\", датированного 1 сентября 1945 года. Затем он был рассекречен, и в 1949 году опубликован в техническом журнале корпорации Bell System iconКонтрольная работа по русской литературе 19(2) века студентки IV курса заочного отделения ифк и мк агаповой Анастасии Анатольевны
В начале 30-ых годов был написан автобиографический роман «Как закалялась сталь» (1935) — одно из хрестоматийных произведений советской...
Доклада \"математическая теория криптографии\", датированного 1 сентября 1945 года. Затем он был рассекречен, и в 1949 году опубликован в техническом журнале корпорации Bell System iconПрограмма дисциплины «Теория вероятностей и математическая статистика»
«Теория вероятностей и математическая статистика» для направления 080700. 62 Бизнес-информатика подготовки бакалавра для специализации...
Доклада \"математическая теория криптографии\", датированного 1 сентября 1945 года. Затем он был рассекречен, и в 1949 году опубликован в техническом журнале корпорации Bell System iconЗарубежная книга, раскрывшая самую таинственную историю Анны Ахматовой
А впереди был ждановский доклад в Союзе писателей Ленинграда и ругательские выступления критиков и писателей, исключение из Союза...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib2.znate.ru 2012
обратиться к администрации
Библиотека
Главная страница