Transcript document

DAAD
2002
Cryptology
Marion Scheepers
Boise State University
Boise , Idaho
Sept 24 – 26, 2002
Information Security
Information Security = Safeguarding information during storage or transmission.
Some objectives of information security:
•Confidentiality
•Data integrity
•Authentication
•Non-repudiation
Cryptology = The mathematics of information security
The idea:



Use mathematics to secure the information
Security is mathematically compromised when some
specific mathematical problem is solved
No known method solves the mathematical problem
in a reasonable amount of time
Cryptographic Primitives




Encryption schemas
Digital signatures schemas
Hash functions
Random number generators
Crypto-system evaluation criteria



Security levels
[How many bit operations are needed to
defeat the security objective?]
Performance
[How many bit operations are needed to
carry out the security objective?]
Ease of implementation
[How “easy” is it to create the crypto-system
based on existing technology?]
Some Number Theory
Theorem [Euclidean Algorithm] :
For all natural numbers a and b, there are
integers m and n such that gcd(a,b) = ma + nb.
Theorem:
ax mod b =1 has a solution if, and only if,
gcd(a,b) = 1.
Euler’s phi function

Definition phi(n) = |{a< n: gcd(a,n) = 1}|.

Theorem [Euler - Fermat] For any a <n with
gcd(a,n) = 1, we have aphi(n) mod n = 1.
Chinese Remainder Theorem

Theorem Let m and n be numbers with
gcd(m,n) =1. Then for all a<m and b<n there
are a unique x<mn with a = x mod m and b =
x mod n.
Dirichlet’s Theorem

Theorem If gcd(a,b) = 1, then the set
{an + b: n=1, 2, 3, …}
contains infinitely many prime numbers.

Riemann Hypothesis (RH):
For all e>0: pi(x) = li(x)+O(x(1/2 + e))

Extended Riemann Hypothesis (ERH):
For all e>0: pi(x,n,a) = li(x)/phi(n)+O(x(1/2 + e))
Miller-Rabin Primality test

Theorem If n is an odd prime, write n-1 = r
2s where r is odd. For any a with gcd(a,n) =
1,
1.
2.

either ar mod n = 1, or else
there is a j = 0, 1, .., s-1 with a(r 2^j) mod n = n-1
Theorem For n > 9 odd and composite, at
most phi(n)/4 positive numbers a < n satisfy
clauses 1 or 2 modulo n.
Primitive roots




Definition: g < n is a primitive root of n if gcd(g,n) = 1
and there is for each i<n with gcd(i,n) = 1, a k with i
= gk mod n.
Theorem [Gauss] n has a primitive root if, and only if,
n = 1, 2, 4, pe or 2pe where p is some odd prime.
Theorem For any M>0 the set {p: p a prime number
and M < least primitive root of p < p-M} is infinite.
Theorem [Burgess] For each e>0 there is a p(e)
such that for each prime p > p(e) the least primitive
root of p < p(1/4 + e)
Computational Complexity I
For f and g sequences of natural numbers:
 f = O(g): there are an N and C with: for all n>N, f(n) <
