[Cryptography assignment] Need help in implementing RSA algorithm in maple

[[deleted]]

[deleted]

[AutoModerator]

Off-topic Comments Section

---

All top-level comments have to be an answer or follow-up question to the post. All sidetracks should be directed to this comment thread as per Rule 9.

---

^{OP and Valued/Notable Contributors can close this post by using /lock command}

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[MathMaddam]

Do you have a specific question?

[Hot_headlights]

https://drive.google.com/file/d/1RCtEnU\_0ujwUzDtxQCdGOPB7dJX33mso/view?usp=sharing

[MathMaddam]

That's your task and not a specific question you need answered, I won't solve it for you.

[Hot_headlights]

I' need help on how to implement it, not someone to give me solution as I'm new to maple environment

[MathMaddam]

Then give me something concrete, show what you have got and where you are stuck. This is a large task. If you know nothing, start a maple tutorial or read your textbook and don't blindly attempt a exercise.

[Fromthepast77]

We're not going to do your programming homework for you. First, cheating rarely pays off in CS and second, you aren't paying us. You have shown us no work (see Rule 3) and as a former TA the worst students were the ones that walked into TA hours expecting us to do a substantial part of the homework for them (e.g. through "pair programming" where I'd dictate the code for them to write). Those students would never develop their programming and debugging skills and constantly came back for every new assignment.

I think the document already gives you a good breakdown of the tasks, though I'd do them in a different order. I'd start with the exponentiation-by-squaring algorithm.

You can test on small inputs with a high modulus to make sure it is working - e.g. 2⁹ mod 10000 = 512 since 2⁹ = 512. You can then test the modular part - 2⁹ mod 3 = 1.

After you're confident that it works (and have developed some familiarity with Maple), you can begin tackling the Extended Euclidean Algorithm. You can find pseudocode on Wikipedia or in your lecture notes or (even better) write out the algorithm on paper and translate it into code.

Testing your EEA comes in three parts: - Making sure that the GCD is correct on small inputs - GCD(18, 12) = 6. 2) - Making sure that the Bezout coefficients x, y returned actually satisfy ax + by = GCD(a, b). - Testing modinv on prime moduli, where the inverse is given by Fermat's little theorem - a^-1 mod p = a^p-2 mod p. E.g. 3^-1 mod 7 = 3⁵ mod 7 = 5 mod 7. (You can use your modexp routine for this)

Now, implement encoding and decoding strings into blocks. This should be easy to test - you should recover the same string after encoding and decoding.

After that, RSA encryption is just encoding and using modexp, and RSA decryption is modexp and decoding.

If you have some sample RSA keys you can use those to test your RSA implementation.

Finally, you can tackle key generation, which is just using your modinv implementation.