Transcript An introduction to Modular arithmetic and Public Key cryptography.

Introduction to Modular Arithmetic and Public Key
Cryptography
What is modular arithmetic?
Modular arithmetic is arithmetic with the
remainders upon division by a fixed number n.
It is based upon the idea that the remainder of the
sum/difference/product of two numbers is the
remainder of the sum/difference/product of the
remainders.
For example, if n=5,
(31+7)%5 = 38%5 = 3, and
(31%5+7%5)%5 = 1+2=3
So, what is arithmetic mod n?
Our “numbers” are 0, 1, 2, ... (n-1).
We add, subtract as usual, but subtract or add n as
necesary to get an answer between 0 and n-1.
For multiplication, the process is similar; multiply
the two numbers together, and then take the
remainder dividing by n.
Some examples, mod n = 6.
4+3=7-6=1
3 – 5 = -2 + 6 = 4
4 * 5 = 20 % 6 = 2
WHAT ABOUT DIVISION?????
Let us say there is an x such that x * 2 = 1.
Let us also say there is a y such that y * 3 = 1
Some examples, mod n = 6.
4+3=7-6=1
3 – 5 = -2 + 6 = 4
4 * 5 = 20 % 6 = 2
WHAT ABOUT DIVISION?????
Let us say there is an x such that x * 2 = 1.
Let us also say there is a y such that y * 3 = 1
Then x * y * 2 * 3 = 6 xy = 1.
Some examples, mod n = 6.
4+3=7-6=1
3 – 5 = -2 + 6 = 4
4 * 5 = 20 % 6 = 2
WHAT ABOUT DIVISION?????
Let us say there is an x such that x * 2 = 1.
Let us also say there is a y such that y * 3 = 1
Then x * y * 2 * 3 = 6 xy = 1.
But 6*anything = 0!!!
Some examples, mod n = 6.
4+3=7-6=1
3 – 5 = -2 + 6 = 4
4 * 5 = 20 % 6 = 2
WHAT ABOUT DIVISION?????
Let us say there is an x such that x * 2 = 1.
Let us also say there is a y such that y * 3 = 1
Then x * y * 2 * 3 = 6 xy = 1.
But 6*anything = 0!!!
So 1 = 0 ?!?!?!?!?!?!?!?!?
Can we divide if n is a prime? Yes,
but......
From now on, our modulus will be a prime p.
We will show how to divide in arithmetic mod p.
Devious method!
We will need a result, called the “extended euclidean
algorithm” to pull this off.
But first, we need the euclidean algorithm to
understand what is going on.
The euclidean algorithm computes the greatest
common divisor of two positive integers.
Elementary Euclidean Algorithm
Extended Euclidean Algorithm
What can we do with the egcd?
Given two numbers a,b, the extended euclidean
algorithm finds their gcd g and two numbers s and
t such that as + bt = g.
In particular, if a and b have no common factors
(aside from 1) (i.e. they are “relatively prime”),
we can find two numbers s,t such that as + bt = 1
For modular division, if p is prime, given a, we
can find s and t such that as +tp = 1. s is then the
“multiplicative inverse” of a (suitably reduced, if
necesary).
Some more, strange, results.
Another result
Chinese remainder theorem:
Given m1, m2, m3, .... mk and a1, a2 a3, ak, where
The mi, mj are positive, pairwise relatively prime
The ai are positive integers less than mi respectively.
Then, there exists a b such that mi divides b-ai for each i.
If we require that b be less than the product of the mi, then
this b is unique.
(Proof in next slide)
Proof of Chinese Remainder Theorem
Suffices to take k=2 by induction. Thus, need to
prove that, for 0 < a < m and 0 < b < n if m and n
are relatively prime, there exists a unique u
between 0 and mn such that u % m = a; u % n = b
Since m and n are relatively prime, there exist p
,q such that pm + qn = 1.
Then bpm + aqn % mn = u satisfies all the
conditions.
The RSA Theorem
Proof of the RSA Theorem
How RSA works
Take two primes, p, q, let n=pq
Chose an e, relatively prime to (p-1)(q-1).
Find a d such that de – k(p-1)(q-1) = 1 with the
extended euclidean algorithm: then
de = 1+k(p-1)(q-1)
“Publish”, n, e as public key.
Encryption: raise a to the e-th power
Decryption: raise result to the d-th power.
“Efficient” powering to compute a^n
Another Crypto-system: DiffieHellman key exchange
Let p be a large prime, s a number between 2 and
p-2; p and s are “publicly known”.
Each person has a private key a.
Whenever two people want to exchange
messages, they send each other s^a mod p
They raise the number they receive to their
private key power mod p, and have an exchange
key for a symmetric crypto-system.
Another Crypto System: El-Gamal
As before, let p be a large (publicly known) prime
number, s some number between 2 and p-2.
Each person chooses a private key e and
“publishes” E = s raised to the e-th power mod p.
To send message x, we first generate a “session
key” k, and send t = s^k and y = E^k x mod p
We decrypt by computing t^(-e) y = x mod p