Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Саломаа А. Кpиптогpафия с откpытым ключом

.pdf
Скачиваний:
114
Добавлен:
02.05.2014
Размер:
1.42 Mб
Скачать

kriptografiq s otkrytym kl`~om

Arto Salomaa

Public-Key

Cryptography

With 18 Figures

Springer-Verlag

Berlin Heidelberg New York London

Paris Tokyo Hong Kong Barcelona

a. sALOMAA

kpIPTOGpAFIQ

S OTKpYTYM KL@^OM

pEpEWOD S ANGLIJSKOGO i.a. wIHLQNCEWA

POD pEDAKCIEJ

a.e. aNDpEEWA I a.a. bOLOTOWA

mOSKWA "mIp"

1995

bbk 22.1 s20

udk 51(0.062)

sALOMAA a.

s20 kpIPTOGpAFIQ S OTKpYTYM KL@^OM: pEp. S ANGL. | m.: mIp, 1995. | 318 S., IL.

ISBN 5{03{001991{X

ppEDLAGAEMAQ WNIMANI@ ^ITATELQ KNIGA QWLQETSQ PpAKTI^ESKI PEpWYM IZDANIEM NA pUSSKOM QZYKE, POSWQ]ENNYM MATEMATI^ESKIM WOPpOSAM KpIPTOGpAFII, I NAPISANA IZWESTNYM FINSKIM U^ENYM, AWTOpOM NESKOLXKIH MONOGpAFIJ I U^EBNIKOW a. sALOMAA. w NEJ OBOB]A@TSQ POSLEDNIE DOSTIVENIQ W OBLASTI KpIPTOGpAFII, OSOBOE WNIMANIE PpI \TOM UDELQETSQ KpIPTOSISTEMAM S OTKpYTYM KL@^OM. tAKVE pASSMATpIWA@TSQ KpIPTOGpAFI^ESKIE PpOTOKOLY, KOTOpYE OTKpYWA@T NOWU@ STpANICU W OBESPE^ENII ZA]ITY INFOpMACIONNYH POTOKOW W pAZLI^NYH KOMPX@TEpNYH SETQH.

dLQ WSEH INTEpESU@]IHSQ PpOBLEMAMI KpIPTOGpAFII I ZA]ITOJ INFOpMACII.

bbk 22.1

rEDAKCIQ LITEpATUpY PO MATEMATI^ESKIM NAUKAM

ISBN 5{03{001991{X(p

USSK

.)

c

 

 

 

 

 

 

°1990 by Springer-Verlag

 

ISBN 0{387{52831{8(

ANGL

.)

 

c

PE EWOD NA

p

USSKIJ QZYK

,

 

 

 

°

p

 

wIHLQNCEW i.a., bOLOTOW a.a., 1995

oT pEDAKTOpOW PEpEWODA

w NASTOQ]EE WpEMQ KpIPTOGpAFIQ PEpEVIWAET BUM. HA PpOTQVENII SWOEJ BOLEE ^EM TYSQ^ELETNEJ ISTOpII ONA OBSLUVIWALA W OSNOWNOM NUVDY WOENNYH, DIPLOMATOW I pAZWED^IKOW W OBESPE^ENII SEKpETNOSTI PpI OBMENE SOOB]ENIQMI I PpEDSTAWLQLA SOBOJ POSTOQNNO OBNOWLQ@- ]IJSQ I SOWEp[ENSTWU@]IJSQ NABOp TEHNI^ESKIH PpIEMOW [IFpOWANIQ (I SOOTWETSTWENNO DE[IFpOWANIQ), KOTOpYE, ESTESTWENNO, SAMI DEpVALISX W SEKpETE. i LI[X S SEpEDINY SEMIDESQTYH GODOW (W SWQZI S IZOBpETENIEM SISTEM S OTKpYTYM KL@^OM) KpIPTOGpAFIQ NE TOLXKO PEpESTALA BYTX SEKpETNYM SWODOM PpIEMOW [IFpOWANIQ/DE[IFpOWANIQ, NO I NA- ^ALA OFOpMLQTXSQ W NOWU@ MATEMATI^ESKU@ TEOpI@ I STALA OB_EKTOM INTENSIWNOGO MATEMATI^ESKOGO IZU^ENIQ.

ppEDLAGAEMAQ WNIMANI@ ^ITATELQ KNIGA | PpAKTI^ESKI PEpWAQ NA pUSSKOM QZYKE, POSWQ]ENNAQ CELIKOM MATEMATI^ESKIM WOPpOSAM KpIPTOGpAFII, | OBOB]AET POSLEDNIE (DO 1990 G.) DOSTIVENIQ W OBLASTI KpIPTOGpAFII I NAPISANA IZWESTNYM U^ENYM, DEJSTWITELXNYM ^LENOM fINSKOJ AKADEMII NAUK, PO^ETNYM DOKTOpOM NESKOLXKIH EWpOPEJSKIH UNIWEpSITETOW, PpOFESSOpOM uNIWEpSITETA tUpKU apTO sALOMAA. oN QWLQETSQ AWTOpOM NESKOLXKIH PpEWOSHODNYH MONOGpAFIJ I U^EBNIKOW, PEpEWEDENNYH NA MNOGIE QZYKI MIpA, W TOM ^ISLE I NA pUSSKIJ (a. sALOMAA. vEM^UVINY TEOpII FOpMALXNYH QZYKOW, | m.: mIp, 1986, 180 S.) I SWY[E STA STATEJ.

w PEpWOJ GLAWE DAETSQ OBZOp KLASSI^ESKIH KpIPTOSISTEM | OT SISTEMY cEZApQ DO KpIPTOSISTEMY DES (STANDApT [IFpOWANIQ DANNYH) | S MNOGO^ISLENNYMI I WESXMA POLEZNYMI PpIMEpAMI. oSNOWNOE SODEpVANIE KNIGI POSWQ]ENO KpIPTOSISTEMAM S OTKpYTYM KL@^OM (GL. 2{5). w GL. 6 pASSMATpIWA@TSQ KpIPTOGpAFI^ESKIE PpOTOKOLY, WOZMOVNO, NAIBOLEE WAVNYE W PpIKLADNOM OTNO[ENII WOPpOSY W KpIPTOGpAFII, OTKpYWA@]IE NOWU@ STpANICU W OBESPE^ENII ZA]ITY INFOpMACIONNYH POTOKOW W pAZLI^NYH KOMPX@TEpNYH SETQH.

ppEDSTAWLENIE \TOGO MATEpIALA S METODI^ESKOJ TO^KI ZpENIQ BEZUPpE^NO, TEKST KNIGI SODEpVIT MNOGO PpIMEpOW I MOVET POSLUVITX HOpO[IM U^EBNIKOM DLQ NA^INA@]IH IZU^ATX \TU NAUKU. iZLOVENIE WEDETSQ STpOGO, NO BEZ IZLI[NEGO FOpMALIZMA. sPECIALISTY PO KpIPTOGpAFII NAJDUT DLQ SEBQ NEKOTOpYE NOWYE pEZULXTATY.

HADE@SX, ^TO KNIGA PpIWLE^ET WNIMANIE [IpOKOJ MATEMATI^ESKOJ OB]ESTWENNOSTI K NOWOJ, BUpNO pAZWIWA@]EJSQ ZA pUBEVOM MATEMATI^E- SKOJ DISCIPLINE I STANET DOSTUPNOJ DLQ OTE^ESTWENNYH SPECIALISTOW PO MATEMATI^ESKIM METODAM OBESPE^ENIQ BEZOPASNOSTI I KONFIDENCIALXNOSTI KOMPX@TEpNOGO OB]ENIQ I KOMMUNIKACIJ W KOMPX@TEpNYH SETQH (W ^ASTNOSTI, ZA]ITA INFOpMACIONNYH POTOKOW W BANKOWSKIH SETQH,

6

oT pEDAKTOpOW PEpEWODA

WSISTEMAH GOLOSOWANIQ PpI OpGANIZACII WYBOpOW S ISPOLXZOWANIEM KOMPX@TEpOW I T.D.).

gLAWY 1, 2, 4, 5 PEpEWEDENY NA pUSSKIJ QZYK i. a. wIHLQNCEWYM, GL. 3, 6 I PpILOVENIQ | a. a. bOLOTOWYM. kOMPX@TEpNYE WEpSTKA I NABOp

WSISTEME LaTEX OSU]ESTWLENY i. a. wIHLQNCEWYM.

w ZAKL@^ENIE POLXZU@SX WOZMOVNOSTX@ WYpAZITX GLUBOKU@ BLAGODApNOSTX I ISKpENN@@ PpIZNATELXNOSTX AWTOpU, PpOQWIW[EMU BESKOpYSTNYJ INTEpES I WNIMANIE K pUSSKOMU IZDANI@ SWOEJ KNIGI.

a. a. bOLOTOW, a. e. aNDpEEW

pAMQTI MOEJ SESTpY sIpKKI sALOMAA 1919{1989

ppEDISLOWIE

kpIPTOGpAFIQ, ILI TAJNOPISX, WEpOQTNO, TAK VE STApA, KAK I PISXMENNOSTX W CELOM. HO LI[X W POSLEDNEE WpEMQ ONA STALA OB_EKTOM [IpOKOMAS[TABNYH NAU^NYH ISSLEDOWANIJ. oDNOJ IZ PpI^IN \TOGO POSLUVILO BOLX[OE ^ISLO NOWYH PpILOVENIJ W OBLASTI ZA]ITY INFOpMACII. wOZMOVNO, DAVE BOLEE WAVNOJ PpI^INOJ OGpOMNOGO pOSTA NAU^NYH ISSLEDOWANIJ W KpIPTOGpAFII QWILASX PLODOTWOpNAQ IDEQ KpIPTOGpAFII S OTKpYTYM KL@^OM, SOZDAW[AQ NOWYE PEpSPEKTIWY I WOZMOVNOSTI W OBMENE INFOpMACIEJ.

|TA KNIGA PpEDSTAWLQET SOBOJ WZGLQD NA KpIPTOGpAFI@ S OTKpYTYM KL@^OM S POZICIJ KLASSI^ESKOJ KpIPTOGpAFII. w KNIGE BYLA SDELANA POPYTKA PpEDSTAWITX NEKOTOpYE IZ SAMYH SOWpEMENNYH DOSTIVENIJ I pEZULXTATOW. ppIWODIMYE W PpIMEpAH DLQ [IFpOWANIQ TEKSTY SOSTAWLQ@T PAKET OSNOWNYH SWEDENIJ O SAUNE.

bLAGODApNOSTI. Hermann Maurer W KONCE SEMIDESQTYH GODOW PpOBUDIL MOJ INTEpES K KpIPTOGpAFII. s 1983 G. Q ISPOLXZOWAL NESKOLXKO WEpSIJ \TOJ KNIGI W KUpSAH KpIPTOGpAFII W uNIWEpSITETAH tUpKU I lEJDENA, A TAKVE W tEHNI^ESKOM UNIWEpSITETE wENY. zAME^ANIQ SLU[ATELEJ \TIH KUpSOW BYLI POLEZNYMI. Juha Honkala, Jarkko Kari, Valtteri Niemi, Lila S^antean, Mika Niemi I Ari Renvall KpITI^ESKI PpO-

^ITALI pAZLI^NYE ^ASTI pUKOPISI, A PEpWYE ^ETWEpO WNESLI TAKVE SWOJ WKLAD W MNOGO^ISLENNYE OBSUVDENIQ. dLQ MENQ TAKVE POLEZ-

NYMI BYLI OBSUVDENIQ S Ron Book, Wilfried Brauer, Karel Culik, Ferenc G¶ecseg, Jozef Gruska, Tero Harju, Iiro Honkala, Helmut JÄurgensen, Juhani KarhumÄaki, Werner Kuich, Hannu Nurmi, Kaisa Nyberg, Azaria Paz, Grzegorz Rozenberg, Kai Salomaa, Aimo TietÄavÄainen, Emo Welzl, Derick Wood I Sheng Yu. oSOBOJ BLAGODApNOSTI ZASLUVIWAET Elisa Mikkola ZA OTLI^NYJ NABOp pUKOPISI, A TAKVE ZA POMO]X W pAZLI^NYH PpAKTI- ^ESKIH WOPpOSAH. Anu HeinimÄaki NApISOWALA pISUNKI. aKADEMIQ NAUK fINLQNDII PpEDOSTAWILA MNE BLAGOPpIQNYE USLOWIQ DLQ pABOTY. pOLEZNOE SOTpUDNI^ESTWO S SOTpUDNIKAMI AKADEMII, OSOBENNO S Marjatta

8

NÄaÄatÄanen, ZASLUVIWAET ISKpENNEJ PpIZNATELXNOSTI. HAU^NAQ OpGANIZACIQ MATINE PODDEpVALA MOI ISSLEDOWANIQ W KpIPTOGpAFII. HAKONEC, Q HOTEL BY POBLAGODApITX IZDATELXSTWO Springer-Verlag I OSOBENNO DOK-

TOpA Hans WÄossner I Mrs. Ingeborg Mayer ZA HOpO[EE WZAIMODEJSTWIE I OPEpATIWNOSTX IZDANIQ KNIGI.

tUpKU, mAJ 1990

apTO sALOMAA

gLAWA 1

kLASSI^ESKAQ KRIPTOGRAFIQ

1.1. kRIPTOSISTEMY I KRIPTOANALIZ

nAUKA I ISKUSSTWO KRIPTOGRAFII IME@T DWE STORONY. sU]ESTWUET MIR LEGALXNYH KOMMUNIKACIJ, ^ASTX@ KOTOROGO QWLQ@TSQ, K PRIMERU, LEGALXNYE POLXZOWATELI BANKOWSKIH I BIRVEWYH SOOB]ENIJ. |TOT MIR MOVNO RASSMATRIWATX KAK OTKRYTYJ I ZALITYJ SOLNE^NYM SWETOM. oDNAKO SU]ESTWUET I TEMNYJ MIR WRAGA, PRIBEGA@]EGO KO WSEWOZMOVNYM ZAPRE]ENNYM PRIEMAM. i ESLI L@DI LEGALXNOGO MIpA HOTQT, ^TOBY WpAG KAK MOVNO MENX[E PONIMAL SODEpVANIE IH SOOB]ENIJ, TO WpAGU, NAPpOTIW, NpAWITSQ IMETX DELO S POSLANIQMI, KOTOpYE LEGKO pAS[IFpOWATX.

kRIPTOGRAFIQ | \TO PRODOLVENIE BORXBY MEVDU DWUMQ MIRAMI. HEOBHODIMOSTX RAZRABOTKI BOLEE SILXNYH METODOW W LEGALXNOM MIRE PpODIKTOWANA USPEHAMI WpAGOW I OZNA^AET W SWO@ O^EREDX NOWYJ WYZOW W IH ADpES. tAKIM OBRAZOM, BORXBA PRODOLVAETSQ.

kAK PREDSTAWLENY DWA \TIH MIRA W KNIGE? ~TO KASAETSQ PRO[LOGO, TO TUT NIKAKIH TRUDNOSTEJ NET. sNA^ALA OPISYWAETSQ METOD LEGALXNOGO MIRA I ZATEM OB_QSNQETSQ, KAK WRAG PREDPRINQL USPE[NU@ ATAKU. sEGODNQ VE SITUACIQ W KORNE MENQETSQ. wSQKIJ RAZ, KOGDA OPISYWAETSQ USPE[NAQ WRAVESKAQ ATAKA, MY DOLVNY PRIZNATX, ^TO SOOTWETSTWU@]IE METODY LEGALXNOGO MIRA WSE VE NE BYLI NADEVNYMI. nELXZQ DOSTIGNUTX USPEHA ODNOWREMENNO W OBOIH MIRAH.

mOVNO DEJSTWOWATX SLEDU@]IM OBRAZOM: SNA^ALA W DETALQH DATX

10

gLAWA 1. kLASSIˆESKAQ KRIPTOGRAFIQ

METOD DLQ LEGALXNOGO MIRA, ZATEM W OB]IH ^ERTAH NABROSATX NEKOTORYE WOZMOVNYE WARIANTY WRAVESKIH ATAK, PRI \TOM ODNOWREMENNO POQSNITX, PO^EMU \TI ATAKI SKOREE WSEGO NE BUDUT IMETX USPEHA. |TO, KONE^NO, NE ISKL@^AET WOZMOVNOGO TpIUMFA NEKOTORYH DRUGIH, MOVET BYTX O^ENX IZOBRETATELXNYH, WRAVESKIH ATAK. tAK ILI INA^E, DALEE W KNIGE ISPOLXZUETSQ DANNYJ PODHOD. wEROQTNOSTX BEZOPASNOSTI METODOW ^ASTO QWLQETSQ O^ENX WYSOKOJ, HOTQ MATEMATI^ESKI \TO NE WSEGDA MOVNO DOKAZATX.

sLEDU@]EE ZAME^ANIE PpIMENIMO K OBOIM MIpAM. hOTQ MY NAZYWAEM IH \LEGALXNYJ" I \TEMNYJ", \TO NE WSEGDA OZNA^AET, ^TO PERWYE | \HORO[IE PARNI", A POSLEDNIE | IZ mORDORA, GDE VIWET sAURON1. w RAZLI^NYH SITUACIQH ROLI MOGUT MENQTXSQ. nAPRIMER, PEREHWAT SOOB- ]ENIJ MOVET PRIMENQTXSQ NA[EJ STRANOJ WO WREMQ WOJNY, TOGDA KAK POSLANIQMI OBMENIWALSQ NA[ WRAG. kONE^NO, SPRAWEDLIWOSTX NA NA[EJ STORONE! iLI DpUGOJ PpIMEp: LEGALXNYE POLXZOWATELI BANKA MOGUT BYTX PRESTUPNIKAMI, A POLICIQ DOLVNA RASSLEDOWATX IH DEJSTWIQ. tERMINOLOGIQ, WWEDENNAQ NIVE, BUDET BESPRISTRASTNOJ, T.E. NIKAKIH SUVDENIJ OTNOSITELXNO TOGO, KAKAQ IZ PROTIWOBORSTWU@]IH STORON PRAWA, MY DELATX NE BUDEM.

tEPERX MY GOTOWY WWESTI FUNDAMENTALXNYE PONQTIQ KRIPTOGRAFII. oNI BUDUT ISPOLXZOWATXSQ NA PROTQVENII WSEJ KNIGI. pOD^ERKNEM, ^TO TERMINOLOGIQ OTN@DX NE ODNOZNA^NA I FIKSIROWANA DLQ RAZLI^NYH OPISANIJ SEKRETNOGO PISXMA. pRI WWEDENII TERMINOLOGII MY ^ASTO BUDEM PRIWODITX I DRUGIE OBOZNA^ENIQ TEH VE PONQTIJ, ISPOLXZUEMYH NEKOTORYMI DRUGIMI AWTORAMI.

nA[ WSEOB]IJ TERMIN DLQ SEKRETNOGO PISXMA | \TO KRIPTOGRAFIQ. oN DEJSTWITELEN DLQ OBOIH MIROW. nEKOTORYE AWTORY ISPOLXZU@T TERMIN KRIPTOLOGIQ W \TOM UNIWERSALXNOM SMYSLE I REZERWIRU@T TERMIN KRIPTOGRAFIQ DLQ DEQTELXNOSTI LEGALXNOGO MIRA.

oSNOWNAQ STRUKTURA IZOBRAVENA NA RIS. 1.1. sOOB]ENIE POSYLAETSQ PO NEZASEKpE^ENNOMU KANALU, GDE ONO MOVET BYTX PEREHWA^ENO S POMO- ]X@ PODSLU[IWANIQ.

kARTINA BUDET TOJ VE SAMOJ, GOWORIM LI MY, DOPUSTIM, O KONNOM KURXERE ILI \LEKTRONNOJ PO^TE. mY NE MOVEM OBESPE^ITX BEZOPASNOSTX KANALA, I, SLEDOWATELXNO, WOZMOVEN PEREHWAT. pERWOO^EREDNYE CELI WRAGA | NARU[ITX SEKRETNOSTX SWQZI I IZWLE^X WYGODU IZ TAJNOJ INFORMACII. dALEKO IDU]IE CELI MOGUT SOSTOQTX W SLEDU@]EM. wOPEpWYH, WRAG MOVET ZAHOTETX IZMENITX SOOB]ENIE, ZAPUTAW PRI \TOM POLU^ATELQ NEDOSTOWEpNYM TEKSTOM, A WO-WTOpYH, WRAG MOVET OBMANUTX POLU^ATELQ, NAZWAW IMQ LOVNOGO OTPRAWITELQ.

1pERSONAV ROMANA dV.r.r.tOLKIENA \wLASTELIN KOLEC". | pRIM. PEREW.