Merkles pussel

Inom kryptografi är Merkles pussel en tidig konstruktion för ett kryptosystem med offentlig nyckel , ett protokoll som utarbetades av Ralph Merkle 1974 och publicerades 1978. Det tillåter två parter att komma överens om en delad hemlighet genom att utbyta meddelanden, även om de inte har några hemligheter i vanligt i förväg.

Beskrivning

Antag att Alice och Bob vill kommunicera. Bob kan skicka ett meddelande till Alice enligt följande: först skapar han ett stort antal pussel, vart och ett med måttlig svårighetsgrad — det måste vara möjligt för Alice att lösa pusslet med en måttlig mängd datoransträngning. Pusslen är i form av ett krypterat meddelande med en okänd nyckel ; nyckeln måste vara tillräckligt kort för att tillåta en brute force attack . Bob skickar alla pussel (dvs. krypterade meddelanden) till Alice, som väljer ett slumpmässigt och löser det. Den dekrypterade lösningen innehåller en identifierare såväl som en sessionsnyckel, så Alice kan kommunicera tillbaka till Bob vilket pussel hon har löst. Båda parter har nu en gemensam nyckel; Alice, för att hon löste ett pussel, och Bob, för att han skickade pusslet. Alla tjuvlyssnare (säg Eva) har en svårare uppgift - hon vet inte vilket pussel som löstes av Alice. Hennes bästa strategi är att lösa alla pussel, men eftersom det finns så många är detta beräkningsmässigt dyrare för Eve än för Alice.

Beskrivning på hög nivå

1. Bob genererar 2 ^N meddelanden som innehåller "Detta är meddelande X. Detta är den symmetriska nyckeln Y", där X är en slumpmässigt genererad identifierare och Y är en slumpmässigt genererad hemlig nyckel avsedd för symmetrisk kryptering. Därför är både X och Y unika för varje meddelande. Alla meddelanden är krypterade på ett sätt så att en användare kan utföra en brute force attack mot varje meddelande med viss svårighet. Bob skickar alla krypterade meddelanden till Alice.
2. Alice tar emot alla krypterade meddelanden och väljer slumpmässigt ett enda meddelande till brute force. Efter att Alice upptäcker både identifieraren X och den hemliga nyckeln Y i meddelandet, krypterar hon sin klartext med den hemliga nyckeln Y och skickar den identifieraren (i klartext) med sin chiffertext till Bob.
3. Bob letar upp den hemliga nyckeln parad med den identifieraren, eftersom det är han som genererade dem i första hand, och dechiffrerar Alices chiffertext med den hemliga nyckeln.

Observera att avlyssnaren Eve kan läsa identifieraren X som skickats tillbaka (i klartext) från Alice till Bob, men har inget sätt att mappa det till den hemliga nyckel Y som Bob och Alice nu använder för sin pågående kommunikation, eftersom värdet av X inom varje meddelande genererades slumpmässigt.

Komplexitet och säkerhetsanalys

Parametrarna för pusselspelet kan väljas för att göra det avsevärt svårare för en avlyssnare att bryta koden än för parterna att kommunicera, men Merkle-pussel ger inte de enorma kvalitativa skillnader i svårighetsgrad som krävs för (och definiera) säkerhet i modern kryptografi.

Anta att antalet pussel skickade av Bob är m , och det tar både Bob och Alice n beräkningssteg för att lösa ett pussel. Då kan båda härleda en gemensam sessionsnyckel inom en tidskomplexitet av O ( m+n ) . Eve, däremot, krävs för att lösa alla pussel, vilket tar hennes O( mn ) tid. Om m ≈ n , har ansträngningen för Eva ungefär kvadratisk komplexitet jämfört med Alice och Bob, dvs hennes beräkningstid är i storleksordningen deras kvadrat. n bör därför väljas tillräckligt stor så att beräkning fortfarande är genomförbar för Alice och Bob samtidigt som den överträffar Eves möjligheter.

Kvadratisk komplexitet anses vanligtvis inte vara tillräckligt säker mot en angripare (eller å andra sidan, för stora m,n, tillräckligt bekvämt för deltagarna) för praktiska kryptografiska tillämpningar i verkligheten. Detta schema har dock särskiljningen av att vara ett av de första exemplen på offentliga nyckel , och var en inspiration för Diffie-Hellman- nyckelutbytesprotokollet, som har mycket högre komplexitet, beroende på det diskreta logaritmproblemet .

2008 visade Boaz Barak och Mohammad Mahmoody-Ghidary ( "Merkle Puzzles Are Optimal" ) att denna kvadratiska gräns inte kan förbättras.

•   Merkle, RC (april 1978). "Säker kommunikation över osäkra kanaler". Kommunikation från ACM . 21 (4): 294–299. CiteSeerX 10.1.1.364.5157 . doi : 10.1145/359460.359473 . [pdf ]

externa länkar

• Ralph Merkle, Secure Communications over Insecure Channels (1974) : En historia om idén och dess publicering, med en intervju från år 1995, redigerad av Arnd Weber
• Ralph Merkle, 1974 projektförslag för CS 244 vid UC Berkeley.
• Ralph Merkle, 7 december 1975, "Säker kommunikation över osäkra kanaler"