Salausalgoritmit, jotka on selitetty esimerkeillä

Salaus, alkeellisimmillaan, on tiede koodien ja salausten käytöstä viestien suojaamiseksi.

Salaus on viestien koodaus tarkoituksena vain antaa vastaanottajan ymmärtää viestin merkitys. Se on kaksisuuntainen toiminto (sinun on voitava kumota kaikki salaus, jonka olet tehnyt viestille). Tämä on suunniteltu suojaamaan siirretyt tiedot.

Jos etsit yleistä taustaa symmetristen ja epäsymmetristen algoritmien eroista ja yleiskatsauksen salauksesta, aloita tästä. Tämä artikkeli kattaa ensisijaisesti kaksi yleisimmin käytettyä salausalgoritmia.

Yleiskatsauksena symmetristen algoritmien syntymisessä oli suuri ongelma niiden ensimmäisessä luomisessa - ne toimivat vain, jos molemmat osapuolet tiesivät jo jaetun salaisuuden. Jos he eivät tehneet, avaimen turvallinen vaihtaminen ilman kolmannen osapuolen eves-pudottamista oli erittäin vaikeaa.

Ja jos kolmas osapuoli hankki avaimen, heidän oli erittäin helppo rikkoa salaus ja voittaa suojatun viestinnän tarkoitus.

Diffie-Hellman ratkaisi tämän ongelman sallimalla muukalaisten vaihtaa tietoja julkisten kanavien kautta, joita voidaan käyttää jaetun avaimen muodostamiseen. Jaettua avainta on vaikea murtaa, vaikka kaikkea viestintää seurattaisiin.

Kuinka Diffie-Hellman toimii?

Diffie-Hellmania kutsutaan avaimenvaihtoprotokollaksi. Tämä on Diffie-Hellmanin ensisijainen käyttö, vaikka sitä voidaan käyttää myös salaukseen (se ei tyypillisesti ole, koska DH: n avulla on tehokkaampaa vaihtaa avaimia ja siirtyä sitten (huomattavasti nopeammin) symmetriseen salaukseen tiedonsiirtoa varten ).

Tämä toimii seuraavasti:

Pohjimmiltaan on kaksi osapuolta, Alice ja Bob, jotka sopivat aloitusväristä (mielivaltainen, mutta sen on oltava aina erilainen). Heillä on myös salainen väri, jonka he pitävät itsessään. Sitten he sekoittavat tämän värin jaetun värin kanssa, jolloin saadaan kaksi eri väriä. Sitten he välittävät tämän värin toiselle osapuolelle, joka sekoittaa sen salaisen värinsä kanssa, jolloin tuloksena on sama lopullinen salainen väri.

Tämä perustuu ajatukseen, että kahden värin sekoittaminen on suhteellisen helppoa, mutta niiden erottaminen salaisen värin löytämiseksi on hyvin vaikeaa. Käytännössä tämä tehdään matematiikan kanssa.

Esimerkiksi:

  1. Bob ja Alice sopivat kahdesta luvusta, suuresta alkuluvusta, p = 29, ja perustasta g = 5
  2. Nyt Bob valitsee salaisen numeron, x (x = 4) ja tekee seuraavat toimet: X = g ^ x% p (tässä tapauksessa% ilmaisee loput. Esimerkiksi 3% 2 on 3/2, kun loput ovat 1) . X = 5 ^ 4% 29 = 625% 29 = 16
  3. Alice valitsee myös salaisen numeron y (y = 8) ja tekee seuraavan: Y = g ^ y% p. Y = 5 ^ 8% 29 = 390625% 29 = 24
  4. Bob lähettää X: n Alicelle ja Alice lähettää Y: n Bobille.
  5. Sitten Bob tekee seuraavaa: K = Y ^ x% p, K = 24 ^ 4% 29 = 331776% 29 = 16
  6. Alice tekee sitten seuraavat toimet: K = X ^ y% p, K = 16 ^ 8% 29 = 4,294,967,296% 29 = 16

Suuri (* mahdollisesti taika *) asia tässä on se, että sekä Bobilla että Alicella on sama numero K ja että he voivat nyt käyttää tätä puhuakseen salaa, koska kukaan muu ei tunne K.

Tämän protokollan turvallisuus perustuu useisiin asioihin:

  1. (Tosiasia) Päälukujen, jopa suurten alkulukujen (kuten p) luominen on suhteellisen helppoa.
  2. (Tosiasia) Modulaarinen eksponentti on helppoa. Toisin sanoen on suhteellisen helppoa laskea X = g ^ x% p.
  3. (Oletus perustuu nykyiseen laskentatehoon ja matematiikkaan) Modulaarinen juurien poiminta ilman alkutekijöitä on erittäin vaikeaa. Pohjimmiltaan on erittäin vaikea löytää K tietämättä x: tä ja y: tä, vaikka olisitkin seurannut liikennettä ja näet p, g, X ja Y.

Siten olettaen, että tämä on toteutettu oikein, avaimen luomiseen tarvittavan matematiikan tekeminen on suhteellisen helppoa, mutta on erittäin vaikeaa ja aikaa vievää tehdä matematiikka, jota tarvitaan avaimen rikkomiseen yrittämällä raakaa sitä.

Vaikka hyökkääjä voisi vaarantaa tämän avaimen, Diffie-Hellman sallii täydellisen salaisuuden eteenpäin.

Mikä on täydellinen salassapitovelvollisuus eteenpäin?

Tämä on ajatus, että jos murtaudut palvelimen käyttämään salaukseen nyt, se ei tarkoita, että kaikki palvelimen koskaan suorittamat viestit voidaan lukea.

Toisin sanoen, se antaa sinun nähdä vain nyt käytettävät viestinnät (eli tällä salaisella avaimella). Koska jokaisella viestintäjärjestelmällä on erilainen salainen avain, joudut murtamaan ne kaikki erikseen.

Tämä on mahdollista, jos jokaisella istunnolla on eri lyhyt avain kullekin istunnolle. Koska Diffie-Hellman käyttää aina uusia satunnaisarvoja kullekin istunnolle (joten se luo uudet avaimet kullekin istunnolle), sitä kutsutaan lyhytaikaiseksi Diffie Hellmaniksi (EDH tai DHE). Monet salauspaketit käyttävät tätä saavuttaakseen täydellisen salaisuuden.

Koska Diffie-Hellman antaa sinun vaihtaa avainmateriaalia selkeässä tekstissä huolimatta jaetun salaisuuden vaarantamisesta ja matematiikka on liian monimutkainen hyökkääjän raakaa voimaa varten, hyökkääjä ei voi johtaa istuntoavainta (ja vaikka voisi, erilaiset, lyhytaikaiset avaimet jokaiselle istunnolle tarkoittavat, että he voisivat vain nipistää tätä istuntoa - ei mitään aiemmin tai tulevaisuudessa).

Välitys salassapito on käytössä missä tahansa Diffie-Hellman-avaimenvaihdossa, mutta vain lyhytaikainen avainten vaihto (eri avain jokaiselle istunnolle) tarjoaa täydellisen salassapidon eteenpäin.

Tässä on Scott Helmen viesti, jossa puhutaan tästä perusteellisemmin ja selitetään, miten tämä otetaan käyttöön palvelimillasi.

Mitkä ovat Diffie-Hellmanin rajoitukset?

DH: n suurin rajoitus on se, että henkilöllisyyttä ei vahvisteta. Toisin sanoen kuka tahansa voi väittää olevansa Alice tai Bob, eikä ole olemassa sisäänrakennettua mekanismia sen toteamiseksi, että heidän lausuntonsa on totta.

Lisäksi, jos toteutusta ei suoriteta turvallisesti, algoritmi voidaan murtaa riittävällä määrällä resursseja (epätodennäköistä, mutta mahdollista akateemisille ryhmille tai kansallisvaltioiden toimijoille).

Esimerkiksi, tämä voi tapahtua, jos satunnaislukugeneraattorilla ei ole riittävää entropiaa halutun voimakkuuden tukemiseksi - toisin sanoen, koska tietokoneella luodut luvut eivät ole koskaan todella satunnaisia, missä määrin olet keinotekoisesti pistänyt epävarmuutta toteutuksestasi.

Lisäksi vuonna 2015 osoitettiin hyökkäys, joka osoitti, että kun monet palvelimet käyttivät samoja alkulukuja kuin avaimenvaihdon alku, Diffie-Hellmanin yleinen turvallisuus oli odotettua heikompi.

Pohjimmiltaan hyökkääjä voisi yksinkertaisesti laskea hyökkäyksen kyseistä alkua vastaan, mikä helpottaa istuntojen vaarantamista kaikille palvelimille, jotka ovat käyttäneet kyseistä alkulukua.

Tämä tapahtui, koska miljoonat palvelimet käyttivät samoja alkunumeroita avaintenvaihtoon. Tämän tyyppisen hyökkäyksen ennakkolaskenta vaatii edelleen joko akateemisen tai kansallisvaltiotason resursseja, eikä todennäköisesti vaikuta valtaosaan ihmisiä.

