Vigenère-rejtjel
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ésA 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ère 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 Carroll egy gyermekújságban megfejthetetlennek nevezte a titkosítást, holott már 1854-ben 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ésA 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ésA 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ésLegyen 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 LMNOÓÖŐPQRSTUÚÜŰVWXYZAÁBCDEÉFGHIÍJK OÓÖŐPQRSTUÚÜŰVWXYZAÁBCDEÉFGHIÍJKLMN JKLMNOÓÖŐPQRSTUÚÜŰVWXYZAÁBCDEÉFGHIÍ ZAÁBCDEÉFGHIÍJKLMNOÓÖŐPQRSTUÚÜŰVWXY IÍJKLMNOÓÖŐPQRSTUÚÜŰVWXYZAÁBCDEÉFGH
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Ő ÉMÜ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ésA 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ésC nyelven
szerkesztésAz 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 nyelven
szerkesztésAz 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 static String alphabet = "aábcdeéfghiíjklmnoóöőpqrstuvwxyz";
private static char encode(char open, char shift) {
if (Character.isLetter(open)) { //Vajon betű-e?
return alphabet.charAt((alphabet.indexOf(open) + alphabet.indexOf(shift)) % alphabet.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) {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < openText.length(); ++i) {
stringBuilder.append(Character.toString(encode(openText.charAt(i), cipherKey.charAt(i % cipherKey.length())))); //Kicsit kerülő módon lehet összefűzni a karaktereket
}
return stringBuilder.toString();
}
public static void main(String[] args) {
String a = "menekuljetekmertjonazellenseg";
String b = "ezakulcsszo";
System.out.println(encodeString(a, b));
}
}
Jegyzetek
szerkesztés- ↑ Röviden: a Caesar-kódolás csoportot alkot.
- ↑ Ez valójában a véges csoportok Cayley-táblázataihoz hasonlítható.
- ↑ Illetve annak osztója. Két periódus között ugyanis egész számszor kell szerepeljen a kulcs.
- ↑ Matematikában járatosabbak kedvéért: modulok k faktorhalmazokba osztjuk a betűket helyük szerint.
- ↑ Gilbert Vernam amerikai mérnök
Források
szerkesztés- Megyesi Zoltán: Titkosírások. Kisújszállás: Szalay. 1999. ISBN 963 9178 85 3
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. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
