Trestegsprotokoll

Ett trepassprotokoll är ett  kryptografiskt protokoll som gör att du säkert kan överföra ett meddelande mellan två parter utan att behöva utbyta eller distribuera vare sig offentliga eller privata nycklar . Detta protokoll förutsätter användningen av ett kommutativt chiffer [1] .

Grundläggande information

Trevägsprotokollet kallas så eftersom tre krypterade meddelanden utbyts mellan avsändaren och mottagaren. Det första trestegsprotokollet utvecklades av Adi Shamir på 1980-talet men har inte publicerats [2] [3] . Grundkonceptet för protokollet är att varje sida av överföringen har sin egen privata nyckel för kryptering och privat nyckel för dekryptering. Varje sida använder sina nycklar oberoende, först för att kryptera meddelandet och sedan för att dekryptera det.

Protokollet använder en krypteringsfunktion och en dekrypteringsfunktion . Ibland kan funktionen för kryptering och dekryptering vara densamma. Krypteringsfunktionen använder krypteringsnyckeln för att ändra det vanliga meddelandet till ett krypterat, eller chiffertext , . För varje krypteringsnyckel finns det en motsvarande dekrypteringsnyckel , som gör att originaltexten kan återställas med hjälp av dekrypteringsfunktionen, .

För att krypterings- och dekrypteringsfunktionerna ska vara lämpliga för ett trevägsprotokoll, för alla meddelanden , måste valfri krypteringsnyckel med motsvarande dekrypteringsnyckel utföras . Med andra ord måste den första krypteringen med nyckeln dekrypteras , även om meddelandet är krypterat med den andra nyckeln . Detta är egenskapen för kommutativ kryptering. Kommutativ kryptering är en kryptering som inte beror på ordningen, det vill säga den är giltig för alla nycklar och för alla meddelanden . För kommutativ kryptering, .

Beskrivning av algoritmen

Anta att Alice vill skicka ett meddelande till Bob. Sedan fungerar trestegsprotokollet enligt följande [1] :

1. Alice väljer en privat krypteringsnyckel och en motsvarande dekrypteringsnyckel . Alice krypterar det ursprungliga meddelandet med nyckeln och skickar chiffertexten till Bob.
2. Bob väljer en privat krypteringsnyckel och en motsvarande dekrypteringsnyckel , krypterar sedan om det första meddelandet med nyckeln och skickar det dubbelkrypterade meddelandet tillbaka till Alice.
3. Alice dekrypterar det andra meddelandet med nyckeln . På grund av kommutativiteten som beskrivs ovan får vi , det vill säga ett meddelande krypterat med endast Bobs privata nyckel. Alice skickar denna chiffertext till Bob.
4. Bob dekrypterar det tredje meddelandet med nyckeln och får det ursprungliga meddelandet.

Det är värt att notera att alla operationer som använder Alices privata nycklar utförs av Alice, och alla operationer som använder Bobs privata nycklar utförs av Bob, det vill säga att den ena sidan av utbytet inte behöver känna till den andras nycklar.

Shamirs trestegsprotokoll

Det första trestegsprotokollet var Shamirs trestegsprotokoll [2] , utvecklat på 1980-talet. Detta protokoll kallas även för Shamir No - Key Protocol , eftersom detta protokoll inte utbyter några nycklar, utan utbytesparterna måste ha 2 privata nycklar för kryptering och dekryptering. Shamirs algoritm använder exponentieringsmodulo ett stort primtal som en funktion av både kryptering och dekryptering, det vill säga, och där  är ett stort primtal [4] . För all kryptering är exponenten i segmentet och är sant för det . Motsvarande indikator för dekryptering väljs så att . Det följer av Fermats lilla teorem att .  

Shamir-protokollet är kommutativt eftersom .

Massey-Omura kryptosystem

Massey-Omura-kryptosystemet föreslogs av James Massey och Jim K.  Omura 1982 som en förbättring av Shamir-protokollet [5] [6] . Massey-Omura-metoden använder exponentiering i Galois-fältet som en funktion av både kryptering och dekryptering, det vill säga och , där beräkningarna är i Galois-fältet. För all kryptering är exponenten i segmentet och är sant för det . Motsvarande indikator för dekryptering väljs så att . Eftersom den multiplikativa gruppen av Galois-fältet har ordning , följer det av Lagranges sats att för alla i .

