Šifravimo algoritmai, paaiškinti pavyzdžiais

Kriptografija yra pats pagrindinis mokslas apie kodų ir šifrų naudojimą pranešimams apsaugoti.

Šifravimas - tai pranešimų kodavimas, siekiant tik leisti numatytam gavėjui suprasti pranešimo prasmę. Tai yra dviejų krypčių funkcija (turite sugebėti anuliuoti bet kokį šifravimą, kurį atlikote pranešime). Tai skirta apsaugoti gabenamus duomenis.

Jei ieškote bendro simetrinių ir asimetrinių algoritmų skirtumo pagrindo ir bendros šifravimo apžvalgos, pradėkite čia. Šis straipsnis pirmiausia apims du dažniausiai naudojamus šifravimo algoritmus.

Apibendrinant, pirmą kartą kuriant simetriškus algoritmus kilo didelė problema - jie efektyviai veikė tik tuo atveju, jei abi šalys jau žinojo bendrą paslaptį. Jei jie to nepadarė, saugiai pasikeisti raktą be trečiosios šalies išvakarėse buvo labai sunku numesti.

Ir jei trečioji šalis gavo raktą, jiems buvo labai lengva sulaužyti šifravimą, o tai sugadino saugaus bendravimo tikslą.

Diffie-Hellmanas išsprendė šią problemą leisdamas nepažįstamiems žmonėms keistis informacija viešaisiais kanalais, kuriais galima suformuoti bendrą raktą. Bendrą raktą sunku nulaužti, net jei stebimas visas ryšys.

Kaip veikia Diffie-Hellmanas?

Diffie-Hellmanas vadinamas raktų mainų protokolu. Tai yra pagrindinis „Diffie-Hellman“ naudojimas, nors jis taip pat galėtų būti naudojamas šifravimui (paprastai taip nėra, nes efektyviau naudoti DH norint pasikeisti raktus, tada persijungti į (žymiai greitesnį) simetrišką duomenų perdavimą ).

Tai veikia taip:

Iš esmės yra dvi šalys - Alisa ir Bobas, kurios susitaria dėl pradinės spalvos (savavališkos, bet kaskart turi skirtis). Jie taip pat turi slaptą spalvą, kurią pasilieka sau. Tada jie sumaišo šią spalvą su bendra spalva, todėl gaunamos dvi skirtingos spalvos. Tada jie perduoda šią spalvą kitai šaliai, kuri sumaišo ją su savo slapta spalva, todėl gaunama ta pati slapta spalva.

Tai remiasi idėja, kad palyginti nesudėtinga maišyti dvi spalvas, tačiau jas atskirti labai sunku, norint rasti slaptą spalvą. Praktiškai tai daroma su matematika.

Pavyzdžiui:

  1. Bobas ir Alisa sutaria dėl dviejų skaičių, didelio pirminio skaičiaus, p = 29, ir bazės g = 5
  2. Dabar Bobas pasirenka slaptą skaičių x (x = 4) ir atlieka šiuos veiksmus: X = g ^ x% p (šiuo atveju% nurodo likutį. Pavyzdžiui, 3% 2 yra 3/2, kur likusi dalis yra 1) . X = 5 ^ 4% 29 = 625% 29 = 16
  3. Alisa taip pat pasiima slaptą skaičių y (y = 8) ir daro taip: Y = g ^ y% p. Y = 5 ^ 8% 29 = 390 625% 29 = 24
  4. Bobas siunčia X Alisai, o Alisa siunčia Y Bobui.
  5. Tada Bobas daro taip: K = Y ^ x% p, K = 24 ^ 4% 29 = 331,776% 29 = 16
  6. Tada Alisa daro taip: K = X ^ y% p, K = 16 ^ 8% 29 = 4 294 967 296% 29 = 16

Puikus (* galbūt magija *) dalykas yra tas, kad tiek Bobas, tiek Alice turi tą patį numerį K ir dabar gali tai naudoti slapta, nes niekas kitas nežino K.

Šio protokolo saugumas priklauso nuo kelių dalykų:

  1. (Faktas) Palyginti lengva generuoti pirminius skaičius, net didelius pirminius skaičius (pvz., P).
  2. (Faktas) Modulinis eksponavimas yra lengvas. Kitaip tariant, palyginti lengva apskaičiuoti X = g ^ x% p.
  3. (Darant prielaidą, pagrįstą dabartine skaičiavimo galia ir matematika) Modulinis šaknų išskyrimas be pagrindinių veiksnių yra labai sunkus. Iš esmės labai sunku rasti K nežinant x ir y, net jei jūs nužiūrėjote eismą ir matote p, g, X ir Y.

Taigi, darant prielaidą, kad tai buvo tinkamai įgyvendinta, palyginti nesudėtinga atlikti matematiką, reikalingą raktui sukurti, tačiau labai sunku ir daug laiko reikia atlikti matematiką, reikalingą norint sugadinti raktą grubiai jį verčiant.

Net jei užpuolikas galėtų sugadinti šį raktą, Diffie-Hellmanas leidžia tobulai saugoti puolėją.

Kas yra tobulas pirmumo slaptumas?

Tai yra mintis, kad jei jūs sugadinsite šifravimą, kurį serveris naudoja bendraujant dabar, tai nereiškia, kad galima perskaityti visus serverio kada nors atliktus ryšius.

Kitaip tariant, tai leidžia pamatyti tik dabar naudojamus ryšius (ty su šiuo slaptu raktu). Kadangi kiekvienas ryšių rinkinys turi skirtingą slaptą raktą, turėsite juos visus nulaužti atskirai.

Tai įmanoma, jei kiekvienoje sesijoje kiekvienam seansui yra skirtingas trumpalaikis raktas. Kadangi Diffie-Hellmanas visada naudoja naujas atsitiktines reikšmes kiekvienam seansui (todėl kiekvienam seansui sukuria naujus raktus), jis vadinamas trumpalaikiu Diffie Hellmanu (EDH arba DHE). Daugelis šifruotų programų naudoja tai, kad pasiektų tobulą paslaptį į priekį.

