Kryptoanalyysi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 11. joulukuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Kryptaanalyysi ( muista kreikkalaisista sanoista κρυπτός "piilotettu" + " analyysi ") on tiedettä menetelmistä salatun tiedon purkamiseksi ilman tähän tarkoitettua avainta , sekä itse tällaisen salauksen purkamisprosessista.

Useimmissa tapauksissa kryptausanalyysi tarkoittaa avaimen selvittämistä; kryptoanalyysi sisältää myös menetelmiä salausalgoritmien tai - protokollien haavoittuvuuden havaitsemiseksi .

Yritystä murtaa tietty salaus käyttämällä kryptausanalyysimenetelmiä kutsutaan salaushyökkäykseksi kyseiseen salaukseen. Salaushyökkäystä, joka rikkoo salauksen, kutsutaan salauksen "säröksi" tai "säröksi".

Amerikkalainen kryptografi William F. Friedman otti termin käyttöön vuonna 1920 osana kirjaansa The Elements of Cryptanalysis [1] .

Kryptusanalyysimenetelmät perustuivat alun perin luonnollisen tekstin kielellisiin malleihin ja toteutettiin vain kynällä ja paperilla. Ajan myötä puhtaasti matemaattisten menetelmien rooli kryptausanalyysissä kasvaa, jonka toteuttamiseen käytetään erikoistuneita kryptanalyyttisiä tietokoneita .

Kryptusanalyysin historia

Salausanalyysi kehittyi kryptografian kehityksen myötä: uudet, edistyneemmät salaukset korvasivat jo rikkoutuneita koodausjärjestelmiä vain kryptanalyytikoille keksiäkseen kehittyneempiä menetelmiä salausjärjestelmien rikkomiseen. Salauksen ja kryptoanalyysin käsitteet liittyvät erottamattomasti toisiinsa: hakkerointia kestävän järjestelmän luomiseksi on otettava huomioon kaikki mahdolliset tavat hyökätä siihen.

Klassinen kryptausanalyysi

Vaikka kryptoanalyysin käsite otettiin käyttöön suhteellisen äskettäin, jotkut hakkerointimenetelmät keksittiin kymmeniä vuosisatoja sitten. Ensimmäinen tunnettu kirjallinen maininta kryptoanalyysistä on " Käsikirjoitus kryptografisten viestien salauksen purkamisesta ", jonka arabitutkija Al-Kindi kirjoitti jo 800-luvulla. Tämä tieteellinen työ sisältää kuvauksen taajuusanalyysimenetelmästä .

Taajuusanalyysi on tärkein työkalu useimpien klassisten permutaatio- tai korvaussalausten murtamiseen. Tämä menetelmä perustuu oletukseen, että symbolien ja niiden sekvenssien ei-triviaali tilastollinen jakauma on olemassa sekä selkeässä että salakirjoituksessa. Lisäksi tämä jakelu säilyy merkkien korvaamiseen saakka sekä salaus- että salauksenpurkuprosessissa. On syytä huomata, että jos salatun viestin pituus on riittävän suuri, yksiaakkosiset salaukset ovat helposti sovellettavissa taajuusanalyysiin: jos kirjaimen esiintymistiheys kielessä ja tietyn merkin esiintymistiheys salatekstissä olevat ovat suunnilleen yhtä suuret, niin tässä tapauksessa voidaan suurella todennäköisyydellä olettaa, että tämä merkki ja on sama kirjain. Yksinkertaisin esimerkki frekvenssianalyysistä olisi yksinkertaisesti laskea jokaisen havaitun merkkien lukumäärä, ja seurata sitten menettelyä, jossa tuloksena saatu merkkien määrä jaetaan tekstin kaikkien merkkien määrällä ja kerrotaan tulos sadalla edustamaan lopullinen vastaus prosentteina. Lisäksi saatuja prosenttiarvoja verrataan oletetun alkuperäisen kielen kirjainten todennäköisyysjakauman taulukkoon.

