Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Cut and Choose - Applied Cryptography

Get Embed Code
1 Language

Showing Revision 2 created 05/24/2016 by Udacity Robot.

  1. Through this problem, you're asked to verify a set of blinded
  2. messages, where blinded message B equals the original
  3. message M times R random nonce raise to the power E
  4. mod n. And so the question is given the random nonce R,
  5. how do we get M from B. There are two very similar ways
  6. to accomplish this and I’ll talk about both of them. And the
  7. first way, the first step is to calculate the inverse of R mod
  8. n, I would like to talk for a second about what this means
  9. and how to calculate it. So in normal arithmetic not
  10. modular finding the inverse is easy, we can just divide by
  11. R. As a simple example, we have 3X equals Y, you can
  12. find X by dividing with 3. But with module arithmetic, this
  13. doesn’t work. Here are some example. 3X equals Y mod 5
  14. and so Y equals 2. If we just divide, we get X equals two-
  15. thirds which doesn’t make sense. X has to be an integer. It
  16. turns out the answer is actually 4 because 3 times 4 is 12,
  17. and 12 mod 5 is 2. And so we need to find a sum Z such
  18. that 3 times Z is congruent to 1 mod 5. It’s fairly easy to
  19. see that Z equals 2 accomplishes this. 3 times 2 is 6, 6 is 1
  20. mod 5. So going back up to our original problem, you can
  21. solve 3X is congruent to Y mod 5 for X, writing it X is
  22. congruent to 2Y mod 5. So if Y equals 2, X is 2 times 2
  23. which is 4. And for mod 5, here are all the inverses: 1
  24. times 1 equals 1, 2 times 3 equals 6 which is congruent to
  25. 1, 3 times 2 equals 6 which is congruent to 1. And 4 times
  26. 4 is equal to 16 which is congruent to 1.
  27. And so we can calculate inverses using the extended
  28. Euclidean algorithm which is implemented in the PyCrypto
  29. library in crypto.util.number.inverse.
  30. So now that we have the inverse of R mod n, we can
  31. calculate our blinded message. You should calculate B to
  32. the power D which equals M times Re to the power D
  33. since E and D are the public and private keys RSA
  34. encryption, we get M to the power D and R mod n. If we
  35. multiply by the inverse of R, we get MD mod n, and if we
  36. apply the public exponent, we can get M.
  37. And the second way of solving this problem. First, take a
  38. random nonce to the power E and we call that R. We’re
  39. going to calculate the inverse of R, if we take our blinded
  40. message times inverse of R, we get our message times
  41. Re times R since Re in capital R inverses they cancel and
  42. we are left with just our message.
  43. Comparing the two ways, the second way is quicker. It
  44. involves one exponentiation and one inverse whereas the
  45. first way requires two exponentiations and one inverse.
  46. And here is my solution. In this first step, we calculate
  47. what I call capital R big nonce. We use the inverse
  48. function from the PyCrypto library to calculate the inverse
  49. of our big nonce, modulus D, our N value. We can then
  50. remove the nonce from our bill by multiplying the bill times
  51. the nonce inverse. Again, modulus N returning. So N the
  52. verify function itself, we loop through all the bills and nonces
  53. remove the nonce, check the value where message
  54. value does give inversions to change message versus
  55. an imager into bits. Make sure
  56. the padding is right. And then convert the bits to a string
  57. and then check the value of that string. We then see if the
  58. test value is equal to our target value, if it's not return false
  59. so you don't need to verify any more. If we've passed
  60. all of these, return true.