Affint chiffer

Det affina chiffer är en typ av monoalfabetisk substitutionschiffer , där varje bokstav i ett alfabet mappas till sin numeriska motsvarighet, krypteras med en enkel matematisk funktion och konverteras tillbaka till en bokstav. Formeln som används innebär att varje bokstav krypterar till en annan bokstav, och tillbaka igen, vilket betyder att chiffret i huvudsak är ett standardsubstitutionskiffer med en regel som styr vilken bokstav som går till vilken. Som sådan har den svagheterna hos alla substitutionschiffer. Varje bokstav är krypterad med funktionen $(ax + b) mod 26$ , där $b$ är storleken på skiftet.

Beskrivning

mappas först bokstäverna i ett alfabet av storleken $m till heltal i intervallet$ $0 ... m - 1$ . Den använder sedan modulär aritmetik för att omvandla det heltal som varje klartextbokstav motsvarar till ett annat heltal som motsvarar en chiffertextbokstav. Krypteringsfunktionen för en enda bokstav är

E(x)=(ax+b){\bmod {m}}

där modul $m$ är storleken på alfabetet och $a$ och $b$ är nycklar till chiffer. Värdet $a$ måste väljas så att $a$ och $m$ är coprime . Dekrypteringsfunktionen är

D(x)=a^{-1}(xb){\bmod {m}}

där $a -1$ är den modulära multiplikativa inversen av $en$ modulo $m$ . Dvs den uppfyller ekvationen

1=aa^{-1}{\bmod {m}}

Den multiplikativa inversen av $a$ existerar endast om $a$ och $m$ är coprime. Utan begränsningen på $en$ kan det därför hända att dekryptering inte är möjlig. Det kan visas på följande sätt att dekrypteringsfunktionen är inversen av krypteringsfunktionen,

{\begin{aligned}D(E(x))&=a^{-1}(E(x)-b){ \bmod {m}}\\&=a^{-1}(((ax+b){\bmod {m}})-b){\bmod {m}}\\&=a^{-1 }(ax+bb){\bmod {m}}\\&=a^{-1}ax{\bmod {m}}\\&=x{\bmod {m}}\end{aligned}}

Svagheter

Eftersom det affina chifferet fortfarande är ett monoalfabetiskt substitutionschiffer, ärver det svagheterna hos den klassen av chiffer. Caesar -chifferet är ett affint chiffer med $a = 1$ eftersom krypteringsfunktionen helt enkelt reduceras till en linjär förskjutning. Atbash -chifferet använder $a = -1$ .

Med tanke på det specifika fallet med kryptering av meddelanden på engelska (dvs. $m = 26$ ), finns det totalt 286 icke-triviala affina chiffer, de 26 triviala Caesar-chiffrorna inte medräknade. Detta nummer kommer från det faktum att det finns 12 tal som är coprime med 26 som är mindre än 26 (dessa är de möjliga värdena för $a$ ). Varje värde på $a$ kan ha 26 olika additionsskift ( $b-$ värdet); därför finns det 12 × 26 eller 312 möjliga nycklar. Denna brist på variation gör systemet så mycket osäkert när det betraktas i ljuset av Kerckhoffs princip .

Chifferets primära svaghet kommer från det faktum att om kryptoanalytikern kan upptäcka (genom frekvensanalys , brute force , gissning eller annat) klartexten av två chiffertexttecken så kan nyckeln erhållas genom att lösa en samtidig ekvation . Eftersom vi vet att $a$ och $m$ är relativt prime kan detta användas för att snabbt kassera många "falska" nycklar i ett automatiserat system.

Samma typ av transformation som används i affina chiffer används i linjära kongruentialgeneratorer , en typ av pseudoslumptalsgenerator . Denna generator är inte en kryptografiskt säker pseudoslumptalsgenerator av samma anledning som det affina chiffert inte är säkert.

Exempel

I det här exemplet som visar kryptering och dekryptering kommer alfabetet att vara bokstäverna A till Z och kommer att ha motsvarande värden som finns i följande tabell.

A	B	C	D	E	F	G	H	jag	J	K	L	M	N	O	P	F	R	S	T	U	V	W	X	Y	Z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Kryptering

$klartexten som ska krypteras "$ AFFINE CIPHER " med hjälp av tabellen ovan för de numeriska värdena för $varje$ bokstav $.$ alfabetet som används. Endast värdet på $a$ har en begränsning eftersom det måste vara coprime med 26. De möjliga värdena som $a$ kan vara är 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 och 25. Värdet för $b$ kan vara godtyckligt så länge $a$ inte är lika med 1 eftersom detta är chiffrets förskjutning. Således kommer krypteringsfunktionen för detta exempel att vara $y = E (x) = (5 x + 8) mod 26$ . Det första steget i att kryptera meddelandet är att skriva de numeriska värdena för varje bokstav.

