Nyilvános kulcsú kriptorendszer

Nyilvános kulcsú kriptográfiai rendszer (egyfajta aszimmetrikus titkosítás , aszimmetrikus titkosítás ) - olyan titkosítási és/vagy elektronikus aláírási (ES) rendszer, amelyben a nyilvános kulcsot nyitott (azaz nem védett, megfigyelhető) csatornán továbbítják, és ellenőrzésre használják. az ES és a titkosítási üzenetek esetében. Az ES generálásához és az üzenet visszafejtéséhez privát kulcsot használnak [1] . A nyilvános kulcsú kriptográfiai rendszereket ma már széles körben használják különféle hálózati protokollokban , különösen a TLS-protokollokban és elődjében, az SSL -ben (a mögöttes HTTPS ), az SSH -ban . PGP -ben, S/MIME -ben is használatos .

A nyilvános kulcsú kriptorendszer ötlete

Általános elvek

Az aszimmetrikus nyilvános kulcsú titkosítás a következő elveken alapul:

• Lehetőség van nagyon nagy számpár létrehozására (nyilvános kulcs és privát kulcs), így a nyilvános kulcs ismeretében lehetetlen kiszámítani a magánkulcsot ésszerű időn belül. Ebben az esetben a generálási mechanizmus jól ismert.
• Erős titkosítási módszerek állnak rendelkezésre az üzenetek nyilvános kulccsal történő titkosításához, így csak a privát kulccsal lehet visszafejteni. A titkosítási mechanizmus jól ismert.
• Két kulcs tulajdonosa a magánkulcsot nem adja ki senkinek, de a nyilvános kulcsot megosztja a partnerekkel, vagy nyilvánosságra hozza.

Ha titkosított üzenetet kell továbbítani a kulcsok tulajdonosának, akkor a küldőnek meg kell kapnia a nyilvános kulcsot. A feladó az üzenetét a címzett nyilvános kulcsával titkosítja, és nyitott csatornákon továbbítja a címzettnek (a kulcsok tulajdonosának). Ugyanakkor senki sem tudja visszafejteni az üzenetet, csak a privát kulcs tulajdonosa.

Ennek eredményeként az üzenetek biztonságosan titkosíthatók, miközben a visszafejtési kulcsot mindenki – még az üzenet küldője is – titokban tartja.

Ez az elv a csomagküldés mindennapi hasonlatával magyarázható: "zár - kulcs a zárhoz". Az A résztvevő személyi zárral és kulccsal rendelkezik. Ha A résztvevő titkos csomagot szeretne kapni B résztvevőtől, akkor nyilvánosan átadja neki a kastélyát. B résztvevő a titkos csomagon lévő zárat zárja és elküldi A résztvevőnek. A csomag átvétele után A résztvevő a kulccsal kinyitja a zárat és átveszi a csomagot.

A zár átadásáról és a csomag elfogásáról való ismerete semmit nem ad a potenciális támadónak: csak az A résztvevő rendelkezik a zár kulcsával, így a csomagot nem lehet kinyitni.

Megvalósítás egyirányú funkcióval

A nyilvános kulcsú kriptográfia gondolata nagyon szorosan kapcsolódik az egyirányú függvények eszméjéhez , vagyis olyan függvényekhez , amelyekből meglehetősen könnyű értéket találni egy ismert értékből , míg a meghatározás lehetetlen . ésszerű idő.

De maga az egyirányú funkció használhatatlan az alkalmazásban: titkosítani tudja az üzenetet, de nem tudja visszafejteni. Ezért a nyilvános kulcsú kriptográfia egyirányú függvényeket használ kiskapuval. A kiskapu olyan titok, amely segít megfejteni. Vagyis létezik olyan , hogy és ismeretében ki tudjuk számítani . Például, ha egy órát több részre szedünk, nagyon nehéz újra összeszerelni egy újra működő órát. De ha van összeszerelési utasítás (kiskapu), akkor ez a probléma könnyen megoldható.

