Rabinin kryptosysteemi

Kryptosysteemi Rabinin on epäsymmetrinen salakirjoitusjärjestelmä , joka perustuu vaikeus ongelma factoring (kuten RSA ). Se keksittiin vuonna 1979 , jonka Michael Rabin  : se on ensimmäinen epäsymmetrinen kryptosysteemi joiden turvallisuus on vähennetty laskennallisen vaikeus tekijöihin kokonaisluku .

Rabinin kryptosysteemillä on se etu, että sillä on todiste vaikeuksista yhtä suuri kuin kokonaislukujen jakaminen, todiste, jota ei vielä ole olemassa RSA: lle. Toisaalta sillä on epädeterminismistä johtuva haitta: kryptosysteemissä olevan toiminnon tuottama lähtö voi olla seurausta neljästä erillisestä panoksesta. Siksi on tarpeen määrittää, mikä merkintä on oikea lisämekanismilla.

Avainten luominen

Kuten kaikissa epäsymmetrisissä salausalgoritmeissa, Rabinin kryptojärjestelmä käyttää julkista avainta ja yksityistä avainta . Julkista avainta käytetään salaamiseen, eikä se ole salaa, kun taas yksityinen avain on salaisuus, ja sen pitäisi olla tiedossa vain sen omistajalle: viestin vastaanottajalle (jotta vain hän voi purkaa salauksen).

Avainten luominen on nimenomaan seuraava:

• Valitse satunnaisesti kaksi isoa alkulukua , p ja q . (Laskelmien yksinkertaistamiseksi voimme valita ne siten, että p ≡ q ≡ 3 (mod 4).)
• Olkoon n = p * q , mikä tekee n: stä julkisen avaimen. Pääluvut p ja q muodostavat yksityisen avaimen.

Salaus edellyttää vain julkista avainta n . Selvittämiseksi tarvitaan tekijöitä n , p ja q .

Tässä on esimerkki, joka toisaalta ei käytä tarpeeksi suuria parametreja turvallisuuden takaamiseksi todellisessa maailmassa: Jos ja niin . Tämä on tietysti huono avainvalinta, koska on merkityksetöntä laskea luku 77. s=7{\ displaystyle p = 7}q=11{\ displaystyle q = 11}ei=77{\ displaystyle n = 77}

Salaus

Salaukseen käytetään vain julkista avainta n . Salausteksti tuotetaan selväkielisestä m : stä seuraavasti.

Antaa olla tilaa mahdollisten selkeiden tekstien (kaikki numerot) ja olkaamme olla selkeä teksti. Salausteksti määritetään seuraavasti: P={0,...,ei-1}{\ displaystyle P = \ {0, ..., n-1 \}}m∈P{\ displaystyle m \ in P}vs.{\ displaystyle c}

vs.=m2modei{\ displaystyle c = m ^ {2} \, {\ bmod {\,}} n}

Toisin sanoen c on neliönmuotoisen tekstin neliöllinen jäännös , modulo n . Käytännössä, lohkosalausalgoritmia käytetään yleensä.

Esimerkki

Edellisessä esimerkissämme on selkeä tekstitila mahdollista. Otetaan vain teksti. Salausteksti on silloin . P={0,...,76}{\ displaystyle P = \ {0, ..., 76 \}}m=20{\ displaystyle m = 20}vs.=m2modei=400mod77=15{\ displaystyle c = m ^ {2} \, {\ bmod {\,}} n = 400 \, {\ bmod {\,}} 77 = 15}

Merkintä

Salakirjoitus 15 tuotetaan neljälle eri arvolle m , ts . Tämä pätee myös useimpiin Rabinin algoritmin tuottamiin salausteksteihin. Toisin sanoen, se on "neljä yhdessä" -ominaisuus. m∈{13,20,57,64}{\ displaystyle m \ sisään \ {13,20,57,64 \}}

Salauksen purku

Salauksen purkamiseen tarvitaan yksityinen avain. Prosessi on seuraava.