1400-1500-luvuilla Euroopassa luotiin ja kehitettiin monikirjaimia korvaavia salauksia . Tunnetuin on ranskalaisen diplomaatin Blaise de Vigenèren salakirjoitus, joka perustui useiden Caesar -salausten sarjaan, joilla on erilaiset siirtoarvot. Kolmen vuosisadan ajan Vigenère-salausta pidettiin täysin kryptografisesti vakaana, kunnes vuonna 1863 Friedrich Kasiski ehdotti omaa menetelmää tämän salauksen murtamiseen. Kasiska-menetelmän perusidea on seuraava: jos pelkässä tekstissä kahden identtisen merkistön välissä on sellainen tekstilohko, että sen pituus on avainsanan pituuden monikerta, niin nämä identtiset pelkkä tekstijoukot merkit menevät samoihin salatekstin osiin salauksen aikana. Käytännössä tämä tarkoittaa, että jos salatekstissä on identtisiä kolmen tai useamman merkin segmenttejä, on suuri todennäköisyys, että nämä segmentit vastaavat samoja selkeän tekstin segmenttejä. Kasiska-menetelmän soveltaminen: salatekstistä etsitään identtisten kolmen tai useamman pituisten segmenttien pareja, minkä jälkeen lasketaan niiden välinen etäisyys eli merkkien lukumäärä, jotka erottavat parillisten segmenttien aloituspaikat. Kaikkien identtisten segmenttien parien analyysin tuloksena saamme joukon etäisyyksiä d 1 , d 2 , d 3 , ... Avainsanan pituus on kunkin etäisyyden jakaja ja siksi niiden suurimmaksi yhteiseksi jakajaksi.

Kryptusanalyysin kehityksen seuraava vaihe liittyy pyörivien salauskoneiden, kuten esimerkiksi Arthur Scherbiuksen keksimän Enigman , keksimiseen . Tällaisten laitteiden tarkoituksena oli minimoida toistuvien salatekstin segmenttien lukumäärä, joiden esiintymistilastoja käytettiin Vigenèren salauksen murtamiseen. Puolalaiset kryptanalyytikot onnistuivat rakentamaan prototyypin salauksenpurkukoneen natsi-Saksan käyttämälle Enigman versiolle . Kone sai nimen " Bomb " siitä, että se piti käytön aikana kellon tikitystä muistuttavia ääniä. Myöhemmin englantilaiset kryptanalyytikot viimeistelivät sen ja hyväksyivät sen.

Nykyaikainen kryptausanalyysi

Uusien salausmenetelmien kehittyessä matematiikasta tuli yhä tärkeämpää. Joten esimerkiksi taajuusanalyysissä kryptanalyytikon tulee olla sekä kielitieteen että tilastotieteen tuntemus. Enigman kryptausanalyysin teoreettisen työn suorittivat pääasiassa matemaatikot, kuten Alan Mathison Turing . Siitä huolimatta kryptografia on saman matematiikan ansiosta saavuttanut sen kehityksen, että hakkerointiin tarvittavien alkeismatemaattisten operaatioiden määrä alkoi saavuttaa tähtitieteellisiä arvoja. Nykyaikaisesta kryptografiasta on tullut paljon vastustuskykyisempi kryptoanalyysille kuin aiemmin käytetyt, vanhentuneet tekniikat, jotka riittivät rikkoutumaan kynällä ja paperilla. Saattaa näyttää siltä, että puhdas teoreettinen kryptausanalyysi ei pysty murtamaan nykyaikaisia salauksia tehokkaammin. Siitä huolimatta historioitsija David Kahn kirjoittaa muistiinpanossaan National Security Agencyn 50-vuotispäivänä:

”Nykyään sadat yritykset tarjoavat monia erilaisia kryptojärjestelmiä, joita ei voida rikkoa millään tunnetuista kryptoanalyysimenetelmistä. Itse asiassa tällaiset järjestelmät ovat vastustuskykyisiä jopa valitulle selväkieliselle hyökkäykselle, eli selkeän tekstin ja sitä vastaavan salatekstin vertailu ei paljasta salausavainta, joka mahdollistaisi muiden viestien salauksen purkamisen. Näin ollen kryptoanalyysi on tietyssä mielessä kuollut. Mutta tämä ei ole loppu. Kryptanalyysi voi olla kuollut, mutta metaforisesti puhuen kissa voidaan nylkeä monella tapaa.

