[JosephS]

Hello mindenki!

Van egy bonyolult kérdésem amire érdekelne a válasz. Van ugye a nyilvános kulcs, amit ismerhet bárki, és van az ahhoz a bizonyos nyilvános kulcshoz tartozó privát kulcs. A prívát kulcs segítségével dekódolható az eredeti forrásra vissza a kivonat. A nyilvános kulcsból tehát elméletileg elõállítható a privát kulcs. Namost ennek technikai akadályai vannak, mégpedig az hogy évtizedekig eltarthatna a dekódolás folyamata még a nagyteljesítményû szuperszámítógépekkel is. A kérdés az, hogy mit is csinál ez az algoritmus, hogy ilyen idõigényes, talán prímszámokkal dolgozik?

[Lulu64]

idézet:

---

A módszer egy 1977-ben született matematikai megoldás. Legismertebb megvalósítása az RSA algoritmus, amelynek kidolgozása három matematikus nevéhez fûzõdik (Rivest, Shamir és Adleman). Lényege: minden felhasználó (feladó és címzett egyaránt) rendelkezik egy kulcspárral, ami egy nyilvános (public) és egy titkos (private) kulcsot tartalmaz. A nyilvános kulcs a titkosításhoz, a privát kulcs a dekódoláshoz használatos. Fontos megjegyezni, hogy a két kulcs egymásból nem számítható ki, vagyis nem állítható elõ a nyilvános kulcsból a titkos kulcs.

Gyakorlati mûködése: a titkos kulcsot optimális esetben csak tulajdonosa ismerheti, viszont publikus kulcsát minél szélesebb körben ismertté kell tennie, hiszen így tudnak neki -címzettnek- titkosított üzenetet küldeni. A két kulcs egymást kiegészítve mûködik; a címzett nyilvános kulcsával titkosítjuk az üzenetet, amit rajta kívül más nem tud elolvasni, hiszen csak õ rendelkezik a dekódolást elvégzõ titkos kulccsal. A módszer erõsségét, a szimmetrikus kulcsos titkosítás hátrányának megoldása szolgáltatja: azok is tudnak titkosított üzeneteket váltani, akik nem ismerik egymást (elég, ha elõzõleg kicserélték nyilvános kulcsaikat). Ez a csere történhet Interneten keresztül is, hiszen attól, hogy valaki megszerzi a nyilvános kulcsunkat még nem fér hozzá bizalmas információkhoz. További elõnyös tulajdonsága, a digitális aláírás készítésének lehetõsége, mely opciót a hitelességvizsgálat céljából érdemes kihasználni.[/quote]

[ 2002. november 29.: Lulu640 szerkesztette a hozzászólást ]

[JosephS]

Na ez eddig OK. De én olvasom a tankönyvben azt, hogy a nyilvános és a titkos kulcs között szoros kapcsolat van, és a nyilvános kulcsból csak nagyon nagy idõ segítségével állítható elõ a titkos kulcs, még az algoritmus ismeretében is. Idézek: "praktikus idõn belül ez lehetetlen". És a kérdésem csak annyi, hogy mitõl lehetetlen? Mi van abban az algoritmusban amitõl lehetetlenné válik?

[Lulu64]

idézet:

---

Ezt írta JosephS:
Na ez eddig OK. De én olvasom a tankönyvben azt, hogy a nyilvános és a titkos kulcs között szoros kapcsolat van, és a nyilvános kulcsból csak nagyon nagy idõ segítségével állítható elõ a titkos kulcs, még az algoritmus ismeretében is. Idézek: "praktikus idõn belül ez lehetetlen". És a kérdésem csak annyi, hogy mitõl lehetetlen? Mi van abban az algoritmusban amitõl lehetetlenné válik?[/quote]

idézet:

---

A nyilvános kulcsból a titkos kulcsot csak nagyszámú mûvelet segítségével lehet elõállítani. A módszer biztonságossága egy NP-teljes matematikai problémán, a prímszámfejtésen alapul. Az még matematikailag nincs bizonyítva, hogy a probléma megfejtésére nem létezik algoritmus, mellyel az "egyszerûen" visszafejthetõ (eddig ilyen módszer nem került nyilvánosságra, noha ez a matematikának egy igen erõsen kutatott területe).[/quote]

Kulcspár: T és N
N(T(x))=x és T(N(x))=x

Határozd meg T-bõl N-t.

idézet:

---

2^13466917-1 <> 4,053,946 számjegy

Prime95 is a free program written by George Woltman and provided on his GIMPS site. Just download the software, install it, and let it run. Simple and easy, but the road is long. To test a single number takes days on the fastest microcomputers, months on others. Michael’s "AMD T-Bird 800Mhz with 512 Megs of RAM" took 42 days.[/quote]

[ 2002. november 29.: Lulu640 szerkesztette a hozzászólást ]

[JosephS]

Ha én ismerem tegyük fel az összes prímszámot 1millió bitig!!!, akkor ezek a titkosítási eljárások elméletileg semmit sem érnek, ugye? Tehát ha az "összes" prímszámot megtalálom akkor meg van oldva a probléma?
Mert itt azt mondja a könyv, hogy a 40 bit hosszú kulcsok nem érnek semmit, simán feltörik, meg azt is írja, hogy 1024 bitnél rövidebb kulcs ma nem nevezhetõ biztonságosnak. De 1024 bitig az összes prímszám kiszámolása után ha jól értelmeztem amit írtál, akkor ki lehet könnyedén számolni a prímszámok ismeretében.

[Lulu64]

idézet:

---

Ezt írta JosephS:
Ha én ismerem tegyük fel az összes prímszámot 1millió bitig!!!, akkor ezek a titkosítási eljárások elméletileg semmit sem érnek, ugye? Tehát ha az "összes" prímszámot megtalálom akkor meg van oldva a probléma?
Mert itt azt mondja a könyv, hogy a 40 bit hosszú kulcsok nem érnek semmit, simán feltörik, meg azt is írja, hogy 1024 bitnél rövidebb kulcs ma nem nevezhetõ biztonságosnak. De 1024 bitig az összes prímszám kiszámolása után ha jól értelmeztem amit írtál, akkor ki lehet könnyedén számolni a prímszámok ismeretében.[/quote]

A 40, 48, 56, 64 már fel van törve. (a 40-es RC5 3óra volt, ha jól emléxem)
Ha lesz (kib@szottul) gyors módszer prímeket számolni, akkor gáz lesz. Ma még ilyen módszer nem ismert.

idézet:

---

RSA (Rivest - Shamir - Adleman)

A legnagyobb gond egy olyan algoritmus megalkotása volt, mely eleget tesz mindazoknak a követelményeknek, amelyek fentebb fogalmazódtak meg. Sok szakember azonban komoly munkába kezdett hogy kifejlesszék ezt a módszert. 1978 sikerült is megalkotni. A módszert a felfedezõk (Rivest, Shamir, Adleman) kezdõbetûinek összeolvasásából RSA névvel látták el, mely a számelmélet tételein alapszik. Röviden ismertetem az algoritmus lépéseit:

1. Válasszunk két igen nagy (lehetõleg 10100-nál nagyobb) prímszámot, p1-t és p2-t.
2. Határozzuk meg az m=p1*p2 és a F(m)=(p1-1)*(p2-1) számokat.

3. Továbbá válasszunk egy e-számot, amely a (p1-1)-hez is, és a (p2-1)-hez is relatív prím, azaz a legnagyobb közös osztójuk 1.

4. Ezek után végül ki kell számolni d-t, mely e-nek az inverze modulo F szerint. Ilyen szám biztos hogy van, hisz e-t direkt úgy választottuk meg.

e*d=1(mod F(m)) és 1<= d <F(m)

Ezután közzé tehetjük a Kp=(m,e)-t, mely a kulcs nyilvános része. A kulcs titkos részét, Ks=(d,p1,p2)-t pedig szigorúan megõrizzük. A kommunikáció a következõképpen zajlik ebben az esetben:
Amikor az “A” felhasználó szeretne üzenni “B”-nek, akkor az alábbiak szerint kell eljárnia. Megkeresi “B” felhasználó nyilvános kulcsát a nyilvános kulcstárból (Kp). A titkosítani kívánt üzenetet egy kölcsönösen egyértelmû algoritmus szerint nem negatív egész számok sorozatává kell tennie, amelynek egyik tagja sem haladhatja meg “B” modulusát. Ezután a kikeresett kulccsal kiszámítjuk az elõkódolt nyílt üzenet (x) rejtett párját (y).

y=xe(mod m) ahol Kp=(m,e) ¬ “B”

Miután “B” megkapta a rejtjeles üzenetet, a dekódolása már rendkívül egyszerû a titkos kulcs birtokában. A dekódolást a számsorozat elemein külön-külön hajtja végre a saját tikos kulcsával(Ks):

x=yd(mod m) ahol Ks=(m,d) ¬ “B”

Az ekkor kapott számsorozatot a már említett kölcsönösen egyértelmû algoritmus segítségével értelmes üzenetté alakíthatja át.

A módszer biztonsága a nagy számok törzstényezõkre bontásának nehézségére épül. Napjainkban a két választott prímszám (p1,p2) 2048 bit hosszúságú, ez 10^617-en nagyságrendû.[/quote]

[JosephS]

Köszönöm a sok infot. Akkor tehát ha megoldódik a gyors prímszámgenerálás problémája, akkor törhetik a fejüket a biztonsági fejlesztõk, hogy mit találjanak ki, ami ilyen jó mint ez.