Starter med SRVB Cryptosystem

Introduksjon

Informasjonssikkerhet er et fascinerende kunnskapsfelt som kan involvere alt fra teoretisk databehandling til programvareteknikk og til og med å se på psykologien til menneskelige feil.

Crypto er nå en av de mange anonyme teknologiske heltene i vårt daglige liv. Sosiale medier, nettbank, militær etterretning og ethvert annet informasjonssystem som håndterer sensitiv informasjon er sterkt avhengig av kryptografi. Kryptografi tillater oss å ha personvern, som noen vurderer den 12. menneskerettigheten .

Denne artikkelen vil gi deg en introduksjon til prinsippene bak offentlige nøkkelkryptosystemer og introdusere deg for Santana Rocha-Villas Boas (SRVB) , et kryptosystem utviklet av forfatteren av artikkelen og prof. Daniel Santana Rocha. I skrivende stund forbereder forfatterne av algoritmen en kampanje som inkluderer en økonomisk belønning for alle som klarer å knekke koden. Siden artikkelen vil dekke algoritmens funksjonalitet i detalj, er dette det beste stedet å starte søket etter prisen. Mer informasjon er tilgjengelig i SRVB-side .

Hva er et kryptosystem?

Kryptografi er en hvilken som helst metode for å hindre tolkbarheten av et budskap, samtidig som det tillates en måte å tolke det på en levedyktig måte så lenge en spesifikk instruksjon er gitt, som vanligvis er den såkalte 'nøkkelen'. Selv om dette er en veldig bred definisjon som inkluderer selv de første teknikkene, er det verdt å nevne at dette ikke dekker alt som er til informasjonssikkerhet.

Det er håpet at teknologiløpet mellom krypteringsmetoder og måter å knekke dem aldri vil ha en klar vinner. Også at hver nye generasjon hever standardene for informasjonssikkerhet og kryptanalyse, som er settet med teknikker for systematisk å dekryptere / bryte krypterte meldinger, det vil si omgå sikkerhet eller kryptering.

For at brukere skal kunne vurdere at et kryptosystem (gitt teknikken for kryptografi) er sikkert, må det ha godkjenning fra det internasjonale ekspertsamfunnet og derfor være offentlig kjent, som er kjent som Kerckhoffs prinsipp . Imidlertid utsetter denne tilstanden systemet for gransking fra det globale kryptanalysesamfunnet, som vil prøve å utvikle måter for systematisk å bryte kryptering.

Hvordan kan du gjøre en bestemt krypteringsprosess hemmelig nok til at bare forsøkte agenter kan knekke den, mens du fremdeles er offentlig nok til at det globale kryptanalysesamfunnet kan vitne om dets robusthet? Svaret er en komponent som er et nøkkelelement i Kryptologi: nøkkelen. En nøkkel til et kryptosystem er en parameter for krypterings- eller dekrypteringsalgoritmene, eller begge deler. Ved å holde parametrene hemmelige, i stedet for algoritmefamilien, kan begge motstridende kravene oppnås. Så lenge parameterfamilien er stor nok (muligens uendelig) og hver av dens komponenter kan vises å ha tilstrekkelige egenskaper, vil det ikke være mulig for angripere å bestemme parametrene bare ved inspeksjon.

Til slutt, for at en nøkkel skal fungere effektivt, må den produseres enkelt, men nesten umulig å gjette. Med beregningskraften til dagens datamaskiner, ville en datamaskin ta kortere tid å knekke en menneskelig generert nøkkel enn noe menneske noen gang ville trenge å forestille seg, pluss at det uansett ikke er lønnsomt å generere nøkler på den måten. På grunn av det, har nøklene en tendens til å bli generert av en algoritme.

En nøkkelgenereringsalgoritme må ikke skape forutsigbare / reproduserbare utganger som et resultat av typisk bruk. Siden algoritmer utfører prosedyrer uten intelligente prosesser, er spørsmålet hvordan dette kan gjøres. Svaret er å konvertere nøkkelgenereringsalgoritmer til kart som forvandler et stort antall virkelig tilfeldige biter til nøkler. Virkelig tilfeldige biter kan anskaffes fra operativsystemet, noe som genererer dem fra usikkerhet i universet. Noen kilder vil være musebevegelser, nettverkspakkeforsinkelser eller til og med dedikert maskinvare, avhengig av applikasjonen.

