ZBezpeŸnostn¡ k¢dy, d¡l 1.
D¡ky masivn¡ propagaci kryptografie se v posledn¡ch letech jaksi ust lil n zor, §e jedin‚, co souŸasn‚ poŸ¡taŸe potýebuj¡, je çifrov n¡. Ve skuteŸnosti ale existuje jeçtØ nejm‚nØ jedna stejnØ d…le§it  odno§ teorie k¢dov n¡, k n¡§ patý¡ napý¡klad tý¡dy bezpeŸnostn¡ch k¢d….

V klidu a bezpeŸ¡

M…§eme ý¡ci, §e bezpeŸnostn¡ k¢dy jsou na tom obdobnØ jako j dro operaŸn¡ho syst‚mu. Prakticky ka§dì u§ivatel dok §e s nadçen¡m obdivovat dovednØ napsanou aplikaci, kter  mu na obrazovce prom¡t  jeden £chvatnì obrazec za druhìm, ale nikdo u§ si neuvØdom¡, §e to vçe je mo§n‚ jen d¡ky j dru operaŸn¡ho syst‚mu, kter‚ celou tu "n dheru" od zaŸ tku a§ do konce podp¡r .
BezpeŸnostn¡ k¢dy (d le jen ECC - Error Control Codes) jsou na tom prakticky stejnØ. Pokud u§ se nØkdo o oblast k¢dov n¡ zaj¡m , potom mu jde o to, aby tam bylo hlavnØ "to çifrov n¡". M lokdo u§ si pýitom pýipouçt¡, §e bez pý¡sluçnìch ECC by cel‚ çifrov n¡ pýiçlo vniveŸ, neboœ k protØjç¡ stranØ by se zaruçenìm kan lem podaýilo protlaŸit sotva Ÿ st z pýen çen‚ zpr vy. JistØ si vzpom¡n te, jak je to nepý¡jemn‚, kdy§ s nØkìm komunikujete pomoc¡ GSM telefonu a sem tam v m vypadne kus hovoru. A to je jen zlomek nepý¡jemnost¡, kter‚ by v s jinak Ÿekaly, kdyby nad vaç¡m spojen¡m nedr§ely ochrannou ruku vhodn‚ ECC. Dalç¡m takovìm pý¡kladem m…§e bìt modemov‚ spojen¡ - jen si vzpomeåte, jak vypad  obrazovka termin lu s ECC a bez nich. To bylo v§dycky "pavouk…", kdy§ nenaskoŸil pý¡sluçnì komunikaŸn¡ protokol.
Takto bychom mohli napý¡klad pýes ochranu dat na velkokapacitn¡ch m‚di¡ch pokraŸovat d l, a§ bychom se dostali týeba k palubn¡m poŸ¡taŸ…m letadel a raketopl n…. Pýedstavte si, §e spokojenØ let¡te na dovolenou do teplìch kraj…, kdy§ tu n hodou vlivem elektromagnetick‚ho vìboje dojde na  sbØrnici palubn¡ho poŸ¡taŸe ke zmØnØ jednoho pýen çen‚ho bitu. Tato zd nlivØ nepodstatn  zmØna m…§e nakonec vyvolat ýetØzovou reakci poruch a n slednØ vyýadit celì elektronickì syst‚m z provozu. Brrr, odporn  pýedstava! NaçtØst¡ jen pýedstava, kter  v praxi t‚mØý nem…§e nastat, a to vçe d¡ky tomu, §e n vrh ýi takto exponovanìch obvod… s t¡mto rizikem poŸ¡tali a sna§ili se mu vŸas pýedch zet. Podstatnou roli v tØchto protiopatýen¡ch pýitom hraj¡ pr vØ ECC, kter‚ umo§åuj¡ nebezpeŸn‚ selh n¡ kl¡Ÿovìch obvod… vŸas odhalit a eliminovat.

