Kryptoanalyysi

Kryptoanalyysi on tieteenala, joka pyrkii kehittämään matemaattisia keinoja kryptografisien tekniikoiden voittamiseen eli salakirjoituksen murtamiseen. Molemmat sisältyvät kryptologiaan.

Kryptoanalyysillä pyritään murtamaan salaus tuntematta purkuavainta. Purkuavainta etsitään salausalgoritmien ominaisuuksien ja siirrettävän datan ominaisuuksien perusteella. Salatun viestin purkaminen raa'alla voimalla tarkoittaa, että salauksen purkuun ei tunneta muuta menetelmää kuin kaikkien mahdollisten avainavaruuden alkioiden kokeileminen. Tätä jatketaan, kunnes viesti saadaan ymmärrettävään muotoon. Esimerkiksi AES-salattua viestiä pidetään murtamattomana, joten tällaisen viestin purkuun ei tunneta muuta menetelmää kuin raaka voima, joka 256-bittisellä AES-salauksella veisi kymmeniä vuosia nykyisillä supertietokoneillakin.

Kryptoanalyysin historia  

Ennen arabialaisen Abu Yusuf al-Kindin keksimää kryptoanalyyttista menetelmää salakirjoituksella salattuja viestejä oli lähes mahdotonta avata ilman koodiavainta. Hänen uudenaikaisten menetelmiensä, kuten frekvenssianalyysi, ansiosta syntyi kryptoanalyytikkojen ammatti. Kryptoanalyysi levisi keskiajalla myös Eurooppaan, missä muutama kryptoanalyytikko tuli hyvin tunnetuksi.

Giovanni Soro oli ensimmäisiä suuria eurooppalaisia kryptoanalyytikkoja. Soro nimitettiin Venetsian salakirjoitussihteeriksi 1506. Soro niitti paljon mainetta, ja häneen turvauduttiin useasti Venetsiankin ulkopuolelta. Esimerkiksi Vatikaani pyysi häneltä palveluksia useammin kuin kerran. Soro ei kuitenkaan ollut täysin rehellinen paavia kohtaan: hän väitti paaville, että Vatikaanin salausjärjestelmä olisi mahdotonta murtaa, jolloin hänen onnistui tuudittaa Vatikaanin kryptografit valheelliseen turvallisuudentunteeseen. Osoittamalla Vatikaanin salakirjoituksen heikkoudet Soro olisi samalla kehottanut näitä luomaan uuden ja tehokkaamman järjestelmän, jota hän ei olisi välttämättä itsekään pystynyt murtamaan.

Venetsian ja Vatikaanin asemat Euroopan suurimpina salakirjoitusvaltoina muuttuivat pian. Ranskan kuningas Frans I otti palvelukseensa useita kryptoanalyytikkoja, joista kuuluisin oli Philibert Baboun. Ranskan mahti kryptoanalyyttisena suurvaltana vakiintui lopullisesti kuninkaan palkattua 1500-luvun lopussa François Vièten. Tämä onnistui tehtävissään niin hyvin, että Espanjan kuningas vetosi jopa Vatikaaniin väittäen Vièten olevan liitossa paholaisen kanssa, muuten tämä ei olisi pystynyt olemaan niin verrattoman loistava kryptoanalyytikko. Paavi kuitenkin tiesi muun Euroopan tavoin, että espanjalaisten salakirjoitus oli naurettavan helppo avata verrattuna muiden maiden salakirjoituksiin. Espanja ei ollut panostanut kryptografiaan, ja siksi viestien salaustaso oli laskenut huomattavasti. Myös Vatikaanin omat kryptoanalyytikot osasivat avata kuninkaan viestejä ilman ongelmia.

Maailmansotien aikana kehitettiin sähkömekaanisia salakirjoituslaitteita, kuten Enigma ja Lorenz. Viisaasti käytettynä niillä olisi voitu saada aikaan hyvin vahva, oman aikansa teknisillä resursseilla käytännössä lähes murtamaton salaus.
Käyttäjien huolimattomuuden vuoksi Englannissa Bletchley Parkissa työskennelleet kryptoanalyytikot saivat selvitettyä Lorenz-kojeen toiminnan täydellisesti, näkemättä ensimmäistäkään aitoa kojetta ennen toisen maailmansodan loppua. 
Puolalaisilla taas oli omat laitteensa, kuten Bombe, alkeellisempien Enigman versioiden murtamiseen jo ennen toista maailmansotaa. Enigman perusmalli oli toiminnaltaan jo tuolloin tunnettu, koska se oli ollut kaupallisesti saatavilla jo 1920-luvulla, mutta myöhempien muunnosten murtamiseen tarvittiin englantilaisten apua. Kaikkia Enigman versioita ei koskaan murrettu. 
Puolalaisten oma Lacida-laite (nimetty  Gwido Langerin, Maksymilian Ciężkin ja Ludomir Danilewiczin tai hänen veljensä Leonard Danilewiczin mukaan) osoittautui jo varhain salaukseltaan heikoksi. Laitteen kehittelijä ja Puolan salakirjoitustoimiston johtaja Gwido Langer määräsi laitteen käytön lopetettavaksi.
Siemens & Halske -yhtiön aivan sodan lopussa kehittämä T43 jäi vähäiselle käytölle, eikä sen koodia tiettävästi ainakaan tuolloin murrettu. T52 murrettiin Ruotsissa 1940 (Arne Beurling) ja myöhemmin Bletchley Parkissa, mutta prosessi oli työläs ja liikennettä vähän, joten mahdollisesti saatavaa tietoa ei pidetty vaivan arvoisena.
Akselivaltojen salatekstien purkamiseen tähdänneet tutkimukset johtivat muun muassa ensimmäisten ohjelmoitavien tietokoneiden kehittämiseen. Tutkijoista ehkä tunnetuin on matemaatikko Alan Turing, joka oli kehittänyt ohjelmoitavan tietokoneen teoreettisen mallin jo 1936.

Kryptoanalyysi nykyisin 
Kvanttitietokone saattaisi pystyä avaamaan suurten lukujen jaollisuuteen perustuvat asymmetriset salakirjoitusmenetelmät nykyistä paljon tehokkaammin. Koneet ovat kuitenkin ainakin vielä hyvin alkeellisella tasolla.

Kvanttietokoneiden ei uskota kykenevän murskaavan nopeaan symmetristen salausmenetelmien murtamiseen. Groverin algoritmilla väsytyshyökkäyksen (engl. brute-force attack) viemä aika on neliöjuuri perinteisen tietokoneen viemästä ajasta. Algoritmi on optimaalinen kyseiseen tarkoitukseen, eikä nopeampi tekniikka ole mahdollinen. Groverin algoritmilla avaimen pituus käytännössä puolittuu, mikä ei ole merkittävää, kun avaimen pituus on esimerkiksi 256 bittiä.

Symmetristen algoritmien murtamiseen yleisimmät tekniikat ovat differentiaalinen kryptoanalyysi ja lineaarinen kryptoanalyysi.

Lähteet

Aiheesta muualla 

Salakirjoitustekniikka