EITC/IS/CCF klasikinės kriptografijos pagrindai

Iki dabartinės eros kriptografija buvo beveik šifravimo sinonimas, paverčiant informaciją iš skaitomos į nesuprantamą nesąmonę. Kad užpuolikai negalėtų pasiekti užšifruoto pranešimo, siuntėjas tik dalijasi dekodavimo procesu su numatytais gavėjais. Kriptografijos literatūroje dažnai vartojami vardai Alisa („A“) – siuntėjui, Bobas („B“) – numatomam gavėjui, o Ieva („pasiklausytojas“) – priešininkas.

Kriptografijos metodai tapo vis sudėtingesni, o jų taikymas buvo įvairesnis, kai Pirmojo pasaulinio karo metais buvo sukurtos rotorinės šifravimo mašinos, o Antrojo pasaulinio karo metais – kompiuteriai.

Šiuolaikinė kriptografija labai priklauso nuo matematinės teorijos ir informatikos praktikos; kriptografiniai metodai yra sukurti remiantis skaičiavimo kietumo prielaidomis, todėl bet kuriam oponentui sunku juos sulaužyti praktiškai. Nors teoriškai įmanoma įsilaužti į gerai suplanuotą sistemą, praktiškai tai neįmanoma. Tokios schemos vadinamos „kompiuteriniu požiūriu saugiomis“, jei jos yra tinkamai sukurtos; nepaisant to, dėl teorinių laimėjimų (pvz., sveikųjų skaičių faktorizavimo metodų patobulinimai) ir spartesnės skaičiavimo technologijos būtina nuolat iš naujo įvertinti ir, jei reikia, pritaikyti šias konstrukcijas. Yra informacijos teoriškai saugių sistemų, tokių kaip vienkartinis blokas, kurios gali būti neįveikiamos net ir esant begalinei skaičiavimo galiai, tačiau praktiškai jas yra daug sunkiau pritaikyti nei geriausias teoriškai sulaužomas, bet skaičiuojant saugias schemas.

Informacijos amžiuje kriptografijos technologijų pažanga sukėlė įvairių teisinių iššūkių. Daugelis šalių kriptografiją klasifikavo kaip ginklą, ribodamos arba uždraudžiančios jos naudojimą ir eksportą dėl galimybės šnipinėti ir kurstyti. Kai kuriose vietose, kur kriptografija yra teisėta, tyrėjai gali priversti atiduoti su tyrimu susijusių dokumentų šifravimo raktus. Kalbant apie skaitmeninę laikmeną, kriptografija taip pat atlieka pagrindinį vaidmenį skaitmeninių teisių valdyme ir autorių teisių pažeidimo konfliktuose.

Terminas „kriptografas“ (priešingai nei „kriptograma“) pirmą kartą buvo pavartotas XIX amžiuje Edgaro Allano Poe apysakoje „Auksinė klaida“.

Iki šiol kriptografija beveik vadino „šifravimą“, ty įprastų duomenų (žinomo kaip paprasto teksto) pavertimą neįskaitomu formatu (vadinamu šifruotu tekstu). Iššifravimas yra priešingas šifravimui, ty nuo nesuprantamo šifruoto teksto pereinama prie paprasto teksto. Šifravimas (arba šifras) yra technikų, kurios atlieka šifravimą ir iššifravimą atvirkštine tvarka, rinkinys. Algoritmas ir kiekvienu atveju „raktas“ yra atsakingi už išsamų šifro vykdymą. Raktas yra paslaptis (pageidautina, kad ją žinotų tik komunikantai), kuri naudojama šifruotam tekstui iššifruoti. Paprastai tai yra simbolių eilutė (idealiu atveju trumpa, kad vartotojas galėtų ją atsiminti). „Kriptosistema“ yra baigtinių galimų paprastų tekstų, šifruotų tekstų, raktų ir šifravimo bei iššifravimo procedūrų, atitinkančių kiekvieną raktą formalia matematine prasme, sutvarkytas elementų rinkinys. Raktai yra svarbūs tiek formaliai, tiek praktiškai, nes šifrus su fiksuotais raktais galima lengvai sulaužyti naudojant tik šifro informaciją, todėl daugeliu atvejų jie tampa nenaudingi (ar net neproduktyvūs).