oformatterad text	A	F	F	jag	N	E	C	jag	P	H	E	R
$x$	0	5	5	8	13	4	2	8	15	7	4	17

Ta nu varje värde på $x$ och lös den första delen av ekvationen, ( $5 x + 8)$ . Efter att ha hittat värdet på $(5 x + 8)$ för varje tecken, ta resten när du dividerar resultatet av $(5 x + 8)$ med 26. Följande tabell visar de första fyra stegen i krypteringsprocessen.

oformatterad text	A	F	F	jag	N	E	C	jag	P	H	E	R
$x$	0	5	5	8	13	4	2	8	15	7	4	17
$(5 x + 8)$	8	33	33	48	73	28	18	48	83	43	28	93
$(5 x + 8) mod 26$	8	7	7	22	21	2	18	22	5	17	2	15

Det sista steget i att kryptera meddelandet är att slå upp varje numeriskt värde i tabellen för motsvarande bokstäver. I det här exemplet skulle den krypterade texten vara IHHWVCSWFRCP. Tabellen nedan visar den ifyllda tabellen för kryptering av ett meddelande i Affine-chifferet.

oformatterad text	A	F	F	jag	N	E	C	jag	P	H	E	R
$x$	0	5	5	8	13	4	2	8	15	7	4	17
$(5 x + 8)$	8	33	33	48	73	28	18	48	83	43	28	93
$(5 x + 8) mod 26$	8	7	7	22	21	2	18	22	5	17	2	15
chiffertext	jag	H	H	W	V	C	S	W	F	R	C	P

Dekryptering

I det här dekrypteringsexemplet är chiffertexten som kommer att dekrypteras chiffertexten från krypteringsexemplet. Motsvarande dekrypteringsfunktion är $D (y) = 21(y - b) mod 26$ , där $a -1$ beräknas vara 21, och $b$ är 8. Skriv till att börja med de numeriska ekvivalenterna till varje bokstav i chiffertexten, som visas i tabellen nedan.

chiffertext	jag	H	H	W	V	C	S	W	F	R	C	P
$y$	8	7	7	22	21	2	18	22	5	17	2	15

Nu är nästa steg att beräkna $21(y - 8)$ , och sedan ta resten när det resultatet divideras med 26. Följande tabell visar resultaten av båda beräkningarna.

chiffertext	jag	H	H	W	V	C	S	W	F	R	C	P
$y$	8	7	7	22	21	2	18	22	5	17	2	15
$21 (å - 8)$	0	−21	−21	294	273	−126	210	294	−63	189	−126	147
$21(y - 8) mod 26$	0	5	5	8	13	4	2	8	15	7	4	17

Det sista steget i att dekryptera chiffertexten är att använda tabellen för att konvertera numeriska värden tillbaka till bokstäver. Klartexten i denna dekryptering är AFFINECIPHER. Nedan är tabellen med det sista steget genomfört.

chiffertext	jag	H	H	W	V	C	S	W	F	R	C	P
$y$	8	7	7	22	21	2	18	22	5	17	2	15
$21 (å - 8)$	0	−21	−21	294	273	−126	210	294	−63	189	−126	147
$21(y - 8) mod 26$	0	5	5	8	13	4	2	8	15	7	4	17
oformatterad text	A	F	F	jag	N	E	C	jag	P	H	E	R

Hela alfabetet kodat

För att göra kryptering och dekryptering snabbare kan hela alfabetet krypteras för att skapa en en-till-en-karta mellan bokstäverna i klartexten och chiffertexten. I det här exemplet skulle en-till-en-kartan vara följande:

bokstav i klartexten	A	B	C	D	E	F	G	H	jag	J	K	L	M	N	O	P	F	R	S	T	U	V	W	X	Y	Z
nummer i klartexten	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
$(5 x + 8) mod 26$	8	13	18	23	2	7	12	17	22	1	6	11	16	21	0	5	10	15	20	25	4	9	14	19	24	3
chiffertextbrev	jag	N	S	X	C	H	M	R	W	B	G	L	F	V	A	F	K	P	U	Z	E	J	O	T	Y	D

Programmeringsexempel

Följande Python- kod kan användas för att kryptera text med det affina chiffer:



      
       
            


  # Skriver ut en transponeringstabell för ett affint chiffer.  # a måste vara coprime till m=26.  def  affine  (  a  :  int  ,  b  :  int  )  ->  Ingen  :  för  i  i  intervallet  (  26  ):  print  (  chr  (  i  +  ord  (  'A'  ))  +  ": "  +  chr  (((  a  *  i  +  b  )  %  26  )  +  ord  (  'A'  )))  # Ett exempelsamtal  affine  (  5  ,  8  )

Se även