Onneksi niille, jotka joutuvat huolehtimaan kansallisvaltioiden hyökkääjistä, on kuitenkin erilainen tapa saavuttaa DH-avaimen vaihto käyttämällä elliptisen käyrän salausta (ECDHE). Tämä ei kuulu tämän artikkelin piiriin, mutta jos olet kiinnostunut oppimaan lisää tämän vaihdon takana olevasta matematiikasta, tutustu tähän artikkeliin.

Tarkempia tietoja DH: n heikkouksista saat tästä valkoisesta paperista ja tältä verkkosivustolta.

RSA

RSA on nimetty tekijöille - Rivest, Shamir, Adleman - ja se on tapa luoda julkisia ja yksityisiä avaimia.

Teknisesti on olemassa kaksi RSA-algoritmia (toista käytetään digitaalisiin allekirjoituksiin ja toista epäsymmetriseen salaukseen) - tämä artikkeli kattaa epäsymmetrisen salauksen algoritmin.

Tämä mahdollistaa avainten vaihdon - määrität ensin kumpikin osapuolen julkisen / yksityisen tapahtuman avaimille, sitten luot symmetrisen avaimen ja lopuksi julkisen / yksityisen avaimen parien avulla kommunikoi jaettu symmetrinen avain turvallisesti.

Koska epäsymmetrinen salaus on yleensä hitaampaa kuin symmetrinen salaus, eikä se skaalaa yhtä hyvin, epäsymmetrisen salauksen käyttäminen symmetristen avainten turvalliseen vaihtamiseen on hyvin yleistä.

Joten miten se toimii?

  1. Valitse 2 erittäin suurta alkulukua (vähintään 512 bittiä tai 155 desimaalia), x ja y (näiden numeroiden on oltava salaisia ​​ja valittava satunnaisesti)
  2. Etsi tuote eli z = x * y
  3. Valitse pariton julkinen kokonaisluku e välillä 3 ja n - 1, ja sillä ei ole yhteisiä tekijöitä (lukuun ottamatta 1) (x-1) (y-1) kanssa (joten se on suhteellisen alkuluku x - 1: lle ja y - 1: lle. ).
  4. Etsi x - 1: n ja y - 1: n pienin yhteinen monikko ja kutsu sitä L: ksi.
  5. Laske yksityinen eksponentti d luvuista x, y ja e. de = 1% L. d on käänteinen e% L: lle (tiedät, että käänteinen on olemassa, koska e on suhteellisen alkuluku z - 1: lle ja y - 1: lle). Tämä järjestelmä toimii, koska p = (p ^ e) ^ d% z.
  6. Tulos (z, e) julkisena avaimena ja (z, d) yksityisenä avaimena.

Nyt, jos Bob haluaa lähettää viestin Alicelle, hän luo salakirjoituksen (C) pelkkää tekstiä (P) käyttäen tätä kaavaa:

C = P ^ e% z

Tämän viestin salauksen purkamiseksi Alice laskee seuraavan:

P = C ^ d% z

D: n ja e: n suhde varmistaa, että salaus- ja salauksenpurkutoiminnot ovat käänteisiä. Tämä tarkoittaa sitä, että salauksenpurkutoiminto pystyy palauttamaan alkuperäisen viestin onnistuneesti ja että alkuperäisen viestin palauttaminen ilman yksityistä avainta (z, d) (tai alkutekijöitä x ja y) on melko vaikea.

Tämä tarkoittaa myös sitä, että voit tehdä z: stä ja e: stä julkisen vaarantamatta järjestelmän turvallisuutta, mikä helpottaa kommunikointia muiden kanssa, joiden kanssa sinulla ei vielä ole jaettua salaista avainta.

Voit myös käyttää toimintoja päinvastaisessa järjestyksessä saadaksesi viestin digitaalisen allekirjoituksen. Ensinnäkin käytät salauksen purkutoimintoa selkeällä tekstillä. Esimerkiksi s = ALLEKIRJOITUS (p) = p ^ d% z.

Sitten vastaanottaja voi tarkistaa digitaalisen allekirjoituksen soveltamalla salaustoimintoa ja vertaamalla tulosta viestiin. Esimerkiksi m = TARKISTA (s) = S ^ e% z.

Usein kun tämä on tehty, selkeä teksti on viestin tiiviste, mikä tarkoittaa, että voit allekirjoittaa viestin (pituudesta riippumatta) vain yhdellä eksponentilla.

