Fermat
Week 0x3.0
Announcements
- Welcome to Computing Security
- We introduce RSA, and
- Why it makes sense, courtesy Fermat
- Action Items:
- 4096_t due today
- BigRSA 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 protocol \(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
1mod 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.
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.
- There are exactly the same number of unique rotations as the length of the necklace
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
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.
- Just try
RSA
- Choose two big primes \(p\), \(q\)
- Find \(n = pq\)
- Find \(\lambda(n)\)
- Find \(e : e \lt \lambda(n) \land \gcd(e, \lambda (n)) = 1\)
- Find \(d : d \equiv e^{-1} \pmod{\lambda (n)}\)
1. \(p\), \(q\)
- Do
4096_tand use, probably, 6k+1 or a performance optimization.
- LibGMP provides
gmp_nextprime
2. \(n\)
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:
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.
Aside: Hamming weight
- What is
65537in binary? - Is multiplying hard?
- Is bit-shifting hard?
- Can we combine bit-shifts to multiple?
- 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
Prime checker
Two primes
Confusingly Named
Public Key
\(d\) (decryptor)
The Process
- Encrypt our message.
--------------------------------------------------------------------------- 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.
Encrypt
- Encrypt our message.
Decrypt
- Decrypt our message.
Is it good?
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)))