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):    
    return set(reduce(list.__add__, 
                ([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)