shannon1949 (776132)

Файл №776132 shannon1949 (C.Shannon. Communication Theory of Secrecy Systems)shannon1949 (776132)2017-06-17СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Communication Theory of Secrecy Systems?By C. E. S HANNON1I NTRODUCTION AND S UMMARYThe problems of cryptography and secrecy systems furnish an interesting application of communication theory1 . In this paper a theory of secrecy systemsis developed. The approach is on a theoretical level and is intended to complement the treatment found in standard works on cryptography 2 . There, adetailed study is made of the many standard types of codes and ciphers, andof the ways of breaking them.

We will be more concerned with the generalmathematical structure and properties of secrecy systems.The treatment is limited in certain ways. First, there are three generaltypes of secrecy system: (1) concealment systems, including such methodsas invisible ink, concealing a message in an innocent text, or in a fake covering cryptogram, or other methods in which the existence of the messageis concealed from the enemy; (2) privacy systems, for example speech inversion, in which special equipment is required to recover the message; (3)“true” secrecy systems where the meaning of the message is concealed bycipher, code, etc., although its existence is not hidden, and the enemy is assumed to have any special equipment necessary to intercept and record thetransmitted signal.

We consider only the third type—concealment system areprimarily a psychological problem, and privacy systems a technological one.Secondly, the treatment is limited to the case of discrete informationwhere the message to be enciphered consists of a sequence of discrete symbols, each chosen from a finite set. These symbols may be letters in a language, words of a language, amplitude levels of a “quantized” speech orvideo signal, etc., but the main emphasis and thinking has been concernedwith the case of letters.The paper is divided into three parts. The main results will now be brieflysummarized. The first part deals with the basic mathematical structure ofsecrecy systems. As in communication theory a language is considered to berepresented by a stochastic process which produces a discrete sequence of?12The material in this paper appeared in a confidential report “A Mathematical Theory of Cryptography” dated Sept.1, 1946, which has now been declassified.Shannon, C.

E., “A Mathematical Theory of Communication,” Bell System Technical Journal, July1948, p.623.See, for example, H. F. Gaines, “Elementary Cryptanalysis,” or M. Givierge, “Cours de Cryptographie.”symbols in accordance with some system of probabilities. Associated witha language there is a certain parameter D which we call the redundancy ofthe language. D measures, in a sense, how much a text in the language canbe reduced in length without losing any information.

As a simple example,since u always follows q in English words, the u may be omitted withoutloss. Considerable reductions are possible in English due to the statisticalstructure of the language, the high frequencies of certain letters or words, etc.Redundancy is of central importance in the study of secrecy systems.A secrecy system is defined abstractly as a set of transformations of onespace (the set of possible messages) into a second space (the set of possiblecryptograms). Each particular transformation of the set corresponds to enciphering with a particular key.

The transformations are supposed reversible(non-singular) so that unique deciphering is possible when the key is known.Each key and therefore each transformation is assumed to have an a prioriprobability associated with it—the probability of choosing that key. Similarlyeach possible message is assumed to have an associated a priori probability,determined by the underlying stochastic process.

These probabilities for thevarious keys and messages are actually the enemy cryptanalyst’s a prioriprobabilities for the choices in question, and represent his a priori knowledgeof the situation.To use the system a key is first selected and sent to the receiving point.The choice of a key determines a particular transformation in the set forming the system. Then a message is selected and the particular transformationcorresponding to the selected key applied to this message to produce a cryptogram. This cryptogram is transmitted to the receiving point by a channeland may be intercepted by the “enemy? .” At the receiving end the inverseof the particular transformation is applied to the cryptogram to recover theoriginal message.If the enemy intercepts the cryptogram he can calculate from it the a posteriori probabilities of the various possible messages and keys which mighthave produced this cryptogram.

This set of a posteriori probabilities constitutes his knowledge of the key and message after the interception. “Knowledge” is thus identified with a set of propositions having associated probabilities. The calculation of the a posteriori probabilities is the generalizedproblem of cryptanalysis.As an example of these notions, in a simple substitution cipher with random key there are 26! transformations, corresponding to the 26! ways we cansubstitute for 26 different letters. These are all equally likely and each there1fore has an a priori probability 26!. If this is applied to “normal English”?The word “enemy,” stemming from military applications, is commonly used in cryptographic workto denote anyone who may intercept a cryptogram.657the cryptanalyst being assumed to have no knowledge of the message sourceother than that it is producing English text, the a priori probabilities of various messages of N letters are merely their relative frequencies in normalEnglish text.If the enemy intercepts N letters of cryptograms in this system his probabilities change.

If N is large enough (say 50 letters) there is usually a singlemessage of a posteriori probability nearly unity, while all others have a totalprobability nearly zero. Thus there is an essentially unique “solution” to thecryptogram. For N smaller (say N = 15) there will usually be many messages and keys of comparable probability, with no single one nearly unity.

Inthis case there are multiple “solutions” to the cryptogram.Considering a secrecy system to be represented in this way, as a set oftransformations of one set of elements into another, there are two naturalcombining operations which produce a third system from two given systems.The first combining operation is called the product operation and correspondsto enciphering the message with the first secrecy system R and encipheringthe resulting cryptogram with the second system S, the keys for R and Sbeing chosen independently.

This total operation is a secrecy system whosetransformations consist of all the products (in the usual sense of productsof transformations) of transformations in S with transformations in R. Theprobabilities are the products of the probabilities for the two transformations.The second combining operation is “weighted addition.”T = pR + qSp+q =1It corresponds to making a preliminary choice as to whether system R or Sis to be used with probabilities p and q, respectively. When this is done R orS is used as originally defined.It is shown that secrecy systems with these two combining operationsform essentially a “linear associative algebra” with a unit element, an algebraic variety that has been extensively studied by mathematicians.Among the many possible secrecy systems there is one type with manyspecial properties. This type we call a “pure” system. A system is pure if allkeys are equally likely and if for any three transformations Ti , Tj , Tk in theset the productTi Tj−1 Tkis also a transformation in the set.

That is, enciphering, deciphering, and enciphering with any three keys must be equivalent to enciphering with somekey.With a pure cipher it is shown that all keys are essentially equivalent—they all lead to the same set of a posteriori probabilities. Furthermore, when658a given cryptogram is intercepted there is a set of messages that might haveproduced this cryptogram (a “residue class”) and the a posteriori probabilities of message in this class are proportional to the a priori probabilities. Allthe information the enemy has obtained by intercepting the cryptogram is aspecification of the residue class. Many of the common ciphers are pure systems, including simple substitution with random key.

In this case the residueclass consists of all messages with the same pattern of letter repetitions as theintercepted cryptogram.Two systems R and S are defined to be “similar” if there exists a fixedtransformation A with an inverse, A−1 , such thatR = AS.If R and S are similar, a one-to-one correspondence between the resultingcryptograms can be set up leading to the same a posteriori probabilities. Thetwo systems are cryptanalytically the same.The second part of the paper deals with the problem of “theoretical secrecy”.

Характеристики

Тип файла
PDF-файл
Размер
549,38 Kb
Тип материала
Высшее учебное заведение

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6418
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее