Re: [viff-devel] Speed of ElGamal encryption
160 bit -- Janus Den 21/09/2008 kl. 17.02 skrev Claudio Orlandi: Could everyone specify the size of the field and the size of the secret keys used? Otherwise it's quite hard to understand the performance reported. Regards, Claudio On Sun, Sep 21, 2008 at 4:59 PM, Adam Langley <[EMAIL PROTECTED]> wrote: On Sun, Sep 21, 2008 at 3:23 AM, Martin Geisler <[EMAIL PROTECTED]> wrote: Calling a ElGamal function in NaCl would be very cool and probably a bit faster since you wont have to do all the tuple packing and unpacking that you do in the Python version. NaCl has support for a primitive called a 'box'. The boxing function takes these inputs: * The message * An nonce * The recipient's public key * The sender's private key Note that requiring the sender's private key makes this different from most public key encryption functions. The unboxing function, symmetrically, requires the sender's public key. (This boxing function may be viewed as a encrypt+sign operation.) If this fits your model, then NaCl already contains everything you need. In this case, the underlying primitive is not ElGamel, but Diffie-Hellman. The two keys are combined with ECDH and the nonce (which both sides must know, but need not be secret) diversifies the long-term shared key into a per-message key. Based on timings for the x86-64 ECDH implementation, which I wrote, 4*10^6 operations should take about 880 seconds for a short message. AGL -- Adam Langley [EMAIL PROTECTED] http://www.imperialviolet.org ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk -- Claudio Orlandi PhD student, Department of Computer Science, Turing-223 Aarhus Universitet, Denmark http://www.daimi.au.dk/~orlandi ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Speed of ElGamal encryption
On Sun, Sep 21, 2008 at 8:02 AM, Claudio Orlandi <[EMAIL PROTECTED]> wrote: > Could everyone specify the size of the field and the size of the > secret keys used? > Otherwise it's quite hard to understand the performance reported. NaCl boxes use curve25519, so the field is GF(2^255-19) and all keys are 32 bytes (the 256th bit is unused). AGL -- Adam Langley [EMAIL PROTECTED] http://www.imperialviolet.org ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Speed of ElGamal encryption
Could everyone specify the size of the field and the size of the secret keys used? Otherwise it's quite hard to understand the performance reported. Regards, Claudio On Sun, Sep 21, 2008 at 4:59 PM, Adam Langley <[EMAIL PROTECTED]> wrote: > On Sun, Sep 21, 2008 at 3:23 AM, Martin Geisler <[EMAIL PROTECTED]> wrote: >> Calling a ElGamal function in NaCl would be very cool and probably a bit >> faster since you wont have to do all the tuple packing and unpacking >> that you do in the Python version. > > NaCl has support for a primitive called a 'box'. The boxing function > takes these inputs: > * The message > * An nonce > * The recipient's public key > * The sender's private key > > Note that requiring the sender's private key makes this different from > most public key encryption functions. The unboxing function, > symmetrically, requires the sender's public key. (This boxing function > may be viewed as a encrypt+sign operation.) > > If this fits your model, then NaCl already contains everything you > need. In this case, the underlying primitive is not ElGamel, but > Diffie-Hellman. The two keys are combined with ECDH and the nonce > (which both sides must know, but need not be secret) diversifies the > long-term shared key into a per-message key. > > Based on timings for the x86-64 ECDH implementation, which I wrote, > 4*10^6 operations should take about 880 seconds for a short message. > > > AGL > > -- > Adam Langley [EMAIL PROTECTED] http://www.imperialviolet.org > ___ > viff-devel mailing list (http://viff.dk/) > viff-devel@viff.dk > http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk > -- Claudio Orlandi PhD student, Department of Computer Science, Turing-223 Aarhus Universitet, Denmark http://www.daimi.au.dk/~orlandi ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Speed of ElGamal encryption
On Sun, Sep 21, 2008 at 3:23 AM, Martin Geisler <[EMAIL PROTECTED]> wrote: > Calling a ElGamal function in NaCl would be very cool and probably a bit > faster since you wont have to do all the tuple packing and unpacking > that you do in the Python version. NaCl has support for a primitive called a 'box'. The boxing function takes these inputs: * The message * An nonce * The recipient's public key * The sender's private key Note that requiring the sender's private key makes this different from most public key encryption functions. The unboxing function, symmetrically, requires the sender's public key. (This boxing function may be viewed as a encrypt+sign operation.) If this fits your model, then NaCl already contains everything you need. In this case, the underlying primitive is not ElGamel, but Diffie-Hellman. The two keys are combined with ECDH and the nonce (which both sides must know, but need not be secret) diversifies the long-term shared key into a per-message key. Based on timings for the x86-64 ECDH implementation, which I wrote, 4*10^6 operations should take about 880 seconds for a short message. AGL -- Adam Langley [EMAIL PROTECTED] http://www.imperialviolet.org ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Speed of ElGamal encryption
Janus Dam Nielsen <[EMAIL PROTECTED]> writes: > Hi, > > I have made some tests of ElGamal encryption in Python (with some > nontrivial amount of help from Martin thanks) > > First test was in bare Python, here an encryption took > > time for 1 enc time for 4*10^6 enc > Python : 0,002980 sec : approx. 3 hours and 20 min > GMPY: 0,000535 sec : 35 min and 40 sec Cool, that is a speedup of 5.5! Not bad when you only had to add a couple of mpz(...) here and there. > Another possiblity I have not tested yet is to use the Dan Bernstein > implementation of encryption based on elliptic curves. I guess that we > can get some more speed from there. Calling a ElGamal function in NaCl would be very cool and probably a bit faster since you wont have to do all the tuple packing and unpacking that you do in the Python version. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/. pgpfKSkGl4c0w.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] Speed of ElGamal encryption
Hi, I have made some tests of ElGamal encryption in Python (with some nontrivial amount of help from Martin thanks) First test was in bare Python, here an encryption took time for 1 enc time for 4*10^6 enc Python : 0,002980 sec : approx. 3 hours and 20 min GMPY : 0,000535 sec : 35 min and 40 sec All the timing is made on my elderly office machine. Another possiblity I have not tested yet is to use the Dan Bernstein implementation of encryption based on elliptic curves. I guess that we can get some more speed from there. However I think that 35 min is worth waiting for and that we can get further speed up using a better implementation, and using state-of the art machines. -- Janus ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
