2017-03-15.ipynb

Kernel: SageMath (stable)

Math 152 - Intro to Mathematical Software

2017-03-15

Kiran Kedlaya; University of California, San Diego

adapted from lectures by William Stein, University of Washington

Guest lecturer: Alina Bucur

** Lecture 27: Public key cryptography and number theory, part 2 **

Announcements:

• Office hours this week:

  • Zonglin: Thursday, March 16, 3:30-5:30 in APM 5748.

  • Kiran: Friday, March 17, 11-12 in APM 7202.

  • Peter: Friday, March 17, 12-1 and 3-4 in APM 6132.

• Homework due Friday, 8pm. Peer grading due Sunday, 8pm.

• No final exam!

• Please do your course evaluation (CAPE)! Evaluations close Monday, March 20 at 8am.

Last time, we saw how to use the difficulty of the discrete logarithm problem to execute a Diffie-Hellman key exchange.

This time, we will use the difficulty of integer factorization to perform RSA encryption and decryption.

To begin with, one needs two large primes $p$ and $q$, preferably of comparable size; one then computes $N = pq$. The values $p$ and $q$ must be kept private, but the value of $N$ will be made public. (Having $p$ and $q$ be of comparable size is important because otherwise, one can try to use a factorization technique that looks specifically for the smaller prime factor, e.g., trial division.)

p = random_prime(2^512)
q = random_prime(2^512)
N = p*q
print(N)

factor(N) ## This won't work.

Since we know the factorization of $N$ as $p*q$, we can compute the Euler phi function $\varphi(N) = (p-1)(q-1)$. This must be kept secret!

ph = (p-1)*(q-1)
print ph

Let's say we want to have a public key for encryption and a secret key for decryption. We pick a value $e$ coprime to $\varphi(N)$ and make that public. We then compute the reciprocal of $e$ mod $\varphi(N)$, called $d$, and keep that private.

e = random_prime(2^64)
d = e^(-1) % ph
print e, d

Now suppose someone wants to send us a secure message. The message must first be transformed into an integer (having no common factor with $N$, but this is essentially automatic because $N$ has only huge prime factors).

s = "MEET ME AT LA JOLLA COVE"
m = Integer("".join(str(ord(i)) for i in s))
m

Our correspondent encrypts $m$ by computing $m^e \pmod{N}$. In addition to $m$, this uses only the public information of $e$ and $N$.

t = power_mod(m, e, N)
t

We receive the ciphertext $t$ and then decrypt it by computing $t^d \pmod{N}$. This uses the private information of $d$.

m1 = power_mod(t, d, N)
m1

Finally, we translate this integer back into a string.

s1 = str(m1)
l = [int(s1[i:i+2]) for i in range(0, len(s1), 2)]
s2 = "".join(str(chr(int(i))) for i in l)
s2

Exercise: decrypt the following ciphertext.

t = 59873471716565803944771270128085762601539360364470353235906296955219120670271150480102119909806465275933886969796440538053292644178392537227649511499411626195432361095619438807522877706183346812568483348689251578790989056777780744964233590108786257841933909842779901814699479096055916059332555272527558592132

One can also do this in reverse: we can use the secret key to encode a message which anyone can decrypt using the public key. This is an example of authentication: the fact that the message decrypts correctly proves that we must have sent it, because (presumably) no one other than us has access to the secret information needed to compute the secret key!

This demonstration is an oversimplification for several reasons: see https://en.wikipedia.org/wiki/RSA_(cryptosystem).

The security of RSA depends on the practical difficulty of factoring $N$. (In principle, there might exist a method for breaking RSA without directly factoring $N$, but no such techniques are currently known.) See https://members.loria.fr/PZimmermann/records/factor.html for some "factoring records".

As with Diffie-Hellman, the performance of RSA is inferior to that of symmetric encryption systems of comparable security. One thus typically uses RSA to encrypt/decrypt a key to then be used for symmetric encryption/decryption.

In addition to being the most widely used public key cryptographic system on the internet, RSA can also be used in SMART CARDS.

Smart cards have a tiny chip embedded in them that allows the card to communicate with the bank through, say, the ATM.

The bank chooses two large primes $p$ and $q$ and computes the modulus $N = pq.$ It programs each card with the RSA encryption with an encryption exponent $e$ specific to that card.

p = random_prime(2^512)
q = random_prime(2^512)
N = p*q
print(N)

The bank needs to compute $\varphi(N),$ which it can do since it knows $p$ and $q.$

ph = (p-1)*(q-1)
print ph

Upon receiving the card, the customer chooses a PIN. The bank stores in each customer account the PIN and the decrypting exponent $d.$ Note that the customer does not know $d.$

e = random_prime(2^64)
d = e^(-1) % ph
print 'encryption exponent program in the chip e =', e
print 'decryption exponent stored by the bank d =', d

When the customer inserts the card at an ATM and enters the PIN, the bank retrieves $d$ from the customer file, picks a random integer $M<N$ and sends $$M^d \pmod N$$ to the card.

M = ZZ.random_element(1,2^100)
t = power_mod (M, d , N)
print M
print t

The card computes $M = t^e \pmod N$ and sends $(M+1)^e \pmod N$ to the bank.

MC = power_mod(t,e,N)
MC - M

r = power_mod(MC+1, e, N) 
print r

The bank computes $$r^d \pmod N = ((M+1)^d)^e \pmod N \equiv M +1 \pmod N$$ and checks that $r - M=1.$ If this holds, it accepts that the card is genuine.

power_mod(r,d,N)- M

Key point: The ATM only sees $M^d\pmod N$ and $(M+1)^e\pmod N$ go through and cannot recover $e,$ which is the crucial piece of information that the card contains.