Istoriškai šifrai dažnai buvo naudojami be jokių papildomų procedūrų, tokių kaip autentifikavimas arba šifravimo ar iššifravimo vientisumo patikros. Kriptosistemos skirstomos į dvi kategorijas: simetriškas ir asimetrines. Tas pats raktas (slaptasis raktas) naudojamas žinutei šifruoti ir iššifruoti simetrinėse sistemose, kurios buvo vienintelės žinomos iki aštuntojo dešimtmečio. Kadangi simetrinėse sistemose naudojami trumpesni raktų ilgiai, simetrinėse sistemose duomenų apdorojimas yra greitesnis nei asimetrinėse sistemose. Asimetrinės sistemos užšifruoja ryšį su „viešuoju raktu“ ir iššifruoja jį naudodamos panašų „privatų raktą“. Asimetrinių sistemų naudojimas pagerina ryšio saugumą, nes sunku nustatyti ryšį tarp dviejų raktų. RSA (Rivest-Shamir-Adleman) ir ECC yra du asimetrinių sistemų (elipsinės kreivės kriptografijos) pavyzdžiai. Plačiai naudojamas AES (Advanced Encryption Standard), kuris pakeitė ankstesnį DES, yra aukštos kokybės simetrinio algoritmo (duomenų šifravimo standarto) pavyzdys. Įvairios vaikų kalbos supainiojimo technikos, pvz., kiaulių lotynų kalba ar kiti žodeliai, ir iš tikrųjų visos kriptografinės schemos, kad ir kokia rimta būtų, iš bet kokio šaltinio iki vienkartinio įkloto įvedimo XX amžiaus pradžioje yra prastos kokybės pavyzdžiai. simetriniai algoritmai.

Terminas „kodas“ dažnai vartojamas šnekamojoje kalboje, nurodant bet kokią šifravimo ar pranešimų slėpimo techniką. Tačiau kriptografijoje kodas reiškia paprasto teksto vieneto (ty prasmingo žodžio ar frazės) pakeitimą kodiniu žodžiu (pavyzdžiui, „wallaby“ pakeičia žodį „ataka auštant“). Priešingai, šifruotas tekstas sukuriamas modifikuojant arba pakeičiant žemiau tokio lygio esantį elementą (pavyzdžiui, raidę, skiemenį ar raidžių porą), kad būtų suformuotas šifruotas tekstas.

Kriptanalizė – tai būdų, kaip iššifruoti užšifruotus duomenis, neturint prieigos prie tam reikalingo rakto, tyrimas; kitaip tariant, tai tyrimas, kaip „sulaužyti“ šifravimo schemas ar jų įgyvendinimą.

Anglų kalboje kai kurie žmonės pakaitomis vartoja terminus „kriptografija“ ir „kriptologija“, o kiti (įskaitant JAV karinę praktiką apskritai) vartoja „kriptografiją“, nurodydami kriptografijos metodų naudojimą ir praktiką, o „kriptologija“ – bendrai. kriptografijos ir kriptoanalizės tyrimas. Anglų kalba yra labiau pritaikoma nei daugelis kitų kalbų, kur „kriptologija“ (kaip praktikuoja kriptologai) visada vartojama antrąja prasme. Pagal RFC 2828 steganografija kartais įtraukiama į kriptologiją.

Kriptolingvistika yra kalbos savybių, kurios turi tam tikros reikšmės kriptografijai ar kriptologijai, tyrimas (pavyzdžiui, dažnių statistika, raidžių deriniai, universalūs modeliai ir pan.).

Kriptografija ir kriptoanalizė turi ilgą istoriją.
Kriptografijos istorija yra pagrindinis straipsnis.
Iki šiuolaikinės eros kriptografija visų pirma buvo susijusi su pranešimų konfidencialumu (ty šifravimu) – pranešimų pavertimu iš suprantamos formos į nesuprantamą formą ir vėlgi, padarant juos neįskaitomus perėmėjams ar pasiklausytojams be slaptų žinių (būtent rakto, reikalingo iššifruoti). to pranešimo). Šifravimas buvo sukurtas taip, kad šnipų, karinių vadų ir diplomatų pokalbiai būtų privatūs. Pastaraisiais dešimtmečiais ši disciplina išaugo ir apima tokius metodus kaip pranešimų vientisumo tikrinimas, siuntėjo/gavėjo tapatybės autentifikavimas, skaitmeniniai parašai, interaktyvūs įrodymai ir saugus skaičiavimas, be kita ko.

Du labiausiai paplitę klasikiniai šifrų tipai yra transpoziciniai šifrai, kurie sistemingai pakeičia raides ar raidžių grupes kitomis raidėmis ar raidžių grupėmis (pvz., „labas pasaulis“ tampa „ehlol owrdl“ trivialiai paprastoje pertvarkymo schemoje), ir pakeitimo šifrai, kurios sistemingai pakeičia raides ar raidžių grupes kitomis raidėmis arba raidžių grupėmis (pvz., „skristi iš karto“ tampa „gmz bu“ Paprastos jų versijos niekada nesuteikė daug privatumo nuo gudrių priešų. Cezario šifras buvo ankstyvas pakeitimo šifras, kuriame kiekviena paprastojo teksto raidė buvo pakeista raide tam tikru skaičiumi abėcėlės pozicijų žemyn. Pasak Suetonijaus, Julius Cezaris naudojo ją su trijų žmonių pamainomis, kad bendrautų su savo generolais. Ankstyvasis hebrajų šifras Atbash yra pavyzdys. Seniausias žinomas kriptografijos panaudojimas yra išraižytas šifruotas tekstas ant akmens Egipte (apie 1900 m. pr. Kr.), tačiau gali būti, kad tai buvo daroma raštingų žiūrovų malonumui. ir nuslėpti informaciją.

Pranešama, kad kriptos buvo žinomos klasikiniams graikams (pvz., scytale transponavimo šifras, kaip teigiama, buvo naudojamas Spartos kariuomenės). Steganografija (praktika nuslėpti net bendravimo buvimą, kad jis būtų privatus) taip pat buvo išrasta senovėje. Pasak Herodoto, frazė, ištatuiruota ant nuskustos vergo galvos ir paslėpta po ataugusiais plaukais. Nematomo rašalo, mikrotaškelių ir skaitmeninių vandens ženklų naudojimas informacijai nuslėpti yra labiau aktualūs steganografijos atvejai.

Kautiliyam ir Mulavediya yra dviejų tipų šifrai, paminėti 2000 metų Indijos Vtsijanos Kamasutroje. Šifruotų raidžių pakaitalai Kautiliyam yra pagrįsti fonetiniais ryšiais, pavyzdžiui, balsių tapimu priebalsiais. Šifro abėcėlė Mulavedijoje susideda iš atitinkamų raidžių ir naudojamų abipusių raidžių.

Pasak musulmonų mokslininko Ibn al-Nadimo, Sasanidų Persija turėjo du slaptus raštus: h-dabrya (pažodžiui „Karaliaus raštas“), kuris buvo naudojamas oficialiam susirašinėjimui, ir rz-saharya, kuris buvo naudojamas keistis slaptomis žinutėmis su kitais. šalyse.

Savo knygoje The Codebreakers Davidas Kahnas rašo, kad šiuolaikinė kriptologija prasidėjo nuo arabų, kurie pirmieji kruopščiai dokumentavo kriptoanalizės procedūras. Kriptografinių pranešimų knygą parašė Al-Khalil (717–786), joje yra anksčiausiai panaudotos permutacijos ir deriniai, išvardyti visus įmanomus arabiškus žodžius su balsėmis ir be jų.

Klasikinio šifro sugeneruoti šifravimo tekstai (taip pat ir kai kurie šiuolaikiniai šifrai) atskleidžia statistinę informaciją apie paprastą tekstą, kurią galima panaudoti šifrui sulaužyti. Beveik visus tokius šifrus galėjo sulaužyti protingas užpuolikas, atradęs dažnių analizę, galbūt arabų matematikas ir polimatas Al-Kindi (taip pat žinomas kaip Alkindas) IX amžiuje. Klasikiniai šifrai vis dar populiarūs ir šiandien, nors daugiausia kaip galvosūkiai (žr. kriptogramą). Risalah fi Istikhraj al-Mu'amma (Rankraštis kriptografinių pranešimų iššifravimui) parašė Al-Kindi ir dokumentavo pirmąjį žinomą dažnių analizės kriptoanalizės metodų panaudojimą.

Kai kuriems išplėstinės istorijos šifravimo metodams, pavyzdžiui, homofoniniam šifrui, kuris linkęs išlyginti dažnių pasiskirstymą, kalbos raidžių dažniai gali būti nenaudingi. Kalbos raidžių grupės (arba n-gramų) dažniai gali sukelti ataką tiems šiframs.

Iki daugiabėcėlinio šifro atradimo, ypač Leon Battista Alberti apie 1467 m., beveik visi šifrai buvo prieinami kriptoanalizei naudojant dažnio analizės metodą, nors yra įrodymų, kad Al-Kindi tai jau žinojo. Alberti sugalvojo idėją naudoti atskirus šifrus (arba pakaitines abėcėles) skirtingoms komunikacijos dalims (galbūt kiekvienai iš eilės paprasto teksto raidei ties riba). Jis taip pat sukūrė, kaip manoma, pirmąjį automatinį šifravimo įrenginį – ratą, kuris įvykdė dalį jo dizaino. Šifravimas Vigenère šifru, daugiabėcėliniu šifru, valdomas raktiniu žodžiu, kuris valdo raidžių pakeitimą pagal tai, kuri raktinio žodžio raidė naudojama. Charlesas Babbage'as parodė, kad Vigenère'o šifras buvo pažeidžiamas Kasiski analizės XIX amžiaus viduryje, tačiau Friedrichas Kasiski paskelbė savo išvadas po dešimties metų.

Nepaisant to, kad dažnio analizė yra galingas ir platus metodas prieš daugelį šifrų, šifravimas išliko veiksmingas praktikoje, nes daugelis būsimų kriptoanalitikų nežino apie šią techniką. Norint sulaužyti pranešimą nenaudojant dažnio analizės, reikėjo žinoti naudojamą šifrą ir galbūt naudojamą raktą, todėl šnipinėjimas, kyšininkavimas, vagystės, dezertyravimas ir kitos kriptovaliutiškai neinformuotos taktikos būtų patrauklesnės. Šifro algoritmo paslaptis XIX amžiuje galiausiai buvo pripažinta nei pagrįsta, nei įmanoma pranešimų saugumo garantija; Tiesą sakant, bet kuri tinkama kriptografinė schema (įskaitant šifrus) turėtų išlikti saugi, net jei priešininkas visiškai supranta patį šifravimo algoritmą. Rakto saugumo turėtų pakakti, kad geras šifras išlaikytų konfidencialumą užpuolimo atveju. Auguste'as Kerckhoffsas pirmą kartą pareiškė šį pagrindinį principą 19 m. ir jis žinomas kaip Kerckhoffo principas; Kita vertus, ir dar atviriau, Claude'as Shannonas, informacijos teorijos ir teorinės kriptografijos pagrindų išradėjas, pakartojo tai kaip Šenono Maksimas – „priešas žino sistemą“.

Siekiant padėti su šifrais, buvo panaudota daug fizinių įtaisų ir pagalbos. Senovės Graikijos istorija, strypas, kurį spartiečiai tariamai naudojo kaip perkėlimo šifro įrankį, galėjo būti vienas pirmųjų. Viduramžiais buvo sukurtos kitos pagalbinės priemonės, pavyzdžiui, šifro grotelės, kurios taip pat buvo naudojamos steganografijai. Sukūrus daugiabėcėles šifrus, tapo prieinamos sudėtingesnės pagalbinės priemonės, tokios kaip Alberti šifro diskas, Johanneso Trithemiuso tabula recta schema ir Thomaso Jeffersono ratų šifras (viešai nežinomas, o Bazeries savarankiškai išrado apie 1900 m.). Dvidešimtojo amžiaus pradžioje buvo sukurta ir užpatentuota daug mechaninių šifravimo/iššifravimo sistemų, įskaitant rotorines mašinas, kurias Vokietijos vyriausybė ir kariuomenė garsiai naudojo nuo XX a. 1920-ųjų pabaigos iki Antrojo pasaulinio karo. Po Pirmojo pasaulinio karo šifrai, įdiegti naudojant aukštesnės kokybės šių mašinų konstrukcijų egzempliorius, žymiai padidino kriptoanalizės sunkumus.

Iki XX amžiaus pradžios kriptografija pirmiausia buvo susijusi su kalbiniais ir leksikografiniais modeliais. Nuo tada dėmesys keitėsi, o kriptografija dabar apima informacijos teorijos, skaičiavimo sudėtingumo, statistikos, kombinatorikos, abstrakčiosios algebros, skaičių teorijos ir apskritai baigtinės matematikos aspektus. Kriptografija yra inžinerijos rūšis, tačiau ji unikali tuo, kad ji susijusi su aktyviu, protingu ir priešišku pasipriešinimu, tuo tarpu kitų tipų inžinerija (pvz., civilinė ar chemijos inžinerija) turi tik kovoti su neutraliomis gamtos jėgomis. Taip pat tiriamas ryšys tarp kriptografijos sunkumų ir kvantinės fizikos.

Skaitmeninių kompiuterių ir elektronikos kūrimas padėjo kriptoanalizei, nes leido sukurti žymiai sudėtingesnius šifrus. Be to, skirtingai nuo tradicinių šifrų, kurie išskirtinai šifruodavo rašytinės kalbos tekstus, kompiuteriai leido šifruoti bet kokio tipo duomenis, kurie gali būti pateikti bet kokiu dvejetainiu formatu; tai buvo nauja ir svarbu. Tiek šifravimo projektavimo, tiek kriptoanalizės srityse kompiuteriai taip išstūmė kalbos kriptografiją. Skirtingai nuo klasikinių ir mechaninių metodų, kurie pirmiausia tiesiogiai manipuliuoja tradiciniais simboliais (ty raidėmis ir skaičiais), daugelis kompiuterių šifrų veikia dvejetainėmis bitų sekomis (kartais grupėmis arba blokais). Kita vertus, kompiuteriai padėjo kriptovaliutų analizei, kuri iš dalies kompensavo padidėjusį šifravimo sudėtingumą. Nepaisant to, geri šiuolaikiniai šifrai išliko priekyje kriptoanalizės; dažnai pasitaiko, kad gero šifro naudojimas yra labai efektyvus (ty greitas ir reikalaujantis nedaug išteklių, pvz., atminties ar procesoriaus pajėgumų), o norint jį sulaužyti reikia daug kartų didesnių pastangų ir daug daugiau, nei reikia klasikinis šifras, efektyviai padarantis kriptovaliutą neįmanomą.

Šiuolaikinė kriptografija debiutuoja.
Naujųjų mechaninių įrenginių kriptovaliutų analizė pasirodė esanti sudėtinga ir atimanti daug laiko. Antrojo pasaulinio karo metu kriptoanalitinė veikla Bletchley parke Jungtinėje Karalystėje paskatino efektyvesnių pasikartojančių užduočių atlikimo metodų išradimą. Colossus, pirmasis pasaulyje visiškai elektroninis, skaitmeninis, programuojamas kompiuteris, buvo sukurtas siekiant padėti iššifruoti šifrus, sukurtus Vokietijos armijos Lorenz SZ40/42 aparatu.

Kriptografija yra palyginti nauja atvirų akademinių tyrimų sritis, prasidėjusi tik aštuntojo dešimtmečio viduryje. IBM darbuotojai sukūrė algoritmą, kuris tapo federaliniu (ty JAV) duomenų šifravimo standartu; Whitfieldas Diffie ir Martinas Hellmanas paskelbė savo pagrindinį susitarimo algoritmą; ir Martino Gardnerio „Scientific American“ rubrika paskelbė RSA algoritmą. Nuo to laiko kriptografija išpopuliarėjo kaip ryšių, kompiuterių tinklų ir apskritai kompiuterių saugumo technika.

Egzistuoja glaudūs ryšiai su abstrakčiąja matematika, nes keli šiuolaikiniai kriptografijos metodai gali išlaikyti savo raktus paslaptyje tik tuo atveju, jei tam tikros matematinės problemos yra sunkiai išsprendžiamos, pvz., sveikųjų skaičių faktorizavimas arba diskrečiųjų logaritmų problemos. Yra tik keletas kriptosistemų, kurios, kaip įrodyta, yra 100% saugios. Claude'as Shannonas įrodė, kad vienkartinis įklotas yra vienas iš jų. Yra keletas pagrindinių algoritmų, kurie tam tikromis sąlygomis buvo saugūs. Pavyzdžiui, nesugebėjimas atsižvelgti į itin didelius sveikuosius skaičius yra pagrindas manyti, kad RSA ir kitos sistemos yra saugios, tačiau nepažeidžiamumo įrodymas nepasiekiamas, nes pagrindinė matematinė problema lieka neišspręsta. Praktiškai jie yra plačiai naudojami, ir dauguma kompetentingų stebėtojų mano, kad jie praktiškai nepalaužiami. Egzistuoja sistemos, panašios į RSA, pvz., Michaelo O. Rabino sukurtas, kurios yra įrodyta, kad yra saugios, jei faktorius n = pq neįmanomas; tačiau jie praktiškai nenaudingi. Diskretaus logaritmo problema yra pagrindas manyti, kad kai kurios kitos kriptosistemos yra saugios, ir yra panašių, mažiau praktiškų sistemų, kurios yra patikimai saugios diskretiškojo logaritmo problemos išsprendžiamumo arba neišsprendžiamumo požiūriu.

Kriptografijos algoritmų ir sistemų kūrėjai, dirbdami su savo idėjomis, turi atsižvelgti į galimą pažangą ateityje, be to, kad turi žinoti kriptografijos istoriją. Pavyzdžiui, pagerėjus kompiuterio apdorojimo galiai, išaugo žiaurios jėgos atakų mastas, todėl išaugo ir reikiami raktų ilgiai. Kai kurie kriptografinių sistemų kūrėjai, tyrinėjantys postkvantinę kriptografiją, jau svarsto galimas kvantinio skaičiavimo pasekmes; paskelbta, kad netrukus bus pradėtas nedidelis šių mašinų diegimas, todėl prevencinio atsargumo poreikis gali būti ne tik spekuliatyvus.

Klasikinė kriptografija šiais laikais

Simetrinė (arba privataus rakto) kriptografija yra šifravimo rūšis, kai siuntėjas ir gavėjas naudoja tą patį raktą (arba, rečiau, kai jų raktai skiriasi, bet yra lengvai apskaičiuojami ir yra laikomi paslaptyje, privačiai ). Iki 1976 m. birželio mėn. tai buvo vienintelis viešai žinomas šifravimo tipas.

Tiek blokiniai, tiek srautiniai šifrai naudojami simetriniams raktų šiframs įgyvendinti. Bloko šifras šifruoja įvestį paprasto teksto blokais, o ne atskirais simboliais, kaip tai daro srauto šifras.

JAV vyriausybė duomenų šifravimo standartą (DES) ir išplėstinį šifravimo standartą (AES) paskyrė kriptografijos standartais (nors DES sertifikatas galiausiai buvo panaikintas, kai buvo sukurtas AES). DES (ypač jos vis dar patvirtintas ir žymiai saugesnis trigubas DES variantas) išlieka populiarus, nepaisant to, kad jis nebenaudojamas kaip oficialus standartas; jis naudojamas įvairiose programose – nuo ​​bankomatų šifravimo iki el. pašto privatumo ir saugios nuotolinės prieigos. Buvo išrasta ir išleista daugybė skirtingų blokinių šifrų, su skirtinga sėkme. Daugelis, įskaitant kai kuriuos, sukurtus kvalifikuotų praktikų, pvz., FEAL, buvo labai sugadinti.

Srautiniai šifrai, skirtingai nei blokiniai šifrai, generuoja be galo ilgą pagrindinės medžiagos srautą, kuris yra susietas su paprastu tekstu bitais arba simboliais, panašiai kaip vienkartinis blokas. Srauto šifro išvesties srautas generuojamas iš paslėptos vidinės būsenos, kuri keičiasi veikiant šifrui. Slapto rakto medžiaga iš pradžių naudojama norint nustatyti tą vidinę būseną. Srauto šifras RC4 yra plačiai naudojamas. Sukūrus raktų srauto blokus (vietoj pseudoatsitiktinių skaičių generatoriaus) ir naudojant XOR operaciją kiekvienam paprastojo teksto bitui su kiekvienu raktų srauto bitu, blokų šifrai gali būti naudojami kaip srauto šifrai.

Pranešimų autentifikavimo kodai (MAC) yra panašūs į kriptografines maišos funkcijas, išskyrus tai, kad slaptasis raktas gali būti naudojamas maišos vertei patvirtinti gavus; šis papildomas sudėtingumas apsaugo nuo atakos prieš atvirus suskaidymo algoritmus, todėl manoma, kad tai verta. Trečioji kriptografijos technikos rūšis yra kriptografinės maišos funkcijos. Jie priima bet kokio ilgio pranešimą kaip įvestį ir išveda mažą fiksuoto ilgio maišą, kuri gali būti naudojama, pavyzdžiui, skaitmeniniams parašams. Užpuolikas negali aptikti dviejų pranešimų, kurie sukuria tą pačią maišą, naudodamas gerus maišos algoritmus. MD4 yra plačiai naudojama, bet dabar sugedusi maišos funkcija; MD5, patobulinta MD4 forma, taip pat plačiai naudojama, tačiau praktiškai neveikia. Secure Hash Algorithm seriją MD5 panašių maišos algoritmų sukūrė JAV Nacionalinė saugumo agentūra: JAV standartų institucija nusprendė, kad saugumo požiūriu buvo „apdairiai“ sukurti naują standartą, kuris „žymiai pagerintų NIST bendro maišos algoritmo patikimumą. įrankių rinkinys“. SHA-1 yra plačiai naudojamas ir saugesnis nei MD5, tačiau kriptoanalitikai nustatė atakas prieš jį; SHA-2 šeima patobulinta SHA-1, tačiau nuo 2011 m. yra pažeidžiama susidūrimų; ir SHA-2 šeima patobulina SHA-1, bet yra pažeidžiama dėl susidūrimų. Dėl to iki 2012 m. turėjo būti surengtas maišos funkcijos dizaino konkursas, siekiant išrinkti naują JAV nacionalinį standartą, žinomą kaip SHA-3. Konkursas baigėsi 2 m. spalio 2012 d., kai Nacionalinis standartų ir technologijų institutas (NIST) paskelbė, kad Keccak yra naujas SHA-3 maišos algoritmas. Kriptografinės maišos funkcijos, skirtingai nei apverčiami blokų ir srauto šifrai, suteikia maišos išvestį, kurios negalima naudoti norint atkurti pradinius įvesties duomenis. Kriptografinės maišos funkcijos naudojamos duomenų, gautų iš nepatikimo šaltinio, autentiškumui patikrinti arba papildomam apsaugos lygiui pridėti.

Nors pranešimas ar pranešimų rinkinys gali turėti skirtingą raktą nei kiti, simetrinio rakto kriptosistemos naudoja tą patį raktą šifravimui ir iššifravimui. Raktų valdymas, reikalingas norint saugiai naudoti simetrinius šifrus, yra didelis trūkumas. Idealiu atveju kiekviena atskira bendraujančių šalių pora turėtų dalytis skirtingu raktu ir galbūt skirtingu kiekvieno išsiųsto šifruoto teksto šifru. Reikalingų raktų skaičius auga tiesiogiai proporcingai tinklo dalyvių skaičiui, todėl reikia sudėtingų raktų valdymo metodų, kad jie visi būtų nuoseklūs ir slapti.

Whitfieldas Diffie ir Martinas Hellmanas išrado viešojo rakto (taip pat žinomo kaip asimetrinio rakto) kriptografijos koncepciją esminiame 1976 m. darbe, kuriame naudojami du skirtingi, bet matematiškai susiję raktai – viešasis raktas ir privatusis raktas. Nors jie yra neatsiejamai susiję, viešojo rakto sistema yra sukurta taip, kad apskaičiuoti vieną raktą („privatųjį raktą“) nuo kito („viešojo rakto“) skaičiavimais neįmanoma. Atvirkščiai, abu raktai yra gaminami slaptai, kaip susieta pora. Pasak istoriko Davido Kahno, viešojo rakto kriptografija yra „revoliucingiausia nauja sąvoka šioje srityje nuo tada, kai Renesanso laikais atsirado daugiaalfabetinis pakeitimas“.

Viešasis raktas viešojo rakto kriptosistemoje gali būti laisvai perduodamas, tačiau susietas privatus raktas turi būti paslėptas. Viešasis raktas naudojamas šifravimui, o privatus arba slaptasis raktas naudojamas iššifruoti viešojo rakto šifravimo schemoje. Nors Diffie ir Hellman negalėjo sukurti tokios sistemos, jie įrodė, kad viešojo rakto kriptografija yra įmanoma, pateikdami Diffie-Hellman raktų mainų protokolą, sprendimą, leidžiantį dviem žmonėms slapta susitarti dėl bendro šifravimo rakto. Plačiausiai naudojamas viešojo rakto sertifikatų formatas yra apibrėžtas X.509 standarto.

Diffie ir Hellman publikacija sukėlė platų akademinį susidomėjimą sukurti praktinę viešojo rakto šifravimo sistemą. Ronaldas Rivestas, Adi Shamiras ir Lenas Adlemanas galiausiai laimėjo konkursą 1978 m., o jų atsakymas tapo žinomas kaip RSA algoritmas.

Diffie-Hellman ir RSA algoritmai buvo ne tik pirmieji viešai žinomi aukštos kokybės viešojo rakto algoritmai, bet ir buvo vieni dažniausiai naudojamų. „Cramer-Shoup“ kriptosistema, „ElGamal“ šifravimas ir daugybė elipsinės kreivės metodų yra asimetrinių raktų algoritmų pavyzdžiai.

GCHQ kriptografai numatė keletą mokslo pažangos, remiantis 1997 m. Britanijos žvalgybos organizacijos Vyriausybės komunikacijų štabo (GCHQ) išleistu dokumentu. Pasak legendos, asimetrinio rakto kriptografiją apie 1970 m. išrado James H. Ellis. Clifford Cocks 1973 metais išrado sprendimą, kuris savo dizainu buvo labai panašus į RSA. Malcolmas J. Williamsonas yra priskiriamas Diffie-Hellman raktų mainų išradimui 1974 m.

Skaitmeninio parašo sistemos taip pat diegiamos naudojant viešojo rakto kriptografiją. Skaitmeninis parašas panašus į tradicinį parašą, nes jį paprasta sukurti vartotojui, o kitiems sunku suklastoti. Skaitmeniniai parašai taip pat gali būti nuolat susieti su pasirašomo pranešimo turiniu; tai reiškia, kad jų negalima „perkelti“ iš vieno dokumento į kitą neaptiktus. Skaitmeninio parašo schemose yra du algoritmai: vienas, skirtas pasirašyti, kuris naudoja slaptą raktą pranešimui apdoroti (arba pranešimo maišą, arba abu), ir kitas tikrinimo, kuris naudoja atitinkamą viešąjį raktą su pranešimu, kad patvirtintų. parašo autentiškumas. Du dažniausiai naudojami skaitmeninio parašo metodai yra RSA ir DSA. Viešojo rakto infrastruktūros ir daugelio tinklo saugumo sistemų (pvz., SSL/TLS, daugelio VPN) veikimas priklauso nuo skaitmeninių parašų.

„Sudėtingų“ problemų, pavyzdžiui, kylančių iš skaičių teorijos, skaičiavimo sudėtingumas dažnai naudojamas viešojo rakto metodams kurti. Sveikųjų skaičių faktorizavimo problema yra susijusi su RSA kietumu, o diskrečiojo logaritmo problema yra susijusi su Diffie-Hellman ir DSA. Elipsinės kreivės kriptografijos saugumas pagrįstas elipsinės kreivės skaičiaus teorinėmis problemomis. Dauguma viešojo rakto algoritmų apima tokias operacijas kaip modulinis dauginimas ir eksponencija, kurios yra daug brangesnės už daugumoje blokinių šifrų naudojamus metodus, ypač naudojant įprastus raktų dydžius, dėl pagrindinių problemų sudėtingumo. Todėl viešojo rakto kriptosistemos dažnai yra hibridinės kriptosistemos, kuriose pranešimas užšifruojamas greitu, aukštos kokybės simetrinio rakto algoritmu, o atitinkamas simetrinis raktas siunčiamas kartu su pranešimu, bet užšifruojamas naudojant viešojo rakto algoritmą. Taip pat dažnai naudojamos hibridinio parašo schemos, kuriose apskaičiuojama kriptografinė maišos funkcija ir tik gauta maiša pasirašoma skaitmeniniu būdu.

Maišos funkcijos kriptografijoje

Kriptografinės maišos funkcijos yra kriptografiniai algoritmai, kurie sukuria ir naudoja specifinius raktus duomenims užšifruoti simetriniam arba asimetriniam šifravimui, ir jie gali būti laikomi raktais. Jie priima bet kokio ilgio pranešimą kaip įvestį ir išveda mažą fiksuoto ilgio maišą, kuri gali būti naudojama, pavyzdžiui, skaitmeniniams parašams. Užpuolikas negali aptikti dviejų pranešimų, kurie sukuria tą pačią maišą, naudodamas gerus maišos algoritmus. MD4 yra plačiai naudojama, bet dabar sugedusi maišos funkcija; MD5, patobulinta MD4 forma, taip pat plačiai naudojama, tačiau praktiškai neveikia. Secure Hash Algorithm seriją MD5 panašių maišos algoritmų sukūrė JAV Nacionalinė saugumo agentūra: JAV standartų institucija nusprendė, kad saugumo požiūriu buvo „apdairiai“ sukurti naują standartą, kuris „žymiai pagerintų NIST bendro maišos algoritmo patikimumą. įrankių rinkinys“. SHA-1 yra plačiai naudojamas ir saugesnis nei MD5, tačiau kriptoanalitikai nustatė atakas prieš jį; SHA-2 šeima patobulinta SHA-1, tačiau nuo 2011 m. yra pažeidžiama susidūrimų; ir SHA-2 šeima patobulina SHA-1, bet yra pažeidžiama dėl susidūrimų. Dėl to iki 2012 m. turėjo būti surengtas maišos funkcijos dizaino konkursas, siekiant išrinkti naują JAV nacionalinį standartą, žinomą kaip SHA-3. Konkursas baigėsi 2 m. spalio 2012 d., kai Nacionalinis standartų ir technologijų institutas (NIST) paskelbė, kad Keccak yra naujas SHA-3 maišos algoritmas. Kriptografinės maišos funkcijos, skirtingai nei apverčiami blokų ir srauto šifrai, suteikia maišos išvestį, kurios negalima naudoti norint atkurti pradinius įvesties duomenis. Kriptografinės maišos funkcijos naudojamos duomenų, gautų iš nepatikimo šaltinio, autentiškumui patikrinti arba papildomam apsaugos lygiui pridėti.

Kriptografiniai primityvai ir kriptosistemos

Didžioji kriptografijos teorinio darbo dalis yra skirta kriptografiniams primityvams – algoritmams, turintiems pagrindines kriptografines savybes – ir kaip jie susiję su kitais kriptografiniais iššūkiais. Tada šie pagrindiniai primityvai naudojami sudėtingesniems kriptografiniams įrankiams kurti. Šie primityvai suteikia pagrindines savybes, kurios naudojamos kuriant sudėtingesnius įrankius, žinomus kaip kriptosistemos arba kriptografiniai protokolai, užtikrinantys vieną ar daugiau aukšto lygio saugumo savybių. Kita vertus, riba tarp kriptografinių primityvų ir kriptosistemų yra savavališka; Pavyzdžiui, RSA algoritmas kartais laikomas kriptosistema, o kartais primityvu. Įprasti pavyzdžiai yra pseudoatsitiktinės funkcijos, vienpusės funkcijos ir kiti kriptografiniai primityvai.

Kriptografinė sistema arba kriptosistema sukuriama sujungiant vieną ar daugiau kriptografinių primityvų, kad būtų sukurtas sudėtingesnis algoritmas. Kriptosistemos (pvz., El-Gamal šifravimas) yra skirtos teikti specifines funkcijas (pvz., viešojo rakto šifravimą), tuo pačiu užtikrinant tam tikras saugumo savybes (pvz., pasirinktas atsitiktinis orakulo modelis-plaintext atakos CPA saugumas). Siekdamos palaikyti sistemos saugumo savybes, kriptosistemos naudoja pagrindinių kriptografinių primityvų savybes. Sudėtinga kriptosistema gali būti sukurta derinant daugybę elementaresnių kriptosistemų, nes skirtumas tarp primityvių ir kriptosistemų yra šiek tiek savavališkas. Daugeliu atvejų kriptosistemos struktūra apima tiesioginį ryšį tarp dviejų ar daugiau šalių erdvėje (pvz., tarp saugaus pranešimo siuntėjo ir gavėjo) arba laike (pvz., tarp saugaus pranešimo siuntėjo ir gavėjo). (pvz., kriptografiškai apsaugotos atsarginės duomenų kopijos).