Primeri iz kriptografije

Vsebina

Uvod
Transpozicijske metode
Enostavne substitucijske metode
Homofonične substitucijske metode
Polialfabetične substitucijske metode
5.1 Rotorski stroji
Vir
Literatura o kriptografiji v slovenščini

1. Uvod

Ogledali si bomo nekaj različnih preprostejših primerov kriptografskih metod, ki jih zasledimo v zgodovini. Povzeti so iz zbornika, ki ga lahko dobite v Komisiji za tisk DMFA.

2. Transpozicijske metode

Transpozicijske metode preuredijo niz znakov glede na neko shemo. Zgodovinsko gledano je bila ta preureditev osnovana na neki geometrijski figuri. Šifriranje poteka v dveh korakih:

čistopis

vpis
Ž

geometrijska figura

izpis
Ž

tajnopis

Najprej se čistopis vpiše v figuro glede na vpisno shemo, v drugem koraku pa se tajnopis iz figure izpiše po neki dogovorjeni izpisni poti. Figura je bila velikokrat kar dvorazsežna matrika. Primer kaže slika 1.

1	2	3	4
R	A	Č	U
N	A	L	N
I	Š	T	V
O	T	R	I

Slika 1: Primer transpozicijske metode z matriko 4×4, čistopisom
RAČUNALNIŠTVO TRI, izpisno potjo branja stolpcev v vrstnem
redu 4-2-3-1 in posledično tajnopisom UNVIAAŠTČLTRRNIO.

Veliko transpozicijskih metod permutira znake čistopisa s fiksno periodo d. Naj bo N_d množica prvih d naravnih števil in p : N_d Ž N_d permutacija nad N_d. Ključ metode je par K = (d,p). Besedilo šifriramo tako, da glede na p permutiramo njegove d dolge odseke. Torej čistopis izgleda takole:

M = m₁ m₂ ... m_d m_d+1 ... m_2d ... , njegov tajnopis pa takole:

E_K (M ) = m_p(1) m_p(2) ... m_p(d) m_d+p(1) ... m_d+p(d) ... .

Tajnopis dešifriramo z inverzno permutacijo p¹. Primer nam prinaša slika 2.

M	=	RAČU	NALN	IŠTV	OTRI
E_K(M )	=	ČRUA	LNNA	TIVŠ	ROIT

Slika 2: Primer permutacijskega šifriranja pri podatkih d = 4 in permutaciji
p = ( 2 4 1 3 ). Besedilo torej razdelimo na odseke dolžine 4, potem pa v
vsaki četverici (po permutaciji p) zamenjamo vrstni red znakov. Iz čistopisa
RAČUNALNIŠTVO TRI dobimo tajnopis ČRUALNNATIVŠROIT.

Kriptoanalitik lahko hitro ugotovi, kdaj ima opravka s transpozicijsko metodo, ker se v tem primeru relativne frekvence znakov v tajnopisu približno ujemajo s pričakovanimi frekvencami, ki so značilne za jezik čistopisa. Proces razbijanja je v tem primeru kar reševanje anagramov. Pri tem si lahko zelo pomagamo z upoštevanjem relativne pogostosti pojavljanja digramov (dveh zaporednih znakov) in trigramov (treh zaporednih znakov).

3. Enostavne substitucijske metode

Enostavne substitucijske metode zamenjajo vsak znak čistopisa z ustreznim znakom tajnopisa. Za šifriranje uporabljamo bijektivno funkcijo f, ki preslika vsak znak iz abecede čistopisa A = {a₀, a₁, ..., a_n1} v abecedo tajnopisa B = { f (a₀), f (a₁), ... , f (a_n1)}. Ključ take metode je seveda funkcija f. Šifrirano sporočilo izgleda potem takole:

E_K(M ) = f (m₁) f (m₂) ... . Primer najdemo na sliki 3.

Funkcija f: A Ž B je podana z naslednjima abecedama:

A:	ABC	ČDE	FGH	IJK	LMN	OPR	SŠT	UVZ	Ž
B:	SLO	VEN	IJA	MDŽ	BCČ	FGH	KPR	ŠTU	Z

Slikanje besedila:

M = R A Č U N A L N I Š T V O T R I
E_f(M ) = H S V Š Č S B Č M P R T F R H M

