Massey-Omura kryptojärjestelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 20. kesäkuuta 2018 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

James Massey ja Jim K. Omura ehdottivat Massey-Omura kryptojärjestelmää vuonna 1978 alun perin Shamir -protokollan parannukseksi . Tämän protokollan toteuttamiseen on kaksi vaihtoehtoa: klassinen ja elliptinen. Ensimmäinen rakentuu diskreetin logaritmiongelman monimutkaisuuteen ja toinen elliptisen käyrän ominaisuuksiin . Tyypillisesti tuloksena olevaa viestiä käytetään perinteisen salausjärjestelmän avaimena. $m$

Alkuperäinen versio

Aluksi Massey-Omura-protokollaa kuvattiin suhteessa kertovaan ryhmään , jossa on alkuluku, ja se oli analogi salaiselle siirrolle käyttämällä laatikoita, jotka oli lukittu yhdellä tai kahdella lukolla. Järjestelmän olemus on seuraava: tilaaja Alice lukitsee laatikon kirjeellä avaimellaan ja lähettää laatikon tilaajalle Bobille. Tilaaja Bob puolestaan lukitsee sen avaimellaan ja lähettää sen takaisin Alicelle. Alice vapauttaa lukkonsa ja osoittaa laatikon Bobia kohti, joka vapauttaa lukkonsa. $Z_{p}^{*}$ $s$

Algoritmi

Järjestelmäparametriksi valitaan suuri alkuluku . Tilaajat Alice ja Bob valitsevat satunnaisluvut ja (välillä 0 - ) koprime , missä on Euler-funktio . $s$ $e_{A}$ $e_{B}$ $p-1$ $p-1=\varphi (p)$ $\varphi$
Laajennetun euklidisen algoritmin avulla lasketaan lukujen ja modulon käänteiset : $d_{A}$ $d_{B}$ $e_{A}$ $e_{B}$ $p-1$

d_{A}={e_{A}}^{-1}{\bmod {(}}p-1)

d_{B}={e_{B}}^{-1}{\bmod {(}}p-1)

Toisin sanoen seuraavat ehdot on täytettävä:

{\displaystyle e_{A}\cdot {d_{A}\equiv 1{\bmod {(}}p-1)))

e_{B}\cdot {d_{B}}\equiv 1{\bmod {(}}p-1)

Numeriparit ovat tilaajien salaisia avaimia . ${\näyttötyyli (e_{A},d_{A})}$ $(e_{B}, d_{B})$

m^{e_{A}\cdot {d_{A}}}=m{\bmod {p}}

, koska

m^{{e_{A}\cdot {d_{A))))=m^{{j\cdot {\varphi (p)+1))}=m^{{j\cpiste {\varphi (p )}}}\cdot {m}=m

(Ensimmäinen tekijä on 1 Eulerin lauseen mukaan ). Samoin . $m^{e_{B}d_{B}}=m{\bmod {p}}$

Tilaaja Alice lähettää viestin ( ) tilaajalle Bob. $m$ $0<m<{p-1}$

Alice salaa viestinsä ensimmäisellä avaimella: ( ) ja lähettää sen tilaajalle Bobille. $m_{1}=m^{e_{A}}{\bmod {p}}$ $0<m_{1}<p$ $m_1$

Bob salaa toisella avaimella: ( ) ja lähettää sen takaisin Alicelle. $m_{2}=m_{1}^{{e_{B))}{\bmod p}$ $0<m_{2}<p$
Alice "avaa ensimmäisen lukon" toisella yksityisellä avaimella:

m_{3}=m_{2}^{{d_{A}}}{\bmod p}=m^{{e_{A}\cdot {e_{B}}\cdot {d_{A}}}} {\bmod p}

Bob "poistaa ensimmäisen lukkonsa" toisella yksityisellä avaimella:

m_{4}=m_{3}^{{d_{B))}{\bmod p}=m^{{d_{B}\cdot {e_{A}}\cdot {e_{B}}\cdot {d_{A}}}}modp=m

