Kysymys:
Yksinkertaisten operaatioiden määrä, joka on turvallisesti koko ihmiskunnan ulottumattomissa?
Nakedible
2011-08-11 22:35:15 UTC
view on stackexchange narkive permalink

Salausprimitiivit väittävät yleensä jonkin tietoturvatason, joka annetaan hyökkäyksen muodostamiseen tarkoitettujen toimintojen lukumääränä. Hash-toiminnot antavat esimerkiksi erilaiset suojaustasot törmäyshyökkäyksille, preimage-hyökkäyksille ja toisille preimage-hyökkäyksille. Näistä johdetaan "turvallisten" avainten koot eri primitiiveille.

On olemassa monia erilaisia ​​suosituksia turvallisten avainten koosta ja monia erilaisia ​​keinoja arvioida tulevaisuuden valmiuksia laskennan suorittamisessa. Esimerkiksi osoitteessa www.keylength.com on paljon näitä suosituksia yhdistettyinä.

Etsin kuitenkin yksinkertaisten toimintojen määrää, jonka voidaan selvästi nähdä olevan koko ihmiskunnan ulottumattomissa. lähitulevaisuudessa - tai itse asiassa pienin sellainen arvo, joka on vielä uskottava.

On hyvin ilmeistä, että 2 ^ 256 yksinkertaista operaatiota ei koskaan saavuteta. On myös hyvin ilmeistä, että 2 ^ 64 yksinkertaista operaatiota voidaan saavuttaa sellaisenaan. Monet suosituksista näyttävät laskevan 2 ^ 128 lukumääräksi, joka olisi turvallinen vähintään 30 vuoden ajan. Joten etsimäni arvo on todennäköisesti välillä 2 ^ 128 ja 2 ^ 256. Oletan arvauksen 2 ^ 160 tai 2 ^ 192 olevan turvallisesti ulottumattomissa.

Mutta haluan konkreettisia argumentteja, joihin voidaan helposti perustella. Haluaisin nähdä argumentteja, jotka perustuvat yksinkertaisiin fysiikan laeihin tai suhteisiin konkreettisiin vakioihin universumista. Esimerkiksi Landauerin periaatetta voidaan käyttää.

Huomaa: Käytetyt varsinaiset yksinkertaiset operaatiot eivät ole merkityksellisiä tässä - ne voivat olla operaatioita kvanttitietokoneella, hash-invokaatioita tai mitä tahansa. .

