2017-03-15.sagews

%md
# 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 **

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 **

%md
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.

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)

100963787892549803870335774975462798752897814514967013692490036682902362945673908430033884725687829798271527140354648499215955907239065718747441198357107081680936918677134593092193704319533204812397391837474897512993456382438797482139188365365058323874934805238772243422463046450292767432123309301586366354789

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

Error in lines 1-1 Traceback (most recent call last): File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 982, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/arith/misc.py", line 2469, in factor int_ = int_, verbose=verbose) File "sage/rings/integer.pyx", line 3722, in sage.rings.integer.Integer.factor (/projects/sage/sage-7.5/src/build/cythonized/sage/rings/integer.c:24549) 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-7.5/src/build/cythonized/sage/rings/factorint.c:6854) p, e = n._pari_().factor(proof=proof) File "sage/libs/cypari2/gen.pyx", line 4200, in sage.libs.cypari2.gen.gen.factor (/projects/sage/sage-7.5/src/build/cythonized/sage/libs/cypari2/gen.c:124611) sig_on() File "src/cysignals/signals.pyx", line 97, in cysignals.signals.sig_raise_exception (build/src/cysignals/signals.c:1303) KeyboardInterrupt

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

100963787892549803870335774975462798752897814514967013692490036682902362945673908430033884725687829798271527140354648499215955907239065718747441198357107061433835343496455841953834698105135470043835924085341416389659223771763760832984888016906894033683879543294236947071415334853341514960107165121757346816780

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

7324753172794958867 66305393240685160738146967378976835105369132733236932422203806425504999193120635812271405929589258076507778135753243102349067711957122263246011595163432840182139806336944417582890941030751988193524136458852269913344205496136735524471084975285213375421994242312951686680007806941768501495159090885720690850783

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

776969843277693265843276653274797676653267798669

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

25896293070206027719355539873677967158215621990508115009873407678595347382546616322577271832520829565977894759543210794174701751375996375269206633020663448483645226648554510602711393246607695414518473056650924504737376892781132892132972613675625279321374045543932936656282918045086146072764782404391237454071

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

776969843277693265843276653274797676653267798669

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

'MEET ME AT LA JOLLA COVE'

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!

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

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)

51607071122431282524437863327492858943853835987496181746506869318840854117851312502635666306112832519328853189004503830693128544363622314777110890019876575620973339563611800776848050008703704851629558667385294348064452151961741989449035009200717082425343796800551924182600496582895689048038205480442332231029

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

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

51607071122431282524437863327492858943853835987496181746506869318840854117851312502635666306112832519328853189004503830693128544363622314777110890019876561121327175234979585192821578051161345516403693433615326278718692064987880582222007186019671181575931668345172515982625409168412489734100068539331850182540

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

encryption exponent program in the chip e = 17328446970395365939 decryption exponent stored by the bank d = 48382990335783798845600093459667857002944960571140791383709506438630693514568725476732788728745537862067771624513963915963136671762587666610938363194888803234797533849753463534914640042398912797015629663039519849718223764287772519956696159031341275252730273140848760756546457626048981765793721273597574469339

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

798150937365003078782795062697 5879498043427010957435994427468283950322327043633813887624122828900167859040764459555136616652772332182663896828406371638487934885753653417304722585133153647812832191590047992156138975636559245978465911210979760033632650240677981316650248424193689687855918308218022552622002949042862951465310469184580023593

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

0

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

15743764959357889101110955665599943317267482269238532612678064377546220041743979010974501943395661438748487777880247629978898039084227368935504615731720185481112180379102823309563008018483561045075960872738465639542305634490266069319533989862424669537932897607527702505311285016043289678450546502993387129919

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

1

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.