Offentlig nøgle kryptosystem

Offentlig nøgle kryptografisk system (en slags asymmetrisk kryptering , asymmetrisk kryptering ) - et kryptering og/eller elektronisk signatur (ES) system, hvor den offentlige nøgle transmitteres over en åben (det vil sige ubeskyttet, observerbar) kanal og bruges til at verificere ES og for krypteringsmeddelelser. For at generere en ES og for at dekryptere beskeden, bruges en privat nøgle [1] . Offentlig nøgle kryptografiske systemer er nu meget brugt i forskellige netværksprotokoller , især TLS-protokoller og dens forgænger SSL (underliggende HTTPS ), SSH . Bruges også i PGP , S/MIME .

Ideen om et offentlig nøglekryptosystem

Generelle principper

Asymmetrisk offentlig nøglekryptering er baseret på følgende principper:

• Det er muligt at generere et par meget store tal (offentlig nøgle og privat nøgle), så det er umuligt at kende den offentlige nøgle, at beregne den private nøgle inden for rimelig tid. I dette tilfælde er genereringsmekanismen velkendt.
• Stærke krypteringsmetoder er tilgængelige til at kryptere en besked med den offentlige nøgle, så den kun kan dekrypteres med den private nøgle. Krypteringsmekanismen er velkendt.
• Ejeren af ​​to nøgler afslører ikke den private nøgle til nogen, men deler den offentlige nøgle med modparter eller gør den offentligt kendt.

Hvis det er nødvendigt at sende en krypteret besked til ejeren af ​​nøglerne, skal afsenderen modtage den offentlige nøgle. Afsenderen krypterer sin besked med modtagerens offentlige nøgle og sender den til modtageren (ejeren af ​​nøglerne) over åbne kanaler. Samtidig kan ingen dekryptere beskeden undtagen ejeren af ​​den private nøgle.

Som et resultat kan beskeder krypteres sikkert, samtidig med at dekrypteringsnøglen holdes hemmelig for alle – også beskedafsenderne.

Dette princip kan forklares gennem hverdagsanalogien "lås - nøgle til låsen" for at sende en pakke. Deltager A har en personlig lås og en nøgle til den. Hvis deltager A ønsker at modtage en hemmelig pakke fra deltager B, så giver han ham offentligt sit slot. Deltager B låser låsen på den hemmelige pakke og sender den til deltager A. Efter at have modtaget pakken, åbner deltager A låsen med nøglen og modtager pakken.

At vide om overførslen af ​​låsen og opsnappe pakken vil ikke give noget til en potentiel angriber: kun deltager A har nøglen til låsen, så pakken kan ikke åbnes.

Implementering via en envejsfunktion

Ideen om offentlig nøglekryptografi er meget tæt forbundet med ideen om envejsfunktioner , det vil sige sådanne funktioner , at det er ret nemt at finde en værdi fra en kendt værdi , mens bestemmelsen fra er umulig i en rimelig tid.

Men selve envejsfunktionen er ubrugelig i applikationen: den kan kryptere en besked, men den kan ikke dekryptere den. Derfor bruger offentlig nøglekryptografi envejsfunktioner med et smuthul. Et smuthul er en hemmelighed, der hjælper med at tyde. Det vil sige, der eksisterer sådan , at vi ved og , kan beregne . Hvis man for eksempel skiller et ur ad i mange dele, er det meget svært at samle et ur, der virker igen. Men hvis der er en monteringsinstruktion (smuthul), så kan dette problem let løses.

Modtageren af ​​informationen genererer en offentlig nøgle og en "fældedør" (med andre ord den offentlige og private del af nøglen), overfører derefter den offentlige nøgle til afsenderen og beholder "fældedøren" for sig selv. Afsenderen krypterer informationen baseret på den offentlige nøgle: Sådan krypteret information er nem at dekryptere, hvis du har både den offentlige nøgle og en "bagdør" på samme tid. Med hensyn til en funktion danner modtageren en bagdør , hvorefter den videregiver information om funktionsparametrene til afsenderen (mens man selv kender funktionsparametrene , er det umuligt at opdage "bagdøren" inden for rimelig tid). Derefter danner afsenderen en krypteret besked , og modtageren udtrækker fra den, vel vidende .

Eksempler

Følgende eksempel hjælper med at forstå ideerne og metoderne til offentlig nøglekryptering - lagring af adgangskoder på en fjerncomputer, som brugerne skal oprette forbindelse til. Hver bruger på netværket har en anden adgangskode. Ved indgangen angiver han navnet og indtaster et hemmeligt kodeord. Men hvis du gemmer adgangskoden på disken på en ekstern computer, så kan nogen læse den (det er især let for administratoren af ​​denne computer at gøre dette) og få adgang til hemmelige oplysninger. For at løse problemet bruges en envejsfunktion. Når du opretter en hemmelig adgangskode, gemmer computeren ikke selve adgangskoden, men resultatet af beregning af funktionen ud fra denne adgangskode og brugernavn. For eksempel kom brugeren Alice med adgangskoden "Gladiolus". Når du gemmer disse data, beregnes resultatet af funktionen ( ALICE_GLADIOLUS ), lad resultatet være strengen CAMOMILE , som vil blive gemt i systemet. Som et resultat vil adgangskodefilen have følgende form:

Navn	(Navn: Adgangskode)
ALICE	KAMILLE
BØNNE	NARCISSUS

Login ser nu sådan ud:

Når Alice indtaster den "hemmelige" adgangskode, tjekker computeren, om funktionen anvendt på ALICE_GLADIOLUS giver det korrekte resultat CAMOMILE gemt på computerens disk. Det er værd at ændre mindst et bogstav i navnet eller i adgangskoden, og resultatet af funktionen vil være helt anderledes. Den "hemmelige" adgangskode er ikke gemt på computeren i nogen form. Adgangskodefilen kan nu ses af andre brugere uden tab af privatliv, da funktionen er næsten irreversibel.

Det foregående eksempel bruger en envejsfunktion uden et smuthul, da det ikke er nødvendigt at hente den originale besked fra den krypterede besked. I det følgende eksempel betragtes et skema med mulighed for at gendanne den oprindelige besked ved hjælp af en "bagdør", det vil sige information, der er svær at finde. For at kryptere teksten kan du tage en stor abonnentfortegnelse, der består af flere tykke bind (det er meget nemt at finde antallet af beboere i byen, der bruger det, men det er næsten umuligt at finde en abonnent ved hjælp af et kendt nummer) . For hvert bogstav fra den krypterede besked vælges et navn, der starter med det samme bogstav. Således tildeles brevet abonnentens telefonnummer. Beskeden, der sendes, for eksempel " BOX ", vil blive krypteret som følger:

Kryptoteksten vil være en kæde af numre skrevet i den rækkefølge, de har valgt i biblioteket. For at gøre det svært at tyde, bør du vælge tilfældige navne, der begynder med det ønskede bogstav. Således kan den oprindelige besked krypteres med mange forskellige lister over numre (kryptotekster).

Eksempler på sådanne kryptotekster:

For at tyde teksten skal du have en opslagsbog udarbejdet efter de stigende tal. Denne mappe er et smuthul (en hemmelighed, der hjælper med at få den indledende tekst) kun kendt af modtageren. Uden data fra begge mapper er det generelt umuligt at tyde teksten, men kun den første mappe er tilstrækkelig til kryptering [2] . I dette tilfælde kan modtageren nemt danne begge mapper på forhånd og kun overføre den første af dem til afsenderen til kryptering.

Offentlig nøgle krypteringsskema

Lad være  nøglerummet og og  være henholdsvis krypterings- og dekrypteringsnøglerne.  er en krypteringsfunktion for en vilkårlig nøgle , sådan at . Her , hvor  er krypteringsteksternes rum, og hvor  er meddelelsernes rum.

 er en dekrypteringsfunktion, der kan bruges til at finde den originale besked givet chifferteksten : ,  er krypteringssættet og  er det tilsvarende dekrypteringssæt. Hvert par har følgende egenskab: at vide , det er umuligt at løse ligningen , det vil sige, for en given vilkårlig chiffertekst er det umuligt at finde en besked . Det betyder, at det er umuligt at bestemme den tilsvarende dekrypteringsnøgle fra den givne . er en envejsfunktion og  er et smuthul [3] .

Nedenfor er et diagram over overførsel af information fra person A til person B. De kan både være enkeltpersoner og organisationer, og så videre. Men for lettere opfattelse er det sædvanligt at identificere deltagerne i programmet med mennesker, oftest omtalt som Alice og Bob. Den deltager, der søger at opsnappe og dekryptere Alices og Bobs beskeder, bliver oftest omtalt som Eve.

