Merkle-Hellman ryggsäckskryptosystem

Merkle-Hellman ryggsäckskryptosystemet , baserat på " ryggsäcksproblemet ", utvecklades av Ralph Merkle och Martin Hellman 1978 [ 1] . Det var ett av de första kryptosystemen med offentlig nyckel , men det visade sig vara kryptografiskt svagt [2] och blev som ett resultat inte populärt.

Beskrivning

"Knappsäcksproblemet" är som följer: att känna till undergruppen av laster som packats i ryggsäcken är det lätt att beräkna den totala vikten , men att känna till vikten är det inte lätt att bestämma underdelen av laster. Mer detaljerat, låt det vara en sekvens av n positiva tal (n är "storleken" på ryggsäcken)

w = ( w 1 , w 2 , …, w n ) och s .

Uppgiften är att hitta en sådan binär vektor

x = ( x 1 , x 2 , …, x n ), ( x i = 0 eller 1),

till

{\displaystyle s=\sum _{i=1}^{n}x_{i}w_{i))

Om varje binärt tal x är associerat med någon bokstav i alfabetet, kan det överföras i krypterad form helt enkelt som summan av s . För en godtycklig uppsättning tal w i är problemet med att återställa x från s NP-hårt .

Merkle lyckades få en funktion invers till talet s som skulle ge en vektor x , med en viss "hemlig" nyckel , och han erbjöd $100 till någon som kunde upptäcka Merkle-Hellmans ryggsäckssystem.

Låt oss överväga det mer i detalj.

Merkle använde inte en godtycklig sekvens w i , utan en superökande, det vill säga sådan att

w_{k+1}>\sum _{i=1}^{k}w_{i}

Det är lätt att se att för en sådan uppsättning siffror är lösningen av problemet trivial. För att bli av med denna trivialitet var det nödvändigt att införa en "hemlig nyckel", nämligen två siffror: q sådan och r sådan att gcd(r, q) =1. Och nu istället för den ursprungliga uppsättningen av siffror w i kommer vi att använda talen b i =r w i mod q . I originalpapperen rekommenderade Merkle att använda n i storleksordningen 100, där n är antalet element i den superökande sekvensen ("storleken" på ryggsäcken). $q>\sum _{i=1}^{n}w_{i}$

Som ett resultat får vi: publik nyckel - ( b 1 , b 2 , ..., b n ), privat nyckel - ( w 1 , w 2 , ..., w n ; q , r ).

Kryptering

– meddelande x = ( x 1 , x 2 , ..., x n ) - beräkna y = b 1 x 1 + b 2 x 2 + , ..., + b n x n

Dekryptering

- beräkna s = yr -1 mod q - lös problemet för s för en superökande sekvens ( w 1 , w 2 , ..., w n ), d.v.s. hitta binärt tal x

Priset gick till A. Shamir efter att han i mars 1982 publicerade en rapport om avslöjandet av Merkle-Hellman ryggsäckssystem med en iteration. Observera att Shamir kunde konstruera en nyckel som inte nödvändigtvis är lika med hemligheten, men som låter dig öppna chiffret .

Så detta var ett av de misslyckade, men mycket intressanta försöken att bygga ett kryptosystem baserat på ryggsäcksproblemet.

Nyckelgenerering

I Merkle-Hellman-systemet består nycklar av sekvenser. Den publika nyckeln är en "komplex" sekvens, den privata nyckeln består av en "enkel" eller superökande sekvens, samt två ytterligare tal - en multiplikator och en modul, som båda används för att omvandla den superökande sekvensen till en "komplex" en (generering av offentlig nyckel) och att transformera summan av en delmängd av en "komplex" sekvens till summan av en delmängd av en "enkel" sekvens (dekryptering). Det sista problemet löses i polynomtid .

Kryptering

Först måste källtexten representeras i binär form och delas upp i block som är lika långa som den publika nyckeln. Vidare, från sekvensen som bildar den publika nyckeln, väljs endast de element som motsvarar ordningen 1 i den binära notationen av källtexten, samtidigt som de element som motsvarar bit 0 ignoreras . Därefter läggs elementen i den resulterande delmängden till. Den resulterande summan är chiffertexten.

Dekryptering

Dekrypteringen är möjlig eftersom multiplikatorn och modulen som används för att generera den publika nyckeln från den superökande sekvensen också används för att omvandla chiffertexten till summan av motsvarande element i den superökande sekvensen. Vidare, med hjälp av en enkel girig algoritm , kan man dekryptera meddelandet med O(n) aritmetiska operationer.

Matematisk beskrivning av algoritmen

Nyckelgenerering

För att kryptera ett n -bitars meddelande väljer vi en superökande sekvens av n naturliga tal som inte är noll

w = ( wi , w2 , … , wn ) .

Därefter väljer vi slumpmässigt coprime heltal q och r så att

q>\sum _{i=1}^{n}w_{i}

Siffran q väljs på ett sådant sätt att det garanterar chiffertextens unikhet (unikhet). Om det är åtminstone lite mindre kan en situation uppstå att flera källtexter (öppna) kommer att motsvara en chiffertext. r måste vara coprime till q , annars kommer den inte att ha en multiplikativ invers modulo q , vars existens är nödvändig för dekryptering.

Låt oss nu bygga sekvensen

β = (β 1 , β 2 , …, β n ),

där varje element beräknas med följande formel

β i = rw i mod q .

β kommer att vara den publika nyckeln medan den privata nyckeln bildar sekvensen ( w , q , r ).

Kryptering

För att kryptera ett n -bitars meddelande

α = (α 1 , α 2 , …, α n ),

var är den i -te biten, dvs {0, 1}, beräknar vi talet c, som blir chiffertexten. $\alpha_i$ $\alpha _{i}{\boldsymbol {\in }}$

c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}.

Dekryptering

För att läsa originaltexten måste mottagaren bestämma de meddelandebitar som skulle uppfylla formeln $\alpha_i$

c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}.

Ett sådant problem skulle vara NP-svårt om β i var slumpmässigt valda värden. Värdena på β i har dock valts så att dekryptering är en enkel uppgift, förutsatt att den privata nyckeln ( w , q , r ) är känd.

Nyckeln till att hitta källtexten är att hitta ett heltal s som är den multiplikativa inversen av r modulo q . Detta betyder att s uppfyller ekvationen sr mod q = 1, vilket är ekvivalent med förekomsten av ett heltal k så att sr = kq + 1. Eftersom r är coprime till q , är det möjligt att hitta s och k med den utökade euklidiska algoritmen . Därefter beräknar mottagaren av chiffertexten

c'\equiv cs{\pmod {q)).

Härifrån

c'\equiv cs\equiv \sum _{i=1}^{n}\alpha _{i}\beta _{i}s{\pmod {q)).

Från det faktum att rs mod q = 1 och βi = rwi mod q

\beta _{i}s\equiv w_{i}rs\equiv w_{i}{\pmod {q)).

Sedan

c'\equiv \sum _{i=1}^{n}\alpha _{i}w_{i}{\pmod {q)).

Summan av alla w i är mindre än q . Därför ligger värdet också i intervallet [0,q-1]. Mottagaren ska således utifrån villkoret fastställa att $\sum _{i=1}^{n}\alpha _{i}w_{i}$ $\alpha_i$

c'=\sum _{i=1}^{n}\alpha _{i}w_{i}.

Och detta är redan en lätt uppgift, eftersom w är en superökande sekvens. Låt w k vara det största elementet i w . Om wk > c' , då ak = 0 ; om w k ≤c' , då α k = 1. Subtrahera sedan produkten w k × α k från c' och upprepa dessa steg tills vi beräknar α.

Exempel

w = {2, 7, 11, 21, 42, 89, 180, 354} är en superökande sekvens.

Det är grunden för att generera en privat nyckel. Beräkna summan av elementen i sekvensen

\sum w=706

Därefter väljer vi ett primtal q som överstiger värdet av summan som erhållits av oss.

q = 881

Vi väljer också ett tal r från intervallet [1,q]

r = 588

w , q och r bildar en privat nyckel.

För att generera en publik nyckel konstruerar vi en sekvens β genom att multiplicera varje element från sekvensen w med r modulo q .

2 * 588 mod 881 = 295 7 * 588 mod 881 = 592 11 * 588 mod 881 = 301 21 * 588 mod 881 = 14 42 * 588 mod 881 = 28 89 * 588 mod 881 = 353 180 * 588 mod 881 = 120 354 * 588 mod 881 = 236 Vi får β = (295, 592, 301, 14, 28, 353, 120, 236).

Sekvensen β bildar den publika nyckeln.

Låt Alice vilja kryptera "a". Först måste hon konvertera "a" till binär

01100001

Sedan multiplicerar hon varje bit med motsvarande tal från sekvensen β och skickar summan av värdena till mottagaren.

a = 01100001 0*295 +1*592 +1*301 + 0 * 14 + 0 * 28 +0*353 + 0 * 120 +1*236 = 1129

För att dekryptera meddelandet multiplicerar Bob värdet han fick med den multiplikativa inversen av r modulo q .

1129 * 442 mod 881 = 372

Efter det bryter Bob ner 372 enligt följande. Den väljer först det största elementet från w som är mindre än 372 och beräknar deras skillnad. Därefter väljer den det näst största elementet som är mindre än den resulterande skillnaden och upprepar dessa steg tills skillnaden blir noll.

372 - 354 = 18 18 - 11 = 7 7 - 7 = 0

Elementen som valdes från w kommer att motsvara 1 i källans binära notation.

01100001

Genom att översätta tillbaka från binär notation får Bob äntligen det önskade "a".

Se även

Anteckningar

↑ Ralph Merkle och Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory , 24(5), september 1978, sid. 525-530.
↑ Adi Shamir, en polynomisk tidsalgoritm för att bryta det grundläggande Merkle-Hellman-kryptosystemet. CRYPTO 1982, sid 279-288. Arkiverad kopia . Hämtad 6 december 2005. Arkiverad från originalet 24 april 2005. (obestämd)

Litteratur

Schneier B. Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 sid. - 3000 exemplar. - ISBN 5-89392-055-4 .

Länkar

ryggsäcksproblemet
Ansökningar	Knapsäcksproblem i kryptografi Skärningsuppgift
Kryptosystem baserade på ryggsäcksproblemet	Merkla-Hellman Naccasha - Stern Graham - Shamira
Dessutom	Lista över uppgifter om ryggsäck

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort