Sissejuhatus

Infoturve on põnev teadmiste valdkond, mis võib hõlmata kõike alates teoreetilisest arvutamisest kuni tarkvaratehnika väljatöötamiseni ja isegi inimvigade psühholoogia vaatamiseni.

Krüpto on nüüd üks paljudest anonüümsetest tehnokangelastest meie igapäevases elus. Sotsiaalmeedia, veebipank, sõjaväeluure ja kõik muud tundlikku teavet käsitlevad infosüsteemid sõltuvad suuresti krüptograafiast. Krüptograafia võimaldab meil privaatsust, mida mõned peavad 12. inimõigus .

See artikkel tutvustab teile avaliku võtme krüptosüsteemide põhimõtteid ja tutvustab teid Santana Rocha-Villas Boas (SRVB) , artikli autori ja prof Daniel Santana Rocha välja töötatud krüptosüsteem. Kirjutamise ajal valmistavad algoritmi autorid ette kampaaniat, mis sisaldab rahalist tasu kõigile, kellel õnnestub kood murda. Kuna artikkel käsitleb algoritmi funktsionaalsust üksikasjalikult, on see parim koht auhinna otsingu alustamiseks. Lisateavet leiate veebilehelt SRVB sait .

Mis on krüptosüsteem?

Krüptograafia on mis tahes meetod sõnumi tõlgendatavuse takistamiseks, võimaldades samal ajal ka viisi selle tõlgendamiseks elujõulisena seni, kuni antakse konkreetne käsk, mis on tavaliselt nn 'võti'. Kuigi see on väga lai määratlus, mis hõlmab isegi paari esimest tehnikat, tasub mainida, et see ei hõlma kõike, mis on infoturbel.

Eeldatakse, et krüptimismeetodite ja nende purustamisviiside vahelises tehnilises võidujooksus pole kunagi lõplikku võitjat. Samuti, et iga uus põlvkond tõstaks infoturbe ja krüptanalüüsi standardeid, mis on tehnikate kogum krüpteeritud kirjade süstemaatiliseks dekrüpteerimiseks / purustamiseks, see tähendab turvalisusest või krüptimisest mööda minnes.

Selleks, et kasutajad saaksid arvata, et krüptosüsteem (arvestades krüptograafiatehnikat) on turvaline, peab see olema rahvusvahelise ekspertide heakskiidu saanud ja seetõttu avalikult tuntud, mis on tuntud kui Kerckhoffsi põhimõte . Kuid see tingimus põhjustab süsteemi ülemaailmse krüptanalüüsi kogukonna kontrolli all, mis püüab välja töötada viise krüptimise süstemaatiliseks rikkumiseks.

Kuidas saaksite teha teatud krüptimisprotsessi piisavalt salajaseks, et ainult proovitud agendid saaksid selle lõhkuda, olles siiski piisavalt avalikud, et globaalne krüptanalüüsi kogukond saaks tõestada selle töökindlust? Vastus on komponent, mis on krüptoloogia põhielement: võti. Krüptosüsteemi võti on krüptimis- või dekrüpteerimisalgoritmide või mõlema parameeter. Parameetrite saladuses hoidmine algoritmide perekonna asemel võib saavutada mõlemad vastuolulised nõuded. Seni, kuni parameetrite perekond on piisavalt suur (võib-olla lõpmatu) ja kõigi selle komponentide omaduste kohta võib näidata piisavaid omadusi, pole ründajatel võimalik parameetreid lihtsalt kontrollimise teel kindlaks määrata.

Lõpuks, et võti töötaks tõhusalt, tuleb seda lihtsalt, kuid peaaegu võimatu ära arvata. Tänapäevaste arvutite arvutusvõimsuse korral võtaks arvuti inimese loodud võtme murdmiseks vähem aega, kui ükski inimene peaks kunagi ette kujutama, lisaks pole niimoodi tasuv võtmeid sellisel viisil genereerida. Seetõttu kipub võtmeid genereerima algoritm.

Võtme genereerimise algoritm ei tohi tüüpilise kasutamise tulemusel luua prognoositavaid / taasesitatavaid väljundeid. Kuna algoritmid täidavad protseduure ilma intelligentsete protsessideta, on küsimus selles, kuidas seda teha. Vastus on muuta võtmete genereerimise algoritmid kaartideks, mis muudavad suure hulga tõeliselt juhuslikke bitte võtmeteks. Operatsioonisüsteemist saab hankida tõeliselt juhuslikke bitte, mis genereerib need universumi ebakindlusest. Mõned allikad on hiire liikumine, võrgupaketi latentsusajad või isegi spetsiaalne riistvara, olenevalt rakendusest.

---

Avaliku võtme krüptosüsteemid

Valmistuge veel kord üllatuma, sest nüüd tutvustame kontseptsiooni, mis on ilmselt vastuolus äsja öelduga: avalik võti.

Siiani oleme näinud turvalise side loomist pärast salajaste parameetrite (võtmete) turvalist vahetamist, kuid probleem parameetrite vahetamise kohta avaliku kanali kaudu jääb alles. Siinkohal tutvustame kontseptsiooni, mis lahendab veidi käegakatsutavama probleemi: turvalise kanali loomine.

Oletame, et Alice töötab Bobiga ja nad tahavad oma tööalaseid suhtlusi krüptimise abil turvaliselt hoida. Nad saavad oma krüptovõtmeid leida ja vahetada, andes oma võtmetega üle USB-mälupulga. Aga mis siis, kui Alice ja Bob asuvad erinevatel mandritel? Kuidas luua turvaline kanal seal, kus seda pole?

Võtmete saatmine e-posti teel ei oleks võimalus, kuna tema konkurent Eve saab vahetuse pealtkuulata ja kasutada oma võtmeid kõigi krüpteeritud andmete hiljem lugemiseks. Kui neil oleks mõni muu digitaalkanal, mille kaudu nad saaksid seda tundlikku teavet edastada, ei vajaks nad ennekõike krüptimist ja seetõttu võtmeid. Samuti võis kinni pidada võtme saatmist füüsilise posti teel, sest kõigepealt on vaja konfidentsiaalset teavet vahetada. Saada üks teistes andmetes peituv stegangreeritud võti see oleks tark, kuid kasutu, kui saatja pole kindel, et adressaat ja ainult saaja on teadlik sellise sõnumi olemasolust ja teab, kuidas seda välja võtta. Nii juhtub, et teadlikkus sõnumi olemasolust koos kirjeldusega, kuidas võtmetest andmetest välja võtta, on võtme tüüp, mis viib meid lähtepunkti.