Kadangi Diffie-Hellmanas leidžia paprastu tekstu keistis pagrindine medžiaga, nesijaudindamas, kad bus pažeista bendroji paslaptis, o matematika yra pernelyg sudėtinga, kad užpuolikas galėtų grubiai kovoti, užpuolikas negali išvesti seanso rakto (ir net jei galėtų, naudodamas skirtingi, trumpalaikiai, kiekvieno seanso raktai reiškia, kad jie galėjo tik šnipinėti šį seansą - ne anksčiau ar ateityje.

Persiuntimo slaptumas įgalinamas bet kuriame „Diffie-Hellman“ raktų maine, tačiau tik trumpalaikis raktų keitimas (skirtingas raktas kiekvienam seansui) užtikrina tobulą pirmumo slaptumą.

Čia yra Scotto Helme'o įrašas, kuriame apie tai kalbama išsamiau ir paaiškinama, kaip tai įgalinti savo serveriuose.

Kokie yra Diffie-Hellmano apribojimai?

Didžiausias DH apribojimas yra tai, kad netikrinama tapatybė. Kitaip tariant, kiekvienas gali teigti, kad yra Alisa ar Bobas, ir nėra jokio įmontuoto mechanizmo, leidžiančio patikrinti, ar jų teiginys yra teisingas.

Be to, jei diegimas nebus vykdomas saugiai, algoritmas gali būti nulaužtas turint pakankamai tam skirtų išteklių (mažai tikėtina, bet įmanoma akademinėms komandoms ar nacionalinės valstybės veikėjams).

Pvz., Taip gali atsitikti, jei atsitiktinių skaičių generatoriui nėra suteikta tinkama entropija, palaikanti norimą stiprumą - kitaip tariant, kadangi kompiuterio sugeneruoti skaičiai niekada nėra atsitiktiniai, o tai, kiek dirbtinai įvedėte netikrumą, turi reikšmės jūsų įgyvendinimo.

Be to, 2015 m. Įvyko ataka, kuri parodė, kad kai daugelis serverių naudojo tuos pačius pirminius skaičius kaip raktų mainų pradžia, bendras Diffie-Hellman saugumas buvo mažesnis nei tikėtasi.

Iš esmės užpuolikas galėtų tiesiog iš anksto apskaičiuoti ataką prieš tą pirminį, kad būtų lengviau sukompromituoti kiekvieno serverio, kuris naudojo tą pirminį numerį, sesijas.

Taip atsitiko todėl, kad milijonai serverių keisdami raktus naudojo tuos pačius pirminius skaičius. Išankstinis tokio tipo atakų skaičiavimas vis dar reikalauja akademinių ar nacionalinės valstybės išteklių ir vargu ar turės įtakos daugumai žmonių.

Tačiau, laimei tiems, kurie turi jaudintis dėl nacionalinių valstybių užpuolikų, yra kitas būdas pasiekti DH raktų mainus naudojant elipsinės kreivės kriptografiją (ECDHE). Šis straipsnis nepatenka į šio straipsnio taikymo sritį, tačiau jei norite sužinoti daugiau apie šio mainų matematiką, peržiūrėkite šį straipsnį.

Norėdami išsamiau susipažinti su DH trūkumais, peržiūrėkite šį dokumentą ir šią svetainę.

RSA

RSA pavadinta kūrėjams - „Rivest“, „Shamir“, „Adleman“ - ir tai yra būdas generuoti viešuosius ir asmeninius raktus.

Techniškai yra du RSA algoritmai (vienas naudojamas skaitmeniniams parašams, o kitas - asimetriškam šifravimui.) - šis straipsnis apima asimetrinio šifravimo algoritmą.

Tai leidžia keistis raktais - pirmiausia kiekvienai šaliai priskiriate sandorio viešuosius / asmeninius raktus, tada sugeneruojate simetrišką raktą ir galiausiai naudojate viešojo / privataus raktų poras, kad saugiai perduotumėte bendrą simetrišką raktą.

Kadangi asimetriškas šifravimas paprastai yra lėtesnis nei simetriškas šifravimas ir nėra taip gerai keičiamas, labai dažnai naudojama asimetrinė šifruotė norint saugiai keistis simetriškais raktais.

Taigi, kaip tai veikia?

  1. Pasirinkite 2 labai didelius pirminius skaičius (mažiausiai 512 bitų arba po 155 dešimtainius skaitmenis), x ir y (šie skaičiai turi būti slapti ir pasirinkti atsitiktinai)
  2. Raskite sandaugą, ty z = x * y
  3. Pasirinkite nelyginį viešąjį skaičių e, tarp 3 ir n - 1, ir neturite bendrų veiksnių (išskyrus 1) su (x-1) (y-1) (taigi jis yra santykinai pirminis iki x - 1 ir y - 1 ).
  4. Raskite mažiausią x - 1 ir y - 1 kartotinį ir pavadinkite jį L.
  5. Apskaičiuokite privatų rodiklį d iš x, y ir e. de = 1% L. d yra e% L atvirkštinė (jūs žinote, kad atvirkštinė egzistuoja, nes e yra santykinai pirminė z - 1 ir y - 1). Ši sistema veikia, nes p = (p ^ e) ^ d% z.
  6. Rezultatas (z, e) kaip viešasis raktas ir (z, d) kaip privatus raktas.

Dabar, jei Bobas norėtų nusiųsti pranešimą Alisai, jis sukuria šifrinį tekstą (C) iš paprasto teksto (P) naudodamas šią formulę:

C = P ^ e% z

Siekdama iššifruoti šį pranešimą, Alisa apskaičiuoja:

P = C ^ d% z

Ryšys tarp d ir e užtikrina, kad šifravimo ir iššifravimo funkcijos yra inversijos. Tai reiškia, kad iššifravimo funkcija gali sėkmingai atkurti pradinį pranešimą ir kad gana sunku atkurti pradinį pranešimą be privataus rakto (z, d) (arba pirminių faktorių x ir y).

Tai taip pat reiškia, kad galite viešai paskelbti z ir e nepakenkdami sistemos saugumui, palengvindami bendravimą su kitais, su kuriais dar neturite bendro slapto rakto.

Taip pat galite naudoti atvirkštines operacijas, kad gautumėte pranešimo skaitmeninį parašą. Pirma, jūs naudojate iššifravimo operaciją paprastame tekste. Pavyzdžiui, s = PARAŠAS (p) = p ^ d% z.

Tada gavėjas gali patikrinti skaitmeninį parašą pritaikydamas šifravimo funkciją ir palyginęs rezultatą su pranešimu. Pavyzdžiui, m = PATIKRINTI (-I) = S ^ e% z.

Dažnai tai padarius, paprastas tekstas yra pranešimo maiša, o tai reiškia, kad galite pasirašyti pranešimą (neatsižvelgiant į ilgį) tik su vienu laipsniu.

Sistemos saugumas pagrįstas keliais dalykais:

  1. (Faktas) Palyginti lengva generuoti pirminius skaičius, net didelius pirminius skaičius (pvz., X ir y).
  2. (Faktas) Dauginti lengva. Labai lengva rasti z.
  3. (Dabartine matematika paremta prielaida) Faktoringas yra sunkus. Atsižvelgiant į z, palyginti sunku atkurti x ir y. Tai galima padaryti, bet tai užtrunka šiek tiek laiko ir yra brangu.

    Vienas vertinimas sako, kad norint susigrąžinti pagrindinius 1024 bitų skaičiaus koeficientus mašina, kuri kainuoja 10 milijonų dolerių, užtruks metus. Padvigubinus dydį, eksponentiškai padidėtų reikalingas darbas (kelis milijardus kartų daugiau).

    Technologijoms tobulėjant toliau, šios išlaidos (ir reikalingi darbai) mažės, tačiau šiuo metu tokio tipo šifravimas, tinkamai įgyvendinamas, yra mažai tikėtinas kompromisų šaltinis.

    Paprastai vieninteliai įsilaužėliai, turintys tokio tipo pinigus ir pasišventę vienam tikslui, yra nacionalinės valstybės. Be to, jei yra lengvesnis būdas sukompromituoti sistemą (žr. Toliau), tai tikriausiai yra geresnis pasirinkimas.

4. (Faktas) Modulinis eksponavimas yra lengvas. Kitaip tariant, palyginti lengva apskaičiuoti c = p ^ e% z.

5. (Faktas) Modulinį šaknų išskyrimą - pakeisti pirmiau pateiktą procesą - lengva, jei turite pagrindinius veiksnius (jei turite z, c, e ir pagrindinius koeficientus x ir y, lengva rasti p, kad c = p ^ e% z).

6. (Darant prielaidą, pagrįstą dabartine skaičiavimo galia ir matematika) Modulinis šaknų išskyrimas be pagrindinių veiksnių yra labai sunkus (jei turite z, c, e, bet ne x ir y, palyginti sunku rasti p, kad c = p ^ e% z, ypač jei a yra pakankamai didelis).

Norite sužinoti daugiau apie matematiką iš daug protingesnių žmonių? Peržiūrėkite šį straipsnį.

Puiku, kas geriau?

Tai priklauso nuo jūsų naudojimo atvejo. Tarp šių dviejų algoritmų yra keli skirtumai - pirma, tobulas slaptumas į priekį (PFS), apie kurį anksčiau kalbėjome Diffie-Hellmano kontekste. Nors techniškai jums gali generuoti efemeriškas RSA raktų poras ir suteikti puikią ateitį paslapties RSA, skaičiuojamoji kaina yra daug didesnė nei Diffie-Hellman - tai reiškia, kad Diffie-Hellman yra geresnis pasirinkimas SSL / TLS diegimas kur norite puikus pirmyn slaptumą .  

Nors tarp šių dviejų algoritmų yra tam tikrų našumo skirtumų (kalbant apie darbą, reikalingą iš serverio), našumo skirtumai paprastai nėra pakankamai dideli, kad skirtųsi juos renkantis.

Vietoj to, apskritai, pagrindinis aspektas nustatant, kuris yra geresnis, priklauso nuo to, kuris iš jų yra labiau palaikomas jūsų naudojimo atveju (pavyzdžiui, diegdami SSL norėsite Diffie Hellmano dėl tobulo į priekį slaptumo) ar kuris yra populiaresnis ar priimtas kaip standartas pramonėje.

Pavyzdžiui, nors Diffie-Hellmanui buvo patvirtinta JAV vyriausybė ir jį palaikė institucinė institucija, standartas nebuvo išleistas, o RSA (standartizuota privačios organizacijos) suteikė nemokamą standartą, o tai reiškia, kad RSA tapo labai populiari tarp privačių organizacijų.

Jei jus domina daugiau skaityti, čia yra puiki tema apie skirtumus.

Norite sužinoti, kaip įsilaužėliai naudoja kriptografines atakas? Išbandykite šį „Cryptopals“ iššūkių rinkinį.

Kuo daugiau sužinau apie kriptografiją, tuo labiau manau, kad Alisa ir Bobas tikriausiai turėtų tiesiog kalbėtis asmeniškai.

- Paulas Reinheimeris (@preinheimer) 2017 m. Kovo 13 d