Lisäksi muistiinpanossaan hän kuvailee tietojen sieppauksen, bugien, sivukanavahyökkäysten ja kvanttitietokoneiden kasvavaa merkitystä tekniikoina, jotka korvaavat perinteiset kryptaanalyysimenetelmät. Vuonna 2010 entinen kansallisen turvallisuuden pääosaston CTO Brian Snow totesi, että kaupallinen salaus on melkein saavuttanut tiedustelupalvelujen käyttämän teknologian tason, ja nyt ne ovat yhdessä "hyvin hitaasti etenemässä jo täysin tutkitulla alueella".

Kryptusanalyysiä on kuitenkin vielä liian aikaista kirjoittaa pois. Ensinnäkin ei tiedetä, kuinka tehokkaita erikoispalveluiden käyttämät kryptoanalyysimenetelmät ovat, ja toiseksi nykyaikaisen tietokonesalauksen muodostumisen ja kehittämisen vuosien aikana on esitetty monia väitteitä sekä teoreettisille että käytännön kryptografisille primitiivisille:

vuonna 1998 haavoittuvuus salatekstipohjaisia hyökkäyksiä vastaan löydettiin lohkosalauksesta MADRYGA , jota ehdotettiin jo vuonna 1984, mutta jota ei käytetty laajalti;
joukko tiedeyhteisön hyökkäyksiä, joista monet olivat täysin käytännöllisiä, tuhosivat kirjaimellisesti FEAL -lohkosalauksen, jota ehdotettiin DES : n korvaamiseksi tavallisena salausalgoritmina, mutta jota ei myöskään käytetty laajalti;
on myös havaittu, että laajalti saatavilla olevilla laskentatyökaluilla A5/1- , A5/2- , CMEA- lohkosalaukset ja DECT -salaukset, joita käytetään matkaviestinnän ja langattoman puhelinliikenteen turvaamiseen, voidaan rikkoa tunneissa tai minuuteissa, ja joskus ja todellisuudessa. aika;
Raaka voimahyökkäys auttoi murtamaan joitain sovelletuista suojausjärjestelmistä, kuten CSS -järjestelmästä, joka suojaa DVD -median digitaalista mediasisältöä .

Näin ollen vaikka nykypäivän turvallisimmat salaukset vastustavat paljon enemmän kryptausanalyysiä kuin Enigma, kryptausanalyysillä on silti tärkeä rooli laajalla tietoturva-alalla.

Kryptanalyysimenetelmät

Bruce Schneier tunnistaa 4 pää- ja 3 muuta kryptausanalyysimenetelmää olettaen, että kryptanalyytikko tuntee salausalgoritmin ( Kerckhoffin periaatteen mukaisesti ):

Kryptusanalyysin perusmenetelmät

Salatekstipohjainen hyökkäys .
Selkeisiin teksteihin ja vastaaviin salateksteihin perustuva hyökkäys .
Valittu selkeä tekstihyökkäys (kyky valita salattava teksti).
Adaptive Plaintext Attack .

Muita kryptaanalyysimenetelmiä

Kryptusanalyysin perusmenetelmät

Salatekstihyökkäykset _

Oletetaan, että kryptanalyytikolla on tietty määrä salatekstejä, jotka on saatu saman salausalgoritmin käytön seurauksena. Tässä tapauksessa kryptanalyytikko voi suorittaa vain salatekstipohjaisen hyökkäyksen. Salaushyökkäyksen tavoitteena on tässä tapauksessa löytää mahdollisimman monta selkeää tekstiä, joka vastaa käytettävissä olevia salatekstejä, tai mikä vielä parempi, löytää salauksessa käytetty avain.

Kryptusanalyytikko voi saada tämän tyyppisen hyökkäyksen syöttötiedot yksinkertaisen salattujen viestien sieppauksen tuloksena. Jos tiedonsiirto tapahtuu avoimen kanavan kautta, tiedonkeruutehtävän toteuttaminen on suhteellisen helppoa ja triviaalia. Salakirjoituspohjaiset hyökkäykset ovat heikoimpia ja hankalia.

Selkeisiin teksteihin ja vastaaviin salateksteihin perustuva hyökkäys

Olkoon kryptanalyytikolla käytössään paitsi salatekstit myös vastaavat selkeät tekstit.

Sitten on kaksi vaihtoehtoa ongelman asettamiseen:

Etsi avain, jota käytetään muuttamaan selkeä teksti salatekstiksi.
Luo algoritmi, joka pystyy purkamaan minkä tahansa tällä avaimella koodatun viestin salauksen.

Selkeiden tekstien hankkimisella on ratkaiseva rooli tämän hyökkäyksen toteuttamisessa. Tavallisia tekstejä poimitaan useista lähteistä. Joten voit esimerkiksi arvata tiedoston sisällön sen tunnisteen perusteella.

Hakkeroidun kirjeenvaihdon tapauksessa voimme olettaa, että kirjeellä on seuraavanlainen rakenne:

"terveisiä";
"pääteksti";
"kohteliaisuuden lopullinen muoto";
"allekirjoitus".

Siksi hyökkäys voidaan järjestää valitsemalla erityyppiset "Terveiset" (esimerkiksi "Hei!", "Hyvää päivää" jne.) ja/tai "Viimeiset kohteliaisuudet" (kuten "Kunnioittavasti", "Teidänne" Ystävällisin terveisin" " jne.). Tämä hyökkäys on vahvempi kuin pelkkä salakirjoitushyökkäys.

Valittu selkokielinen hyökkäys

Suorittaakseen tämän tyyppisen hyökkäyksen kryptanalyytikolla ei tarvitse olla vain tietty määrä selkeitä tekstejä ja niistä johdettuja salatekstejä. Tässä tapauksessa kryptanalyytikon on muun muassa kyettävä poimimaan useita selkeitä tekstejä ja saamaan niiden salauksen tulos.

Kryptusanalyytikon tehtävät toistavat selkokielisen hyökkäyksen tehtäviä, eli salausavaimen hankkimista tai salauksen purkualgoritmin luomista annetulle avaimelle.

Voit saada syötetietoja tämän tyyppiselle hyökkäykselle esimerkiksi seuraavasti:

Luo ja lähetä väärennetty, salaamaton viesti, jonka väitetään olevan peräisin joltakin käyttäjistä, jotka tavallisesti käyttävät salausta.
Joissakin tapauksissa voit saada vastauksen, joka sisältää salakirjoituksen, joka lainaa väärennetyn viestin sisältöä.

Suorittaessaan tämän tyyppistä hyökkäystä kryptanalyytikolla on mahdollisuus valita selkeän tekstin lohkoja, jotka voivat tietyin edellytyksin mahdollistaa lisätietojen saamisen salausavaimesta.

Adaptive Plaintext Attacks

Tämäntyyppinen hyökkäys on kätevämpi erikoistapaus valitulle selkokieliselle hyökkäykselle. Mukautuvasti valitun selkotekstihyökkäyksen mukavuus on se, että sen lisäksi, että kryptaanalyytikko voi valita selvän tekstin, hän voi päättää salata yhden tai toisen selkeän tekstin jo saatujen salauksen ja myöhempien salauksenpurkutoimintojen tulosten perusteella. Toisin sanoen valitussa selkotekstihyökkäyksessä kryptanalyytikko valitsee vain yhden suuren selkeän tekstin lohkon myöhempää salausta varten ja alkaa sitten analysoida järjestelmää näiden tietojen perusteella. Mukautuvan hyökkäyksen järjestämisen tapauksessa kryptanalyytikko voi vastaanottaa minkä tahansa selkeän tekstin lohkojen salauksen tulokset kerätäkseen häntä kiinnostavia tietoja, jotka otetaan huomioon valittaessa seuraavia salattavaksi lähetettäviä selkeän tekstin lohkoja, ja pian. Palautteen läsnäolo antaa adaptiivisesti valittuun salatekstiin perustuvalle hyökkäykselle etua kaikkiin yllä oleviin hyökkäyksiin verrattuna.

Kryptusanalyysin lisämenetelmiä

Valittu salakirjoitushyökkäys

