Krypteringsalgoritme

Fra Wikipedia, den frie encyklopædi

En krypteringsalgoritme eller chiffer (eng. cipher, fr. chiffre) er en kryptografisk algoritme der entydigt omsætter en besked, klarteksten (eng. plaintext), til krypteret form, chifferteksten (eng. ciphertext), ved hjælp af en nøgle, krypteringsnøglen (eng. encryption key), samt en tilsvarende algoritme der går den modsatte vej. Den første proces kaldes kryptering, den anden dekryptering. Nøglen til de to processer er ikke nødvendigvis de samme. Algoritmen kan være af ikke-matematisk karakter, men er som oftest matematisk.

Med moderne computere har kryptering bevæget sig fra efterretningstjenesternes domæne og ud til almindelige brugere. De fleste e-mail programmer kan sættes op til at kryptere og signere den afsendte e-mail. På denne måde kan meddelelsen ideelt set kun læses af den tilsigtede modtager.

Under 2. verdenskrig brugte den tyske marine en kryptografisk algoritme, hvis succes desværre gav årsag til mange skibsforlis, idet u-både ved hjælp af denne modtog oplysninger om de allieredes bevægelser. Algoritmen hed Enigma, og dette ord er blevet nærmest synonymt for kodesprog til krigsmæssig anvendelse.

[redigér] Basale operationer

[redigér] Transposition

Transposition flytter enheder (f.eks. tegn eller ord) af klarteksten til en anden position, dvs. rækkefølgen af enhederne ændres, men enhederne selv ændres ikke. Matematisk set anvendes en bijektiv funktion på enhedernes positioner. Ved dekryptering foretages blot den modsatte operation. Transpositionen kan være afhængig af krypteringsnøglen, i så fald er denne "opskriften" på transpositionen.

[redigér] Permutation

Permutation er et specialtilfælde af transposition. Her vælger man en permutation af en vis længde, der så anvendes på klarteksten i blokke af denne længde. Jo længere permutationen er, desto sikrere er algoritmen. Teoretisk kan ethver transpositionsalgoritme beskrives som en permutation, men dette er ofte ikke praktisk.

[redigér] Substitution

Substitution erstatter de enkelte enheder med andre symboler eller enheder efter et fastlagt mønster, dvs. enhederne ændres, men deres positioner gør ikke (modsat transpositionpermutation ovenfor). Ved dekryptering substitueres den modsatte vej. Substitutionen kan være afhængig af krypteringsnøglen, i så fald er denne "opskriften" på substitutionen.

Hvis substitutionen opererer på enkelte tegn kaldes den simpel; hvis der opereres på grupper af tegn kaldes substitutionen polygrafisk. Hvis der anvendes samme substitution på hele klarteksten kaldes substitutionen monoalfabetisk, hvis substitutionen ændrer sig undervejs kaldes den polyalfabetisk. Ved homofonisk substitution anvendes mere en ét symbol for hver enhed i klarteksten for at gøre kryptoanalyse sværere.

[redigér] Klassiske krypteringsalgoritmer

[redigér] Cæsaralgoritmen

Cæsaralgoritmen flytter hvert bogstav et antal pladser ned i alfabetet. Eksemplet viser et skift på tre pladser, således at et B i klarteksten bliver til et E i cifferteksten.

Cæsaralgoritmen er et specialtilfælde af substitution. Hvert bogstav erstattes med et bogstav et antal pladser længere nede i alfabetet. Nøglen er antallet af pladser der flyttes.

Et shift cipher for den engelske alfabet er givet ved

• e(x) = x+K modulus 26
• d(x) = x-K modulus 26

F.eks. i teksten "cæsar" med K=3 bliver "c" til "G", "æ" til "A" osv., hvilket giver teksten: "GAVDU". Cæsaralgoritmen brydes relativt let ved frekvensanalyse.

[redigér] Monoalfabetisk substitution

I monoalfabetisk substitution erstattes hver bogstav med et andet, f.eks. efter en tabel som denne:

abcdefghijklmnopqrstuvwxyzæøå
SMFKÆQCPHEALGXÅZYWNUBJDRVTIOØ

Således bliver "cæsar" til "FINSW". En nemmere måde at anvende substitution er at benytte et kodeord, der skrives først uden at gentage bogstaver, hvorefter man tager de ubenyttede bogstaver i rækkefølge. Således får man ved brug af nøglen "MÅNESKIN":

