Massey-Omura kryptosystem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 20 juni 2018; verifiering kräver 1 redigering .

Massey-Omura-kryptosystemet föreslogs 1978 av James Massey och Jim K. Omura, ursprungligen som en förbättring av Shamir- protokollet . Det finns två alternativ för att implementera detta protokoll: klassiskt och elliptiskt. Den första bygger på komplexiteten i det diskreta logaritmproblemet , den andra på egenskaperna hos en elliptisk kurva . Vanligtvis används det resulterande meddelandet som nyckeln till ett traditionellt kryptosystem. $m$

Originalversion

Inledningsvis beskrevs Massey-Omura-protokollet i relation till den multiplikativa gruppen , där är ett primtal, och var en analog av hemlig överföring med hjälp av lådor låsta med ett eller två lås. Kärnan i schemat är som följer: abonnenten Alice låser lådan med brevet med sin nyckel och skickar lådan till abonnenten Bob. Prenumeranten Bob låser i sin tur den med sin nyckel och skickar tillbaka den till Alice. Alice släpper sitt lås och pekar lådan mot Bob, som släpper sitt lås. $Z_{p}^{*}$ $sid$

Algoritm

Ett stort primtal väljs som en systemparameter . Prenumeranterna Alice och Bob väljer slumpmässiga tal och (mellan 0 och ) coprime till , var är Euler-funktionen . $sid$ $e_{A}$ $e_{B}$ $p-1$ $p-1=\varphi (p)$ $\varphi$
Med hjälp av den utökade euklidiska algoritmen, och beräknas , reciproka tal och 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)

Med andra ord måste följande villkor vara uppfyllda:

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

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

Par av nummer är hemliga nycklar för abonnenter. $(e_{A},d_{A})$ $(e_{B},d_{B})$

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

, därför att

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

(Den första faktorn är 1 enligt Eulers teorem ). Likaså . $m^{e_{B}d_{B}}=m{\bmod {p}}$

Prenumeranten Alice skickar ett meddelande ( ) till prenumeranten Bob. $m$ $0<m<{p-1}$

Alice krypterar sitt meddelande med den första nyckeln: ( ) och skickar det till prenumeranten Bob. $m_{1}=m^{e_{A}}{\bmod {p}}$ $0<m_{1}<p$ $m_1$

Bob krypterar med den andra nyckeln: ( ) och skickar tillbaka den till Alice. $m_{2}=m_{1}^{{e_{B))}{\bmod p}$ $0<m_{2}<p$
Alice "låser upp det första låset" med den andra privata nyckeln:

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

Bob "tar bort sitt första lås" med en andra privat nyckel:

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

Totalt: prenumeranten Bob fick ett hemligt meddelande från Alice. $m$

Problem vid användning

Denna version av systemet kan implementeras utan att använda exponentieringsproceduren i finita fält, men det diskreta logaritmproblemet är svårt nog för Bob att han inte kan fastställa nyckeln och hädanefter läsa meddelanden som inte var avsedda för honom. En förutsättning för tillförlitlighet är ett bra meddelandesigneringssystem. Utan användning av signaturer kan vilken som helst tredje part Eva utge sig för att vara Bobs prenumerant och skicka ett meddelande av formuläret till Alice . Alice kommer att fortsätta proceduren och, genom att "ta bort sitt lås", öppnar han vägen för bedragaren Eva att dekryptera meddelandet. I detta avseende måste åtföljas av autentisering . $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}$

Elliptisk variant

En elliptisk version av detta protokoll ger möjlighet att skicka ett meddelande från Alice till Bob över en öppen kanal utan att först överföra någon nyckelinformation. Systemparametrarna här är: ekvationen för en elliptisk kurva och fältet som ges av ett irreducerbart polynom . Låt ordningen på den elliptiska kurvan vara lika med , vara ett heltal coprime till ( ). Med Euklids algoritm kan man hitta $\varepsilon$ $F$ $\varepsilon$ $N$ $e$ $N$ $1<e<N$

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

Per definition av modulo-jämförbarhet :

e*d=jN+1

Detta betyder att för vilken punkt som helst av ordningens elliptiska kurva : $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

, det är

e\cdot (d\cdot P)=P

Nu, med hjälp av och och vilken punkt som helst på den elliptiska kurvan, kan vi beräkna $e$ $d$ $P$

Q=d\cdot {P}

R=e\cdot {Q}

Var . Att beräkna en punkt från är ekvivalent med att lösa det diskreta logaritmproblemet för en elliptisk kurva. $P=R$ $P$ $eP$

Algoritm

Prenumeranten Alice placerar sitt meddelande vid någon punkt i den elliptiska kurvan och multiplicerar det med sitt hemliga värde , får en poäng . Denna punkt skickas till prenumeranten Bob. $m$ $M(m)$ $e_{A}$ $P_{1}=e_{A}\cdot {M(m)}$
Bob räknar ut och skickar resultatet till Alice. $P_{2}=e_{B}\cdot {P_{1}}$
Alice "låser upp" genom att beräkna . Returnerar resultatet till den som ringer Bob. $P_{3}=d_{A}\cdot {P_{2}}$
Bob dekrypterar meddelandet med sin hemliga krypteringsnyckel : $d_{B}$

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

Litteratur

N. Koblitz "Kurs i talteori och kryptografi". Moskva, 2001
A. A. Bolotov, S. B. Gashkov, A. B. Frolov, A. A. Chasovskikh "Algorithmic foundations of elliptic cryptography. Moskva, 2004
B. N. Voronkov, A. S. Shchegolevatykh "Element av talteori och kryptoskydd". Voronezh, 2008