# Asymmetric Encryption

Use hard math problems called “Trapdoor Functions”

### Example: Factoring Multiples of Primes

• Easy to multiply hard to factor
• Difficult to process without a key but easy to process with a key (the “trapdoor”)
``````

In [ ]:

#Lets test this idea...
import cProfile, pstats, StringIO

Prime1=307 #Try some others 7907 15485857 7919 15485863
Prime2=293

#or get some big primes from here:https://primes.utm.edu/

def factors(n):
([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def printStats(pr):
s = StringIO.StringIO()
sortby = 'cumulative'
ps = pstats.Stats(pr, stream=s).sort_stats(sortby)
ps.print_stats()
print s.getvalue()

pr = cProfile.Profile()
pr.enable()
MyProduct=Prime1 * Prime2
pr.disable()
print "Product of 2 Primes=", MyProduct
print "Execution Stats:\n",printStats(pr)

print "Lets factor it!"

pr.enable()
MyFactors=factors(MyProduct)
pr.disable()
print "Factors of ", MyProduct, " are:",MyFactors
print "Execution Stats:\n",printStats(pr)

``````

### Risk

Attacker can use known plaintext and A's public Ke to test a generated private key.

### Computation

Asymmetric key encryption is very expensive Never encrypt message; transmit encrypted symmetric key

Ex: In software RSA is 100 times slower than DES

``````     In embedded hardware it is even slower

``````

### Delay Time

Stream ≤ Stream-Block ≤ Block
DES: 64-bit blocks
RSA: 100-200-bit blocks (short blocks: limited security)

## Diffie-Hellman Key Exchange

• Created by Whitfield Diffie and Martin Hellman
• One of the most common encryption protocols in use today.
• Key exchange for SSL, TLS, SSH and IPsec
• Key per session, not to be reused
• A couple of variations have evolved
• Ephemeral Diffie-Hellman (EDH)
• Elliptic Curve Diffie-Hellman (ECDH)
• Elliptic Curve Diffie-Hellman Ephemeral (ECDHE)

### Example

``````

In [ ]:

#Alice & Bob: Agree on a large prime p (1024+ bits)
p = 23
#Alice & Bob: Agree on a generator g
base_g = 5

#Alice & Bob: Choose private numbers a (S) & b (R)
Apriv = 6 #Alice's secret
Bpriv = 15 #Bob's secret

print "Alice sends Bob A = g^Apriv mod p"
#A = 5^6 mod 23
Apub = (base_g**Apriv)%p
print "Alice's shared value->Bob=",Apub

print "Bob sends Alice B = g^Bpriv mod p"
#B = 5^15 mod 23
Bpub=(base_g**Bpriv)%p
print "Bob's shared value->Alice=",Bpub,"\n"

print "Alice computes s = B^Apriv mod p"
#s = 19*6 mod 23
s=(Bpub**Apriv)%p
print "Alice has Shared Secret=",s,"\n"

print "Bob computes s = A^BPriv mod p"
#s = 8*15 mod 23
s=(Apub**Bpriv)%p

print "Bob has Shared Secret=",s
#Alice and Bob now share a secret (2).

``````

Intruder cannot compute K even with p, g, g^x, g^y
Exponentiation (easy); Discrete Logarithm (hard)