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