Kriptográfia

Dr. Olajos Péter


Kivonat:

A jegyzet a KEZEK pályázat eredményeként született, melyben a titkosítás alapjait tekintjük át, rávilágítva azokra a kérdésekre és problémákra, melyek napjainkban is aktuálisak. Az oka ennek nagyon egyszerű: az elektronikus és egyben digitális világ lassan meghódítja a teljes Világot (a Föld nevű bolygónkat) így a korábbi analóg eszközök lassan kimennek a divatból, bár továbbra is hasznosak a szakemberek számára (is). A jegyzet célja ezért azt is bemutatni, hogy napjaink informatikai eszközeit miképpen kell(ene) úgy programozni majd, hogy az elektronikusan tárolt adataink biztonságban legyenek pl. a támadóktól vagy az egyszerűen túl kíváncsi hacker-ektől.


Tartalomjegyzék

1. Bevezetés

A kriptográfia, azaz a titkosítás napjaink (2014-et írunk) kulcsfontosságú informatikai eleme, hiszen a különböző államok titkos dokumentumainak védelme egyértelműen hiányosnak bizonyult. Nem véletlen tehát, hogy több esetben a védelmet a papír alapú tárolásban látják ismét a kiemelt vezetők (pl. egy-egy miniszterelnök), de ez nem oldja meg azt, hogy bizonyos anyagokat elektronikusan lehet csak tárolni. Gondolhatunk itt a bűnüldözésben használt pl. ujjlenyomat vagy adóazonosítók listájára. A jegyzetben több ismert könyv anyagát használtam fel, megpróbálva az alapoktól bemutatni a titkosítási folyamatokat. E jegyzet gerincét adja a Buchman-féle jegyzet (lásd [1]), melyet kiegészít lineáris algebrai alapokkal a Gaál István-Kozma László jegyzet (lásd [4]). A kuriózumnak számító hátizsák probléma és az egyéb színes történetek a Liptai Kálmán (lásd [2]) és az Simon Singh (lásd [3]) által fémjelzett könyvekben is megtalálhatóak, melyek méltán lehetnek érdekesek az olvasóknak (is).

A jegyzetben lesznek olyan matematikai fogalmak és állítások, melyek tárgyalása más, felsőbb évfolyamokhoz kötött tárgyakban alapvető fogalmaknak vagy állításoknak minősülnek. A szerző feltételezi ezen tárgyak mélyebb ismeretét mint pl. analízis, diszkrét matematika, lineáris algebra.

A titkosítás alapjaként a következőket fogalmazhatjuk meg. Az adó, tradicionálisan Alice (A) bizalmas üzeneteket küld a nyilvános csatornán a vevőnek, akit Bob (B) személyesít meg. A bizalmas üzenetet természetesen úgy akarja kódolni, hogy

A klasszikus modellben Alice és Bob megállapodnak valamilyen általuk bonyolultnak talált eljárásban, amellyel üzeneteiket titkosítják és ezt mindketten titokban tartják.

Ha elég ügyesek és tisztességesek, akkor a lehallgató (Eve) csak az elfogott, kódolt üzenetek elemzésével nyerhet információt az aktuális adatcsere tartalmáról.

Mielőtt rátérnénk a kódolási sémákra és algoritmusokra röviden definiáljuk azokat a fogalmakat, amelyek segítségével egy-egy algoritmus jellemezhető.

Ha $ f$ és $ g$ két, természetes számokon értelmezett valós (esetleg komplex) értékű függvény, akkor

2. Kódolás

2.1. Kódolási sémák

A kriptográfia (cryptography) egyik tradicionális része a kódolás (encryption). A kódolási sémákat (encryption scheme) azért használunk, hogy megtartsunk üzeneteket vagy titkos adatokat tároljunk.

Először definiáljuk a kódolási sémákat:

Definíció:
Egy kódolási séma vagy kriptorendszer egy $ (\mathcal{P}, \mathcal{C}, \mathcal{K}, \mathcal{E}, \mathcal{D})$ ötös a következő tulajdonságokkal:

  1. $ \mathcal{P}$ , $ \mathcal{C}$ és $ \mathcal{K}$ véges halmazok, $ \mathcal{P}$ a nyílt szöveg tér, $ \mathcal{C}$ a rejtett szöveg tér és $ \mathcal{K}$ a kulcstér. $ \mathcal{P}$ elemeit nyílt szövegnek, $ \mathcal{C}$ elemeit rejtett szövegnek, $ \mathcal{K}$ elemeit kulcsoknak nevezzük. Egy üzenet a nyílt szöveg szimbólumaiból álló szó.

  2. $ \mathcal{E} = {E_k |k \in \mathcal{K}}$ azoknak az $ E_k \colon \mathcal{P} \to \mathcal{C}$ függvényeknek a családja, amelyeket a rejtjelezéshez használunk.
    $ \mathcal{D}= {D_k |k \in \mathcal{K}}$ azoknak a $ D_k\colon \mathcal{C} \to \mathcal{P}$ függvényeknek a családja, amelyeket a visszafejtéshez használunk.

  3. Mindegyik $ e\in \mathcal{K}$ kulcshoz van egy $ d\in \mathcal{K}$ kulcs, melyekre minden $ p\in \mathcal{P}$ nyílt szöveg esetén

    $\displaystyle D_d(E_e (p)) = p.
$

Példa:
Első példaként leírjuk a Caeser-féle titkosítást. A nyílt, a rejtett szövegtér és a kulcstér egyaránt a $ \Sigma = \{A, B, C, \ldots, Z\}$ halmazzal egyezik meg. Az $ A, B, C, \ldots, Z$ betűket az alábbi táblázattal azonosítjuk, felhasználva az $ 1, 2, 3, \ldots, 25$ számokat.

Táblázat: A betűk és a számok közötti kapcsolat.

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

A fenti táblázat segít bennünket, hogy betűkkel számoljunk. Például az $ e \in \mathbb{Z}_{26}$ kulcs esetén a megfelelő kódoló (rejtjelező) függvény a

$\displaystyle E_e\colon \Sigma \to \Sigma,\quad x \to (x + e) \mod 26.
$

Analóg módon adhatjuk meg egy $ d \in \mathbb{Z}_{26}$ dekódoló (visszafejtő) függvényt. A függvény a

$\displaystyle D_d\colon \Sigma \to \Sigma,\quad x \to (x - d) \mod 26.
$

Ebben az esetben a kódoló és dekódoló kulcs megegyezik ($ d = e$ ). Ez azonban nem minden kriptorendszerre érvényes.

A Caesar-féle titkosítás könnyen módosítható úgy, hogy a nyílt és a rejtett szövegtér az összes olyan $ \vec{\omega} = (\omega_1 , \omega_2 ,\ldots, \omega_n )$ szövegből áll, ahol $ \omega_i \in \Sigma$ , $ 1\leq i \leq n$ . Ekkor pl. az $ E_e$ függvény minden $ \omega_i$ betűt kicserél az $ \omega_i + e \mod 26$ -ra ( $ 1\leq i \leq n$ ). Ezt ugyancsak Caesar-féle titkosításnak nevezzük. Tekintsünk egy egyszerű kódolt feladatot. Az alábbi táblázatban látható egy magyar szöveg kódolása $ e = 3$ esetben (a modulus már nagyobb, mint 26).

Táblázat: Egy példa magyar szöveg kódolására.

B U D A P E S T K E L E T P Á R I Z S A
E X G D S H V W N H O H W S D U L C V D

(Az ékezetes betűk kódja ugyanaz, mint a megfelelő ékezet nélkülieké.)

Megjegyzés:
Egy kis történelem:

A fent ismertetett titkosítás neve nem véletlen: a római császár ezt használta háborúiban a katonai üzenetek titkosítására. Ez egy nagyon egyszerű un. ,,helyettesítéses'' titkosítás, amelyikben a nyílt szöveg minden betűjét a rejtjel ábécé egy meghatározott betűjével helyettesítenek.

Gaius Julius Caesar De Bello Gallico című művében tudósít arról, hogy a gall háborúban (58-50 Kr.e.) hogyan küldött egy rejtjelezett üzenetet Q. Tullius Ciceronak (a híres szónok testvéröccsének), aki légiójával ostrom alatt volt. Az alkalmazott rendszer monoalfabetikus volt és a latin betűket göröggel helyettesítette. Caesar írásaiból nem derül ki azonban az, hogy valóban a k = 3 kulcsú eltolásos titkosításról volt-e szó. Ezt az információt később Suetonius adta.

A fenti példa alapján is látható, hogy mivel a kulcstér nagyon kicsi, az eltolásos titkosítást igen könnyű feltörni. Ez a rejtjelzés már arra a támadásra is érzékeny, amelynek során a támadó csupán a rejtett szöveget ismeri. Ha egyszerűen a 26 lehetséges kulcs mindegyikét végigpróbáljuk, kiderül, hogy melyik kulcs esetén adódik értelmes nyílt szöveg, ha pedig a rejtett szöveg elég hosszú, csak egy megfelelő titkosítás adódik.

2.2. Ábécék és szavak

A szövegek készítéséhez szimbólumokra van szükség egy ábc-ből. Ábc alatt egy nem üres $ \Sigma$ halmazt értünk. A $ \Sigma$ hosszán a halmaz elemeinek számát értjük, az elemeket szimbólumnak vagy betűnek mondjuk.

Mivel az ábc-k véges halmazok, ezért jelölhetjük őket nemnegatív, egész számokkal.

Ha az ábc hossza $ m$ , akkor a betűk jelölhetőek számokkal a $ \mathbb{Z}_m = \{0, 1,\ldots m - 1\}$ -ből. Általában a $ \mathbb{Z}_m$ ábc-t használjuk. Definiáljuk a szavakat:

Definíció:
Legyen $ \Sigma$ egy ábc.

  1. Egy $ \Sigma$ feletti szó vagy sztring $ \Sigma$ -beli szimbólumok alkotta véges sorozat, melybe beletartozik az üres sorozat. Ennek a jele a $ \varepsilon$ és üres sztringnek nevezzük.
  2. Egy $ \Sigma$ feletti $ \vec{\omega}$ szó hossza a komponenseinek számát jelenti. Jelölése $ |\omega|$ . Az üres szó hossza 0.
  3. Az összes $ \Sigma$ feletti szavak halmazát, beleértve az üres szót is $ \Sigma^*$ -gal jelöljük.

  4. Ha $ \vec{v}, \vec{w} \in \Sigma^*$ , akkor $ \vec{v}\vec{w} =\vec{v}\circ \vec{w}$ egy olyan sztring, amelyet a két szó összefűzésével kaptunk. Nyilvánvalóan teljesül, hogy

    $\displaystyle \vec{v}\circ \varepsilon = \varepsilon \circ \vec{v} = \vec{v}.
$

  5. Ha $ n$ egy nemnegatív egész, akkor $ \Sigma^n$ jelöli az összes $ \Sigma$ feletti $ n$ hosszúságú szavak halmazát.

Például a Coca és a Cola összefűzésének eredménye CocaCola.

A Caesar-féle titkosítás monoalfabetikus kriptorendszer, mert a nyílt szöveg minden betűjének a rejtett szövegben mindig ugyanaz a betű felel meg. Ezzel szemben egy polialfabetikus kriptorendszerben lehetséges, hogy ugyanannak a nyílt szövegbeli szimbólumnak különböző rejtett szövegbeli szimbólumok felelnek meg, attól függően, hogy a szöveg melyik helyén állnak.

Egy ilyen polialfabetikus kriptorendszert, amelyik az eltolásos titkosításra épül, de jóval nehezebb feltörni, Blaise de Vigenère (1523-1596) francia diplomata javasolt. Rendszere Leon Battista Alberti (szül. 1404) itáliai matematikus, Johannes Trithemius (szül. 1492) német apát és Giovanni Porta (szül. 1535) itáliai természettudós előmunkáira épül. Ez a titkosítás úgy működik, mint az eltolásos titkosítás, azzal a különbséggel, hogy a betűk, amelyekkel a nyílt szöveg egy szimbóluma sifrírozva van, most még a szövegbeli helyüknek megfelelően is változnak.

Példa:
Vigenère-féle titkosítás

Ez a szimmetrikus polialfabetikus kriptorendszer egy úgynevezett Vigenère-négyzetet használ.

Táblázat: A Vigenèr-féle négyzet.

Image vigenere_negyzet

Ez egy 26 sorból és 26 oszlopból álló mátrix. Mindegyik sorban az ábécé 26 betűje szerepel, sorról sorra mindig egy pozícióval balra tolva. Ez azt jelenti, hogy az egyes sorok felfoghatók egy-egy eltolásos titkosításként, ahol a kulcsok sorban $ 0, 1,\ldots, 25$ . A szimbólum szövegbeli helyétől függ az, hogy a Vigenère-négyzet melyik sorát használja az ember egy nyílt szövegbeli szimbólum rejtésére.

Az üzeneteket $ n$ állandó hosszúságú blokkra osztjuk és blokkonként rejtjelezzük, vagyis $ \mathcal{K} = \mathcal{P} = \mathcal{C} = \mathbb{Z}^n_{26}$ . Az $ n$ blokkhosszat a rendszer periódusának is nevezik. Egy $ w$ szóban az $ i$ -edik betűt $ w_i$ -vel jelöljük.

Az $ E_k$ kódoló függvényt és a $ D_k$ dekódoló függvényt, amelyek mindketten $ \mathbb{Z}^n_{26}$ -ból $ \mathbb{Z}^n_{26}$ -be képeznek, mindegyik $ k\in \mathbb{Z}^n_{26}$ kulcs esetén a következőképpen definiáljuk:

$\displaystyle E_k (b) = (b + k) \mod 26,$    
$\displaystyle D_k (c) = (c - k) \mod 26,$    

ahol a $ k$ -val való összeadást és kivonást megint jelenként kell elvégezni modulo 26. Ekkor a megbeszélt $ k\in \mathbb{Z}^n_{26}$ kulcsot betűről betűre a $ b\in \mathbb{Z}^n_{26}$ blokk szimbólumai fölé írjuk. Ha a nyílt szöveg utolsó blokkjának kevesebb szimbóluma van, mint $ n$ , akkor a kulcsnak csak annyi jelét használjuk fel, amennyi szükséges. Amikor a nyílt szöveg $ i$ -edik $ b_i$ szimbólumát rejtjelezzük, fölötte a $ k_i$ kulcsszimbólum áll és a Vigenère-négyzet $ k_i$ -edik sorát használjuk eltolásos titkosításként.

Válasszuk például az $ n = 4$ blokkhosszat és a $ k = \mathnormal{TONY}$ kulcsot. A következő ábra egy angol nyelvű $ m$ nyílt szöveg kódolását mutatja, amelyik hét blokkból áll és a $ c$ rejtett szövegben a Vigenère-titkosítást alkalmaztuk a $ k$ kulccsal.

$ k$ T O N Y T O N Y T O N Y T O N Y T O N Y T O N Y T O N Y
$ m$ H U N G A R I A N I S A L L G R E E K T O G E R M A N S
$ c$ A I A E T F V Y G W F Y E Z T P X S X R H U R P F O A Q

A nyílt szöveg első betűjéhez, a ,,H''-hoz a ,,T'' kulcsszimbólumot rendeljük hozzá. A Vigenère-négyzet ,,H''-oszlopának és a ,,T''-sorának kereszteződésében ,,A'' található, ez lesz a rejtett szöveg első szimbóluma, amint azt a korábbi táblázatban is láthatjuk.

2.3. Szimmetrikus és asszimetrikus kriptorendszerek

Röviden elmagyarázzuk, hogy mi a különbség a szimmetrikus és az asszimetrikus kriptorendszerek között.

Ha Alice el akar küldeni egy kódolt üzenetet Bobnak, akkor ő egy $ e$ kulcsot használ és Bob használja a megfelelő kulcsot, hogy visszafejtse (dekódolja) az eredeti szöveget.

Ha egy kriptorendszerben az $ e$ kódoló kulcs mindig megegyezik a $ d$ dekódoló kulccsal, vagy $ d$ könnyen kiszámítható $ e$ -ből, akkor a kriptorendszert szimmetrikusnak nevezzük.

Ha Alice és Bob szimmetrikus kriptorendszert használ, akkor ki kell cserélniük a titkos $ e$ kulcsot mielőtt elkezdenek kommunikálni egymással. Viszont a biztonságos kulcscsere a fő probléma. Ugyanis az $ e$ kódoló kulcsot biztonságban kell tartani, mivel bárki, aki ismeri meghatározhatja a $ d$ dekódoló kulcsot.

A Caesar-féle titkosítás példa a szimmetrikus kriptorendszerre.

Az asszimetrikus kriptorendszerben a $ d$ és $ e$ kulcsok különbözőek és a $ d$ kiszámítása az $ e$ -ből kivitelezhetetlen. Az ilyen rendszerekben a kódoló kulcsok nyilvánosak.

Ha Bob fogadni akar kódolt szövegeket, akkor nyilvánossá kell tennie a saját $ e$ kódoló kulcsát, miközben a $ d$ dekódoló kulcsot titokban kell tartania. Bárki használhatja Bob $ e$ kulcsát, hogy üzenetet küldjön neki. Emiatt $ e$ -t nyilvános kulcsnak, a dekódoláshoz használt $ d$ kulcsot titkos kulcsnak nevezzük.

A fentiek miatt az asszimetrikus rendszereket szokás nyilvános kulcsú rendszereknek nevezni.

A nyilvános kulcsú rendszerekben két kulcstérre van szükség, hiszen a kétféle kulcs más alakot jelent. Emiatt kicsit módosítani kell a kriptorendszer definícióját.

2.4. Kriptoanalízis

A kriptoanalízis feladata az, hogy adott kriptorendszereket feltörjön, elsősorban azért, hogy a szükséges kulcsot a visszafejtéshez megállapítsa. Attól függően, hogy milyen információk állnak a kriptoanalízis rendelkezésére, a támadások több típusát lehet megkülönböztetni és ezzel a vizsgált kriptorendszer biztonságát, illetve sérülékenységét jellemezni.

A támadó (attacker) a kódolt üzenetből meg tudja mondani, hogy milyen kriptorendszert használnak és emellett megpróbál információt szerezni azokról az emberekről is, akik rendelkeznek hasznos információval a használatban levő kriptorendszerről.

A modern kriptoanalízis így feltételezi a támadóról, hogy tudja milyen kriptorendszert használnak. Csak a (titkos) kulcs és a nyílt szöveg tekinthető titkosnak.

A támadó megpróbálja visszaállítani a nyílt szöveget a kódoltból, vagy megpróbálja kitalálni a kulcso(ka)t.

A következő támadási típusok lehetségesek:

Rejtett szövegű támadás:
A támadó ismeri a kódolt/rejtett szöveget és megpróbálja visszakapni a megfelelő nyílt szöveget vagy a kulcsot.

Ismert nyílt szövegű támadás:
A támadó ismer egy nyílt szöveget és a hozzá tartozó kódolt szöveget (esetleg további ilyen párokat). Megpróbálja megtalálni a kulcsot és dekódolni vele más rejtett szövegeket.

Választott nyílt szövegű támadás:
A támadó képes kódolni a nyílt szövegeket, de nem ismeri a (titkos) kulcsot. Megpróbálja megtalálni a használt kulcsot vagy dekódolni más rejtett szövegeket.

Alkalmazkodóan választott nyílt szövegű támadás:
A támadó képes kódolni a nyílt szövegeket, továbbá képes kiválasztani újabb nyílt szövegeket, mint a kapott kódolt szövegek függvényeként, de nem ismeri a kulcsot. Megpróbálja megtalálni a használt kulcsot vagy dekódolni más rejtett szövegeket.

Választott rejtett szövegű támadás:
A támadó képes dekódolni, de nem ismeri a kulcsot. Megpróbálja megtalálni a kulcsot.

Sokféle módja van, hogy a fektiekben leírt támadásokat létrehozzuk. A legegyszerűbb rejtett szövegű támadás pl. tartalmazza az összes lehetséges kulcsot, amellyel dekódolhatjuk a rejtett szövegeket. Ezt kimerítő keresésnek is nevezzük.

Ez a leggyengébb formája a támadásnak és az a kriptorendszer, amelyik ennek a támadásnak sem áll ellen nem sokat ér.

Az ismert nyílt szövegű támadások gyakran a nyílt szöveg nyelvének statisztikai jellemzőit használják ki. Az ilyen támadások gyakran a rejtjelezett szövegben előforduló betűk gyakoriságát vizsgálják. Emellett a nyílt szöveg számára alkalmazott természetes nyelv redundanciáját is kihasználják.

Például sok természetes nyelvben az ,,E'' betű statisztikusan szignifikáns módon a leggyakrabban fordul elő. Hosszú ,,tipikus'' szövegek vizsgálata szerint az ,,E'' gyakorisága az angolban 12.31%, a franciában 15.87%, a németben pedig 18.46%. Más nyelvekben más betűk léphetnek fel a legnagyobb gyakorisággal.

,,Tipikus'' finn szövegekben például 12.06%-kal az ,,A'' a leggyakoribb betű.

A gyakoriságelemzés szemmel láthatóan hasznos a monoalfabetikus kriptorendszerek elleni támadás során. Ha például egy eltolásos módon kódolt német szövegben az ,,Y'' betű lép fel leggyakrabban, ami a németben - akárcsak a legtöbb nyelvben - ritka, akkor ebből arra következtethetünk, hogy ez az ,,E'' rejtett változata, az alkalmazott kulcs pedig az ,,U'' ($ k = 20$ , lásd a korábbi táblázatot). Az egyes betűk gyakorisága mellett vizsgálhatjuk a betűpárok (digrammok), a betűhármasok (trigrammok) stb. előfordulásait is. A támadásnak ez a módja működik a polialfabetikus kriptorendszerek esetében is, feltéve, hogy a periódus (vagyis a blokkhossz) ismert.

Az ismeretlen periódusú polialfabetikus kriptorendszerek ezzel szemben nagyobb biztonságot nyújtanak. A Vigenère-féle titkosítás például hosszú ideig ellenállt minden feltörési kísérletnek.

Csak 1863-ban, mintegy 300 évvel a feltalálása után, talált módszert Friedrich Wilhelm Kasiski német kriproanalitikus a Vigenère-féle titkosítás feltörésére. Megmutatta, hogyan lehet meghatározni az alkalmazott periódust a kulcsszöveg szavainak ismétlődéséből akkor is, ha a periódus kezdetben ismeretlen volt. Végül a gyakoriságelemzés segítségével a rejtjelezett szöveg visszafejthető. Singh írja, hogy a rendkívül sokoldalú Charles Babbage, akit sokan kora zsenijének tartanak, a Kasiski-féle módszert valószínűleg korábban, 1854-ben felfedezte, bár nem hozta nyilvánosságra.

A kriptográfia történetében mérföldkőként kell megemlítenünk Claude Shannonnak (1916-2001) a modern kód- és információelmélet atyjának úttörő munkáját.

Shannon bebizonyította, hogy vannak kriptorendszerek, amelyek egy bizonyos szigorú matematikai értelemben tökéletes titkosságot tesznek lehetővé. Pontosabban szólva egy kriptorendszer akkor tökéletes titkosságú, ha $ |\mathcal{C}| = |\mathcal{K}|$ , a kulcsok $ \mathcal{K}$ -ban egyenletes eloszlásúak, és minden $ p\in \mathcal{P}$ -re és minden $ c\in \mathcal{C}$ -re pontosan egy $ k\in \mathcal{K}$ kulcs van, amelyre $ E_k (p) = c$ . Ez azt jelenti, hogy egy ilyen kriptorendszer a legtöbb gyakorlati célra nem használható, mert ahhoz, hogy tökéletes titkosságot garantálhassunk, egyrészt minden kulcsnak legalább olyan hosszúnak kell lennie, mint a rejtjelezendő üzenet, másrészt egyszeri használat után minden kulcsot el kell dobni.

2.5. Permutációk

Annak érdekében, hogy bevezethessük a kódolási sémák egy nagyon általános osztályát, melyet blokk titkosításnak nevezünk (lásd a következő fejezetet) szükség van némi matematikai kitérőre a permutációkkal kapcsolatban.

Definíció:
Az $ ( 1,2,\ldots,n)$ számok egy sorrendjét ezen számok egy permutációjának nevezzük.

Jelölés:

  1. A permutációk halmazát $ P_n$ -nel jelöljük. Megjegyezzük, hogy $ |P_n|=n!$ .
  2. \begin{displaymath}
\pi=\left(
\begin{array}{cccc}
1 & 2 & \ldots & n \\
i_1 & i_2 & \ldots & i_n
\end{array}
\right)
\end{displaymath}

Definíció:
Az $ ( 1,2,\ldots,n)$ számok $ ( i_1,i_2,\ldots,i_n)$ permutációjában $ i_k$ inverzióban áll $ i_l$ -lel, ha $ k<l$ , de $ i_k>i_l$ $ (1\leq k<l\leq n)$ .

Jelölés:
Az $ ( i_1,i_2,\ldots,i_n)$ összes inverzióinak a számát $ I(i_1,i_2,\ldots,i_n)$ -nel jelöljük.

Példa:
Az $ ( 5,1,4,2,3 )$ permutáció inverzióinak száma 6.

Definíció:
Egy permutáció páros, ha összes inverzióinak száma páros, egyébként páratlan.

Lemma:
Bármely $ ( i_1,i_2,\ldots,i_n)$ permutáció létrehozható az $ ( 1,2,\ldots,n)$ -ből kiindulva, csak elempárok egymás utáni cseréjével.

Lemma:
Két elem cseréjénél az inverziók számának paritása ellenkezőjére változik.

Definíció:
A

\begin{displaymath}
\pi=\left(
\begin{array}{cccc}
1 & 2 & \ldots & n \\
i_1 & i_2 & \ldots & i_n
\end{array}
\right) \;\;\; \mbox{ és}\;\;\; \rho=\left(
\begin{array}{cccc}
1 & 2 & \ldots & n \\
j_1 & j_2 & \ldots & j_n
\end{array}
\right)
\end{displaymath}

permutációk szorzata

\begin{displaymath}\left(
\begin{array}{cccc}
1 & 2 & \ldots & n \\
j_{i_1} & j_{i_2} & \ldots & j_{i_n}
\end{array}
\right).
\end{displaymath}

Példa:

\begin{displaymath}\left(
\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5 \\
2 & 4 & 1 & 5 & 3
\end{array}
\right)\cdot\left(
\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5 \\
4 & 3 & 5 & 2 & 1
\end{array}
\right)
=
\left(
\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5 \\
3 & 2 & 4 & 1 & 5
\end{array}
\right)
\end{displaymath}

Megjegyzés:

  1. A szorzás nem kommutatív.
  2. A permutációk csoportot alkotnak $ (P_n,\cdot)$ , egységeleme az $ ( 1,2,\ldots,n)$ identikus permutáció.
  3. Egy $ \pi$ permutáció inverzén azt a $ \rho$ permutációt értjük, melyre $ \pi\rho$ az identikus permutáció.

Lemma:
Azonos paritású permutációk szorzata páros, ellenkező paritású permutációk szorzata páratlan.

Megjegyzés:
Könnyen ellenőrizhető, hogy a

\begin{displaymath}
\pi=\left(
\begin{array}{cccc}
1 & 2 & \ldots & n \\
i_1 & i_2 & \ldots & i_n
\end{array}
\right)
\end{displaymath}

permutáció inverze

\begin{displaymath}
\pi^{-1}=\left(
\begin{array}{rrrr}
i_1 & i_2 & \ldots & i_n\\
1 & 2 & \ldots & n
\end{array}
\right)
\end{displaymath}

Lemma:
Egy permutáció paritása megegyezik inverzének paritásával.

Legyen $ X =\{0, 1\}^n$ az összes $ n$ hosszúságú bitsztring halmaza.

Az $ X$ permutációja, amely a bitek helyének permutációját jelenti bit permutációnak nevezzük.

Formálisan a következőképpen adhatunk meg egy bit permutációt:

Legyen $ \pi\in P_n$ . Ekkor az

$\displaystyle f\colon \{0, 1\}^n \to \{0, 1\}^n,\quad b_1\ldots b_n \to b_{\pi(1)} \ldots b_{\pi(n)}
$

egy bit permutáció. Speciális bit permutációk a balra vagy jobbra ciklikus bitpermutációk. A balra $ i$ ciklikus permutáció a ( $ b_0, b_1 ,\ldots, b_{n-1}$ ) bitsztringből a ( $ b_{i \mod n}, b_{(i+1) \mod n},\ldots , b_{(i+n-1) \mod n}$ ) bitsztringet állítja elő. A jobbra lépő változatok analóg módon adhatóak meg.

2.6. Blokk titkosítás

Definíció:
Egy kriptorendszert blokk titkosításnak nevezünk, ha a nyílt és a rejtett szövegtér egy $ \Sigma$ ábc feletti rögzített $ n$ hosszúságú szavak $ \Sigma^n$ halmazával egyezik meg. Az $ n$ blokk hosszúság egy pozitív egész szám.

Nyilvánvalóan a Caesar-féle titkosítás egy blokk titkosítás, melynek a blokk hosszúsága 1 (ezért az ilyen blokk hosszúságú blokk titkosításokat helyettesítő titkosításnak is nevezik).

Tétel:
Egy blokk titkosítás kódoló függvényei a permutációk.

A tétel alapján a következő általános módon adható meg a blokk titkosítás.

Rögzítsük az $ n$ blokk hosszúságot és a $ \Sigma$ ábc-t. Ekkor $ \mathcal{P} = \mathcal{C} = \Sigma^n$ . A kulcstér a $ \Sigma$ összes permutációjának $ P(\Sigma^n)$ halmaza. A kódoló függvény egy $ \pi\in P(\Sigma^n)$ kulcs esetén az

$\displaystyle E_{\pi}\colon \Sigma_n \to \Sigma^n,\quad \vec{v} \to \pi(\vec{v}).
$

A megfelelő dekódoló függvény a

$\displaystyle D_{pi}\colon \Sigma^n \to \Sigma^n,\quad \vec{v} \to \pi^{-1}(\vec{v}).
$

Ezen rendszerben a kulcstér elég nagy, ti. a kulcsok száma $ (|\Sigma|^n)!$ . Emiatt ez a séma elég biztonságosnak tűnik. Azonban nem világos, hogy miképpen válasszunk ki egy megfelelő permutációt, hogyan történjen hatékonyan a kiértékelés stb. (egyszóval ineffektív). Ezért a kulcstérnek csak egy részhalmazát fogjuk használni.

Példa:
Egy lehetséges példaként adódik a permutációs titkosítás. Ez csak permutációt használ, hogy permutálja a szimbólumok helyét. Ha $ \Sigma = \{0, 1\}$ , akkor ezek éppen a bitpermutációk. A kulcstér a $ P_n$ és legyen $ \pi\in P_n$ , továbbá

$\displaystyle E_{\pi}\colon \Sigma^n \to \Sigma^n,\quad (\nu_1 , \ldots, \nu_n) \to (\nu_{\pi(1)} ,\ldots, \nu_{\pi(n)})
$

és

$\displaystyle D_{\pi}\colon \Sigma^n \to \Sigma^n,\quad (\chi_1 ,\ldots , \chi_n) \to (\chi_{\pi^{-1}(1)} ,\ldots , \chi_{\pi^{-1} (n)} )
$

A kulcstér $ n!$ elemű. Minden kulcs úgy van kódolva mint egy $ n$ hosszúságú egész sorozat a $ [0,1,\ldots,n-1]$ halmazból.

2.7. Többszörös kódolás és blokk kódolás

A blokk titkosítás biztonságának érdekében érdemes azt többször végrehajtani. Például az $ E - D - E$ háromszoros titkosítást használhatjuk. Ekkor egy $ p$ nyílt szöveget a következőképpen kódolunk:

$\displaystyle c = E_{k_1} (D_{k_2} (E_{k_3} (p))),
$

ahol $ k_i$ , ( $ 1 \leq i \leq 3$ ) a kulcs. Ez a kulcstér növekedését eredményezi. Ha csak duplázni akarjuk a kulcs hosszát, akkor legyen $ k_1 = k_3$ .

Először tekintsük át, hogy milyen módon lehet tetszőleges hosszúságú dokumentumot kódolni.

2.7.1. ECB mód

