Hill chiffer

Hill's chiffermaskin, från figur 4 i patentet

I klassisk kryptografi är Hill -chifferet ett polygrafiskt substitutionschiffer baserat på linjär algebra . Uppfanns av Lester S. Hill 1929, det var det första polygrafiska chiffer där det var praktiskt (men knappt) att operera på mer än tre symboler samtidigt.

Följande diskussion förutsätter en grundläggande kunskap om matriser .

Kryptering

Varje bokstav representeras av en siffra modulo 26. Även om detta inte är en väsentlig egenskap hos chifferet, används detta enkla schema ofta:

Brev	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
siffra	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

För att kryptera ett meddelande multipliceras varje block med n bokstäver (som betraktas som en n - komponentvektor ) med en inverterbar n × n matris mot modul 26. För att dekryptera meddelandet multipliceras varje block med inversen av matrisen som används för kryptering.

Matrisen som används för kryptering är chiffernyckeln och den bör väljas slumpmässigt från uppsättningen inverterbara n × n matriser ( modulo 26). Chifferet kan naturligtvis anpassas till ett alfabet med valfritt antal bokstäver; all aritmetik behöver bara göras modulo antalet bokstäver istället för modulo 26.

Tänk på meddelandet 'ACT' och nyckeln nedan (eller GYB / NQK / URP med bokstäver):

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}$

Eftersom 'A' är 0, 'C' är 2 och 'T' är 19, är meddelandet vektorn:

${\begin{pmatrix}0\\2\\19\end{pmatrix}}$

Sålunda ges den chiffrerade vektorn av:

${\begin{pmatrix}6&24&1\&17\17\17\17\17\13\17\13\13\13\13\\13\17\\13\\13\\17\\17\\17\\17\\17\\17\\17\ pmatrix}}{\begin{pmatrix}0\\2\\19\end{pmatrix}}={\begin{pmatrix}67\\222\\319\end{pmatrix}}\equiv {\begin{pmatrix} 15\\14\\7\end{pmatrix}}{\pmod {26}}$

som motsvarar en chiffertext av 'POH'. Anta nu att vårt meddelande istället är "CAT", eller:

${\begin{pmatrix}2\\0\\19\end{pmatrix}}$

Den här gången ges den chiffrerade vektorn av:

${\begin{pmatrix}6&24&1\\13&13&13&13&13&13&13 pmatrix}}{\begin{pmatrix}2\\0\\19\end{pmatrix}}={\begin{pmatrix}31\\216\\325\end{pmatrix}}\equiv {\begin{pmatrix} 5\\8\\13\end{pmatrix}}{\pmod {26}}$

som motsvarar en chiffertext av "FIN". Varje bokstav har förändrats. Hill-chifferet har uppnått Shannons diffusion , och ett n -dimensionellt Hill-chiffer kan diffundera helt över n symboler på en gång.

Dekryptering

För att dekryptera, gör vi tillbaka chiffertexten till en vektor och multiplicerar sedan helt enkelt med den inversa matrisen av nyckelmatrisen (IFK / VIV / VMI i bokstäver). Vi finner att, modulo 26, inversen av matrisen som användes i föregående exempel är:

${\begin{pmatrix}6&24&1\\13&120\1\13&120\end} }^{-1}{\pmod {26}}\equiv {\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}$

Om vi ​​tar det föregående exemplet med chiffertext av 'POH' får vi:

${\begin{pmatrix}8&5&10\2\12\21\21\81&81 pmatrix}}{\begin{pmatrix}15\\14\\7\end{pmatrix}}={\begin{pmatrix}260\\574\\539\end{pmatrix}}\equiv {\begin{pmatrix} 0\\2\\19\end{pmatrix}}{\pmod {26}}$

vilket får oss tillbaka till "ACT", som förväntat.

Två komplikationer finns i valet av krypteringsmatrisen:

1. Alla matriser har inte en invers . Matrisen kommer att ha en invers om och endast om dess determinant inte är noll.
2. Determinanten för krypteringsmatrisen får inte ha några gemensamma faktorer med den modulära basen.

Om vi ​​arbetar med modulo 26 enligt ovan måste determinanten vara icke-noll och får inte vara delbar med 2 eller 13. Om determinanten är 0, eller har gemensamma faktorer med den modulära basen, kan matrisen inte användas i kullen chiffer, och en annan matris måste väljas (annars går det inte att dekryptera). Lyckligtvis är matriser som uppfyller villkoren för att användas i Hill-chifferet ganska vanliga.

För vårt exempel på nyckelmatris:

$_ 6&24&1\\13&16&10\\20&17&15\end{vmatrix}}=6(16\cdot 15-10\cdot 17)-24(13\cdot 15-10\cdot 20)+1(13\cdot 17-16\ 20)=441\ekvivalent 25{\pmod {26}}}$

Så, modulo 26, är determinanten 25. Eftersom $25=5^{2}$ och $26=2\times 13$ , har 25 inga gemensamma faktorer med 26 , och denna matris kan användas för Hill-chifferet.

Risken för att determinanten har gemensamma faktorer med modulen kan elimineras genom att göra modulen primtal . Följaktligen lägger en användbar variant av Hill-chifferet till 3 extra symboler (som ett mellanslag, en punkt och ett frågetecken) för att öka modulen till 29.

Exempel

Låta

$K={\begin{pmatrix}3&3\\2&5\end{pmatrix}}$

vara nyckeln och anta att klartextmeddelandet är "HJÄLP". Då representeras denna klartext av två par

${\displaystyle HJÄLP\to {\begin{pmatrix}H\\E\end{pmatrix}},{\$

Sedan räknar vi

${\begin{pmatrix}3&3\\2&5\end{pmatrix}}{\begin{pmatrix}7\\4\ end{pmatrix}}\equiv {\begin{pmatrix}7\\8\end{pmatrix}}{\pmod {26}},$ och

${\begin{pmatrix}3&3\\2&5\end{pmatrix}}{\begin{pmatrix}11\\15\end{pmatrix}}\equiv {\begin{pmatrix}0\\19\end {pmatrix}}{\pmod {26}}$

och fortsätt kryptering enligt följande:

${\begin{pmatrix}7\\8\end{pmatrix}},{\begin{pmatrix}0\\19\end {pmatrix}}\to {\begin{pmatrix}H\\I\end{pmatrix}},{\begin{pmatrix}A\\T\end{pmatrix}}$

Matrisen K är inverterbar, därför existerar $K^{-1}$ så att $KK^{-1}=K^{-1 }K=I_{2}$ . Inversen av K kan beräknas genom att använda formeln ${\begin{pmatrix}a&b\\c&d \end{pmatrix}}^{-1}=(ad-bc)^{-1}{\begin{pmatrix}d&-b\\-c&a\end{pmatrix}}$

Denna formel gäller fortfarande efter en modulär reduktion om en modulär multiplikativ invers används för att beräkna $(ad-bc)^{-1}$ . Därför beräknar vi i det här fallet

$K^{-1}\equiv 9^{-1}{ \begin{pmatrix}5&23\\24&3\end{pmatrix}}\equiv 3{\begin{pmatrix}5&23\\24&3\end{pmatrix}}\equiv {\begin{pmatrix}15&17\\20&9\end{pmatrix }}{\pmod {26}}$

$HIAT\to {\begin{pmatrix}H\\I\ end{pmatrix}},{\begin{pmatrix}A\\T\end{pmatrix}}\to {\begin{pmatrix}7\\8\end{pmatrix}},{\begin{pmatrix}0\\ 19\end{pmatrix}}$

Sedan räknar vi

${\begin{pmatrix}15&17\\20&9\end{pmatrix}}{\begin{pmatrix} 7\\8\end{pmatrix}}={\begin{pmatrix}241\\212\end{pmatrix}}\equiv {\begin{pmatrix}7\\4\end{pmatrix}}{\pmod {26 }},$ och

${\begin{pmatrix}15&17\\20&9\end{pmatrix}}{\begin {pmatrix}0\\19\end{pmatrix}}={\begin{pmatrix}323\\171\end{pmatrix}}\equiv {\begin{pmatrix}11\\15\end{pmatrix}}{\ pmod {26}}$

Därför,

$\begin{pmatrix} 11\\15\end{pmatrix}}\to {\begin{pmatrix}H\\E\end{pmatrix}},{\begin{pmatrix}L\\P\end{pmatrix}}\to HELP}$ .

säkerhet

Det grundläggande Hill-chifferet är sårbart för en känd klartextattack eftersom det är helt linjärt . En motståndare som fångar upp $n^{2}$ teckenpar i klartext/chiffertext kan sätta upp ett linjärt system som (vanligtvis) enkelt kan lösas; om det händer att detta system är obestämt, är det bara nödvändigt att lägga till några fler klartext/chiffertext-par. Att beräkna denna lösning med vanliga linjära algebraalgoritmer tar då väldigt lite tid.