ECC kontra çifrov n¡
Nerad bych, aby z pýedchoz¡ho vìkladu vznikl dojem, §e m m nØco proti kryptografii (kter  mØ ostatnØ §iv¡). Jen se sna§¡m upozornit, §e vedle tohoto jistØ u§iteŸn‚ho n stroje maj¡ i ECC (pros¡m nezamØåovat tuto zkratku s kryptosyst‚my na b zi eliptickìch kýivek - bohu§el tak‚ ECC) v komunikaŸn¡m ýetØzci sv‚ pevn‚ m¡sto. Ka§dì z tØchto n stroj… odv d¡ sv…j kus pr ce a mus¡ jej odv dØt dobýe, jinak je danì syst‚m jako celek nepou§itelnì.
KromØ çifrov n¡ a ECC existuje jeçtØ jeden velmi rozç¡ýenì druh k¢dov n¡ a t¡m je komprimace. Tu pro dalç¡ vìklad ponech me ponØkud stranou, avçak plat¡ o n¡ v podstatØ tot‚§, co bylo ýeŸeno o pýedchoz¡ch dvou technologi¡ch.
Konkr‚tnØjç¡ pýedstavu o tom, jak vlastnØ takovì kvalitn¡ komunikaŸn¡ kan l vypad , pom…§e vytvoýit obr zek. Na nØm vid¡me typick‚ ýazen¡ jednotlivìch kod‚r… a dekod‚r… v cel‚m ýetØzu. PodotknØme, §e zdaleka nemus¡ j¡t v§dy o komunikaŸn¡ spojen¡ v exaktn¡m slova smyslu, tedy o nØjakì kus dr tu odnØkud a§ nØkam. Zrovna tak m…§e kan l pýedstavovat pamØœov‚ m‚dium, do nØho§ se nejdý¡ve vlo§¡ (zak¢duje) informace, kter  se s odstupem Ÿasu zase pýeŸte (dek¢duje) zpØt do procesoru. Podle konkr‚tn¡ aplikace tak‚ nemus¡ bìt v§dy zastoupeny vçechny Ÿ sti ýetØzu, napý¡klad modul tor.
UpozornØme, §e ýazen¡ uvedenìch komponent nen¡ mo§n‚ prov dØt nahodile. Ka§dì Ÿl nek m  sv‚ pevn‚ m¡sto a jeho zmØna mus¡ bìt nejdý¡ve velmi dobýe zv §ena a promyçlena. Zrovna tak jako nem  cenu prov dØt komprimaci po çifrov n¡, nen¡ ani vhodn‚ prov dØt ECC zabezpeŸen¡ pýed çifrov n¡m, Ÿi dokonce pýed kompres¡. D…vod je nasnadØ a spoŸ¡v  v tom, §e jednotliv‚ druhy k¢dov n¡ mohou rozb¡t syst‚m, kterì v k¢du vytvoýil pýedch zej¡c¡ Ÿl nek, a t¡m jej vyýadit z Ÿinnosti.

