Debreceni Egyetem
Természettudományi és Technológiai Kar
Matematikai IntézetDie-Hellman algoritmus
csoportgy¶r¶kben és moduló 1
készítette:

Ferenczi Fruzsina

témavezet®: Dr. Tengely Szabolcs

Debrecen, 2016

Tartalomjegyzék

Tartalomjegyzéki

1 Bevezet®
1.1. A csoportgy¶r¶kr®l . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. A kriptográáról és a közös kulcsgenerálásról . . . . . . . . . . . .

3
3
5

2 Közös kulcsgenerálás csoportgy¶r¶k feletti mátrixokban
2.1. A felépítésr®l . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. A közös kulcsgenerálás menetér®l . . . . . . . . . . . . . . . . . . .
2.3. A közös kulcsgenerálás bemutatása választott példán . . . . . . . .

7
7
7
8

3 Arin-Abu kriptorendszer
11
3.1. Az AAβ felépítésének menetér®l . . . . . . . . . . . . . . . . . . . . 11
3.2. Az AAβ bemutatása választott példán . . . . . . . . . . . . . . . . 12
4 Az Arin-Abu rendszer törése
13
4.1. Röviden a lánctörtekr®l . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2. A diszkrét logaritmus probléma megoldásáról moduló 1-ben . . . . 13
4.3. A megfelel®en közeli konvergensválasztásról, és a hibahatárról . . . 14
4.4. A diszkrét logaritmus probléma megoldása moduló 1-ben, választott példán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5 Sage kódok

17

Irodalomjegyzék

27iKöszönetnyilvánítás

Köszönettel tartozom családomnak az eddigi egyetemi éveim alatt nyújtott támogatásukért és türelmükért.
Továbbá szeretném megköszönni az oktatóim problémára való nyíltságát, és segítségüket abban, hogy fenntartsam a szenvedélyemet a matematika iránt.

11. Bevezet®

A matematika hasznos, és szerethet®. Azonban sokszor találkozunk az érdekl®dés
felkeltésének hiányával, vagy a motiváció elvesztésével.
Gyakran a matematika szerethet®ségének megtapasztalásában az érdekl®d®keta feszes, nagyszámú tételek és fogalmak megállítják. Sokszor hosszú tételsorok
után is az elért eredmény kevésbé látványos egy felületesebben a témában szemlél®d®nek annál, mint hogy motivációt érezzen a megértésre és a folyatásra.
Szakdolgozatomban a reál érdekl®dés¶ emberek gyelmét és szeretetét szeretnémújra felébreszteni a matematika iránt azzal, hogy a tételek és deníciók helyett a
metódusokat, megértést segít® és interaktív példákat helyezem el®térbe. Ehhez
korunk próbálkozásaival és eredményeivel egy közkedvelt és tapasztalati tudományágat, a kriptográát (nagyvonalakban a kódírás, -fejtés, -törés) választottam.
Ebben a fejezetben egy összetettebb matematikai struktúra, a csoportgy¶r¶ kerül
bemutatásra, m¶veleteivel egyetemben. Továbbá a közös kulcsgenerálás lépéseit,hasznosságának tárgyalását is magába foglalja. Ezek az alapok képzik a dolgozat
els® tárgyalt titkosításának alapját.

1.1. A csoportgy¶r¶kr®l
A dolgozat els® kriptorendszerének mátrixai csoportgy¶r¶elemekb®l épülnek fel,így érdemes a csoportgy¶r¶ fogalmának áttekintésével kezdenünk.

1.1.1. Deníció. Egy csoport egy olyan (G, ∗) rendezett pár, ahol G egy halmaz
és a ∗ egy olyan bináris m¶velet G-n, amely teljesíti a következ® tulajdonságokat:• Asszociatív. (x ∗ (y ∗ z) = (x ∗ y) ∗ z minden x, y, z ∈ G-re.)• Invertálható. (Létezik egy olyan e ∈ G elem, amelyre e ∗ x = x és x ∗ e = xminden x ∈ G esetén, és minden x ∈ G esetén létezik egy olyan y ∈ G elem
amelyre x ∗ y = e és y ∗ x = e.)

Megjegyzés. Abel-csoport, más néven kommutatív csoport az olyan csoport, amelyekben a csoportm¶velet kommutatív.
Megjegyzés. Multiplikatív csoportról beszélünk, ha ∗ szorzás.
3

4

FEJEZET 1.

BEVEZET

Megjegyzés. Egy G halmaz a rajta értelmezett ∗ m¶velettel félcsoport, ha a halmaz
zárt a m¶veletre nézve és a m¶velet asszociatív.

