Darbo pradžia su SRVB kriptosistema

Įvadas

Informacijos saugumas yra patraukli žinių sritis, apimanti viską nuo teorinio skaičiavimo iki programinės įrangos inžinerijos ir netgi žmogaus klaidų psichologijos.

Kripto dabar yra vienas iš daugelio anoniminių technologijų herojų mūsų kasdieniame gyvenime. Socialinė žiniasklaida, internetinė bankininkystė, karinė žvalgyba ir bet kuri kita su slapta informacija susijusi informacinė sistema labai priklauso nuo kriptografijos. Kriptografija leidžia mums turėti privatumą, kurį kai kurie mano 12-oji žmogaus teisė .

Šis straipsnis supažindins su viešojo rakto kriptosistemų principais ir su jumis „Santana Rocha-Villas Boas“ (SRVB) , kriptosistema, kurią sukūrė straipsnio autorius ir prof. Daniel Santana Rocha. Rašymo metu algoritmo autoriai rengia kampaniją, į kurią įeina finansinis atlygis tiems, kuriems pavyksta nulaužti kodą. Kadangi straipsnis išsamiai aprašys algoritmo funkcionalumą, tai yra geriausia vieta pradėti prizo paiešką. Daugiau informacijos galite rasti SRVB svetainė .

Kas yra kriptosistema?

Kriptografija yra bet koks būdas užkirsti kelią pranešimo aiškinamumui, kartu suteikiant galimybę ją interpretuoti perspektyviu būdu, jei tik pateikiama konkreti instrukcija, kuri paprastai yra vadinamasis „raktas“. Nors tai labai platus apibrėžimas, apimantis net keletą pirmųjų metodų, verta paminėti, kad tai neapima visko, kas yra informacijos saugumui.

Tikimasi, kad techninės lenktynės tarp šifravimo metodų ir būdų, kaip juos sugadinti, niekada neturės galutinio nugalėtojo. Be to, kiekviena nauja karta pakelia informacijos saugumo ir kriptanalizės standartus, kurie yra metodų rinkinys sistemingai iššifruoti / nutraukti šifruotus pranešimus, tai yra apeiti saugumą ar šifravimą.

Kad vartotojai galėtų manyti, kad kriptosistema (atsižvelgiant į kriptografijos techniką) yra saugi, ji turi turėti tarptautinės ekspertų bendruomenės pritarimą ir todėl būti viešai žinoma, vadinama Kerckhoffs principas . Tačiau būtent dėl ​​šios sąlygos sistema gali būti tikrinama iš pasaulinės kriptanalizės bendruomenės, kuri bandys rasti būdus, kaip sistemingai nutraukti šifravimą.

Kaip galite padaryti tam tikrą šifravimo procesą pakankamai slaptą, kad jį sugadinti galėtų tik bandyti agentai, tačiau vis tiek būti pakankamai viešais, kad pasaulinė kriptanalizės bendruomenė galėtų patvirtinti jo tvirtumą? Atsakymas yra komponentas, kuris yra pagrindinis kriptologijos elementas: raktas. Kriptosistemos raktas yra šifravimo ar iššifravimo algoritmų arba abiejų parametras. Laikant slaptus parametrus, o ne algoritmų šeimą, galima pasiekti abu prieštaraujančius reikalavimus. Kol parametrų šeima yra pakankamai didelė (galbūt begalinė) ir gali būti įrodyta, kad kiekviena jos sudedamoji dalis pasižymi tinkamomis savybėmis, užpuolikams nebus įmanoma nustatyti parametrus paprasčiausiai patikrinus.

Galiausiai, norint, kad raktas veiktų efektyviai, jį reikia pagaminti lengvai, bet beveik neįmanoma atspėti. Turint šių dienų kompiuterių skaičiavimo galią, kompiuteriui prireiks mažiau laiko nulaužti žmogaus sugeneruotą raktą, nei kada nors reikėtų įsivaizduoti, be to, tokiu būdu generuoti raktus neapsimoka. Dėl to raktus paprastai generuoja algoritmas.

Raktų generavimo algoritmas neturi sukurti nuspėjamų / atkuriamų rezultatų dėl įprasto naudojimo. Kadangi algoritmai atlieka procedūras be jokių intelektualių procesų, kyla klausimas, kaip tai galima padaryti. Atsakymas yra konvertuoti raktų generavimo algoritmus į žemėlapius, kurie daugybę tikrai atsitiktinių bitų paverčia raktais. Iš operacinės sistemos galima gauti tikrai atsitiktinius bitus, kurie juos generuoja iš visatos netikrumo. Kai kurie šaltiniai būtų pelės judėjimas, tinklo paketų delsos ar net speciali aparatūra, priklausomai nuo programos.