Princip ECC
Ne§ se pust¡me do dalç¡ho vìkladu, ujasn¡me si nejdý¡ve pýedstavu o tom, co to vlastnØ k¢dov n¡ je. Form lnØ vzato je ka§d‚ k¢dov n¡, kter‚ budeme znaŸit jako ?, zobrazen¡ ??: S ? C, kde S je mno§ina vstupn¡ch slov a C je mno§ina vçech slov dan‚ho k¢du nad jeho abecedou. Aby bylo mo§n‚ zdrojov‚ slovo nejen zak¢dovat, ale v pý¡padØ potýeby zase spr vnØ dek¢dovat, mus¡ bìt zobrazen¡ ??prost‚. Takov‚mu k¢du se potom ý¡k  jednoznaŸnØ dek¢dovatelnì.
Ka§dì z Ÿl nk… komunikaŸn¡ho ýetØzu, kterì je uveden na obr zku, implementuje nØjakì druh ?, kterì splåuje urŸit  krit‚ria. U komprimace je napý¡klad § douc¡, aby pr…mØrn  d‚lka k¢dovìch slov z C byla menç¡ ne§ u slov ze S - k¢d odstraåuje zbyteŸnou redundanci vstupn¡ho jazyka. V pý¡padØ çifrov n¡ n m jde zase o to, aby inverzn¡ zobrazen¡ ?-1 byl schopen spoŸ¡tat pouze majitel pý¡sluçn‚ho tajn‚ho kl¡Ÿe. ékolem kod‚ru ECC je potom vytvoýit takovou strukturu vìstupn¡ch dat, u kter‚ bude mo§n‚ snadno detekovat, Ÿi dokonce odstranit chyby, kter‚ nastaly bØhem pr…chodu informace zaruçenìm kan lem.
Vlastn¡ princip ECC je zalo§en na myçlence vyu§it¡ takzvan‚ k¢dov‚ vzd lenosti. Metrika pou§it  pro mØýen¡ t‚to vzd lenosti z vis¡ na typu kan lu, kterì ud v  charakter oŸek vanìch chyb. Jak si za okam§ik uk §eme, nejpou§¡vanØjç¡ metrikou je v tomto pý¡padØ Hammingova vzd lenost. Napýed si ale ýekneme nØco o k¢dov‚ vzd lenosti obecnØ.
MØjme dvØ k¢dov  slova, kter  oznaŸ¡me jako c1 a c2. Jejich vzd lenost (mØýena vhodnou metrikou), kterou oznaŸ¡me jako d(c1, c2), n m ý¡k , kolik chyb mus¡ bØhem pýenosu slova c1 kan lem nastat, abychom jej nebyli schopni rozliçit od c2. Celì trik ECC tedy spoŸ¡v  v tom, §e pou§it‚ k¢dov n¡ ??injektuje vstupn¡ slova z mno§iny S do mno§iny C, kter  je obecnØ vØtç¡ ne§ S. D¡ky tomu se jednotliv  slova na t‚to mno§inØ "rozptìl¡" tak, §e m…§eme hovoýit o minim ln¡ k¢dov‚ vzd lenosti (dmin(?)) mezi libovolnou dvojic¡ k¢dovìch slov. Za k¢dov  slova pýitom pova§ujeme ta, kter  maj¡ sv…j vzor v mno§inØ S. Ostatn¡m slov…m z C ý¡k me slova nek¢dov . Pýedpokl d me d le, §e jsme v r mci dan‚ho k¢du schopni o libovoln‚m x ? C rozhodnout, je-li x k¢dov‚ slovo, Ÿi nikoliv.
Z uveden‚ho je vidØt, §e zaveden¡ ECC znamen  nutnØ pýid n¡ nØjak‚ redundantn¡ informace. Zd nlivØ tedy kod‚r ECC "kaz¡" vìsledek pr ce komprimaŸn¡ho modulu. V jist‚m smyslu je to i pravda, neboœ vìsledn  redundance nØkdy (kdy§ je kan l zvl çtØ nekvalitn¡) m…§e bìt i v¡ce ne§ 100 procent p…vodn¡ d‚lky slova, avçak na rozd¡l od bاn‚ "neu§iteŸn‚" nadbyteŸnosti je n m tato ku prospØchu. D¡ky n¡ jsme toti§ schopni rozliçit slova k¢dov  od slov nek¢dovìch a t¡m detekovat chyby vznikl‚ na pýenosov‚m kan lu.