1. Bob vælger et par og sender krypteringsnøglen (offentlig nøgle) til Alice over den offentlige kanal, og dekrypteringsnøglen (privat nøgle) er beskyttet og hemmelig (den må ikke transmitteres over den offentlige kanal).
2. For at sende en besked til Bob bruger Alice krypteringsfunktionen defineret af den offentlige nøgle : ,  den modtagne chiffertekst.
3. Bob dekrypterer chifferteksten ved hjælp af den omvendte transformation , entydigt identificeret af værdien .

Videnskabeligt grundlag

Asymmetriske cifre begyndte i New Directions in Modern Cryptography af Whitfield Diffie og Martin Hellman , udgivet i 1976 . Påvirket af Ralph Merkles arbejde med distribution af offentlige nøgler foreslog de en metode til at opnå private nøgler ved hjælp af en offentlig kanal. Denne eksponentielle nøgleudvekslingsmetode, som blev kendt som Diffie-Hellman nøgleudveksling , var den første offentliggjorte praktiske metode til at etablere hemmelig nøgledeling mellem godkendte brugere af en kanal. I 2002 foreslog Hellman at kalde algoritmen "Diffie-Hellman-Merkle", idet han anerkendte Merkles bidrag til opfindelsen af ​​offentlig nøglekryptografi. Den samme ordning blev udviklet af Malcolm Williamson ( eng.  Malcolm J. Williamson ) i 1970'erne, men blev holdt hemmelig indtil 1997 . Merkles offentlige nøglefordelingsmetode blev opfundet i 1974 og udgivet i 1978 og kaldes også Merkle-gåden.

I 1977 udviklede MIT- forskerne Ronald Rivest , Adi Shamir og Leonard Adleman en krypteringsalgoritme baseret på faktoriseringsproblemet. Systemet blev opkaldt efter de første bogstaver i deres efternavne ( RSA  - Rivest, Shamir, Adleman). Det samme system blev opfundet i 1973 af Clifford Cocks , som arbejdede på Government Communications Center ( GCHQ ), men dette arbejde blev kun opbevaret i centrets interne dokumenter, så dets eksistens blev først kendt i 1977 . RSA var den første algoritme, der var egnet til både kryptering og digital signatur.  

Generelt er kendte asymmetriske kryptosystemer baseret på et af de komplekse matematiske problemer, som giver dig mulighed for at bygge envejsfunktioner og bagdørsfunktioner. For eksempel er Merkle-Hellman og Hoare-Rivest kryptosystemer afhængige af det såkaldte backpacking-problem .

Grundlæggende principper for opbygning af offentlige nøglekryptosystemer

1. Lad os starte med en svær opgave . Det burde være svært at løse i teoriens forstand: der burde ikke være en algoritme, der kunne bruges til at sortere gennem alle mulighederne for at løse problemet i polynomisk tid i forhold til problemets størrelse. Det er mere korrekt at sige: der burde ikke være en kendt polynomiel algoritme, der løser dette problem - da det endnu ikke er bevist for noget problem, at der i princippet ikke findes en passende algoritme til det.
2. Du kan vælge en let underopgave fra . Det skal løses i polynomisk tid og bedre hvis i lineær tid.
3. "Shuffle and Shake" for at få en opgave , der er helt anderledes end den originale. Problemet skal i det mindste ligne det oprindelige uløselige problem .
4. åbner med en beskrivelse af, hvordan den kan bruges som krypteringsnøgle. Hvordan man får det, holdes hemmeligt som et hemmeligt smuthul.
5. Kryptosystemet er organiseret på en sådan måde, at dekrypteringsalgoritmerne for en lovlig bruger og en kryptoanalytiker er væsentligt forskellige. Mens den anden løser -problemet, bruger den første et hemmeligt smuthul og løser -problemet.

Kryptografi med flere offentlige nøgler

• Følgende eksempel viser et skema, hvor Alice krypterer en besked, så kun Bob kan læse den, og omvendt, Bob krypterer en besked, så kun Alice kan dekryptere den.

Lad der være 3 nøgler , , , fordelt som vist i tabellen.

ansigt	Nøgle
Alice
Bønne
Carol
Dave	,
Ellen	,
Franc	,

Så kan Alice kryptere beskeden med nøglen , og Ellen kan dekryptere med nøglerne , Carol kan kryptere med nøglen , og Dave kan dekryptere med nøglerne . Hvis Dave krypterer beskeden med nøgle , så kan Ellen læse beskeden, hvis med nøgle , så kan Frank læse den, hvis med begge nøgler og , så læser Carol beskeden. Andre deltagere handler på samme måde. Således, hvis et undersæt af nøgler bruges til kryptering, så kræves de resterende nøgler i sættet til dekryptering. Et sådant skema kan bruges til n nøgler.