Neliöjuuret ja lasketaan. Laajennettu Eukleideen algoritmi mahdollistaa laskea ja , kuten . ms=vs.mods{\ displaystyle m_ {p} = {\ sqrt {c}} \, {\ bmod {\,}} p}mq=vs.modq{\ displaystyle m_ {q} = {\ sqrt {c}} \, {\ bmod {\,}} q}ys{\ displaystyle y_ {p}}yq{\ displaystyle y_ {q}}ys⋅s+yq⋅q=1{\ displaystyle y_ {p} \ cdot p + y_ {q} \ cdot q = 1}

Se herättää sitten kiinalainen jäännöslause laskea vankkumatta juuret , , ja varten . ( on moduulin n lopun luokan joukko  ; neljä neliöjuuria ovat joukossa ): +r{\ displaystyle + r}-r{\ displaystyle -r}+s{\ displaystyle + s}-s{\ displaystyle -s}vs.+eiZ∈Z/eiZ{\ displaystyle c + n \ mathbb {Z} \ sisään \ mathbb {Z} / n \ mathbb {Z}}Z/eiZ{\ displaystyle \ mathbb {Z} / n \ mathbb {Z}}{0,...,ei-1}{\ displaystyle \ {0, ..., n-1 \}}

r=(ys⋅s⋅mq+yq⋅q⋅ms)modei-r=ei-rs=(ys⋅s⋅mq-yq⋅q⋅ms)modei-s=ei-s{\ displaystyle {\ begin {matrix} r & = & (y_ {p} \ cdot p \ cdot m_ {q} + y_ {q} \ cdot q \ cdot m_ {p}) \, {\ bmod {\, }} n \\ - r & = & nr \\ s & = & (y_ {p} \ cdot p \ cdot m_ {q} -y_ {q} \ cdot q \ cdot m_ {p}) \, {\ bmod {\,}} n \\ - s & = & n-s \ loppu {matriisi}}}

Esimerkki

Edellisestä esimerkistä löydämme ensin juuret modulo yksityisen avaimen alkuluvut: ja . ms=1{\ displaystyle m_ {p} = 1}mq=9{\ displaystyle m_ {q} = 9}

Laajennettu euklidinen algoritmi antaa sitten ja . ys=-3{\ displaystyle y_ {p} = - 3}yq=2{\ displaystyle y_ {q} = 2}

Kiinan jäljellä oleva lause antaa neljä mahdollista neliöjuuria, joista m = 20 , alkuperäinen selkeä teksti. m∈{64,20,13,57}{\ displaystyle m \ sisällä \ {64, \ mathbf {20}, 13,57 \}}

Huomautuksia ja viitteitä

Liitteet

Bibliografia

• [Buchmann 2001] (de) Johannes Buchmann, Einführung in die Kryptographie , Berliini, Springer,2001, 2 nd  ed. , 231  Sivumäärä ( ISBN  3-540-41283-2 , OCLC  248045737 ).
• [Menezes, van Oorschot ja Vanstone 1996] (en) Alfred Menezes ja Scott A. Vanstone, Käsikirja sovelletusta salauksesta , Boca Raton, CRC Press,Lokakuu 1996, 780  Sivumäärä ( ISBN  0-8493-8523-7 , OCLC  849453812 ).
• [Rabin 1979] (en) Michael O. Rabin, "  Digitalisoidut allekirjoitukset ja julkisen avaimen toiminnot , joita ei voida ratkaista kuin factoring  " , MIT-tietotekniikan laboratorio ,tammikuu 1979( lue verkossa [PDF] ).
• [Lindhurst 1999] (en) Scott Lindhurst, "Analyysi Shankin algoritmista neliöjuurien laskemiseksi rajallisissa kentissä" , julkaisussa R. Gupta ja KS Williams, Proc 5th Conf Can Nr Theo Assoc , voi.  19, AMS, kokoonpano  "CRM Proc & Lec Notes",Elokuu 1999.
• [Kumanduri ja Romero 1997] R. Kumanduri ja C. Romero, lukuteoria tietokoneohjelmilla , Prentice Hall,1997.

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">