Week 1: Starting My Research: Computational Hardness Assumptions

Apr 07, 2022

Hello everyone and welcome back to my blog! After the website deleted my first draft, I have finally mustered up the will to redo this. I began my senior project by researching the math behind cybersecurity and encryption as well as the assumptions and principles used.

I began with computational hardness assumptions-assumptions about how hard it would be (how long it would take a computer) to decrypt messages/”crack the code” without the key. Computational hardness assumptions are what all cryptographic algorithms are built upon. I learned that while in theory it is possible to have an algorithm (such as “one-time pad”) with an infinitely difficult computational hardness assumption, in practice, algorithms that are used such as RSA do not as algorithms with infinitely difficult computational hardness assumptions are comically impractical.

I continued my research by looking at RSA. I created a list of question which will be my basis for research in future weeks based on problems I faced in attempting to recreate RSA in python. For example, how large primes used for RSA are generated and how computational difficulties (even with the key) are overcome. I also did some math to figure out generally how to decipher messages encrypted with RSA (I found the multiplicative inverse of a mod b given the multiplicative inverse of b mod a).

3 Replies to “Week 1: Starting My Research: Computational Hardness Assumptions”

  1. Szymon S. says:

    How do you plan to generate primes?

    1. Soren D. says:

      Very good question! I initially tried just creating a long list of every prime number up to a certain size and then randomly selecting primes from that list, but this would’ve taken my computer way too long before primes big enough to be used for RSA were found, so instead I wound up writing code to randomly select a number of a certain size and then test if it is prime, if it is not the computer selects another number and tries again. For actual encryption, this is approximately the same method used but it is modified to select numbers that are more likely to be prime. I discuss some of the tests for whether or not a number is a prime candidate in my next blog post.

  2. Danny D. says:

    Do you have alot of experience working in python or are you learning it during your project?

Leave a Reply