Montgomery Reduction

Loading...

Do curso por University of Maryland, College Park

Segurança de Hardware

284 classificações

Explore Related Videos

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

University of Maryland, College Park

Segurança de Hardware

284 classificações

Curso 4 de 5 em Specialization Cybersecurity

In this course, we will study security and trust from the hardware perspective. Upon completing the course, students will understand the vulnerabilities in current digital system design flow and the physical attacks to these systems. They will learn that security starts from hardware design and be familiar with the tools and skills to build secure and trusted hardware.

Na lição

Physical Attacks and Modular Exponentiation

This week you will learn the fundamentals about physical attacks: what are physical attacks, who are the attackers, what are their motivations, how can they attack your system (from hardware), what kind of skills/tools/equipment they should need to break your system, etc. You will also see what are the available countermeasures. You will learn how system security level and tamper resistance level are defined and some general guidelines on how to make your system secure by design. In the second part, you will learn a useful mathematical operation called modular exponentiation. It is widely used in modern cryptography but it is very computational expensive. You will see how security vulnerability might be introduced during the implementation of this operation and thus make the mathematically sound cryptographic primitives breakable. This will also be important for you to learn side channel attack next week.

Physical Attacks (PA) Basics14:32

Physical Attacks and Countermeasures 13:55

Building Secure Systems 10:25

Modular Exponentiation (ME) Basics 6:15

ME in Cryptography8:54

ME Implementation and Vulnerability14:25

Montgomery Reduction11:51

Conheça os instrutores

Gang Qu
Associate Professor
Electrical and Computer Engineering

We now learn another way to do fast modular multiplication.

This method is known as Montgomery Reduction.

Let R and N be two integers that are relatively prime to each other.

And R is greater than N.

For any integer T, which is greater than or equal to 0 and less than the product

of N and R, the Montgomery reduction of T mod N with respect to R

is defined as the modular multiplication of T and R inverse mod N.

Where R inverse it the multiplicative inverse of R mod N.

Which means R times R inverse equal to one, mod N.

From this definition, we see that Montgomery reduction is nothing but

a modular multiplication and, mod, mod N.

The following algorithm actually tells us there are some other ways

to compute this quantity.

We start with some modular modification between T and

the negative and inverse mod R.

And we call this value m.

Next, we add T and

m times N, and the sum will be divided by R.

The quotient, t, will be compared with N.

If N is less than or equal to t, N will be subtracted from t,

and the final value of t will be report, reported as the Montgomery reduction.

Before we show this claim is true,

let's see what is interesting in the Montgomery reduction algorithm.

The goal of the algorithm is to compute the Montgomery reduction,

which is the modular multiplication and the mod N.

But in this algorithm you don't see any modular multiplication in the mod N.

What we do see is one modular multiplication in the mod R.

This feature actually gives us a way to speed up the modular multiplication,

which we'll show later on.

Now let's prove this result t is indeed the Montgomery reduction.

To prove this is true we have to show two things.

First t times R must equal to capital T and the mod N,

and second, t must be between zero and N.

To see the first equation, we start with the definition of t,

and we multiply both sides by capital R.

This gives us t times R equal to T plus m times N.

When we do a mod N operation, the second term disappeared, so

the only thing left is T as required.

If t is obtained by subtracting N from the original t,

we see this equation still holds.

Because it is entered a (mod N) operation.

So subtracting or adding a N doesn't change anything.

To see the second condition which tells the range of t,

we start with the definition of m.

So, m is defined as the remainder of T times megative N

inverse divided by R, or the mod R operation.

From the definition of remainder or

mod operation we know m must be between zero and R.

So if we multiply this inequality by N, we know zero is less than or

equal to m times N and less than N times R.

This combined with the range, we select a T, so we have the following inequality.

T plus m times N must be greater than or equal to 0,

and also less than one N times R plus another N times R,

so total less than 2 times N times R.

So if we divided this inequality by R, what we get is T plus

m times N divided by R will fall into the range of zero and 2 times N.

And this quotient, it is exactly the definition of T.

So we know that one T is less than, less than N, it is what we need.