Offentlige nøkkelkryptosystemer

Forbered deg på å bli overrasket en gang til, for nå vil vi introdusere et konsept som tilsynelatende strider mot det vi nettopp sa: den offentlige nøkkelen.

Så langt har vi sett opprettelsen av sikker kommunikasjon etter at de hemmelige parametrene (nøklene) har blitt utvekslet sikkert, men problemet med å utveksle parametrene gjennom en offentlig kanal gjenstår. På dette punktet vil vi introdusere et konsept som løser et litt mer håndgripelig problem: å skape en sikker kanal.

La oss si at Alice jobber med Bob, og de ønsker å holde arbeidsinteraksjonene sine trygge ved kryptering. De kan finne og bytte krypteringsnøklene sine ved å overlevere en USB-flashstasjon med nøklene. Men hva om Alice og Bob befinner seg på forskjellige kontinenter? Hvordan etablere en sikker kanal der det ikke er noen?

Å sende nøkler via e-post ville ikke være et alternativ, siden konkurrenten Eve kan fange sentralen og bruke nøklene til å lese alle de krypterte dataene senere. Hvis de hadde en annen digital kanal som de kunne overføre denne sensitive informasjonen gjennom, ville de ikke trenge kryptering og derfor nøklene i utgangspunktet. Sending av nøkkelen via fysisk post kan også avskjæres, siden det til å begynne med er nødvendig å utveksle konfidensiell informasjon. Send en stegangrafert nøkkel gjemmer seg i andre data det ville være smart, men ubrukelig med mindre avsenderen er sikker på at mottakeren, og mottakeren alene, er klar over eksistensen av en slik melding og vet hvordan den skal hentes ut. Det er bare slik at bevisstheten om eksistensen av en melding sammen med beskrivelsen av hvordan du trekker ut nøkkelen fra dataene, er en type nøkkel i seg selv, som bringer oss tilbake til utgangspunktet.

Løsningen er å designe et kryptosystem som krypteringsparameteren ikke er nok til å tolke den originale meldingen gjennomførbart. ^[en] , og lagrer parameteren som lar deg tolke meldingen. Vi kaller den parameteren den private nøkkelen. Basert på den private nøkkelen, kan man muligens generere et sett med parametere for et krypteringsverktøy uten å få de nye parameterne til å avsløre hva den private nøkkelen er. Det settet med parametere kan deles offentlig fordi det ikke er så viktig hvem som kan kryptere noe, så lenge bare én person kan dekryptere det. Siden dette settet med parametere for krypteringsverktøyet kan gjøres offentlig, kalles det en offentlig nøkkel.

Kryptografi der krypterings- og dekrypteringsnøkler er forskjellige, og førstnevnte ikke kan brukes til å utlede sistnevnte, kalles asymmetrisk kryptografi, mens symmetrisk kryptografi er det vi har når disse nøklene er like eller lett utledes fra hverandre. Alice sender Bob sin offentlige nøkkel, som bare kan brukes til å kryptere ting som bare hun kan dekryptere (med sin private nøkkel, som hun holder privat), og omvendt sender Bob Alice sin offentlige nøkkel, som bare kan brukes til å kryptere ting at bare han kan dekryptere (ved hjelp av sin private nøkkel, som han også holder privat). Men hvordan kan du legge ut en parameter for en krypteringsalgoritme som den eksakte inverse algoritmen ikke kan trekkes fra?

Svaret ligger innen matematikk mer relatert til programmering, teorien om beregningskompleksitet . Alle som har gått dypt nok i matteproblemer, har hørt om transformasjoner som er enkle å gjøre på en måte, men vanskelig å gjøre omvendt. I beregning, for eksempel, er det vanligvis en enkel øvelse å finne et derivat av en lærebok mens du gjør det inverse (som å løse en hvilken som helst fysisk del eller litt ikke-triviell fysisk lærebok. ODE eller PDE , for eksempel) krever en mer undersøkende prosess av den første hypotesen om funksjonsfamilier som garantert (eller i det minste troverdig) inneholder løsningen (e) og løser omvendte problemer for å finne løsninger på disse familiene.

