程序代写代做代考 algorithm Public Key Cryptography

Public Key Cryptography

Cryptography

‹#›

Cryptography
Greek for “hidden writing”
The art of enciphering and deciphering codes
In modern use – the art of secure communication
Much wider than just enciphering and deciphering
One of the main tools for protecting information
Confidentiality – prevents adversaries from reading the information
Integrity – ensures detection of unauthorised modifications

‹#›

‹#›

Finite Fields
A field is an algebraic structure that consists of:
A set of elements
Four operations: addition, subtraction, multiplication and division
Examples: rational numbers, real numbers.
Finite fields are fields with a finite number of elements
Example: GF(p) – Integers modulo a prime number p

‹#›

Example: GF(7)
Seven elements: 0, 1, 2, 3, 4, 5, 6
Arithmetic:
1+1=?
3+3=?
5+5=?
3·2=?
4·2=?
1/2=?

‹#›

Exponentiation
Exponentiation: repeated multiplication
x0 = 1
xi+1 = x·xi
What is 32 in GF(7)? 33?

Can we do that efficiently with large numbers?
… e.g. 1000 digit numbers?

‹#›

A look at binary numbers
A binary number e is a sequence of bits e0…en-1 such that
What is ⎣e/2k⎦?

What about ⎣e/2k-1⎦?

‹#›

Square and Multiply
x ⟵1
for i ⟵|e|-1 downto 0 do
x ⟵x2 mod p
if (ei =1) then
x = xb mod p
endif
done
return x

‹#›

Logarithms
Reverse of exponentiation
What is log3(6) in GF(7)?

Discrete logarithm (DLP) is a hard problem!
No efficient algorithm known

‹#›

Key pairs
Agree on a finite field GF(p) and a generator g
Keys come in pairs
Represent a DLP problem

(public, private) = (A, α) where A=gα mod p

Oscar (the adversary) knows A. Why can’t he find α
Discrete logarithm is hard.
If p is a 3072 bit prime, Bob needs to test ~2128 values to find α

‹#›

Identity
Identity means holding a private key

How do we prove identity?
How does Bob verify that he is talking to Alice?

In our settings, Alice claims/asserts identity by publishing (“committing”) a public key A from a pair (A, α)

‹#›

Identification
Problem: Alice no longer has an identity

(A, α) = keypair()
A
???
s
A =? gs (mod p)
s=α

‹#›

Ephemera
Bob verifies because
gs = gα+r = gα·gr=A·R (mod p)
Note: s reveals nothing about α because r is random

(A, α) = keypair()
A
???
R
A·R =? gs (mod p)
s=α+r
(R, r) = keypair()
s

‹#›

Ephemera
Problem: Replay attack
Will solve later

(A, α) = keypair()
A
???
R
A·R =? gs (mod p)
s=α+r
(R, r) = keypair()
s

‹#›

Cheating
Bob verifies because
gs = gr’ = R’=A·R (mod p)
Note: Oscar knows nothing about α
Oscar does not know log(R)

(A, α) = keypair()
A
???
R
A·R =? gs (mod p)
s=r’
(R’, r’) = keypair()
s

R=R’/A

‹#›

Detecting cheating
Alice sends s=α+r=log(A·R)
And knows both α=log(A) and r=log(R)
Oscar sends s=log(A·R)
But knows neither α=log(A) nor r=log(R)
Bob cannot ask for α, and cannot ask for both s and r as these would reveal α
Bob can ask for either s or r and verify them
Correct s proves knowledge of α, if honest
Correct r proves honesty but not knowledge of α

‹#›

Identification
Bob verifies because
gs = geα+r = geα·gr=Ae·R (mod p)
To cheat, Oscar need to guess e: 50% chance
Replay attacks have 50% chance of being detected
Repeat until Bob is satisfied
(A, α) = keypair()
A
???
R
Ae·R =? gs (mod p)
s=eα+r
(R, r) = keypair()
s
e=random({0,1})
e

‹#›

Chaum-Evertse-Graaf ID
(A, α) = keypair()
A
???
R1
Ae1·R1 =? gs1 (mod p)
s1=e1α+r1
(R1, r1) = keypair()
s1
e1=random({0,1})
e1
???
R128
Ae128·R128 =? gs128 (mod p)
s128=e128α+r128
s128
e128=random({0,1})
e128

‹#›

Schnorr ID
128 rounds of Chaum-Evertse-Graaf:
Too much communication
128⨉R, 128⨉s
Too much computation
Alice and Bob compute 128 exponentiations, each

Schnorr’s idea: “parallelise” the 128 rounds
Use a single 128-bit challenge instead of 128 one bit challenges

‹#›

Schnorr ID
Single round
Alice computes one exponentiation
Bob computes two exponentiations (one is short)
(A, α) = keypair()
A
???
R
Ae·R =? gs (mod p)
s=eα+r
(R, r) = keypair()
s
e=random({0,1})
e
e=random([0,2128))

‹#›

Digital Signatures
Non-interactive proofs that a signer has witnessed (created, saw) some data
Provides:
Authenticity – we know the message is genuine
Message integrity – we know it was not modified
Non-repudiability – the signer cannot deny signing
Only need the signer’s public key to verify signatures

‹#›

“Non-interactive Schnorr”
(A, α) = keypair()
A
e=Hash(R)
Ae·R =? gs (mod p)
s=eα+r
(R, r) = keypair()
s
R
e=Hash(R)

‹#›

