Mintafeladat az RSA algoritmus szeml´eltet´es´ere Feladat Adottak a p = 269 ´es q = 241 pr´ımsz´amok, tov´abb´a az e = 53201 nyilv´anos kulcs ´es az x = 48055 ny´ılt sz¨oveg. • Sz´amolja ki n = p · q ´es ϕ(n) ´ert´ek´et! • Igazolja az euklideszi algoritmussal, hogy ϕ(n) ´es e relat´ıv pr´ımek, majd szint´en az euklideszi algoritmust felhaszn´alva sz´amolja ki az e sz´am multiplikat´ıv inverz´et modulo ϕ(n) ! • Titkos´ıtsa az x u ¨zenetet az n ´es e nyilv´anos kulcsok seg´ıts´eg´evel! • Fejtse vissza az el˝oz˝o pontban kapott kriptosz¨ovegb˝ol az eredeti ny´ılt sz¨oveget! ´s Megolda . n = pq = 269 · 241 = 64829; ϕ(n) = (p − 1)(q − 1) = 268 · 240 = 64320. . Az euklideszi algoritmus v´egrehajt´asa sor´an az al´abbi marad´ekos oszt´asokat kellett kisz´amolni. A legnagyobb k¨oz¨os oszt´o az utols´o nem nulla marad´ek (a bekeretezett marad´ek): gcd(ϕ(n), e) = 1, azaz ϕ(n) ´es e val´oban relat´ıv pr´ımek. 64320 53201 11119 8725 2394 1543 851 692 159 56 47 9 2
= = = = = = = = = = = = =
1 4 1 3 1 1 1 4 2 1 5 4 2
· 53201 + 11119 · 11119 + 8725 · 8725 + 2394 · 2394 + 1543 · 1543 + 851 · 851 + 692 · 692 + 159 · 159 + 56 · 56 + 47 · 47 + 9 · 9 + 2 · 2 + 1 · 1 + 0
Legyen d az e sz´am multiplikat´ıv inverze modulo ϕ(n) . (d l´etezik, mivel ϕ(n) ´es e relat´ıv pr´ımek.) A meghat´aroz´as´ahoz az el˝oz˝o t´abl´azatban lefel´e haladva soronk´ent kell kifejezni az oszt´asi marad´ekokat ϕ(n)-nel ´es e-vel. (A r´eszleteket csak az els˝o p´ar sorban k¨oz¨olj¨ uk, az ´attekinthet˝os´eg miatt ϕ(n) helyett itt ink´abb az F bet˝ ut haszn´aljuk.) 11119 = F − e 8752 = e − 4 · 11119 = e − 4 · (F − e) = −4 · F + 5 · e 2394 = 11119 − 8725 = (F − e) − (−4 · F + 5 · e) = 5 · F − 6 · e 1543 = 8725 − 3 · 2394 = (−4 · F + 5 · e) − 3(5 · F − 6 · e) = −19 · F + 23 · e 851 = 2394 − 1543 = (5 · F − 6 · e) − (−19 · F + 23 · e) = 24 · F − 29 · e 692 = −43 · F + 52 · e 159 = 67 · F − 81 · e 56 = −311 · F + 376 · e 47 = 689 · F − 833 · e 9 = −1000 · F + 1209 · e 2 = 5689 · F − 6878 · e 1
1 = −23756 · F + 28721 · e ⇒ 1 ≡ 28721 · e (mod ϕ(n)) ⇒ d = 28721. . Az y kriptosz¨oveg el˝oa´ll´ıt´asa y ≡ xe (mod n)
⇔
y ≡ 4805553201 (mod 64829)
alapj´an t¨ort´enik. Ennek gyors lebonyol´ıt´asa ´erdek´eben a kitev˝ot kett˝o hatv´anyainak ¨osszegek´ent ´all´ıtjuk el˝o: 53201 = 215 + 214 + 211 + 210 + 29 + 28 + 27 + 26 + 24 + 20 . Ezt felhaszn´alva 15
14
11
10
9
8
7
6
4
0
x53201 = x2 · x2 · x2 · x2 · x2 · x2 · x2 · x2 · x2 · x2 = = (((. . . (12 )x)2 x)2 )2 )2 x)2 x)2 x)2 x)2 x)2 x)2 )2 x)2 )2 )2 )2 x. Minden l´ep´esben (mod 64829) kell a n´egyzetre emel´eseket ´es a szorz´asokat tekinteni. Teh´at el˝osz¨or (12 ·48055)2 ·48055 ≡ 27981 (mod 64829), majd 279812 ≡ 61357 (mod 64829), ut´ana 613572 ≡ 61419 (mod 64829), 614192 · 48055 ≡ 31149 (mod 64829), stb. A k¨ovetkez˝o sz´amol´asok eredm´enyei: 22178, 49487, 35533, 25004, 60979, 41488, 9459, 8661, 5768, 12547, 61606 (mod 64829). A v´egeredm´eny lesz a keresett kriptosz¨oveg: y = 61606, ezt kell elk¨ uldeni a c´ımzettnek. . A d = 28721 titkos kulccsal lehet megfejteni az y kriptosz¨oveget, m´egpedig x ≡ y d (mod n)
⇔
x ≡ 6160628721 (mod 64829)
kisz´am´ıt´as´aval. Itt a felbont´ast nem r´eszletezz¨ uk, de a sorozatos n´egyzetre emel´esek (mod 64829) eredm´enyeit k¨oz¨olj¨ uk a nyomon k¨ovethet˝os´eg kedv´e´ert: 54732, 53646, 4348, 39865, 119, 14161, 17824, 32876, 16282, 58318, 59784, 39057, 22879, 48055. Mint l´athat´o, a legutols´o sz´am val´oban a kiindul´asi ny´ılt sz¨oveg x = 48055.
2
Mintafeladat a h´atizs´ak algoritmus szeml´eltet´es´ere Feladat Adott a {vk }10 ovekv˝o so0 = {1, 3, 7, 14, 28, 54, 110, 219, 437, 875, 1750} szupern¨ rozat ´es az m = 3527 primmodulus, tov´abb´a az a = 2222 sz´am ´es az x = 666 ny´ılt sz¨oveg. • Az euklideszi algoritmust felhaszn´alva sz´amolja ki az a sz´am b multiplikat´ıv inverz´et modulo m! ´ ıtsa el˝o a megadott {vk }10 sorozat, az a sz´am ´es az m modulus seg´ıts´eg´evel a • All´ k=0 {wk }10 nyilv´ a nos kulcsot! k=0 ¨zenetet, majd titkos´ıtsa azt a nyilv´anos kulcs • ´Irja fel kettes sz´amrendszerben az x u seg´ıts´eg´evel (jel¨olje C az ´ıgy kapott kriptosz¨oveget)! • Fejtse vissza a C kriptosz¨ovegb˝ol az eredeti ny´ılt sz¨oveget! ´s Megolda .
3527 2222 1305 917 388 141 106 35
= 1 = 1 = 1 = 2 = 2 = 1 = 3 = 35
· 2222 + 1305 · 1305 + 917 · 917 + 388 · 388 + 141 · 141 + 106 · 106 + 35 · 35 + 1 · 1 + 0
Hasonl´oan az el˝oz˝o mintafeladathoz, az 1 -et mint a 3527 ´es 2222 legnagyobb k¨oz¨os oszt´oj´at ki lehet fejezni 3527 ´es 2222 eg´eszegy¨ utthat´os line´aris kombin´aci´ojak´ent (a sz´amol´ast most nem r´eszletezz¨ uk). gcd(3527, 2222) = 1 = 63 · 3527 − 100 · 2222 ⇒ 1 ≡ −100 · 2222 (mod 3527) ⇒ b = 3427 = 3527 − 100 ≡ −100 (mod 3527). . A {wk } sorozat tagjait a wk ≡ a · vk (mod m) k´eplet szolg´altatja: {wk }10 0 = {2222, 3139, 1446, 2892, 2257, 70, 1057, 3419, 1089, 873, 1746}. . x = 666 = (01010011010)2 , ´es az´ert ´ırtunk az x sz´am kettes sz´amrendszerbeli alakj´anak elej´ere egy 0-t, hogy mind a tizenegy bit fel legyen t¨ untetve. Ha az k-adik bitet εk jel¨oli, akkor a C kriptosz¨oveget az x ny´ılt sz¨ovegb˝ol a C=
10 X
εk wk
k=0
formul´aval lehet meghat´arozni. Eszerint C = 12580. . A C kriptosz¨oveg megfejt´es´ehez a b titkos kulccsal kell beszorozni C-t modulo m, majd osszegek´ent kell fel´ırni. az ´ıgy kapott sz´amot a szupern¨ovekv˝o {vk }10 0 sorozat elemeinek ¨ b · C = 12580 · 3427 ≡ 1139 (mod 3527). 1139 = 875+219+28+14+3 = 1·v9 +0·v8 +1·v7 +0·v6 +0·v5 +1·v4 +1·v3 +0·v2 +1·v1 +0·v0 , ahonnan x = (1010011010)2 = 666. 3
Mintafeladat a 2 × 2-es m´atrixj´at´ekok elemz´es´ere Feladat Tekints¨ uk az
"
A=
6 −4 −2 8
#
m´atrixszal megadott m´atrixj´at´ekot. • Igazolja, hogy a j´at´ekosoknak nincs tiszta strat´egi´ajuk! • Hat´arozza meg grafikus m´odszerrel a j´at´ekosok kevert strat´egi´ait, ´es a j´at´ek ´ert´ek´et! • Hat´arozza meg algebrai m´odszerrel a j´at´ekosok kevert strat´egi´ait, ´es a j´at´ek ´ert´ek´et! uk fel, hogy a m´asodik j´at´ekos a bank. Mennyi´ert adja a bank az els˝o j´at´ekosnak • Tegy¨ egy j´at´ek jog´at, hogy igazs´agos legyen a j´at´ek? ´s Megolda . Az A m´atrix sorminimumainak maximuma nem egyezik meg az oszlopmaximumok minimum´aval (−2 6= 6), teh´at nincsenek tiszta strat´egi´ak. Jel¨olj¨ uk a meghat´arozand´o kevert strat´egi´at az els˝o j´at´ekosn´al [p, 1 − p]-vel, a m´asodik j´at´ekosn´al [q, 1 − q]-val. . Az al´abbi egyenl˝otlens´egeket kell grafikus u ´ton megoldani.
6p − −4p +
2(1 − p) ≥ v 8(1 − p) ≥ v v → max (0 ≤ p ≤ 1)
6q − −2q +
4(1 − q) ≤ v 8(1 − q) ≤ v v → min (0 ≤ q ≤ 1)
v
v
8
8
1
A 0
1
A
p
0
-2
1 q
2 -4
2
1
1. ´abra. p ´es q meghat´ aroz´ asa grafikus u ´ton.
4
Ehhez a v = −2 + 8p ´es v = 8 − 12p valamint a v = −4 + 10q ´es v = 8 − 10q egyenlet˝ u egyeneseket kell felt¨ untetni. (Az ´abr´akon az egyenesek sorsz´amoz´asa a fel´ır´asuk sorrendj´eben t¨ort´ent.) Mindk´et ´abr´an az A pont koordin´at´ait kell meghat´arozni. Az els˝o esetben a v = −2+8p = 8−12p egyenletekb˝ol p = 21 , v = 2. A m´asodik esetben v = −4+10q = 8−10q miatt q = 35 , v ism´et 2. Teh´at az optim´alis strat´egi´ak [p, 1 − p] = [1/2, 1/2] ´es [q, 1 − q] = [3/5, 2/5]. . A p ´es q val´osz´ın˝ us´egek mellett az els˝o j´at´ekos nyerem´eny´enek v´arhat´o ´ert´eke ³
E(p, q) = 6pq − 4p(1 − q) − 2(1 − p)q + 8(1 − p)(1 − q) = 20 pq − 53 p − 12 q + ³
= 20 p −
1 2
´³
q−
3 5
´
2 5
´
=
+ 2.
Teh´at a j´at´ek ´ert´eke 2, amely az els˝o j´at´ekosnak kedvez˝o. Az optim´alis strat´egi´ak: [p, 1 − p] = [1/2, 1/2], [q, 1 − q] = [3/5, 2/5]. . A kor´abbiak szerint az els˝o j´at´ekos j´at´ekonk´ent ´atlagosan 2 p´enzegys´eget nyer a m´asodikt´ol. Ha ennyibe ker¨ ul a j´at´ek az els˝o sz´am´ara, akkor j´at´ekjog megv´etel´evel az egy j´at´ekra jut´o ´atlagos nyerem´enye 0 lesz, mik¨ozben a m´asodik j´at´ekos a j´at´ekban elszenvedett vesztes´eg´et a j´at´ekjog d´ıj´aval kompenz´alja. A j´at´ek ´ara teh´at k´et p´enzegys´eg legyen.
5
Mintafeladat a 2 × n-es ill. k × 2-es m´atrixj´at´ekok elemz´es´ere Feladat Tekints¨ uk az
"
D=
−1 14 8 −4 5 4 −6 −2 6 2
#
m´atrixszal megadott m´atrixj´at´ekot. • Igazolja, hogy a j´at´ekosoknak nincs tiszta strat´egi´ajuk! • Hat´arozza meg grafikus m´odszerrel az els˝o j´at´ekos kevert strat´egi´aj´at ´es a j´at´ek ´ert´ek´et! • Az el˝obbi eredm´enyeket felhaszn´alva hat´arozza meg algebrai m´odszerrel a m´asodik j´at´ekos kevert strat´egi´aj´at! • Kinek el˝ony¨os a j´at´ek? Tegy¨ uk fel, hogy a fizet´esi m´atrix elemei forint kifizet´eseket jelentenek. V´arhat´oan mennyi p´enzt nyer az egyik j´at´ekos a m´asikt´ol, ha az optim´alis strat´egi´akat k¨ovetve 1000 j´at´ekot j´atszanak? ´s Megolda . A D m´atrix sorminimumainak maximuma nem egyezik meg az oszlopmaximumok minimum´aval (−4 6= 4), teh´at nincsenek tiszta strat´egi´ak. Jel¨olj¨ uk a meghat´arozand´o kevert strat´egi´at az els˝o j´at´ekosn´al [p, 1 − p]-vel, a m´asodik j´at´ekosn´al [q1 , q2 , q3 , q4 , q5 ]-tel (q1 + q2 + q3 + q4 + q5 = 1). . Az al´abbi egyenl˝otlens´egrendszert kell grafikus u ´ton megoldani. −p 14p 8p −4p 5p
+ − − + +
4(1 − p) 6(1 − p) 2(1 − p) 6(1 − p) 2(1 − p) v → max
≥ ≥ ≥ ≥ ≥
v v v v v (0 ≤ p ≤ 1)
Az egyenl˝otlens´egek bal oldala alapj´an a v = 4 − 5p, v = −6 + 20p, v = −2 + 10p, v = 6 − 10p, v = 2 + 3p egyeneseket kell ´abr´azolni a [0, 1] intervallumon. (A grafikonon az itteni fel´ır´asuk sorrendj´eben sorsz´amoztuk az egyeneseket.) Az egyenesek alatti tartom´anyok k¨oz¨os r´esz´enek legmagasabb pontj´at, A-t kiemelt¨ uk. Ez rajta van az els˝o n´egy egyenes mindegyik´en, ´es p meghat´aroz´as´ahoz a koordin´at´ait kell kisz´amolni. B´armely k´et, rajta ´athalad´o egyenes alkalmas erre, v´alasszuk pl. az els˝ot ´es a m´asodikat. Ekkor a v = 4 − 5p = −6 + 20p egyenletekb˝ol p = 25 , tov´abb´a v = 2 k¨ovetkezik. Teh´at az els˝o j´at´ekos optim´alis stat´egi´aja [p, 1 − p] = [2/5, 3/5], a j´at´ek ´ert´eke v = 2. . Az A ponton ´athalad´o egyenesek k¨oz¨ ul a negyediknek, azaz v = 6 − 10p-nek legkisebb a meredeks´ege; a legnagyobb meredeks´eg˝ u pedig a m´asodik, azaz a v = −6 + 20p egyenlet˝ u egyenes. A sz´oban forg´o k´et egyenest ´es a v = 2 eredm´enyt felhaszn´alva u ´gy kell megv´alasztani a λ ∈ IR, 0 ≤ λ ≤ 1 val´os sz´amot, hogy a λ(6 − 10p) + (1 − λ)(−6 + 20p) = 2 6
v
2
3 6
4 5
4 2
A 1
0
p
1
-2
-6
2. ´abra. p meghat´ aroz´ asa grafikus u ´ton. ´ egyenl˝os´eg minden p-re teljes¨ ulj¨on. Atrendezve (12λ − 6) + (20 − 30λ)p = 2-h¨oz jutunk, ahonnan 20 − 30λ = 0, teh´at λ = 23 (hasonl´o eredm´enyre vezet, ha 12λ − 6 = 2-b˝ol indulunk ki). Az egyenesek szorsz´am´ab´ol, valamint a λ ´es 1 − λ sz´amokb´ol fel´ırhatjuk a m´asodik j´at´ekos optim´alis strat´egi´aj´at: [q1 , q2 , q3 , q4 , q5 ] = [0, 1/3, 0, 2/3, 0]. . A kor´abbiak szerint az els˝o j´at´ekos j´at´ekonk´ent ´atlagosan 2 forintot nyer a m´asodikt´ol, ez´ert a j´at´ek sz´am´ara el˝ony¨os, ´es 1000 j´at´ek ut´an v´arhat´oan 2 · 1000 = 2000 forinttal gyarapodik. Igazs´agoss´a lehetne tenni a j´at´ekot, ha a D m´atrix minden elem´et 2-vel cs¨okkenten´enk.
7
Mintafeladat m´atrixj´at´ekok szimplex m´odszerrel val´o elemz´es´ere Feladat Tekints¨ uk a
4 −3 −5 3 0 B = −3 3 3 −5
m´atrixszal megadott m´atrixj´at´ekot. • Vizsg´alja meg, hogy van-e a j´at´ekosoknak tiszta strat´egi´ajuk! • Hat´arozza meg a szimplex m´odszerrel a j´at´ekosok strat´egi´ait, ´es a j´at´ek ´ert´ek´et (v)! ´s Megolda . A B m´atrix sorminimumainak maximuma nem egyezik meg az oszlopmaximumok minimum´aval (−3 6= 0), teh´at nincsenek tiszta strat´egi´ak. Jel¨olj¨ uk a meghat´arozand´o kevert strat´egi´at az els˝o j´at´ekosn´al [p1 , p2 , p3 ]-mal, a m´asodik j´at´ekosn´al [q1 , q2 , q3 ]-mal. . A szimplex m´odszerrel val´o megold´ashoz transzform´alni kell a B m´atrixot, mert nem csak pozit´ıv elemeket tartalmaz. Ez´ert B minden elem´ehez hozz´aadunk hatot, ekkor a B1 m´atrixhoz jutunk: 10 3 1 B1 = 3 9 6 . 9 9 1 A B1 m´atrix alapj´an fel´ırhat´o a 10x1 3x1 9x1 z = x1
+ 3x2 + 9x2 + 9x2 + x2
+ x3 + 6x3 + x3 + x3
≤ ≤ ≤ →
1 1 1 max (x1 , x2 , x3 ≥ 0)
line´aris programoz´asi feladat, amelyet a szimplex m´odszer alkalmaz´as´aval oldunk meg. Megengedett b´azistranszform´aci´ok (a gener´al´oelem pozit´ıv, ´es egy adott oszlopb´ol mindig a sz˝ uk keresztmetszetet kell v´alasztani) egym´as ut´ani alkalmaz´as´ava arra kell t¨orekedni, hogy a t´abl´azat als´o sor´aban csupa negat´ıv ´ert´ek legyen. A gener´al´oelemeket a szok´asoknak megfelel˝oen bekeretezt¨ uk.
x 1 6 u1 x 3 6 u2 x 2 6 u3
x1 x3 u3 6 x 2
x1 10 3 9 1
x2 x3 3 1 9 6 9 1
u1 5/39 2/13 -17/117 -16/117
1 1
b 1 1
u1 1/10 -3/10
x2 x3 3/10 1/10 81/10 57/10
1 0
-9/10 -1/10
63/10 7/10
u3 u2 -1/39 -2/117 -3/13 7/39 19/117 -1/351 11/117 -56/351
1/10 9/10
b 10/117 4/39 5/351 -71/351
8
b 1/10 7/10
u1 1/7 6/7
u3 -1/21 -9/7
x3 2/21 39/7
b 2/21 4/7
1/10 -1/10
-1/7 10/63 0 -1/9
1/63 8/9
1/63 -1/9
u1 2/19 -1/19 -17/19 -1/19
x2 u2 3/19 -1/57 27/19 10/57 117/19 -1/57 -11/19 -3/19
b 5/57 7/57 5/57 -4/19
A t´abl´azatb´ol az al´abbi megold´asok olvashat´ok le. Prim´al feladat: x = [x1 , x2 , x3 ] = [5/57, 0, 7/57]; az elt´er´esvektor [u1 , u2 , u3 ] = [0, 0, 5/57]. Du´al feladat: y = [y1 , y2 , y3 ] = [1/19, 3/19, 0]; az elt´er´esvektor [w1 , w2 , w3 ] = [0, 11/9, 0]. A maxim´alis (ill. minim´alis) ´ert´ek: ve = 4/19. Ezen eredm´enyeket felhaszn´alva a m´atrixj´at´ek megold´asa a k¨ovetkez˝o. ·
¸
·
¸
1 19 1 3 1 3 [p1 , p2 , p3 ] = · y = · , , 0 = , , 0 , ve 4 19 19 4 4 ·
[q1 , q2 , q3 ] =
¸
·
¸
1 19 5 7 5 7 ·x= · , 0, = , 0, , ve 4 57 57 12 12
1 5 −6=− . ve 4 A fentiek szerint az els˝o j´at´ekosnak rendre 1/4, 3/4 val´osz´ın˝ us´eggel kell v´alasztania az 1-es ´es 2-es strat´egi´akat, m´ıg a m´asodik j´at´ekosnak rendre 5/12, 7/12 val´osz´ın˝ us´eggel az 1-es ´es 3-as strat´egi´akat. A j´at´ek ´ert´eke −5/4 < 0, teh´at a m´asodik j´at´ekosnak el˝ony¨os. v=
9
Mintafeladat Pollard % algoritmus´anak szeml´eltet´es´ere Feladat Adott az N = 246733 term´eszetes sz´am, amelyet a Pollard f´ele % m´odszerrel szeretn´enk faktoriz´alni egy f (x) eg´eszegy¨ utthat´os polinom ´es az x0 kezd˝oelem ´altal gener´alt sorozat seg´ıts´eg´evel. • Bontsa fel k´et sz´am szorzat´ara N -et, ha f (x) = x2 + 1 ´es x0 = 2! • V´egezze el a szorzatt´a bont´ast egy m´asik polinomot ´es m´asik kezd˝oelemet felhaszn´alva! ´s Megolda . Az xn+1 ≡ f (xn ) (mod N ) iter´aci´ot kell alkalmazni x0 -b´ol kiindulva ”egyszeres ´es k´etszeres sebess´eggel”. A legnagyobb k¨oz¨os oszt´o meghat´aroz´as´ara ism´et az Euklideszi algoritmust haszn´altuk.
1 2 3 4 5 6 7 8 9
xn ≡ f (xn−1 ) (mod N ) x2n ≡ f (f (x2n−2 )) (mod N ) gcd(N, xn − x2n ) x0 = 2 x0 = 2 5 26 1 26 211597 1 677 126543 1 211597 99653 1 133298 225011 1 126543 28771 1 159150 90806 1 99653 86408 1 210626 222422 983
Teh´at 983 az egyik oszt´oja N = 246733-nak. Az oszt´ast elv´egezve megkapjuk N egy faktoriz´aci´oj´at: 246733 = 983 · 251. . Legyen most f (x) = x2 + 3, x0 = 3.
1 2 3 4 5 6
xn ≡ f (xn−1 ) (mod N ) x2n ≡ f (f (x2n−2 )) (mod N ) gcd(N, xn − x2n ) x0 = 3 x0 = 3 12 147 1 147 12978 1 21612 244820 1 12978 83650 1 156581 19002 1 244820 8127 251
M´asodszorra N -nek egy m´asik oszt´oj´at, a 251-et kaptuk. N felbont´asa megegyezik az el˝oz˝o´evel.
10