Et eksempel som faktisk brukes i RSA kryptosystem multipliserer store primtall i stedet for å ta det resulterende produktet i betraktning uten å vite faktorene. Å gjøre multiplikasjonen er trivielt, men factoring krever det tilfeldig ^[2] gjett de viktigste faktorene, som har hundrevis av sifre. En viktig egenskap ved operasjonen er behovet for å skalere godt. Legge til noen få sifre over størrelsen på primtallene i RSA vil resultere i en nøkkel som krever tusenvis av flere operasjoner for å dekryptere og legge til en liten økning i kompleksiteten i krypteringsprosessen. Generelt sett brukes produktet av primtall for kryptering, mens paret av primfaktorer brukes til dekryptering.

Med alt dette i tankene, la oss ta en titt på hvordan SRVB-krypteringssystemet fungerer.

Den underliggende algoritmen: undersøk SRVB

Delsett-sumsproblemet

Som ethvert annet offentlig nøkkelkryptosystem, er SRVB avhengig av vanskeligheten med å løse et bestemt problem som er lett å produsere. Når det gjelder SRVB, er det Delsett sumproblem , som kan beskrives som følger:

Dado el entero $ w $ og $ v_1, cdot cdot cdot, v_N i Z $ encuentra la secuencia $ b_1, cdot cdot cdot, b_N i {0,1} $, slik at $ sum_ {i = 1} ^ {N} v_i b_i = w $.

Det er klart at dette problemet kan oppstå ved å tilfeldig velge N-heltall, tilfeldig velge en delmengde av dem, og oppsummere denne delmengden, noe som er trivielt.

