Williamsin salausjärjestelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 20. joulukuuta 2014 tarkistetusta versiosta . tarkastukset vaativat 11 muokkausta .

Williams Cryptosystem on julkisen avaimen salausjärjestelmä, jonka Hugh Cowie Williams loi vuonna 1984.

Historia

Algoritmi kehitettiin vuonna 1984 vaihtoehdoksi tunnetummalle RSA:lle. Kehityksen tarkoituksena oli päästä eroon kryptojärjestelmän haavoittuvuuksista.

Tietoja algoritmista

Minkä tahansa kryptojärjestelmän osalta on toivottavaa, että todistetaan, että sen rikkoutumisen laskennallinen monimutkaisuus on samanlainen kuin sellaisen ongelman laskennallinen monimutkaisuus, jota ei tällä hetkellä voida ratkaista ennakoitavissa olevassa ajassa. Williamsin salausjärjestelmä perustuu RSA:n tapaan oletukseen, että suuria lukuja on vaikea faktoroida, ja on todistettu, että minkä tahansa salatekstin murtamiseen alustavan kryptaanalyysin avulla (jossa on vain julkinen avain), on välttämätöntä tekijöitä [ 1] , eli ratkaise yhtälö ja . Tätä väitettä ei ole todistettu RSA - järjestelmälle . Tekijöintiongelman laskennallista monimutkaisuutta ei tunneta, mutta sen uskotaan olevan melko korkea. Mutta kuten RSA, Williamsin salausjärjestelmä on alttiina salakirjoitushyökkäyksille. $pq=n$ $s$ $q$

Algoritmin kuvaus

Vaikka Williamsin järjestelmäalgoritmi ei olekaan laskennallisesti monimutkaisempi kuin RSA, sitä on paljon hankalampi kuvata. Sille on olemassa lemma [2] , joka kuvataan matemaattista laitteistoa käsittelevässä osiossa - sillä on keskeinen rooli tässä kryptojärjestelmässä.

Matemaattinen laite

Aluksi on määriteltävä terminologia - se on lainattu neliökenttien teoriasta , mutta salausjärjestelmässä tarvitaan vain alkeellisia tietoja. Harkitse elementtiä

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

missä ovat kokonaislukuja, ja on ehdollinen elementti, jonka neliö on . Sitten seuraavat kaavat ovat voimassa: $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})

Luvun konjugaattia kutsutaan $\alpha$

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

Määrittelemme myös funktioita, jotka auttavat meitä ilmaisemaan tämän luvun tehon. Päästää

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

niin u voidaan ilmaista seuraavasti: $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}})

Viimeinen lauseke on vain ymmärtämisen helpottamiseksi. Koska funktiot on määritelty pareille , ne eivät sisällä . Jos nyt oletetaan, että , voimme kirjoittaa seuraavat toistuvuussuhteet: $(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))

Nämä kaavat on suunniteltu nopeasti laskemaan ja . Koska ja , se ei myöskään riipu . $X_{i}$ $Y_{i}$ $X_{0}=1$ $X_{1}=a$ $X_{i}(\alpha )$ $b$

Lemma

Antaa olla kahden parittoman alkuluvun tuote ja ; ovat kokonaislukuja, jotka täyttävät yhtälön . Anna Legendre-symbolien täyttää kongruenssit $n$ $s$ $q$ $a,b,c$ $a^{2}-cb^{2}=1{\pmod n}$ $\delta _{p}=$ $\textstyle \left({{\frac {c}{p))}\oikea)$ $\delta _{q}=\textstyle \left({{\frac {c}{q))}\oikea)$

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

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

Olkoon lisäksi ja Jacobi-symboli yhtä suuri kuin 1. Merkitään $gcd(cb,n)=1$ $\textstyle \left({{\frac {2(a+1)}{n))}\oikea)$

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

ja oletamme sen ja täytämme vertailun $e$ $d$

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

Näillä oletuksilla

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

Avaimen luominen

Ensin valitaan kaksi alkulukua ja ja niiden tulo lasketaan . Luettelon avulla valitaan luku siten, että Legendre-symbolit täyttävät lemman asetetut ehdot. Sitten (myös valinnalla) määritetään numero siten, että Jacobi-symboli $s$ $q$ $n$ $c$ $\delta _{p}$ ${\displaystyle \delta _{q))$ $s$

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

ja Numero valitaan samalla tavalla kuin lemassa: $gcd\textstyle \left(s,n\right)=1.$ $m$

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

Sitten valitaan luvut , jotka täyttävät lemman asetetut ehdot. Valitsemme satunnaisen, esimerkiksi , ja laskemme kaavan mukaan $d, e$ $d:gcd\textstyle \left(d,m\right)=1$ $e$

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

Sitten on julkinen avain ja yksityinen avain. ${n,e,c,s}$ ${p,q,m,d}$

Salaus

Kaikki laskelmat tässä ovat modulo . Tässä oleva merkintä tarkoittaa Esitetään pelkkä teksti numerona . Määrittele ja : jos Jacobi-symboli on yhtä suuri kuin , niin $n$ $a+b{\sqrt c}{\pmod n}$ $(a\mod n)+(b\mod n){\sqrt c}.$ $w\in{2,3,...,n-1}$ $\gamma$ $b_{1}$ $\textstyle \left({{\frac {w^{2}-c}{n))}\oikea)$ $+1$

