Avainsana-arkisto: kryptografia

Tiede

Perusalgebra salaisten koodien ja avaruusviestinnän taustalla

Kommentoi

Avaruustutkimus vaatii valtavaa tarkkuutta. Kun Marsiin laskeudutaan 70 miljoonan kilometrin päähän lähimmästä huoltoasemasta, tehokkuus on maksimoitava ja varauduttava odottamattomiin tilanteisiin. Tämä koskee kaikkea avaruusaluksen suunnittelusta tiedonsiirtoon: Maahan tasaisena nollien ja ykkösten virtana palaavissa viesteissä on väistämättä virheitä, joten ne on pystyttävä tunnistamaan ja korjaamaan tuhlaamatta arvokasta aikaa ja energiaa.

Tässä kohtaa matematiikka tulee kuvaan mukaan. Matemaatikot ovat keksineet nerokkaita tapoja siirtää ja tallentaa tietoa. Yksi yllättävän tehokas menetelmä on Reed-Solomon-koodit, jotka perustuvat samaan perusalgebraan, jota oppilaat oppivat koulussa. Pistäydytään matematiikan tunnilla katsomassa, miten Reed-Solomon-koodit auttavat tiedon siirtämisessä ja suojaamisessa ja korjaavat samalla esiin tulevat kalliit virheet.

Kaksi oppilasta, Art ja Zeke, vaihtavat salaisia viestejä neiti Al-Jabrin matematiikan tunnilla. Art avaa Zeken viimeisimmän viestin ja saa selville luvut 57 ja 99. Hän tietää, että hänen on annettava x-koordinaatit 3 ja 6, jotta saadaan aikaan pisteet (3, 57) ja (6, 99). Art liittää molemmat pisteet lineaariseen yhtälöön y = Ax + B ja saa tulokseksi seuraavan yhtälösysteemin:

57 = 3A + B

99 = 6A + B

Viestin purkamiseksi Artin on ratkaistava A ja B. Hän aloittaa vähentämällä ensimmäisen yhtälön toisesta yhtälöstä:

   99 = 6A + B −  (57 = 3A + B) =   42 = 3A

Tämä eliminoi B:n. Jakamalla tämän uuden yhtälön molemmat puolet 3:lla saadaan A = 14. Kun tämä sijoitetaan takaisin ensimmäiseen yhtälöön 57 = 3 × 14 + B, saadaan B = 15.

Art tietää nyt, että pisteiden (3, 57) ja (6, 99) kautta kulkevaa suoraa kuvaa yhtälö y = 14x + 15. Mutta hän tietää myös, että Reed-Solomon-koodissa salainen viesti on piilotettu kertoimiin. Hän purkaa Zeken viestin käyttämällä heidän sopimaansa yksinkertaista aakkossalakirjoitusta: 14 on ”N” ja 15 on ”O”, mikä kertoo Artille, että Zeke ei voi pelata videopelejä tänään koulun jälkeen.

Tämän yksinkertaisen Reed-Solomon-koodin salaisuus perustuu kahteen geometriseen perustietoon. Ensinnäkin minkä tahansa kahden pisteen kautta kulkee yksikäsitteinen viiva. Toiseksi, kertoimien A ja B tapauksessa jokainen (ei-kohtisuora) suora voidaan kirjoittaa muodossa y = Ax + B. Yhdessä nämä kaksi tosiasiaa takaavat, että jos tiedät kaksi pistettä suoralla, voit löytää A:n ja B:n, ja jos tiedät A:n ja B:n, tiedät kaikki suoran pisteet. Lyhyesti sanottuna, jommankumman tiedon hallussapito vastaa suoran tuntemista.

Reed-Solomon-koodit hyödyntävät näitä ekvivalentteja informaatiojoukkoja. Salainen viesti koodataan kertoimina A ja B, ja viivan pisteet jaetaan osiin, joista osa lähetetään julkisesti ja osa pidetään salassa. Viestin purkaminen tapahtuu keräämällä palat yhteen ja kokoamalla ne uudelleen. Tämä vaatii vain yksinkertaista algebraa.

