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.

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]

C nyelvű példa[szerkesztés]

Az alábbi példában csak az angol ábécé kis- és nagybetűivel dolgozunk. Legyen a kódolandó nyílt szöveg menekuljetekMERTjonAZellenseg, a kulcs pedig EZaKULCSSZO. Ekkor a következő kódolt szöveget kapjuk: qdnoefnbwssoLEBNuqfSYspkexmpi. Dekódolásnál a dekódolandó szöveg legyen QdnoefnbwssoLebnUqfSySpkexmpi, a kulcs pedig ne változzon. Ekkor a dekódolt szövegünk MenekuljetekMertJonAzEllenseg lesz.

#include <stdio.h>
int main(){
	int i=0,j=0,k=0,d=0;
	char c;
	char kulcs[128];                                        //127 karakter + a stringet lezáró karakter (\0)
	char szoveg[256];                                       //255 karakter + a stringet lezáró karakter (\0)
    printf("[K]odolni vagy [D]ekodolni szeretnel? (K/D)\n");
    scanf("%c",&c);
    printf("Kerem a kulcsot!\n");
    scanf("%s",kulcs);
    printf("Kerem a nyilt szoveget!\n");
    scanf("%s",szoveg);
	for(k=0;kulcs[k] != '\0';k++){                          //Kisbetű->nagybetű konvertálás a kulcsban
		if(kulcs[k] >= 'a' && kulcs[k] <= 'z')
			kulcs[k] = kulcs[k] - 32 ;
        d++;
	}
	if(c == 'K'){                                           //Itt kódolunk
		while(szoveg[i] != '\0'){
			if(j == d){
			j = 0;
			}
			if(szoveg[i] >= 'a' && szoveg[j] <= 'z'){       //A eset: a nyílt szöveg karaktere kisbetű
			if(((szoveg[i]-97)+(kulcs[j]-65)) <= 25){
				szoveg[i] = szoveg[i] + (kulcs[j]-65);}
			else{
				szoveg[i] = szoveg[i] + (kulcs[j]-65)-26;}
			}
			if(szoveg[i] >= 'A' && szoveg[i] <= 'Z'){       //B eset: a nyílt szöveg karaktere nagybetű
			if((szoveg[i] - 65)+(kulcs[j]-65) <= 25){
				szoveg[i] = szoveg[i] + (kulcs[j] - 65);}
			else{
				szoveg[i] = szoveg[i] + (kulcs[j]-65)-26;}
			}
            i++;
            j++;
    }
	printf("A kodolt szoveg: %s\n",szoveg);
    }else if(c == 'D'){                                     //Itt dekódolunk
        while(szoveg[i] != '\0'){
            if(j == d){
            j = 0;}
            if(szoveg[i] >= 'a' && szoveg[j] <= 'z'){
            if((szoveg[i] - 97)-(kulcs[j]-65)>=0){          //A eset: a dekódolandó szöveg karaktere kisbetű
                szoveg[i] = szoveg[i] - (kulcs[j] - 65);}
            else{
                szoveg[i] = szoveg[i] - (kulcs[j] - 65) + 26;}
            }
            if(szoveg[i] >= 'A' && szoveg[i] <= 'Z'){       //B eset: a dekódolandó szöveg karaktere nagybetű
            if((szoveg[i] - 65)-(kulcs[j]-65)>=0){
                szoveg[i] = szoveg[i] - (kulcs[j] - 65);}
            else{
                szoveg[i] = szoveg[i] - (kulcs[j] - 65) + 26;}
            }
			i++;
			j++;
    }
	printf("A kodolt szoveg: %s\n",szoveg);
	}
    return 0;
    }

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]

Fordítás[szerkesztés]

  • 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.

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