0

As I understand it, OpenSSL uses Miller-Rabin to probabilistically generate large numbers which are highly likely to be prime from which to build its keys.

I also understand that the software uses enough rounds to render the chances of using an accidentally composite number to be astronomically small.

But I'm being strict and paranoid. I want provably prime keys (e.g. by Maurer's algorithm or some other). Can I make OpenSSL generate such keys? Or, can I generate OpenSSL certificates using some other software which satisfies this condition?

  • 1
    Note if you implement this provable algorithm on an electronic computer there is still a risk of cosmic ray hits causing a false positive. Plus a risk of unpublicized (and possibly unintentional but possibly intentional) bugs in the CPU causing a wrong and even perversely wrong result; you should re-prove with multiple machines of different ISAs produced in different fab plants. Since the OEMs and chipmakers keep their supply chains secret, you probably have to buy your own fab plant and do your own CPU design. Enjoy. – dave_thompson_085 Oct 12 '16 at 2:13
1

I don't think openssl has code to generate RSA keys using the algorithm you want. But you can use any software to generate the values that must be encoded in the private key, and then encode them in the right way so that openssl can then use the key for anything (generate CSR, create self signed certificates, be a TLS server, be a TLs client that uses client certificates, etc.).

The format of the key that you must provide is specified in PKCS#1 [1] and includes: n, e, d, p, q, d mod (p-1), d mod (q-1) and (inverse of q) mod p.

Observe what openssl produces when it generates a private key:

openssl genpkey -algorithm RSA -out private_key.pem -pkeyopt rsa_keygen_bits:2048

This is what's inside:

openssl rsa -in private_key.pem -text -noout

This is how it is encoded:

openssl asn1parse -inform pem -in private_key.pem

 0:d=0  hl=4 l=1212 cons: SEQUENCE
 4:d=1  hl=2 l=   1 prim: INTEGER           :00
 7:d=1  hl=2 l=  13 cons: SEQUENCE
 9:d=2  hl=2 l=   9 prim: OBJECT            :rsaEncryption
20:d=2  hl=2 l=   0 prim: NULL
22:d=1  hl=4 l=1190 prim: OCTET STRING      [HEX DUMP]:308204A20201000282010100CEDECBB4CFA04699F0C849D7FFF9AD1AFAEB422821889A39D3B5D6C216B4D0AF6E60E12221DA77AEFC6C6FB4932764A787AD8A5388382FB34F7592F1BD829A379931AA06D79BA8A23CC2FC0B43E766AB86D5471CD2CB7C90D4953F923C716C82B8F225A26B1D6F23E123301CC5C1D66675567E2FBA2EDA31986416BC9BEAD6A9CA3995AEFB1CE62F21600509489642031EA849325FB0DA6ECEE614642141946493C58B5BE56AEE21A96EB3C0593387067BCE6C11210402A8277CD31E62B0FAF470E51AC1DF87E7AF682562FEF576139F6491E864B190AFCF25E9D18AA89390AF6EC59169AD72851A2428B7C4EEB9E59F2EB4C3E1ADF6A5BE41425922FA06C7A10203010001028201000EFF29C756D1E8AC5A3F3AD334D455CF41E77229549D018935A6D605C5FD9FAF48122FDFF8924CE0DB9DC4CF5367A4AD5C71A138830487B8B906EDFB2660E46B2968E7498DB1D41CC6C8DFDAB5367E43EB07651B5AD0B39C103D2D999D561FA6AE5FA788C9B91D887D56BEB32746F113066899C73DF90D8A50E0D8A11DB07D953A11087FF85B78255CAC52FE55F2F6646EA2521C0CA8F3B2EEFD09B7B3DBEF53A0F7CAB2B0C3AE325F014A1C4FDCB15E2CD3B8AA27A0B0FD1531473CA7CA781B9B675196AE147A17FDBAE6837E50E117D568492EE76EB0C996097A06D892DEB0249574757D8B2FE365DDF1FCC37B755CAD91C76781A7A72ADB9755B179498EFD02818100F2AED36E57E843155C2CD3CACAC84FBFD94DDF13796F2F189109C5A6AC0D345BE1B7EC4CE903618DA045B49D47F24D762566BBEFA2E84E4A5BC10024A9E8964AB60F4B4E7E63948D341BB977E257A17B69AB509123E2A671200BA31E05D39E0F5A5EFF063A11918DEBEC7FD550D0729D5EDBBD466BC0D23D77942200D95901FF02818100DA38E120A3738BB96FC20056186F0A0ED748609E05D50561D7EA2BE439094FF2439F9C03DC6E808F3AB280358D0651632C384C4AA4CE067F319B9426A8B804A3817410F914FF072FCA98024E66067FE572C8ECE5E4FE263BDECC8EDBB60060D0EFF17B1D21FA711E4F8C59D826FAB348595563DCFE41348500F45B310DECF65F0281802A71951CE956FFD48E88708A39290B799C41D850099EFE77A7763411506A06CC430FEDCE0DBABFA70B6EE585D47D763AC193D42EB72935F81F5003FC6592FE2616ED59D862967BF6AE34631DAA827505A69785C1BCAAF93D33C39545BCF323E3BF8479C9D7021798E0B83E2B4AB50A36A7CE7AAE044E76F6B5213D4934BA327502818068BB15A8D16959ECA46B4A3807BFFAE6C6819105262D6748DF141EFE883524EE53701DB368AE8BFAB1A40B8E27E1995BEC5414A15A591A9B1ED6D91278B4E05D0C7B04CE563A535BA772AEE0AB6C812340A497B579E253BD361F9C8C6BDBE09B461CF206385176CAA248ECB1A57B7A61C5A60AA87C4A1507A43EA22977D27B270281806B36867417418016B3E567A514C904E0443C0F8BBABF361230BF8021FC8BE807EB7DA4A77EA72FAB4F12C54C541C97F6368D54D60078A4347942884DBF2240017E1F554A771BD373B949A9B320D1589A617B0E16EC2A61A2C8D6F91F892A436FC553EFD98F371BFD66BB466016E63A3297271EE058025324CB7A5B27A262F099