Et brute force-søk vil ha en kompleksitet på $ O (N * 2 ^ N) $, beregner for hver kombinasjon av $ b $ s-verdier. En mer effektiv tilnærming ble gitt av Horowitz og Sahni i 1972 , med en kompleksitet av O (N * 2N / 2). Problemet er minst like vanskelig hvis vi erstatter $ b $ s og $ w $ med $ k $ - dimensjonale vektorer av heltall. Imidlertid må omfanget der dette vanskeligere problemet må utføres også ha et isomorfisme med en [ring] (https://en.wikipedia.org / wiki / Ring_ (matematikk)) der en enklere versjon av det samme problemet utføres, som vi vil se neste. Av denne grunn utnytter SRVB delmengdeproblemet innen Gaussiske heltall , hvor $ k = 2 $ ..

Det er et spesielt tilfelle der dette problemet er enkelt å beregne ved hjelp av en grådig algoritme. Hvis vi bestiller en sekvens av skaleringsfaktorer $ v_1, cdot cdot cdot, v_N $ der hvert heltall i sekvensen er større enn summen av alle heltall som gikk foran den ($ forall i, sum_ {j = 1 } ^ {i-1} v_jsekvens av overdreven forstørrelse .

Her er en enkel beskrivelse av den grådige løsningen for denne saken:

1. Det starter med $ i = N $, den nåværende observerte faktoren, og $ w ’= w $, resten av $ w $

2. Hvis den nåværende skaleringsfaktoren er for stor til å passe resten av $ w $, betyr det at $ v_i> w '$, sett $ b_i = 0 $ og fortsett til neste trinn. Ellers vet vi at skaleringsfaktoren må være i sekvensen (siden resten av faktorene er mindre enn $ v_i $), og derfor setter vi $ b_i = 1 $.

3. $ w ’ Leftarrow w’ - v_i * b_i $, $ i Leftarrow i - 1 $. Si $ i> 0 $, vuelve al paso 2.

4. Bekreft det, nå $ w '== 0 $, ellers er problemet ødelagt.

Dette fungerer fordi vi vet at alle multiplikatorer som er mindre enn den som i øyeblikket er observert ikke samlet kan dekke så mye av (under) sum $ w '$ som den nåværende multiplikatoren. Så hvis den gjenværende summen er større enn den nåværende faktoren, vet vi med sikkerhet at alle følgende faktorer sammen ikke kan oppsummeres uten hjelp av den nåværende faktoren. På den annen side, siden alle multiplikatorer er positive, hvis den nåværende faktoren $ v_i $ er større enn den gjenværende summen $ w '$, vil tilføying av en hvilken som helst annen faktor få resultatet til å overstige $ w' $ enda mer.

Vi skal sette opp en kommentar for resten av artikkelen. Vi velger $ v_1, cdot cdot cdot, v_n $ og $ w $ for å være faktorene og summen av overøkningssekvensen, mens $ u_1, cdot cdot cdot, u_n $ og $ y $ vil være The offentlige tilgjengelige parametere er gitt for å hente $ b_1, cdot cdot cdot, b_n $.

Med en sekvens $ u_1, cdot cdot cdot, u_n $ valgt for ikke å være super fantastisk, og tallet $ y $ er offentlig tilgjengelig, ikke nok informasjon blir gitt offentlig for å hente sekvensen $ b_1, cdot cdot cdot, b_n $. Imidlertid, hvis det er en super fantastisk sekvens $ v_1, cdot cdot cdot, v_n $ som kan ta plassen til sekvensen $ u_1, cdot cdot cdot, u_n $, kan denne sekvensen brukes til å løse problem med en grådig tilnærming.

Vi vil vise hvordan det fungerer nedenfor.

Bruk av sum av delmengder i et eldre kryptosystem

I 1978, Ralph Merkle og Martin Helman , de utviklet en måte å utnytte de to ryggsekkparadigmene og linearitet av moduloperasjonen for å bygge forbindelsen mellom de to sekvensene som er beskrevet i forrige avsnitt, og dermed oppnå et krypteringssystem for offentlig nøkkel. Ideen var å transformere enkel ryggsekk (den som består av den superøkende vektoren til heltallene) i den harde (den som mangler denne egenskapen) ved hjelp av en lineær operasjon (modulen) med hemmelige operander. Transformasjonen består i å multiplisere hver $ v_i $ med til $ theta $ og ta resten av dette produktet med en $ alpha $, hvor $ alpha gt sum_ {i = 1} ^ N v_i $ og $ gcd ( alpha, theta) = 1 $ (to begrensninger som snart vil være berettiget). Resultatet, sekvensen $ u_1, ldots, u_N $, øker ikke lenger, og kan betraktes som en vanskelig ryggsekk .

En tilfeldig permutasjon av sekvensen $ u_1, ldots, u_N $ vil bli gitt til partiet som ønsker å kryptere og sende oss en melding. Permutasjon gjøres slik at en tredjepart har vanskelig for å gjette hva den opprinnelige superøknings-sekvensen er. Bitblokkene i en melding brukes som koeffisienter $ b_1, ldots, b_N $. Krypteringen gjøres ved å multiplisere sekvensen av nøkler med denne sekvensen av koeffisienter, og legge til multiplikasjonene i et resultat, som vi må merke $ og $. Bare eieren av den private nøkkelen kan transformere $ y $ til den tilsvarende $ w $ som ville blitt oppnådd hvis de samme $ b_1, ldots, b_N $ blokker ble multiplisert med enkle heltall (sekvensen $ v_1, ldots, v_N $). Dette gjøres ved å multiplisere $ y $ med $ theta ^ {- 1} $, the invers multiplikativ av $ theta $ modul $ alpha $ (hvis eksistens avhenger av den tilstanden til $ gcd ( alpha, theta) = 1 $). Med andre ord, $ ( theta * theta ^ {- 1}) bmod alpha = 1 $. Etter det beregner vi $ w = (y * theta ^ {- 1}) bmod a $. Årsaken til at dette garantert fungerer, er modulær linearitet , det vil si at den lineære kombinasjonen av restene er lik resten av den lineære kombinasjonen.

Hvis vi fortløpende bruker definisjonen på $ u $, kvotientringen og linearitetsegenskapen til moduloperatøren, ser vi korrespondansen:

$ begin {align} y & = sum_ {i = 1} ^ N b_iu_i newline & = sum_ {i = 1} ^ N b_i (v_i * theta bmod alpha) newline & = sum_ { i = 1} ^ N b_i * v_i * theta bmod alpha newline & = left [ sum_ {i = 1} ^ N b_i * v_i * theta right] bmod alpha newline & = venstre [ sum_ {i = 1} ^ N b_i * v_i høyre] * theta bmod alpha newline & = w * theta bmod alpha end {align} $

Og så den den enkle summen $ w $ kan hentes ved å multiplisere begge sider med $ theta ^ {- 1} $ og ta modulen med $ alpha $. For å gjøre dette, må man vite både $ alpha $ og $ theta $ (som gjør at $ theta ^ {- 1} $ enkelt kan beregnes), som må holdes private som deler av den private nøkkelen.

En enkelt begrensning, $ alpha gt sum_ {i = 1} ^ N v_i $, var ikke berettiget, og her er forklaringen: likestillingen mellom andre og tredje linje består av en likhet mellom typer avfall av kvotientring av heltallene modulo $ alpha $. Med andre ord setter den bare likheten til resten av medlemmene når de deler med $ alpha $, som ikke er en tilstrekkelig forutsetning for likestilling mellom medlemmene . Som et resultat kan mer enn en vektor med $ b $ -verdier kartlegges til en enkelt $ y $, som unngås ved å begrense $ w $ til å være mindre enn $ alpha $ for en kombinasjon av $ b $ -verdier.

Som alle andre tilfeller av hverdagen, er full kunnskap om alle hypoteser ofte umulig og aldri lett. Som et resultat må vi stole på matematisk intuisjon når vi vurderer om et kryptografisk system er trygt å bruke, noe som ikke gir oss reelle garantier. Seks år etter opprettelsen brøt MH-kryptosystemet med en angrep av A. Shamir . Det var flere forsøk på å gjenopplive MH, hvorav mange også mislyktes.

Santana Rocha Cryptosystem - Villas Boas (SRVB)

I 2016, etter litt idédugnad med forfatteren av denne artikkelen om ^[3] Inspirerte muligheter for et kryptosystem hadde Daniel Santana Rocha ideen om å erstatte $ theta $ og $ alpha $ for Gaussiske heltall. Av mer tekniske årsaker fører denne tilnærmingen til motstand mot det nevnte Shamir-angrepet.

Han oppfattet også en blokk med biter som består av mange trinn i den tidligere beskrevne lineære kombinasjonen av a napa dura . I hver av dem vil et nytt heltall (gaussisk), tilsvarende en, høyere enn summen av alle de forrige bli lagt til på slutten av sekvensen, mens det minste tallet vil bli eliminert.

En annen, men elegant analog begrensning gjelder for $ alpha $, som nå er et Gaussisk heltall. Vi krever $ w leq vert alpha vert ^ 2 $, hvor $ w $ igjen er den høyeste lineære kombinasjonen av de naturlige heltallene i den enkle ryggsekken. Årsaken er veldig vanskelig å formalisere, men det kan heldigvis lett gjettes ut fra en elegant beskrivelse:

Tenk deg et firkantet gitter i det komplekse tallplanet, hvis side er en hypotenus av en rett trekant av ben a og b, parallelt med de virkelige og imaginære aksene. Et eksempel på et slikt gitter er gitt nedenfor. Guassiske heltall modulo $ alpha = a + bi $ kan representeres av punkter lokalisert i nevnte gitter. Innenfor dette nettverket er det $ vert alpha vert ^ 2 $ forskjellige punkter. Hvis vi velger en stor nok $ alpha $, kan vi passe på alle de lineære kombinasjonene av den enkle ryggsekken. Så vi setter et krav til $ w leftarrow vert alpha vert ^ 2 $, hvor w er [som beskrevet].

Dette er den grafiske representasjonen av isomorfismen $ f: Z / n rightarrow Z [i] / ( alpha) $, hvor $ n = 13 $ og $ alpha = a + bi = 3 + 2i $ (merk at $ n $ og $ alpha $ tilfredsstiller faktisk $ n = vert alpha vert ^ 2 = a ^ 2 + b ^ 2 $ etter behov). Punktene representerer de gaussiske heltallene, det vil si de komplekse tallene $ a + bi $, der $ a $ og $ b $ er heltall. Som vanlig representerer den horisontale aksen den virkelige delen, mens den vertikale representerer den imaginære delen. Flytting av et punkt mot høyre eller venstre tilsvarer derfor å legge til henholdsvis +1 eller -1 til den nåværende verdien. På samme måte tilsvarer å flytte et punkt opp eller ned med å legge til henholdsvis + i eller -i.

De røde prikkene tilsvarer $ 0 bmod ( alpha) $. I tillegg til disse farger vi også 4 flere par poeng.

$ F $ isomorfismen er definert av transformasjonen av $ i $ th-elementet i den sykliske sekvensen $ (0,1,2, cdot cdot cdot, 10,11,12,0,1,2, cdot cdot cdot) $ i $ i $ th-elementet i den også sykliske sekvens av punkter i figuren, som følger følgende regler:

1. Start fra den røde prikken i første rad;
2. Følg høyre horisontale piler; bortsett fra det
3. Når du følger pilene, tar sekvensen ut av gitteret, når den en av de ikke-svarte punktene. I stedet for å gå til det punktet, hopper det til samme fargede punkt (det vil si ekvivalent punktmodul $ alpha $) innenfor samme firkant; og endelig
4. Når dette ikke-svarte punktet blir rødt (som skjer etter at alle de andre fargene har passert), hopper sekvensen til det øvre røde punktet, og starter dermed syklusen på nytt;

For å kartlegge minst $ Y $ naturlige heltall, ta et kvadrat med området $ vert alpha vert ^ 2 $ (der $ vert alpha vert = sqrt {a ^ 2 + b ^ 2} $ er av Pythagoras-teorem , målingen på din side) minst like høy.

Legg merke til at hvert 'hopp' endrer radnummeret $ r $ til $ r leftarrow (r + b) (mod a + b) $ hvis man teller radene fra topp til bunn, og, tilsvarende, til $ r leftarrow ( r + a) (mod a + b) $ hvis man teller fra bunnen av. Derfor er den nødvendige og tilstrekkelige betingelsen for at hver rad (og punkt) skal krysses nøyaktig en gang i hver syklus at størrelsen på hoppene er koprime med antall rader, eller med andre ord $ gcd (a, a + b) = gcd (b, a + b) = 1 $. På grunn av egenskapene til den største felles divisoroperatøren tilsvarer begge $ gcd (a, b) = 1 $.

Y. S. Villas Boas bemerket behovet for $ a $ og $ b $ coprimity. For å bevare superinkrement, må hvert nye heltall $ w $ som legges til slutten av sekvensen, overstige summen av alle nåværende ($ w> sum_ {i = 1} ^ k v_i $). Du observerte at for å oppnå dette måtte multiplikasjonskoeffisientene $ b_i $ være minst 1, og derfor kunne ikke hver bit kartlegges til koeffisientene 0 og 1. Hvis koeffisientene var 0 og 1, bare komposittblokken bare for en ville tilfredsstille superinkrementet. Av denne grunn ble biter 0 og 1 henholdsvis kartlagt til multiplikasjonskoeffisientene 1 og 2.

Til slutt, og på en mindre triviell måte: under hvert dekodingstrinn, blir et nytt heltall $ v_1 $ funnet som en løsning på ligningen $ b_1 v_1 = v_ {n + 1} - sum_ {i = 2} ^ {n} b_i v_i $, der alle $ v_i $ og $ b_i $ er kjent med $ 1

En endelig teknisk løsning å løse er tilfellet der meldingsstørrelsen i byte ikke er et multiplum av blokkstørrelsen. Med andre ord, hva skal jeg gjøre med mulige gjenværende byte i den siste datablokken, slik at når datablokkene er hentet, bevares alle byte med det opprinnelige innholdet, men ikke mer enn dem? Vi løste det ved å gjenta den siste byten i meldingen en gang. Denne kopien blir deretter fulgt av en tilfeldig sekvens der hver komponent bare kreves for å være forskjellig fra den forrige. Derfor, når datablokkene blir hentet, den siste av dem eller i verste fall den før den siste den blir avkortet ved siste byte-repetisjon. ^[4]