Discrete Logarithm Problem (DLP) - Cryptography and Network Security Video Lecture - Computer Science Engineering (CSE)

so welcome to this class on discrete log
problem so as we were discussing about
public key cryptography we will continue
with that and discuss about the
following topics so first we will
introduce the problem of discrete
logarithm problem and try to understand
like what is the problem statement we
shall follow it up with an application
of the discrete logarithm problem to a
crypto system which is commonly referred
to as the el-gamal cryptosystem and then
we shall discuss about some popular
cryptanalytic techniques for discrete
logarithms and which are commonly no no
I mean with the names of which those
algorithms are the shanks algorithm the
pollak Hellman algorithm and the index
calculus algorithm and we shall conclude
with another application of the discrete
logarithm problem to key agreement or
key exchange problems and it is commonly
referred to as a DV Hellman problem so
it's a slight variation of the discrete
logarithm problem but we shall see the
first of all the corresponding problem
and also its application in key exchange
in where two parties would like to
exchange information to arrive at a
common key so first of all what is the
problem of discrete logarithm so
consider a finite mathematical group
where G is the group and dot is the
corresponding operator that is a
multiplication operation and now for any
element alpha which belongs to this
group G and has order n so we know what
is meant by order so means that if I
take alpha and if I multiply it in times
then I get the unity of this group so
let the group let the corresponding set
be referred to as this and it is
obtained by raising alpha to its various
powers the possible powers or which is
referred as I can can range from the
range of it lies between 0 to n minus 1
both the intervals included right so we
know that alpha power n is not included
because alpha power n is back to 1 that
is it is this our clock group right so
the discrete logarithm problem
that is a DLP as it is commonly known as
is to find the unique integer I where I
lies between 0 and n minus 1 such that
this particular condition is satisfied
that means there are two given elements
alpha and beta the question is to find
this I such that alpha power of I is
equal to beta so basically we are what
we are trying to find out is logarithm
of beta with respect to alpha so this is
commonly referred to as a discrete log
of beta with reference to R with respect
to the value alpha okay so now proper
for proper choices of this group like if
I choose the parameters properly as we
will see in context to the crypt
analysis that if then this particular
computation of this particular value is
considered to be a computationally
difficult problem okay so therefore this
is a possible or a candidate one way
function as we have seen that in context
to public key algorithms previously like
when we studied about RSA then we have
also seen that one-way functions or
candidate one-way functions are
important to the development of public
key ciphers similarly here this is also
another possible candidate one-way
function which can have potential
applications in public key cryptography
so discrete logarithmic problem as we
know is the inverse of the
exponentiation operation so if I
consider the exponential operation in
the modulo P field then the discrete
logarithm is nothing but the in
corresponding inverse right now
exponentiation
is easy to compute we know that there is
a polynomial time algorithm commonly
referred to as a square and multiply
auger algorithm through which we can
compute the exponentiation quite easily
right however if the group is properly
chosen then the computation of discrete
log is believed to be a difficult
problem okay
so therefore the exponentiation is a
possible one-way problem because the
forward Direction is considered to be
easy it's quite easy we have a
polynomial time solution for computing
the exponentiation and however the
inverse that is computing the discrete
log is considered to be a
computationally intractable or a
difficult problem
okay and therefore this has got
potential applications in public key
ciphers okay so let us see one such
application and it is commonly referred
to as the el-gamal cryptosystem now you
note that in el-gamal cryptosystem we
will define or we denote this p to be a
prime number and consider the group ZP
star so we know remember what is meant
by ZP star that is here it is a
multiplicative group that is 0 is being
excluded from this group okay so Z so we
we are assuming that that in this prime
group that is that P star okay there
computation of the discrete log problem
is computationally difficult so that's
our basic assumption using this
assumption we will see one proposal of a
possible crypto system so let alpha
which belongs to ZP star be a primitive
element primitive element we know that
if I take this primitive element and if
I keep on multiplying then I generate
all the elements in the group okay so
therefore using this particular
primitive element what we will do is we
will see how the crypto system is
defined okay so immediately you know
that for any crypto system it is a 5
topple right so therefore there is a
corresponding plaintext
and also a corresponding ciphertext
space right so here the plaintext is
also chosen from the ZP star that is it
is any element in ZP star
however the ciphertext is actually a
cross product of 2 or it is an ordered
pair that is you can refer to as say Y 1
comma Y 2 where Y 1 is an element of ZP
star
and Y 2 is also an element of ZP star
okay so therefore the space of
ciphertext is obtained by the Cartesian
product of ZP star and ZP star okay so
now what is the key of this algorithm
the key of this algorithm is the public
parameter P which is known to everybody
that is not only the sender and the
receiver knows but also the adversary
knows okay
similarly the alpha and beta are also
publicly known values okay
but a is actually a secret okay so if I
just consider like a public key cipher
then P alpha and beta is what
the public key but a is the gives the
corresponding private key is a
corresponding secret element okay now
this values like alpha and beta satisfy
a particular relation that is if I take
alpha and raise it to the power of a
then I obtain beta of course in a modulo
P field okay but here do you note that
based upon this assumption if I even if
I give to an adversary alpha and beta
because of the proper choice of P
computation of a is believed to be
difficult right now we will try to apply
this particular assumption to encrypt a
possible message say X okay so the idea
is quite simple the idea is what you so
when you are trying to encrypt X what
you do is that you choose a random
number
art which belongs to ZP minus 1 okay so
that P minus 1 means it will live from 0
and continue until P minus 2 okay so we
choose an R which belongs to that P
minus 1 and using that we will encrypt
the value of x ok so art is remember
that art is a random choice okay so what
we do is that we take X and we also pair
it with a random component called R and
obtain the ciphertext y1 and y2 so from
this statement itself you know that the
computation of y1 and y2 actually not
only depends upon the plaintext X but
also depends upon the random choice R so
which means that it is not necessary
that the same value of x will always get
mapped to the same ciphertext so this
algorithm is by definition a randomized
algorithm right
so what we do is this is essentially
computation of these y1 and y2 as two
pairs okay so not first of all why two
actually okay so y2 what we do is this
that is we take beta which is
essentially this value and raise it to
the power of r and multiply it with X
okay so that is somewhat some sort of a
manipulative masking ok you take X and
you mask it by multiplying it with beta
are okay so therefore what you do is
this that is you compute y2 and remember
that y 2 is nothing but X and you
multiply it with beta power of R and do
a modulo P ok so next what you do is
that you compute y 1 and y 1 is nothing
but alpha and raised again power to
power of r okay and again donna done and
of course a modulo P is of course there
now you note that by our previous
assumption of choice of beta and alpha
we know that beta is nothing but alpha
power of a mod P okay so what the
receiver does is that when it receives
this y2 in order to find out this value
of x it needs the inverse of beta power
of R that means it needs to compute the
value of beta power of R but remember
that the receiver also has got this
alpha power of R right so what the
receiver does is the receiver takes
alpha power of R that is basically y1
and raises both of them to the power of
a ok so if you do that that is equal to
alpha power of a whole power of r right
and that is nothing but beta power of R
right so therefore because the at the
corresponding receiver has a knowledge
of this value of a computation of beta
power of R is quite trivial he can do it
in polynomial steps right so then what
the receiver does is that the receiver
computes the inverse of beta power of R
that is beta power of R inverse and you
know that by extended Euclidean
algorithm you can actually compute the
inverse also in polynomial number of
steps in bali steps right
so then what it does is that it masks
this inverse order multiplies this
inverse with y2
okay and therefore if we multiply x beta
power of R with the inverse of beta
power of R then you again get back
X right so therefore the receiver is
able to correctly obtain back the value
of X right but however it is believed
that if the adversary has to find out
the value of x it needs either to guess
the value of ay or it needs to obtain
the value of ay through some means which
means that the adversary should have the
potential power of solving the discrete
log problem in the field okay and that
is believed to be a difficult problem
right so it's a quite simple algorithm
that way and now we can see the steps
like y 1 is equal to alpha power of r
mod p y 2 is equal to X beta power of R
mod P that's the encryption step for
decryption what you do is that you take
Y 2 multiply it with by raising Y 1
power of a you know y1 power of a is
nothing but beta power of art you
compute the inverse of beta power of R
multiplied with X into beta power of R
and obtain back X so the encryption if
you do the proper decryption in this way
you get back the original plaintext X
right so therefore the working of the
algorithm can be summarized again like
this plaintext X is masked by
multiplying means by beta power of art
yielding Y to the value of alpha power
of odd is also transmitted as a part of
the ciphertext Bob who has a secret a
can compute beta power of R by raising
alpha power of R 2 a and then you
obtains X by dividing by 2 with beta
power of art dividing means multiplying
by the inverse so note that the el-gamal
algorithm as I told you is a randomized
algorithm that is - takes depends on
both the plaintext X and the random
value are chosen by Alice which is the
encrypted and therefore the same
plaintext can actually be mapped into P
minus 1 cipher texts depending upon the
choice of our write because you can have
how many choices of are from 0 to P
minus 2 that's P minus 1 choices for
each of these choices the same plaintext
we're getting will get mapped into P
minus 1 different ciphertext okay so
that way this algorithm is quite good
because it's an inherently it's a
randomized algorithm right and therefore
it gives two maybe two nice properties
which can which we require because of
the requirements of semantic security
so we've just considered a very simple
example here like for example P equal to
2 5 7 9 is a prime number and alpha is
equal to 2 is the primitive element of
that P star consider that there is a
secret value 7 6 5 which is a secret
component and we want and we just choose
2 values like beta and alpha so beat
alpha is 2 so we just take 2 and raise
it to this secret value obtain back beta
so note that 9 for 9 is the value of
beta therefore alpha that is 2 and beta
that is 9 for 9 are the public
parameters right but a which is the 7 6
5 is the secret component so now suppose
Alice wishes to send X equal to 1 to 9 9
to Bob so what she does is that she
randomly chooses a value R equal to 8 5
3 and what she does is first obtain y 1
that is by raising this 2 that is alpha
2 the secret value 8 5 3 obtained back 4
3 5 and y 2 is multiplying or masking 1
2 9 9 which is the message which he
wants to send by with the corresponding
value of beta power of R so beta is 9 4
9 here it is raised to 8 5 3 which is a
random component and obtained back 2 3 9
6
okay so therefore when the ciphertext
will correspond to 4 3 5 paired with two
three nine six ok so if you want to so
Alice send is this one as the ciphertext
and what Bob does is that Bob computes 2
3 multiplied by X by multiplying 2 3 9 6
by taking 4 3 5 and raising it to the
power of 7 6 5 which is the
corresponding value of the secret so you
note that again that Bob has this secret
value so you can easily do this
operation but the adversary should be
unable because it neither has the
knowledge of this knot it cannot extract
out this knowledge because of the
assumption of the discrete log problem
and multiplies we are and what Bob does
is Bob multiplies with the inverse will
be two three nine six and obtains whacks
X which is one two nine nine which is
the same as the initial value of x okay
that is a message so therefore we see
that mathematically if you use the
el-gamal encryption then you get back
whatever method used want to encrypt it
okay
however we will we will now consider the
crypt analysis problems of the discrete
block this skill op challenge okay like
if I want to give two values if I if I'm
given with two values of alpha and beta
how really difficult it is to compute
the value of a and we will consider some
classical examples to this direction
okay but before I go into that there is
a small note that I would like to make
that is if alpha power of I so we know
that in normal integers computing
logarithm is not very difficult because
when you are not considering the modulo
field that is when you are not doing the
modulo operation then your alpha power I
is always a monotonically non-decreasing
value which means that if I increase the
value of I there are Zabar I will not
decrease right when you are not doing
the congruence or when you are not doing
the modulo operation okay so which means
that this gives you the scope of
applying a binary search kind of
technique to arrive at the value of v
right for example you check with a large
value of I if you see that alpha power
of Y that is the value that is the beta
which is so what we do is that you
choose a large value of I guess a large
value of I and then if you see that the
beta is larger than that the beta which
is equal to alpha power of I is larger
than that then you apply binary search
such to the larger part right and then
if you see that it is lesser than that
other than that then what you do is that
you apply binary search to the lower
region right that way you can actually
try to converge at that chill value of I
if alpha power Y was a monotonically
non-decreasing series that is if I
increase I alpha bar Y does not decrease
but the problem with this modular field
is that alpha power of I I mean there is
no ordering of this alpha power of Y it
may happen that even if you increase
where value of I alpha power of Y
becomes smaller right so therefore the
only way of doing it is by an exhaustive
search that's the assumption okay that's
that I mean at least you cannot engage a
simple binary search kind of technique
to arrive at the value of I therefore
one possible solution is to do an
exhaustive search in the worst case
right because you may not be lucky so in
may need to very wife well verify all
the values of I and take whether alpha
power of I matches with a given value of
beta right so this will actually engage
order of n time because n is the group
order so order of n times and the
storage that you require is order of 1
because you can I'm not doing any
storage at this point ok however you can
actually engage at time memory trade-off
here ok and using that time a money
trade-off you can try to reduce the
value of the time complexity reduce the
time complexity however the space
complexity will automatically increase
ok and therefore you can actually do
some amount of pre computations ok and
now what is the idea of doing that is
like this suppose you stored all the
possible values of alpha power of I
modulo P as ordered pairs so what you
can do is that you can store them as
ordered pairs like I paired with alpha
power of I modulo P ok and sort the
elements with respect to the second
parameter that is with respect to this
alpha power of I modulo P you can sort
them right you can immediately as I
because of the previous description or
other discussion you know that if I even
if I increase I alpha power of I mod P
is not automatically sorted right so
what we need to do is maybe engage and
efficient sorting algorithm to sort this
ok so alpha power of I so we basically
sort this ordered pair list based on the
second argument next what we do is that
we now what we do is this that is we
search for the given challenge by
employing a binary search that is for
example so what I do is this that is I
take I and compute alpha power of I
modulo P so this is basically a pre
computation that I am doing and what I
am doing is essentially swatting them
based on the second argument ok and I
make a list say that list is l1 so now I
know that I have to look for the case
where beta is equal to alpha power of I
modulo P right
that means that if this so this is a
pre-computation stage okay I have
already done this and this is stored in
the memory now what I do is that I take
this value of beta and I search for
after I have sorted out
I have after I have sorted this list
that is it is as it is called here as l1
which is the sorted list based on the
second argument okay
based on alpha power of I mod P okay so
then what I do is that I take this value
of beta and I search in this list using
a binary search kind of technique right
so basically what I do is that I look
for its location by applying a binary
such kind of method okay so now what is
the complexity here we know immediately
that the storage complexity here will be
because of I need to store the entire
list the storage complexity will be
order of P ok so order of P order order
of in whatever ok so the storage
complexity will be order of P right now
what about your sorting algorithm your
sorting algorithm will have a complexity
of so I'm referring to P as n then it
becomes in actually and this is order of
n log n right so that's your sorting
complexity now I am also doing a binary
search so the search will actually
require an order of log n complexity
right now what you note one thing that
because we are actually considering very
large fields their logarithm of n is
actually very small or negligible
compared to n remember that you are
dealing with say thousand 48 bit of
large numbers okay so in that case in
such kind of big scenarios okay so when
you are dealing with say 2 0 48 or 1 0 2
for 8 bit Prime's right then it may
happen that this logarithm of n is
actually very smooth actually the
logarithm of n is very small compared to
this value of n ok so then you can
chillie approximate this as order of in
and approximate this as order of 1 so
when you are considering these discrete
log crypt analysis problems we will
always do these studies neglect this
value of logarithm in compared to this
value of M okay so therefore in this
case your time complexity okay that is
the time complexity to search is
actually a constant time okay its order
of 1 ok
however your memory complexity is order
of n so you see that this is just the
opposite of what we saw in the beginning
right we what the beginning what we
started what we the time complexity of
all relevant and space complexity of
order of 1 but during some using some
pre-computation you can actually reduce
your reduce drastically your time
complexity but of course at the cost of
your space complexity now there is an
algorithm which is called as the baby
step giant stream algorithm which
actually tries to optimize both okay so
it was it is called the shanks baby step
giant step algorithm and we will next
see the description of this algorithm so
consider this algorithm that is what it
does is that the problem is again the
same that is given alpha and beta and
given a choice of group and a value of n
my objective is to find the
corresponding value of a for which beta
matches with alpha power of a in this
group right so what is done is like this
so first you actually set a value or
variable m to the square root of n okay
and then you start computing alpha power
of M J where J runs from 0 to M minus 1
okay that is your value of alpha power
of M J is what is computed and stored
okay so that means immediately you
understand that what is the amount of
storage required for this it is equal to
M because you need to do M such
computations and M is square root
in right the other thing what you do and
also what you do is again stored this or
a moderate pairs like J comma alpha MJ
with respect to the second coordinate
that is you sort them by again an
efficient sorting algorithm and obtain
the list which is called l1 okay so
basically the least l1 the least l1 is
so M is equal to square root of n okay
that is set to square root of N and what
we do is that we make a list l1 which is
the sorted list based on the second
argument in your J comma alpha MJ okay
so where your J is actually running from
0 to M minus 1 okay so you compute the
various values of J and you find out or
calculate the value of alpha power of M
J that is at least l1 the least l2 is
actually made out of a different weights
what you do is that this sort at least
based on the second argument of already
in I comma beta by alpha power of I so
here also your I ranges from 0 to M
minus 1 okay so now you note that in l1
the elements are computed how the
elements are look looking like say when
you start with the value of J equal to 0
it is alpha power of 0 so that is 1
right next you have whatever when value
of J is equal to 1 it is alpha power of
M then alpha power of 2 m and so on
right
so it's a kind of a big jump you see
that it is alpha power of m alpha power
of 2m and so on right M is a quite big
number but here you are actually
computing like beta power of alpha power
of I so that is alpha power of zero
which means it is beta next you divide
this beta by alpha power of 1 next you
divide it by beta power of alpha square
and so on so these are actually small
jumps right and therefore these jumps
are referred to as the giant steps and
these are actually the baby steps okay
now what you do is that in this list l1
and l2 which are both sorted you are
trying to find out a common element
based on the second argument okay so the
second Illuma argument in this list l1
is alpha power of M J right in the
second argument here is beta power of
alpha so now since both of them are
sorted you can actually traverse down
both the lists in linear time and you
can find out an element which actually
matches in the second component right so
that means in linear time you can find
out that alpha power of M J is equal to
beta power of alpha I and you can find
out the corresponding values of inj okay
so this means that beta is equal to
alpha power of mi sorry MJ plus I so
that means what you are supposed so if
you get a corresponding so basically
here in this list in the lists L 1 and L
2 obtain I and J such that this relation
is maintained so note that you can do
this in linear time because both the
lists are sorted right you can find such
a common element and if you do that then
your what you are supposed to return
because you have got the value of
J is nothing but M of J plus I and that
is the value of the discrete block now
let us do a sort of an analysis of this
algorithm first you know that the steps
2 & 3 can actually be pre computed right
so that means here in this algorithm the
steps 2 & 3 can be pre computed 2 & 3
can be pre computed and if so so
therefore if step 6 is successful that
is if alpha power of M J is equal to Y
is equal to beta alpha power of minus I
then alpha power of M J plus I is equal
to beta so that means that the logarithm
of this value of beta with respect to
this value of alpha is nothing but M J
plus I so this algorithm returning MJ
plus I is actually correct so that gives
the correctness of this algorithm the
next is whether this algorithm will
terminate okay so you note that this
search is always successful that is
because when you are computing this MJ
plus I the maximum value of J is what M
minus 1 and what is the maximum value of
I that is M minus 1 so when you plug in
these maximum values you get M into M
minus 1 plus M minus 1 that is nothing
but M minus 1 into M plus 1 that is
equal to M square minus 1 so M square
minus 1 is nothing but n minus 1 and I
know that the logarithm of beta with
respect to be alpha can be maximum equal
to n minus 1 so which means I am
checking for all the possible or
potential values of the exponent right
but only this has been done in a
slightly clever way the clever way is
because you are essentially using some
amount of storage right but I mean also
doing some amount of time expanding some
amount of time complexity but the fun is
here that you are actually doing both in
times of order of M and M is actually
square root of n that means both of your
time complexity and your space
complexity is reduced to order of square
root of n right so this is the advantage
over the previous two algorithms right
you are doing a kind of beta trade-off
between the time and the memory
requirement of this algorithm right
so the algorithm runs in order of aim
time with order of M memory again I am
neglecting the logarithmic factors that
is the corresponding log factors are
neglected and this is the complexity and
again note that M is equal to square
root of n so therefore this is an order
of square root of n time and square root
of n time and n memory requirement okay
so now we will actually discuss about
another algorithm which is called the
pollak Hellman algorithm okay so this
polygon Hellman algorithm is based upon
the Chinese remainder theorem okay so
the Chinese remainder theorem if you
remember that we discussed is basically
expressing hole as part okay and then
using these parts to compute the hole
okay
so what you do here is that you take
with the N which is the group order and
you decompose that or do a prime
factorization of that okay so therefore
you are believing here that you know the
corresponding values like the
corresponding prime factorization of n
see for example I am assuming here that
there are K such prime factors and you
know that by the theory of arithmetic
that you know that you can actually
obtain like P 1 to the power of e 1 P 2
to the power of e 2 and so on p ke ^ EK
right so this is the prime factorization
and all of these prime values are
distinct Prime's and our objective is
again the same that is we want to
compute the logarithm of beta with
respect to alpha so what is the first
objective the first objective is to
instead of computing a itself we are
trying to compute a but mod of P 1 to
the power of P I ^ e I and this we are
trying to compute the the logarithm but
modulo each of this corresponding P 1 ^
e 1 P 2 ^ e 2 and so on till PK ^ e 3
now once we have them from there we can
actually engage the Chinese remainder
theorem and we can obtain the value of a
modulo n right so that we can we know
that we have a very efficient algorithm
for doing that so the main problem is
how do I essentially construct the
values of a modulo each of these P 1 ^ e
1 P 2 ^ e 2 and so on
right and for this we have a very
detailed step so let us go gradually
through them now suppose you consider
that one of those prime factors is Q
okay and the corresponding exponent is C
that means you know that if you take
modulo Q power C the n becomes congruent
to 0 because n is divisible by Q power
of C what about Q power of C plus 1 it
is definitely not 0 because that is the
highest value of C is the highest such
value that you can have at most C
factors of Q in n right so therefore n
is not congruent to 0 modulo Q power C
plus 1 right so remember the primes are
distinct okay so we next compute X is
equal to a modulo Q power C so we take a
and we want to compute mod of Q power C
so for that we note one thing that is X
that is this value of x must lie between
0 and Q power of C minus 1 right that
means you can always write X like this
right you can always write them as AI
multiplied with Qi
where each of this a is again lies
between 0 and Q minus 1 right so you can
always decompose X because X lies
between Q power of C minus 1 this thing
this you can you can draw an analogy of
this to the year by normal binomial
decomposition right you know that if
there is a value of x which lies between
say it's less than Q power of C minus 1
this replace the Q by 2 you will
understand the value energy right so
therefore X you can always write as a
sigma where IE is equal to 0 to C minus
1 AI ^ qy okay where each of this a is
are actually again lying from 0 to Q
minus Q Y minus 1 Q minus 1 okay and for
your I II will actually range from again
as is so shown in the series we range
from 0 to C minus 1 now in that case
therefore a you know that Q power of C
divides X minus a right or a minus X
that means a is equal to X plus some
integer multiplied by Q power
see right so that is X is this series
plus s multiplied with this Q power of C
right so therefore your a is actually
equal to Sigma of a I Q to the power of
I that is the value of when you
arranging I from 0 to C minus 1 plus s
into Q Bar of C so what is this value
this is nothing the value of X all right
so our objective if you want to follow
find the value of x we need to find the
values of all these a is a 0 to a C
minus 1 right so therefore we need to
find out need to determine a 0 a 1 and
so on
tip a of C minus 1 right so we need an
algorithm through which we can determine
from a 0 to a C minus 1 right so the
first step is to compute this a 0 okay
and for that we give a very nice claim
that is beta and alpha are the two
values for which I mean I'm needed to
find out the discrete log of beta with
reference to alpha and we make a claim
that is beta the claim is like this that
is if you take beta okay and raise it to
n by Q then you obtain alpha again
raising it to a zero in by Q so that's
the claim okay so let us see it's a
quite simple proof that is you know that
beta is equal to alpha power of a right
so therefore your left hand side here is
nothing but alpha power of a multiplied
or raised to the power of n by Q so what
is alpha power of a alpha power of a is
nothing but Sigma of AI Qi q power of AI
plus s Q power of C
whole raised to the power of n by Q so
now if you just see that is your got
alpha and this core is considered a
power of zero here a power of zero Q
power of zero right plus a power of one
Q part of one that is one plus a power
of two that is again raised to the power
of Q power of square and so on the final
term is guessed Q power of C the whole
thing is raised to the power of n by Q
right so you note that apart from this
term all the other terms are actually
having a value of Q in the exponent so
therefore this will be like alpha power
of a zero whole power of n by Q
multiplied with alpha 2 raised to some
cons some constant times n right and you
remember that n was the order of alpha
so which means that alpha power of n is
equal to 1 so that means this is equal
to alpha a 0 n by Q right so that
actually satisfies this result so that
means if we would like to compute the
value of a 0 what will you do you will
raise various values of alpha ok and say
you will consider like and you also note
one thing that is the value of a 0 you
note that it lies between 0 and Q minus
1 note this thing right so what will you
do you will try with all these Q values
in the worst case in a very Nev way you
will try for all these Q values and you
will check that which for which case
alpha n by 2 the power of n by Q raised
to the power of that value of guess ok
is equal to beta power of n by Q
wherever it matches you will refer that
to us
or deport that is the value of a 0 so
what is the time complexity here it is
order of two right and if you can
actually engage the shanks algorithm
here then you can reduce it to the order
of square root of Q right so in
so basically from order of root cube to
order of Q you you have an algorithm you
already know a way of doing it right so
you can actually obtain the value of a 0
right so if the value of C that you have
got is equal to 1 then it is done
because you don't have any other value
of that any other a values right but if
your C value is higher than that then
you need to compute a 1 in 2 and so on
delay is C minus 1 right so this is
actually your step one which actually
computes the value of a 0 so in step 2
onwards we will try to compute the other
work okay so for that we have like so if
C is equal to 1 then we are done in the
second step otherwise we proceed to
obtain the values of like a 1 a 2 and so
on till a C minus 1 ok
and for that we actually have got a
similar kind of approach but slightly a
little involved ok so how so what is the
what is the claim here the claim that we
make here is this that is we say that
let us denote this B as equal to beta 0
ok we actually engage a recursive
technique to obtain the values of a 1 a
2 and so on okay so it's a kind of
recursive technique so first we get a 0
from there we obtain a value of beta and
I say that it is beta 1 ok so we start
like this we make is so we obtain a 0
right so what we do is that after this a
0 using this a 0 we obtain a value
called beta 0 ok now using this beta 0
we obtain a 0 you obtain the value of a
1 from a 1 we again obtain the value of
beta 1 ok we gradually continue this
until a unless we obtain a of C minus 1
and we stop there ok so let us see how
the definition of beta 1 we can get from
the definition of beta 0 ok so your beta
0 or rather beta J is defined like this
beta J is equal to beta and we raise it
alpha minus alpha to the power of minus
a 0 plus a 1 a 2
a 1q okay so minus a 1 Q minus a 0 plus
a 1 q plus so on delay J minus 1 Q J
minus 1 okay so this beta so therefore
if you do that then you get like this
right beta J is equal to beta and you
raise it to the power of alpha minus a 0
plus a 1 Q plus so on and the final
thing is a J minus 1 Q of J minus 1 okay
and we note that beta is nothing but
equal to alpha power of a right so alpha
power of a minus a 0 plus a 1 Q plus so
on till a of J minus 1 Q of G minus 1
right now what was a so if remembered a
was like this right a was equal to Sigma
of AI Q power of I where I goes from 0
to C minus 1 plus s of Q power of C
right so therefore if you plug in this
value here then you get alpha but you
note that all the higher powers remain
but these things are kind of subtracted
out from a right so what remains is a
power of j q power of j right plus a
power of j plus 1 q power of j plus 1
and so on till a of c minus 1 Q of C
minus 1 plus s of Q power of C right
so that's your beta J beta bar beta J
okay so what we do next
is that we raise beta J like our
previous case like when we computed a 0
similar to that we raised this beta J
and we would like to divide it by n by Q
of J plus 1 okay so if you do that then
you will see that all the higher terms
gets cancelled excise from this point it
gets cancelled except for
right so here you have got alpha a power
of J by Q okay but the higher things are
again like alpha some other constant k1
again multiplied within again you know
that alpha n being a group order this
again goes to unity so what we have got
is alpha a J by Q right so therefore
again you can actually engage again a
shanks algorithm or a simple algorithm
to do a finding for this value of a J
right you already know the value of the
corresponding beta J and from there you
can engage and I'm going to thing to
find the value of a G right you know
beta J right because beta J is your
definition you see that beta J depends
upon the beta J actually depends upon
the coefficient till J minus 1 okay so
in your recursive approach if you have
obtained till a J minus 1 then you can
actually define the value of B J beta J
right so using this beta J now you can
actually obtain the weather of a J and
again using this AJ you can define beta
J plus 1 right again using the beta J
plus 1 you can obtain the next value of
the corresponding a coefficient right so
essentially you can actually summarize
these two descriptions like this that is
there are two equations ok one equation
is this that is beta J n by or raised to
the power of n by Q plus J plus 1 is
equal to alpha AJ n by Q ok I missed an
N here actually there is an N multiplied
right so so because of this in right so
there's an multiplied so therefore beta
J to the power of n by Q power of J plus
one is equal to alpha to the power of AJ
n by Q this is one equation the other
equation is the definition of beta J
plus one which you can always define
like beta J alpha to the power of minus
AJ Q J it is the second equation so this
is exactly the same thing but only the
previous thing has been a PI mean you
can write that as a rakaats recursion
like this okay so what the point is that
you can actually engage these two
equations and compute the value of a0
then you can obtain the value of a0 then
compute the value the quad-core compute
the next value of beta okay and compute
the next value of a1 compute the next
value of b2 and so on you can apply them
and obtain the value of AC minus one
repeatedly applying equations 1 and 2
right so now we will see some there's a
final summarization of that that is
given your GN alpha beta and C and Q you
can actually obtain what you are
basically doing is computing beta J
raising it to the power of n by cube
power J plus 1 and checking that for
which value it is equal to alpha I n by
Q the whichever value is give this you
know that this is the corresponding
value of H a and you are repeating this
alright so that way you can actually
obtain is 0 till AC minus 1 so note that
this algorithm is for a particular prime
value and for a particular I mean for a
particular prime value and for a
particular exponent value C is the
exponent and Q is the prime prime factor
and the corresponding exponent so you
need to repeat this for all the prime
factors right and what is the complexity
of this algorithm
he seems you are doing this and if I
assume that each of this step is order
of Q and you are doing it for all the C
coefficients the order is like order C Q
right if you use shanks algorithm you
can actually do C to OC Q power of 1/2
right so let us consider a very simple
and small example like P equal to 29
alpha is equal to 2 and beta is equal to
18
order of N is in this case 28 okay and
therefore do you know that P is the
prime value already is 28 because that's
one less than the prime value right so
that the prime factors are 2 square into
7 power of 1 4 into 7 is 28 and you set
the value of Q is equal to 2 and C equal
to 2 because that's your first prime
value and the first exponent so then the
step 1 a will be like finding the value
of a 0 because your C is equal to 2 so
that means how many coefficients will
you have you will have a 0 and a 1 right
and since Q is equal to 2 the value of a
0 can be either equal to 0 or can it can
either be equal to 1 all right so what
you do is that you check for this for
both these values and you find that in
this case and note that noting that a 0
will lie between 0 and 1 in this case we
find that when a 0 is equal to 1 this
equation is satisfied that is alpha
raise to the power of 14 a 0 is equal to
beta to the power of 14 modulo 29
because that's a modulo P field right
and your P is 29 here so you find that a
0 is equal to 1 so it's next what you do
is that you compute the next value of
beta and you raise beta 1 to the power
of n by Q square and obtain the value of
alpha I mean check when it is equal to
alpha to the power of n by Q raised to
the power of a 1 again you do two checks
like because a 1 can either be 0 or it
can either be 1 0 will of course not
satisfy this and you find that 1
satisfies this you can check that also
so if 1 satisfies then you know that a 0
is 1 a 1 is 1 so what is the
corresponding value it is 3 1 1 and your
prime is 2 here so it is 3 ok so you get
that a is equal congruent to 3 modulo 4
so similarly you can do this and find
out that a is congruent to 4 modulo 7 so
then you can actually apply a Chinese
remainder theorem which we have studied
previously to find the value of a which
is modular 28 and that is congruent to
11 in this case so that's your solution
that's the discrete log problem so here
this is a step 1 a and the computation
of these things will be having
computation of the subsequent
coefficients are step 1 B actually
and you have to do it for all the prime
factors in this case there are two prime
factors one is two and other one is
seven and you obtain the value of the
discrete block right so this is the
basic algorithm for the pooling Hellman
algorithm okay
so after this we'll study the index
calculus method and see how much time we
have for the next discussions okay so
for the index index calculus method the
previous algorithms can be applied to
any group okay but the present algorithm
is more specialized it finds the
discrete lock in ZP star where P is a
prime value okay and alpha is a
primitive element modulo P so it finds a
discrete log in that P star where P is a
prime and alpha is a primitive element
modulo P so what is done in this index
calculus algorithm is by using something
is called a factor base okay so you
start with some small Prime's and assume
that your factor base is composed of
some small primes okay and you for the
first step there are two steps in this
algorithm okay the first step is to
compute the discrete log of all these
prime values in this factor this okay
suppose the P 1 P 2 and so on till
suppose P be fact prime numbers are
there in your factor base you compute
the logarithm or discrete log of all
these prime elements with respect to
your alpha okay which is the primitive
element in that P star then using these
logarithms you try to compute the
logarithm which is required okay so we
will see next how to do that so the
first step is to of the algorithm is to
find the logarithms of the B Prime's in
the factor base the second step is to
compute the discrete logarithm of a
desired element beta using the knowledge
of the discrete logs or the element in
the factor base okay so let the factor
base B be equal to P 1 P 2 and so on
till P V okay and assume that C is
greater than B that is C some number
which is greater than P okay it could be
like B plus 10 or
plus 20 something in the pre-computation
phase next what we do is that we
construct we actually choose some army
tell you of XJ okay and find out the
value of alpha power of XJ it's a random
choice okay and we factor it out and the
thing is that you have to find out or
randomly choose but check that when you
are doing a prime factorization of alpha
power of XJ the prime factors should
belong to this factor this that is it
should be expressible in the form of
this congruence that is P 1 to the power
of a 1 J P 2 to the power of a 2 J and
so on take PB to the power of a BJ not
Allah P okay so now if you get such an
XJ value and if you so that so you are
you have to find out J I mean you have
to repeat this and find out seat such
choices and note that C is greater than
B okay so what so what we do first is
that we can also express these
congruence in this logarithm form by
taking the log on both sides then you
have got XJ is congruent to a 1 J
multiplied with log of P 1 with respect
to alpha plus 1 today BJ
log of P B BAE self based alpha and note
that when you want to consider in the
exponents then you are doing a modulo of
P minus 1 right because the exponent is
pon de l'épée minus 1 so you actually
are doing that and you obtain J such I
mean you obtain C such congruence is and
since your C is greater than B you can
expect that you will have a unique
solution for each of these logarithms
okay
so using this technique you can try to
compute the discrete blocks of each of
the prime elements in the factor base
that's your first step okay the next
step is actually quite trivial like what
you do is supposed to you already have
obtained the discrete blocks or the
elements in the factor base we now
compute the discrete blocks of beta with
respect to alpha now choose a random
integer s we are s lies between 1 and P
minus 2 and you compute a gamma where
gamma is equal to beta multiplied by
alpha power of s okay modulo P now you
attend to
Gama over the factor base so therefore
again you have to choose s such that
gamma can be factored or what the factor
this okay which means you have to repeat
this choice of s okay then if you can
factor out then then you have got P 1 to
the power of C 1 and so on did PV to the
power of C B modulo P if you take the
logarithm on both sides then you have
got log beta base alpha which you want
plus s equal to this thing right and
since you know all these C ones still C
B's and you also know all these
individual logarithms computing of
computation of this logarithm is
actually very simple you just take this
sum subtract out this and do a modulo P
minus 1 operation right so therefore
this is quite doable and if there's an
example to show that you take P equal to
1
3:07 alpha is equal to 5 and suppose the
factor base here is 2 3 5 & 7
okay the first step is to choose some
arbitrary value of x in this case the
choice of X are four zero six three five
one three six nine eight six five where
if you have raised this alpha to these
powers and compute the modulo you are
able to able to express their outputs in
the factor base okay as a so this gives
rise to three congruences which if you
solve you will be able to find out the
logarithms of each of this Prime's in
the factor this then you arbitrarily
choose a value of s in this case a
random value of s equal to seven seven
three six gives you the value if you
multiply this with nine four five one
you will get 8400 which can again be
factored in this factor base if you take
a logarithm in both sides and if you
subtract out s sake right they take the
sum and again subtract out this do a
modulo one three zero six then you are
able to obtain the corresponding
logarithm okay so I stop here at this
point and the comma just to be the note
that the complexity of this algorithm is
ordered but it's a sahba exponential
algorithm okay and it actually reduces
to order of e 1 plus small o of 1 and
raised to the power of square root of Ln
P Ln of Ln P okay which you can prove
but the proof is beyond the scope of
this class okay
so I'll just again continue with this
discrete log problem in the next class
but a small point which you can think on
is this that is you can think of this
problem like suppose the logarithm of
beta to the base alpha in a group G lies
in the interval of s comma T where s and
T are two integers such that 0 is less
than equal to s is less than T is less
than n where n is the order of alpha you
can actually think of how will you
modify the shanks algorithm to compute
the logarithm of beta to the base alpha
in order of square root of t minus s
okay so you already know the interval
and you have to develop the algorithm to
do that okay so in the next class my
reference has been Stinson's books and
the next class we'll continue with the
Feldman
you
you