Cg(n).
 f = o(g): lim(f(n)/g(n)) = 0.
 length(n) = 1 + [log2(n)].
 Ln(g,c) = O( e(c (ln(n)^g) (ln(ln(n))^ (1-g)))
NOTE: Ln(0,c) = O((ln(n))c) is “polynomial in length of n”
Ln(1,c) = O(e(c ln(n))) is “exponential in length of n”
Ln(g,c) for 0 < g < 1 is “subexponential and
superpolynomial in length of n”
Computational Complexity 2
Computation
Bit operations
m+n
O(max{ln(m),ln(n)})
mn
O(ln(m)ln(n))
Solve(mu+nv = b)
O(ln(m)ln(n))
Solve(a*x mod m =1) O(ln(m)2)
b^n mod m
O(ln(n) ln(m)2)
RSA on a finite group G
fn(a) = an
Theorem. If gcd(n,|G|) = 1, then fn is one-toone. Moreover, if m is a solution for nx mod
|G| = 1, then fm is an inverse for fn.
RSA Keys
Public keys: The group G and the function fn.
Coding function: F maps messages in
ordinary text into the group G.
Private key: The function fm.
Alice encrypts to Bob

Look up Bob’s public key (G,fn) and coding
function F.

With M = F(message), compute E = fn(M).
[Then E is the encrypted version of M]

Send E to Bob.
Bob decrypts
Compute D = fm(E).
Compute the inverse of D under the coding
function F.
RSA signatures
Public keys: The group G and the function fn.
Private key: fm.
Bob signs an item, a, known to Alice:
 s = fm(a)
Alice checks if s is Bob’s signature on a:
 b = fn(s)
 If b = a, then Alice accepts s as Bob’s signature on a.
Classical RSA
To construct the public and private keys:
 Choose two prime numbers p and q.
 Put R = pq. And put G = {a<R: gcd(a,R) = 1} with
operation multiplication mod R. NOTE: |G| = phi(R).
 Choose n so that gcd(n,phi(R)) = 1. This n specifies
the encryption function fn.
 Compute m = 1/n mod phi(R). This specifies the
private key fm.
 Coding Function: ASCIIPad
 Example
RSA key generation efficiency
Selection of prime numbers. prime numbers must be
large. Issue 1: How to test if a large number is
prime?
Issue 2: What is the probability that a large number
be prime?
 Computing R. O(ln(p)ln(q)). Polynomial time.
 Selecting n. n must be odd.
Issue: Probability(gcd(n,phi(R)) = 1)?
phi(phi(R))/phi(R).
 Computing m. O(ln(phi(R))2). Polynomial time.

RSA operations - efficiency

Coding computation: polynomial time.

Encryption: fn(M) = Mn mod R. O(ln(n) ln(R)2)
polynomial time.

Decryption: fm(E) = Em mod R. O(ln(m)ln(R)2)
~ O(ln(R)3) – polynomial time.
RSA security

Use the factorization of R to compute phi(R) in
polynomial time in the length of R. From phi(R) and
fn compute fm in polynomial time in the length of
phi(R).

Issue: How hard is it to factor R? The best factoring
algorithms (Lenstra’s Number Field Sieve) has super
polynomial time LR(1/3,c) for some constant c. This
is subexponential.
Fermat factoring [Stopped here: Sept 24]
Pollard p-1 method


RSA signature issues

If enough small primes have been signed,
these can be used to construct forged
signatures on specific messages.
Example

If items signed are first padded, and n is
small, certain signatures can be forged.
El-Gamal crypto system
(G,*): a finite group, g: element of large order.
Private key: a natural number N < |<g>|.
Public keys: G, g and y (=gN)
Coding function: A bijective function F which
maps messages in ordinary text into G.
Alice encrypts for Bob





Compute M:= F(message)
Choose a random natural number R<|<g>|
Compute: z:= yR and d:=gR in G.
Compute E:=M*z in G.
Send (E,d) to Bob.
Bob Decrypts

Compute x = dN.

Compute the inverse, X, of x in G.

Compute D:= X*E in G.

Compute the inverse of F’s value on D.
Signature Schema

Items to be signed: elements of {0, 1, …,
|G|-1}.

Given: Bijection f from G to {0, 1, … , |G|-1}.

The public signature key is (G,g,y,f)
Bob signs m

Choose a random number k in {1, …, |G|-1}

Compute t = gk

Compute a solution, s, to the equation
m = N f(t) + sk mod |<g>|

The signature is (t,s)
Alice verifies Bob’s signature

Verify that both y and s are less than |<g>|.

Then verify if yf(t)ts (= g Nf(t) + sk) = gm

If both are true: Accept (t,s) as signature of
the owner of public key (G,g,y) on m.
Classical El-Gamal






Choose a large prime number p.
Put G = {1,2, …, p-1} with operation
multiplication mod p. NOTE: |G| = p-1.
Choose a primitive root g of p.
Choose N in {1,2,…,p-1} randomly. This
specifies the private key.
Compute y = gN mod p
Coding Function: ASCIIPad
El-Gamal key generation




Selection of prime numbers.
Issue 1: How to test if a large number is prime?
Issue 2: probability that a large number is prime?
Selection of a primitive root.
Theoretical estimate: There are primitive roots < p¼ + o(1).
Exhaustive search can be exponential time (O(e(¼+o(1)) ln(p))).
ERH implies: Least primitive root is O(ln(p)6).
Issue: How to test if g is a primitive root of p?
Selecting N. N must be large, but not easy to guess.
Issue: What is a good way to choose N “randomly”?
Computing y. O(ln(p)2). Polynomial time in length of p.
El-Gamal operations


Encryption:
z and d: O(ln(p)2) – polynomial time.
E: O(ln(p)2) - polynomial time.
Decryption:
x = yN mod p: O(ln(p)2) – polynomial time.
X= x-1 mod p: O(ln(p) 2) – polynomial time.
X*E mod p: O(ln(p)2) – polynomial time.
El-Gamal Security level
For discrete logarithms in this group:
super polynomial time Lp(1/3,C), some
constant C.
This is subexponential, and compares to the
estimates for factoring classical RSA moduli
Hellman-Pohlig-Silver Algorithm
[Stopped here: Sept. 25 (no signatures)]
Classical El-Gamal signatures
To sign message m:
 Choose, randomly, k with 0 < k < p-1.
 Compute t = gk mod p.
 Solve m = Nt+ks mod (p-1) for s
 Signature is (t,s)
NOTE: s = (m- Nt)/k mod (p-1) if gcd(k,p-1) = 1.
Security threats for signatures
1.
Hellman Pohlig Silver algorithm.
2.
Covert channels used to leak private keys.
3.
Signature trapdoors by the key designers.
4.
Careless choice of the primitive root.
a = x2 mod p, p prime and 0 < a<p:
Definition: a is a quadratic residue of p if
a = x^2 mod p
has a solution. Else, a is a non-quadratic
residue of p.
 Definition: Legendre(a,p) = 1 if a is a
quadratic residue of p, -1 otherwise.

Quadratic Reciprocity


Theorem: If Legendre(a,p) =1 then a = x^2
mod p has exactly two solutions. If p mod 4
=3, then exactly one of these two solutions is
also a quadratic residue of p.
Theorem [Quadratic Reciprocity] For odd
prime numbers p and q,
Legendre(p,q)*Legendre(q,p) = (-1)(p-1)(q-1)/4
Solving a = x2 mod p





Theorem [Euler] If p mod 4 = 3 and Legendre(a,p) = 1, then
b = a(p+1)/4 mod p solves a = x2 mod p, and b is a quadratic
residue for p.
For p mod 4 =1, the Tonelli-Shanks algorithm can be used to
compute solutions when they exist. This algorithm depends on
finding first a quadratic nonresidue of p.
Theorem For each M there are infinitely many primes p such
that M < least quadratic nonresidue of p < p-M
Theorem For each prime p, the least quadratic nonresidue of p
is below 1 + p1/2.
Theorem [ERH] For each prime p there is a quadratic
nonresidue of p of size O(ln(p)2).
Tonnelli-Shanks algorithm
1.
2.
3.
Given a quadratic nonresidue, the algorithm finds a square
root in time O(ln(p)4).
There is no known deterministic polynomial time algorithm for
finding a quadratic nonresidue.
For each e>0 there is a polynomial time algorithm that finds a
nonresidue with probability > 1-e:
a. Randomly choose n<p [50% chance nonresidue].
b. Check in O(ln(p)3) time if n is a nonresidue.
This is a non-deterministic polynomial time algorithm.
ERH indicates a deterministic polynomial time algorithm.
Elliptic Curves over Zp, p>3



Consider equations of form
y2 = x3 + ux2 +vx +w and u, v, w in Zp
Examples over real line
With appropriate substitutions equivalent to:
E: y2 = x3 + a*x + b, and a, b in Zp .
If 4a3+27b2 mod p is nonzero we say: “E is
an elliptic curve over Zp”.
E/Zp for 4a3+27b2 mod p nonzero



Solutions in Zp x Zp of E: y2 = x3 + ax + b, and
a, b in Zp, together with extraneous point O is
denoted E/Zp.
There is an Abelian group operation on E/Zp.
For A = [x1,y1] and B = [x2,y2] in E/Zp define:
If A = B: L = (3x12 + a)/2y1
Else:
L = (y2-y1)/(x2-x1)
Group operation

A+O = A = O+A

If x1 = x2 but y1 is not y2: A+B = O.

Else: A+B = [x3,y3] where
x 3 = L 2 – x 1 – x 2.
y3 = y1 – L(x1 – x3).
Trace of Frobenius
t = || E/Zp | - (p+1)|
Definition:

If t = 1:

E/Zp is anomalous.
If t mod p = 0: E/Zp is supersingular.
Theorem[Hasse] t < 2sqrt(p)+1.
Theorem:
1.
p mod 4 = 3: E/Zp supersingular exactly if b = 0.
2.
p mod 4 = 1: E/Zp supersingular exactly if a = 0.
The structure of E/Zp
Theorem E/Zp is isomorphic to Zd x Ze where d
divides gcd(e,p-1). (d = 1 is possible).
Definition E/Zp[m] = {a in E/Zp:m*a = O}.
Theorem If m mod p > 0 then E/Zp[m] is
isomorphic to Zm x Zm.
Computational Complexity and E/Zp

Group operation: O(ln(p)2) – polynomial time

Group order: O(ln(p)8) – polynomial time
(Schoof’s algorithm)

Finding a point in E/Zp : Opr(ln(p)4) – probabilistic
polynomial time
Examples
Discrete logarithms and E/Zp
O(ln(p)) – polynomial time.

Anomalous:

Supersingular: Lk(1/3, c) where
c = (64/9)1/3) and k = pn, some “small” n.
Subexponential but superpolynomial time.

General:
O(eCln(p)) – exponential time.
Hellman-Pohlig-Silver algorithm also applies to E/Zp.
Koblitz embedding for E/Zp




Probabilistic parameter k: 30 < k < 51
Embedding F into Zp: range-values below p/k
To embed m: Search x in [mk,(m+1)k) with
[x,y] in E/Zp for some y. This is image of m.
Probability of failure about (1/2)k.
Recovering m from Koblitz point
m = floor(x/k).
.
El-Gamal on Elliptic Curve Groups

Public Key: E/Zp, g in E/Zp, y (= N*g)
(Specify p, a, b for E/Zp)

Private Key: N with 0 < N < |<g>|
EC El-Gamal Key Generation





Selection of prime number p
Selection of parameters a and b
Selection of point g: Opr(ln(p)4)
Selection of private key N
Computation of y: O(ln(N)ln(p)3)
EC-El Gamal Crypto-computations

Coding function: Opr(ln(p)4)

All other computations: O(ln(p)4) or better.
Example
EC-El Gamal vs RSA Security Level


General Elliptic curves E/Zp: O(eCln(p)).
General RSA parameter R: LR(1/3,c).
From Cln(p) = c(ln(R))1/3(ln(ln(R)))2/3:
Consider the graph of y3 = kxln(x)2