Az információ címzettje létrehoz egy nyilvános kulcsot és egy "csapóajtót" (más szóval a kulcs nyilvános és privát részét), majd a nyilvános kulcsot átadja a küldőnek, és a "csapóajtót" megtartja magának. A feladó a nyilvános kulcs alapján titkosítja az információkat: az ilyen titkosított információkat könnyű visszafejteni, ha egyszerre rendelkezik nyilvános kulcsgal és "hátsó ajtóval". Funkciót tekintve a vevő egy hátsó ajtót képez , majd a funkció paramétereiről információt ad át a küldőnek (a funkció paramétereinek ismeretében még a "hátsó ajtó" észlelése sem lehetséges ésszerű időn belül). Ezt követően a feladó titkosított üzenetet hoz létre , és a címzett kivonat belőle , tudván .

Példák

A következő példa segít megérteni a nyilvános kulcsú kriptográfia ötleteit és módszereit – jelszavak tárolását egy távoli számítógépen, amelyhez a felhasználóknak csatlakozniuk kell. A hálózat minden felhasználója más jelszóval rendelkezik. A bejáratnál jelzi a nevet és beír egy titkos jelszót. De ha a jelszót egy távoli számítógép lemezén tárolja, akkor valaki elolvashatja (ezt a számítógép rendszergazdája különösen könnyen megteheti), és hozzáférhet a titkos információkhoz. A probléma megoldására egyirányú funkciót használnak. A titkos jelszó létrehozásakor a számítógép nem magát a jelszót tárolja, hanem a függvény ebből a jelszóból és felhasználónévből történő kiszámításának eredményét. Például az Alice felhasználó a "Gladiolus" jelszóval állt elő. Ezen adatok elmentésekor az ( ALICE_GLADIOLUS ) függvény eredménye számítódik ki, legyen az eredmény a CAMOMILE sztring , ami el lesz mentve a rendszerbe. Ennek eredményeként a jelszófájl a következő formájú lesz:

Név	(Név: Jelszó)
ALICE	KAMILLA
BAB	NÁRCISZ

A bejelentkezés most így néz ki:

Amikor Alice beírja a "titkos" jelszót, a számítógép ellenőrzi, hogy az ALICE_GLADIOLUS -ra alkalmazott függvény a számítógép lemezén tárolt CAMOMILE helyes eredményt adja-e vagy sem. Érdemes legalább egy betűt megváltoztatni a névben vagy a jelszóban, és teljesen más lesz a funkció eredménye. A „titkos” jelszó semmilyen formában nem tárolódik a számítógépen. A jelszófájlt mostantól más felhasználók is megtekinthetik a magánélet elvesztése nélkül, mivel a funkció szinte visszafordíthatatlan.

Az előző példa egy egyirányú függvényt használ kiskapu nélkül, mivel nem szükséges az eredeti üzenetet lekérni a titkosított üzenetből. A következő példában egy olyan sémát veszünk figyelembe, amely képes visszaállítani az eredeti üzenetet egy „hátsó ajtó” segítségével, vagyis olyan információkkal, amelyeket nehéz megtalálni. A szöveg titkosításához használhat egy nagy előfizetői névjegyzéket, amely több vastag kötetből áll (nagyon könnyű megtalálni a város bármely lakójának számát, de szinte lehetetlen előfizetőt találni egy ismert számmal) . A titkosított üzenet minden betűjéhez egy azonos betűvel kezdődő név kerül kiválasztásra. Így a levél hozzá van rendelve az előfizető telefonszámához. Az elküldött üzenet, például " BOX ", a következőképpen lesz titkosítva:

A kriptoszöveg egy számokból álló lánc lesz, amely az általuk választott sorrendben van beírva a könyvtárba. A megfejtés megnehezítése érdekében válasszon véletlenszerű neveket, amelyek a kívánt betűvel kezdődnek. Így az eredeti üzenet sokféle számlistával (kriptotextussal) titkosítható.

Példák az ilyen kriptotextusokra:

A szöveg megfejtéséhez a növekvő számok szerint összeállított kézikönyvvel kell rendelkeznie. Ez a könyvtár egy kiskaput (titkot, amely segít a kezdeti szöveg megszerzésében), amelyet csak a címzett ismer. Mindkét könyvtárból származó adatok nélkül általában lehetetlen a szöveg megfejtése, de csak az első könyvtár elegendő a titkosításhoz [2] . Ebben az esetben a címzett könnyen előre kialakíthatja mindkét könyvtárat, és csak az elsőt adja át a feladónak titkosítás céljából.

