Kryptologia

Monoalfaattinen substituutio

Sen sijaan, että vain lisäät kiinteän offsetin jokaiseen merkkiin, voit laskea substituutiotaulukon etukäteen generoimalla aakkosten satunnaisen permutaation. Esimerkiksi:

 ABCDEFGHIJKLMNOPQRSTUVWXYZ MQHPSVJYCURFTBILAKWNGZDOEX

Nyt ATTACKATDAWN on nyt MNNMHRMNPMDB.

Tätä ei voi murtaa arvaamalla avainta (mahdollisia avaimia on $n!$), mutta frekvenssianalyysillä voi murtaa minkä tahansa monoalfabeettisen substituutiosalakirjoituksen, jos viesti on tarpeeksi pitkä.

Tekniikoille, joiden avain on permutaatio, yksi tapa tehdä avaimesta helpommin muistettava on valita lause, asettaa sen yksilölliset kirjaimet ja täyttää sitten puuttuvat kirjaimet järjestyksessä. Esimerkiksi PREMATURE OPTIMIZATION IS THE ROOT OF ALL EVIL tuottaa tämän substituutiokartoituksen:

 PREMATUOIZNSHFLVBCDGJKQWXY

Homofoninen substituutio

Jokainen selkotekstin kirjain vastaa yhtä tai useampaa symbolia salatekstissä. Kohteiden lukumäärän tulisi olla verrannollinen niiden esiintymistiheyteen (taajuusanalyysin voittamiseksi). Esimerkki:

 A 12 15 36 50 56 70 81 95 B 51 84 C 16 44 65 D 04 06 48 82 E 01 17 19 34 47 49 58 60 67 77 85 90 F 13 27 G 09 28 H 26 42 53 59 68 71 I 35 73 76 86 91 96 J 18 K 07 L 29 40 54 87 M 25 30 N 21 61 62 69 74 94 O 02 03 08 10 57 75 93 P 41 98 Q 97 R 32 38 43 45 80 83 S 14 22 39 79 89 99 T 00 20 23 33 46 52 72 78 88 U 11 64 66 V 37 W 63 92 X 31 Y 24 55 Z 05

Valitaan salakirjoitusta varten satunnaisesti vaihtoehdoista. Esimerkki: ATTACKATDAWN:n yksi mahdollinen salaus on

 56 78 20 95 65 07 12 72 06 50 92 61

Simppeli Vigenère

Simppeli Vigenère-salakirjoituksena tunnettua salakirjoitusta ei keksinyt Vigenère lainkaan… sen näyttäisi kuvanneen ensimmäisenä Giovan Battista Bellaso. Avain on merkkijono, joka lisätään selkotekstiin modulaarisella yhteenlaskulla, kuten tässä esimerkissä (A=0, B=1, C=2, …, Z=25):

 Plaintext: TAKEACOPYOFYOURPOLICYTONORMAWILCOXONTHETHIRDFLOOR Key: QUARKQUARKQUARKQUARKQUARKQUARKQUARKQUARKQUARKQUAR Ciphertext: JUKVKSIPPYVSOLBFILZMONOEYHGANSBWOOYDNHVDXCRUPBIOI

Salakirjoitustekstin tuottamiseen käsin voidaan käyttää koodipyörää tai tabula rectaa.

Tämä systeemi ei ole turvallinen, koska avain toistuu. Jos avaimen pituus voidaan määrittää, salausanalyytikko voi tehdä useita taajuusanalyysejä (yksi jokaiselle avaimen siirtymäarvolle). Menetelmiä avaimen pituuden määrittämiseksi ovat Kaisiski-menetelmä ja Friedmanin testi.

Binääridatan (eli bittisarjan) osalta modulaarinen yhteenlasku base-2 on vain yksinkertainen xor. Esimerkki:

 Plaintext: 0110000101010000111101001010101010010000001111101 Key: 0000011100000111000001110000011100000111000001110 Ciphertext: 0110011001010111111100111010110110010111001110011

Autoavain Vigenère

Vigenère itse asiassa loi autokey-salauksen, joka on vahvempi, koska avain ei koskaan toistu. Sen sijaan ”avain” muodostuu avainlauseesta, jota seuraa selkoteksti, esimerkiksi näin:

 Plaintext: TAKEACOPYOFYOURPOLICYTONORMAWILCOXONTHETHIRDFLOOR Key: QUARKTAKEACOPYOFYOURPOLICYTONORMAWILCOXONTHETHIRD Ciphertext: JUKVKVOZCOHMDSFUMZCTNHZVQPFOJWCOOTWYVVBHUBYHYSWFU

