The Ohm’s Law of Cybersecurity?

The Ohm’s Law of Cybersecurity?

When I studied electrical engineering the most fundamental equation related to Ohm’s Law. Without an understanding of that, there was little in the way of understanding of the field. So, in Cybersecurity, what’s the equivalent to Ohm’s Law? Well, to me, it is the principles of public-key encryption, and especially to RSA. 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 (RSA) who made it come alive with the RSA method.

And so, the work for the new semester basically starts when the old semester is finished, and I’m revising all my cryptography labs so that they mainly use a single Python library: cryptography. Within this library there are Hazmat primitives, and which are defined as possibly being insecure in a production environment, but which are great at outlining the core principles of cryptography. To import the RSA related methods we just add:

from cryptography.hazmat.primitives.asymmetric import rsa

RSA key generation

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 PHI, which is:

PHI=(p−1)(q−1)

We then pick e so that it does not share a factor with PHI:

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×e(mod 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 (mod N)

and to decrypt:

M=C^d (mod N)

The following is the code to perform the key generation of different key sizes [here]:

from cryptography.hazmat.primitives.asymmetric import rsa
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}")
except Exception as e:
    print(e)

A sample run for a key size of 512 bits is [here]:

RSA key size: 512
M=10

=== RSA Private key ===
p=98156922065387133541330105373775133732162160347788378650800189242133118641001 q=92268768045300800179051019026527767556181439485878541126365690785895565028281 d=1965532848809202662727291463593643202531496163901834625703114541303664145961421999681947343527384365816155971971376461762343587283620973110398473913393473 N=9056818274091873367584792283592532838663197925447130413042608288927669066573607678952838878382584135781885638982853356221552831639362887228279788851149281

Bit length of p and q is 256
Bit length of N is 512

=== RSA Public key ===

N=9056818274091873367584792283592532838663197925447130413042608288927669066573607678952838878382584135781885638982853356221552831639362887228279788851149281 e=65537

Message=10
Cipher=5192135235403948938894307452469338126830430311001569185379979677243171780270351548331808604330122535580475975307233918445400384034271575690501236877010777
Decrypt=10

and for 1,024 bits [here]:

RSA key size: 1024
M=10

=== RSA Private key ===
p=12992563796314908666829331295992674671253652453668131461956465202062266484146943978269050187002635862654669555363972851351483631926095064004176287756047623 q=11220014351582682519432389844974904286772005078501373816308727325845160783793245020246452882678934344106735575513567622612980510250490483151656413094343817 d=103500893530991386771620309614269568081539263925664668477583443624701848468009081582364551413534904321243497119723696383111486750706768464916342369734836515486906602445356909584870870411420277448081692124954390295964084547607421455072628406154243892438662665095618236916678134336519774483081006266528161922449 N=145776752258506855963802201353729442379485477206513622703474804857666610282347492632082388214068836356436248323382946634716157124950452061748561816537619691003865633755650453921210131837176661129285862890812275252719084589994751551138577244826116295198812101551947674789798820796748320023205489152196587596991

Bit length of p and q is 512
Bit length of N is 1024

=== RSA Public key ===

N=145776752258506855963802201353729442379485477206513622703474804857666610282347492632082388214068836356436248323382946634716157124950452061748561816537619691003865633755650453921210131837176661129285862890812275252719084589994751551138577244826116295198812101551947674789798820796748320023205489152196587596991 e=65537

Message=10
Cipher=100011804415657790890759278820204388535842706573511600511281540147246920088147637653863712103345269426719171263880789634405307663003155693542774092272611403370401857969471827738049319455791220523347549845619876320488047776585152185541617982058590071752366291380271698716779408183694049606402574321938142307123
Decrypt=10

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. Here is the running code:

Conclusions

RSA is more than 40 years old and is still going strong. While the ECC (Elliptic Curve Cryptography) has replaced it in most applications (because of its small key sizes and speed), it is still around in digital certificates and in SSH login parameters. Its greatest threat, though, is quantum computers, and which do not find the factorization of a modulus into its prime number factors a difficult problem. So, it may be goodbye to RSA, and hello to lattice methods, or isogenies, hash-based signatures, or … who knows?