Jelölje $ \Sigma$ az ábc-t, a blokk hosszúság pedig legyen $ n$ . Az ECB kifejezés az electronic codebook rövidítésből származik.

Tetszőleges hosszúságú nyílt szöveget $ n$ hosszúságú blokkokra bontunk. Ha szükséges, elérjük, hogy a nyílt szöveg hossza $ n$ -nel osztható legyen. Ha a kulcs $ e$ , akkor minden $ n$ hosszúságú tömböt kódolunk az $ E_e$ kulccsal. Nyilvánvalóan egy rejtjelezett szövegsorozatot kapunk, melyet a megfelelő $ D_d$ -vel dekódolunk (a $ d$ az $ e$ -hez tartozó megfelelő kulcs).

Példa:
Tekintsünk egy blokk kódolót, mely a bit permutációkat használja 4 hosszúság (bit)vektorokon. Ekkor $ \Sigma = \{0, 1\}$ , blokk hosszúság 4 és $ \mathcal{K} = P_4$ . Kódoljuk a következő nyílt szöveget:

$\displaystyle m = 101100010100101.
$

Felbontjuk 4 hosszúságú blokkokra. Az utolsó blokk hossza 3. Ezért tegyünk hozzá még egy 0-t, azaz a

$\displaystyle m = 1011\ 0001\ 0100\ 1010
$

kapjuk és a blokkok rendre: $ m_1 = 1011$ , $ m_2 = 0001$ , $ m_3 = 0100$ , $ m_4 = 1010$ . Használjuk a

$\displaystyle \pi=\left(\begin{array}{cccc}
1&2&3&4\\
2&3&4&1\\
\end{array}\right)
$

kulcsot. A blokkokat külön kódoljuk, és a $ c_1 = E_{\pi} (m_1 ) = 0111$ , $ c_2 = E_{\pi} (m_2 ) = 0010$ , $ c_3 = E_{\pi} (m_3 ) = 1000$ , $ c_4 = E_{\pi} (m_4 ) = 0101$ sorozatot kapjuk. A teljes kódolt szöveg a

$\displaystyle c = 0111001010000101.
$

Amikor ECB-t használunk, akkor egyforma méretű blokkokat kódolunk egyforma méretű rejtjelezett blokkokra. Ez lehetőséget ad felfedezni mintaelemeket a nyílt szövegben a rejtett szöveg segítségével, azaz egy statisztikai támadás könnyen célt ér.

Másrészt a támadó helyettesíthet rejtjelezett blokkokat más rejtjelezett blokkokkal, melyet ugyanazzal a kulccsal kódoltak. Ezt a manipulációt a fogadó nehezen veheti észre, azaz nagy méretű szövegeket nem érdemes ECB mód segítségével kódolni.

Az ECB mód biztonsága azzal növelhető, ha minden blokk egy bizonyos része véletlenszerűen van megválasztva, miközben a fennmaradó rész a nyílt szövegből származik. De emiatt sok bitet kell véletlenszerűen generálni, és még több blokkot kódolni. Ez viszont rontja az ECB hatékonyságát.

2.7.2. CBC mód

A CBC név az chiperblock chaning-re utal. Ez már elkerüli az ECB problémáit, ugyanis egy blokk kódolása nem csak a kulcstól, hanem az azt megelőző blokktól is függ. Ekkor a kódolás kontextus (környezet) függő. Ugyanaz a blokk más környezetben másképpen kerül kódolásra. A fogadó így meg tudja mondani, hogy a rejtett szöveg módosult-e, hiszen a manipulált szöveg dekódolása nem működik.

Tekintsük a $ \Sigma = \{0, 1\}$ ábc-t, legyen $ n$ a blokkhosszúság. Szükség van egy definícióra:

Definíció:
A

$\displaystyle \oplus\colon \{0, 1\}^2 \to \{0, 1\},\quad b\oplus c\to b\oplus c
$

leképezést a következő táblázattal definiáljuk:

$ b$ $ c$ $ b\oplus c$
0 0 0
1 0 1
0 1 1
1 1 0

Ezt a leképezést kizáró vagynak nevezünk, röviden XOR. Tetszőleges $ b = (b_1 , b_2 ,\ldots, b_k )$ , $ c = (c_1 , c_2 ,\ldots, c_k ) \in \{0, 1\}^k$ esetben legyen

$\displaystyle b \oplus c = (b_1 \oplus c_1 , b_2 \oplus c_2 ,\ldots , b_k\oplus c_k).
$

Ha az elemek a $ \mathbb{Z}/2\mathbb{Z}$ csoportból kerülnek ki és a 0,1-gyel adjuk meg a reprezentánsokat, akkor a kizáró vagy éppen az összeadás a csoportban.

A CBC mód felhasznál egy kezdetiérték vektort (inicializációs vektor), jelöljük $ IV$ -vel, melyet nyilvánossá kell tenni. Hasonlóan az ECB módhoz itt is $ n$ hosszúságú blokkokra bontjuk a nyílt szöveget. Ha Alice kódolja az $ m_1 , m_2 ,\ldots, m_t$ $ n$ -hosszúságú blokkok sorozatát az $ e$ kulccsal, akkor a következőket kapja:

$\displaystyle c_0 = IV,\quad c_j = E_e (c_{j-1} \oplus m_j),\quad 1 \leq j \leq t,
$

melyből a kódolt üzenet a $ c = c_1 c_2 \ldots c_t$ lesz.

A dekódoláshoz Bob használja a $ d$ kulcsot (melyre érvényes a $ D_d (E_e (w)) = w$ ), azaz kiszámolja a

$\displaystyle c_0 = IV,\quad m_j = c_{j-1}\oplus D_d (c_j ),\quad 1\leq j\leq t
$

értékeket.

Voltaképpen megkapja a $ c_0\oplus D_d(c_1)=c_0\oplus c_0\oplus m_1=m_1$ -et. Analóg módon megmutatható, hogy a többi szövegrész is korrekt lesz.

Példa:
Tekintsük a következő példát a korábbi, ECB mód esetén megadott feltételekkel. A nyílt szöveg blokkjai:

$\displaystyle m = 1011\ 0001\ 0100\ 1010.
$

A kulcs ismét a

$\displaystyle \pi=\left(\begin{array}{cccc}
1&2&3&4\\
2&3&4&1\\
\end{array}\right)
$

és az inicializációs vektor legyen $ IV = 1010$ . Ekkor $ c_0 = 1010$ , $ c_1 = E_{\pi} (c_0\oplus m_1 ) = E_{\pi} (0001) = 0010$ , $ c_2 = E_{\pi} (c_1\oplus m_2) = E_{\pi} (0011) = 0110$ , $ c_3 = E_{\pi} (c_2 \oplus m_3) = E_{\pi} (0010) = 0100$ , $ c_4 = E_{\pi} (c_3 \oplus m_4) = E_{\pi} (1110) = 1101$ , azaz a teljes rejtett szöveg

$\displaystyle c = 0010011001001101.
$

A dekódoláshoz, azaz az $ m_1,\ldots,m_4$ meghatározásához az $ m_1 = c_0 \oplus E_{\pi}^{-1} (c_1)=1010\oplus0001=1011$ , $ m_2 = c_1 \oplus E_{\pi}^{-1} (c_2)=0010\oplus 0011=0001$ , $ m_3 = c_2 \oplus E_{\pi}^{-1} (c3)=0110\oplus0010=0100$ , $ m_4 = c_3 \oplus E_{\pi}^{-1} (c_4)=0100\oplus 1110=1010$ számításokat kell elvégezni.

Általában a CBC mód ugyanazt a nyílt szöveget különböző módon kódolja különböző inicializációs vektor esetén, mivel a blokkok kódolása a megelőző blokktól is függ. Így ha a rejtjelezett blokkok sorrendje megváltozik vagy ha egy rejtjelezett blokkot kicserélnek, akkor a dekódolás lehetetlen. Ez előny az ECB-vel szemben.

Viszont megjelenhet az átviteli hiba. Egy nyílt szöveg $ m_j$ blokkja a $ c_j$ és a $ c_{j-1}$ kódolt blokkokból számítható ki. Ha pl. a $ c_j$ rejtjelezett blokk nem jut el korrekten a fogadóhoz, akkor az $ m_j$ és a $ m_{j+1}$ is inkorrekt lesz. De a további $ m_{j+2} , m_{j+3},\ldots$ blokkokra már nincs hatással. Ezeket hiba nélkül meg lehet határozni.

2.7.3. CFB mód

Láttuk, hogy a CBC mód alkalmas hosszú üzenetek kódolására, azonban a valós idejű (azaz még a fogadás közben szeretnénk dekódolni az üzenetet, mint ahogy régen a távírászok tették) alkalmazásokban hatékonysági probléma lép fel. A valós idejű kódoláshoz és dekódoláshoz például biztonságos telefon vonal kell. A rejtett szöveg elkészítéséhez Alice alkalmazza a kódoló függvényt, majd amikor elkészült a kódolás, elküldi a blokkot Bobnak, aki alkalmazza a dekódoló függvényt, azaz a kódolás és dekódolás szekvenciálisan megy. Ez így időben költséges.

A CFB módban (chipher feedback) a kódoló függvényt nem közvetlenül használjuk a blokkok kódolására, hanem inkább kulcs blokkokat generálunk vele.

A nyílt szöveg kódolása ezen kulcs blokkokkal úgy történik, hogy a blokkokat összeadjuk$ \mod 2$ . A titkosított szöveg dekódolása ugyancsak a rejtjelezett blokkok hozzáadását jelenti$ \mod 2$ . A kulcs blokkokat szimultán generálhatja a küldő (Alice) és a fogadó (Bob) is. Csak az összeadások$ \mod 2$ zajlanak szekvenciálisan.

A korábbi CBC módban használt blokk kódolást használjuk.

Szükség van egy inicilizációs vektorra $ IV\in\{0, 1\}^n$ és egy $ r \in \mathbb{Z}^+$ , ahol $ 1 \leq r \leq n$ . A nyílt szöveget felbontjuk $ r$ hosszúságú blokkokra. Az $ m_1, m_2, \ldots, m_u$ sorozat kódolásához Alice beállítja

$\displaystyle I_1 = IV
$

értéket. Továbbá minden $ 1 \leq j \leq u$ -ra végrehajtja a következőket:

  1. $ O_j = E_k (I_j)$ ,
  2. $ t_j$ -be kerül az $ O_j$ első $ r$ db bitje,
  3. $ c_j = m_j \oplus t_j$ ,
  4. $ I_{j+1} = 2^r I_j + c_j \mod 2^n$ , így $ I_{j+1}$ úgy készül, hogy az első $ r$ bit törlődik, majd hozzáfűzzük a $ c_j$ -t.
A kódolt szöveg nyilvánvalóan a $ c_1, c_2,\ldots c_u$ .

A dekódolás hasonlóan megy. Bob beállítja a

$\displaystyle I_1 = IV
$

értéket és minden $ 1 \leq j \leq u$ -ra végrehajtja a következőket:

  1. $ O_j = E_k (I_j)$ ,
  2. $ t_j$ -be kerül az $ O_j$ első $ r$ db bitje,
  3. $ m_j = c_j \oplus t_j$ ,
  4. $ I_{j+1} = 2^r I_j + c_j \mod 2^n$ .
Alice és Bob azonnal ki tudja számolni a $ t_{j+1}$ sztringet, amint ismeri a rejtjelezett $ c_j$ blokkot. Így a $ t_1$ kulcs blokkot szimultán számolják ki. Ezután Alice generálja a $ c_1 = m_1 \oplus t_1$ -et és elküldi Bobnak. A $ c_1$ kiszámítása gyorsan megy, hiszen csak a XOR kell hozzá. Ezután megy a többi kulcs blokk szimultán meghatározása.

Példa:
Legyen minden objektum megadása ugyanaz, mint a korábbi példákban, továbbá válasszuk $ r$ -et 3-nak. Ekkor a blokkok a következők lesznek:

$\displaystyle m_1 = 101,\quad m_2 = 100,\quad m_3 = 010,\quad m_4 = 100,\quad m_5 = 101.
$

Legyen a kulcs megint a

$\displaystyle \pi=\left(\begin{array}{cccc}
1&2&3&4\\
2&3&4&1\\
\end{array}\right)
$

és az inicializációs vektor $ IV = 1010$ . A CFB mód ekkor a következőket eredményezi:

$ j$ $ I_j$ $ O_j$ $ t_j$ $ m_j$ $ c_j$
1 1010 0101 010 101 111
2 0111 1110 111 100 011
3 1011 0111 011 010 001
4 1001 0011 001 100 101
5 1101 1011 101 101 000

A CFB módban az átviteli probléma elrontja a dekódolást az $ I_j$ vektorban levő hibás, kódolt rész hosszában. Fontos megjegyezni, hogy a CFB nem használható a nyilvános kulcsú kriptorendszerekkel, mert a küldő és a fogadó is ugyanazzal az $ e$ kulccsal rendelkezik.

2.7.4. OFB mód

Az OFB a output feedback rövidítése. Hasonló a CFB-hez, ugyanis egy blokk kódolót használ $ n$ blokkhosszal, továbbá egy másik $ r$ blokkhosszt is használ az $ I_1$ inicializáló vektor mellett.

Ha Alice kódol egy nyílt szöveget, akkor hasonlóan a CFB-hez azt $ r$ hosszúságú blokkokra vágja szét (ahol a blokkok száma $ u$ ). Ezután végrehajtja a következőket minden $ 1 \leq j \leq u$ -ra:

  1. $ O_j = E_k (I_j)$ ,
  2. $ t_j$ -be kerül az $ O_j$ első $ r$ db bitje,
  3. $ c_j = m_j \oplus t_j$ ,
  4. $ I_{j+1} = O_j$ .
A dekódolás analóg módon megy, csak a 3. lépést kell kicserélni a $ m_j = c_j \oplus t_j$ -re.

Ha egy kódolt rész egy bitje rosszul kerül a fogadóhoz (átviteli hiba), akkor a nyílt szövegben pontosan ugyanaz a hely lesz rossz. Ennek a rossz bitnek nincs további hatása.

A $ t_j$ kulcs blokk csak az $ I_1$ inicializációs vektortól és a $ k$ kulcstól függ. Ezeket a küldő és a fogadó szimultán kiszámolhatja. Ez így jobb, mint a CFB mód, azonban a kódolás így nem függ a blokkot megelőző résztől, csak a saját pozíciójától. Emiatt a kódolt szöveggel való manipuláció könnyebb az OFB-ben, mint a CFB-ben.

Példa:
Ismét a korábbi példákban is használt paramétereket használjuk. Legyenek ismét a nyílt szöveg blokkjai a következők:

$\displaystyle m_1 = 101,\quad m_2 = 100,\quad m_3 = 010,\quad m_4 = 100,\quad m_5 = 101.
$

Továbbá legyen a kulcs megint a

$\displaystyle \pi=\left(\begin{array}{cccc}
1&2&3&4\\
2&3&4&1\\
\end{array}\right)
$

és az inicializációs vektor $ IV = 1010$ . A OFB mód ekkor a következőket eredményezi:

$ j$ $ I_j$ $ O_j$ $ t_j$ $ m_j$ $ c_j$
1 1010 0101 010 101 111
2 0101 1010 101 100 001
3 1010 0101 010 010 000
4 0101 1010 101 100 001
5 1010 0101 010 101 111

Ha ugyanazt a $ k$ kulcsot használjuk a két nyílt szöveg kódolásához, akkor az inicializációs vektort cserélni kell. Egyébként ugyanaz a $ t_j$ kulcs blokk sorozat generálódik és mindkét $ c_j = m_j \oplus t_j$ és $ c'_j = m'_j \oplus t'_j$ kódolt blokk felhasználásával a támadó visszakapja a $ c_j \oplus c'_j = m_j \oplus m'_j$ kifejezést. Így képes meghatározni az $ m'_j$ -t, ha ismeri $ m_j$ -t.

2.8. Folyam titkosítás

Röviden vegyük át, hogyan lehet kódolni tetszőlegesen nagy nyílt szövegeket úgy, hogy az önálló, nyílt szöveg blokkok kódolása a saját környezetüktől függjön.

Ezt az alapelvet általánosították a folyam titkosításban.

Csak egy példát adunk egy folyam kódolóra.

Egy jól ismert folyam kódoló a következőképpen működik:

A $ \Sigma = \{0, 1\}$ . A nyílt és a rejtett szövegtér a $ \Sigma^*$ . A kulcstér a $ \Sigma^n$ , ahol $ n \in\mathbb{N}$ . A $ \Sigma^*$ -beli szavak bitenként kerülnek kódolásra a következő módon:

Legyen $ k = (k_1 , k_2 ,\ldots, k_n)$ egy kulcs és $ w = \sigma_1 \sigma_2 \ldots \sigma_m$ egy $ m$ hosszúságú szó a $ \Sigma^*$ -ból. Alice generál egy $ z_1 , z_2 , \ldots, z_m$ kulcssorozatot, ugyanis

$\displaystyle z_i = k_i,\quad 1\leq i\leq n
$

és $ m > n$ esetben

$\displaystyle z_i =\sum^n_{j=1} c_j z_{i-j} \mod 2, n < i \leq m,
$

ahol $ c_1 , c_2 ,\ldots , c_n$ rögzített együtthatók.

Az ilyen típusú egyenleteket hívjuk $ n$ -edfokú lineáris rekurzív egyenleteknek. Az $ E_k$ kódoló és a $ D_k$ dekódoló függvények megadása a következő:

$\displaystyle E_k(w) = \sigma_1 \oplus z_1,\ldots, \sigma_m \oplus z_m,\quad D_k(w) = \sigma_1 \oplus z_1,\ldots, \sigma_m \oplus z_m.
$

Példa:
Legyen $ n = 4$ . A kulcs folyam a következő rekurzióval legyen előállítva:

$\displaystyle z_{i+4} = z_i + z_{i+1}.
$

Válasszuk meg a $ c_i$ -ket a következőképpen: $ c_1 = c_2 = 0$ , $ c_3 = c_4 = 1$ . Legyen $ k = (1, 0, 0, 0)$ a kulcs. Ekkor a következő kulcssorozatot kapjuk:

Image seq

Ez a kulcssorozat periódikus, a periódus 15.

A fenti folyamkódoló implemetált a hardware-ben mint lineáris eltolásos regiszter.

2.9. Affin kódolás

Legyen $ m$ egy pozitív egész. Az affin kódoló egy $ \mathbb{Z}_m$ ábc-vel rendelkező blokk kódoló 1 blokk hosszúsággal. A kulcstér az összes $ (a, b) \in \mathbb{Z}^2_m$ párból áll, ahol $ a$ és $ m$ relatív prímek. Az $ E_k$ kódoló függvény az $ k = (a, b)$ kulcsra nézve a

$\displaystyle E_k\colon \Sigma \to \Sigma,\quad x \to ax + b \mod m,
$

