Public-Key Cryptosystems | RSA Assumption | Alison
Loading
Notes d'étude
Study Reminders
Support
Text Version

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Foundations of CryptographyDr. Ashish ChoudhuryDepartment of Computer ScienceInternational Institute of Information Technology – BangaloreLecture – 45RSA AssumptionHello everyone, welcome to this lecture.(Refer Slide Time: 00:42)So just to recap in the last lecture, we have seen Candidate Public Encryption Scheme, CPA￾secure Public Encryption Scheme, mainly El Gamal encryption scheme. In this lecture and the next lecture, we will discuss another Candidate Public Encryption Scheme based on the different hard problem, which we call as RSA assumption, which will lead us to another public encryption scheme namely the RSA Public Encryption Scheme.(Refer Slide Time: 00:58)So to understand the RSA assumption, let us first try to understand the set ZN*. So ZN*basically is a set of integers modulo N, which are co-prime to the modulus N, namely ZN* is the collection of all elements b in the range {1,…,N-1} such that the element b is co-prime to the modulus N. Namely, their GCD is 1. For example, the set Z10* is nothing but the elements 1,3,7, and 9.Because all these elements 1, 3,7, and 9, they are co-prime to the modulus 10, and it is easy to see that if modulus N is prime, then the set ZN* basically consist of all the elements 1 to N-1.So, a well-known fact from the number theory whose proof I am skipping is that the set ZN*along with the operation multiplication modulo N constitutes a group and satisfies all the axioms of the group.So, for instance, I have drawn the matrix for the elements in Z10*, namely 1, 3, 7 and 9, and the result of performing the operation multiplication modulo 10 for any pair elements from the set, and now you can see that all the axioms of the groups are satisfied and that is why this is a group. Moreover, a well-known fact from the number theory is that we have polytime algorithms for computing the multiplicative inverse, which I denote by, a-1, for any element a in the set ZN*. And there is a well-known algorithm for that, which we call as Extended Euclid’s GCD algorithm, which we will discuss in one of our subsequent lectures, and the running time of that algorithm is polynomial in the number of bits that we need to represent the modulus N.(Refer Slide Time: 02:47)So, let us next discuss Euler’s Totient Function, φ function. So the Euler’s Totient Function, which is the denoted by the symbol φ(N) is basically the cardinality of the set ZN*, namely it is the number of elements in the set 1 to N-1, which are co-prime to your modulus N. Some of the well-known facts again borrowed from Number theory are as follows. If N is a prime p, then the value of φ(p) is nothing but p -1. Because there are exactly p-1 elements, which are co-prime to p. On the other hand, if n is the product of 2 distinct primes, p and q, then φ(N) is nothing but p-1 times q-1. That means, there are these many elements, namely p-1 times q-1 elements in the range {1,…., N-1}, which will be co-prime to your modulus N. To verify that, let us take an example, say N = 10, which you can write as the product of 2 and 5, where 2 and 5 are prime. So your p is 2 and your q is 5, then we know that there are 4 elements in the set Z10*, so φ(10) should be 4, and 4 is nothing but p-1, namely 2-1 multiplied by q-1, which is 5-1, and finally another interesting property which we will use from Number Theory is that, for any element a in the ZN*, aφ(N) modulo N is 1. That means, if N is a prime p, then this φ(N) is nothing but p-1, so we get ap-1 modulo p to be 1.This property or this result is also called as Fermat’s Little Theorem, and we also get due to this fact, the corollary that if you have any element a belonging to the set ZN*, then ax modulo N is exactly the same as ax modulo φ(N) modulo N. That means, in the exponent you can reduce the exponent x to x modulo φ(N). So the reason this corollary issue is that, if your x is anyhow less than φ(N), then both L.H.S. and R.H.S. are same, but if your x is more than φ(N)then to compute ax modulo φ(N), what you can do is, you can rewrite axas several batches of aφ(N)with φ(N) in the exponent. aφ(N) depending upon the relationship between x and φ(N), and the last batch will have ax modulo φ(N), and everything in the base modulo N. Now, we know that aφ(N) modulo N is 1, that means each of these batches, you have full aφ(N) modulo N, are going to give you the answer 1. So, all this batches are going to give you the answer 1, 1, 1, 1 and 1 multiplied by 1 is going to give you 1. So, you are finally left with the last batch, which has ax modulo φ(N). So, that is how we get this corollary.(Refer Slide Time: 06:03)So, with all this mathematics in place, now let us try to understand the RSA permutation. So this RSA permutation is a mapping from the set ZN* to ZN*, so the way this permutation is defined as follows. Imagine, you are given an exponent e, which is greater than 2, such that the exponent e is co-prime to your value φ(N). So, I stress it is co-primed to φ(N), not to N.Now, a well-known fact from Number Theory is that if you have an e, which is co-prime to φ(N), then you can find out the multiplicative inverse of that e modulo φ(N).In general, if you have 2 numbers, say a and b, such that GCD of a and b is 1, that means, a and b are co-prime to each other, then you can always find the multiplicative inverse of a modulo b. So, my modulus in this case is φ(N), because e is co-prime to φ(N), and if e is co￾prime to φ(N), by using the Extended Euclid algorithm, I can find d where e and d constitutes their mutual multiplicative inverses.That means, e times d modulo φ(N), and d times e modulo φ(N) is 1. Now, the RSA permutation is defined as follows. To go in the forward direction, the function is fe, and to compute the value of fe(x) where x is a member of ZN*, we basically compute xeand do mod N. On the other hand, the reverse direction function is basically a function of d, namely, fd(y), and this function is basically if I want to compute fd(y), I will compute yd, and then perform mod N.I claim here that the function fd is the inverse of the function fe and vice versa. So, for that consider any arbitrary x here, belonging to ZN*, and say I map it to y, as per the function fe,so my y is nothing but xe, and now let’s see what we obtain by reversing this value y as per the function fd. If I reverse this y as per fd, then I obtain xe mod N, and then whole raise to the power d mod N.So I can take the overall mod outside, and I obtain that this is the same as xetimes d modulo N, and by using the corollary that we have stated in the last slide, xed modulo N in the exponent, I can reduce this exponent e*d to e*d modulo φ(N). I know that e*d modulo φ(N), which is there in the exponent, gives me value 1, because I have chosen e and d such that they are multiplicative inverse of each other.So, in the exponent, it is e times d modulo φ(N) reduces to 1, so hence I obtain that this xedmodulo N is nothing but x modulo N, and since I have chosen my x to belong to the set ZN*.That means x is anyhow less than N, and if x is less than N, then x modulo N gives you x such that the effect of mod does not happen at all. So this proves that your function fd and feare mutually inverse of each other.I also prove here now that my function fe(x) is a bijection, and that means, it is a one-to-one onto mapping. For that, let us consider an arbitrary pair of inputs x1, x2, from the set ZN*, and say the resultant images of x1 and x2 as per the function fe, are y1 and y2. Now, if y1 and y2 are same, that means, x1e modulo N, is same as x2e modulo N, that means, if I raise both the sides to the exponent d, I get x1ed modulo N is same as the x2ed modulo N.This basically means that x1 is equal to x2, because x1ed modulo N, is nothing but x1 and x2edmodulo N is nothing but x2. So that means, if I take an arbitrary x1, x2 mapping to the same y, then basically I end up showing that x1 is equal to x2, and hence I overall get that my function fe is a permutation here.(Refer Slide Time: 10:32)Now, let us discuss resultant assumption, which will be related to the RSA assumption, which we will finally discuss. This is called the Factoring Assumption, and the intuition behind this assumption is that, if you are given the product of two large arbitrary prime numbers, it turns out that finding the prime factors is indeed a difficult task. This is a very widely known and well-studied problem studied over several centuries. And till now, we do not have efficient polytime algorithms for factorizing a product of two arbitrary prime numbers, if those prime numbers are chosen arbitrarily. So, this intuition or the hardness of this problem is going to be formalized by an experiment, and for that experiment, let us first define an algorithm, which we call as GenModulus algorithm. It basically picks two random n-bit prime numbers, say p and q, and there are well-known algorithms to pick random prime numbers.I am not going into the exact details at how exactly you pick those two random prime numbers, in poly(n) time. You can refer to the book by Katz and Lindell for the exact algorithm. Now, once p and q are chosen, you compute the modulus, namely N, which is the product p and q. Now, the Factoring Assumption, with respect to the GenModulus algorithm, is modeled as an experiment, which we call as Factor Experiment, and the rules of that experiment are as follows.The challenger runs the GenModulus algorithm, generates the parameter N, p, and q, and the challenge is thrown to the adversary, namely N, and the challenge for the adversary is to come up with its prime factorization, namely p and q. So, it submits a pair of numbers, p’ and q’, and we say that the output of the experiment is 1, namely adversary has won the experiment if indeed, the pair p’, q’ is exactly the same as the prime factorization of your modulus N, and we say that the Factoring Assumption holds with respect to our algorithm GenModulus, if for every polytime adversary, the probability that the adversary could come up with correct factorization of the modulus N, is upper bounded by some negligible function. Notice that, there is always a guessing strategy by an adversary, it can guess some p’ and q’, and with non-zero probability, it may indeed with the correct factorization of N. (Refer Slide Time: 13:00)What we want is basically that no polytime adversary should be able to do anything better than that. That is basically the intuition of this experiment. Now, finally let us see the RSA assumption here. So, it turns out that Factoring Assumption, even though it looks like a candidate One-Way Function, that means that if I give you the product of two arbitrary large prime numbers and challenge you to come up with the factorization, then that looks like a candidate One-Way Function. But just based on this candidate One-Way Function, we cannot directly get a practical public-key cryptosystem. So, to get around that, we introduce a related problem, which we call as an RSA problem, whose difficulty is related to the hardness of the factoring problem. So, this RSA problem is described with respect to another parameter generation algorithm, which we call as GenRSA.So, what does GenRSA algorithm does is, it first runs the GenModulus algorithm and pick up random primes p and q of size n-bits each, and multiples them to get the modulus N, and now it computes the value φ(N) and it is computable because φ(N) is nothing but the product of p-1 and q-1. Then this GenRSA algorithm picks an exponent e such that e is relatively prime or co-prime to φ(N).And since e is co-prime to φ(N), by running the Extended Euclid’s algorithm, the multiplicative inverse d of e modulo φ(N) can be computed. Overall, this GenRSA algorithm now outputs N, p, q, e, and d. Intuitively, the RSA problem is, if you are given just a public modulus N and the public exponent e, and the random element y from the ZN* set, then the challenge for you is to compute the eth root of y modulo N without actually knowing the actual value of d or without knowing the prime factorization of N.I stress that the challenge is to compute eth root modulo N because if I just challenge you to compute the eth root without modulo N, that is very easy to do that. The challenge here is to compute the value of eth root of the random y modulo N, which is formalized by this experiment which I call as RSA-inv experiment.The experiment is as follows, the challenger runs the GenRSA algorithm to generate the parameters N, p, q, e, d are random-wise chosen from the set ZN*. Again, if you are wondering that how picking up a random element from the set ZN* is possible in poly(n) time, well it is possible, you can see the reference book by Katz and Lindell where the algorithm is given of how to pick random elements.Now the challenge for the adversary is to find out the eth root of this random y just based on the knowledge of public modulus N and the public exponent e. So, it has to output a group element say x and we say that adversary has won the experiment or the output of the experiment is 1, if and only if, x is indeed the eth root of random y modulo N, namely if xemodulo N is y. We say that RSA assumption holds with respect to this GenRSA algorithm, if for every polytime algorithm participating in this experiment, the probability that it can come up with the correct eth root of a random y is upper bounded by some negligible probability.(Refer Slide Time: 16:23)Now, let’s try to compare the RSA assumption and Factoring Assumption, because on a high level, they might look similar to you. So, on your left hand side you have the factoring experiment where the challenge for the adversary is to come up with the prime factors of the public modulus N. On the right hand side, you have the experiment modeling the RSA problem where adversary is now given some extra information as part of its challenge, namely, it is given the public exponent e and the random y from the set ZN*, and its goal is to come up with eth root of random y modulo N.It turns out that we can prove that if RSA assumption holds, then Factoring Assumption also holds and this can be proved by contrapositive, namely, if you assume that factoring is computationally easy, that means it is possible for a polytime adversary to come up with a prime factorization p, q of a modulus N. Then, once you factorize your modulus N into its prime factorization of p and q, then you can easily compute φ(N) because φ(N) is nothing but p-1 times q-1.And if φ(N) is computable in polytime and anyhow e is given to you, then by running the Extended Euclid algorithm, you can yourself compute the multiplicative inverse of e, namely d, and once you compute d, the eth root of y is nothing but yd modulo N. That means, this implication is indeed true. On the other hand, let’s try to consider the relationship between the Factoring Assumption and RSA, in the sense, can we say that if Factoring Assumption holds, then RSA assumption holds and we do not have any answer for this. That means, we cannot prove that if RSA assumption does not hold and the Factoring Assumption does not hold. It is a big open problem because there might be a way to efficiently solve the RSA problem without actually factoring your modulus. Because one of the ways of solving the RSA problem might be to factorize your N and then once the factorization is known, come up with value of d and so on, but that need not be the only way to solve the RSA problem. There might be other ways to compute to solve the RSA problem in polynomial amount of time without actually factorizing your modulus, and in that sense, making the RSA assumption is a very strong assumption compared to making the factoring assumption because difficulty wise, the factoring problem looks like a more challenging problem, more difficult problem than solving the RSA problem.(Refer Slide Time: 19:05)So, finally let us discuss how exactly you can utilize your RSA Permutation as a Trapdoor Permutation because in our next lecture, we are going to treat our RSA Permutation as aTrapdoor permutation, and we will see that how we can formulate an instantiation of public encryption scheme from this RSA Permutation. So, for that recall the definition of One-Way Trapdoor Permutation.So, it is a function from set x to the set x, which is easy to compute for any input from the domain, but the difficult to invert from any random input from the co-domain, until and unless you are given with special trapdoor information. So, this is formalized by saying that more formally we have trapdoor permutation scheme over the set x, which consists of a Key Generation algorithm, a trapdoor function f, and its inverse where the Parameter Generation algorithm will output a public parameter and a secret parameter, the function f is basically, a keyed function, keyed by the public key pk and it takes value from the set x and it gives you an output from the x set and it is a Deterministic algorithm and the corresponding inverse algorithm is operated by a secret key, so your secret key is basically acting as a trapdoor information here and using this trapdoor information, you can correctly invert any y from the codomain, namely the set x. The correctness property that we require from the trapdoor permutation scheme is that for every pair of parameter generated by Generation algorithm, for every x from your domain, if you compute the value of fpk(x), and say obtain the y output, and now if you invert that y with the secret key sk, you should get back the x, and a second requirement is the one wayness requirement, which basically states that your function f should behave like a one-way function, even if an adversary knows the value of the public parameter pk.(Refer Slide Time: 21:09)So, let us see how we can visualize the RSA permutation from the set ZN* to ZN* as an instantiation of the Trapdoor Permutation. So, basically RSA Trapdoor Permutation consistsof three algorithms, the Parameter Generation algorithm is nothing but GenRSA algorithm, namely, it picks uniformly random n-bit prime numbers, p and q, compute the modulus N, and then compute the size of ZN*, namely φ(N).It picks up the public exponent e, such that e is co-prime to φ(N). Since e is co-prime to φ(N), by running the Extended Euclid algorithm, multiplicative inverse of e modulo φ(N) is computed and the public parameters are N, e, and the secret parameters are N, d. The forward direction function, namely the function fRSA, and operated with the public key N, e is as follows. To compute the value of this function fRSA on an input x basically you just output xe modulo N, and xe modulo N can be computed in poly(n) time. We will see later on how exactly this group exponentiation can be computed in polynomial in n amount of time. On the other hand, if you have a trapdoor namely a secret parameter n, d and if you want to invert any given y from the set ZN*. Basically you have to compute yd modulo N. So, let’s see whether this RSA Trapdoor Permutation indeed satisfies the requirement of a generic Trapdoor Permutation Scheme. So the correctness requirement states that, it should hold that xefollowed by raising it to d modulo N, should give me my x and we already have proved that indeed that is the case when we showed that the function f and the inverse RSA function are inverse of each other.On the other hand, the One-Wayness property from this RSA permutation, requires that anyone who knows just the public parameter, namely say N, e, but does not know the trapdoor information, say d, without the knowledge of the trapdoor information, it is difficult to compute the eth root of any random y, and its turns out that indeed that is the case if the RSA assumption holds with respect to your Parameter Generation algorithm that means.If indeed the RSA problem is difficult to solve with respect to this RSA Parameter Generation algorithm, then this so called RSA permutation can be viewed as an instantiation of your Trapdoor Permutation. So, recall that in one of our previous lectures, we had seen that how generically we can convert Trapdoor Permutation Scheme into a key agreement protocol with weak secrecy notion.And now if you instantiate Trapdoor Permutation by an RSA Trapdoor Permutation, then by using the RSA Trapdoor Permutation, we actually obtain an RSA key exchange protocol, which gives you a weak secrecy notion, namely the resultant key is going to be known to the sender and the receiver, and the adversary will not know the full key in its entirety. On the other hand, the discrete log function that we had discussed earlier, it cannot be viewed as an instantiation of the Trapdoor Permutation. Because we know the forward-direction function, namely say gxcan be treated as your forward direction function, but we do not know what should be the corresponding trapdoor information using which we can use and invert back this function. That is kind of big challenging problem which is there. On the other hand, in the context of RSA permutation, we have the corresponding trapdoor associated namely the exponent d, which is the multiplicative inverse of e, modulo φ(N). So that brings me to the end of this lecture. In this lecture, we have introduced the RSA assumption, and we have seen the relationship between the RSA problem and the factoring problem. Thank you.

Notification
You have received a new notification
Click here to view them all