#@# Diffie-Hellman key exchange #@# =========================== #@# Discrete logarithm problem: find x in b = a^x mod m, knowing a, b and m. #@# This problem is very hard for a big modulus (if chosen correctly). #@# #@# Diffie-Hellman key exchange: a method for two people to agree on a shared #@# secret (e.g. encryption key) through a public channel. #@# Steps of Diffie-Hellman key exchange between Alice and Bob: #@# * They agree on prime p and base g. #@# * Alice generates a secret random exponent: a. #@# * Bob generates a secret random exponent: b. #@# * Alice sends g^a mod p to Bob. #@# * Bob sends g^b mod p to Alice. #@# * Common secret: g^(a*b) = (g^a)^b = (g^b)^a (mod p). #@# Note: a listener will only learn g, g^a and g^b (mod p), from which it is #@# hard to calculate g^(a*b) without solving the discrete logarithm problem. #@# #@# Reminder: modular exponentiation (a^b mod m) in Sage: #@# very slow: a^b % m # DON'T do this (it calculates a^b first) #@# efficient: power_mod(a, b, m) #@# --------------------------------------------------------------------------- #@# Exercise 1: Diffie-Hellman key exchange #@# [with solution] #@# #@# Implement the Diffie-Hellman key exchange, i.e. calculate the common secret #@# in the two different ways (one for each participant). # Class that implements one party (person) of the Diffie-Hellman key exchange class dh_party: # Constructor: initialize values def __init__ (self, p, g): self._p = p self._g = g # Generate a secret exponent (x) import secrets self._x = secrets.randbelow(int(p)) # Raise any given base to the private exponent: a^x mod p def power_of (self, a): return power_mod(a, self._x, self._p) # Calculate the public value: g^x mod p def public (self): return self.power_of(self._g) # Perform the Diffie-Hellman key exchange with the other party. # other: another dh_party (to get public() from). def common_key (self, other): return self.power_of(other.public()) def diffie_hellman (): p = random_prime(2^128) # or often a fixed constant g = 2 # common choice for the base (it is efficient) alice = dh_party(p, g) bob = dh_party(p, g) ka = alice.common_key(bob) kb = bob.common_key(alice) print("ka =", ka) print("kb =", kb) #diffie_hellman() #@# Note: the Diffie-Hellman key exchange protects against eavesdropping, but #@# not against active interference (e.g. man-in-the-middle attacks). We can #@# protect against it e.g. by using digital signatures (see next class). #@# --------------------------------------------------------------------------- #@# Exercise 2: break Diffie-Hellman by discrete log #@# #@# If the modulus (p) is too small, then an attacker can just solve the #@# discrete logarithm problem by a brute-force search to find one of the #@# secret exponents (a or b), and then replay the steps from it. #@# Implement this attack, i.e. generate g, g^2, g^3, g^4 etc. (mod p) until #@# it matches one of the known public powers, say g^a mod p, and then use the #@# found exponent to calculate the common secret. #@# Efficiency tips: #@# 1. Instead of using exponentiation for each power, just use the previous #@# power to calculate the next one in one step: g^(n+1) = g^n * g (mod p). #@# 2. Instead of solving for one specific exponent (say g^a), check for both #@# of them simultaneously, and stop the loop when any of g^a or g^b is found. #@# p, g: the fixed public parameters #@# ga: g^a mod p #@# gb: g^b mod p #@# Return: the common secret, i.e. g^(a*b) mod p def break_dh (p, g, ga, gb): pass #TODO def test_break_dh (): #@# p, g = 314159, 23 #@# print(f"p={p}, g={g}") #@# alice = dh_party(p, g) #@# bob = dh_party(p, g) #@# print("actual:", bob.common_key(alice)) #@# print("broken:", break_dh(p, g, alice.public(), bob.public())) #@# #test_break_dh() #@# --------------------------------------------------------------------------- #@# Exercise 3: ElGamal encryption #@# #@# The Diffie-Hellman key exchange can also be used to create an asymmetric #@# encryption (see 6rsa.sage), called the ElGamal encryption. It works by #@# calculating a shared secret 's' using the Diffie-Hellman key exchange, and #@# then multiplying it by the message m (after it is converted to an integer), #@# modulo p. This modular multiplication is only reversible if s is known #@# (by multiplying with the inverse of s, modulo p). #@# #@# ElGamal key generation: #@# * Fixed constants: big prime p and base g #@# * Generate a random x between 1 and p-2. #@# * Calculate h := g^x mod p (= Alice's first message in D-H). #@# * Public key: pk = (p, g, h) #@# * Private key: sk = (p, g, x) (in some texts, sk = x only) #@# ElGamal encryption (c = Enc(m, pk)): #@# * Generate a random y between 1 and p-2. #@# * c1 := g^y mod p (= Bob's first response in D-H). #@# * s := h^y mod p (= (g^(x*y) mod p, the "common secret"). #@# * c2 := m * s mod p (m is the plaintext, a number between 0 and p-1). #@# * Ciphertext: c = (c1, c2) (twice as long as m) #@# ElGamal decryption (m = Dec(c, sk)): #@# * s := c1^x mod p (= g^(x*y) mod p, the "common secret"). #@# * m := c2 * s^(-1) mod p (s^(-1) is the modular inverse of s mod p). #@# * Alternative: instead of calculating s and then inverting it, it can #@# be calculated once using Fermat's little theorem (a^(p-1) mod p = 1): #@# s^(-1) = c1^(-x) = c1^(p-1-x) (mod p). #@# #@# Implement key generation, encryption and decryption in ElGamal. # Helper functions: convert strings to/from list of bytes: def str2bytes (str): # "ABCD" -> [65,66,67,68] return [ord(c) for c in str] def bytes2str (bytes): # [65,66,67,68] -> "ABCD" return "".join([chr(b) for b in bytes]) # Helper functions: convert list of bytes to/from big integer (in base 256) def bytes2int (b): # [11,22,33] -> 11*256^2 + 22*256 + 33 = 726561 return ZZ(b[::-1], 256) def int2bytes (i, length=0): return ZZ(i).digits(256, padto=length)[::-1] # Key generation # Return: the pair (pk, sk) as described above. def elgamal_gen (): pass #TODO # Encryption # m: the plaintext (list of bytes) # Return: c = (c1, c2) (for simplicity, you can leave them as integers) def elgamal_enc (m, pk): p, g, h = pk pass #TODO # Decryption # c = (c1, c2): the ciphertext (as returned above) def elgamal_dec (c, sk): p, g, x = sk pass #TODO def test_elgamal (): #@# pk, sk = elgamal_gen() #@# print("pk =", pk) #@# print("sk =", sk) #@# m = str2bytes("secret message") #@# print("m =", bytes2int(m), "\n =", repr(bytes2str(m))) #@# c = elgamal_enc(m, pk) #@# print("c =", c) #@# mm = elgamal_dec(c, sk) #@# print("m =", bytes2int(mm), "\n =", repr(bytes2str(mm))) #@# assert m == mm #@# #test_elgamal() #@# Note: Alice's values (x and h) are _static_, i.e. they are part of the #@# long-term keys pk and sk, whereas Bob's values (y and c1) are _ephemeral_, #@# i.e. they must be regenerated for every message (see exercise 5 why). #@# --------------------------------------------------------------------------- #@# Exercise 4: Diffie-Hellman for 3 people #@# #@# The Diffie-Hellman key exchange can be extended to share a secret between #@# any number of people. For example, 3 people can do it like this: #@# * Alice, Bob and Cecile all generate secret values: a, b, c. #@# * Round 1: Alice -> Bob -> Cecile: #@# - Alice calculates g^a mod p, and sends it to Bob. #@# - Bob calculates (g^a)^b mod p, and sends it to Cecile. #@# - Cecile calculates ((g^a)^b)^c mod p as the common secret. #@# * Round 2: Bob -> Cecile -> Alice. #@# * Round 3: Cecile -> Alice -> Bob. #@# All three rounds result in calculating the common secret g^(a*b*c) mod p #@# by the last person in the row, but in different order (as each person has #@# access to different exponents). Note that all partial powers can be sent #@# publicly: g, g^a, g^b, g^c, g^(a*b), g^(b*c), g^(a*c) (mod p), and only the #@# final power is secret: g^(a*b*c) mod p. #@# Implement this 3-way Diffie-Hellman key exchange inside the template below. # Class that implements one of the three people (the last one in each round). # It extends dh_party to override common_key() (but inherits everything else). class dh3_party (dh_party): # Calculate the common key. # other1, other2: the two other people (in correct order). # Use their public() and power_of() methods appropriately. def common_key (self, other1, other2): pass #TODO # Putting the 3-way key exchange together def dh3 (): pass #TODO #print("k1 =", ...) #print("k2 =", ...) #print("k3 =", ...) #dh3() #@# --------------------------------------------------------------------------- #@# Exercise 5: reusing ElGamal's ephemeral key #@# #@# In the ElGamal encryption (exercise 3), the value y must be used only once. #@# If it is ever reused, like for the two ciphertexts below, then the two #@# messages are multiplied by the same s (because s = h^y mod p), which means #@# that knowing one plaintext, an attacker can solve it for s, and then use s #@# to solve for the other plaintext. Note that the reuse of y can be spotted #@# easily, because then c1 is identical (because c1 = g^y mod p). That is: #@# (c1, c2) = Enc(m1, pk), #@# (c1, c3) = Enc(m2, pk). #@# Break the encryption using a known-plaintext attack (KPA, see 1break.sage), #@# i.e. knowing m1, (c1,c2) and (c1,c3) (and of course the public key pk), #@# recover the second plaintext m2. pk = (84520632807705135222174306444253, 2, 82740875900030269828745304629231) #@# m1 = str2bytes("known message") #@# c1,c2 = (14168431278498551308690282277720, 24049674618280057502552083075837) #@# c1,c3 = (14168431278498551308690282277720, 78322272138520951547984399779344) #@# #TODO #@# --------------------------------------------------------------------------- #@# Exercise 6: dining cryptographers #@# #@# The dining cryptographers protocol is an application of the Diffie-Hellman #@# key exchange. There are n people, each with a secret number, and they want #@# to find the sum of these numbers without revealing any individual number #@# (e.g. the sum of tips after a dinner at a restaurant, or counting anonymous #@# votes). The following table shows this for 4 people, with the secret values #@# sa, sb, sc and sd. First, each pair of people agrees on a common key using #@# the Diffie-Hellman key exchange (kxy means the common key between X and Y). #@# Then, each party calculates the following sums, and publishes the result: #@# pub. sec. Alice Bob Cecile David #@# Alice : pa = sa + kab + kac + kad #@# Bob : pb = sb - kab + kbc + kbd #@# Cecile : pc = sc - kac - kbc + kcd #@# David : pd = sd - kad - kbd - kcd #@# Then, the sum of these public sums is the same as the sum of the secrets: #@# pa + pb + pc + pd = sa + sb + sc + sd, #@# because all the common keys (kxy) cancel out. #@# Implement this protocol for any number of people, extending the dh_party #@# class from exercise 1. # Class that implements one participant of the dinner (extending dh_party). class dining_person (dh_party): # Initialize the secret number and the Diffie-Hellman key exchange def __init__ (self, p, g): dh_party.__init__(self, p, g) self._secret = randrange(5) print("secret =", self._secret) # for testing # Calculate the public sum of this person (e.g. pa). # people: list of all participants (to do a common_key() with each). # (Note: it includes self, i.e. self == people[i] for some i). def calc_public (self, people): pass #TODO # Perform the protocol for n people, i.e. calculate the sum of their secrets # using the implemented calc_public() method of the above class. def dining_sum (n): p, g = random_prime(2^128), 2 people = [dining_person(p, g) for i in range(n)] pass #TODO #print("sum =", dining_sum(5))