Zeken palaset olivat numerot 57 ja 99, jotka hän lähetti Artille. Nämä numerot ovat viestin julkinen osa. Art yhdisti ne omiin palasiinsa 3 ja 6, jotta saatiin muodostettua pisteet (3, 57) ja (6, 99). Tässä tapauksessa numerot 3 ja 6 muodostavat viestin yksityisen osan, josta Art ja Zeke sopivat etukäteen.

Nämä kaksi pistettä sijaitsevat suoralla, ja viestin purkamiseksi sinun tarvitsee vain löytää suoran yhtälö. Kummankin pisteen liittäminen yhtälöön y = Ax + B antaa sinulle kahden yhtälön järjestelmän suoralle, joiden molempien on oltava todellisia. Nyt strategia on suoraviivainen: Ratkaise systeemi, määritä suora ja pura viesti.

Algebran tunnilla olet luultavasti oppinut monia yhtälöryhmien ratkaisumenetelmiä, kuten kuvaajien käyttöä, arvaamista ja tarkistamista sekä sijoittamista. Art käytti eliminointia, menetelmää, jossa yhtälöitä käsitellään algebrallisesti muuttujien poistamiseksi yksi kerrallaan. Joka kerta, kun eliminoit muuttujan, järjestelmä on hieman helpompi ratkaista.

Kuten muissakin salausmenetelmissä, viestien turvallisuus perustuu julkisten ja yksityisten tietojen älykkääseen yhdistämiseen. Zeke voisi huutaa numerot 57 ja 99 luokkahuoneessa, eikä se vaarantaisi hänen Artille lähettämänsä viestin turvallisuutta (tosin hän saattaisi joutua vaikeuksiin neiti Al-Jabrin kanssa). Tämä johtuu siitä, että ilman vastaavaa yksityistä tietoa  (x-koordinaatteja 3 ja 6) on mahdotonta tunnistaa suoran yhtälöä. Niin kauan kuin he pitävät nämä arvot omana tietonaan, he voivat turvallisesti välittää salaiset viestinsä julkisesti.

Viiva y = 14x + 15 sopii hyvin kaksikirjaimisen sanan ”no” välittämiseen, mutta entä jos oppilaat haluavat jakaa pidemmän salaisuuden? Tässä kohtaa algebran, geometrian ja lineaaristen yhtälöryhmien koko teho astuu kuvaan.

Oletetaan, että Zeke haluaa tietää, miten Art uskoo pärjäävänsä huomisessa englannin kokeessa. Art muuntaa kolmen kirjaimen vastauksensa numeroiksi 14, 59 ja 82 ja antaa ne Zekelle. Opiskelijat sopivat etukäteen, että käytettäessä Reed-Solomon-koodeja, joiden pituus on 3, heidän yksityiset numeronsa ovat 2, 5 ja 6, joten Zeke kokoaa palaset yhteen ja muodostaa kohdat (2, 14), (5, 59) ja (6, 82).

Mikään lineaarinen funktio ei kulje näiden kolmen pisteen kautta. Mutta on olemassa ainutlaatuinen toisen asteen funktio, joka kulkee. Ja koska jokainen toisen asteen funktio voidaan kirjoittaa muodossa y = Ax2 + Bx + C, voidaan soveltaa samaa yleistä menetelmää. Ainoa ero on järjestelmän koko.

Kunkin pisteen liittäminen yhtälöön y = Ax2 + Bx + C antaa yhden yhtälön, joten kolme pistettä tuottaa seuraavan kolmen yhtälön järjestelmän:

(2, 14):            14 = 4A + 2B + C

(5, 59):            59 = 25A + 5B + C

(6, 82):            82 = 36A + 6B + C

Kolmen yhtälön järjestelmä, jossa on kolme tuntematonta, vaatii hieman enemmän työtä ratkaistavaksi kuin kahden yhtälön järjestelmä, jossa on kaksi tuntematonta, mutta tavoite on sama: Yhdistä yhtälöpareja taitavasti muuttujien poistamiseksi.

Jos esimerkiksi vähennät ensimmäisen yhtälön toisesta, saat uuden yhtälön 45 = 21A + 3B. Vastaavasti jos vähennät toisen yhtälön kolmannesta, saat 23 = 11A + B. Nämä algebralliset käsittelyt tuottavat uuden järjestelmän:

45 = 21A + 3B

23 = 11A + B