Krypteret med en nøgle	Dekrypteret med nøgle
og
og
og
	,
	,
	,

• Nu kan du sende beskeder til grupper af agenter uden at kende gruppens sammensætning på forhånd.

Overvej først et sæt bestående af tre agenter: Alice, Bob og Carol. Alice får nøgler og , Bob - og , Carol - og . Nu, hvis beskeden, der sendes, er krypteret med nøglen , er det kun Alice, der kan læse den ved sekventielt at anvende nøglerne og . Hvis du vil sende en besked til Bob, krypteres beskeden med nøglen , Carol - med nøglen . Hvis du vil sende en besked til både Alice og Carol, så bruges nøglerne og til kryptering .

Fordelen ved denne ordning er, at der kun kræves én besked og n nøgler for at implementere den (i en ordning med n agenter). Hvis individuelle beskeder sendes, det vil sige, at der bruges separate nøgler for hver agent (i alt n nøgler) og hver besked, så kræves nøgler for at sende beskeder til alle forskellige undersæt.

Ulempen ved denne ordning er, at du også skal udsende en undergruppe af agenter (listen over navne kan være lang), som du vil udsende beskeden til. Ellers bliver hver af dem nødt til at gennemgå alle kombinationer af nøgler på jagt efter en passende. Agenter bliver også nødt til at gemme en betydelig mængde information om nøglerne [4] .

Krypteringsanalyse af offentlige nøglealgoritmer

Det ser ud til, at et offentligt nøglekryptosystem er et ideelt system, der ikke kræver en sikker kanal til at overføre krypteringsnøglen. Dette ville betyde, at to legitime brugere kunne kommunikere over en åben kanal uden at skulle mødes for at udveksle nøgler. Det er det desværre ikke. Figuren illustrerer, hvordan Eve, der fungerer som en aktiv interceptor, kan overtage systemet (dekryptere beskeden beregnet til Bob) uden at bryde krypteringssystemet.

I denne model opsnapper Eve den offentlige nøgle sendt af Bob til Alice. Det genererer derefter et nøglepar og "forklæder sig" som Bob ved at sende Alice den offentlige nøgle , som Alice tror er den offentlige nøgle, som Bob har sendt til hende. Eve opsnapper krypterede beskeder fra Alice til Bob, dekrypterer dem med den hemmelige nøgle , genkrypterer dem med Bobs offentlige nøgle og sender beskeden til Bob. Ingen af ​​deltagerne er således klar over, at der er en tredjepart, der enten blot kan opsnappe beskeden eller erstatte den med en falsk besked . Dette understreger behovet for offentlig nøglegodkendelse . Til dette bruges normalt certifikater . Distribueret nøglestyring i PGP løser problemet ved hjælp af garanter [5] .

En anden form for angreb er at beregne den private nøgle fra den offentlige nøgle (figur nedenfor). Kryptanalytikeren kender krypteringsalgoritmen , analyserer den, prøver at finde . Denne proces forenkles, hvis kryptoanalytikeren har opsnappet flere kryptotekster c sendt af person A til person B.

De fleste offentlige nøglekryptosystemer er baseret på problemet med faktorisering af store tal. For eksempel bruger RSA produktet af to store tal som den offentlige nøgle n. Kompleksiteten ved at knække en sådan algoritme ligger i vanskeligheden ved at faktorisere tallet n. Men dette problem kan løses realistisk. Og hvert år bliver nedbrydningsprocessen hurtigere og hurtigere. Nedenfor er faktoriseringsdataene ved hjælp af "Quadratic Sieve"-algoritmen.

Også nedbrydningsproblemet kan potentielt løses ved hjælp af Shor-algoritmen , når du bruger en tilstrækkelig kraftig kvantecomputer .

For mange metoder til asymmetrisk kryptering adskiller den kryptografiske styrke opnået som et resultat af kryptoanalyse sig væsentligt fra de værdier, der er erklæret af udviklerne af algoritmer baseret på teoretiske estimater. Derfor er spørgsmålet om brug af datakrypteringsalgoritmer i mange lande inden for lovgivningsmæssig regulering. Især i Rusland er det kun de datakrypteringssoftwareværktøjer, der har bestået statscertificering i administrative organer, især i FSB , FSTEC , tilladt til brug i statslige og kommercielle organisationer [6] .

Funktioner i systemet

Ansøgning

Offentlig nøgle kryptosystemalgoritmer kan bruges [7] :

• som et uafhængigt middel til at beskytte transmitteret og lagret information,
• som et middel til at distribuere nøgler (normalt ved hjælp af algoritmer fra offentlige nøglekryptosystemer distribueres nøgler, der er små i størrelse, og transmissionen af ​​store informationsstrømme udføres ved hjælp af andre algoritmer)
• som et middel til brugergodkendelse.

Fordele

Fordele ved asymmetriske cifre frem for symmetriske :

• ingen grund til først at overføre den hemmelige nøgle over en pålidelig kanal;
• kun den ene side kender dekrypteringsnøglen, som skal holdes hemmelig (i symmetrisk kryptografi er en sådan nøgle kendt af begge parter og skal holdes hemmelig af begge);
• i store netværk er antallet af nøgler i et asymmetrisk kryptosystem meget mindre end i et symmetrisk.

Ulemper

Ulemper ved den asymmetriske krypteringsalgoritme sammenlignet med den symmetriske:

• det er sværere at foretage ændringer i algoritmen;
• længere nøgler - nedenfor er en tabel, der sammenligner nøglelængden af ​​en symmetrisk algoritme med længden af ​​en RSA-nøgle med tilsvarende kryptografisk styrke:

• kryptering-dekryptering ved hjælp af et nøglepar er to til tre størrelsesordener langsommere end kryptering-dekryptering af den samme tekst ved hjælp af en symmetrisk algoritme;
• Der kræves betydeligt flere computerressourcer, derfor bruges asymmetriske kryptosystemer i praksis i kombination med andre algoritmer:
  1. for EDS er beskeden tidligere hashed, og ved hjælp af en asymmetrisk nøgle signeres kun et relativt lille resultat af hash-funktionen ;
  2. til kryptering bruges de i form af hybride kryptosystemer , hvor store mængder data krypteres med en symmetrisk chiffer på en sessionsnøgle, og kun selve sessionsnøglen transmitteres ved hjælp af en asymmetrisk chiffer.

Typer af asymmetriske cifre

• RSA (Rivest-Shamir-Adleman)
• DSA (Digital Signature Algorithm)
• Elgamal (ElGamal Cipher System)
• Diffie-Hellman (Diffie-Hellman Key Exchange)
• ECDSA (Elliptic Curve Digital Signature Algorithm) er en offentlig nøglealgoritme til at skabe en digital signatur.
• GOST R 34.10-2012
• Rabin
• Luc
• McEliece
• Williams kryptosystem

Se også

• Blok chiffer
• Stream chiffer
• Public Key Infrastructure (PKI)
• CEILIDH
• Adgangskodekompleksitet
• Hushmail  er en webbaseret e-mail-tjeneste baseret på offentlig nøglekryptering.

Noter

1. ↑ Bruce Schneier. Anvendt kryptografi. 2. udg. Protokoller, algoritmer og kildetekster i C-sprog. Kapitel 2.7 Digitale signaturer og kryptering.
2. ↑ Salomaa A. Offentlig nøglekryptografi. Med. 74-75
3. ↑ Handbook of Applied Cryptography, Menezes AJ, Oorschot PC, Vanstone SA s. 25-26
4. ↑ Bruce Schneier. Anvendt kryptografi. 2. udg. Protokoller, algoritmer og kildetekster i C-sprog. Kapitel 3.5
5. ↑ PGP. Nøglefordeling. . Arkiveret fra originalen den 26. juli 2013. (ubestemt)
6. ↑ Princippet om tilstrækkelig beskyttelse (utilgængeligt link) . Hentet 4. december 2008. Arkiveret fra originalen 24. maj 2010. (ubestemt) 
7. ↑ Barichev S. Kryptografi uden hemmeligheder. Med. tyve

Litteratur

• Salomaa A. Offentlig nøglekryptering. — M .: Mir, 1995. — 318 s. — ISBN 5-03-001991-X .
• AJ Menezes, PC van Oorschot, SA Vanstone. Håndbog i anvendt kryptografi . - 1997. - ISBN 0-8493-8523-7 .
• Schneier B. Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 eksemplarer.  - ISBN 5-89392-055-4 .

Links

• Tredive år med den offentlige nøgle | Computerworld Rusland | Forlag "Open Systems"  (russisk)