Superökande sekvens

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 18 mars 2018; kontroller kräver 16 redigeringar .

En sekvens kallas superincreasing , vars varje term är större än summan av alla tidigare termer. Mer formellt är en sekvens av positiva heltal superökande om villkoret [1] [2] är uppfyllt : $s_{1},s_{2},\dots$

${\displaystyle \forall n>1\ :\ s_{n}>\summa _{j=1}^{n-1}s_{j))$

Denna klass av sekvenser används flitigt i Merkle-Hellmans ryggsäckskryptosystem .

Det är till exempel superökande, men inte. ${\displaystyle \{1,3,6,13,27,52\))$ ${\displaystyle \{1,3,4,9,15,25\))$

Metoder för att konstruera en superökande sekvens

Antag att vi står inför uppgiften att konstruera en superökande sekvens för ett visst antal objekt . Elementet väljs slumpmässigt från en enhetlig fördelning av naturliga tal över följande segment: . Nästa element väljs enhetligt från segmentet , medlemmen av sekvensen som följer efter det väljs från segmentet , elementet väljs slumpmässigt från segmentet . Uppenbarligen, med sådana fördelningar av sekvensmedlemmarna, kommer supertillväxtvillkoret att vara uppfyllt, eftersom den nedre gränsen för varje segment är exakt lika med summan av alla de högra gränserna för de föregående segmenten ökade med en [3] . Låt oss till exempel konstruera flera superökande sekvenser på det här sättet för : ${\displaystyle \{s_{n}\}_{1}^{N))$ $N$ $s_{1}$ $[1,2^{N}]$ $s_{2}$ $[1\cdot 2^{N}+1,2\cdot 2^{N}]$ $[3\cdot 2^{N}+1,4\cdot 2^{N}]$ $s_{n}$ $[(2^{n-1}-1)\cdot 2^{N}+1,2^{n-1}\cdot 2^{N}]$ $N=5$

n	Linjesegmentet	Exempel 1	Exempel 2	Exempel 3
ett	$[1,32]$	5	tio	32
2	$[33,64]$	56	49	64
3	$[97 128]$	98	113	97
fyra	$[225 256]$	225	225	225
5	$[481 512]$	481	510	493

Konstruktion med ett slumpmässigt valt steg

Om det är slumpmässigt valda nummer, kan de återstående elementen i den superökande sekvensen hittas från olikheten [4] : $h,s_{1}\geq 1$

${\displaystyle s_{n}>h+\sum _{j=1}^{n-1}s_{j))$

Låt , . Då, till exempel, sekvensen uppfyller villkoret och är superökande. $h=10$ $s_{1}=9$ ${\displaystyle \{9,20,52,100,192\))$

Konstruktion baserad på Fibonacci-sekvensen

Varje element i Fibonacci-sekvensen uppfyller relationen: , vars noll och första medlemmar är: . Av detta kan man se att de första medlemmarna i Fibonacci-sekvensen: . Ibland kan du stöta på en generaliserad Fibonacci-sekvens . Detta är en sekvens vars medlemmar uppfyller ekvationens villkor: . Det vill säga, den generaliserade sekvensen erhålls från den klassiska genom att ändra de två första termerna i Fibonacci-sekvensen och behåller principen för bildandet av följande termer. För att konstruera en superökande sekvens används formen av den generaliserade Fibonacci-sekvensen. För att beräkna någon medlem av den superökande sekvensen är det nödvändigt att välja fyra element: två initiala ( och ) och två positiva faktorer ( och ) [5] . ${\displaystyle u_{n+1}=u_{n}+u_{n-1))$ $u_{0}=0,u_{1}=1$ ${\displaystyle \{0,1,1,2,3,5,8,13,21,34,55,89,...\))$ ${\displaystyle u_{n+1}=a\cdot u_{n}+b\cdot u_{n-1))$ ${\displaystyle \{s_{n}\}_{1}^{N))$ ${\displaystyle s_{1))$ $s_{2}$ $a$ $b$

Vi får följande fall:

Sekvensen uppfyller superökningsvillkoret för . $s_{1}<s_{2},a\leq b$
Sekvensen är inte superökande för . $a>b$
För , sekvensen börjar uppfylla supertillväxtvillkoret efter flera iterationer . $s_{1}>s_{2},a\leq b$
För förblir sekvensen superökande. $s_{1}<s_{2},T={a \over b}<0.669$

