Re: RSA Keygen problem
On Jan 21, 2:36 pm, Nelson Bolyard wrote: > Jean-Daniel wrote to mozilla.dev.security on 2009-01-20 10:42 PST: > > > Hello, I'm trying to generate a keypair using nss, but I encounter some > > issue. My key generation can take up to 30 seconds on a recent machine > > (Core 2 Duo 2.2 Ghz) (most generation take less the 10 seconds, and > > sometimes less than 5 seconds, but even 10 seconds is more than what I > > expect). > > What version of NSS? NSS 3.12 with NSPR 4.7 (the nss-3.12-with-nspr-4.7 source package). > What OS? Mac OS 10.5.6 (darwin 9.6.0) > Can you list the .o (or .obj) files built under nss/lib/freebl/* in Darwin_SINGLE_SHLIB: aeskeywrap.o alg2268.o alghmac.o arcfive.o arcfour.o camellia.o des.o desblapi.o dh.o dsa.o ec.o freebl.def freeblver.o ldvector.o libfreebl3.dylib md2.o md5.o mp_gf2m.o mpcpucache.o mpi.o mplogic.o mpmontg.o mpprime.o pqg.o prng_fips1861.o rawhash.o rijndael.o rsa.o sha512.o sha_fast.o shvfy.o sysrand.o tlsprfalg.o For instance, the compiler invocation for mpprime.c is the following one (other freebl objects are compiled using the same flags): cc -o Darwin9.6.0_OPT.OBJ/Darwin_SINGLE_SHLIB/mpprime.o -c -O2 -fPIC - Di386 -Wmost -fpascal-strings -fno-common -pipe -DDARWIN - DHAVE_STRERROR -DHAVE_BSD_FLOCK -DXP_UNIX -DSHLIB_SUFFIX=\"dylib\" - DSHLIB_PREFIX=\"lib\" -DSHLIB_VERSION=\"3\" -DSOFTOKEN_SHLIB_VERSION= \"3\" -DRIJNDAEL_INCLUDE_TABLES -UDEBUG -DNDEBUG -DUSE_UTIL_DIRECTLY - DMP_API_COMPATIBLE -I../../../../dist/Darwin9.6.0_OPT.OBJ/include - I../../../../dist/public/nss -I../../../../dist/private/nss -Impi - Iecl mpi/mpprime.c > > > Did I miss something. Is there any magic flag to improve this ? Or a > > faster RSA keygen function in nss ? > > I have an AMD Athlon 64 running at 2.2 Ghz. I did a test generating a > bunch of 2k bit RSA key pairs. I repeatedly executed the command > time certutil -d DB -G -g 2048 -f pwfile -z noisefile > > I found that average time was 2 seconds, maximum was 17 seconds, minimum was > under 1/2 second. These seem like expected/normal times to me. I'm > surprised that your system is taking much longer. > > Generating a 2k bit RSA key requires finding two 1k bit prime numbers. > At that size, prime numbers are pretty sparse and it can take a long > time, sifting through lots of numbers, to find a prime that big. There > is natural variability in that process because prime numbers are not > uniformly distributed in the number space. But still, I don't expect > your times to be a large multiple of my times, given similar CPUs and > speeds. > > Please follow up in the mozilla.dev.tech.crypto news group. I did an other simple test that call SECKEY_CreateRSAPrivateKey() in a loop and then call the OpenSSL equivalent to compare both functions. NSS does not perform as bad as I thought first, but it remain slower than what I expect on a modern machine. See the result for 20 loops: --- NSS --- average: 5714 ms min: 1240 ms, max: 15160 --- OpenSSL --- average: 1646 ms min: 385 ms, max: 4744 ___ dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
Re: RSA Keygen problem
> You are running Darwin, and freebl does not have any optimizations for > RSA on darwin. It has some assembly optimizations on most other x86 > platforms. But on Darwin, freebl is built with plain C code, and no > assembly at all. That is one reason why the code is running a lot slower. > > It's likely that your OpenSSL version has been built with some assembly > optimizations, which could explain the difference. This is the system provided OpenSSL library. I think Apple has enabled all possible optimizations. > > Even if you end up building NSS with optimizations, they use the regular > multiply instructions, which performs best on AMD chips, but not as well > on Intel CPUs. For Intel, one needs to use the SSE2 and above > instructions set, which NSS currently doesn't do - except on one > platform, Linux. I have an SSE2 chip, and I also compile an NSS lib passing the SSE2 flag to GCC, but unfortunately (as you mention), their is no optimization foe SSE2 on Darwin in the NSS sources. > > Another possible reason is if you are comparing 32-bit NSS vs 64-bit > OpenSSL binaries. Regardless of assembly optimizations. The 64-bit code > is always a lot faster, even without optimizations. Of course, but as my test exec is link on both library, so that could no be the case. Anyway by default, gcc produce 32 bits binary on OS X, and you should ask it explicitly to get a 64 bits version (and I don't ask it). > FYI, I ran the following command on Solaris x64, on a 4-year old dual > AMD Opteron 246 (2.2 GHz), with a 32-bit optimized of NSS 3.12, with > optimizations : > > time ./rsaperf -n none -k 2048 -g -i 1 > > This does one keygen, plus one RSA private key op (there is no way to > make rsaperf do 0 private key ops ...). But the time of the private key > op is about 26 ms, fixed time, and mostly noise lost in the keygen time. > > My results were between 0.91 and 5.38 seconds, with an average of 2.72 > seconds. Still slower than your openssl build, but about twice as fast > as your NSS results. > > When using a 64-bit optimized build of NSS, on the same system, the > results were way better. > > Out of 10, the RSA keygen time only varies from 0.25 to 0.84 second. The > average was 0.6 second. The lone private key op time dropped to 4.6 > milliseconds, so it's still negligible. That's what I supected. If I do not managed to find a way to generate an optimized binary, I think I'm going to workaround this issue by generating the key using OpenSSL and then, import them in my NSS db. Thank you. ___ dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
Re: RSA Keygen problem
On Jan 22, 2:48 am, Julien R Pierre - Sun Microsystems wrote: > Jean-Daniel, > > Jean-Daniel wrote: > >> Another possible reason is if you are comparing 32-bit NSS vs 64-bit > >> OpenSSL binaries. Regardless of assembly optimizations. The 64-bit code > >> is always a lot faster, even without optimizations. > > > Of course, but as my test exec is link on both library, so that could > > no be the case. > > Anyway by default, gcc produce 32 bits binary on OS X, and you should > > ask it explicitly to get a 64 bits version (and I don't ask it). > > I am not sure what kind of application you are developing, but if RSA > keygen performance is an issue, I would strongly recommend you consider > going 64-bits if it's an option. > > > That's what I supected. > > > If I do not managed to find a way to generate an optimized binary, I > > think I'm going to workaround this issue by generating the key using > > OpenSSL and then, import them in my NSS db. > > I am not sure if we have the required functions to import raw private > keys in the NSS API. We go out of our way to make it difficult and > ensure that never happens :-). Even if you can do it, it will be difficult. In fact, I do not directly use the OpenSSL generator, I'm using the CDSA keygen API and it return a PKCS1 public key and a PKCS8 private key. After that, I can decode the public key using SEC_ASN1DecodeItem with the SECKEY_RSAPublicKeyTemplate and I can use PK11_ImportDERPrivateKeyInfoAndReturnKey() to import the private key. Except if there is know bugs with this function ? > I would suggest you open an RFE in bugzilla against NSS to add freebl > optimizations on Darwin . I will have a look at that too. -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
Re: RSA Keygen problem
On Jan 22, 1:23 am, Robert Relyea wrote: > Nelson B Bolyard wrote: > > Julien R Pierre - Sun Microsystems wrote, On 2009-01-21 15:03: > > >> Even if you end up building NSS with optimizations, they use the regular > >> multiply instructions, which performs best on AMD chips, but not as well > >> on Intel CPUs. For Intel, one needs to use the SSE2 and above > >> instructions set, which NSS currently doesn't do - except on one > >> platform, Linux. > > > Is there any reason why we can't use the same optimizations on Darwin/x86 > > as we use on Linux? > > If darwin/x86 uses gas, then it's should be just a matter of setting > some defines in the freebl make file and testing. (the primary thing > that holds back using these assembler optimizations is differences in > the assembler syntax on our various platforms). > Unfortunately it doesn't use gas. I have modified the mpi_x86.s to use be able to compile it using gcc, but I have a question. The darwin mpi library is configured to use 64bits mp_digit (as ULONG_LONG_MAX is defined and long long are 64 bits), and so, the assembly file does not works. Now, if I use the MP_USE_UINT_DIGIT preprocessor flag, I can force it to defined mp_digit as 32 bits value, and it compiles fine (using the same sse2 assembly than linux). My first test shows a significant improvement: average: 1371 ms min: 389 ms, max: 2648 Is there a simple way to test if the generated values are correct ? -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
Re: RSA Keygen problem
On Jan 22, 6:46 pm, Nelson B Bolyard wrote: > > min: 389 ms, max: 2648 > > That's more like what's expected. > > > > > Is there a simple way to test if the generated values are correct ? > > Two ways come to mind. > > 1) Run NSS's cipher tests. > cd mozilla/security/nss/tests/cipher > cipher.sh > /tmp/cipher.sh.log 2>&1 > Then look at results.html in the generated directory > mozilla/tests_results/security/HOST.N > > 2) Run NSS's FIPS mode self test. > cd mozilla/security/nss/tests/fips > fips.sh > /tmp/fips.sh.log 2>&1 > Then look at results.html in the generated directory > mozilla/tests_results/security/HOST.N > > where HOST is your host name and N is an integer that increments with each > test run. Everything is green. The new asm file does not try to determine at runtime if SSE2 is present, but it does it at compile time. By default the Apple GCC version define __SSE2__, so the default is to use it on Mac. And as mention before, all supported Mac have a processor with SSE2 available, so it should be fine. Else, this is a simple copy/paste of the Linux version (without the .type lines, as the Darwin assembler does not like them). diff -Naur mozilla/security/nss/lib/freebl/Makefile mozilla/security/ nss/lib/freebl/Makefile --- mozilla/security/nss/lib/freebl/Makefile2008-03-28 01:35:26.0 +0100 +++ mozilla/security/nss/lib/freebl/Makefile2009-01-22 20:37:24.0 +0100 @@ -147,6 +147,27 @@ endif endif # Linux +ifeq ($(OS_TARGET),Darwin) +#ifeq ($(CPU_ARCH),x86_64) +#ASFILES = arcfour-amd64-gas.s mpi_amd64_gas.s +#ASFLAGS += -march=opteron -m64 -fPIC +#DEFINES += -DNSS_BEVAND_ARCFOUR -DMPI_AMD64 - DMP_ASSEMBLY_MULTIPLY +#DEFINES += -DNSS_USE_COMBA +#DEFINES += -DMP_CHAR_STORE_SLOW -DMP_IS_LITTLE_ENDIAN +# DEFINES += -DMPI_AMD64_ADD +#MPI_SRCS += mpi_amd64.c mp_comba.c +#endif +ifeq ($(CPU_ARCH),i386) +ASFILES = mpi_x86-darwin.s +DEFINES += -DMP_USE_UINT_DIGIT +DEFINES += -DMP_ASSEMBLY_MULTIPLY -DMP_ASSEMBLY_SQUARE +DEFINES += -DMP_ASSEMBLY_DIV_2DX1D +DEFINES += -DMP_CHAR_STORE_SLOW -DMP_IS_LITTLE_ENDIAN +# Should it be enabled on Darwin ? +#ECL_USE_FP = 1 +endif +endif # Darwin + ifeq ($(OS_TARGET),AIX) DEFINES += -DMP_USE_UINT_DIGIT ifndef USE_64 diff -Naur mozilla/security/nss/lib/freebl/mpi/mpi_x86-darwin.s mozilla/security/nss/lib/freebl/mpi/mpi_x86-darwin.s --- mozilla/security/nss/lib/freebl/mpi/mpi_x86-darwin.s1970-01-01 01:00:00.0 +0100 +++ mozilla/security/nss/lib/freebl/mpi/mpi_x86-darwin.s2009-01-22 22:41:36.0 +0100 @@ -0,0 +1,503 @@ +# +# * BEGIN LICENSE BLOCK * +# Version: MPL 1.1/GPL 2.0/LGPL 2.1 +# +# The contents of this file are subject to the Mozilla Public License Version +# 1.1 (the "License"); you may not use this file except in compliance with +# the License. You may obtain a copy of the License at +# http://www.mozilla.org/MPL/ +# +# Software distributed under the License is distributed on an "AS IS" basis, +# WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License +# for the specific language governing rights and limitations under the +# License. +# +# The Original Code is the Netscape security libraries. +# +# The Initial Developer of the Original Code is +# Netscape Communications Corporation. +# Portions created by the Initial Developer are Copyright (C) 2000 +# the Initial Developer. All Rights Reserved. +# +# Contributor(s): +# +# Alternatively, the contents of this file may be used under the terms of +# either the GNU General Public License Version 2 or later (the "GPL"), or +# the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), +# in which case the provisions of the GPL or the LGPL are applicable instead +# of those above. If you wish to allow use of your version of this file only +# under the terms of either the GPL or the LGPL, and not to allow others to +# use your version of this file under the terms of the MPL, indicate your +# decision by deleting the provisions above and replace them with the notice +# and other provisions required by the GPL or the LGPL. If you do not delete +# the provisions above, a recipient may use your version of this file under +# the terms of any one of the MPL, the GPL or the LGPL. +# +# * END LICENSE BLOCK * + +# $Id: mpi_x86.s,v 1.6 2006/12/11 09:45:32 gerv%gerv.net Exp $ +# + +.text + + # ebp - 36: caller's esi + # ebp - 32: caller's edi + # ebp - 28: + # ebp - 24: + # ebp - 20: + # ebp - 16: + # ebp - 12: + # ebp - 8: + # ebp - 4: + # ebp + 0: caller's ebp + # ebp + 4: return address + # ebp + 8: a argument + # ebp + 12: a_len argument + # ebp + 16: b argument + # ebp + 20: c argument + # registers: + # eax: + # ebx:carry + # ecx:a_len + # edx: + # esi:a ptr + # edi:c ptr +.private_extern_s_mpv_mul_d +_s_mpv_mul_d: +#ifndef __SSE2__ +push
Re: RSA Keygen problem
On Jan 24, 1:09 am, Julien R Pierre - Sun Microsystems wrote: > Jean-Daniel, > > Jean-Daniel wrote: > > Everything is green. > > Great ! > > > The new asm file does not try to determine at runtime if SSE2 is > > present, but it does it at compile time. > > By default the Apple GCC version define __SSE2__, so the default is to > > use it on Mac. > > And as mention before, all supported Mac have a processor with SSE2 > > available, so it should be fine. > > Is there an open-source version of the Darwin OS that may run on PCs > that aren't x86 Macs, and may lack SSE2 ? Since the death of OpenDarwin, I think the only Darwin stand alone projet is PureDarwin. But there is not yet a stable version. And in the list of required processor, all listed processor have SSE2. http://www.puredarwin.org/users/prerequisites Theoretically it may be possible to compile and install Darwin on a machine without SSE2, but in practice I'm not sure someone already tried that. > Please open a bug in bugzilla, and attach your patches there, as well as > information from this thread. OK. -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
Re: RSA Keygen problem
On Jan 24, 1:40 am, Nelson B Bolyard wrote: > Jean-Daniel wrote, On 2009-01-21 07:43: > > >> What OS? > > > Mac OS 10.5.6 (darwin 9.6.0) > > Pardon my display of ignorance regarding MacOS/X, but ... > > What exactly is darwin? > Is it just another name for MacOS X? > Is it MacOS X for x86 PCs? > Is it some alternative to Apple's standard Mac OS X? > or ?? Darwin is the name of the Unix layer of Mac OS X. This is the Open source part of OS X. http://en.wikipedia.org/wiki/Darwin_(operating_system) I don't think they're a lot of people that use it as a stand alone OS, but this name is generally used by projects that deals only with the Unix layer of Mac OS X. -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
Re: RSA Keygen problem
On Jan 24, 2:46 am, Julien R Pierre - Sun Microsystems wrote: > Jean-Daniel, > > Jean-Daniel wrote: > > Since the death of OpenDarwin, I think the only Darwin stand alone > > projet is PureDarwin. > > But there is not yet a stable version. And in the list of required > > processor, all listed processor have SSE2. > > >http://www.puredarwin.org/users/prerequisites > > > Theoretically it may be possible to compile and install Darwin on a > > machine without SSE2, but in practice I'm not sure someone already > > tried that. > > Thanks ! I am surprised they don't even attempt to support any AMD CPUs. > Indeed, all listed processors have SSE2. That said, if you want a patch with SSE2 detection support (with and without PIC), I can provide one too. -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