Nyilvános kulcsú titkosítási séma

Legyen  a kulcstér és és  a titkosítási és visszafejtési kulcsok.  egy tetszőleges kulcs titkosítási függvénye, így . Itt hol  a titkosított szövegek tere , hol  pedig az üzenetek tere.

 egy visszafejtési funkció, amellyel meg lehet találni az eredeti üzenetet a titkosított szöveg mellett : ,  a titkosítási készlet, és  a megfelelő visszafejtési készlet. Mindegyik párnak a következő tulajdonsága van: ismeretében lehetetlen megoldani az egyenletet , vagyis adott tetszőleges rejtjelezett szöveg esetén nem lehet üzenetet találni . Ez azt jelenti, hogy az adott kulcsból nem lehet meghatározni a megfelelő visszafejtő kulcsot . egy egyirányú függvény, és  egy kiskaput jelent [3] .

Az alábbiakban az A személy által B személynek történő információtovábbítás diagramja látható. Lehetnek magánszemélyek és szervezetek is, stb. De a könnyebb észlelés érdekében a programban résztvevőket szokás emberekkel azonosítani, akiket leggyakrabban Alice és Bob néven emlegetnek. Azt a résztvevőt, aki Alice és Bob üzeneteit próbálja elkapni és visszafejteni, leggyakrabban Évának nevezik.

1. Bob választ egy párt , és elküldi a titkosítási kulcsot (nyilvános kulcsot) Alice-nek a nyilvános csatornán keresztül, a visszafejtési kulcs (privát kulcs) pedig védett és titkos (nem szabad nyilvános csatornán továbbítani).
2. Ha üzenetet szeretne küldeni Bobnak, Alice a nyilvános kulcs : ,  a fogadott rejtjelezett szöveg által meghatározott titkosítási funkcióját használja .
3. Bob az érték által egyedileg azonosított inverz transzformáció segítségével dekódolja a rejtjelezett szöveget .

Tudományos alapok

Az aszimmetrikus titkosítások Whitfield Diffie és Martin Hellman 1976 -ban megjelent New Directions in Modern Cryptography című művében kezdődtek . Ralph Merkle nyilvános kulcsok elosztásával kapcsolatos munkája hatására egy módszert javasoltak a privát kulcsok nyilvános csatornán keresztül történő megszerzésére. Ez az exponenciális kulcscsere módszer, amely Diffie-Hellman kulcscsere néven vált ismertté , volt az első közzétett gyakorlati módszer a titkos kulcsok megosztására a csatorna hitelesített felhasználói között. 2002 -ben Hellman javasolta az algoritmus "Diffie-Hellman-Merkle" elnevezését, elismerve Merkle hozzájárulását a nyilvános kulcsú kriptográfia feltalálásához. Ugyanezt a sémát Malcolm Williamson ( eng.  Malcolm J. Williamson ) dolgozta ki az 1970-es években, de 1997 -ig titokban tartották . A Merkle nyilvános kulcsú elosztási módszerét 1974 -ben találták fel és 1978 -ban adták ki, és Merkle-rejtvénynek is nevezik.

1977- ben az MIT tudósai Ronald Rivest , Adi Shamir és Leonard Adleman a faktorizációs problémán alapuló titkosítási algoritmust fejlesztettek ki. A rendszert vezetéknevük első betűiről nevezték el ( RSA  - Rivest, Shamir, Adleman). Ugyanezt a rendszert 1973 -ban találta ki Clifford Cocks , aki a Kormányzati Kommunikációs Központban ( GCHQ ) dolgozott, de ezt a munkát csak a központ belső dokumentumai őrizték, így a létezéséről csak 1977 -ben tudtak . Az RSA volt az első olyan algoritmus, amely titkosításra és digitális aláírásra egyaránt alkalmas volt.  

