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.