Lahendus on krüptosüsteemi kujundamine, mille krüpteerimisparameetrist ei piisa originaalsõnumi mõistlikuks tõlgendamiseks. ^[üks] ja salvestades teile parameetri, mis võimaldaks teil sõnumit tõlgendada. Nimetame seda parameetrit privaatvõtmeks. Privaatvõtme põhjal saab krüptimisvahendi jaoks parimal viisil luua parameetrite komplekti, panemata neid uusi parameetreid avalikustama, mis on privaatne võti. Seda parameetrite komplekti saab avalikult jagada, sest pole nii oluline, kes saab midagi krüptida, kui ainult üks inimene saab selle dešifreerida. Kuna seda krüptimistööriista parameetrite komplekti saab avalikustada, nimetatakse seda avalikuks võtmeks.

Krüptograafiat, kus krüptimis- ja dekrüpteerimisvõtmed erinevad ning esimest ei saa kasutada teise järeldamiseks, nimetatakse asümmeetriliseks krüptograafiaks, samas kui sümmeetriline krüptograafia on meil siis, kui need võtmed on samad või üksteisest kergesti järeldatavad. Alice saadab Bobile oma avaliku võtme, mida saab kasutada ainult selliste asjade krüptimiseks, mille ainult tema saab dekrüpteerida (oma privaatvõtmega, mille ta hoiab privaatsena) ja vastupidi, Bob saadab Alice'ile oma avaliku võtme, mida saab kasutada ainult asjade krüptimiseks et ainult ta saab dekrüpteerida (kasutades oma privaatvõtit, mida ta ka privaatsena hoiab). Kuidas saab aga krüptimisalgoritmi jaoks parameetrit postitada, millest täpset pöördalgoritmi ei saa tuletada?

Vastus peitub matemaatika valdkonnas, mis on rohkem seotud programmeerimisega, arvutusliku keerukuse teooria . Igaüks, kes on piisavalt süvenenud matemaatikaülesannetesse, on kuulnud teisendustest, mida on lihtne teha ühel ja teisel viisil. Näiteks arvestuses on õpiku tuletise leidmine tavaliselt lihtne harjutus, tehes samal ajal pöördvõimalust (näiteks mis tahes füüsilise osa või veidi mitte triviaalse füüsilise õpiku lahendamine). ODE või PDE Näiteks nõuab funktsioonide perekondade esimese hüpoteesi, mis on tagatud (või vähemalt usutav), uurimisprotsessi, et sisaldada lahendust (lahendusi) ja lahendada pöördprobleeme nende perekondade lahenduste leidmiseks.

Näide, mida tegelikult kasutatakse RSA krüptosüsteem korrutab suurepäraseid algarvusid selle asemel, et saadud toodet tegureid teadmata faktoriseerida. Korrutamise tegemine on triviaalne, kuid faktooring nõuab seda juhuslikult ^[2] arvake ära peamised tegurid, millel on sadu numbreid. Operatsiooni oluline omadus on vajadus hästi skaalata. Mõne numbri lisamisel algarvude suurusele RSA-s saadakse võti, mille dekrüpteerimiseks ja krüpteerimisprotsessi keerukuse lisamiseks on vaja veel tuhandeid toiminguid. Üldiselt kasutatakse krüptimiseks algarvude korrutist, dešifreerimiseks aga algtegurite paari.

Kõike seda silmas pidades heidame pilgu sellele, kuidas töötab SRVB krüptograafiline süsteem.

Alusalgoritm: uurige SRVB-d

Alamhulga summa probleem

Nagu iga teine ​​avaliku võtme krüptosüsteem, tugineb SRVB ka konkreetse probleemi lahendamise raskusele, mida on lihtne toota. SRVB puhul on see Alamhulga summa probleem , mida saab kirjeldada järgmiselt:

Dado el entero $ w $ ja $ v_1, cdot cdot cdot, v_N Z $ encuentra la secuencia $ b_1, cdot cdot cdot, b_N sisse {0,1} $, nii et $ sum_ {i = 1} ^ {N} v_i b_i = w $.

On selge, et see probleem võib ilmneda juhuslikult valides N täisarvu, valides juhuslikult nende alamhulga ja kokku võttes selle tühise, mis on tühine.

