О применениях математики в криптографии

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

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

Основы современ­ной тео­рии сек­рет­ной связи были раз­ра­бо­таны Кло­дом Шен­но­ном во время Вто­рой миро­вой войны. Им была тео­ре­ти­че­ски обос­но­вана возмож­ность постро­е­ния совершен­ного шифра — такого спо­соба шиф­ро­ва­ния, что у пере­хва­тившего пре­об­ра­зо­ван­ное сообще­ние зло­умыш­лен­ника не будет ни одной «зацепки» для выде­ле­ния исход­ного сообще­ния.

Допу­стим, что есть сообще­ние, кото­рое надо зашиф­ро­вать и пере­дать полу­ча­телю. Сна­чала исход­ное сообще­ние «оциф­ро­вы­вают», запи­сав его в виде дво­ич­ной после­до­ва­тель­но­сти, состо­ящей из нулей и еди­ниц. Спо­собы пре­об­ра­зо­ва­ния сообще­ния (и шиф­ро­ва­ние, и расшиф­ро­ва­ние) можно подго­то­вить зара­нее, если усло­виться, что сообще­ние в виде дво­ич­ной после­до­ва­тель­но­сти должно иметь не более $T$ зна­ков. Стро­ится сек­рет­ная слу­чай­ная дво­ич­ная после­до­ва­тель­ность длины $T$ (напри­мер, её можно полу­чить, под­бра­сы­вая $T$ раз иде­аль­ную монету и полагая оче­ред­ной знак рав­ным 1, если выпал «орёл», и 0, если выпала «решка»). Эту сек­рет­ную после­до­ва­тель­ность («ключ») необ­хо­димо доста­вить отпра­ви­телю и полу­ча­телю так, чтобы никому, кроме них, она не была известна. Когда при­дёт время пере­дачи, отпра­ви­тель восполь­зу­ется клю­чом: «сложит по модулю 2» (т. е. по пра­вилу $0+0=0$, $0+1=1$, $1+1=0$) каж­дый знак пере­да­ва­емого сообще­ния с соот­вет­ствующим зна­ком ключа. Полу­чен­ная после­до­ва­тель­ность и будет зашиф­ро­ван­ным сообще­нием. При­няв зашиф­ро­ван­ное сообще­ние, полу­ча­тель также восполь­зу­ется сек­рет­ным клю­чом: при­ба­вит (по модулю 2) к каж­дому знаку зашиф­ро­ван­ного сообще­ния соот­вет­ствующий знак ключа и вос­ста­но­вит исход­ное сообще­ние.

Опи­сан­ный шифр явля­ется совершен­ным, так как при­бав­ле­ние к шиф­ро­ван­ному сообще­нию всех возмож­ных дво­ич­ных после­до­ва­тель­но­стей длины $T$ даёт все возмож­ные дво­ич­ные после­до­ва­тель­но­сти, и выде­лить из них истин­ное сообще­ние без зна­ния ключа будет невозможно. Однако если исполь­зо­вать ту же сек­рет­ную после­до­ва­тель­ность ещё хотя бы раз, то шифр пере­ста­нет быть совершен­ным.

Понятно, что при­ме­нять подоб­ные шифры при больших объёмах пере­писки неудобно. Как пра­вило, для шиф­ро­ва­ния исполь­зуют элек­трон­ные устройства или компью­тер­ные программы, реа­ли­зующие слож­ные алго­ритмы пре­об­ра­зо­ва­ния сколь угодно длин­ных сообще­ний с помощью сек­рет­ных клю­чей. Таким обра­зом, при выбран­ном алго­ритме зашиф­ро­ван­ное сообще­ние явля­ется функцией от исход­ного сообще­ния и ключа. Эту связь можно рас­смат­ри­вать как урав­не­ние отно­си­тельно ключа, если известны алго­ритм, исход­ное и зашиф­ро­ван­ное сообще­ния. Чтобы обес­пе­чить прак­ти­че­скую невозмож­ность реше­ния таких урав­не­ний пере­бо­ром всех возмож­ных клю­чей, множе­ство этих клю­чей должно быть аст­ро­номи­че­ски велико.

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

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

Крип­тография явля­ется бога­тым источ­ни­ком труд­ных матема­ти­че­ских задач, а матема­тика — одной из основ крип­тографии. Исто­рия пока­зы­вает, что рано или поздно раз­ви­тие матема­ти­че­ских мето­дов и тех­ники при­во­дит к тому, что задачи, казавши­еся нераз­решимыми, нахо­дят реше­ние. Отста­ва­ние в твор­че­ском сорев­но­ва­нии матема­ти­ков раз­ных стран может при­ве­сти к пораже­ниям в эко­номике, дипло­ма­тии и воен­ных опе­рациях.

Разворот книги

Книга «Математическая составляющая»
Книга «Математическая составляющая»

Лите­ра­тура

Дори­ченко С. А., Ященко В. В. 25 этю­дов о шиф­рах. — М.: ТЕИС, 1994.

Вве­де­ние в крип­тографию / Под ред. В. В. Ященко. — 4‐е изд. — М.: МЦНМО, 2012.