Általánosságban elmondható, hogy az ismert aszimmetrikus titkosítási rendszerek az egyik összetett matematikai problémán alapulnak, amely lehetővé teszi egyirányú függvények és hátsó ajtófüggvények felépítését. Például a Merkle-Hellman és a Hoare-Rivest kriptorendszerek az úgynevezett hátizsákos problémára támaszkodnak .

A nyilvános kulcsú kriptorendszerek felépítésének alapelvei

1. Kezdjük egy nehéz feladattal . Elméleti értelemben nehéznek kell lennie a megoldásnak: ne legyen olyan algoritmus, amellyel a probléma nagyságához képest polinomiális időben rendezhető lenne az összes megoldási lehetőség. Helyesebb, ha azt mondjuk: ne legyen ismert polinomiális algoritmus, ami ezt a feladatot megoldja - hiszen még egyetlen feladatra sem bizonyított, hogy elvileg nincs rá megfelelő algoritmus.
2. Kiválaszthat egy könnyű részfeladatot a közül . Polinom időben kell megoldani, és jobb, ha lineáris időben.
3. „Shuffle and Shake” , hogy az eredetitől teljesen eltérő feladatot kapjon . A probléma legalább úgy néz ki, mint az eredeti megoldhatatlan probléma .
4. megnyílik egy leírással, hogyan használható titkosítási kulcsként. Hogy hogyan lehet hozzájutni , azt titokban tartják, mint egy titkos kiskaput.
5. A kriptorendszer úgy van megszervezve, hogy a legális felhasználó és a kriptoanalitikus visszafejtési algoritmusai jelentősen eltérjenek egymástól. Míg a második megoldja a -problémát, az első titkos kiskaput használ, és megoldja a -problémát.

Kriptográfia több nyilvános kulccsal

• A következő példa egy olyan sémát mutat be, amelyben Alice titkosítja az üzenetet, hogy csak Bob tudja elolvasni, és fordítva, Bob titkosítja az üzenetet, hogy csak Alice tudja visszafejteni.

Legyen 3 kulcs , , , a táblázat szerint elosztva.

Arc	Kulcs
Alice
Bab
Ének
Dave	,
Ellen	,
Frank	,

Ezután Alice titkosíthatja az üzenetet a kulccsal , Ellen pedig a kulcsokkal , Carol a kulccsal , Dave pedig a kulcsokkal tudja visszafejteni . Ha Dave kulccsal titkosítja az üzenetet , akkor Ellen el tudja olvasni az üzenetet, ha kulccsal , akkor Frank el tudja olvasni, ha mindkét és a kulccsal , akkor Carol olvassa el az üzenetet. Más résztvevők hasonló módon járnak el. Így, ha a kulcsok egy részhalmazát használjuk a titkosításhoz, akkor a készlet többi kulcsára van szükség a visszafejtéshez. Egy ilyen séma n kulcshoz használható.

Kulccsal titkosítva	Kulccsal visszafejtve
és
és
és
	,
	,
	,

• Mostantól üzeneteket küldhet ügynökcsoportoknak anélkül, hogy előre ismerné a csoport összetételét.

Vegyünk először egy készletet, amely három ügynökből áll: Alice, Bob és Carol. Alice kap kulcsokat és , Bob - és , Carol - és . Most, ha az elküldött üzenet a kulccsal titkosítva van , akkor csak Alice tudja elolvasni a kulcsok és a kulcsok egymás utáni alkalmazásával . Ha üzenetet szeretne küldeni Bobnak, az üzenet a kulccsal , Carol - a kulccsal van titkosítva . Ha Alice-nek és Carolnak is szeretne üzenetet küldeni, akkor a és kulcsok titkosításra szolgálnak .

Ennek a sémának az az előnye, hogy csak egy üzenetre és n kulcsra van szükség a megvalósításához (n ügynököt tartalmazó sémában). Ha egyedi üzeneteket küldenek, azaz külön kulcsot használnak minden ügynökhöz (összesen n kulcs) és minden egyes üzenethez, akkor kulcsok szükségesek az üzenetek küldéséhez az összes különböző részhalmazhoz.

Ennek a sémának az a hátránya, hogy az ügynökök egy részhalmazát is sugároznia kell (a névlista hosszú lehet), amelyhez az üzenetet továbbítani kívánja. Ellenkező esetben mindegyiküknek át kell mennie az összes billentyűkombináción, hogy megfelelőt keressen. Ezenkívül az ügynököknek jelentős mennyiségű információt kell tárolniuk a kulcsokról [4] .