Även om enbart matrismultiplikation inte resulterar i ett säkert chiffer är det fortfarande ett användbart steg när det kombineras med andra icke-linjära operationer, eftersom matrismultiplikation kan ge diffusion . Till exempel kan en lämpligt vald matris garantera att små skillnader före matrismultiplikationen kommer att resultera i stora skillnader efter matrismultiplikationen. Vissa moderna chiffer använder faktiskt ett matrismultiplikationssteg för att ge diffusion. Till exempel är MixColumns-steget i AES en matrismultiplikation. Funktionen g i Twofish är en kombination av icke-linjära S-boxar med en noggrant vald matrismultiplikation (MDS).

Nyckelutrymmesstorlek

Nyckelutrymmet är uppsättningen av alla möjliga nycklar . Nyckelutrymmesstorleken är antalet möjliga nycklar. Den effektiva nyckelstorleken , i antal bitar, är den binära logaritmen för nyckelutrymmets storlek.

Det finns $26^{n^{2}}$ matriser med dimensionen n × n . Således $\log _{2}(26^{n^{2}})$ eller ca $4.7n^{2}$ en övre gräns på nyckelstorleken på Hill-chifferet med n × n matriser. Detta är bara en övre gräns eftersom inte varje matris är inverterbar och därför användbar som nyckel. Antalet inverterbara matriser kan beräknas via den kinesiska restsatsen . Dvs en matris är inverterbar modulo 26 om och endast om den är inverterbar både modulo 2 och modulo _13. Antalet inverterbara n × n matriser modulo 2 är lika med ordningen för den allmänna linjära gruppen GL(n, Z2 ). Det är

$2^{n^{2}}(1-1/2)(1-1/2^{2})\cdots (1-1/2^{n}).$

är antalet inverterbara matriser modulo 13 (dvs. storleksordningen GL(n, Z13 ) ₎

$13^{n^{2}}(1-1/13)(1-1/13^{2})\cdots (1-1/13^{n}).$

Antalet inverterbara matriser modulo 26 är produkten av dessa två tal. Därför är det

$26^{n^{2}}(1-1/2)(1-1/2^{2})\cdots (1-1/2^{n})(1-1/13) (1-1/13^{2})\cdots (1-1/13^{n}).$

Dessutom verkar det vara klokt att undvika för många nollor i nyckelmatrisen, eftersom de minskar diffusionen. Nettoeffekten är att det effektiva tangentutrymmet för ett grundläggande Hill-chiffer är cirka $4,64n^{2}-1,7$ . För ett 5 × 5 Hill-chiffer är det cirka 114 bitar. Naturligtvis är nyckelsökning inte den mest effektiva kända attacken.

Mekanisk implementering

När man använder 2 symboler samtidigt ger ett Hill-chiffer inga speciella fördelar jämfört med Playfair eller bifid-chifferet, och det är faktiskt svagare än båda, och något mer mödosamt att använda med penna och papper. När dimensionen ökar blir chifferet snabbt omöjligt för en människa att hantera för hand.

Ett Hill-chiffer av dimension 6 implementerades mekaniskt. Hill och en partner tilldelades ett patent ( US Patent 1 845 947 ) för denna enhet, som utförde en 6 × 6 matrismultiplikationsmodul 26 med hjälp av ett system av kugghjul och kedjor.

Tyvärr var utväxlingsarrangemangen (och därmed nyckeln) fixerade för en given maskin, så trippelkryptering rekommenderades för säkerheten: ett hemligt olinjärt steg, följt av det breda diffusionssteget från maskinen, följt av ett tredje hemligt olinjärt steg. (Det mycket senare Even-Mansour-chifferet använder också ett okänt diffusivt mellansteg). En sådan kombination var faktiskt mycket kraftfull för 1929, och indikerar att Hill uppenbarligen förstod konceptet med en möte-i-mitt-attack såväl som förvirring och spridning. Tyvärr sålde inte hans maskin.

Se även

Andra praktiska "penna-och-papper" polygrafiska chiffer inkluderar:

• Playfair chiffer
• Bifid chiffer
• Trifid chiffer

• Lester S. Hill, Cryptography in an Algebraic Alphabet, The American Mathematical Monthly Vol.36, juni–juli 1929, s. 306–312. ( PDF )
• Lester S. Hill, Concerning Certain Linear Transformation Apparatus of Cryptography, The American Mathematical Monthly Vol.38, 1931, s. 135–154.
• Jeffrey Overbey, William Traves och Jerzy Wojdylo, On the Keyspace of the Hill Cipher, Cryptologia , Vol.29, No.1, januari 2005, pp. 59–72. ( CiteSeerX ) ( PDF )

externa länkar

• " Hill Cipher Web App " implementerar Hill-chifferet och visar de inblandade matriserna
• " Hill Cipher Explained " illustrerar den linjära algebra bakom Hill Cipher
• " Hill's Cipher Calculator " beskriver Hill Cipher med en webbsida