I was looking for a modular exponentiation function (for RSA computation) but I could not find one.
Did I miss it? I could do an exponentiation then a modulo but that would be slow, I guess.
Last edit: Yahyaoui 2016-05-05
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
You're right no such method exists.
From https://en.wikipedia.org/wiki/Modular_exponentiation several algo can be used to implement this function. Now the question is how fast do you need this function to be implemented?
The fastest way to implement it is using a high level code in C++. You can drop few C++ lines of code yourself I guess.
Of course, a better solution for speed is to implement it using internal bigz routines. I confess I've no idea of speed difference between the two solutions. It depends on how often you use it in your own code.
I'll try to implement Right-to-left binary method in the next couple of days. On your side, can you experiment the same algo using CBignum C++ wrapper?
BTW, I'm curious to know how you currently use bigz? Directly in C/C++ or as base implementation for another language as I do for my lisp (OpenLisp)?
C.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I've made 1.6.1 that contains BzModExp and modExp C++ wrapper method.
It uses Right-to-left binary method.
Using the sample from Wikipedia it looks to work and valgrind reports no error.
Can you please test and give me feedback?
C.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
BTW, I'm curious to know how you currently use bigz?
I was not using it at that time but it would be directly in a C program (a test
program for RSA PKCS#1 signature generation and verification).
Can you please test and give me feedback?
I downloaded 1.6.1 and tested your function. It works, the modular exponentiation gives me the same results as OpenSSL RSA_private_encrypt (I am not using the OpenSSL
BN functions).
For the moment, I am just trying to make signature work, using different
libraries and my own code, and I may push my tests further.
I hesitated to use also a BigZ for exponent, the rationale for BzUInt is: BzPow also uses a BzUInt which makes BzModExp consitent with this API. Even if BzUInt is a uint32_t this allows quite huge numbers It makes code faster as I have only to deal with native integers. It's not too complicated to make a wrapper (provided that exponent is <= BzUInt), as with CBignum.h
a function to get the length in bits of a big number, I think you missed BzLength()
a function to create a BigZ from a buffer (unsigned char and a given length, not just from a zero terminated string), Yes I can do that
Christian
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Here is the private exponent of a 2048 bits RSA key as a hexdecimal
privateExponent:
0e:2b:5d:d3:a8:f4:7a:a5:83:9f:3c:02:dd:f7:4d:
c3:51:d9:f5:2d:63:d4:d9:18:9d:dd:31:12:f8:b3:
31:59:12:cf:e9:53:b6:20:19:5a:5a:2d:d2:2f:44:
de:da:e3:82:00:a0:29:58:bf:e1:48:cc:fa:29:22:
29:19:03:35:60:d2:a2:e0:0c:26:5e:28:61:44:8e:
bb:b2:62:7d:40:70:be:b9:b5:65:25:ef:91:23:79:
c8:04:dd:fa:2f:57:68:97:3e:51:ce:3e:45:d5:e2:
47:1d:1a:b9:55:1e:55:7a:26:2c:79:91:31:8c:e7:
40:3c:c7:d4:4d:19:da:15:94:96:f8:f7:3b:f8:3d:
7f:14:64:d6:51:bf:06:d7:d9:28:eb:7b:1b:28:0f:
47:13:45:29:5f:1b:4c:fe:f0:2b:0e:bf:c2:02:48:
6a:80:51:74:db:c3:7a:04:33:68:9d:74:3a:e5:9f:
c4:1a:e7:b1:57:84:70:e2:25:99:4b:29:bb:be:94:
bc:b4:5b:8b:57:ea:e5:84:56:9d:e4:be:80:73:48:
49:fb:4e:ec:da:05:cb:b5:10:f9:65:08:ca:23:27:
83:bd:8e:70:e6:81:fe:a5:d8:d7:3f:41:68:7a:da:
05:ce:fc:e4:e9:a7:a6:d3:37:b7:f4:ef:31:4e:60:
a1
You can try it :
$ openssl genrsa 2048 > key-test.pem
$ openssl rsa -in ketest.pem -text
Sorry I'm totally new to RSA but there is something I still don't understand.
Using BzModExp(base, exponent, modulus) you can compute quite HUGE number using only BzUInt exponent.
In your last example, are you saying that privateExponent is really the exponent to apply to modExp? If true, I better understand why this function is important.
Tell me and I'll be glad to change the code with BzUInt
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
An RSA key is a pair, private and public key. Both includes the same modulus, a big integer that is the product of two secret prime numbers (Factoring such a big integer is hard so it is ok to reveal the modulus to the public).
A private key is essentially a couple (modulus 'n', private exponent 'd') and a public key is a couple (modulus 'n', public exponent 'e'). The private exponent (which must stay secret) and the public exponent are chosen according to requirements described here https://tools.ietf.org/html/rfc3447#section-3
To encrypt a message, one must first turn the message into a (big) number, then apply the operation
m^e mod n
where m is the integer representing the message, e the public exponent and n the modulus. It is defined here https://tools.ietf.org/html/rfc3447#section-5.1 Then, the encrypted message can be converted from a (big) integer to any representation (binary, base64 etc) typically to include it in a document, mail etc.
To decrypt a message, once the encrypted message has been converted back to an integer, one must apply the operation
m = c^d mod n
where c is the encrypted message, d the private exponent and n is (the same) modulus
To generate a signature for a message, one must encode the message, then convert it into an integer, then, apply the decryption operation (using the private key). Then, the message is sent with its signature to anyone who has the public key corresponding to the private key.
To verify a signature, one must first convert the signature into an integer, apply the encryption operation (using the public) key and decode the result while comparing it to the message supposedly signed.
Signature is described here https://tools.ietf.org/html/rfc3447#section-8
Usually, the public exponent is chosen as a small valid integer (often 3 or 65537), that’s why I have been able to test BzModExp with a BzUInt exponent (so only for encryption/signature verification).
But the private exponent is recommended to have almost the same size as the modulus. Hence, a common 2048 bits RSA key has a big integer as a private exponent.
French authorities recommend at least 2048 bits for an RSA key and a private exponent that has the same size (see 2.2.1.1 Factorisation in http://www.ssi.gouv.fr/uploads/2014/11/RGS_v-2-0_B1.pdf).
US authorities recommend at least 1024 bits and 2048 bits in some cases for an RSA key and a private key which length is at least 2^1024 (for a 2048 bits key) according to “B.3.1 Criteria for IFC Key Pairs” page 53 of http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
Last edit: Yahyaoui 2016-05-18
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Many thanks for your short and long replies.
I'll study more in depth. The last two days I spent some time with BzModExp and I think code from svn (not yet as tar.gz) better meets your need. I also handle more corner cases as well as negative modulus.
Can you please test latest commited version and give me your feedback? If all is ok, I'll make an official 1.6.2 version.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Sorry for the long delay. I was able to test version 1.6.2 and to successfully cross check results with OpenSSL BigNumber implementation. I used randomly generated numbers, with a base, exponent and modulus up to 4096 bits.
The speed of execution on my tests is between that of OpenSSL BN and another library BigDigits http://www.di-mgt.com.au/bigdigits.html
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Here is a comparison on different integer sizes, first column in bytes (base, modulus and exponent having the same size),
Second column is your library average time (after 100 bigints generation) divided by OpenSSL's BN average time. Third column is the same but for BigDigits.
And the raw average times (in seconds) for a similar run (same integers size for each block as before)
OpenSSL BN average time: 0.00011
BigZ average time: 0.00343
--
OpenSSL BN average time: 0.00060
BigZ average time: 0.01974
--
OpenSSL BN average time: 0.00420
BigZ average time: 0.13435
--
OpenSSL BN average time: 0.03205
BigZ average time: 0.99941
--
OpenSSL BN average time: 0.00000
BigZ average time: 0.00001
--
OpenSSL BN average time: 0.00001
BigZ average time: 0.00005
--
OpenSSL BN average time: 0.00011
BigZ average time: 0.00336
--
OpenSSL BN average time: 0.00061
BigZ average time: 0.01968
--
OpenSSL BN average time: 0.00423
BigZ average time: 0.13524
--
OpenSSL BN average time: 0.03222
BigZ average time: 0.99825
Intel(R) Core(TM) i5-2520M CPU @ 2.50GHz
Debian x86_64 GNU/Linux
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Many thanks for your performance study. It leaves room for optimizations. The goal of this 'old' lib is to be highly portable and accurate. Efficiency, which is of course interesting to have, comes only after.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Hello,
I was looking for a modular exponentiation function (for RSA computation) but I could not find one.
Did I miss it? I could do an exponentiation then a modulo but that would be slow, I guess.
Last edit: Yahyaoui 2016-05-05
You're right no such method exists.
From https://en.wikipedia.org/wiki/Modular_exponentiation several algo can be used to implement this function. Now the question is how fast do you need this function to be implemented?
The fastest way to implement it is using a high level code in C++. You can drop few C++ lines of code yourself I guess.
Of course, a better solution for speed is to implement it using internal bigz routines. I confess I've no idea of speed difference between the two solutions. It depends on how often you use it in your own code.
I'll try to implement Right-to-left binary method in the next couple of days. On your side, can you experiment the same algo using CBignum C++ wrapper?
BTW, I'm curious to know how you currently use bigz? Directly in C/C++ or as base implementation for another language as I do for my lisp (OpenLisp)?
C.
I've made 1.6.1 that contains BzModExp and modExp C++ wrapper method.
It uses Right-to-left binary method.
Using the sample from Wikipedia it looks to work and valgrind reports no error.
Can you please test and give me feedback?
C.
Thanks for your quick response.
I was not using it at that time but it would be directly in a C program (a test
program for RSA PKCS#1 signature generation and verification).
I downloaded 1.6.1 and tested your function. It works, the modular exponentiation gives me the same results as OpenSSL RSA_private_encrypt (I am not using the OpenSSL
BN functions).
For the moment, I am just trying to make signature work, using different
libraries and my own code, and I may push my tests further.
BTW, for RSA computation use case, it would be practical to have
- an exponent that is also a BigZ (instead of a BzUInt), see the "private exponent" that is usually a big integer https://tools.ietf.org/html/rfc3447#section-2
- a function to create a BigZ from a buffer (unsigned char and a given
length, not just from a zero terminated string), similar to
https://tools.ietf.org/html/rfc3447#section-4.2
- a function to get the length in bits of a big number, for use in step
one of 8.1.1 https://tools.ietf.org/html/rfc3447#section-8.1
Last edit: Yahyaoui 2016-05-05
Hi, glad to know it works.
I hesitated to use also a BigZ for exponent, the rationale for BzUInt is:
BzPow also uses a BzUInt which makes BzModExp consitent with this API.
Even if BzUInt is a uint32_t this allows quite huge numbers
It makes code faster as I have only to deal with native integers.
It's not too complicated to make a wrapper (provided that exponent is <= BzUInt), as with CBignum.h
Christian
Hi,
Noted.
Not large enough for an RSA key private exponent, which has almost the same size as the modulus, e.g. 256 bytes for a 2048 bits RSA key.
Thank you.
Wail
On SVN (not yet in archive) BzFromStringLen has been added.
I'm not sure to understand you. Do you mean that:
n4294967295 // 32bit
or
n18446744073709551615 // 64bit
Are not enough?
This corresponds to BzPow(n, ~0) or BzModExp(n, ~0, m)
For n=2, it will take days to print the former, it 4Gb of memory to store this number.
Hi,
Here is the private exponent of a 2048 bits RSA key as a hexdecimal
privateExponent:
0e:2b:5d:d3:a8:f4:7a:a5:83:9f:3c:02:dd:f7:4d:
c3:51:d9:f5:2d:63:d4:d9:18:9d:dd:31:12:f8:b3:
31:59:12:cf:e9:53:b6:20:19:5a:5a:2d:d2:2f:44:
de:da:e3:82:00:a0:29:58:bf:e1:48:cc:fa:29:22:
29:19:03:35:60:d2:a2:e0:0c:26:5e:28:61:44:8e:
bb:b2:62:7d:40:70:be:b9:b5:65:25:ef:91:23:79:
c8:04:dd:fa:2f:57:68:97:3e:51:ce:3e:45:d5:e2:
47:1d:1a:b9:55:1e:55:7a:26:2c:79:91:31:8c:e7:
40:3c:c7:d4:4d:19:da:15:94:96:f8:f7:3b:f8:3d:
7f:14:64:d6:51:bf:06:d7:d9:28:eb:7b:1b:28:0f:
47:13:45:29:5f:1b:4c:fe:f0:2b:0e:bf:c2:02:48:
6a:80:51:74:db:c3:7a:04:33:68:9d:74:3a:e5:9f:
c4:1a:e7:b1:57:84:70:e2:25:99:4b:29:bb:be:94:
bc:b4:5b:8b:57:ea:e5:84:56:9d:e4:be:80:73:48:
49:fb:4e:ec:da:05:cb:b5:10:f9:65:08:ca:23:27:
83:bd:8e:70:e6:81:fe:a5:d8:d7:3f:41:68:7a:da:
05:ce:fc:e4:e9:a7:a6:d3:37:b7:f4:ef:31:4e:60:
a1
You can try it :
$ openssl genrsa 2048 > key-test.pem
$ openssl rsa -in ketest.pem -text
2048 bits is a minimum in many recommandations https://certsimple.com/blog/measuring-ssl-rsa-keys
Fixed in revision 172, thanks for your suggestion
Sorry I'm totally new to RSA but there is something I still don't understand.
Using BzModExp(base, exponent, modulus) you can compute quite HUGE number using only BzUInt exponent.
CBignum three(3);
std::cout << "==> " << three.modExp(10001, one << 30000) << std::endl;
==> 48940505560278776229097701875434641504363973607476139818044609785754771924429572362440466892543544929019756135669707386300216748997531611557144437436104337504359577065498673173076270886530670059678978935036042532344826589971119823276339277253706612025602162823440859811676850618586049514416779522179728561385005501989356780734715320356767551880905578755637419601255241417618922801190730230456560742986752063730563371822586686654040013236885507412019178280997342607622319527964599527461828551055898166783475890359320758998334357082551025970565113296587357418810370165148795310596972523902584520988326834346195045490231034684837428013067470423060020387689114494376571996020373032401942289616783094264890354692217021507819133371755342371444757004911531103372155059817180698775583413342707678935695967246885032426554528676250398683627281503828029404592109112577517473681627223577493115901409073187363109780387926369020710333203064001417217804724909502938308960671553188442761213781331843834586707233379133613419188813292461310090630996550906595454520369854068237925165939637795543288762636641889603828791584508109640611475315782875643058872510364845210907467037186324655527428500475355512168241394285989135979276304252285220322978379350016403666209638764845975807453483607816665969628240932273105156006488249494763955805804931075287341110312923940829070572051047617598235115418196627180608305020206053942854796840941992991174517537411022745046634213031238756002007471549698870458645150912157733369545537230791504435157710847934270235470755949215255918494810013412370956182857031974315325138152912596562680788455061051461567265592044598977210578864313925042881333157413403428977959088515757878656628936146267165548615564600233901212599652574640355205362785282182567151030432261409486597255632724468311240224148475214687742409355406097340123883176272900037075090229881608871236232610155554772018578041183637720339716135265396381850478247739195058013755654853000357188473190108919138265467307454004517715611754627620908986980120857870537282140721406352343605304490201950203720659520146870201067928860964841381271470182687384955800192620800387891597764772739966181718020049547759910193622727145882326011548190113351096126246345215259243096640964803558931518998609114793909230518334372905017918903820113042261744182840555381093919343298120277865638232868493007580401664549090603130842837839811008781392063926409866693578085081963688535738858820962639289369455281667878490883489424367064836528848761865197300821075640056322442706677950558456196005657339217747253098850705986590749813205657299360276864677603097505707529468338399184492370383659452031714347207551334809619725991583552257693928985954194957702446673939837657793373053909758433765762887391246845839976396117937232477409548932549499757852534859494180688438504893424535195411354683961578541626932522234529322408106879123180509825415451181796315190512266339420322322094113682312953145264818674272581257875547841819453082201988844483333854333484310594498466741018402349503664153531466281855311585209974208214393087702276461395716021912647980486855322797664256230971020617613528033651126422547551193075437301641685317957094541891058524077546894501649675497006960805243823788881949365592138831805771204740627179965501533787410501451485785724410066081583972244677139008866889111270936100567202167082647484784548427226220742959871134782513262391834353513032294340937257269298972260747764307320721833117253549203269846605300061245332313919202223557495202898824258043956873306702026218447732263452371438752461938814842011209684566439011935152243996727453939714252723214558888025496848304582102276964608526136005365181538515341372367889137294830697894662555189443888479707415990206526562878893610390338213131692897170084875546092394893204357563818180970257274940133416035472786520322349770370504291289342678002310950793731000098277084484543465146529484142496203536441709275373253271922988021726054766201881830724564247805386560501164103983407100969241248506443316631635340669688692088275644930642428464995722047722188178436054935722541460396755315929493855624055067775137126979463008439200154138990262755111424113485909798963343183387773789146849680170510159621773963805809668678422687529403047295523078883365073644819098357098855489604823852619840763663990852771081175959486877448060037825800292029645956771945603634817672890069373586067349617905477267908832970206015464897312714180867628171963401948874773659138598157984041080565783868143710643189204657747194301259485552530449887231311001394515194892572731350589506536917432085643901826065781347529381344371511190692490726585679103904687145351343804543963144041417277037500416679480970792988135049067424488954895610984557546606436244599678986656390892987651724494315619656600003
In your last example, are you saying that privateExponent is really the exponent to apply to modExp? If true, I better understand why this function is important.
Tell me and I'll be glad to change the code with BzUInt
Hi,
Short answer, yes, the privateExponent is really the exponent to apply to modExp :) That’s why I have been insisting so much.
Long answer.
In RSA, PKCS #1 defines public key encryption and signatures. The basic operation is for encryption/decryption is modular exponentiation. The same operation is used for signature generation and verification.
PKCS #1 has an RFC https://tools.ietf.org/html/rfc3447 based on a specification that has been (slightly) updated http://www.emc.com/emc-plus/rsa-labs/standards-initiatives/pkcs-rsa-cryptography-standard.htm
An RSA key is a pair, private and public key. Both includes the same modulus, a big integer that is the product of two secret prime numbers (Factoring such a big integer is hard so it is ok to reveal the modulus to the public).
A private key is essentially a couple (modulus 'n', private exponent 'd') and a public key is a couple (modulus 'n', public exponent 'e'). The private exponent (which must stay secret) and the public exponent are chosen according to requirements described here https://tools.ietf.org/html/rfc3447#section-3
To encrypt a message, one must first turn the message into a (big) number, then apply the operation
m^e mod n
where m is the integer representing the message, e the public exponent and n the modulus. It is defined here https://tools.ietf.org/html/rfc3447#section-5.1 Then, the encrypted message can be converted from a (big) integer to any representation (binary, base64 etc) typically to include it in a document, mail etc.
To decrypt a message, once the encrypted message has been converted back to an integer, one must apply the operation
m = c^d mod n
where c is the encrypted message, d the private exponent and n is (the same) modulus
To generate a signature for a message, one must encode the message, then convert it into an integer, then, apply the decryption operation (using the private key). Then, the message is sent with its signature to anyone who has the public key corresponding to the private key.
To verify a signature, one must first convert the signature into an integer, apply the encryption operation (using the public) key and decode the result while comparing it to the message supposedly signed.
Signature is described here https://tools.ietf.org/html/rfc3447#section-8
Usually, the public exponent is chosen as a small valid integer (often 3 or 65537), that’s why I have been able to test BzModExp with a BzUInt exponent (so only for encryption/signature verification).
But the private exponent is recommended to have almost the same size as the modulus. Hence, a common 2048 bits RSA key has a big integer as a private exponent.
French authorities recommend at least 2048 bits for an RSA key and a private exponent that has the same size (see 2.2.1.1 Factorisation in http://www.ssi.gouv.fr/uploads/2014/11/RGS_v-2-0_B1.pdf).
US authorities recommend at least 1024 bits and 2048 bits in some cases for an RSA key and a private key which length is at least 2^1024 (for a 2048 bits key) according to “B.3.1 Criteria for IFC Key Pairs” page 53 of http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
Last edit: Yahyaoui 2016-05-18
Many thanks for your short and long replies.
I'll study more in depth. The last two days I spent some time with BzModExp and I think code from svn (not yet as tar.gz) better meets your need. I also handle more corner cases as well as negative modulus.
Can you please test latest commited version and give me your feedback? If all is ok, I'll make an official 1.6.2 version.
Hi,
Sorry for the long delay. I was able to test version 1.6.2 and to successfully cross check results with OpenSSL BigNumber implementation. I used randomly generated numbers, with a base, exponent and modulus up to 4096 bits.
The speed of execution on my tests is between that of OpenSSL BN and another library BigDigits http://www.di-mgt.com.au/bigdigits.html
Many thanks for your feedback. Have you a raw estimate of speed comparision with other libraries you tested?
Here is a comparison on different integer sizes, first column in bytes (base, modulus and exponent having the same size),
Second column is your library average time (after 100 bigints generation) divided by OpenSSL's BN average time. Third column is the same but for BigDigits.
64;32.076281;96.726730
128;32.582921;117.286274
256;31.248344;120.533497
512;31.051856;122.162815
1;2.820433;0.993808
5;4.133791;2.746141
64;30.169319;88.385303
128;32.494430;118.780947
256;31.910014;119.603529
512;31.127676;122.216675
And the raw average times (in seconds) for a similar run (same integers size for each block as before)
Intel(R) Core(TM) i5-2520M CPU @ 2.50GHz
Debian x86_64 GNU/Linux
Many thanks for your performance study. It leaves room for optimizations. The goal of this 'old' lib is to be highly portable and accurate. Efficiency, which is of course interesting to have, comes only after.