Trivium (salakirjoitus)

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

Trivium on symmetrinen synkroninen suoratoiston salausalgoritmi, joka keskittyy ensisijaisesti laitteistototeutukseen joustavalla tasapainolla nopeuden ja elementtien määrän välillä, jolla on myös mahdollisuus varsin tehokkaaseen ohjelmistototeutukseen.

Salaus otettiin käyttöön joulukuussa 2008 osana eurooppalaisen eSTREAM- projektin profiilia 2 (hardware oriented ciphers). Salauksen kirjoittajat ovat Christophe De Kannier ja Bart Prenel.

Tämä virtasalaus tuottaa enintään bittiä lähtövirtaa avaimen 80 bitistä ja IV :n (alustusvektorin) 80 bitistä. Tämä on eSTREAM-projektin yksinkertaisin salaus, joka osoittaa erinomaisia tuloksia kryptografisen vakauden suhteen. $2^{64}$

Trivium sisältyy ISO/IEC 29192-3 -standardiin kevyenä stream-salauksena.

Kuvaus

Triviumin alkutila on 3 siirtorekisteriä, joiden kokonaispituus on 288 bittiä. Jokainen kellojakso muuttaa bittejä siirtorekistereissä myötäkytkennän ja takaisinkytkennän epälineaarisen yhdistelmän avulla. Salauksen alustamiseksi avain K ja alustusvektori IV kirjoitetaan kahteen kolmesta rekisteristä ja algoritmi suoritetaan 4x288 = 1152 kertaa, mikä takaa, että jokainen alkutilan bitti riippuu avaimen jokaisesta bitistä ja jokaisesta bitistä. alustusvektorista.

Alustusvaiheen läpäisyn jälkeen jokainen sykli luodaan avainvirran Z uusi jäsen , joka läpäisee XOR -proseduurin tekstin seuraavan jäsenen kanssa. Salauksen purkuprosessi tapahtuu käänteisessä järjestyksessä - jokainen salatekstin jäsen XOR-koodataan jokaisen avainvirran Z jäsenen kanssa . [yksi]

Algoritmi

Suoratoista salauksia

Trivium luo Z -sekvenssin , niin sanotun avainvirran, enintään bitin pituisen. Viestin salaamiseksi on välttämätöntä XOR XOR-viesti ja avainvirta. Salauksen purku suoritetaan samalla tavalla, XOR-toiminto suoritetaan salatekstistä ja avainvirrasta. $N\leq 2^{64}$

Alustus

Algoritmi alustetaan lataamalla 80-bittinen avain ja 80-bittinen alustusvektori 288-bittiseen alkutilaan. Alustus voidaan kuvata seuraavalla pseudokoodilla .

(s_{1},s_{2},...,s_{93})\leftarrow (K_{1},...,K_{80},0,...,0)

(s_{94},s_{95},...,s_{177})\leftarrow (IV_{1},...,IV_{80},0,...,0)

(s_{178},s_{179},...,s_{288})\leftarrow (0,...0,1,1,1)

{\mbox{for}}\ i=1\ {\mbox{to}}\ 4\cdot 288\ {\mbox{do}}

{\displaystyle t_{1}\leftarrow s_{66}+s_{91}\cdot s_{92}+s_{93}+s_{171))

{\displaystyle t_{2}\leftarrow s_{162}+s_{175}\cdot s_{176}+s_{177}+s_{264))

{\displaystyle t_{3}\leftarrow s_{243}+s_{286}\cdot s_{287}+s_{288}+s_{69))

(s_{1},s_{2},...,s_{93})\leftarrow (t_{3},s_{1},...,s_{92})

(s_{94},s_{95},...,s_{177})\leftarrow (t_{1},s_{94},...,s_{176})

(s_{178},s_{179},...,s_{288})\leftarrow (t_{2},s_{178},...,s_{287})

{\mbox{end for))

