Kysymys:
Kuinka arvioida RSA-salauksen purkamiseen tarvittava aika?
Gens
2011-06-12 14:48:42 UTC
view on stackexchange narkive permalink

Kuinka arvioida RSA-salauksen purkamiseen tarvittava aika? Tarkoitan aikaa, joka tarvitaan Rsa-salauksen purkamiseen avaimen pituudella 1024, 2048, 3072, 4096, 5120, 6144, 5120, 7168, 8192, 9216, 10240, 11264, 12288, 13312, 14336, 15360 ja 16384?

Aiheeseen liittyvät: [Mikä on aikaisempien salattujen tietojen "turvallisuusajan heikkeneminen"] (http://security.stackexchange.com/q/2652/396)
1024-bittinen RSA-salaus murtui huolellisesti nälkään menevällä sähkön suorittimella Katso tämä artikkeli ... cpu-of-ele /
Aiheeseen liittyvä: [Kuinka kauan kestää RSA 1024: n murtaminen tietokoneella?] (Https://crypto.stackexchange.com/q/70829/2592)
Kolme vastused:
#1
+90
Thomas Pornin
2011-06-12 20:25:11 UTC
view on stackexchange narkive permalink

Katso tältä sivustolta yhteenveto eri tutkijoiden ja organisaatioiden käyttämistä tärkeimmistä vahvuusarvioista.

"512-bittinen 12 μs" on täysin väärä. Katsotaanpa mistä se tulee. Vuosi 1999 oli vuosi, jolloin ensimmäinen 512-bittinen yleinen kertoin suoritettiin RSA: n (yritys) julkaisemalle haasteelle, jonka nimi oli RSA-155 (koska luku koostui 155 desimaaliluvusta - binäärisenä) , pituus on 512 bittiä). Tämä jakaminen kesti 6 kuukautta. Samana vuonna järjestetyssä Eurocrypt-tapahtumassa (toukokuussa; tuolloin 512-bittinen jakotekniikka oli alkanut, mutta sitä ei ollut vielä saatu päätökseen) Adi Shamir Weizmannilta Institute esitteli teoreettisen laitteen nimeltä TWINKLE, joka oletettavasti voi auttaa varsin vähän tekijöinä. Sen tulisi koostua valtavasta määrästä diodeja, jotka vilkkuvat huolellisesti valituilla taajuuksilla, eräänlaisena mustana putkena. Shamir toi mukautetun laitteen, joka 10 metrin päästä näytti kahvinkeittimeltä. Hän pyysi ihmisiä sammuttamaan valon, jotta Eurocrypt-osallistuja voisi ihmetellä neljä punaista diodia, jotka vilkkuvat 2, 3, 5 ja 7 sekunnin sisääntuloissa. Ooh! ja Aah! He menivät, vaikka varsinainen kone, olisiko se rakennettu, vaatisi muutama miljoona diodia ja taajuutta 10 tai 100 gigahertsissä . Joten ajatus on hauska (ainakin krypologian tutkijoille, joilla tiedetään olevan outo huumorintaju), mutta se ei ole vielä ylittänyt teoreettista luonnosvaihetta. Shamir on loistava näyttelijä.

TWINKLE on kuitenkin vain "apua". Tunnetuinta faktorointialgoritmia kutsutaan General Number Field Sieve; kaksi seuraavaksi tulevaa algoritmia ovat kvadraattiseula ja elliptisen käyrän menetelmä. 512-bittinen luku on QS: n ja ECM: n ulottumattomissa nykypäivän tekniikalla, ja varsinkin vuoden 1999 tekniikalla. GNFS on erittäin monimutkainen (matemaattisesti ottaen), varsinkin kun se vaatii joidenkin kriittisten parametrien huolellista valintaa ("polynomivalinta"). Joten erittäin älykkäiden aivojen (suurten tietokoneiden kanssa, mutta aivot ovat tässä tärkeimmät) on oltava alkuvaiheessa. Jälkeenpäin GNFS koostuu kahdesta osasta, seulasta ja lineaarisesta pelkistyksestä . Seula voidaan valmistaa samanaikaisesti satojen tai tuhansien koneiden yli, joiden on silti oltava suhteellisen suuria (RAM-muistissa), mutta tämä on mahdollista. Lineaarinen pienennys käsittää asioiden laskemisen matriisilla, joka on liian suuri sopimaan tietokoneeseen (usealla suuruusluokalla, ja vaikka oletamme, että mainitussa tietokoneessa on teratavua nopeaa RAM-muistia). On algoritmeja pitämään matriisi (joka on melko harva) pakatussa muodossa ja pystymään silti laskemaan siitä, mutta tämä on vaikeaa. 512-bittisessä kertoimessa seulonta kesti noin 80% kokonaisajasta, mutta suuremmille numeroille lineaarinen pelkistys on pullonkaula.

TWINKLE on vain seulan osan nopeuttaminen. Se ei tee mitään lineaariselle pelkistykselle. Toisin sanoen, se nopeuttaa osaa, joka on helppoa (suhteellisen ottaen). Jopa TWINKLE-parannettu seulontapuoli ei olisi läheskään 12 μs. Sen sijaan se auttaisi mieluummin viemään neljän kuukauden seulontaponnistuksen esimerkiksi kolmeen viikkoon. Mikä on tieteellisesti hyvä, mutta ei ennätysmurtaja, varsinkin kun lineaarinen pelkistys hallitsee suurempia kokoja. 12 μs: n luku näyttää sekoittuneen vieläkin myyttisempään petoon, Quantum Computeriin, joka voisi helposti ottaa huomioon suuria lukuja, jos laadukkaan laadunvalvonta 512 "quitilla" voitaisiin rakentaa. D-Wave on äskettäin julkistanut kvanttitietokoneen, jossa on 128 kiintolevyä, mutta kävi ilmi, että nämä eivät olleet "todellisia" kiiittoja, eivätkä ne sovellu faktorointiin (he voivat teoriassa silti tehdä joitain tehokkaita likiarvoja optimointiongelmissa, mikä on hienoa mutta periaatteessa ei sovellettavissa salaukseen, koska kryptografiset algoritmit eivät ole lähellä likiarvoja - ne on suunniteltu siten, että yksi väärä bitti sekoittaa koko asian. Paras "todellinen" laadunvalvontatoimi näyttää toistaiseksi olevan IBM: n prototyyppi, jolla on - sikäli kuin muistan - 5 kubitia, minkä ansiosta se voi todeta, että 15 on yhtä suuri kuin 3 kertaa 5.

Nykyinen RSA factoring-ennätys on 768-bittinen kokonaisluku, joka ilmoitettiin joulukuussa 2009. Se kesti neljä vuotta, ja siihen osallistui älykkäimpiä teoreetikkoja, jotka tällä hetkellä elävät maan päällä, mukaan lukien Lenstra ja Montgomery, joilla on jonkin verran jumalankaltainen asema nuo piirit. Olen äskettäin oppinut, että parametrien valinta 1024-bittiselle lukutekijöille on alkanut (se on "aivokas" osa); seulonta on teknisesti toteuttamiskelpoinen (se on kallista ja edellyttää vuosien laskenta-aikaa monissa yliopistoklustereissa), mutta toistaiseksi kukaan ei tiedä miten tehdä lineaarinen pelkistysosa 1024-bittiselle kokonaisluvulle. Joten älä odota 1024-bittistä taukoa pian.

Tällä hetkellä omistautunut amatööri, joka käyttää julkaistua koodia (esim. Msieve), voi saavuttaa 512-bittisen kertoimen, jos hänellä on pääsy tehokkaisiin tietokoneisiin (useita kymmeniä isoja tietokoneita ja vähintään yksi kello täynnä) nopeaa RAM-muistia) ja muutaman kuukauden vapaa-aika; periaatteessa "omistautunut amatööri" tarkoittaa "tylsää tietojenkäsittelytieteen opiskelijaa varakkaassa yliopistossa". Ammattilaisten ulottumattomissa on kaikki, mikä on yli 512 bittiä.

Yhteenveto: koodissasi voit palauttaa "käytännöllisesti katsoen loputtoman" murtumisajaksi kaikille avaimen pituuksille. Tyypillinen käyttäjä ei riko 1024-bittistä RSA-avainta, ei nyt eikä myöskään kymmenessä vuodessa. Maan päällä on noin tusina ihmistä, jotka uskottavalla tavalla voivat väittää, että on mahdollista ajatella pienellä mutta ei nollan todennäköisyydellä, että he saattavat pystyä laskemaan yhden 1024-bittisen kokonaisluvun jossain määrittelemättömässä vaiheessa ennen vuotta 2020.

(On kuitenkin erittäin helppoa erottaa RSA: n tai minkä tahansa RSA: ta käyttävän sovelluksen toteutus siten, että sen hallussa olevat luottamukselliset tiedot voidaan palauttaa vaivautumatta RSA-avain ollenkaan. Jos käytät 1024-bittisiä RSA-avaimia, voit olla varma, että kun hakemuksesi hakkeroidaan, se ei tapahdu RSA-avaintekijöillä.)

+1. En halunnut väittää, että 512-bittinen factoring-asia oli väärä, koska tiedän paljon vähemmän kvantista (tai koko alueesta yleensä) kuin sinä, mutta minulla oli vahva tunne, että se oli. Minulla oli myös reilu idea factoring-algoritmeja, jotka räätälöitiin lukumäärää kohti, mutta ei siinä määrin kuin kuvailet, koska numeroteoriani ei ole vielä niin hyvä. Joten +2, jos voisin.
+1, @Thomas Pornin: Todellinen salauskirjan lopullinen vastaus.
En ole käynyt tällä sivustolla kauan, mutta saan * todella * hyvä arvata, mihin kysymyksiin karhu vastaa.
Joitakin vuosia myöhemmin 512 bittiä on "noin 7,5 tuntia": http://blog.cryptographyengineering.com/2015/03/attack-of-week-freak-or-factoring-nsa.html(Tyypillisiä käyttäjiä ei edelleenkään ole t missään lähellä 1024-bittisten avainten rikkomista, eikä se ole jäljellä vastauksen "kymmenen vuoden" kuluessa. Sellaiset organisaatiot, jotka mahdollisesti ovat, eivät tee julkisia ilmoituksia: http: //crypto.stackexchange .com / a / 1982/5249)
Pieni nittivalinta: IRRHYM "yksi (iso tietokone) * täynnä * RAM-muistia", ei "yksi kello (joka on aika kertoa tai mitata aikaa)".
#2
+25
user2213
2011-06-12 16:49:18 UTC
view on stackexchange narkive permalink

Lyhyt vastaus : Helpoin tapa olisi käyttää päälukulause, mutta muista, että se on likiarvo. Arvioi, kuinka kauan sinun pitäisi kokeilla kaikkia näitä primejä; aika per prime * alkukertojen määrä antaa sinulle kokonaisajan. Tämä antaa sinulle arvion raakaa voimaa koskevasta hausta.

Voit myös käyttää ajoaika-estimaattia kvadraattiseulalla tai yleisen lukukentän seulalla. Tämä antaa sinulle arviot factoring-algoritmeista, joita RSA-numeroita rikkovat ihmiset tosiasiallisesti käyttävät.

Pitkä tausta :

Numeroteorian aika!

Ensinnäkin katsotaanpa puhumiesi numeroiden kokoa. Koska 2 ^ 3 = 8, joka on 1000 binäärissä, voimme nähdä, että tämä on nelibittinen luku, pienin mahdollinen. Joten 2 ^ 2 = 4 on 3-bittinen luku (100). Joten tietylle x: lle pienin mahdollinen arvo sen varmistamiseksi, että meillä on tarpeeksi bittejä, on 2 ^ (x-1). 2 ^ 2047 = 16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650498045875098875194826053398028819192033784138396109321309878080919047169238085235290822926018152521443787945770532904303776199561965192760957166694834171210342487393282284747428088017663161029038902829665513096354230157075129296432088558362971801859230928678799175576150822952201848806616643615613562842355410104862578550863465661734839271290328348967522998634176499319107762583194718667771801067716614802322659239302476074096777926805529798115328. Se on koko numeron olet tekemisissä täällä, eli koko n laskettaisi.

Seuraava suuri kysymys sitten on, miten n rakennetaan? n = pq kuten tiedät RSA: n määritelmästä, joten etsit kahta alkukertaa tämän luvun tekijöinä. Kysymykseksi tulee sitten, kuinka voimme määrittää luvun olevan ensisijainen ja voimmeko laskea sen?

Joten numero on määritelmän mukaan pelkistämätön, jos x sitä pienemmälle numerolle \ gcd (p, x) = 1 lukuun ottamatta x = 1 . Voimme kuitenkin parantaa sitä. Sinun pitäisi ymmärtää melko nopeasti, että mikä tahansa numero, se on joko prime tai ei. Jos se ei ole prime, niin sen gcd: n ja ainakin yhden prime: n on oltava suurempi kuin 1 (muuten se olisi prime). Tästä päätellään, että minkä tahansa ei-alkuluvun kokonaisluvun on oltava jaettavissa alkuluokkalla. Muodollinen matemaattinen todiste ei todellakaan ole niin suuri harppaus täältä.

Tätä kutsutaan aritemtisen peruslauseeksi ja se yksinkertaistaa asioita hieman. Joten nyt, kun selvitämme, onko luku ensisijainen, meidän ei enää tarvitse kokeilla kaikkia numeroita, vain numerot, jotka tiedämme jo olevan tärkeimmät!

Tämä on selvästi edelleen todella hidasta, joten tehkäämme toinen havainto - tietyt tekijät esiintyvät pareittain, alempi kahdesta luvusta on korkeintaan luvun neliöjuuri. Jos olemme rajoitettu N: ään (luonnollisten numeroiden joukko), se edustaa suurimman mahdollisen tarkistettavan arvon ylärajaa. Joten nyt, mihin tahansa numeroon N, meidän on etsittävä jokaista kokonaislukua alkaen 2 ja suuntaamalla sqrt (N) kutakin lukua varten, jonka määrittelemme ensisijaiseksi luettelossa. Voimme sitten, jos löydämme alkuluvun, päätellä, onko se tekijä N itse. En aio arvioida sen ajoaikaa, koska sanon epäilemättä väärän asian, mutta se vie kauan.

Nyt näet RSA: n vahvuuden. Valitse erittäin suuri pääministeri ja pääset pitkälle. Nykytilanteessa meidän on aloitettava 2: sta, mikä on selvästi kamalaa.

Primality-testauksen tarkoituksena on parantaa sitä käyttämällä erilaisia ​​tekniikoita. Naiivi menetelmä on juuri keskusteltu. Luulen, että näiden tekniikoiden yksityiskohtainen keskustelu on luultavasti sopivampi Mathille, joten haluan tiivistää sen: kaikki ajonajat ovat roskaa, ja tämän käyttäminen keinona laskea primejä olisi kauheaa.

Emme siis voi laskea ensiöiden määrää luotettavasti pienemmäksi kuin luku ottamatta ikuisesti, koska se on käytännössä analoginen kokonaislukukertoimien kanssa. Entä funktio, joka laskee jotenkin primejä jollakin muulla tavalla?

Kirjoita \ pi (n) = \ frac {n} {\ log (n) - 1.08366} , yksi yritys päälukulauseessa likiarvo alkukertojen määrälle. Se on kuitenkin täsmälleen se; Tällaisen funktion tarkoituksena on laskea tarkalleen alkumäärä, mutta tällä hetkellä se antaa sinulle vain arvion. Tarkoituksessasi tätä voidaan pitää tarpeeksi hyvänä.

Se on kuitenkin ehdottomasti likimääräinen. Katso loput artikkelista. Muun muassa muut arviot ovat riippuvaisia ​​Riemannin hypoteesista.

Okei, entä entä kokonaislukutekijä? Toiseksi tähän mennessä parhainta menetelmää kutsutaan kvadraattiseulaksi ja parasta kutsutaan yleisen numerokentän seulaksi. Molemmat näistä menetelmistä koskettavat melko kehittynyttä matematiikkaa; olettaen, että olet tosissasi factoring primes, saisin lukea näitä. Sinun pitäisi varmasti pystyä käyttämään arvioita molemmissa parannuksina alkuluku-lauseen käyttämisessä, koska jos aiot laskea suuria primejä, haluat käyttää näitä etkä raakaa voimahakua.

Mutta haluan tietää kvantista?

Okei, riittävän reilu. Kokonaislaskenta kvanttitietokoneella voidaan suorittaa naurettavan lyhyessä ajassa, olettaen, että pystymme toteuttamaan Shorin algoritmin. Haluan kuitenkin huomauttaa, että tämä vaatii kvanttitietokoneen. Sikäli kuin olen tietoinen, sellaisen mittakaavan kvanttitietokoneiden kehittäminen, joka voi rikkoa RSA: n, on tällä hetkellä tie poispäin. Katso kvanttilaskennan kehitys.

Joka tapauksessa Shorin algoritmi olisi eksponentiaalisesti nopeampi. Sen sivulla on arvio sen ajoajasta, jonka haluat sisällyttää arvioihisi.

+1 Kiitos vastauksesta. Tiedän, että tällaisen vastauksen kirjoittaminen vaatii todellisia ponnisteluja. Mutta ei-matemaattisena ihmisenä tuskin ymmärrän yksityiskohtia.
Annetut linkit ovat liian etukäteen minulle. Voitteko arvioida karkeasti vaaditun ajan näiden RSA-avainten pituuksien murtamiseen?
@Gens paras panoksesi on mennä pari / gp: n kanssa ja pitää kiinni raakavoiman likiarvosta; voit tosiasiallisesti laskea todelliset luvut. Wikipedia-linkit puhuvat laskennallisesta monimutkaisuudesta; voit liittää numeroita näihin - temppu selvittää, mitä tämä tarkoittaa laskennallisten kulujen kannalta. Itse asiassa laskennallinen monimutkaisuus arvioi vain suurimman, hallitsevimman termisarjan (katso matemaattinen analyysi), joten todelliset ajoajat suoritettavan työn suhteen vaihtelevat toteutuksen ja prosessorin mukaan.
Kiitos ehdotuksesta, mutta ehkä minun täytyy laittaa palkkio jollekin, joka tekee minulle työtä :)
Yksi pieni huolenaihe tästä vastauksesta. Sanot, että luvun "suurin mahdollinen tekijä" on sen neliöjuuri. Tämä on tietysti väärin; se on alkusarjan (mukaan lukien) yläraja, joka on otettava huomioon, ennen kuin luku voidaan julistaa ensisijaiseksi. Toisin sanoen, kun otetaan huomioon luku 33, jonka neliöjuuri on 5,75 (-ish), meidän ei tarvitse testata, onko 11 tekijä, koska olisimme jo löytäneet tekijän, kun testasimme 3. Tämä voidaan osoittaa siitä, että Pahin tapaus algoritmille on alkuluvun neliö, jolloin esimerkiksi 5 on korkein testi, jota tarvitaan 25: lle.
@BMDan Tein muokkauksen, luulen, että tämä lukee nyt oikein! Kerro minulle, jos ei :) Kiitos kommenteista: D
@AntonyVennard Kiitos päivityksestä. Lukee nyt paljon puhtaammin, IMHO.
#3
-1
Evgeny
2015-10-18 02:17:54 UTC
view on stackexchange narkive permalink

Toinen vaihtoehto on luoda iso tietokanta mahdollisista avaimista ja käyttää sitä hakutaulukkona. Ilmeisesti et tarvitse edes KAIKKIA alkukuvia, vain pari vie sinut läpi suuren osan Internet-liikenteestä.

Lähde: https://freedom-to-tinker.com/blog / haldermanheninger / how-is-nsa-breaking-so-much-crypto /

Tämä viesti koskee (Dlog-hyökkäyksiä) jaettua pääministeriä / ryhmää * Diffie-Hellmanille *, eikä sillä ole mitään tekemistä RSA: n kanssa. Vaikka samat kirjoittajat olivat mukana aikaisemmassa työssä, jossa tarkasteltiin RSA-moduulien tai tekijöiden päällekkäisyyttä ja todettiin, että se oli pienempi mutta ei vähäpätöinen ongelma: https://freedom-to-tinker.com/blog/nadiah/new-research-theres- no-need-panic-over-factorable-keys-just-mind-sinun-ps-ja-qs /


Tämä Q & A käännettiin automaattisesti englanniksi.Alkuperäinen sisältö on saatavilla stackexchange-palvelussa, jota kiitämme cc by-sa 3.0-lisenssistä, jolla sitä jaetaan.
Loading...