Tartalomjegyzék
Kriptográfia
- Szerző: Sallai András
- Copyright © Sallai András, 2011, 2014, 2015
- Licenc: GNU Free Documentation License 1.3
- Web: http://szit.hu
Bevezetés
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.
- Program01.java
class Program01 { public static String rot13(String input) { StringBuilder output = new StringBuilder(); for(int i=0;i<input.length();i++) { char ch = input.charAt(i); if(ch >= '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:
Ahol x a kódolandó karakter, az m a használt ábécé nagysága (angol ábécé esetén 26).
Dekódolás:
Az 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 5×5-ö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, 5×5-ö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