Diszkr´et matematika 11. el˝oad´as ´ MARTON Gy¨ ongyv´er Sapientia Egyetem, M˝ uszaki ´ es Hum´ antudom´ anyok Tansz´ ek Marosv´ as´ arhely, Rom´ ania
[email protected]
2016, ˝ oszi f´ el´ ev
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Mir˝ol volt sz´o az elm´ult el˝oad´ason?
legnagyobb k¨ oz¨ os oszt´ o az eukleid´eszi algoritmus ´es v´ altozatai line´ aris kongruenci´ ak modul´ aris inverz az RSA titkos´ıt´ o, baby v´ altozat
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Mir˝ol lesz sz´o?
megjegyz´esek az el˝ oz˝ o el˝ oad´ ashoz: inverz f¨ uggv´eny, vide´ o, anim´ aci´ o megjegyz´esek a 6. labor 4-es feladat´ ahoz az RSA sz¨ oveg, b´ ajtsorozat titkos´ıt´ asa, baby v´ altozat legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ os diofantoszi egyenletek a k´ınai marad´ekt´etel
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Az RSA, sz´amp´elda Kulcsgener´ al´ as Legyen p = 61, q = 97 k´et pr´ımsz´ am. Meghat´ arozzuk: n = 61 · 97 = 5917, φ = (p − 1) · (q − 1) = 60 · 96 = 5760. Legyen e = 7, ahol lnko(7, φ) = 1. Meghat´ arozzuk e inverz´et (mod φ) szerint, kapjuk: d = 823, mert 7 · 823 = 1 (mod 5760). A nyilv´ anos-kulcs : (7, 5917). A titkos-kulcs : (823, 5917). Titkos´ıt´ as (b´ arki titkos´ıthat) Az x = 2014 ´ert´eket szeretn´ek titkos´ıtani, ekkor a titkos´ıtott ´ert´ek: cx = 20147 ≡ 1526 (mod 5917). Visszafejt´es (csak a titkos-kulcs birtokosa tud visszafejteni) x = 1526823 ≡ 2014 (mod 5917). ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Az RSA, b´ajtsorozat titkos´ıt´asa
b´ ajtsorozat: [0,255] k¨ oz¨ otti ´ert´ekb˝ ol ´ all´ o sorozat, azaz 256-os sz´ amrendszerbeli sz´ amjegyeket tartalmaz´ o sorozat, ezt fogjuk titkos´ıtani az RSA algoritmus egy nagy sz´ amot titkos´ıt: a b´ ajtsorozatot ´ at kell alak´ıtani nagy sz´ amm´ a, azaz a 256-os sz´ amrendszerbeli sz´ amjegyeket ´ at kell alak´ıtani 256l sz´ amrenszerbe, ahol l a b´ ajtsorozat hossza az alakit, f¨ uggv´eny, a bemeneti l hossz´ us´ ag´ u stringet ´ atalak´ıtja eg´esz sz´ amm´ a, (256-os sz´ amrendszerb˝ ol alak´ıt 256l sz´ amrendszerbe), a string elemeire alkalmazzuk a ord() k¨ onyvt´ arf¨ uggv´enyt, az vAlakit, f¨ uggv´eny, egy eg´esz sz´ amot ´ atalak´ıt egy l hossz´ us´ ag´ u stringg´e, (256l -es sz´ amrendszerb˝ ol alak´ıt 256-os sz´ amrendszerbe), alkalmazzuk a chr() k¨ onyvt´ arf¨ uggv´enyt.
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Az RSA, sz¨oveg-rejtjelez˝o def alakit(szoveg, l): szam = 0 pr = 1 for i in range(l): temp = ord(szoveg[i]) szam += temp * pr pr = pr << 8 return szam def vAlakit(szam, l): szoveg = ’’ for i in range(l): temp = szam & 255 szoveg += chr(temp) szam = szam >> 8 return szoveg ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Az RSA, sz¨oveg-rejtjelez˝o A feladat konstans kulcsokkal dolgozik, a kulcsgener´ al´ as az el˝ oz˝ o el˝ oad´ ason volt t´ argyalva. A f¨ uggv´ eny param´ etere az a karakterl´ anc amit titkos´ıtani szeretn´ enk. from random import randint import base64 def RSA_main (szoveg): k = 256 e = 3 p = 148569510378747575788228425143133393923 q = 118544365557834428591364998965090431971 n = p * q phi = (p-1) * (q-1) d = inverz(e, phi) l = len(szoveg) if l > k/8: print "nagyobb kulcs meret kell!" return print "encryption..." cszoveg = RSA_cryptS(e, n, l, k/8, szoveg) print "encrypted text: ", cszoveg print "encrypted text in base64: ", , base64.b64encode(cszoveg) print print "decryption..." nszoveg = RSA_decryptS(d, n, l, k/8, cszoveg) print "decrypted text: ", nszoveg
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Az RSA, sz¨oveg-rejtjelez˝o
def RSA_cryptS(e, n, l1, l2, szoveg): x = alakit (szoveg, l1) cx = pow (x, e, n) cszoveg = vAlakit (cx, l2) return cszoveg def RSA_decryptS(d, n, l1, l2, cszoveg): cx = alakit (cszoveg, l2) nx = pow(cx, d, n) nszoveg = vAlakit (nx, l1) return nszoveg
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A legkisebb k¨oz¨os t¨obbsz¨or¨os
Az a ´es b eg´esz sz´ amok legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ ose, az a legkisebb sz´ am amely oszthat´ o a-val ´es b-vel is. Jel¨ ol´ese: lkkt(a, b), vagy [a, b]. Kapcsolat a legnagyobb k¨ oz¨ os oszt´ oval: (a, b) · [a, b] = a · b. Q ai Q bi Q min{ai ,bi } Ha a = pi ´es b = pi , akkor lnko(a, b) = pi . Q ai Q bi Q max{ai ,bi } Ha a = pi ´es b = pi , akkor lkkt(a, b) = pi . Megjegyz´esek: k´et sz´ am pr´ımt´enyez˝ os felbont´ asa alapj´ an meghat´ arozhat´ o, teh´ at a k´et sz´ am legnagyobb k¨ oz¨ os oszt´ oja, legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ ose nagy sz´ amok eset´eben, a pr´ımt´enyez˝ os felbont´ as meghat´ aroz´ as´ ara nem ismert hat´ekony elj´ ar´ as, ekkor az eukleid´eszi algoritmust kell haszn´ alni
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Diofantoszi egyenletek eg´esz egy¨ utthat´ os t¨ obbismeretlenes algebrai egyenletek, amelyeknek megold´ asai eg´esz sz´ amok (ritk´ an term´eszetes vagy racion´ alis sz´ amok), elnevez´ese Diophantosz (3. sz´ azad), g¨ or¨ og matematikus ut´ an, csak els˝ ofok´ u k´etismeretlenes diofantoszi egyenletekkel fogunk foglalkozni: a · x + b · y = c,
1. t´etel Legyenek a, b eg´esz sz´ amok, u ´gy hogy d = lnko(a, b). Az a · x + b · y = c egyenletnek nincs megold´ asa az eg´esz sz´ amok k¨ or´eben, ha d nem osztja c-t. Ha d | c, akkor az egyenletnek v´egtelen sok megold´ asa van: x = x0 + (b/d) · n, y = y0 − (a/d) · n, ahol n eg´esz sz´ am ´es x0 , y0 az egyenlet egy partikul´ aris megold´ asa.
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Diofantoszi egyenletek, p´elda Egy el´ arus´ıt´ o 1676 ron ´ert´ekben rendelt alm´ at ´es k¨ ort´et. Minden l´ ada alma 36 ronba, ´es minden l´ ada k¨ orte 50 ronba ker¨ ul. H´ any l´ ada alm´ at ´es h´ any l´ ada k¨ ort´et rendelt? 1. megold´ as: 16 l´ ada alm´ at ´es 22 l´ ada k¨ ort´et rendelt, 16 · 36 + 22 · 50 = 1676. 2. megold´ as: 41 l´ ada alm´ at ´es 4 l´ ada k¨ ort´et rendelt, 41 · 36 + 4 · 50 = 1676. A megold´ as menete: Meghat´ arozzuk 36, 50 legnagyobb k¨ oz¨ os oszt´ oj´ at: d = 2. Megvizsg´ aljuk, hogy d = 2 osztja-e 1676-ot. A kiterjesztett eukleid´eszi algoritmussal meghat´ arozzuk: x = 7, y = −5 ´ert´ekeket: 7 · 36 + (−5) · 50 = 2. 1676 Megszorozzuk az egyenletet = 838 -cal. d Egy partikul´ aris megold´ as x0 = 5866, y0 = −4190: 5866 · 36 − 4190 · 50 = 1676 a feladat megold´ as´ ahoz a pozit´ıv megold´ asok kellenek ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Diofantoszi egyenletek
Keress¨ uk a pozit´ıv megold´ asokat, fenn kell ´ alljon: 50 · n = 5866 + 25 · n d
≥0
⇒n
≥ −234.64
36 · n = −4190 − 18 · n d
≥0
⇒n
≤ −232.7
5866 + −4190 +
⇒
n= x1 = y1 =
−234 5866 + 25 · (−234) = 16 −4190 − 18 · (−234) = 22
⇒
n= x2 = y2 =
−233 5866 + 25 · (−233) = 41 −4190 − 18 · (−233) = 4
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Diofantoszi egyenletek, p´elda
Egy el´ arus´ıt´ o 549 ron ´ert´ekben rendelt alm´ at ´es k¨ ort´et. Minden l´ ada alma 18 ronba, ´es minden l´ ada k¨ orte 33 ronba ker¨ ul. Mennyi az a minim´ alis l´ adasz´ am amit az el´ arus´ıt´ o rendelhetett? Megold´ asok: 25 l´ ada alma ´es 3 l´ ada k¨ orte, o ¨sszesen 28 l´ ada 14 l´ ada alma ´es 9 l´ ada k¨ orte, o ¨sszesen 23 l´ ada 3 l´ ada alma ´es 15 l´ ada k¨ orte, o ¨sszesen 18 l´ ada Az el´ arus´ıt´ o 18 l´ ada gy¨ um¨ olcs¨ ot rendelt.
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Diofantoszi egyenletek A megold´ as menete: Meghat´ arozzuk 18 ´es 33 legnagyobb k¨ oz¨ os oszt´ oj´ at: d = 3. Megvizsg´ aljuk, hogy d = 3 osztja-e 549-et. A kiterjesztett eukleid´eszi algoritmussal meghat´ arozzuk: x = 2, y = −1 ´ert´ekeket: 2 · 18 + (−1) · 33 = 3. 549 Megszorozzuk az egyenletet = 183 - mal. d Egy partikul´ aris megold´ as x0 = 366, y0 = −183. Keress¨ uk a pozit´ıv megold´ asokat, fenn kell ´ alljon: 366 +
33 · n = 366 + 11 · n d
≥0
⇒ n ≥ −33.2
−183 −
18 · n = −183 − 6 · n d
≥0
⇒ n ≤ −30.5
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Diofantoszi egyenletek
⇒
n= x1 = y1 =
−33 366 + 11 · (−33) = 3 −183 − 6 · (−33) = 15
⇒
n= x2 = y2 =
−32 366 + 11 · (−32) = 14 −183 − 6 · (−32) = 9
⇒
n= x3 = y3 =
−31 366 + 11 · (−31) = 25 −183 − 6 · (−31) = 3
A minimumot az x1 = 3, y1 = 15 megold´ as adja, ami o ¨sszesen 18 l´ ad´ at jelent.
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Egy k´etismeretlenes diofantikus egyenlet pozit´ıv megold´asai from math import ceil, floor def diofant (a, b, c): (d, x, y) = extEuclid (a, b) if c % d <> 0: print "no solution" return x *= c/d y *= c/d bd = b/d ad = a/d n1 = int (ceil(-x / float(bd))) n2 = int (floor(y / float(ad))) for i in range(n1, n2 + 1): print x + bd * i, y - ad * i
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A k´ınai marad´ekt´etel Feladat: Ha egy toj´ asokkal teli kos´ arb´ ol kivessz¨ uk a toj´ asokat 2, 3, 4, 5, majd 6 -os´ aval, akkor rendre 1, 2, 3, 4, 5 toj´ as marad mindig a kos´ arban. Ha 7-es´evel vessz¨ uk ki nem marad egy toj´ as sem. H´ any toj´ as van a kos´ arban? A feladat az al´ abbi kongruencia rendszerrel modellezhet˝ o: x x x x x x
≡ ≡ ≡ ≡ ≡ ≡
1 2 3 4 5 0
(mod (mod (mod (mod (mod (mod
2) 3) 4) 5) 6) 7)
Mi a fenti rendszer megold´ asa?
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A k´ınai marad´ekt´etel 2. t´etel Legyenek m1 , m2 , ..., mr pozit´ıv, p´ aronk´ent relat´ıv pr´ımek. Ekkor az x x .. . x
≡ ≡
a1 a2
(mod m1 ) (mod m2 )
≡
ar
(mod mr )
kongruencia rendszernek M = m1 · m2 · ... · mr modulus szerint egy megold´ asa van. A megold´ as meghat´ aroz´ as´ anak menete: meghat´ arozzuk: Mk = M/mk = m1 · m2 · ... · mk−1 · mk+1 · ... · mr , meghat´ arozzuk az Mk ´ert´ekek inverz´et (mod mk ) szerint, jel¨ olj¨ uk ezeket Mˆk -val, ˆ1 + a2 · M2 · M ˆ2 + ... + ar · Mr · M ˆr lesz a rendszer megold´ x = a 1 · M1 · M asa. ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A k´ınai marad´ekt´etel A toj´ asos feladat az al´ abbi kongruencia rendszerre vezethet˝ o vissza: x x x
≡ ≡ ≡
4 (mod 5) 11 (mod 12) 0 (mod 7)
mert az x ≡ 3 (mod 4) egyenlet megold´ asai kiel´eg´ıtik az x ≡ 1 (mod 2) egyenlet megold´ asait, az x ≡ 5 (mod 6) egyenlet megold´ asai kiel´eg´ıtik az x ≡ 2 (mod 3) egyenlet megold´ asait, az x ≡ 11 (mod 12) egyenlet megold´ asai kiel´eg´ıtik az x ≡ 3 (mod 4) ´es x ≡ 5 (mod 6) egyenletek megold´ asait.
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A k´ınai marad´ekt´etel
A megold´ as menete: a1 = 4, a2 = 11, a3 = 0, m1 = 5, m2 = 12, m3 = 7, M = 420, M1 = 84, M2 = 35, M3 = 60, ˆ1 = 4, M ˆ2 = 11, M ˆ3 = 2, M vegy¨ uk ´eszre, hogy fenn´ all: ˆ1 = 1 M1 · M ˆ2 = 1 M2 · M ˆ3 = 1 M3 · M
(mod m1 ) (mod m2 ) (mod m3 )
84 · 4 = 1 35 · 11 = 1 60 · 2 = 1
x = 84 · 4 · 4 + 11 · 11 · 35 + 5 · 60 · 0 = 119 (mod 420).
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
(mod 5) (mod 12) (mod 7)