Alustusmenettely varmistaa, että jokainen alkutilan bitti riippuu avaimen jokaisesta bitistä ja jokaisesta alustusvektorin bitistä. Tämä vaikutus saavutetaan jo 2 täyden ajon jälkeen (2*288 syklin suoritusta). 2 lisäsyöttöä on suunniteltu mutkistamaan bittisuhteita. Esimerkiksi nollaavaimesta ja alustusvektorista saadun avainvirran Z ensimmäisillä 128 tavulla on suunnilleen sama määrä 1:itä ja 0:ita tasaisesti jakautuneina. Jopa yksinkertaisimmilla ja identtisillä avaimilla Trivium-algoritmi tuottaa sarjan lukuja, jotka ovat lähellä satunnaista.

Avainvirran ensimmäiset 128 tavua, luotu noloista K ja IV heksadesimaalimuodossa 0000000 e0 fb 26 bf 59 58 1b 05 7a 51 4e 2e 9f 23 7f c9 0000010 32 56 16 03 07 19 2d cf a8 e7 0f 79 b2 a1 cd e9 0000020 52 f7 03 92 68 02 38 b7 4c 2b 75 1a a2 9a 9a 59 0000030 55 28 98 49 74 6e 59 80 80 03 4c 1a a5 b5 f2 d4 0000040 34 69 bb 86 ca 52 15 b3 ae 80 12 69 73 55 9a 31 0000050 b2 6c 0e f5 16 40 20 d6 30 7f 4e 3f 48 16 dc 24 0000060 25 5c mainos c4 10 a1 c9 1b bb e8 01 4e dc fc 2e 27 0000070 9e fa ae 02 a2 48 05 b2 2e fb f4 4f 27 76 56 27 0000080 3e 5e b7 06 4e e6 4a 57 7b ad a2 3a 1c 52 ff 48 0000090 f3 92 f8 87 ff 98 aa 87 e6 bf f6 19 38 3c ff 19 00000a0 3f 0a a5 fd 01 ec d0 d8 fa f0 fa 87 09 a1 4e ee 00000b0 63 29 9f 9b 31 ef 95 a5 c7 76 19 8d c7 e0 df 55 00000c0 1b 0f 50 e9 b8 91 85 ea 06 7b d5 2a ad 2b 77 f4 00000d0 ac 84 9b 6d 3f 2e a9 85 99 d7 04 95 02 33 fd f0 00000e0 b7 f8 5b 6e b7 c8 f0 b4 46 aa 20 cd a0 dd dd 4f

Kuten näette, 4 alustusjakson jälkeen soluihin kirjoitetut yksiköt vaikuttivat kaikkiin muihin alkutilan bitteihin, joten jopa yksinkertaisimmilla ja identtisillä avaimilla viestin jokainen tavu muuttuu salauksen seurauksena. algoritmi. $s_{286}$ $s_{287}$ $s_{288}$

Algoritmin toiminta

Virtageneraattori käyttää 15 bittiä 288-bittisestä alkutilasta muuttaakseen tilasta 3 bittiä ja laskeakseen 1 bitin avainvirrasta . Algoritmin tuloksena voidaan saada jopa bittejä avainvirrasta . Algoritmi voidaan kuvata seuraavalla pseudokoodilla. $z_{i}$ $N\leq 2^{64}$

{\mbox{for}}\ i=1\ {\mbox{to}}\ N\ {\mbox{do}}

{\displaystyle t_{1}\leftarrow s_{66}+s_{93))

{\displaystyle t_{2}\leftarrow s_{162}+s_{177))

t_{3}\leftarrow s_{243}+s_{288}

{\displaystyle z_{i}\leftarrow t_{1}+t_{2}+t_{3))

{\displaystyle t_{1}\leftarrow s_{66}+s_{91}\cdot s_{92}+s_{93}+s_{171))

{\displaystyle t_{2}\leftarrow s_{162}+s_{175}\cdot s_{176}+s_{177}+s_{264))

{\displaystyle t_{3}\leftarrow s_{243}+s_{286}\cdot s_{287}+s_{288}+s_{69))

(s_{1},s_{2},...,s_{93})\leftarrow (t_{3},s_{1},...,s_{92})

(s_{94},s_{95},...,s_{177})\leftarrow (t_{1},s_{94},...,s_{176})

(s_{178},s_{179},...,s_{288})\leftarrow (t_{2},s_{178},...,s_{287})

{\mbox{end for))

