HPC (chiffer)
HPC ( Hasty Pudding Cipher ) är en blocksymmetrisk kryptoalgoritm skapad av den berömde amerikanske kryptologen och matematikern Richard Schreppel från Arizona State University 1998 . De två första orden i namnet på kryptoalgoritmen kan översättas som "mjölig vaniljsås " . HPC fick ett så konstigt namn, tydligen, på grund av överflöd av "slug" numeriska transformationer, vilket avsevärt komplicerar analysen .
Allmän struktur
HPC är baserat på Feistel-cellen och har en intressant funktion - storleken på både det krypterade blocket och krypteringsnyckeln begränsas inte av någonting. Faktum är att HPC-algoritmen består av fem olika (men relaterade) underalgoritmer, som var och en är designad för att kryptera block av olika längder:
| namn | Blockstorlek i bitar |
|---|---|
| HPC Tiny | 0 - 35 |
| HPC kort | 36 - 64 |
| HPC-medium | 65 - 128 |
| HPC lång | 129 - 512 |
| HPC Extended | 513 och uppåt |
Struktur för HPC-Medium-omgången [1] [2]
Kryptering utförs i 8 omgångar. Ett krypterat 128 -bitars block skrivs in i två 64 -bitars register och , varefter ett stort antal olika matematiska operationer utförs på dem:
| Beteckning | Drift |
|---|---|
| modulo 2 tillägg | |
| modulo tillägg | |
| modulo subtraktion | |
| rotera vänster med n bitar | |
| rotera höger med n bitar | |
| nollställer den låga byten för ett 64 -bitars block | |
| bitvis logiskt "och" |
Dessutom deltar några konstanter i omgången :
-
- - storleken på det krypterade blocket i bitar
- - " pseudo-slumpmässig " konstant
- - värden som bestämmer antalet bitar av det cykliska skiftet :
-
- - registrets aktuella värde vid tidpunkten för utförande
- - nummer på den aktuella omgången, från noll
- - utökat nyckelfragment :
- - fragment av en extra nyckel:
![{\displaystyle k_{1}=K[<S_{0}>\And 255]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04883ba641ce4594f0ef0ade42c09925ff1f7dbd)
![{\displaystyle k_{2}=K[<S_{0}>\And 255]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0d932134433a89a384e5202ae6595eb607a9845)
![{\displaystyle k_{3}=K[(<S_{0}>\And 255)+3*i+1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c19f7d5c8920ed700ddf8e245600b5dd7d73014)
![{\displaystyle k_{4}=K[b+16+i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2495cc3185496f7c2bda0a26ec8314f8ab800898)
![{\displaystyle Sp_{1}=Spice[i\oplus 4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28345dbcffb189a101c3515b5b2dfce0e66b5406)
![{\displaystyle Sp_{2}=Krydda[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e289a771930295314d8c0e88b8f786aa9846c1ec)
![{\displaystyle Sp_{3}=Spice[i\oplus 7]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27329e4949fedeae101f552c59aae2bcded1d20b)
![{\displaystyle Sp_{4}=Krydda[i\oplus 2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1abe08fe1ec023a615e9a7230bfbc7482ea81044)
![{\displaystyle Sp_{5}=Krydda[i\oplus 1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eade896bdc57e24af5c0fe61cf5c3bc48803beda)
Efter att ha slutfört 8 omgångar av transformation utförs ytterligare 2 operationer:
![{\displaystyle S_{0res}'=S_{0}'+K[b+8]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/293206577b6cc8e1f0d1883757fd5db3ed032bc7)
![{\displaystyle S_{1res}'=S_{1}'+K[b+9]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89249d79acc42f0cfca45fdbb1e408b7d0196449)
Dekryptering utförs genom att utföra de omvända operationerna i omvänd ordning.
Nyckelexpansionsprocedur
Uppgiften med nyckelexpansionsproceduren är att generera en utökad nyckel , som är en uppsättning av 256 64- bitars ord. Det är tydligt att var och en av subalgoritmerna måste ha sin egen procedur. Att känna till en av de utökade nyckelmatriserna tillåter inte en att beräkna vare sig de andra matriserna eller själva krypteringsnyckeln . Men med en fast storlek på krypterade block räcker det att generera en utökad nyckel en gång för denna subalgoritm.
Steg 1: Initiering
-
- , - liknande " pseudo-slumpmässiga " konstanter
- - Krypteringsnyckelstorlek i bitar
- - subalgoritmnummer (3 för HPC-Medium)
![{\displaystyle K[0]=PI19+Nc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffc7d825425a76894f7a39c6d7312f5ed27f00e2)
![{\displaystyle K[1]=E19+L}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eaadc7fd8c17f62049ffc613ec60dedea0d05258)
![{\displaystyle K[2]=R220<<Nc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/accd843923192ed2107b865d44ccd133b0b39887)
De återstående 253 orden i nyckeln initieras enligt följande:
![{\displaystyle K[i]=K[i-1]+(K[i-2]\oplus (K[i-3]>>23)\oplus (K[i-3]<<41))mod2 ^{64}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e4808bcebfd07f601e7cd27c0632ec05d538f5)
Steg 2: Tillägg
Bitvis modulo 2-tillägg av krypteringsnyckeln och den initierade utökade nyckeluppsättningen utförs, men inte mer än 128 ord.
Steg 3: Omrörning
Funktionen för utökad nyckeldatablandning utförs , vilket säkerställer att varje bit av nyckeln påverkar varje bit av den utökade nyckeln :
Steg 1Registren initieras :
![{\displaystyle S_{0}=K[255],S_{1}=K[254],...,S_{7}=K[248]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/191eeb1a8ccea22f2b61c7a2e85b79d41721d5b1)
För varje ord i den utökade tangenten utförs operationen som visas i figuren. För att förstärka effekten rekommenderar författaren av algoritmen 3 omgångar av blandning.
- - bitvis logiskt "eller"
- - numret på det beräknade ordet för den utökade nyckeln
- - blanda runt nummer
- - aktuella värden för de utökade nyckelorden :
![{\displaystyle kc_{1}=K[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55f99304739f743c0c20b808535773204e63fd86)
![{\displaystyle kc_{2}=K[(i+83)\And 255]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae54acb6d0ec7c7f0e8d94dd16c6bdd74f1fa434)
![{\displaystyle kc_{3}=K[<R_{0}>\And 255]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11aef067e306a8a1760415c56f3806f096cac713)
Steg 4: Lägga till
Om nyckelstorleken överstiger 128 64 -bitars ord, upprepas steg 2 och 3 för varje block med 128 ord. Proceduren för att blanda nycklar i komplexitetsordning liknar således själva krypteringsproceduren .
Ytterligare nyckel
Dess syfte är att modifiera krypteringsresultatet med samma inmatningsblock och nycklar . Tilläggsnyckeln kan vara hemlig, vilket ökar den faktiska mängden nyckelinformation, men i en algoritm med en obegränsad nyckellängd kan denna möjlighet vara onödig. I sådana fall kan du helt enkelt återställa tilläggsnyckeln .
Fördelar och nackdelar
- En omgång av kryptering av HPC-algoritmen består av ett mycket stort antal elementära operationer. I jämförelse, till exempel, med den inhemska algoritmen GOST 28147-89 , som består av endast 4 elementära operationer, verkar HPC vara extremt komplex och besvärlig. Men på grund av det faktum att alla operationer utförs på 64- bitars ord, visade HPC förvånansvärt hög hastighet på 64 -bitars plattformar. På AES- krypteringsstandardtävlingen, när det gäller krypteringshastigheten för 128 -bitars block, var HPC näst efter DFC- algoritmen , och HPC-krypterade 512- och 1024- bitars block 2-3 gånger snabbare än alla dess konkurrenter.
- De uppenbara nackdelarna med algoritmen inkluderar, förutom komplexiteten, omöjligheten att parallellisera processerna för kryptering och blandning, såväl som de enorma krav som algoritmen ställer på icke-flyktigt och random access-minne, vilket gör det ganska svårt att använda. det i smarta kort .
- Algoritmen kom inte till det andra steget av AES . I sin artikel [4] slog författaren ut mot AES- experterna och trodde att prioriteringarna var felaktiga i tävlingen. Enligt Richard Schreppel är det nödvändigt att välja algoritmer anpassade för 64 -bitars plattformar som världsstandard, eftersom framtiden ligger hos dem. Dessutom hävdade författaren till HPC att det är omöjligt att utveckla en algoritm som fungerar lika bra både på kraftfulla flerkärniga 64-bitarsservrar och på svaga och billiga 8 -bitars smarta kort . Denna position påverkade dock inte resultatet av tävlingen.
Kryptanalys
- För att stimulera intresset för kryptoanalysen av sin uppfinning, åtog sig författaren att belöna varje kryptoanalytiker med en flaska av den berömda Dom Pérignon- champagnen . Utmärkelser kommer att hållas tills koden öppnas, eller tills lådan (10 flaskor) är tom. [5]
- Enligt författaren till chifferet har HPC en säkerhetsnivå på 400 bitar , det vill säga en framgångsrik attack på chifferet kommer att kräva testning. Ett sådant uttalande är baserat på att räkna antalet mellanliggande tillstånd i krypteringsprocessen , samt på storleken på den utökade nyckeln [6] .
Sårbarheter
David Wagner sårbarhet i - chifferet [7] Carl D'Halluin, Gert Bijnens, Bart Presnel och Vincent Rayman ett dokument [8] som bekräftade detta. Det visade sig att ungefär var 256 :e nyckel i algoritmen har 230 ekvivalenta nycklar . Denna brist rättades dock omedelbart av författaren redan innan man summerade resultaten av den första omgången av tävlingen.
Attackera "Chosen Spice"
Med denna typ av attack kan en angripare, som har tillgång till par av klartext och chiffertext, genom att manipulera arrayen med den extra nyckeln "Spice", se hur klartexten eller chiffertexten ändras i efterföljande krypteringar . Men enligt författaren har attacker av denna typ ännu inte observerats, och arbete inom detta område kräver ansträngningar från det kryptoanalytiska samhället. [2]
Anteckningar
- ↑ Panasenko S.P. Krypteringsalgoritmer. Särskild uppslagsbok - St Petersburg. : BHV-SPb , 2009. - 576 sid. — ISBN 978-5-9775-0319-8
- ↑ 1 2 Richard Schroeppel, "Hasty Pudding Cipher Specification", maj 1999 (länk inte tillgänglig) . Hämtad 31 oktober 2010. Arkiverad från originalet 17 juli 2011.
- ↑ och har samma form, men generellt sett kommer dessa att vara olika tal, eftersom de beror på det aktuella värdet på .
- ↑ Rich Schroeppel, Puddingmeister, "The Hasty Pudding Chipher: One Year Later", 12 juni 1999 (länk ej tillgänglig) . Hämtad 31 oktober 2010. Arkiverad från originalet 30 november 2021.
- ↑ "SÄKERHETSSYSTEM FÖR KOMMUNIKATION OCH TELEKOMMUNIKATION", 1999 . Datum för åtkomst: 30 oktober 2010. Arkiverad från originalet den 3 juli 2011.
- ↑ Rich Schroeppel, Hilarie Orman, "An Overview of the Hasty Pudding Chipher", juli 1998 (länk inte tillgänglig) . Hämtad 31 oktober 2010. Arkiverad från originalet 30 november 2021.
- ↑ Richard Schroeppel, "Tweaking the Hasty Pudding Chipher" 14 maj 1999 (länk ej tillgänglig) . Hämtad 31 oktober 2010. Arkiverad från originalet 30 november 2021.
- ↑ "Equivalent Keys of HPC", 1999
| Symmetriska kryptosystem | |
|---|---|
| Streama chiffer | |
| Feistel nätverk | |
| SP nätverk | |
| Övrig | |