[PDF] A Method for Obtaining Digital Signatures and Public-Key

View - Download A Method for Obtaining Digital Signatures and Public-Key

Previous PDF

Next PDF

AMethodforObtainingDigital

SignaturesandPublic-KeyCryptosystems

R.L.Rivest,A.Shamir,andL.Adleman

Abstract

key.Thishastwoimportantconsequences: knowsthecorrespondingdecryptionkey.

CRCategories:2.12,3.15,3.50,3.81,5.25

IIntroduction

Di ffi

IIPublic-KeyCryptosystems

D(E(M)=M.(1)

(b)BothEandDareeasytocompute. computeDefficiently. mally,

E(D(M)=M.(2)

thekey. isimpractical. 2 decryptionprocedureswithsubscripts:E A ,D A ,E B ,D B

IIIPrivacy

himsincehedoesnotknowhowtodecryptit. communicationschannel.

First,heretrievesE

A E A (M).AlicedeciphersthemessagebycomputingD A (E A (M))=M.Byproperty A (M).Shecanenciphera 3 privateresponsewithEB ,alsoavailableinthepublicfile. file.

IVSignatures

sender. B S=D B (M). 4 encryptsSusingE A (forprivacy),andsendstheresultE A (S)toAlice.Heneednot sendMaswell;itcanbecomputedfromS.

AlicefirstdecryptstheciphertextwithD

A toobtainS.Sheknowswhoisthe ofthesender,inthiscaseE B (availableonthepublicfile): M=E B (S). ofasignedpaperdocument. createdS=D B (M).Alicecanconvincea"judge"thatE B (S)=M,soshehasproof thatBobsignedthedocument. ,sincethenshewould havetocreatethecorrespondingsignatureS =D B (M )aswell. othermessage.) theencryptiondevicebeforetransmission. subroutine"thatcanbeexecutedasneeded. encryptionalgorithmE PF .Theproblemof"lookingup"E PF itselfinthepublicfile isavoidedbygivingeachuseradescriptionofE PF whenhefirstshowsup(inperson) 5

VOurEncryptionandDecryptionMethods

e isdividedbyn.

C≡E(M)≡M

e (modn),foramessageM.

D(C)≡C

d (modn),foraciphertextC. shouldproperlybesubscriptedasinn A ,e A ,andd A ,sinceeachuserhashisownset. ourmethod? n=p·q. di ffi gcd(d,(p-1)·(q-1))=1 ("gcd"means"greatestcommondivisor"). 6 ofd,modulo(p-1)·(q-1).Thuswehave e·d≡1(mod(p-1)·(q-1)). canbedoneefficiently. moduloaprimenumber.

VITheUnderlyingMathematics

M

φ(n)

≡1(modn).(3)

φ(p)=p-1.

φ(n)=φ(p)·φ(q)

=(p-1)·(q-1)(4) =n-(p+q)+1. integersmoduloφ(n): e·d≡1(modφ(n)).(5) correctlyifeanddarechosenasabove).Now

D(E(M))≡(E(M))

d ≡(M e d (modn)=M e·d (modn)

E(D(M))≡(D(M))

e ≡(M d e (modn)=M e·d (modn) and M e·d ≡M k·φ(n)+1 (modn)(forsomeintegerk). 7 M p-1 ≡1(modp) andsince(p-1)dividesφ(n) M k·φ(n)+1 ≡M(modp). allM.Arguingsimilarlyforqyields M k·φ(n)+1 ≡M(modq). M e·d ≡M k·φ(n)+1 ≡M(modn). oftheauthors'previousproof.)

VIIAlgorithms

requiredoperation.

AHowtoEncryptandDecryptEfficiently

ComputingM

e (modn)requiresatmost2·log 2 (e)multiplicationsand2·log 2 (e) dinsteadofe):

Step1.Lete

k e k-1 ...e 1 e 0 bethebinaryrepresentationofe.

Step2.SetthevariableCto1.

Step3a.SetCtotheremainderofC

2 whendividedbyn.

Step3b.Ife

i

Step4.Halt.NowCistheencryptedformofM.

Knuth[3]studiesthisproblemindetail.

integratedcircuitchips.) 8

BHowtoFindLargePrimeNumbers

numberspandq,sothatnhas200digits. (ln10 100
gcd(a,b)=1andJ(a,b)=a (b-1)/2 (modb),(6) onein2 100

J(a,b)=ifa=1then1else

ifaiseventhenJ(a/2,b)·(-1) (b 2 -1)/8 elseJ(b(moda),a)·(-1) (a-1)·(b-1)/4 e ffi checked. 9

CHowtoChoosed

DHowtoComputeefromdandφ(n)

gcd(φ(n),d)bycomputingaseriesx 0 ,x 1 ,x 2 ,...,wherex 0 ≡φ(n),x 1 =d,andx i+1 x i-1 (modx i ),untilanx k equalto0isfound.Thengcd(x 0 ,x 1 )=x k-1 .Compute foreachx i numbersa i andb i suchthatx i =a i ·x 0 +b i ·x 1 .Ifx k-1 =1thenb k-1 isthemultiplicativeinverseofx 1 (modx 0 ).Sincekwillbelessthan2log 2 (n),this computationisveryrapid.

Ifeturnsouttobelessthanlog

2 (n),startoverbychoosinganothervalueofd. some"wrap-around"(reductionmodulon).

VIIIASmallExample

x 0 =2668,a 0 =1,b 0 =0, x 1 =157,a 1 =0,b 1 =1, x 2 =156,a 2 =1,b 2 =-16(since2668=157·16+156), x 3 =1,a 3 =-1,b 3 =17(since157=1·156+1).

ITSALLGREEKTOME

0920190001121200071805051100201500130500

M 17 =(((((1) 2

·M)

2 2 2 2

·M=948(mod2773).

10

Thewholemessageisencipheredas:

157
≡920(mod2773),etc.

IXSecurityoftheMethod:CryptanalyticAp-

proaches concerningthesecurityoftheNBSmethod[2].)

AFactoringn

factorsanumbernintimeO(n 1/4 exp ln(n)·ln(ln(n))=n⎷ lnln(n)/ln(n) 11 =(ln(n))⎷ ln(n)/ln(ln(n)) digits).

Table1

DigitsNumberofoperationsTime

501.4×10

10

3.9hours

759.0×10

12

104days

1002.3×10

15

74years

2001.2×10

23

3.8×10

9 years

3001.5×10

29

4.9×10

15 yearsquotesdbs_dbs12.pdfusesText_18

[PDF] a method for obtaining digital signatures and public key cryptosystems bibtex

[PDF] a method for obtaining digital signatures and public key cryptosystems pdf

[PDF] a method for stochastic optimization adam

[PDF] a method for stochastic optimization kingma

[PDF] a method is executed when it is called

[PDF] a method that calls itself is an iterative method

[PDF] a method that calls itself is referred to as a(n)

[PDF] a methods signature consists of quizlet

[PDF] a million little things cast elliot

[PDF] a million little things cast john

[PDF] a million little things cast pj

[PDF] a million little things cast season 2 episode 16

[PDF] a million little things next air date

[PDF] a million little things next episode air date

[PDF] a million little things next episode preview