Tietysti tämä riippuu siitä, kuinka kauan yksi "yksinkertainen toimenpide" kestää ja kuinka monta niistä voit suorittaa rinnakkain. SHA-265-hashin käyttö vaatii enemmän kuin yksinkertaisen lisäyksen (joka sopii rekisterikokoon).
No, ilmeisesti. Mutta etsin sellaisten operaatioiden määrää, joihin ei koskaan päästä, riippumatta siitä, kuinka yksinkertaista se on. Joten arvojen laskeminen silmukassa on tarpeeksi hyvä tai jotain vielä yksinkertaisempaa. Esimerkiksi Landauerin periaatteessa laskentayksikkö on yhden bitin muutos.
@Nakedible, Kun aloitat keskustelun [Landauerin periaatteesta] (http://fi.wikipedia.org/wiki/Landauer%27s_principle), sinun tulee puhua myös [tuntemattomista] (https://fi.wikipedia.org/wiki/Ei_tunnettuja_tuntemattomia).
Tämä kuulostaa Crypto-kysymykseltä enemmän kuin täällä, mutta tämä on melko mielenkiintoinen luku.
Neljä vastused:
#1
+309
Thomas Pornin
2011-08-12 00:08:50 UTC
view on stackexchange narkive permalink

Lähtökohtana pidämme sitä, että jokainen perusoperaatio merkitsee vähän energiankulutusta; Landauerin periaate asettaa tämän rajan arvoon 0,0178 eV, joka on 2,85 × 10 -21 J. Toisaalta aurinkokunnan kokonaismassa, jos se muunnetaan kokonaisuudessaan energiaksi tuottaisi noin 1,8 × 10 47 J (itse asiassa sen saisit auringon massasta tämän sivun mukaan, mutta aurinko vie Lionin osuus aurinkokunnan kokonaismassasta). Tämä tarkoittaa kovaa rajaa, joka on noin 6,32 × 10 68 alkeislaskentaa, mikä on noin 2 225,2 . (Luulen, että tämän laskennan esitti jo Schneier "Sovelletussa salauksessa".)

Tämä on tietysti melko äärimmäinen skenaario, etenkään meillä ei ole aavistustakaan siitä, miten voimme muuntaa massan energiaksi - ydinfissio ja fuusio muuntaa vain pienen osan käytettävissä olevasta massasta energiaksi.

Tarkastellaan tavallisempaa näkökulmaa. Vaikuttaa olennaiselta olettaa, että olemassa olevan tekniikan mukaan jokaisen perusoperaation on jotenkin tarkoitettava ainakin yhden logiikkaportin kytkemistä. Yksittäisen CMOS -portin kytkentäteho on noin C × VVsup>2 jossa C on portin kuormituskapasitanssi, ja V on jännite, jolla portti toimii. Vuodesta 2011 lähtien erittäin huippuluokan portti pystyy toimimaan 0,5 V: n jännitteellä ja muutaman femtofaradin kuormituskapasitanssilla ("femto" tarkoittaa 10 -15 ). Tämä johtaa minimaaliseen energiankulutukseen operaatiota kohden, joka on vähintään 10 -15 J. Nykyinen maailman energiankulutus on noin 500 EJ (5 × 10 20 ). J) vuodessa (tai niin sanotaan tämä artikkeli). Olettaen, että maapallon kokonaisenergiantuotanto ohjataan yhteen laskelmaan kymmenen vuoden ajan, saadaan rajaksi 5 × 10 36 , joka on lähellä 2 122 .

Sitten on otettava huomioon tekninen kehitys. Kun otetaan huomioon tämänhetkinen suuntaus ekologisiin huolenaiheisiin ja öljyn huippu, energian kokonaistuotannon ei pitäisi kasvaa kovin paljon tulevina vuosina (sanotaan korkeintaan kerroin 2 vuoteen 2040 asti - jo ekologin painajainen ). Toisaalta integroitujen piirien suunnittelussa on edistytty teknologisesti. Mooren laissa todetaan, että tietylle sirupinnalle mahtuu kaksi kertaa niin monta transistoria joka toinen vuosi. Hyvin optimistinen näkemys on, että tämä transistoreiden määrän kaksinkertaistaminen voidaan tehdä jatkuvalla energiankulutuksella, mikä puolestaan ​​puolittaisi perustoiminnan energiakustannukset kahden vuoden välein. Tämä johtaisi yhteensä 2 138 vuoteen 2040 - ja tämä on tarkoitettu yhdelle kymmenen vuoden pituiselle laskennalle, joka mobilisoi kaikki koko planeetan resurssit.

Joten tavallinen viisaus "128 bittiä riittää seuraaville vuosikymmenille" ei ole pois päältä (kaikki riippuu siitä, mitä pidät "turvallisena") ulottumattomissa, mutta oma paranoiatasoni on melko rauhallinen ja 128 bittiä "vain").