a $ D_k$ dekódoló függvény pedig a $ k = (a' , b)$ -re a

$\displaystyle D_k\colon \Sigma \to \Sigma,\quad x \to a' (x - b) \mod m
$

megadással rendelkezik. Egy dekódoló kulcs meghatározásához, amely az $ (a, b)$ kulcshoz tartozik meg kell oldanunk az $ aa' \equiv 1
\mod m$ egyenletet. Ekkor a dekódoló kulcs az $ (a' , b)$ lesz.

Példa:
Ha Alice az $ m = 26$ , $ (a, b) = (7, 3)$ beállításokat teszi meg és kódolja azt a német szót, hogy ,,BALD'' az affin kódolóval ECB módban, akkor a következőt kapja:

B A L D
1 0 11 3
10 3 2 24
K D C Y

Bob kiszámolja a megfelelő dekódoló függvényt, azaz meghatároz egy $ a'$ egész számot, melyre $ 7a' \equiv 1 \mod 26$ . Innen kapja az $ a' = 15$ megoldást. Így a dekódoló függvény egy $ \sigma$ szimbólumhoz a $ 15(\sigma - 3) \mod 26$ -ot rendeli. Így Bob valóban visszakapja a ,,BALD'' szót:

K D C Y
10 3 2 24
1 0 11 3
B A L D

Az affin kódoló kulcstere az $ m = 26$ miatt $ \varphi(26) \cdot 26 = 312$ elemet tartalmaz. Így, ha a kódolót ECB módban használjuk, akkor feltörhető egy rejtett szövegű támadással (a teljes kulcstéren való kimerítő keresés által). Ismert nyílt szövegű támadás esetén, ha két szimbólum ismert a kódolásukkal együtt, akkor az affin kódolás feltörhető csupán egyszerű lineáris algebrai számolással. Ezt mutatja be a következő példa:

Példa:
Azonosítsuk az $ \{A, B, \ldots , Z\}$ ábc-t a $ \mathbb{Z}_{26}$ -tal a szokásos módon. Ha a támadó tudja, hogy az affin kódolás alkalmazásánál (rögzített $ (a, b)$ kulcs esetén) az $ E$ betű képe $ R$ és $ S$ képe $ H$ , akkor a következő kongruenciákat kapja:

$\displaystyle 4a + b \equiv 17 \mod 26,\quad 18a + b \equiv 7 \mod 26.
$

Az első konguenciából kapja a $ b \equiv 17 - 4a \mod 26$ -ot. Ezt használva a második kongruenciában kapja a $ 18a + 17 - 4a \equiv 7
\mod 26$ és így $ 14a \equiv \mod 26$ . Ebből $ 7a \equiv 8 \mod 13$ . Megszorozva ezt a 7 inverzével modulo 13 (ez a 2), kapjuk a $ a \equiv 3 \mod 13$ , azaz választhatjuk az $ a = 3$ és a $ b = 5$ értékeket.

2.10. Affin lineáris függvények

Az affin lineáris függvények felhasználhatóak egyszerű blokk titkosításra.

Definíció:
Egy $ f\colon R^n \to R^l$ függvényt affin lineárisnak nevezünk, ha létezik egy $ A\in R^{(r,l)}$ mátrix és egy $ \vec{b}\in R^l$ vektor, hogy

$\displaystyle f (\vec{v}) =(A\vec{v} + \vec{b})
$

minden $ \vec{v}\in R^n$ . Ha $ \vec{b} = 0$ , akkor a függvényt lineárisnak nevezzük.

Hasonlóan adható meg az affin lineáris függvény a $ \mathbb{Z}^n_m \to \mathbb{Z}^l_m$ esetben:

Definíció:
Egy $ f\colon \mathbb{Z}^n_m \to \mathbb{Z}^l_m$ függvényt affin lineárisnak nevezünk, ha létezik egy $ A \in \mathbb{Z}^{(r,l)}$ mátrix és egy $ \vec{b}\in \mathbb{Z}^l_m$ vektor, hogy

$\displaystyle f (\vec{v}) = (A\vec{v} + \vec{b}) \mod m
$

minden $ \vec{v} \in \mathbb{Z}^n_m$ . Ha $ b\equiv 0 \mod m$ , akkor a függvényt lineárisnak nevezzük.

Tétel:
Az affin lineáris függvény ( $ R^n \to R^l$ ) pontosan akkor bijektív ha $ l = n$ és $ \det A$ egység az $ R$ -ben.

Tétel:
Az affin lineáris függvény ( $ \mathbb{Z}^n_m \to \mathbb{Z}^l_m$ ) pontosan akkor bijektív ha $ l = n$ és $ \det A$ relatív prím $ m$ -re vonatkozólag.

Példa:
Tekintsük a következő $ f\colon \{0, 1\}^2 \to \{0, 1\}^2$ függvényt, amely következő módon van definiálva:

$\displaystyle f (0, 0) = (0, 0);\ f (1, 0) = (1, 1);\ f (0, 1) = (1, 0);\ f (1, 1) = (0, 1).
$

Ez a leképezés lineáris, mert $ f (\vec{v}) =\left(\begin{array}{cc}1&1\\ 0&1\end{array}\right)\vec{v}$ minden $ \vec{v} \in \{0, 1\}^2$ -re.

Tétel:
Egy $ f\colon R^n \to R^n$ függvény pontosan akkor lineáris, ha

$\displaystyle f (a\vec{v} + b\vec{w}) = af(\vec{v}) + bf(\vec{w})
$

minden $ \vec{v}, \vec{w} \in R^n$ és $ a, b \in R$ esetben. Pontosan akkor affin lineáris, ha az $ R^n \to R^n$ , $ \vec{v} \to f(\vec{v}) - f (\vec{0})$ lineáris.

2.11. Affin lineáris blokk titkosítás

Ezek az affin eset általánosításai. Megmutatjuk, hogy ezek alapvetően könnyen támadhatóak. Ez vezet majd egy törvényszerűségre: a biztonságos blokk kódolás nem lehet lineáris vagy könnyen közelíthető lineáris függvényekkel.

Legyen $ n, m$ pozitív egész számok, ahol $ m > 2$ .

Definíció:
Egy $ n$ hosszúságú blokk kódolót és a $ \mathbb{Z}_m$ nyílt-, rejtett szövegteret együtt affin lineárisnak nevezzük, ha ennek az összes kódoló függvénye affin lineáris. Lineárisnak nevezzük, ha az összes kódoló függvény lineáris.

Az affin lineáris blokk kódolók explicite leírhatóak, mivel a kódoló függvények affin lineárisak, azaz

$\displaystyle E\colon \mathbb{Z}^n_m \to \mathbb{Z}^n_m,\quad \vec{v} \to A\vec{v} + \vec{b} \mod m,
$

ahol $ A \in \mathbb{Z}^{(n,n)}$ és $ \vec{b}\in \mathbb{Z}^n$ . Az $ E$ bijektív, így $ \det A$ relatív prím az $ m$ -re, azaz a kódoló függvényt egyértelműen meghatározza az $ (A, \vec{b})$ pár. Ezt a párt fogjuk kulcsként használni.

Ekkor a megfelelő dekódoló függvény a

$\displaystyle D\colon \mathbb{Z}^n_m \to \mathbb{Z}^n_m,\quad \vec{v} \to A' (\vec{v} - \vec{b}) \mod m,
$

ahol $ A = \left(a'\right.$   adj$ \left.A\right) \mod m$ ( adj$ A = (-1)^{i+j} \det A_{j,i}$ ) és $ a'$ az inverze a $ \det A$ -nak modulo $ m$ .

2.12. Vigenére, Hill és permutáció titkosítás

Két ismert affin lineáris titkosítást nézünk meg.

Az első a Vigenère titkosítás (Blaise Vigenère), ahol a kulcstér $ \mathcal{K} = \mathbb{Z}^n_m$ . Ha $ \vec{k} \in \mathbb{Z}^n$ , akkor

$\displaystyle E_{\vec{k}}\colon \mathbb{Z}^n_m \to \mathbb{Z}^n_m,\quad \vec{v} \to \vec{v}+\vec{k} \mod m,
$

és

$\displaystyle D_{\vec{k}}\colon \mathbb{Z}^n_m \to \mathbb{Z}^n_m,\quad \vec{v} \to \vec{v} - \vec{k} \mod m.
$

Ezek affin lineárisak, a kulcstér elemeinek száma $ mn$ .

A másik jól ismert titkosítás a Hill-féle.

Ezt Lester S. Hill találta fel 1929-ben. A kulcstér $ \mathcal{K}$ az összes $ A \in \mathbb{Z}^{(n,n)}$ mátrix, ahol lnko$ (\det A, m) = 1$ .

A kódoló függvény ekkor egy $ A\in \mathcal{K}$ kulcs esetén a

$\displaystyle E_A\colon \mathbb{Z}^n_m \to \mathbb{Z}^n_m,\quad \vec{v} \to A\vec{v} \mod m.
$

Így a Hill-féle titkosítás a legáltalánosabb lineáris blokk titkosításnak felel meg.

Végül megmutatjuk, hogy a permutációs titkosítás lineáris. Legyen $ \pi\in P_n$ és jelölje $ \vec{e}_i$ ( $ 1\leq i \leq n$ ) az egységmátrix sorait (szokás ezeket egységvektoroknak is nevezni). Továbbá legyen $ E_{\pi}$ egy olyan $ n \times n$ típusú mátrix, melynek az $ i$ -dik sorában az $ \vec{e}_{\pi(i)}$ áll. Ezt a mátrixot az $ n \times n$ -es identikus mátrixból kapjuk a $ \pi$ permutáció segítségével történő sorpermutálásból.
Az $ E_{\pi}$ $ j$ -dik oszlopa az $ \vec{e}_{\pi(j)}$ egységvektor. Bármely $ \vec{v} = (v_1 ,\ldots, v_n ) \in \Sigma^n$ -re kapjuk, hogy a $ (v_{\pi(1)},\ldots, v_{\pi(n)}) = E_{\pi} \vec{v}$ .
Így a permutáció titkosítás lineáris, lényegében a Hill-féle titkosítás speciális esete.

2.13. Az affin lineáris blokk titkosítás kriptoanalízise

Nézzük meg, hogy lehet feltörni egy $ \mathbb{Z}_m$ ábc-vel és $ n$ blokkhosszúsággal rendelkező affin lineáris titkosítást ismert nyílt szövegű támadás esetén.

Alice és Bob megegyeznek egy kulcsban és a kódoló függvény a

$\displaystyle E\colon \mathbb{Z}^n_m \to \mathbb{Z}^n_m,\quad \vec{v} \to A\vec{v} + \vec{b} \mod m,
$

ahol $ A \in \mathbb{Z}^{(n,n)}$ és $ \vec{b}\in \mathbb{Z}^n$ . A támadó, Oscar meg akarja határozni az $ (A, \vec{b})$ kulcsot. Oscar felhasználja az $ n + 1$ $ \vec{w}_i$ ( $ 0 \leq i \leq n$ ) nyílt szöveget és azok megfelelő kódolt $ \vec{c}_i = (A\vec{w}_i + \vec{b})$ alakjait. Ekkor

$\displaystyle \vec{c}_i - \vec{c}_0 \equiv A(\vec{w}_i - \vec{w}_0 ) \mod m.
$

Ha a $ W$ az a mátrix, amely

$\displaystyle W = (\vec{w}_1 - \vec{w}_0 ,\ldots, \vec{w}_n - \vec{w}_0) \mod m
$

alakban, $ C$ mátrix pedig

$\displaystyle C = (\vec{c}1 - \vec{c}_0 ,\ldots, \vec{c}_n - \vec{c}_0 ) \mod m
$

alakban áll elő, akkor azt kapjuk, hogy

$\displaystyle AW \equiv C \mod m.
$

Ha $ \det W$ relatív prím az $ m$ -hez, akkor

$\displaystyle A \equiv C\left(w'\right.$   adj$\displaystyle \left. W \right) \mod m,
$

ahol $ w$ a $ \det W$ inverze modulo $ m$ . Továbbá még azt is kapjuk, hogy

$\displaystyle \vec{b} = \vec{c}_0 - A\vec{w}_0 .
$

Így $ n + 1$ nyílt- és titkos szöveg ismeretében a kulcs meghatározható. A titkosítás lineáris, akkor Oscar használja a $ \vec{w}_0 = \vec{c}_0 = \vec{b}_0 = \vec{0}$ beállítást.

Példa:
Megmutatjuk a Hill-féle titkosítás feltörését $ n = 2$ blokkhosszúság esetén. Feltételezzük, hogy a HAND szó kódolt alakja a FUSS. Ekkor a $ \vec{w}_1 = (7, 0)$ kódolt alakja a $ \vec{c}_1 = (5, 20)$ és a $ \vec{w}_2 = (13, 3)$ kódolt alakja a $ \vec{c}_2 = (18, 18)$ . Ekkor a

\begin{displaymath}
W=\left(
\begin{array}{cc}
7 & 13\\
0 & 3\\
\end{array}\right)
\end{displaymath}

és

\begin{displaymath}
C=\left(
\begin{array}{cc}
5 & 18\\
20 & 18\\
\end{array}\right).
\end{displaymath}

Ebben az esetben a $ \det W = 21$ és $ (21, 26) = 1$ . A 21 inverze modulo 26 az 5. Ebből adódik a

$\displaystyle A = 5C\left(\right.$adj$\displaystyle \left. W \right) \mod 26 = 5 \cdot \left(
 \begin{array}{cc}
 5 & 18\\ 
 20 & 18\\ 
 \end{array}\right) \left(
 \begin{array}{cc}
 3 & 13\\ 
 0 & 7\\ 
 \end{array}\right)\mod 26$    
$\displaystyle =\left(
 \begin{array}{cc}
 23 & 19\\ 
 14 & 6\\ 
 \end{array}\right).$    

Ekkor valóban teljesül az $ A \cdot W = C$ .

Feladatok (kódolás)

  1. A VHFUHW titkosított szöveg a Caesar-féle titkosítással készült. Határozzuk meg a kulcsot és a nyílt (eredeti) szöveget!

  2. Mutassuk meg, hogy a következő eljárás egy kriptorendszert ad meg.
    Legyen $ w$ egy sztring a $ \{A, B, \ldots , Z\}$ felett. Válasszunk két Caesar-féle kulcsot, melyek legyenek $ k_1$ és $ k_2$ . Kódoljuk a $ w$ páratlan sorszámú elemeit $ k_1$ -gyel, a párosakat $ k_2$ -vel. Ezután készítsük el a kódolt szöveg fordítottját.

    Határozzuk meg a nyílt-, a rejtett szövegteret és a kulcsteret!

  3. Kódoljuk a 11111111111111 szöveget az ECB, a CBC, a CFB és az OFB módokkal. A permutáció kódolás blokk hossza legyen 3 és

    $\displaystyle k=\begin{pmatrix}
1&2&3\\
2&3&1
\end{pmatrix}.
$

    Az inicializációs vektor a 000. Az OFB és a CFB módoknál legyen $ r=2$ .

  4. Kódoljuk a 10101010101010 szöveget az ECB, a CBC, a CFB és az OFB módokkal. A permutáció kódolás blokk hossza legyen 3 és

    $\displaystyle k=\begin{pmatrix}
1&2&3\\
2&1&3
\end{pmatrix}.
$

    Az inicializációs vektor a 000. Az OFB és a CFB módoknál legyen $ r=2$ .

  5. Legyen $ k=1010101$ , $ c=1110011$ , $ w=1110001\ 1110001\ 1110001$ . Kódoljuk a $ w$ -t felhasználva a korábbi fejezetben leírt folyam kódolót!

  6. Találjuk egy kulcsot azon affin lineáris kódoláshoz, mely az $ \{A, B, \ldots , Z\}$ ábécén a blokk hosszúsága 3 és a ,,RED'' szót ,,ONE''-nak kódolja!

  7. Találjunk egy olyan affin lineáris leképezést, amely $ (\mathbb{Z}/2\mathbb{Z})^3\to(\mathbb{Z}/2\mathbb{Z})^3$ módon képez és az (1,1,1) képe (0,0,0).

  8. Adjunk meg egy olyan kriptorendszert, melynek kódolási függvényei injektívek, de nem szürjektívek!

  9. Határozzuk meg a $ \{0,1\}^n$ ( $ n \in\mathbb{N}$ ) halmazon a bit permutációk számát!

  10. Adjunk meg egy olyan $ \{0,1\}^n$ halmazon permutációt, amely nem bit permutáció!

3. Valószínűség és tökéletes biztonság

3.1. A tökéletes biztonság

A következőket feltételezzük: Alice kódolt üzeneteket küld Bobnak, amit Oscar el tud olvasni. Oscar megpróbál információt kapni az eredeti szövegből a titkosított segítségével. Egy kriptorendszer akkor tökéletes biztonságú, ha Oscar semmit sem tud meg a nyílt szövegből a titkos alapján. Ezt formalizáljuk matematikai értelemben is.

A kriptorendszer véges $ \mathcal{P}$ nyílt-, véges $ \mathcal{C}$ rejtett- és véges $ \mathcal{K}$ kulcstérrel rendelkezik ($ E_k$ és $ D_k$ kódoló és dekódoló függvények, $ k\in \mathcal{K}$ ).

Feltételezzük, hogy egy $ p$ nyílt szöveg valószínűsége $ Pr_{\mathcal{P}}(p)$ . A $ Pr_{\mathcal{P}}$ függvény egy valószínűségeloszlás a nyílt szövegtéren. Ez függ például a(z) (anya)nyelvtől, amit használnak.

Egy új nyílt szöveg esetén Alice választ egy olyan kulcsot, amely független a nyílt szövegtől. Egy $ k$ kulcs valószínűsége $ Pr_{\mathcal{K}}(k)$ . Ez hasonló módon egy valószínűség eloszlás a kulcstéren. annak a valószínűsége, hogy a $ p$ nyílt szöveg fordul elő (jelenik meg) és a $ k$ kulccsal kódoljuk

$\displaystyle Pr(p,k)=Pr_{\mathcal{P}}(p) Pr_{\mathcal{K}}(k).
$

Ez egy valószínűség eloszlást határoz meg a $ \mathcal{P} \times \mathcal{K}$ szorzatteren.

Ha $ p$ egy nyílt szöveg, akkor ugyancsak $ p$ -vel fogjuk jelölni a $ \{(p, k) : k \in \mathcal{K}\}$ eseményt, azaz a $ p$ kódolását.

Hasonlóan, ha $ k$ egy kulcs, akkor ugyancsak $ k$ -vel fogjuk jelölni a $ \{(p, k) : p \in \mathcal{P}\}$ eseményt, azaz a $ k$ -t kiválasztották a kódoláshoz. Nyilvánvalóan kapjuk tehát, hogy

$\displaystyle Pr(p) = Pr_{\mathcal{P}}(p),\quad Pr(k) = P r_{\mathcal{K}}(k).
$

A korábbiak alapján a $ p$ és $ k$ független. Egy rejtjelezett $ c\in \mathcal{C}$ esetén a $ c$ egyúttal a $ \{(p, k) : E_k (p) = c\}$ eseményt is jelenti, azaz a végeredménye a kódolásnak $ c$ .

Oscar ismeri a $ Pr_{\mathcal{P}}$ valószínűségeloszlást a nyílt szövegtéren, például tudja, hogy Alice és Bob milyen (anya)nyelven beszél egymással. Oscar figyel egy $ c$ titkosított szöveget. Ha ez gyakran előfordul a nyílt szövegben, és a többi kevésbé, akkor Oscar kideríthet valamit. Ha minden előfordulás egyforma valószínűséggel működik, akkor Oscar semmit sem tud kideríteni. Ez motiválta Shannon definícióját a tökéletes biztonsággal kapcsolatban.

Definíció:
Egy kriptorendszer tökéletes biztonságú, ha azon események, hogy bizonyos titkosított szövegek előfordulnak és bizonyos nyílt szövegek kódolásra kerülnek függetlenek egymástól. Azaz $ Pr(p|c) = Pr(p)$ teljesül minden $ p$ nyílt és $ c$ rejtjelezett szövegre.

Példa:
Legyen $ \mathcal{P} = \{0, 1\}$ , $ Pr(0) = 1/4$ , $ Pr(1) = 3/4$ . Legyen továbbá a $ \mathcal{K} = \{A, B\}$ , $ Pr(A) = 1/4$ , $ Pr(B) = 3/4$ . Végül $ C = \{a, b\}$ . Ekkor annak a valószínűsége, hogy az 1 nyílt szöveg előfordul és a $ B$ kulccsal kódoljuk: $ Pr(1)Pr(B) = 9/16$ . A kódoló függvény $ E_{\mathcal{K}}$ a következőképpen működik: $ E_A (0) = a$ , $ E_A (1) = b$ , $ E_B (0) = b$ , $ E_B (1) = a$ . Az $ a$ titkos szöveg valószínűsége $ Pr(a) = P r(0, A) + P r(1, B) = 5/8$ .

A $ b$ titkos szöveg valószínűsége $ Pr(b) = P r(1, A) + P r(0, B) = 3/8$ . Most már ki tudjuk számolni a $ Pr(p|c)$ feltételes valószínűséget az összes $ p$ nyílt és $ c$ titkos szöveghez. Ez $ Pr(0|a) = 1/10$ , $ Pr(1|a) = 9/10$ , $ Pr(0|b) = 1/2$ , $ Pr(1|b) = 1/2$ . Ezek az eredmények mutatják, hogy megadott kriptorendszer nem tökéletes biztonságú. Ha Oscar elfogja az a kódolt üzenetet, akkor okkal gondolhatja, hogy az megfelelő nyílt szöveg az 1-es.

Tétel:
Legyen $ \mathcal{C} = \mathcal{K}$ és $ Pr(p) > 0$ tetszőleges $ p$ nyílt szövegre. A kriptorendszer pontosan akkor lesz tökéletes biztonságú, ha a kulcstéren megadott valószínűség eloszlás egyenletes eloszlást követ és ha minden $ p$ nyílt és $ c$ titkos szöveghez pontosan egy olyan $ k$ kulcs van, hogy $ E_k (p) = c$ teljesül.

Megjegyzés:
A tételből következik, hogy az előző példa tökéletes biztonságú lesz, ha beállítjuk a $ Pr(A) = Pr(B) = 1/2$ értékeket.

3.2. Vernam-féle egyszeri kód

Az egyik leghíresebb kriptorendszer a tökéletes biztonságú Vernam-féle egyszeri kód vagy röviden Vernam-féle titkosítás (Vernam one-time pad). Legyen $ n$ egy pozitív egész. A Vernam-féle titkosítás kódolja az $ n$ hosszúságú bitsztringeket. A nyílt, a rejtett szövegtér, a kulcstér megegyezik és $ \mathcal{P} = \mathcal{C} = \mathcal{K} = \{0, 1\}^n$ . A kódoló függvény egy $ k$ kulcsra a

$\displaystyle E_k\colon \{0, 1\}^n \to \{0, 1\}^n,\quad p \to p \oplus k.
$

A kódoláshoz Alice választ véletlenszerűen egy kulcsot egyenletes eloszlás szerint, majd kiszámolja a kódolt üzenetet.

Ez nyilvánvalóan teljesíti a feltételt, azaz tökéletes biztonságú a rendszer.

Ezt a kriptorendszert Gilbert Vernam találta ki 1917-ben. Azonban 1949 után bizonyította Shannon a tökéletes biztonságát.

Sajnos az egyszeri-kód nem nagyon hatékony. A biztonságos kommunikációhoz Alice és Bob véletlenszerűen választja/generálja a megfelelő hosszúságú kulcsot. Mivel minden kulcs csak egyszer használható, így ez sok költséggel jár.

Ha egy kulcsot több üzenethez is felhasználunk, akkor a rendszer már nem lesz tökéletesen biztonságos, ugyanis ismert nyílt szövegű támadással a kulcs könnyen meghatározható. Ha a $ p$ nyílt szöveg és a hozzá tartozó $ c$ kódolt szöveg ismert, akkor $ m \oplus c = m \oplus m \oplus k = k$ .

3.3. Véletlen számok

Ha Alice és Bob a Vernam-féle egyszeri kódot szeretné használni, akkor szükségük van egyenletes eloszlású véletlen bitekre. A gyakorlatban használt bit generátorok szoftver vagy hardware alapúak. Fontos, hogy ha bit generátort használunk, akkor a támadó ezt ne tudja leutánozni. Ezért a biztonságos bit generátorok tipikusan a hardware alapúak.

A következőkben feltételezünk egy véletlen-bit generátort, amely egyenletes eloszlás szerint generálja a véletlen biteket.

Szeretnénk előállítani véletlen számokat a $ \{0,1,\ldots,m\}$ ( $ m\in\mathbb{N}$ ) halmazból. Legyen $ n=\lfloor \log m\rfloor+1$ . Ekkor generálunk $ n$ darab véletlen bitet, melyeket a $ b_1,b_2,\ldots,b_n$ -nel jelölünk. Ha az $ a=\sum^n_{i=1}b_i 2^{n-i}$ szám nagyobb mint $ m$ , akkor ezt elhagyjuk és generálunk egy másikat az előzőek szerint. Egyébként kaptunk egy véletlen $ a$ számot. Nyilvánvalóan az így generált $ a$ számok egyenletes eloszlásúak a $ \{0,1,\ldots,m\}$ halmazon.

Ha egy pontosan $ n$ -bites egyenletes eloszlású véletlen számra van szükség, akkor generáljunk $ n-1$ véletlen bitet ( $ b_2,\ldots,b_n$ ). Legyen $ b_1=1$ és a kimenet $ a=\sum^n_{i=n-1}b_i2^{n-i}$ .

Feladatok (tökéletes biztonság)

  1. Legyen $ S$ egy véges halmaz és a $ Pr$ a valószínűségi eloszlás $ S$ -en. Bizonyítsuk be, hogy
    1. $ Pr(\emptyset)=0$

    2. Az $ A\subset B \subset S$ implikálja, hogy $ Pr(A)\leq Pr(B)$ .

  2. Az $ m$ egyenletes eloszlás szerint került kiválasztásra az $ \{1,2,\ldots,1000\}$ halmazon. Határozzuk meg annak a valószínűségét, hogy négyzetszámot választottunk!

  3. Bizonyítsuk be, hogy a Caesar-féle titkosítás nem tökéletes biztonságú!

  4. Határozzuk meg az $ n$ értékét, melyre annak a valószínűsége, hogy $ n$ ember közül kettőnek ugyanakkor van a szülinapja legalább 9/10!

  5. Tekintsük azt a lineáris blokk kódolót, melynek blokk hossza $ n$ és az ábécé $ \{0,1\}^n$ . Az $ A\in\{0,1\}^{(n,n)}$ mátrixok kulcsterén, ahol det$ (A)\equiv 1 \mod 2$ válasszunk egy egyenletes eloszlást. Ez a kriptorendszer tökéletes biztonságú?

4. DES

4.1. Bevezetés

Az eddig bemutatott rendszerek közül az affin lineárisakról kiderült, hogy könnyen feltörhetőek. A tökéletes biztonságú Vernam-féle titkosítás viszont ineffektív. Ebben a fejezetben a Data Encryption Standard (DES) kriptorendszert mutatjuk be.

Sok-sok éven keresztül ez a kriptorendszer volt érvényben USA-ban és természetesen világszerte használták. A DES már nem bizonságos. 2000 októberében bejelentették az Advanced Encryption Standard (AES) használatát. Ezt Rijndael adat kódoló formulának is nevezik. Azonban ma is vannak DES variánsok, melyek biztonságosak. Azaz a DES nemcsak történetileg, hanem egyéb okokból kifolyólag is érdekes.

4.2. Feistel titkosítás

A DES algoritmust szokás Feistel titkosításnak is hívni. Egy blokk kódolót használunk a $ \{0, 1\}$ ábc-n. Legyen $ t$ a blokk hosszúság. Legyen $ f_K$ a kódoló függvény a $ K$ kulcshoz. A Feistel kódolás ezekből az összetevőkből jön létre mint egy blokk kódoló $ 2t$ hosszúsággal és $ \{0, 1\}$ ábc-vel. Rögzítünk egy $ r \geq 1$ számot a sorozathoz, a $ \mathcal{K}$ kulcs teret és egy módszert, hogy egy tetszőleges $ k\in \mathcal{K}$ kulcshoz generálhassunk egy $ K_1,\ldots,K_r$ kulcssorozatot.

A kódoló $ E_k$ függvény a következőképpen működik. Legyen $ p$ a nyílt szövegtér $ 2t$ hosszúságú. Kettévágjuk két $ t$ hosszúságú részre, azaz $ p = (L_0 , R_0 )$ , ahol $ L_0$ a bal, $ R_0$ a jobb oldali rész. Ekkor a sorozat

$\displaystyle (L_i , R_i ) = (R_{i-1} , L_{i-1} \oplus f_{K_i} (R_{i-1} )),\quad 1\leq i\leq r
$

módon jön létre, és

$\displaystyle E_k (L_0 , R_0 ) = (R_r , L_r ).
$

Nyilvánvaló, hogy a Feistel kódolás biztonsága a külső blokk kódolástól függ. Ez a biztonság növelhető ismételt alkalmazással. A dekódolás a következőképpen megy:

$\displaystyle (R_{i-1} , L_{i-1}) = (L_i , R_i \oplus f_{K_i} (L_i )),\quad 1 \leq i \leq r.
$

Ezt használva $ r$ -szer a $ K_r,\ldots, K_1$ kulcssorozattal visszakapjuk a $ (L_0 , R_0 )$ eredeti szöveget az $ (R_r , L_r )$ -ből.

4.3. DES algoritmus

A DES kriptorendszer egy kicsit módosított Feistel kódolást jelent a $ \{0, 1\}$ ábc-vel és 64 blokkhosszúsággal.

4.3.1. A nyílt és a rejtett szövegtér

A nyílt és a rejtett szövegtér a DES-ben a $ \mathcal{P} = \mathcal{C} = \{0, 1\}^{64}$ . A DES kulcsok 64 hosszúságú bitsztringek a következő tulajdonsággal. Ha a 64 bites DES kulcsot 8 byte-ra vágjuk szét, akkor minden egyes byte-ban a 8 bit összege páratlan. Ez azt jelenti, hogy 7 bit már egyértelműen meghatározza a 8. bitet. Így az 1 bites átviteli hibákat ezzel javíthatjuk. Így a kulcs tér

$\displaystyle \mathcal{K} = \{(b_1 ,\ldots, b_{64} ) \in \{0, 1\}^{64} :\sum_{i=1}^8 b_{8k+i} \equiv 1 \mod 2,\ 0 \leq k \leq 7\}.
$

A DES kulcsok száma $ 2^{56} \approx 7.2 \cdot 10^{16}$ .

Például egy érvényes DES kulcs hexdecimális alakban a következő lehet:

$\displaystyle 133457799BBCDFF1
$

vagy bináris kifejtésben a következő táblázat mutatja:

Táblázat: Egy érvényes DES kulcs.

0 0 0 1 0 0 1 1
0 0 1 1 0 1 0 0
0 1 0 1 0 1 1 1
0 1 1 1 1 0 0 1
1 0 0 1 1 0 1 1
1 0 1 1 1 1 0 0
1 1 0 1 1 1 1 1
1 1 1 1 0 0 0 1

4.3.2. Kezdeti/Inicializáló permutáció

Adott $ p$ nyílt szöveg esetén a DES három lépésből áll. A Feistel kódolás ,,elsőbbségét'' is megtartva a DES egy (IP) inicializációs permutációt hajt végre a $ p$ -n.

Ez egy bitpermutáció 64 bites vektorokhoz, azaz független a választott kulcstól. Az IP és inverze látható a következő ábrán. A táblázatot a következőképpen kell értelmezni: ha $ p \in \{0, 1\}^{64}$ , $ p = p_1 p_2 p_3 \ldots p_{64}$ , akkor IP$ (p) = p_{58} p_{50} p_{42}\ldots p_7$ .

Táblázat: Az inicializációs permutáció, IP és IP$ ^{-1}$ .

IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7

IP$ ^{-1}$
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25

A 16 körös Festel kódolást alkalmazzuk a permutált nyílt szövegre. Végül a titkosított szöveget az IP inverzével kapjuk, azaz

$\displaystyle c =$   IP$\displaystyle ^{-1}(R_{16}, L_{16}).
$

4.3.3. A belső blokk kódolás

Az ábc a $ \{0, 1\}$ , a blokk hosszúság 32 és a kulcstér a $ \{0, 1\}^{48}$ . Ekkor egy $ f_K\colon \{0, 1\}^{32} \to \{0, 1\}^{32}$ kódoló függvényt használunk egy $ K \in \{0, 1\}^{48}$ kulccsal. Az $ R \in \{0, 1\}^{32}$ rész kibővítésre kerül egy E$ \colon \{0, 1\}^{32}\to \{0, 1\}^{48}$ függvénnyel. Ezen függvény megadása látható a következő táblázatban:

Táblázat: Az $ E$ és a $ P$ függvények.

E
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
    
P
16 7 10 21
29 12 28 17
1 15 23 26
5 18 31 20
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25

Ha $ R = R_1 R_2 R_3 \ldots R_{32}$ , akkor E$ (R) = R_{32} R_1 R_2 \ldots R_{32} R_1$ . A következő lépés a E$ (R) \oplus K$ kiszámítása és az eredmény felosztása 8 blokkra, melyeket jelöljünk $ B_i$ -vel ( $ 1 \leq i \leq 8$ ). Ezek 6 hosszúságúak, azaz

   E$\displaystyle (R) \oplus K = B_1 B_2 B_3 B_4 B_5 B_6 B_7 B_8.
$

A következőkben az $ S_i$

$\displaystyle S_i\colon \{0, 1\}^6 \to \{0, 1\}^4,\quad 1\leq i\leq 8
$

függvényeket használjuk (ezeket $ S$ -dobozoknak is nevezik). Ezen függvények használatával kapjuk a

$\displaystyle C = C_1 C_2 C_3 C_4 C_5 C_6 C_7 C_8
$

sztringet, ahol $ C_i = S_i(B_i)$ , $ 1 \leq i \leq 8$ . Ezek 32 hosszúságúak. Erre még alkalmazzuk a P permutációt (lásd az előző táblázatban). Így megkaptuk az $ f_K(R)$ -et.

4.3.4. S-dobozok

Az $ S$ dobozok alkotják a DES algoritmus ,,szívét'', ugyanis (nagyon) nem lineárisak. Minden egyes $ S$ -doboz reprezentálható egy táblázattal, amely 4 sorból és 16 oszlopból áll. Minden egyes $ B_i = b_1 b_2 b_3 b_4 b_5 b_6$ sztring esetén az $ S_i(B_i)$ érték a következőképpen számolható ki:

Az az egész, amelynek bináris alakja $ b_1 b_6$ lesz a sorindex. A $ b_2 b_3 b_4 b_5$ bináris számnak megfelelő egész számot pedig oszlopindexként használjuk. A táblázatban megkeressük az megfelelő értéket, megadjuk a bináris alakját, és ha szükséges hozzárakunk további 0-kat, hogy a hossza 4 legyen. Így megkaptuk az $ S_i(B_i)$ -t.

Az $ S$ -dobozokat adja meg a következő táblázat.

Táblázat: A DES-hez tartozó $ S$ -dobozok.

Sor Oszlop
  [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]
$ S_1$
[0] 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
[1] 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
[2] 4 1 14 8 13 6 2 11 15 12 9 7 3 10 7 0
[3] 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
$ S_2$
[0] 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
[1] 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 15
[2] 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
[3] 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
$ S_3$
[0] 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
[1] 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
[2] 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
[3] 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
$ S_4$
[0] 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
[1] 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
[2] 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
[3] 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
$ S_5$
[0] 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
[1] 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
[2] 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
[3] 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
$ S_6$
[0] 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
[1] 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
[2] 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
[3] 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
$ S_7$
[0] 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
[1] 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
[2] 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
[3] 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
$ S_8$
[0] 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
[1] 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
[2] 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
[3] 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11

Példa:
Például határozzuk meg az $ S_1 (001011)$ -t. Ekkor a sorindexet a 01, az oszlopindexet a 0101 adja meg. Ezek éppen az 1 és 5 egész számokat jelentik. Az első $ S$ -dobozban a megfelelő cellaérték a 2, melynek a bináris alakja az 10, azaz a 4 hosszúság miatt az $ S_1 (001011) = 0010$ .

4.3.5. Kulcsok

Végül a kulcsok generálása maradt hátra. Legyen $ k \in \{0, 1\}^{64}$ egy DES kulcs. Ebből generáljuk a $ K_i$ , $ 1 \leq i \leq 16$ kulcssorozatot, melyek 48 hosszúak.

Definiáljuk a $ \nu_i$ , $ 1 \leq i \leq 16$ értékeket a következőképpen:

$\displaystyle \nu_i=\begin{cases}1,& \mbox{minden } i \in \{1, 2, 9, 16\}\mbox{-ra,}\\
2,& \mbox{egyébként.}
\end{cases}
$

A következő algoritmussal ill. függvényekkel kapjuk a kulcsokat:

PC1$\displaystyle \colon \{0, 1\}^{64}\to \{0, 1\}^{28} \times \{0, 1\}^{28},$    
PC2$\displaystyle \colon \{0, 1\}^{28}\times \{0, 1\}^{28}\to \{0, 1\}^{48},$    

ahol a fenti függvényeket az alábbiak szerint adjuk meg.

Táblázat: A PC1 és a PC2 függvények.

PC1
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
    
PC2
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32

Az algoritmus:

  1. Legyen $ (C_0 , D_0 ) =$   PC1$ (k)$ .
  2. Minden $ 1 \leq i \leq 16$ -ra tegyük a kövekezőket:
    1. Legyen $ C_i$ az a sztring, melyet a $ C_{i-1}$ -ből ciklikus, $ \nu_i$ pozícióval történő balra eltolással kapunk.
    2. Legyen $ D_i$ az a sztring, melyet a $ D_{i-1}$ -ből ciklikus, $ \nu_i$ pozícióval történő balra eltolással kapunk.
    3. Határozzuk meg a $ K_i =$   PC2$ (C_i , D_i)$ -t.
A PC1 függvény $ C$ és $ D$ , két 28 hosszúságú sztringet ad vissza a 64 hosszúságú kulcsból. Ez a táblázatból jól látható. Például, ha $ k = k_1 k_2 k_3 \ldots k_{64}$ , akkor $ C = k_{57} k_{49}\ldots k_{36}$ . A PC2 függvény egy $ (C, D)$ párból ad vissza egy 48 hosszúságú sztringet. Például PC2$ (b_1 b_2\ldots b_{56}) = b_{14} b_{17}\ldots b_{32}$ .

A DES alapján történő kódolással kapott titkos szöveget a fordított sorrendben alkalmazott kulcssorozat kódolással kapjuk vissza.

4.4. Egy DES példa

Készítsük el a $ p = 0123456789ABCDEF$ nyílt szöveg kódolását a DES segítségével. Ennek bináris alakja az

0 0 0 0 0 0 0 1
0 0 1 0 0 0 1 1
0 1 0 0 0 1 0 1
0 1 1 0 0 1 1 1
1 0 0 0 1 0 0 1
1 0 1 0 1 0 1 1
1 1 0 0 1 1 0 1
1 1 1 0 1 1 1 1

Alkalmazzuk a korábban már látott IP permutációt, ekkor kapjuk

1 1 0 0 1 1 0 0
0 0 0 0 0 0 0 0
1 1 0 0 1 1 0 0
1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 0
1 0 1 0 1 0 1 0
1 1 1 1 0 0 0 0
1 0 1 0 1 0 1 0
azaz

$\displaystyle L_0 = 11001100000000001100110011111111,$    
$\displaystyle R_0 = 11110000101010101111000010101010.$    

Használjuk a korábbi példában megismert DES kulcsot, azaz az 133457799BBCDFF1-et, melynek a bináris alakja

0 0 0 1 0 0 1 1
0 0 1 1 0 1 0 0
0 1 0 1 0 1 1 1
0 1 1 1 1 0 0 1
1 0 0 1 1 0 1 1
1 0 1 1 1 1 0 0
1 1 0 1 1 1 1 1
1 1 1 1 0 0 0 1
Számoljuk ki az első kulcsot:

$\displaystyle C_0 = 1111000011001100101010101111,$    
$\displaystyle D_0 = 0101010101100110011110001111,$    
$\displaystyle C_1 = 1110000110011001010101011111,$    
$\displaystyle D_1 = 1010101011001100111100011110.$    

Ebből kapjuk a

$\displaystyle K_1 = 000110110000001011101111111111000111000001110010
$

kulcsot. Ezt felhasználva kapjuk a

   E$\displaystyle (R_0) \oplus K_1 = 011000010001011110111010100001100110010100100111,
$

és

$\displaystyle f_{K_1}(R_0 ) = 00000011010010111010100110111011,
$

végül

$\displaystyle R_1 = 11001111010010110110010101000100.
$

A többi forduló hasonlóan számolható ki.

4.5. A DES biztonsága

A feltalálása óta a DES biztonságát intenzíven vizsgálták. Speciális technikákat, úgy mint differenciált és lineáris kriptoanalízisbeli megoldásokkal támadták a DES-t. De a legsikeresebb támadás a kulcstéren történő kimerítő keresés volt. Speciális hardware vagy munkaállomások nagy hálózatával feltörhető a DES kódolás néhány napon vagy órán belül.

A DES-t ma már csak akkor tekinthetjük biztonságosnak, ha háromszoros kódolást hajtanak végre. Ebben a vonatkozásban fontos tudni, hogy a DES nem csoport. Ez azt jelenti, hogy ha rendelkezünk egy $ k_1$ és egy $ k_2$ kulccsal, akkor nincs olyan harmadik $ k_3$ kulcs, hogy

   DES$\displaystyle _{k_1} \circ$   DES$\displaystyle _{k_2} =$   DES$\displaystyle _{k_3}.
$

Nyilvánvalóan fordított esetben a többszörös titkosítás nem növelné a biztonságot.

Feladatok (DES)

  1. Mutassuk meg, hogy a $ C_{16}$ és a $ D_{16}$ megkapható a $ C_1$ -ből és a $ D_1$ -ből csupán ciklikus egy pozícióval való jobbra tolással!

  2. Tegyük fel, hogy $ K_1=K_2=\cdots =K_{16}$ . Mutassuk meg, hogy a $ C_1$ összes bitje megegyezik a $ D_1$ összes bitjével!

  3. A következő függvények közül melyik lesz lineáris egy rögzített kulcsra?
    IP, $ E(R)\oplus K$ , $ S_i$ $ 1 \leq i \leq 8$ , P, PC1 és PC2.
    Bizonyítsa a linearitást vagy adjon egy számolási példát!

  4. Számolja ki a korábbi fejezetben ismertetett példa második körét!

  5. Számolja ki a korábbi fejezetben ismertetett példa harmadik körét!

5. AES

Jelmondat is lehetne: ,,Az új király: RIJNDAEL''.

Az AES pályázat győztese 2000-ben a RIJNDAEL lett. Az algoritmus keresztszülői a tervezők voltak, Vincent Rijman, egyetemi kutató és Joan Daemen, számítógépes szakértő.
A RIJNDAEL struktúrája a titkosító és a megoldó oldalon hasonló, a műveletek jól párhuzamosíthatók. A mai nagyteljesítményű RISC és CISC processzorokon éppúgy alkamazható, mint egy 8bites chip-kártyán.
Jelenlegi ismereteink szerint ellenáll a jelenleg ismert összes támadási módnak, így pillanatnyilag nincs jobb gyakorlati módszer a feltörésére, mint a kimerítő keresés a kulcstéren (brute force-attack).

5.1. Alapok

A RIJNDAEL nem a Feistel-struktúrát használja, hanem a kör eredményének kialakításában az összes bemeneti adatbit részt vesz - nem csak a fele. A körfüggvényeket négy, egymástól független transzformációból építi fel. Ezeket a RIJNDAEL terminológiában rétegeknek nevezzük (layers).

a)
Lineáris keverőréteg MixColumns (oszlopszinten párhuzamosítható), ShiftRows (sorszinten párhuzamosítható)
b)
Nem lineáris réteg SubBytes (bájtszinten párhuzamosítható)
c)
Kulcsfüggő réteg AddRoundKey (bájtszinten párhuzamosítható)

Az utolsó kör némi eltérést mutat a többihez képest, mert a keverőrétege kismértékben eltér.

5.2. Az algoritmus specifikációja

5.2.1. Paraméterek: Körök száma, adatblokk- és kulcsméret

A RIJNDAEL algoritmus blokkmérete és kulcsmérete egymástól függetlenül paraméterezhető: 128-256 bitig terjedhet mindkettő, 32 bites lépésekben.

5.2.2. A State változó

Az egyes körök (ezen belül az egyes rétegek) ki- és bemeneti adatait egy State nevű struktúrában tároljuk. Ábrázolására a specifikáció egy négyzethálót ajánl, amelynek mindig négy sora van, oszlopainak száma a blokkmérettől függ: $ N_B$ . Egy-egy cella egy-egy bájtot jelent. A kulcs ábrázolása hasonló, a sorok száma szintén 4, az oszlopok száma pedig $ N_K$ .

Image tablazat1

A state-struktúra feltöltésekor mind a kulcs, mind a titkosítandó adat esetén fentről lefelé és balról jobbra kell haladni.

5.2.3. A körfüggvények rétegei: SubBytes, ShiftRows, MixColumns, AddRoundKey

A RIJNDAEL az iteratív kódolók családjába tartozik, ami a közbülső részeredmények többszöri újrafeldolgozását jelenti. A RIJNDAEL 10-12-14-szer ismételi körfüggvényét, a kulcs és blokkméret függvényében:

$ N_R$ $ {\bf N_B=4}$ $ N_B=6$ $ N_B=8$
$ N_K=4$ $ {\bf 10}_{(AES-128)}$ 12 14
$ N_K=6$ $ {\bf 12}_{(AES-192)}$ 12 14
$ N_K=8$ $ {\bf 14}_{(AES-256)}$ 14 14

A RIJNDAEL körfüggvénye (round transformation) a már korábban is említett négy rétegből áll.

Minden körfüggvény egyforma, kivéve az utolsót, amely egy kicsit eltér a többitől, mert kimaradt a MixColumns lépés:

Round(State, RoundKey)
begin
SubBytes(State)
ShiftRows(State)
MixColumns(State)
AddRoundKey(State, RoundKey);
end;
FinalRound(State, RoundKey)
begin
SubBytes(State)
ShiftRows(State)
 
AddRoundKey(State, RoundKey);
end;

5.2.3.1. A SubBytes transzformáció-bájtszintű művelet

A SubBytes transzformáció nem lineáris, invertálható S-dobozt alkalmaz, pontosan egyet: minden egyes bájt helyettesítése ugyanazzal az S-dobozzal történik.

Image tablazat2

Ez az S-box - működési szempontjából - egyenértékű az ősi Caesar-titkosítással, az egykori +3 helyett a következő összefüggés határozza meg az S-doboz kimeneti bitjeit:

$\displaystyle o_i=b_i\ \oplus\ b_{(i+4)\mbox{ mod 8}}\ \oplus\ b_{(i+5)\mbox{ mod 8}}\oplus b_{(i+6)\mbox{ mod 8}}\ \oplus\ b_{(i+7)\mbox{ mod 8}}\ \oplus\ c_i$    
$\displaystyle c=01100011,\ {\mbox és}\ 0\leq i \leq 7$    

A bonyolultnak tűnő definíció ellenére az S-dobozoknál megszokott szótárszerű működést kapjuk: ha például az $ A_{00}$ értéke $ 74$ , az S-doboz eredménye $ 92$ , és ez csak a bemeneti értéktől függ.

5.2.3.2. Az InvSubBytes transzformáció - bájtszintű művelet

Az InvSubBytes transzformáció szintén egy S-dobozt használ, a SubBytes S-dobozának inverzét.

Az előbbi számpéldát alapul véve, ha az $ A_{00}$ értéke $ 92$ , az inverz S-doboz eredménye $ 74$ . (Szintén Caesar tiszteletének jeleként...)

5.2.3.3. A ShiftRows transzformáció - sorszintű művelet

Ez az egyik legegyszerűbb rétegfüggvény, a state-struktúra sorait tolja el ciklikusan különböző mértékben. Az első sort nem tolja el, a többi ciklikus eltolásának mértéke pedig az adatblokk méretétől függ, és előre definiált.

A függvényt a következőképpen adhatjuk meg:

$\displaystyle s'_{r,c}=s_{r,(c+shift(r,N_B))\mbox{ mod } N_B}, \mbox{ ahol } 0<r<4 \mbox{ és } 0\leq c< N_B,
$

továbbá

$\displaystyle shift(1,4)=1;\quad shift(2,4)=2;\quad shift(3,4)=3;
$

A specifikáció idevonatkozó értékei a következők:

$ N_B$ $ c_1$ $ c_2$ $ c_3$
(AES) 4 1 2 3
6 1 2 3
8 1 3 4

Image tablazat3

5.2.3.4. A InvShiftRows transzformáció - sorszintű művelet

A specifikáció szerint a ShiftRows inverz művelete ugyanez a balra forgatás, de a forgatások lépésszámai a blokkméret függvényében rendre: $ 0,\ N_B-c_1,\ N_B-c_2,\ N_B-c_3$ pozíció.

5.2.3.5. A MixColumns transzformáció - oszlopszintű művelet

A MixColumns a legbonyolultabb rétegfüggvény és -áttekintve a szabványon - szinte csak ennek a kedvéért érdemes megismerkedni egy új fogalommal, a polinommal és a rajta értelmezett speciális $ \bullet$ gombóc - szorzás művelettel.

A MixColumns a state-struktúra oszlopait alakítja át. Az oszlop minden egyes bájtját, mint polinomot megszorozza egy-egy másik, előre definiált polinommal, majd ezek összege adja az új oszlop egy-egy bájtját. Az új bájt kialakításában az oszlop minden bájtja részt vesz, így ha az oszlop 32 bitjének egyike megváltozik, megváltozik az egész oszlop: vagyis ez a művelet nagyfokú függőséget teremt az egyes bájtok között.

Image tablazat4

5.3. A polinomok

A RIJNDAEL algoritmus lényegében bájtorientált, mert az elemi lépéseket bájtokon hajtja végre. Ezek egy része ugyan (alternatív algoritmus kialakításával) optimalizálható például 32-bites processzorokra, de ettől még az alapelv nem változik. Az algoritmus legfurcsább művelete a MixColumns és párja az InvMixColumns.

5.3.1. Műveletek a polinomokkal

Összeadás Két polinom összege a megfelelő helyiértéken lévő együtthatók$ \pmod 2$ összege, vagyis XOR kapcsolata.

Mennyi $ c(x)=a(x)+b(x)$ , ha

$\displaystyle a(x)$ $\displaystyle =x^7+x^6+x^2+x^1$    
$\displaystyle b(x)$ $\displaystyle =x^6+x^5+x^4+x^3+x^2+x^1+x^0\ \ \ ?$    
$\displaystyle c(x)$ $\displaystyle =x^7+x^5+x^4+x^3+x^0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ C_i=A_i\ \oplus\ B_i$    

És mindez a hexadecimális jelöléssel:

$\displaystyle a(x)$ $\displaystyle ={11000110}={C6}$    
$\displaystyle b(x)$ $\displaystyle ={01111111}={7F}$    
$\displaystyle c(x)$ $\displaystyle ={10111001}={B9}\ \ \ \ \ \ \ \ \ \ C_i=A_i\ \oplus\ B_i$    

Mivel a bitszintű műveleteket bájtonként is elvégezhetjük, egyszerűen számolhatunk így is:

$\displaystyle C=A\ \oplus\ B=C6\ \oplus\ 7F=B9$    

Szorzás A polinomok szorzása egy kicsit a modulo aritmetikához hasonlítható. Első lépésként vegyünk egy speciális polinomot: $ m(x)=\{01\}\{1B\}$ , vagyis $ m(x)=x^8+x^4+x^3+x^1+x^0$ . E polinomnak saját magán és 1-en kívül nincs más osztója. Olyan, mintha prímszám lenne. Sok ilyen polinom van, de a RIJNDAEL pont ezt használja. A RIJNDAEL-ben használt szorzás művelete (melynek jelölése a továbbiakban $ \bullet$ ) a polinomok szorzatának fenti $ m(x)$ -szel történő osztási maradékát adja eredményül:
$ c(x)=a(x)\bullet b(x) \mod m(x)$ .

Szorzás egy bizonyos polinommal - xtime() Ha az alábbi általános polinomot megszorozzuk az $ x^1=\{02\}$ polinommal, az eredmény:

$\displaystyle \left(B_7x^7\right.$ $\displaystyle \left.+B_6x^6+B_5x^5+B_4x^4+B_3x^3+B_2x^2+B_1x^1+B_0x^0\right)\bullet x^1=$    
$\displaystyle B_7x^8$ $\displaystyle +B_6x^7+B_5x^6+B_4x^5+B_3x^4+B_2x^3+B_1x^2+B_0x^1$    

Ne feledkezzünk meg arról, hogy a $ \bullet$ művelet előírja az $ m(x)$ modulusképzést is!
A fenti eredményből láthatjuk még, hogy minden együttható egy hellyel balra vándorolt. Vagyis hogyan is kell egy tetszőleges $ b(x)$ polinomot egy ilyen $ \{02\}$ polinommal megszorozni? Egyszerűen a $ b(x)$ ,,ábrázolását'' egy hellyel balra toljuk és ha a bájtból kilépő bit ,,1'', az eltolást még egy $ \oplus \{01\}\{1B\}$ is követi. Ezt a műveletet a RIJNDAEL specifikációja xtime()-nak hívja, megvalósítható függvényként is, de akár előre ki is számolható egy táblázatba az összes xtime(0-255) érték.

A InvMixColumns transzformáció - oszlopszintű művelet

A polinomok terén tett kis kitérők után térjünk vissza az AES rétegeire. Legutóbb MixColumns-ot láttuk, és ennek inverze az InvMixColumns. A két réteg között csak az előre definiált szorzó polinomok jelentik a különbséget, az elvégzendő művelet mindkét esetben azonos:

$\displaystyle B_{0c}$ $\displaystyle = ({0e}\bullet A_{0c})\oplus ({0b}\bullet A_{1c})\oplus ({0d}\bullet A_{2c})\oplus ({09}\bullet A_{3c})$    
$\displaystyle B_{1c}$ $\displaystyle = ({09}\bullet A_{0c})\oplus ({0e}\bullet A_{1c})\oplus ({0b}\bullet A_{2c})\oplus ({0d}\bullet A_{3c})$    
$\displaystyle B_{2c}$ $\displaystyle = ({0d}\bullet A_{0c})\oplus ({09}\bullet A_{1c})\oplus ({0e}\bullet A_{2c})\oplus ({0b}\bullet A_{3c})$    
$\displaystyle B_{3c}$ $\displaystyle = ({0b}\bullet A_{0c})\oplus ({0d}\bullet A_{1c})\oplus ({09}\bullet A_{2c})\oplus ({0e}\bullet A_{3c})$    

Az AddRoundKey transzformáció - bájtszintű transzformáció Ez a legegyszerűbb művelet. Feladata, hogy mindazt, ami eddig történt a state-struktúrában, kulcsfüggővé tegye.

A bemeneti state-struktúra bájtjait egyszerűen összeadja (XOR-olja) a körkulcsot tartalmazó state-struktúra bájtjaival.

$ B_{00}=A_{00}\oplus R_{00}$ , $ B_{01}=A_{01}\oplus R_{01}$ , stb.

$ A_{00}$ $ A_{01}$ $ A_{02}$ $ A_{03}$
$ A_{10}$ $ A_{11}$ $ A_{12}$ $ \cdots$
$ \cdots$ $ \cdots$ $ \cdots$ $ \cdots$
$ \cdots$ $ \cdots$ $ \cdots$ $ \cdots$
$ \oplus$
$ R_{00}$ $ R_{01}$ $ R_{02}$ $ R_{03}$
$ R_{10}$ $ R_{11}$ $ R_{12}$ $ \cdots$
$ \cdots$ $ \cdots$ $ \cdots$ $ \cdots$
$ \cdots$ $ \cdots$ $ \cdots$ $ \cdots$
$ =$
$ B_{00}$ $ B_{01}$ $ B_{02}$ $ B_{03}$
$ B_{10}$ $ B_{11}$ $ B_{12}$ $ \cdots$
$ \cdots$ $ \cdots$ $ \cdots$ $ \cdots$
$ \cdots$ $ \cdots$ $ \cdots$ $ \cdots$

5.3.2. Kulcsszervezés

A körkulcsok előállítása, a kiterjesztett kulcs születése A titkos kulcsból egy igen hosszú, úgynevezett kiterjesztett kulcsot készít az algoritmus. Ennek feldarabolása szolgáltatja majd a körkulcsokat. Mekkora ez a kiterjesztett kulcs?

Az egyes körökben felhasznált körkulcsokat ebből a kiterjesztett kulcsból származtatja a RIJNDAEL: az első $ N_B$ szót a 0. körhöz, a második $ N_B$ szót az 1. körhöz használja fel és így tovább. A kiterjesztett kulcs jelölése a továbbiakban $ EXP[i]$ .

A kiterjesztett kulcs elejére a titkos kulcs másolatát helyezi, majd minden további szó rekurzív módon a korábbi szavakból származtatható. Bár a kiterjesztett kulcsot mindig a titkos kulcsból származtatjuk, a szabvány nem ajánlja (sőt, majdnem tiltja), hogy azt közvetlenül specifikáljuk - valószínűleg ezért, mert nem csak a kulcstól, hanem a körök számától és a blokkmérettől is függ.
A kiterjesztett kulcs előállítására két - hasonló - algoritmus van attól függően, hogy mekkora a titkos kulcs hossza.

Körkulcs kiválasztása - szóalapú kiterjesztett kulcsból

A körkucs (round key, RK) kiválasztása a kiterjesztett kulcsból a blokkmérettől függően történik. Minden egyek körkulcs $ N_B$ darab szóból áll, vagyis a state-struktúrával egyező méretű darabokra kell vágni a kiterjesztett kulcsot:

a)
Az első körkulcs az első $ N_B$ darab szó,

