[[oktatas:kriptológia|< Kriptológia]] ====== Kriptográfia ====== * **Szerző:** Sallai András * Copyright (c) Sallai András, 2011, 2014, 2015 * Licenc: GNU Free Documentation License 1.3 * Web: http://szit.hu ===== Bevezetés ===== {{:oktatas:kriptológia:kodolaselvivazlata.png|}} Titkosítás rejtjelezés és adatrejtés. Rejtjelezés, sifrírozás angolosan: cipher, crypt. * titkos kulcsú kódolás - hagyományos kódolások * nyilvános kulcsú kódolás Igazi biztonságnak azt tekintjük, ha tetszőleges nyílt szöveg esetén is biztonságos a titkosítás. A kódolás mindig kétféle alapmódszeren alapszik: * helyettesítés - más szimbólumokkal helyettesítjük az eredetit * keverés - a sorrendben változtatunk ===== Hagyományos kódolás ===== Konvencionális vagy egykulcsos és szimetrikus blokk-kódolás néven is ismert. A nyílt adatból blokkokat készítünk. Legyen ez x. x = (x1,x2,x3,x4, ... xM) Ezt hívjuk plaintext-nek is. A titkosító egy algoritmussal ebből előállítja a titkosított szöveget. Legyen ez y y = (y1,y2,y3,y4, ... yN) Ezt hívjuk ciphertextnek angolul. A kódolás angolul encrypt. A titkosítást ez után jelöljük egy nagy "E" betűvel. A dekódolás angolul decrypt. A visszafejtést ez után jelöljük egy nagy "D" betűvel. A kódolást jelöljük Ek, ahol a k a titkosító algoritmus és annak inverze, amelyet ismételgetünk. Vagyis k = (k1, k2, k3, k4, ... kM Ezek után a kódolás így írható fel képlettel: y = Ek(x) A visszafejtés képlettel: x = Dk(y) ===== Helyettesítés ===== Betűnkénti helyettesítés A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B U R K O L A T C D E F G H I J M N P Q S V W X Y Z A felső ábécé alá írtam egy értelmes szót, amiben minden karakter csak egyszer fordul elő. Utána írtam az ábécé megmaradt betűit sorrendbe. Az üzenet olvasója tehát a **burkolat** szót kell, hogy ismerje az üzenet visszafejtéséhez. A "holnap reggel" szöveg ezek után így titkosítható: TIFHBJ NOAAOF A nyílt üzenet és a titkosított üzenet blokk hossza ugyanaz. Ha kihagyjuk a szóközöket az üzenet nehezebben visszafejthető: TIFHBJNOAAOF ===== Keverés ===== Más néven: Transzpozíció ==== Permutáció használata ==== A nyílt szöveget például 8 karakteres tömbökre osztjuk. A következő lépésben blokkonként kódolunk a következő permutáció szerint: 1 2 3 4 5 6 7 8 6 3 1 7 2 8 4 5 Az 1-es helyen lévő karaktert a 6-os helyre, a 2-es helyen lévő karaktert 3-as helyre, stb. A kulcs a megfejtéshez az aktuális permutáció. A módszer keverhető a helyettesítő módszerrel. A "holnap reggel" szöveg titkosítása: ^ Indexek ^^^^^^^^^^^^ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | ^ Nyílt szöveg ^^^^^^^^^^^^ | h | o | l | n | a | p | r | e | g | g | e | l | ^ Permutáció ^^^^^^^^^^^^ | 7 | 9 | 12 | 4 | 10 | 2 | 11 | 8 | 6 | 5 | 1 | 3 | ^ Kód ^^^^^^^^^^^^ | e | p | l | n | g | g | h | e | o | a | r | l | ===== Caesar titkosítás ===== Az eredeti Caesar titkosításban tulajdonképpen eltoljuk az ábécét 3 betűvel jobbra. | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | a | b | c | Az a betű helyett tehát d írok. A b betű helyett e-t. A hideg kódolása például: klghj Az ábécét megfeleltetjük számoknak is. | A = 0, B = 1, C = 2, ... Z = 25 | A nyílt szövegen karakterenként végrehajtjuk a következő műveletet: yi = xi + ki (mod 26) i = 1, 2, ..., M moduló összeadásával kódoljuk Dekódolás xi = yi-ki (mod 26) ===== ROT13 ===== Az eltolás mindig 13. {{:oktatas:programozás:algoritmusok:rot13.png|}} {{:oktatas:programozás:algoritmusok:rot13_titok.png|}} class Program01 { public static String rot13(String input) { StringBuilder output = new StringBuilder(); for(int i=0;i= 'a' && ch <= 'm') { output.append((char)(ch + 13)); }else if(ch >= 'n' && ch <= 'z') { output.append((char)(ch - 13)); }else if(ch >= 'A' && ch <= 'M') { output.append((char)(ch + 13)); }else if(ch >= 'N' && ch <= 'Z') { output.append((char)(ch - 13)); }else { output.append(ch); } } return output.toString(); } public static void main(String[] args) { System.out.println(rot13("titkos fogadas")); } } Linuxokon a játékok között található egy rot13 parancs, amely megvalósítja a titkosítást. Debian alapú rendszereken a telepítése: apt-get install bsdgames Használata: echo titok | rot13 ===== Affin rejtjelezés ===== Monoalfabetikus rejtjelezés. * 0 ≤ a * a ≤ 24 * (a,25) = 1 Kódolás: e(x) = (ax + b) mod m Ahol x a kódolandó karakter, az m a használt ábécé nagysága (angol ábécé esetén 26). Dekódolás: d(y) = a^{-1}(y - b) mod m Az a^{-1} reciproka az m-nek. Támadható gyakoriságelemzéssel. ===== Homofonikus titkosítás ===== A betűk gyakorisága alapján, még annyi kódot adunk az adott betűhöz, ahány százalékos a gyakorisága. ^ a ^ b ^ c ^ d ^ e ^ f ^ g ^ h ^ i ^ j ^ k ^ l ^ m ^ n ^ o ^ p ^ q ^ r ^ s ^ t ^ u ^ v ^ w ^ x ^ y ^ z ^ | 18 | 36 | 23 | 29 | 66 | 35 | 57 | 43 | 89 | 84 | 76 | 39 | 55 | 41 | 61 | 14 | 31 | 22 | 47 | 50 | 27 | 34 | 42 | 58 | 40 | 56 | | 53 | 73 | 64 | 54 | 82 | 77 | 69 | 94 | 33 | | | 30 | 74 | 92 | 67 | 32 | | 70 | 48 | 80 | 59 | | 45 | | 26 | | | 71 | | 60 | 72 | 95 | | | 24 | 99 | | | 97 | | 87 | 62 | | | 15 | 05 | 02 | 98 | | | | | | | 52 | | | 25 | 65 | | | 85 | 75 | | | 80 | | 63 | 79 | | | 01 | 16 | 07 | | | | | | | | 19 | | | | 37 | | | 86 | 78 | | | | | 81 | 88 | | | 20 | 04 | 17 | | | | | | | | 49 | | | | 83 | | | 96 | 68 | | | | | 90 | 93 | | | 03 | 13 | 10 | | | | | | | | 20 | | | | 12 | | | | | | | | | | 91 | | | | | 06 | | | | | | | | 51 | | | | 46 | | | | | | | | | | | | | | | 11 | | | | | | | | | | | | 28 | | | | | | | | | | | | | | | 21 | | | | | | | | | | | | 10 | | | | | | | | | | | | | | | | | | | | | | | | | | | 38 | | | | | | | | | | | | | | | | | | | | | | | | | | | 44 | | | | | | | | | | | | | | | | | | | | | | Törése: A nyelv jellegzetességeit keressük, minthogy az angolban a q után csak u állhat. ===== Vigenére ===== Polialfabetikus kód, többféle kódábécét használ. Giovan Batista Belaso írta le 1553-ban elsőként, de Blaise de Vigenère nevéhez fűzik. A különböző Caesar kódok használatához **Blaise de Vigenère** (1523 - 1596) francia diplomata, fordító, kriptológus és alkimista készített elsőként egy táblázatot, amely segít a kódolásban és a visszafejtésben. Különböző Caesar-kódok sorozatát használjuk, a következő táblázat alapján: ^ ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ J ^ K ^ L ^ M ^ N ^ O ^ P ^ Q ^ R ^ S ^ T ^ U ^ V ^ W ^ X ^ Y ^ Z ^ ^ A | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | ^ B | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | ^ C | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | ^ D | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | ^ E | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | ^ F | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | ^ G | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | ^ H | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | ^ I | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | ^ J | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | ^ K | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | ^ L | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | L | ^ M | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | ^ N | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | ^ O | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | ^ P | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | ^ Q | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | ^ R | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | ^ S | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | R | R | ^ T | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | ^ U | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | ^ V | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | ^ W | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | ^ X | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | ^ Y | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | ^ Z | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Legyen a lekódolandó szöveg "reggel támadunk". Választok egy kulcsot, mondjuk titok. Leírom ismétlések nélkül: tiok Utána írom a fennmaradó ábécét: tiokabcdefghjl Csak az l betűig írtam le, de nem is lesz többre szükség. Aláírom a kódolandó szöveget: tiokabcdefghjl reggeltamadunk Az r betű titkosítása: Az r-dik sorban megkeresem a t-dik betűt: h A következő e-dik sorban, megkeresem az i-dik betűt. ===== Kircher-féle rejtjel ===== Polialfabetikus helyettesítés, amely a Vigenére rejtjelen alpszik. Athanasius Kircher dolgozta ki, aki 1602 és 1680 között élt jezsuita páter. A XVII. században jelentős tudós. A Vigenére rejtjelezéssel teljesen megegyezik, de a kód betűi helyett azok ábécében elfoglalt helyét írjuk fel. Az eljárás az eredeti szöveg növekedésével jár. ===== Véletlen átkulcsolás ===== One-time pad (OTP) Magyarul szokták még "egyszeres átkulcsolás" néven emlegetni. A titkosítandó szöveg mindenegyes karakteréhez külön kódot rendelek. A kulcs hossza így megegyezik a tisztaszöveg hosszával. Elméletileg és gyakorlatilag törhetetlen, mivel semmilyen összefüggés nem ismerhető fel a titkosított szöveg egyes karakterei között. ===== Playfair-rejtjel ===== **Digrafikus** helyettesítő rejtjel. 1854-ben Charles Wheatstone találta fel, de legfőbb támogatójának, Lord Playfairnek a nevét viseli. Az ábécét felírjuk egy 5x5-ös mátrixba: | a | b | c | d | e | | f | g | h | i | j | | k | l | m | n | o | | p | r | s | t | u | | v | w | x | y | z | A titkosítandó szöveget betűpárokba rendezzük. Legyen a titkosítandó szöveg például: holnap nyitas Betűpárokat alakítunk ki: ho ln ap ny it as Vegyük az első betűpárt. A h és az o egy különböző sorban és oszlopban vannak, és meghatározzák egy négyzet bal felső és jobb alsó sarkát. Ennek a négyzetnek veszem a jobb felső és bal alsó sarkát, az itt lévő betűk lesznek a kódok. jm A következő betűpáros az ln. Elhelyezkedésüket tekintve nem alkotnak négyzetet, mert egy sorban vannak. Ilyenkor j betű helyett a j után következő betűt írom le, az m helyett az az utána következőt. Ha az ma a tábla végén lenne, akkor a vele azonos sorban a tábla első oszlopában lévő betűt írom le. jm mo A következő betűpár az ap. Az ap sem alkot négyzetet a táblázatban, mert a két betű egy oszlopban van. Így az mindkét betű alatt lévő betűket írom fel. Ha egyik betű az utolsó sorban lenne, akkor az első sor betűjét írom fel. jm mo fv A fenti gondolatmenetet követve a végső kód: jm mo fv td ny cp ===== Négy négyzet-rejtjel ===== Készítünk négy négyzetet, 5x5-ös mátrixokból, egy-egy sorban két négyzetet elhelyezve: | a | b | c | d | e ^ | k | a | r | o | m | | f | g | h | i | j ^ ::: | b | c | d | e | f | | k | l | m | n | o ^ ::: | g | h | i | j | l | | p | r | s | t | u ^ ::: | n | p | s | t | v | | v | w | x | y | z ^ ::: | u | w | x | y | z | ^ ^^^^^^^^^^^ | g | o | m | b | a ^ | a | b | c | d | e | | c | d | e | f | h ^ ::: | f | g | h | i | j | | i | j | k | l | n ^ ::: | k | l | m | n | o | | p | r | s | t | u ^ ::: | p | r | s | t | u | | v | w | x | y | z ^ ::: | v | w | x | y | z | Így egy nagyobb négyzetet kapunk. A bal felső és a jobb alsó négyzet a szimpla ábécé, q nélkül. Az angol ábécéből kihagyható a q vagy egynek tekinthető az i és a j, mivel csak 25 helyünk van. A jobb felső és a bal alsó négyzetben elhelyezek egy-egy kulcsszót. A kulcsszó elhelyezhető a bal felső sarokból kezdve, balról jobbra, vagy spirálalakban is. Ha kulcsszóban ismétlődik egy betű, akkor azt kihagyjuk. A ki nem töltött helyeket az ábécé maradék betűivel töltöm fel. Legyen a kódolandó szöveg: holnap nyitas Betűpárokat alakítunk ki: ho ln ap ny it as Vegyük az első betűpárt, a ho-t. Az első betűjét a h-t, megkeresem a bal felső mátrixban. A második betűjét a jobb alsó mátrixban keresem meg: | a | b | c | d | e ^ | k | a | r | o | m | | f | g | **h** | i | j ^ ::: | b | c | d | e | f | | k | l | m | n | o ^ ::: | g | h | i | j | l | | p | r | s | t | u ^ ::: | n | p | s | t | v | | v | w | x | y | z ^ ::: | u | w | x | y | z | ^ ^^^^^^^^^^^ | g | o | m | b | a ^ | a | b | c | d | e | | c | d | e | f | h ^ ::: | f | g | h | i | j | | i | j | k | l | n ^ ::: | k | l | m | n | **o** | | p | r | s | t | u ^ ::: | p | r | s | t | u | | v | w | x | y | z ^ ::: | v | w | x | y | z | Kikeresem a h sorát hol keresztezi az o oszlopa a jobb felső mátrixban. Az f-nél. Akkor ez az első kódszó. A h oszlopát az o sora a bal alsó mátrixban a k-nál keresztezi, ezért a következő kódszó a k betű. | a | b | c | d | e ^ | k | a | r | o | m | | f | g | **h** | i | j ^ ::: | b | c | d | e | **//f//** | | k | l | m | n | o ^ ::: | g | h | i | j | l | | p | r | s | t | u ^ ::: | n | p | s | t | v | | v | w | x | y | z ^ ::: | u | w | x | y | z | ^ ^^^^^^^^^^^ | g | o | m | b | a ^ | a | b | c | d | e | | c | d | e | f | h ^ ::: | f | g | h | i | j | | i | j | **//k//** | l | n ^ ::: | k | l | m | n | **o** | | p | r | s | t | u ^ ::: | p | r | s | t | u | | v | w | x | y | z ^ ::: | v | w | x | y | z | fk A fenti sémát követve, a teljes kódszöveg: fk jj kp jy et rp Az eredeti szöveg: holnap nyitas Kódolva: fkjjkpjyetrp ===== Nyilvános kulcsú titkosítás ===== {{:oktatas:kriptológia:nyilvanoskulcs.png|}}