Tässä käytettiin selkotekstiä osana avainta. Voit käyttää myös salaustekstiä. Nykyaikaiset automaattiset avainsalakirjoitukset luovat siirtoarvot satunnaislukugeneraattorilla. Avain siementää generaattorin.

One Time Pad

Jos avain:

• on yhtä pitkä tai pidempi kuin koodattava viesti
• on aidosti satunnaisesti generoitu
• käytetään vain kerran

Tällöin käytössäsi on todistetusti suojattu salaus, jota kutsutaan nimellä one time pad. Varsinainen algoritmisi voi käyttää polyalfaattista substituutiota tai jopa pelkkää xorointia viestin ja avaimen välillä, kunhan täytät edellä mainitut kolme kriteeriä.

Kertakäyttöalustaa ei voi koskaan murtaa. Se on täydellinen salausjärjestelmä, ainakin matemaattisesta näkökulmasta.

Playfair

Tämä on esimerkki polygrafisesta substituutiosalakirjoituksesta.Se korvaa merkkipareja. Avain on {A..I,K..Z}:n permutaatio, esimerkiksi:

 Z C B M L G D A Q E T U O K H F S X V N P I Y R W

Salausta varten kirjoitetaan selkoteksti (ilman välilyöntejä tai välimerkkejä) ja merkitään X-kirjain kaksoiskirjainten väliin ja tarvittaessa loppuun, jotta tekstin pituus olisi tasainen.Sitten jokaiselle kirjainparille:

• Jos $(a,b)$ on ensimmäisen merkin rivi ja sarake ja $(c,d)$ on toisen merkin rivi ja sarake.
• Jos $a \neq c$ ja $b \neq d$ niin palauta $(a,d)(b,c)$.
• Jos $a = c$ niin palautetaan $(a,(b+1) \bmod 5)(c,(d+1) \bmod 5)$.
• Jos $b = d$ niin palautetaan $((a+1) \bmod 5,b)((c+1) \bmod 5,d)$.

Salaus ajaa säännöt toisinpäin. Playfair-salaus on melko epävarma.

Four-square

Kryptaa digrafeja kuten Playfair, mutta on hieman vahvempi, koska se sallii kaksoiskirjaimet ja ei tuota käänteisiä salaustekstidigrafeja käänteisille valkotekstidigrafeille. Esimerkki

 a b c d e G I V E M f g h i k L B R T Y l m n o p O D A H C q r s t u F K N P Q v w x y z S U W X Z P R E M A a b c d e T U O I Z f g h i k N S H F L l m n o p V B C D G q r s t u K Q W X Y v w x y z

Okei, hieman vahvempi kuin Playfair, mutta mitä sitten? Tietokoneet pystyvät murtamaan nämä sekunneissa tai ehkä minuuteissa (jos salaustekstiä on tarpeeksi).

Yksinkertainen lohkotranspositio

Yksinkertaisin transpositio-salaus jakaa viestin n-kokoisiin lohkoihin ja sekoittaa sitten jokaisen lohkon $(1..n)$:n permutaation mukaisesti.

Pylvästranspositio

Kirjoita viesti rivi riviltä ruudukkoon ja lue se sitten sarakkeittain. Täysin epävarmaa. Avain on vain rivien lukumäärä. Arvaa se.

Kiskoaita

Kiskoaita ei ole yhtään parempi kuin edellinen, vain hauskempi. Avain on niiden kiskojen lukumäärä, joihin kirjoitetaan selkotekstiä ylös ja alaspäin, jolloin salateksti syntyy lukemalla yksi kisko kerrallaan.

Esimerkki: Voit koodata "fill out and file a WS2475 form" neljällä kiskolla:

 f t l 4 m i u a i e 2 7 r l o n f a s 5 o l d w f

Luet sitten salatekstin "ftl4miuaie27rlonfas5oldwf". Tämä on triviaali murtaa. Arvaa vain $k$.

Substituution ja transposition yhdistäminen

Transpositio yksinään on hyvin heikko; substituutio on heikko; niiden yhdistäminen on parempi. Voit sekoittaa monia klassisia substituutiosalakirjoituksia erilaisiin transpositioihin tai käyttää joitain erityisiä yhdistelmäsalakirjoituksia, kuten bifidiä. Myös useimmat kuuluisat roottorikoneet ja nykyaikaiset salakirjoitukset käyttävät tätä yhdistelmää; itse asiassa ne soveltavat näitä muunnoksia monta kertaa.

