2016-05-25.sagews

Math 480: Open Source Mathematical Software

2016-05-25

William Stein

Lectures 26: Public key cryptography (part 2 of 3): RSA

Plan:

1. Homework/grading reminder.

2. Next week -- discussion

3. Today: explain RSA

4. Work on homework

n = 17*13
n

221

m = n/13
m

17

is_prime(m)

False

# WTF?!

parent(m)

Rational Field

type(m)

<type 'sage.rings.rational.Rational'>

is_prime(ZZ(m))

True

m = n//17  # floor division
is_prime(m)

True

%md

WE will not meet next week.  There are 9 assignments.
You will be completely done with everything related to this
class on Friday May 27 at 6pm.

WE will not meet next week. There are 9 assignments. You will be completely done with everything related to this class on Friday May 27 at 6pm.

Recall... the Diffie-Hellman key exchange:

• A and B agree on $g \in \ZZ/p\ZZ$.

• A and B choose random $a,b$ and send $g^a$ and $g^b$.

• The shared secret is $s = (g^a)^b = g^{ab} = (g^b)^a$, which both A and B can easily compute, but an eavesdropper (presumably) can't.

DH is simple, beautifully symmetric, and is useful for setting up an active secure channel for temporary communication:

• login to a website, ssh to a remote computer, etc.

---

DH does not solve a lot of interesting problems though. For example:

• B publishes some information -- a "public key" -- on their website.

• Anybody at any time, and without B having to do anything, can encrypt a message that only B can decrypt.

There is a solution to this problem, which also uses modular arithmetic. It's completely different than Diffie-Hellman!

## The RSA Cryptosystem

RSA = Rivest-Shamir-Adleman

(Errata: In the lecture yesterday I said GCHQ secretly also discovered DH, but actually they also discovered RSA.)

---

How RSA works. There's one basic idea from number theory that you have to know about to understand RSA.

Let $p$ be a prime. Fermat's Little Theorem says that for every integer $a$ coprime to $p$, we have $$a^{p-1} \equiv 1 \pmod{p}?$$

Try it out:

p = 23
for a in [1..p]:
    print a, Mod(a, p)^(p-1)

1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 0

Proof: The cardinality of the finite group $(\ZZ/p\ZZ)^*$ is $p-1$ and it's a basic result in group theory that the order of any element of a group divides the cardinality of the group.

---

Similarly for component $n$, we have that if $\gcd(a,n)=1$, then $$a^{\varphi(n)} \equiv 1\pmod{n}$$ since $(\ZZ/n\ZZ)^*$ is a group of order $\varphi(n)$.

$\varphi(pq) = (p-1)\cdot (q-1)$

n = 20
r = euler_phi(n)
print "phi(n) =",r
for a in range(n ):
    if gcd(a,n) == 1:
        print a, Mod(a, n)^r

phi(n) = 8 1 1 3 1 7 1 9 1 11 1 13 1 17 1 19 1

So A wants to send a secret message to B.... here's how.

• Step 1. Setup:

  • B secretly chooses two large prime numbers $p$ and $q$ at random and an integer $e$, and publishes $n=pq$ and $e$.

  • B knows $p$ and $q$, so B can compute $\varphi(n) = (p-1)(q-1)$, and also an integer $d$ such that $ed \equiv 1\pmod{\varphi(n)}$. Thus $ed = 1 + k \varphi(n)$ for some $k$.

• Step 2. Encryption:

  • A encodes the message as an integer $m$ modulo $n$.

  • Then A encrypts the message as $t = m^e\pmod{n}$.

• Step 3. Decryption:

  • B decrypts the message by using that $t^d = (m^e)^d = m^{ed} \equiv m^{1 + k \varphi(n)} \equiv m \pmod{n}$.

This last step uses that $m^{\varphi(n)} \equiv 1 \pmod{n}$.

Let's try it out!

# Step 1: Setup

