Transcript Document

Ch1 - Algorithms with numbers

Basic arithmetic






Addition
Multiplication
Division
Modular arithmetic
RSA –factoring is hard
Primality testing
Addition

53+35=88

Cost? (n – number of bits)

O(n)
Multiplication

13x11=143

Cost?

O(n2)
al-Khwārizmī

Operations




determining parity (even or odd)
addition
duplation (doubling a number, left shift)
mediation (halving a number, rounding down, right shift)
al-Khwārizmī

Cost?


O(n2)
Can we do better?
Division

Cost?
Modular arithmetic

A system for dealing with restricted ranges of
integers

Addition
x+y mod N, assuming x, y <N
 O(n), n - number of bits N has (size of input)
(x+y mod N = x+y or x+y-N)


Multiplication
x*y mod N
 ?

Modular arithmetic
RSA





Ron Rivest, Adi Shamir, Leonard Adleman (1977)
Algorithm for public-key cryptography, based on
the presumed difficulty of the factoring problem.
2002 A.M. Turing Award
RSA is one of the most used cryptographic
protocols on the net. Your browser uses it to
establish a secure session with a site.
Needed for implementing RSA:





FLT (Fermat’s Little Theorem)
Fast Exponentiation
Extended Euclidean Algorithm
Modular inverses
CRT (Chinese Remainder Theorem)
Turing Lecture on Early RSA Days, Ronald L. Rivest
Turing Lecture on Early RSA Days, Ronald L. Rivest
Turing Lecture on Early RSA Days, Ronald L. Rivest
In April 2012, the factorization of 143 is achieved.
RSA public-key cryptosystem
In a public-key cryptosystem, everyone has a public key and a
secret key. Suppose Alice and Bob are two participants.
Alice PA , SA
Bob PB , SB
The keys specify 1-1 functions from message M to itself:
M= SA (PA (M))
M= PA (SA (M))
Encryption:
encrypt
M
PA
Communication
channel
Bob
decrypt
SA
Alice
PA(M)
M
RSA
Digital signatures:
SA
PA
Communication
channel
M
Alice
M
Bob
SA(M)
=?
Accept
RSA algorithm






Select at random 2 large prime numbers p & q;
(p & q might be, say, 100 decimal digits each.)
Compute n: n = pq;
Select an odd integer e that is relatively prime to
(n) = (p-1)(q-1);
Compute d as the multiplicative inverse of e, modulo (n);
(de  1 mod (n))
Publish P = (e, n) as the RSA public key;
Keep secret S = (d, n) as the RSA secret key.
If M Zn ={0,1,…,n-1},
P(M) = Me mod n
S(C) = Cd mod n, C=P(M).
RSA example
Pick p = 47, q=71.
n=pq=3337.
(n) = (p-1)(q-1)=46*70=3220, choose e=79 (at random).
d =79-1 mod 3220 = 1019.
PA=(79, 3337).
SA=(1019, 3337).
Message: M = 6882326879666683
= 688 232 687 966 668 3
M1 = 688  68879 mod 3337 = 1570 =C1
M2 = 232  23279 mod 3337 = 2756 =C2
…
C = 1570 2756 2091 2276 2423 158
C1 = 1570  15701019 mod 3337 = 688 =M1
…
C2 = 158  1581019 mod 3337 = 3 =M2
Another example
m e mod n
n = 4559, e = 13.
Smiley Transmits: “Last name Smiley”

L A S T
N A M E
S M I L E Y

1201 1920 0014 0113 0500 1913 0912 0525

120113 mod 4559, 192013 mod 4559, …

1074 0116 1478 2150 3906 4256 1445 2462
RSA
Bob receives the encrypted blocks c = m e mod n.
He have a private decryption exponent d
which when applied to c recovers the original
blocks m : (m e mod n )d mod n = m
For n = 4559, e = 13
the decryptor d = 3397.
RSA
n = 4559, d = 3397

1074 0116 1478 2150 3906 4256 1445 2462

1074 3397 mod 4559, 01163397 mod 4559, …

1201 1920 0014 0113 0500 1913 0912 0525

LA S T
N A M E
S M I L E Y
RSA
Technical difficulties:







How do we know the algorithm works correctly?
How to pick large prime numbers?
Compute pq
How to choose e
Compute d
How to compute Me, Cd
Can any one break the code?
RSA

If I want to encrypt credit card numbers, how
big my p and q should be?

If I want to encrypt words of four random
characters from ASCII set, how big my p and q
should be?
How to pick large
prime numbers ?
Primality testing


Hard, but much easier than factoring.
Fermat’s Little Theorem(~1640):
If p is prime, then a, s.t. 1≤a<p, ap-11 (mod p).
?

The numbers make us fail are called
Fermat pseudoprime -extremely rare (ex.
2340=1mod341; Carmichael number 561, 2560=1mod561)
Lagrange’s Prime Number
Theorem
Theorem: The number of prime numbers between 1
and x is “about” x/lnx .
Not only are primes easy to detect, but they are
also relatively abundant.
Carmichael number
A number c is a Carmichael number if it is not a
prime, and still for all prime divisors d of c it
so happens that d-1divides c-1. The smallest
Carmichael number is 561 = 31117 .
If c is a Carmichael number and a is relatively
prime to c, then ac-1  1 mod c.
Primality testing
Primality testing
Fermat's Last Theorem
Fermat's Last Theorem
states that
xn + yn = zn
has no non-zero integer
solutions for x, y and z
when n > 2.
RSA
Technical difficulties:







How do we know the algorithm works correctly?
How to pick large prime numbers?
Compute pq
How to choose e
Compute d
How to compute Me, Cd?
Can any one break the code?
How to compute
e
M,
d
C ?
Modular exponentiation
In order to implement RSA, exponentiation
relative some modulo needs to be done a lot. So
this operation better be doable, and fast.
Q: How is it even possible to compute 28533397
mod 4559 ? After all, 28533397 has
approximately 3397·4 digits!
Modular exponentiation
A: By taking the mod after each multiplication.
For example:
233 mod 30  -73 (mod 30)
 (-7)2 ·(-7) (mod 30)  49 · (-7) (mod 30)
 19·(-7) (mod 30)  -133 (mod 30)
 17 (mod 30)
Modular exponentiation
Therefore, 233 mod 30 = 17.
Q: What if had to figure out 2316 mod 30. Same
way tedious: need to multiply 15 times.
Is there a better way?
Modular exponentiation
A: Better way. Notice that 16 = 2·2·2·2 so that 2316 =
232·2·2·2 = (((232)2)2)2
Therefore:
2316 mod 30  (((-72)2)2)2 (mod 30)
 (((49)2)2)2 (mod 30)  (((-11)2)2)2 (mod 30)
 ((121)2)2 (mod 30)  ((1)2 )2 (mod 30)
 (1)2 (mod 30)  1(mod 30)
Which implies that 2316 mod 30 = 1.
Q: How about 2325 mod 30 ?
Modular exponentiation
A: The previous method of repeated squaring works
for any exponent that’s a power of 2. 25 isn’t.
However, we can break 25 down as a sum of such
powers: 25 = 16 + 8 + 1. Apply repeated squaring to
each part, and multiply the results together. Previous
calculation:
238 mod 30 = 2316 mod 30 = 1
Thus: 2325 mod 30  2316+8+1 (mod 30) 
Modular exponentiation

x25 mod N

Cost? – polynomial time (n=logN)
Modular exponentiation
How do we compute xy mod m , m>0?
repeated squaring algorithm:
mod-exp(x, y, m)
if y = 0 then return(1)
else
z = mod-exp(x, y div 2, m)
if y mod 2 = 0 then return(z * z mod m)
else return(x * z * z mod m)
Compute d ?
Modular Inverse
GCD

Greatest common divisor

Example:
Euclid Algorithm
If a,bZ+, apply division (mod) repeatedly as follows:
a = q1b + r1,
b = q2r1 + r2,
r1 = q3r2 + r3,
……
rk-2 = qkrk-1+ rk,
rk-1 = qk+1rk
Then, rk = GCD(a,b).
Proof: (1) rk|a, rk|b
(2) if d|a, d|b, then d| rk.
where 0 < r1 < b
where 0 < r2 < r1
where 0 < r3 < r2
where 0 < rk-1 < rk
Recursion Theorem
a,b  N, b0, gcd(a,b) = gcd(b, a mod b).
Proof :
Let d = gcd(a,b).  d|a, d|b.
d|a-qb = a mod b  d|b, d|a mod b  d|gcd(b, a mod b).
Let d = gcd(b, a mod b).  d|b, d| a mod b.
d|a-qb, d|b  d|a  d|gcd(a,b).
 gcd(a,b) = gcd(b, a mod b).
Computing GCD
Euclid gcd(x,y) {
if y = 0 then return(x)
else return(gcd(y,x mod y))
}
Euclid Algorithm
Example: Computing gcd(125, 87)
125 = 1*87 + 38
87 = 2*38 + 11
38 = 3*11 + 5
11 = 2*5 + 1
5 = 5*1
 gcd(125,87)=1
gcd(125,87) = 1
11 - 2*5
=1
11 - 2*(38-3*11) = 1
- 2*38 + 7*11 = 1
- 2*38 + 7*(87 - 2*38) = 1
7*87 - 16*38 = 1
7*87 - 16*(125-1*87) = 1
- 16*125 + 23*87 = 1
1 = 125*(-16) + 87*23
1 = as + bt
Extended Euclidean Algorithm

obtain gcd(a,b) and x,y, s.t. gcd(a,b) = ax+by.
Extended-Euclid (a,b)
if (b==0)
return (a,1,0);
(d’,x’,y’)=Extended-Euclid(b, a mod b);
(d,x,y)=(d’, y’, x’-a/by’);
return (d,x,y);
Ex:
demo
a
412
260
152
108
44
20
4
b
260
152
108
44
20
4
0
q
1
1
1
2
2
5
x
12
-7
5
-2
1
0
1
y
-19
12
-7
5
-2
1
0
d
4
4
4
4
4
4
4
Cost?
Theorem: The algorithm above correctly computes the
gcd of x and y in time O(n), where n is the total
number of bits in the input (x; y)
Multiplicative Inverse
Multiplicative inverse x of a, modulo n:
ax = 1 mod n.
 ax = kn+1
If gcd(a,n)=1, ax-kn = gcd(a,n).  ax+ny =
gcd(a,n).
Therefore, x can be found using extended
Euclidean algorithm.
Is the multiplicative inverse unique?
Multiplicative Inverse
Theorem:
 n>1, if gcd(a,n)=1, then ax=1 (mod n) has a unique
positive solution, modulo n.
Example:
a = 79; n = 3220.
x = 1019.
ax = 80501 = 25*3220+1.
x = -2201.
ax = -173879 = -54*3220+1.
RSA
Technical difficulties:







How do we know the algorithm works correctly?
How to pick large prime numbers?
Compute pq
How to choose e
Compute d
How to compute Me, Cd?
Can any one break the code?
How do we know RSA works
correctly?
Chinese Remainder Theorem (~1700 old)

http://en.wikipedia.org/wiki/RSA_Factoring_C
hallenge#The_prizes_and_records