Nyt sinulla on ”kaksi kertaa kaksi” -järjestelmä: kaksi yhtälöä ja kaksi tuntematonta. Voit ratkaista sen kertomalla toisen yhtälön luvulla -3 ja lisäämällä sen ensimmäiseen yhtälöön:

       45 =   21A + 3B +   (-69 = -33A − 3B) =     -24 = -12A

Huomaa, miten toistuva poistaminen on muuttanut alkuperäisen kolmen yhtälön järjestelmän yhdeksi yhtälöksi, joka on helppo ratkaista: A = 2. Takaperin työskennellen voit liittää A = 2 yhteen kaksi kertaa kaksi -järjestelmän yhtälöistä ja löytää B = 1. Liitä sitten molemmat arvot yhteen alkuperäisistä yhtälöistä ja saat C = 4. Kun Zeke on käyttänyt yksinkertaista aakkoslukua 2:een, 1:een ja 4:ään, hän tietää, että Art saa huomisen englannin kokeessa huonon tuloksen. Ainakin hän saa paljon algebraharjoitusta.

Polynomifunktioita koskevan erityisen tosiasian ansiosta voit lähettää minkä tahansa pituisen viestin Reed-Solomon-koodeilla. Avain on tämä: Kun tasossa on n pistettä, joilla on eri x-koordinaatit, on olemassa yksikäsitteinen polynomi, jonka ”aste” on n-1 ja joka kulkee niiden kautta. Polynomin aste on muuttujan suurin potenssi lausekkeessa, joten toisen asteen funktiolla, kuten y = Ax2 + Bx + C, on aste 2, koska x:n suurin potenssi on 2. Lineaarisella funktiolla on aste 1, koska yhtälössä y = Ax + B x:n suurin potenssi on yksi.

Ensimmäisessä esimerkissä käytimme sitä tosiasiaa, että kaksi pistettä määrittää yhden lineaarisen eli 1. asteen polynomin. Toisessa esimerkissä käytimme apuna sitä, että kolme pistettä määrittää yksikäsitteisen 2. asteen eli kvadraattisen polynomin. Ja jos haluat lähettää viestin, jonka pituus on 10, voit koodata viestin 9-asteisen polynomifunktion 10:nä kertoimena. Kun sinulla on funktio, laske 10 julkista y-arvoa arvioimalla funktio aiemmin sovituilla 10 yksityisellä x-arvolla. Kun olet tehnyt tämän, voit turvallisesti välittää nämä y-koordinaatit julkisesti vastaanottajan purettavaksi. Käytännössä Reed-Solomon-koodit ovat hieman monimutkaisempia kuin tämä, ja niissä käytetään monimutkaisempia kertoimia ja käännösjärjestelmiä, mutta perusajatus on sama.

Sen lisäksi, että Reed-Solomon-koodit pitävät viestisi turvallisena, ne tarjoavat myös yksinkertaisia ja tehokkaita tapoja virheiden havaitsemiseen ja jopa korjaamiseen. Tämä on tärkeää aina, kun tietoja siirretään tai tallennetaan, sillä on aina mahdollista, että osa tiedoista katoaa tai korruptoituu.

Yksi ratkaisu tähän ongelmaan olisi yksinkertaisesti lähettää ylimääräisiä kopioita tiedoista. Zeke voi esimerkiksi lähettää viestin [14, 14, 14, 14, 15, 15, 15] eikä [14, 15]. Kunhan Art tietää, että jokainen viestin osa on lähetetty kolminkertaisena, hän voi purkaa viestin ja tarkistaa, onko siinä virheitä. Jos hän löytää virheitä, hänellä on itse asiassa hyvät mahdollisuudet korjata ne. Jos Art saa viestin [14, 14, 24, 15, 15, 15], se, että kolme ensimmäistä numeroa ovat erilaisia, varoittaa häntä virheestä, ja koska kaksi numeroa on 14, hän voi arvata, että myös 24:n pitäisi todennäköisesti olla 14. Sen sijaan, että Art pyytäisi lähettämään viestin uudelleen, hän voi jatkaa dekoodausta. Tämä on tehokas mutta kallis strategia. Mitä aikaa, energiaa ja vaivaa tarvitaan n tiedon lähettämiseen, sitä tarvitaan kolme kertaa enemmän.

