Week 13: Elliptic Curve Cryptography (ECC), Prefect for ETL Pipelines

DSAN 5500: Data Structures, Objects, and Algorithms in Python

Author

Affiliation

Jeff Jacobs

jj1088@georgetown.edu

Open slides in new window →

Where We Left Off

• Eliminating side-effects
• Where we’re going: loops without side-effects

“Incoming” Side-Effects

import os
os.environ['exponent'] = '2'
def compute_powers(my_nums: list[int]) -> list[int] | list[float]:
  return [n ** int(os.environ['exponent']) for n in my_nums]
compute_powers([1, 2, 3])

[1, 4, 9]

• You (responsible for your org’s compute_powers()) commit code and go to sleep 😴
• Meanwhile, teammate in Singapore starts up Python and runs your code…

import dotenv
dotenv.load_dotenv(override=True)
compute_powers([1, 2, 3])

[1, 8, 27]

• Same function, run in different environments, produces different outputs…
• One solution: Figure out DC-Singapore environment-coordination system… 😫
• FP solution: Refactor code to eliminate side-effects (Ex: exponent argument would tell user they need to explicitly specify exponent before using your function!)

“Outgoing” Side-Effects

• Previous slide: “incoming” side-effects (from exponent environment variable)
• Here: secret “outgoing” side-effect (may be as “surprising” to user)

def add(a, b):
  with open('log.txt', 'w', encoding='utf-8') as logfile:
    logfile.write(f'User adding {a} and {b}')
  return a + b

• General principle: Think of who is using function and what they will expect
  • Ex: When doing math, people “expect” PEMDAS

User Expectations Across Locales

def parse_money_amount(money_amount: str) -> float:
  return float(money_amount.replace(",",""))
parse_money_amount("1,000,000")

1000000.0

parse_money_amount("1'000'000")

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In[5], line 1
----> 1 parse_money_amount("1'000'000")

Cell In[4], line 2, in parse_money_amount(money_amount)
      1 def parse_money_amount(money_amount: str) -> float:
----> 2   return float(money_amount.replace(",",""))

ValueError: could not convert string to float: "1'000'000"

Loops?

• The examples thus far have built on intuitions around:
• How we might “chop” a long line-by-line function into smaller parts (“verbs”)
• How we might refactor functions to eliminate side effects
• Loops are a bit less intuitive to FP-ify, but the key is tail recursion: Function does something to the first element in the list, then calls itself on the remainder of the list

Tail Recursion 1: Sum

def my_sum(my_list):
  total = 0
  for cur_element in my_list:
    total = total + cur_element
  return total
my_sum([1, 2, 3, 4])

10

def my_sum_r(my_list):
  if len(my_list) == 0:
    return 0
  return my_list[0] \
    + my_sum_r(my_list[1:])
my_sum_r([1, 2, 3, 4])

10

from functools import reduce
my_sum_tr = lambda my_list: reduce(
  lambda acc, list_tail: acc + list_tail,
  my_list,
  0
)
my_sum_tr([1, 2, 3, 4])

10

Tail Recursion 2: Factorial

def my_factorial_loop(n):
  product = 1
  for i in range(2, n + 1):
    product = product * i
  return product
my_factorial_loop(4)

24

def my_factorial_r(n):
  if n == 1:
    return 1
  return n * my_factorial_r(n - 1)
my_factorial_r(4)

24

from functools import reduce
my_factorial_tr = lambda n: reduce(
  lambda acc, x: acc * x,
  range(1, n + 1),
  1
)
my_factorial_tr(4)

24

From W11: Cryptography Roadmap

	👍	👎
One-Time Pad	Provably perfectly(!) secure ✅	Requires establishing a single shared (symmetric) key
RSA / Diffie-Hellman / ElGamal	Provably secure (via NP-hardness of prime factorization) ✅	Restarts sometimes required; key sizes have to grow exponentially bc Moore’s Law
Elliptic Curve Cryptography	Provably secure (discrete logarithm NP-hard) ✅	[Still 👍] Smaller key sizes: 256-bit ECC \(\approx\) 3072-bit RSA
Throughout: Public keys, secret keys, signatures, etc., are all functions! \(\leadsto\) Functional Programming

Math with Elliptic Curves

Addition of points (\(\oplus\)) and multiplication-by-constants (\(\otimes\)) given an elliptic curve. From AbdElHaleem et al. (2022)

Encrypting/Decrypting: Should be Easy for Alice/Bob, Hard for Everyone Else!

• Multiplication is easy! Given \(P\), \(100 \otimes P\) can be computed via “divide and conquer” approach:

1. \(P \rightarrow 2P\)	5. \(12P \rightarrow 24P\)
2. \(2P \rightarrow 3P\)	6. \(24P \rightarrow 25P\)
3. \(3P \rightarrow 6P\)	7. \(25P \rightarrow 50P\)
4. \(6P \rightarrow 12P\)	8. \(50P \rightarrow 100P\)

• Division is hard! Given \(P\) and \(Q\), solving \(Q = nP\) for \(n\) requires “brute force” checking:

1. \(1 \cdot P\)
2. \(2 \cdot P\)
3. \(3 \cdot P\)
\(\vdots\)

Elliptic Curve Cryptography in Python

from tinyec.ec import SubGroup, Curve
field = SubGroup(p=17, g=(15, 13), n=18, h=1)
curve = Curve(a=0, b=7, field=field, name='p1707')
print('curve:', curve)
for k in range(0, 25):
    p = k * curve.g
    print(f"{k} * G = ({p.x}, {p.y})")

curve: "p1707" => y^2 = x^3 + 0x + 7 (mod 17)
0 * G = (None, None)
1 * G = (15, 13)
2 * G = (2, 10)
3 * G = (8, 3)
4 * G = (12, 1)
5 * G = (6, 6)
6 * G = (5, 8)
7 * G = (10, 15)
8 * G = (1, 12)
9 * G = (3, 0)
10 * G = (1, 5)
11 * G = (10, 2)
12 * G = (5, 9)
13 * G = (6, 11)
14 * G = (12, 16)
15 * G = (8, 14)
16 * G = (2, 7)
17 * G = (15, 4)
18 * G = (None, None)
19 * G = (15, 13)
20 * G = (2, 10)
21 * G = (8, 3)
22 * G = (12, 1)
23 * G = (6, 6)
24 * G = (5, 8)

Discrete ECC

ETL Pipelines with Prefect!

Colab Demo(s)

References

AbdElHaleem, Sherif H., Salwa K. Abd-El-Hafiz, and Ahmed G. Radwan. 2022. “A Generalized Framework for Elliptic Curves Based PRNG and Its Utilization in Image Encryption.” Scientific Reports 12 (1): 13278. https://doi.org/10.1038/s41598-022-17045-x.