Lucifer (salaus)

Lucifer on 1970 - luvun IBM -  tutkimusprojekti kryptografisesti vahvan lohkosalauksen luomiseksi . Tutkimuksen tulokset johtivat kahden menetelmän luomiseen halkeamattomien symmetristen salausten rakentamiseen - Feistel-verkkoon ja permutaatio-permutaatioverkkoon . "Lucifer" loi perustan nykyaikaiselle symmetriselle kryptografialle. Horst Feistel ja Don Coppersmith , joista tuli myöhemmin tunnettuja kryptografeja , osallistuivat projektiin . "Luciferin" kehitys johti DES-algoritmin luomiseen .   

Historia

Algoritmin ensimmäinen versio vuodelta 1971 käytti 48-bittisiä lohkoja ja avaimia, ja se perustui SP-verkkoihin. Algoritmin myöhempi muunnos patentoitiin saman vuoden marraskuussa ( US-patentti 3 796 830 ; marraskuu 1971), ja siinä käytettiin Feistelin verkkoa . Patentti sisältää sekä kuvauksen itse algoritmista että Feistel-verkosta. Tämä salaus käytti 64-bittisiä avaimia ja 32-bittisiä lohkoja. Ja lopuksi, viimeisin versio ehdotettiin vuonna 1973, ja se toimi 128-bittisillä lohkoilla ja avaimilla.

Ensimmäinen versio

Kesäkuun 1971 näytteen Lucifer-algoritmin rakenne on SP-verkko (tai substituutio-permutaatioverkko) - kahden peräkkäisen kerroksen "sandwich". Ensimmäinen kerrostyyppi on 128 bitin P-lohko, jota seuraa toinen kerros, joka koostuu 32 moduulista, joista kukin koostuu kahdesta 4-bittisestä S-lohkosta, joiden vastaavat tulot on oikosuljettu ja sama arvo syötetään ne edellisestä tulostekerroksesta. Mutta itse korvauslohkot ovat erilaisia ​​(ne eroavat korvaustaulukoista). Moduulin ulostulo vastaanottaa arvoja vain yhdestä S-laatikosta, mikä nimenomaan määräytyy avaimen yhdellä bitillä, jonka numero vastasi rakenteen S-laatikon numeroa. Kuvassa on esitetty algoritmin yksinkertaistettu kaavio pienemmällä bittisyvyydellä ja epätäydellisellä määrällä kierroksia. Se käyttää 16 S-box-valitsinta (yhteensä 32 S-laatikkoa), joten tämä malli käyttää 16-bittistä avainta.

Tarkastellaan nyt kuinka salateksti muuttuu yllä olevassa algoritmissa, kun vain yksi bitti muuttuu. Yksinkertaisuuden vuoksi otamme S-laatikoiden vaihtotaulukot siten, että jos kaikki nollat ​​syötetään S-laatikon tuloon, tulos on kaikki nollia. Todellisissa järjestelmissä tällaisia ​​substituutiotaulukoita ei käytetä, koska ne yksinkertaistavat suuresti kryptanalyytikon työtä, mutta esimerkissämme ne havainnollistavat selkeästi vahvaa merkkien välistä suhdetta vaihdettaessa yhtä bittiä salatusta viestistä. Voidaan nähdä, että ensimmäisestä P-lohkosta johtuen ainoa yksikkö siirtyy lohkon keskelle, sitten seuraava epälineaarinen S-lohko "kertoi" sen ja jo kaksi yksikköä muuttaa sijaintiaan seuraavan johdosta. P-lohko jne. Salauslaitteen lopussa vahvan symbolien välisen yhteyden ansiosta lähtöbiteistä tuli monimutkainen toiminto tulobitteistä ja käytetystä avaimesta. Keskimäärin puolet biteistä on "0" ja puolet "1" lähdössä.

Toinen ja kolmas versio

Algoritmin seuraava versio käytti Feistel -verkkoa SP-verkon sijaan . Feistel-verkko on ytimenään vaihtoehto SP-verkoille ja sitä käytetään paljon laajemmin. Teoreettisesta näkökulmasta pyöreä salaustoiminto voidaan pelkistää SP-verkkoon, mutta Feistel-verkko on käytännöllisempi, koska salaus ja salauksen purku voidaan suorittaa samalla laitteella, mutta käänteisessä avainten järjestyksessä. Algoritmin toinen ja kolmas versio (käyttivät Feistel-verkkoa) toimivat 32-bittisillä lohkoilla 64-bittisellä avaimella ja 128-bittisillä lohkoilla 128-bittisillä avaimilla. Uusimmassa (kolmannessa) versiossa pyöreä salaustoiminto oli järjestetty hyvin yksinkertaisesti - ensin salattu alilohko kuljetettiin 4-bittisten S-laatikoiden kerroksen läpi (samanlainen kuin kerrokset SP-verkoissa, vain S-laatikko on vakio ja ei riipu avaimesta), sitten siihen modulo 2 lisättiin pyöreä avain, jonka jälkeen tulos kuljetettiin P-lohkon läpi.

Muistiinpanot

Kirjallisuus

• Alan G. Konheim. Tietokoneturva ja kryptografia . - Amerikan Yhdysvallat: WILEY, 2007. - S.  283-287 . — 544 s. — ISBN 978-0-471-94783-7 .
• Horst Feistel. Salaus ja tietokoneiden yksityisyys // Scientific American . - 1973. - Voi. 228, nro 05. - S. 15-23.
• Sergei Panasenko. salausalgoritmit. Erikoisopas. - Pietari: BHV-Petersburg, 2009. - S. 301-312. — 576 s. — ISBN 978-5-9775-0319-8 .

Linkit

• Horst Feistel. Kryptografia ja tietokoneturvallisuus käännös Andrey Vinokurov