Viešojo rakto kriptosistemos

Pasiruoškite dar kartą nustebti, nes dabar pristatysime koncepciją, kuri akivaizdžiai prieštarauja ką tik pasakytai: viešasis raktas.

Iki šiol matėme saugaus ryšio sukūrimą po to, kai buvo saugiai apsikeista slaptais parametrais (raktais), tačiau parametrų keitimo viešuoju kanalu problema išlieka. Šiuo metu pristatysime koncepciją, kuri išspręs šiek tiek labiau apčiuopiamą problemą: saugaus kanalo sukūrimas.

Tarkime, Alisa dirba su Bobu, ir jie nori, kad jų sąveika būtų saugi šifruojant. Šifravimo raktus jie gali rasti ir jais pasikeisti perduodami USB atmintinę su savo raktais. Bet ką daryti, jei Alisa ir Bobas yra skirtinguose žemynuose? Kaip sukurti saugų kanalą ten, kur jo nėra?

Raktų siuntimas el. Paštu nebūtų pasirinkimas, nes jo konkurentė Ieva gali perimti mainus ir naudoti savo raktus vėliau perskaityti visus užšifruotus duomenis. Jei jie turėtų kitą skaitmeninį kanalą, kuriuo galėtų perduoti šią neskelbtiną informaciją, jiems visų pirma nereikėtų šifravimo ir todėl raktų. Rakto siuntimas fiziniu paštu taip pat galėtų būti sulaikytas, nes pirmiausia reikia keistis konfidencialia informacija. Atsiųskite vieną nukopijuotas raktas, slepiantis kituose duomenyse tai būtų protinga, bet nenaudinga, nebent siuntėjas yra tikras, kad gavėjas ir tik gavėjas žino apie tokios žinutės egzistavimą ir žino, kaip ją išgauti. Taip atsitinka, kad žinojimas apie pranešimo egzistavimą kartu su aprašymu, kaip raktą išgauti iš duomenų, yra pats rakto tipas, atvedantis mus į pradinį tašką.

Sprendimas yra sukurti kriptosistemą, kuriai šifravimo parametro nepakanka, kad būtų galima tinkamai interpretuoti pradinį pranešimą. ^[vienas] ir išsaugo jums parametrą, kuris leistų interpretuoti pranešimą. Mes tą parametrą vadiname privačiu raktu. Remiantis privačiu raktu, galima tinkamai sukurti parametrų rinkinį šifravimo įrankiui, nepriversiant tų naujų parametrų atskleisti, kas yra privatus raktas. Tas parametrų rinkinys gali būti viešai naudojamas, nes nėra taip svarbu, kas gali kažką užšifruoti, jei tik vienas asmuo gali jį iššifruoti. Kadangi šis šifravimo įrankio parametrų rinkinys gali būti viešas, jis vadinamas viešuoju raktu.

Kriptografija, kai šifravimo ir iššifravimo raktai skiriasi, o pirmųjų negalima panaudoti išvedant antruosius, vadinama asimetrine kriptografija, tuo tarpu simetriška kriptografija yra tai, ką turime, kai tie raktai yra vienodi arba lengvai vienas iš kito daromi išvados. Alisa siunčia Bobui savo viešąjį raktą, kurį galima naudoti tik šifruojant dalykus, kuriuos iššifruoti gali tik ji (su savo privačiu raktu, kurį ji saugo), ir, atvirkščiai, Bobas siunčia Alisai savo viešąjį raktą, kurį galima naudoti tik šifruojant daiktus kad iššifruoti gali tik jis (naudodamas savo privatųjį raktą, kurį jis taip pat saugo). Bet kaip galite paskelbti šifravimo algoritmo parametrą, iš kurio negalima nustatyti tikslaus atvirkštinio algoritmo?