Oletetaan, että kryptanalyytikolla on väliaikainen pääsy salaustyökaluun tai -laitteeseen. Tässä tapauksessa kryptanalyytikko voi rajoitetun ajan saada tuntemistaan salateksteistä vastaavat selkeät tekstit, minkä jälkeen kryptanalyytikon on aloitettava järjestelmän analysointi. Tämän tyyppisessä hyökkäyksessä analyysin tavoitteena on saada salausavain.

Tämä ongelma voidaan muotoilla ytimekkäästi seuraavasti.

Annettu: $C_{1},P_{1}=D_{k}(C_{1});C_{2},P_{2}=D_{k}(C_{2});C_{3}, P_{3}=D_{k}(C_{3});\dots ;C_{n},P_{n}=D_{k}(C_{n}),$

missä on :s käytettävissä oleva salateksti, on vastaava selkeä teksti ja on salauksen purkutoiminto avaimella . $C_{n}$ $n$ $P_{n}$ $C_{n}$ $D_{k}$ $k$

Etsi: käytetty salausavain . $k$

Mielenkiintoista on , että valittua salatekstihyökkäystä voidaan kutsua myös " lounashyökkäykseksi " tai " keskiyön hyökkäykseksi ". Oletetaan, että otsikko " Lunchtime Attacks " kuvastaa sitä tosiasiaa, että laillinen käyttäjä voi jättää salauksenpurkukoneensa valvomatta lounasaikaan, ja kryptanalyytikko voi hyötyä tästä.

Avain-arvattu hyökkäys

Toisin kuin nimi, valitun avaimen hyökkäys ei tarkoita, että kryptanalyytikko harjoittaa yksinkertaista avaimien luettelointia toivoen löytävänsä oikean. Tämäntyyppinen hyökkäys perustuu siihen, että kryptanalyytikko voi tarkkailla useita avaimia käyttävän salausalgoritmin toimintaa. Kryptanalyytikko ei aluksi tiedä mitään avainten tarkasta merkityksestä, mutta hän tietää jonkin matemaattisen suhteen, joka yhdistää avaimet toisiinsa. Esimerkki tästä on tilanne, jossa kryptanalyytikko havaitsi, että kaikkien avainten viimeiset 80 bittiä ovat samat, vaikka itse bittien arvot voivat olla tuntemattomia.

Bandit cryptanalysis

Kryptanalyytikko voi käyttää niin sanottua " inhimillistä tekijää " eli yrittää kiristämällä, lahjomalla, kidutuksella tai muilla keinoilla saada tietoa salausjärjestelmästä tai jopa itse salausavaimesta. Esimerkiksi lahjuksen antamista, yhtenä gangsteri krypta-analyysin lajikkeista, voidaan kutsua "avaamiseksi avaimen ostolla". Siten ruumiinavaustekniikka on rakennettu ihmisten heikkoudelle kiinteänä osana tietoturvajärjestelmää.

Bandit-kryptausanalyysiä pidetään erittäin tehokkaana tapana rikkoa järjestelmä ja usein paras tapa murtaa salauksia.

Erilaiset hyökkäykset

Katso myös

American Cryptogram Association

Muistiinpanot

↑ David Kahn . Koodin katkaisijat . — M.: Tsentrpoligraf , 2000. — 473 s. — ISBN 5-227-00678-4 .

Kirjallisuus

David Kahn, Huomautuksia National Security Agencyn 50-vuotispäivänä , 1. marraskuuta 2002.
Schneier B. Cryptanalysis // Applied Cryptography. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodit julkaisussa C. - M. : Triumf, 2002. - S. 19-22. — 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .
Pilidi V. S. Kryptografia. Johdanto luvut . - Rostov-on-Don: SFU, 2009. - 110 s.
Alex Biryukov ja Eyal Kushilevitz.: Differentiaalisesta kryptaanalyysistä vain salakirjoitushyökkäyksiin

Linkit

Kryptoanalyysi: eilen, tänään, huomenna | avoimet järjestelmät. DBMS | Kustantaja "Open Systems" (venäjä)

Sanakirjat ja tietosanakirjat	iso kiinalainen Britannica (verkossa)
Bibliografisissa luetteloissa	GND : 4830502-9