Подпишитесь на наши новости
Вернуться к началу с статьи up
 

КРИПТОГРА́ФИЯ

  • рубрика

    Рубрика: Математика

  • родственные статьи
  • image description

    В книжной версии

    Том 16. Москва, 2010, стр. 38

  • image description

    Скопировать библиографическую ссылку:




Авторы: А. М. Зубков

КРИПТОГРА́ФИЯ (от крип­то... и ...гра­фия), 1) нау­ка о ме­то­дах пре­об­ра­зо­ва­ния ин­фор­ма­ции для её за­щи­ты при пе­ре­да­че по не­за­щи­щён­ным ка­на­лам свя­зи и о спо­со­бах прак­тич. реа­ли­за­ции этих ме­то­дов.

Пра­ви­ло крип­то­гра­фич. пре­об­ра­зо­ва­ния ин­фор­ма­ции на­зы­ва­ет­ся шиф­ром, про­цесс это­го пре­об­ра­зо­ва­ния – за­шиф­ро­ва­ни­ем, про­цесс пре­об­ра­зо­ва­ния за­шиф­ро­ван­но­го со­об­ще­ния в ис­ход­ное – рас­шиф­ро­ва­ни­ем. Тер­мин «де­шиф­ро­ва­ние» обо­зна­ча­ет про­цесс вос­ста­нов­ле­ния ис­ход­но­го со­об­ще­ния по за­шиф­ро­ван­но­му, ко­то­рый осу­ще­ст­в­ля­ет­ся по­сто­рон­ним ли­цом, не имею­щим в на­ча­ле это­го про­цес­са пол­но­го зна­ния о спо­собе рас­шиф­ро­ва­ния. В клас­сич. схе­ме шифр со­сто­ит из двух осн. эле­мен­тов: сек­рет­ного клю­ча (ко­то­рый не дол­жен быть из­вес­тен ни­ко­му, кро­ме от­пра­ви­те­ля и по­лу­ча­те­ля со­об­ще­ния) и спо­соба пре­об­ра­зо­ва­ния па­ры (со­об­ще­ние, ключ) в за­шиф­ро­ван­ное со­об­ще­ние и па­ры (за­шиф­ро­ван­ное со­об­ще­ние, ключ) – в ис­ход­ное со­об­ще­ние.

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

Крип­то­гра­фич. ме­то­ды ши­ро­ко ис­поль­зу­ют­ся в разл. сис­те­мах за­щи­ты ин­фор­ма­ции. Для ре­ше­ния за­дач раз­ра­бот­ки шиф­ров и ме­то­дов де­шиф­ро­ва­ния в раз­ное вре­мя при­вле­ка­лись мн. учё­ные, сре­ди ко­то­рых бы­ли ма­те­ма­ти­ки, напр. Ф. Ви­ет, Х. Гольд­бах, Н. Ви­нер, А. Тью­ринг. Ос­но­вы совр. тео­ре­тич. К. и тео­рии ин­фор­ма­ции бы­ли за­ло­же­ны в го­ды 2-й ми­ро­вой вой­ны К. Шен­но­ном. Он пред­ло­жил рас­смат­ри­вать шифр как ото­бра­же­ние пря­мо­го про­из­ве­де­ния мно­же­ст­ва $Z$ всех по­тен­ци­аль­но воз­мож­ных со­об­ще­ний и мно­же­ст­ва $K$ клю­чей в мно­же­ст­во $E$ за­шиф­ро­ван­ных тек­стов; при лю­бом фик­си­ро­ван­ном клю­че это ото­бра­же­ние $Z$ в $E$ долж­но быть об­ра­ти­мым. Шен­нон до­ка­зал, что шифр мо­жет быть со­вер­шен­ным (т. е. прин­ци­пи­аль­но не де­шиф­руе­мым) толь­ко в слу­чае, ко­гда чис­ло разл. клю­чей не мень­ше чис­ла воз­мож­ных со­об­ще­ний, и что ес­ли это ус­ло­вие вы­пол­не­но, то мож­но по­стро­ить со­вер­шен­ный шифр. При­ме­ром со­вер­шен­но­го шиф­ра яв­ля­ет­ся шифр гам­ми­ро­ва­ния. Ес­ли ис­ход­ное со­об­ще­ние пред­став­ле­но в ви­де дво­ич­ной по­сле­до­ва­тель­но­сти $m_1,m_2,…,m_T$, со­стоя­щей из ну­лей и еди­ниц, то в ка­че­ст­ве клю­ча нуж­но слу­чай­но и рав­но­ве­ро­ят­но вы­брать дво­ич­ную по­сле­до­ва­тель­ность $γ_1,γ_2,...,γ_T$ из мно­же­ст­ва всех $2^T$ дво­ич­ных по­сле­до­ва­тель­но­стей дли­ны $T$; то­гда со­вер­шен­ным бу­дет шифр, пе­ре­во­дя­щий $m_1,m_2,…,m_T в m_1+γ_1,m_2+γ_2,…,m_T+γ_T (все сло­же­ния про­во­дят­ся по мо­ду­лю 2), и по­лу­ча­тель, зная $γ_1,γ_2,...,γ_T$, мо­жет вос­ста­но­вить ис­ход­ное со­об­ще­ние, вы­чис­лив $(m_1+γ_1)+γ_1=m_1, (m_2+γ_2)+γ_2=m_2,…, (m_T+γ_T)+γ_T=m_T$. При этом от­пра­ви­тель и по­лу­ча­тель долж­ны за­ра­нее со­гла­со­вать зна­че­ние клю­ча $γ_1,γ_2,...,γ_T$, поль­зу­ясь ка­на­лом свя­зи, ко­то­рый за­ве­до­мо за­щи­щён от всех по­сто­рон­них (напр., пе­ре­слать ключ в за­пе­ча­тан­ном кон­вер­те с на­дёж­ным курь­е­ром). Ес­ли по­сто­рон­ний, у ко­то­ро­го нет ни­ка­кой ин­фор­ма­ции о $γ_1,γ_2,...,γ_T$, по­пы­та­ет­ся вос­ста­но­вить ис­ход­ное со­об­ще­ние, пе­ре­би­рая все воз­мож­ные ва­ри­ан­ты по­сле­до­ва­тель­но­сти $γ_1,γ_2,...,γ_T$, то он по­лу­чит все воз­мож­ные дво­ич­ные по­сле­до­ва­тель­но­сти дли­ны $T$, в т. ч. и $m_1,m_2,…,m_T$, но у не­го не бу­дет ос­но­ва­ний вы­де­лить со­об­ще­ние $m_1,m_2,…,m_T$ из мно­же­ст­ва всех ос­таль­ных ком­би­на­ций $T$ дво­ич­ных зна­ков. Не­удоб­ст­во ука­зан­но­го шиф­ра свя­за­но с не­об­хо­ди­мо­стью ис­поль­зо­ва­ния за­щи­щён­но­го ка­на­ла свя­зи для пе­ре­да­чи клю­чей, сум­мар­ная дли­на ко­то­рых не мень­ше сум­мар­ной дли­ны бу­ду­щих сек­рет­ных со­об­ще­ний. По­это­му на прак­тике ис­поль­зу­ют­ся шиф­ры, в ко­то­рых объ­ём клю­чей су­ще­ст­вен­но мень­ше объ­ё­ма пе­ре­да­вае­мых сек­рет­ных со­об­ще­ний. Та­кие шиф­ры не мо­гут быть со­вер­шен­ны­ми; во­об­ще го­во­ря, за­шиф­ро­ван­ные с их по­мо­щью со­об­ще­ния мож­но де­шиф­ро­вы­вать с по­мо­щью пол­но­го пе­ре­бо­ра всех воз­мож­ных клю­чей. Под стой­ко­стью шиф­ра обыч­но по­ни­ма­ют вре­мя ра­бо­ты наи­луч­ше­го ал­го­рит­ма вы­чис­ле­ния сек­рет­но­го клю­ча по из­вест­ным па­рам ис­ход­ных и за­шиф­ро­ван­ных со­об­ще­ний и из­вест­ным пра­ви­лам за­шиф­ро­ва­ния. Од­на­ко су­ще­ст­вую­щие ме­то­ды по­зво­ляют по­лу­чать толь­ко верх­ние оцен­ки стой­ко­сти шиф­ров (а имен­но, оцен­ки вре­ме­ни ра­бо­ты кон­крет­ных ал­го­рит­мов вы­чис­ле­ния клю­ча).

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

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

