#kryptografia

[liodiy]

Zapoznaj się z trzecim rządowym projektem kryptoustawy

Wprowadzenie Kryptologia jest dziedziną informatyki zajmującą się utrzywaniem poufności i integritetu danych. W ostatnich latach wiele krajów oraz przedsiębiorstw wpadło w napięcie związane z problemem cyberbezpieczeństwa, co prowadziło do intensywnej aktywności w dziedzinie ochrony informacji. Jeden z najważniejszych projektów w tej kategorii jest Money.pl – trzeci rządowy projekt…

Zapoznaj się z trzecim rządowym projektem kryptoustawy

[eksopolitiikka]

Perusalgebra salaisten koodien ja avaruusviestinnän taustalla

Perusalgebra salaisten koodien ja avaruusviestinnän taustalla

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:

1. Käyttämällä samoja x-koordinaatteja kuin alkuperäisessä esimerkissä saadaan pisteet (3, 33) ja (6, 57) ja siten yhtälöryhmä:

33 = 3A + B

57 = 6A + B

Vähentämällä ensimmäinen yhtälö toisesta saadaan 24 = 3A, joten A = 8. Kytkemällä A = 8 ensimmäiseen yhtälöön saadaan 33 = 24 + B, joten B = 9. Yksinkertainen aakkosellinen salaus kääntää viestin muotoon ”HI”.

2. Käyttämällä kahta erillistä x-koordinaattia generoimaan pisteet (x1, y1) ja (x2, y2), Art ja Zeke varmistavat, että systeemillä

y1 = Ax1 + B

y2 = Ax2 + B

on aina uniikki ratkaisu, joka voidaan löytää vähentämällä yhtälöt toisistaan. Esimerkiksi, vähentämällä ensimmäinen yhtälö toisesta aina eliminoi muuttujan B ja antaa ratkaisuksi A:lle:

y2 − y1 = Ax2 − Ax1

y2 − y1 = A(x2 − x1)

A=y2–y1x2–x1

Kun A on määritetty, se voidaan sijoittaa jompaan kumpaan alkuperäiseen yhtälöön

B=y1–x1(y2–y1x2–x1)

Tämä toimii aina, niin kauan kuin ei joudu jakamaan nollalla, joten x1 ja x2 ovat väkisin eri lukuja. Tämä on ensimmäinen askel sen osoittamiseen, että suuremmilla yhtälöryhmillä on oltava uniikki ratkaisu.

3. Kolme pistettä johtavat seuraavaan yhtälöryhmään:

(2, 90)                          90 = 4A + 2B + C

(5, 387)                        387 = 25A + 5B + C

(6, 534)                        534 = 36A + 6B + C

Ratkaisemalla yhtälöryhmä saadaan A = 12, B = 15, ja C = 12, eli “LOL” sen jälkeen kun numerot on tulkittu kirjaimina

4. Kyllä. Ensimmäiset kaksi pistettä ovat (1, 27) ja (3, 43). Yhtälöryhmällä

27 = A + B

43 = 3A + B

on ratkaisu A = 8 ja B = 19, mistä saadaan suora y = 8x + 19 ja salainen viesti on “HN.” Mutta huomaa, että kolmas piste ei osu suoralle, sillä 8 × 10 + 19 = 99, ei 90. Lisäpiste osoittautuu virheeksi.

Virheen korjaamiseksi suorita lineaarinen regressio pisteille (1, 27), (3, 43) ja (10, 90). Tästä saadaan suora, jonka kulmakerroin on erittäin lähellä  7:ää, mistä voidaan tulkita että A = 7. Käyttämällä A:lle tätä arvoa voidaan saada B:lle arvo 20, ja viesti voidaan tulkita olevan “GO.”

  Artikkelin julkaissut Quanta Magazine

https://eksopolitiikka.fi/tiede/perusalgebra-salaisten-koodien-ja-avaruusviestinnan-taustalla/?utm_source=TR&utm_medium=eksopolitiikka.tumblr.com&utm_campaign=SNAP%2Bfrom%2B_%7C+Eksopolitiikka.fi+%7C_

[davinci260]

Social Content Locker - wtyczka dla Bloggera odblokowująca dostęp do treści po udostępnieniu

http://dlvr.it/BfkL8C

[davinci260]

Jak zakodować treść posta na blogu?

http://dlvr.it/6KxgRk

[andrzejcybulski]

miniLock - Szyfrowanie w przeglądarce

miniLock – Szyfrowanie w przeglądarce

W czasach kiedy jesteśmy nadzorowani w internecie przez różne organy, a cyberprzestępcy także nie śpią, korzystanie z  szyfrowania stało się niemal obowiązkiem.

Ale szyfrowanie nie jest takie łatwe, czasami jest skomplikowane i utrudnia nam życie. Aby to zmienić, 23 letni Nadim Kobeissiz pochodzenia Libańczyk, postanowił dać nam proste rozwiązanie silnego szyfrowania w postaci dodatku do…

View On WordPress

[cyberbezpieczenstwo]

Nadciąga rewolucja w kryptografii

Cen­trum badaw­cze firmy IBM udostęp­niło na licen­cji GPL bibliotekę HElib służącą do szyfrowania homomor­ficz­nego – rewolucyj­nego spo­sobu zabez­pieczania zbiorów danych, który pozwala prze­prowadzać operacje bez­pośred­nio na szyfrogramach.