CAST
VØci, kter‚ jsou levn‚, nebìvaj¡ pý¡liç kvalitn¡. Kdy§ ale jde o algoritmus, kterì se m  st t çifrovac¡m standardem, je situace £plnØ jin . Mus¡ bìt superkvalitn¡ a zcela zadarmo. Na jeden takovì se nyn¡ pod¡v me podrobnØ.

æifrovac¡ standard zdarma

V polovinØ devades tìch let nebyla situace na poli çifrovac¡ch algoritm… r…§ov . Mnoz¡ lid‚ pochopili, §e DES u§ m  sv  nejlepç¡ l‚ta d vno za sebou, ale nemØli m¡sto nØj pý¡liç na vybranou. Existovalo toti§ jen velmi m lo alternativ. Mnoh‚ z nich byly pouze za pen¡ze - pýi komerŸn¡m pou§it¡ se za nØ muselo platit. To byl zejm‚na pý¡pad çvìcarsk‚ çifry IDEA, americkìch çifer RC2, RC4, RC5 a dalç¡ch. V t‚to situaci pýiçla kanadsk  spoleŸnost Entrust Technologies s n padem poskytnout çifrovac¡ algoritmus, kterì by byl volnØ çiýitelnì a pou§itelnì zdarma pro osobn¡ i komerŸn¡ £Ÿely. Proto sponzorovala vìvoj nov‚ho algoritmu, kterì by byl dostateŸnØ variabiln¡ a silnì, pou§itelnì bez pýehnanìch n rok… na slo§itost a tak‚ dostateŸnØ svi§nì. Vìsledek byl nazv n CAST podle inici l svìch kanadskìch tv…rc… (C. Adams, S. Tavares) a na internetu byl v kvØtnu roku 1997 publikov n pod oznaŸen¡m RFC 2144 .

Americkì, nebo kanadskì?
CAST tak pýinesl alternativu k algoritmu Blowfish, kterì ze stejnìch d…vod… nab¡dl jako freeware AmeriŸan B. Schneier o dva roky dý¡ve. T¡m vznikla koneŸnØ i v oblasti freewaru urŸit  konkurence a nab¡dka. CAST si brzo z¡skal pý¡znivce na cel‚m svØtØ, stejnØ tak jako Blowfish, a oba se d¡ky bezplatn‚mu pou§it¡ brzy objevily v ýadØ komerŸn¡ch produkt….
Vìhodou CAST se staly dvØ podstatn‚ skuteŸnosti, kter‚ jej upýednoståovaly pýed algoritmem Blowfish. Jednak jej ve svìch produktech zaŸal pou§¡vat Microsoft, jednak z¡skal certifik t kvality od ofici ln¡ho kanadsk‚ho £ýadu CSE (Communication Security Establishment), a d  se tak pou§¡t pro ochranu citlivìch dat v kanadskìch vl dn¡ch organizac¡ch a instituc¡ch (urŸen¡ pro stupeå "designated information" podle kanadsk‚ho syst‚mu klasifikace). Za zm¡nku stoj¡ i jeho vŸlenØn¡ do programu PGP (Pretty Good Privacy), kde nahradil pro komerŸn¡ £Ÿely licenŸn¡mi poplatky zat¡§enì çvìcarskì algoritmus IDEA.

Je CAST podobnì DES?
Ano, v mnoha smØrech je. Pou§¡v  ovçem ýadu novìch kryptografickìch myçlenek a je nesrovnatelnØ kvalitnØjç¡. S DES m  spoleŸnì tzv. Feistel…v princip. Algoritmus Feistelova typu pracuje v cyklech toto§nìch operac¡, kter‚ se nazìvaj¡ rundy (rounds). Ka§d  runda opakuje stejn‚ operace se vstupem a vìstup z jedn‚ rundy je z roveå vstupem do rundy n sleduj¡c¡, ale v r…znìch rund ch jsou pou§ity odliçn‚ tzv. rundovn¡ kl¡Ÿe (viz t‚§ pýipojen  sch‚mata). Rundovn¡ kl¡Ÿe se odvozuj¡ v inicializaŸn¡ f zi algoritmu z vlastn¡ho çifrovac¡ho kl¡Ÿe r…znØ slo§itìm procesem (DES napý¡klad oproti CAST pou§¡v  velmi jednoduchì postup, kterì m…§e vytvoýit i tzv. slab‚ kl¡Ÿe).
Feistel…v princip umo§åuje pro odçifrov n¡ pou§¡t stejnì postup jako pro zaçifrov n¡, jen se obr t¡ poýad¡ vìbØru rundovn¡ch kl¡Ÿ… (zkuste si tento geni ln¡ princip rozmyslet podle obr zku). Tato vlastnost je vìhodn  zejm‚na pro hardware a çifrovac¡ Ÿipy. Dalç¡ podobnost s DES je opØt na £rovni obecn‚ho principu, kterìm jsou tzv. substituŸnØ-permutaŸn¡ s¡tØ. DES i CAST pou§¡vaj¡ substituce, a to ve formØ pevnìch substituŸn¡ch tabulek zvanìch S-boxy. DES m  osm S-box…, kter‚ zobrazuj¡ çest bit… na Ÿtyýi, u CAST to jsou Ÿtyýi mohutnØjç¡ S-boxy S1 a§ S4, kter‚ pýev dØj¡ osm bit… na 32. Toto "rozç¡ýen¡" je jedn¡m z novìch prvk…, kter‚ se objevily u nØkolika çifer devades tìch let.
D le DES pou§¡v  permutaci bit… (pýeh zen¡ poýad¡ bit…), kter  je skuteŸnìm "zabij kem" pro softwarovou realizaci, zat¡mco CAST jako permutaci pou§¡v  cyklickou rotaci bit…. Tu lze, jak zn mo, softwarovØ realizovat velmi jednoduçe. KromØ toho CAST pou§¡v  aritmetick‚ operace sŸ¡t n¡ a odŸ¡t n¡ v cel‚ ç¡ýi 32bitov‚ho slova, tj. v modulu 232. Uveden‚ operace jsou kryptologicky silnØjç¡ a pýi realizaci souŸasnØ rychlejç¡. Vìsledkem je proto çifra kvalitnØjç¡ a rychlejç¡ ne§ DES. Autoýi uv dØj¡, §e rychlost çifrov n¡ dat v operaŸn¡ pamØti PC je na 150MHz Pentiu asi 3 MB/s.

CAST je bezpeŸnì
D¡ky vìçe uvedenìm zes¡len¡m oproti DES si CAST z¡skal velkou d…vØru. PýispØlo k tomu jistØ i zveýejnØn¡ vçech kryptografickìch detail… a £vah o bezpeŸnosti algoritmu ve studii "Constructing Symmetric Ciphers Using the CAST Design Procedure" (viz infotipy).
CAST vìhodnØ vyu§¡v  skuteŸnosti, §e Feistel…v princip je u§ velmi dlouho pou§¡vanì a prozkoumanì, a pýitom zav d¡ dalç¡ kvalitn¡ kryptografick‚ operace. Vìsledkem jsou velmi dobr‚ vlastnosti algoritmu, jako je konfuze, difuze, lavinovitost, nez vislost bit… atd., co§ dosvØdŸuje i skuteŸnost, §e dosud nebyla odhalena § dn  jeho slabina.
CAST se samozýejmØ vyhìb  vçem notoricky zn mìm neçvar…m DES, jako je vlastnost komplement rnosti nebo existence slabìch a poloslabìch kl¡Ÿ…. Dalç¡m d…le§itìm pýedpokladem bezpeŸnosti je d‚lka kl¡Ÿe. Zde d v  CAST u§ivateli volnou ruku a umo§åuje volit d‚lku kl¡Ÿe od 40 a§ do 128 bit… (po osmi bitech). Posledn¡m - a nepochybnØ z sadn¡m - potvrzen¡m jeho kvality se stalo u§ zm¡nØn‚ ofici ln¡ stanovisko kanadsk‚ho £ýadu CSE.

Popis algoritmu
Popis lze shrnout do Ÿtyý z kladn¡ch krok…. OznaŸme bity otevýen‚ho textu (vstupu algoritmu) jako m1 ... m64, bity çifrovac¡ho kl¡Ÿe K jako k1 ... k128 (pokud je kl¡Ÿ kratç¡, je do d‚lky 128 bit… doplnØn nulami) a çifrovì text (tj. vìstup algoritmu) jako c1 ... c64. Algoritmus m  12 nebo 16 rund, podle toho, zda p…vodn¡ kl¡Ÿ m  d‚lku do 80 bit… (vŸetnØ) nebo v¡ce ne§ 80 bit…. Rundy nemaj¡ zcela toto§nou m¡chac¡ funkci f (jak je zn zornØno na obr zku Feistelova principu), ale funkce f jsou týi. Liç¡ se v r…zn‚m poýad¡ vìbØru operac¡ +, -, xor, kter‚ jsou v obr zku zn zoråuj¡c¡m m¡chac¡ funkci oznaŸeny jako operace a, b, c, d. Proto rozezn v me typ1 (f1), typ2 (f2) a typ3 (f3) t‚to funkce. Konkr‚tn¡ naplnØn¡ operac¡ u funkc¡ f1 a§ f3 je uvedeno d le v odstavci o m¡chac¡ funkci f.
Proto§e se popis algoritmu mØn¡ v z vislosti na d‚lce kl¡Ÿe K, zohledåuje se to tak‚ v oznaŸen¡ algoritmu. Algoritmus se pak oznaŸuje jako CAST5-x, pýiŸem§ Ÿ¡slo za pomlŸkou ud v  d‚lku kl¡Ÿe v bitech (12 mo§nost¡). Za z kladn¡ verze se pova§uj¡ CAST5-40, CAST5-80 a CAST5-128. K nim jsou tak‚ definov ny kontroln¡ pý¡klady (viz infotipy).

Zaçifrov n¡
1. krok:
Pý¡prava rundovn¡ch kl¡Ÿ…. Z kl¡Ÿe K se vypoŸte 16 p r… rundovn¡ch kl¡Ÿ… {Kmi, Kri}, i = 0 ... 15, kde Kmi jsou 32bitov  slova (maskovac¡ kl¡Ÿe) a Kri pØtibitov  slova (rotaŸn¡ kl¡Ÿe). 
2. krok:
Otevýenì text se rozdØl¡ na lev‚ (L) a prav‚ (R) 32bitov‚ slovo: 
L0 = m1 ... m32,   R0 = m33 ... m64.
3. krok:
Nyn¡ n sleduje 16 (pý¡padnØ 12) rund (i = 0 ... 15), v nich§ se vypoŸ¡t vaj¡ Li+1 a Ri+1 z Li a Ri podle vztah…:
Li+1 = Ri 
Ri+1 = Li xor f(Ri, Kmi, Kri) 
Pýitom funkce f je vyb¡ran  postupnØ jako f1, f2, f3 a cyklicky d le.
4. krok:
Na z vØr probØhne vìmØna poýad¡ L16 a R16, tj. çifrovì text je definov n jako c1 ... c64 = (R16, L16) - nikoliv, jak by se dalo oŸek vat, jako (L16, R16). 

Odçifrov n¡
Jak u§ bylo ýeŸeno, odçifrov n¡ prob¡h  stejnìm postupem jako zaçifrov n¡. Proto byl tak‚ uŸinØn 4. krok v uveden‚m popisu. Jedinì rozd¡l pýi odçifrov n¡ oproti zaçifrov n¡ spoŸ¡v  v obr cen¡ poýad¡ vìbØru p r… rundovn¡ch kl¡Ÿ…. Jako prvn¡ se tedy pou§ije ten p r rundovn¡ch kl¡Ÿ…, kterì byl pýi zaçifrov n¡ pou§it jako posledn¡, atd. 

SubstituŸn¡ boxy
CAST pou§¡v  8 konstantn¡ch substituŸn¡ch box… S1 a§ S8, kter‚ zobrazuj¡ bajt na Ÿtyýbajtov‚ slovo. Ka§dì S-box tedy zab¡r  v pamØti 1 KB. Pýi vlastn¡m çifrov n¡ dat ale postaŸ¡ vyhradit pamØœ 4 KB na S-boxy S1 a§ S4, neboœ S5 a§ S8 se pou§¡vaj¡ pouze k pý¡pravØ p r… rundovn¡ch kl¡Ÿ….
M¡chac¡ funkce f
V m¡chac¡ funkci jsou pou§ity bاn‚ operace intelskìch procesor…, jako je sŸ¡t n¡ (+) a odŸ¡t n¡ (-) 32bitovìch slov v modulu 232 (tj. pý¡padn‚ pýeteŸen¡ se zanedb v ), operace xor a cyklick  rotace 32bitov‚ho slova o n bit… doleva (<<< n ). Pro snadnØjç¡ popis oznaŸme D vstupn¡ 32bitov‚ slovo funkce f a I 32bitov‚ slovo, kter‚ vznikne jako mezivìsledek. Jednotliv‚ bajty slova I oznaŸme od nejvìznamnØjç¡ho Ia a§ po nejm‚nØ vìznamnì Id. Z pis m¡chac¡ funkce f je pak jednoduchì:

Typ 1: 
I = ((Kmi + D) <<< Kri)
f = ((S1[Ia] xor S2[Ib]) - S3[Ic]) + S4[Id]

Typ 2: 
I = ((Kmi xor D) <<< Kri)
f = ((S1[Ia] - S2[Ib]) + S3[Ic]) xor S4[Id]

Typ 3: 
I = ((Kmi - D) <<< Kri)
f = ((S1[Ia] + S2[Ib]) xor S3[Ic]) - S4[Id]

Tyto rovnice pak definuj¡ konkr‚tn¡ instance operac¡ a a§ d v obr zku m¡chac¡ funkce.

Pý¡prava rundovn¡ch kl¡Ÿ…
Zbìv  popsat, jak se vytv ýej¡ rundovn¡ kl¡Ÿe z k1 ... k128. Postup je dost podobnì vlastn¡mu procesu çifrov n¡, ale jeho popis by vy§adoval pomØrnØ hodnØ m¡sta. Z jemce proto odkazujeme na popis uvedenì v RFC 2144 nebo na programovou realizaci (viz infotipy). Poznamenejme, §e zde, a pr vØ jen zde, se vyu§¡vaj¡ S-boxy S5 a§ S8, kter‚ jsou tak‚ pevnØ definovan‚. Vìstupem je nakonec 12 nebo 16 p r… rundovn¡ch kl¡Ÿ… {Kmi, Kri}.

Z vØr
CAST pýedstavuje zdarma standard, kterì je çiroce akceptov n, je dostateŸnØ rychlì a bezpeŸnì a m  mo§nost siln‚ i slab‚ verze podle d‚lky kl¡Ÿe. Co si pý t v¡ce? Nen¡ divu, §e vyplnil vakuum, kter‚ existuje od "p du" DES, a potrv  jeçtØ jeden dva roky, ne§ bude vybr n novì americkì çifrovac¡ standard AES.
Vlastimil Kl¡ma (vklima@decros.cz)

Infotipy
http://ds.internic.net/frc/
rfc2144 .txt 
(Obsahuje definici a z kladn¡ dokument - RFC 2144: CAST-128 Encryption Algorithms, C. Adams, Entrust Technologies, May 1997.)

http://www.entrust.com/library.htm
(Obsahuje studii "Constructing Symmetric Ciphers Using the CAST Design Procedure" o kryptograficko-bezpeŸnostn¡ch aspektech algoritmu.)

http://adonis.ee.queensu.ca:8000/cast/cast.html
(Obsahuje dokument "CAST Encryption Algorithm Related Publications" s dalç¡mi informacemi k algoritmu.)

http://www.mhv.net/~mgraffam/ce/cryptography.html
(Obsahuje volnØ çiýitelnou implementaci CAST v jazyce C.)