Vigenère-rejtjel

A Wikipédiából, a szabad enciklopédiából
A Vigenère-rejtjel Blaise de Vigenère (a képen) után kapta a nevét, bár Giovan Battista Bellaso hamarabb találta fel ezt a kódot. Vigenère egy erősebb autokulcs-kódot talált fel

A Vigenère-kód vagy Vigenère-rejtjel egy titkosítási módszer, amely különböző Caesar-kódok sorozatát használja, egy adott kulcsszó betűitől függően. Ez egy egyszerű fajtája a polialfabetikus rejtjeleknek.

Ezt a kódot több alkalommal is újra feltalálták, a módszert először Giovan Battista Bellaso írta le 1553-ban, La cifra del. Sig. Giovan Batista Belaso című könyvében, azonban később tévesen Blaise de Vigenère-nek tulajdonították, és mind a mai napig az ő nevét viseli.

A kódot széles körben ismerik, mivel könnyen megérthető és használható, azonban kezdők számára nem ritkán feltörhetetlennek bizonyul; ez az oka annak, hogy franciául a „le chiffre indéchiffrable” („feltörhetetlen kód”) elnevezés ragadt rá.

Története[szerkesztés]

A Caesar-kódok feltörése Al-Kindi munkájától kezdve szinte rutinmunkának számított, ezért a rejtjelezésben érdekelt emberek elkezdtek olyan technikák után kutatni, amik ahhoz hasonlóan egyszerűek, ugyanakkor lényegesen nagyobb biztonságot adnak. Némi logikával kikövetkeztethető, hogy az egymás után alkalmazott Caesar-kódolások is Caesar-kódok, hiszen két egymás utáni eltolás együttesen is eltolást adnak.[1]

Elsőként 1467-ben Leon Battista Alfredi tudósított egy polialfabetikus kódolásról. Ő két lemezt használt, amikre az ábécék voltak írva, azonban nem betűnként, hanem szavanként forgatta el a lemezeket, ily módon a módszere nem is igazi Vigenère-kódolás. Az eltolások váltását a szó elejére írt betűvel jelezte.

A Vigenère-kódolás egyik kritikus eleme a tabula recta, az ábécéket felsoroló táblázat.[2] Ezt 1508-ban Johannes Trithemius közölte le a Poligraphia című művében. Maga Trithemius is közzétett egy merev, kiszámítható módszert a titkosításra, azonban ezen alapul a Vigenère által leírt szisztéma is.

Az igazi módszert Giovan Battista Bellaso közölte 1553-as művében. Ő már kifejtette a kulcs használatát és javasolta a betűnkénti változtatást, mint feltörést nehezítő eljárást, így a korábbi elgondolásoknál erősebb, ugyanakkor rugalmasabb kódolást tett lehetővé. Kulcsként gyakorlatilag bármilyen betűcsoportot (szavakat, rövid kifejezéseket, idézeteket lehet használni például), és mindössze ezt kell szigorúan titokban tartani. A kulcscsere lehetséges valamilyen más üzenetben elrejtve, vagy magában a kódolt üzenetben, de történhet személyes találkozón is. Éppen ezért a Vigenère-kódot használó partnerek lehallgatásakor központi jelentőségű a kulcs megszerzése. Bellaso még csak részben használta a saját eljárását, a titkosítás során minden szót az első betűjével kódolt el.

Blaise de Vigenèer 1586-ban már autokulcsos kódolást ír le. Ennek lényege, hogy a rövid kulcsszó után az üzenetet a saját betűivel titkosítjuk. Emiatt a 19. században Vigenère-t kezdték ennek a kódolásnak a kitalálójaként emlegetni.

Vigenère eljárása hamar elismertségre tett szert kivételes nehézsége okán. 1868-ban Lewis Carrol egy gyermekújságban megfejthetetlennek nevezte a titkosítást, holott már 1854-ban Charles Babbage megfejtett egy hasonló módszert, bárt ez a munkája nem maradt fent. Egy Friedrich Kasiski nevű német őrnagy már 1863-ban leírta a Vigenère-kód feltörésének módszerét, ennek ellenére 1917-ben a Scientific American még lehetetlennek nevezte a megfejtését.

