Fermat

Week 0x6

Prof. Calvin

Crypto

Announcements

• Welcome to variously CS 276/CS 540
  • We introduce RSA, and
  • Why it makes sense, courtesy Fermat
• Action Items:
  • 4096_t due this week
  • RSAinC due next week

Today

• New
  • Public Key Cryptography
  • Fermat’s little theorem
  • RSA

Public Key Cryptography

Motivating Example

• Canonical Example is Snowden x Greenwald 2013
  • Snowden wished to communicate a secret to Greenwald
  • Snowden and Greenwald had never met
  • Snowden could not transmit the secret in plain text
• Vs enigma, no prior agreement on how to encrypt/decrypt

Reads Cryptobook

A key exchange proto- col \(P\) is a pair of probabilistic machines \((A, B)\) that take turns in sending messages to each other. At the end of the protocol, when both machines terminate, they both obtain the same value \(k\). A protocol transcript \(T_P\) is the sequence of messages exchanged between the parties in one exe- cution of the protocol.

Reads Cryptobook

Since \(A\) and \(B\) are probabilistic machines, we obtain a different transcript every time we run the protocol. Formally, the transcript \(T_P\) of protocol \(P\) is a random variable, which is a function of the random bits generated by \(A\) and \(B\). The eavesdropping adversary \(E\) sees the entire transcript \(T_P\) and its goal is to figure out the secret \(k\).

Set the Stage

• Snowden has e.g. files on a harddrive
  • The files contain keywords that cannot be safely transmitted over US-based internet connections.
  • Snowden is based in Hawai’i with no access to non-US-based connections.
  • Snowden needs to encrypt the files in such as a way that only a trusted destination may read them.

First Contact

• Snowden contacts Greenwald to agree to use a secure messaging protocol
  • Use of such protocols is relatively non-suspicious, used for banking etc.
  • It was enough to raise alarms for Snowden, but not quickly enough to stop him.
• Greenwald agrees to a recommended protocol

Initialization

• Greenwald generates a combination of numerical values on a local computing device.
  • One of these is the public-key, which Greenwalk may circulate broadly.
• We see an example of such a technology on the next slide.

SecureDrop

• Embed doesn’t work for what are likely obvious reasons:
• Link

Safety Note

• Probably dropping to The Intercept is not recommended.
• Reality Winner is currently incarcerated due to a leak fumbled by The Intercept
• Read more

Step 2

• Greenwald & co. hold in reserve a private-key
• They defend it like lives depend on it, as they did for Winner and Snowden.
• So: not stored in plaintext on a hard-drive
• So: if on a hard-drive, hard-drive is in a secure site from e.g. federal law enforcement.

Step 3

• Snowden, and hopefully enough others to avoid suspicion, use the public key to encrypt their payload.
• In addition to e.g. top secret documents, concerned community members could send in less-secret materials such as analysis of policing data with which they would rather not be affiliated.
• Journalists sift through the inputs.

It’s that simple

• Okay but like how do we do that:
  • Any eaves-dropping adversary can see the public key.
  • One-to-one communication of a key is already dangerous
  • All this encryption/decryption needs to be managable by e.g. non-computing specialized journalists.

Today

• New
  • ✓ Public Key Cryptography
  • Fermat’s little theorem
  • RSA

Fermat’s Little Theorem

Numbers

• We have already learned from SHA and others, that if ‘its in’ a computer we can say it’s a number.
• We have already learned, from 4096_t and others, that numbers of arbitrarily large sizes can undertake operations in a computer.
• We find a numerical operation that scrambles bits given a public key that is reversible only with a private key.

Theorem

\[ \exists e, d, p, q \in \mathbb{N} : \forall m \in \mathbb{N} : (m^e)^d \equiv m \pmod{pq} \]

• \(m\) : message, such as top secret documents or your credit card number.
• \(e\) : encryptor, the public key, that Greenwald or bandcamp post pubicly
• \(d\) : decryptor, the private key, that Greenwald stores in a bombproof safe or a dubiously secure AWS instance.

Strategy

• We show Fermat’s little theorem.

\[ \begin{align} \forall a \in \mathbb{N}, p \in \mathbb{P} : \gcd(p,a) = 1 \implies a^{p-1} \equiv 1 \pmod{p} \\ \end{align} \]

• That is, there’s a prime you can raise a number to in order to get 1 mod that prime.

Proof

• This is called “combinatorics”
  • Look, I thought it was gonna be a CS class too.
• We go live to a proof I never learned but love, “counting necklaces”
  • Wikipedia is my legal guardian.

Necklaces

• Simplest known proof.
• Combinatorial proof.
• Adapted from Golomb’s proof.
  • Golomb is an electrical engineer who allegedly invented Tetris
  • A lot of people allegedly did that though.

Simplification

• Assume: \[ 0 \leq a \leq p - 1 \]
• Consequence of modular arithmetic. \[ a^p \pmod{p} \lt p. \]

Simplification

• We note the following expressions are logicially equivalent.

\[ a^{p-1} \equiv 1 \pmod{p} \]

• Multiply by \(a\)

\[ a^p \equiv a \pmod{p} \]

Strings

• Consider strings/necklaces of length \(p\).
• Alphabet with \(a\) symbols.
  • Jeweler with \(a\) gemstones
• Total number of strings is \(a^p\).
• Take \(p = 5, a = 2\) say “amethyst” and “beryl”

necklaces = [
    "AAAAA", "AAAAB", "AAABA", "AAABB", "AABAA", "AABAB", "AABBA", "AABBB",
    "ABAAA", "ABAAB", "ABABA", "ABABB", "ABBAA", "ABBAB", "ABBBA", "ABBBB",
    "BAAAA", "BAAAB", "BAABA", "BAABB", "BABAA", "BABAB", "BABBA", "BABBB",
    "BBAAA", "BBAAB", "BBABA", "BBABB", "BBBAA", "BBBAB", "BBBBA", "BBBBB"
]

Necklaces

• Strings as necklaces.
• Regard rotationally related necklaces as friends.

def friends(n, m):
  return any([n == m[i:] + m[:i] for i in range(len(m))])

assert(friends("AAABB", "BBAAA"))

Friends 5gether

• Get it? Not 2gether?

friends = [
    ["AAAAB", "AAABA", "AABAA", "ABAAA", "BAAAA"],
    ["AAABB", "AABBA", "ABBAA", "BBAAA", "BAAAB"],
    ["AABAB", "ABABA", "BABAA", "ABAAB", "BAABA"],
    ["AABBB", "ABBBA", "BBBAA", "BBAAB", "BAABB"],
    ["ABABB", "BABBA", "ABBAB", "BBABA", "BABAB"],
    ["ABBBB", "BBBBA", "BBBAB", "BBABB", "BABBB"],
    ["AAAAA"],
    ["BBBBB"]
]

Aside

• We note this suffices as a proof that:

\[ 2^5 = 32 \equiv 2 \pmod{5} \]

Counting Friends

• We note:
  • There are exactly the same number of unique rotations as the length of the necklace
    • After that we repeat.
    • So… \(p \equiv 0 \pmod{p}\) and \(p\) is length.
  • Unless there is only one symbol, then exactly one rotation.
    • There are exactly \(a\) unique symbols, so
    • Exactly \(a\) strings of this form.

Strategy

• We show Fermat’s little theorem.

\[ \begin{align} \forall a \in \mathbb{N}, p \in \mathbb{P} : \gcd(p,a) = 1 \implies a^{p-1} \equiv 1 \pmod{p} \\ \end{align} \]

• Proof

nofriends = [
    ["AAAAA"],
    ["BBBBB"]
]

Today

• New
  • ✓ Public Key Cryptography
  • ✓ Fermat’s little theorem
  • RSA

New Goal

• We want: \[ a^p \equiv a \pmod{p} \implies \] \[ \exists e, d, p, q \in \mathbb{N} : \forall m \in \mathbb{N} : (m^e)^d \equiv m \pmod{pq} \]
• We can restrict \(e,d,p,q\) \[ \exists e, d\in \mathbb{N}, p, q \in \mathbb{P}: \forall m \in \mathbb{N} : (m^e)^d \equiv m \pmod{pq} \]

Insight

• We use something called the “Carmichael function” denoted, confusingly, as \(\lambda\):

\[ \lambda(n) = \text{min}(\{m : \forall a : gcd(a,n) = 1 : a^m \equiv 1 \pmod{n}\}) \]

• Say, \(\lambda(n)\) is the smallest number that coprimes to \(n\) are equivalent to zero mod \(n\).
• Easy for prime \(p\), its \(\lambda(p) = p - 1\).
  • Just try 5, it’s not too bad.

RSA

1. Choose two big primes \(p\), \(q\)
2. Find \(n = pq\)
3. Find \(\lambda(n)\)
4. Find \(e : e \lt \lambda(n) \land \gcd(e, \lambda (n)) = 1\)
5. Find \(d : d \equiv e^{-1} \pmod{\lambda (n)}\)

1. \(p\), \(q\)

• Do 4096_t and use, probably, 6k+1 or a performance optimization.

# this will still be slow with big numbers
def find_large_prime(k):
    candidate = 6 * k + 1
    # you need a prime tester
    while not is_prime(candidate):
        candidate += 6
    return candidate

• LibGMP provides gmp_nextprime

2. \(n\)

n = p * q;

3. \(\lambda(n)\)

• This one is kept secret by the way.
• It so happens: \[ \forall p,q \in \mathbb{P} : \lambda(pq) = \text{lcm}(p-1, q-1) \]
• There’s fast ways to this, but anything goes this week.

Aside: lcm

• GitHub Copilot provides:

def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b."""
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    """Calculate the Least Common Multiple of a and b."""
    return a * b // gcd(a, b)

4. \(e\)

• Find \(e : e \lt \lambda(n) \land \gcd(e, \lambda (n)) = 1\)
• You know what is comprime with whatever \(\lambda (n)\) is?
• A prime number.

e = 65537; // 2 ^ 16 + 1

Aside: Hamming weight

1. What is 65537 in binary?
2. Is multiplying hard?
3. Is bit-shifting hard?
4. Can we combine bit-shifts to multiple?
5. If we did that, what numbers would be easiest to multiply by?

5. \(d\)

• This one is very secret!
• Find \(d : d \equiv e^{-1} \pmod{\lambda (n)}\)
• There’s a good way to do this, or…
• Find \(de \equiv 1 \pmod{\lambda (n)}\)
  • Just start at \(d = 1\) and go up until you find it.
  • It’ll be less than \(\lambda (n)\)

Today

• New
  • ✓ Public Key Cryptography
  • ✓ Fermat’s little theorem
  • ✓ RSA

Using RSA

Let’s make a secret

s = "C" # a random string

Prime checker

is_prime = lambda n : any([n % i for i in range(2, int(n **.5))])
is_prime(60), is_prime(61)

(False, True)

Two primes

hide_p = lambda: find_large_prime(10)
hide_q = lambda: find_large_prime(15)
n = hide_p() * hide_q()
n

5551

Confusingly Named

hide_λ = lambda: lcm(hide_p() - 1,  hide_q() - 1)

Public Key

e = 65537

\(d\) (decryptor)

def find_d():
  d = 1
  while 1 != (d * e % hide_λ()):
    d += 1
  return d

The Process

• Encrypt our message.

m = ord(s) # to number
c = m ** e
m, c, c % n

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
File ~\AppData\Local\Programs\Python\Python312\Lib\site-packages\IPython\core\formatters.py:711, in PlainTextFormatter.__call__(self, obj)
    704 stream = StringIO()
    705 printer = pretty.RepresentationPrinter(stream, self.verbose,
    706     self.max_width, self.newline,
    707     max_seq_length=self.max_seq_length,
    708     singleton_pprinters=self.singleton_printers,
    709     type_pprinters=self.type_printers,
    710     deferred_pprinters=self.deferred_printers)
--> 711 printer.pretty(obj)
    712 printer.flush()
    713 return stream.getvalue()

File ~\AppData\Local\Programs\Python\Python312\Lib\site-packages\IPython\lib\pretty.py:394, in RepresentationPrinter.pretty(self, obj)
    391 for cls in _get_mro(obj_class):
    392     if cls in self.type_pprinters:
    393         # printer registered in self.type_pprinters
--> 394         return self.type_pprinters[cls](obj, self, cycle)
    395     else:
    396         # deferred printer
    397         printer = self._in_deferred_types(cls)

File ~\AppData\Local\Programs\Python\Python312\Lib\site-packages\IPython\lib\pretty.py:649, in _seq_pprinter_factory.<locals>.inner(obj, p, cycle)
    647         p.text(',')
    648         p.breakable()
--> 649     p.pretty(x)
    650 if len(obj) == 1 and isinstance(obj, tuple):
    651     # Special case for 1-item tuples.
    652     p.text(',')

File ~\AppData\Local\Programs\Python\Python312\Lib\site-packages\IPython\lib\pretty.py:394, in RepresentationPrinter.pretty(self, obj)
    391 for cls in _get_mro(obj_class):
    392     if cls in self.type_pprinters:
    393         # printer registered in self.type_pprinters
--> 394         return self.type_pprinters[cls](obj, self, cycle)
    395     else:
    396         # deferred printer
    397         printer = self._in_deferred_types(cls)

File ~\AppData\Local\Programs\Python\Python312\Lib\site-packages\IPython\lib\pretty.py:787, in _repr_pprint(obj, p, cycle)
    785 """A pprint that just redirects to the normal repr function."""
    786 # Find newlines and replace them with p.break_()
--> 787 output = repr(obj)
    788 lines = output.splitlines()
    789 with p.group():

ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

Too Big

• Haha Python can’t handle big numbers.
• Not to worry, we’re working in modular arithmetic.

def modexp(m, e, n):
  if e == 0:
      return 1
  if e == 1:
      return m % n
  if e % 2:
      return (m * modexp(m*m % n, e//2, n)) % n
  return  modexp(m*m % n, e//2, n) % n

Encrypt

• Encrypt our message.

m = ord(s) # to number
c = modexp(m, e, n)
m, c

(67, 4972)

Decrypt

• Decrypt our message.

new_m = modexp(c % n, find_d(), n)
new_m, m

(67, 67)

Is it good?

chr(modexp(modexp(ord("C"), e, n), find_d(), n))

'C'

All

def find_large_prime(k):
    is_prime = lambda n : any([n % i for i in range(2, int(n **.5))])
    candidate = 6 * k + 1
    # you need a prime tester
    while not is_prime(candidate):
        candidate += 6
    return candidate

def lcm(a, b):
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    return a * b // gcd(a, b)

s = "C" # a random string
m = ord(s) # to number

hide_p = lambda: find_large_prime(10)
hide_q = lambda: find_large_prime(15)
n = hide_p() * hide_q()

hide_λ = lambda: lcm(hide_p() - 1,  hide_q() - 1)

e = 65537 # encryptor

def find_d():
    d = 1
    while 1 != (d * e % hide_λ()):
        d += 1
    return d

def modexp(m, e, n):
    if e == 0:
        return 1
    if e == 1:
        return m % n
    if e % 2:
        return (m * modexp(m*m % n, e//2, n)) % n
    return  modexp(m*m % n, e//2, n) % n

c = modexp(m, e, n) # ciphertext

new_m = modexp(c % n, find_d(), n)

print(chr(modexp(modexp(ord("C"), e, n), find_d(), n)))