Criptosistemul Massey-Omura

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 20 iunie 2018; verificarea necesită 1 editare .

Criptosistemul Massey-Omura a fost propus în 1978 de James Massey și Jim K. Omura, inițial ca o îmbunătățire a protocolului Shamir . Există două opțiuni pentru implementarea acestui protocol: clasic și eliptic. Prima este construită pe complexitatea problemei logaritmului discret , a doua pe proprietăţile unei curbe eliptice . De obicei, mesajul rezultat este folosit ca cheie a unui criptosistem tradițional. $m$

Versiunea originală

Inițial, protocolul Massey-Omura a fost descris în relație cu grupul multiplicativ , unde este un număr prim, și a fost un analog al transferului secret folosind cutii blocate cu una sau două lacăte. Esența schemei este următoarea: abonatul Alice încuie cutia cu scrisoarea cu cheia sa și trimite cutia abonatului Bob. Abonatul Bob, la rândul său, îl încuie cu cheia și i-o trimite înapoi lui Alice. Alice își eliberează lacătul și îndreaptă cutia către Bob, care își eliberează încuietoarea. $Z_{p}^{*}$ $p$

Algoritm

Un număr prim mare este selectat ca parametru de sistem . Abonații Alice și Bob aleg numere aleatoare și (între 0 și ) coprime la , unde este funcția Euler . $p$ $e_{A}$ $e_{B}$ $p-1$ $p-1=\varphi (p)$ $\varphi$
Cu ajutorul algoritmului euclidian extins și se calculează reciprocele numerelor și modulo : $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)

Cu alte cuvinte, trebuie îndeplinite următoarele condiții:

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

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

Perechile de numere sunt chei secrete ale abonaților. $(e_{A},d_{A})$ $(e_{B},d_{B})$

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

, deoarece

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

(Primul factor este 1 după teorema lui Euler ). La fel . $m^{e_{B}d_{B}}=m{\bmod {p}}$

Abonatul Alice trimite un mesaj ( ) abonatului Bob. $m$ $0<m<{p-1}$

Alice își criptează mesajul cu prima cheie: ( ) și îl trimite abonatului Bob. $m_{1}=m^{e_{A}}{\bmod {p}}$ $0<m_{1}<p$ $m_1$

Bob criptează cu a doua cheie: ( ) și o trimite înapoi lui Alice. $m_{2}=m_{1}^{{e_{B))}{\bmod p}$ $0<m_{2}<p$
Alice „deblochează prima lacăt” cu a doua cheie privată:

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

Bob „își scoate primul lacăt” cu o a doua cheie privată:

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

Total: abonatul Bob a primit un mesaj secret de la Alice. $m$

Probleme de utilizare

Această versiune a sistemului poate fi implementată fără a utiliza procedura de exponențiere în câmpuri finite, dar problema logaritmului discret este suficient de dificilă pentru Bob încât nu poate determina cheia și de acum înainte să citească mesaje care nu i-au fost destinate. O condiție prealabilă pentru fiabilitate este un sistem bun de semnare a mesajelor. Fără utilizarea semnăturilor, orice terță parte Eva poate pretinde a fi abonatul lui Bob și poate returna un mesaj din formular către Alice . Alice va continua procedura și, prin „scoaterea lacătului”, va deschide calea impostoarei Eva să decripteze mesajul. În acest sens, trebuie să fie însoțit de autentificare . $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}$

Varianta eliptică

O versiune eliptică a acestui protocol oferă posibilitatea de a trimite un mesaj de la Alice către Bob pe un canal deschis, fără a transmite mai întâi nicio informație cheie. Parametrii sistemului aici sunt: ecuația unei curbe eliptice și câmpul dat de un polinom ireductibil . Fie ordinea curbei eliptice egală cu , fie un întreg coprim cu ( ). Prin algoritmul lui Euclid, se poate găsi $\varepsilon$ $F$ $\varepsilon$ $N$ $e$ $N$ $1<e<N$

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

Prin definiția comparabilității modulo :

e*d=jN+1

Aceasta înseamnă că pentru orice punct al curbei eliptice de ordin : $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

, acesta este

e\cdot (d\cdot P)=P

Acum, folosind și și orice punct al curbei eliptice, putem calcula $e$ $d$ $P$

Q=d\cdot {P}

R=e\cdot {Q}

Unde . Calcularea unui punct de la este echivalentă cu rezolvarea problemei logaritmului discret pentru o curbă eliptică. $P=R$ $P$ $eP$

Algoritm

Abonatul Alice își plasează mesajul într-un punct al curbei eliptice și îl înmulțește cu valoarea sa secretă , obține un punct . Acest punct este trimis abonatului Bob. $m$ $M(m)$ $e_{A}$ $P_{1}=e_{A}\cdot {M(m)}$
Bob calculează și trimite rezultatul lui Alice. $P_{2}=e_{B}\cdot {P_{1}}$
Alice „deblochează” calculând . Returnează rezultatul apelantului Bob. $P_{3}=d_{A}\cdot {P_{2}}$
Bob decriptează mesajul folosind cheia secretă de criptare : $d_{B}$

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

Literatură

N. Koblitz „Curs de Teoria numerelor și Criptografie”. Moscova, 2001
A. A. Bolotov, S. B. Gashkov, A. B. Frolov, A. A. Chasovskikh „Bazele algoritmice ale criptografiei eliptice. Moscova, 2004
B. N. Voronkov, A. S. Shchegolevatykh „Elemente ale teoriei numerelor și criptoprotecției”. Voronej, 2008