Our Cybersecurity Foundation Is Crumbling?

Goodbye RSA?
Photo by Zé Ferrari Careto on Unsplash

Our Cybersecurity Foundation Is Crumbling?

Goodbye RSA or Work-in-progress or An Overstated Claim?

I am so lucky to work in an industry with so many amazing people. One of the greats is Claus P. Schnorr. He is famous for creating the Schnorr signature, and which allows signers to merge their signatures together, and then for the resultant signature to be easily checked against one public key. But, he continues to make advances in the field of cryptography, and his latest paper could blow a hole in RSA [here]:

The quote from the Cryptology ePrint Archive of the paper says “The destroyes [sic] the RSA cryptosystem”:

The strength of the RSA method is in the difficulty in factorising a modulus (N) to its prime number factors. In previous work the number field sieve or quadratic sieve methods have been found to be the best at factoring the module, but Claus has used a lattice-based factoring approach, and has found considerable speed-ups. At present, the limit of factorizing is around 250 digits (or 829 bits) [here]:

The paper says that the new method algorithm factors integers 𝑁≈2⁴⁰⁰ and 𝑁≈2⁸⁰⁰ by 4.2x10⁹ and 8.4x10¹⁰ arithmetic operations. This would mean that it is much faster then the existing best methods, and has also managed to factor a 800-bit modulus. This would move the at-risk around for RSA to more than 1K bit keys.

But, there’s strong debate about the posting of the paper on the Cryptology ePrint Archive, and especially related to its bold claims. Some say it is a work-in-progress paper, while others doubt the performance of the method.

Watch this space for updates.

Claus Schnorr

In Feb 1989, Claus Schnorr submitted a patent which was assigned to no-one. It has 11 claims, and allowed digital signatures which could be merged for multiple signers [here]:

With the Schnorr signature, we create a signature (R,s) for a hash of the message (MM). We first generate a private key (x) and then derive the public key from a point on the elliptic curve (G) to get:

P=x⋅G

Next, we select a random value (k) to get a signature value of R:

R=k⋅G

The value of s is then:

s=k−Hash(M,R)⋅x

Our signature of M is (s,R) and the public key is P.

To check the signature we calculate

P⋅Hash(M,R)+s⋅G

This becomes x⋅G⋅Hash(M,R)+(k−Hash(M,R)⋅x)⋅G

which is:

x⋅G⋅Hash(M,R)+k⋅G−Hash(M,R)⋅x⋅G=k⋅G

The value of k⋅G is equal to R, and so if the result is the same as R, the signature checks out.

A sample run with the message of “Hello” is (and where “BN” is “Big Number”) [here]:

Message:Hello
Private Key: dce71358bf6d57dffaf8ac422ea972dca65badd2ce21b585803ea3075b7de388
Public key: Buffer 03 9d e0 bd 0a e1 b2 1c 64 c7 35 12 31 1c d5 fd 35 42 f1 0a f5 02 9c c7 eb 81 e5 fb cc c8 51 18 27Signature [s]: BN: 18573f5212373b51022b00cbe12276b8099a351526b3384ccd1f02ad71761ff1Signature [r]: BN: 3d96504afbe3beec97a753c38d614ec5fa68cf8219df36d7cce891319058d5dbPublic key recover: Buffer 03 9d e0 bd 0a e1 b2 1c 64 c7 35 12 31 1c d5 fd 35 42 f1 0a f5 02 9c c7 eb 81 e5 fb cc c8 51 18 27Signature verified: true

In this case, we have 256-bit private key (dce7 … 388), and produce a 512-bit public key (03 96e … 827) — the “03” part identifies that we are using a Bitcoin public key. Thus, if we know the message — and which will be stored on the blockchain in the case of Bitcoin — and the key, we can see that we can recover the public key from the signature.

One of the great advantages of the Schnorr signature is that we can sign more than one message. Let’s say we have a transaction, and Bob, Alice and Trent must authorise it. In a Bitcoin network, this is defined as a “multisig” setup. Bob, Alice and Trent must then go away and create their own new “aggregated” signature, which will be their new public key for transactions. This is not efficient, and also reveals the Bob, Alice and Trent are working together. In an improved setup, we can define an n-from-m setup, where we can merge Bob, Alice and Trent’s keys into one public key, and then use that. The public key will then not reveal that Bob, Alice and Trent are working together, but they will create a new public key which will validate the transaction.

If we wanted just any two of them to validate it, we could ask for a 2-from-3 multisig. So if Bob, Alice and Trent are directors in a company, they could define that any two of them could validate a transaction.

The Bitcoin network could have found a way to enable this type of signature merging of public keys, and it all points to the Schnorr method. In the illustration below, we can see that the current method involves Bob, Alice and Trent getting together and creating a new public key (and an associated private). With Schnorr’s key aggregation method, we can take Bob, Alice and Trent’s public keys and then merge into a new transaction key. It will then not be possible to see the parties who created the transaction key.

Postscript

Anyway the discovery of ground-breaking things takes me back to a paper written by the mighty Hendrik W Lenstra and which used elliptic curves to factorize for prime numbers. It was the birth of ECC (Elliptic Curve Cryptography).

Hendrik W. Lenstra Jr.

Hendrik W. Lenstra Jr. become a Professor at the University of Amsterdam in 1979, and then, in 1987, he appointed to the University of California, Berkeley. One of his most famous PhD students is Daniel J. Bernstein [here], who is famous for producing standards such as Curve 25119, ChaCha20 and Poly1305. In the year he was appointed to Berkley, he outlined a method to factorize integrations using elliptic curve methods [1]:

ECM

With his method, we define the moving from a point P on an elliptic curve to 2P. For this we find the tangent to the point P and use this to find 2P. This tangent will be defined with a slope (s) and with a gradient in the form of a/b. For this we must find the modular inverse of b. If we cannot find the modular inverse of b, a factor of N is gcd(N,b), and where gcd() is the greatest common denominator.

If our curve is y²=x³+ax+b, the slope (s) will be:

s=(3x²+a)/(2y)

as defined in differentiation.

In detail, we first pick a random point P=(x0,y0) on an elliptic curve of:

y²=x³+Ax+B

We also select a random value of A and then calculate:

B=y⁰²−x⁰³−Ax (mod N)

For two points on the curve: P=(Px,Py) and Q=(Qx,Qy) , the slope of the line between them will be:

s=(Py−Qy)(Px−Qx)

With this we have s in the form of a/b(modN) .

Next we define:

R=P+Q=(Rx,−Ry)

and using:

s=(Px−Qx)(Py−Qy)(mod N)

Rx=s2−Px−Qx(mod N)

Ry=Py+s(Rx−Px)(mod N)

If Px=Qx and Py=−Qy, we define as 0 [Identity], else we calculate R=P+P=2P=(Rx,−Ry):

s=(3Px²+A)/(2Py) (mod N)

Rx=s2−2Px(modN)

Ry=P+s(Rx−Px) (mod N)