Nyilvános kulcsú algoritmusok kriptoanalízise

Úgy tűnik, hogy a nyilvános kulcsú titkosítási rendszer ideális rendszer, amely nem igényel biztonságos csatornát a titkosítási kulcs továbbításához. Ez azt jelentené, hogy két jogos felhasználó kommunikálhat egy nyitott csatornán anélkül, hogy találkoznia kellene a kulcsok cseréjéhez. Sajnos nem az. Az ábra azt szemlélteti, hogy Eve, mint aktív elfogó, hogyan tudja átvenni a rendszert (dekódolni a Bobnak szánt üzenetet) anélkül, hogy feltörné a titkosítási rendszert.

Ebben a modellben Eve elfogja a Bob által Alice-nek küldött nyilvános kulcsot. Ezután létrehoz egy kulcspárt , és Bobnak "maszkírozza" azáltal, hogy elküldi Alice-nek a nyilvános kulcsot , amelyről Alice azt gondolja, hogy Bob küldött neki nyilvános kulcsot. Eve elfogja Alice-től Bobnak küldött titkosított üzeneteket, visszafejti azokat a titkos kulccsal , újra titkosítja Bob nyilvános kulcsával , és elküldi az üzenetet Bobnak. Így egyik résztvevő sem veszi észre, hogy van egy harmadik fél, aki vagy egyszerűen elkaphatja az üzenetet , vagy hamis üzenettel helyettesítheti . Ez rávilágít a nyilvános kulcsú hitelesítés szükségességére. Ehhez általában tanúsítványokat használnak . Az elosztott kulcskezelés a PGP -ben kezesek segítségével oldja meg a problémát [5] .

A támadás másik formája a privát kulcs kiszámítása a nyilvános kulcsból (az alábbi ábra). A kriptoanalitikus ismeri a titkosítási algoritmust , elemzi azt, megpróbálja megtalálni . Ez a folyamat leegyszerűsödik, ha a kriptoanalitikus több c kriptotextust elfogott, amelyeket A személy küldött B személynek.

A legtöbb nyilvános kulcsú titkosítási rendszer a nagyszámú faktorizációs problémán alapul. Például az RSA két nagy szám szorzatát használja n nyilvános kulcsként. Egy ilyen algoritmus feltörésének bonyolultsága az n szám faktorálásának nehézségében rejlik. De ez a probléma reálisan megoldható. És minden évben a bomlási folyamat egyre gyorsabbá válik. Az alábbiakban a "Quadratic Sieve" algoritmust használó faktorizációs adatok láthatók.

Ezenkívül a dekompozíciós probléma potenciálisan megoldható a Shor algoritmus használatával, ha kellően erős kvantumszámítógépet használunk .

Az aszimmetrikus titkosítás számos módszerénél a kriptográfiai elemzés eredményeként kapott kriptográfiai erősség jelentősen eltér az algoritmusok fejlesztői által az elméleti becslések alapján deklarált értékektől. Ezért sok országban az adattitkosítási algoritmusok használatának kérdése a jogszabályi szabályozás területéhez tartozik. Különösen Oroszországban csak azok az adattitkosító szoftvereszközök használhatók állami és kereskedelmi szervezetekben, amelyek állami tanúsítványt kaptak a közigazgatási szervekben, különösen az FSB -ben, az FSTEC -ben [6] .

A rendszer jellemzői

Alkalmazás

Nyilvános kulcsú titkosítási rendszer algoritmusok használhatók [7] :

• mint független eszköz a továbbított és tárolt információk védelmére,
• a kulcsok elosztásának eszközeként (általában nyilvános kulcsú kriptorendszerek algoritmusai segítségével kis méretű kulcsokat osztanak ki, és a nagy információáramlás továbbítása más algoritmusok segítségével történik),
• a felhasználói hitelesítés eszközeként.

Előnyök

Az aszimmetrikus rejtjelek előnyei a szimmetrikusokkal szemben :

• nem kell először átvinni a titkos kulcsot egy megbízható csatornán;
• csak az egyik fél ismeri a visszafejtő kulcsot, amelyet titokban kell tartani (a szimmetrikus kriptográfiában egy ilyen kulcsot mindkét fél ismer, és mindkettőnek titokban kell tartania);
• nagy hálózatokban a kulcsok száma egy aszimmetrikus kriptorendszerben sokkal kevesebb, mint egy szimmetrikusban.

Hátrányok

Az aszimmetrikus titkosítási algoritmus hátrányai a szimmetrikushoz képest:

• nehezebb megváltoztatni az algoritmust;
• hosszabb kulcsok – az alábbi táblázat egy szimmetrikus algoritmus kulcshosszát hasonlítja össze egy hasonló kriptográfiai erősségű RSA-kulcs hosszával:

• a kulcspár segítségével történő titkosítás-dekódolás két-három nagyságrenddel lassabb, mint ugyanazon szöveg szimmetrikus algoritmussal történő titkosítása-dekódolása;
• lényegesen több számítási erőforrásra van szükség, ezért a gyakorlatban aszimmetrikus titkosítási rendszereket alkalmaznak más algoritmusokkal kombinálva:
  1. EDS esetén az üzenet előzetesen kivonatolva van, és egy aszimmetrikus kulcs segítségével a hash függvénynek csak viszonylag kis eredményét írják alá ;
  2. titkosításhoz hibrid kriptorendszerek formájában használják őket , ahol nagy mennyiségű adatot titkosítanak szimmetrikus rejtjellel egy munkamenetkulcson, és csak magát a munkamenetkulcsot továbbítják aszimmetrikus titkosítással.

Az aszimmetrikus titkosítások típusai

• RSA (Rivest-Shamir-Adleman)
• DSA (Digital Signature Algorithm)
• Elgamal (ElGamal titkosítási rendszer)
• Diffie-Hellman (Diffie-Hellman kulcscsere)
• Az ECDSA (Elliptic Curve Digital Signature Algorithm) egy nyilvános kulcsú algoritmus digitális aláírás létrehozására.
• GOST R 34.10-2012
• Rabin
• Luc
• McEliece
• Williams kriptorendszer

Lásd még

• Blokk titkosítás
• Stream titkosítás
• Nyilvános kulcsú infrastruktúra (PKI)
• CEILIDH
• Jelszó bonyolultsága
• A Hushmail  egy nyilvános kulcsú titkosításon alapuló webalapú e-mail szolgáltatás.

Jegyzetek

1. ↑ Bruce Schneier. Alkalmazott kriptográfia. 2. kiadás Protokollok, algoritmusok és forrásszövegek C nyelven. 2.7. fejezet Digitális aláírás és titkosítás.
2. ↑ Salomaa A. Nyilvános kulcsú titkosítás. Val vel. 74-75
3. ↑ Handbook of Applied Cryptography, Menezes AJ, Oorschot PC, Vanstone SA, 25-26.
4. ↑ Bruce Schneier. Alkalmazott kriptográfia. 2. kiadás Protokollok, algoritmusok és forrásszövegek C nyelven. fejezet 3.5
5. ↑ PGP. Kulcselosztás. . Archiválva az eredetiből 2013. július 26-án. (határozatlan)
6. ↑ Az elegendő védelem elve (hozzáférhetetlen link) . Letöltve: 2008. december 4. Az eredetiből archiválva : 2010. május 24.. (határozatlan) 
7. ↑ Barichev S. Rejtjelezés titkok nélkül. Val vel. húsz

Irodalom

• Salomaa A. Nyilvános kulcsú kriptográfia. — M .: Mir, 1995. — 318 p. — ISBN 5-03-001991-X .
• AJ Menezes, PC van Oorschot, SA Vanstone. Alkalmazott kriptográfia kézikönyve . - 1997. - ISBN 0-8493-8523-7 .
• Schneier B. Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód in C. - M .: Triumph, 2002. - 816 p. - 3000 példányban.  - ISBN 5-89392-055-4 .

Linkek

• A nyilvános kulcs harminc éve | Computerworld Oroszország | "Open Systems" kiadó  (orosz)