abcdefghijklmnopqrstuvwxyzæøå
MÅNESKIABCDFGHJLOPQRTUVWXYZÆØ

Som cæsaralgoritmen brydes monoalfabetisk substitution relativt let med frekvensanalyse.

[redigér] Polyalfabetisk substitution - Vigenèrealgoritmen

Et tabula recta til brug for Vigenèrealgoritmen

I polyalfabetisk substitution erstattes det samme bogstav med forskellige bogstaver. Et eksempel på polyalfabetisk substitution er Vigenèrealgoritmen (opkaldt efter Blaise de Vigenère). Her vælges et ord som nøgle, og hvert bogstav i nøglen bruges skiftevis til at vælge en substitutionstabel. Typisk benyttes et tabula recta (se illustration), hvilket betyder at alle substitutionstabeller svarer til en Cæsaralgoritme (se ovenfor). Er kodebogstavet f.eks. "E", benyttes en cæsaralgoritme med et skift på fire pladser. Et eksempel med nøglen "VIGENERE":

Klartekst:    angribveddaggry
Nøgle:        VIGENEREVIGENER
Chiffertekst: VVMVVFMIYLGKTVP

Læg mærke til at hele fire bogstaver krypteres til "V", mens de to "d"'er i klarteksten krypteres forskelligt.

Vigenère algoritmen brydes ved først at lave en Kasiski test, der fastlægger længden af nøglen. Derefter benyttes frekvensanalyse på de bogstaver i chifferteksten der er oversat med det samme bogstav i nøglen.

[redigér] Autokey

[redigér] Moderne kryperingsalgoritmer

[redigér] Symmetrisk kryptering

I symmetrisk kryptering benyttes samme nøgle til kryptering og dekryptering.

Blandt ofte anvendte symmetriske krypteringsalgoritmer er DES, Triple DES (3DES, der bl.a. bruges i Dankort-systemet), IDEA og AES.

[redigér] Asymmetrisk kryptering

I asymmetrisk kryptering (også kendt som public key-kryptografi) benyttes som oftest to forskellige nøgler (typisk opdelt som den hemmelige og den offentlige nøgle) til kryptering og dekryptering. Der findes også algoritmer til asymmetriske kryptering, der benytter sig udelukkende af private nøglepar, men disse er ikke ofte anvendt. Nøgleparret er som Yin og Yang; har den ene nøgle krypteret en bid information, kan kun den anden dekryptere den. Det er bemærkelsesværdigt, at ikke engang den nøgle, der har krypteret informationen, kan dekryptere cifferteksten.

Det kan umiddelbart undre, at asymmetrisk kryptering kan virke. En analogi fra den virkelige verden kan illustrere princippet: A ønsker at kunne modtage en hemmelig leverance fra B. En tredjepart C må ikke kunne få fat i den hemmelige leverance, og når først den er afsendt, må B heller ikke kunne få fat i leverancen. A sender en hængelås til B, men beholder nøglen. B låser leverancen nede i en kasse og sender den til A. A åbner kassen med sin nøgle.

De mest kendte asymmetriske krypteringsalgoritmer er RSA og Diffie-Hellmann.

[redigér] Diverse noter

• Af sikkerhedsgrunde er det ofte hensigtsmæssigt at komprimere data inden kryptering, idet redundans vil give en tredjepart bedre mulighed for at bryde krypteringen.
• Det eneste krypteringssystem, der beviseligt er 100 % sikkert, er det såkaldte one-time pad. Her er nøglen er lige så lang som klarteksten, og nøglen må ikke genbruges. Dette er for besværligt til de fleste praktiske anvendelser, men er blevet anvendt i praksis, bl.a. til den "Røde telefon", der forbandt Det Hvide Hus i Washington med Kreml i Moskva.
• Kryptering bliver sjældent brudt pga. svagheder i selve algoritmen. Oftest drejer det sig om fejl i implementeringen eller andre menneskelige fejl.
• En kryptografisk algoritmes styrke skal typisk måles mod omkostningen ved at bryde den i bredeste forstand. Således er omkostninger den "billigste" af flere muligheder, der ud over at finde fejl i algoritmen og benytte brute force angreb, omfatter at finde personen der kender nøglen og tvinge den ud af ham/hende.