And if t is greater than or equal to N, and following the definition,

N will be subtracted from t, again putting the, the value of t into the right range.

This completes the proof.

It tells us, indeed, the Montgomery reduction algorithm does give

us the correct answer from Mon, from Montgomery reduction.

When we plug in the definition of m into the equation for

t, indeed we get the Montgomery Reduction algorithm's formula.

Where the reduction equal to T plus T times negative N inverse mod R

times N divided by R.

And pay attention here, at the end we have a mod n operation.

And remember in the procedure we do have mod N.

So this mod N here is actually a shorthand in the notation.

Remember, when we do this division divided by R,

we know that if the quotient is less than N we don't do anything.

If the quotient of t is greater than or equal to N, we subtract the N from t.

This is exactly the modular operation.

So that is why we use mod N as a short-handed notation to indicate this

condition and this subtraction operation.

Next we'll show how we can use Montgomery Reduction to simplify,

or to speed up, the computation of modular multiplication, of modular multiplication.

So to apply Montgomery reduction, so let's pick integer R,

which is greater than N and relatively prime to N.

And then we compute the following quantities in order.

First, we compute an inverse mod N, and

then we do the modular multiplication between a and R mod N,

and similarly we do another modular multiplication between b and R mod N.

And the last of the two operations, are the Montgomery reductions.

First, we compute the Montgomery reduction of a prime times b prime

mod N, with respect to R, and then this new result is called c prime.

We can calculate the Montgomery reduction of c prime.

After we do this, we return the value of c, and the claim is c is

indeed the modular multiplication of a times b mod N.

And to see this,

we start from the definition of c and then plug in the definition of c prime.

So what we get is c prime times R inverse equal to

a prime times b prime times R inverse times another R inverse.

And because this multiplication, they are commutative, so

we pair up a prime with one of the R inverse to get a prime times R inverse,

which is a, following the definition here.

And similarly, b prime times R prime gives us b,

which shows this is indeed the modular multiplication.

So what we see here is we pick this R satisfies only two conditions.

First R must be greater than N.

And second, R and N must be relative prime to each other.

And so, as long as these two condition are satisfied, we can pick any R we want.

So when R happens to be a power of two.

So what we know that in digital computer, the multiplication of R in

this case will be a shift of k back to the left by k bits.

And the division by R with the modular

R operation will be a shift to the right by k bits.

So all these operations will be trivial operations.

So that is why, if we are following the Montgomery reduction algorithm and

pick R as a power of two, then this gives us

a great potential to optimize the modular exponentiation.

So now let's see example to see how this can be performed.

Let's see, we want to compute 68 times 57, modular 109.

So in this case, we have a equal to 68, b equals to 57, and N equal to 109.

So we pick a R which we want to have a power of 2 and greater than N.

So we pick R equal to 128, which is 2 to the power 7.

And then we compute an inverse and their mods R, which give us 27 101 here.

Because 109 times 101 equals to 1 modulo 128.

And when we put a negative sign here, it becomes 27.

So now we compute a prime, which is the modular multiplication between a and

R, in this case 68 times 128 which is 93.

And similarly, b prime will be defined as 57,

which is the value of b times R, which is 128.

And the result is 102.

And next we compute using the Montgomery reduction formula

to compute the Montgomery reduction of a prime times b prime.

So a prime times b prime which is the T here, plus the T times

negative N inverse which is 27 mod 128 times N,

which is 109, and then divided by R which is 128.

And if we simplify this, we realize the result is 178.

However, this is greater than N, which is 109.

So we subtract 109 from here.

We got the result, 69.

Next, we do another round of Montgomery Reduction of c prime.

So what we do is, we plug in the value of c prime into the formula here,

we've got c equal to c prime, which is 69,

plus 69 times 27 mod 128 times 101, 109 divided by 128.

And this give us a result of 61.

To verify this indeed is the result, the correct result, so

we used the naive, straightforward multiplication and modular.

So when we multiply 68 and 57, we got 3876.

And then when we do a mod 109, we got 61.

Which is exactly the same value here.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play