Where Would You Find Both ECC and RSA Working Well Together?

Where Would You Find Both ECC and RSA Working Well Together? Well, In Virtually Every Web Connection

Don’t you sometimes worry that we use the Internet and don’t actually understand how it works? Well, let’s dive into the wonderful world of key exchanges, and which are the core of every TLS connection that we make to the Web.

ECDH (Elliptic Curve Diffie Hellman)

For key exchange, we started with the wonderful Diffie-Hellman method. This used discrete logs, and where Alice generated a secret value (a) and passed g^a (mod p) to Bob. Bob generated b and passed g^b (mod p). They then ended up with the same shared secret of g^{ab} (mod p). But discrete logs have struggled to scale up, and we need fairly large values of p.

Thus ECC (Elliptic Curve Cryptography) came along and allowed Alice to generate a secret (a), and then a public key point of a.G. Bob did the same and generated b and b.G. They then pass their public key points and end with the same value a.b.G:

ECDH with RSA Authentication (ECDHE with RSA)

This method is known as ECDH (Elliptic Curve Diffie Hellman). But, along comes Eve, who breaks the connection between Bob and Alice and can create keys which she can break. So, how do we overcome this? Well, we can digitally sign the values exchanged so that Bob knows it was Alice that send the exchanged value and vice-versa. And, since most Web sites have RSA keys, the most natural way to sign the values is to use an RSA signature. For this, they create key pairs of (e,N) and (d,N), and then the signature of a message (M) is created using the private key (d,N):

Sig = M^d mod N

The receiver then checks the signature against the public key (e,N) with:

M = Sig ^e mod N

If this equals the value sent, the public key value exchanged has been authenticated.

Overall, ECDHE with RSA signing is by far the most popular way to create a key on TLS connection. So let’s code this.

Coding

In the following I have used the secp256k1 curve to implement this [here]:

from Crypto.Util.number import *
from Crypto import Random
import Crypto
from secp256k1 import curve,scalar_mult,inverse_mod
import sys
import hashlib

from secp256k1 import curve,scalar_mult,inverse_mod
import random

def hash(m1,m2):
    m = hashlib.sha256()
    m.update(str.encode(m1))
    m.update(str.encode(m2))
    M=int(m.hexdigest(),16)
    return M

def rsa_sign(m,dr,n):
    M=pow(m,dr,n)
    return M
        
def rsa_verification(m,er,n,h):
    M=pow(m,er,n)
    if(M==h):
        return True
    else :
        return False
    
def genRSAKey(bits):
    p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
    q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
    N=p*q
    PHI=(p-1)*(q-1)
    n=p*q
    e=65537
    d=pow(e,-1,PHI)
    return n,e,d

bits=256

alice_rsa_n, alice_rsa_e,alice_rsa_d = genRSAKey(bits)
a=random.randrange(1, curve.n)
A= scalar_mult(a, curve.g)
alice_hash=hash(str(A[0]),str(A[1]))
alice_sign=rsa_sign(alice_hash,alice_rsa_d,alice_rsa_n)

bob_rsa_n, bob_rsa_e,bob_rsa_d = genRSAKey(bits)
b=random.randrange(1, curve.n)
B = scalar_mult(b, curve.g)
bob_hash=hash(str(B[0]),str(B[1]))
bob_sign=rsa_sign(bob_hash,bob_rsa_d,bob_rsa_n)

alice_hash_receive=hash(str(B[0]),str(B[1]))
sign_result_alice=rsa_verification(bob_sign,bob_rsa_e,bob_rsa_n,alice_hash_receive)

bob_hash_receive=hash(str(A[0]),str(A[1]))
sign_result_bob=rsa_verification(alice_sign,alice_rsa_e,alice_rsa_n,bob_hash_receive)

alice_sharekey=scalar_mult(a,B)
bob_sharekey=scalar_mult(b,A)

print(f"Bob ECC b={b}")
print(f"Bob ECC b.G={B}")
print(f"\nBob RSA e={bob_rsa_e}, d={bob_rsa_d}, N={bob_rsa_n}")

print(f"\nAlice ECC a={a}")
print(f"Alice ECC a.G={A}")
print(f"\nAlice RSA e={alice_rsa_e}, d={alice_rsa_d}, N={alice_rsa_n}")

print("\n\nAlice verifies Bob's RSA signature:",sign_result_alice)
print("Bob verifies Alice's RSA signature:",sign_result_bob)

print(f"\nBob shared key: {bob_sharekey}")
print(f"Alice shared key: {alice_sharekey}")

and a sample run for 256-bit prime numbers is [here]:

Bob ECC b=40878359643961117371550739109177854635257694192773029768850396041104530693376
Bob ECC b.G=(26991471179888402854120143675524292413490670281644607075354935670920828395891, 11889508684340617275772144824150953838573569806310269158472769506377427846779)

Bob RSA e=65537, d=3951698151008058354299667201479267547666220622883272961521743075740354101397093991779016650815792352851538848957221864573372949811980239304877387383713793, N=6527926845023444669315083038422775118377765759128401181641178533380273403656586840444151258946536639259848538521661392420351885575075257080542821532347649

Alice ECC a=57952917752821937063631234203285063911794295803614370262960350932821018310719
Alice ECC a.G=(51938184597695837150822176419007969019314522509543962245147989522023786471744, 104519422524704071160727841791620153181866828930539747851450120369645420642367)

Alice RSA e=65537, d=5567538660836934197766788145812999065912906814053702443852757788214237054535281832863840109824056025415178503742672847133704645293924949139389051505670017, N=6638764623108150295095556834033450743836362830185173339084789257417787814182304080015070403398021886958143460945762708881922894642414772030742895996510721

Alice verifies Bob's RSA signature: True
Bob verifies Alice's RSA signature: True

Bob shared key: (71896057164999134714181474320234333542981320366705043302079184329835085892516, 42132477468024724802994386136558690807668821360898707440963120504403801927975)
Alice shared key: (71896057164999134714181474320234333542981320366705043302079184329835085892516, 42132477468024724802994386136558690807668821360898707440963120504403801927975)

And that’s it! ECC and RSA is perfect harmony within authenticated key exchanges and which are the heart of virtually every Web connection. Here’s the demo:

https://asecuritysite.com/rsa/rsa_ecdsa