b)
a második körkulcs a második $ N_B$ darab szó és így tovább.

Egy körkulcsban az első szó az első state-oszlophoz, a második szó a második state-oszlophoz tartozik, és így tovább. Az alábbi ábra ezt a kiválasztást és a körkulcsként való felhasználást mutatja $ N_B=4$ (128 bites adatblokk) esetén:

Exp0 Exp1 Exp2 Exp3 Exp4 Exp5 Exp6 Exp7 $ \cdots$ $ \cdots$
Round Key 0 Round Key 1 $ \cdots$

$ A_{00}$ $ A_{01}$ $ A_{02}$ $ A_{03}$
$ A_{10}$ $ A_{11}$ $ A_{12}$ $ A_{13}$
$ A_{20}$ $ A_{21}$ $ A_{22}$ $ A_{23}$
$ A_{30}$ $ A_{31}$ $ A_{32}$ $ A_{33}$
$ \oplus$
Exp0 Exp1 Exp2 Exp3
$ =$
$ B_{00}$ $ B_{01}$ $ B_{02}$ $ B_{03}$
$ B_{10}$ $ B_{11}$ $ B_{12}$ $ B_{13}$
$ B_{20}$ $ B_{21}$ $ B_{22}$ $ B_{23}$
$ B_{30}$ $ B_{31}$ $ B_{32}$ $ B_{33}$

Körkulcs kiválasztása - bájtalapú kiterjesztett kulcsból

A bájtokból felépülő kiterjesztett kulcsból - 32-bites szavak felhasználása nélkül - megfelelő indexelést használva vehetjük ki a bájtokat:

   Round Key 0 Round Key 1 $ \cdots$
 Exp 0 1 2 3 4 $ \cdots$ 15 16 17 18 19 20 $ \cdots$ 31 $ \cdots$

$ A_{00}$ $ A_{01}$ $ A_{02}$ $ A_{03}$
$ A_{10}$ $ A_{11}$ $ A_{12}$ $ A_{13}$
$ A_{20}$ $ A_{21}$ $ A_{22}$ $ A_{23}$
$ A_{30}$ $ A_{31}$ $ A_{32}$ $ A_{33}$
$ \oplus$
$ R_{00}$ $ R_{01}$ $ R_{02}$ $ R_{03}$
$ R_{10}$ $ R_{11}$ $ R_{12}$ $ R_{13}$
$ R_{20}$ $ R_{21}$ $ R_{22}$ $ R_{23}$
$ R_{30}$ $ R_{31}$ $ R_{32}$ $ R_{33}$
$ =$
$ B_{00}$ $ B_{01}$ $ B_{02}$ $ B_{03}$
$ B_{10}$ $ B_{11}$ $ B_{12}$ $ B_{13}$
$ B_{20}$ $ B_{21}$ $ B_{22}$ $ B_{23}$
$ B_{30}$ $ B_{31}$ $ B_{32}$ $ B_{33}$

Ezzel végére értünk AES alapműveleti ismertetésének, nekiláthatunk a titkosító és a megfejtő algoritmus felépítésének.

5.4. A titkosítás

A megismert elemekből most már felépíthetjük magát a RIJNDAEL titkosító algoritmust. Alkalmazzuk az egyes lépéseket a következők szerint:

1)
Ha új kulcsot állít be a felhasználó, rögtön készítünk egy kiterjesztett kulcsot.
2)
A RIJNDAEL kezdő lépése: AddRoundKey
3)
$ N_R-1$ körben a Round függvény alkalmazása
4)
majd a FinalRound függvény alkalmazása.

Az inverz művelet

A megoldóalgoritmus az eredeti lépések inverzeit használja, az egyes lépéseket fordított sorrendben alkalmazza, a körkulcsok fordított sorrendben kerülnek felhasználásra.

A két algoritmus ezért nem egyforma, sőt a körfüggvény egyes lépései is különbözőek, mert azok - az AddRoundKey kivételével - nem saját maguk inverzei.

Ennyi a RIJNDAEL. Ha valaki további irodalmat böngész, vegye figyelembe, azt az apró eltérést, hogy a korai cikkekben másként hívják a rétegfüggvényeket:

RIJNDAEL eredeti elnevezései FIPS197, végleges elnevezések
ByteSup SubBytes
ShiftRow ShiftRows
MixColumn MixColumns
AddRoundKey AddRoundKey

Feladatok (AES)

  1. Gyakorlásképpen végezzük el egy rövid szöveg kódolását az AES-sel egy egyszerű kulcs segítségével! Legyen ez a szöveg: ,,Helló világ!''.

  2. Határozzuk meg, hogy a 2A és 75 hexadecimális számokhoz milyen polinomok tartoznak a fejezetben ismertetett reprezentációban!

  3. Legyenek $ a(x)=x^3+x^2+1$ és $ b(x)=x^5+x^3+1$ adott polinomok. Határozzuk meg az $ a(x)+b(x)$ és a $ a(x)\bullet b(x)$ ( mod$ m(x)$ ) értékeket!

  4. Határozzuk az xtime(47) művelet értékét!

  5. Legyenek $ s_{0,1}=01101111$ , $ s_{1,1}=01101001$ , $ s_{2,1}=01001100$ és $ s_{3,1}=10001001$ adott feltöltései egy oszlopnak. Határozzuk meg a MixColumns művelet eredményét.

6. Prímszám generálás

Sok nyilvános kulcsú rendszerben nagy (random) prímeket használnak. Ezeket egyszerűen adott méretben véletlenszerűen generált számok közül választják ki. Ebben a fejezetben azzal foglalkozunk, hogy miképpen lehet hatékonyan eldönteni egy pozitív számról annak prímségét.

6.1. Triviális osztás

Az első egyszerű prímtesztelő eljárás az un. triviális osztás. Ez lényegében az Eratoszthenészi szitát használja, azaz megnézi, hogy $ \sqrt n$ -ig van-e prímosztója az $ n$ pozitív egésznek. Ha nincs, akkor prím, ellenkező esetben összetett szám.

Nyilvánvalóan ez a módszer felhasználható az $ n$ prímfaktorizációjára is, hiszen ha egy $ p$ prím osztja az $ n$ -et, akkor megismételjük a triviális osztást az $ n/p$ -re.

Mindaddig folytatjuk ezt, amíg prímet nem kapunk.

Ha $ n$ nagy, akkor ez a módszer nem hatékony (ineffektív). Faktorizáció esetén a triviális osztást tipikusan a $ 10^6$ -nál kisebb prímosztókra alkalmazzuk.

A triviális osztás futási idejének becsléséhez szükségünk van a prímek számának becslésére, mely prímek egy adott korlát alatt vannak. Jól ismert a $ \pi(x)$ számelméleti függvény, amely az $ x$ pozitív valós számnál nem nagyobb prímek számát adja meg. Például: $ \pi(1)=0$ , $ \pi(4)=2$ , $ \pi(124)=30$ . Ide kapcsolódik a következő fontos tétel:

Tétel:
1. Ha $ x\geq 17$ , akkor $ \pi(x)> x/\log x$ .
2. Ha $ x>1$ , akkor $ \pi(x)< 1.25506\cdot (x/\log x)$

Az előző tételből következik, hogy legalább $ \lceil \sqrt n/\log \sqrt n\,\rceil$ osztás szükséges ahhoz, hogy az $ n$ számról bizonyítsuk annak prím tulajdonságát a triviális osztással. Például az RSA (lásd a következő fejezetet) kriptorendszerhez $ 10^{75}$ -nél nagyobb prímek kellenek.

Az ehhez szükséges osztások száma triviális osztása esetén legalább $ 10^{75/2}/\log 10^{75/2}>3.6\cdot 10^{36}$ . Ezt lehetetlen kivárni.

A továbbiakban olyan hatékony módszereket nézünk meg, amelyek nagy valószínűséggel bizonyítják egy pozitív egészről annak prím tulajdonságát. Ezeket együttesen prím teszteknek nevezzük. Az első ilyen a Fermat teszt.

6.2. Fermat teszt

Ez a teszt nyilvánvalóan az Fermat tételen alapszik.

Tétel:
Ha $ n$ prímszám, akkor $ a^{n-1}\equiv 1 \mod m$ teljesül minden $ a\in\mathbb{Z}$ , ahol lnko$ (a,n)=1$ .

Ez a tétel felhasználható annak eldöntésére, hogy egy pozitív egész összetett. Válasszunk egy pozitív egész $ a$ számot az $ \{1,2,\ldots,n-1\}$ halmazból. Könnyen meghatározhatjuk az $ y\equiv a^{n-1}\mod n$ értéket. Ha $ y\neq 1$ , akkor $ n$ összetett. Ha $ y=1$ , akkor nem tudjuk, hogy $ n$ prím vagy összetett, amit a következő példa is mutat.

Példa:
Tekintsük az $ n=341=11\cdot 31$ számot. Ekkor

$\displaystyle 2^{340}\equiv 1\mod 341,
$

bár $ n$ összetett. Így ha véletlenül az $ n=341$ és $ a=2$ esetet kapjuk, akkor $ y=1$ , azaz nem bizonyítottunk semmit sem.

Másrészt viszont a

$\displaystyle 3^{340}\equiv 56 \mod 341.
$

Így az $ n=341$ és $ a = 3$ választás mellett bizonyítottuk, hogy $ n$ összetett.

Ha a Fermat teszt bizonyítja, hogy egy $ n$ összetett, akkor nem ad meg prímosztót. Így nem használható faktorizációra.

6.3. Carmichael számok

A Fermat teszt bizonyíthatja egy pozitív egész szám összetettségét, de a prímségét NEM. Ha a Fermat teszt nem képes találni egy megfelelő $ a$ számot az $ n$ összetettségére, akkor nagy valószínűséggel prím. Sajnos vannak olyan számok, melyek összetettek és átmennek a Fermat teszten tetszőleges $ a$ alap esetén. Ezeket Carmichael számoknak hívjuk.

Szükségünk van két definícióra.

Definíció:
Ha $ n$ egy páratlan összetett szám és ha $ a$ egy egész, melyre az

$\displaystyle a^{n-1}\equiv 1\mod n
$

teljesül, akkor $ n$ -et pszeudoprímnek nevezzük az $ a$ bázisra nézve.

Definíció:
Ha $ n$ pszeudoprím minden olyan $ a$ bázisra, melynél lnko$ (a,n)=1$ , akkor az $ n$ -et Carmichael számnak nevezzük.

A legkisebb Carmichael szám az $ 561=3\cdot 11\cdot 17$ . Megmutatható, hogy végtelen sok Carmichael szám van. A Carmichael számok létezése miatt a Fermat teszt nem optimális a gyakorlatban. A jobb választás a Miller-Rabin teszt (lásd a következő alfejezetben). A Miller-Rabin teszt analíziséhez szükségünk van a Carmichael számok karakterizációjára.

Tétel:
Egy páratlan $ n\geq 3$ összetett szám Carmichael szám pontosan akkor, ha négyzetmentes (azaz nincs többszörös prímosztója) és az $ n$ minden $ p$ prímosztója esetén a $ p-1$ egész osztja az $ n-1$ -et.

6.4. Miller-Rabin teszt

A Miller-Rabin teszt a Fermat teszttel ellentétben bármely összetett számról bizonyítani tudja annak összetettségét. Más szavakkal: nincs a Miller-Rabin tesztben a Carmichael-számoknak megfelelő analóg változat.

A Miller-Rabin teszt a Kis Fermat tétel egy módosítása. Legyen $ n$ egy páratlan, pozitív egész és legyen

$\displaystyle s=\max\bigm\{r\in\mathbb{N}:2^r$ osztja az $\displaystyle n-1$-et$\displaystyle \bigm\},
$

így $ 2^s$ a legnagyobb kettő hatvány, amely osztja az $ n-1$ -et. Legyen

$\displaystyle d=(n-1)/2^s.
$

Ekkor $ d$ páratlan.

Tétel:
Ha $ n$ prím és $ a$ egy az $ n$ -hez relatív prím egész szám, akkor az előző jelölések felhasználásával

$\displaystyle a^d\equiv 1\mod n
$

vagy létezik egy $ r$ egész a $ \{0,1,\ldots,s-1\}$ halmazból, hogy

$\displaystyle a^{2^rd}\equiv -1\mod n.
$

Ha $ n$ prím, akkor legalább az egyik tételbeli feltétel teljesül. Ezért, ha találunk egy olyan $ a$ számot, mely relatív prím az $ n$ -hez és egyik tételbeli kongruencia sem teljesül ( $ r\in\{0,1,\ldots,s-1\}$ -re), akkor $ n$ összetett. Egy ilyen $ a$ számot az $ n$ összetettségére vonatkozó tanúnak hívunk.

Példa:
Legyen $ n=561$ . Mivel az $ n$ Carmichael szám, a Fermat teszt nem tudja bizonyítani annak összetettségét. De az $ a=2$ egy tanú az $ n$ összetettségére. Ugyanis ekkor $ s=4$ , $ d=35$ és $ 2^{35}\equiv 163 \mod 561$ , $ 2^{2\cdot 35}\equiv 166\mod 561$ , $ 2^{2^2\cdot 35}\equiv 67\mod 561$ , $ 2^{2^3\cdot 35}\equiv 1\mod 561$ . Ezért a tétel alapján az 561 összetett.

A Miller-Rabin teszt hatékonyságára vonatkozólag elmondhatjuk, hogy elég sok tanú adódik egy összetett szám összetettségére. A következő tétel ezt formalizálja:

Tétel:
Ha $ n\geq 3$ egy páratlan, összetett szám, akkor az $ \{1,\ldots,n-1\}$ halmaz legfeljebb $ (n-1)/4$ olyan számot tartalmaz, mely relatív prím az $ n$ -re és nem tanú az $ n$ összetettségére vonatkozólag.

A Miller-Rabin teszt alkalmazása egy páratlan, pozitív egész esetén azt jelenti, hogy véletlenszerűen választunk egy $ a\in\{2,3,\ldots,n-1\}$ számot. Ha $ (a,n)>1$ , akkor $ n$ összetett. Egyébként kiszámoljuk az $ a^d$ , $ a^{2d}$ , $ \ldots$ , $ a^{2^{s-1}d}$ számokat. Ha találunk tanút az $ n$ összetettségére, akkor $ n$ összetett. Annak a valószínűsége, hogy nem találtuk meg a tanút legfeljebb 1/4. Ha megismételjük a Miller-Rabin tesztet $ t$ -szer, akkor a korábbi valószínűség legfeljebb $ (1/4)^t$ . Például $ t=10$ esetén ez a valószínűség legfeljebb $ 1/2^{10}\sim 1/10^6$ . A még részletesebb vizsgálatok kimutatták, hogy ez a (hibázási) valószínűség valójában még kisebb.

6.5. Véletlen prímek

A legtöbb nyilvános kulcsú kriptorendszerben véletlen prímszámokra van szükség, de adott rögzített bithosszúsággal.

Ha egy $ k$ bithosszúságú prímet akarunk előállítani, akkor először véletlenszerűen generálunk egy páratlan $ k$ -bites számot. Ehhez az első és utolsó bit legyen 1-es, a maradék $ k-2$ bitet válasszuk ki egyenletes eloszlás szerint véletlenszerűen. Ezután teszteljük a számot, hogy prím. Először egy adott $ B$ korlát alatti prímekkel való oszthatóságot nézzük meg, ahol tipikusan a korlát $ B=10^6$ . Ha nincs prímosztó, akkor alkalmazzuk a Miller-Rabin tesztet $ t$ -szer. A $ t=3$ választás elegendő ahhoz, hogy a hiba valószínűsége kisebb legyen mint $ (1/2)^{80}$ , ha $ k\geq 1000$ . Ha ezek a tesztek nem találnak tanút, akkor a szám prím. Ha a triviális osztás hatékonyabb, mint a Miller-Rabin teszt, akkor nagyobb $ B$ korlátot kell választani.

Feladatok (prímszám generálás)

  1. Használjunk Fermat tesztet, hogy megmutassuk az 1111 számról, hogy nem prím!

  2. Határozzuk meg a $ \pi(100)$ -t! Hasonlítsuk össze a fejezetben adott korláttal!

  3. Határozzuk meg a legkisebb 2-es alapú pszeudoprímet!

  4. Használjuk a Fermat tesztet, hogy megmutassuk az ötödik Fermat szám ( $ F_5=2^{2^5}+1$ ) összetettségét. Bizonyítsuk be, hogy az összes Fermat prím pszeudoprím a 2-es alapra.

  5. Használjuk a Miller-Rabin tesztet, hogy megmutassuk az ötödik Fermat szám ( $ F_5=2^{2^5}+1$ ) összetettségét

  6. Bizonyítsa be, hogy egy Carmichael szám legalább három különböző prímfaktorral rendelkezik!

  7. Készítsünk olyan programot, amely implementálja a Miller-Rabin tesztet és meghatározza a legkisebb 512 bites prímet!

  8. Határozzuk meg a Miller-Rabin teszttel a tanúkat a 221 összetettségére az $ \{1,2,\ldots,220\}$ halmazban.

7. Nyilvános kulcsú titkosítás

Korábban már tárgyaltuk a szimmetrikus kriptorendszerek esetén, hogy a kulcs megosztása és kezelése igen lényeges. Amikor Alice és Bob ilyen rendszert használ, akkor előtte ki KELL cserélniük a titkos kulcsot, hogy azután titkosítva tudjanak kommunikálni egymással. A kulcs cseréhez szükségük van egy biztonságos csatornára vagy egy futárra. A kulcs-csere probléma még bonyolultabbá válik, ha sok ember szeretné kicserélni a titkosított üzeneteit pl. az Interneten.

Ha egy kommunikációs hálózat $ n$ felhasználóval rendelkezik és bármely kettő kulcsot cserél, akkor $ n(n-1)/2$ titkos kulcs cserére van szükség és az összes ilyen kulcsot biztonságos helyen kell tartani. Így pl. $ n=1000$ esetén 499500db kulcs kell.

Egy másik megoldási lehetőség a kulcs cserére egy kulcs központ használata, melyben minden felhasználó kicserélheti a titkos kulcsát ezzel a kulcs központtal. Ha Alice üzenetet akar küldeni Bobnak, akkor titkosítja az üzenetet a saját titkos kulcsával és elküldi a kulcs központba. A központ ismerve az összes titkos kulcsot dekódolja az üzenetet Alice kulcsával, majd kódolja Bob kulcsával és elküldi neki. Ebben az esetben $ n$ felhasználó esetén a kulcscserék száma $ n$ -re redukálódik. Azonban a kulcs központ ismeri az összes titkos üzenetet, miközben biztonságosan kell tárolnia a tikos kulcsokat.

A nyilvános kulcsú rendszerekben a kulcsok kezelése egyszerűbb. Az ilyen rendszerekben a dekódoló kulcs a titkos. A titkos kulcs kiszámítása a nyilvános kulcsból elérhetetlen.

A nyilvános kulcsokat egy nyilvános helyen tárolják, ahol megtalálható az adott felhasználó nyilvános kulcsa. Ha Bob üzenetet akar küldeni Alice-nak, akkor megkapja a nyilvános kulcsát Alice-nak. Ezzel titkosítja az üzenetet és elküldi Alice-nak. Alice képes dekódolni az üzenetet a saját titkos kulcsával.

A nyilvános kulcsú kriptorendszerekben nincs szükség kulcs cserére a felhasználók között. Bár mindenki olvashatja a nyilvános kulcsokat, de védeni kell a jogosulatlan írástól. Ha például a támadó képes kicserélni Alice nyilvános kulcsát a sajátjára, akkor az Alice-nak küldött üzeneteket el tudja olvasni.

Sajnos a nyilvános kulcsú rendszerek nem olyan hatékonyak, mint a legtöbb szimmetrikus kriptorendszer. Ezért a gyakorlatban a nyilvános kulcsú és a szimmetrikus rendszerek kombinációját használják.

Például ha Alice egy $ m$ üzenetet akar küldeni Bob-nak, akkor Alice generál egy szakasz kulcsot egy hatékony szimmetrikus rendszerben. Kódolja a szakasz kulccsal (és a szimmetrikus rendszerrel) az $ m$ üzenetet és megkapja a $ c$ titkosított szöveget. A kódolás gyors, mivel hatékony szimmetrikus rendszert használtunk. Alice kódolja a szakasz kulcsot is Bob nyilvános kulcsával. Ez megint gyosan megy, mivel a szakasz kulcs rövid, bár a nyilvános kulcsú rendszerben a kódolás nem hatékony. Ekkor Alice elküldi a $ c$ kódolt üzenetet és a titkosított szakasz kulcsot Bob-nak. Bob dekódolja a szakasz kulcsot a saját titkos kulcsával, majd az így kapott szakasz kulccsal dekódolja $ c$ -ből az $ m$ eredeti üzenetet. Ekkor a nyilvános kulcsú rendszert csak a szakasz kulcs cseréjére használtuk fel. A továbbiakban megadunk néhány nyilvános kulcsú rendszert.

7.1. RSA kriptorendszer

Az RSA nevet a feltalálóinak kezdőbetűiből kapjuk, azaz Ron Rivest, Adi Shamir és Len Adleman, amely az első nyilvános kulcsú rendszer volt és napjainkban is az egyik legfontosabb. A biztonsága két nagy prím szorzatának, mint összetett számnak a bonyolultságával adható meg.

7.1.1. Kulcs generálás

Először nézzük meg, hogy Bob miképpen állítja elő a saját (titkos-private) és a nyilvános (public) kulcsát. Bob előállít véletlenszerűen és egymástól függetlenül két nagy prímszámot. Legyenek ezek $ p$ és $ q$ , továbbá kiszámolja a szorzatukat $ n=pq$ .

Ezután Bob kiválaszt egy olyan $ e$ egész számot, hogy

$\displaystyle 1<e<\varphi(n)=(p-1)(q-1)$ és    lnko$\displaystyle (e,(p-1)(q-1))=1.
$

Megjegyezzük, hogy $ e$ mindig páratlan, hiszen $ p-1$ páros. Bob meghatároz egy $ d$ egész számot, melyre

$\displaystyle 1<d<(p-1)(q-1)$    és $\displaystyle de\equiv 1 \mod {(p-1)(q-1)}.
$

Mivel lnko$ (e,(p-1)(q-1))=1$ , ezért ilyen $ d$ szám mindig létezik.

Bob nyilvános kulcsa az $ (n,e)$ pár, a titkos kulcs a $ d$ szám. Az $ n$ számot az RSA modulusnak, az $ e$ -t kódoló kitevőnek, a $ d$ -t dekódoló kitevőnek nevezzük. Megjegyezzük, hogy a $ d$ titkos kulcs csak akkor számolható ki az $ e$ -ből, ha az $ n$ prímtényezői $ p$ és $ q$ ismert. Ezért a támadónak meg kell próbálnia elkészíteni az $ n$ prímtényezős felbontását. Ha sikerül, akkor könnyen meghatározza Bob $ d$ titkos kulcsát.

Példa:
Bob választ két prímszámot: $ p=11$ és $ q=23$ . Ekkor $ n=253$ és $ (p-1)(q-1)=10\cdot 22=4\cdot 5 \cdot 11$ . A legkisebb lehetséges $ e$ az $ e = 3$ , mivel lnko$ (3,23)=1$ . A kibővített euklideszi algoritmus adja, hogy $ d=147$ .

7.1.2. Kódolás

Először megnézzük, hogy miképpen kódolunk számokat az RSA rendszerben. Utána megmutatjuk az RSA használatát, mint blokk kódolót.

Az első variánsban a nyílt szövegtér mindazon $ m$ egész értéket tartalmazza, amelyre

$\displaystyle 0\leq m < n.
$

Az $ m$ szöveg kódolása a

$\displaystyle c=m^e \mod n
$

számítást jelenti.

A titkosított szöveg a $ c$ . Ha Alice ismeri az $ (n,e)$ nyilvános kulcsot, akkor képes kódolni. A megfelelő gyors hatványozási algoritmussal ez hatékonyan megtehető.

Most megmutatjuk, hogy miképpen használjuk az RSA-t, mint blokk kódolót. Használjuk a $ \Sigma=\mathbb{Z}_N=\{0,1,\ldots,N-1\}$ ábc-t valamilyen pozitív egész $ N$ -re. Legyen

$\displaystyle k=\lfloor \log_N n\rfloor.
$

Az $ m_1m_2\ldots m_k\in\Sigma^k$ megfelel az

$\displaystyle m=\sum_{i=1}^k m_iN^{k-i}.
$

Megjegyezzük, hogy a $ k$ megválasztása implikálja, hogy

$\displaystyle 0\leq m\leq (N-1)\sum_{i=1}^k N^{k-i}=N^k-1< n.
$

Ezáltal azonosíthatjuk a $ \Sigma^k$ blokkokat a nekik megfelelő egész számokkal. Egy $ m$ blokkot a $ c=m^e\mod n$ módon kódolunk. A $ c$ egész számot az $ N$ bázisban adunk meg. Mivel $ 0\leq c<n<N^{k+1}$ , ezért az $ N$ bázisban a $ c$ kifejtése legfeljebb $ k+1$ hosszúságú. Ezért írhatjuk a következőt:

$\displaystyle c=\sum_{i=0}^k c_iN^{k-i},\quad c_i\in\Sigma,\ 0\leq i\leq k.
$

A kódolt szöveg így a

$\displaystyle c_0c_1\ldots c_k
$

alakban adható meg. Ezzel a módszerrel az RSA a $ k$ hosszúságú blokkokat injektív módon képezi le $ k+1$ hosszúságú blokkokra.

Példa:
Legyen $ \Sigma=\{0,a,b,c\}$ a következő azonosítással:

0 $ a$ $ b$ $ c$
0 1 2 3

Ha az RSA modulus pl. $ 253=11\cdot 23$ , akkor kapjuk a $ k=\lfloor\log_4 253\rfloor=3$ . Ez a nyílt szövegblokkok hossza, a titkosított szöveg hossza 4. Kódoljuk a $ abb$ blokkot. Ez a 122 blokknak felel meg, amelyhez tartozó egész szám

$\displaystyle m=1\cdot 4^2+2\cdot 4^1+2\cdot 4^0=26.
$

Ez az egész a

$\displaystyle c=26^3 \mod {253}=119
$

értékre kódolódik, ahol $ e = 3$ (és a megfelelő titkos kulcs $ d=147$ ).

Ha ezt felírjuk a 4 bázisra nézve, akkor a

$\displaystyle c=1\cdot 4^3+3\cdot 4^2+1\cdot 4+3\cdot 1
$

felírást kapjuk, amely a

$\displaystyle acac
$

titkosított szövegnek felel meg.

7.1.3. Dekódolás

Az RSA dekódolása a következő tételt használja fel:

Tétel:
Legyen $ (n,e)$ egy nyilvános RSA kulcs és $ d$ a megfelelő titkos kulcs. Ekkor

$\displaystyle (m^e)^d\mod n=m
$

bármely $ m$ esetén, ha $ 0\leq m< n$

Ennek alapján a $ c$ titkosított értékből az $ m$ a következőképpen számolható: $ m=c^d\mod n$ . Ez is mutatja, hogy az RSA rendszer egy kriptorendszer, azaz minden kódoló függvényhez van dekódoló függvény.

7.1.4. Egy kis történelem...

Az 1970-es években Ralph Merkle, Whitfield Diffie és Martin Hellman egy új típusú kódot javasoltak, ez volt a nyilvános jelkulcsú titkosítás. Olyan titkosítást szerettek volna megvalósítani, melynél a titkosítási módszert publikussá is lehetne tenni, ugyanis nagyon nehéz visszacsinálni. Persze nem lenne túl épületes a módszer, ha a legális felhasználónak is rengeteg munkájába kerülne a fejtés. Ezt úgy lehetne megoldani, hogy egy parányi információt eltitkolunk az avatatlan szemlélőtől, amely aztán bennünket a gyors megfejtéshez vezet.

A matematikában egy kicsit is jártas olvasó bizonyára rögtön fennakad a ,,nagyon nehéz'' kifejezésen, ugyanis ez nem egy jól definiált fogalom. Ha pontosabb leírását szeretnénk elérni, akkor el kell mélyednünk egy kicsit a bonyolultság elmélet problémáiban.

7.1.4.1. Hátizsák probléma

Az első olyan probléma, amely alkalmas arra, hogy megvalósítsuk a nyilvánosság igényét, a Hátizsák probléma.

Maga a probléma a titkosítási lehetőségek nélkül is régen foglalkoztatja a matematikusokat. A kérdés az, hogy ha van egy hátizsákunk és egy csomó apróságunk, van-e módszer annak eldöntésére, hogy melyeket válasszunk ki azért, hogy a hátizsák tele legyen. Első olvasáskor is érezhető, hogy ha hatalmas hátizsák van birtokunkban és rengeteg kisebb nagyobb aprósággal akarjuk telezsúfolni, akkor a próbálkozós módszer elég sok ideig fog tartani.

Fogalmazzuk meg pontosabban a problémát: legyen adva egy $ A:=(a_1,a_2,\ldots,a_n)$ vektor, melynek elemei pozitív egészek, és egy pozitív $ k$ szám. Határozzuk meg azon $ a_i$ értékeket, melyeknek az összege $ k$ . A próbálkozások biztos módszerét követve $ 2^n$ lehetőséget végig próbálva biztosan eredményre jutunk. Ez $ 10$ elemnél nem is tart túl sokáig, hiszen csak 2048 próbálkozásra van szükségünk. Ellenben, ha 300 elemet kell végig próbálni, akkor már egy ,,nehéz'' problémával kell szembe néznünk.

Ha nem tévesztjük el célunkat, azaz továbbra is egy titkosítási módszer előállítása a cél, akkor a kérdés az, hogy van-e a Hátizsák problémának olyan változata amikor a bepakolás egyszerű. El tudunk képzelni ilyen kellemes helyzetet.

Legyen ugyanis minden csomag olyan nagy, hogy a tőle kisebb összes csomag együttesen beleférjen, de ne töltse ki. Ekkor a pakolás egyszerű. Vegyük elő a zsákot és rakjuk bele a lehető legnagyobb csomagot. Nyilvánvaló az előzőek miatt, hogy ha ezt kihagyjuk, akkor az összes többi kicsi már nem töltheti ki. A maradék helyre megint tegyük bele a lehető legnagyobb csomagot, amely lépés szükségszerűségét az előzőek indokolják. Ha folytatjuk ezeket a lépéseket, rövid időn belül célhoz érünk, azaz tele lesz a hátizsák, vagy meggyőződünk róla, hogy nem lehetséges a pontos bepakolás.

1982-ben Ralph Merkle felállított egy nyilvános kulcsú titkosítást, amelyet a Hátizsák problémára épített. A kitaláló 1000 dollárban fogadott, hogy a kód feltörhetetlen.

A pontosabb tárgyaláshoz szükségünk lesz a szupernövekvő vektor definíciójára. A továbbiakban feltételezzük, hogy a betűk pozitív egész számokat jelölnek.

Definíció:
Az $ A:=(a_1,a_2,\ldots,a_n)$ vektor szupernövekvő, ha minden szám nagyobb az előzőek összegénél, azaz

$\displaystyle a_j>\sum_{i=1}^{j-1}a_i \quad j=2,3,\ldots ,n.$

Ezek után lássuk az ötletet. Az egyszerűség kedvéért tegyük fel, hogy az $ AB$ betűpárt akarjuk titkosítani. Legyen adott a $ C:=(c_1,c_2,\ldots,c_{10})$ szupernövekvő vektor. Feleltessük meg az $ A$ betűt a $ 00001$ , a $ B$ betűt a $ 00010$ számnak. Más betűk esetén hasonló kódolást végzünk, azaz a betű ábc-beli sorszámát kettes számrendszerben 5 biten ábrázoljuk.

Mondhatjuk, hogy $ AB$ betűpárnak az $ X_{AB}=(0,0,0,0,1,0,0,0,1,0)$ vektor felel meg.

Képezzük ezután a $ C$ és $ X_{AB}$ vektorok $ CX_{AB}$ skaláris szorzatát. Nyilvánvaló, hogy az így kapott összeghez a szupernövekvő vektornak csak azok a komponensei adnak járulékot, amelyek megfelelői a kódolandó szövegben 1-el egyenlőek.

Így tehát egy egész számot kaptunk, amelyből a titkosított szöveget csak az tudja visszafejteni, aki meg tudja mondani, hogy ez a szám az $ A$ vektor mely komponenseinek összegeként áll elő. Ekkor fel tudunk írni egy egyesekből és nullákból álló vektort, amelyben egyes szerepel egy adott helyen, ha a megfelelő helyen lévő $ A$ -beli elem benne van az összegben és nulla, ha nem.

Ezután már csak dekódolnunk kell a nullákból és egyesekből álló számsorozatot és a megfejtés kész.

Szupernövekvő vektor esetén ez nem jelent problémát. Az előzőekben említett hátizsákba való bepakolás szisztémáját követve általános esetben a következőképpen járhatunk el:

Legyen adva egy $ A:=(a_1,a_2,\ldots,a_n)$ szupernövekvő vektor, és tételezzük fel, hogy a kódolt szöveg (ami csupa egyesből és nullából áll) pontosan egy $ n$ dimenziós $ X$ sorvektornak felel meg. Az $ AX$ skaláris szorzat értékét jelöljük $ k$ -val. Ekkor a fejtő a következőképpen járhat el. Megvizsgálja, hogy a $ k\geq a_n$ egyenlőtlenség teljesül-e. Ha igen, akkor az $ X$ vektor utolsó helyén egyes áll, ha nem, akkor nulla. Ezután $ k_1$ -et úgy definiáljuk, hogy