Varje element i Galois-fältet representeras som en binär normal basvektor , där varje basvektor är kvadraten på den föregående. Det vill säga, basvektorerna där  är elementet i fältet med den maximala ordningen . Med hjälp av denna representation kan exponentiering till en potens av 2 göras med hjälp av ett cykliskt skift . Detta innebär att höjning till en godtycklig makt inte kan göras med mer än skift och multiplikationer. Dessutom kan multipla multiplikationer utföras parallellt. Detta möjliggör snabbare hårdvaruimplementationer genom att använda flera multiplikatorer [7] .

Säkerhet

En nödvändig förutsättning för säkerheten för trevägsprotokollet är att angriparen inte kan fastställa något om det ursprungliga meddelandet från de tre vidarebefordrade meddelandena [8] . Detta villkor innebär en begränsning av valet av krypterings- och dekrypteringsfunktioner. Till exempel kan den kommutativa funktionen xor inte användas i ett trevägsprotokoll eftersom . Det vill säga, genom att känna till de tre vidarebefordrade meddelandena kan du återställa det ursprungliga meddelandet [9] .

Kryptografisk styrka

För krypteringsfunktionerna som används i Shamir-algoritmen och Massey-Omura-algoritmen beror säkerheten på komplexiteten i att beräkna diskreta logaritmer i ett ändligt fält. Om en angripare kan beräkna diskreta logaritmer för Shamir-metoden eller för Massey-Omura-metoden, kan protokollet vara brutet. Nyckeln kan beräknas från meddelanden och . När det är känt är det lätt att beräkna graden att dechiffrera . Angriparen kan sedan beräkna genom att höja det avlyssnade meddelandet till kraften . 1998 visades det att, under vissa antaganden, att bryta Massey-Omura-kryptosystemet motsvarar att bryta Diffie-Hellman-kryptosystemet [10] .

Autentisering

Trestegsprotokollet tillhandahåller inte autentisering av utbytesparterna [11] . Därför, utan implementering av tredje parts autentisering, är protokollet sårbart för en man-in- the-middle-attack . Detta innebär att om en angripare har förmågan att skapa falska meddelanden eller avlyssna och ersätta riktiga överförda meddelanden, så äventyras utbytet .

Anteckningar

1. ↑ 1 2 B. Schneier, 1996 .
2. ↑ 12 A.G. _ Konheim, 1981 , sid. 345.
3. ↑ A. Menezes, P. van Oorschot, S. Vanstone, 1996 , sid. 535.
4. ↑ A. Menezes, P. van Oorschot, S. Vanstone, 1996 , sid. 500.
5. ↑ Patent, US4567600.
6. ↑ A. Menezes, P. van Oorschot, S. Vanstone, 1996 , sid. 642.
7. ↑ Lidl, Niederreiter 1998 , sid. 601.
8. ↑ A.G. Reinhold, 1991 , sid. 3-5.
9. ↑ Yoshito Kanamori, Seong-Moo Yoo, 2009 , sid. 65-66.
10. ↑ Sakurai, K.; Shizuya, H., 1998 , sid. 29-43.
11. ↑ A.G. Konheim, 1981 , sid. 346-7.

Litteratur

• B. Schneier. Tillämpad kryptografi: "Protokoll, algoritmer och källkoder i C". - 2:a upplagan. — New York: John Wiley & Sons, 1996.
• Lidl R., Niederreiter G. Finita fält. I 2 vol. - Moskva: Mir, 1998. - 430 sid. — ISBN 5-03-000065-8 .
• Sakurai, K.; Shizuya, H. En strukturell jämförelse av beräkningssvårigheten att bryta diskreta logkryptosystem  //  Journal of Cryptology: Artikel. - 1998. - Nej . 11 . - S. 29-43 . — ISSN 09332790 .
• A. G. Reinhold. Stark kryptografi - The Global Tide of Change  //  Cato Institute : Artikel. - 1991. - Nej . 51 . - S. 3-5 .
• US patent 4 567 600 , amerikanskt patent på Massey-Omura kryptosystem
• AG Konheim. kryptografi . - New York: John Wiley & Sons, 1981. - S.  345-7 .
• Yoshito Kanamori, Seong-Moo Yoo. Quantum three-pass protocol: Nyckeldistribution med hjälp av quantum superposition states // International Journal of Network Security & Its Applications  (  IJNSA) : Artikel. - 2009. - Nej . 2 . - S. 65-66 .
• A. Menezes, P. van Oorschot, S. Vanstone. Handbok för tillämpad kryptografi. — 5:e tryckningen. - CRC Press, 1996. - S. 500, 535, 642. - 816 sid. - ISBN 0-8493-8523-7 .