Совр. шиф­ра­то­ры де­лят­ся на 2 клас­са: по­точ­ные и блоч­ные. По­точ­ные шиф­ра­то­ры пред­став­ля­ют со­бой элек­трон­ные уст­рой­ст­ва с ячей­ка­ми па­мя­ти и спе­циа­ли­зир. про­цес­со­ра­ми; они вы­ра­ба­ты­ва­ют по­сле­до­ва­тель­но­сти не­ко­то­рых зна­ков и ис­поль­зу­ют их вме­сто слу­чай­ной рав­но­ве­ро­ят­ной по­сле­до­ва­тель­но­сти в шиф­ре гам­ми­ро­ва­ния. По­сле­до­ва­тель­ность, вы­ра­ба­ты­вае­мая по­то­ко­вым шиф­ра­то­ром, од­но­знач­но оп­ре­де­ля­ет­ся клю­че­вы­ми па­ра­мет­ра­ми, за­даю­щи­ми на­чаль­ные со­стоя­ния яче­ек па­мя­ти ко­неч­но­го ав­то­ма­та и вы­бор тех или иных ва­ри­ан­тов ра­бо­ты про­цес­со­ров. Это по­зво­ля­ет от­пра­ви­те­лю и по­лу­ча­те­лю, со­гла­со­вав­шим за­ра­нее зна­че­ния клю­че­вых па­ра­мет­ров, вы­ра­ба­ты­вать од­ну и ту же по­сле­до­ва­тель­ность $γ_1, γ_2,..., γ_T$. Блоч­ные шиф­ра­то­ры раз­би­ва­ют ис­ход­ное со­об­ще­ние, пред­став­лен­ное в ви­де дво­ич­ной по­сле­до­ва­тель­но­сти, на бло­ки оди­на­ко­во­го раз­ме­ра (напр., по 64, 128 или бо­лее би­тов), вы­чис­ля­ют об­ра­зы этих бло­ков при вза­им­но од­но­знач­ном ото­бра­же­нии, кон­крет­ный вид ко­то­ро­го за­ви­сит от сек­рет­но­го клю­ча, и объ­е­ди­ня­ют об­ра­зы бло­ков в за­шиф­ро­ван­ное со­об­ще­ние. По­лу­ча­тель, ис­поль­зуя тот же сек­рет­ный ключ, что и от­пра­ви­тель, раз­би­ва­ет по­лу­чен­ное со­об­ще­ние на бло­ки и, при­ме­няя к ним об­рат­ное ото­бра­же­ние, вос­ста­нав­ли­ва­ет ис­ход­ное со­об­ще­ние.

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

В схе­ме шиф­ро­ва­ния с от­кры­тым клю­чом, пред­ло­жен­ной в 1976 амер. учё­ны­ми У. Диф­фи и М. Хелл­ма­ном, ис­поль­зу­ют­ся се­мей­ст­ва $\{E_e, e∈M\}$ и $\{D_d, d∈M\}$ ото­бра­же­ний за­шиф­ро­ва­ния и рас­шиф­ро­ва­ния со­от­вет­ст­вен­но, дей­ст­вую­щие на ко­неч­ном мно­же­ст­ве $K$ (напр., на мно­же­ст­ве клю­чей шиф­ра­то­ра) и об­ла­даю­щие сле­дую­щи­ми свой­ст­ва­ми: а) для ка­ж­до­го $e∈M$ су­ще­ст­ву­ет та­кое $d∈M$, что $E_e$ и $D_d$ – вза­им­но об­рат­ные ото­бра­же­ния; б) за­да­ча на­хо­ж­де­ния зна­че­ния $k$ из мно­же­ст­ва $K$ по ото­бра­же­нию $E_e$ и зна­че­нию $z=E_e(k)$ вы­чис­ли­тель­но не­раз­ре­ши­ма за за­дан­ное вре­мя; в) су­ще­ст­ву­ют не очень слож­ные спо­со­бы вы­чис­ле­ния зна­че­ний ото­бра­же­ний $E_e$ и $D_d$ и по­строе­ния пар вза­им­но об­рат­ных ото­бра­же­ний $(E_e, D_d)$.

Ес­ли та­кие се­мей­ст­ва вы­бра­ны, то лю­бой або­нент $A$ мо­жет вы­ра­бо­тать па­ру вза­им­но об­рат­ных ото­бра­же­ний $(E_e, D_d)$, со­об­щить всем же­лаю­щим пра­ви­ло вы­чис­ле­ния ото­бра­же­ния $E_e$ (от­кры­тый ключ), а пра­ви­ло вы­чис­ле­ния $D_d$ (сек­рет­ный ключ) дер­жать в сек­ре­те. Лю­бой або­нент $B$, что­бы пе­ре­дать або­нен­ту $A$ зна­че­ние $k$ в ви­де, за­щи­щён­ном от по­сто­рон­них, мо­жет пе­ре­дать або­нен­ту $A$ по об­ще­дос­туп­но­му ка­на­лу свя­зи зна­че­ние $z=E_e(k)$. То­гда або­нент $A$, знаю­щий ото­бра­же­ние $D_d$, смо­жет вос­ста­но­вить $k$ по $z$, а по­сто­рон­ние, не знаю­щие $D_d$ и не имею­щие воз­мож­но­сти по­стро­ить $D_d$ по $E_e$, не смо­гут это­го сде­лать. Т. к. ма­те­ма­ти­че­ски стро­го обос­но­ван­ные при­ме­ры ото­бра­же­ний, удов­ле­тво­ряю­щих ус­ло­вию б), ещё не най­де­ны, У. Диф­фи и М. Хелл­ман пред­ло­жи­ли ис­поль­зо­вать для по­строе­ния сис­тем шиф­ро­ва­ния с от­кры­тым клю­чом ал­го­рит­мич. за­да­чи, счи­таю­щие­ся вы­чис­ли­тель­но слож­ны­ми. Ны­не пред­ло­жен ряд сис­тем шиф­ро­ва­ния с от­кры­тым клю­чом, ос­но­ван­ных на слож­но­сти ре­ше­ния за­дач ти­па раз­ло­же­ния на­ту­раль­ных чи­сел на про­стые мно­жи­те­ли, вы­чис­ле­ния квад­рат­но­го кор­ня в муль­ти­п­ли­ка­тив­ной груп­пе вы­че­тов по со­став­но­му мо­ду­лю, дис­крет­но­го ло­га­риф­ми­ро­ва­ния [т. е. ре­ше­ния срав­не­ния ви­да $ax≡b (\mod n)$, где $n$ – дос­та­точ­но боль­шое на­ту­раль­ное чис­ло], ана­ло­гич­ных за­дач для групп эл­лип­тич. кри­вых над ко­неч­ны­ми по­ля­ми и не­ко­то­рых дру­гих.

