Cryptography - University Of Maryland

Cryptography - University Of Maryland

Cryptography Lecture 19 Exponentiation Compute ab ? ab = O(b a) Just writing down the answer takes exponential time! Instead, look at modular exponentiation I.e., compute [ab mod N]

Size of the answer < N How to do it? Computing ab and then reducing modulo N will not work Modular exponentiation Consider the following algorithm: exp(a, b, N) { // assume b 0 ans = 1; for (i=1, i b; i++)

ans = [ans * a mod N]; return ans; } This runs in time O(b * poly(a, N)) This is an exponential-time algorithm! Efficient modular exponentiation Assume b = 2k for simplicity The preceding algorithm roughly corresponds to

computing a*a*a**a Better: compute (((a2)2)2)2 2k multiplications vs. k squarings Note k = O(b) Efficient exponentiation Consider the following algorithm: exp(a, b, N) { // assume b 0 x=a, t=1;

while (b>0) { if (b odd) t = [t * x mod N], b = b-1; x = [x2 mod N], b = b/2; } return t; } Why does this work? Invariant: answer is [t xb mod N] Running time is polynomial in a, b, N

Primes and divisibility Assume you have encountered this before Notation a | b If a | b then a is a divisor of b

p > 1 is prime if its only divisors are 1 and p p is composite otherwise d = gcd(a, b) if both: d | a and d | b d is the largest integer with that property Computing gcd? Can compute gcd(a, b) by factoring a and b and looking for common prime factors

This is not (known to be) efficient! Use Euclidean algorithm to compute gcd(a, b) One of the earliest nontrivial algorithms! Euclidean algorithm Proposition Given a, b > 0, there exist integers X, Y such that Xa + Yb = gcd(a, b)

Moreover, d=gcd(a, b) is the smallest positive integer that can be written this way See book for proof Can use the extended Euclidean algorithm to compute X, Y See book for details Modular inverses b is invertible modulo N if there exists an

integer a such that ab = 1 mod N Let [b-1 mod N] denote the unique such a that lies in the range {0, , N-1} Division by b modulo N is only defined when b is invertible modulo N In that case, [c/b mod N] defined as [c b-1 mod N] Cancellation The expected cancellation rule applies for

invertible elements I.e., if ab = cb mod N and b is invertible modulo N, then a = c mod N Proof: multiply both sides by b-1 Note: this is not true if b is not invertible E.g., 3*2 = 15*2 mod 8 but 3 15 mod 8 Invertibility How to determine whether b is invertible

modulo N? Thm: b invertible modulo N iff gcd(b, N)=1 To find the inverse, use extended Euclidean algorithm to find X, Y with Xb + YN = 1 Then [X mod N] is the inverse of b modulo N Conclusion: can efficiently test invertibility and compute inverses! Group theory

Groups Introduce the notion of a group Provides a way of reasoning about objects that share the same mathematical structure Not absolutely needed to understand crypto applications, but does make it conceptually easier Groups An abelian group is a set G and a binary operation

defined on G such that: (Closure) For all g, hG, gh is in G There is an identity eG such that eg=g for gG Every gG has an inverse hG such that hg = e (Associativity) For all f, g, hG, f(gh) = (fg)h (Commutativity) For all g, hG, gh = hg The order of a finite group G is the number of elements in G


under addition under multiplication under addition under multiplication \{0} under multiplication {0,1}* under concatenation {0, 1}n under bitwise XOR 2 x 2 invertible, real matrices under mult. Groups

The group operation can be written additively or multiplicatively I.e., instead of gh, write g+h or gh Does not mean that the group operation has anything to do with (integer) addition or multiplication Identity denoted by 0 or 1, respectively Inverse of g denoted by g or g-1, respectively Group exponentiation: m a or am, respectively

Computations in groups When computing with groups, need to fix some representation of the group elements Must fix some representation for group elements Usually (but not always) some canonical representation Usually want a unique representation for each element Must be possible to efficiently identify elements in the group Must be possible to efficiently perform the group

operation Group exponentiation can be computed efficiently Useful example N = {0, , N-1} under addition modulo N Identity is 0 Inverse of a is [-a mod N] Associativity, commutativity obvious Order N

Example What happens if we consider multiplication modulo N? {0, , N-1} is not a group under this operation! 0 has no inverse Even if we exclude 0, there is, e.g., no inverse of 2 modulo 4 Example Consider instead the invertible elements

modulo N, under multiplication modulo N I.e., *N = {0 < x < N : gcd(x, N) = 1} Closure Identity is 1 Inverse of a is [a-1 mod N] Associativity, commutativity obvious (N) (N) = the number of invertible elements modulo N

= |{a {1, , N-1} : gcd(a, N) = 1}| = The order of *N Two special cases If p is prime, then 1, 2, 3, , p-1 are all invertible modulo p (p) = |*p| = p-1 If N=pq for p, q distinct primes, then the invertible elements are the integers from 1 to

N-1 that are not multiples of p or q (N) = |*N| = ? Fermats little theorem Let G be a finite group of order m. Then for any g G, it holds that gm = 1 Proof (abelian case) Examples In N :

For all aN, we have N a = 0 mod N (Note that N is not in the group!) In *N : For all a*N, we have a(N) = 1 mod N p prime: for all a *p, we have ap-1 = 1 mod p

Recently Viewed Presentations

  • Indifference Points I

    Indifference Points I

    An indifference point is the point where two options are equal. It is generally stated in terms of a common variable. Above the indifference point, one of the alternatives will yield lower cost or be more favorable. Below indifference point,...
  • Economics of Disasters Are Disasters Good for the

    Economics of Disasters Are Disasters Good for the

    Assumptions of the Model: All resources are used to produce the 2 categories of products on the X and Y axes. At all points on the curve, all resources are fully employed, given the available technology. (we choose from the...
  • The Gold Empires of West Africa - Mrs. Hildebrand-Johnson&#x27;s ...

    The Gold Empires of West Africa - Mrs. Hildebrand-Johnson's ...

    Trading Empires in Africa. For 1000s of years, the hot, dry Sahara separated North Africa from the rest of the continent. 400 B.C. Berber's found ways to cross the Sahara to West Africa—this opened trade between the 2 regions.
  • Overview of the Compliance Requirements for the Stage 2 DBP ...

    Overview of the Compliance Requirements for the Stage 2 DBP ...

    To see the specific analytes included in this group violation click on . Fed Fiscal Year. Individual Violations in Group. These are the individual analytes that are included in the 515 sample group. The monitoring and reporting violation mailed to...
  • Sparta! Chapter 7 - The Glory of Ancient Greece Section 2: SPARTA

    Sparta! Chapter 7 - The Glory of Ancient Greece Section 2: SPARTA

    Spartan Women & Girls: played sports; trained in wrestling . and spear throwing. socialized with men. allowed to own land and take part . in business. still had to obey men
  • Title of presentation -

    Title of presentation -

    "Learning at and through Work" "Learning at and through Work" Employment-based model, Structured training on and off the job, Formal training contracts between all parties, Has a training plan, and Fit under a National VET recognition framework, Supported by on-site...
  • Essentials Workshop

    Essentials Workshop

    Students are expected to log into the OLS (K-8) LMS (9-12) each scheduled school calendar day. Attendance and Truancy We, as well as the Michigan Department of Education, take your student's attendance very seriously.
  • California Youth Soccer Association, Inc.

    California Youth Soccer Association, Inc.

    US Youth Soccer includes 55 state youth soccer associations. One (1) per state, except for California, New York, Ohio, Pennsylvania and Texas, which each have two (2) state associations US Youth Soccer Association is divided into four (4) regions.