Debreceni Egyetem
Természettudományi és Technológiai Kar
Matematikai Intézet

Szakdolgozat

Kriptográfiai eljárások
implementálása a SageMath
programcsomagbakészı́tette:

Dsupin Krisztiántémavezető: Dr. Tengely Szabolcs

Debrecen, 2018

Tartalomjegyzék1

2

3

Bevezetés . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.1

Diszkrét logaritmus probléma . . . . . . . . . . . . . .

3

1.2

Diszkrét logaritmus probléma véges csoportokban . . .

4Gyenge GDLP két speciális generátorral . . . . . . . . .

5

2.1

Gyenge GDLP SageMath-ben . . . . . . . . . . . . . .

8

2.2

A megoldást végző program forráskódja . . . . . . . . . 10

Gyenge GDLP két tetszőleges generátorral . . . . . . . 12
3.1

Gyenge GDLP SageMath-ben . . . . . . . . . . . . . . 15

3.2

Az általános megoldást végző program forráskódja . . . 171

Köszönetnyilvánı́tás
Szeretnék köszönetet mondani témavezetőmnek Dr. Tengely Szabolcsnak
a sok segı́tségért, biztatásért és a hasznos tanácsokért, amikkel nagyban
hozzájárult e szakdolgozat létrejöttéhez. Köszönettel tartozom a családomnakés barátaimnak a támogatásukért, amivel segı́tették, hogy ez a dolgozat
elkészülhessen.

2

1

BevezetésTöbb ma ismert kriptorendszer biztonsága egy matematikailag nehezen számı́tható problémán alapszik, mint például a diszkrét logaritmus probléma, egészszámok faktorizációja, Diffie-Hellman probléma, stb. Ebben a dolgozatban adiszkrét logaritmus probléma kap kiemelt figyelmet [1].

1.1

Diszkrét logaritmus probléma

Tekintsük az α elem által generált véges ciklikus G csoportot, továbbá legyen
β P G egy további elem. A tradicionális diszkrét logaritmus probléma (DLP)egy nem negatı́v x egész szám keresése, melyre αx “ β.
A DLP-re épülő kriptográfiai modellek épı́tésekor fontos követelmény a
probléma nehezen kezelhetősége. A diszkrét logaritmus probléma számára
gyakorlatban használatos csoportok Fq multiplikatı́v csoportja, továbbá nagyméretű ciklikus részcsoportjai megfelelően választott E elliptikus görbének Fq
felett.
A probléma kezelhetősége függ a csoport reprezentációján. Például Zn ben DLP kérdése könnyen megoldható. Egy adott β P Zn és α P Zn
generátor esetén egyszerű olyan nemnegatı́v x megadása, melyre xα “ β.
Mivel gcdpn, αq “ 1, a kiterjesztett euklideszi algoritmus segı́tségével α multiplikatı́v inverze kiszámolható, amely DLP megoldását jelenti.
A diszkrét logaritmus probléma megoldására szolgáló algoritmusokat három
csoportra oszthatjuk:
1. Algoritmusok melyek tetszőleges csoportban működnek [2].
Például: Brute-force keresés, Baby-step giant-step, Pollard-féle rho algoritmus.
2. Algoritmusok melyek tetszőleges csoportban működnek, és hatékonyok
kis prı́mfaktor rendű csoportokban [3].
Például: Pohlig-Hellman algoritmus.
3. Algoritmusok melyek csak speciális csoportban működnek [3].
Például: index-kalkulus algoritmus.

3

1.2

Diszkrét logaritmus probléma véges csoportokban

Ahogy [4]-ban definiált általános diszkrét logaritmus probléma (GDLP) tetszőleges véges csoportra a következő: Legyen G véges véges csoport α1 , . . . , αtgenerátorokkal, továbbá adott β P G. Határozzunk meg egy pozitı́v egész
k-t és egészekből álló px11 , . . . , x1t , . . . , xk1 , . . . xkt q szám kt-st melyre:β“kźpα1xi1 . . . αtxit q.

i“1Az px11 , . . . , x1t , . . . , xk1 , . . .kt q szám kt-st az α1 , . . . , αt -re vonatkozó β általános
diszkrét logaritmusnak nevezzük.
Ha

