 ## ← Cut and Choose - Applied Cryptography

• 2 Followers
• 60 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=B-b3UqOLxQk" data-team="udacity"></div> ``` 1 Language

• English [en] original

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.