I am making a chat feature in my app where I want to encrypt it E2EE, but the problem is when I start to calculate the public key (public key = g^private % n) it takes a decade to get it done. I need to know how to simplify it for the CPU.
-
5What CPU, language and code? Also realize that secure e2ee is very difficult to get right, you have a close to zero chance. Better to use something like open source Signal.– zaphDec 31, 2018 at 14:07
-
How are you doing the modular exponentiation? Are you doing exponentiation by squaring?– forestJan 1, 2019 at 2:45
-
Android device @zaph– Aly HassanJan 1, 2019 at 8:42
-
@forest I am just using the equation the same as this with vars (public key = g^private % n)– Aly HassanJan 1, 2019 at 8:43
-
@AlyHassan Well that explains why it's so slow. You should never directly perform that computation as it will take forever. You need to use an optimized modular exponentiation algorithm.– forestJan 1, 2019 at 8:47
|
Show 3 more comments
2 Answers
DON'T ROLL YOUR OWN CRYPTO
Writing a crypto implementation is hard: not only does it have to "work" in the sense that the math is right, you're properly handling big ints, etc; but it has to be "secure" in the sense that you have no buffer overflows, you handle all error conditions correctly, your code is completely timing invariant, etc.
Put it this way: if I was a dev manager and we needed to write and harden a production-quality Diffie-Hellman implementation, I would want 1 - 3 PhD level crypto engineers and I would give them ~ 1 month to write and harden the implementation. If that doesn't describe your team, then I would suggest using a cryptographic library instead.
For what you're describing, I would use the Signal Protocol (there are libsignal libraries in most major programming languages). If you really want to use DH directly, then I would use the crypto package for your language, or OpenSSL. In addition to security, you'll get the side-benefit that these implementations will be much faster than yours since they will use advanced mathematical and assembly language tricks to make the exponentiation and modular reductions more efficient.
DON'T ROLL YOUR OWN CRYPTO
answered Dec 31, 2018 at 15:57
-
2Interesting: "1 - 3 PhD level crypto engineers". Were I worked there was a minimum of a doctorate level and that did not mean they were any good at real-world problems. Or as my boss said: "A PhD means they have solved one problem in their life." and we had a substantial number that were basically worthless. And then one must wonder what degree Moxie has.– zaphDec 31, 2018 at 22:57
-
2DH is actually pretty simple. I'd just hire one guy with the qualifications to implement cryptographic primitives. It's not that difficult to do securely. While you're absolutely correct that you shouldn't try to put together your own cryptosystem, I think you're exaggerating the amount of effort required significantly.– forestJan 1, 2019 at 2:45
-
ok, I can agree with you at this point, but since I am no expert in security. How do I secure my Chat E2EE? What Android libraries can I use? Jan 1, 2019 at 8:47
-
1@AlyHassan This answer gives an example (Signal). My answer additionally gives OTR as an example (OTR is a protocol designed for secure end-to-end encrypted chat), which is usable with the libotr library.– forestJan 1, 2019 at 8:48
It's likely that the reason this operation is so slow for you is because you are using the naïve method of modular exponentiation where you compute a power first and perform modular reduction second. You need to use certain optimizations to avoid this. In particular, when the exponent and modulus are large, you can use a form of exponentiation by squaring for efficiency. If you are doing this in Java, which I would guess based on the fact that you are writing this for Android, you can use modPow().
However, I do need to point out that Mike Ounsworth is absolutely correct. You really should not be implementing cryptographic primitives on your own without a significant amount of experience. While you may be able to implement the algorithm, you will likely not be protected against edge cases, nor will your implementation be resistant to side-channel attacks. Just because it works doesn't mean it's secure!
So what should you do if you really want to write your own end-to-end encrypted chat application? Use an existing library which provides this functionality. Even better, you can use an entire pre-designed secure protocol such as OTR or Signal, allowing you to have secure encryption safely.
-
2To expand on what forest states: If you implement your own crypto solution it will appear to you to be secure but most likely will not be. Even Moxie made mistakes in Signal that needed to be corrected. His mistakes (at least one) were found by others because it is popular and believed to be secure by experts. Your implementation will not receive that level of 3rd party scrutiny and attackers will not tell you.– zaphJan 1, 2019 at 13:20