1.1.2. Deníció. A két kétváltozós m¶velettel rendelkez® (R, +, ∗) struktúrákatgy¶r¶nek nevezünk, ahol (R, +) Abel csoport,(R, ∗) félcsoport, tovább a disztributivitás fennáll a m¶veletekre (minden x, y, z ∈ R-re x ∗ (y + z) = (x ∗ y) + (x ∗ z),és (x + y) ∗ z = (x ∗ z) + (y ∗ z)).
1.1.3. Deníció. Legyen G egy multiplikatív csoport, és R egy egységelemesasszociatív gy¶r¶. Jelölje
R[G] := {u|u : G → R, #{g ∈ G|u(g) 6= 0} < ∞}azon függvények halmazát, amelyben az u és v függvények akkor egyenl®k, hav(g) = u(g) teljesül ∀g ∈ G-re.

1.1.4. Deníció. A függvények összegét és szorzatát a következ®képpen deniálP
hatjuk (u + v)(g) := u(g) + v(g)-t és (u ∗ v)(g) := h∈G u(h) ∗ v(h−1 ∗ g).
1.1.5. Deníció. Az R[G] a két (jóldeniált) m¶veletre gy¶r¶t alkot, és ezt
nevezzük csoportgy¶r¶nek.
Ezt követ®en a választott u ∈ R[G] függvénynek egyértelm¶en megfeleltethet®
a :=Xu(g) ∗ g

g∈G

formális összegre térünk át. A formális összegként kezelt függvényekkel a bevezetettösszeadást és szorzást is újradeniáljuk:

1.1.6. Deníció. Legyeneka :=Xu(g) ∗ g

b :=

g∈G

X

v(g) ∗ gg∈Ga, b tetsz®leges u, v ∈ R[G] elemeknek megfeleltethet®ek. Ekkor:X
X X
a + b =:
(u(g) + v(g)) ∗ ga ∗ b =:(u(h) ∗ v(h−1 ∗ g) ∗ g
g∈Gg∈G h∈g.
Ezek ismeretében a következ® fejezetekben már áttérhetünk a Zm [Sn ], n, m ∈N/{1} csoportgy¶r¶k tárgyalására, és ezen belül is az n = 3, m = 7 könnyen
kezelhet® esetre.
Végezetül, tekintsük a következ® példát:
a = 2(1, 2) + 4(1, 2, 3)

b = 6(2, 3)

1.2.

A KRIPTOGRÁFIÁRÓL ÉS A KÖZÖS KULCSGENERÁLÁSRÓL

5

a + b = 6(2, 3) + 2(1, 2) + 4(1, 2, 3)a ∗ b = 2(1, 2) + 4(1, 2, 3) + 5(1, 3, 2) + 3(1, 3) 6= b ∗ a = 5(1, 2) + 2(1, 2, 3)

1.2. A kriptográáról és a közös kulcsgenerálásról
A kriptológia a biztonságos kommunikáció tudománya. Két ága a kriptográaés a kriptoanalízis. A kriptográa olyan módszerekkel foglalkozik, melyek biztosítják az üzenetek védettségét és hitelességét. Alapja a bet¶k átrendezése és
helyettesítése. A kriptoanalízis a kódolt szövegek kulcs nélküli megfejtését jelenteti.
A kriptográában az I. világháború alatt számos eljárást dolgoztak ki, éstörtek fel rövid id®n belül. A II. világháború alatt megkezd®dött a titkosító gépek
tömeges alkalmazása, ami nagy lendületet adott a matematika és az informatika fejl®désének. A rejtjelez® eszközökre híres példa a második világháborúban anémet Enigma, a japán Purple,a brit Typex, és az amerikai SIGABA, továbbá anavahó indiánok nyelve is.
Modern kriptográa a számítógép létrejöttével gyorsabb és hatékonyabb kódolásra képes. Emellett a kódolás alapja bináris, különböz® kódokkal, például
ASCII-vel készül a kódolás. Az Amerikai Szabványügyi Hivatal pályázatot írt ki,
és szabványnak a DES-t választotta, egy szimmetrikus kulcsú rejtjelezést. A kulcs
szétosztása csak személyesen volt biztonságos. Ezt a problémát a kulcsmegosztás
hidalta át [1].
A dolgozat els® kriptorendszerének váza az 1970-es években megalkotott DieHellman közös kulcsgenerálás, ezért kitérünk az algoritmus általánosított felépítésére.

Megjegyzés. A rendszerek bemutatása és használata során legyen A fél, azaz a
kommunikációt kezd® fél neve Alice, az Alice üzenetét fogadó B fél neve pedig
Bob, a kriptográa hagyományait követve.
A szimmetrikus titkosítás lépései (nagyvonalakban) a következ®k:• Alice valamilyen biztonságos csatornán eljuttatja a titkos kulcsát Bobnak.
• Alice a titkos kulccsal kódolja az üzenetet, majd közzéteszi.
• Végül Bob a titkos kulcs segítségével visszakódolja.

A szimmetrikus titkosítók els® lépésének támadhatósága motiválta Whiteld
Die és Martin Hellman közös kulcsgeneráló módszerét:• Adott egy nyilvános üzenet.

6

FEJEZET 1.

BEVEZET• Mindkét fél titkosítja egy saját, titkos kulccsal az üzenetet, majd közzéteszi.
• Ezután egymás kódolt üzenetét a saját kulcsukkal továbbkódolva, mindket-t®jüknek ugyanaz a duplán kódolt üzenet áll rendelkezésére.

Így a kódolt üzenet kezelhet® közös kulcsként egy szimmetrikus titkosításnál.

Megjegyzés. Ezzel a módszerrel a komplett kommunikáció is lebonyolítható:
Alice az A kulcsával titkosítja az üzenetet. Ekkor Eve nem tudja elolvasni az A
kulcs ismerete nélkül.
Bob sem tudja visszafejteni, ezért a saját B kulcsa segítségével tovább alakítja azüzenetet. Eve ekkor a két kulcs ismeretének hiányában nem tud dekódolni.
Ezután Alice visszafejti az A kulcsos titkosítást, de Eve el®l még a B kulcs miattaz üzenet tényleges tartalma védve van.
Végül Bob dekódol a B kulcs alapján.
A Die-Hellman titkostást használhatjuk moduló egy prím hatványozást véve,
így a diszkrét logaritmusok biztosítanak védettséget. Egy másik lehet®ség például,
hogy az üzenet egy könnyen kezelhet® fokszámú polinom, a két külön kulcs pedig,
amivel titkosításként szorzunk, magas fokszámú polinomok. Így a gyökkereséslesz problémás az illetéktelenek számára.

2. Közös kulcsgenerálás
csoportgy¶r¶k feletti
mátrixokban

2.1. A felépítésr®l
Nagy elemszámú halmazokon érdemes a közös kulcsgenerálást végezni, mivel ígya kriptoszöveg titkossága biztosítva van a random elemválasztásos visszafejtés, ésa memóriaigényes törések ellen.
Ml Zm [Sn ]-nek, azaz a Zm [Sn ] csoportgy¶r¶ felett vett l × l-es mátrixok halmazának igen kis (l, m, n) választással is viszonylag nagy az elemszáma.
• Sn elemei n elem permutációinak összessége, azaz n!.
• Minden Sn -beli elemhez egy Zm -beli számot rendelünk, így Zm [Sn ] elemszáma mn! .
l2• Egy l × l-es mátrix l2 darab eleme (mn! ) = mn!∗l féleképpen tölthet® fel
2

az adott csoportgy¶r¶ elemeivel.

Így például (2, 7, 3) választással a M2 Z7 [S3 ]-nak 724 ∼ 1.9 ∗ 1020 eleme van. A
továbbiakban részletesebben ezen a halmazon reprezentáljuk a protokoll lépéseit.

2.2. A közös kulcsgenerálás menetér®lA használt csoportgy¶r¶ egy kitüntetett g eleme, és az eljárás menete nyilvános.
A kulcsgenerálás a következ®képpen történik:• Alice választ egy a elemet a csoportgy¶r¶b®l, majd nyilvánossá teszi g a =ga -t.
• Közben Bob szintén választ egy b elemet a csoportgy¶r¶b®l, és g b = gb -t

nyilvánossá teszi.

• Alice kiszámolja gb a -t.

7

FEJEZET 2.

KÖZÖS KULCSGENERÁLÁS CSOPORTGYRK FELETTI

8MÁTRIXOKBAN• Közben Bob szintén kiszámolja ga b -t. Alice és Bob most ugyanazzal a gk =ga b = gb a = g a∗b titkos közös kulccsal rendelkezik [2].

Ezt követ®en már megkezd®dhet a közös kulcs segítségével a tényleges kommunikáció.
A nagy elemszám mellett a protokoll további el®nye, hogy a mátrixhatványozás
nem túl memória- és m¶veletigényes [3], így kell®en gyorsan végezhet® a kulcsgenerálás.

2.3. A közös kulcsgenerálás bemutatása választott példán
A könnyebb megértés érdekében érdemes megnéznünk egy konkrét példát is. Az
átláthatóság kedvéért a jegyzet a fentebbi megfogalmazást követi. A használt
csoportgy¶r¶, ez esetben M2 Z7 [S3 ] egy g eleme, és az eljárás menete nyilvános.
g=3(1, 2) + (1, 2, 3) 2(1, 2) + 5(1, 3)
2(2, 3) + 2(1, 3)(1, 3)!

A kulcsgenerálás a következ®képpen történik:• Alice választ egy a ∈ M2 Z7 [S3 ], majd nyilvánossá teszi g a = ga -t. Legyena = 3.
ga =2 + 4(2, 3) + 3(1, 2) + 3(1, 2, 3) + 2(1, 3, 2) + (1, 3)
5 + 4(2, 3) + 2(1, 2) + (1, 2, 3) + (1, 3, 2) + (1, 3)

4(2, 3) + 6(1, 2) + 4(1, 2, 3) + 2(1, 3, 2) + 4(1, 3)
4 + 4(2, 3) + 6(1, 2) + 3(1, 3, 2) + 5(1, 3)• Közben Bob szintén választ egy b ∈ M2 Z7 [S3 ] elemet, és g b = gb -t nyilvánossá teszi. Legyen b = 10.
gb =

5 + (2, 3) + 5(1, 2) + 4(1, 2, 3) + (1, 3, 2) + 2(1, 3)
5(2, 3) + 4(1, 2, 3) + 2(1, 3)

3 + 5(2, 3) + 2(1, 2) + 4(1, 3, 2)
2 + 6(2, 3) + 3(1, 2) + 4(1, 2, 3) + 2(1, 3, 2) + 5(1, 3)

• Alice kiszámolja gb a -t.
• Közben Bob szintén kiszámolja ga b -t. Alice és Bob most ugyanazzal a
gk = ga b = gb a = g a∗b titkos közös kulccsal rendelkezik, azaz a következ®
M2 Z7 [S3 ]-beli elemmel:
gk = g3∗10


=

6 + 4(2, 3) + 4(1, 2) + 4(1, 2, 3) + 5(1, 3, 2) + 6(1, 3)
5 + 5(2, 3) + 4(1, 2) + 2(1, 2, 3) + 5(1, 3)

4(2, 3) + (1, 2) + 5(1, 2, 3) + (1, 3, 2) + 2(1, 3)
2 + 3(2, 3) + 4(1, 2) + 6(1, 2, 3)

Megjegyzés. A csoportgy¶r¶s mátrixokban való kulcsgenerálás törhet®. A probléma visszavezethet® véges testek feletti diszkrét logaritmus problémára, ahol már
létezik hatékony algoritmus [4].
Legyen Fq véges test.
• Az Mn (Fq [G])-beli DLP-t Mn (Fq )-beli DLP-vé redukáljuk.
• Mn (Fq )-beli DLP-t Fq b®vítéseinek DLP-jére redukáljuk.



2.3.

A KÖZÖS KULCSGENERÁLÁS BEMUTATÁSA VÁLASZTOTT PÉLDÁN

9• Erre a DLP-re már létezik hatékony algoritmus.

Ezzel a metódussal a D. Kahrobaei, C. Koupparis és V. Shpilrain eredeti,
2013-as titkosító cikkében [2] kit¶zött törési problémát Chris Monico és Mara D.
Neusel oldotta meg, kevesebb, mint két évvel kés®bb [5].

3. Ariffin-Abu kriptorendszer

3.1. Az AAβ felépítésének menetér®lAz AAβ kriptorendszer Arin és Abu káosz-alapú nyilvános kulcsú kriptorendszere [6]. Egy Die-Hellman közös kulcsgenerálási rendszer, ahol egy szorzás
operátorral dolgozunk, a valós számok halmazán moduló 1-ben. Gyakorlatban,
mivel az irracionális számok nem reprezentálhatóak számítógépen, valamilyen
konzisztens közelítésükkel dolgozhatunk. Ennek a kódolási sémának a lánctörtes
törés [7] által hangsúlyozott, diszkrét logaritmus moduló 1-beli probléma az alapja, és ezt el®térbe helyezve a következ®képpen építhet® fel:
Legyenek A0 és A1 2 × 2-es mátrixok:
A0 =

1 α
1 0

!
A1 =

β 1
1 0

!

ahol α és β ismert egészek,továbbá x ∈ [0, 1[ ismert valós szám. A fentieket
felhasználva Alice és Bob közös kulcs generálása:• 1. lépés: Alice kiszámít egy nA privát egészet:∗ Választ egy tetsz®leges k bites bináris sztringet, a1 . . . ak -t.
∗ Kiszámítja az A = Aak Aak−1 . . . Aa1 egész elem¶ mátrixot.
∗ nA -nak A[1, 1]-et választja.

 B a saját k bites bináris sztringjét megválasztva analóg módon kiszámít
egy nB ∈ Z-t.
• 2. lépés: A kiszámítja rA ≡ nA ∗ x (mod 1) -et, és elküldi B -nek.
 B kiszámítja rB ≡ nB ∗ x (mod 1) -et, és elküldi A-nak.
• 3. lépés: A megosztott közös kulcs nA nB ≡ nB nA (mod 1), ezzel a tényleges

kommunikáció megkezdhet®.

11

12

FEJEZET 3.

ARIFFIN-ABU KRIPTORENDSZER

3.2. Az AAβ bemutatása választott példán
Az AAβ kriptorendszer megértését segíti a következ® számszer¶sített példa:A kriptorendszer (α, β, x) ∈ Z2 × [0, 1[ paraméterezését válasszák a felek(2, 3, 0.5678354675678 . . .)-nek. Így A0 és A1 2 × 2-es mátrixok
A0 =

1 2
1 0

!

3 1
1 0

A1 =

!

lesznek, továbbá legyenek a kés®bbi sztringek k = 6 hosszúságúak. Alice és Bob
közös kulcs generálása:• 1. lépés: Alice kiszámít egy nA privát egészet:∗ 110010 = a6 . . . a1 bináris sztringet választja.
∗ Kiszámítja az A mátrixot a következ®képpen:

=



1
1

2
0

A = Aa6 . . . Aa1 = A0 A1 A0 A0 A1 A1 =





3
1

1
0

1
1

=

2
0

1
1

196 60124 38

2
0

3
1

1
0

3
1

1
0



=

!

∗ nA -nak A[1, 1] = 196-ot választja.

 Bob a saját 6 bites 000110 bináris sztringjéb®l analóg módon el®állítja
nB = 95-öt.
• 2. lépés: Alice kiszámítja rA ≡ 196 ∗ 0.5678354675678 . . . ≡ 0.295751643 . . .
(mod 1) -et, és elküldi Bobnak.
 Bob kiszámítja rB ≡ 95∗0.5678354675678 . . . ≡ 0.944369419 . . . (mod 1)-et, és elküldi Alice-nak.
• 3. lépés:A megosztott közös kulcs nA nB ≡ 0.0964061124 . . . (mod 1).

4. Az Ariffin-Abu rendszer törése

4.1. Röviden a lánctörtekr®l
Az Arin-Abu kriptorendszer töréséhez szükséges ismernünk a lánctörteket. Ezt
a témát öleli fel az alfejezet.
A lánctört alak valós számokra a következ® reprezentációs formát jelenti:
a = a0 +1
a1 + a +2:= [a0 , a1 , a2 , a3 , a4 , . . .]1
1
1
a3 + a +...
41
1+ahol a ∈ R, a0 := [a], a1 := [ {a}], ai = [ {ai−1} ], i ∈ N /1 és [.], {.} rendre az
egészrész, törtrész függvény.
A konstrukció alatta = a0 +1
1
b2= a0 += a0 += ...
b3
b1
a 1 + 1 b4
a1 + b2

a2 + b3

részekre bomlik a, ahol b1 ≥ b2 ≥ b3 ≥ b4 ≥ . . . nemnegatív egész sorozat. Így
szigorúan monoton csökken® bi sorozat esetén az 1 érték¶ tag, egyenl®ség esetén pedig az egyértelm¶en következ® 0 tag jelenti a sorozat végét. Így minden
racionális szám, azaz véges és végtelen szakaszos tizedes tört alakban megjeleníthet® szám, felírató véges lánctört alakban. Továbbá minden irracionális számfelírható végtelen lánctört alakban, mindig eggyel több jegy¶ véges lánctörtet
számolva ki.

4.2. A diszkrét logaritmus probléma megoldásáról moduló 1-ben
Legyenek x, y ∈ [0, 1[ ismertek. Keressük n ∈ Z-t, amivelnx ≡ y(mod 1).
• y = 0 esetben: n = 0 megoldás, tehát feltehetjük, hogy y 6= 0.

13

14

FEJEZET 4.

AZ ARIFFIN-ABU RENDSZER TÖRÉSE

• Ezért x nem írható fel np , p ∈ Z formában, mert
n∗

p
≡y
n

(mod 1) ⇒ p ≡ y(mod 1) ⇒ y = 0

lenne.
• Feltehetjük, hogy n pozitív. Negatív n-ekre az nx ≡ y (mod 1) kongruenciával számolhatunk, ahol n := −n, y := 1 − y .
x, y adottak, n pozitív, y 6= 0. Kiszámítunk egy kell®en jól approximáló abkonvergenst x-hez. Ekkor a kongruenciából n közelítése kinyerhet®:nx ≡ y(mod 1)a∼= y (mod 1)bna ∼= yb (mod b)nn∼= yba−1(mod b)A DLP: nx ≡ y (mod 1) pozitív n-ekre a következ®képpen oldható meg [7]:x, y valós számok adottak.
• Ha y = 0, akkor n = 0, és az algoritmus megáll.
• Ha y 6= 0, kiszámítjuk a konvergenseket x-hez, a lánctörtté alakítást használ-

va. Minden ab konvergensre:

 Kiszámítja a0 -t, a legközelebbi egészet by -hoz.
 Kiszámítja az egyértelm¶ n0 egészet, amivel n0 ≡ a0 a−1 (mod b) és
0 ≤ n0 ≤ b.
 Ha n0 x ≡ y (mod 1), akkor n = n0 , és az algoritmus megáll.
 Egyébként áttér a következ® konvergens vizsgálatára.

4.3. A megfelel®en közeli konvergensválasztásról, és ahibahatárról
Mivel a nevez®k bármely valós szám ab konvergenseiben n®nek, így x ∈ R-nek van
olyan ab approximációja, amire b ≥ 2n.
nx ≡ y (mod 1) miatt ∃m ∈ Z : nx = y + m. Így x minden ab konvergenséveligaz, hogyn ab megközelít®leg y + m
na megközelít®leg yb + mb
na − mb megközelít®leg yb.

4.4.

A DISZKRÉT LOGARITMUS PROBLÉMA MEGOLDÁSA MODULÓ 1-BEN,

15VÁLASZTOTT PÉLDÁN

Legyen a hiba  := x − ab .
ana − mb = nb − mb = nb(x − ) − mb = bnx − bn − mb = b(y + m) − nbbSzeretnénk a törésnél a by -hoz legközelebbi a0 egésszel dolgozni. Tegyük fel,hogy vannak olyan konvergensek, ahol a0 az na − mb egésszel egyezik.
Ehhez az kell, hogy m = 0 és |nb| < 12 teljesüljön, na − mb = by + bm − nb
miatt.
• Válasszuk maximális hibahatárnak b12 -et, azaz legyen || < 12 . Így |nb| <nb= nb ≤ 12 .
b2
• Ha a0 = na − mb, akkor a0 ≡ na (mod b), és mivel ab konvergenseknél a ésb relatív prímek, n ≡ a0 a−1 := n0 (mod b). De mivel n ≤ 12 b < b, és n0 < b,így nincs moduláris redukció, azaz m = 0, és n = n0 .

Az 2n ≤ b küszöböt elér®, és 12 maximális hibahatárt kielégít® konvergensek
esetén a0 ≈ by kerekítéssel hatékonyan és egyértelm¶en dolgozhatunk.

4.4. A diszkrét logaritmus probléma megoldása moduló
1-ben, választott példánTekintsük az y ≡ rA ≡ nA ∗ x (mod 1) DLP-t az el®z® fejezetb®l.
• y 6= 0.
• Kiszámítjuk a konvergenseket x = 0.78217087686061859 . . .-hez, a lánctört-

té alakítást használva:x = 0.78217087686061859 . . . = 0 +1
1 + 3+

1
1+

1
1
1
1+ 2+...

Az x-hez tartozó kovergenssorozat tehát
0+0=1
1
=1
1+0
1
3
0+
1 = 4
1 + 3+0
0+

0+

1
1

1 + 3+ 1

=

4
5

1+0

7 18 61 79 1009 1088 2097... ; ; ;;;;...
9 23 78 101 1290 1391 2681

Minden konvergensre, így a megfelel® 2097
2681 -re is:

16

FEJEZET 4.

AZ ARIFFIN-ABU RENDSZER TÖRÉSE

 Kiszámítja a0 -t, a legközelebbi egészet by -hoz.
 Kiszámítja az egyértelm¶ 2415 := n0 ≡ a0 a−1 = 2527∗2097−1 (mod 2681),
0 ≤ n0 ≤ b egészet.
 n0 x ≡ y (mod 1), azaz 2415∗0.78217087686061859 . . . ≡ 0.94266761839389801 . . .,akkor n = n0 , és az algoritmus megáll.
 Visszakaphatjuk n = nA -t b ∗ y = 2681 ∗ 0.94266761839389801 . . .
kerekítésével a legközelebbi egészhez, mi megtaláljuk az n0 = 2415 =nA -t, amit kerestünk.(Hasonlóképpen visszakaphatjuk nB = 3725-öt,5282
használva az 6753
konvergenst x-re, az y = rB értéket, és a0 = 3961
számítását.

5. Sage kódok

Ebben a fejezetben a dolgozat algoritmusait implementáltam a SageMath [8] programcsomagban.
pretty_print(html(r'<p>CSOPORTGYRS RENDSZER:</p>'))h1=SymmetricGroup(3).gen(0)h2=SymmetricGroup(3).gen(1)G3S7=GroupAlgebra(SymmetricGroup(3),Integers(7))
pretty_print(html(r'<p>Dolgozzunk$\mathbb{M} _2 \mathbb{Z} _7[S_3]$ csoportgy¶r¶ egy kitüntetett$g=\left(\begin{array}{cc}a_{11}&a_{12}\\a_{21}&a_{22}\end{array}\right)$
elemével, aminek elemei a következ® alakban állnak el®:</p>'))pretty_print(html(r'<p>$a_{ij}=a_{ij}[1]()+a_{ij}[2](1,2)+a_{ij}[3](1,2,3)+a_{ij}[4](2,3)+a_{ij}[5](1,3,2)+a_{ij}[6](1,3),$</p>'))pretty_print(html(r'<p>ahol az $a_{ij}[k]$ értékek$\mathbb{Z}_7$-b®l kerülnek ki és az alábbi beviteli mez®kön
tudjuk az értékeiket megadni.</p>'))pretty_print(html(r'<p>Továbbá a két fél válasszon egy-egy,
egyénenként titkos természetes számot.</p>'))@interactdef_(a11=input_grid(1,6, default = [0,3,1,0,0,0], label='$a_{11}$'),
a12=input_grid(1,6, default = [0,2,0,0,0,5], label='$a_{12}$'),
a21=input_grid(1,6, default = [0,0,0,2,0,2], label='$a_{21}$'),
a22=input_grid(1,6, default = [0,0,0,0,0,1], label='$a_{22}$'),

17

18

FEJEZET 5.

SAGE KÓDOK

x=('Alice száma',3),y=('Bob száma',10)):
A=[0,0,0,0]
B=[a11,a12,a21,a22]
k=0
for n in range(4):for i in range(3):for j in range(2):A[n]=A[n]+G3S7(B[n][0][k])*h1^i*h2^j
k=k+1
k=0
g=matrix([[A[0],A[1]],[A[2],A[3]]])pretty_print(html('$$g=%s$$'%latex(g)))
pretty_print(html(r'<p>Alice nyilvánossá teszi$g^{%s}=g_{%s}$-t, azaz $$g_{%s}=%s$$ mátrixot.</p>'%(x,x,x,latex(g^x))))
pretty_print(html(r'<p>Bob nyilvánossá teszi$g^{%s}=g_{%s}$-t, azaz $$g_{%s}=%s$$ mátrixot.</p>'%(y,y,y,latex(g^y))))pretty_print(html(r'<p>Alice és Bob most ugyanazt a$g_{k}={g_a}^b={g_b}^a=g^{a*b}$ titkos kulcsot képzi
a közzétett mátrixok segítségével, azaz a következ®
$\mathbb{M} _2\mathbb{Z} _7[S_3]$-beli elemet:</p>'))pretty_print(html(r'<p>$$g_{%s*%s}=%s$$</p>'%(x,y,latex((g^x)^y))))195.1. ábra. Csoportgy¶r¶s rendszer

5.2. ábra. Csoportgy¶r¶s rendszer

pretty_print(html(r'<p>ARIFFIN-ABU RENDSZER:</p>'))pretty_print(html(r'<p>A kriptorendszer$\alpha ,\beta ,x \in \mathbb{Z} ^2 \times [0,1[$
paraméterezését válasszák a felek meg a következ®képpen,
továbbá $A$ és $B$ felek válasszanak egy-egy tetsz®leges$6$ bites bináris sztringet, rendre$a_1\ldots a_6$-t és $b_1\ldots b_6$-t.</p>'))A0=MatrixSpace(ZZ,2,2)
A1=MatrixSpace(ZZ,2,2)

20

FEJEZET 5.

SAGE KÓDOK

@interactdef _(valt=input_grid(1,2, default = [2,3],
label=r'$ \alpha , \beta $'), x=('x',0.5678354675678),
a=input_grid(1,6, label='$a_1 \ldots a_6$',
default=[1,1,0,0,1,0]),b=input_grid(1,6, label='$b_1 \ldots b_6$',
default=[0,0,0,1,1,0])):ii=0for i in range(6):if a[0][i]==1 or a[0][i]==0:
ii=ii+1
jj=0
for j in range(6):if a[0][j]==1 or a[0][j]==0:
jj=jj+1
if ii!=6:
pretty_print(html(r'<p>A félnek bináris sztringet
kell válsztania.</p>'))elif jj!=6:
pretty_print(html(r'<p>B félnek bináris sztringet
kell válsztania.</p>'))else:
pretty_print(html(r'<p>Így $A_0$ és $A_1$$2\times 2$-es mátrixok:</p>'))A0=matrix([[1,valt[0][0]],[1,0]])A1=matrix([[valt[0][1],1],[1,0]])pretty_print(html('$A_0=%s \quad A_1=%s$'%(latex(A0),latex(A1))))pretty_print(html('$A$ kiszámítja az$A=A_{a_6} \ldots A_{a_1}=A_%sA_%sA_%sA_%sA_%sA_%s$egészet.'%(a[0][5],a[0][4],a[0][3],a[0][2],a[0][1],a[0][0])))A=matrix([[1,0],[0,1]])

21
while i>=0:
if a[0][i]==1:
A=A*A1else:
A=A*A0i=i-1
pretty_print(html('$A=%s$'%latex(A)))
rA=(x*A[0,0]) % 1
if rA<0:rA=1+rA
pretty_print(html('A továbbküldi B-nek$r_A \equiv x*A[1,1] \pmod 1$-et,azaz $%s \equiv %s*%s \pmod 1$ értéket.'%(rA.n(digits=9),x,A[0][0])))pretty_print(html('$B$ kiszámítja az$B=A_{b_6} \ldots A_{b_1}=A_%sA_%sA_%sA_%sA_%sA_%s$mátrixot.'%(b[0][5],b[0][4],b[0][3],b[0][2],b[0][1],b[0][0])))
B=matrix([[1,0],[0,1]])
while j>=0:
if b[0][j]==1:
B=B*A1else:
B=B*A0
j=j-1
pretty_print(html('$B=%s$'%latex(B)))
rB=(x*B[0,0]) % 1
if rB<0:rB=1+rB
pretty_print(html('B továbbküldi A-nak$r_B \equiv x*B[1,1] \pmod 1$-et,azaz $%s \equiv %s*%s \pmod 1$ értéket.'%(rB.n(digits=9),x,B[0][0])))koz1=(rB*A[0][0]) % 1

22

FEJEZET 5.

SAGE KÓDOK

if koz1<0:
koz1=1+koz1
pretty_print(html('A közös kulcs számítása
a kapott $r_B$ értékkel:$közös \equiv r_B*A[1,1] \equiv %s*%s \equiv %s \pmod 1$'%(rB.n(digits=9),A[0][0],koz1.n(digits=9))))koz2=(rA*B[0][0]) % 1
if koz2<0:
koz2=1+koz2
pretty_print(html('B közös kulcs számítása a kapott$r_A$ értékkel:$közös \equiv r_A*B[1,1] \equiv %s*%s \equiv %s \pmod 1$'%(rA.n(digits=9),B[0][0],koz2.n(digits=9))))23
5.3. ábra. Arin-Abu rendszer

5.4. ábra. Arin-Abu rendszer

pretty_print(html(r'<p>ARIFFIN-ABU RENDSZER TÖRÉSE:</p>'))pretty_print(html(r'<p>$$n_A*x \equiv r_A \pmod 1$$ DLP-ben$n_A$-t keressük. $x \in R$ és $0 \leq r_A < 1$ nyilvánosak
a jogosult felek kommunikációja során.</p>'))@interactdef _(x=('$x$',0.5678354675678),rA=('$r_A$',0.295751643)):
if x==0:
if rA==0:
pretty_print(html(r'<p>$n_A \in R$ minden esetben
kielégíti a kongruenciát, ez az eset triviális.</p>'))else:
pretty_print(html(r'<p>$n_A$ nem létezik,
ez az eset triviális.</p>'))

24

FEJEZET 5.

SAGE KÓDOK

else:
if rA==0:
pretty_print(html(r'<p>$n_A=0$,ez az eset triviális.</p>'))elif rA<0 or 1<=rA:
pretty_print(html(r'<p>A $0 \leq r_A < 1$
kritérium nem teljesül.</p>'))else:
pontos=len(x.str())-1
Rp=RealField(pontos+100)
ct=QQ(x).continued_fraction()i=2
hiba=1convs=Sequence([])
while abs(hiba)>0 and i<30:
a=ct.numerator(i)b=ct.denominator(i)convs.extend([a/b])
brA=round(b*rA)
nA=Integers(b)(brA)*(Integers(b)(a^(-1)))
hiba=Rp(RR(nA)*x).frac().n(digits=17)-rA
i=i+1
pretty_print(html(r'<p>Az $x$-hez tartozó
lánctörtekb®l képzett konvergenssorozat tagjai:</p>'))pretty_print(html(r'<p>$\ldots%s\ldots$</p>'%str(convs)[1:-1]))
pretty_print(html(r'<p>$\frac{a}{b}=%s$kell®en közeli konvergens x-hez.</p>'%latex(convs[i-3])))pretty_print(html(r'<p>Kiszámítjuk $\overline{a}$-t,

25
a legközelebbi egészet $b*r_A$-hoz:</p>'))pretty_print(html(r'<p>$\overline{a}\approx b*r_A=%s*%s\approx %s$</p>'%(b,rA,brA)))
pretty_print(html(r'<p>A keresett $n_A$ így$\overline{a}$ és $a^{-1} \pmod b$-beliszorzata lesz:</p>'))pretty_print(html(r'<p>$n_A\equiv \overline{a}*a^{-1}\equiv%s*%s\equiv %s \pmod {%s}$</p>'%(brA,Integers(b)(a^(-1)),nA,b)))pretty_print(html(r'<p>Az $n_A$ kulcs tehát:%s</p>'%nA))
pretty_print(html(r'<p>Az $n_B$ kulcs $r_B$-vel
és $x$-el analóg módon számolható.</p>'))5.5. ábra. Arin-Abu rendszer törése

26

FEJEZET 5.

5.6. ábra. Arin-Abu rendszer törése

SAGE KÓDOK

Irodalomjegyzék[1] A kriptográa története, Wikipedia, 2015.

https://hu.wikipedia.org/wiki/A_kriptogr%C3%A1fia_t%C3%B6rt%C3%
A9nete.

[2] Delaram Kahrobaei, Charalambos Koupparis and Vladimir Shpilrain: Public
Key Exchange Using Matrices Over Group Rings, Cornell University Library,
Computer Science, Cryptography and Security, 21 pages, 2013.
https://eprint.iacr.org/2013/114.pdf.
[3] Dr. Tengely Szabolcs: Mátrixok n-edik hatványának zárt alakja, Debreceni
Egyetem, Oktatási segédletek, 2014.
http://shrek.unideb.hu/~tengely/Magyary/oktatas.html.
[4] Alex Myasnikov: Discrete logarithm problem for matrices over nite grouprings, Stevens Institute of Technology, 18 pages.
http://web.stevens.edu/algebraic/GAGTA/Slides/Myasnikov.pdf.
[5] Chris Monico and Mara D. Neusel: Cryptanalysis of a system using matrices
over group rings, Groups Complexity Cryptology, volume 7, 2015.
[6] M.R.K. Arin and N.A. Abu: AAB-Cryptosystem: A Chaos Based Public
Key Cryptosystem, International Journal of Cryptology Research, 149-163,2009.
http://www.mscr.org.my/V1(2)/PP%20149-163.pdf.
[7] Simon R. Blackburn: The discrete logarithm problem modulo one: cryptanalysing the Arin-Abu cryptosystem, Journal of Mathematical Cryptology,
volume 4, pages 193-198 ,2010.
https://eprint.iacr.org/2010/114.pdf.
[8] W. A. Stein et al.: Sage Mathematics Software (Version 7.1), The Sage Development Team, 2016.
http://www.sagemath.org.

27