Detekce a oprava chyb
V n sleduj¡c¡m textu si uk §eme, jak se s vyu§it¡m k¢dov‚ vzd lenosti prov d¡ u ECC detekce a oprava chyb. Vyu§ijeme pýitom pojmu minim ln¡ k¢dov‚ vzd lenosti (dmin(?)) tak, jak jsme si jej zavedli v pýedchoz¡ Ÿ sti.
Pýedpokl dejme, §e jsme do kan lu vyslali k¢dov‚ slovo c1 a pýijali jsme slovo x. Prvn¡, co n s o tomto slovØ zaj¡m , je, zda je tak‚ k¢dov‚. Pokud ano, potom buÔ bØhem pýenosu nedoçlo k § dn‚ chybØ (potom x = c1), nebo doçlo k takov‚mu poŸtu chyb, kterì odpov¡d  minim ln¡ k¢dov‚ vzd lenosti. Potom jsme ve stavu, kdy si chybnØ mysl¡me, §e bylo vysl no nØjak‚ c2, d(c1, c2) = d(c1, x) = dmin(?).
Pokud slovo x nen¡ k¢dov‚, potom je mo§n‚ jednoznaŸnØ prohl sit, §e bØhem pýenosu doçlo k chybØ (vys¡laŸ by toti§ nek¢dov‚ slovo nikdy nevyslal). Odtud m…§eme vyvodit n sleduj¡c¡ tvrzen¡: Danì k¢d ? je schopen detekovat t chyb pr vØ tehdy, kdy§ dmin(?) ? t + 1 (tvrzen¡ T1.1).
Zabìvejme se nyn¡ mo§nost¡ opravy chyb - v tom n m pom…§e obr zek. Vid¡me, §e ka§d‚ k¢dov‚ slovo kolem sebe vytv ý¡ sf‚rickì obal, jeho§ polomØr mØý¡me pomoc¡ urŸen‚ metriky. Tento polomØr n m ý¡k , jak moc m…§e bìt jeçtØ dan‚ slovo poruçeno, aby st le patýilo do "p…vodn¡" sf‚ry vyslan‚ho k¢dov‚ho slova. Dekod‚r prov dØj¡c¡ opravu chyby potom pracuje tak, §e pýijat‚ slovo nahrad¡ k¢dovìm slovem ze stýedu pý¡sluçn‚ sf‚ry. Tomuto zp…sobu dek¢dov n¡ se ý¡k  oprava s minim ln¡ vzd lenost¡.
Formalizace uveden‚ho pozorov n¡ je s vyu§it¡m obr zku snadn . Pýedpokl dejme, §e chceme, aby danì k¢d ? opravoval t-n sobn‚ chyby. Potom mus¡ ka§d‚ k¢dov‚ slovo kolem sebe m¡t sf‚rick‚ okol¡ o polomØru alespoå t, kter‚ m  pr zdnì pr…nik libovolnìm dalç¡m okol¡m jin‚ho k¢dov‚ho slova. Tento pýedpoklad bude splnØn, pokud pro dmin(?) plat¡, §e dmin(?) ? 2t + 1 (tvrzen¡ T1.2).