По­треб­но­сти ком­мер­че­ских и фи­нан­со­вых ор­га­ни­за­ций, а так­же осо­бен­но­сти элек­трон­ных средств свя­зи, за­да­чи за­щи­ты элек­трон­ных баз дан­ных и т. п. сти­му­ли­ро­ва­ли раз­ра­бот­ку ря­да но­вых на­прав­ле­ний ис­поль­зо­ва­ния крип­то­гра­фич. ме­то­дов: за­щи­ты ин­фор­ма­ции в ком­пь­ю­тер­ных се­тях, т. н. элек­трон­ной под­пи­си, иден­ти­фи­ка­ции поль­зо­ва­те­ля (как при де­ло­вой пе­ре­пис­ке, так и при ис­поль­зова­нии элек­трон­ных кре­дит­ных карт), ме­то­дов раз­де­ле­ния сек­ре­та (та­ких спо­со­бов раз­де­ле­ния сек­рет­ной ин­фор­ма­ции ме­ж­ду $n$ ли­ца­ми, ко­то­рые не по­зво­ля­ют по­лу­чить ни­ка­кой ин­фор­ма­ции о сек­ре­те, ес­ли од­но­вре­мен­но не со­бе­рёт­ся хо­тя бы $k$ лиц из этой груп­пы) и т. п.

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

Прак­ти­че­ски все крип­то­гра­фич. спо­со­бы пре­об­ра­зо­ва­ния ин­фор­ма­ции яв­ля­ют­ся де­тер­ми­ни­ро­ван­ны­ми. При ана­ли­зе спо­со­бов шиф­ро­ва­ния час­то ис­поль­зу­ют­ся ве­ро­ят­но­ст­ные ме­то­ды, при­ме­няе­мые к ве­ро­ят­но­ст­ным мо­де­лям де­тер­ми­ни­ро­ван­ных крип­то­гра­фич. ал­го­рит­мов. В кон. 20 – нач. 21 вв. в К. ста­ли про­ни­кать идеи и ме­то­ды кван­то­вой тео­рии ин­фор­ма­ции и кван­то­вой свя­зи.

2) Тай­но­пись, сис­те­ма из­ме­не­ния пись­ма с це­лью сде­лать текст не­по­нят­ным для не­по­свя­щён­ных.

3) Раз­дел па­лео­гра­фии, изу­чаю­щий гра­фи­ку сис­тем тай­но­пи­си.

Лит.: Шен­нон К. Э. Ра­бо­ты по тео­рии ин­фор­ма­ции и ки­бер­не­ти­ке. М., 1963; Diffie W., Hell­man M. E. New directions in cryptogra­phy // IEEE Transactions on Information The­ory. 1976. Vol. 22. P. 644–654; Са­ло­маа А. Крип­то­гра­фия с от­кры­тым клю­чом. М., 1996; Menezes A. J., Oorschot PC. van, Vanstone Scott A. Handbook of applied cryptography. Bo­ca Raton, 1997; Кан Д. Взлом­щи­ки ко­дов. М., 2000; Коб­лиц Н. Курс тео­рии чи­сел и крип­то­гра­фии. М., 2001; Со­бо­ле­ва Т. А. Ис­то­рия шиф­ро­валь­но­го де­ла в Рос­сии. M., 2002; Шнай­ер Б. При­клад­ная крип­то­гра­фия. М., 2002; Ос­но­вы крип­то­гра­фии. 3-е изд. М., 2005.

Вернуться к началу