HDD titkositas

Thu Oct 28 21:11:00 CEST 2004

Mivel a listat ugy latom nem olvassak csak irjak egyesek

RSA ugyben reggel megadtam az ertheto magyar leirasok helyet, most
megis arra jovok haza , hogy nem lett elolvasva semmi....

Ezert buntibol idemasolom az egyik iromanyt:
(es megismetlem a linkeket is)

PowerPoint diakban
http://www.netacademia.net/secu/konf/rsa2004.asp

A doc amit be masoltam a vegere...
http://www.netacademia.net/tudastar/pubarticle.aspx?fid=28

Itt pedig egy BASIC forras van , ami win-nel kiprobalhato
http://www.netacademia.net/tudastar/articlepage.aspx?upid=957

Ez meg egy primitiv bemutato:

Mint "tudjuk", az RSA titkosítás így zajlik:

T^e mod N = C

ahol T a titkosítandó Text, C pedig a titkosított változat, azaz Ciphertext.
(A ^ hatványozás, a mod pedig maradékos osztás.)
Kibontani így kell:

C^d mod N = T

Most egy olyan számpéldát adok Nektek, amivel mind a titkosítást, mind a
kibontást meg tudjátok tenni 100 alatti számokra ("Text").

Privát kulcs: e=91, N=10807
Publikus kulcs: d=3611, N=10807

Titkosítsuk mondjuk az 53-at (T=53), elo a Calc.EXE-vel (tudományos
nézetben!)!

53^91 mod 10807 = 9711

Tehát az 53 titkosítva: 9711. Most fejtsük meg a titkosítást:

9711^6311 mod 10807 = 53

KJ

-----------------------------------------------------------
Rivest, Shamir, Adleman
Ez a három úr egyike (hármika) annak a néhány kiválasztott elméleti
matematikusnak, akik eredményeiket a gyakorlatban is hasznosítani tudták. A
többi matematikus "csak" bebizonyítja, hogy végtelen számú prímszám van,
vagy kiszámolja P (pí) értékét négymillió jegyig - egyszóval semmi
aprópénzre válthatót nem alkot.

A mi embereink azonban 1977-ben megalkották a nyílt kulcsú titkosítás máig
el nem avult, fel nem tört algoritmusát, amellyel komplett iparágakat
teremtettek. Sot! Magyarországon épp most készül a digitális aláírásról
szóló törvény - a hármak bandája tehát országokat is mozgat!

Annyira egyszeru az RSA algoritmus képlete, hogy valószínuleg a dolog nem is
muködik. Fogod a titkosítanó dokumentumot, felemeled egy gigantikus
hatványra, majd az eredmény modulóját veszed... és ezzel látszólag
elveszíted az eredeti dokumentumot. De mégsem, mert ha egy másik hatalmas
számmal az eredményt ismét meghatványozod, majd megint modulóját veszed,
visszakapod az eredeti doksit. Hmmm. De miért? És meddig? Mi az esélye és
veszélye annak, hogy az RSA-t megtörik?

E sok kérdésre egyelore nem adom meg a választ, eloször ugyanis ismét
számmisztikázunk. Hatványozni fogunk, így számológép használata javasolt!

2. számmisztika

-Gondolj egy számot (T). (2 és 10 között, különben kiakad a számológéped.)

-Most keress egy tetszoleges prímszámot (N), mely NAGYOBB, mint az elozo
számod.

-Emeld a gondolt számot a (N-1). hatványra.

-Vedd az eredmény modulusát N-nel (modulus = maradékos osztás)

-A maradék: 1

Matekul ez így fest:

T(N-1) mod N = 1 (ha N nagyobb mint T, és N prímszám)

A fenti "trükk" megfejtéséhez már némileg több beleérzoképesseg kell. De nem
túl sok. Ezt a játékot már az ókorban is ismerték, Euler pedig
bebizonyította, hogy a képlet minden prímszámmal muködik, HA a prímszám
nagyobb, mint a gondolt szám. Ezek a prímszámok tudnak valamit, amire a
többi szám nem képes. Vegyük például ezt a másik, hasonló kiszámolót:

3. számmisztika

-Gondolj egy számot (T). (2 és 10 között, különben kiakad a számológéped. Ne
ugyanazt, mint az elobb!)

-Most keress egy tetszoleges prímszámot (N), mely NAGYOBB, mint az elozo
számod.

-Emeld a gondolt számot N. hatványra.

-Vedd az eredmény modulusát N-nel -A maradék: a gondolt szám.

Ez már igen érdekes! Matekul kifejezve:

TN mod N = T (ha N nagyobb mint T, és N prímszám)

Ez valójában nem más, mint a fentebbi, második számmisztikai egyenlet,
melynek mindkét oldalát megszoroztuk T-vel. Íme elottünk az RSA algoritmus
alapja, egy hatványozós, modulós képlet, mely visszaadja az eredeti számot!
Ez a játék azonban egyfelhasználós, az RSA-t viszont párban kell játszani
(Titkosító, Megfejto), másrészt ki engedte meg, hogy egy modulós képlet
mindkét oldalát büntetlenül megszorozzuk T-vel? Ki mondta, hogy igaz marad
az egyenlet? Egyelore zsákutcába jutottunk. Tegyük félre egy pillanatra a
játszadozást. Mi is a cél?

Ariadné, Indiana Jones és a függvények
Célunk egy olyan függvénypár találása, melyek egymást kiegészítve
visszavisznek a kiindulóponthoz. Ha a két függvény egyikét a Titkosító,
másikát a Megfejto alkalmazza, ugyanazt az adatot kapjuk vissza. Ilyen
függvénypárokat igen egyszeru találni, mivel gyakorlatilag mindegyik ilyen.
Legyen a titkosítás például az, hogy a titkosítandó számhoz hozzáadunk egyet
(hu, de bonyolult!):

Adat + 1 = titok

Ebben az esetben a kiegészíto függvény, mely az eredeti adatot visszaadja:

Titok - 1 = adat

Ugyanilyen formán a világ számtalan függvénye használható gagyi nyílt kulcsú
titkosításra a SIN()-tól a négyzetre emelésig, de egytol egyig mind gyatra,
mert tulajdonképpen nincs is szükségem a fordított függvényre - boven elég,
ha az eredeti muveletsorozatot lépésrol lépésre visszafelé hajtjuk végre.
Ariadné függvények, mert húzzák maguk után a fonalat, amelynek segítségével
bármilyen bonyolult labirintusból kitalálunk. De vegyük csak Indiana Jones
példáját. Bemegy egy barlangba, ahol a háta mögött leomlik a fal, árvíz
mossa el a hidakat, karók jönnek ki a földbol, és ha még ez sem elég, hát
meggyullad valami. Ott áll hosünk a barlang legmélyebb pontján bezárva,
látszólag reménytelenül (orra elott a dinkák osi bálványszobra), de ebben a
siralmas helyzetben hirtelen megtalálja a kivezeto utat ábrázoló térképet.
Ha nem Indiana Jones kavarodott volna be a barlangba, tutibiztos nem talált
volna ki, errol tanúskodnak a falak mentén némán üldögélo csontvázak.
(Hollywood nem spórol a dramaturgiai kaptafákkal.)

Ez kell nekünk! Olyan függvény, melybe ha besétáltunk, visszaút nincs többé.
Hiába próbálkozunk a lépések fordítottjával, a mennyezetrol lezuhant szikla
utunkat állja. Kijutni csak akkor tudunk, ha a bálvány talpa alól kihúzzuk a
térképet. Na ez az RSA. Aki nem tudja, hogy a bálvány lába alatt van a
térkép, az meghal.

Az ilyen függvényeket csapda (trapdoor) függvényeknek nevezzük. Az elso
muködo példával Diffe és Hellmann rukkolt elo 1975-ben, pontosan a második
számmisztikára alapozva. Most pedig lássuk, mi kell még:

1.       Moduloaritmetika és kongruencia

2.       Relatív prímek

3.       Euler fíje

4.       A szorzás, mint a helyzet megmentoje

1. Moduloaritmetika, kongruencia
Ha az a cél, hogy beomoljon az alagút, keresve sem találhatnánk jobb
matematikai muveletet a modulonál. Oly kiválóan fejbecsapja az áldozat
számot, hogy az eredménybol soha nem leszünk képesek visszaállítani az
eredetit. A modulo, vagy maradékos osztás életünk szerves részét képezi.
Amikor azt mondjuk, kettokor kezdodik a NATE, akkor valójában 14 óráról
beszélünk, modulo 12. Modulo 12-vel fejbevágva a 14 tulajdonképpen egyenlo
2-vel. Ezt a furcsa egyenloséget a matematikában kongruenciának hívják, és
hármas egyenloségjellel jelölik (º). Bármely szám bármely másikkal képzett
modulusát igen könnyu vizualizálni. A

127 mod 21 = 1

nem más, mint egy 21 "órából" álló számkör, melyre a 127-et "felcsavarjuk".
Többször körbefut, majd a vége valameddig elér a 21-es számkörön. Ez a
maradék a moduló végeredménye. A fenti írásmód a "hétköznapi". Ugyanez
matekul:

127 º 1 (mod 21)

Ennek olvasata: a 127 valójában ugyanaz, mint az egy, ha modulo 21-ben
gondolkozunk. A NATE 2-kor kezdodik Matekul így fest:

14 óra º 2 óra (mod 12-ben gondolkodva)

Hol találunk még modulót mindennapjainkban? Hát a számítógépeinkben. A mai
elterjedt processzorok 32 bitesek, ami tulajdonképpen annyit jelent, hogy
2^32-nel modulálnak minden egész számon végzett matematikai muveletet. Ha
túl nagy fába vágjuk a fejszénket, a túlcsordulás miatt könnyen azon
kaphatjuk magunkat, hogy

1 + 1 º 232 + 1 + 1

Hármas egyenloségjellel persze. De akkor már bánhatjuk.

Modulo a hét napjai (mod 7), a beszélt nyelv (220V= ketto-húsz, azaz mod
100) stb. Modulo mindenütt.

Érdekes, és késobb hasznunkra válik majd, hogy a moduloaritmetikában
(szinte) bármikor fejbecsaphatjuk a muvelet tagjait a modulussal, a számítás
elott, vagy a végeredményen - egyre megy. Példa:

Most 11 óra van. Mennyit mutat majd a vekker 27 óra múlva?

1. számítás: a modulo a végeredményre sújt le:

11+27 = 38 º 2 (mod 12 esetén)

2. számítás: a moduloval már a kedzoértékeket fejbecsapjuk

27 º 3 (mod 12-vel lecsapva)

11 º 11 (mod 12-vel lecsapva. Nem változik)

11 + 3 = 14 º 2 (mod 12)

Ez a trükk ráadásul nemcsak összeadásra, hanem könnyen belátható módon
gyorsított összeadásra, vagyis szorzásra is muködik! Egy tyúk levágásának és
feldolgozásának ideje 3 óra (forralás, belezés, belsoségek megtisztítása,
darabolás, csomagolás, fagyasztás). Sajnos 50 élo tyúkot kaptunk vidékrol
bele a panellakás  kellos közepébe. Ha délelott 11-kor kezdem, vajon fent
lesz-e a napocska, amikor befejezem? Egyedül csinálom, a feleségem nem ért
hozzá (nem sokat nyaralt vidéken gyermekkorában). Mivel a napocska hollétére
vagyok kíváncsi, mod 24-gyel dolgozom:

1. számítás: mod 24 a végeredményre

3 * 50 = 150 º 6 (mod 24) A nap épp keloben lesz.

2. számítás: mod 24 a kiindulási adatokra

50 mod 24 º 2 (mod 24)

2 * 3 = 6. A nap épp keloben lesz.

Hogy én beledöglök-e a több mint hatnapi megszakítás nélküli tyúkpucolásba?
Nem érdekes... Ennél sokkal fontosabb, hogy a moduloaritmetika bármikor
bevetheto. Például, ha egy modulós számítás során kezdene elszaladni az
eredmény a végtelen felé. Csak lesújtunk rá a modulóval, és rögtön nyugton
marad, mi pedig számolhatunk tovább.

2. Relatív prímek
Megy még a prímtényezokre bontás? Hatodik osztályos anyag. És hogy kapom meg
két szám legnagyobb közös osztóját? Segítek.

Prímtényezokre bontás:

18 = 2 * 3 * 3

30 = 2 * 3 * 5

A legnagyobb közös osztó kiszámítása
Két szám közös prímtényezoinek szorzata. A fenti esetben a 2, és a 3 közös,
így 18 és 30 legnagyobb közös osztója 6.

Ha két szám prímtényezoi egyáltalán nem egyeznek, akkor a legnagyobb közös
osztójuk 1, s a két szám relatív prím egymáshoz képest. Példa:

28 = 2 * 2 * 7

45 = 3 * 3 * 5

Prímtényezoikben nincs közös, legnagyobb közös osztójuk 1. A 28 és a 45
egymáshoz képest relatív prímek. Hogy mi a csudára jó ez nekünk? Hát
kipróbálhatjuk, hogy a hatványozós-modulós játék (a 3. számmisztika) egészen
biztosan csak akkor muködik-e, ha N prím, vagy netalán a relatív prímek is
eleget "tudnak", és elég, ha N relatív prím T-hez képest?

HA a hatványkitevot fel tudnánk bontani két részre, valahogy így:

N=P*Q (ami ugyebár addig nem megy, amíg ebben a számjátékban N kötelezoen
prím) akkor

T(P*Q) ºT (mod N)

ugyanazt adná, a hatványozást pedig két különbözo emberre bízhatnánk