Hammingova vzd lenost
Pro vØtçinu bezpeŸnostn¡ch k¢d…, se kterìmi se v praxi setk me, se jako metrika s £spØchem pou§¡v  takzvan  Hammingova vzd lenost. JistØ v s nepýekvap¡, §e Hammingova vzd lenost dvou slov x = x1x2...xn a y = y1y2...yn, kterou znaŸ¡me jako d(x, y), je definov na jako poŸet pozic, na nich§ se ýetØzce x a y liç¡ (definice D1.1). Napý¡klad d(0101, 0111) = 1, d(0000, 1111) = 4. Existuj¡ i obecnØjç¡ definice Hammingovy vzd lenosti, avçak tato je pro n s zat¡m postaŸuj¡c¡.
Mno§inu vçech (k¢dovìch i nek¢dovìch) slov dan‚ho k¢du n m Hammingova vzd lenost organizuje do struktury, kter  se oznaŸuje jako n-rozmØrn  krychle, kde n je d‚lka slova. V tomto grafu jsou spolu spojeny hranou v§dy ta slova, kter  se liç¡ pr vØ v jedn‚ pozici, nebo chcete-li pr vØ v jedn‚ chybØ. Sf‚rick  okol¡ jednotlivìch k¢dovìch slov potom z p…vodn¡ krychle vyt¡naj¡ jej¡ urŸit‚ podgrafy, kter‚ ironi¡ osudu zrovna moc sf‚ricky nevypadaj¡. Nicm‚nØ o opravØ a detekci chyb st le plat¡ vìçe uveden  obecn  tvrzen¡. Jenom se naçe pýedstavy h…ý vizu lnØ ztv råuj¡.
Obr zek ukazuje, jak vypad  sf‚rick‚ okol¡ o polomØru jedna se stýedem v bodØ (111) na "klasick‚" trojrozmØrn‚ krychli. Pro vØtç¡ d‚lky k¢dovìch slov je u§ týeba notn‚ d vky fantazie, tak§e se pro dalç¡ vìklad pýidr§¡me algebraick‚ho popisu tØchto struktur a jejich vizualizaci pýenech me modern¡mu vìtvarn‚mu umØn¡.

Model kan lu
Teorie informace a k¢dov n¡ definuje ýadu model…, kterìmi je mo§n‚ popsat chov n¡ nejr…znØjç¡ch typ… pýenosovìch kan l…. My se zde dnes sezn m¡me s jej¡m klasickìm z stupcem, kterì se oznaŸuje jako bin rn¡ symetrickì kan l. Na tomto modelu si z roveå dok §eme spr vnost dek¢dov n¡ s minim ln¡ vzd lenost¡.
Obr zek ukazuje chov n¡ tohoto kan lu vzhledem k pýenosu element rn¡ Ÿ sti slova, v tomto pý¡padØ jednoho bitu. PravdØpodobnost chyby kan lu oznaŸujeme jako p. Vid¡me, §e pravdØpodobnost pýeps n¡ nuly na jedniŸku a jedniŸky na nulu je stejn  - odtud slovo "symetrickì". V praxi se m…§eme setkat i s asymetrickìmi kan ly, kde pravdØpodobnost chyby z vis¡ na pýen çen‚ informaci. Sem patý¡ zejm‚na struktury typu PROM, PLA, PGA a jim podobn‚. Pro naçe dalç¡ studium se vçak omez¡me v¡cem‚nØ jen na symetrick‚ kan ly.
VØnujme se nyn¡ v kr tkosti d…kazu spr vnosti dek¢dov n¡ s minim ln¡ vzd lenost¡. Nejprve urŸ¡me pravdØpodobnost, §e i bit… pýijat‚ho n-bitov‚ho slova je chybnìch, jako P(i) = pi(1 - p)n-i. D le pýedpokl dejme, §e p < 1/2, co§ je z kladn¡ pýedpoklad. Potom plat¡, §e P(i + 1) < P(i) neboli §e slova pýijat  s menç¡m poŸtem chyb jsou pravdØpodobnØjç¡. Odtud plyne spr vnost dek¢dov n¡ s minim ln¡ vzd lenost¡ pro Hammingovu vzd lenost a bin rn¡ symetrickì kan l, neboœ podle n¡ dekod‚r pýedpokl d , §e bylo vysl no takov‚ k¢dov‚ slovo, kter‚ je vzhledem k pýijat‚ hodnotØ x zat¡§eno nejmenç¡ chybou, kter  je, jak jsme si uk zali, nejv¡ce pravdØpodobn  (d…kaz P1.1).