Huomautus kvanttitietokoneista: laadunvalvonta voi tehdä melko paljon yhdessä "toiminnossa". Tavallinen esitys on, että laadunvalvonta suorittaa "useita laskutoimituksia samanaikaisesti, jotka suodatamme loppuun". Tämä väite on väärä monissa yksityiskohdissa, mutta se sisältää silti vähän totuutta: Laadunvalvojan tulisi pystyä hyökkäämään n bitin symmetriseen salaukseen (esim. Symmetrinen salaus n : llä) -bit-avain) 2n/2 alkeiskvanttioperaatioissa. Tästä syystä klassinen temppu: Kvanttitietokoneiden (jos niitä on koskaan olemassa) huomioon ottamiseksi kaksinkertaista avaimen pituus. Tästä syystä AES: llä on 256-bittinen avain, SHA-512 ... (AES: n 256-bittistä avainta ei ole suunniteltu suojaamaan hypoteettisilta kvanttitietokoneilta, mutta näin 256-bittiset avaimet ovat nykyään perusteltuja.

Halusin vain sanoa, wow. Tämä on kaunis vastaus, hyvin tehty Thomas. :-)
Hyvä vastaus! Juuri sellainen päättely, jota etsin. En kuitenkaan etsi "turvallisesti" ulottumattomissa, etsin "ei ole ihmiskunnan saavutettavissa millään tavalla". Olettaen, että nopeus ei ole kuin kevyt matka, resurssien rajoittaminen aurinkokuntaamme vaikuttaa kohtuulliselta - mielestäni voidaan kuitenkin perustella luku, joka on alle 2 ^ 225 ja joka olisi silti kohtuullisen koko ihmiskunnan ulottumattomissa, vaikka koko lajin kohtalo riippuisi siitä.
Erittäin vaikuttava vastaus, toivoisin voivani äänestää useammin kuin kerran. Mutta vaikka oletettaisiinkin, että hyperlaskenta on ulottumattomissa, älä unohda palautuvaa tietojenkäsittelyä - jos pystyt suorittamaan 2 ^ 31 toimintasi palautuvasti, saatat pystyä saavuttamaan tuon 2 ^ 256 operaation klassisella tietokoneella mustaa aukkoa käyttämällä negentropyyn ja koko aurinkokunnan heittämiseen pala palalta.
En (henkilökohtaisesti) usko, että palautettavaa tietojenkäsittelyä ei koskaan tule esiin, joten aivan kuten FTL, en pidä sitä.
Tämä vastaus on hieno, mutta minulla on yksi varaus. Sanotaan, että toistamme Mooren lain siten, että kunkin yksittäisen transistorin koko puolittuu joka toinen vuosi (se on sama asia kuin kaksinkertaistetaan suuttimessa olevien transistorien lukumäärä, jos muotti on samankokoinen). Mihin se jättää meidät? [Subatomitransistoreilla] (https://en.wikipedia.org/wiki/Moore%27s_law#Ultimate_limits_of_the_law), mitä ilmeisesti ei tapahdu, ellei fysiikassa ole jossakin merkittävää läpimurtoa. Täysin uuden tyyppinen tekniikka muutaman vuoden sisällä? Kvanttitietokoneet eivät ole lähellä tätä pistettä.
Voisiko 128-bittisen ja 256-bittisen avaimen välisen eron tulkita myös suojaksi tulevaisuudessa havaituilta AES-heikkouksilta? Voisitko koskaan odottaa AES-hyökkäyksen vähentävän sen voimakkuutta puoleen, ikään kuin kvanttitietokone voisi?
Tämä tulkinta on varmasti olemassa ja se on jopa laajalle levinnyt; jotkut ihmiset haluavat isompia avaimia, koska he olettavat, että hyökkäykset kuluttavat jotenkin avainkappaleita vähitellen. Tosiasiat eivät kuitenkaan tue tätä oletusta. Todellisuudessa tauot ovat yleensä kaikki tai ei mitään. Joissakin erityistapauksissa isommat avaimet voivat olla heikompia (esimerkiksi AES-256 osoittautui huomattavasti heikommaksi kuin AES-128 melko esoteerisia, ja onneksi ei sovellettavissa käytännössä, niihin liittyviä avainhyökkäyksiä vastaan).
@ThomasPornin varma, että löydät algoritmista virheen, mikä on toinen huolenaihe. Tämä analyysi koskee energiantarpeita tosiasiallisen hyökkäyksen suorittamiseksi, olettaen, että sinun täytyy tehdä se. Jos algoritmi on rikki, "turvallisen" bittien lukumäärän valitseminen ei välttämättä auta. Suurin osa algoritmivirheistä koputtaa muutaman bitin hakutilan koosta, jonka hyökkääjän on etsittävä, mutta jotkut epäonnistumiset ovat paljon pahempia.
Massaa ei muuteta energiaksi, se on yleinen väärinkäsitys. Massa on * ekvivalentti * energiaan. Ne kuvaavat samaa taustalla olevaa asiaa.
Mielenkiintoinen sivuhuomautus universaaleille rajoille: olettaen, että huoneen lämpötilan sijasta 2,76K (taustasäteilylämpötila) ja olettaen, että maailmankaikkeudessa on 10 ^ 24 tähteä, tarvitsemme vähintään 312 bittiä turvallisuutta; 624 bittiä immuuniksi galaktisten interienien kvanttitietokoneille.
Mielestäni ensimmäisessä oletuksessa on ongelma, joka on kutsuttava esiin.Laundauerin periaate koskee vain peruuttamattomia toimintoja.
Lisätään yllä olevaan @davenpcj's-kommenttiin: [Jos meillä olisi "täysin tehokas" tietokone ja kaikki Linnunradan energia käytettävissä, mihin numeroon se voisi laskea?] (Https://physics.stackexchange.com/q/257323/14091) voi olla merkitystä tässä.
#2
+31
gowenfawr
2011-08-11 23:38:38 UTC
view on stackexchange narkive permalink

Huomaa: käytetyillä yksinkertaisilla operaatioilla ei ole merkitystä tässä - ne voivat olla operaatioita kvanttitietokoneella, hash-kutsuja tai mitä tahansa.

No, kvanttitietokone on syy, miksi kukaan ei voi kertoa sinulle "sellaisten yksinkertaisten toimintojen määrää, joiden voidaan selvästi nähdä olevan koko ihmiskunnan ulottumattomissa lähitulevaisuudessa". Määritelmän mukaan kvanttitietokone suorittaa päinvastoin "todelliset yksinkertaiset operaatiot"; sen avulla voidaan ohittaa suuri osa "yksinkertaisen toiminnan" avaruudesta kvanttikäden avulla. Kun tietokone, joka ohittaa osan yksinkertaisesta toimintatilasta, on olemassa, kysymyksesi "kuinka suuren tilan on oltava" tulee arvaamattomasti merkityksettömäksi.

Se on teoria joka tapauksessa. Emme ole saavuttaneet tulevaisuuden tasoa, jossa kvanttitietokoneet voivat tehdä sen, mitä mielestämme heidän pitäisi pystyä tekemään. Vaikka olen tyytyväinen sanomaan, että tällaista kvanttitietokonetta ei ole, eikä sitä ole missään laatikossa.

Kvanttialgoritmit voivat vähentää tiettyjen * tavoitteiden * saavuttamiseksi tarvittavien yksinkertaisten toimintojen määrää - kuten salausprimitiikin murtamista - mutta en ole siitä kiinnostunut. Kvanttioperaatio on edelleen operaatio ja kvanttitietokoneet ovat edelleen vain tietokoneita.
Äänestin melkein melkein tämän pelkästään viimeisen lauseen osalta.
@MichaelKjörling: Tein varmasti.
#3
+9
Nakedible
2016-07-27 13:20:49 UTC
view on stackexchange narkive permalink

Viimeksi lisättävä asia, joka todennäköisesti liittyy kysymykseen, on se, että Landauerin periaate ei välttämättä pidä kiinni:

http://phys.org/news/2016-07- kumoaa kuuluisan fyysisen.html

He mittaivat "OR" -portin (joka on selvästi loogisesti peruuttamaton portti) käytön aikana hukkaan menneen energian määrän ja osoittivat logiikkaoperaatio voidaan suorittaa jopa 5 prosentilla odotetusta kBT ln2 -rajasta. Nature Communications -artikkelin johtopäätös on, että ei ole mitään perustavaa laatua olevaa rajaa eikä käännettävää logiikkaa tarvita tietokoneiden käyttämiseen ilman energiankulutusta.

Miksi tämän löytäminen kesti niin kauan? Osittain siksi, että kokeessa oli saavutettava poikkeuksellinen herkkyys osoittaakseen, että Landauerin raja voidaan ylittää: yli 10-21 Joule, missä 1 Joule on energia, joka tarvitaan omenan nostamiseen metrin korkeudesta maasta. Tämä on hyvin pieni määrä energiaa.

10 - 21 joulen voima - ei vaikuta minusta poikkeuksellisen arkaluontoisena kokeiluna, koska 10 ^ 21 joulea on kaksinkertainen ihmisen vuotuinen energiankulutus.
@Mr47 Minusta tuntuu, että sen piti olla 10 ^ -21, mikä on todellakin hyvin pieni.
#4
+6
davenpcj
2016-07-15 22:13:40 UTC
view on stackexchange narkive permalink

Vaikka pidän kovasti @ thomas-porninin vastauksesta, mielestäni ensimmäisessä oletuksessa on ongelma, joka on kutsuttava esiin.

Laundauerin periaate koskee vain peruuttamattomia toimintoja.

Päinvastoin kuin jotkut saattavat olettaa, käännettävä tietojenkäsittely on jo saavutettavissa. Operaatiot ovat yleisiä kvanttitietokoneissa ja homomorfisissa salaussysteemeissä. CNOT (wiki), kuten Fredkin Gatessa, on palautuva vastine, joka tuottaa XOR-tuloksen ja erottavan kontrollibitin. Jos nämä tiedot säilytetään, operaatio voidaan peruuttaa vapaasti. Jos se sen sijaan tuhoutuu jättäen vain XOR: n, Landauerin periaate pätee.

Kuten muut ovat todenneet, kvanttilaskenta muuttaa asioita, mutta se johtuu siitä, että se käyttää CNOT-portteja XOR: n sijaan qubiteillä, jolloin ohjausbitit jätetään säilyttää kvanttisuppositiotila ja suorittaa operaatio kuluttamatta Landauerin tuhoamiskustannuksia.

Jos siis lähtötilat ovat romahtaneet, tuhotut hash-bitit (esimerkiksi) energiakustannuksilla , vastaamaan tunnettua lähtöä, syötteen laskemiseksi ei tarvita lisäkustannuksia, paitsi jokaisen bitin arvon tutkiminen.

Vähintään, tämän pitäisi vaatia vähintään hashissa olevien bittien määrä ja vähintään bittien lukumäärä syötetiedoissa. Tietyn tiivistealgoritmin kohdalla tiivisteen laskeminen lohkolle voi vaatia paljon enemmän XOR / CNOT-operaatioita kuin itse data, nämä kaikki on laskettava yhteen.

SHA-256: lle ( wiki) / 1 gigabitti, joka on 256 bittiä lähtö hashista, 1 gigabitti tulosta ja 16 ja / add / xor operaatioista 512 bitin palan jokaisessa 32 bitin osassa, plus 8 muuta 32 bitin lisäystä taitettuna nykyisessä arvossa; tai 33 kt.

Jos sinulla on ~ 2 terabittiä tallennustilaa qubiteinä ja ~ 10 -15 J bittiä kohti ongelman määrittämiseksi ja tilan tiedustelemiseksi, voit kääntää kyseisen hajautuksen.

No, ei aivan päinvastoin. Löydät joukon kaikista 1 gigabittikokoisista panoksista, jotka tuottavat kyseisen tuotoksen hajautusmerkin, ja aloita kulutus enemmän bittiä kohden valitaksesi yhden niistä.

Turvallisuustarpeista riippuen törmäys voi olla riittävä.

(EDIT) Tutkijat ovat viime aikoina julkaisseet peruuttamattoman primitiivisen operaation, joka vaatii vähemmän kuin mainittu raja, mikä viittaa virheeseen alkuperäisissä laskelmissa.



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...