Järjestelmän turvallisuus perustuu muutamaan asiaan:

  1. (Tosiasia) Päälukujen, jopa suurten alkulukujen (kuten x ja y) luominen on suhteellisen helppoa.
  2. (Tosiasia) Kertolasku on helppoa. Z: n löytäminen on erittäin helppoa.
  3. (Oletus perustuu nykyiseen matematiikkaan) Faktorointia on vaikea. Kun otetaan huomioon z, on suhteellisen vaikea palauttaa x ja y. Se on kykenevä, mutta se kestää jonkin aikaa, ja se on kallista.

    Erään arvion mukaan 1024-bittisen luvun alkutekijöiden palauttaminen veisi vuoden koneella, joka maksoi 10 miljoonaa dollaria. Koon kaksinkertaistaminen lisäisi eksponentiaalisesti tarvittavaa työtä (useita miljardeja kertoja enemmän).

    Kun tekniikka etenee edelleen, nämä kustannukset (ja vaadittava työ) vähenevät, mutta tässä vaiheessa tämän tyyppinen, oikein toteutettu salaus on epätodennäköinen kompromissin lähde.

    Yleensä ainoat hakkerit, joilla on tämäntyyppinen raha ja omistautuminen yhteen kohteeseen, ovat kansallisvaltiot. Lisäksi, jos on helpompi tapa vaarantaa järjestelmä (katso alla), se on todennäköisesti parempi vaihtoehto.

4. (Tosiasia) Modulaarinen eksponentti on helppoa. Toisin sanoen on suhteellisen helppoa laskea c = p ^ e% z.

5. (Tosiasia) Modulaarinen juuriuuttaminen - yllä olevan prosessin kääntäminen - on helppoa, jos sinulla on alkutekijät (jos sinulla on z, c, e ja alkutekijät x ja y, on helppo löytää p niin, että c = p ^ e% z).

6. (Nykyiseen laskentatehoon ja matematiikkaan perustuva oletus) Modulaarinen juurien poiminta ilman alkutekijöitä on erittäin vaikeaa (jos sinulla on z, c, e, mutta ei x ja y, on suhteellisen vaikea löytää p: tä siten, että c = p ^ e% z, varsinkin jos a on riittävän suuri).

Haluatko oppia lisää matematiikasta paljon älykkäämpiä ihmisiä? Tutustu tähän artikkeliin.

Hienoa, mikä on parempi?

Se riippuu käyttötapauksestasi. Näiden kahden algoritmin välillä on muutama ero - ensinnäkin täydellinen eteenpäin salassapito (PFS), josta puhuimme aiemmin Diffie-Hellmanin yhteydessä. Vaikka teknisesti voisit luoda lyhytaikaisia ​​RSA-avainpareja ja tarjota täydellisen etusalaisuuden RSA: n kanssa, laskennalliset kustannukset ovat paljon korkeammat kuin Diffie-Hellmanille - mikä tarkoittaa, että Diffie-Hellman on parempi valinta SSL / TLS-toteutuksiin, joissa haluat täydellisen salaisuuden eteenpäin. .  

Vaikka algoritmien välillä on joitain suorituskykyeroja (palvelimelta vaadittavan työn suhteen), suorituskykyerot eivät yleensä ole riittävän suuria erottamaan toisistaan.

Sen sijaan ensisijainen näkökohta määritettäessä, mikä on parempi, riippuu siitä, kumpi on paremmin tuettu käyttötapauksessasi (esimerkiksi SSL: n käyttöönotossa haluat Diffie Hellmanin täydellisen salassapitovelvollisuuden vuoksi) tai mikä on suositumpi tai hyväksytty alan standardina.

Esimerkiksi kun Diffie-Hellman oli Yhdysvaltain hallituksen hyväksymä ja institutionaalisen elimen tukema, standardia ei julkaistu - kun taas RSA (yksityisen organisaation standardoima) tarjosi ilmaisen standardin, mikä tarkoittaa, että RSA: sta tuli erittäin suosittu yksityisten organisaatioiden keskuudessa.

Jos olet kiinnostunut lukemaan lisää, täällä on hieno lanka eroista.

Haluatko oppia hakkereiden käyttämään salaushyökkäyksiä? Kokeile näitä Cryptopalsin haasteita.

Mitä enemmän opin salauksesta, sitä enemmän luulen, että Alice ja Bob todennäköisesti puhuvat vain henkilökohtaisesti.

- Paul Reinheimer (@preinheimer) 13. maaliskuuta 2017