What I’ve learned about RSA Encryption and Large Prime Numbers – How To Generate

One of the ways in which I function, is to write down thoughts in this blog, that may seem clear to me at first, but which, once written down, require further thought and refinement.

I’ve written numerous times about Public Key Cryptography, in which the task needs to be solved, to generate 1024-bit prime numbers – or maybe even, larger prime numbers – And I had not paid much attention to the question, of how exactly to do that efficiently. Well only yesterday, I read a posting of another blogger, that inspired me. This blogger explained in common-sense language, that a probabilistic method exists to verify whether a large number is prime, that method being called “The Miller-Rabin Test”. And the blogger in question was named Antoine Prudhomme.

This blogger left out an important part in his exercise, in which he suggested some working Python code, but that would be needed if actual production grade-code was to generate large prime numbers for practical cryptography. He left out the eventual need, to perform more than just one type of test, because this blogger’s main goal was to explain the one method of testing, that was his posting subject.

I decided to modify his code, and to add a simple Fermat Test, simply because (in general,) to have two different probabilistic tests, reduces the chances of false success-stories, even further than Miller-Rabin would reduce those chances by itself. But Mr. Prudhomme already mentioned that the Fermat Test exists, which is much simpler than the Miller-Rabin Test. And, I added the step of just using a Seive, with the known prime numbers up to 65535, which is known not to be prime itself. The combined effect of added tests, which my code performs prior to applying Miller-Rabin, will also speed the execution of code, because I am applying the fastest tests first, to reduce the total number of times that the slower test needs to be applied, in case the candidate-number could in fact be prime, as not having been eliminated by the earlier, simpler tests. Further, I tested my code thoroughly last night, to make sure I’ve uploaded code that works.

Here is my initial, academic code:

http://dirkmittler.homeip.net/text/Generate_Prime_3.py

 

(Corrected 10/03/2018, 23h20 … )

(Updated 10/08/2018, 9h25 … )

Continue reading What I’ve learned about RSA Encryption and Large Prime Numbers – How To Generate

A Hypothetical form of Broadcast Encryption

I have pursued the mental exercise, of supposing that a group of (n) people might exist, who are to receive a broadcast, encrypted message, but in such a way that two of those recipients’ credentials are required, to decrypt that message. The assumed author of the message is a secure party, entrusted to keep all the encryption details of the system.

The basis of my exercise is, that RSA encryption and hybrid encryption may be used, with the twist, that as long as the modulus is the same for two transactions, a symmetrical key can be encrypted twice, in order to be decrypted twice. A formalized way to write this could be:

C = (T ^ E1) ^ E2 mod (p)(q)

T = (C ^ D2) ^ D1 mod (p)(q)

Where (p) and (q) are random 1024-bit prime numbers, (T) stands for the symmetrical encryption key, and (C) stands for the encrypted form of that key. Clearly, (p) and (q) would be filtered by the central party, such that neither (p-1) nor (q-1) are divisible by either (E1) or (E2), which are, 65537 and 32771 respectively.

My concept continues, that the central party associates a single prime number with each distributed recipient for the long term, and that the recipient is not allowed to know their own prime number. For any pair of recipients, a modulus (p)(q) follows, which the recipients store, for each other recipient, that the current recipient may eventually want to combine his key with.

(Corrected 09/22/2018, 18h00 … )

(As of 09/21/2018, 23h40 : )

Continue reading A Hypothetical form of Broadcast Encryption