Låt oss till exempel ta . De första elementen i den resulterande superökande sekvensen är: . $s_{1}=2,s_{2}=3,a=5,b=7$ $\{2,3,5\cdot 3+7\cdot 2,5\cdot 29+7\cdot 3,5\cdot 166+7\cdot 29\}=\{2,3,29,166\}$

Bygger på den befintliga superincreasing-sekvensen

Tillståndet för igenväxt uppfylls av ett antal krafter av . Genom att känna till den superökande sekvensen kan vi konstruera en ny med hjälp av uppsättningen . För implementering är det nödvändigt att tillämpa på uppsättningen av följande operationer [6] : $2$ ${\displaystyle \{s_{n}\}_{1}^{N))$ ${\displaystyle \{s_{n}^{'}\}_{1}^{N))$ $\{1,2,2^{2},...,2^{N-1}\}$ ${\displaystyle \{s_{n}\}_{1}^{N))$

$n=1:\{s_{1}+1,s_{2}+1,s_{3}+2,...,s_{N-1}+2^{N-3},s_ {N}+2^{N-2}}\$

$\ldots$

$n=k:\{s_{1},s_{2},s_{3},...,s_{k}+1,s_{k+1}+1,...,s_{ N-1}+2^{Nk-2},s_{N}+2^{Nk-1}}\$

$...$

$n=N-1:\{s_{1},s_{2},s_{3},...,s_{N-1}+1,s_{N}+1}\$

$n=N:\{s_{1},s_{2},s_{3},...,s_{N-1},s_{N}+1}\$

Detaljerat exempel för en vald superökande sekvens : ${\displaystyle \{3,6,13,27,52,105\))$

	${\displaystyle s_{1))$	$s_{2}$	${\displaystyle s_{3))$	${\displaystyle s_{4))$	$s_{5}$	$s_{6}$
	$3$	$6$	$13$	$27$	$52$	$105$
$n=1$	$3+1=4$	$6+1=7$	$13+2=15$	$27+2^{2}=31$	$52+2^{3}=60$	$105+2^{4}=121$
$n=2$	$4$	$7+1=8$	$15+1=16$	$31+2=33$	$60+2^{2}=64$	$121+2^{3}=129$
$n=3$	$4$	$8$	$16+1=17$	$33+1=34$	$64+2=66$	$129+2^{2}=133$
$n=4$	$4$	$8$	$17$	$34+1=35$	$66+1=67$	$133+2=135$
$n=5$	$4$	$8$	$17$	$35$	$67+1=68$	$135+1=136$
$n=6$	$4$	$8$	$17$	$35$	$68$	$136+1=137$

Vi fick en ny superökande sekvens . ${\displaystyle \{s_{n}^{'}\}_{1}^{N}=\{4,8,17,35,68,137\))$

Användning av den superökande sekvensen i kryptografi

Super-ökande ryggsäckar

Merkle-Hellmans kryptosystem är baserat på "knapsäckproblemet" - en krypteringsalgoritm för offentlig nyckel - som beskrivs nedan. Problemet ser ut så här: givet en sekvens av icke- repeterande positiva heltal. Låt talet också tillhöra mängden naturliga tal. Om detta är möjligt är det nödvändigt att hitta en uppsättning pseudoslumpmässiga binära sekvenser för att uppfylla villkoret: [2] . $\{a_{n}\}_{1}^{N}$ $k$ ${\displaystyle \{b_{n}\}_{1}^{N))$ ${\displaystyle k=b_{1}a_{1}+b_{2}a_{2}+...+b_{n}a_{n))$

Låt vara en superökande sekvens. I det här fallet står vi inför ett "lätt" problem med en ryggsäck, vilket inte är svårt att lösa. För att göra detta jämförs det med elementet . Om då värdet minskas med och hoppa till medlemmen av sekvensen . Åtgärden upprepas tills processen avslutas. Om i slutändan , så hittas lösningen på problemet i form av en sekvens , annars existerar den inte [2] . $\{a_{n}\}_{1}^{N}$ $k$ $a_{n}$ ${\displaystyle k\geq a_{n))$ $b_{n}=1$ $k$ $a_{n}$ $a_{n-1}$ $k=0$ ${\displaystyle \{b_{n}\}_{1}^{N))$

Om sekvensen inte är superökande (eller normal) är ryggsäckar ett "hårt" problem som bara kan lösas genom att räkna upp alla möjliga alternativ. $\{a_{n}\}_{1}^{N}$

Den privata nyckeln i Merkle-Hellman-algoritmen är sekvensen av vikter för det superökande ryggsäcksproblemet, medan den publika nyckeln är sekvensen av vikter för det normala ryggsäcksproblemet med samma lösning. Det finns ett sätt att konvertera det superökande ryggsäcksproblemet till ett normalt ryggsäcksproblem med hjälp av modulära aritmetik. För att få en normal ryggsäckssekvens kommer vi att använda en superökande ryggsäckssekvens. Låt oss till exempel ta en talföljd: , och modulo multiplicera varje element i denna sekvens med talet . Ett villkor ställs på: värdet på modulen måste vara större än summan av alla element i sekvensen, till exempel . Och multiplikatorn måste vara ett relativt primtal med en modulo, till exempel . I ett sådant fall skulle den normala ryggsäckssekvensen vara [2] : $\{2,3,7,13,27,61\}$ $m$ $n$ $m$ $m=115$ $n$ $n=31$

$2\cdot 31mod115=62;$

$3\cdot 31mod115=93;$

$7\cdot 31mod115=102;$

$13\cdot 31mod115=58;$

$27\cdot 31mod115=32;$

$61\cdot 31mod115=51.$

Vi får en normal talföljd: . Den superökande ryggsäckssekvensen är den privata nyckeln, medan den normala ryggsäckssekvensen är den offentliga nyckeln. ${\displaystyle \{62,93,102,58,32,51\))$

System för multilateral hemlighetsdelning

Ett flerpartisystem för hemlighetsdelning med en superökande sekvens föreslogs 2017. Det unika med systemet ligger i det faktum att det inte bara är multilateralt, utan också implementerar en struktur med sekventiell åtkomst efter nivåer. Algoritmen använder Shamir-schemat , eller snarare genereringen av hemliga aktier, följt av den hemliga återställningsfasen [7] .

Låt oss presentera en algoritm för att implementera ett multilateralt hemlighetsdelningssystem.

Generering av hemliga aktier [8]

Steg 1.1. En hemlighet väljs , där är något primtal som är känt för alla parter och anger det slutliga storleksfältet . Låt , var är antalet deltagare mellan vilka du behöver dela hemligheten . ${\displaystyle s\in \mathbb {Z} _{p}-\{0\))$ $sid$ $sid$ $p=2^{l-1}$ $l$ $s$

Steg 1.2. Låt oss omvandla hemligheten till -bitars pseudo-slumpmässiga binära talsystem och bilda sekvensen . $s$ $(l-1)$ ${\displaystyle st=\{s_{l-1},s_{l-2},s_{l-3},...,s_{3},s_{2},s_{1}\))$

Steg 1.3. Låt oss komponera en binär längdsekvens från slumpmässigt valda element: . $l-1$ ${\displaystyle \{e_{l-1},e_{l-2},e_{l-3},...,e_{3},e_{2},e_{1}\))$

Steg 1.4. Vi använder XOR- operationen mellan elementen i sekvenserna från steg 1.2 och steg 1.3. Som ett resultat får vi en ny sekvens: . $st^{'}=\{s_{l-1}\oplus e_{l-1},s_{l-2}\oplus e_{l-2},s_{l-3}\oplus e_ {l-3},...,s_{3}\oplus e_{3},s_{2}\oplus e_{2},s_{1}\oplus e_{1}\}=\{s_{l -1}^{'},s_{l-2}^{'},s_{l-3}^{'},...,s_{3}^{'},s_{2}^{' },s_{1}^{'}\}$

Steg 1.5. Låt oss bygga en superökande sekvens av slumpmässiga längdtal : . $l-1$ ${\displaystyle w=\{w_{l-1},w_{l-2},w_{l-3},...,w_{3},w_{2},w_{1}\))$

Steg 1.6. Vi beräknar beloppet , som kommer att vara känt för alla deltagare. Funktion pseudokod: $u=bagsum(st^{'},w)$

funktion bugsum(a, b); Ingång: och . output: summa. summa ; för i r göra summa summa ; slutet

a=\{a_{1},...,a_{r}}\

b=\{b_{1},...,b_{r}\}

\leftarrow 0

\i

\leftarrow

+

{\displaystyle a_{i}\times b_{i))

retursumma;

Steg 1.7. Välj ett primtal , som kommer att tillkännages för alla deltagare, och så att: och för , där antalet nivåer och det totala antalet deltagare i nivån . $q$ $w_{1}+w_{2}+w_{3}+...+w_{l-1}<q$ $\max(n_{i})$ $1\leq i\leq l$ $i-$ $n_{i}-$ $i$

Steg 1.8. Vi fördelar bland alla deltagare på nivån med , där bestämmer graden av Shamir-schemapolynomet på nivån . Därefter måste du konvertera elementen i sekvensen i steg 1.3 till decimalsystemet och även fördela dem efter nivå med hjälp av . $w_{i}$ $i$ $(t_{i},n_{i})$ ${\displaystyle t_{i}<n_{i))$ $F(x)$ $i$ $l$ $(t_{l},n_{l})$

Hemlig återhämtningsfas [8]

Steg 2.1. Åtminstone får deltagarna hemligheten på nivån och får en andel för . ${\displaystyle t_{i))$ $i$ ${\displaystyle w_{i))$ $1\leq i\leq l-1$

Steg 2.2. Den första nivån kontrollerar om det verkligen är sant för det belopp som erhölls i steg 1.6. Om olikheten är sann, matar den första nivån ut och skickar till den andra nivån ett nytt summavärde: . Annars matar den ut och skickar till nästa lager och lägger till sin utdatabit till den tomma sekvensen . Det är nödvändigt att gå igenom alla nivåer och gradvis fylla sekvensen . $u\geq w_{1}$ $ett$ ${\displaystyle u_{1,2}^{'}=u-w_{1))$ $0$ $u_{1,2}^{'}=u$ $0$ $st^{''}$ $st^{''}$

Steg 2.3. Nivån utför hemlig återhämtning och sekvenssådd . Vi upprepar beräkningarna som utfördes i steg 1.4 med XOR-operationen: . $l$ $\{e_{l-1}^{'},e_{l-2}^{'},e_{l-3}^{'},...,e_{3}^{'} ,e_{2}^{'},e_{1}^{'}\}$ $st=\{e_{l-1}^{'}\oplus s_{l-1}^{'},e_{l-2}^{'}\oplus s_{l-2}^{ '},e_{l-3}^{'}\oplus s_{l-3}^{'},...,e_{3}^{'}\oplus s_{3}^{'},e_ {2}^{'}\oplus s_{2}^{'},e_{1}^{'}\oplus s_{1}^{'}\}$

Steg 2.4 . Slutligen fick vi en hemlig binär sekvens som kan konverteras till decimal för att få hemligheten . $s$

Anteckningar

↑ Richard A. Mollin, en introduktion till kryptografi (diskret matematisk & tillämpningar) , Chapman & Hall/CRC; 1 upplaga (10 augusti 2000), ISBN 1-58488-127-5
↑ 1 2 3 4 Schneier, 1993 .
↑ Merkle, Hellman, 1978 .
↑ Salomaa, 1995 .
↑ Merzouga, Ali-Pachab, Hadj-Saidb, Ali-Pachab, 2019 .
↑ Murin, 2011 .
↑ Basit, Chanakya, Venkaiah, Abdul Moiz, 2020 .
↑ 1 2 Harsha, Chanakya, Vadlamudi China Venkaiah, 2017 .

Litteratur

Bruce Schneier. Tillämpad kryptografi: protokoll, algoritmer och källkod i C. - 1993. - P. 463-465. — ISBN 978-0471117094 .
Merkle RC och Hellman ME Trapdoor ryggsäck. - 1978. - S. 525-526.
Salomaa A. Public-Key Kryptografi. — 1995.
A. Merzouga, A. Ali-Pachab, N. Hadj-Saidb, H. Ali-Pachab. Produktion av en superökande sekvens baserad på Fibonaci-sekvensen . — 2019.
P. Harsha, P. Chanakya och Vadlamudi China Venkaiah. Ett återanvändbart flerdelat hemligt delningsschema baserat på superincreasing sekvens . — 2017.
A. Basit, P. Chanakya, V. Ch. Venkaiah och S. Abdul Moiz. Nytt multi-hemligt delningsschema baserat på superökande sekvens för nivåordnad åtkomststruktur . — 2020.
Murin DM I storleksordningen för tillväxt av antalet injektions- och superväxande ryggsäcksvektorer . — 2011.

Länkar

Superökande sekvenser