Cryptography Tutorials - Herong's Tutorial Examples - Version 5.36, by Dr. Herong Yang
Performance of Prime Number Generation
This section describes the performance of prime number generation using the java.math.BigInteger class. Larger prime numbers and higher certainties requires longer generation time.
Since my program is working, I want to use it to do more tests to see the impact on the generation time when I increase the bit length of the prime number.
In the first set of tests, I fixed the certainty to 16, which gives a probability of 99.99847412109375%. Testing results of different bit lengths are summarized in the table below:
Gen. Val. Bits Cert. Probability time time Prime 16 16 99.99847412109375 1 32 64063 32 16 99.99847412109375 2 40 4229630129 64 16 99.99847412109375 3 34 18000105070399368923 128 16 99.99847412109375 19 36 323465175613040279975... 256 16 99.99847412109375 17 38 917924135915163081716... 512 16 99.99847412109375 121 62 966939251609260746850... 1024 16 99.99847412109375 343 126 160235677041735401079... 2048 16 99.99847412109375 6746 743 322355788576903895186... 3072 16 99.99847412109375 24545 2362 553613219309114846316...
As you can see, generating a prime number with 1024 or less bits is pretty fast, taking less than 1 second. But it took 6.7 seconds to generate a 2048-bit prime number, and 24.5 seconds to generate a 3072-bit prime number.
In the second set of tests, I fixed the bit length to 3072. Testing results of different certainty levels are summarized in the table below:
Gen. Val. Bits Cert. Probability time time Prime 3072 16 99.99847412109375 34824 2344 565702937028652677653... 3072 32 99.99999997671694 57465 2334 481349137981705251267... 3072 64 100.0 8763 2341 353663618372094331380... 3072 128 100.0 63645 2413 430259008059707049953... 3072 256 100.0 34017 2352 440736874159753618303... 3072 512 100.0 7039 2357 486492819926034358966... 3072 1024 100.0 120450 2337 567519578195425341872...
It is interesting to see that probability rounds up to 100% when the certainty is 64 or higher.
Also the prime number generation time is not truly proportional to the certainty. For example, it took much less time for certainty=512 than certainty=16. This could be caused by the randomness of the algorithm.
Last update: 2013.
Table of Contents
Introduction to AES (Advanced Encryption Standard)
DES Algorithm - Illustrated with Java Programs
DES Algorithm Java Implementation
DES Algorithm - Java Implementation in JDK JCE
DES Encryption Operation Modes
PHP Implementation of DES - mcrypt
Blowfish - 8-Byte Block Cipher
Secret Key Generation and Management
Cipher - Secret Key Encryption and Decryption
►RSA Implementation using java.math.BigInteger Class
Generating Prime Number with BigInteger Class
►Performance of Prime Number Generation
RSA Encryption Implementation using BigInteger Class
RsaKeyGenerator.java for RSA Key Generation
RSA Keys Generated by RsaKeyGenerator.java
RsaKeyValidator.java for RSA Key Validation
64-bit RSA Key Validated by RsaKeyValidator.java
Converting Byte Sequences to Positive Integers
Cleartext Block Size for RSA Encryption
Cleartext Message Padding and Revised Block Size
Ciphertext Block Size for RSA Encryption
RsaKeyEncryption.java for RSA Encryption Operation
RsaKeyDecryption.java for RSA Decryption Operation
Testing RsaKeyEncryption.java with a 16-bit Key
Testing RsaKeyEncryption.java with a 64-bit Key
Testing RsaKeyEncryption.java with a 3072-bit Key
Introduction of DSA (Digital Signature Algorithm)
Java Default Implementation of DSA
Private key and Public Key Pair Generation
PKCS#8/X.509 Private/Public Encoding Standards
Cipher - Public Key Encryption and Decryption
OpenSSL Introduction and Installation
OpenSSL Generating and Managing RSA Keys
OpenSSL Generating and Signing CSR
OpenSSL Validating Certificate Path
"keytool" and "keystore" from JDK
"OpenSSL" Signing CSR Generated by "keytool"
Migrating Keys from "keystore" to "OpenSSL" Key Files
Certificate X.509 Standard and DER/PEM Formats
Migrating Keys from "OpenSSL" Key Files to "keystore"
Using Certificates in IE (Internet Explorer)