MADRYGA

MADRYGA (til ære for forfatteren WE Madryga) er en blokkrypteringsalgoritme skabt af V. E. Madriga i 1984.

Egenskaber

Denne algoritme er designet til at gøre det nemt og effektivt at implementere kryptering i software. Algoritmen udfører alle operationer på bytes.

Ved udformningen af algoritmen løste forfatteren følgende problemer:

Klarteksten kan ikke hentes fra chifferteksten uden hjælp af en nøgle (algoritmen er sikker);
Antallet af operationer, der kræves for at bestemme nøglen ud fra den tilgængelige chiffertekst og almindelig tekst, bør være statistisk lig med produktet af antallet af krypteringsoperationer med antallet af mulige nøgler;
Algoritmens fremtrædende karakter påvirker ikke chifferens styrke;
En ændring i en bit af nøglen skal forårsage, for den samme klartekst, en radikal ændring i chifferteksten, og en ændring i en bit af klarteksten skal forårsage, for den samme nøgle, en radikal ændring i chifferteksten;
Algoritmen skal indeholde en ikke-kommutativ kombination af substitutioner og permutationer;
Substitutionerne og permutationerne anvendt i algoritmen skal bestemmes af både input og nøgle;
Redundante plaintext bitgrupper skal være fuldstændig maskeret i chifferteksten;
Længden af chifferteksten skal være lig med længden af klarteksten;
Der bør ikke være nogen simple relationer mellem eventuelle nøgler og funktioner i chifferteksten;
Alle mulige nøgler skal give en stærk chiffer (der må ikke være svage nøgler);
Nøgle- og tekstlængde kan justeres for at opfylde forskellige sikkerhedskrav;
Algoritmen skal tillade effektiv softwareimplementering på store mainframes , minicomputere , mikrocomputere og med diskret logik.

DES-algoritmen opfyldte de første ni krav, men de sidste tre blev nye. De giver denne algoritme mulighed for softwareimplementeringer.

Beskrivelse af algoritmen

Madryga består af to indlejrede løkker. Den ydre løkke gentages otte gange (men dette tal kan øges for at forbedre sikkerheden) og indeholder anvendelsen af den indre løkke til klartekst. Den indre løkke forvandler klarteksten til chiffertekst, der gentages for hver 8-bit blok (byte) af klarteksten. Derfor behandles hele klarteksten otte gange sekventielt af algoritmen.

Den indre sløjfe-iteration fungerer på et 3-byte vindue med data kaldet en arbejdsramme. Dette vindue forskydes med én byte pr. iteration. De første to bytes af arbejdsrammen roteres med et variabelt antal positioner, og den sidste byte er XORed med nogle nøglebits. Efterhånden som arbejdsrammen skrider frem, bliver alle bytes sekventielt "roteret" og XORed med dele af nøglen. Successive rotationer blander resultaterne af tidligere XOR'er og rotationer, og resultatet af XOR påvirker rotationen. Dette gør processen reversibel.

Da hver byte med data påvirker ja-bytes til venstre og en byte til højre, afhænger hver byte med chiffertekst efter otte gange af 16 byte til venstre og otte byte til højre.

Ved kryptering sætter hver operation af den indre sløjfe driftsrammen til den næstsidste tekstbyte og skifter den til den almindelige tekstbyte tredje til venstre for den sidste. Hele nøglen XOReres først med en tilfældig konstant og roteres derefter 3 bit til venstre. De nederste tre bits af arbejdsrammens lave byte bibeholdes og bestemmer rotationen af de resterende to bytes. Den lave byte af arbejdsrammen XOReds derefter med den lave byte af nøglen. Dernæst forskydes foreningen af de to høje bytes cyklisk til venstre med et variabelt antal bit (fra 0 til 7). Til sidst flyttes arbejdsrammen til højre med en byte, og hele processen gentages.

Betydningen af den tilfældige konstant er at omdanne nøglen til en pseudo-tilfældig sekvens. Længden af konstanten skal være lig med nøglens længde. Ved udveksling af data skal abonnenter bruge konstanter af samme længde. For en 64-bit nøgle anbefaler Madriga konstanten 0x0f1e2d3c4b5a6978.

Ved dekryptering vendes processen. Ved hver iteration af den indre sløjfe sættes arbejdsrammen til bytens tredjedel fra venstre for den sidste byte af chifferteksten, og cykler tilbage til den byte, der er to bytes til venstre for den sidste byte af chifferteksten. Både nøglen og de to bytes med chiffertekst roteres til højre i processen, og XOR udføres før rotationerne.

Krypteringsanalyse MADRYGA

Forskere ved Queensland University of Technology har undersøgt Madryga sammen med nogle andre blokcifre. De fandt ud af, at der ikke var nogen oversvømmelseseffekt i denne algoritme til at konvertere almindelig tekst til chiffertekst. Også i mange chiffertekster var procentdelen af enere højere end procentdelen af nuller.

Med et overfladisk bekendtskab med algoritmen kom Eli Biham til følgende konklusioner:

Algoritmen består kun af lineære operationer (cyklisk skift og XOR), lidt modificeret afhængigt af dataene
Dette er intet som kraften i DES S-bokse .
Pariteten af alle bits af chifferteksten og almindelig tekst er uændret og afhænger kun af nøglen. Derfor, givet klarteksten og den tilsvarende chiffertekst, kan man forudsige pariteten af chifferteksten for enhver klartekst.

Noter

Litteratur