非对称密码

非对称密码概论、RSA密码、ELGamal密码等Limitations in Symmetric CipherSender and receiver must share the samekeyKey distributionFind secure channelsOther limitation of authentication schemeDoes not have non-repudiationAsymmetric CryptographyACiphertextBPlaintext- EncryptionDecryption +PlaintextKEEvery one know the Ke can encrypt the messageKE can be publishedPublic KeyOnly b know the Kp can decrypt the messagep must keep secretPrivate KePublic Key CryptographyNeed the mathematical insideSeem strangeUntil 1976. Diffie hellman New Directions inCryptographypublic-key encryption schemespublic-key distribution systems(Diffie-Hellman key agreementprotocol)digital signaturea few years later the first system was invented, i. e. RSaThe most meaningful achievement in cryptographyfor thousand years5Formal analysisEncrypt rule ek is publicDecrypt rule dk is privateEvery one(know ex)can encrypt using ekOnly the one hold dk can decryptThe properties of two rules ek and aKalexx))=Xdk is the inverse of ekdk is very difficult to calculate by known ekOne-way FunctionOne-way function FFor all x∈×, it is easy(P- problem) to compute F(xFor almost all y∈Y, findinga X∈ X With F(X)=yiscomputationally difficult, i.e. compute f-1 is verydifficult(may be a NPc-problem)EXample: Factoring ProblemGiven primes p and g, computer= pqThis is very easy to compute, since we just multiply p and qThe inverse problem: given N find p and gTrapdoor One-way FunctionOne-way is insufficientTrapdoor is neededThe one know the trapdoor information caneasily calculate the f-1(P problem)Y=f(X): easydomaintargetX=f-1(Y): Computationally infeasibleX=fK: 1(Y): easy if trap-door K is knownProblems in CryptographyThe Factoring ProblemQuadratic Residues ProblemThe Discrete Logarithm ProblemIn elliptic curvesKnapsack ProblemChapter 6 Asymmetric CryptographyAsymmetric Cryptography OverviewRSA CryptographyELGamal CryptographyElliptic Curve CryptographyRabin CryptographyKnapsack Cryptography10