My course is secure programming.
This part may be regarding Modular exponentiation. I guess this question need to use Windowing method to solve it.
I uploaded my lecture video to youtube. You can see the video at 54:44
https://youtu.be/AGhx11CCpNg?t=3284
This is my question 3
Windowing method Compute x" where n = 2654310 [o - 7)8 bit Because we is using 8 bit 116 011' 116 101 111 = ' ( x 683). x 3 (x51 ) 23 . x 6 (x414) 23 . x5 (x3317) 23 . X7 x51 x414 x 3317 x26543 # mul 4 Pre-compute x, x', . .., x (6 muls) 16 + 6 = 22 multiplications (vs 24 muls non-window) ( ) . ( ) ) . 1 2 4 multiplication Windowing method Compute x" where n = 2654310 For the precomputation table, I think we need to get every value that can be represented by binary for the window size you have chosen. So, in this case, the window size is 3, and we can have 0 to 7 in binary (000, 001, 010, 011, 100, 101, 110, 111). As we work left to right, we 110 011 110 101 111 take xin where n is the number represented in binary by that window. For the first one, 110 is 6, so we take x"6. Then, we take that value to x6 (x6)23. x 3 (x51)23.x6 (x414)23 . x5 (x3317) 23 . x7 the power of 2*3, and multiply it all by x'n for the next window - for the second one ((x*6)*2*3)*x*3 *where x*3 is because our window is 011 x6 x51 414 3317 which is 3 in binary. We don't have 2 or 4 in binary in any of our x26543 windows for this problem, so they aren't actually used. However, when we do the precomputation table we still calculate them. Remember # mul that the method for calculating the values in the precomputation table s: x*2 = xx (1 multiplication), x*3=(x*2)x (2nd multiplication), ., x*7= (x*6)x 6th multiplication). However, where can I find x*2 and x*4 in the slide? So I don't understand this logic. Pre-compute x2, x3, . .., x7 (6 muls) 5 2626, 20, 16 + 6 = 22 multiplications Where can I find Je and 2(4 ?3) This part may be regarding Modular exponentiatron This part is about the m-ary algorithm for calculating modular exponentiatron. The pseudocode of the algorithm is given in Algorithm 1. 3.1) Assuming a window size w, how many multiplications are required for calculating the precomputation table g? 3.2) Assuming that e is a random n-bit number and the window size if w, how many multiplication and square operations are expected to be required for computing the exponentiatron phase? 3.3) What is the optimal value of w if e is a 2048 bit number? input : Window size w, basis b, exponent e = _ ei2", modulus p output: be mod p / / Precomputation g[1] - b for i from 2 to 2" do | gli]