Atsakymas slypi matematikos srityje, labiau susijusioje su programavimu, skaičiavimo sudėtingumo teorija . Kiekvienas, kuris pakankamai įsigilino į matematikos užduotis, yra girdėjęs apie transformacijas, kurias lengva atlikti vienaip, bet sunku atvirkščiai. Pavyzdžiui, skaičiuojant vadovėlio darinio suradimas paprastai yra paprastas pratimas, atliekant atvirkštinį (pvz., Išsprendžiant bet kurią fizinę dalį ar šiek tiek ne trivialų fizinį vadovėlį). ODE arba PDE , pvz.) reikalingas labiau tiriamas pirmosios hipotezės apie funkcijų šeimas, kurios yra garantuotos (arba bent jau tikėtinos), kad būtų sprendimas (-ai) ir išspręstos atvirkštinės problemos, kad būtų galima rasti šių šeimų sprendimus.

Pavyzdys, kuris iš tikrųjų naudojamas RSA kriptosistema daugina puikius pradus, o ne faktoriuoja gautą produktą, nežinodamas veiksnių. Dauginimas yra nereikšmingas, tačiau faktoringas reikalauja, kad pasirinktumėte atsitiktinai ^[2] atspėkite pagrindinius veiksnius, kurie turi šimtus skaitmenų. Svarbi operacijos savybė yra būtinybė gerai mastelėti. Pridėjus kelis skaitmenis virš pirminių skaičių RSA, bus gautas raktas, kuriam iššifruoti ir šiek tiek padidėti šifravimo proceso sudėtingumas reikalauja dar tūkstančių operacijų. Paprastai kalbant, pirminių skaičių sandauga naudojama šifravimui, o pirminių veiksnių pora naudojama iššifravimui.

Turėdami visa tai omenyje, pažvelkime į tai, kaip veikia SRVB kriptografinė sistema.

Pagrindinis algoritmas: išnagrinėkite SRVB

Pogrupio sumos problema

Kaip ir bet kuri kita viešojo rakto kriptosistema, SRVB remiasi sunkumu išspręsti tam tikrą problemą, kurią lengva sukurti. SRVB atveju tai yra Pogrupio sumos problema , kurį galima apibūdinti taip:

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

Aišku, ši problema gali kilti atsitiktinai pasirinkus N sveikus skaičius, atsitiktinai pasirinkus jų pogrupį ir apibendrinus šį pogrupį, kuris yra trivialus.