openssl asn1parse -inform pem -in private_key.pem -strparse 22

   0:d=0  hl=4 l=1186 cons: SEQUENCE
   4:d=1  hl=2 l=   1 prim: INTEGER           :00
   7:d=1  hl=4 l= 257 prim: INTEGER           :CEDECBB4CFA04699F0C849D7FFF9AD1AFAEB422821889A39D3B5D6C216B4D0AF6E60E12221DA77AEFC6C6FB4932764A787AD8A5388382FB34F7592F1BD829A379931AA06D79BA8A23CC2FC0B43E766AB86D5471CD2CB7C90D4953F923C716C82B8F225A26B1D6F23E123301CC5C1D66675567E2FBA2EDA31986416BC9BEAD6A9CA3995AEFB1CE62F21600509489642031EA849325FB0DA6ECEE614642141946493C58B5BE56AEE21A96EB3C0593387067BCE6C11210402A8277CD31E62B0FAF470E51AC1DF87E7AF682562FEF576139F6491E864B190AFCF25E9D18AA89390AF6EC59169AD72851A2428B7C4EEB9E59F2EB4C3E1ADF6A5BE41425922FA06C7A1
 268:d=1  hl=2 l=   3 prim: INTEGER           :010001
 273:d=1  hl=4 l= 256 prim: INTEGER           :0EFF29C756D1E8AC5A3F3AD334D455CF41E77229549D018935A6D605C5FD9FAF48122FDFF8924CE0DB9DC4CF5367A4AD5C71A138830487B8B906EDFB2660E46B2968E7498DB1D41CC6C8DFDAB5367E43EB07651B5AD0B39C103D2D999D561FA6AE5FA788C9B91D887D56BEB32746F113066899C73DF90D8A50E0D8A11DB07D953A11087FF85B78255CAC52FE55F2F6646EA2521C0CA8F3B2EEFD09B7B3DBEF53A0F7CAB2B0C3AE325F014A1C4FDCB15E2CD3B8AA27A0B0FD1531473CA7CA781B9B675196AE147A17FDBAE6837E50E117D568492EE76EB0C996097A06D892DEB0249574757D8B2FE365DDF1FCC37B755CAD91C76781A7A72ADB9755B179498EFD
 533:d=1  hl=3 l= 129 prim: INTEGER           :F2AED36E57E843155C2CD3CACAC84FBFD94DDF13796F2F189109C5A6AC0D345BE1B7EC4CE903618DA045B49D47F24D762566BBEFA2E84E4A5BC10024A9E8964AB60F4B4E7E63948D341BB977E257A17B69AB509123E2A671200BA31E05D39E0F5A5EFF063A11918DEBEC7FD550D0729D5EDBBD466BC0D23D77942200D95901FF
 665:d=1  hl=3 l= 129 prim: INTEGER           :DA38E120A3738BB96FC20056186F0A0ED748609E05D50561D7EA2BE439094FF2439F9C03DC6E808F3AB280358D0651632C384C4AA4CE067F319B9426A8B804A3817410F914FF072FCA98024E66067FE572C8ECE5E4FE263BDECC8EDBB60060D0EFF17B1D21FA711E4F8C59D826FAB348595563DCFE41348500F45B310DECF65F
 797:d=1  hl=3 l= 128 prim: INTEGER           :2A71951CE956FFD48E88708A39290B799C41D850099EFE77A7763411506A06CC430FEDCE0DBABFA70B6EE585D47D763AC193D42EB72935F81F5003FC6592FE2616ED59D862967BF6AE34631DAA827505A69785C1BCAAF93D33C39545BCF323E3BF8479C9D7021798E0B83E2B4AB50A36A7CE7AAE044E76F6B5213D4934BA3275
 928:d=1  hl=3 l= 128 prim: INTEGER           :68BB15A8D16959ECA46B4A3807BFFAE6C6819105262D6748DF141EFE883524EE53701DB368AE8BFAB1A40B8E27E1995BEC5414A15A591A9B1ED6D91278B4E05D0C7B04CE563A535BA772AEE0AB6C812340A497B579E253BD361F9C8C6BDBE09B461CF206385176CAA248ECB1A57B7A61C5A60AA87C4A1507A43EA22977D27B27
1059:d=1  hl=3 l= 128 prim: INTEGER           :6B36867417418016B3E567A514C904E0443C0F8BBABF361230BF8021FC8BE807EB7DA4A77EA72FAB4F12C54C541C97F6368D54D60078A4347942884DBF2240017E1F554A771BD373B949A9B320D1589A617B0E16EC2A61A2C8D6F91F892A436FC553EFD98F371BFD66BB466016E63A3297271EE058025324CB7A5B27A262F099

1 - https://tools.ietf.org/html/rfc3447#appendix-A.1.2

  • Actually PKCS1 plus PKCS8 rfc5208, although for the unencrypted case the latter is trivial, plus in your example PEM 'armor' although OpenSSL can equally handle files without that. – dave_thompson_085 Oct 12 '16 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.