Transcript 1 (mod n)

The RSA Cryptosystem
and Factoring Integers (I)
Rong-Jaye Chen
OUTLINE

[1] Modular Arithmetic Algorithms
[2] The RSA Cryptosystem

[3] Quadratic Residues

[4] Primality Testing

[5] Square Roots Modulo n

[6] Factoring Algorithms

[7] Other Attacks on RSA

[8] The Rabin Cryptosystem

[9] Semantics Security of RSA

p2.

[1] Modular Arithmetic Algorithms

1. The integers
 a divides b  a|b
 If b has a divisor a {1,b} , then a is said to be
nontrivial.
 a is prime if it has no nontrivial divisors; otherwise, a is
composite.
 The prime theorem：
{a is prime | a  [2, x ]}   ( x ) ~ x / log x


If c|a and c|b, then c is common divisor of a and b.
If d is a great common divisor of a and b, then we write
d=gcd(a,b).
p3.


Euclidean algorithm(a,b)
(for great common divisor)
input： a  b  0
output：d  gcd( a, b)
(1) Set r0=a and r1=b
(2) Determine the first n  0 so that rn+1=0,
where ri+1=ri-1 mod ri
(3) Return (rn)
Extended Euclidean algorithm(a,b)
input：a>0, b>0
output: (r, s, t) with r=gcd(a,b) and sa+tb=r
(Omitted)
p4.

Example ：gcd(299,221)=?
299  1  221  78
( q2  1, r2  78)
221  2  78  65
( q3  2, r3  65)
78  1  65  13
( q4  1, r4  13)
65  5  13  0
( q5  5, r5  0)
gcd( 299,221)  r4  13  78  65
 78  (221  2  78)  3  78  221
 3  (299  1  221)  221  3  299  4  221
p5.


If gcd(a,b)=1, then a and b are said to be
relatively prime.
Phi function：
 (n) #{a | gcd(a, n)  1 and 1  a  n}
1.  ( p e )  ( p  1) p e1 for prime p
2.  (ab)   (a) (b) for gcd( a, b)  1
p6.

2. The integers modulo n



a is congruent to b modulo n, written a  b (mod n ) ,
if n|a-b.
Zn={0,1,…,n-1}
Given a  Z n , if  x  Z n s.t. ax  1 (mod n), then a is
said to be invertible and its inverse x is denoted a-1.
p7.

Use Extended Euclidean Algo to calculate a-1 mod n

Example：a=7 and n=9
Euclidean algorithm
to find gcd(a,n)
9  1 7  2
7  3 2 1
2  21  0
Extended Euclidean algorithm
to write gcd(a,b)=sa+tn
1  7  3 2
 7  3(9  1  7)  4  7  3  9
7 1  4 mod 9
p8.

Zn*={a|gcd(a,n)=1 and 0<a<n}


 (n) is defined as Z n*
For example, Z12*={1,5,7,11},
Z15*={1,2,4,7,8,11,13,14}

(Zn*, *) forms a multiplication group
p9.

Fermat’s little theorem：
If a  Z *p ( p is prime) , then a p1  1 (mod p)

Euler’s theorem：
If a  Z n* , then a ( n )  1 (mod n)


The order of a  Z n* , written ord(a), as the least positive
integer t such that at  1(mod n).
*
*
If a  Z n , has ord ( a )  Z n   ( n) , then a is said to be a
generator of Zn*; in this case, Z *  {a i | 0  i   (n)}.
n
p10.

Example ：n=15
Z15*={1,2,4,7,8,11,13,14}
ψ(15)= ψ(3) ψ(5)=2*4=8
a  Z15*
1
2
4
7
8
11
13
14
ord (a)
1
4
2
4
2
2
4
2
p11.

3. Chinese remainder theorem
If the integers n1,…,nk are pairwise relatively prime,
then the system of congruences
x  a1 (mod n1 )
x  a2 (mod n2 )
x  ak (mod nk )
has a unique solution modulo n=n1*n2*…*n k
p12.

Algorithm：Gauss algorithm
(1) Input k , ni , ai , for i=1,2,…,k
(2) Compute N i 
n
n
j
for i=1,2,…,k
j 1, j  i
(3) Compute inverse
(4) Compute
M i  N i1 mod ni for i =1,2,…,k
k
x   ai N i M i mod n
i 1
p13.
Example
x  1 mod 3
x  6 mod 7
x  8 mod 10
According to Gauss algorithm,
x  1  70  (701 mod 3)  6  30  (301 mod 7)  8  21  ( 211 mod 10)
 1  70  (11 mod 3)  6  30  ( 2 1 mod 7)  8  21  (11 mod 10)
 1  70  1  6  30  4  8  21  1
 958 mod 210  118
p14.

4. Square-and-Multiply

Algorithm: Square-and-Multiply(x, c, n)
Input：
x  Zn
, c with binary representation c 
Output： x mod n
c
l 1
i
c
2
i
i 0
z 1
for i  l  1 downto 0
do z  z 2 mod n
if ci  1
then z  (z  x) mod n
return ( z )
p15.
Example :
97263533 mode 11413=?
i
ci
z
11
1
12x9726=9726
10
1
97262x9726=2659
9
0
26592=5634
8
1
56342x9726=9167
7
1
91672x9726=4958
6
1
49582x9726=7783
5
0
77832=6298
4
0
62982=4629
3
1
46292x9726=10185
2
1
101852x9726=105
1
0
1052=11025
0
1
110252x9726=5761
p16.

[2] The RSA Cryptosystem




Proposed by Rivest, Shamir, and Adleman (1977)
Used for encryption and signature schemes
Based on the intractability of the integer factorization
problem
Key generation
 Let p, q be large prime, n=pq and (n)=(p-1)(q-1)
 Choose randomly b s.t. gcd(b,(n))=1
-1 mod (n)
 Compute a  b
 Public-key: (n, b)
 Private-key: (n, a) or (p, q, a)
p17.

RSA Cryptosystem
Let n=pq, where p and q are primes.
Let P = C = Zn , and define
K ={(n,p,q,a,b): ab=1 (mod (n))}.
For K= (n,p,q,a,b), define
eK(x)=xb mod n
and
dK(y)=ya mod n


Public-key: (n, b)
Private-key: (n, a) or (p, q, a)
p18.

Verify the encryption and decryption are inverse operations
ab=1 (mod (n)),
we have ab = t(n)+1, for t>=1
Suppose that x in Zn*; then we have
(xb)a = xt(n)+1 (mod n)
= (x(n))tx
= 1tx (mod n)
= x (mod n)
As desired. For x in Zn but not in Zn*, (do exercise)
p19.

Eg. p=7, q=13, n=91, (n)=(p-1)(q-1)=72

Choose b=5, compute a=b-1=29

Public-key: (91,5)

Private-key: (7,13,29)

Assume message m=23
So cipher-text c = me mod n = 235 mod 91 = 4
and can be decrypted by
m = cd mod n = 429 mod 91 = 23
p20.

RSA encryption
Alice
M
KUBob
E
KRBob
C
D
M
n = pq
b*a = 1 (mod ø(n))
Private key
KRBob = (n, a)
Public key
KUBob = (n, b)
Bob
EKUBob(M)=
Mb (mod n)
Encryption
DKRBob(C)=
Ca (mod n)
Decryption
p21.
n = pq
b*a = 1 (mod ø(n))
Signing key
KRAlice = (n, a)
Verification
key

KUAlice = (n, b)
RSA signature scheme
Alice
M
M
Hash
KRAlice A
H
E
EKRAlice(H(M))=
H(M)a (mod n)
Signing
H
KUAlice
Compare
Bob
D
DKUAlice(A)=
Ab (mod n)
Verification
p22.

[3] Quadratic Residue

1. Quadratic residue modulo n
*
 Let a  Z n , then a is a quadratic residue modulo n
*
if there exists x  Z n with
x 2  a(mod n). In this case,
x is a square root of a modulo n. Otherwise, a is a
quadratic nonresidue modulo n.

Qn：the set of quadratic residues modulo n.

Qn ：the set of quadratic nonresidues modulo n.

Z n*  Qn  Qn
p23.

2. Theorem ：p > 2 is prime and α is a generator of Zp*
a  Z *p is a quadratic residue modulo p  i  Z s.t. a   2i (mod p)
p24.

3. Corollary ： p > 2 is prime and α is a generator of Zp*

(1)
Q p  { i mod p | i even, 0  i  p  2}
Q p  { i mod p | i odd, 0  i  p  2}


(2) Qp  Qp  ( p  1) / 2

(3) If a  Q p , then x 2  a(mod p) has exactly t wo solutions.

(4)

p 1
2
 1(mod p)
4. Legendre symbol  a  ：p > 2 is prime and a  Z
 p
 
a
  
 p
0
p|a
1
a mod p  Qp
1
a mod p  Qp
p25.

5. Theorem ：Euler’s criterion

6. E.g ：  3   ?
p1
a
p is prime and a  Z , then    a 2 (mod p)
 p
 23 
23 - 1
 10112
2
use Square-and-Multiply
231
 3
   3 2 mod 23  1, so 3  Q23
 23 
p26.

7. Jacobi symbol  a  ：
 n
n > 2 is an odd integer, pi is prime and n  p1e1  p1ek
e1
 a 
a  a 


      
 n   p1 
 pk 
ek
p27.

8. Properties of Jacobi symbol：m, n > 2 are odd integers




(1)  a 
a
   {1,0,1}, and    0  gcd( a,n)  1
 n
 n
(2)  ab    a  b  and  a    a  a 
    

   
 n   n  n 
 mn   m  n 
a b
If a  b(mod n) then     
 n  n
n 1
 1, n  1(mod 4)
1
  1
(4)    1 and 
  ( 1) 2  
 n
 n 
 1, n  3(mod 4)
(3)

(5)

(6)
 2
 
 n
n 2 1
( 1) 8
 1, n  1(mod 8)

 1, n  3(mod 8)
 m  n 
    (-1)
 n   m
m-1 n-1
2 2
p28.

9. E.g ：calculate Jacobi symbol without factoring n
a  28, n  55
2
 28   2   7 
    
 55   55   55 
 55 
  ( 1)
 7
(property 2)
551 7 1
2 2
(property 6)
 55 
 6
     
 7
7
  1
    ( 1)
 7 
(property 3)
71
2
1
(property 4)
p29.

10. Jacobi symbol V.S. Quadratic residue modulo n




a
   1  a  Qn
 n
a
definition J n  {a  Z n* |    1}
 n
The element of
~
Qn  J n \ Qn are called psedosquares modulo n.
~
Qn  J n , and Qn  J n in the case n is prime.
p30.

11. E.g ：n=15
 a   1, a  1(mod 3),
 a   a  a 
 

and
    
 3   1, a  2(mod 3),
15
3
5
    
 a   1, a  1(mod 5),
 
 5   1, a  2(mod 5).
a
The Jacobi symbol   are calculated in the following table：
 n
*
a  Z15
a
 
 3
a
 
 5
 a
 
 15 
1
2
4
7
8
11 13
14
1
-1
1
1
-1
-1
1
-1
1
-1
1
-1
-1
1
-1
1
1
1
1
-1
1
-1
-1
-1
~
Hence, J15  {1,2,4,8}. It can be verfied that Q15  {1,4}, then Q15  J15 \ Q15  {2,8}
p31.

12. Quadratic residuosity problem(QRP)
Determine if a given a  J n is a quadratic residue or
pseudosquare modulo n
p32.

[4] Primality Testing
(1) Prime numbers

1. How to generate large prime numbers?
(1) Generate as candidate a random odd number n of
appropriate size.
(2) Test n for primality.
(3) If n is composite, return to the first step.
p33.

2. Distribution of prime numbers
(1) prime number theorem
Let Π(x) denote the number of prime
numbers ≦x.
Π(x) ~ x/ln(x) when n∞.
(2)Dirichlet theorem
If gcd(a, n)=1, then there are infinitely many
primes congruent to a mod n.
p34.
(3) Let Π(x, n, a) denote the number of primes in the
interval [2, x] which are congruent to a modulo n,
where gcd(a, n)=1 . Then
Π(x, n, a) ~
x
 ( n) ln x
The prime numbers are roughly uniformly distributed
among the φ(n) congruence classes in Zn*
(4) Approximation for the nth prime number pn
n ln n  pn  n( ln n  ln ln n) for n  6
p35.
(2) Solovay-Strassen primality test

1. Trial method for testing n is prime or composite
 a  [2, n ], if a does not divide n  n is prime

2. Definition ：Euler witness
Let n be an odd composite integer and
(1) If
1  a.  n
a
gcd(a, n)  1 or a ( n 1) / 2    (mod n)
n
then a is an Euler witness (to compositeness) for n.
p36.
(2) Otherwise, if
gcd( a, n)  1 and a
( n 1) / 2
a
   (mod n)
n
then n is said to be an Euler pseudoprime to
the base a. The integer a is called an Euler liar
(to primality) for n.
p37.

3. Example (Euler pseudoprime)
 Consider n = 91 (= 7x13)
9
Since 945 =1 mod 91, and    1
 91 
so 91 is an Euler pseudoprime to the base 9.

4. Fact
At most Φ(n)/2 of all the numbers a, are Euler liars
for n.
p38.

5. Algorithm ：Solovay-Strassen(n, t)

INPUT: n is odd, n ≧3, t ≧1

OUTPUT: “prime” or “composite”

1. for i = 1 to t do :
1.1 choose a random integer a, 2 ≦ a≦n-2
if gcd(a,n) ≠1 then return ( “composite” )
1.2 compute r=a(n-1)/2 mod n (use square-andmultiply)
if r ≠ 1 and r ≠ n-1 then return ( “composite” )
a
 
n
1.3 compute Jacobi symbol s=
if r ≠ s then return ( “composite” )

2. return ( “prime” )
p39.

6. Solovay-Strassen error-probability bound
 For any odd composite integer n, the
probability that Solovay-Strassen (n, t)
declares n to be “prime” is less than (1/2)t
p40.

(3) Miller-Rabin primality test

1. Fact
 P : odd prime
p-1 = 2sr, where r is odd
a  N , gcd (a, p) = 1
then ar = 1 (mod n)
j
or a2 r = -1 (mod n) for some j, 0≦ j≦s-1

Why ?
(1) Fermat’s little theorem, ap-1 = 1 mod p
(2) 1, -1 are the only two square roots of 1 in Zp*
p41.

2. Definition
 n : odd composite integer
n-1 = 2sr, where r is odd
1≦a ≦n-1
 a is a strong witness to compositeness for n
if ar ≠ 1 (mod n), and
j
a2 r ≠ -1 (mod n) for all j, 0≦ j≦s-1

n is a strong pseudoprime to the base a
if ar =
1 (mod n)
j
or a2 r = -1 (mod n) for some j, 0≦ j≦s-1
(a is called a strong liar to primality for n)
p42.

3. Algorithm: Miller-Rabin (n, t)
 INPUT: n is odd, n ≧3, t ≧1
 OUTPUT: “prime” or “composite”



1. write n-1 = 2sr such that r is odd.
2. for i = 1 to t do :
2.1 choose a random integer a, 2 ≦ a≦n-2
2.2 compute y=ar mod n (use square-and-multiply)
2.3 if y ≠ 1 and y ≠ n-1 do :
j1
while j ≦ s-1 and y ≠n-1 do :
y  y2 mod n
if y = 1 then return ( “composite” )
j  j+1
if y ≠ n-1 then return ( “composite” )
3. return ( “prime” )
p43.

4. Example (strong pseudoprime)
 Consider n = 91 (= 7x13)
 91-1 = 2*45, s=1, r=45
r
45 =1 mod 91, 91 is a strong
 Since 9 = 9
pseudoprime to the base 9.
 The set of all strong liars for 91 is {1, 9, 10,
12, 16, 17, 22, 29, 38, 53, 62, 69, 74, 75, 79,
81, 82, 90}
 The number of strong liars of for 91 is
18 = Φ(91)/4
p44.

5. Fact
 If n is an odd composite integer, then at
most ¼ of all the numbers a, 1 ≦a ≦n-1 are
strong liars for n. In fact if n=!9, then
number of strong liars for n is at most
Φ(n)/4.
p45.


6. Miller-Rabin error-probability bound
 For any odd composite integer n, the
probability that Miller-Rabin (n, t) declares
n to be “prime” is less than (1/4)t
7. Remark
 For most composite integers n, the number
of strong liars for n is actually much smaller
than the upper bound of Φ(n)/4.
 Miller-Rabin error-probability bound is much
smaller than (1/4)t .
p46.