Tässä pseudokoodissa kaikki laskutoimitukset suoritetaan modulo 2. Eli yhteen- ja kertolaskuoperaatiot ovat XOR- ja AND -operaatioita .

Jakso

Avaimen virtausjaksoa on vaikea määrittää alkutilan muutosten epälineaarisen luonteen vuoksi. Vaikka kaikki liipaisimet olisi AND-ed, mikä johtaa täysin lineaariseen piiriin, voidaan osoittaa, että mikä tahansa avain- ja alustusvektoripari johtaa avainvirran generointiin, jonka jakso on järjestyksessä (joka ylittää jo vaaditun avainvirran pituuden ). $2^{96-3}-1$ $2^{64}$

Jos oletetaan, että Trivium alkaa generoida satunnaista avainvirtaa pienen iteraatiomäärän jälkeen, niin kaikki generoidut sekvenssit pituuteen asti ovat yhtä todennäköisiä. Sekä todennäköisyys, että avain/alustusvektoripari muodostaa avainvirran, jonka jakso on alle noin [2] . $2^{288}$ $2^{80}$ $2^{-208}$

Trivium-perheen salakirjoitukset

Tämän salauksen modifikaatiot eroavat siirtorekisterien lukumäärästä ja pituudesta.

Univium

Univium-virtasalaus koostuu yhdestä siirtorekisteristä, ja koodaukseen tarvitaan vain rekisterin pituista avainta. [yksi]

Bivium

Yhdessä Triviumin kanssa sen kirjoittajat ehdottivat Bivium-salausta, joka toteuttaa vain 2 siirtorekisteriä, joiden kokonaispituus on 177 bittiä. Alustusprosessi on samanlainen kuin Triviumissa. Jokaisessa jaksossa 2 tilabittiä muutetaan ja avainvirran uusi bitti luodaan. Avainvirran Z sukupolven mukaan on olemassa 2 versiota: Bivium-A ja Bivium-B (Bivium). Bivium-A:ssa toteutetaan uuden jäsenen Z suora riippuvuus muuttuneesta tilabitistä , sen erosta Bivium-B:ssä (Bivium) . [3] ${\displaystyle z_{i}\leftarrow t_{1))$ ${\displaystyle z_{i}\leftarrow t_{1}+t_{2))$

Trivium-lelu ja Bivium-lelu

Leluversiot saatiin pienentämällä rekisterien pituuksia, mikä vähensi algoritmin laskennallista monimutkaisuutta, mutta säilytti kaikki matemaattiset ominaisuudet. Jokaisen rekisterin pituus pieneni 3 kertaa ja Bivium-lelu koostui myös vain kahdesta rekisteristä.

Jokainen Trivium-salauksen modifikaatio luotiin yksinkertaistamaan sen matemaattista kuvausta, jolla on enemmän opetuksellinen tarkoitus kuin tarkoitus käyttää niitä tietoturvatyökaluissa. [neljä]

Suorituskyky

Algoritmin standardilaitteistototeutus vaatii 3488 porttia ja tuottaa 1 bitin avainvirtaa kellojaksoa kohden. Mutta koska jokainen uusi bitin tila ei muutu ainakaan 64 kierroksen ajan, niin 64 tilaa voidaan generoida rinnakkain, kun logiikkaelementtien määrä kasvaa 5504:ään. Myös erilaiset suorituskyvyn vaihtelut ovat mahdollisia elementtien lukumäärästä riippuen. käytetty.

Tämän algoritmin ohjelmistotulkinta on myös varsin tehokas. Triviumin C -toteutus AthlonXP 1600+:ssa tarjoaa yli 2,4 Mbps salauksen

Turvallisuus

Toisin kuin varhaisissa stream-salauksissa, kuten RC4 , Trivium-algoritmissa on yksityisen avaimen ( K ) lisäksi myös alustusvektori ( IV ), joka on julkinen avain. IV:n käyttö mahdollistaa useita itsenäisiä salaus-/salauksenpurkuistuntoja käyttämällä vain yhtä avainta ja useita alustusvektoreita (yksi kutakin istuntoa kohti). On myös mahdollista käyttää useita alustusvektoreita samalle istunnolle käyttämällä uutta IV :tä jokaiselle uudelle viestille.

