„Félprímek” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Nincs szerkesztési összefoglaló |
1 forrás archiválása és 0 megjelölése halott linkként. #IABot (v2.0beta2) |
||
31. sor:
A félprímeket a [[számelmélet]]ben, különösen [[kriptográfia]]i alkalmazásokban a [[Nyilvános kulcsú rejtjelezés|nyílt kulcsú titkosítás]]nál alkalmazzák. Az [[RSA-eljárás]] arra alapul, hogy két nagy prímet találni és összeszorozni viszonylag könnyű, viszont a szorzatot [[Prímfelbontás|faktorizálni]], azaz a félprím ismeretében a szorzat tényezőit meghatározni nehéz.
Az RSA Factoring Challenge-ben a feladat bizonyos elég nagy félprímek prímtényezős felbontása volt. Az RSA Security díjakat tűzött ki a megoldóknak, és néhány díjat már el is vittek. A legutolsót 2007-ben zárták le.<ref>[http://www.rsa.com/rsalabs/node.asp?id=2092 Information Security, Governance, Risk, and Compliance - EMC] {{Wayback|url=http://www.rsa.com/rsalabs/node.asp?id=2092 |date=20130507091636 }}. RSA. Hozzáférés ideje: 2014-05-11.</ref>
A gyakorlati kriptográfiában nem elegendő tetszőleges félprímet választani. Léteznek specializált faktorizáló algoritmusok, amelyek bizonyos alakú félprímeket hatékonyan tudnak faktorizálni, egy jó félprím pedig nehezen faktorizálható. A ''p'' és a ''q'' tényezők legyenek nagyok, közelítőleg azonos nagyságrendűek, de ne legyenek túl közel egymáshoz. Ez kivédi a [[triviális osztás]]t (kis prím az egyik tényező), és a [[Pollard-féle ró algoritmus]]t. Ha túl közel lennének egymáshoz, akkor a [[Fermat-faktorizáció]] miatt lehetne könnyen feltörni a kódot. A tényezők szomszédai se legyenek kis számok szorzatai, mert akkor alkalmazható lenne [[Pollard p-1 algoritmus]]a, vagy [[Williams p+1 algoritmus]]a. Mindezek azonban nem segítenek a titkos vagy jövőbeli algoritmusokkal szemben.
| |||