Slika 3: Primer šifriranja pri podani funkciji f in ključni besedi
SLOVENIJA MOJA DEŽELA. Črke, ki se ponovijo, izpustimo,
tiste, ki pa ne nastopijo v ključni besedi, razporedimo po vrsti v
abecedo tajnopisa. Iz čistopisa RAČUNALNIŠTVO TRI smo
tako dobili tajnopis HSVŠČSBČMPRTFRHM.

Metode, ki temeljijo na premaknjeni abecedi, krožno premaknejo znake desno za k mest, to je

f (a) = a + k (mod n) .

Pri tem pomeni n velikost abecede A (v slovenščini je n = 25 in a pomeni znak iz abecede A. Ta tip šifriranja je uporabljal Julij Cezar pri k = 3 in se po njem tudi imenuje. Primer za k = 10 najdemo na sliki 4.

Zamik abecede:

A:	ABC	ČDE	FGH	IJK	LMN	OPR	SŠT	UVZ	Ž
f (A):	JKL	MNO	PRS	ŠTU	VZŽ	ABC	ČDE	FGH	I

Potek šifriranja:

M = R A Č U N A L N I Š T V O T R I
E_f(M ) = C J M F Ž J V Ž Š D E G A E C Š

Slika 4: Primer Cezarjeve metode za k = 10. Iz čistopisa RAČUNALNIŠTVO TRI
smo dobili tajnopis CJMFŽJVŽŠDEGAECŠ.

Možne so seveda še bolj zapletene preslikave. Nekatere temeljijo na množenju in so oblike:

f (a) = ak (mod n),

kjer morata biti k in n tuji, da je potem moč zaloge vrednosti f enaka n. Če oba zadnja primera združimo, dobimo afino preslikavo:

f (a) = ak₁ + k₀ (mod n).

Preslikave višjih redov so polinomske s stopnjo t:

f (a) = a^tk_t + a^t1k_t1 + + ak₁ + k₀ (mod n).

Za abecedo tajnopisa lahko uporabljamo tudi nestandardne znake, na primer grafične ali glasbene znake.

V splošnem so substitucijske kriptografske metode lahko rešljive, ker primerjamo relativne frekvence znakov tajnopisa s pričakovanimi, pogamo si s pogostostjo digramov in trigramov. Potem, ko najdemo nekaj substitucijskih parov, nam ostane še reševanje sistema kongruenčnih enačb.

4. Homofonične substitucijske metode

Homofonične substitucijske metode preslikajo vsak znak abecede čistopisa v množico znakov abecede tajnopisa. Elementi f (a), v katere se lahko preslika isti a, se imenujejo homofoni. Preslikava f je naslednje oblike f : A Ž P(B). Čistopis M = m₁ m₂ ... se šifrira v tajnopis E_f(M ) = b₁b₂ ..., kjer je b_i izbran slučajno iz množice homofonov f (m_i). Primer prikazuje slika 5.

Za homofone uporabimo števila od 1 do 99. Za uporabljene črke jih izberimo takole:

A:	09	17	19	34	K:	03	83
E:	41	56			M:	02	44	76
I:	60	67			T:	15	27	32

Šifriranje:

M = M A T E M A T I K A
E_f(M ) = 76 19 27 56 02 34 32 60 83 17

Slika 5: Primer šifriranja s pomočjo homofonov. Tako lahko dosežemo,
da se znaki v tajnopisu ne ponavljajo enako kot v čistopisu. Iz čistopisa
MATEMATIKA smo dobili tajnopis 76 19 27 56 02 34 32 60 83 17.

Homofonične tajnopise je mnogo težje razbiti kot tajnopise enostavnih substitucijskih metod, še posebno če je število homofonov, ki so prirejeni črkam, sorazmerno z njihovo relativno pogostostjo pojavljanja v čistopisu. V tem primeru bo porazdelitev pojavitev tajnopisnih znakov precej podobna enakomerni porazdelitvi, kar onemogoča statistično analizo. Še vedno pa je možna uporaba porazdelitve digramov v tajnopisu.

Očitno je metodo težje razbiti, če priredimo črkam več simbolov. V skrajnem primeru, ko vsaki črki čistopisa priredimo enkraten simbol tajnopisa, jo je povsem nemogoče ugnati.

5. Polialfabetične substitucijske metode

Enostavne substitucijske metode so občutljive na kriptografsko analizo, ker ohranjajo porazdelitev frekvenc črk v abecedi. Homofonične metode zakrivajo to porazdelitev z definiranjem več tajnopisnih znakov za vsako črko. Polialfabetične metode pa jo skrivajo z uporabo več substitucij.

Največkrat so polialfabetične metode periodične substitucijske metode. Na podlagi periode d vzamemo d abeced B₁, B₂, ..., B_d. Če je f_i: A Ž B_i preslikava iz abecede čistopisa A v i-to abecedo tajnopisa B_i, šifriramo sporočilo

M = m₁m₂ ... m_dm_d+1 ... m_2d ... v tajnopis E(M ) = f₁(m₁) ... f_d(m_d) f₁(m_d+1) ... f_d(m_2d)... .

Če je d = 1, je metoda monoalfabetična in enaka enostavni substitucijski.

5.1 Rotorski stroji

Rotorski stroji izvajajo polialfabetične substitucijske kriptografske metode z dolgo periodo. Rotorski stroj vsebuje t rotorjev ali obročev. Obod vsakega obroča R_i ima 25 kontaktov (za vsako črko enega) na sprednji in zadnji površini. Vsak kontakt spredaj je povezan z enim kontaktom zadaj, kar določa preslikavo f_i iz čistopisa v tajnopis. R_i se lahko zavrti v 25 različnih položajev, vsak položaj pa določa novo preslikavo. Ko je R_i v položaju j_i, je preslikava določena z

F_i(a) = ( f_i(a j_i) mod 25 + j_i) mod 25.

Vsaka črka vstopa v prvi rotor, potuje skozi naslednje rotorje in izstopi kot element tajnopisa na drugi strani. Stroj s t rotorji tako določa substitucijsko metodo, ki jo sestavljajo preslikave F₁, ..., F_t. Črko m_i sporočila M = m₁m₂ ... se šifrira takole:

E_{k_i}(m_i) = F_t(...F₂( F₁(m_i))...),

kjer k_i določa preslikave f₁, ..., f_t in položaje j₁, ..., j_t vseh rotorjev. Po vsaki šifrirani črki zamenjamo lego enemu ali več rotorjem in s tem spremenimo ključ. Rotorski stroj s t rotorji ponovi isti ključ po 25^t zaporednih šifriranih črkah.

Rotorski stroji generirajo dolge nize ključev, pa kljub temu niso neobčutljivi na kriptografsko analizo. Uporabljali so jih Nemci v drugi svetovni vojni, ki so svoj stroj poimenovali Enigma. Imel je 210²⁰ uporabniško nastavljivih ključev, kar je več, kot jih ima danes najbolj razširjen postopek DES, a so ga zavezniške sile vseeno uspele razvozlati.

6. Vir

B. B. Lavrenčič in Tomaž Pisanski: Zbornik referatov Delavnice o varovanju (elektronskih) podatkov, DMFA, Ljubljana 1995.

7. Literatura o kriptografiji v slovenščini

Šifriranje - zanesljivo varovanje, Cifra Komunikacijski sistemi d.o.o., Ljubljana 1994.
Mario Korva in Mitja Zornada: Učinkovita kripto zaščita in izmenjava dokumentov po modemskih komunikacijah, Cifra Komunikacijski sistemi d.o.o., Ljubljana 1995.
B. Magajna: Tajnopisi, Obzornik za matematiko in fiziko 38 (1991), strani 9-18, DMFA, Ljubljana.
Marija Vencelj: Šifriranje z javnim ključem, Presek 22 (1994/1995), strani 354-357, DMFA, Ljubljana.
Marija Vencelj: To in ono o tajnopisih, Presek 22 (1994/1995), strani 257-263, DMFA, Ljubljana.
Boštjan Vilfan: Izbrani sestavki iz teorije avtomatov in jezikov, I. del, strani 33-53, Fakulteta za elektrotehniko in računalništvo, Ljubljana 1995.
J. Zupan: Nekaj o kriptografskih metodah, Obzornik za matematiko in fiziko 25 (1978), strani 129-136, DMFA, Ljubljana.

ensa 1996. Zadnji popravek dne 25. avgusta 1998. Obiskov: