Day 5: Key Exchange & Public Key Encryption

Lecture Topics

• notes
• key exchange
  • the story
  • Diffie-Hellman key exchange
• public key encryption
• Merkle puzzles

Background information

We’ll be working in the main.py file. The following files are also available:

• cryptoy.py
  • note: IntMod is now included in cryptoy
• hashing.py
• symmetric.py

The group you’ll be using for Diffie-Hellman is in the cryptoy library: the class Ed25519 represents a group element. Information about this class/group:

• Ed25519.generator() returns the generator for the group
• Ed25519.identity() returns the identity for the group
• Ed25519.order is the group’s order: an integer
• The following operators are defined for Ed25519:
  • *: multiplies two group elements
  • **: raises a group element to an integer power
  • ==/!=: checks for equality
  • G.inverse(): gets the inverse of G
  • G.to_bytes(): represents G as a (unique) byte sequence
• fun fact: “Ed25519” roughly translates as “the twisted edwards elliptic curve over base field of order $ 2^{255}-19 $”. This group is defined in the internet standard RFC7748, section 4.2.

Problems

• required:

  • Diffie-Hellman key exchange:
    • diffie_hellman_key_gen
    • diffie_hellman_derive_shared
  • Diffie-Hellman-based public key encryption:
    • public_key_encrypt
    • public_key_decrypt

• bonus:

  • Merkle puzzles key exchange:
    • int_hash
    • merkle_key_gen
    • merkle_derive_shared
    • merkle_prob_estimate
  • attacking Diffie-Hellman key exchange:
    • written question 1: describe your attack
    • implement your attack as a class with:
      • a constructor: AttackDH.__init__
      • a message handler: AttackDH.handle_msg
      • the class’s docstring contains the test for the attack