Williams 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 december 2014; kontroller kräver 11 redigeringar .

Williams Cryptosystem är ett krypteringssystem med offentlig nyckel skapat av Hugh Cowie Williams 1984.

Historik

Algoritmen utvecklades 1984 som ett alternativ till den mer kända RSA. Syftet med utvecklingen var att bli av med sårbarheterna i kryptosystemet.

Om algoritmen

För vilket kryptosystem som helst är det önskvärt att det bevisas att dess brytning har en beräkningskomplexitet som liknar beräkningskomplexiteten hos ett problem som för tillfället inte kan lösas inom en överskådlig tid. Liksom RSA, är Williams kryptosystem baserat på antagandet att det är svårt att faktorisera stora tal, och det har bevisats att för all krypteringstext som bryts med hjälp av preliminär kryptoanalys (som endast har den publika nyckeln), är det nödvändigt att faktorisera [ 1] , det vill säga lös ekvationen för och . Detta påstående har inte bevisats för RSA- systemet . Faktoriseringsproblemets beräkningskomplexitet är okänd, men den tros vara ganska hög. Men precis som RSA är Williams kryptosystem sårbart för en chiffertextattack. $pq=n$ $sid$ $q$

Beskrivning av algoritmen

Williams systemalgoritm, även om den inte är beräkningsmässigt mer komplex än RSA, är mycket mer besvärlig att beskriva. Det finns ett lemma för den [2] , som kommer att beskrivas i avsnittet om den matematiska apparaten - den spelar en nyckelroll i detta kryptosystem.

Matematisk apparat

Till att börja med bör terminologin definieras - den är lånad från teorin om kvadratiska fält , men endast den mest grundläggande kunskapen krävs för ett kryptosystem. Tänk på elementet

\alpha =a+b{\sqrt c}=(a,b),

där är heltal och är ett villkorligt element vars kvadrat är . Då kommer följande formler att vara giltiga: $a,b,c$ ${\sqrt c}$ $c$

\alpha _{1}+\alpha _{2}=(a_{1}+a_{2},b_{1}+b_{2}),

\alpha _{1}\cdot \alpha _{2}=(a_{1}a_{2}+c\cdot b_{1}b_{2},a_{1}b_{2}+a_{2} b_{1})

Konjugatet av ett tal kallas $\alfa$

{\bar \alpha }=ab{\sqrt c}

Vi definierar också funktioner som hjälper oss att uttrycka kraften i detta tal. Låta

\alpha ^{i}=X_{i}(\alpha )+Y_{i}(\alpha ){\sqrt {c)),

då kan du uttryckas så här: $X_{i}$ $Y_{i}$ ${\displaystyle \alpha ^{i))$

X_{i}(\alpha )=(\alpha ^{i}+{\bar \alpha }^{i})/2

Y_{i}(\alpha )=b(\alpha ^{i}-{\bar {\alpha }}^{i})/(\alpha -{\bar {\alpha }})=( \alpha ^{i}-{\bar {\alpha }}^{i})(2{\sqrt {c}})

Det sista uttrycket är endast för att underlätta förståelsen. Eftersom funktionerna är definierade för par innehåller de inte . Om vi nu antar att , då kan vi skriva följande återkommande relationer: $(a,b)$ $c$ $a^{2}-b^{2}c=1$

X_{2i}=2{X_{i}}^{2}-1

Y_{2i}=2X_{i}Y_{i}

{\displaystyle X_{2i+1}=2X_{i}X_{i+1}-X_{1))

{\displaystyle Y_{2i+1}=2X_{i}Y_{i+1}-Y_{1))

Dessa formler är utformade för att snabbt beräkna och . Sedan och , det beror inte heller på . $X_{i}$ $Y_{i}$ $X_{0}=1$ $X_{1}=a$ $X_{i}(\alpha )$ $b$

Lemma

Låta vara produkten av två udda primtal och ; är heltal som uppfyller ekvationen . Låt Legendre-symbolerna och tillfredsställa kongruenserna $n$ $sid$ $q$ $a,b,c$ $a^{2}-cb^{2}=1{\pmod n}$ $\delta _{p}=$ $\textstil \left({{\frac {c}{p))}\right)$ $\delta _{q}=\textstil \left({{\frac {c}{q))}\right)$

\delta _{p}=-p{\pmod 4}

\delta _{q}=-q{\pmod 4}

Vidare, låt och Jacobi-symbolen vara lika med 1. Beteckna $gcd(cb,n)=1$ $\textstil \left({{\frac {2(a+1)}{n))}\höger)$

m=(p-\delta _{p})(q-\delta _{q})/4

och vi antar det och uppfyller jämförelsen $e$ $d$

ed=(m+1)/2{\pmod m}

Under dessa antaganden

\alpha ^{2ed}=\pm \alpha {\pmod {n}}

Skapa en nyckel

Först två primtal och väljs , och deras produkt beräknas . Med hjälp av uppräkning väljs ett nummer så att Legendre symboliserar och uppfyller de villkor som ställs i lemma. Sedan (även genom val) bestäms ett nummer så att Jacobi-symbolen $sid$ $q$ $n$ $c$ $\delta _{p}$ ${\displaystyle \delta _{q))$ $s$

\textstil \left({{\frac {s^{2}-c}{n))}\right)=-1

och Antal väljs på samma sätt som i lemmat: $gcd\textstyle \left(s,n\right)=1.$ $m$

m=(p-\delta _{p})(q-\delta _{q})/4

Sedan väljs siffror som uppfyller de villkor som ställs i lemma. Vi väljer slumpmässigt, till exempel, och beräknar med formeln $d, e$ $d:gcd\textstyle \left(d,m\right)=1$ $e$

e={\frac {m+1}{2}}d^{{-1}}{\pmod m}

Sedan är den offentliga nyckeln och är den privata nyckeln. ${n,e,c,s}$ ${p,q,m,d}$

Kryptering

Alla beräkningar här är modulo . Notationen här betyder Låt oss representera klartexten som ett tal . Definiera och : om Jacobi-symbolen är lika med , då $n$ $a+b{\sqrt c}{\pmod n}$ $(a\mod n)+(b\mod n){\sqrt c}.$ $w\in{2,3,...,n-1}$ $\gamma$ $b_{1}$ $\textstil \left({{\frac {w^{2}-c}{n))}\right)$ $+1$

b_{1}=0

och

\gamma =w+{\sqrt c},

annars definierar vi genom produkten $\gamma$

b_{1}=1

och

\gamma =(w+{\sqrt c})(s+{\sqrt c}).

Då är det lätt att verifiera att Jacobi-symbolen

\textstil \left({{\frac {\gamma {\bar \gamma }}{n}}}\right)=1,

som verifieras genom direkt beräkning (i det andra fallet, med hänsyn till valet och multiplikativiteten för Jacobi-symbolen). Därefter hittar vi numret $s$

\alpha ={\frac {\gamma }{{\bar \gamma }}}.

Låt oss representera det i formen uppfyller de villkor som ställs i lemma. De uppfyller faktiskt byggvillkoren, och $\alfa$ $\alpha =a+b{\sqrt c}.$ $\alfa$ $p,q,n,c,d,e$

\alpha {\bar \alpha }={\frac {\gamma }({\bar \gamma }}}{\frac ({\bar \gamma }}{\gamma }}=1.

2(a+1)={\frac {\gamma }({\bar \gamma }}}+{\frac ({\bar \gamma }}{\gamma }}+2={\frac {(\gamma +{\bar \gamma })^{2}}{{\bar \gamma }\gamma }}{\pmod n}

Det följer av den sista formeln att

\textstil \left({{\frac {2(a+1)}{n))}\right)=1.

Efter att ha mottagit det, bör det krypteras med exponentiering - resultatet kan representeras genom och som kan [3] snabbt (för antalet operationer i ordning ) hittas med återkommande formler. Låt oss presentera notationen $\alfa,$ $e$ $X_{e}(\alpha )$ $Y_{e}(\alpha ),$ $\log e$

E={\frac {X_{e}(\alpha )}{Y_{e}(\alpha )))

Då blir kryptotexten en trippel av siffror där $(E,b_{1},b_{2}),$ $b_{2}=a\mod 2.$

Dekryptering

Dekryptering är lättare. Beräknade först

\alpha ^{{2e))={\frac {\alpha ^{{2e))}{{(\alpha {\bar \alpha })}^{e))}={\frac {E+{\sqrt c}}{E-{\sqrt c}}},

vad en angripare kan göra. Men för den slutliga dekrypteringen är det nödvändigt att beräkna, som visas i lemma - trots vad som hålls hemligt. $\alpha ^{{2ed}}$ $d$

\alpha ^{{2ed}}=X_{d}(\alpha ^{{2e}})+Y_{d}(\alpha ^{{2e}}){\sqrt c}=\pm \alpha

Siffran som skickas i meddelandet kommer att indikera vilket av tecknen som är korrekt - det som ger ett jämnt resultat eller det som ger ett udda. Siffran kommer att indikera om resultatet ska multipliceras med . Som ett resultat kommer vi att få numret $b_{2},$ $b_{1}$ $(s-{\sqrt c})/(s+{\sqrt c})$

\alpha '={\frac {w+{\sqrt c}}{w-{\sqrt c}}}

Och vi kan enkelt hitta källtexten, som kommer att slutföra dekrypteringsprocessen.

w={\frac {\alpha '+1}{\alpha '-1}}{\sqrt c}

Säkerhet

Liksom RSA kan ett kryptosystem attackeras baserat på en vald chiffertext . Anta att en kryptoanalytiker har hittat någon algoritm som med sannolikhet gör det möjligt att dechiffrera kryptotexten. Då kan han göra följande: $\delta>0$

1. Välj ett tal så att Jacobi-symbolen ;

\phi

\textstil \left({{\frac {\phi ^{2}-c}{n))}\right)=-1

2. Kryptera , men på ett sådant sätt som om den nämnda Jacobi-symbolen är lika med och , efter att ha mottagit kryptotexten vid utgången ;

\phi

+1

b_{1}=0

(E,0,b_{2})

3. Dekryptera den mottagna kryptotexten, få några .

\psi \neq \phi

Då med sannolikhet kan kryptoanalytikern få $\delta>0$

\phi -\psi =p{\pmod n}

eller

\phi -\psi =q{\pmod n}

Det gör att du kan faktorisera och knäcka kryptosystemet. $n$

Prestanda

Efter generering av nyckeln sker huvudberäkningarna när man höjer ett tal till en potens, och detta kan göras i modulo multiplikationer, som var och en sker i additionsoperationer, som i sin tur utförs i elementära additionsoperationer med konstant hastighet - dvs. , i , med samma hastighet, vilket är exponentieringen av en heltalsmodulo, som krävs för att använda RSA. $\alfa$ $O(\log e)$ $O(\log e)$ $O(\log e)$ $O(\log ^{3}e)$

Exempel

Nyckelgenerering

Låt oss välja, till exempel, och , vems produkt är . Därför att $p=11$ $q=13$ $n=143$

\left({\frac {5}{11}}\right)=1=-11{\pmod {4}}

och

\left({\frac {5}{13}}\right)=-1=-13{\pmod {4}}

Du kan välja . Dessutom, om vi väljer , får vi $c=5$ $s=2$

\left({\frac {s^{2}-c}{n}}\right)=\left({\frac {-1}{11}}\right)\left({\frac { -1}{13}}\right)=-1

Vilket uppfyller satsens villkor. Nästa får vi

m=\left({\frac {10\cdot 14}{4}}\right)=35

Och slutligen väljer vi exponenterna för kryptering och dekryptering: sedan

23\cdot 16=18{\pmod {m))

Kan välja

e=23

d=16

Kryptering

Låt originaltexten vara . Därför att $\omega =21$

\left({\frac {21^{2}-5}{143}}\right)=\left({\frac {7}{11}}\right)\left({\frac {7 }{13}}\right)=(-1)\cdot (-1)=1

Vi har , och $b_{1}=0$ $\gamma =21+{\sqrt {5}}$

\alpha =\left({\frac {21+{\sqrt {5}}}{21-{\sqrt {5}}}}\right)=125+6{\sqrt {5}}{ \pmod {143}}

Eftersom det är udda får vi . Efter att ha räknat och vi får $125$ $b_{2}=1$ $X_{23}(\alpha )=68$ $Y_{23}(\alpha )=125$

E=68\cdot {125}^{-1}=68\cdot 135=28{\pmod {143}}

Således är chiffertexten en trippel . $(28,1,1)$

Dekryptering

Nu ska du räkna ut : ${\displaystyle \alpha ^{2e))$

\alpha ^{2e}=\left({\frac {28^{2}+5}{28^{2}-5}}\right)+2\cdot \left({\frac {28 }{28^{2}-5}}\right){\sqrt {5}}=95+126{\sqrt {5}}{\pmod {143}}

Sedan beräknar vi också $d=16$

X_{16}(\alpha ^{2e})=18

Y_{16}(\alpha ^{2e})=137

Sedan måste då vara udda och $b_{2}=1$ $a$

\alpha '=-(18+137{\sqrt {5)))=125+6{\sqrt {5}}{\pmod {143}}

Med tanke på att den andra komponenten i chiffertexten är , drar vi slutsatsen att . I detta fall $b_{1}=0$ $\alpha '=\alpha$

\omega ={\frac {126+6{\sqrt {5}}}{124+6{\sqrt {5}}}}{\sqrt {5}}=21{\pmod {143}}

Således fick vi , som var den ursprungliga klartexten. $\omega =21$

Anteckningar

↑ Kim, 1992 .
↑ Williams, 1985 .
↑ Arto Salomaa - Public Key Cryptography, ed. Fred, 1995, ISBN 5-03-001991-X

Litteratur

Hugh C. Williams. Vissa kryptofunktioner med offentlig nyckel som är lika svårhanterliga som faktorisering. — 1985.
Kwangio Kim (Red.). Public Key Kryptografi. - 1992. - S. 1-17.