Z kladn¡ druhy ECC
Pro lepç¡ n zornost dneçn¡ho vìkladu si na z vØr uk §eme nØkolik jednoduchìch typ… ECC. D…le§itìm parametrem ka§d‚ho k¢du je poŸet informaŸn¡ch znak… ve vìsledn‚m k¢dov‚m slovØ. Jednotliv‚ k¢dy se proto Ÿasto popisuj¡ dvojic¡ (n, k), kde n je d‚lka k¢dov‚ho slova (nejŸastØji nad bin rn¡ abecedou, a tud¡§ mØýen  v bitech) a k je poŸet informaŸn¡ch znak… v tomto slovØ.
VezmØme si napý¡klad bin rn¡ k¢d celkov‚ kontroly parity. N sleduj¡c¡ k¢dovac¡ pýedpis dopln¡ ka§d‚ vstupn¡ slovo o bit vytv ýej¡c¡ sudou paritu: ?(x) = x1x2...xkp, kde p = x1 + x2 +...+ xk mod 2 (definice D1.2). Tento jednoduchì k¢d typu (k + 1, k), kterì je napý¡klad pou§it na fyzick‚ £rovni bاn‚ho s‚riov‚ho RS 232, asi ka§dì zn . Pod¡vejme se nyn¡, jak‚ jsou jeho obecn‚ vlastnosti. Snadno nahl‚dneme, §e jeho minim ln¡ k¢dov  vzd lenost dmin(?) je dva - je týeba zmØnit dva bity, aby vìsledn‚ slovo mØlo opØt sudou paritu. Podle T1.1 je tento k¢d schopen detekovat pouze jednon sobn‚ chyby a nen¡ schopen prov dØt jejich opravu (viz T1.2). 
Pro extr‚mnØ zaruçen‚ kan ly je mo§n‚ pou§¡t opakovac¡ k¢d ý du s (nØkdy tak‚ k¢d koktavì). Jeho k¢dovac¡ pýedpis je n sleduj¡c¡ ?(x) = x1,1x1,2...x1,sx2,1x2,2 ...x2,s...xk,1xk,2...xk,s, pýiŸem§ xi,j = xi (definice D1.3). Vid¡me, §e ka§dì znak vstupn¡ho slova je zak¢dov n jako s-n sobn‚ opakov n¡ tohoto znaku. O minim ln¡ k¢dov‚ vzd lenosti plat¡, §e dmin(?) = s. Podle tvrzen¡ T1.1 dost v me, §e tento k¢d je schopen detekovat a§ s - 1 chyb a z toho je schopen ?(s - 1)/2? chyb i opravit (viz T1.2). U§ u koktav‚ho k¢du ý du s = 3 dost v me v praxi pou§itelnì vìsledek. Nevìhodou je zde pochopitelnØ velk  nadbyteŸnost - je to k¢d typu (s*k, k).

Z vØr
Dnes jsme si zde udØlali malì £vod do teorie ECC, kter‚ se nyn¡ budeme vØnovat v nØkolika dalç¡ch pokraŸov n¡ch. Snahou je, aby tento seri l nakonec vytvoýil jakousi ucelenou miniencyklopedii ECC, kter  bude slou§it jako rychlì pr…vodce touto problematikou. Z tohoto d…vodu budeme i jednotliv‚ poznatky (definice atd.) postupnØ Ÿ¡slovat, abychom se na nØ mohli kdykoliv pozdØji odk zat. V ka§d‚m dalç¡m d¡lu budeme proto pýedpokl dat, §e Ÿten ý m  k dispozici k nahl‚dnut¡ vçechny pýedch zej¡c¡ d¡ly.
AŸkoliv r z tØchto Ÿl nk… bude sp¡çe matematickì (jinak to u ECC ani nejde), budu se sna§it, aby byl pý¡stupnì co nejçirç¡mu poŸtu Ÿten ý…. Vçe bude prob¡r no pomalu a s d…razem na co nejsnadnØjç¡ pochopen¡ dan‚ problematiky. Nav¡c se budeme sna§it (pokud mo§no bez £jmy na obecnosti a spr vnosti) o co nejvØtç¡ zjednoduçen¡ dan‚ l tky.
Tom ç Rosa (tomas.rosa@decros.cz)