Toore jõuotsingu keerukus on $ O (N * 2 ^ N) $, arvutades iga $ b $ s väärtuste kombinatsiooni jaoks. Tõhusama lähenemisviisi andis Horowitz ja Sahni 1972. aastal , keerukusega $ O (N * 2N / 2). Probleem on vähemalt sama keeruline, kui asendame $ b $ s ja $ w $ täisarvude dimensioonivektoritega $ k $. Kuid ulatusel, kus seda raskemat probleemi tuleb lahendada, peab olema ka isomorfism [rõngaga] (https://et.wikipedia.org / wiki / Ring_ (matemaatika)), kus viiakse läbi sama probleemi lihtsam versioon, nagu näeme järgmisena. Sel põhjusel kasutab SRVB ära alamhulga summa probleemi Gaussi täisarvud , kus $ k = 2 $ ..

On erijuhtum, kus seda probleemi on ahne algoritmi abil lihtne arvutada. Kui tellime skaalategurite jada $ v_1, cdot cdot cdot, v_N $, milles jada iga täisarv on suurem kui kõigi sellele eelnenud täisarvude summa ($ forall i, sum_ {j = 1} liigne suurendusjärjestus .

Siin on selle juhtumi ahne lahenduse lihtne kirjeldus:

1. See algab praegu vaadeldava teguriga $ i = N $ ja $ w ’= w $, ülejäänud osa $ w $

2. Kui praegune skaalategur on liiga suur, et mahutada ülejäänud osa $ w $, tähendab see, et $ v_i> w '$, määrake $ b_i = 0 $ ja jätkake järgmise sammuga. Vastasel juhul teame, et skaalategur peab olema järjestuses (kuna ülejäänud tegurid on väiksemad kui $ v_i $) ja seega panime $ b_i = 1 $.

   häkkida krediitkaardi täielikud andmed 2018

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

4. Veenduge, et nüüd on $ w '== 0 $, vastasel juhul on probleem rikutud.

See töötab, sest me teame, et kõik praegu vaadeldavatest väiksemad kordajad ei saa ühiselt katta nii suurt osa (ala) summast $ w '$ kui praegune kordaja. Nii et kui järelejäänud summa on suurem kui praegune tegur, teame kindlalt, et kõiki järgmisi tegureid kokku ei saa ilma praeguse teguri abita kokku võtta. Teiselt poolt, kuna kõik kordajad on positiivsed, siis kui praegune tegur $ v_i $ on suurem kui ülejäänud summa $ w '$, muudaks mis tahes muu teguri lisamine tulemuse veelgi suuremaks kui $ w' $.

Kavatseme ülejäänud artikli jaoks märkuse koostada. Teguriteks ja ülekasvamise järjestuse summaks valime $ v_1, cdot cdot cdot, v_n $ ja $ w $, samas kui $ u_1, cdot cdot cdot, u_n $ ja $ y $ on avalikud saadaolevad parameetrid, mis on ette nähtud seadmete $ b_1, cdot cdot cdot, b_n $ hankimiseks.

Kui järjestus $ u_1, cdot cdot cdot, u_n $ on valitud mitte eriti vinge ja number $ y $ on avalikult saadaval, ei esitata avalikult piisavalt teavet järjestuse $ b_1, cdot cdot hankimiseks cdot, b_n $. Kui aga on olemas super vinge järjestus $ v_1, cdot cdot cdot, v_n $, mis võiksid asendada järjestuse $ u_1, cdot cdot cdot, u_n $, võib seda järjestust kasutada ahne lähenemise probleem.

Kuidas see töötab, näitame allpool.

Alamhulkade summade kasutamine vanemas krüptosüsteemis

Sisse 1978, Ralph Merkle ja Martin Helman , mõtlesid nad välja viisi, kuidas neid kahte seljakotiparadigmat ja lineaarsus mooduli operatsioonist ühenduse loomiseks eelmises jaotises kirjeldatud kahe järjestuse vahel, luues seeläbi avaliku võtme krüptosüsteemi. Idee oli muuta lihtne seljakott (see, mis koosneb täisarvude ülisuurest vektorist) kõvas (selles, kus see omadus puudub), kasutades salajaste operandidega lineaarset toimingut (moodulit). Teisendus seisneb iga $ v_i $ korrutamises väärtusega $ theta $ ja ülejäänud toote võtmine $ alpha $ -ga, kus $ alpha gt sum_ {i = 1} ^ N v_i $ ja $ gcd ( alpha, theta) = 1 $ (kaks piirangut, mis peagi õigustatakse). Tulemus, järjestus $ u_1, ldots, u_N $, enam ei suurene ja seda võib pidada a-ks raske seljakott .

Jaotise $ u_1, ldots, u_N $ juhuslik permutatsioon antakse osapoolele, kes soovib meile krüptida ja meile sõnumi saata. Permutatsioon toimub nii, et kolmandal osapoolel on raske ära arvata, milline on algne ülitõusu järjestus. Sõnumi bittplokke kasutatakse koefitsientidena $ b_1, ldots, b_N $. Krüptimine toimub, korrutades võtmete jada selle koefitsientide järjestusega ja lisades tulemuseks korrutised, millele peame sildistama $ ja $. Ainult privaatvõtme omanik saab teisendada $ y $ vastavaks $ w $ -ks, mis saadakse, kui samad $ b_1, ldots, b_N $ plokid korrutatakse lihtsad täisarvud (järjestus $ v_1, ldots, v_N $). Selleks korrutatakse $ y $ korruga $ theta ^ {- 1} $, pöördvõrdeline of $ theta $ moodul $ alpha $ (mille olemasolu sõltub sellest tingimusest $ gcd ( alpha, theta) = 1 $). Teisisõnu, $ ( theta * theta ^ {- 1}) bmod alpha = 1 $. Seejärel arvutame $ w = (y * theta ^ {- 1}) bmod a $. Põhjus, miks see toimib, on mooduli lineaarsus , see tähendab, et jääkide lineaarne kombinatsioon on võrdne ülejäänud lineaarse kombinatsiooniga.

Kui rakendame järjestikku $ u $ määratlust, jagurõnga ja moodulioperaatori lineaarsuse omadust, näeme vastavust:

$ begin {joondamine} 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 * teeta right] bmod alpha newline & = vasakule [ sum_ {i = 1} ^ N b_i * v_i right] * teeta bmod alfa newline & = w * teeta bmod alfa end {joondus} $

Ja nii lihtne summa $ w $ saab kätte, korrutades mõlemad pooled väärtusega $ theta ^ {- 1} $ ja võttes mooduli väärtusega $ alpha $. Selleks peab teadma nii $ alpha $ kui ka $ theta $ (mis võimaldavad $ theta ^ {- 1} $ hõlpsasti arvutada), mis tuleb hoida privaatvõtme osana privaatsena.

Üks piirang, $ alpha gt sum_ {i = 1} ^ N v_i $, ei olnud õigustatud ja siin on selgitus: teise ja kolmanda rea ​​võrdsus koosneb võrdsusest jäätmete liigid selle jagatisrõngas täisarvudest modulo $ alpha $. Teisisõnu, see määrab ülejäänud liikmete võrdsuse ainult jagamisel $ alpha $ -ga, mis ei ole liikmete võrdsuse piisav tingimus . Selle tulemusel saab ühe $ y $ väärtustega kaardistada rohkem kui ühe vektori $ b $ väärtustest, mida saab vältida, piirates $ w $ väärtuste mis tahes kombinatsioonide puhul $ w $ vähem kui $ alpha $.

Nagu iga teine ​​igapäevane elu, on ka kõigi hüpoteeside täielik tundmine võimatu ja mitte kunagi lihtne. Seetõttu peame krüptograafiasüsteemi ohutu kasutamise üle otsustamisel tuginema matemaatilisele intuitsioonile, mis ei paku meile reaalseid garantiisid. Kuus aastat pärast selle loomist katkestas MH krüptosüsteem a rünnak kõrval A. Šamir . MH taaselustamiseks tehti veel mitu katset, millest paljud ka ebaõnnestusid.

---

Santana Rocha krüptosüsteem - Villas Boas (SRVB)

Aastal 2016, pärast ajurünnakuid selle artikli autoriga ^[3] Krüptosüsteemi inspireeritud võimalustest tekkis Daniel Santana Rochal mõte asendada Gaussi täisarvud $ theta $ ja $ alpha $. Tehnilisematel põhjustel viib selline lähenemine vastupanu ülalmainitud Shamiri rünnakule.

Ta mõtles ka bittide ploki, mis koosneb paljudest etappidest eespool kirjeldatud lineaarses kombinatsioonis a napa dura . Mõlemas neist lisatakse jada lõppu uus täisarv (Gauss), mis on võrdne ühega, suurem kui kõigi eelnevate summa, samas kui väikseim arv elimineeritakse.

Teistmoodi, kuid elegantselt analoogne piirang kehtib $ alpha $ puhul, mis on nüüd Gaussi täisarv. Nõuame väärtust $ w leq vert alpha vert ^ 2 $, kus $ w $ on jällegi lihtsa seljakoti loomulike täisarvude kõrgeim lineaarne kombinatsioon. Põhjust on väga raske vormistada, kuid õnneks saab selle elegantsest kirjeldusest lihtsalt aimata:

llc s või c corp

Kujutage ette kompleksarvu ruudukujulist võre, mille külg on täisnurga kolmnurga hüpotenuus jalad a ja b, paralleelsed reaalse ja kujuteldava teljega. Sellise võre näide on toodud allpool. Guassi täisarvusid modulo $ alpha = a + bi $ saab esitada punktides, mis asuvad nimetatud võre sees. Selles võrgus on $ vert alpha vert ^ 2 $ erinevat punkti. Kui valime piisavalt suure $ alpha $, mahutame kõik lihtsa seljakoti lineaarsed kombinatsioonid. Seega seame nõude väärtusele $ w leftarrow vert alpha vert ^ 2 $, kus w on [nagu kirjeldatud].

See on isomorfismi $ f graafiline esitus: Z / n rightarrow Z [i] / ( alpha) $, kus $ n = 13 $ ja $ alpha = a + bi = 3 + 2i $ (pange tähele, et $ n $ ja $ alpha $ vastavad tegelikult vajadusele $ n = vert alpha vert ^ 2 = a ^ 2 + b ^ 2 $). Punktid tähistavad Gaussi täisarvusid, see tähendab kompleksarvusid $ a + bi $, kus $ a $ ja $ b $ on täisarvud. Nagu tavaliselt, tähistab horisontaaltelg reaalset osa, vertikaalne aga kujuteldavat osa. Seetõttu on punkti liigutamine paremale või vasakule samaväärne +1 või -1 lisamisega selle praegusele väärtusele. Samamoodi on punkti liigutamine üles või alla samaväärne vastavalt + i või -i lisamisega.

Punased punktid on samaväärsed väärtusega $ 0 bmod ( alpha) $. Peale nende värvime veel 4 punktipaari.

Värv	Samaväärne ... mod α-ga
Oranž	1 USD
Roheline	$ i $
Sinine	$ -1-i $
violetne	$ 1-i $

Isomorfismi $ f $ määratleb tsüklilise järjestuse $ i elemendi $ i $ th muundamine (0,1,2, cdot cdot cdot, 10,11,12,0,1,2, cdot cdot cdot) $ ka joonise punktide tsüklilise tsüklilise järjestuse $ i $ th elemendis, mis järgib järgmisi reegleid:

1. Alustage esimese rea punasest punktist;
2. Järgige parempoolseid horisontaalnoole; välja arvatud see
3. Kui noolte järgimine viib jada võre alt välja, jõuaks see ühte mitte-mustasse punkti. Selle punkti minemise asemel hüppab see samas ruudus samasse värvipunkti (see tähendab samaväärsesse punktimoodulisse $ alpha $); ja lõpuks
4. Kui see mitte-must punkt muutub punaseks (mis juhtub pärast kõigi teiste värvide möödumist), hüppab järjestus ülemisse punasesse punkti, alustades seega tsüklit uuesti;

Vähemalt looduslike täisarvude $ Y $ kaardistamiseks võtke ruut, mille pindala on $ vert alpha vert ^ 2 $ (kus $ vert alpha vert = sqrt {a ^ 2 + b ^ 2} $ on Pythagorase teoreem , teie küljel olev mõõt) vähemalt sama kõrge.

Pange tähele, et iga 'hüpe' muudab rea numbri $ r $ väärtuseks $ r leftarrow (r + b) (mod a + b) $, kui loetakse ridu ülevalt alla ja samaväärselt väärtusele $ r leftarrow ( r + a) (mod a + b) $, kui üks loeb alt üles. Seetõttu on vajalik ja piisav tingimus, et igas reas (ja punktis) läbitakse täpselt üks kord igas tsüklis, et hüpete suurus oleks sama, kui ridade arv, või teisisõnu $ gcd (a, a + b) = gcd (b, a + b) = 1 $. Suurima ühisjaguri operaatori omaduste tõttu on mõlemad võrdsed väärtusega $ gcd (a, b) = 1 $.

Y. S. Villas Boas märkis vajadust $ a $ ja $ b $ ühilduvuse järele. Ülekasvu säilitamiseks peab iga jada lõppu lisatud uus täisarv $ w $ ületama kõigi praeguste arvude summa ($ w> summa_ {i = 1} ^ k v_i $). Märkasite, et selle saavutamiseks peavad teie korrutamiskoefitsiendid $ b_i $ olema vähemalt 1 ja seetõttu ei saa iga bitti kaardistada koefitsientidega 0 ja 1. Kui koefitsiendid olid 0 ja 1, siis ainult ühe liitplokk ainult ühele rahuldaks supertõusu. Sel põhjusel kaardistati bitid 0 ja 1 korrutusteguritega 1 ja 2.

Lõpuks ja vähem triviaalsel viisil: iga dekodeerimisetapi ajal leitakse uus täisarv $ v_1 $ lahendina võrrandile $ b_1 v_1 = v_ {n + 1} - sum_ {i = 2} ^ {n} b_i v_i $, kus kõik $ v_i $ ja $ b_i $ on tuntud kui $ 1

Lõplik tehniline lahendus on see, kui sõnumi suurus baitides ei ole ploki suuruse mitmekordne. Teisisõnu, mida teha viimase andmeploki võimalike järelejäänud baitidega, et pärast andmeplokkide saamist säiliksid kõik algse sisu baidid, kuid mitte rohkem kui need? Lahendasime selle, korrates sõnumi viimast baiti üks kord. Sellele eksemplarile järgneb juhuslik järjestus, milles iga komponent peab erinema ainult eelmisest. Seega, kui andmeblokid on kätte saadud, siis viimane neist või halvimal juhul üks enne viimast see kärbitakse viimasel baitide kordusel. ^[4]

Nüüd näitame SRVB krüptosüsteemi näidet.

Alustame parameetritest:

$ k = $ 4;

$ m = 4 $;

mis annab ploki pikkuse $ l = 4 * 4 = 16 $ ja ülimalt uskumatu järjestuse $ k + 1 = 5 $ looduslikud täisarvud, mida kasutatakse - ehk siis lineaarselt kombineerituna koos selle lineaarse kombinatsiooni tulemusega ja vähendati viimase k + 1 elemendini _— m = 4 korda;

Olgu lihtsuse huvides järgmine: $ v_i $ (ülimalt uskumatu) vektor:

$ (1,2,4,8,16) $

Tegelikult on viie esimese viie astme jada lihtsalt sellepärast, et see on viie elemendi ja rangelt väikseima võimaliku väärtusega ülivinge järjestus (vältides seega avalikus võtmes 0-d, mis triviaalselt annaks vaste 0-le korrespondent)

Nagu me varem ütlesime, peavad $ alpha = a + bi $ jaoks täisarvud $ a $ ja $ b $ olema ühisrahvuses ning vastavalt mainitud uuele piirangule peame taotlema, et $ a ^ 2 + b ^ 2 = vert alpha vert ^ 2 geq W $. Kiire arvutus annab $ W = $ 1590. Arvestades, et $ sqrt {1590} simeq 39.8 $, oleks väga mugav valida $ alpha $ $ alpha = 39 + 40i $, kuna see on piisavalt suur, et mahutada isomorfismi vähemalt täisarvude ringiga 1590 komponenti, rahuldades samas ka $ gcd (a, b) = 1 $. Samuti peame valima $ theta $ nii, et $ gcd (a, theta) = 1 $ ^[5] ja soovitavalt mitte liiga madal, nii et $ (a_1 * theta) \% alpha neq v_1 * theta $, (ka teabe edastamise vältimiseks). $ theta = 60 $ teeb seda tööd, tootes:

-19-1i dollarit, 1 + 38i, 3-3i, 6-6i, 12-12i dollarit ^[6]

Laseme siis käed määrduda. Võtke teade b. Kõigepealt kaardistame selle baidimassiivi vastavalt [ASCII] (https://et.wikipedia.org/wiki/ASCII#8-bit_codes) ja meie andmeplokkide kärpimise kokkuleppele:

Hola ApeeScape!

Kuna meie andmeblokk on 16 bitti = 2 baiti pikk ja sõnum on 13 tähemärki pikk, siis jõuame lõpuks 7 2-baidise andmeplokini, kus viimane sisaldab kaks korda bitimärki '!'. Krüpteerime esimese ploki samm-sammult. Pöörake tähelepanu, sest iga baidi bitid võetakse nende tähtsuse järjekorras.

$ m = 01001000 01100101 $

• Esimese baidi esimene hammustus: $ (0,0,0,1) parempoolne (1,1,1,1,2) cdot (-19-1i, 1 + 38i, 3-3i, 6-6i, 12 -12i) = 15 + 4i $
• Esimese baidi teine ​​näks: $ (0,0,1,0) parempoolne (1,1,1,2,1) cdot (1 + 38i, 3-3i, 6-6i, 12-12i, 15 + 4) = 49 + 9i $
• Esimese baidi esimene hammustus: $ (0,1,0,0) paremnool (1,1,2,1,2) cdot (3-3i, 6-6i, 12-12i, 15 + 4i, 49 + 9i) = 106-10i $
• Segundo nibble del praimeri bait: $ (0,1,1,0) rightarrow (1,1,2,2,1) cdot (6-6i, 12-12i, 15 + 4i, 49 + 9i, 106- 10i) = 252-2i $

Ja nii me lihtsalt kaardistasime

node.js: serveripoolne

'Ta' $ Rightarrow (12-12i, 15 + 4i, 49 + 9i, 106-10i, 252-2i) $

Ülejäänud krüptitud kiri on järgmine:

“Ll” $ Rightarrow (12-12i, 21-2i, 61-3i, 185-31i, 367-59i) $

“O” $ Rightarrow (12-12i, 25 + 33i, 65 + 32i, 111 + 44i, 244 + 124i) $

„Sihtmärk” $ Rightarrow (12-12i, 9 + 10i, 46 + 12i, 149 + 5i, 277 + 31i) $

“Pt” $ Rightarrow (12-12i, 3 + 16i, 46 + 12i, 73 + 23i, 201 + 49i) $

'Al' $ Rightarrow (12-12i, 4 + 54i, 44 + 53i, 117 + 193i, 231 + 389i) $

'!!' $ Rightarrow (12-12i, 4 + 54i, 32 + 65i, 63 + 92i, 121 + 247i) $

Dekrüptimiseks on meil $ theta ^ {- 1} = 60 ^ {- 1} = 27 + i $:

$ ($ ”He” $ Rightarrow) $ $ (12-12i, 15 + 4i, 49 + 9i, 106-10i, 252-2i) * teeta ^ {- 1} \% alpha = (16,47 , 93 223 527)

Nüüd tuleb ahne algoritm:

Esiteks lahutasime kõik soodustegurid, mis korrutati ühega, sest on teada, et nad panustasid viimasesse vähemalt üks kord, mille tulemuseks oli:

• Teise baidi teine ​​näks:

$ T vasak vasak (527-233-93-47-16) = 148 $

$ (T geq 223) = (148 geq 223) = vale Rightarrow b_1 = 0; T vasakpoolne nool (T - 0 * 223) = 148 $

$ (T geq 93) = (148 geq 93) = true Rightarrow b_2 = 1; T vasakpoolne nool (T - 1 * 93) = 55 $

$ (T geq 47) = 55 geq 47) = true parempoolne b_3 = 1; T vasakpoolne nool (T - 1 * 47) = 8 $

$ (T geq 16) = 8 geq 16) = vale Rightarrow b_4 = 0; T vasakpoolne nool (T - 0 * 16) = 8 $

Tulemus: 0110;

Ülejäänud: 8 (lisatakse jada algusesse uue madalaima elemendina);

Eemaldage 527 praeguse järjestuse lõpust;

• Teise baidi esimene hammustus:

$ T vasak vasak (233-93-47-16-8) = 59 $

$ (T geq 93) = (59 geq 93) = vale Rightarrow b_1 = 0; T vasakpoolne nool (T - 0 * 93) = 59 $

$ (T geq 47) = (59 geq 47) = true Rightarrow b_2 = 1; T vasakpoolne nool (T - 1 * 47) = 12 $

$ (T geq 16) = (12 geq 16) = vale Rightarrow b_3 = 0; T vasak vasak (T - 0 8 16) = 12 $

$ (T geq 8) = (12 geq 8) = true Rightarrow b_4 = 1; T vasakpoolne nool (T - 0 * 12) = 4 $

Tulemus: 0101;

Ülejäänud: 4 (lisatakse jada algusesse uue madalaima elemendina);

kuidas programmeerimiskeelt luua

Jätke praeguse jada lõpust 233;

• Esimese baidi teine ​​näks:

$ T vasakpoolne nool (93 - 47 - 16 - 8 - 4) = 18 $

$ (T geq 47) = (18 geq 47) = vale Rightarrow b_1 = 0; T vasakpoolne nool (T - 0 * 47) = 18 $

