中国矿业大学：密码学_Outline

Outline 曹天杰 Tianie cao ticao(cumt. edu. cn College of Computer science and echnology, China University of Mining and Technology Xuzhou china 中国矿业大学计算机科学与技术学院 2003.6.16

曹天杰 Tianjie Cao tjcao@cumt.edu.cn College of Computer Science and Technology, China University of Mining and Technology, Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.6.16 Outline

Attacks. Services. and mechanisms Security Attack: Any action that compromises the security of information Security Mechanism: A mechanism that is designed to detect, prevent, or recover from a security attack Security service: A service that enhances the security of data processing systems and information transfers. A security service makes use of one or more security mechanisms

Attacks, Services, and Mechanisms * Security Attack: Any action that compromises the security of information. * Security Mechanism: A mechanism that is designed to detect, prevent, or recover from a security attack. * Security Service: A service that enhances the security of data processing systems and information transfers. A security service makes use of one or more security mechanisms

Cryptosystem A cryptosystem is a five -tuple(P, C, K, E, D) where the following conditions are satisfied 1. P is a finite set of possible plain texts 2.C is a finite set of possible ciphertexts 3. K, the keyspace, is a finite set of possible keys 4. For each kEK, there is an encryption rule K Ee and a corresponding decryption rule dk∈D. Each eK:P→ C and dk:C→>Pare functions such that dek x))= x for every plaintext X∈P

Cryptosystem • A cryptosystem is a five -tuple (P, C, K, E, D), where the following conditions are satisfied: • 1. P is a finite set of possible plain texts • 2. C is a finite set of possible ciphertexts • 3. K, the keyspace, is a finite set of possible keys • 4. For each kK, there is an encryption rule eK  E. and a corresponding decryption rule dK  D). Each eK : P → C and dK : C → P are functions such that dK(eK(x)) = x for every plaintext x  P

Taxonomy of cryptographic primitives Arbitrary length hash functions Unkeyed Primitives One-way permutations Random sequences Block cIphers Symmetric-key ciphers Stream aRbitrary length hash functions(MACs) cIphers Securit Primitives ymmetrIc-key Primitives Signatures Pseudorandom sequences Identification primitives Public-key ciphers Public-key Primitives Signatur Identification primitives

Taxonomy of cryptographic primitives. Arbitrary length hash functions One-way permutations Random sequences Symmetric-key ciphers Arbitrary length hash functions(MACs) Signatures Pseudorandom sequences Identification primitives Public-key ciphers Signatures Identification primitives Unkeyed Primitives Symmetric-key Primitives Public-key Primitives Security Primitives Block ciphers Stream ciphers

Background on Functions(ctd) one-way function if f(x)is easy to compute for all X E X, but it is computationally infeasible to find anyE X such that f(x) trapdoor one-way function if given trapdoor information, it becomes feasible to find an X E X such that f(x)=y

Background on Functions (ctd) • one-way function if – f(x) is easy to compute for all x  X, but – it is computationally infeasible to find any x  X such that f(x) =y. • trapdoor one-way function if – given trapdoor information, it becomes feasible to find an x  X such that f(x) =y

Cryptanalysis- Types of Attacks Ciphertext-Only Attack Attacker knows ciphertext of several messages encrypted with the same key and/or several keys Recover the plaintext of as many messages as possible or even better deduce the key(or keys) Given: CI=EK(PD, C2=EK(P2),C=Ek(P Deduce: Either P, P,,P k; or an algorithm to intel from Ci+= EkPi+v Known-Plaintext Attack Known ciphertext plaintext pair of several messages Deduce the key or an algorithm to decrypt further messages Given Pl, C- Ek(P), P2, C2- Ek(P Ek(P) Deduce: Either k, or an algorithm to infer Pi+i from Ek(P

Cryptanalysis - Types of Attacks • Ciphertext-Only Attack – Attacker knows ciphertext of several messages encrypted with the same key and/or several keys – Recover the plaintext of as many messages as possible or even better deduce the key (or keys) – Given: C1 = Ek (P1 ), C2 = Ek (P2 ),...Ci = Ek (Pi ) Deduce: Either P1 , P2 ,...Pi ; k; or an algorithm to infer Pi+1 from Ci+1 = Ek (Pi+1) • Known-Plaintext Attack – Known ciphertext / plaintext pair of several messages – Deduce the key or an algorithm to decrypt further messages – Given: P1 , C1 = Ek (P1 ), P2 , C2 = Ek (P2 ),...Pi , Ci = Ek (Pi ) – Deduce: Either k, or an algorithm to infer Pi+1 from Ci+1 = Ek (Pi+1)

Cryptanalysis Types of Attacks Chosen-Plaintext Attack Attacker can choose the plaintext that gets encrypted thereby potentially getting more information about the key Given: P,C= Ek(PD, P2,C2=(P2P, Ci=Ek(PV, where the cryptanalyst gets to choose Ppo r 2 Deduce: Either k, or an algorithm to infer Pi+, from Ek(P It Adaptive chosen-Plaintext Attack Attacker can choose a series of plaintexts, basing choice on the result of previous encryption >differential cryptanalysis Chosen-ciphertext attack Given: Cl, PI=DK(C1, C2, P2=DK(C2),Ci, P=DKC educe k

Cryptanalysis - Types of Attacks • Chosen-Plaintext Attack – Attacker can choose the plaintext that gets encrypted thereby potentially getting more information about the key – Given: P1 , C1 = Ek (P1 ), P2 , C2 = Ek (P2 ),...Pi , Ci = Ek (Pi ), where the cryptanalyst gets to choose P1 , P2 ,...Pi Deduce: Either k, or an algorithm to infer Pi+1 from Ci+1 = Ek (Pi+1) • Adaptive Chosen-Plaintext Attack – Attacker can choose a series of plaintexts, basing choice on the result of previous encryption → differential cryptanalysis! • Chosen-ciphertext attack – Given: C1 , P1 = Dk (C1 ), C2 , P2 = Dk (C2 ),...Ci , Pi = Dk (Ci ) – Deduce: k

Models for evaluating security Unconditional security(perfect secrecy Adversaries have unlimited computational resources Observation of the ciphertext provides no information to an adversary d One time pac Complexity-theoretic security Adversaries have polynomial computational power Asymptotic analysis and usually also worst-case analysis is used Provable security provably secure if the difficulty of defeating crypto system can be shown to be as difficult as solving a well-known number-theoretic problem

Models for evaluating security • Unconditional security (perfect secrecy) – Adversaries have unlimited computational resources – Observation of the ciphertext provides no information to an adversary – One time pad • Complexity-theoretic security – Adversaries have polynomial computational power. – Asymptotic analysis and usually also worst-case analysis is used • Provable security – provably secure if the difficulty of defeating crypto system can be shown to be as difficult as solving a well-known number-theoretic problem

Models for evaluating security (ctd) Computational security(Practical security) We might define a cryptosystem to be computationally secure if the best algorithm for breaking it requires at least N operations, where n is some specified, very large number The problem is that no known practical cryptosystem can be proved to be secure under this definition neither the Shift Cipher, the Substitution Cipher nor the Vigenke Cipher is computationally secure against a ciphertext-only attack(given a sufficient amount of ciphertext) Ad hoc security(heuristic security) any variety of convincing computational security unforeseen attacks may remain

Models for evaluating security (ctd) • Computational security (Practical security) – We might define a cryptosystem to be computationally secure if the best algorithm for breaking it requires at least N operations, where N is some specified, very large number. – The problem is that no known practical cryptosystem can be proved to be secure under this definition. – neither the Shift Cipher, the Substitution Cipher nor the Vigenke Cipher is computationally secure against a ciphertext-only attack (given a sufficient amount of ciphertext). • Ad hoc security (heuristic security) – any variety of convincing computational security – unforeseen attacks may remain

Shannon's definition of perfect Secrecy The One-Time Pad Ek(m=mok ciphertext C One-Time ad k bits of random key K use random key sequence only once and then discard it 1001101010 1101000111

Shannon‘s Definition of Perfect Secrecy m ciphertext C One-Time Pad k bits of random key K 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 0 1 0 0 0 1 1 1 use random key sequence only once and then discard it ! The One-Time Pad Ek (m) = m  k k