Hazmat RSA Keys
[Hazmat Home][Home]
With RSA, we have the magic of public key encryption, and where Bob can generate a key pair: a public key and a private key, and then send Alice his public key. If she wants to encrypt something for him, she encrypts it with his public key, and then the only key which can decrypt it is his private key. A truly wonderful concept, and it was Rivest, Shamir and Adleman who made it come alive with the RSA method. In RSA, we start by generating two prime numbers (\(p,q\)) and then calculate the modulus (\(N\)) of \(N=pq\). It is this modulus (\(N\)) that provides the core of the security of RSA, and it must be difficult to determine the prime numbers for a given modulus value. Our prime numbers must thus be of a size that makes it difficult to factorize, and they must be randomly generated.
|
Theory
In RSA, we start by generating two prime numbers (\(p,q\)) and then calculate the modulus (\(N\)):
\(N=pq\)
It is this modulus (\(N\)) that provides the core of the security of RSA, and it must be difficult to determine the prime numbers for a given modulus value. Our prime numbers must thus be of a size that makes it difficult to factorize, and they must be randomly generated. Next we calculate \(\textrm{PHI}\), which is:
\(\textrm{PHI}=(p-1)(q-1)\)
We then pick \(e\) so that it does not share a factor with \(\textrm{PHI}\):
\( \textrm{GCD} (e,PHI)=1 \)
and where GCD is the greatest common denominator. In practice \(e\) typically has a value of 65,537 (and which is a prime number, so is safe). The encryption key is now \((e,N)\). Bob and can then send this to Alice for her to encrypt a message for him using his public key.
Bob determine the decryption value (\(d\)) with:
\(d \times e \pmod {\textrm{PHI}} = 1\)
For this we use an inverse mod function to determine \(d\). For example, we can use:
d=libnum.invmod(e,PHI)
To encrypt a message (\(M\)), we use:
\(C=M^e \pmod N\)
and to decrypt:
\(M=C^d \pmod N\)
from cryptography.hazmat.primitives.asymmetric import rsa from cryptography.hazmat.primitives import serialization import sys size=512 M=5 if (len(sys.argv)>1): size=int(sys.argv[1]) if (len(sys.argv)>2): M=int(sys.argv[2]) try: print(f"RSA key size: {size}\nM={M}\n") private_key = rsa.generate_private_key(public_exponent=65537,key_size=size) priv= private_key.private_numbers() p=priv.p q=priv.q d=priv.d n=p*q print("=== RSA Private key ===") print (f"p={p} q={q} d={d} N={n}") print (f"\nBit length of p and q is {p.bit_length()}") print (f"Bit length of N is {n.bit_length()}") print("\n=== RSA Public key ===") pub = private_key.public_key() e=pub.public_numbers().e n=pub.public_numbers().n print (f"\nN={n} e={e}") C = pow(M,e,n) Plain = pow(C,d,n) print (f"\nMessage={M}") print (f"Cipher={C}") print (f"Decrypt={Plain}") print("\n=== Private Key PEM format ===") pem = private_key.private_bytes(encoding=serialization.Encoding.PEM,format=serialization.PrivateFormat.PKCS8,encryption_algorithm=serialization.NoEncryption()) print ("Private key: ",pem.decode()) pem = pub.public_bytes(encoding=serialization.Encoding.PEM,format=serialization.PublicFormat.SubjectPublicKeyInfo) print("\n=== Public Key PEM format ===") print ("Public key: ",pem.decode()) except Exception as e: print(e)
A sample run for a key size of 512 bits is:
RSA key size: 512 M=10 === RSA Private key === p=104246026371772984220662363493435490218409222273146797669777229768813322522619 q=87764422957761813010189435192685570137340542873489819058412535016211511303279 d=4012299361214260935294366489647345647140120634154877723686151072708135243606910493946647392830339539251447557780176267972885887483729470644416359202530845 N=9149092350158276292278866310567415597112907901625142527303130818415262498182791538711443942226407372585092947344737367458999404718783731242921308646367701 Bit length of p and q is 256 Bit length of N is 512 === RSA Public key === N=9149092350158276292278866310567415597112907901625142527303130818415262498182791538711443942226407372585092947344737367458999404718783731242921308646367701 e=65537 Message=10 Cipher=1341090462557952268105508828016189814400540752858368328867164870648424998246946391759684890965103582948669370899625446806653410687280340898343707290630948 Decrypt=10 === Private Key PEM format === Private key: -----BEGIN PRIVATE KEY----- MIIBUwIBADANBgkqhkiG9w0BAQEFAASCAT0wggE5AgEAAkEArq/U9OIi93dp/UQQ k10yiBE4PkyRmQy8Dhe2iXy7ymltfkUTqH+Ae+cAOfc/PJDem4SXKYTQARn2tPji +ilh1QIDAQABAkBMm7Xz0vxstITZ2jC+v796ZrrYr3GmwivyrjmSIA6nHE0KIhjE yypPFhiiQftumREj7Sbuwbow6nVD/WXT76YdAiEA5nko9gdu1FlxM1itSIJobNss u9feyepFaQfQd1YxT/sCIQDCCOcudvGhT2kub854Ftmgnul/oTOBVNzabyGwNGTc bwIgeLpbBJXcLowzyivXibYWMX+WLUflQmvftCcNwpV5+2UCIA8a/lRhsiHqureA wMQck0ir1mW3OPlCkAb5S9gZ3BhFAiAilqDaTqDM1peePrq+8uU4S4FTGGLrm+pU jid9D8xVDw== -----END PRIVATE KEY----- === Public Key PEM format === Public key: -----BEGIN PUBLIC KEY----- MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAK6v1PTiIvd3af1EEJNdMogROD5MkZkM vA4Xtol8u8ppbX5FE6h/gHvnADn3PzyQ3puElymE0AEZ9rT44vopYdUCAwEAAQ== -----END PUBLIC KEY-----
and for 1,024 bits:
RSA key size: 1024 M=10 === RSA Private key === p=13003430640930495304172597642692695219093534037167516608093032092212850519182647839160977228125698457891610436375397363118159371840582370322389206415181147 q=10637381060155006860147776777122471665900914267156663488726614583983743537086990892529634831264755925977644714092695203345107007038825187518695448708617191 d=117904494354807131426834296203360748299819631936572736446172091880505478039848704349034316264389797538201155993569717084550695210796650021853124869669247483067682907473621079954096703631553611962607930910348647658854624452134338978181394472782375515347279562825778262055559073271860317790625055750935989201733 N=138322446816873332479824557762376767472661318193207801737693650279660732762249870879162629737380988512272687831848961720104521991836816004908226278279245182293349780084100605452279896891248174348644032589248555757017664555964805667506265649811145442927660648320238808502769549119589585009551902963700143298077 Bit length of p and q is 512 Bit length of N is 1024 === RSA Public key === N=138322446816873332479824557762376767472661318193207801737693650279660732762249870879162629737380988512272687831848961720104521991836816004908226278279245182293349780084100605452279896891248174348644032589248555757017664555964805667506265649811145442927660648320238808502769549119589585009551902963700143298077 e=65537 Message=10 Cipher=57192169558147973487293064403561379954778412549675078140296908547697315069051671657280945055341446394881642653978001209918927542133877426926832524464341014431032036432476576928864806865068268057420203383496370343421238022895913999511816711052672386281908988312608135903574654585532478341778290199554484395851 Decrypt=10 === Private Key PEM format === Private key: -----BEGIN PRIVATE KEY----- MIICeAIBADANBgkqhkiG9w0BAQEFAASCAmIwggJeAgEAAoGBAMT6SrlBWdS8+o6Z akiFjvpj6gVOLGGetAAaWLjozgdkYwLjqxW8xVvDyayiEluDUXNzNoDblwrz7uS+ tNwXhoALlhjckTYLvLx58Fk3zQ4MPCK0siI0NakLeBJSh7WqQB5o3hY3q142PBvA hmOcQfarWA9TGXFyE1TdSuIM+RYdAgMBAAECgYEAp+bNgQHyh4MadCjTTsQBru8x 0Jnk/MUhm6DZlaxjyitItnLIJ3xEIkdOhgeUbEsQR7+ias5C/oQVUwg39A9dhhEX 6Vd5OtHzjSe9h/WHEvy59iZRyQV3wnq1RyfllGvtIum7aW8TeYV+jwAJTZz47P0x 4WHVIDlzDdg/hnlsK0UCQQD4R3Hqfq9n7BTnab5K/knQ1nAN4BzcHRWnIb1+bhvl u0xGWlevd7bebdXwNxsT1qPVBXi3cQDZXmhdpgy+FAVbAkEAyxpvf5vxt49Yzft+ 9iRyHwbALtHXMPKQIIBkNi3KUYKmP1s0mfzHRmQv2dlwEhV2ot+4yDecQwhzQ3Qr 5I+T5wJAOLRYmC4G8b1BqPjFtWsOgNv5C7I75SnfYCScmtubE4ULjqXjkPfOlE6R piNv08AZ+vUc9QiiIQMm4vyhvGfmMQJBAMeau2mWQQA9iPEm8afGOcH0SHu7Dtm0 CaFnjRUR+3wQAoLRh+iuXMn5PG3FHDcpkOaRKHDc9l2KuHzadyixUpECQQCmDcPi iwKkkM6rbZZ9FwWgufMP6AlsLbXfgXUsQLZH7nQJIKhsFc2Gwmd4wHBI/rUq2A5l mrYUQBBcwJEOqYVo -----END PRIVATE KEY----- === Public Key PEM format === Public key: -----BEGIN PUBLIC KEY----- MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDE+kq5QVnUvPqOmWpIhY76Y+oF TixhnrQAGli46M4HZGMC46sVvMVbw8msohJbg1FzczaA25cK8+7kvrTcF4aAC5YY 3JE2C7y8efBZN80ODDwitLIiNDWpC3gSUoe1qkAeaN4WN6teNjwbwIZjnEH2q1gP UxlxchNU3UriDPkWHQIDAQAB -----END PUBLIC KEY-----
Note that we normally use RSA keys of 2,048 bits and above, as the state-of-the-art in factorizing the modulus is approaching 1,024 bits.