Reed-Solomon-koodien taustalla oleva matematiikka tarjoaa kuitenkin tehokkaan vaihtoehdon. Sen sijaan, että lähetät useita kopioita jokaisesta datasta, voit lähettää vain yhden ylimääräisen pisteen! Jos tämä ylimääräinen piste sopii polynomiin, tieto on oikea. Jos se ei sovi, on tapahtunut virhe.

Jotta näet, miten tämä toimii, oletetaan, että haluat tarkistaa viestin ”NO” ensimmäisessä esimerkissä. Zeke voi vain lähettää ylimääräisen y-koordinaatin 155. Olettaen, että hän ja Art sopivat etukäteen kolmannesta yksityisestä x-koordinaatista, vaikkapa x = 10, Art voi tarkistaa tämän kolmannen pisteen purkamaansa viivaan. Kun hän liittää x = 10 yhtälöön y = 14x + 15 ja näkee, että tulos on 155, hän tietää, ettei lähetyksessä ollut virheitä.

Tämä ei toimi vain linjojen kohdalla. Jotta Zeke voisi tarkistaa ”BAD” toisessa esimerkissä, Art voi lähettää y = 25. Jos he ovat sopineet, että 3 on ylimääräinen yksityinen x-koordinaatti, Zeke voi liittää x = 3 kvadraattifunktioonsa y = 2×2 + x + 4 ja tarkistaa, että piste (3, 25) sopii, ja vahvistaa jälleen virheettömän lähetyksen vain yhdellä pisteellä.

Ja tuo lisäpiste voi mahdollisesti korjata myös virheitä. Jos virhe havaitaan eikä vastaanottaja pysty rakentamaan viestin sisältävää polynomifunktiota, hän voi sen sijaan rakentaa ”parhaiten sopivan” polynomin regressiotekniikoiden avulla. Kuten tilastotieteen tunnilla käytetty parhaan sovituksen viiva, tämä on se polynomifunktio, joka matemaattisesti määritetään sopivimmaksi annettuihin pisteisiin, vaikka se ei kulkisi kaikkien pisteiden läpi. Viestin rakenteesta ja lähetetyn lisätiedon määrästä riippuen tämä parhaiten sopiva polynomi voi auttaa rekonstruoimaan oikean polynomin — ja siten oikean viestin — jopa virheellisistä tiedoista.

Tämä tehokkuus viestinnän lähettämisessä ja korjaamisessa selittää, miksi NASA on käyttänyt Reed-Solomon-koodeja kuuhun ja Marsiin suuntautuvissa lennoillaan. Ja se antaa sinulle pohdittavaa, kun ratkaiset seuraavaa yhtälösysteemiäsi. Kun arvaat, tarkistat tai poistat ratkaisun, ajattele Reed-Solomon-koodien voimaa ja eleganssia sekä kaikkia salaisuuksia, joita järjestelmäsi saattaa paljastaa.

Harjoitustehtäviä

1. Käyttäen samaa salausta kuin ylempänä, Art lähettää julkiset numerot 33 ja 57 Zeken tulkittavaksi. Mikä on viesti?

2. Kuinka Art ja Zeke voivat olla varmoja siitä, että heidän yksityisistä luvuistaan ​​x = 3 ja x = 6 johtuvalla yhtälöryhmällä on aina ratkaisu?

3. Vastauksena Artin ”BAD”-viestiin englannin kokeesta Zeke lähettää takaisin [90, 387, 534]. Olettaen, että he käyttävät samaa salausta kuin ylempänä, mikä on hänen viestinsä?

4. Lola lähettää sinulle kaksikirjaimisen viestin ja yhden virheentarkistusnumeron käyttäen Reed-Solomon-koodia ja samaa yksinkertaista aakkosnumeerista koodia, jota Art ja Zeke käyttävät. Olette salaa sopineet x-koordinaatit 1, 3 ja 10 etukäteen, ja Lola lähettää julkiset numerot [27, 43, 90]. Sisältääkö viesti virheen?

Vastaukset:

Lue loppuun →

Tiede

Näin toimii kvanttikryptografia

Kommentoi

Vuonna 1994 tietojenkäsittelytieteilijä Peter Shor keksi että jos kvanttitietokone keksittäisiin, ne kykenisivät hajottamaan ison osan siitä infrastruktuurista, jota käytetään suojelemaan verkossa jaettua tietoa. Tuo pelottava mahdollisuus on saanut tutkijat rämpien tuottamaan uudenlaisia “kvanttien jälkeisiä” kryptausmenetelmiä, jotta pelastettaisiin informaatiota niin paljon kuin mahdollista ennen niiden päätymistä kvanttihakkereille.

Aiemmin vuonna 2022 National Institute of Standards and Technology kertoi neljästä finalistista sen post-kvanttikryptografiastandardille. Kolme niistä käyttää “hilakryptografiaa” — menetelmää, joka on saanut inspiraatiota hiloista, avaruuden säännönmukaisista pisterakenteista.

Hilakryptografia ja muut kvanttien jälkeiset mahdollisuudet eroavat nykyisistä standardeista monin tavoin. Mutta ne kaikki nojaavat matemaattiseen asymmetriaan. Nykyisten kryptografisten järjestelmien tarjoama turva perustuu kertolaskuun ja tekijähajotelmaan: mikä tahansa tietokone voi nopeasti kertoa yhteen kaksi lukua, mutta voi kestää vuosisatoja selvittää kryptografisesti suuren luvun alkulukutekijät. Tuo asymmetria tekee salaisuuksista helpon koodata, mutta vaikeaa purkaa.

Shor sai selville algoritmistaan, että tekijähajotelma tekee algoritmista haavoittuvaisen kvanttitietokoneiden hyökkäykselle.  “Se on erittäin tietty, erikoinen juttu jonka kvanttitietokoneet osaavat tehdä”, sanoo Katherine Stange,  Coloradon yliopiston matemaatikko Boulderissa. Shorin jälkeen kryptograafikoilla oli uusi homma: etsi uusi matemaattisten operaatioiden joukko, joita on helppo käyttää mutta lähes mahdoton purkaa.

Hilakryptografia on eräs tähänastisista kaikkein menestyksekkäimmistä. Alunperin se on kehitetty 1990-luvulla. Se nojaa pisteiden summien takaisinmallintamisen vaikeuteen.

Tässä on eräs tapa kuvata hilakryptografiaa: kuvittele, että ystävälläsi on hila, joka siis on pelkkä kuvion muodostava toistuvien pisteiden joukko tasolla. Ystäväsi haluaa nimetä 10 näistä pisteistä. Mutta hän on vastarannankiiski, ja ei piirrä koko hilaa. Sen sijaan hän mainitsee vain kaksi pistettä — ensimmäinen, jonka x-koordinaatti on 101 ja y-koordinaatti 19, ja toinen piste koordinaateissa [235, 44].

Onneksi hilalta on helppoa löytää uusia pisteitä, koska kun lisäät ja vähennät kaksi hilapistettä, saat kolmannen pisteen samasta hilasta. Eli tarvitsee vain summata pisteet yhteen, tai kertoa niitä jollain kokonaisluvulla ja summata, tai jokin näiden kombinaatio. Tämän kun tekee kahdeksalla eri tavalla, voit vastata ystäväsi kysymykseen.

Mutta ystäväsi ei ole tyytyväinen. Hän antaa sinulle samat kaksi alkupistettä ja sitten pyytää etsimään pisteen lähellä origoa [0, 0] samasta hilasta. Tähän kysymykseen vastaamiseksi tarvitsee löytää pisteiden [101, 19] ja [235, 44] kombinaatio, jolla päästään lähelle pistettä [0, 0]. Tämä ongelma on paljon vaikeampi kuin ensimmäinen, ja todennäköisesti päädyt vain arvailemaan päästäksesi lähelle vastausta. Tällainen asymmetria on hilakryptografian taustalla.

Jos oikeasti haluat käyttää hilakryptografiaa informaation jakamiseen, se tapahtuisi seuraavalla tavalla. Kuvittele, että ystävä (läheisempi!) haluaa lähettää sinulle turvallisen viestin. Aloitat lukujen neliömäisellä hilalla. Oletetaan, että siinä on kaksi riviä ja kaksi saraketta:

Nyt keksit yksityisen “avaimen”, jonka vain sinä tiedät. Tässä esimerkissä oletamme, että yksityinen avain on kaksi salaista lukua: 3 ja  −2. Kerrot ensimmäisen sarakkeen numerot 3:lla ja jälkimmäisen -2:lla. Summaat tulokset yhteen ja saat kolmannen sarakkeen, jossa on kaksi lukua.

Laitat tämän uuden sarakkeen oman hilasi laidalle. Tämä kolmas sarake on julkinen avaimesi. Tätä voit levitellä vapaasti!

(Oikean elämän skenaario olisi monimutkaisempi. Jotta voisit pitää hakkerit loitolla dekoodaamasta yksityistä avainta, tähän pitää lisätä hieman satunnaiskohinaa viimeiseen sarakkeeseen. Mutta tässä sivuutamme sen yksinkertaisuuden vuoksi.)

Nyt ystäväsi käyttää julkista avainta lähettämään sinulle viestin. Hän keksii itselleen omat salaiset numerot: 2 ja 0. Hän kertoo ensimmäisen rivin luvut 2:lla ja jälkimmäisen 0:lla. Sitten hän summaa tuloksen yhteen ja saa kolmannen rivin.

Nyt hän liittää uuden rivin hilan alle ja lähettää sen takaisin sinulle. (Todellisessa systeemissä taaskin pitäisi lisätä kohinaa.)

Nyt voit lukea viestin. Katso ensin onko ystäväsi alin rivi oikein. Sovella omaa salaista avaintasi rivin kahteen ensimmäiseen lukuun. Tulokseksi pitäisi tulla viimeinen luku.

Ystäväsi voi myös valita lähettää sinulle rivin ja väärän luvun viimeisessä sarakkeessa. Hän tietää, että tämä numero ei sovi laskelmiin.

Jos ystäväsi lähettää rivin, jossa viimeinen luku on oikein, voit tulkita tämän nollaksi. Jos hän lähettää rivin joka on väärin, voit tulkita sen ykköseksi. Rivi tällä tavoin koodaa yksittäisen bitin: joko 0 tai 1.

Ulkopuolinen hyökkääjä ei pääse käsiksi joko yksityiseen avaimeesi tai ystäväsi yksityiseen avaimeen. Ilman niitä hyökkääjällä ei ole ideaa siitä onko loppuluku oikein vaiko ei.

Käytännössä viestit ovat pidempiä kuin yhden bitin mittaisia. Joten ihmiset generoivat esim. 100 uutta saraketta yhden sijaan. Sitten viestin lähettäjä luo yksittäisen uuden rivin ja näin yksi rivi koodaa joko ykkösen tai nollan jokaisella rivin sarakkeella.

Jos hilakryptografia toteutettaisiin oikeasti, siihen liittyy lukemattomia pikkujuttuja joita tässä skenaariossa ei käsitelty. Esimerkiksi, jos haluat viestin olevan oikeasti salassa muilta, matriisissa pitää olla uskomattoman paljon lukuja, mikä tekee koko hommasta niin sekavaa ettei sitä voi käyttää. Tämän kiertämiseksi tutkijat käyttävät matriiseja, joilla on käyttökelposia symmetrioita, jotka voivat pienentää parametrien lukumäärää. Tuon lisäksi on kokonainen kokoelma erilaisia säätöjä, joita voidaan soveltaa itse ongelmaan ja siihen tapaan millä virheitä käsitellään, sekä muuta.

Tottakai aina on mahdollista, että joku löytää virheen hilakryptografiassa, niinkuin Shor tekijöiksi hajottamisessa. Mitään varmuutta ei ole siitä, että jokin tietty kryptograafinen menetelmäi toimii mahdollisen hyökkäyksen iskiessä. Kryptografia toimii niin kauan kunnes se rikotaan. Aiemmin eräs lupaava kvanttien jälkeinen kryptografiamenetelmä murrettiin, eikä siihen käytetty edes kvanttitietokonetta vaan ihan tavallista läppäriä.Stangelle koko projekti on paradoksi: “Se mitä pidän kryptografiassa kiehtovana on, että me olemme rakentaneet tämmöisen infrastruktuurin ihmisrodulle siinä uskossa, että ihmiset olisivat rajoitteellisia”, hän sanoo. “Se on niin nurinkurista.”

 

Artikkelin julkaissut Quanta Magazine