Rabinin salausjärjestelmä
Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 17. elokuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .Rabinin salausjärjestelmä on julkisen avaimen salausjärjestelmä, jonka turvallisuuden takaa vaikeus löytää neliöjuuria jäännösrenkaasta modulo yhdistelmälukua . Järjestelmän turvallisuus, kuten RSA -menetelmän turvallisuus , johtuu suurten lukujen huomioon ottamista vaikeudesta. Salatun viestin salaus voidaan purkaa neljällä tavalla. Järjestelmän haittana on tarve valita oikea viesti neljästä mahdollisesta.
Historia
Tammikuussa 1979 Michael O. Rabin julkaisi kuvauksen järjestelmästään. On todistettu, että selkeän tekstin palauttaminen salatekstistä on yhtä vaikeaa kuin suurten lukujen laskeminen huomioon . Rabinin järjestelmästä tuli ensimmäinen epäsymmetrinen salausjärjestelmä, jolle tällainen todistus suoritettiin. Palautuksen monimutkaisuus liittyy vaikeuteen erottaa neliöjuuren modulo yhdistelmäluku N = p · q . Tekijöintitehtävä ja neliöjuuriongelma ovat ekvivalentteja, eli:
- kun tiedät luvun N alkujakajat , voit erottaa neliöjuuret modulo N ;
- tietäen kuinka erottaa neliöjuuret modulo N , voidaan kertoa N alkutekijöiksi.
Avaimen luominen
Rabin-järjestelmä, kuten mikä tahansa epäsymmetrinen salausjärjestelmä , käyttää julkista ja yksityistä avainta. Julkista avainta käytetään viestien salaamiseen ja se voidaan luovuttaa yleisölle. Yksityistä avainta tarvitaan salauksen purkamiseen, ja sen pitäisi olla vain salattujen viestien vastaanottajien tiedossa.
Avainten luontiprosessi on seuraava:
- kaksi satunnaislukua p ja q valitaan ottaen huomioon seuraavat vaatimukset:
- numeroiden on oltava suuria (katso bitin syvyys );
- lukujen on oltava alkulukuja ;
- seuraavan ehdon on täytyttävä: p ≡ q ≡ 3 mod 4 .
- lasketaan luku n = p · q ;
- numero n on julkinen avain; luvut p ja q ovat suljettuja.
Esimerkki. Olkoon p = 7 ja q = 11 . Silloin n = p · q = 7 · 11 = 77 . Luku n = 77 on julkinen avain ja luvut p = 7 ja q = 11 ovat yksityinen avain. Vastaanottaja kertoo lähettäjille numeron 77. Lähettäjät salaavat viestin numerolla 77 ja lähettävät sen vastaanottajalle. Vastaanottaja purkaa viestin salauksen numeroilla 7 ja 11. Annetut avaimet ovat huonoja käytännön käyttöön, koska numero 77 hajoaa helposti alkutekijöiksi (7 ja 11).
Salaus
Alkuperäinen viesti m (teksti) salataan julkisella avaimella - numerolla n seuraavan kaavan mukaan:
c = m² mod n .Modulokertoimen käytöstä johtuen Rabin-järjestelmän salausnopeus on suurempi kuin RSA -menetelmän salausnopeus , vaikka jälkimmäisessä tapauksessa valitaan pieni eksponenttiarvo.
Esimerkki (jatkuu). Olkoon lähdeteksti m = 20 . Tällöin salateksti olisi: c = m² mod n = 20² mod 77 = 400 mod 77 = 15 .
Salauksen purku
Viestin salauksen purkamiseen tarvitset yksityisen avaimen - numerot p ja q . Salauksen purkuprosessi on seuraava:
- ensinnäkin Euklidisen algoritmin avulla luvut ja löytyvät yhtälöstä ;
- Sitten lasketaan kiinalaisen jäännöslauseen avulla neljä numeroa:
Esimerkki (loppu). Dekoodauksen tuloksena saamme: . Näemme, että yksi juurista on alkuperäinen teksti m .
Algoritmin arviointi
Tehokkuus
Tekstin purkaminen johtaa oikean tekstin lisäksi kolmeen väärään tulokseen. Tämä on Rabinin salausjärjestelmän suurin haitta ja yksi niistä tekijöistä, jotka estivät sitä löytämästä laajaa käytännön käyttöä.
Jos lähdeteksti on tekstiviesti, oikean tekstin määrittäminen ei ole vaikeaa. Kuitenkin, jos viesti on satunnaisten bittien virta (esimerkiksi avainten tai digitaalisen allekirjoituksen luomiseksi ), oikean tekstin määrittämisestä tulee todellinen ongelma. Yksi tapa ratkaista tämä ongelma on lisätä viestiin tunnettu otsikko tai jonkinlainen nimike ennen salausta.
Laskentanopeus
Rabin-algoritmi on samanlainen kuin RSA-koodaus, mutta sen sijaan, että viesti nostetaan tehoon e , salaus käyttää sanomalohkon neliöintitoimintoa, mikä vaikuttaa suotuisasti algoritmin nopeuteen tinkimättä salauksen vahvuudesta.
Dekoodaukseen sovelletaan kiinalaista jäännöslausetta sekä kahta modulo- eksponentiota. Tässä tehokkuus on verrattavissa RSA:han.
Halutun tekstin valitseminen neljästä lisää laskentakustannuksia. Ja tämä varmisti, että Rabinin salausjärjestelmä ei saanut laajaa käytännön käyttöä.
Turvallisuus
Rabinin salausjärjestelmän suuri etu on se, että satunnainen teksti voidaan palauttaa kokonaan salatekstistä vain, jos salauksen purkaja pystyy ottamaan tehokkaasti huomioon julkisen avaimen n.
Rabinin salausjärjestelmä on todistetusti vastustuskykyinen kaikki tai ei mitään -hyökkäykselle, joka perustuu valittuun salakirjoitushyökkäykseen, jos ja vain, jos kokonaisluvun sisällyttäminen alkutekijöihin on vaikeasti ratkaistavissa.
Kaikki tai ei mitään -suojaus tarkoittaa, että tietyllä algoritmilla salattua tekstiä hyökkääjän on palautettava lohko alkuperäisestä tekstistä, jonka koon yleensä määrää salausjärjestelmän suojausparametri. Alkuperäinen ja salateksti huomioon ottaen hyökkääjän on palautettava koko yksityisen avaimen lohko . Tässä tapauksessa hyökkääjä joko saavuttaa täydellisen menestyksen tai ei saa mitään. Sana "ei mitään" tarkoittaa, että hyökkääjällä ei ole salaisia tietoja ennen epäonnistunutta hyökkäystä tai sen jälkeen.
Rabinin salausjärjestelmä on täysin puolustuskyvytön valittuun salatekstiin perustuvia hyökkäyksiä vastaan . Pääsääntöisesti hyökkääjä käyttää kaikkia mahdollisuuksiaan. Hän ottaa yhteyttä hyökkäyksen kohteena olevaan käyttäjään, lähettää hänelle salatekstin myöhempää salauksen purkamista varten ja vaatii alkuperäisen tekstin palauttamista.
Esimerkiksi redundanssin lisääminen, kuten viimeisten 64 bitin toistaminen, voi tehdä juurista ainutlaatuisen. Salauksenpurkualgoritmi tässä tapauksessa tuottaa yhden juuren, jonka hyökkääjä jo tietää.
Prosessi on lisäksi haavoittuvainen, koska koodauksessa käytetään vain neliömäisiä jäännöksiä. Esimerkissä, jossa n = 77, käytetään vain 23:ta 76 mahdollisesta tilasta.
Katso myös
Kirjallisuus
- Mao V. Salaus - epäsymmetriset menetelmät // Moderni kryptografia : Teoria ja käytäntö / käänn. D. A. Klyushina - M .: Williams , 2005. - 768 s. — ISBN 978-5-8459-0847-6
- Schneier B. Sovellettu kryptografia. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi julkaisussa C. - M. : Triumph, 2002. - 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .