CS代考 Asymmetric Cryptography

Asymmetric Cryptography
SFL @ TU Dortmund

From Symmetric to Asymmetric Cryptography

Copyright By PowCoder代写 加微信 powcoder

• Flashback: Last week, we introduced symmetric cryptography (one-time pads, AES, mode of operations, MACs) and hash functions
plaintext ciphertext
….. …..
….. ….
ciphertext plaintext
(encryption) (decryption)
Cryptographic Algorithm
Symmetric Key Cryptography (a.k.a. private-key crypto)
• Same key used for encrypting and decrypting a message
• Single key needs to be shared among communication partners
• Usually computationally fast
Asymmetric Cryptography
(a.k.a. public-key crypto)
• Uses pairs of keys (public key for encr., and private key for decr.)
• Public keys can be disseminated to everyone→easy distribution
• Usually computationally slow

Confidentiality in Public-Key Crypto

Public Key Cryptography: Key Exchange
• Private-key crypto requires secret key between communication pairs • Number of keys: n(n-1)/2
• Q1: How can we securely exchange symmetric keys?
• Q2: Can we gain the same security guarantees without symmetric keys?

Chlod- wig

Edel- traud
• Public key crypto solves this problem by concepts introduced by W. Diffie and M. Hellman (in 1976!)
Gott- fried
Frid- bert

Public Key Cryptography: Key Exchange
• How can the parties exchange shared key in the first place?
• Exchanging keys over secure out-of-bound channel (e.g., phone) is infeasible • Exchanging keys in public let adversaries spy on keys
• General idea of key exchange
• Derive secret key from publicly exchanged information

Towards Key Exchange: Merkle’s Puzzle (1/2)
• Basic Idea of Merkle’s Puzzle
1. A sends B m weakly-encrypted puzzles p1..m = {(Ii, Si)}Wi
(weak Wi and strong keys Si are unique keys, i.e., they differ per puzzle)
2. Bruteforcing all puzzles takes long, but solving one is doable by brute force:
B solves any randomly-chosen puzzle pj by guessing Wj (and obtains Sj)
3. B sends Ii to A to tell which puzzle he cracked; j has to remain secret
4. Ii identifies strong symmetric key Si, which is used as key from now on

p1..m = {(Ii, Si)}Wi
bruteforce pj Ij
{}k : Encryption under key k
Wi: Weak keys (n bits)
Si: Strong keys (>> n bits)
Ii: Puzzle (and key) identifier
j: randomly-chosen puzzle index
Merkle, R. C. (1978): “Secure Communications over Insecure Channels”. Communications of the ACM. (discovered in 19674)

Merkle’s Bruteforce Success
• How can Bob determine if he successfully bruteforced a key (and thus the key is correct)?
A: Decryption attempts with wrong keys fail.
B: Decryption with the correct keys takes longer than with wrong keys.
C: The „correct“ plaintext message contains a well-known constant value.

Merkle’s Key Index
• Can Bob also share the key index j (i.e., the index of the
puzzle that he chose) and not just the key identifier Ii?
A: Yeah, j is a similarly good identifier as Ii.
B: Yes, but sending both j and Ii creates unnecessary overhead.
C: No!!! Please. Just. Don‘t.

Towards Key Exchange: Merkle’s Puzzle (2/2)
• Security analysis
• Assumption: N attempts required to break a single puzzle Wj
• Complexity for B is O(N), for attacker O(N * m)
– B just has to solve one puzzle
– Attacker has to solve 50% of the puzzles (on average) or all puzzles (worst case) • Such a (small) complexity does not give sufficient security guarantees • Larger m are costly, as puzzles have to be transferred
• Still, Merkle‘s ideas have advanced key exchange research
Merkle, R. C. (1978): “Secure Communications over Insecure Channels”. Communications of the ACM. (discovered in 1974)

Excursion: Modular Arithmetic (Part 1)
• Modulo (mod) is the remainder of the division of two values
• x mod n means the remainder when dividing x by n
• Example: 12 mod 10 = 2 (sometimes also written as 12 ≡ 10 (mod 2))
• General modular arithmetic rules:
• (a + b) mod n = ((a mod n) + (b mod n)) mod n
• (a – b) mod n = ((a mod n) – (b mod n)) mod n
• (a * b) mod n = ((a mod n) * (b mod n)) mod n
• (ax)y mod n = ((ax mod n)y mod n = axy mod n
• (a * (b + c)) mod n = (((a * b) mod n) + ((a * c) mod n)) mod n

Diffie- Exchange (1/2)
模幂(英语:modular exponentiation)是一种对模进行的幂运算,在计算机科学,尤其是公开密钥加 密方面有一定用途。 模幂运算是指求整数b的e次方b^e被正整数m所除得到的余数c的过程,可用数学符号表示为c = b^e mod m。由c的定义可得0 ≤ c < m。例如,给定b = 5,e = 3和m = 13,53 = 125被13除得的余数c = 8。 • Basic idea of DHKE • Partners agree on (public) modular exponentiation base g and divisor p • Partners chose each one private exponent for modular exponentiation (x, y) • Partners exchange exponentiation results (not the exponents!) • Common group element becomes the key (Yx mod p == Xy mod p) X = gx mod p Y = gy mod p k = Yx mod p k = Xy mod p public number (base) large public prime secret large numbers Yx mod p == Xy mod p Yx mod p == Xy mod p (gy mod p)x mod p == (gx mod p)y mod p gyx modp==gxy modp Diffie, W. and Hellmann, M.: „ in Cryptography“, IEEE Transactions on Information Theory, 1976. 11 Diffie- Exchange (2/2) 互质 是公约数只有1的两个整数。 如果一个整数同时是几个整数的约数,称这 个整数为它们的“公约数”;公约数中最大的 称为最大公约数。 约数,又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数,我们就 说a能被b整除,或b能整除a。a称为b的倍 数,b称为a的约数。 • Security Analysis • Modular exponentiation (gx mod p) is cheap to compute - Using Euler‘s Theorem or Square-and-Multiply • Discrete logarithm (inverse) is hard to compute - In our case, the discrete logarithm needs to find x such that gx mod p = X - Practically impossible to inverse modular exponentiation on large numbers →Modular exponentiation is1 a one way function (1unless somebody finds a practical algorithm to compute discrete logarithm) →Hardness of Diffie-Hellman ≈ Hardness of discrete logarithm phi(n): 0到n之间,与n互质 (互素)的正整数的数量 Person-in-the-Middle Attack Against DHKE • Person-in-the-Middle can observe, drop, alter and insert messages • PITM places itself between Alice and Bob and performs two key exchanges • KeyexchangebetweenA↔MandM↔B • Alice and Bob cannot authenticate each other and trust the key exchanges X = gx mod p Y’=gy’ modp k’=Y’x modp k’=Xy’ modp Z = gz mod p Y = gy mod p k’’=Yz modp k’’=Zy modp • Extend DHKE with signatures to withstand this attack Public Key Cryptography: Encryption • Alternatively to exchanging keys, we can use public-key encryption • Removes need to exchange keys per pair Edel- traud Frid- bert Public Key Cryptography: Encryption • New paradigm: Communicating parties advertise some PUBLIC INFORMATION that allow anyone to securely communicate with them • Each partner creates a key pair • Private key (K-) is kept secret • Public key (K+) is known to others • En-/decryption approach: • Encrypt with public key • Decrypt with private key • {{m}K+}K- = m Edel- traud - Frid- From Diffie- Encryption • The essentials of use DHKE basics Encrypt |m| ≤ |p| Standard DHKE g: public number (base) p: large public prime x, y: secret large numbers X = gx mod p Y = gy mod p k = Yx mod p c = (m * k) mod p m = (c / k) mod p Decryption Encryption • Textbook scheme x, y: kM: kE: public number (base) large public prime secret large numbers message/session key ephemeral public key Y = gy mod p kM =Yx modp kE =gx modp c = (m * kM) mod p, kE kM =kEy modp m = (c / kM) mod p Encrypt |m| ≤ |p| Decryption RSA – Encryption and Decryption (1/3) • RSA: Public-key crypto system by Rivest, Shamir and Adleman • Public key is number pair (e, n) • Private key is number pair (d, n), where d is the multiplicative inverse of e • n is RSA modulus • En- and decryption via modular arithmetic Encryption: encrypt m (with m < n) by modular exponentiation with e Decryption: decrypt c by modular exp. with multiplicative inverse d In other words: e*d mod z = 1 (we will define z on the next slide) e: public key exponent d: private key exponent m: message c: ciphertext c = me mod n m = cd mod n RSA – Encryption and Decryption (2/3) • Modular multiplicative inverse x of a is where x*a mod u = 1 • Example for mod 10: 3 is inverse of 7 (and vice versa); 2, 4, 6, etc. have none • x exists if a is relatively prime to u, i.e., share no factors except 1 • φ(u) determines how many numbers are relatively prime to u (cf. Euler’s totient function) • RSA Key Generation • Choose two large prime numbers p and q • Compute n = pq and z = φ(n) = φ(pq) = φ(p)φ(q) = (p-1)(q-1) • Choose e < z that is relative prime to z (has no common factors with z) - e becomes part of the encryption key (public key) • Find d such that ed – 1 is exactly divisible by z (i.e., has no remainder) - Use extended Euclidean algorithm to find ed mod z = 1 - d becomes part of the decryption key (private key) Computing d (private key) • Can an attacker also compute d, knowing e and n? A: Yes, but that doesn‘t matter. B: No, the attacker doesn‘t know the primes p and q. C: No, since p and q are public, but very large known primes. Textbook RSA • Real RSA implementations add random padding to a message before encrypting it. Why? A: To fit the message to a certain block size (e.g., 512 bits) B: To avoid known-plaintext attacks. C: To avoid replay attacks. RSA – Encryption and Decryption (3/3) • RSA Complexity Analysis • RSA relies on the fact* that factorization (deriving p and q from n) is hard • p and q therefore have to be large primes and determine strength of key • Largest factorized RSA number is 829 bits; recommended to use >= 2048 bits • If attackers knew p and q (and e), they could easily derive d
• RSA Security Guarantees
• The provided textbook RSA scheme seems to provide confidentiality, but:
• RSA (w/o padding) is deterministic and thus prone to chosen plaintext attacks
• RSA (w/o padding) is susceptible to some chosen-ciphertext attacks – Basic idea follows this observation: m1e m2e = (m1 m2)e

Chosen-Plaintext Attack (CPA)
把 加密方法 看作黑盒:攻击者不知道key,但是能通过不同的input和对应 的output猜测出plaintext
• Threat model
• Attacker does not know the keys, but can use encryption as a black box
(encryption oracle) with arbitrary plaintext inputs
• Goal: Recognize known plaintext despite encryption, or learn key(s)
• Problematic if encryption results in deterministic output, i.e., generates identical output given identical inputs (e.g., keys, plaintext)
• Example:
m1 = “yes”, m2 = “no”
c1 = Fk(“yes”), c2 = Fk(“no”)
Do you want to marry me?
c = Fk(“no”)
c == c1? c == c2?

Chosen-Ciphertext Attack (CCA)
• Threat model
• Attacker does not know the keys, but can use decryption as a black box
(decryption oracle) with arbitrary ciphertext inputs • Goal: Derive key(s)
• Example, based on Caesar cipher (c := m + k mod 26) “ABC”, Bob
把 解密方法 看作黑盒:向通讯一方发送ciphertext,这一方解密 该ciphertext。攻击者通过截取解密后的plaintext,推测key。

Wait. What is “CDE” about?, Alice
k = “C”–“A” = “D”–“B” = “E”–“C” = 2
m = “CDE” F-1k

Hybrid Encryption (1/2)
• Public-key encryption looks powerful and easy!
• Why don’t we use public-key cryptography for everything?
• Number theoretic assumptions in general lead to constructions that are several order of magnitude less efficient than the corresponding schemes based on complexity assumptions (i.e., private-key setting)
• How do we keep the advantages of the public-key setting without sacrificing the efficiency of the scheme?

Hybrid Encryption (2/2)
• Solution: Use public-key encryption to exchange a private key that is then used to encrypt follow-up communication symmetrically
• This construction is called hybrid encryption and can be built on top of any two secure public-key and private-key encryption schemes
• Examples:
• TLS handshake uses public-key crypto (typically DHKE) to negotiate a
symmetric session key that is used to protect the TLS session
• OpenPGP email encryption uses public key of recipient to encrypt a symmetric session key that will be used to encrypt the email

Integrity in Public-Key Crypto

Digital Signatures
• Public-key signature schemes can seal and authenticate a message • Integrity: Message has not been tempered with
• Authenticity: Message sender is known and can be verified
• Basic idea: Use secret key for signing, and public key for verifying
Hello! Alice
t -~ ! Elice
Something is wrong!

RSA – Digital Signatures (1/2)
• RSA allows to sign a message m by encrypting H(m) with private key • Signing H(m) instead of m reduces overhead and is more secure (→next
• Only party that owns private key can generate such a signature
• Verification by decryption with public key
• This inverse of normal RSA en-/decryption allows for message signing
1. Create signature and send along with message to receiver
2. Recipient checks if message digest corresponds to decrypted signature
e: KA+ (public key of Alice)
d: KA- (private key of Alice) m: message
c: ciphertext
m, sig = H(m)d mod n H(m) =?= sige mod n
不再是使用收件人的公钥加密信息,而是用发件人的私钥进行加密。

RSA – Digital Signatures (2/2)
• Why signing H(m) and not m?
• Let an attacker observe signature s = {m}K- = mK- mod n
• It follows that m’ = mx can use signature s’ = sx = {m’}K-
• Example: If you sign the amount of a money transfer, attacker can square it • Such an attack is not possible with a cryptographic hash
• Other reasons to sign the hash digest:
1. Asymmetric cryptography is slow, so reduce length to encrypt
2. If m is too large, it does not fit into RSA modulus (m < n) 3. An attacker could easily derive the plaintext from the signature (by decrypting with K+, i.e., m = sK+) 意思是,可以生成一 个m‘,并使用已知的签名方 法,伪造出合法签名s’ Signatures • signature scheme: g: public number (base) p: large public prime y: public key of Alice e: private key of Alice k: signing key (relative prime to p-1) (a,b): signature long-term pubkey “session pubkey” y = ge mod p a = gk mod p b = (m – ea)k-1 mod (p-1) yaab modp==gm modp yaab mod p ≡ (ge)a (gk)b mod p ≡ (ge)a (gk)(m-ea)/k mod p-1 mod p // Hint#1 ≡ gea gk(m-ea)/k mod p ≡ gea gm-ea mod p ≡ gm mod p Hint #1: Fermat’s little theorem states that ap-1 = 1 (mod p), which allows us to simplify. yaab mod p =?= gm mod p Signature Verification Summary: Asymmetric Cryptography • Public keys can be disclosed to anyone, obsoleting key exchanges • Modular exponentiation is key enabler for public-key cryptography • Diffie- Exchange: Secure key exchange despite passive attackers • : Encrypt using a one-time key derived from a half-way DHKE • RSA: Encrypt using the multiplicative inverse of decrypting • Asymmetric cryptography usually derives a symmetric key for follow- up encryption (hybrid encryption) • Digital signatures provide integrity, authenticity and non-repudiation (and all of this is publicly verifiable!) Digital Signatures (pub-key) vs. MAC (private-key) • We have studied MACs and seen that they provide integrity: Why do we need digital signatures then? • Public verifiability: Everybody can verify the signature • Public keys of sender verify a signature (instead of private key in MAC) • Integrity proofs can be transferred! • Non-repudiation: Signer cannot deny that she signed a document • Easy to establish in a public-key world with world-readable public keys • Non-reputation in a private-key setting is not as easy - With symmetric (H)MACs, the signing key by definition is (and has to be kept) secret - Even if a trusted judge knew the signing key, the judge cannot tell which of the two parties has signed the document Further Reading (e-book see library) • Paar / Pelzl – Understanding Cryptography (2016) (“Kryptografie verständlich“, German version) • Number theory (Chapter 6.3) • Diffie-Hellman (Chapter 8.1) • RSA encryption (Chapter 7, up to 7.3 incl.) and signatures (Chapter 10.2) • encryption (Chapter 8.5) and signatures (Chapter 10.3) 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com