Az amerikai polgárháborúban a konföderációs seregek is használták ezt a kódolást, azonban nagyon gyenge jelszavakkal, így az uniós seregek rutinszerűn fejtették meg az üzeneteiket. A kulcsok a "Manchester Bluff" és a "Complete Victory" voltak, később ehhez még hozzávették a "Come Retribution" kulcsot is.

Gilbert Vernam megpróbált javítani a módszeren, de az megmaradt ugyanilyen sebezhetőnek, ellenben sikerült egy elméletileg törhetetlen eljárást találnia, ami a Vigenère-kulcson alapul.

Ez a szócikk részben vagy egészben a Vigenère_cipher című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.

Elmélet[szerkesztés]

A Vigenère-rejtjelezés eredetileg a betűknek egy adott kulcs szerint táblázatból való kikeresését jelentette, azonban a csoportelmélet segítségével egyrészt sikerült matematikai alapokra helyezni, másrészt pedig a feltörését és annak nehézségét meghatározni.

Kódolás és dekódolás[szerkesztés]

A rejtjelezéshez a nyílt szövegen túl egy kulcsra is szükség van, aminek segítségével a kódolt szöveget létrehozzuk. A nyílt szöveget kulcs hosszúságú darabokra osztjuk, majd a darabok alá a kulcsot írva az egyes betűket egy táblázat megfelelő rovatából keressük ki. A táblázatban a Caesar-kódok vannak felsorolva, minden sorban egy-egy betűvel eltolva az előtte lévőt. A megfelelő kódolt karaktert a nyílt karakter oszlopában és a kulcs karakterének sorában találjuk.

Kódolási példa[szerkesztés]

Legyen a nyílt szöveg a Budapest felett az ég felhőtlen, a kulcs pedig Lojzi. Ekkor nem szükséges az összes kód-ábécét felsorolni, csak a megfelelőeket:

AÁBCDEÉFGHIÍJKLMNOÓÖŐPQRSTUÚÜŰVWXYZ
IÍJKLMNOÓÖŐPQRSTUÚÜŰVWXYZAÁBCDEÉFGH
JKLMNOÓÖŐPQRSTUÚÜŰVWXYZAÁBCDEÉFGHIÍ
LMNOÓÖŐPQRSTUÚÜŰVWXYZAÁBCDEÉFGHIÍJK
OÓÖŐPQRSTUÚÜŰVWXYZAÁBCDEÉFGHIÍJKLMN
ZAÁBCDEÉFGHIÍJKLMNOÓÖŐPQRSTUÚÜŰVWXY

A kódolás ekkor:

Nyílt szöveg:  BUDAPEST FELETT AZ ÉG FELHŐTLEN
Kulcs:         LOJZILOJ ZILOJZ IL OJ ZILOJZILO
Kódolt szöveg: NGNZWÖÉB ÉMÜQBS IK RŐ GMÜUXSSÖY

A dekódolás hasonlóan történik, a kulcs sorában megkeressük a megfelelő karaktert, és az oszlop betűjét írjuk helyette. Az máris világos, hogy az egykarakteres kulcs a klasszikus Caesar-rejtjelet adja vissza.

Sokkal érdekesebb azonban, hogy a rejtjelezés minden betűpárhoz egy meghatározott betűt rendel hozzá, méghozzá egyértelműen:

ahol A az ábécé. Ez feltűnően hasonlít a műveletekre, csak éppen a hagyományos műveletekkel ellentétben véges sok eredményünk lehet - igaz, véges sok "számból". A Vigenère-kód így analóg a szorzással vagy osztással, annyi kitétellel, hogy ha kifutunk az ábécéből, akkor az elején vissza kell jöjjünk. Ilyet a véges csoportok tudnak. Másrészt minden sorban szerepel az ábécé minden betűje, így az eltolások logikusan összeadásként értelmezhetőek. A kódolás tehát két, kissé absztrakt módon értelmezett szám összeadásaként fogalmazható meg, ez a számítógépes megvalósítás alapja is.

