Massey-Omura kriptorendszer

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. június 20-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A Massey–Omura kriptorendszert 1978-ban javasolta James Massey és Jim K. Omura, eredetileg a Shamir protokoll továbbfejlesztéseként . Két lehetőség van ennek a protokollnak a megvalósítására: klasszikus és elliptikus. Az első a diszkrét logaritmus probléma összetettségére , a második egy elliptikus görbe tulajdonságaira épül . Általában az eredményül kapott üzenetet egy hagyományos kriptorendszer kulcsaként használják. $m$

Eredeti verzió

Kezdetben a Massey-Omura protokollt a szorzócsoporttal kapcsolatban írták le , ahol egy prímszám, és egy vagy két zárral lezárt dobozok titkos átvitelének analógja volt. A séma lényege a következő: Alice előfizető kulcsával lezárja a levéllel ellátott dobozt, és elküldi a dobozt Bob előfizetőnek. Bob előfizető pedig a kulcsával lezárja, és visszaküldi Alice-nek. Alice kioldja a zárat, és Bob felé mutat a dobozzal, aki kioldja a zárat. $Z_{p}^{*}$ $p$

Algoritmus

Rendszerparaméterként nagy prímszám van kiválasztva . Alice és Bob előfizetők véletlenszerű számokat választanak, és (0 és ) között kopíroznak , ahol az Euler függvény . $p$ $e_{A}$ $e_{B}$ $p-1$ $p-1=\varphi (p)$ $\varphi$
A kiterjesztett euklideszi algoritmus segítségével kiszámítjuk a számok és a modulo reciprokát : $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)

Más szóval, a következő feltételeknek kell teljesülniük:

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

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

A számpárok az előfizetők titkos kulcsai . $(e_{A},d_{A})$ $(e_{B}, d_{B})$

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

, mert

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

(Az első tényező az Euler-tétel szerint 1 ). Hasonlóképpen . $m^{e_{B}d_{B}}=m{\bmod {p}}$

Alice előfizető üzenetet ( ) küld Bob előfizetőnek. $m$ $0<m<{p-1}$

Alice az első kulccsal titkosítja az üzenetet: ( ), és elküldi Bob előfizetőnek. $m_{1}=m^{e_{A}}{\bmod {p}}$ $0<m_{1}<p$ $m_1$

Bob a második kulccsal titkosít: ( ) és visszaküldi Alice-nek. $m_{2}=m_{1}^{{e_{B))}{\bmod p}$ $0<m_{2}<p$
Alice "feloldja az első zárat" a második privát kulccsal:

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

Bob "eltávolítja az első zárat" egy második privát kulccsal:

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

Összesen: Bob előfizető titkos üzenetet kapott Alice-től. $m$

Használati problémák

A rendszer ezen verziója a hatványozási eljárás használata nélkül is megvalósítható véges mezőkben, de a diszkrét logaritmus probléma elég nehéz Bob számára ahhoz, hogy nem tudja meghatározni a kulcsot , és ezentúl elolvashatja a nem neki szánt üzeneteket. A megbízhatóság előfeltétele a jó üzenet-aláíró rendszer. Aláírások használata nélkül bármely harmadik fél, Eva, kiadhatja magát Bob előfizetőjének, és visszaküldheti az űrlap üzenetét Alice-nek . Alice folytatja az eljárást, és a "zár eltávolításával" megnyitja az utat a csaló Éva előtt, hogy visszafejtse az üzenetet. Ebben a tekintetben hitelesítésnek kell kísérnie . $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}$

Elliptikus változat

A protokoll elliptikus változata lehetővé teszi, hogy üzenetet küldjön Alice-től Bobnak egy nyitott csatornán anélkül, hogy először bármilyen kulcsfontosságú információt továbbítana. A rendszerparaméterek itt a következők: egy elliptikus görbe és egy irreducibilis polinom által adott mező egyenlete . Legyen az elliptikus görbe sorrendje egyenlő -vel , legyen egész szám másodpróbája ( ). Euklidész algoritmusa szerint meg lehet találni $\varepsilon$ $F$ $\varepsilon$ $N$ $e$ $N$ $1<e<N$

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

A modulo összehasonlíthatóság meghatározása szerint :

e*d=jN+1

Ez azt jelenti, hogy a sorrend elliptikus görbéjének bármely pontjára : $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

, vagyis

e\cdot (d\cdot P)=P

Most a és és az elliptikus görbe bármely pontjával kiszámíthatjuk $e$ $d$ $P$

Q=d\cdot {P}

R=e\cdot {Q}

Hol . Egy pont kiszámítása innen megegyezik egy elliptikus görbe diszkrét logaritmusfeladatának megoldásával. $P=R$ $P$ $eP$

Algoritmus

Alice előfizető az elliptikus görbe egy pontjára helyezi üzenetét és megszorozza titkos értékével , pontot kap . Ezt a pontot elküldjük Bob előfizetőnek. $m$ $M(m)$ $e_{A}$ $P_{1}=e_{A}\cdot {M(m)}$
Bob kiszámolja és elküldi az eredményt Alice-nek. $P_{2}=e_{B}\cdot {P_{1}}$
Alice "felold" a számítással . Az eredményt visszaküldi a hívó Bobnak. $P_{3}=d_{A}\cdot {P_{2}}$
Bob titkos titkosítási kulcsával visszafejti az üzenetet : $d_{B}$

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

Irodalom

N. Koblitz "Számelmélet és kriptográfia tanfolyam". Moszkva, 2001
A. A. Bolotov, S. B. Gashkov, A. B. Frolov, A. A. Chasovskikh "Az elliptikus kriptográfia algoritmikus alapjai. Moszkva, 2004
B. N. Voronkov, A. S. Shchegolevatykh „A számelmélet és a kriptovédelem elemei”. Voronyezs, 2008