\begin{displaymath}
k_1:=\left\{
\begin{array}{ll}
k & \mbox{, ha $k<a_n$,}\\
k-a_n & \mbox{, ha $k\geq a_n$.}
\end{array}
\right.
\end{displaymath}

Hasonlóan folytatva az eljárást $ a_1$ -ig megkapjuk, hogy mely helyeken vannak egyesek és mely helyeken nullák. Ez az alak lesz a keresett betűknek a kódolt alakja. A dekódolás ezután egy egyszerű táblázat segítségével könnyen megvalósítható.

Jól látható, hogy ha az $ A$ vektort közöljük a megfejtés nagyon egyszerű. A továbbiakban az egyszerűség kedvéért az $ (A,\alpha)$ probléma megoldásáról beszélünk, ha egy $ \alpha$ számot bontunk fel egy $ A$ vektorban szereplő komponensek összegére.

A probléma az, hogy a fejtés az illegális fejtőnek is nagyon könnyű, ami pedig ellentmond kitűzött céljainknak.

Meg kell tehát vizsgálni, hogy hogyan tudjuk ,,elrontani'' az $ A$ vektort úgy, hogy ne látszódjon szupernövekvőnek, de mi vissza tudjuk belőle állítani az eredeti vektort. Így megvalósulna a nyilvános kulcsú kódolás gondolata, hisz egy tetszőleges vektor komponensei összegeként előállítani egy számot nagyon nehéz feladat, feltéve ha a komponensek elegendően nagyok és sokan vannak.

Ezek a nem pontosan körülírt fogalmak azt jelentik, hogy olyan vektort kell választanunk, amelyekből az összeg tagjainak kiválasztása a fejtés szempontjából irreálisan hosszú ideig tart. Ami azt jelenti, hogy az illegális fejtőnek nagyon nehéz dolga van, a szupernövekvő vektor ismerője pedig könnyen megoldhatja az előző módon a fejtést.

Válasszunk egy olyan $ m$ természetes számot, melyre

$\displaystyle m>\sum_{i=1}^n a_i.$

Ez az $ m$ nyilvánvalóan sokkal nagyobb bármelyik $ a_i$ -nél, hisz az $ A$ vektor szupernövekvő volt. Legyen $ t$ olyan természetes szám, melyre $ (t,m)=1$ . Az $ m$ számot modulusnak, a $ t$ -t szorzónak nevezzük.

A $ t$ választásából következik, hogy létezik egy $ t^{-1}$ -el jelölt természetes szám, melyre

$\displaystyle tt^{-1}\equiv 1\mod{m}.$

Ezen választások után képezzük a $ ta_i,\ (i=1,2,\ldots,n)$ szorzatokat és redukáljuk $ \mod m$ , így rendre $ b_1,b_2,\ldots,n$ értékeket kapunk.

A $ B=(b_1,b_2,\ldots,b_n)$ vektort publikáljuk titkosító kulcsként. A $ B$ vektor nem szupernövekvő, így hiába publikus a kulcs, a fejtés gondot okoz. Az $ A$ vektoron végzett műveletek sorozatát erős moduláris szorzásnak nevezzük $ m$ -re és $ t$ -re vonatkozóan. A $ t,t^{-1}$ és $ m$ értékek képezik a titkos csapóajtót, amiknek segítségével a legális felhasználó visszafejtheti a $ B$ vektorból az $ A$ vektort. Ugyanakkor meghatározhatja a titkosításból származó $ \beta$ összeg $ \alpha$ ,,ősképét'', amit aztán $ A$ ismeretében és az említett algoritmus segítségével megfejthetünk. A csapóajtó használatát és a módszer jóságát a következő tétel bizonyítja.

Tétel:
Tegyük fel, hogy $ A=(a_1,a_2,\ldots,a_n)$ egy szupernövekvő vektor és a $ B$ vektort $ A$ -ból $ m$ -re és $ t$ -re vonatkoztatott erős moduláris szorzással származtatjuk. Tegyük fel továbbá, hogy

$\displaystyle u \equiv t^{-1}\mod m, \ \beta\ $   tetszőleges pozitív egész és    
$\displaystyle \alpha \equiv u\beta \mod m,\quad 0<\alpha<m.$    

Ekkor érvényesek a következő állítások:

Bizonyítás:
Az első rész nem szorul bizonyításra, hisz láttuk a megoldási módszer algoritmusát.

A harmadik rész bizonyításához tételezzük fel, hogy létezik egy $ n$ bites $ D$ vektor, amely megoldása a $ (B,\beta)$ hátizsák problémának, azaz $ BD=\beta$ . Következésképpen a

$\displaystyle \alpha\equiv u\beta=uBD\equiv u(tA)D\equiv AD\pmod{m}.$

Mivel $ m$ nagyobb $ A$ komponenseinek összegénél, ezért $ AD<m$ . Az $ \alpha<m$ egyenlőtlenség is teljesül $ \alpha$ definíciója miatt. Így nyilvánvalóan érvényes az $ AD=\alpha$ egyenlőség, azaz $ D$ megegyezik az $ (A,\alpha)$ hátizsákprobléma egyetlen megoldásával. Ami így a második rész érvényességét is igazolja.
$ \fbox{}$

Ralph Merkle az 1000 dolláros fogadását elvesztette. Adi Shamir a kód egyik változatát azonnal feltörte, bár ez nem volt elég a fogadás megnyeréséhez. Ernest Brickell-nek azonban 1985-ben sikerült egy gyors algoritmust találnia a hátizsákprobléma megoldására, azaz sikerült feltörnie az előzőekben megismert titkosítási módszert.

7.1.4.2. Az RSA titkosítási rendszerről még egy kicsit...

A számelmélet egy nagyon híres művelője G. H. Hardy (1877-1947) így írt munkásságáról:

- Soha nem csináltam semmi ,,hasznosat''. Az ész egyetlen felfedezése sem változtatott a világon, és nem valószínű, hogy valaha is változtatni fog rajta közvetve vagy közvetlenül, jól vagy rosszul, akár kis mértékben is.

- Részt vettem más matematikusok képzésében, ugyanolyan matematikusokéban, mint amilyen én vagyok, és munkájuk-- vagy legalábbis amennyi ebből az én segítségemnek tulajdonítható-- mind ez ideig épp olyan haszontalan volt, mint a sajátom. A matematikus életének értéke, bármiféle gyakorlati norma szerint ítéljük is meg, a nullával egyenlő és mindenképpen jelentéktelen a matematikán kívűl.
$ \fbox{}$

A kiváló matematikus sok megjegyzésével lehetne vitatkozni, de fél évszázad távlatából ez nem lenne túl bölcs dolog. Amiért mégis ide kívánkoztak ezek a sorok annak az az érdekes tény az oka, hogy a nyilvános kulcsú kódolás ötletének megvalósítása a számelmélethez, a ,,matematika királynőjéhez'', vezette a kutatókat, immáron gyakorlati hasznot húzva Hardy ,,haszontalan'' tudományából.

A hátizsák probléma megalkotásával párhuzamosan tovább folytak a kutatások a nyilvános kulcsú kódolás megvalósítása érdekében. Az új ötlet a prímek világából származik.

Úgy gondolhatnánk, hogy egy összetett szám prímtényezőkre bontása egyszerű dolog. Ez az elképzelés igaznak is bizonyul, ha a szám nem túlságosan nagy.

Ifj. Hendrik W. Lenstra ezt tréfásan úgy fogalmazta: Tegyük fel, hogy a takarítónő tévedésből kidobta a $ p$ és $ q$ számokat, de a $ pq$ szorzat megmaradt. Hogyan nyerhetjük vissza a tényezőket? Csakis a matematika vereségeként érzékelhetjük, hogy ennek legreményteljesebb módja a szeméttelep átguberálása és memohipnotikus technikák alkalmazása.

Ezen kis kitérő után vizsgáljuk tovább az RSA rendszert.

7.1.5. A titkos kulcs biztonsága

Mivel az RSA nyilvános kulcsú rendszer, ezért teljesülnie kell annak, hogy elérhetetlen kiszámolni a nyilvános $ (n,e)$ kulcsból a $ d$ titkos kulcsot. Nyilvánvaló hogy a $ d$ kiszámításának bonyolultsága megegyezik az $ n$ prímfaktorizációjának bonyolultságával.

Nyitott probléma, hogy egy adott RSA modulus faktorizációja minden esetben ,,bonyolult'', azaz csak RSA-ra alapuló rendszert nem szabad alkalmazni.

Az RSA megfelelő modulusának megválasztása csak úgy történhet, hogy a két prím közel egyforma hosszúságú legyen, de legalább 512 bithosszúságú.

A gyakorlatban adott hosszúságú véletlen prímeket használnak, de itt is vigyázni kell. Ugyanis, ha a $ p$ prím esetén a $ p-1$ kis prím faktorokkal rendelkezik, akkor az ún. $ p-1$ faktorizációs algoritmus sikeres (lásd később). Kérdés, hogy vannak-e ilyen speciális tulajdonságú prímek. A válasz egyszerű, ha a véletlen szám generálás jól működik, akkor nem kapunk ilyen eseteket ill. nagyon kicsi a valószínűsége, hogy ilyen előforduljon.

7.1.6. Az e és d megválasztása

Az $ e$ nyilvános kulcsot olyan kicsire választjuk, amennyire csak lehetséges, hogy a kódolás hatékony legyen. Az $ e=2$ választás nem lehetséges, hiszen $ \varphi(n)=(p-1)(q-1)$ páros, és teljesülnie kell a lnko$ ((p-1)(q-1),e)=1$ feltételnek. A legkisebb lehetséges kódoló kitevő az $ e = 3$ . Ha ezt használjuk, akkor a kódolás csak egy négyzetreemelést és egy szorzást igényel modulo $ n$ .

Azonban a kicsi kódoló kitevők használata, mint az $ e = 3$ választás nagyon veszélyes lehet, mert a támadó alkalmazhatja az ún. alacsony-kitevőjű támadást.

Ez akkor működik, ha ugyanazt az $ m$ üzenetet kódoljuk $ e$ -szer az $ e$ kulccsal és páronként relatív prím $ n_l$ ( $ 1\leq l\leq e$ ) RSA modulusokkal.

Képzeljük el a következő helyzetet. Egy bank ugyanazt az üzenetet küldi el számos ügyfelének, felhasználva azok nyilvános kulcsait. A konstrukciójuk miatt a RSA modulusok páronként relatív prímek (melyek egyenként nagy prímek szorzata).

A támadás a következő: legyen a $ c_i\equiv \mod n_i$ , $ 1\leq i\leq e$ a megfelelő RSA titkos üzenet. Ekkor a támadó a következő algoritmust alkalmazza.

  1. Határozzuk meg a $ c\equiv c_i\mod n_i$ értéket, ahol $ 1\leq i\leq e$ és $ 0\leq c < \prod_{i=1}^e n_i$ a kínai maradéktétel segítségével.
  2. Határozzuk meg az $ m$ üzenetet, mint az $ e$ -dik gyökét $ c$ -nek $ \mathbb{Z}$ -ben.

A következő tétel megmutatja, hogy a fenti algoritmus helyes:

Tétel:
Legyenek az $ e\in\mathbb{N}$ , $ n_1,n_2,\ldots,n_e\in\mathbb{N}$ számok páronként relatív prímek és $ m\in\mathbb{N}$ , ahol $ 0\leq m< n_i$ minden $ 1\leq i\leq e$ . Legyen $ c\in \mathbb{N}$ , melyre teljesül a $ c\equiv m^e \mod n_i$ , $ 1\leq i\leq e$ és $ 0\leq c\prod_{i=1}^e n_i$ . Ekkor $ c=m^e$ .

Az $ e$ -dik gyöke egy $ e$ -dik hatványnak könnyen meghatározható, így az alacsony-kitevőjű támadás jól alkalmazható.

Példa:
Legyen $ e = 3$ , $ n_1=143$ , $ n_2=391$ , $ n_3=899$ , $ m=135$ . Ekkor $ c_1=60$ , $ c_2=203$ , $ c_3=711$ . A kínai maradéktétel segítségével kapjuk az $ x_1,x_2,x_3$ számokat, melyekre teljesül a $ x_1n_2n_3\equiv 1 \mod n_1$ , $ n_1x_2n_3\equiv 1 \mod n_2$ , $ n_1n_2x_3\equiv 1 \mod n_3$ és $ x_1=-19$ , $ x_2=-62$ , $ x_3=262$ . Ezek segítségével $ c=(c_1x_1n_2n_3+c_2n_1x_2n_3+c_3n_1n_2x_3)\mod n_1n_2n_3=2460375$ . Innen kapjuk végül, hogy $ m=2460375^{1/3}=135$ .

Az alacsony-kitevőjű támadás nem alkalmazható, ha a kódolt üzenetek páronként különbözőek. Ez könnyen elérhető, ha a nyílt szövegbe véletlenszerűen választunk meg néhány bitet. Természetesen választhatunk nagy kódoló kitevőt is, például $ e=2^{16}+1$ az egyik legnépszerűbb.

7.1.7. Hatékonyság

Az RSA kódolás csak egy hatványozást igényel modulo $ n$ . A kicsi kódoló kitevőt érdemes választani, de vigyázni kell az alacsony-kitevőjű támadás miatt, mely miatt további speciális elemeket kell alkalmazni.

Az RSA dekódolás ugyancsak egy hatványozást igényel modulo $ n$ , de a dekódoló kitevőnek közel olyan nagynak kell lennie, mint az $ n$ . Kicsi $ d$ kulcs könnyen kiszámolható a nyilvános $ (n,e)$ kulcsból.

Tegyük fel, hogy az $ n$ RSA modulus egy $ k$ bites szám. Ekkor tipikusan $ d$ is egy $ k$ bites szám és $ k/2$ db bit 1-es. Így a gyors hatványozási technikával a dekódolás $ k$ db négyzetreemelést és $ k/2$ szorzást igényel modulo $ n$ . Összehasonlítva ezt $ k=1024$ -re a DES-szel a dekódolás elég lassúnak adódik.

Az RSA dekódolás gyorsítható, ha kihasználjuk a kínai maradéktételt. Ez a következőképpen működik. Alice dekódolni akarja a $ c$ titkos üzenetet. A saját titkos kulcsa $ d$ . Ekkor kiszámolja a

$\displaystyle m_p=c^{d\mod p-1}\mod p,\quad m_q=c^{d\mod q-1}\mod q
$

értékeket. Kiszámol még egy $ m\in\{0,1,\ldots,n-1\}$ számot úgy, hogy

$\displaystyle m\equiv m_p\mod p,\quad m\equiv m_q\mod q.
$

Ez az $ m$ éppen a kódolt nyílt szöveg lesz. Az $ m$ meghatározásához felhasználja a kibővített euklideszi algoritmust, hogy megtalálja azokat az $ y_p$ és $ y_q$ egészeket, melyekre

$\displaystyle y_p p+y_q q=1.
$

Ekkor

$\displaystyle m=(m_p y_q q+m_q y_p p)\mod n.
$

Megjegyezzük, hogy az $ y_p p\mod n$ és az $ y_q q\mod n$ együtthatók függetlenek a titkos szövegtől.

Megmutatjuk, hogy az RSA dekódolás a kínai maradéktétellel hatékonyabb, mint a szokásos változat. Tegyük fel, hogy az RSA modulus $ k$ -bites szám és a $ d$ is az. Ennek $ p$ és $ q$ prím faktorai $ k/2$ bites számok. Két legfeljebb $ r$ bites egész szám szorzása legfeljebb $ Cr^2$ ideig tart, ahol a $ C$ konstans. Hasonlóan az osztás ilyen típusú számokkal legfeljebb $ Cr^2$ időt igényel. Az $ m=c^d\mod n$ számolás legfeljebb $ 2Ck^3$ ideig tart.

Az $ m_p$ és az $ m_q$ kiszámítása $ Ck^3/2$ ideig tart, ahol elhanyagolhatjuk az $ y_p p\mod n$ és az $ y_q q\mod n$ számításokat, hiszen ez csak a kibővített euklideszi algoritmus egyszeri alkalmazását igényli, mely kvadratikus futási idővel rendelkezik. Az $ m=(m_p y_q q+m_q y_p p)\mod n$ számolás csak két szorzást és egy összeadást jelent, így tehát a kínai maradéktétel alkalmazásával 4-szer gyorsabb megoldást kaptunk a szokásos eljáráshoz képest.

7.1.8. Általánosítás

Az RSA általánosítása a következőt (is) jelentheti. A nyilvános kulcs egy véges $ G$ csoportból és az $ e$ kódoló kitevőből áll, ahol az $ e$ relatív prím a $ G$ csoport $ o$ rendjével. Az RSA esetén ez a $ (\mathbb{Z}/n\mathbb{Z})^*$ , ahol $ n$ az RSA modulus.

A titkos kulcs $ d$ , melyre $ ed\equiv 1\mod o$ . Nyilvánvalóan az $ o$ -t titkos helyen kell tartani, különben a $ d$ az előző kongruenciából könnyen meghatározható. Az üzenetek a $ G$ csoportba vannak beágyazva.

Olyan $ G$ csoportok meghatározása, melyeknél a rendet titokban kell tartani, miközben bárki számolhat $ G$ -ben nehéznek tűnik. Több RSA variáns ismert, de azonnal megszűnik a biztonságuk, ha az egészek faktorizációja könnyűvé válik. Ezért érdekesek a további altenatívák.

7.2. Rabin kódolás

Ez a titkosítás is a egész számok faktorizációjának bonyolultságára épül, de megmutatható, hogy aki feltöri a Rabin rendszert hatékonyan, az hatékonyan faktorizál egész számokat.

7.2.1. Kulcs generálás

Alice véletlenszerűen választ két nagy prímet $ p$ -t és $ q$ -t, ahol $ p\equiv q\equiv 3\mod 4$ . Ez a választás teszi még hatékonyabbá a dekódolást. De a később láthatjuk, hogy enélkül is jól működik a rendszer.

Alice kiszámolja az $ n=pq$ -t, az $ n$ Alice nyilvános kulcsa, a $ (p,q)$ pár a titkos kulcs.

7.2.2. Kódolás és dekódolás

Hasonlóan az RSA kódoláshoz a nyílt szövegtér $ \{0,1,\ldots,n-1\}$ halmaz. Egy $ m\in\{0,1,\ldots,m\}$ nyílt szöveg esetén Bob felhasználja Alice $ n$ nyilvános kulcsát és megkapja a alábbi értéket:

$\displaystyle c=m^2\mod n.
$

A Rabin rendszer is használható blokk kódolóként.

Alice-nak az $ m$ meghatározásához a $ c$ gyökeiből kell kiindulnia. Kiszámolja az

$\displaystyle m_p=c^{(p+1)/4}\mod p,\quad m_q=c^{(q+1)/4}\mod q
$

értékeket. Ekkor a $ \pm m_p+p\mathbb{Z}$ két gyöke a $ c+p\mathbb{Z}$ -nek $ \mathbb{Z}/p\mathbb{Z}$ -ben, és a $ \pm m_q+q\mathbb{Z}$ két gyöke a $ c+q\mathbb{Z}$ -nek $ \mathbb{Z}/q\mathbb{Z}$ -ben. Ezek a négyzetgyökök valóban könnyen meghatározhatóak, mivel $ p$ és $ q$ kongruens 3-mal modulo 4. Ha ez nem igaz, akkor is meghatározhatóak, de nehezebben (polinomiális időben). Ekkor Alice kiszámolja a négy gyökét a $ c+p\mathbb{Z}$ -nek. Ehhez az RSA-hoz hasonlóan felhasználja a kibóvített euklideszi algoritmust, azaz meghatároz olyan $ y_p$ és $ y_q$ egész együtthatókat, melyekre

$\displaystyle y_p p+y_q q=1.
$

Ezután kiszámolja az

$\displaystyle r=(y_p p m_q+y_q q m_p)\mod n,\quad s=(y_p p m_q - y_q q m_p)\mod n
$

értékeket. Könnyű belátni, hogy $ \pm r$ és a $ \pm s$ a négy gyöke $ c$ -nek modulo $ n$ az $ \{0,1,\ldots,n-1\}$ halmazban. Az egyik ezek közül az eredeti $ m$ üzenet lesz.

Példa:
Alice a $ p=11$ és a $ q=23$ prímek használja. Ekkor $ n=253$ . Bob kódolja az $ m=158$ üzenetet. Ő kiszámolja a

$\displaystyle c=m^2\mod n=170
$

értéket. Alice meghatározza az $ y_p=-2$ és az $ y_q=1$ értékeket.

Ő a következő négyzetgyököket kapja:

$\displaystyle m_p=c^{(p+1)/4}\mod p=c^3\mod p=4,$    
$\displaystyle m_q=c^{(q+1)/4}\mod q=c^6\mod q=3.$    

Továbbá meghatározza az

$\displaystyle r=(y_p p m_q+y_q q m_p)\mod n=-2\cdot 11\cdot 3+1\cdot 23\cdot 4\mod n=26
$

és

$\displaystyle s=(y_p p m_q-y_q q m_p)\mod n=-2\cdot 11\cdot 3-1\cdot 23\cdot 4\mod n=95
$

értékeket. A 170 négyzetgyöke modulo 253 az $ \{1,\ldots,252\}$ halmazban a 26, 95, 158, 227. Az egyik az eredeti üzenet.

Több módszer is van arra, hogy kiválasszuk az eredeti üzenetet a gyökök közül. Alice kiválaszthatja azt, amelyik a leginkább értelmesnek tűnik. Ez viszont sok munkával is járhat, pl. ha a kódolt üzenet éppen egy szimmetrikus rendszer kulcsa. Az is egy lehetséges megoldás, hogy csak speciális alakú üzeneteket kódolunk. Például csak olyan üzeneteket, melyek utolsó 64 bitje egyenlő. Kicsi a valószínűsége annak, hogy a titkos üzenet több gyöke is rendelkezzen ezzel a tulajdonsággal, így Alice ki tudja választani a konkrét nyílt szöveget.

7.2.3. Hatékonyság és biztonság

A Rabin rendszer mindössze egy négyzetgyökvonást igényel, így a rendszer hatékonyabb, mint az RSA (még a lehetséges legkisebb 3 kódoló kitevő választás esetén is). A dekódolás ugyanannyira költséges, mint az RSA (amikor a kínai maradéktétellel használjuk).

Ugyanis két hatványozás van modulo $ p$ és $ q$ , továbbá a kínai maradéktétel alkalmazása.

Korábban jeleztük, hogy a Rabin rendszer feltörése egyenértékű a Rabin modulus faktorizációjának problémájával. Nyilvánvaló, hogy ha ismert a modulus felbontása, akkor a Rabin rendszer feltörhető. Fordítva is igaz, nézzük meg most ezt.

Tegyük fel, hogy a támadó fel tudja törni a Rabin rendszert. Legyen $ n$ a nyilvános kulcs, melyek prím faktorai $ p$ és $ q$ . Legyen $ R$ az az algoritmus, mely feltöri a Rabin rendszert. Adott $ c\in\{0,1,\ldots,n-1\}$ esetben, ahol $ c+n\mathbb{Z}$ egy négyzetszám a $ (\mathbb{Z}/n\mathbb{Z})^*$ az $ R$ kiszámolja az $ m=R(c)\in\{0,1,\ldots,n-1\}$ értéket, mely az eredeti üzenet. Más szavakkal adott $ c$ négyzetszám esetén az $ R$ algoritmus meghatározza annak $ m$ négyzetgyökét modulo $ n$ .

A támadó véletlenszerűen kiválaszt egy $ x\in\{1,\ldots,n-1\}$ egész értéket. Ha $ (x,n)\neq 1$ , akkor ez a legnagyobb közös osztó megegyezik az $ n$ egyik prímfaktorával. Így az $ n$ faktorizáció megtörtént. Más esetben a támadó kiszámolja az

$\displaystyle c=x^2\mod n$    és $\displaystyle m=R(c)
$

értékeket. Az $ m+n\mathbb{Z}$ maradékosztály a $ c+n\mathbb{Z}$ négyzetgyöke. Ennek szükségképpen meg kell egyeznie az $ x+n\mathbb{Z}$ -vel, de $ m$ kielégíti a következő kongruenciák valamelyikét:

$\displaystyle m\equiv x\mod p$    és $\displaystyle m\equiv x \mod q,$    
$\displaystyle m\equiv -x\mod p$    és $\displaystyle m\equiv -x \mod q,$    
$\displaystyle m\equiv x\mod p$    és $\displaystyle m\equiv -x \mod q,$    
$\displaystyle m\equiv -x\mod p$    és $\displaystyle m\equiv x \mod q.$    

Az első esetben azt kapjuk, hogy $ m=x$ és így $ (m-x,n)=n$ . A másodikban $ m=n-x$ és így $ (m-x,n)=1$ . A harmadikban azt kapjuk, hogy $ (m-x,n)=p$ , míg a negyedikben $ (m-x,n)=q$ . Mivel $ x$ véletlenszerűen válaszható pl. egyenletes eloszlás szerint, így minden eset egyenlő valószínűséggel rendelkezik. Ezáltal az $ n$ faktorizációjának valószínűsége $ 1/2$ . $ k$ -szor történő ismétlés esetén $ n$ faktorizációjának valószínűsége $ 1-(1/2)^k$ .

Példa:
Legyen $ n=253$ , mint korábban. Tegyük fel, hogy a támadó képes kiszámolni az $ R$ algoritmussal a négyzetgyököt modulo 253. Ekkor az $ x=17$ választás mellett a lnko$ (17,253)=1$ -et kapja. Ekkor kiszámolja a $ c=17^2\mod 253=36$ értéket. A 36 négyzetgyöke modulo 253 a 6, 17, 236, 247. Így a lnko$ (6-17,253)=11$ és lnko$ (247-17,253)=23$ . Ha $ R$ adja valamelyik négyzetgyököt, akkor a támadó faktorizálta az $ n$ -et.

A fenti faktorizáló algoritmusban feltételeztük, hogy a nyílt szövegtér tartalmazza az $ \{0,1,\ldots,n-1\}$ halmaz minden elemét. Tegyük fel, hogy a nyílt szöveg speciális formájú. Korábban jeleztük, hogy ezzel kerülhető el a sok munka a dekódolás során, amikor az eredeti szöveget kell kiválasztani. De ekkor a faktorizáló algoritmus nem működik. Ugyanis az $ R$ algoritmus csak olyan titkos szöveget tud dekódolni, mely speciális formájú nyílt szövegből kaptunk. Amikor a támadó megpróbálja faktorizálni az $ n$ -et, neki biztosnak kell lennie abban, hogy a $ c=x^2\mod n$ speciális alakú. Nem világos, hogyan tudná ezt megtenni, hacsak az $ x$ maga is speciális alakú. Ebben az esetben az $ R$ által adott négyzetgyök nem vezet a faktorizációhoz.

7.3. Diffie-Hellman féle kulcscsere

Ebben a részben a Diffie és Hellman szabványát(protokollt) adjuk meg a titkos kulcs cseréhez nem biztonságos csatornában.
Ez a protokoll önmagában nem egy nyilvános kulcsú kriptorendszer, de ez az alapja az ElGamal rendszernek, mely a következő alfejezetben található.
A szituáció a következő. Alice és Bob egy szimmetrikus rendszert szeretne használni, hogy titokban tartsák üzeneteiket egy nem biztonságos csatornában. Kezdetben Alice-nak és Bob-nak ki kell cserélnie egy titkos kulcsot. A Diffie-Hellman protokoll esetén bárki, aki lehallgatja a kulcscserét nem képes előállítani belőle a titkos kulcsot. Voltaképpen ez a szabvány egy mérföldkő a nyilvános kulcsú kriptorendszerekben.
A kulcscsere nem az egészek faktorizációs problémakörén alapszik, hanem a diszkrét logaritmus problémán (DLP).

7.3.1. Diszkrét logaritmus

Legyen $ p$ egy prímszám. Ismert, hogy a $ (\mathbb{Z}/p\mathbb{Z})^*$ csoport ciklikus, melynek a rendje $ p-1$ . Legyen $ g$ egy primitív gyök modulo $ p$ . Ekkor tetszőleges $ A\in\{1,2,\ldots,p-1\}$ egész esetén létezik egy olyan $ a\in\{0,1,2,\ldots,p-2\}$ kitevő, hogy

$\displaystyle A\equiv g^a \mod p.
$

Ezt az $ a$ kitevőt (exponens) hívjuk az $ A$ diszkrét logaritmusának a $ g$ bázisra vonatkozólag. Jelölés: $ a=$dlog$ _g A$ . A diszkrét logaritmus kiszámítása elég nehéz. Nem ismert olyan hatékony algoritmus, mely ezen problémát hatékonyan megoldja. De az sem bizonyított, hogy ez a probléma voltaképpen nehéz.

Példa:
Legyen a $ p=13$ . Egy primitív gyök modulo 13 a 2. A következő táblázatban megadjuk az összes $ \{1,2,\ldots,12\}$ halmazban levő egész diszkrét logaritmusát a 2 bázisra nézve.

$ A$ 1 2 3 4 5 6 7 8 9 10 11 12
dlog$ _2 A$ 0 1 4 2 9 5 11 3 8 10 7 6

A diszkrét logaritmus tetszőleges ciklikus csoportban definiálható. Legyen $ G$ $ n$ -ed rendű egy ciklikus csoport $ g$ generátorral, és legyen $ A$ egy csoportbeli elem. Ekkor létezik egy $ a\in\{0,1,\ldots,n-1\}$ kitevő, melyre

$\displaystyle A=g^a.
$

Ez az exponenst nevezzük az $ A$ diszkrét logaritmusának a $ g$ bázisra vonatkozólag.

Példa:
Tekintsük a $ \mathbb{Z}/n\mathbb{Z}$ additív csoportot, ahol $ n$ egy pozitív egész. Ez ciklikus, rendje $ n$ . A generátora ennek a csoportnak az $ 1+n\mathbb{Z}$ . Legyen $ A\in\{0,1,\ldots,n-1\}$ . Az $ a$ diszkrét logaritmusa az $ A+n\mathbb{Z}$ -nak az $ 1+n\mathbb{Z}$ bázisra nézve az $ A\equiv a\mod n$ kongruenciát adja. Így $ a=A$ . A további generátorok a $ \mathbb{Z}/n\mathbb{Z}$ -ben azok a $ g+n\mathbb{Z}$ maradékosztályok, ahol lnko$ (g,n)=1$ . Az $ a$ diszkrét logaritmusa az $ A+n\mathbb{Z}$ -nek a $ g+n\mathbb{Z}$ bázisra nézve a

$\displaystyle A\equiv ga\mod n
$

kongruenciát adja. Ez megoldható pl. a kibővített euklideszi algoritmus segítségével. A $ \mathbb{Z}/n\mathbb{Z}$ -ben a diszkrét logaritmus kiszámítása hatékonyan megy, ezért ez a csoport nem használható a biztonságos Diffie-Hellman féle kulcscsere implementálásakor.

7.3.2. A kulcscsere

A Diffie-Hellman féle kulcscsere a következőképpen működik. Alice és Bob meg akarnak egyezni egy titkos kulcsban, miközben egy nem biztonságos csatornán keresztül kell kommunikálniuk. Először megegyeznek egy nagy $ p$ prímben és egy $ g$ primitív gyökben modulo $ p$ , ahol $ 2\leq g \leq p-2$ . A $ p$ prím és a $ g$ primitív gyök nyilvános, azaz használhatják a nem biztonságos csatornát.

Először Alice kiválaszt véletlenszerűen egy $ a\in\{0,1,\ldots,p-2\}$ egész számot. Kiszámítja a

$\displaystyle A=g^a\mod p
$

értéket és elküldi az $ A$ eredményt Bob-nak, miközben az $ a$ kitevőt titokban tartja.

Bob ugyancsak kiválaszt véletlenszerűen egy $ b\in\{0,1,\ldots,p-2\}$ egész számot. Ő is kiszámolja a

$\displaystyle B=g^b\mod p
$

értéket és az eredményt elküldi Alice-nak. Ő is titokban tartja a $ b$ kitevőt. Hogy megkapjuk a titkos kulcsot, Alice kiszámolja a

$\displaystyle B^a\mod p=g^{ab}\mod p
$

értéket és Bob is kiszámolja az

$\displaystyle A^b=g^{ab}\mod p
$

értéket. Ekkor a közös (titkos) kulcs a

$\displaystyle K=g^{ab}\mod p.
$

Példa:
Legyen $ p=17$ és $ g=3$ . Alice az $ a=7$ kitevőt választja, kiszámolja a

$\displaystyle g^a\mod p=11
$

értéket és elküldi Bob-nak ($ A=11$ ). Bob kiválasztja a $ b=4$ kitevőt, kiszámolja a

$\displaystyle g^b=\mod p=13
$

értéket és elküldi Alice-nak ($ B=13$ ). Alice kiszámolja a

$\displaystyle B^a\mod p=4,
$

Bob ugyancsak kiszámolja a $ A^b\mod p=4$ értéket. A közös (titkos) kulcs a 4.

7.3.3. Biztonság

A támadó megtudhatja a $ p$ , $ g$ , $ A$ és $ B$ értékeket, de nem tudja az $ a$ diszkrét logaritmusát az $ A$ -nak és a $ b$ diszkrét logaritmusát az $ B$ -nek. Megpróbálja meghatározni a $ K=g^{ab}\mod p$ titkos kulcsot az ismert adatokból. Ez a Diffie-Hellman probléma. Ha a támadó meg tudja határozni a titkos kulcsot, akkor meg tudja oldani a Diffie-Hellman problémát. Amint a probléma megoldása nehéz, a támadó nem képes meghatározni a titkos kulcsot.

A középső ember típusú támadás esetén a támadó Alice és Bob közé áll, azaz Alice nem tudhatja/ellenőrizheti, hogy valóban Bob-tól kap üzenetet, és hasonlóan Bob-ra is ez teljesül. Ekkor minden kulcscsere és üzenetváltás a támadón keresztül zajli, aki így azokat elolvashatja (dekódolja).

Amikor Alice üzenetet küld Bob-nak, akkor a támadóval korábban kicserélt kulcs segítségével kódol, amit a támadó dekódol, majd kódolja a Bob-bal kicserélt ill. létrehozott titkos kulccsal.

Ennek elkerülése érdekében használjuk majd a digitális aláírást (lásd később).

Egy későbbi fejezetben tekintjük át azokat a csoportokat, melyekre nézve a Diffie-Hellman féle probléma megoldása nehéz.

7.4. ElGamal féle titkosítás

Ez a kriptorendszer szorosan kötődik a Diffie-Hellman kulcscseréhez. A rendszer biztonsága ugyancsak a Diffie-Hellman féle probléma bonyolultságán alapul a $ (\mathbb{Z}/p\mathbb{Z})^*$ -ban.

7.4.1. Kulcs generálás, kódolás, dekódolás

Alice kiválaszt egy $ p$ prímet, ahogy azt korábban láttuk, a $ g$ primitív gyök modulo $ p$ . Ekkor véletlenszerűen kiválaszt egy $ a\in\{0,1,\ldots,p-2\}$ kitevőt és kiszámolja az

$\displaystyle A=g^a\mod p
$

értéket. Ekkor Alice nyilvános kulcsa a $ (p,g,A)$ . A titkos kulcsa az $ a$ kitevő. Az $ A$ egész Alice kulcsrésze a Diffie-Hellman protokollból. Ez a kulcsrész rögzített az ElGamal kriptorendszerben.

A nyílt szövegtér a $ \{0,1,\ldots,p-1\}$ halmaz. Egy $ m$ üzenet kódolásához Bob megkapja a $ (p,g,A)$ nyilvános kulcsot Alice-tól.

Kiválaszt véletlenszerűen egy $ b\in\{0,1,\ldots,p-2\}$ kitevőt és kiszámolja a

$\displaystyle B=g^b\mod p
$

értéket. A $ B$ szám Bob kulcsrésze a Diffie-Hellman féle szabványból. Bob meghatározza a

$\displaystyle c=A^bm\mod p
$

értéket. Más szavakkal, Bob kódolja az $ m$ üzenetet azzal, hogy megszorozza azt a Diffie-Hellman féle titkos kulccsal modulo $ p$ .

Alice megkapja a $ (B,c)$ párt. Az $ m$ üzenet viszaállításához elosztja a $ c$ -t a $ B^a$ Diffie-Hellman féle titkos kulccsal modulo $ p$ . Hogy elkerülje az inverz számítást modulo $ p$ , meghatározza az $ x=p-1-a$ kitevőt. Mivel $ 1\leq a\leq p-2$ , így $ 1\leq x\leq p-2$ .

Ekkor kiszámolja az $ m=B^x c\mod p$ értéket. Ez valóban az eredeti üzenet, ugyanis

$\displaystyle B^xc\equiv g^{b(p-1-a)}A^bm\equiv (g^{p-1})(g^{a})^{-b}A^bm\equiv A^{-b}A^bm\equiv m\mod p.
$

Példa:
Alice kiválasztja a $ p=23$ , $ g=7$ , $ a=6$ értékeket és kiszámolja az $ A=g^a\mod p=4$ -et. A nyilvános kulcsa $ (23,7,4)$ . A titkos kulcsa a 6. Bob kódolja az $ m=7$ üzenetet. Kiválasztja a $ b=3$ -at, kiszámolja a $ B=g^b\mod p=21$ -et és a $ c=A^bm\mod p=11$ értéket. A kódolt üzenet a $ (21,11)$ . Alice visszaállítja az $ m$ üzenetet, mivel kiszámolja a $ B^{p-1-a}\mod p=7=m$ értéket.

7.4.2. Hatékonyság

Az ElGamal dekódolás az RSA-hoz hasonlóan csak egy (moduláris) hatvány kiszámítását igényli. Látni fogjuk, hogy mindkét rendszerben a modulus egyforma méretű. Továbbá a kínai maradéktétel nem gyorsítja az ElGamal dekódolást.

Az ElGamal kódolás két (moduláris) hatványozást igényel: az $ A^b\mod p$ és a $ B=g^b\mod p$ . Az RSA csak egy (moduláris) hatványozást igényel, de az ElGamal hatványok kiszámítása független attól a nyílt szövegtől, amelyet aktuálisan kódolni akarunk. Ezért ezek a számítások előre letárolhatóak. Így a tényleges kódolás csak egy (moduláris) szorzást jelent és ezért jóval hatékonyabb, mint az RSA kódolás. Nyilvánvalóan az előre kiszámított hatványokat biztonságban kell tartani, mint pl. egy bankkártyát.

Az ElGamal kriptorendszerben a kódolt szöveg kétszer olyan hosszú, mint a nyílt szöveg. Ezt üzenet kiterjesztésnek vagy bővülésnek nevezzük és ez egy hátránya a rendszernek. Másrészről az ElGamal egy randomizált rendszer, amelyet előnyként kell tekinteni.

A nyilvános kulcs hosszát redukálhatjuk, ha ugyanazt a $ p$ prímet használjuk az összes nyilvános kulcsban. Azonban, ha ezen prímre vonatkozó diszkrét logaritmus kiszámítása könnyűvé válik, akkor a teljes rendszer elveszíti a biztonságát.

7.4.3. ElGamal és Diffie-Hellman

Ha egy támadó képes kiszámítani a diszkrét logaritmust modulo $ p$ , akkor fel tudja törni az ElGamal rendszert is. Csak meghatározza Alice titkos $ a$ kulcsát, mint az $ A$ diszkrét logaritmusát a $ g$ alapra vonatkozólag.

Ekkor kiszámolja a nyílt szöveget az $ m=B^{p-1-a}c\mod p$ formulából. Viszont nem ismert, hogy az ElGamal feltöréséből kapunk-e lehetőséget a diszkrét logaritmus hatékony kiszámítására modulo $ p$ . Nyilvánvaló, hogy az ElGamal feltörése és a Diffie-Hellman féle kulcscsere feltörése egyformán bonyolult.

7.4.4. Paraméterek megválasztása

A jelenlegi alkalmazások alapján a $ p$ prímszámnak legalább 768 bithosszúnak kell lennie. Továbbá, később ismertetésre kerülő Pohlig-Helman és a számtest szita algoritmusok ezen prímeket elkerülik. A legjobb választás az egyenletes eloszlás szerinti véletlen prímgenerálás valamilyen hossz szerint.

Minden egyes új ElGamal titkosítás esetén egy új $ b$ kitevőt kell választani.

Ha Bob ugyanazt a $ b$ -t választja az $ m$ és $ m'$ kódolásához, akkor a

$\displaystyle c=A^bm\mod p
$ és $\displaystyle c'=A^bm'\mod p
$

kapja meg. Ekkor teljesül a

$\displaystyle c'c^{-1}\equiv m'm^{-1}\mod p
$

összefüggés. A támadó, aki ismeri az $ m$ -et vissza tudja állítani az $ m'$ -t felhasználva az

$\displaystyle m'=c'c^{-1}m\mod p
$

formulát.

Feladatok (nyilvános kulcsú titkosítás)

  1. Mutassuk meg, hogy az RSA kriptorendszerben a $ d$ dekódoló kitevő megválasztható úgy is, hogy $ de\equiv 1 \mod$   lkkt$ (p-1,q-1)$ !

  2. Határozzuk meg az összes kódoló kitevőt az $ m=437$ RSA modulusra nézve!

  3. Generáljunk két 8 bites prímszámot és a megfelelő 16 bites RSA modulust úgy, hogy az $ e=5$ kulcsot használhassuk. Számoljuk ki a megfelelő $ d$ titkos kulcsot. Kódoljuk a 110100110110111 sztringet az 5 nyilvános kulccsal!

  4. Alice kódolja az $ m$ üzenetet Bob nyilvános (899,11) RSA kulccsával. Ekkor a rejtett szöveg a 468. Határozzuk meg az eredeti/nyílt szöveget!

  5. Mennyi művelet szükséges egy RSA kódoláshoz, ha a kitevő $ e=2^{16}+1$ ?

  6. Ugyanazt az $ m$ üzenetet kódolták a következő RSA kulcsokkal: (391,3), (55,3) és (87,3). A rejtett szövegek rendre: 208, 38 és 32. Használjuk az alacsony kitevős támadást, hogy meghatározzuk $ m$ -et!

  7. Ugyanazt az $ m$ üzenetet kódolták a következő RSA kulcsokkal: (493,3) és (493,5). A rejtett szövegek rendre: 293 és 421. Használjuk a közös modulus támadást, hogy meghatározzuk $ m$ -et!

  8. Legyen $ n=1591$ . Alice nyilvános RSA kulcsa $ (n,e)$ , ahol $ e$ a lehető legkisebb. Alice megkapja a kódolt $ c=1292$ szöveget. Dekódoljuk az üzenetet a kínai maradéktétel segítségével!

  9. Alice megkapja az ElGamal-lal titkosított szöveget ($ B=30$ , $ c=7$ ). A titkos kulcsa a ($ p=43$ , $ g=3$ ). Határozzuk meg az eredeti szöveget!

  10. Legyen $ p=53$ , $ g=2$ , $ A=30$ Bob nyilvános ElGamal kulcsa. Alice használja, hogy előállítsa a rejtett (24, 37) szöveget. Határozzuk meg az eredeti szöveget!

8. Faktorizáció

Ebben a fejezetben leírjuk a legfontosabb faktorizáló algoritmusokat, ahol feltesszük, hogy $ n \in\mathbb{N}$ összetett. Ezt nyilvánvalóan a Fermat vagy a Miller-Rabin prímtesztekkel megállapíthatjuk.

8.1. Triviális osztás

Az $ n$ egy kis prímosztójának megkereséséhez készítsünk egy prímszám táblázatot, mely prímek egy adott $ B$ korlát alatt vannak. Ez pl. az Eratosztheneszi szitával is könnyen megtehető. Ekkor megtalálható az a maximális $ e(p)$ kitevő is, ahol még $ p^{e(p)}$ osztja az $ n$ -et. Egy ilyen tipikus korlát a $ B=10^6$ .

8.2. p-1 módszer

Vannak olyan faktorizáló algoritmusok, melyek jól működnek bizonyos összetett számok esetén. Ezeket az összetett számokat nem szabad használni RSA vagy Rabin modulusként. Az egyik ilyen a John Pollard féle $ p-1$ módszer.

A $ (p-1)$ módszer a legjobban működik olyan $ p$ prímfaktorral rendelkező összetett számok esetén, amikor a $ p-1$ csak kis prímosztókkal rendelkezik. Ekkor lehetséges meghatározni a $ p-1$ egy $ k$ többszörösét anélkül, hogy ismernénk a $ p-1$ prím(hatvány)tényezős alakját.

A kis-Fermat tételből adódik, hogy

$\displaystyle a^k\equiv 1\mod p
$

minden olyan $ a$ -ra, amely nem osztja a $ p$ -t.

Azaz ez azt jelenti, hogy a $ p$ osztja az $ a^k-1$ -et. Ha az $ a^k-1$ nem osztható $ n$ -nel, akkor lnko$ (a^k-1,n)$ egy valódi osztója az $ n$ -nek, azaz egy faktorát találtuk meg $ n$ -nek.

A $ p-1$ módszer felhasználja az összes prímhatványt egy adott $ B$ korlát alatt, nevezetesen legyen

$\displaystyle k=\prod_{q\in \mathbb{P},\ q^e\leq B} q^e.
$

Ha a prímhatványok, melyek osztják a $ p-1$ -et kisebbek mint $ B$ , akkor $ k$ egy többszöröse $ p-1$ -nek. Az algoritmus kiszámolja a $ g=(a^k-1,n)$ értéket egy megfelelő $ a$ bázisra nézve. Ha nem találunk osztót, akkor egy új $ B$ korlátot választunk.

Példa:
Legyen az összetett szám az $ n=1241143$ . Használjuk a $ B=13$ korlátot. Ekkor $ k=8\cdot 9\cdot 5\cdot 7\cdot 11\cdot 13$ és

$\displaystyle (2^k-1,n)=547.
$

Így $ p=547$ egy osztója az $ n$ -nek. A másik faktor a $ q=2269$ . Mind a két szám prím.

8.3. Kvadratikus szita

Az egyik leghatékonyabb faktorizáló algoritmus.

8.3.1. Alapötlet

Próbáljunk meg faktorizálni egy páratlan, pozitív egész számot. Ez elegendő az RSA feltöréséhez, hiszen a modulus két nagy prím szorzata. Általában rekurzívan használva a kvadratikus szitát az $ n$ összes faktora megtalálható.

A kvadratikus szita meghatározza azon $ x$ és $ y$ számokat, melyekre az

$\displaystyle x^2\equiv y^2\mod n
$

és az

$\displaystyle x\not\equiv \pm y\mod n
$

teljesülnek.

Ekkor $ n$ egy osztója az $ x^2-y^2=(x-y)(x+y)$ -nak, de nem osztója az $ x-y$ -nak vagy a $ x+y$ -nak. Így $ g=(x-y,n)$ egy valódi osztója az $ n$ -nek.

Példa:
Legyen $ n=7429$ , $ x=227$ , $ y=210$ . Ekkor $ x^2-y^2=n$ , $ x-y=17$ , $ x+y=437$ . Így lnko$ (x-y,n)=17$ , amely egy valódi osztója az $ n$ -nek.

8.3.2. x és y meghatározása

A korábbi ötletet számos más algoritmus is felhasználja, de másképpen határozzák meg az $ x$ és $ y$ értékeket. A kvadratikus szita esetén a következő módon történik.

Legyen

$\displaystyle m=\lfloor\sqrt n\rfloor
$

és

$\displaystyle f(X)=(X+m)^2-n.
$

Az eljárást először egy példán keresztül mutatjuk be.

Példa:
Legyen ismét $ n=7429$ . Ekkor $ m=86$ and $ f(X)=(X+86)^2-7429$ . Ekkor azt kapjuk, hogy

$\displaystyle f(-3)$ $\displaystyle =83^2-7429=-540=-1\cdot 2^2\cdot 3^3\cdot 5,$    
$\displaystyle f(1)$ $\displaystyle =87^2-7429=140=2^2\cdot 5\cdot 7,$    
$\displaystyle f(2)$ $\displaystyle =88^2-7429=315=3^2\cdot 5\cdot 7.$    

Ebből adódik, hogy

$\displaystyle 83^2$ $\displaystyle \equiv -1\cdot 2^2\cdot 3^3\cdot 5\mod 7429,$    
$\displaystyle 87^2$ $\displaystyle \equiv 2^2\cdot 5\cdot 7\mod 7429,$    
$\displaystyle 88^2$ $\displaystyle \equiv 3^2\cdot 5\cdot 7\mod 7429.$    

Ha a két utolsó kongruenciát öszeszorozzuk, akkor kapjuk a

$\displaystyle (87\cdot 88)^2\equiv (2\cdot 3\cdot 5\cdot 7)^2\mod n.
$

Ezáltal kaptuk meg az

$\displaystyle x=87\cdot 88\mod n=227,\quad y=2\cdot 3\cdot 5\cdot 7\mod n=210
$

értékeket.

A példában olyan $ s$ értékeket adtunk meg, hogy az $ f(s)$ csak kis prímfaktorokkal rendelkezett. Aztán használtuk az

$\displaystyle (s+m)^2\equiv f(s)\mod n
$

kongruenciákat. Ezekből a konguenciákból kiválasztottuk az olyanokat, melyek szorzatai négyzetszámokat eredményeztek a bal és jobb oldalon egyaránt.

A bal oldal mindig négyzetszám és ráadásul tudjuk a jobb oldalak prímfaktorizációját. Nyilván akkor lesz a jobb oldal négyzetszám, ha a $ -1$ -nek és az összes prímnek a kitevője páros. A következő részben megnézzük, hogy miképpen válasszuk ki a megfelelő kongruenciákat.

8.3.3. A kongruenciák kiválasztása

Ha $ n$ nagy, akkor nagyon sok prímfaktor és kongruencia jöhet szóba. A kiválasztáshoz lineáris algebrai eszközöket használunk.

Példa:
Három kongruenciából kell választanunk. A cél olyan kongruenciák kiválasztása, hogy a jobb oldalak szorzata négyzetszám legyen. A kiválasztást a $ \lambda_i\in\{0,1\}$ , $ 1 \leq i \leq 3$ együtthatókkal vezéreljük. Ha $ \lambda_i=1$ , akkor az $ i$ kongruenciát kiválasztottuk, egyébként nem.

A kiválasztott kongruenciák jobb oldalainak szorzata a

$\displaystyle (-1\cdot 2^2\cdot 3^3\cdot 5)^{\lambda_1}\cdot (2^2\cdot 5\cdot 7)^{\lambda_2} \cdot (3^2\cdot 5\cdot 7)^{\lambda_3}=$    
$\displaystyle (-1)^{\lambda_1}\cdot 2^{2\lambda_1+2\lambda_2}\cdot 3^{3\lambda_1+2\lambda_3}\cdot 5^{\lambda_1+\lambda_2+\lambda_3}\cdot 7^{\lambda_2+\lambda_3}.$    

Ennek kell négyzetszámnak lennie. Nyilvánvalóan a kitevőknek párosnak kell lennie, azaz a következő lineáris rendszert kapjuk:

$\displaystyle \lambda_1$ $\displaystyle \equiv 0\mod 2$    
$\displaystyle 2\lambda_1+2\lambda_2$ $\displaystyle \equiv 0\mod 2$    
$\displaystyle 3\lambda_1+2\lambda_3$ $\displaystyle \equiv 0\mod 2$    
$\displaystyle \lambda_1+\lambda_2+\lambda_3$ $\displaystyle \equiv 0\mod 2$    
$\displaystyle \lambda_2+\lambda_3$ $\displaystyle \equiv 0\mod 2.$    

Ebből a lineárisan függő sorokat elhagyva kapjuk a következőt:

$\displaystyle \lambda_1$ $\displaystyle \equiv 0\mod 2$    
$\displaystyle \lambda_1+\lambda_2+\lambda_3$ $\displaystyle \equiv 0\mod 2$    
$\displaystyle \lambda_2+\lambda_3$ $\displaystyle \equiv 0\mod 2.$    

A megoldás

$\displaystyle \lambda_1=0, \quad \lambda_2=\lambda_3=1.
$

Azaz a második és a harmadik kongruencia szorzata lesz a megfelelő.

Most vázlatosan bemutatjuk, hogy általánosságban a kvadratikus szita hogyan választja ki a megfelelő kongruenciákat. Válasszuk egy pozitív egész $ B$ számot.

Ekkor keressünk olyan $ s$ egészeket, hogy az $ f(s)$ csak olyan prímfaktorokkal rendelkezzen, amely az

$\displaystyle F(B)=\{p\in\mathbb{P}:p\leq B\}\cup {-1}
$

faktorbázishoz tartozik. Az ilyen $ f(s)$ értékeket $ B$ -simának nevezzük. A következő táblázat tartalmazza, hogy milyen módon alakulnak a faktor bázis méretek.

Táblázat: A faktorbázis mérete és a szitálási intervallum.

Az $ n$ decimális számjegyeinek száma 50 60 70 80 90 100 110 120
A faktorbázis * 1000 3 4 7 15 30 51 120 245
A szitálási intevallum (millió) 0,2 2 5 6 8 14 16 26

Ha találunk annyi $ s$ -et, mint amennyi a faktorbázis elemeinek a száma, akkor megpróbálhatjuk megoldani a megfelelő lineáris rendszert. Mivel a rendszer a $ \mathbb{Z}/2\mathbb{Z}$ test felett van, ezért a Gauss algoritmus működik. Viszont nagy $ n$ -ek esetén már más módszert kell használni.

8.3.4. Szitálás

Már csak az maradt, hogy megmutassuk miképpen találjuk meg azon $ s$ értékeket, melyekre az $ f(s)$ érték $ B$ -sima.

Egyik lehetőség, hogy kiszámoljuk az $ f(s)$ értékeket az $ s=0,\pm 1,\pm 2,\pm 3,\ldots$ esetekre és teszteljük a triviális osztással, hogy melyik $ f(s)$ érték $ B$ -sima. Sajnos ezek az értékek tipikusan nem $ B$ -simák. Ennek a detektálásához minden egyes faktorbázisbeli elemnél triviális osztás kellene, amely nagyon nem hatékony, mivel a faktorbázis nagy, ha $ n$ nagy. Egy hatékonyabb módszer, ha szitálási technikákat használunk, melyek a következők.

Egy egyszerű eseten keresztül magyarázzuk el a fő gondolatot. Lerögzítünk egy szitálási intervallumot

$\displaystyle S=(-C,-C+1,\ldots,0,1,\ldots,C).
$

Meg akarjuk határozni mindazon $ s\in S$ -ket, melyekre $ f(s)$ $ B$ -sima. Először kiszámoljuk az $ f(s)$ értékeket minden $ s\in S$ -re. Minden egyes $ p$ faktorbázisbeli prím esetén elosztjuk az $ f(s)$ értékeket a legnagyobb $ p$ hatvánnyal. A $ B$ -sima $ f(s)$ értékek pontosan azok lesznek, melyekre az 1 vagy -1 marad.

Hogy megkapjuk melyik $ f(s)=(s+m)^2-n$ érték osztható egy $ p$ prímmel a faktorbázisból, először határozzuk meg az összes olyan $ s\in\{0,1,\ldots,p-1\}$ értéket, melyre az $ f(s)$ osztható $ p$ -vel. Nem nehéz belátni, hogy az $ f(X)$ polinomnak legfeljebb két zérushelye van modulo $ p$ . Kis prímérték esetén próbálgatással találjuk meg, nagyobb érték esetén más módszert kell használni.

Tegyük fel, hogy ismerjük az $ f(X)$ zérusait modulo egy $ p$ prím a $ \{0,1,\ldots,p-1\}$ -ben (ezek éppen azok, melyekre az $ f(s)$ osztható $ p$ -vel).

Azon további $ s$ értékeket, melyekre $ f(s)$ osztható $ p$ -vel megkaphatjuk, ha a zérushelyekhez hozzáadjuk a $ p$ többszöröseit. Voltaképpen a zérushelyről kiindulva lépegetünk $ p$ -vel mindkét irányban a szitálási intervallumban. Minden egyes lépésben osztjuk az aktuális $ f(s)$ értéket $ p$ -vel. Ezt hívjuk $ p$ -vel való szitálásnak. Így elkerüljük a felesleges és sikertelen osztásokat $ p$ -vel a triviális osztással szemben. A prímhatványokat hasonlóan kapjuk meg.

Példa:
Legyen $ n=7429$ , $ m=86$ és $ f(X)=(X+86)^2-7429$ . A faktorbázis a $ \{2,3,5,7\}\cup \{-1\}$ . Mint szitálási intervallumot használjuk a $ \{-3,-2,\ldots,3\}$ halmazt. A szitát mutatja a következő táblázat:

Táblázat: A szita

$ s$ $ -3$ $ -2$ $ -1$ 0 1 2 3
$ (s+m)^2-n$ $ -540$ $ -373$ $ -204$ $ -33$ 140 315 492
Szitálás 2-vel $ -135$   $ -51$   35   123
Szitálás 3-mal $ -5$   $ -17$ $ -11$   35 41
Szitálás 5-tel $ -1$       7 7  
Szitálás 7-tel         1 1  

Feladatok (faktorizáció)

  1. Fermat faktorizált egy egész $ n$ számot, melyet az $ n=x^2-y^2=(x-y)\cdot(x+y)$ alakban adott meg. Faktorizáljuk az $ n=13199$ számot ezzel a módszerrel. Ez vajon egy általános módszer, hogy faktorizáljuk az összes összetett számot? Mi a futási ideje ennek az algoritmusnak?

  2. Faktorizáljuk a 831802500 számot a triviális osztással!

  3. Használjuk a $ p-1$ módszert, hogy faktorizáljuk az $ n=138277151$ !

  4. Faktorizáljuk az 11111-et a kvadratikus szitával!

  5. Használjuk a $ p-1$ módszert, hogy faktorizáljuk az $ n=18533588383$ !

9. Diszkrét logaritmus

Ebben a fejezetben a diszkrét logaritmus probléma (DL problem) bonyolultságával foglalkozunk. Több nyilvános kulcsú kriptorendszer biztonsága ezen probléma bonyolultságán alapul.

9.1. DL probléma

Ebben a fejezetben $ G$ egy $ n$ -edrendű ciklikus csoport, $ \gamma$ a csoport generátora és $ 1$ a neutrális elem a $ G$ csoportban. Feltételezzük, hogy az $ n$ ismert és legyen $ \alpha$ a csoport egy eleme. A cél, hogy megtaláljuk a legkisebb nemnegatív $ x$ egészt, melyre

$\displaystyle \alpha=\gamma^x.
$

Ezt nevezzük az $ \alpha$ elem $ \gamma$ alapú diszkrét logaritmusának. Amikor a DL problémáról beszélünk, akkor arra gondolunk, hogy miképpen találjuk meg az $ x$ -et. A kriptográfiai alkalmazásokban ez garantált, így a támadónak csak egy problémája van, hogy megtalálja az $ x$ -et.

9.2. Leszámlálás

A legegyszerűbb módszer, hogy meghatározzuk az $ x$ diszkrét logaritmust a tesztelés. Azaz megnézzük, hogy az $ x=0,1,\ldots$ közül mely érték esetén áll fenn az összefüggés. Amint ezt megtaláljuk, akkor megvan a diszkrét logaritmus is. Ezt hívjuk leszámlálásnak. A leszámlálás $ x-1$ szorzást és $ x$ összehasonlítást igényel $ G$ -ben. Csak az $ \alpha$ , a $ \gamma$ és a $ \gamma^k$ elemeket kell tárolni. Azaz csak három csoportbeli elemet kell tárolni a leszámlálás során.

Példa:
Meghatározzuk a 3 diszkrét logaritmusát az 5 alapra vonatkozólag a $ (\mathbb{Z}/2017\mathbb{Z})^*$ csoportban. A leszámlálás az $ x=1030$ eredményt hozta, melyhez 1029 szorzást kellett elvégezni modulo 2017.

A kriptográfiai alkalmazásokban azt kapjuk, hogy $ x\geq 2^{160}$ . Ezért a leszámlálás végigvihetetlen, mert legalább $ 2^{160}-1$ csoportbeli művelet szükséges.

9.3. A Shanks-féle Apró-Lépés Óriás-Lépés algoritmus

A leszámlálási algoritmus következő fejlődési lépése a D. Shanks által megadott Apró-Lépés Óriás-Lépés algoritmus (Baby-Step Giant-Step algorithm). Az algoritmus kevesebb csoportbeli műveletet igényel, de több tárolást.

Legyen

$\displaystyle m=\lceil\sqrt{n}\rceil
$

és írjuk fel az ismeretlen $ x$ diszkrét logaritmust az

$\displaystyle x=qm+r, \quad 0\leq r< m
$

alakban. Az Apró-Lépés Óriás-Lépés algoritmus kiszámolja a $ q$ -t és az $ r$ -et. Ez a következőképpen működik. A fentiek alapján kapjuk, hogy

$\displaystyle \gamma^{qm+r}=\gamma^x=\alpha.
$

Ebből következik, hogy

$\displaystyle (\gamma^m)^q=\alpha\gamma^{-r}.
$

Először kiszámoljuk az Apró-Lépések

$\displaystyle B=\left\{(\alpha\gamma^{-r},r): 0\leq r< m \right\}
$

halmazát. Ha ebben a halmazban megtalálunk egy $ (1,r)$ párt, akkor $ \alpha\gamma^{-r}=1$ , azaz $ \alpha=\gamma^r$ . Így beállíthatjuk az $ x=r$ -t, mint a legkisebb lehetséges $ x$ . Ha nem találunk ilyen párt, akkor meghatározzuk a

$\displaystyle \delta=\gamma^m
$

értéket. Ezután teszteljük a $ q=1,2,\ldots$ értékeket, hogy találunk-e $ \delta^q$ csoportbeli elemet, amely első komponensként előfordul a $ B$ -ben (azaz van-e $ (\delta^q,r)$ pár a $ B$ -ben). Amint találunk ilyet, akkor

$\displaystyle \alpha\gamma^{-r}=\delta^q=\gamma^{qm},
$

amely implikálja a

$\displaystyle \alpha=\gamma^{qm+r}
$

összefüggést. Így a diszkrét logaritmus a

$\displaystyle x=qm+r
$

lesz. A $ \delta^q$ , $ q=1,2\ldots$ elemeket hívjuk Óriás-Lépéseknek. Össze kell hasonlítanunk minden egyes $ \delta^q$ elemet az Apró-Lépések $ B$ halmazában lévő összes rendezett pár első komponensével. Azért, hogy ez hatékonyan működjön a $ B$ elemeit egy hash táblában tároljuk, ahol kulcs az első komponens.

Példa:
Meghatározzuk a 3 diszkrét logaritmusát az 5 alapra nézve a $ (\mathbb{Z}/2017\mathbb{Z})^*$ csoportban. A $ \gamma=5+2017\mathbb{Z}$ , $ \alpha=3+2017\mathbb{Z}$ , $ m=\lceil\sqrt{2017}\rceil=45$ . Az Apró-Lépések halmaza a

$\displaystyle B=\left\{(3,0);(404,1);(1291,2);(1065,3);(213,4);(446,5);(896,6);(986,7);(1004,8);\right.$    
$\displaystyle (1411,9);(1089,10);(1428,11);(689,12);(1348,13);(673,14);(538,15);(511,16);$    
$\displaystyle (909,17);(1392,18);(1892,19);(1992,20);(2012,21);(2016,22);(1210,23);(242,24);$    
$\displaystyle (1662,25);(1946,26);(1196,27);(1046,28);(1016,29);(1010,30);(202,31);(1654,32);$    
$\displaystyle (1541,33);(1115,34);(223,35);(448,36);(493,37);(502,38);(1714,39);(1553,40);$    
$\displaystyle \left.(714,41);(1353,42);(674,43);(1345,44)\right\}$    

Ezután kiszámoljuk a $ \delta=\gamma^m=45+2017\mathbb{Z}$ elemet. Az Óriás-Lépések a következő értékek:

$\displaystyle 45,8,360,64,863,512,853,62,773,496,133,1951$    
$\displaystyle 1064,1489,444,1827,1535,497,178,1959,1424,1553.$    

Megtalálható a $ (1553,40)$ pár az Apró-Lépések halmazában. Így $ \alpha\gamma^{-40}=1553+2017\mathbb{Z}$ . Mivel az 1553 a 22-dik Óriás-Lépés, ezért

$\displaystyle \gamma^{22\cdot 45}=\alpha\gamma^{-40}.
$

Emiatt

$\displaystyle \gamma^{22\cdot 45+40}=\alpha.
$

A megoldása a DL problémának az $ x=22\cdot 45+40=1030$ . Az Apró-Lépések halmazának meghatározásához 45 szorzás kellett modulo 2017, az Óriás-Lépésekhez 21. A leszámlálás sokkal több szorzást igényelt, nevezetesen 1029-et. Másrészről viszont az Apró-Lépések halmazának tárolásához 45 hely kellett, miközben a leszámlálásnál csupán három.

Ha hash táblát használunk, hogy megtaláljuk a megfelelő Óriás-Lépést, mint az Apró-Lépések halmazának első komponnesét, akkor konstans számú összehasonlítás szükséges. Ebbő adódik a következő állítás.

Tétel:
Az Apró-Lépés Óriás-Lépés algoritmus $ O(\sqrt{|G|})$ szorzást és összehasonlítást igényel a $ G$ -ben. Továbbá tárolni kell $ O(\sqrt{|G|})$ elemet $ G$ -ből.

A tétel alapján az idő- és a tárigény közelítőleg $ \sqrt{|G|}$ az Apró-Lépés Óriás-Lépés algoritmus esetén. Ha $ |G|>2^{160}$ , akkor az algoritmussal történő diszkrét logaritmus kiszámítása elérhetetlen.

9.4. Pollard-féle algoritmus

Ez az algoritmus hasonló lépésszámmal működik, mint a korábbi Apró-Lépés Óriás-Lépés algoritmus (nevezetesen $ O(\sqrt{|G|})$ ), de csak konstans mennyiségű tárolást igényel.

Továbbra is a DL problémát szeretnénk megoldani. Ehhez szükségünk van három páronként diszjunkt részhalmazra a $ G$ -ből, legyenek ezek $ G_1$ , $ G_2$ , $ G_3$ , melyekre teljesül, hogy $ G_1\cup G_2\cup G_3=G$ . Legyen $ f\colon G\to G$ a következőképpen megadva:

$\displaystyle f(\beta)=\left\{\begin{array}{ll}
\gamma\beta, & \mbox{ha } \beta\in G_1,\\
\beta^2, & \mbox{ha } \beta\in G_2,\\
\alpha\beta, & \mbox{ha } \beta\in G_3.
\end{array}\right.
$

Választunk egy véletlen $ x_0$ számot a $ \{1,\ldots,n\}$ halmazból és kiszámoljuk a $ \beta_0=\gamma^{x_0}$ csoportbeli elemet. Ezután kiszámoljuk a $ (\beta_i)$ sorozatot a következő rekurzióval:

$\displaystyle \beta_{i+1}=f(\beta_i).
$

Ezen sorozat elemeit úgy is írhatjuk, hogy

$\displaystyle \beta_i=\gamma^{x_i}\alpha^{y_i},\ i\geq 0.
$

Ebben az esetben az $ x_0$ egy inicilizációs véletlen szám, $ y_0=0$ , azaz a következőket kapjuk:

$\displaystyle x_{i+1}=\left\{\begin{array}{ll}
x_{i}+1 \mod n, & \mbox{ha } \beta_i\in G_1,\\
2x_{i} \mod n, & \mbox{ha } \beta_i\in G_2,\\
x_{i}, & \mbox{ha } \beta_i\in G_3,
\end{array}\right.
$

és

$\displaystyle y_{i+1}=\left\{\begin{array}{ll}
y_{i}, & \mbox{ha } \beta_i\in G_1,\\
2y_{i} \mod n, & \mbox{ha } \beta_i\in G_2,\\
y_{i}+1 \mod n, & \mbox{ha } \beta_i\in G_3.
\end{array}\right.
$

Mivel véges csoportban dolgozunk, ezért két elemnek a $ (\beta_i)$ sorozatban egyenlőnek kell lennie, azaz van olyan $ i\geq 0$ és $ k\geq 1$ , melyre $ \beta_{i+k}=\beta_i$ . Ez implikálja, hogy

$\displaystyle \gamma^{x_i}\alpha^{y_i}=\gamma^{x_{i+k}}\alpha^{y_{i+k}}
$

és ezért

$\displaystyle \gamma^{x_i-x_{i+k}}=\alpha^{y_{i+k}-y_i}.
$

Így az $ x$ -re, mely az $ \alpha$ diszkrét logaritmusa a $ \gamma$ alapra nézve teljesül, hogy

$\displaystyle (x_i-x_{i+k})\equiv x(y_{i+k}-y_i)\mod n.
$

Megoldjuk ezt a kongruenciát. A megoldás egyértelmű modulo $ n$ ha $ y_{i+k}-y_i$ invertálható modulo $ n$ . Ha a megoldás nem egyértelmű, akkor a diszkrét logaritmus megkereshető a különböző lehetséges esetek tesztelésével modulo $ n$ . Ha túl sok lehetőség van, akkor megismételjük az algoritmust egy különböző inicializációs $ x_0$ -lal.

Az algoritmusnak tárolnia kell az összes $ (\beta_i,x_i,y_i)$ hármast. Ezeknek a száma ismét $ \sqrt{|G|}$ -vel adható meg, mint a korábbi Apró-Lépés Óriás-Lépés algoritmusban. De megmutatható, hogy mindig csak egy hármas tárolására van szükség. Így a Pollard-féle algoritmus sokkal kevesebb tárigényű, mint a korábbiak.

Kezdetben ugyanis a $ (\beta_0,x_0,y_0)$ -at kell tárolni. Tegyük fel, hogy egy ponton az algoritmusban a $ (\beta_i,x_i,y_i)$ tárolva van. Ekkor $ (\beta_j,x_j,y_j)$ kiszámolható a $ j=i+1,i+2,\ldots$ -ból amíg nincs egyezés vagy $ j=2i$ . Az utóbbi esetben $ \beta_i$ -t töröljük és $ \beta_{2i}$ -t tároljuk tovább.Így csak azon $ (\beta_i,x_i,y_i)$ hármasokat kell tárolni, melyekre $ i=2^k$ . Megmutatható, hogy az első eset is működik, azaz van egyezés (további részletekért lásd még a [1]-t).

Példa:
A Pollard-féle $ \rho$ -algoritmussal oldjuk meg az

$\displaystyle 5^x\equiv 3 \mod 2017
$

diszkrét logaritmus problémát.

Az összes maradék osztályt a legkisebb nemnegatív reprezentánsával adunk meg. Legyen

$\displaystyle G_1=\{1,\ldots,672\},\ G_2=\{673,\ldots,1344\},\ G_3=\{1345,\ldots,2016\},
$

és $ x_0=1023$ . A következő táblázat mutatja a tárolt hármasokat és a végső hármast, amelyik ismétlődik és egyben segít nekünk meghatározni a diszkrét logaritmust.
j $ \beta_i$ $ x_j$ $ y_j$
0 986 1023 0
1 2 30 0
2 10 31 0
4 250 33 0
8 1366 136 1
16 1490 277 8
32 613 447 155
64 1476 1766 1000
98 1476 966 1128
Láthatjuk, hogy

$\displaystyle 5^{800}\equiv 3^{128}\mod 2017.
$

Az $ x$ meghatározásához meg kell oldanunk a

$\displaystyle 128x\equiv 800 \mod 2016
$

kongruenciát. Mivel lnko$ (128,2016)=32$ osztja a 800-at, így a kongruenciának van egyértelmű megoldása modulo 63. Azaz meg kell oldanunk a

$\displaystyle 4z\equiv 25 \mod 63
$

kongruenciát. Ennek a $ z=22$ a megoldása. Így az $ x$ diszkrét logaritmus az egyike az $ x=22+k\cdot 63$ , $ 0\leq k< 32$ értékeknek. A $ k=16$ esetben kapjuk meg az $ x=1030$ diszkrét logaritmust.

Feladatok (diszkrét logaritmus)

  1. Oldjuk meg a $ 3^x\equiv 693 \mod 1823$ DL problémát az Apró-Lépés Óriás-Lépés algoritmussal.

  2. Használjuk az Apró-Lépés Óriás-Lépés algoritmust, hogy meghatározzuk a 15 diszkrét logaritmusát a 2-es alapra nézve modulo 239!

  3. Oldjuk meg a $ g^x\equiv 507\mod 1117$ DL problémát a legkisebb primitív $ g$ gyökkel modulo 1117 a Pollard-féle $ \rho$ -algoritmussal!

  4. Használjuk a Pollard-féle $ \rho$ -algoritmust, hogy meghatározzuk a 2 diszkrét logaritmusát a 3-as alpra nézve modulo 65537!

  5. Oldjuk meg a $ g^x\equiv 15\mod 3167$ DL problémát a legkisebb primitív $ g$ gyökkel modulo 3167 a Pollard-féle $ \rho$ -algoritmussal!

10. Hash függvények

Ebben a fejezetben a hash függvényeket tárgyaljuk. A mi esetünkben pl. a digitális aláírásnál használjuk fel őket. A továbbiakban feltételezzük, hogy $ \Sigma$ egy ábc.

10.1. Hash és tömörítési függvények

Definíció:
Egy hash függvény alatt a következő

$\displaystyle h\colon \Sigma^*\to \Sigma^n,\ n\in\mathbb{N}
$

leképezést értjük. Így egy hash függvény tetszőleges hosszúságú bitsztringet leképez egy rögzített hosszúságú bitsztringre. A hash függvények sohasem injektívek.

Példa:
Az a leképezés, amely a $ b_1b_2\ldots b_k$ bitsztringet a $ \{0,1\}^*$ -ból a $ b_1\oplus b_2\oplus \ldots \oplus b_k$ -t állítja elő hash függvény. Például a 01101 képe 1. Általánosan egy $ b$ sztring képe 1, ha az egyesek száma páratlan $ b$ -ben, egyébként 0.

A hash függvények tömörítő függvényekből generálhatóak.

Definíció:
Egy tömörítő függvény

$\displaystyle h\colon \Sigma^m\to \Sigma^n,\ n,m\in\mathbb{N}, \ m> n
$

leképezés, mely rögzített hosszúságú sztringből állít elő rövidebb sztringet.

Példa:
Az a leképezés, amely a $ b_1b_2\ldots b_m\in\{0,1\}^m$ szóhoz a $ b_1\oplus b_2\oplus \ldots \oplus b_m$ -t rendeli tömörítő függvény, ha $ m>1$ .

A hash és a tömörítő függvények számos kontextusban használatosak. A kriptográfiában is fontos szerepet játszanak. A kriptográfiai hash és tömörítő függvényeknek olyan tulajdonságokkal kell rendelkezniük, melyek garantálják biztonságukat. A következőkben leírjuk ezeket a tulajdonságokat formálisan.

Legyen $ h\colon \Sigma^*\to\Sigma^n$ egy hash függvény vagy $ h\colon \Sigma^m\to\Sigma^n$ egy tömörítő függvény. Jelöljük a $ \Sigma^*$ vagy $ \Sigma^m$ argumentumokat $ h$ -ban $ D$ -vel.

Ha $ h$ -t a kriptográfiában használjuk, akkor $ h(x)$ kiszámolásának könnyűnek kell lennie minden $ x\in D$ esetén. A továbbiakban ezt végig feltételezzük.

Definíció:
Egy $ h$ függvényt egyirányú függvénynek nevezünk, ha elérhetetlen $ h$ -t invertálni.

Mit jelent az ,,elérhetetlen'' kifejezés? Elég komplikált leírni ezt precíz matematikai módon. Hogy ezt megtegyük, szükségünk lenne a bonyolultságelmélet nyelvezetére, amelyet viszont eddig is háttérbe szorítottunk. Ezért, hogy mégis fogalmunk legyen róla megadunk egy intuitív definíciót.

Bármely algoritmus, amely egy $ s\in\Sigma^n$ bemenet esetén megpróbálja meghatározni azon $ x$ -et, melyre $ h(x)=s$ majdnem mindig elbukik, mert túl sok időt vagy tárt használ ehhez. Nem ismert, hogy léteznek-e egyirányú függvények. Viszont léteznek olyan függvények, melyeket könnyű kiszámolni, de nem ismerünk invertáló algoritmust hozzájuk. Ezeket emiatt egyirányú függvényként használjuk.

Példa:
Ha $ p$ véletlenszerűen választott 1024 bites prím és a $ g$ egy primitív gyök modulo $ p$ , akkor az $ f\colon \{0,2,\ldots, p-2\}\to \{1,2,\ldots,p-1\}$ , $ x\to g^x\mod p$ könnyen számolható, de hatékony invertáló függvény nem ismert, mivel a diszkrét logaritmust nehéz meghatározni. Ezért $ f$ egyirányú függvényként használható.

Definíció:
A $ h$ egy ütközése egy $ (x,x')\in D^2$ pár, melyre $ x\neq x'$ és $ h(x)=h(x')$ .

Minden hash és tömörítő függvénynek vannak ütközései, mivel ezek nem injektívek.

Definíció:
Egy $ h$ függvényt gyengén ütközésmentesnek nevezünk, ha elérhetetlen kiszámolni egy $ (x,x')$ ütközését adott $ x\in D$ esetén.

Az alábbi példa mutatja, hogy hol van szükség ilyen típusú függvényekre.

Példa:
Alice szeretné védeni egy $ x$ kódoló algoritmusát a saját merevlemezén az illetéktelen változtatásoktól. Egy $ h\colon \Sigma^*\to\Sigma^n$ hash függvényt használ, hogy kiszámolja az $ x$ program $ y=h(x)$ hash értékét és ezen $ y$ hash értéket letárolja a saját intelligens kártyájára. Munka után Alice hazamegy és magával viszi a kártyát. A következő reggelen Alice bemegy az irodába. Mielőtt ismét használná a kódoló programot ellenőrzi, hogy változott-e, azaz a hash érték ugyanaz-e, mint a kártyán.

Ez a teszt akkor biztonságos, ha a $ h$ hash függvény gyengén ütközésmentes. Ha nem lenne az, akkor egy ellenség kiszámolhatna egy másik $ h(x)$ hash értékű $ x'$ ősképet és módosíthatná az $ x$ programot $ x'$ -re anélkül, hogy Alice észrevenné.

Az előző példa is mutatja a tipikus felhasználását a gyengén ütközésmentes hash függvényeknek.

Definíció:
Egy $ h$ függvényt (erősen) ütközésmentesnek nevezünk, ha elérhetetlen kiszámolni bármely $ (x,x')$ ütközését a $ h$ -nak.

Számos alkalmazásban van szükség ilyen típusú függvényekre, pl. digitális aláírásoknál (lásd a következő fejezetet). Megmutatható, hogy az ütközésmentes hash függvények egyirányúak.

10.2. A születésnap támadás

Ebben a fejezetben leírunk egy egyszerű támadást a hash függvényeken, melyet születésnap támadásnak vagy születésnap problémának is nevezünk. Az erősen ütközésmentes függvényeket támadja. A támadás a születésnap paradoxonon alapul.

A születésnap támadásban kiszámolunk annyi hash értéket, amennyit csak az időnk és a tárunk megenged. Ezek az értékek együtt kerülnek tárolásra az inverz képükkel. Ezután ütközést keresünk. A hash értékek születésnapoknak felelnek meg. Feltételezzük, hogy a sztringek a $ \Sigma^*$ -ból úgy kerültek kiválasztásra, hogy az eloszlás a megfelelő hash értékeken egy egyenletes eloszlás. Tudjuk még a következőket is:

Ha $ k$ db sztring kerül kiválasztásra az $ x\in\Sigma^*$ -ból, ahol

$\displaystyle k\geq (1+\sqrt{1+(8\ln 2)|\Sigma^n|})/2,
$

akkor annak a valószínűsége, hogy két hash érték megegyezik túllépi az 1/2-et. Egyszerűbben, feltételezzük, hogy $ \Sigma = \{0, 1\}$ . Ekkor a

$\displaystyle k\geq f(n)=(1+\sqrt{1+(8\ln 2)2^n})/2
$

feltétel elegendő. A következő táblázat mutatja a $ \log_2(f(n))$ értékeket az $ n$ tipikus méreteire.

$ n$ 50 100 150 200
$ \log_2(f(n))$ 25,24 50,24 75,24 100,24

Így ha kiszámolunk kicsivel több, mint $ 2^{n/2}$ db hash értéket, akkor a születésnap támadás megtalál egy ütközést nagyobb valószínűséggel, mint 1/2. A születésnap támadás elkerülése érdekében $ n$ -et úgy kell kiválasztani, hogy a $ 2^{n/2}$ db hash érték kiszámítása elérhetetlen legyen. Napjainkban $ n\geq 128$ vagy még az $ n\geq 160$ feltétel is szükséges.

10.3. Tömörítő függvények a kódoló függvényekből

Nem ismert, hogy létezik-e ütközésmentes hash függvény, mint ahogy az sem, hogy létezik-e biztonságos és hatékony kódolási séma. Lehet azonban egy kódoló függvényből konstruálni hash függvényt, mely addig lesz ütközésmentes, amíg a kódoló séma biztonságos. A következőkben ezt írjuk le.

Tekintsünk egy olyan kriptorendszert, amelynek nyílt-, rejtett szövegtere és kulcstere is a $ \{0,1\}^n$ halmaz. A kódoló függvényt az

$\displaystyle e_k\colon \{0,1\}^n\to\{0,1\}^n,\ k\in\{0,1\}^n
$

módon adjuk meg. A hash értékek hossza $ n$ . A születésnap támadás elkerülése érdekében legyen $ n\geq 128$ . Ezért a DES nem használható.

A

$\displaystyle h\colon \{0,1\}^n\times \{0,1\}^n\to\{0,1\}^n
$

hash függvényt a következő módokon adjuk meg:

$\displaystyle h(k,x)=e_k(x)\oplus x,$    
$\displaystyle h(k,x)=e_k(x)\oplus x\oplus k,$    
$\displaystyle h(k,x)=e_k(x\oplus k)\oplus x,$    
$\displaystyle h(k,x)=e_k(x\oplus k)\oplus x\oplus k.$    

Amíg a kriptorendszer biztonságos, addig ezek a függvények is ütközésmentesnek tűnnek. Sajnos erre az állításra nem ismert bizonyítás.

10.4. Hash függvények a tömörítő függvényekből

Ütközésmentes tömörítő függvény felhasználható arra, hogy ütközésmentes hash függvényt készítsünk vele. Ezt R. Merkle mutatta meg és a következőkben mi is megadjuk az ötletét.

Legyen

$\displaystyle g\colon \{0,1\}^m\to\{0,1\}^n
$

egy tömörítő függvény és legyen

$\displaystyle r=m-n.
$

Mivel $ g$ egy tömörítő függvény, így $ r>0$ . Egy tipikus választás $ n$ -re és $ r$ -re az $ n=128$ és a $ r=512$ . A $ g$ -ből készítünk egy

$\displaystyle h\colon \{0,1\}^*\to\{0,1\}^n
$

hash függvényt. Legyen $ x\in \{0,1\}^*$ . A következőkben megadjuk a $ h(x)$ számítását abban az esetben, ha $ r>1$ . Az $ r=1$ esetet az Kedves Olvasóra bízzuk gyakorlásképpen. Hozzáteszünk minimálisan annyi 0-át $ x$ -hez, hogy az új sztring hossza osztható legyen $ r$ -rel. Ezután még hozzáteszünk $ r$ db 0-át. Ekkor meghatározzuk az eredeti $ x$ sztring hosszának bináris előállítását és hozzáteszünk annyi 0-át, hogy a hossza osztható legyen $ r-1$ -gyel. A normalizált reprezentációjú sztring elé és minden $ (r-1)j$ -dik ( $ j=1,2,\ldots,$ ) szimbólum elé szúrjunk be egy 1-est. Az eredményül kapott sztringet hozzátesszük a korábban normalizált sztringhez. A teljes sztring egy

$\displaystyle x=x_1x_2\ldots x_t,\ x_i\in\{0,1\}^r,\ 1\leq i\leq t
$

sorozatként írható fel, ahol a szavak hossza $ r$ . Megjegyezzük, hogy minden egyes szó a partícióban, amely reprezentálja az eredeti $ x$ hosszát az 1-es szimbólummal kezdődik.

Példa:
Legyen $ r=4$ , $ x=111011$ . Először átalakítjuk az $ x$ -et a 0011 1011 alakúra. Hozzáadunk $ r$ db nullát, azaz kapjuk a 0011 1011 0000 alakot. Az eredeti $ x$ hossza 6. A bináris előállítása a 6-nak 110. A további 1-esek hozzátevésével kapjuk az 1110-t. Így végül kapjuk a 0011 1011 0000 1110 sztringet.

A $ h(x)$ hash függvényt iteratívan számoljuk ki. Legyen

$\displaystyle H_0=0^n.
$

Ez a sztring $ n$ db nullából áll. Ezután meghatározzuk a következőt az alábbi módon:

$\displaystyle H_i=g(H_{i-1}\circ x_i),\ 1\leq i\leq t.
$

Végül legyen

$\displaystyle h(x)=H_t.
$

Megmutatjuk, hogy $ h$ ütközésmentes, ha $ g$ ütközésmentes, melyet úgy bizonyítunk, hogy a $ h$ egy ütközéséből meg tudjuk határozni a $ g$ egy ütközését.

Legyen $ (x,x^\prime)$ egy ütközése a $ h$ -nak. Továbbá legyen $ x_1,\ldots,x_t,x_1^\prime,\ldots,x_{t'}^\prime$ az $ x$ és az $ x^\prime$ blokk sorozata, mint korábban és legyen $ H_0,\ldots,H_t,H_0^\prime,\ldots,H_{t'}^\prime$ a megfelelő hash értékek sorozata. Tegyük fel, hogy $ t\leq t'$ . Ekkor

$\displaystyle H_t=H_{t'}^\prime
$

mivel $ (x,x')$ egy ütközése $ h$ -nak. Először tegyük fel, hogy van olyan $ i$ index ($ 0\leq i<t$ ), melyre

$\displaystyle H_{t-i}= H_{t'-i}^\prime.
$

és

$\displaystyle H_{t-i-1}\neq H_{t'-i-1}^\prime.
$

Ekkor

$\displaystyle H_{t-i-1}\circ x_{t-i}\neq H_{t'-i-1}^\prime\circ x_{t'-i}^\prime
$

és

$\displaystyle g(H_{t-i-1}\circ x_{t-i})=H_{t-i}=H_{t'-i}^\prime=g(H_{t'-i-1}^\prime\circ x_{t'-i}^\prime).
$

Ez egy ütközése a $ g$ -nek. Tegyük fel, hogy

$\displaystyle H_{t-i}=H_{t'-i}^\prime,\ 0\leq i\leq t.
$

Alább megmutatjuk, hogy van olyan $ i$ index ( $ 0\leq i\leq t-1$ ), hogy

$\displaystyle x_{t-i}\neq x_{t'-i}^\prime.
$

Ez implikálja, hogy

$\displaystyle H_{t-i-1}\circ x_{t-i}\neq H_{t'-i-1}^\prime\circ x_{t'-i}^\prime
$

és

$\displaystyle g(H_{t-i-1}\circ x_{t-i})=H_{t-i}=H_{t'-i}^\prime=g(H_{t'-i-1}^\prime\circ x_{t'-i}^\prime).
$

Így megkaptuk a $ g$ egy ütközését.

A következőkben megmutatjuk, hogy van olyan $ i$ index ( $ 0\leq i\leq t-1$ ), hogy

$\displaystyle x_{t-i}\neq x_{t'-i}^\prime.
$

Ha azon szavak száma, amelyek reprezentálják az $ x$ hosszát kisebb, mint azon szavak száma, amelyek reprezentálják az $ x^\prime$ hosszát, akkor van olyan $ i$ index úgy, hogy az $ x_{t-i}$ zérus sztring, de az $ x_{t'-i}$ nem zérus, mivel 1-gyel kezdődik.

Ha azon szavak száma, amelyek reprezentálják az $ x$ hosszát megegyezik azon szavak számával, amelyek reprezentálják az $ x^\prime$ hosszát, de az $ x$ hossza különbözik az $ x^\prime$ hosszától, akkor a hosszak reprezentációja tartalmaz egy eltérő szót ugyanazzal az indexszel.

10.5. Hatékony hash függvények

A gyakorlatban használt hash függvényeket az előző alfejezetben leírt módon állítják elő. Ezen konstrukció módosításával gyorsítják a kiértékelést. A következő táblázat technikai adatokat tartalmaz néhány, a gyakorlatban is használt hash függvényről.

Táblázat: Speciális hash függvények paraméterei

hash függvény blokk hossz relatív sebesség
MD4 128 1,00
MD5 128 0,68
RIPEMD-128 128 0,39
SHA-1 160 0,28
RIPEMD-160 160 0,24

A táblázatban levő függvények mindegyike nagyon hatékony. Az MD4 hash függvény a továbbiakban nem tekinthető ütközésmentesnek, mert $ 2^{20}$ db hash érték kiszámítása mellett már található egy ütközés. Másrészről az MD4 konstrukciójának alapelvét felhasználják az összes táblázatban levő hash függvényben. Az MD5 sem teljesen biztonságos, mert a tömörítő függvényében egy ütközést lehet találni.

10.6. Egy aritmetikai tömörítő függvény

Korábban már megjegyeztük, hogy nincs bizonyíthatóan ütközésmentes tömörítő függvény. Azonban van olyan tömörítő függvény, amelyről bizonyítani lehet, hogy ütközésmentes, ha a $ \mathbb{Z}/p\mathbb{Z}$ -ben a diszkrét logaritmus kiszámítása elérhetetlen. Ezt Chaum, van Heijst és Pfitzmann fejlesztette ki és a következőkben elmagyarázzuk a működését.

Legyen $ p$ egy prímszám, a $ q=(p-1)/2$ ugyancsak prím, $ a$ egy primitív gyök modulo $ p$ , a $ b$ egy véletlenszerűen választott szám a $ \{1,2,\ldots,p-1\}$ halmazból. Tekintsük a következő leképezést:

$\displaystyle h\colon \{0,1,\ldots,q-1\}^2\to \{1,\ldots,p-1\},\ (x_1,x_2)\to a^{x_1}b^{x_2}\mod p.
$

Ez nem egy a korábbi definíciónak megfelelő tömörítő függvény. Azonban mivel $ q=(p-1)/2$ , az $ (x_1,x_2)$ bitsztringeket képezi le, melyek teljes bináris hossza közel kétszer akkora mint a $ p$ -é olyan sztringekre, melyek bináris hossza legfeljebb $ p$ -é. Nem nehéz módosítani ezt a függvényt úgy, hogy olyan legyen mint ahogy azt a korábbi definíció szerint elvárjuk.

Példa:
Legyen $ q=11$ , $ p=23$ , $ a=5$ , $ b=4$ . Ekkor $ h(5,10)=5^4\cdot 4^{10} \mod 23=20\cdot 6\mod 23=5$ Egy ütközése a $ h$ -nak egy $ (x,x')\in \{0,1,\ldots,q-1\}^2\times \{0,1,\ldots,q-1\}^2$ pár, melyre $ x\neq x'$ és $ h(x)=h(x')$ . Megmutatjuk, hogy egy ütközést találni $ h$ -hoz implikálja a $ b$ diszkrét logaritmus kiszámítását az $ a$ alapra nézve modulo $ p$ .

Legyen $ (x,x')$ egy ütközése a $ h$ -nak, ahol $ x=(x_1,x_2)$ , $ x'=(x_3,x_4)$ , $ x_i\in\{0,1,\ldots,q-1\}$ , $ 1\leq i\leq 4$ . Ekkor

$\displaystyle a^{x_1}b^{x_2}\equiv a^{x_3}b^{x_3}\mod p,
$

melyből következik, hogy

$\displaystyle a^{x_1-x_3}\equiv b^{x_4-x_2}\mod p.
$

Jelöljük $ y$ -nal a $ b$ diszkrét logaritmusát az $ a$ alapra vonatkozóan modulo $ p$ . Ekkor

$\displaystyle a^{x_1-x_3}\equiv a^{y(x_4-x_2)}\mod p.
$

Mivel az $ a$ egy primitív gyök modulo $ p$ , ezért az

$\displaystyle x_1-x_3\equiv y(x_4-x_2)\mod (p-1)=2q
$

kongruenciát kapjuk. Ennek a kongruenciának $ y$ a megoldása, nevezetesen a $ b$ diszkrét logaritmusa az $ a$ alapra vonatkozólag. Ez akkor lehetséges, ha $ d=$lnko$ (x_4-x_2,p-1)$ osztja az $ x_1-x_3$ -at. Az $ x_2$ és az $ x_4$ választása miatt kapjuk, hogy $ |x_4-x_2|<q$ . Mivel $ p-1=2q$ , ezért

$\displaystyle d\in\{1,2\}.
$

Ha $ d=1$ , akkor a korábbi kongruenciának van egy egyértelmű megoldása modulo $ p-1$ . Az $ y$ diszkrét logaritmus meghatározható úgy, mint a kongruencia legkisebb nemnegatív megoldása.

Ha $ d=2$ , akkor a kongruenciának két különböző megoldása van és a diszkrét logaritmus a két eredmény kipróbálásával megtalálható.

Láthatjuk, hogy a tömörítő függvény ütközésmentes mindaddig, amíg a diszkrét logaritmus kiszámítása nehéz probléma. Ezért az ütközésmentesség leredukálható egy jól ismert számelméleti problémára. Sajnos ezen tömörítő függvény kiszámítása nem nagyon hatékony, mivel moduláris hatványozásra van szükség. Emiatt ez a hash függvény csak egy elméleti érdekesség.

10.7. Üzenet hitelesítő kódok

A kriptográfiai hash függvényeket arra használják, hogy ellenőrizzék velük vajon egy állomány változott-e. Az állomány hash értékét elkülönítve tárolják. Egy állomány integritását úgy ellenőrzik, hogy kiszámolják az aktuális állomány hash értékét és azt összehasonlítják a tárolt változattal. Ha a két érték megegyezik, akkor az állomány nem változott.

Ha nemcsak az integritást, hanem a hitelességet is bizonyítani kell, akkor parametrizált hash függvényt kell használnunk.

Definíció:
Egy parametrizált hash függvény egy $ \{h_k : k\in \mathcal{K}\}$ hash függvény család. Itt $ \mathcal{K}$ egy halmaz. Ezt hívjuk a $ h$ kulcsterének.

Egy parametrizált hash függvényt üzenet hitelesítő kódnak is nevezünk vagy röviden MAC (Message Authentication Code).

Példa:
Tekintsünk egy

$\displaystyle g\colon \{0,1\}^*\to \{0,1\}^4
$

hash függvényt. Ez transzformálható a MAC-ba a

$\displaystyle h_k\colon \{0,1\}^*\to \{0,1\}^4,\ x\to g(x)\oplus k
$

módon, ahol a kulcstér a $ \{0,1\}^4$ . A következő példa mutatja, hogy miképpen használhatóak a MAC függvények.

Példa:
Alice professzor elküld egy listát a tanulmányi irodának e-mailen keresztül mindazon diákok neveivel, akik átmentek a kriptográfiai osztályba. Nagyon fontos, hogy a tanulmányi iroda biztos legyen abban, hogy ez az e-mail hiteles. A hitelesség bizonyítására egy $ \{h_k : k\in \mathcal{K}\}$ MAC-ot használnak. Alice és a tanulmányi iroda kicserélnek egymás között egy titkos $ k\in \mathcal{K}$ kulcsot. Az $ x$ listájával együtt Alice ugyancsak elküldi az $ y=h_k(x)$ hash értéket a tanulmányi irodának. Bob, a titkár ugyancsak ki tudja számolni az $ y'=h_k(x')$ hash értéket a fogadott $ x'$ üzenet alapján. Elfogadja az $ x'$ -t, ha $ y=y'$ .

Feladatok (hash függvények)

  1. Konstruáljunk egy egyirányú függvényt, amely biztonságos, ha az egészek faktorizációja nehéz!

  2. Egy $ \pi\in P_3$ permutáció esetén legyen az $ e_\pi$ a három hosszúságú bitsztringek bitpermutációja. Minden $ \pi\in P_3$ esetén határozzuk meg a

    $\displaystyle h_\pi\colon \{0,1\}^3\times \{0,1\}^3\to \{0,1\}^3,\ (x_1,x_2)\to e_\pi(x_1)\oplus x_2
$

    tömörítő függvény ütközéseinek számát!

  3. Tekintsük a $ h\colon \{0,1\}^*\to\{0,1\}^*$ , $ k\to \lfloor 10000(k(1+\sqrt{5})/2) \mod 1\rfloor$ hash függvényt, ahol a sztringeket azokkal az egészekkel jelöljük, mint amit reprezentálnak és $ r\mod 1=r-\lfloor r \rfloor$ egy nemnegatív valós $ r$ esetén.
    1. Határozzuk meg a képek maximális hosszát!
    2. Találjunk egy ütközését a hash függvénynek!

  4. Tekintsük ismét a $ h$ tömörítő függvényt a második feladatból úgy, hogy

    $\displaystyle \pi=\begin{pmatrix}
1 & 2&3\\
3&2&1
\end{pmatrix}.
$

    Határozzuk meg a $ h(0101010101011)$ hash értéket!

11. Digitális aláírás

A digitális aláírást elektronikus dokumentumok aláírására használják. Az ilyen aláírások hasonló tulajdonságokkal rendelkeznek a kézzel megvalósult aláírásokhoz. Tekintsük át röviden ezeket a tulajdonságokat.

Ha Alice aláír egy dokumentumot a saját kézi aláírásával, akkor mindenki aki látja a dokumentumot és ismeri Alice aláírását megerősítheti, hogy valóban Alice írta alá a dokumentumot. Például, az aláírás felhasználható, mint egy triviális bizonyíték arra nézve, hogy Alice tudja mi van dokumentumban.

Sok esetben van szükség elektronikus dokumentumok aláírására, pl. elektronikus szerződések, bank tranzakciók és e-mail-ek esetén.

A digitális aláírások a következőképpen működnek. Feltételezzük, hogy Alice alá akar írni egy $ m$ dokumentumot. Egy titkos $ d$ kulcsot használ és kiszámolja az $ s(d,m)$ aláírást. Felhasználva az $ e$ nyilvános kulcsot Bob ellenőrizheti, hogy az $ s(d,m)$ valóban az $ m$ aláírása.

Egy ilyen aláírási séma biztonságos, ha senki sem képes előállítani az $ s(d,m)$ aláírást anélkül, hogy tudná a titkos $ d$ kulcsot. A következő részekben leírjuk az ismert aláírási sémákat.

11.1. RSA aláírások

Az RSA felhasználható digitális aláírások generálására. Az ötlet egyszerű. Alice aláírja az $ m$ dokumentumot azzal, hogy kiszámolja az $ s=s(d,m)=m^d\mod n$ értéket. Itt a $ d$ Alice titkos kulcsa és $ n$ az RSA modulus. Bob ellenőrzi az $ s^e\mod n=m^{ed}\equiv m\mod n$ értéket.

Feltehetjük a kérdést, hogy ez miért aláírás? Nyilvánvalóan ahhoz, hogy az $ m$ -et meghatározzuk, szükség lenne az $ s$ érték $ e$ -dik gyökére, amely elérhetetlen. Csak Alice ismeri a $ d$ kulcsot, azaz csak ő számolhatta ki az $ s$ -et és ezáltal írhatta alá az $ m$ -et.

A kulcsgenerálás ugyanaz, mint az RSA kódolásban. Az aláírás kiszámítása és ellenőrzése a fentiekben ismertetésre került. Fontos megjegyezni: ekkor nem az a fontos, hogy az $ m$ értéke micsoda, hanem az aláírás. A lényeg, hogy azt Alice készítette el a saját titkos kulcsával. Ezért ezen aláírást bárki megerősítheti, ha használja Alice nyilvános kulcsát.

Többféle támadás lehetséges. Az egyik lehetőség, ha a támadó képes kicserélni Alice nyilvános kulcsát a saját nyilvános kulcsával, anélkül, hogy Bob ezt észrevenné. Ekkor aláírhat Alice nevében. Emiatt használnak biztonsági központokat.

A másik lehetőség a következő. A támadó választ egy $ s\in\{0,\ldots,n-1\}$ . Ekkor ő azt állítja, hogy ez Alice aláírása. Bob megpróbálja ellenőrizni ezt aláírást. Kiszámolja az $ m=s^e\mod n$ értéket és elhiszi, hogy Alice írta alá az $ m$ -et. Ha az $ m$ értelmes szöveg, akkor a támadó képes hamisítani Alice aláírását. Ezt nevezzük létezésen alapuló hamisítványnak.

Példa:
Alice kiválasztja a $ p=11$ , $ q=23$ , $ e = 3$ értékeket. Ekkor kapja az $ n=253$ , $ d=147$ értékeket. Alice nyilvános kulcsa a $ (253,3)$ . A titkos kulcsa 147. A támadó szeretné visszavenni a pénzét Alice számlájáról. Elküldi az $ s=123$ értéket a pénzintézetnek. A pénzintézet kiszámolja az $ m=123^3\mod 253=52$ . Elhiszi, hogy Alice szeretne visszautalni 52$-t, ami nem igaz. Így Alice egy létezésen alapuló hamisítvány áldozata lesz.

További veszély adódik még abból is, hogy az RSA multiplikatív. Ha $ m_1,m_2\in\{0,\ldots,n-1\}$ és $ s_1=m_1^d\mod n$ , $ s_2=m_2^d\mod n$ az $ m_1$ , $ m_2$ aláírásai, akkor

$\displaystyle s=s_1s_2\mod n=(m_1m_2)^d\mod n
$

az $ m=m_1m_2$ aláírása. Két érvényes RSA aláírásból kiszámolható egy harmadik. A következőkben megnézzük, hogy ezek a támadások hogyan háríthatóak el.

A támadások közül kettő lehetetlen, ha csak olyan $ m\in\{0,\ldots,n-1\}$ egészeket írunk alá, melyek bináris kifejtése $ w\circ w$ alakú, ahol $ w\in\{0,1\}^*$ . Így a bináris kifejtés két egyforma féllel rendelkezik. A szöveg ugyanúgy íródik alá, de a $ w\circ w$ technikailag íródik alá. Amikor megerősítik az aláírást, akkor Bob kiszámolja az $ m=s^e\mod n$ . Ellenőrzi, hogy az $ m$ bináris kifejtése $ w\circ w$ alakú-e. Ha nem, akkor az aláírást elutasítják.

Ekkor az létezésen alapuló hamisítvány nem működik. Ugyanis a támadónak olyan $ s$ aláírást kellene készítenie, amelyre az $ m=s^e\mod n$ pontosan $ w\circ w$ alakú. Nem ismert, hogy miképpen lehet ilyet készíteni, ha nem ismert a titkos kulcs.

Az RSA multiplikativitása sem működik többé, mert szinte biztosan nem teljesül, hogy az $ m=m_1m_2\mod n$ bináris kifejtése $ w\circ w$ alakú, még ha az teljesül is a két faktorra.

Az

$\displaystyle R\colon \{0,1\}^*\to \{0,1\}^*,\quad w\to R(w)=w\circ w
$

függvényt, amelyet a speciális struktúrájú dokumentumok generálásához használunk redundancia függvénynek nevezzük.

Az aláírás megerősítése mellett Bob megkapja azt a dokumentumot is, amelyet aláírtak. Ha Alice alá akar írni egy tetszőlegesen hosszú dokumentumot, akkor használ egy

$\displaystyle h\colon \{0,1\}^*\to \{0,\ldots,n-1\}
$

ismert ütközésmentes hash függvényt. Mivel $ h$ ütközésmentes, ezért $ h$ egyirányú is.

Az $ x$ dokumentum aláírása

$\displaystyle s=h(x)^d\mod n.
$

Ebből csak a $ h(x)$ határozható meg, de az $ x$ nem. Ezért Bob csak akkor erősítheti meg az aláírást, ha ő is ismeri az $ x$ -et. Miután Alice kiszámolja az $ s$ aláírását az $ x$ -nek, elküldi azt az $ x$ -szel együtt Bob-nak. Bob kiszámolja az $ m=s^e\mod n$ értéket és összehasonlítja az $ x$ hash függvény értékével.

Mivel a hash függvény nyilvános, Bob meg tudja ezt tenni. Ha az $ m$ és a $ h(x)$ egyenlő, akkor Bob elfogadja az aláírást, egyébként elutasítja.

Ez az eljárás ugyancsak lehetetlenné teszi a létezésen alapuló hamisítvány elkészítését. Tegyük fel, hogy a támadó kiválaszt egy $ s$ aláírást. Mivel neki az $ x$ mellett el kell küldenie az $ s$ -et is, amelyre $ h(x)=s^e\mod n$ teljesül, így az $ m=s^e\mod n$ az inverze az $ x$ -nek a $ h$ -ra nézve. Mivel a $ h$ egyirányú, így a támadás nem lehetséges.

A multiplikatív támadás sem alkalmazható. Mivel $ h$ egyirányú, lehetetlen olyan $ x$ -et találni, hogy $ h(x)=m=m_1m_2\mod n$ . Továbbá a támadó nem képes kicserélni Alice $ x$ dokumentumát egy $ x'$ másikra, mivel ekkor az $ (x,x')$ egy ütközése a $ h$ -nak és $ h$ ütközésmentes.

11.2. ElGamal aláírás

Az ElGamal aláírás hasonló az ElGamal kriptorendszerhez, bár nem használja az abban leírt módszert. A biztonsága a $ (\mathbb{Z}/p\mathbb{Z})^*$ -beli diszkrét logaritmus kiszámításának bonyolultságán alapszik, ahol $ p$ prím.

A kulcsgenerálás ugyanaz, mint az ElGamal rendszerben ($ p$ egy nagy véletlen prím, $ g$ primitív gyök modulo $ p$ , $ a\in\{1,2,\ldots,p-2\}$ véletlen szám, $ A=g^a\mod p$ , titkos kulcs $ a$ , nyilvános kulcs $ (p,g,A)$ ).

Alice aláír egy $ x\in \{0,1\}^*$ dokumentumot. Egy nyilvános, ismert

$\displaystyle h\colon \{0,1\}^*\to \{1,2,\ldots,p-2\}
$

hash függvényt használ. Alice véletlenszerűen kiválaszt egy $ k\in\{1,2,\ldots,p-2\}$ számot, amely relatív prím $ p-1$ -gyel. Kiszámolja az

$\displaystyle r=g^k \mod p,\quad s=k^{-1}(h(x)-ar)\mod (p-1)
$

értéket, ahol $ k^{-1}$ a $ k$ inverze modulo $ p-1$ . Az $ x$ aláírása az $ (r,s)$ pár. Mivel hash függvényt használtunk, a megerősítő nem képes visszakapni az $ x$ dokumentumot az aláírásból. Alice-nak kell azt átadnia.

A megerősítő, Bob felhasználja Alice nyilvános $ (p,g,A)$ kulcsát. Ellenőrzi, hogy

$\displaystyle 1\leq r\leq p-1
$

teljesül-e. Ha ez nem teljesül, akkor elutasítja az aláírást. Egyébként ellenőrzi még az

$\displaystyle A^rr^s\equiv g^{h(x)}\mod p
$

kongruenciát.

Elfogadja az aláírást, ha a kongruencia teljesül, egyébként elutasítja. A fenti feltételek alapján nincs más mód elkészíteni az aláírást.

Példa:
Legyen ismét $ p=23$ , $ g=7$ , $ a=6$ és kiszámoljuk a $ A=g^a\mod p=4$ értéket. A nyilvános kulcs a (23,7,4), a titkos a 6. Alice alá akar írni egy dokumentumot, melyre $ h(x)=7$ . Kiválaszt egy $ k=5$ értéket és megkapja az $ r=17$ -et. Az inverze a $ k$ -nak modulo $ p-1$ a $ k^{-1}=9$ . Ezért $ s=k^{-1}(h(x)-ar)\mod p=3$ . Az aláírás a $ (17,3)$ pár. Bob ellenőrzi az aláírást. Kiszámolja az $ A^rr^s\mod p=5$ értéket és a $ g^{h(x)}\mod p=5$ -öt. Egyenlőek, így az aláírás megerősítve.

A $ p$ kiválasztása esetén hasonlóan kell eljárni, mint a ElGamal kriptorendszer esetén.

A $ k$ kiválasztásánál viszont figyelni kell arra, hogy minden új aláíráshoz új $ k$ is kell. Ez akkor garantált, ha $ k$ véletlenszerűen generált.

Tegyük fel, hogy az $ s_1$ , $ s_2$ az $ x_1$ , $ x_2$ dokumentumokhoz készült aláírások ugyanazzal a $ k$ -val. Ekkor az $ r=g^k\mod p$ is ugyanaz mindkét aláírásnál. Emiatt

$\displaystyle s_1-s_2\equiv k^{-1}(h(x_1)-h(x_2))\mod (p-1).
$

Ebből a kongruenciából a $ k$ meghatározható, ha a $ h(x_1)-h(x_2)$ invertálható modulo $ p-1$ . A $ k$ , $ s_1$ , $ r$ , $ h(x_1)$ adatokból Alice titkos $ a$ kulcsa meghatározható, mivel

$\displaystyle s_1=k^{-1}(h(x_1)-ar)\mod (p-1)
$

és emiatt

$\displaystyle a\equiv r^{-1}(h(x_1)-ks_1)\mod (p-1).
$

11.3. DSA: digitális aláírási algoritmus

A Digitális Aláírási Algoritmust (Digital Signature Algorithm - DSA) az USA NIST (National Institute of Standard and Technology) szervezete javasolta és szabványosította. Ez egy hatékony variánsa az ElGamal aláírási sémának. Ebben lényegesen csökkentették az használt kitevők bitjeinek számát.

Alice választ egy $ q$ prímszámot, melyre

$\displaystyle 2^{159}<q<2^{160}.
$

Így $ q$ bináris hosszúsága 160. Alice választ egy nagy $ p$ prímet a következő tulajdonságokkal: A bináris hossza $ p$ -nek 512 és 1024 közé esik és 64 többszöröse. A $ q\mid (p-1)$ feltétel implikálja, hogy a $ \mathbb{Z}/p\mathbb{Z}$ csoport $ q$ rendű elemeket tartalmaz. Ezután Alice választ egy primitív $ x$ gyököt $ \mod p$ és kiszámolja a

$\displaystyle g=x^{(p-1)/q} \mod p.
$

Ekkor a $ g+p\mathbb{Z}$ elem $ q$ rendű a $ (\mathbb{Z}/p\mathbb{Z})^*$ -ben. Végül Alice választ egy véletlen $ a$ számot az $ \{1,2,\ldots,q-1\}$ halmazból és kiszámolja

$\displaystyle A=g^a \mod p.
$

Alice nyilvános kulcsa a $ (p,q,g,A)$ . A titkos kulcsa $ a$ .

Alice el szeretne küldeni egy $ x$ dokumentumot. Ekkor felhasznál egy ismert

$\displaystyle h\colon \{0,1\}^*\to \{1,2,\ldots,q-1\}
$

ütközésmentes hash függvényt. Választ egy véletlen $ k$ számot, melyre $ k\in\{1,2,\ldots,q-1\}$ és kiszámolja az

$\displaystyle r=(g^k \mod p)\mod q,
$

és legyen

$\displaystyle s=k^{-1}(h(x)+ar)\mod q.
$

A $ k^{-1}$ az inverze a $ k$ -nak modulo $ q$ . Az aláírás az $ (r,s)$ .

Az érvényesítés a következő módon működik. Bob szeretné érvényesíteni az $ (r,s)$ aláírást az $ x$ dokumentumhoz. Megkapja Alice nyilvános $ (p,q,g,A)$ kulcsát és a nyilvános hash függvényt. Ekkor megnézi, hogy

$\displaystyle 1\leq r\leq q-1,\ 1\leq s\leq q-1
$

feltételek teljesülnek. Ha ez nem teljesül, akkor Bob elutasítja az aláírást. Egyébként megnézi, hogy az

$\displaystyle r=((g^{(s^{-1}h(x))\mod q} A^{(rs^{-1})\mod q})\mod p)\mod q
$

teljesül. Ha a megfelelő módon lett elkészítve az aláírás, akkor a

$\displaystyle g^{(s^{-1}h(x))\mod q} A^{(rs^{-1})\mod q}\equiv g^{s^{-1}(h(x)+ra)}\equiv g^k\mod p
$

alapján az előző feltétel teljesül.

A DSA nagyon hasonló az ElGamal-féle aláírási sémához. Már az ElGamal sémában is teljesül, hogy az előszámítások gyorsabbá teszik az aláírás generálását. Viszont a DSA hatékonyabb az ElGamal-hoz képest, mivel csak két hatványozás szükséges modulo $ p$ , miközben az ElGamal-ban három kell. Továbbá a DSA kitevők 160 bitesek, miközben az ElGamal-ban olyan nagyok mint a $ p$ , azaz legalább 768 bitesek. Ez megspórol több mint 600 négyzetreemelést és szorzást modulo $ p$ . A biztonságnál hasonló feltételekre kell vigyázni, mint az ElGamal-nál.

Feladatok (digitális aláírás)

  1. Számoljuk ki az $ m=11111$ RSA aláírását (hash függvény nélkül) az $ n=28829$ RSA modulussal és a legkisebb nyilvános $ e$ kitevővel!

  2. Problematikus-e az alacsony kitevőjű vagy a közös modulus támadás az RSA-ból az RSA típusú aláírásnál?

  3. Legyen $ p=130$ . Számoljunk ki egy érvényes titkos $ a$ kulcsot és egy nyilvános $ (p,g,A)$ kulcsot az ElGamal aláírási szisztéma szerint!

  4. Legyen $ p=2237$ . Számoljunk ki egy érvényes titkos $ a$ kulcsot és egy nyilvános $ (p,g,A)$ kulcsot az ElGamal aláírási szisztéma szerint!

  5. Számoljuk ki az $ m=11111$ RSA aláírását (hash függvény nélkül) az $ n=28829$ RSA modulussal és a nyilvános $ e=5$ kitevővel!

Irodalomjegyzék

1
J. BUCHMAN, Introduction to Cryptography, Springer, 2000.

2
LIPTAI KÁLMÁN, Kriptográfia, Kempelen Farkas Digitális Tankönyvtár, 2011.

3
S. SINGH, The Code Book. The Secret History of Codes and Code Breaking. Fourth Estate, 1999, (Magyarul: Kódkönyv, A rejtjelezés és rejtjelfejtés története, Park Könyvkiadó, 2002).

4
GAÁL ISTVÁN, KOZMA LÁSZLÓ, Lineáris algebra, DE jegyzet, 2008.