$ (T geq 16) = (18 geq 16) = true Rightarrow b_2 = 1; T vasakpoolne nool (T - 1 * 16) = 2 $

$ (T geq 8) = (2 geq 8) = vale Parempoolne b_3 = 0; T vasakpoolne nool (T - 0 * 8) = 2 $

$ (T geq 4) = (2 geq 4) = vale Rightarrow b_4 = 0; T vasakpoolne nool (T - 0 * 4) = 2 $

Tulemus: 0100;

Jäänuk: 2 (lisatakse jada algusesse uue madalaima elemendina);

Tilk 93 praeguse järjestuse lõpust;

• Esimese baidi esimene hammustus:

$ T vasakpoolne nool (47-16-8-4-2) = 17 $

$ (T geq 16) = (17 geq 16) = true Rightarrow b_1 = 1; T vasakpoolne nool (T - 1 * 16) = 1 $

$ (T geq 8) = (1 geq 8) = vale Rightarrow b_2 = 0; T vasakpoolne nool (T - 0 * 8) = 1 $

$ (T geq 4) = (1 geq 4) = vale Rightarrow b_3 = 0; T vasakpoolne nool (T - 0 * 4) = 1 $

$ (T geq 2) = (1 geq 4) = vale Rightarrow b_4 = 0; T vasakpoolne nool (T - 0 * 2) = 1 $

Tulemus: 1000;

Puhkus: 1 (lisatakse jada algusesse uue madalaima elemendina);

Kustuta praeguse järjestuse lõpust 47;

Selle tulemusena oleme leidnud andmeploki: “01001000 01100101”, mis sisaldab meie sõnumi kahte esimest märki “He”. Vähe sellest, oleme edukalt hankinud ka meie $ (1,2,4,8,16) $ privaatse võtme üliodava järjestuse.

Teised andmeplokkide kaardid lähevad samamoodi.

---

Võrdlus peamise avaliku võtme krüptosüsteemidega

SRVB on:

1. Täiesti tasuta ja avalik;

2. Oluliselt lihtsam ja hõlpsam mõista ning rakendada kui JNE ^[7] ;

3. Võtmetes rohkesti ja seetõttu praktiliselt ei maksa, vastupidiselt näiteks RSA , mis põhineb algarvudel, mis on kallid .

Nüüd võime kokku võtta kõige tõenäolisemad haavatavused. Kuna SRVB pärineb MH-st, on lihtne kahtlustada, et see oleks [Shamiri rünnaku] üldistuse suhtes haavatav (https://en.wikipedia.org/wiki/Merkle-Hellman_knapsack_cryptosystem#cite_note-2) või mõnda autoril oli põhjust arvata, et see nii ei ole, seda tuleb veel kinnitada (mis on krüptosüsteemide puhul väga tüüpiline).

---

Mis järgmiseks?

Rocha märkis kasutatavate jagamisrõngaste osas mõned üldistused, mis võivad viia krüptanalüüsi keerukuse suurenemiseni. Uurime ka neid võimalusi.

Lineaarne algebraline varjutus

Nii juhtub, et SRVB väljatöötamise ja dokumenteerimise käigus pakkus Villas Boas välja uue lähenemisviisi avaliku võtme seljakoti krüptosüsteemi kontseptsiooni täiustamiseks, mida selles dokumendis üksikasjalikult ei selgitata, et see artikkel ei oleks liiga pikk. ja tüütu, aga siin on sellega pintsel. Kui te ei saa sellest aru, ärge muretsege, jääge lihtsalt meie järgmise artikli postitamise juurde, kus me läheme üksikasjadesse täpsemalt: vaadake näiteks $ N $ summat $ ja $ alamhulka jagamise $ u_i $ rõnga elemendid (mis isomorfselt vastavad super suureneva järjestuse positiivsetele täisarvudele $ v_i $, nagu varem) nende $ u_i $ reavektori korrutisena veeruvektoriga $ B $ (binaarse ) nullist ja ühest ^[8] .

$ y = sum_ {i = 1} ^ n u_i b_i = (u_1, cdot cdot cdot, u_n) ^ T cdot (b_1, cdot cdot cdot, b_n) $ = UB,

kus $ b_i {0,1} $

Kujutage nüüd ette, et selle $ u_i $ vektori asemel on teil vasakul maatriks V $ n $ korda $ N $ (koos $ n [9] n vasakul maatriksi R järgi, määrates n maatriksi P järgi:

P = RV

Idee on selles, et Bob kasutab P-d oma uue avaliku võtmena. R-i juhuslikkuse tõttu on vektor

$ Y = PB = RV B = RW $

kas teave $ w $ on varjatud müra abil teistes V ridades. Samuti arvutab Bob ette ja salvestab reavektori S, mis vastab:

$ R ^ T S ^ T = e_1 $

Kui Alice saadab Y Bobile, leiab ta SY, kuna:

$ SY = S (PB) = S ((RV) B) = SRVB = {e_1} ^ T R ^ {- 1} ((RV) B) = $

(siiani ainult määratlused)

kuidas mõõta investeeringutasuvust

$ {e_1} ^ T (V B) = {e_1} ^ T W = w $

(Nüüd, kasutades ära assotsiatiivsus R-de tühistamiseks)

ja seejärel jätkake nagu varem, et ekstraheerida $ b_i $ vektor vektorist $ w $ ahne algoritmi abil.

Nii et ühesõnaga kasutab lineaaralgebraline varjatus maatriksi korrutamise assotsiatiivsust (asjaolu, et saaksime termineid laiendada ja seejärel nende komponente uues järjekorras opereerida, kui me hoiame kõigi operandide jada järjestuses) segage lineaarselt ja filtreerige müra väärtusele $ w $ (vastavalt krüpteerimisel ja dekrüpteerimisel). Ja piiraval juhul $ n = 1 $ naaseb süsteem elegantselt Rocha lähenemisviisi järgi originaali juurde.

SRVB kampaania: tänuväärne väljakutse

Nagu eespool selgitatud, näitab Kerckhoffi põhimõtte kohaselt kogemus, et avalikult tuntud katkematu krüptosüsteemi iidsus on sama usaldusväärsuse peamine allikas, palju rohkem kui autorite endi teoreetiline argumentatsioon, välja arvatud mis tahes muu asi, sest lõplik tõendeid algoritmide tõhususe kohta üldiselt pole.

Ja siin on meil suurepärane võimalus neid ideid praktikas rakendada, et võita suurepärane auhind: teades seda fakti, käivitasime programmi mainitud kampaania , mis on põhimõtteliselt ühisrahastus. auhinna eest, mis antakse automaatselt esimesele, kes sõnumit murrab. Raha teisendatakse antud rahakoti bitcoinideks, mille privaatne võti krüpteeritakse ja avaldatakse SRVB-s, nii et igaüks, kes seda suudab dekrüpteerida, võib raha lihtsalt anonüümselt võtta ja küsimusi ei esitata.

Aitäh

See konkreetne artikkel ja kogu SRVB krüptoprojekt üldiselt on saanud suurt abi prof. Charles F. de Barros , [São João Del Rei föderaalse ülikooli] dotsent (http://www.ufsj.edu.br/). Prof Barros andis meile tehnilise ülevaate SRVB krüptosüsteemist endast. Ma uskusin, et see on vaja esitada enne, kui julgen avaldada, ja et mul läheb selle iseseisvalt tegelemiseks kindlasti palju kauem aega.

Lisaks tahaksin avaldada õpetajale ka sügavat tänu Adnan Ademovic erakordselt läbimõeldud, tähelepaneliku ja kannatliku töö eest selle väljaande toimetajana. Artikkel.

---

Sõnastik

1. Krüptoloogia / krüptograafia: Teadus / praktika, mis muudab sõnumi peaaegu võimatuks tõlgendada ilma konkreetse juhiste komplektita (antud kontekstis nn 'võti'), võimaldades neid juhiseid jagavatel agentidel turvaliselt suhelda, isegi kui kolmandad osapooled neid kinni peavad;
2. Steganograafia: Teadus / praktika ühe sõnumi varjamiseks teise sees, lisades viimasele näiliselt kahjutuid modifikatsioone;
3. Võtmete genereerimine: juhuslike (eeldatavate) sisendite kaardistamine kehtivatele (juhuslikele) võtmetele;
4. Krüpteerimine / kodeerimine: Ühe hõlpsasti tõlgendatava sõnumi hõlpsasti arvutatav kaardistamine teise, mida on keeruline või võimatu tõlgendada, kasutades elementi (nagu juhuslikult määratletud) see, mis vastab võtmele (vastavalt Kerckhoffsi põhimõttele) tuntud ja avalikult kinnitatud) algoritmide perekonnast;
5. Dekrüpteerimine / dekodeerimine: Kergesti arvutatava kaardistamise, mis koosneb ülaltoodud pöördvõimalustest, saab määratleda ka elemendiga (mis on juhuslikult määratletud ja seetõttu kolmandate isikute poolt teadmata ja raskesti aimatav) _once, mis vastab a-klahvile_ (samal põhimõttel , üldtuntud) algoritmide perekond, mis väljastab sel viisil algse sõnumi, kui see krüptimisega sisestatakse;
6. Krüptosüsteem: Triaad kodeerimisalgoritmide perekonnast, vastavate dekrüpteerimisalgoritmide perekond ja võtmete genereerimise algoritm;
7. Liitlased: Agentid, kellele suhtlus on mõeldud ja kellelt oodatakse käitumist vastavalt protokolli reeglitele;
8. Vaenlased / kolmandad isikud: Agendid, kellega suhtlemine pole mõeldud, kuid üritavad sellest hoolimata suhtlust nuhkida ja krüptosüsteemi poolt tugevdatud turvalisusest mööda hiilida;
9. Ohutu kanal: Mis tahes suhtlusprotokoll (protseduur), mida on lihtne kasutada ja mis samal ajal takistab kolmandatel osapooltel tõlgendada elujõulisel viisil seda, mida nende kasutajad mõtlevad.
10. Pole turvaline kanal: mis tahes kanal (see tähendab protokoll või protseduur), mis, nagu nimigi ütleb, ei ole turvaline kanal;
11. Võtme murdmine: Võtme avastamise protsess avaliku võtme (nt krüpteeritud sõnumi või avaliku võtme) abil, mis ei hõlma võtme enda kasutamist ja mis eeldatavasti ei võimalda võtit leida. Kuna selle protsessi tulemusel saadud teave võimaldab sõnumite dekrüpteerimist, on see konkreetne juhtum ...
12. Sõnumi rikkumine / dekrüpteerimine: Mis tahes viis krüpteeritud sõnumi algse sisu tuletamiseks ainult krüpteeritud sõnumi enda ja muu teabe abil, millest ei peetud originaalsisu mahaarvamiseks piisavat;
13. Krüptosüsteemi purustamine: Selle meetodi abil krüpteeritud sõnumi mis tahes parameetri abil võimaliku katkestamise süsteemse viisi avastamine;
14. Põhimõte / Desideratum / Axiom / Kerckhoffsi seadus: Hollandi krüptograafi nime kandev krüptoloogiline põhimõte. Auguste Kerckhoffs , mille kohaselt peab krüptosüsteemi turvaliseks pidamiseks kõik sellega seonduv, välja arvatud selle (isiklikud) võtmed, olema avalikud teadmised;
15. Võti: Krüptosüsteemi salajane parameetrite määramine, mis võimaldab seda tahtmatult (ja sellest tulenevalt katkestada) kolmandate osapoolte poolt, samal ajal kui krüptanalüütikute kogukond seda ka kinnitab (vastavalt Kerckhoffi põhimõttele);
16. Sümmeetriline krüptosüsteem: Kõik krüptosüsteemid, milles kodeerimiseks on piisav mis tahes parameetri jaoks, et dekodeerimiseks parameeter hõlpsasti tuletada, tuleks seetõttu hoida privaatsena. Võib selle ümber sõnastada, öeldes, et krüptimise ja dekrüpteerimise parameetrid on mõlemad võtmega samaväärsed;
17. Krüptosüsteemi sümmeetria / avalik võti: Mis tahes krüptosüsteem, mille jaoks on olemas kodeerimise parameetrite väljendamise viis, mis ei ole piisav vastava dekodeerimise parameetri tuletamiseks, võimaldades seda ebaturvalise kanali kaudu liitlastele saata või isegi avalikustada jne. turvaline kanalikeskkond, kus seda polnud;
18. Avalik võti: Asümmeetrilise krüptosüsteemi komponent, mis on krüpteerimise parameetrite määramiseks piisav, kuid pole piisav dekrüpteerimisparameetri realiseerimiseks, st ...
19. Privaatne võti: Asümmeetrilise krüptosüsteemi komponent, millest piisab dekrüpteerimise parameetriks ning seetõttu tuleb neid hoida privaatsena ja tavaliselt piisab ka krüptimise parameetriseerimisest;

---

^[üks] Pange tähele, et siin olevad fraasid dešifreerida või dešifreerida ei kehti, sest enne, kui antud krüptosüsteem (koos kõigi komponentide, sealhulgas võtmetega) on täpselt määratletud, ei saa klassifitseerida antud meetodit krüptimise algse sõnumi tõlgendamiseks tahtlikuks suhtluseks (dekrüpteerimine) või rünnakuks (dekodeeritud).

^[2] Kuigi selle ennustamistöö parandamiseks on olemas tehnikaid, on seda siiski palju raskem avastada kui nende paljundamist.

^[3] Esimene inspiratsioon oli vaadata tau oletuste puu , lõpmatu puu, mille juured on arvul 1 ja mille teised sõlmed koosnevad täisarvudest, mille tulemuseks on eelmiste sõlmede liitmise, lahutamise või korrutamise binaaroperatsioon, võib-olla ka ise opereeritud sõlm. Teooria eesmärk on seotud selle puu sügavusega, milles iga täisarv ilmub esmakordselt. Alumistest harudest on ilmselt raske arvukalt leida (isegi kui vajadust leevendame), kuid kohe on vaja kontrollida, kas antud toimingute jada annab tegelikult antud tulemuse.

^[4] See pole kindlasti kõige loomulikum lähenemisviis, kuid selle kasutuselevõtt tagab, et see baitide polsterdus (nn täidis ) ...

1. Peidab polstrimõõdu (erinevalt näiteks šifriteksti vargus ) ja varjab sõnumi lõppu, tähistades valitud tavalise teksti rünnakud keerulisem;
2. Parandage bitijaotust võimalikult ühtlasele lähedale;

Kui oleks teada, et iga teate viimased plokid on süsteemselt kallutatud jaotuses, mis pole kaugeltki ühtlane, võiks ründaja seda fakti statistilise krüptanalüüsi tegemiseks ära kasutada, kuna mis tahes antud sõnumivalim oleks statistiliselt esinduslikum kui vastupidine. Teisisõnu, viimased plokid on statistiliselt vähem erinevad, neist saavad sõnumi kõige nõrgemad lülid.

^[5] Ärge tehke viga: see suurim ühine jagaja on Gaussi, samas kui ülalolev on tõeline.

^[6] … Mis pole täiuslik, sest see paljastab hõlpsasti tõsiasja, et kolm viimast komponenti on proportsioonides 1, 2 ja 4. Kuid lihtsuse huvides jätame selle detaili tähelepanuta.

^[7] ... mis on nii keeruline, et neid on kurikuulsaid juhtumeid, kui sellel põhinevaid protokolle ei juurutata ja hooldada .

^[8] Siinkohal ei käsitle me Rocha lähenemist mitme lineaarse kombinatsiooni plokile, mis võimaldab meil ka pisteliselt juhuslikult permuteerida, et muuta need veelgi tumedamaks.

^[9] Kuigi mitte täiesti juhuslik. Selle ülevõtmine peab hõlmama vektori $ e_1 = (1,0,…, 0) $ loodud alamruumi.