Mivel a kódot a címzettnek el kell tudnia olvasni, ezért a műveletnek megfordíthatónak kell lennie - ez a műveleti tulajdonságok miatt teljesül. A dekódolás így megfelel a kivonásnak, szokás szerint absztrakt értelmezéssel. Ezen okból szokott a kezdők bicskája beletörni, a Vigenère-kód ugyanis a számrejtvényekkel rokonítható matematikai feladat.

Ha nem eltolásos, hanem keveréses helyettesítést alkalmazunk, akkor a Bessieres-kódot kapjuk, ami ugyan nehezebben törhető, de nehezebb a kódolás és a dekódolás is.

Feltörés[szerkesztés]

A kódot a számtalan variációs lehetőség miatt sokáig feltörhetetlennek gondolták, azonban Leonhard Euler felfedezte, hogy a kulcsnál lényegesen hosszabb szöveg esetén periodikus ismétlődések lesznek a kódolt szövegben. Az összes periódus legnagyobb közös osztója lesz a kulcs hossza.[3] Ekkora darabokra bontva a szöveget a visszafejtés lényegesen egyszerűbbé válik.

A kódolt szöveget ugyanis a betűk helye szerint k csoportba osztjuk. Az első halmazba az 1., (k+1)-edik, (2k+1)-edik, stb., a másodikba a 2., (k+2)-dik, stb... karakterek kerülnek.[4] Ezek után a halmazokra gyakoriságanalízist végzünk, így a szöveg és a kulcs párhuzamosan fogja adni magát. Gyakorlott rejtjelfejtőnek gyakoriságtáblázat birtokában, nem túl hosszú kulcs esetén mintegy 6-9 órába telik megfejteni a kódolt szöveget.

A fenti eljárás akkor igazán hatékony, ha hosszú a szöveg és rövid a kulcs, azaz kevés faktorhalmaz van, sok elemmel. Éppen ezért célszerű olyan kulcsot választani, ami összemérhető a nyílt szöveg hosszával. Ha a kulcs azonos hosszúságú a szöveggel, akkor a fejtés reménytelen, esetleg új üzenetek elfogásával van csak esély a fejtésre. Ebben az esetben Vernam-kódról[5] beszélünk. Ha pedig a kulcs egyszer használatos, akkor egy bizonyítottan feltörhetetlen rendszert, a 'One-time Pad-et kapjuk. Ennek az egyetlen hátránya, hogy a legalább az első kulcsot mindenképpen valahogy el kell juttassuk a címzetthez.

Megvalósítások[szerkesztés]

Java nyelvű példa[szerkesztés]

Az alábbi példa rögzített módon tartalmazza a kódábécét, mivel elsősorban demonstrációs célból írták.

public class Vigenere{
    private String alphabeth="aábcdeéfghiíjklmnoóöőpqrstuúüűvwxyz" //Lusta vagyok Unicode-dal foglalkozni...
    
    private static char encode(char open, char shift){
        if( Caharcter.isLetter( open ){  //Vajon betű-e?
            return alphabeth.charAt( ( alphabeth.indexOf( open ) + alphabeth.indexOf( shift ) ) % alphabeth.length() );  //Itt történik a moduláris összegzés
        } else {
            return open; //Ha nem betű, nincs mit csinálni vele
        }
    }
    
    public static String encodeString(String openText, String cipherKey){
        public String cipherString = "";
    
        for(int i = 0; i < openText.length(); i++){
            cipherString.concat( Character.toString( encode( openText.charAt( i ), cipherKey.charAt( i % cipherKey.length() ) ) ) ); //Kicsit kerülő módon lehet összefűzni a karaktereket
        }
        
        return cipherString;
    }
}

Jegyzetek[szerkesztés]

  1. Röviden: a Caesar-kódolás csoportot alkot.
  2. Ez valójában a véges csoportok Cayley-táblázataihoz hasonlítható.
  3. Illetve annak osztója. Két periódus között ugyanis egész számszor kell szerepeljen a kulcs.
  4. Matematikában járatosabbak kedvéért: modulok k faktorhalmazokba osztjuk a betűket helyük szerint.
  5. Gilbert Vernam amerikai mérnök

Források[szerkesztés]

Külső hivatkozások[szerkesztés]