Yhteensä: tilaaja Bob sai salaisen viestin Alicelta. $m$

Ongelmia käytössä

Tämä järjestelmän versio voidaan toteuttaa ilman eksponentioproseduuria äärellisissä kentissä, mutta diskreetin logaritmin ongelma on Bobille niin vaikea, että hän ei pysty määrittämään avainta ja tästä lähtien lukea viestejä, joita ei ole tarkoitettu hänelle. Luotettavuuden edellytyksenä on hyvä viestien allekirjoitusjärjestelmä. Ilman allekirjoituksia kuka tahansa kolmas osapuoli Eva voi teeskennellä olevansa Bobin tilaaja ja palauttaa lomakkeen viestin Alicelle . Alice jatkaa menettelyä ja "poistamalla lukkonsa" avaa tien huijari Evalle viestin salauksen purkamiseen. Tältä osin on liitettävä todennus . $m_{1}=m^{{e_{A}}}$ $m^{{e_{A}}}$ $m_{{\tilde {2}}}=m_{1}^{{e_{E}}}{\bmod p}$ $m_{2}=m_{1}^{{e_{B))}{\bmod p}$

Elliptinen variantti

Tämän protokollan elliptinen versio tarjoaa mahdollisuuden lähettää viesti Alicesta Bobille avoimen kanavan kautta ilman, että ensin lähetetään mitään avaintietoja. Järjestelmäparametrit ovat: elliptisen käyrän yhtälö ja redusoitumattoman polynomin antama kenttä . Olkoon elliptisen käyrän järjestys yhtä suuri kuin , olkoon ( ) kokonaisluku koprime. Euklidesin algoritmilla voidaan löytää $\varepsilon$ $F$ $\varepsilon$ $N$ $e$ $N$ $1<e<N$

d\equiv {e^{-1}}{\pmod {N}}

Modulovertailun määritelmän mukaan :

e*d=jN+1

Tämä tarkoittaa, että missä tahansa järjestyksen elliptisen käyrän pisteessä : $P$ $\varepsilon$ $N$

e\cdot {(d\cdot P)}=(e\cdot {d})P=(j\cdot {N}+1)P=(j\cdot {N})P+P=j \cdot {0}+P=0+P=P

, tuo on

e\cdot (d\cdot P)=P

Nyt voimme laskea käyttämällä ja ja mitä tahansa elliptisen käyrän pistettä $e$ $d$ $P$

Q=d\cdot {P}

R=e\cdot {Q}

Missä . Pisteen laskeminen pisteestä vastaa elliptisen käyrän diskreetin logaritmitehtävän ratkaisemista. $P=R$ $P$ $eP$

Algoritmi

Tilaaja Alice asettaa viestinsä johonkin elliptisen käyrän pisteeseen ja kertoo sen salaisella arvollaan , saa pisteen . Tämä piste lähetetään tilaajalle Bob. $m$ $M(m)$ $e_{A}$ $P_{1}=e_{A}\cdot {M(m)}$
Bob laskee ja lähettää tuloksen Alicelle. $P_{2}=e_{B}\cdot {P_{1}}$
Alice "avautuu" laskemalla . Palauttaa tuloksen soittajalle Bob. $P_{3}=d_{A}\cdot {P_{2}}$
Bob purkaa viestin salauksen salaisella salausavaimellaan : $d_{B}$

M(m)=d_{B}\cpiste {P_{3}}

Kirjallisuus

N. Koblitz "Lukuteorian ja kryptografian kurssi". Moskova, 2001
A. A. Bolotov, S. B. Gashkov, A. B. Frolov, A. A. Chasovskikh "Elliptisen kryptografian algoritmiset perusteet. Moskova, 2004
B. N. Voronkov, A. S. Shchegolevatykh "Lukuteorian ja kryptosuojauksen elementit". Voronež, 2008