Semanttinen pysyvyys

Semanttisesti turvallinen kryptojärjestelmä kryptografiassa on salausjärjestelmä , joka ei salli alkuperäistä selkeää tekstiä koskevan merkityksellisen tiedon vuotamista salatekstistä . Otetaan mikä tahansa luokan PP todennäköisyysalgoritmi , jonka syötteenä ensimmäisessä tapauksessa on jonkin satunnaisen viestin salateksti ja tämän viestin pituus, ja toisessa tapauksessa vain viestin pituus. Jos ero todennäköisyyksien välillä saada jotain luotettavaa tietoa alkuperäisestä viestistä ensimmäisessä ja toisessa tapauksessa on mitätön, niin tämän salauksen tuottanutta kryptojärjestelmää pidetään semanttisesti turvallisena. [1] Laskennallisen monimutkaisuuden kannalta tämä käsite on analoginen täysin turvalliselle Shannon - salaukselle . Täydellisen suojattu salaus tarkoittaa, että alkuperäisestä viestistä ei saada lainkaan tietoa, kun taas semanttinen suojaus tarkoittaa, että mitään salakirjoituksesta löytyvää alkuperäistä viestiä koskevaa tietoa ei voida käyttää viestin minkään fragmentin salauksen purkamiseen. [2] [3] :378–381

Historia

Goldwasser ja Micali ottivat semanttisen vahvuuden käsitteen kryptografiaan vuonna 1982. [1] Heidän alun perin ehdottamansa määritelmä ei kuitenkaan antanut arviota todellisten kryptosysteemien vahvuudesta . Myöhemmin Goldwasser ja Micali osoittivat, että semanttinen suojaus vastaa salatekstin erottamattomuutta täsmäävien selkokielisten hyökkäysten yhteydessä . [4] Tämä semanttisen vahvuuden määritelmä on yleisempi, koska se auttaa arvioimaan käytettyjen kryptojärjestelmien vahvuutta.

Symmetrinen kryptografia

Symmetristen salausjärjestelmien tapauksessa vihollisen ei pitäisi pystyä oppimaan salatekstistä mitään tietoa selkeästä tekstistä. Tämä tarkoittaa, että vastustaja, jolla on kaksi selkeää tekstiä ja kaksi vastaavaa salatekstiä, ei voi määrittää tarkalleen, mikä salateksti vastaa mitäkin selvää tekstiä.

Julkisen avaimen salaus

Julkisen avaimen salausjärjestelmän sanotaan olevan semanttisesti turvallinen, jos salatekstin ja julkisen avaimen hallussa oleva vastustaja ei voi saada mitään merkityksellistä tietoa alkuperäisestä selkeästä tekstistä. Semanttinen suojaus ottaa huomioon vain passiiviset kryptohyökkäykset, esimerkiksi silloin, kun kryptoanalyytikko voi tarkkailla vain lähetettyjä salatekstejä ja generoida omia salatekstejään julkisella avaimella. Toisin kuin muut turvallisuuskäsitteet, semanttinen suojaus ei ota huomioon valittuja salatekstihyökkäyksiä , joissa kryptanalyytikko pystyy purkamaan joidenkin valittujen salatekstien salauksen, ja monet semanttisesti vahvat salausjärjestelmät ovat heikkoja tämäntyyppisiä hyökkäyksiä vastaan. Siksi semanttista vahvuutta ei voida pitää riittävänä edellytyksenä yleiskäyttöisen salausjärjestelmän vahvuudelle.

Salatekstin erottamattomuus hyökkäyksille, jotka perustuvat valittuun selkeään tekstiin, määritetään yleensä seuraavalla kokeella: [5]

  1. Satunnainen avainpari luodaan .
  2. Vastustajalle, polynomiselle aikarajalle, annetaan julkinen avain , jonka avulla hän voi luoda minkä tahansa määrän salatekstejä (polynomin aikarajojen sisällä).
  3. Vastustaja luo kaksi samanpituista viestiä ja lähettää ne lähettäjälle julkisen avaimen kanssa.
  4. Lähettäjä valitsee yhden viesteistä satunnaisesti, salaa sen vastaanotetulla julkisella avaimella ja lähettää tuloksena olevan salatekstin vastustajalle.

Tarkasteltavalla salausjärjestelmällä on salatekstin erottamattomuusominaisuus (ja siten se on semanttisesti vastustuskykyinen valituille selkokielisille hyökkäyksille), jos vastustaja ei pysty määrittämään kumman kahdesta viestistä lähettäjä valitsi huomattavasti suuremmalla todennäköisyydellä kuin (satunnaisen arvauksen todennäköisyys) .

Koska vastustajalla on julkinen avain, semanttisesti turvallisen järjestelmän on määritelmänsä mukaan oltava todennäköisyyspohjainen, eli sillä on oltava satunnainen komponentti. Muussa tapauksessa vastustaja voi julkista avainta käyttämällä yksinkertaisesti laskea viestien salatekstit ja verrata niitä palautettuun salatekstiin ja määrittää onnistuneesti lähettäjän valinnan.

Esimerkkejä semanttisesti turvallisista algoritmeista ovat Goldwasser-Micali-salausjärjestelmä , ElGamal -malli ja Peye-salausjärjestelmä . Näitä järjestelmiä pidetään todistetusti turvallisina , koska kussakin tapauksessa semanttisen turvallisuuden todiste voidaan pelkistää vaikeaksi matemaattiseksi ongelmaksi. Semanttisesti herkät algoritmit, kuten RSA , voidaan tehdä semanttisesti turvallisiksi täytemenetelmillä (esim . OAEP ).

Muistiinpanot

  1. ↑ 1 2 S. Goldwasser ja S. Micali , Todennäköisyyspohjainen salaus & kuinka pelata mentaalista pokeria salassa pitäen kaikki osatiedot Arkistoitu 31. maaliskuuta 2020 Wayback Machinessa , Annual ACM Symposium on Theory of Computing, 1982.
  2. ↑ Shannon, Claude. Salassapitojärjestelmien viestintäteoria  // Bell System Technical  Journal : päiväkirja. - 1949. - Voi. 28 , ei. 4 . - s. 656-715 . - doi : 10.1002/j.1538-7305.1949.tb00928.x .
  3. ↑ Goldreich, Oded. Kryptografian perusteet: Osa 2, Perussovellukset. Voi. 2. Cambridge University Press, 2004.
  4. ↑ S. Goldwasser ja S. Micali , Probabilistinen salaus . Journal of Computer and System Sciences, 28:270-299, 1984.
  5. ↑ Katz, Jonathan; Lindell, Yehuda. Johdatus nykyaikaiseen kryptografiaan : periaatteet ja protokollat  . — Chapman and Hall/CRC, 2007. Arkistoitu 8. maaliskuuta 2017 Wayback Machinessa