p = next_prime(ZZ.random_element(2^512))
q = next_prime(ZZ.random_element(2^512))
n = p*q
phi_n = (p-1)*(q-1)
e = 3
while gcd(e,phi_n) != 1:
    e += 1
d = lift(Mod(e, phi_n)^(-1))

print "The public key is"
print "n = ", n
print "e = ", e

The public key is n = 127717216655786214407091437662444535749240552276188026026427394576414330429686365856608957838339533186272346532099546180841055184529875110136739492764846143081619571729358853474181117437999752291983686706308467169947599687577490140584859209847850830815390728760381909678660035069619669698275354542903092012863 e = 5

p
q

11463368583518816195787609756897898284888539745888965156407126837019661148148807294536195138721126453036527341500687788272583142912271920887347296047713787 11141333869296376436073235965344735632605597694471878317528404059237811366014809628047379815780769901731658405686156650902790055262464327433289086651767949

e*d % phi_n

1

parent(lift(Mod(7,15)))

Integer Ring

# Step 2: Encryption

## Encode our message as a number in base 26:

mesg = "tectonicxxandxxsharkxxtankxxarexxundercover"
m = 0
for i, a in enumerate(mesg):
    m += 26^i * (ord(a) - ord('a'))
print "m = ", m

## Then encrypt it!

t = Mod(m, n)^e
print "encrypted message = ", t

m = 4613687604820056968581129277215495307270152505781622265499707 encrypted message = 2090455487101886385630288527493944868161255825812498262608543045261122043038713760594614274905819576983374630438491620026262028329203562995688652685487539330950833374308981223237077748047967907563093111920869083873677573237976419884774298362346381558097543809500667583082778777187834544360943888902615307

# Step 3: Decryption

r = lift(t^d)
print "decrypted message = ", r

## And decode
z = ''
while r:
    z += chr((r % 26) + ord('a'))
    r = r//26

print "message = ", z

decrypted message = 4613687604820056968581129277215495307270152505781622265499707 message = tectonicxxandxxsharkxxtankxxarexxundercover

Attacking RSA

To attack RSA the observer has to compute $m\pmod{n}$ given $m^e\pmod{n}$.

That is NOT the discrete log problem again! (Why?)

In theory, the attacker has all the information they need. They know $n$, so they can "just" factor $n$ to find $p,q$, then compute $\varphi(n)=(p-1)(q-1)$, and $d$ as above.

However... factoring large numbers seems to be really frickin' hard.

n

127717216655786214407091437662444535749240552276188026026427394576414330429686365856608957838339533186272346532099546180841055184529875110136739492764846143081619571729358853474181117437999752291983686706308467169947599687577490140584859209847850830815390728760381909678660035069619669698275354542903092012863

e

5

Mod(389, n)^e

8907339520949

Mod(8907339520949, n)^d

389

is_prime(n)

False

factor(n) # will just waste cpu forever

Error in lines 1-1 Traceback (most recent call last): File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/arith.py", line 2459, in factor int_ = int_, verbose=verbose) File "sage/rings/integer.pyx", line 3511, in sage.rings.integer.Integer.factor (/projects/sage/sage-6.10/src/build/cythonized/sage/rings/integer.c:22694) F = factor_using_pari(n, int_=int_, debug_level=verbose, proof=proof) File "sage/rings/factorint.pyx", line 352, in sage.rings.factorint.factor_using_pari (/projects/sage/sage-6.10/src/build/cythonized/sage/rings/factorint.c:6295) p, e = n._pari_().factor(proof=proof) File "sage/libs/pari/gen.pyx", line 8977, in sage.libs.pari.gen.gen.factor (/projects/sage/sage-6.10/src/build/cythonized/sage/libs/pari/gen.c:140617) pari_catch_sig_on() File "sage/ext/interrupt/interrupt.pyx", line 88, in sage.ext.interrupt.interrupt.sig_raise_exception (/projects/sage/sage-6.10/src/build/cythonized/sage/ext/interrupt/interrupt.c:924) raise KeyboardInterrupt KeyboardInterrupt

OK, now work on your homework...