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 

#or get some big primes from here:

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)
    print s.getvalue()

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

print "Lets factor it!"

print "Factors of ", MyProduct, " are:",MyFactors
print "Execution Stats:\n",printStats(pr)


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


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)


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
print "Bob's shared value->Alice=",Bpub,"\n"

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

print "Bob computes s = A^BPriv mod p"
#s = 8*15 mod 23

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)