Here are some test runs:

  • p=15 (Factor: 3 and 5 Try!
  • p=6,161 (Factors: 61 x 101) Try!
  • p=32,128 (Factors: 64 x 502) Try!
  • p=53,421 (Factor: 3 x 17,807) Try!
  • p=55,440 (Factors: 2 x 2 x 2 x 2 x 3 x 3 x 5 x 7 x 11) Try!
  • p=100,001 (Factor: 3 and 17,807) Try!
  • p=999,999 (Factor: 3 x 3 x 3 x 7 x 11 x 13 x 37) Try!
  • p=455,839 (Factor: 559 and 761) Try!

Coding

An outline of the code used is [code]:

#!/usr/local/bin/python
# -*- coding: utf-8 -*-
import math
import random 
import sys#y^2=x^3+ax+b mod n prime=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271 ]
# ax+by=gcd(a,b). This function returns [gcd(a,b),x,y]. Source Wikipedia
def extended_gcd(a,b):   
	x,y,lastx,lasty=0,1,1,0
	while b!=0:
		q=a/b
		a,b=b,a%b
		x,lastx=(lastx-q*x,x)
		y,lasty=(lasty-q*y,y)
	if a<0: 
		return (-a,-lastx,-lasty)
	else:
		return (a,lastx,lasty)# pick first a point P=(u,v) with random non-zero coordinates u,v (mod N), then pick a random non-zero A (mod N), 
# then take B = u^2 - v^3 - Ax (mod N).
# http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorizationdef randomCurve(N):
	A,u,v=random.randrange(N),random.randrange(N),random.randrange(N)
        B=(v*v-u*u*u-A*u)%N
        return [(A,B,N),(u,v)]	# Given the curve y^2 = x^3 + ax + b over the field K (whose characteristic we assume to be neither 2 nor 3), and points
	# P = (xP, yP) and Q = (xQ, yQ) on the curve, assume first that xP != xQ. Let the slope of the line s = (yP - yQ)/(xP - xQ); since K 	       # is a field, s is well-defined. Then we can define R = P + Q = (xR, - yR) by
	#	s=(xP-xQ)/(yP-yQ) Mod N		
	#	xR=s^2-xP-xQ	Mod N
	#	yR=yP+s(xR-xP)	Mod N 
	# If xP = xQ, then there are two options: if yP = -yQ, including the case where yP = yQ = 0, then the sum is defined as 0[Identity]. 	       # thus, the inverse of each point on the curve is found by reflecting it across the x-axis. If yP = yQ != 0, then R = P + P = 2P = 	      # (xR, -yR) is given by
	#	s=3xP^2+a/(2yP)	Mod N	
	#	xR=s^2-2xP	Mod N
	#	yR=yP+s(xR-xP)	Mod N
	#	http://en.wikipedia.org/wiki/Elliptic_curve#The_group_law''')
	
def addPoint(E,p_1,p_2):
	if p_1=="Identity": return [p_2,1]
	if p_2=="Identity": return [p_1,1]
	a,b,n=E
	(x_1,y_1)=p_1
	(x_2,y_2)=p_2
	x_1%=n
	y_1%=n
	x_2%=n
	y_2%=n
	if x_1 != x_2 :
		d,u,v=extended_gcd(x_1-x_2,n)
		s=((y_1-y_2)*u)%n
		x_3=(s*s-x_1-x_2)%n
		y_3=(-y_1-s*(x_3-x_1))%n
	else:
		if (y_1+y_2)%n==0:return ["Identity",1]
		else:
			d,u,v=extended_gcd(2*y_1,n)
			s=((3*x_1*x_1+a)*u)%n
			x_3=(s*s-2*x_1)%n
			y_3=(-y_1-s*(x_3-x_1))%n	return [(x_3,y_3),d]	# http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
	#	Q=0 [Identity element]
	#	while m:
	#		if (m is odd) Q+=P
	#		P+=P
	#		m/=2
	#	return Q')def mulPoint(E,P,m):
	Ret="Identity"
	d=1
	while m!=0:
		if m%2!=0: Ret,d=addPoint(E,Ret,P)
		if d!=1 : return [Ret,d]  # as soon as i got anything otherthan 1 return 
		P,d=addPoint(E,P,P)
		if d!=1 : return [Ret,d]
		m>>=1
	return [Ret,d]
def ellipticFactor(N,m,times=5):
	for i in xrange(times):
		E,P=randomCurve(N);
		Q,d=mulPoint(E,P,m)
		if d!=1 : return d
	return Nfirst=True
n=455839
if (len(sys.argv)>1):
        n=int(sys.argv[1])print n,'=',for p in prime:
	while n%p==0:
		if (first==True):
			print p,
			first=False
		else:
			print 'x',p,
		n/=pm=int(math.factorial(2000))
while n!=1:
	k=ellipticFactor(n,m)
	n/=k
	if (first==True):
		print k,
		first=False
	else:
		print 'x',k,

The great public key methods of the past, may not scale well into the 2020s, especially as factorization becomes more powerful, and is actually beating Moore’s Law. If you are interested, here are other methods for factorization:

  • Difference of squares. Diffsq. This factorizes using the difference of squares method.
  • Factors of integers. Factors. Determine factors of an integer.
  • Pollard’s ρ method (Factoring integers). Pollard. The Pollard ρ method factorises integers.
  • Simplify ap(modN) Go. Simplify the a^p (modN) operation.
  • Smooth numbers. Go. Outline of smooth numbers.
  • Quadratic residue (mod p). Go. Outline of quadratic residue (mod p).
  • Quadratic residue (mod N) and where N=pq. Go. Outline of quadratic residue (mod N) with N made-up of two prime numbers.
  • Dixon. Go. Dixon Method.

References

[1] Lenstra Jr, H. W. (1987). Factoring integers with elliptic curves. Annals of mathematics, 649–673.