Cryptographic Hash Function
A hash function that is also:
One-way, i.e. no easy way of inverting it
Small changes in the input result in large changes in the output
Collision resistant – hard to find a pair of inputs that hash to the same value
Examples:
MD5 (insecure)
SHA-1 (insecure)
SHA-256
Keccak

‹#›

“Compact NI Schnorr”
“Compact” because e is typically much shorter than R
(A, α) = keypair()
A
e=Hash(R)
Ae·R =? gs (mod p)
s=eα+r
(R, r) = keypair()
s
R
e=Hash(R)
e
R=gs/Ae (mod p)
e=?Hash(R)

‹#›

Avoiding Division
Division is less efficient than multiplication. Can we remove it?
(A, α) = keypair()
A
e=Hash(R)
s=eα+r
(R, r) = keypair()
s
e
R=gs/Ae (mod p)
e=?Hash(R)
s=r-eα
R=gs·Ae (mod p)
e=?Hash(R)

‹#›

Schnorr Signatures
(A, α) = keypair()
A
e=Hash(R)
(R, r) = keypair()
s
e
s=r-eα
R=gs·Ae (mod p)
e=?Hash(R)
M
e=Hash(R,M)
R=gs·Ae (mod p)
e=?Hash(R,M)

‹#›

Symmetric encryption

5pm at the
rose garden?

5pm at the
rose garden?

‹#›

“Formal” definitions
A cipher defined over (K, M, C) is a pair of efficient functions (E, D)
E: K⨉MC, D: K⨉CM
(We usually write Ek(m) instead of E(k,m))
5pm at the
rose garden?
Ek()
Gobbledy
gobbledygook
Gobbledy
gobbledygook
Dk()
5pm at the
rose garden?

‹#›

Diffie-Hellman Key Exchange
Task:
Alice and Bob want to establish a shared secret
They have no secure channel to transfer it

Recall that A=gα mod p, B=gβ mod p
Hence: Bα=(gβ)α=gβα=gαβ= (gα)β=Aβ

(A, α) = keypair()
A
(B, β) = keypair()
B
S=Bα mod p
S=Aβ mod p

‹#›

Forward Secrecy
Alice and Bob can now use S to derive a secret key for a symmetric protocol.
What would happen if Alice’s key is compromised?
Alice can generate a new key pair
But what about past communication?
(A, α) = keypair()
A
(B, β) = keypair()
B
S=Bα mod p
S=Aβ mod p

‹#›

Ephemeral DH
Alice and Bob generate random key pairs every time they communicate
Provides forward secrecy
No authentication. Vulnerable to Man in the Middle (MITM) attacks

(KA, kA) = keypair()
KA
(KB, kB) = keypair()
KB
S=KBkA mod p
S=KAkB mod p

‹#›

Class Exercise
Describe an MITM attack that allows Oscar to decrypt all communication between Alice and Bob.
(KA, kA) = keypair()
KA
(KB, kB) = keypair()
KB
S=KBkA mod p
S=KAkB mod p

‹#›

Ephemeral DH + Signatures
Use long term keys to sign ephemeral keys
How does Alice know that B is Bob’s key?

(KA, kA) = keypair()
KA
(KB, kB) = keypair()
KB
S=KBkA mod p
S=KAkB mod p
(A, α) = keypair()
A
(B, β) = keypair()
B
(RA, sA) = sign(KA, α)
(RA, sA)
(RB, sB) = sign(KB, β)
verify(KB, RB, sB, B)
verify(KA, RA, sA, A)
(RB, sB)

‹#›

Certificates
To know that B is Bob’s key, Bob asks a trusted entity (certificate authority or CA) to sign it.
The CA issues a certificate certifies that the key belongs to Bob
How does Alice know she can trust the certificate authority?
Use another trusted certificate authority?
Root CAs are implicitly trusted.

‹#›

Root CAs
Where do we get these from?
Downloaded with the browser?
Firefox default list includes 159 CAs
Chicken and egg problem
Pre-installed on our computer
What happens if one of them is breached?

‹#›

e = ei ⋅2
i

i=0

n−1

e=e
i
×2
i
i=0
n-1
å

e 2k⎢⎣

⎦= ei ⋅2

i−k

i=k

n−1

e2
k
ê
ë
ú
û
=e
i
×2
i-k
i=k
n-1
å

e 2k−1⎢⎣

⎦= ei ⋅2

i−k+1

i=k−1

n−1
∑ = 2 ⋅ e 2k⎢⎣ ⎥⎦+ ek−1

e2
k-1
ê
ë
ú
û
=e
i
×2
i-k+1
i=k-1
n-1
å
=2×e2
k
ê
ë
ú
û
+e
k-1

e 2k−1⎢⎣

⎦= ei ⋅2

i−k+1

i=k−1

n−1

e2
k-1
ê
ë
ú
û
=e
i
×2
i-k+1
i=k-1
n-1
å

e 2k−1⎢⎣

⎦= 2 ⋅ e 2

k⎢


⎦+ ek−1

e2
k-1
ê
ë
ú
û
=2×e2
k
ê
ë
ú
û
+e
k-1

b
e 2k−1⎢⎣⎢


⎦⎥ = b

2⋅ e 2k⎢⎣⎢

⎦⎥+ek−1

b
e2
k-1
ê
ë
ê
ú
û
ú
=b
2×e2
k
ê
ë
ê
ú
û
ú
+e
k-1

= b
e 2k⎢⎣⎢


⎦⎥⎛




2

⋅bek−1

=b
e2
k
ê
ë
ê
ú
û
ú
æ
è
ç
ö
ø
÷
2
×b
e
k-1