Make encryption algorithm efficient enough to work quickly with larger numbers of encryption bits
Opened this issue · 2 comments
- Perhaps prime generation could be faster. Could be slow because 2 unique safe primes are needed. Should do more profiling, as is much slower than standard GMPY2 prime generation calls.
- Random number generation appears to be very slow. Perhaps could pre-generate lists of random numbers or parallelize randomness. Be careful with how child processes are seeded; sometimes in Python child processes use the same randomness seed as their parent.
I spent some time googling around for faster safe prime generation, and it seems like in general safe prime generation is much slower than single prime generation due to the requirement that p=2q+1 is also prime (which happens less and less often as the number of bits grows).
I did find one note describing a way to speed up safe prime generation: https://eprint.iacr.org/2003/186.pdf. However, given that our current method uses gmpy2 which is coded in C and that we would be implementing any alternative methods in Python, I think there's a good chance that we won't actually be able to produce a faster implementation.
Conclusion: Safe prime generation might just have to be slow. But at least it's a one-time cost and can be done independently prior to running the Shuffle-Sum algorithm.
Looks like some good ideas. Why are we limited to using python? We could just take gmpy2 and extend it to use this method, if it doesn't already