«Теорія зв'язку в секретних системах» (англ. Communication Theory of Secrecy Systems) — стаття американського математика та інженера Клода Шеннона, опублікована в журналі англ. Bell System Technical Journal в 1949 році.
Автор | Клод Шеннон |
---|---|
Мова | англійська |
В ній вперше були визначені фундаментальні поняття теорії криптографії, доведена досконала криптостійкість шифру Вернама, визначено поняття відстані єдиності, розглянута проблема надмірності мови й запропонована ідея створення шифрів на основі декількох циклів заміни та перестановки. Вважається, що саме з появою цієї статті криптографія, яка колись вважалася мистецтвом, почала розвиватися як наука.
Історія
З початку 1940-х років Клод Шеннон працював на (англ. National Defense Research Committee). В лабораторіях Белла — дослідному центрі в галузі телекомунікацій і електронних систем, серед інших питань, він займався дослідженнями в області теорії інформації та криптографії, зокрема, питаннями безпеки урядового зв'язку.
1 вересня 1945 року, як результат його напрацювань, вийшла секретна доповідь «Математична теорія криптографії» (англ. A Mathematical Theory of Cryptography). Серед тих, кому вона була направлена, були , , , Гаррі Найквіст, Ральф Хартлі, Джон Робінсон Пірс, , Волтер Шухарт і .
Через три роки була опублікована робота Шеннона «Математична теорія зв'язку» (англ. A Mathematical Theory of Communication), яка вважається основоположною в теорії інформації. У жовтні 1949 року журнал Bell System Technical Journal опублікував статтю Клода Шеннона з криптографії «Теорія зв'язку в секретних системах» (англ. Communication Theory of Secrecy Systems). В останню, також як і раніше в «Математичну теорію зв'язку», увійшла значна частина концептуальних напрацювань, раніше викладених у секретній доповіді «Математична теорія криптографії». В обох статтях був розроблений математичний апарат для відповідних систем.
Лабораторії Белла працювали над секретними системами. Я працював над системами зв'язку й також був призначений в деякі комітети, які вивчали техніку криптоаналізу. Робота над обома математичними теоріями - зв'язку й криптографії - йшла одночасно з 1941 року. Не можна сказати, що одна завершилася раніше іншої - обидві були так близькі, що не могли бути розділені. (Клод Шеннон) |
Зміст
Стаття складається з трьох частин: «Математична структура секретних систем», «Теоретична секретність» і «Практична секретність».
Математична структура секретних систем
У першій частині статті введено формальне визначення криптосистеми (симетричної криптосистеми), що складається з джерела повідомлень, джерела ключів, шифрувальників, повідомлення, ключа криптограми й шифрувальника противника. Визначено функцію шифрування, яка залежить від вихідного повідомлення і ключа, процес дешифрування для одержувача повідомлення, що складається в обчисленні відображення, зворотного шифруванню, і процес дешифрування для супротивника — спробі визначити початкове повідомлення, знаючи тільки криптограмму і апріорні ймовірності різних ключів та повідомлень.
Автор також запропонував подання криптосистеми у вигляді двочасткового графа, у вершинах якого розташовані можливі повідомлення і можливі криптограми, а кожному ключу шифрування поставлено у відповідність множину ребер, що з'єднують кожне можливе повідомлення з відповідною йому криптограмою.
Наведено математичний опис раніше відомих шифрів. Розглянуто шифр простої підстановки, шифр Віженер, діграмна, триграмна і n-граммна підстановки, шифр Плейфера, шифр з автоключем і дробові шифри.
Основними критеріями оцінки властивостей (стійкості) криптосистем у статті названі: розмір (довжина) ключа, складність операцій шифрування і дешифрування, можливість або неможливість дешифрування повідомлення противником єдиним способом, ступінь впливу помилок при шифруванні і передачі на отримане повідомлення та ступінь збільшення розміру повідомлення у результаті шифрування. В кінці статті зазначено, що у разі шифрування складеного природною мовою повідомлення можна поліпшити загальну оцінку криптосистеми за всіма перерахованим параметрам одночасно.
Запропонована структура алгебри секретних систем (алгебри шифрів) з двома основними операціями комбінування шифрів: зважена сума (додавання шифрів з вагами у вигляді ймовірностей вибору шифру) і витвір (послідовне застосування). Нові шифри запропоновано отримувати комбінуванням зваженої суми і комбінації різних шифрів.
Теоретична секретність
У другій частині статті визначено поняття досконалої стійкості криптосистеми, системи, де вихідне повідомлення і криптограма статистично незалежні.
Доведена повна стійкість шифру Вернама (одноразового шифроблокнота). Показана ненадійність деяких шифрів на прикладі шифру Цезаря, в якому частота появи символів, яка відповідає символам вихідного повідомлення, що не залежать від ключа.
При розгляді випадкового шифру було введено поняття відстані єдиності — мінімального числа символів криптограми, з допомогою яких ключ може бути визначений однозначно. Також відзначена проблема надмірності мови, яка полягає в тому, що надмірність, що являє собою набір умов, накладених на символи повідомлення, дає додаткові можливості при дешифруванні криптограми противником.
Введено поняття ідеально стійкої криптосистеми, яка має нескінченну відстань єдиності. Приватним (більш суворим) випадком таких систем є досконало секретні системи. Їх характерною особливістю є те, що ідеальна криптосистема зберігає невизначеність навіть при успішній операції дешифрування противником.
Практична безпека
У третій частині статті визначена робоча характеристика криптосистеми як функція, що залежить від числа відомих символів криптограми і дорівнює середнім обсягам роботи, витраченій на знаходження ключа шифрування. Ця функція має деякі подібності з поняттям обчислювальної складності алгоритму.
Розглянуто можливість розкриття шифру за допомогою статистичного аналізу частоти символів зашифрованого тексту і методу імовірних слів. Згідно описаної у статті теорії, противник в процесі дешифрування може використовувати деякі статистичні властивості мови. Показано, що, наприклад, за умови знання мови вихідного повідомлення, для деяких шифрів можливо розкрити текст, що складається з декількох десятків символів. В якості прикладу слів/словосполучень, які найчастіше зустрічаються в англійській мові, автор навів конструкції «the», «and», «that» і склад «-tion», а в якості поєднання символів «qu», що прямо пов'язано з питанням про , розглянутих у другій частині статті.
Запропоновано використовувати кілька шарів (циклів) замін і змін, що згодом було використано при побудові блочних шифрів. В оригінальній статті Шеннон назвав ці методи «confusion» (заплутування, відповідає заміні) і «diffusion» (розсіювання, відповідає перестановці).
Оцінки впливу
У книзі «Зломщики кодів» Девіда Кана висловлено думку про те, що в той час, як стаття «Математична теорія зв'язку» послужила початком розвитку теорії інформації, у статті «Теорія зв'язку в секретних системах» розглянута наукова сутність криптографії. Відзначено великий внесок автора у вказівці на мовну надмірність як ґрунт для криптоаналізу, і що саме Шеннон вперше ввів фундаментальні принципи дешифрування. Іншою важливою ідеєю статті Шеннона в книзі Кана вважається введення відстані єдиності.
Вітфілд Діффі і Мартін Геллман у статті «Нові напрямки в криптографії» (англ. New Directions in Cryptography) констатували, що Шеннон в «Теорії зв'язку в секретних системах» довів досконалу секретність одноразового шифроблокнота, але його використання є практично нездійсненною задачею для більшості прикладних цілей. Існує думка, що ця стаття Діффі і Геллмана призвела до прориву в криптографії, тому що було показано, як сторони можуть отримати загальний секретний ключ, використовуючи незахищений від прослуховування канал зв'язку, чого не було в криптографії, описаної в статті Шеннона.
Брюс Шнайєр у книзі «Прикладна Криптографія» зазначив, що до 1967 року література з криптографії була беззмістовною, за одним рідкісним винятком, яким є стаття «Теорія зв'язку в секретних системах».
У книзі [en] помічено, що стаття є однією з кращих основоположних статей із захисту інформації й важливо, що вона поєднує практичну та теоретичну сторону питання, вводить фундаментальні ідеї надмірності і відстані єдиності.
В «Енциклопедії з криптографії та безпеки» вказано на вплив, запропонованої в даній роботі ідеї, про використання декількох циклів, що складаються із заміни та перестановки, на створення блочних шифрів і SP-мережі. Також особливо відзначена модель криптосистеми, описана Шенноном, і теорема про досконалої секретності шифру Вернама. Крім того, однією з найбільш цитованих максим в криптографії названо припущення з першої частини статті: «Противнику відома застосована система» (англ. The enemy knows the system being used).
Примітки
- В.И. Левин. К.Э. ШЕННОН И СОВРЕМЕННАЯ НАУКА : ( )[] // Вестник ТГТУ : статья. — 2008. — Т. 14, № 3. — С. 714—716. — ISSN 0136-5835.
- 杉本, 舞. C.E.シャノンの暗号理論 : [ 22 квітня 2018] : ( )[яп.] // 科学哲学科学史研究 : статья. — 京都大学文学部科学哲学科学史研究室, 2006. — Т. 1 (20 3月). — С. 139, 142—144. — DOI:10.14989/56970.
- Whitfield Diffie. Preface to Claue Shannon’s A Mathematical Theory of Cryptography : [ 21 квітня 2018] : ( )[англ.] // IACR : статья. — 2015. — December.
- Claude Shannon. A Mathematical Theory of Cryptography : [ 28 березня 2016] : ( )[англ.]. — 1945. — 1 September.
- Аграновский, Хади
- Hellman An Extension of the Shannon Theory Approach to Cryptography // IEEE Trans. Inf. Theory
- Davio, Goethals Elements of Cryptology // Secure Digital Communications
- В. В. Ященко, Н. П. Варновский, Ю. В. Нестеренко, Г. А. Кабатянский, П. Н. Девянин, В. Г. Проскурин, А. В. Черемушкин, П. А. Гырдымов, А. Ю. Зубов, А. В. Зязин, В. Н. Овчинников, М. И. Анохин Введение в криптографию|ответственный
- (PDF). Архів оригіналу (PDF) за 29 листопада 2016. Процитовано 21 квітня 2018.
- (PDF). Архів оригіналу (PDF) за 4 листопада 2016. Процитовано 21 квітня 2018.
- Encyclopedia of Cryptography and Security / Henk C. A. van Tilborg. — 1. — Springer, 205. — С. 12, 41, 146, 161, 169, 206, 244, 289, 290, 323, 372, 480, 568, 601, 602. — 684 с. — .
- B. Schneier Applied cryptography (2nd ed.): protocols, algorithms, and source code in C
-
У Вікіджерелах є Q27960404
Посилання
- Стаття Шеннона A Mathematical Theory of Cryptography [ 28 березня 2016 у Wayback Machine.] на сайті IACR
- Стаття Шеннона Communication Theory of Secrecy Systems [ 4 листопада 2016 у Wayback Machine.] на сайті
- Сторінка статті на Google Scholar [ 4 листопада 2016 у Wayback Machine.]
- Сторінка публікації на IEEE Xplore Digital Library [ 22 березня 2018 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Teoriya zv yazku v sekretnih sistemah angl Communication Theory of Secrecy Systems stattya amerikanskogo matematika ta inzhenera Kloda Shennona opublikovana v zhurnali angl Bell System Technical Journal v 1949 roci Teoriya zv yazku v sekretnih sistemah AvtorKlod ShennonMovaanglijska V nij vpershe buli viznacheni fundamentalni ponyattya teoriyi kriptografiyi dovedena doskonala kriptostijkist shifru Vernama viznacheno ponyattya vidstani yedinosti rozglyanuta problema nadmirnosti movi j zaproponovana ideya stvorennya shifriv na osnovi dekilkoh cikliv zamini ta perestanovki Vvazhayetsya sho same z poyavoyu ciyeyi statti kriptografiya yaka kolis vvazhalasya mistectvom pochala rozvivatisya yak nauka IstoriyaZ pochatku 1940 h rokiv Klod Shennon pracyuvav na angl National Defense Research Committee V laboratoriyah Bella doslidnomu centri v galuzi telekomunikacij i elektronnih sistem sered inshih pitan vin zajmavsya doslidzhennyami v oblasti teoriyi informaciyi ta kriptografiyi zokrema pitannyami bezpeki uryadovogo zv yazku 1 veresnya 1945 roku yak rezultat jogo napracyuvan vijshla sekretna dopovid Matematichna teoriya kriptografiyi angl A Mathematical Theory of Cryptography Sered tih komu vona bula napravlena buli Garri Najkvist Ralf Hartli Dzhon Robinson Pirs Volter Shuhart i Cherez tri roki bula opublikovana robota Shennona Matematichna teoriya zv yazku angl A Mathematical Theory of Communication yaka vvazhayetsya osnovopolozhnoyu v teoriyi informaciyi U zhovtni 1949 roku zhurnal Bell System Technical Journal opublikuvav stattyu Kloda Shennona z kriptografiyi Teoriya zv yazku v sekretnih sistemah angl Communication Theory of Secrecy Systems V ostannyu takozh yak i ranishe v Matematichnu teoriyu zv yazku uvijshla znachna chastina konceptualnih napracyuvan ranishe vikladenih u sekretnij dopovidi Matematichna teoriya kriptografiyi V oboh stattyah buv rozroblenij matematichnij aparat dlya vidpovidnih sistem Laboratoriyi Bella pracyuvali nad sekretnimi sistemami Ya pracyuvav nad sistemami zv yazku j takozh buv priznachenij v deyaki komiteti yaki vivchali tehniku kriptoanalizu Robota nad oboma matematichnimi teoriyami zv yazku j kriptografiyi jshla odnochasno z 1941 roku Ne mozhna skazati sho odna zavershilasya ranishe inshoyi obidvi buli tak blizki sho ne mogli buti rozdileni Klod Shennon ZmistStattya skladayetsya z troh chastin Matematichna struktura sekretnih sistem Teoretichna sekretnist i Praktichna sekretnist Matematichna struktura sekretnih sistem U pershij chastini statti vvedeno formalne viznachennya kriptosistemi simetrichnoyi kriptosistemi sho skladayetsya z dzherela povidomlen dzherela klyuchiv shifruvalnikiv povidomlennya klyucha kriptogrami j shifruvalnika protivnika Viznacheno funkciyu shifruvannya yaka zalezhit vid vihidnogo povidomlennya i klyucha proces deshifruvannya dlya oderzhuvacha povidomlennya sho skladayetsya v obchislenni vidobrazhennya zvorotnogo shifruvannyu i proces deshifruvannya dlya suprotivnika sprobi viznachiti pochatkove povidomlennya znayuchi tilki kriptogrammu i apriorni jmovirnosti riznih klyuchiv ta povidomlen Avtor takozh zaproponuvav podannya kriptosistemi u viglyadi dvochastkovogo grafa u vershinah yakogo roztashovani mozhlivi povidomlennya i mozhlivi kriptogrami a kozhnomu klyuchu shifruvannya postavleno u vidpovidnist mnozhinu reber sho z yednuyut kozhne mozhlive povidomlennya z vidpovidnoyu jomu kriptogramoyu Priklad grafa Shennona absolyutno sekretnoyi sistemi Mi i 1 4 vihidni povidomlennya Ei i 1 4 kriptogrami numeraciya dug grafa vidpovidaye numeraciyi klyuchiv 1 4 Navedeno matematichnij opis ranishe vidomih shifriv Rozglyanuto shifr prostoyi pidstanovki shifr Vizhener digramna trigramna i n grammna pidstanovki shifr Plejfera shifr z avtoklyuchem i drobovi shifri Osnovnimi kriteriyami ocinki vlastivostej stijkosti kriptosistem u statti nazvani rozmir dovzhina klyucha skladnist operacij shifruvannya i deshifruvannya mozhlivist abo nemozhlivist deshifruvannya povidomlennya protivnikom yedinim sposobom stupin vplivu pomilok pri shifruvanni i peredachi na otrimane povidomlennya ta stupin zbilshennya rozmiru povidomlennya u rezultati shifruvannya V kinci statti zaznacheno sho u razi shifruvannya skladenogo prirodnoyu movoyu povidomlennya mozhna polipshiti zagalnu ocinku kriptosistemi za vsima pererahovanim parametram odnochasno Zaproponovana struktura algebri sekretnih sistem algebri shifriv z dvoma osnovnimi operaciyami kombinuvannya shifriv zvazhena suma dodavannya shifriv z vagami u viglyadi jmovirnostej viboru shifru i vitvir poslidovne zastosuvannya Novi shifri zaproponovano otrimuvati kombinuvannyam zvazhenoyi sumi i kombinaciyi riznih shifriv Teoretichna sekretnist U drugij chastini statti viznacheno ponyattya doskonaloyi stijkosti kriptosistemi sistemi de vihidne povidomlennya i kriptograma statistichno nezalezhni Dovedena povna stijkist shifru Vernama odnorazovogo shifrobloknota Pokazana nenadijnist deyakih shifriv na prikladi shifru Cezarya v yakomu chastota poyavi simvoliv yaka vidpovidaye simvolam vihidnogo povidomlennya sho ne zalezhat vid klyucha Pri rozglyadi vipadkovogo shifru bulo vvedeno ponyattya vidstani yedinosti minimalnogo chisla simvoliv kriptogrami z dopomogoyu yakih klyuch mozhe buti viznachenij odnoznachno Takozh vidznachena problema nadmirnosti movi yaka polyagaye v tomu sho nadmirnist sho yavlyaye soboyu nabir umov nakladenih na simvoli povidomlennya daye dodatkovi mozhlivosti pri deshifruvanni kriptogrami protivnikom Vvedeno ponyattya idealno stijkoyi kriptosistemi yaka maye neskinchennu vidstan yedinosti Privatnim bilsh suvorim vipadkom takih sistem ye doskonalo sekretni sistemi Yih harakternoyu osoblivistyu ye te sho idealna kriptosistema zberigaye neviznachenist navit pri uspishnij operaciyi deshifruvannya protivnikom Praktichna bezpeka U tretij chastini statti viznachena robocha harakteristika kriptosistemi yak funkciya sho zalezhit vid chisla vidomih simvoliv kriptogrami i dorivnyuye serednim obsyagam roboti vitrachenij na znahodzhennya klyucha shifruvannya Cya funkciya maye deyaki podibnosti z ponyattyam obchislyuvalnoyi skladnosti algoritmu Rozglyanuto mozhlivist rozkrittya shifru za dopomogoyu statistichnogo analizu chastoti simvoliv zashifrovanogo tekstu i metodu imovirnih sliv Zgidno opisanoyi u statti teoriyi protivnik v procesi deshifruvannya mozhe vikoristovuvati deyaki statistichni vlastivosti movi Pokazano sho napriklad za umovi znannya movi vihidnogo povidomlennya dlya deyakih shifriv mozhlivo rozkriti tekst sho skladayetsya z dekilkoh desyatkiv simvoliv V yakosti prikladu sliv slovospoluchen yaki najchastishe zustrichayutsya v anglijskij movi avtor naviv konstrukciyi the and that i sklad tion a v yakosti poyednannya simvoliv qu sho pryamo pov yazano z pitannyam pro rozglyanutih u drugij chastini statti Zaproponovano vikoristovuvati kilka shariv cikliv zamin i zmin sho zgodom bulo vikoristano pri pobudovi blochnih shifriv V originalnij statti Shennon nazvav ci metodi confusion zaplutuvannya vidpovidaye zamini i diffusion rozsiyuvannya vidpovidaye perestanovci Ocinki vplivuU knizi Zlomshiki kodiv Devida Kana vislovleno dumku pro te sho v toj chas yak stattya Matematichna teoriya zv yazku posluzhila pochatkom rozvitku teoriyi informaciyi u statti Teoriya zv yazku v sekretnih sistemah rozglyanuta naukova sutnist kriptografiyi Vidznacheno velikij vnesok avtora u vkazivci na movnu nadmirnist yak grunt dlya kriptoanalizu i sho same Shennon vpershe vviv fundamentalni principi deshifruvannya Inshoyu vazhlivoyu ideyeyu statti Shennona v knizi Kana vvazhayetsya vvedennya vidstani yedinosti Vitfild Diffi i Martin Gellman u statti Novi napryamki v kriptografiyi angl New Directions in Cryptography konstatuvali sho Shennon v Teoriyi zv yazku v sekretnih sistemah doviv doskonalu sekretnist odnorazovogo shifrobloknota ale jogo vikoristannya ye praktichno nezdijsnennoyu zadacheyu dlya bilshosti prikladnih cilej Isnuye dumka sho cya stattya Diffi i Gellmana prizvela do prorivu v kriptografiyi tomu sho bulo pokazano yak storoni mozhut otrimati zagalnij sekretnij klyuch vikoristovuyuchi nezahishenij vid prosluhovuvannya kanal zv yazku chogo ne bulo v kriptografiyi opisanoyi v statti Shennona Bryus Shnajyer u knizi Prikladna Kriptografiya zaznachiv sho do 1967 roku literatura z kriptografiyi bula bezzmistovnoyu za odnim ridkisnim vinyatkom yakim ye stattya Teoriya zv yazku v sekretnih sistemah U knizi en pomicheno sho stattya ye odniyeyu z krashih osnovopolozhnih statej iz zahistu informaciyi j vazhlivo sho vona poyednuye praktichnu ta teoretichnu storonu pitannya vvodit fundamentalni ideyi nadmirnosti i vidstani yedinosti V Enciklopediyi z kriptografiyi ta bezpeki vkazano na vpliv zaproponovanoyi v danij roboti ideyi pro vikoristannya dekilkoh cikliv sho skladayutsya iz zamini ta perestanovki na stvorennya blochnih shifriv i SP merezhi Takozh osoblivo vidznachena model kriptosistemi opisana Shennonom i teorema pro doskonaloyi sekretnosti shifru Vernama Krim togo odniyeyu z najbilsh citovanih maksim v kriptografiyi nazvano pripushennya z pershoyi chastini statti Protivniku vidoma zastosovana sistema angl The enemy knows the system being used PrimitkiV I Levin K E ShENNON I SOVREMENNAYa NAUKA Vestnik TGTU statya 2008 T 14 3 S 714 716 ISSN 0136 5835 杉本 舞 C E シャノンの暗号理論 22 kvitnya 2018 yap 科学哲学科学史研究 statya 京都大学文学部科学哲学科学史研究室 2006 T 1 20 3月 S 139 142 144 DOI 10 14989 56970 Whitfield Diffie Preface to Claue Shannon s A Mathematical Theory of Cryptography 21 kvitnya 2018 angl IACR statya 2015 December Claude Shannon A Mathematical Theory of Cryptography 28 bereznya 2016 angl 1945 1 September Agranovskij Hadi Hellman An Extension of the Shannon Theory Approach to Cryptography IEEE Trans Inf Theory Davio Goethals Elements of Cryptology Secure Digital Communications V V Yashenko N P Varnovskij Yu V Nesterenko G A Kabatyanskij P N Devyanin V G Proskurin A V Cheremushkin P A Gyrdymov A Yu Zubov A V Zyazin V N Ovchinnikov M I Anohin Vvedenie v kriptografiyu otvetstvennyj PDF Arhiv originalu PDF za 29 listopada 2016 Procitovano 21 kvitnya 2018 PDF Arhiv originalu PDF za 4 listopada 2016 Procitovano 21 kvitnya 2018 Encyclopedia of Cryptography and Security Henk C A van Tilborg 1 Springer 205 S 12 41 146 161 169 206 244 289 290 323 372 480 568 601 602 684 s ISBN 9781441959065 B Schneier Applied cryptography 2nd ed protocols algorithms and source code in C U Vikidzherelah ye Q27960404PosilannyaStattya Shennona A Mathematical Theory of Cryptography 28 bereznya 2016 u Wayback Machine na sajti IACR Stattya Shennona Communication Theory of Secrecy Systems 4 listopada 2016 u Wayback Machine na sajti Wiley Online Library Storinka statti na Google Scholar 4 listopada 2016 u Wayback Machine Storinka publikaciyi na IEEE Xplore Digital Library 22 bereznya 2018 u Wayback Machine