Bifid

Tässä korvataan kirjaimet niiden koordinaateilla ruudukkoon ja tehdään koordinaateille pylvästranspositio. Esimerkki:

 Z C B M L G D A Q E T U O K H F S X V N P I Y R W

Kirjoita (rivi, sarake)-koordinaatit selkotekstin jokaisen kirjaimen alle (esim, ”A” on rivillä 1, sarakkeessa 2; ”T” on rivillä 2, sarakkeessa 0 jne.):

 ATTACKATDAWN 122102121143 200213201244

Luetaan sitten riveittäin, ryhmitellään pareittain ja etsitään salakirjoitustekstin kirjaimet:

 122102121143200213201244 A U B A D R T B Q T A W

Trifid

Kuten Bifid, mutta kuutiolla. Esimerkki:

 Z C B M L F V N P G D A Q E X I R W T U O K H S Y . J

Salausta varten kirjoitetaan ensin koordinaatit:

 ATTACKATDAWN 000001000022 122102121110 200210201221

 000001000022122102121110200210201221 Z C Z O S F H Q V I N .

Enigma

Enigma oli kuuluisa saksalainen toisen maailmansodan aikainen roottorikone (itse asiassa koneperhe).Useimmissa versioissa toteutettiin polyalfabeettinen substituutiosalauskoodi, jossa oli jakso 16900 ja lisäksi pistokytkentä salauskoodausta (transponointia) varten. Avain koostui roottoreiden järjestyksestä, kunkin roottorin alkuasennosta, rengasasetuksista ja pistolevyn asetuksista (noin 1,6 × 1020 mahdollisuutta). Joka päivä julkaistiin uusi avain (enemmän tai vähemmän) koodikirjoissa.

Liittoutuneet pystyivät murtamaan avaimen, koska sen rakenteessa oli joitakin heikkouksia…

• Yksikään kirjain ei salannut itseensä
• Self-reciprocity tarkoitti sitä, että salakirjoittajan asetusvaihtoehtoja oli vähemmän

…mutta mikä tärkeämpää, monet heikkoudet siinä, miten sitä käytettiin…

• Salakirjoittajien löytäminen oli todella helppoa. Useimmat viestit alkoivat säätiedotuksella.
• Varhain viestiavaimet ilmestyivät kahdesti peräkkäin.

…ja hankkimalla koodikirjoja kaapatuilta aluksilta.

Se miten Enigma murrettiin voit lukea NSA:sta,jaWikipediasta.

Nykyaikaiset salausmenetelmät

Nyt kun meillä on Shannonin informaatioteoria, erittäin tehokkaat tietokoneet ja vuosisatojen teoria ja käytäntö takanamme, useimmat nykyaikaiset tekniikat:

• käyttävät bittijonoja, eivät merkkijonoja
• ovat varovaisia peittääkseen täysin selkotekstin kuviot ja redundanssit
• käyttävät satunnaisia avaimia (joita voidaan myös käyttää uudelleen)
• varmistavat sen, että hyvin pienetkin muutokset selkotekstissä vaikuttavat suureen osaan salatusta tekstistä (ja päinvastoin). Tätä kutsutaan AvalancheEfektiksi.

Lisäksi on hyvä, jos salakirjoitus on:

• tehokas
• vikasietoinen

Useimmat salakirjoitukset ovat joko lohko- tai virtasalakirjoituksia. Lohkosalakirjoitukset vaativat täytettä ja voivat toimia eri tiloissa (Ks. Schnierin kirja tai Wikipedian artikkeli.)

• ECB – Electronic Codebook
• CBC – Cipher Block Chaining
• CFB – Cipher Feedback
• OFB – Output Feedback
• CTR – Counter
• BC – Block Chaining
• PCBC – Propagating Cipher Block Chaining
• CBCC – Cipher Block Chaining with Checksum

DES

Wikipediassa

IDEA

Wikipediassa

RC4

Wikipediassa

RC6

Wikipediassa

Blowfish

At Wikipedia

Twofish

At Wikipedia

AES

At Wikipedia

AES on uusi standardi, joka korvaa DES:n. Se voitti kilpailun (vuonna 2001), jossa se esitettiin nimellä Rijndael, ja voittiRC6:n, Serpentin, MARSin ja Twofishin.

Key Exchange

Diffie ja Hellman (vuoden 2015 Turing-palkinnon voittajat) ja heidän ystävänsäMerkle osoittivat vuonna 1976, että kaksi ihmistä voi vaihtaa salaisen avaimen ilman, että heidän tarvitsee tavata salaa:

• Alice valitsee alkuluvun $n$ ja lähettää sen salassa Bobille
• Alice valitsee alkuluvun mod $n$ (miten löytää),nimeltään $g$, ja lähettää sen salassa Bobille
• Alice valitsee salaisen kokonaisluvun $a$, ja lähettää $g^a \bmod n$ selvänä Bobille
• Bob valitsee salaisen kokonaisluvun $b$ ja lähettää $g^b \bmod n$ selvänä Alicelle
• Alice laskee ($g^b \bmod n)^a \bmod n$ ja Bob laskee ($g^a \bmod n)^b \bmod n$. Tämä on avain!(Se on $g^{ab} \bmod n$)

Tämä on luultavasti turvallista, jos $n$ on hyvin suuri ja $\frac{n-1}{2}$ on myös alkuluku, koska vaikka Eve tietää $g$, $n$, $g^a \bmod n$ ja $g^b \bmod n$, ei tunneta mitään tehokasta tapaa saada $a$ tai $b$ näistä.Se on diskreetin logaritmin ongelma, muistatko?

Esimerkki pienellä $n$:

• Alice valitsee $n=208799$ ja $g=13$ ja lähettää nämä Bobille
• Alice valitsee $a=152335$ ja Bob valitsee $b=98113$
• Alice lähettää Bobille $13^{152335} \bmod 208799 = 73033$
• Bob lähettää Alicelle $13^{98133} \bmod 208799 = 147540$
• Alice laskee $147540^{152335} \bmod 208799 = 8435$
• Bob laskee $73033^{98133} \bmod 208799 = 8435$
• Salainen avain on $8435$.

Älä tee tätä pienillä $n$:n arvoilla.

Yleisesti, ellet saa jonkinlaista sertifikaattia,älä yritä turvata mitään reaalimaailman järjestelmiä yksin. Mutta tietysti dogo eteenpäin ja opettelealgoritmit ja harjoittele koodausta toistaiseksi.

Julkisen avaimen kryptografia

Julkisen avaimen salakirjoitukset ratkaisevat salaisen avaimen salakirjoitusten avaintenhallinnan painajaisen nopeuden kustannuksella. $n$-ihmisten ryhmässä tarvitaan vain $n$julkisia avaimia ja $n$ yksityisiä avaimia.

RSA-kryptosysteemi

Diffie-Hellman ei tee salausta, vaan vaihtaa vain avaimen.RSA voi salata ja purkaa salauksen. Näin se toimii. Kumpikin henkilö

• Luo kaksi suurta alkulukua, $p$ ja $q$.
• Valitsee arvon $e$, joka on suhteellisesti alkuluku suhteessa $(p-1)(q-1)$.
• Julkaisee julkisen avaimensa $(N,e)$, jossa $N = pq$.
• Lasketaan $d$ = $e$:n modulaarinen käänteisluku suhteutettuna $(p-1)(q-1)$:n. Pidetään se salassa.
• Hävittää $p$ ja $q$.

Tarkista nyt tämä:

• Liisa lähettää viestin $m$ Bobille lähettämällä $c = m^e \bmod N$.
• Bob purkaa tämän helposti, koska $m = c^d \bmod N$.

Triviaali esimerkki:

VAROITUS!
Tämä esimerkki on vain havainnollistamista varten. Älä koskaan toteuta omaa salausalgoritmia. Varmista myös, että ymmärrät, miten kamalaa julkisen avaimen kryptografia on näin pienillä avaimilla. Todellisissa avaimissa pitäisi olla tuhansia bittejä.

Käytetään 16-bittistä avainta (ÄLÄ tee tätä IRL). Generoidaan kaksi satunnaista 8-bittistä alkulukua:

$p = 163\\q = 173$

Generoidaan 16-bittinen alkuluku koodin eksponenttia varten:

$e = 64013$

Nyt:

$n = pq = 28199 \\\d = \mathsf{modInverse}(e, (p-1)(q-1)) = 6797$

Koodataan merkkijono ¿Dónde está ud.?. Tässä se on UTF-8:na:

c2 bf 44 c3 b3 6e 64 65 20 65 73 74 c3 a1 20 75 64 2e 3f

Desimaalilukuna:

194 191 68 195 179 110 100 101 32 101 115 116 195 161 32 117 100 46 63

Sovelletaan nyt koodausfunktiota jokaiseen::

$194^{64013} \bmod 28199 = 15626$
$191^{64013} \bmod 28199 = 19945$
$68^{64013} \bmod 28199 = 27982$
$\vdots$
$63^{64013} \bmod 28199 = 18384$