Titkosító: TP º R (mod N nyomása alatt)

Megfejto: RQ º T (mod N)

miénk is lenne az RSA.

1. próba:

T=5 (a titkosítandó szám)

N=6 (relatív prím T-hez, ha nem hiszed, számold ki)

56 mod 6=...1

Jaj. Ez nem az eredeti szám, ez biza nem 5. Ez nem jött be. Euler! Segíts!

3. Euler fíje

Mitol muködik...

... a 3. számmisztika? Jobban utánaolvasva kiderül, hogy a hatványkitevo
csak prímszámok esetén ugyanaz, mint a modulus (N), és ott is csak azért,
mert "véletlenül" így jön ki minden prímszámnál. A hatványkitevo ugyanis nem
más, mint a modulus relatív prímjeinek száma + 1. Ez jó bonyolultan hangzik,
úgyhogy vegyünk példákat:

·          9-hez képest relatív prímek (azaz a legnagyobb közös osztójuk 1):
1, 2, 4, 5, 7 és 8. Összesen 6 darab.

·          7-hez képest relatív prímek: 1,2,3,4,5 és 6. (Azaz minden nála
kisebb szám, merthogy a 7 maga prím.) Összesen megint 6 darab.

Euler a görög f (fi) betuvel jelölte azt, hogy egy számnak hány relatív
prímje van. Így f(9) = 6, és f(7) szintén 6 (bár mero véletlenségbol annyi,
nincs semmi köze a 7-nek a 9-hez). Prímszámoknál borzasztó egyszeru
kiszámítani:

f(N) = N-1

minthogy mindegyik nála kisebb szám relatív prímje egy prímnek. A 3.
számmisztika kijavítva:

T f(N)+1 ºT (mod N)

Lássuk az elozo példát, hátha így összejön!

2. próba

T=5 (a titkosítandó szám)

N=6 (relatív prím T-hez, 2*3 legnagyobb közös osztója 5-tel: 1)

f(6)=1 és 5, azaz összesen 2 darab

5(2+1) mod 6 = ...jaj de izgulok ... = 5!

Hurrá! visszakaptuk az eredetit! Pedig a matekozáshoz használt N nem is
prím! Ki meri azt állítani, hogy a 6-os prímszám? Elégtelen!

Ez már majdnem RSA, csak egyfelhasználós.

RSA!
Itt buktunk el az elobb: ha a hatványkitevot fel tudnánk bontani két részre,
valahogy így:

f(N)+1=P*Q

ami mostmár megy, mert a 6 messze nem prím, akkor

T(P*Q) º T (mod N után)

tök jól muködne, a hatványozást pedig két különbözo emberre bízhatnánk

Titkosító: TP mod N = R

Megfejto: RQ mod N = T

és miénk lenne az RSA.

3. próba:

A fenti példában a hatványkitevo 3. Ezt sajna csak így lehet
szorzótényezokre bontani: 1*3. Az 1 nem valami "jó" hatványkitevo, ugyanis
nem csinál semmit a hatványozás során.

Már megint kicsúszott a markunk közül ez a nyomorult RSA, de nem adjuk fel!

4. A szorzás, mint a helyzet megmentoje
A második számmisztika gyúrása
Emlékeztetoül, ez volt az:

T(N-1) º 1 (mod N)

Most már tudjuk (Euler segített), ez valójában

Tf(N) º 1 (mod N-nel kupánvágva)

Mindkét oldalt emeljük négyzetre:

Tf(N) * Tf(N) º 1 * 1 (mod N)

Most köbre:

Tf(N) * Tf(N) * Tf(N) º 1 * 1 * 1 (mod N)

Bízvást menne negyedik hatványra is... Írjuk fel a köböst a hatványkitevok
osszevonásával:

T3*f(N) º 1 (ne feledd: mod N!)

Ebben az a röhej, hogy a moduloaritmetika miatt a hármas helyén akármilyen
szám állhat, és nem zavarja köreinket! Hoppá! Így ha a f(N)+1 felbontása
olyan béna lenne, mint az elozo bekezdésben (1 és 3 jött ki), semmi gond,
mert K*f(N)+1 éppoly jó felbontási alany, így:

2+1 helyett bátran megpróbálkozhatunk akár a

7*2+1 (=15) felbontásával: 3 és 5.

Sokadik nekifutás.

4. próba

T=5 (a titkosítandó szám)

N=6 (relatív prím T-hez, 2*3 legnagyobb közös osztója 5-tel: 1)

f(6)=1 és 5, azaz összesen 2

K*f(N)+1=7*2+1=15=P*Q. P=3, Q=5

Titkosító: TP mod N=R, azaz 53 mod 6=5

Megfejto: RQ mod N=T, azaz 55 mod 6=5

Done!!!!!!!!! RSA-zunk!!!!!

A publikus kulcs P és N

A privát kulcs Q és N

Egy hétköznapi példa
A hét napjaival fogunk titkosítani. Az egyszeruség miatt az év negyedik
napja lesz a titkosítottan átküldött infó, a modulus pedig 7, azaz vasárnap.
Azért választottam ezt a példát, mert ebben oly természetes a modulus!

T=4, csütörtök (a titkosítandó szám)

N=7, azaz egy naptárlap napjainak száma (relatív prím T-hez, legnagyobb
közös osztója 4-gyel: 1)

f(7)=1, 2, 3, 4, 5 és 6, azaz összesen 6

K*f(N)+1=4*6+1=25=P*Q. P=5, Q=5 (ez bénaság, a két hatványkitevo sose legyen
egyforma, de mi csak gyakorlunk)

A titkosítás valójában a naptár elorepörgetése rengeteg nappal, így rengeteg
lappal. Ahol az elorepörgetés megáll, megnézzük milyen napot írunk (ez a Mod
7).

·          Titkosítás: TP mod N=R, azaz 45 mod 7=2, azaz kedd. Ezt küldöm el
a partneremnek.

·          Megfejtés: RQ mod N=T, azaz 25 mod 7=4, azaz csütörtök.

A publikus kulcs P és N, azaz 5 és 7. Lássuk, ennek birtokában vissza
tudjuk-e fejteni az eredeti napot. A modulo miatt sok "vért" veszítettünk,
gyakorlatilag fogalmunk sincs, hogy hány napot rohantunk elore, kizárólag a
maradék maradt. Ennélfogva T akármi lehet, mert végtelen sok olyan szám van,
amit ha P-edik hatványra emelünk, majd mod 7-tel lefejezünk, keddet ad
eredményül. Visszaút nincs. Elore pedig csak azok hatolhatnak, akik ismerik
Q-t, a privát kulcsot.

Kulcsgenerálás
Már tudjuk, hogy a modulusnak nem kell prímszámnak lennie, boven elég, ha
relatív prím a titkosítandó adathoz. Vajon hogy a csudába biztosítható, hogy
a modulus:

1.       Oltári nagy szám legyen

2.       Relatív prím gyakorlatilag bármihez (fontos.doc például)

3.       Meg tudjuk állapítani a f-jét (relatív prímjeinek számát)

4.       f -je felbontható két egész szám szorzatára

Hmm. Ez igazán nehéz feladatnak tunne, ha vakon bökdösnénk a számok között.
E helyett okosan a következot tesszük:

1.       Veszünk két bazinagy prímszámot, X és Y (www.mersenne.org és egyéb
módszerek, lásd BYTE cikkem)

2.       Ezek szorzata lesz N, a modulus, ami ugyan nem prím, de mivel két
elvetemülten nagy prímszám szorzata, gyakorlatilag bármilyen nagy számhoz
relatív prím lesz

3.       Mindkét prímszámnak tudjuk a f-jét (prímszámokról lévén szó X-1 és
Y-1), így N f-je is adott: f=(X-1)*(Y-1)

4.       Ezután felbontjuk f-t két szám szorzatára (P és Q). Nem nehéz, hisz
"K*f(N)+1 éppoly jó felbontási alany", lásd fenn. P és Q ideális esetben
egymáshoz képest relatív prím, de ez nem szükséges feltétel

5. A bazinagy prímszámokat elhajítjuk. Többé nem kellenek.

A kulcspárok pedig P, N és Q, N

Gyenge pontok
Az RSA gyenge pontja nem az algoritmus, hanem a kulcsgenerálás. Mivel N
része a publikus kulcsnak, az RSA addig "él", amíg nincs jobb módszer N
prímtényezokre bontásához, mint a próbálgatás. Az RSA Labs kihívja maga
ellen a sorsot, és pályázatot hirdet prímtényezokre bontásra tízezertol (576
bites) kétszázezer dolláros (2048 bites) díjért. Az [1] címen lehet nevezni!

Ellenorzés
Ne mondd, hogy elsore feldolgoztad. Nem igaz. Most légyszíves olvasd el
elölrol. Ami nem megy elsore, majd megy másodikra. Ami nem megy másodikra,
madj sikerül harmadikra. Ami nem megy harmadikra...

Fóti Marcell

MZ/X

      A cikkben szereplo URL-ek:

      [1] http://www.rsasecurity.com/rsalabs/challenges/factoring/index.html