Tällä hetkellä ei tunneta hyökkäysmenetelmiä tätä algoritmia vastaan, jotka olisivat tehokkaampia kuin peräkkäinen luettelointi . Tämän hyökkäyksen monimutkaisuus riippuu viestin pituudesta ja on suuruusluokkaa . $2^{120}$

Hyökkäysmenetelmistä on tutkimuksia (esim. kuutiohyökkäys [5] ), jotka ovat teholtaan lähellä laskemista. Lisäksi on olemassa hyökkäysmenetelmä, jonka avulla voit palauttaa K :n IV :stä ja avainvirrasta. Tämän hyökkäyksen monimutkaisuus on yhtä suuri ja pienenee hieman yhdellä avaimella käytettävien alustusvektorien määrän kasvaessa. Hyökkäykset ovat mahdollisia myös avainvirran näennäissatunnaisen sekvenssin tutkimuksella kuvioiden löytämiseksi ja virran myöhempien bittien ennustamiseksi, mutta nämä hyökkäykset vaativat monimutkaisten epälineaaristen yhtälöiden ratkaisun. Tällaisen hyökkäyksen pienin monimutkaisuus on [6] [7] $2^{135}$ $2^{164}$

Tutkimusmenetelmät

Melkein kaikki Triviumin hakkerointisaavutukset ovat yrityksiä käyttää hyökkäyksiä, jotka on suoritettu onnistuneesti algoritmin katkaistuihin versioihin [1] . Usein tutkittavana käytetään Bivium-algoritmin versiota, joka käyttää vain kahta siirtorekisteriä, joiden kokonaispituus on 192 bittiä [1] .

Muistiinpanot

↑ 1 2 3 4 Arkistoitu kopio . Haettu 23. joulukuuta 2009. Arkistoitu alkuperäisestä 25. syyskuuta 2018. (määrätön)
↑ Arkistoitu kopio . Haettu 23. joulukuuta 2009. Arkistoitu alkuperäisestä 20. lokakuuta 2016. (määrätön)
↑ Kaksi triviaalia hyökkäystä Triviumiin | SpringerLink . Haettu 27. heinäkuuta 2018. Arkistoitu alkuperäisestä 27. heinäkuuta 2018. (määrätön)
↑ Arkistoitu kopio . Haettu 10. maaliskuuta 2017. Arkistoitu alkuperäisestä 12. maaliskuuta 2017. (määrätön)
↑ Arkistoitu kopio . Haettu 23. joulukuuta 2009. Arkistoitu alkuperäisestä 17. toukokuuta 2017. (määrätön)
↑ Arkistoitu kopio . Haettu 23. joulukuuta 2009. Arkistoitu alkuperäisestä 26. elokuuta 2016. (määrätön)
↑ Arkistoitu kopio . Haettu 23. joulukuuta 2009. Arkistoitu alkuperäisestä 30. heinäkuuta 2016. (määrätön)

Linkit

Trivium eSTREAM-projektisivulla Arkistoitu 23. syyskuuta 2015 Wayback Machinessa
Algoritmin kuvaus eSTREAM-projektisivulla . Arkistoitu 20. syyskuuta 2015 Wayback Machineen
Virtasalausten rakentamisen periaatteet

Symmetriset salausjärjestelmät
Suoratoista salauksia	A3 A5 A8 Desim F-FCSR Vilja HC-256 KCipher-2 MIKKI MUGI HAUKI Phelix RC4 Kani TIIVISTE LUMI SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistelin verkko	GOST 28147-89 (Magma) blowfish Camellia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra SOPIMUS DES DESX DFC E2 enRUPT FEAL HPC IDEA KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 UusiDES NDS RC5 RC6 SIEMEN Simon Sinopoli jätkä SM4 Speck TEE XTEA XXTEA Raiden RTEA Kolminkertainen DES Kaksi kalaa
SP verkko	Heinäsirkka 3 tapaa ABC AARIA AES (Rijndael) Akelarre Anubis BaseKing Basso Omatic Vyö CRYPTON Timantti 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer esittää Sateenkaari TURVALLISTA HAI NELIÖ Käärme kolme kalaa
Muut	SAMMAKKO NUSH REDOC SC2000 SHACAL CS-Cipher