Salausteksti on:

15626 19445 27982 22746 2679 7739 16824 23107 9054 23107 8378 16412 22746 5566 9054 881 16824 17864 18384

Tiedon purkamiseksi:

$15626^{6797} \bmod 28199 = 194$
$19445^{6797} \bmod 28199 = 191$
$27982^{6797} \bmod 28199 = 68$
$\vdots$
$16824^{6797} \bmod 28199 = 63$

Saamme alkuperäisen viestin takaisin!

Muuten
Koska symmetrinen salaus on niin paljon nopeampi, voit ensin luoda salaisen avaimen ja lähettää sen julkisen avaimen salauksella suojatulla linjalla. Nyt kaikki tuleva viestintä voi käyttää salaista avainta.

Kryptografinen häivytys

Hash, eli sormenjälki, tarkistussumma, viestin digesti on bittikuvio (yleensä noin 160 bittiä), joka luodaan viestistä kryptografisen häivytysfunktion avulla. Jotta hash olisi turvallinen eli kryptografinen, on oltava laskennallisesti mahdotonta

• löytää viesti, joka hashaa tiettyyn arvoon (yksisuuntaisuus)
• löytää kaksi viestiä, jotka hashaa samaan arvoon (törmäyskestävyys)

Matemaattisesti ajateltuna, kryptografinen hash-funktio $H$ tuottaa viestistä hashin, $H(m) = c$, siten, että $m$ ei voida tehokkaasti määrittää $c$:stä, eikä voida tehokkaasti löytää $m_1 \neq m_2$ siten, että $H(m_1) = H(m_2)$,

Viestin yhden ainoan bitin muuttaminen saa digestin näyttämään täysin erilaiselta.

$ cat willThis is my will.I leave 1000 dollars to Aliceand everything else to Bob.Signed, Eve.$ md5sum willc18feb890752c9e680c99d1e909fd761 will$ sed "s/1/9/g" will > Will$ cat WillThis is my will.I leave 9000 dollars to Aliceand everything else to Bob.Signed, Eve.$ md5sum Will85570bc2d0458b1f98f484261dee7d4d Will

Turvallinen hash tarjoaa keinon määrittää, onko viestiä peukaloitu.

Katso Steve Friedlin kuvitettu opas kryptografisista hasheista.

Viestin todennuskoodit

Nämä ovat samanlaisia kuin kryptografiset hasheet, paitsi että niissä käytetään salaista avainta, kun taas hasheissa käytetään vain itse viestiä.

$MAC(m, k) = c$

Lisätietoja:

• MAC:t vs. Hashes at StackOverflow
• Digitaaliset allekirjoitukset Wikpediassa
• MAC:t Wikipediassa

Digitaaliset allekirjoitukset

Miten Bob voi olla varma siitä, että viesti on tullut Liisalta eikä joltakulta toiselta?Allekirjoittamalla viestin Liisalta; näin. Käytännössä yleensä allekirjoitetaan hash, ei koko viestiä.

RSA for Digital Signatures

Jos Alice lähettää viestin Bobille,

• Alice salaa m:n yksityisellä avaimellaan
• Alice salaa m:n Bobin julkisella avaimella
• Bob purkaa m:n yksityisellä avaimellaan
• Bob purkaa m:n yksityisellä avaimellaan
• . Alicen julkisella avaimella

$m = A(B'(B(A'(m)))$

DSA

Wikipediassa

Kryptoanalyysi

Tämä on laaja aihe eikä sitä käsitellä tässä. Sen sijaan tässä on luettelo tekniikoista.

• Frekvenssianalyysi
• Tunnettu selkotekstihyökkäys
• Tunnettu salaustekstihyökkäys
• Valittu selkotekstihyökkäys
• Valittu avainhyökkäys
• Lineaarinen kryptoanalyysi
• Differentiaalinen kryptoanalyysi
• Varkaus
• Lahjonta
• Kiristys

Ohjelmointiesimerkkejä

Heh, emme aio näyttää, miten roll-your-own crypto. Aiomme tarkastella joitakin todellisia olemassa olevia kirjastoja.

Lähetätkö tietoja IP-verkon yli?
Käytä TLS:ää.
Lue kuitenkin eteenpäin, jos haluat käyttää hauskoja kryptokirjastoja.

JavaScript-esimerkkejä

Viite: Node crypto.

Python Esimerkit

Viittaus: Python kryptokirjastot -Python hashlib -Python secrets

Java Esimerkit

.