b_{1}=0

\gamma =w+{\sqrt c},

muuten määrittelemme tuotteen kautta $\gamma$

b_{1}=1

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

Sitten on helppo varmistaa, että Jacobi-symboli

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

joka varmistetaan suoralla laskennalla (toisessa tapauksessa ottaen huomioon Jacobi-symbolin valinta ja moninkertaisuus ). Seuraavaksi löydämme numeron $s$

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

Esitetään se muodossa, joka täyttää lemman asetetut ehdot. Todellakin, ne täyttävät rakennusehdot, ja $\alpha$ $\alpha =a+b{\sqrt c}.$ $\alpha$ $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}

Viimeisestä kaavasta seuraa, että

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

Kun se on saatu , se tulee salata eksponentioimalla - tulos voidaan esittää ja joka voidaan [3] nopeasti (operaatioiden lukumäärälle järjestyksessä ) löytää toistuvia kaavoja käyttäen. Otetaan käyttöön merkintä $\alpha,$ $e$ $X_{e}(\alpha )$ $Y_{e}(\alpha ),$ $\log e$

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

Silloin kryptoteksti on kolminkertainen numeroista missä $(E,b_{1},b_{2}),$ $b_{2}=a\mod 2.$

Salauksen purku

Salauksen purku on helpompaa. Ensin laskettu

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

mitä hyökkääjä voi tehdä. Mutta lopullista salauksen purkamista varten on tarpeen laskea, kuten lemmassa esitetään - huolimatta siitä, mitä pidetään salassa. $\alpha ^{{2ed}}$ $d$

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

Viestissä välitetty numero ilmaisee, mikä merkeistä on oikein - se, joka antaa parillisen vai joka antaa parittoman. Numero osoittaa, tuleeko tulos kertoa luvulla . Tämän seurauksena saamme numeron $b_{2},$ $b_{1}$ $(s-{\sqrt c})/(s+{\sqrt c})$

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

Ja voimme helposti löytää lähdetekstin, joka viimeistelee salauksen purkuprosessin.

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

Turvallisuus

Kuten RSA, salausjärjestelmään voidaan hyökätä valitun salatekstin perusteella . Oletetaan, että kryptoanalyytikko on löytänyt algoritmin, joka mahdollistaa kryptotekstin purkamisen todennäköisyydellä. Sitten hän voi tehdä seuraavan: $\delta>0$

1. Valitse numero siten, että Jacobi-symboli ;

\phi

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

2. Salaa , mutta siten, että mainittu Jacobi-symboli on yhtä suuri kuin ja , vastaanotettuaan kryptotekstin lähdössä ;

\phi

+1

b_{1}=0

(E,0,b_{2})

3. Pura vastaanotetun kryptotekstin salaus saadaksesi jonkin verran .

\psi \neq \phi

Sitten todennäköisyydellä kryptanalyytikko voi saada $\delta>0$

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

tai

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

Tämä mahdollistaa salausjärjestelmän jakamisen ja murtamisen. $n$

Suorituskyky

Avaimen luomisen jälkeen päälaskelmat tapahtuvat nostettaessa luku potenssiin, ja tämä voidaan tehdä modulokertolaskuissa, joista jokainen tapahtuu yhteenlaskuoperaatioissa, jotka puolestaan suoritetaan vakionopeuden alkeissummausoperaatioissa - eli , in , samalla nopeudella, joka on RSA:n käyttämiseen vaaditun kokonaisluvun modulon eksponentio. $\alpha$ $O(\log e)$ $O(\log e)$ $O(\log e)$ $O(\log ^{3}e)$

Esimerkki

Avaimen luominen

Valitaan esimerkiksi ja , jonka tuote on . Koska $p=11$ $q=13$ $n=143$

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

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

Voit valita . Lisäksi, jos valitsemme , saamme $c = 5$ $s = 2$

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

Mikä täyttää lauseen ehdon. Seuraavaksi saamme

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

Ja lopuksi valitsemme salauksen ja salauksen purkamisen eksponentit: since

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

Voi valita

e=23

d=16

Salaus

Olkoon alkuperäinen teksti . Koska $\omega =21$

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

Meillä on , ja $b_{1}=0$ $\gamma =21+{\sqrt {5}}$

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

Koska se on outoa, saamme . Laskettuamme ja saamme $125$ $b_{2}=1$ $X_{23}(\alpha )=68$ $Y_{23}(\alpha )=125$

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

Näin ollen salateksti on kolmiosainen . ${\näyttötyyli (28,1,1)}$

Salauksen purku

Nyt sinun pitäisi laskea : ${\displaystyle \alpha ^{2e))$

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

Koska , laskemme myös $d=16$

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

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

Koska , sitten on pariton ja $b_{2}=1$ $a$

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

Ottaen huomioon, että salatekstin toinen komponentti on , päättelemme, että . Tässä tapauksessa $b_{1}=0$ $\alpha '=\alpha$

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

Siten saimme , joka oli alkuperäinen selväkieli. $\omega =21$

Muistiinpanot

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

Kirjallisuus

Hugh C. Williams. Jotkut julkisen avaimen kryptotoiminnot ovat yhtä vaikeita kuin faktorointi. – 1985.
Kwangio Kim (Toim.). Julkisen avaimen kryptografia. - 1992. - S. 1-17.