Armys hjernelignende computere bevæger sig tættere på krakningskoder

US Army Research Laboratory forskere har opdaget en måde at udnytte nye hjernelignende computerarkitekturer til et ældgammelt talteoretisk problem kendt som heltalsfaktorisering.

Ved at efterligne pattedyrs hjernefunktioner i computing, Hærforskere åbner et nyt løsningsrum, der bevæger sig væk fra traditionelle computingarkitekturer og mod enheder, der er i stand til at operere inden for ekstrem størrelse-, vægt-, og strømbegrænsede miljøer.

"Med mere computerkraft på slagmarken, vi kan behandle oplysninger og løse beregningsmæssigt hårde problemer hurtigere, "sagde Dr. John V." Vinnie "Monaco, en ARL -datalog. "Programmering af den type enheder, der passer til disse kriterier, for eksempel, hjerneinspirerede computere, er udfordrende, og krakning af kryptokoder er kun en applikation, der viser, at vi ved, hvordan vi gør dette. "

Selve problemet kan angives i enkle vendinger. Tag et sammensat heltal N og udtryk det som produktet af dets primære komponenter. De fleste mennesker har afsluttet denne opgave på et tidspunkt i folkeskolen, ofte en øvelse i elementær regning. For eksempel, 55 kan udtrykkes som 5*11 og 63 som 3*3*7. Hvad mange ikke var klar over, var, at de udførte en opgave, som hvis den blev udført hurtigt nok til store antal, kunne bryde meget af det moderne internet.

Kryptering af offentlig nøgle er en metode til sikker kommunikation, der bruges meget i dag, baseret på RSA -algoritmen udviklet af Rivest, Shamir, og Adleman i 1978. RSA -algoritmens sikkerhed er afhængig af vanskeligheden ved at faktorisere et stort sammensat heltal N, den offentlige nøgle, som distribueres af modtageren til alle, der ønsker at sende en krypteret besked. Hvis N kan indregnes i dets primære komponenter, derefter den private nøgle, nødvendig for at dekryptere meddelelsen, kan gendannes. Imidlertid, vanskeligheden ved at regne store heltal hurtigt frem.

Når størrelsen på N stiger med et enkelt ciffer, den tid det ville tage at faktor N ved at prøve alle mulige kombinationer af primfaktorer er omtrent fordoblet. Det betyder, at hvis et tal med ti cifre tager 1 minut at faktorere, et tal med tyve cifre vil tage omkring 17 timer og et tal med 30 cifre omkring to år, en eksponentiel vækst i indsatsen. Denne vanskelighed ligger til grund for sikkerheden ved RSA -algoritmen.

Udfordrer dette, Monaco og hans kollega Dr. Manuel Vindiola, fra laboratoriets afdeling for beregningsvidenskab, demonstreret, hvordan hjernelignende computere fremskynder de aktuelt mest kendte algoritmer til factoring af heltal.

Forskergruppen har udtænkt en måde at faktorisere store sammensatte heltal ved at udnytte den massive parallelisme af nye computerarkitekturer, der efterligner pattedyrhjernens funktion. Såkaldte neuromorfe computere fungerer efter vidt andre principper end konventionelle computere, såsom bærbare computere og mobile enheder, alt baseret på en arkitektur beskrevet af John von Neumann i 1945.

I von Neumann -arkitekturen, hukommelse er adskilt fra den centrale behandlingsenhed, eller CPU, som skal læse og skrive til hukommelsen over en bus. Denne bus har en begrænset båndbredde, og meget af tiden, CPU'en venter på at få adgang til hukommelse, ofte omtalt som von Neumann -flaskehalsen.

Neuromorfe computere, på den anden side, ikke lider af en von Neumann -flaskehals. Der er ingen CPU, hukommelse, eller bus. I stedet, de indeholder mange individuelle beregningsenheder, meget ligesom neuroner i hjernen.

Disse enheder er forbundet med fysiske eller simulerede veje til overførsel af data, analog til synaptiske forbindelser mellem neuroner. Mange neuromorfe enheder fungerer baseret på de fysiske responsegenskaber for det underliggende materiale, såsom grafenlasere eller magnetiske tunnelkryds. På grund af dette, disse enheder forbruger størrelsesordener mindre energi end deres von Neumann -kolleger og kan fungere på en molekylær tidsskala. Som sådan, enhver algoritme, der er i stand til at køre på disse enheder, kan drage fordel af deres muligheder.

Hastigheden opnået af ARL-forskerne skyldes formuleringen af ​​en metode til heltalsfaktorisering ved hjælp af en neuromorf co-processor. De nuværende hurtigste algoritmer til factoring af heltal består primært af to faser, sigtning og en matrixreduktion, og sigtningsfasen omfatter det meste af beregningsindsatsen.

Sigtning indebærer søgning efter mange heltal, der tilfredsstiller en bestemt egenskab kaldet B-glat, heltal, der ikke indeholder en primfaktor større end B. Monaco og Vindiola var i stand til at konstruere et neuralt netværk, der opdager B-glatte tal hurtigere og med større nøjagtighed end på en von Neumann-arkitektur. Deres algoritme udnytter den massive parallelisme af hjerneinspirerede computere og individuelle neurons medfødte evne til at udføre aritmetiske operationer, såsom tilføjelse. Efterhånden som neuromorfe arkitekturer fortsat stiger i størrelse og hastighed, ikke begrænset af Moores lov, deres evne til at tackle større heltal faktoriseringsproblemer vokser også. I deres arbejde, det anslås, at 1024-bit nøgler kunne brydes på cirka et år, en opgave, der engang troede at være uden for rækkevidde. Til sammenligning, den nuværende rekord, et 232 decimaltal (RSA-768) tog omkring 2, 000 års computetid i løbet af flere år.

Fra et bredere perspektiv, denne opdagelse får os til at stille spørgsmålstegn ved, hvordan et skift i computingparadigme kan påvirke nogle af vores mest grundlæggende sikkerhedsantagelser. Når nye enheder skifter til at inkorporere massiv parallelisme og udnytte materialets fysik til at beregne, den beregningsmæssige hårdhed, der ligger til grund for nogle sikkerhedsprotokoller, kan blive udfordret på måder, man ikke tidligere havde forestillet sig. Dette arbejde åbner også døren for nye forskningsområder inden for nye computerarkitekturer, hvad angår algoritmedesign og funktionsrepræsentation, sammen med applikationer med lav effekt og maskinel intelligens.

"Krypterede meddelelser i krigsførelse har ofte en udløbsdato, når deres indhold ikke kan bruges, "Sagde Monaco." Det haster med at dekryptere fjendtlig kommunikation, især dem på markniveau, da disse udløber hurtigst, sammenlignet med kommunikation på højere niveauer. I feltforhold, strøm og forbindelse er yderst begrænset. Dette er en stærk motiverende faktor for at bruge en hjerneinspireret computer til en sådan opgave, hvor konventionelle computere ikke er praktiske. "