Žiaurios jėgos paieškos sudėtingumas būtų $ O (N * 2 ^ N) $, apskaičiuojant kiekvieną $ b $ s verčių derinį. Efektyvesnį požiūrį suteikė Horowitzas ir Sahni 1972 m , kurio sudėtingumas yra $ O (N * 2N / 2). Problema yra bent jau tokia pat sunki, jei pakeisime $ b $ s ir $ w $ į $ k $ - sveikųjų skaičių matmenų vektorius. Tačiau apimtys, kuriose turi būti vykdoma ši sunkesnė problema, taip pat turi turėti izomorfizmas su [žiedu] (https://en.wikipedia.org / wiki / Ring_ (math)), kur atliekama lengvesnė tos pačios problemos versija, kaip pamatysime toliau. Dėl šios priežasties SRVB išnaudoja pogrupio sumos problemą Gauso sveikieji skaičiai , kur $ k = 2 $ ..

Yra specialus atvejis, kai šią problemą lengva apskaičiuoti naudojant godų algoritmą. Jei užsakysime skalės koeficientų seką $ v_1, cdot cdot cdot, v_N $, kurioje kiekvienas eilės skaičius yra didesnis už visų prieš tai buvusių sveikųjų skaičių sumą ($ forall i, sum_ {j = 1} per didelė didinimo seka .

Čia yra paprastas godaus šio atvejo sprendimo aprašymas:

1. Jis prasideda nuo $ i = N $, šiuo metu stebimo faktoriaus, ir nuo $ w ’= w $, likusios iš $ w $

2. Jei dabartinis mastelio koeficientas yra per didelis, kad tilptų į likusią $ w $ dalį, tai reiškia, kad $ v_i> w '$, nustatykite $ b_i = 0 $ ir tęskite kitą žingsnį. Priešingu atveju mes žinome, kad mastelio koeficientas turi būti seka (nes likę veiksniai yra mažesni nei $ v_i $), todėl mes įdėjome $ b_i = 1 $.

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

4. Patikrinkite, dabar $ w '== 0 $, kitaip problema sugadinta.

Tai veikia, nes mes žinome, kad visi daugikliai, mažesni už šiuo metu stebimą, negali bendrai padengti tiek (pogrupio) sumos $ w '$, kiek dabartinis daugiklis. Taigi, jei likusi suma yra didesnė už dabartinį koeficientą, mes tikrai žinome, kad visų šių veiksnių kartu nebus galima susumuoti be dabartinio veiksnio pagalbos. Kita vertus, kadangi visi daugikliai yra teigiami, jei dabartinis koeficientas $ v_i $ yra didesnis už likusią sumą $ w '$, pridėjus bet kurį kitą veiksnį, rezultatas dar labiau viršytų $ w' $.

Mes sukursime anotaciją likusiam straipsniui. Mes pasirenkame $ v_1, cdot cdot cdot, v_n $ ir $ w $ kaip veiksnius ir pridėtinės sekos sumą, o $ u_1, cdot cdot cdot, u_n $ ir $ y $ bus viešai prieinami parametrai, kurie pateikiami norint gauti $ b_1, cdot cdot cdot, b_n $.

Pasirinkus seką $ u_1, cdot cdot cdot, u_n $, kad nebūtų labai nuostabu, o skaičius $ y $ yra viešai prieinamas, nėra pakankamai informacijos, kad būtų galima gauti seką $ b_1, cdot cdot cdot, b_n $. Tačiau, jei yra super nuostabi seka $ v_1, cdot cdot cdot, v_n $, kuri galėtų užimti sekos $ u_1, cdot cdot cdot, u_n $ vietą, šią seką būtų galima naudoti norint išspręsti godaus požiūrio problema.

Parodysime, kaip tai veikia toliau.

Pogrupių sumų naudojimas senesnėje kriptosistemoje

Į 1978 m., Ralfas Merkle ir Martinas Helmanas , jie sugalvojo išnaudoti tas dvi kuprinių paradigmas ir tiesiškumas modulio operacijos, kad būtų sukurtas ryšys tarp dviejų sekų, aprašytų ankstesniame skyriuje, taip sukuriant viešojo rakto kriptosistemą. Idėja buvo pakeisti lengva kuprinė (tas, kuris susideda iš super didėjančio sveikųjų skaičių vektoriaus) kietajame (tame, kuriame trūksta šios savybės) naudojant linijinę operaciją (modulį) su slaptais operandais. Transformacija susideda iš kiekvieno $ v_i $ padauginimo iš $ theta $ ir likusio šio produkto paėmimo iš $ alfa $, kur $ alpha gt sum_ {i = 1} ^ N v_i $ ir $ gcd ( alpha, theta) = 1 $ (du apribojimai, kurie netrukus bus pagrįsti). Rezultatas, seka $ u_1, ldots, u_N $, nebeauga ir gali būti laikoma a sunki kuprinė .

Atsitiktinis sekos $ u_1, ldots, u_N $ permutavimas bus suteiktas šaliai, norinčiai užšifruoti ir atsiųsti mums pranešimą. Permutacija atliekama taip, kad trečiajai šaliai sunku atspėti, kokia yra pirminė padidinimo seka. Pranešimo bitų blokai naudojami kaip koeficientai $ b_1, ldots, b_N $. Šifravimas atliekamas padauginus raktų seką iš šios koeficientų sekos ir pridedant daugybos rezultatą, kurį turime pažymėti $ ir $. Tik privataus rakto savininkas gali pakeisti $ y $ į atitinkamą $ w $, kuris būtų gautas, jei tie patys $ b_1, ldots, b_N $ blokai būtų padauginti iš paprasti sveikieji skaičiai (seka $ v_1, ldots, v_N $). Tai daroma padauginus $ y $ iš $ theta ^ {- 1} $, atvirkštinis daugiklis iš $ theta $ modulio $ alpha $ (kurio egzistavimas priklauso nuo tos $ gcd ( alpha, theta) = 1 $ sąlygos). Kitaip tariant, $ ( theta * theta ^ {- 1}) bmod alpha = 1 $. Po to apskaičiuojame $ w = (y * theta ^ {- 1}) bmod a $. Priežastis, kodėl tai garantuotai veiks, yra modulio tiesiškumas , tai yra likutinis linijinis derinys yra lygus likusiai linijinei kombinacijai.

Jei nuosekliai taikysime $ u $ apibrėžimą, koeficiento žiedą ir modulio operatoriaus tiesiškumo savybę, matysime atitikimą:

$ 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 & = kairė [ sum_ {i = 1} ^ N b_i * v_i right] * theta bmod alfa newline & = w * theta bmod alfa end {align} $

Ir taip lengva suma $ w $ galima gauti padauginus abi puses iš $ theta ^ {- 1} $ ir imant modulį su $ alpha $. Norėdami tai padaryti, turite žinoti ir $ alpha $, ir $ theta $ (kurie leidžia lengvai apskaičiuoti $ theta ^ {- 1} $), kurie turi būti privatūs kaip privataus rakto dalys.

Vienintelis suvaržymas - $ alpha gt sum_ {i = 1} ^ N v_i $ - nebuvo pagrįstas ir pateikiamas paaiškinimas: antrosios ir trečiosios eilutės lygybę sudaro lygybė tarp atliekų rūšys iš dalinamasis žiedas iš sveikųjų skaičių modulo $ alpha $. Kitaip tariant, tai tik nustato likusių narių lygybę dalijant iš $ alpha $, o tai nėra pakankama narių lygybės sąlyga . Dėl to daugiau nei vienas $ b $ verčių vektorius galėjo būti susietas su vienu $ y $, to galima išvengti apribojant $ w $ bet kokiam $ b $ verčių deriniui, kad jis būtų mažesnis nei $ alfa $.

Kaip ir bet kurio kito kasdienio gyvenimo atvejo, visapusiškai žinoti visų hipotezių yra neįmanoma ir niekada lengva. Todėl mes turime pasikliauti matematine intuicija spręsdami, ar kriptografinė sistema yra saugi naudoti, o tai nesuteikia mums realių garantijų. Praėjus šešeriems metams po jos sukūrimo, MH kriptosistema nutrūko a ataka pateikė A. Šamiras . Buvo dar keli bandymai atgaivinti MH, kurių daugelis taip pat nepavyko.

„Santana Rocha“ kriptosistema - „Villas Boas“ (SRVB)

2016 m., Po kai kurių minčių su šio straipsnio autoriumi apie ^[3] Įkvėptos kriptosistemos galimybės, Danieliui Santanai Rocha kilo mintis Gauso sveikaisiais skaičiais pakeisti $ theta $ ir $ alpha $. Dėl techninių priežasčių šis požiūris sukelia pasipriešinimą minėtam Šamiro išpuoliui.

Jis taip pat sumanė bitų bloką, susidedantį iš daugelio anksčiau aprašyto tiesinio a derinio žingsnių napa dura . Kiekviename iš jų sekos pabaigoje būtų pridėtas naujas sveikasis skaičius (Gauso), lygus vienetui, didesnis už visų ankstesnių skaičių, tuo tarpu mažiausias skaičius būtų pašalintas.

$ Alpha $, kuris dabar yra Gauso sveikasis skaičius, taikomas kitoks, bet elegantiškai analogiškas apribojimas. Mes reikalaujame $ w leq vert alpha vert ^ 2 $, kur $ w $ vėlgi yra didžiausias tiesinių natūralių sveikųjų skaičių derinys lengvoje kuprinėje. Priežastį labai sunku įforminti, tačiau, laimei, ją galima lengvai atspėti iš elegantiško aprašymo:

Įsivaizduokite kompleksinio skaičiaus plokštumos kvadratinę gardelę, kurios kraštas yra stačiojo trikampio taškas kojos a ir b, lygiagrečios tikrosioms ir įsivaizduojamosioms ašims. Tokios grotelės pavyzdys pateiktas žemiau. Gvajaus sveikieji skaičiai modulo $ alpha = a + bi $ gali būti pavaizduoti taškais, esančiais minėtoje gardelėje. Šiame tinkle yra $ vert alpha vert ^ 2 $ skirtingų taškų. Jei pasirenkame pakankamai didelę $ alpha $, galime pritaikyti visus linijinius lengvos kuprinės derinius. Taigi mes nustatome reikalavimą $ w leftarrow vert alpha vert ^ 2 $, kur w yra [kaip aprašyta].

Tai grafinis izomorfizmo $ f vaizdas: Z / n dešiniarankis Z [i] / ( alpha) $, kur $ n = 13 $ ir $ alpha = a + bi = 3 + 2i $ (atkreipkite dėmesį, kad $ n $ ir $ alpha $ iš tikrųjų tenkina $ n = vert alpha vert ^ 2 = a ^ 2 + b ^ 2 $, kaip reikalaujama). Taškai žymi Gauso sveikuosius skaičius, tai yra kompleksinius skaičius $ a + bi $, kur $ a $ ir $ b $ yra sveiki skaičiai. Kaip įprasta, horizontali ašis rodo tikrąją dalį, o vertikalė - įsivaizduojamą. Todėl taško perkėlimas į dešinę arba į kairę yra lygiavertis +1 ar -1 pridėjimui prie dabartinės jo vertės. Panašiai taško perkėlimas aukštyn arba žemyn prilygsta atitinkamai + i arba -i pridėjimui.

Raudoni taškai atitinka $ 0 bmod ( alfa) $. Be šių, mes taip pat nuspalviname dar 4 taškų poras.

Izomorfizmą $ f $ apibrėžia ciklinės sekos $ elemento $ i $ th transformacija (0,1,2, cdot cdot cdot, 10,11,12,0,1,2, cdot cdot cdot) $ taip pat cikliškos taškų sekos elemento $ i $ th elemente, kuris laikosi šių taisyklių:

1. Pradėkite nuo raudono taško pirmoje eilėje;
2. Laikykitės dešinių horizontalių rodyklių; išskyrus tai
3. Stebėdami rodykles, išimkite seką iš grotelių, ji pasiektų vieną iš ne juodų taškų. Užuot ėjęs į tą tašką, jis peršoka į tą patį spalvų tašką (tai yra, lygiavertį taško modulį $ alpha $) tame pačiame kvadrate; ir, galiausiai
4. Kai šis nejuodas taškas nusidažo raudonai (tai nutinka po to, kai praeina visos kitos spalvos), seka peršoka į viršutinį raudoną tašką, taip iš naujo pradedant ciklą;

Norėdami susieti bent $ Y $ natūralius sveikuosius skaičius, paimkite kvadratą, kurio plotas $ vert alpha vert ^ 2 $ (kur yra $ vert alpha vert = sqrt {a ^ 2 + b ^ 2} $ Pitagoro teorema , matavimas jūsų pusėje) bent jau toks pat aukštas.

Atkreipkite dėmesį, kad kiekvienas „šuolis“ pakeičia eilutės numerį $ r $ į $ r leftarrow (r + b) (mod a + b) $, jei skaičiuojamos eilutės iš viršaus į apačią, ir, lygiaverčiai, į $ r leftarrow ( r + a) (mod a + b) $, jei skaičiuojama iš apačios į viršų. Todėl būtina ir pakankama sąlyga, kad kiekviena eilutė (ir taškas) būtų pereinama tiksliai vieną kartą per kiekvieną ciklą, yra ta, kad šuolių dydis atitiktų eilučių skaičių arba, kitaip tariant, $ gcd (a, a + b) = gcd (b, a + b) = 1 $. Dėl didžiausio bendro daliklio operatoriaus savybių abu yra lygiaverčiai $ gcd (a, b) = 1 $.

Y. S. Villasas Boasas pažymėjo, kad reikia $ a $ ir $ b $ suderinamumo. Norint išsaugoti prieaugį, kiekvienas naujas skaičius, pridėtas prie sekos pabaigos, turi viršyti visų dabartinių skaičių ($ w> sum_ {i = 1} ^ k v_i $). Pastebėjote, kad norint tai pasiekti, jūsų daugybos koeficientai $ b_i $ turi būti bent 1, todėl kiekvieno bito negalima susieti su koeficientais 0 ir 1. Jei koeficientai buvo 0 ir 1, tik sudėtinis blokas skirtas tik vienam patenkintų superpadidėjimą. Dėl šios priežasties 0 ir 1 bitai buvo atitinkamai susieti su dauginimo koeficientais 1 ir 2.

Galiausiai ir ne taip trivialiai: kiekvieno dekodavimo veiksmo metu randamas naujas sveikasis skaičius $ v_1 $ kaip lygties $ b_1 v_1 = v_ {n + 1} - sum_ {i = 2} ^ {n} sprendimas. b_i v_i $, kur visus $ v_i $ ir $ b_i $ žino $ 1

Galutinis techninis sprendimas yra atvejis, kai pranešimo dydis baitais nėra daugiklis iš bloko dydžio. Kitaip tariant, ką daryti su galimais likusiais paskutinio duomenų bloko baitais, kad, gavus duomenų blokus, būtų išsaugoti visi pirminio turinio baitai, bet ne daugiau nei jie? Mes tai išsprendėme pakartodami paskutinį pranešimo baitą vieną kartą. Po šios kopijos seka atsitiktinė seka, kurioje reikalaujama, kad kiekvienas komponentas skirtųsi tik nuo ankstesnio. Todėl, kai gaunami duomenų blokai, paskutinis iš jų arba blogiausiu atveju - prieš paskutinį jis sutrumpinamas paskutinio baito pakartojimo metu. ^[4]