k
)
!ź
xi1
xit
Sk “
pα1 . . . αt q | xij P Znj
i“1ahol nj jelöli αj rendjét. A legkisebb pozitı́v egész k0 , melyre @k ą k0 , G Ď
Sk -t a G csoport pα1 , . . . , αt q-re vonatkozó mélységének nevezzük.
Adott Fq test és n rögzı́tett természetes szám. Az n ˆ n reguláris mátrixok
csoportját a mátrixszorzás műveletével n fokú általános lineáris csoportként
ismert Fq felett, jelölése GLpn, qq. Könnyen látható, hogy |GLpn, qq| “
ś
n´1 n
i
i“0 pq ´q q. Az 1 determinánsú mátrixok hamaza GLpn, qq-ban részcsoportot
alkot, melyet speciális lineáris csoportnak nevezünk, jelölése SLpn, qq. SLpn, qq
a det : GLpn, qq Ñ F˚q homorfizmus magja, és ennélfogva |SLpn, qq| “|GLpn, qq|{pq ´ 1q. GLpn, qq centruma a tλI | λ P F˚q u alakú, SLpn, qq centruma tλI | λn “ 1u alakú mátrixokból áll. Az n rendű projektı́v lineáris
csoport alatt Fq felett P SLpn, qq “ SLpn, qq{ZpSLpn, qqq-t értjük. Itt csak
az n “ 2 esettel foglalkozunk majd, ahol q páratlan, tehát |P SLp2, qq| “
pq 2 ´ 1qq{2.

42Gyenge GDLP két speciális generátorral

Tekintsük G “ P SLp2, pq csoport, ahol p páratlan prı́m. Legyen α, β kétteszőleges, nem felcserélhető, p rendű eleme a G csoportnak, továbbá legyenek
H, K ď G részcsoportok α, illetve β generátorral. [5]-ben a szerző megmutatja, hogy G-t generálja α és β, továbbá G “ HKHK. Ezenfelül G mélysége
α és β generátorokkal egyenlő kettővel.
A továbbiakban feltesszük, hogy G csoportot SLp2, pq-beli mátrixok reprezentálják, ´I faktorig, ahol I a 2 ˆ 2-es egységmátrix.
Tekintsünk A, B mátrixokat az alábbi módon:
ˆ
˙
ˆ
˙
1 1
1 0
, B“
.
A“
0 1
1 1
Ekkor A és B p rendű, nem felcsélhető, és G-t generálja. Megmutatjuk,
hogy az általános diszkrét logaritmus probléma a G csoportban hatékonyan
megoldható.
ˆ˙
m11 m12Feltéve, hogy M “
P G, m11 , m12 , m21 , m22 P Fp . Mivel G
m21 m22
kettő mélységű, ezért M reprezentálható M “ Ai B j Ak B l módon, ahol i, j, k, lnemnegatı́v egészek. Az általános diszkrét logaritmus probléma megoldása,
egy nemnegatı́vakból álló rendezett pi, j, k, lq négyes megtalálását jelenti, ahol
M “ Ai B j Ak B l .
Vegyük észre, hogy
ˆ
i

A “

˙
1 i
,
0 1

ˆ
j

és B “

˙
1 0
.
j 1

Amiből következik
ˆ
i

j

k

m11 m12m21 m22˙l

AB A B “

Emiatt
ˆ

ˆ
“

1 i
0 1

˙ˆ
˙ˆ
˙ˆ
˙
1 0
1 k
1 0
.
j 1
0 1
l 1

˙
1 ` ij ` lpp1 ` ijqk ` iq p1 ` ijqk ` i.
j ` lpjk ` 1q
jk ` 15

A mátrix egyes elemeinek kiszámolásával az alábbi négy egyenletőből állóés pi, j, k, lq ismeretlenes egyenletrendszerhez jutunk:1 ` ij ` lpp1 ` ijqk ` iq “ m11
p1 ` ijqk ` i “ m12j ` lpjk ` 1q “ m21jk ` 1 “ m22Az egyenletrendszer megoldható i, j, k, l-ra Gröbner bázist használva. Legyen
I ideál
I “ x 1 ` ij ` lpp1 ` ijqk ` iq ´ m11 ,p1 ` ijqk ` i ´ m12 ,j ` lpjk ` 1q ´ m21 ,jk ` 1 ´ m22 y.
I ideál GB Gröbner bázisa a racionális számok halmaza felett:GB “ rl ´ jim21 ` jm11 ´ m21 ,k ` im22 ´ m12 ,jim12 m21 ` ji ` jm11 m12 ´ m11 ` m12 m21 ` 1,
jim22 ´ jm12 ` m22 ´ 1,
m11 m22 ´ m12 m21 ´ 1s.
Tehát az általános diszkrét logaritmus probléma megoldása P SLp2, p)-ben,ekvivalens az alábbi egyenletrendszer megoldásával.

l ´ jim21 ` jm11 ´ m21 “ 0k ` im22 ´ m12 “ 0
jim22 ´ jm12 ` m22 ´ 1 “ 0.
Az egyenletrendszernek általában több megoldása létezik. Az alábbi állı́tásmódszert biztosı́t megoldáskereséshez, ha M P G.
Állı́tás 2.1. Legyenek A, B és M mátrixok az előbb használt értékekkel.
Ekkor létezik n ă p nemnegatı́v egész, hogy nm22 ´m12 ‰ 0 és olyan pi, j, k, lq
6számnégyes, hogy i “ n, j “ p1 ´ m22 qpnm22 ´ m12 q´1 , k “ m12 ´ nm22 , l “
p1 ´ m22 qpnm21 ´ m11 qpnm22 ´ m12 q´1 ` m21 mely megoldás M “ Ai B j C k Dl
problémára.
Bizonyı́tás. Direkt számı́tással igazolható, hogy pi, j, k, lq kielégı́tik a fenti
egyenletetrendszert. n lézetését M P P SLp2, pq biztosı́tja és emiatt b, d nem
lehet egyszerre nulla.
Példa 2.1. Az alábbi példa szemlélteti a módszert: Tekintsük G “ P SLp2, 7q
csoportot SLp2, 7q-beli mátrixokkal reprezentálva modulo ˘I. Legyenek
A, B, M P G az alábbiak:
ˆ
˙
ˆ
˙
ˆ
˙
5 2
1 1
1 0
M“
, A“
, B“
.
6 4
0 1
1 1
Az M, A, B mátrix által meghatározott általános diszkrét logaritmus kiszámı́tása
megfelel pi, j, k, lq nemnegatı́v számnégyes meghatározásának, melyre
M “ Ai B j C k D l .
Az egyenletrendszer melyet korábban meghatároztunk ı́gy alakul:
1 ` ij ` lppi ` ijqk ` iq “ 5pi ` ijqk ` i “ 2j ` lpjk ` 1q “ 6
jk ` 1 “ 4.
2.1 miatt pi, j, k, lq “ p0, 5, 2, 2q. F7 -beli mátrix szorzásból adódik, hogy
M “ A0 B 5 C 2 D 2 .

7

2.1

Gyenge GDLP SageMath-ben

A fenti példa megoldása SageMath [6] programcsomagban:

Interaktı́v megvalósı́tás SageMath-ben.

8

ˆ

˙
8 13
Másik példának tekintsük az M “
P P SLp2, 17q mátrixot. Az
16 7
ı́gy adódó GDLP megoldásai SageMath segı́tségével a következők:

9

2.2
1
2
3

4
5
6

7
8
9
10
11
12
13
14

15

16

17
18
19

A megoldást végző program forráskódja@interact(layout=[['Pmx','M']])def _(Pmx=input_grid(1,1, default = [[7]], label='$p=$'),
M=input_grid(2,2, default = [[5,2],[6,4]],ãÑlabel='$M=$')):
p=Pmx[0][0]; M=matrix(GF(p),2,2,M)
if M not in SL(2,p):pretty_print(html(r'<center>$%s \ \notin \ SL(2,%s)ãÑ$'%(latex(M),latex(p))))else:
P.<i,j,k,l>=PolynomialRing(GF(p),4)
Ptmp.<X1,X2,X3,X4>=PolynomialRing(ZZ,4)
A=matrix(GF(p),[[1,1],[0,1]])
B=matrix(GF(p),[[1,0],[1,1]])pretty_print('Legyenek adottak az alábbi mátrixok:')pretty_print('M=',M,', A=',A,', B=',B);printpretty_print ('\nCélunk olyan $(i,j,k,l)$ számnégyesãÑ
megtalálása, ahol:')html(r'<center>$%sˆi%sˆj%sˆk%sˆl=%s$'ãÑ%(latex(A),latex(B),latex(A),latex(B),latex(M)));printpretty_print ('\nA mátrix egyes elemeinekãÑkiszámolásával az alábbi $(i,j,k,l)$ ismeretlenesãÑegyenletrendszerhez jutunk:')
Ai=matrix(P,[[1,i],[0,1]]); Ak=matrix(P,[[1,k],[0,1]])
Bj=matrix(P,[[1,0],[j,1]]); Bl=matrix(P,[[1,0],[l,1]])
Mi=Ai*Bj*Ak*Bl

20
21

22
23
24
25

26
27
28
29

I=ideal(Mi[v][w]-M[v][w] for v in [0..1] for w inãÑ
[0..1])
for v in [0..3]:
pretty_print(Mi.list()[v],'=',M[v//2][v%2])
print
pretty_print('Az egyenletrendszer megoldását könnyı́ti aãÑGröbner bázis megadása, amelyhez legyen $I$ ideálãÑ
az alábbi:')
IList=[Mi.list()[w]-M[w//2][w%2] for w in [0..3]]
pretty_print(IList);printpretty_print('A keresett Gröbner bázis:')
GB=I.groebner_basis()
10

30
31

32
33
34
35
36

37

38
39
40

pretty_print(GB);printpretty_print('Az eredeti egyenletrendszer megoldásaãÑekvivalens az Gröbner bázis segı́tségével konstruáltãÑegyenletrendszer megoldásával:')for z in [0..len(GB)-1]:
pretty_print(GB[z],'=',0)
print
var('x1,x2,x3,x4')
S=[Ptmp(g(i=X1,j=X2,k=X3,l=X4))
ãÑ(X1=x1,X2=x2,X3=x3,X4=x4)==0 for g in GB]
pretty_print('Az egyenlerszer megoldásai az alábbi
ãÑ
$(i,j,k,l)$ számnégyesek:')
Sol=solve_mod(S,p)
for t in [0..len(Sol)-1]:
pretty_print(Sol[t])113Gyenge GDLP két tetszőleges generátorral

Tegyük fel, hogy C, D két nem felcserélhető, p rendű elem G “ P SLp2, pqben, továbbá tekintsük A és B mátrixokat az előző fejezetben definiált módon.
Bármely adott M P G esetén a célunk i, j, k, l egészek meghatározása, melyre:
M “ C i Dj C k Dl .
Olyan g P G “ P SLp2, pq elemet keresünk, mely teljesı́ti a következőketvalamely nemnegatı́v s, t ă p egészekre:C “ g ´1 As gés D “ g ´1 B t g.

stEzzel ekvivalens módon valamely g P G eseténgCˆ˙ “ A g és gD “ B g,g1 g2
valamely s, t ă p egészekre. Mivel g “, ı́gy egy g1 , g2 , g3 , g4
g3 g4
változókkal adott egyenletrendszerhez jutunk, amiből g meghatározható.

Amennyiben g P G elemet már meghatároztuk.
M “ C i Dj C k Dl
“ pg ´1 As gqi pg ´1 B t gqj pg ´1 As gqk pg ´1 B t gql“ pg ´1 Asi gqpg ´1 B tj gqpg ´1 Ask gkpg ´1 B tl gq“ g ´1 Asi B tj Ask B tl g.
Legyenek x “ si, y “ tj, v “ sk, w “ tl. Ekkor:
M “ g ´1 Ax B y Av B w g
gM g ´1 “ Ax B y Av B w .
Jelölje M1 “ gM g ´1 . Természetesen M1 P G, továbbá:M1 “ Ax B y Av B w .
Így visszavezettük a tetszőleges C, D generátorokkal adott általános diszkrét logaritmus problémát, az előző részben már megoldott két speciális
A, B generátorokkal adott problémára.
12

Mivel esetünkben minden nemnulla elemnek létezik inverze, ı́gy i, j, k, lelemek a következő módon számolhatók ki:
i “ xs´1 , j “ yt´1 , k “ vs´1 , l “ wt´1ahol minden művelet modulo p értendő.
Végezetül az s “ 0 vagy t “ 0 eset nem fordulhat elő, mivel C “ g ´1 As gés D “ g ´1 B t g. Amennyiben s “ 0, abból As megegyezik az egységmátrixszal, vagyis C úgyszintén az egységmátrix-szal egyenlő, ami ellentmondana
C p-rendűségének. Hasonlóan adódik, hogy t ‰ 0.
Példa 3.1. Feltéve, hogy a G “ P SLp2, pq csoportok SLp2, 7q-beli mátrixokkal
reprezentálhatók ´I faktorig. Legyenek adottak C, D nem felcserélhető 7
rendű mátrixok, és M P G az alábbi módon adottak:
ˆ
˙
ˆ
˙
ˆ
˙
3 5
5 1
2 5
, C“
, D“
.
M“
2 6
5 4
4 0
Célunk kiszámolni M általános diszkrét logaritmus problémáját tekintettel
pC, Dq-re, vagyis olyan nemnegatı́v i, j, k, l egészek találása, mely esetén M “
C i Dj C k Dk .
ˆ
˙
g1 g2
Olyan g “elemet keresünk, mely teljesı́ti a következőket valamely
g3 g4
nem negatı́v s, t ă p egészekre, C “ g ´1 As g és D “ g ´1 B t g. Vagyis:
ˆ
˙ ˆ
˙´1 ˆ
˙ˆ
˙
5 1
g1 g2
1 s
g1 g2
“
5 4
g3 g4
0 1
g3 g4
ˆ
˙ ˆ
˙´1 ˆ
˙ˆ
˙
2 5
g1 g2
1 0
g1 g2
“
.
4 0
g3 g4
t 1
g3 g4
Az egyenleteket rendezve, majd a mátrix elemeit tekintve az alábbi egyenletrendszerekhez jutunk:g1 ` 4g2 “ 0
5g1 ´ g2 “ 0´g1 t ` g3 ´ g4 “ 0´g2 t ` 5g3 ´ g4 “ 0´g3 s ` 4g1 ` g2 “ 0´g4 s ` 4g1 ` 3g2 “ 0
4g3 ` 5g4 “ 0
g3 ` 3g4 “ 0.
13A Gröbner bázis meghatározásával a GDLP megoldása a következőképpen
egyszerűsödik:
g4 s ` g2 “ 0
g2 t ` 2g4 “ 0
g1 ` 4g2 “ 0
g3 ` 3g4 “ 0.
Az egyenletekből az egyes változókat g1 segı́tségével kifejezve g4 “ ´ gs2 , g1 “´4g2 , g3 “ ´3g4 . Ezeket a g mátrixba visszahelyettesı́tve
˙
ˆ
˙
ˆ
0
0
0 0
s
t
g¨C ´A ¨g “és g ¨ D ´ B ¨ g “ 4g2 st´g2 ´g2 st`g2
0 0ss
adódik. Ezek segı́tségével s, t lehetséges értékei meghatározhatók, melyek amost tárgyalt példa esetében
ps, tq P tp1, 2q, p6, 5q, p3, 3q, p5, 6q, p4, 4q, p2, 1qulehetnek. Ezek közül tetszőleges megoldáshoz vezet, válasszuk ki példáuls “ 1, t “ 2 értékeket további számoláshoz. Ezeket visszahelyettesı́tve G ¨C ´ As ¨ G és g ¨ D ´ B t ¨ g mátrixba, négyismeretlenes egyenletrendszerhez
jutunk meghatarázhatóak g1 , g2 , g3 , g4 értékei, amik az előbb kiválasztott s, tértékek esetén az alábbiak lehetnek:
pg1 , g2 , g3 , g4 q P tp6, 2, 6, 5q, p1, 5, 1, 2q, p14, 6, 4, 1q, p5, 4, 5, 3q, p2, 3, 2, 4q, p3, 1, 3, 6qu.
Ismétˆ egy˙tetszőleges megoldást választva, például p6, 2, 6, 5q számnégyest
ˆ
˙
6 2
3 3
´1
g “
mátrix adódik. Kiszámolva M1 “ G ¨ M ¨ G “
6 5
1 6mátrixot, vagyis az olyan px, y, v, wq számnégyeseket keresünk, melyek kielégı́tik
M1 “ Ax B y Av B w egyenletet. A 2 részben mutatot módszer segı́tségével
px, y, v, wq P tp0, 4, 3, 3q, p1, 3, 4, 2q, p2, 1, 5, 0q, p3, 2, 6, 1q, p5, 5, 1, 4q, p6, 6, 2, 5qu.
Az M “ C i Dj C k Dl GDLP probléma megoldásai tehát a következő:pi, j, k, lq P tp0, 2, 3, 5q, p1, 5, 4, 1q, p2, 4, 5, 0q, p3, 1, 6, 4q, p5, 6, 1, 2q, p6, 3, 2, 6qu.

14

3.1

Gyenge GDLP SageMath-ben

Tekintsük az előző példa megoldását SageMath programcsomagban.

15

ˆ

˙
ˆ
˙
ˆ
˙
3 3
5 6
7 10
Másik példának tekintsük az M “
,C “
,D “
11 7
6 10
12 8
P SLp2, 13q-beli mátrixokat. Az ı́gy adódó GDLP megoldásai SageMathsegı́tségével a következők:

16

3.2
1
2
3
4
5
6
7
8

Az általános megoldást végző program forráskódja

def sortfv(L):#sort by first variable
SL=[]
TL=[L[i][0] for i in [0..len(L)-1]]
for j in [0..len(L)-1]:
SL.append(L[TL.index(max(TL))])L.remove(L[TL.index(max(TL))])
TL.remove(TL[TL.index(max(TL))])
return SL

9
10
11
12
13
14
15
16
17
18

@interact(layout=[['Pmx','M','C','D']])def sortfv(L):#sort by first variable
SL=[]
TL=[L[i][0] for i in [0..len(L)-1]]
for j in [0..len(L)-1]:
SL.append(L[TL.index(max(TL))])L.remove(L[TL.index(max(TL))])
TL.remove(TL[TL.index(max(TL))])
return SL

19
20
21
22
23
24

@interact(layout=[['Pmx','M','C','D']])def _(Pmx=input_grid(1,1, default = [[7]], label='$p=$'),
M=input_grid(2,2, default = [[3,5],[2,6]], label='$M=$'),
C=input_grid(2,2, default = [[5,1],[5,4]], label='$C=$'),
D=input_grid(2,2, default = [[2,5],[4,0]],ãÑlabel='$D=$')):
17

25

26

27

28
29
30
31
32
33
34
35
36
37

p=Pmx[0][0]; M=matrix(GF(p),2,2,M); C=matrix(GF(p),2,2,C);ãÑ
D=matrix(GF(p),2,2,D)
if C.multiplicative_order()!=p orãÑD.multiplicative_order()!=p:pretty_print('Adjon meg másik mátrixokat, a megadottãÑ
rangfeltételekkel')else:
P.<g1,g2,g3,g4,s,t>=PolynomialRing(GF(p),6)
P.<i,j,k,l>=PolynomialRing(GF(p),4)
Ptmp.<X1,X2,X3,X4,Y1,Y2>=PolynomialRing(ZZ,6)GVar=[g1,g2,g3,g4,s,t]var('x1,x2,x3,x4,S,T')
G=matrix([[g1,g2],[g3,g4]])
As=matrix([[1,s],[0,1]])
Bt=matrix([[1,0],[t,1]])
N=matrix(2)

38
39
40
41

42

43

44

45
46

pretty_print('Legyenek adottak az alábbi mátrixok:')pretty_print('M=',M,', C=',C,', D=',D,', G=',G)html('<br><center>Célunk olyan $(i,j,k,l)$ számnégyesãÑ
megtalálása, ahol:')html(r'<center>$%s=%sˆi%sˆj%sˆk%sˆl$'%ãÑ(latex(M),latex(C),latex(D),latex(C),latex(D)))
html('<br><center>A korábbi fejezetben definiált $A,B$ãÑ
mátrixok segı́tségével. A probléma megoldható egy
ãÑ$G$ mátrix segı́tségével melyre:')html(r'<center>$%s=%s%s%s \quad$ és $\quadãÑ%s=%s%s%s$'%(latex(C),latex(G),ãÑlatex(As),latex(G),latex(D),latex(G),latex(Bt),latex(G)))
html('<br><center>Ezzel ekvivalens módon megoldandó:')html(r'<center>$%s=%s%s-%s%sˆ{-1} \quad$ és $\quadãÑ%s=%s%s-%s%s$'%(latex(N),latex(G),latex(C),latex(As),ãÑlatex(G),latex(N),latex(G),latex(D),latex(Bt),latex(G)))

47
48
49

50

51
52

W1=G*D-Bt*G; W2=G*C-As*G
iw=ideal([W1[0,0],W1[0,1],W1[1,0],W1[1,1],W2[0,0],ãÑ
W2[0,1],W2[1,0],W2[1,1]])
html('<br><center>Ehhez az alábbi egyenlentrendszer
ãÑmegoldásása szükséges:')for y in [0..1]:
for z in [0..1]:
18

53
54
55
56

pretty_print(W1[y][z],'=',0)
for y in [0..1]:
for z in [0..1]:
pretty_print(W2[y][z],'=',0)

57
58

59
60
61
62

63

html('<br><center>Az egyenletrendszer megoldásátãÑmegkönnyı́ti a Gröbner bázis megadása, amelyhez ezãÑesetben:')
GB=iw.groebner_basis()
pretty_print(GB)
GBList=[] #GB with symbolic variables
for i in GB:ãÑ
GBList.append(Ptmp(i(g1=X1,g2=X2,g3=X3,g4=X4,s=Y1,t=Y2))
ãÑ(X1=x1,X2=x2,X3=x3,X4=x4,Y1=S,Y2=T))
XVar=[x1,x2,x3,x4]

64
65

66
67
68
69
70
71
72
73
74
75

#V1:variables in GB parts, V2:amount of variables,ãÑ
V3:V2 sorted
V1=[y.variables() for y in GBList]
V2=[]
for y in [0..len(XVar)-1]:
n=0 #number for index
for z in [0..len(GBList)-1]:
if XVar[y] in V1[z]:n+=1V2.append((n,XVar[y]))V3=sortfv(copy(V2));
x=V3[0][1];ãÑ
g=Ptmp(x(x1=X1,x2=X2,x3=X3,x4=X4))(X1=g1,X2=g2,X3=g3,X4=g4)
ãÑ#x:special xi element, g: x in GF(p)

76
77
78
79
80
81
82
83
84

85

PrevC=[] #PreviouslyChecked
ESol=[] #EquationSolutions
for y in [0..len(GBList)-1]:
VarT=list(V1[y])z=0
lh=len(VarT)-1 #length
while z<=lh:
if bool(VarT[z]==x) or (VarT[z] in PrevC) orãÑ(VarT[z] not in XVar):
r=VarT.index(VarT[z]) #removable item
19

86
87
88
89
90
91
92
93
94

95

VarT.remove(VarT[r])
lh-=1
else:
z+=1
if len(VarT)!=0:
ESol.append((solve(GBList[y],VarT[0]))[0])
if len(VarT)!=0:
PrevC.append(VarT[0])html('<br><center>A Gröbner bázisból $g1,g2,g3,g4$
ãÑvátozók kifejezése $%s$ segı́tségével:'%(latex(g)))
pretty_print(ESol)

96
97
98
99
100

X=matrix(2,2,[x1,x2,x3,x4])
for i in [1..3]:for y in ESol:
X=X.substitute({y.lhs():y.rhs()})

101
102

H=[Ptmp(a.numerator()(x1=X1,x2=X2,x3=X3,x4=X4,S=Y1,T=Y2))(X1=g1,X2=g2,X3=g3,X4=g4,Y1=s,Y2=t)/Ptmp(a.denominator()(x1=X1,x2=X2,x3=X3,x4=X4,S=Y1,T=Y2))
ãÑ(X1=g1,X2=g2,X3=g3,X4=g4,Y1=s,Y2=t) for a inãÑ
copy(X.list())]ãÑ
V=matrix(2,2,H)
G1=V*C-As*V; G2=V*D-Bt*V;
GmatList=[G1,G2]
html('<br><center> A $G$ mátrixba visszahelyettesı́tveãÑ
az imént kiszámolt $g1,g2,g3,g4$ értékeket, majdãÑkiszámolva $G1=G\cdot C-Aˆs\cdot G, \ G2=G\cdotãÑD-Bˆt\cdot G$ adódik:')html('<center>$G1=%s \quad$ és $\quadãÑ
G1=%s$'%(latex(G1),latex(G2)))
N=[]
ãÑ
ãÑ

103
104
105
106

107

108
109
110
111
112
113

for I in GmatList:
if I!=matrix(2):for y in [0..1]:
for w in [0..1]:

20

114

if I[y][w]!=0: N.append(solve_mod(PtmpãÑ((I[y][w].numerator()/g)ãÑ(g1=X1,g2=X2,g3=X3,g4=X4,s=Y1,t=Y2))
ãÑ(X1=x1,X2=x2,X3=x3,X4=x4,Y1=S,Y2=T),p))

115
116
117
118
119
120
121

122

for i in [0..len(N)-1]:
N[i]=Set(N[i])ST=N[0]for y in [1..len(N)-1]:
ST=ST.intersection(N[y])html('<br><center>$G1$ és $G2$ elemet figyelembe véveãÑ$s$ és $t$-re adódó feltételek:')pretty_print(ST)

123
124
125

126
127
128

129
130
131
132
133

134

135
136
137
138

T1=W1(s=ST[0][0],t=ST[0][1]).list()
for y in [0..len(T1)-1]:ãÑT1[y]=Ptmp(T1[y](g1=X1,g2=X2,g3=X3,g4=X4,s=Y1,t=Y2))
ãÑ(X1=x1,X2=x2,X3=x3,X4=x4,Y1=S,Y2=T)
S1=Set(solve_mod(T1,p))
T2=W2(s=ST[0][0],t=ST[0][1]).list()
for y in [0..len(T2)-1]:ãÑT2[y]=Ptmp(T2[y](g1=X1,g2=X2,g3=X3,g4=X4,s=Y1,t=Y2))
ãÑ(X1=x1,X2=x2,X3=x3,X4=x4,Y1=S,Y2=T)
S2=Set(solve_mod(T2,p))GEm=(S1.intersection(S2)).list() #GElements
if (0,0,0,0) in GEm:
GEm.remove((0,0,0,0))
html('<br><center>A lehetésges $s,t$ értékek közülãÑválasszul például $s=%s,ãÑ
t=%s$'%(latex(ST[0][0]),latex(ST[0][1])))
html('<br><center>Ezeket visszahelyettesı́tve $G1$ ésãÑ$G2$ mátrixokba, majd az adódó négyismeretlenesãÑegyenletrendszert megoldva $g1,g2,g3,g4$ értékei azãÑalábbiak lehetnek')for y in GEm:pretty_print(y)G=matrix(GF(p),2,2,GEm[0])html('<br><center>Egy szabadon választott megoldástãÑ
kiválasztva, például $%s$, a $g1,g2,g3,g4$ elemekãÑközül, adódik az alábbi $G$ãÑmátrix'%(latex(GEm[0])))
21

139
140
141

html('<center>$G=%s$'%(latex(G)))
W1=G*D-Bt*G
W2=G*C-As*G

142
143
144

P.<i,j,k,l>=PolynomialRing(GF(p),4)
M1=G*M*G.inverse(); MOr=M; M=M1

145
146

147

148
149
150

html('<center>Alkalmazzuk a speciális generátorokkal
ãÑhasznált módszert $M_1=G*M*Gˆ{-1}$-re,ahol:')html(r'<center>$M_1=%s=%s %sãÑ
%s$'%(latex(M1),latex(G),latex(MOr),latex(G.inverse())))
Ai=matrix(P,[[1,i],[0,1]]); Ak=matrix(P,[[1,k],[0,1]])
Bj=matrix(P,[[1,0],[j,1]]); Bl=matrix(P,[[1,0],[l,1]])
Mi=Ai*Bj*Ak*Bl

151
152

153
154
155

156
157
158
159
160

161

162
163
164

165

I=ideal(Mi[v][w]-M[v][w] for v in [0..1] for w inãÑ
[0..1])
IList=[Mi.list()[w]-M[w//2][w%2] for w in [0..3]]
GB=I.groebner_basis()
LIS=[Ptmp(g(i=X1,j=X2,k=X3,l=X4))
ãÑ(X1=x1,X2=x2,X3=x3,X4=x4)==0 for g in GB]
Sol=solve_mod(LIS,p)s=ST[0][0]; t=ST[0][1]
SolFn=[]for y in [0..len(Sol)-1]:
SolFn.append((Sol[y][0]*inverse_mod(int(s),p),ãÑSol[y][1]*inverse_mod(int(t),p),ãÑSol[y][2]*inverse_mod(int(s),p),ãÑSol[y][3]*inverse_mod(int(t),p)))html('<br><center>Az eredeti egyenlerszer megoldásai azãÑalábbi $(i,j,k,l)$ számnégyesek:')
for t in [0..len(Sol)-1]:
pretty_print(SolFn[t])html('<br><center>Vagyis az $%s$ megoldása a GDLPãÑ
problémának, ugyanis:'%(latex(SolFn[0])))html(r'<center>$%s=%sˆ{%s}%sˆ{%s}%sˆ{%s}%sˆ{%s}$'ãÑ%(latex(MOr),latex(C),latex(SolFn[0][0]),latex(D),ãÑlatex(SolFn[0][1]),latex(C),latex(SolFn[0][2]),ãÑlatex(D),latex(SolFn[0][3])))22

Irodalomjegyzék[1] Ivana Ilic. The Discrete Logarithm Problem in Non-abelian Groups. PhD
thesis, Boca Raton, FL, USA, 2010.
[2] Andrew V Sutherland. Order Computations in Generic Groups. PhD
thesis, Cambridge, MA, USA, 2007.
[3] Alfred J. Menezes, Scott A. Vanstone, and Paul C. Van Oorschot. Handbook of Applied Cryptography. CRC Press, Inc., Boca Raton, FL, USA,
1st edition, 1996.
[4] Lee C. Klingler, Spyros Magliveras, Fred Richman, and Michal Sramka.
Discrete logarithms for finite groups. 85:3–19, 06 2009.
[5] Michal Sramka. New Results in Group Theoretic Cryptology. PhD thesis,
Boca Raton, FL, USA, 2006. AAI3239161.
[6] The Sage Developers. SageMath, the Sage Mathematics Software System(Version 8.1), 2018. http://www.sagemath.org.
[7] Ivana Ilic and Spyros Magliveras. Weak discrete logarithms in non-abeliangroups. 74, 08 2010.

23