
Title:
Cut and Choose  Applied Cryptography

Description:

Through this problem, you're asked to verify a set of blinded

messages, where blinded message B equals the original

message M times R random nonce raise to the power E

mod n. And so the question is given the random nonce R,

how do we get M from B. There are two very similar ways

to accomplish this and I’ll talk about both of them. And the

first way, the first step is to calculate the inverse of R mod

n, I would like to talk for a second about what this means

and how to calculate it. So in normal arithmetic not

modular finding the inverse is easy, we can just divide by

R. As a simple example, we have 3X equals Y, you can

find X by dividing with 3. But with module arithmetic, this

doesn’t work. Here are some example. 3X equals Y mod 5

and so Y equals 2. If we just divide, we get X equals two

thirds which doesn’t make sense. X has to be an integer. It

turns out the answer is actually 4 because 3 times 4 is 12,

and 12 mod 5 is 2. And so we need to find a sum Z such

that 3 times Z is congruent to 1 mod 5. It’s fairly easy to

see that Z equals 2 accomplishes this. 3 times 2 is 6, 6 is 1

mod 5. So going back up to our original problem, you can

solve 3X is congruent to Y mod 5 for X, writing it X is

congruent to 2Y mod 5. So if Y equals 2, X is 2 times 2

which is 4. And for mod 5, here are all the inverses: 1

times 1 equals 1, 2 times 3 equals 6 which is congruent to

1, 3 times 2 equals 6 which is congruent to 1. And 4 times

4 is equal to 16 which is congruent to 1.

And so we can calculate inverses using the extended

Euclidean algorithm which is implemented in the PyCrypto

library in crypto.util.number.inverse.

So now that we have the inverse of R mod n, we can

calculate our blinded message. You should calculate B to

the power D which equals M times Re to the power D

since E and D are the public and private keys RSA

encryption, we get M to the power D and R mod n. If we

multiply by the inverse of R, we get MD mod n, and if we

apply the public exponent, we can get M.

And the second way of solving this problem. First, take a

random nonce to the power E and we call that R. We’re

going to calculate the inverse of R, if we take our blinded

message times inverse of R, we get our message times

Re times R since Re in capital R inverses they cancel and

we are left with just our message.

Comparing the two ways, the second way is quicker. It

involves one exponentiation and one inverse whereas the

first way requires two exponentiations and one inverse.

And here is my solution. In this first step, we calculate

what I call capital R big nonce. We use the inverse

function from the PyCrypto library to calculate the inverse

of our big nonce, modulus D, our N value. We can then

remove the nonce from our bill by multiplying the bill times

the nonce inverse. Again, modulus N returning. So N the

verify function itself, we loop through all the bills and nonces

remove the nonce, check the value where message

value does give inversions to change message versus

an imager into bits. Make sure

the padding is right. And then convert the bits to a string

and then check the value of that string. We then see if the

test value is equal to our target value, if it's not return false

so you don't need to verify any more. If we've passed

all of these, return true.