How to implement RSA algorithm on EC elliptic curves?

Question

Python

Hello, we set the task to implement the RSA cryptographic algorithm on elliptic curves, I found only information on ECDSA on the net, and RSA decided to try to collect something from them.

# coding: utf-8

# # Реализация системы шифрования ECDSA

import collections
import hashlib
import random

# [Standards for Efficient Cryptography](http://www.secg.org/sec2-v2.pdf) определяет требования к параметрам элииптических кривых, наиболее подходящих для целей криптографии.

EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')

curve = EllipticCurve(
    'secp256k1',
    # Field characteristic.
    p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
    # Curve coefficients.
    a=0,
    b=7,
    # Base point.
    g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
       0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),
    # Subgroup order.
    n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
    # Subgroup cofactor.
    h=1,
)

def inverse_mod(k, p):
    """Возвращает обратное k по модулю p.
    Эта функция возвращает число x удовлетворяющее условию (x * k) % p == 1.
    k не должно быть равно 0 и p должно быть простым.
    """
    if k == 0:
        raise ZeroDivisionError('деление на 0')

    if k < 0:
        # k ** -1 = p - (-k) ** -1  (mod p)
        return p - inverse_mod(-k, p)

    # Раширенный алгоритм Евклида.
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = p, k

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    gcd, x, y = old_r, old_s, old_t

    assert gcd == 1
    assert (k * x) % p == 1

    return x % p

# #### Функции для работы с элиптическими кривыми

# In[32]:

def is_on_curve(point):
    """Возвращает True если точка лежит на элиптической кривой."""
    if point is None:
        # None represents the point at infinity.
        return True

    x, y = point

    return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0


def point_neg(point):
    """Инвертирует точку по оси y -point."""
    assert is_on_curve(point)

    if point is None:
        # -0 = 0
        return None

    x, y = point
    result = (x, -y % curve.p)

    assert is_on_curve(result)

    return result


def point_add(point1, point2):
    """Возвращает результат операции сложения point1 + point2 оперируя законами операции над группами."""
    assert is_on_curve(point1)
    assert is_on_curve(point2)

    if point1 is None:
        # 0 + point2 = point2
        return point2
    if point2 is None:
        # point1 + 0 = point1
        return point1

    x1, y1 = point1
    x2, y2 = point2

    if x1 == x2 and y1 != y2:
        # point1 + (-point1) = 0
        return None

    if x1 == x2:
        # This is the case point1 == point2.
        m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
    else:
        # This is the case point1 != point2.
        m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)

    x3 = m * m - x1 - x2
    y3 = y1 + m * (x3 - x1)
    result = (x3 % curve.p,
              -y3 % curve.p)

    assert is_on_curve(result)

    return result


def scalar_mult(k, point):
    """Возвращает k * точку используя дублирование и алгоритм сложения точек."""
    assert is_on_curve(point)

    if k % curve.n == 0 or point is None:
        return None

    if k < 0:
        # k * point = -k * (-point)
        return scalar_mult(-k, point_neg(point))

    result = None
    addend = point

    while k:
        if k & 1:
            # Add.
            result = point_add(result, addend)

        # Double.
        addend = point_add(addend, addend)

        k >>= 1

    assert is_on_curve(result)

    return result


# ###  Реализация ECDSA алгоритма

# In[33]:

def make_keypair():
    """Создаем пару случайных публичных-приватных ключей."""
    private_key = random.randrange(1, curve.n)
    public_key = scalar_mult(private_key, curve.g)

    return private_key, public_key


def hash_message(message):
    """Возвращает обрезанный SHA521 хеш сообщение."""
    message_hash = hashlib.sha512(message).digest()
    e = int.from_bytes(message_hash, 'big')

    # FIPS 180 написано, что когда хеш надо обрезать, крайние праввые биты
    # должны быть отброшены.
    z = e >> (e.bit_length() - curve.n.bit_length())

    assert z.bit_length() <= curve.n.bit_length()

    return z


def sign_message(private_key, message):
    z = hash_message(message)

    r = 0
    s = 0

    while not r or not s:
        k = random.randrange(1, curve.n)
        x, y = scalar_mult(k, curve.g)

        r = x % curve.n
        s = ((z + r * private_key) * inverse_mod(k, curve.n)) % curve.n

    return (r, s)


def verify_signature(public_key, message, signature):
    z = hash_message(message)

    r, s = signature

    w = inverse_mod(s, curve.n)
    u1 = (z * w) % curve.n
    u2 = (r * w) % curve.n

    x, y = point_add(scalar_mult(u1, curve.g),
                     scalar_mult(u2, public_key))

    if (r % curve.n) == (x % curve.n):
        return 'signature matches'
    else:
        return 'invalid signature'


# In[46]:

print('Curve:', curve.name)

private, public = make_keypair()
print("Private key:", hex(private))
print("Public key: (0x{:x}, 0x{:x})".format(*public))


# In[47]:

msg = b'Hello!'
signature = sign_message(private, msg)
print('Message:', msg)
print('Signature: (0x{:x}, 0x{:x})'.format(*signature))
print('Verification:', verify_signature(public, msg, signature))


# In[48]:

msg = b'Hi there!'
print('Message:', msg)
print('Verification:', verify_signature(public, msg, signature))


# In[49]:

private, public = make_keypair()

msg = b'Hello!'
print('Message:', msg)
print("Public key: (0x{:x}, 0x{:x})".format(*public))
print('Verification:', verify_signature(public, msg, signature))


# ### ECRSA

# In[64]:

from collections import namedtuple
class PublicKey(namedtuple('PublicKey', 'n e')):
    """Публичный ключ применяется для шифрования данных."""

    __slots__ = ()

    def encrypt(self, x):
        """Зашифровать ``x``.

        Результатом является число которое может быть расшифровано приватным ключем.
        """
        return pow(x, self.e, self.n)


class PrivateKey(namedtuple('PrivateKey', 'n d')):
    """Приватный ключ который применяется для дешифрования данных."""

    __slots__ = ()

    def decrypt(self, x):
        """Дешифровать число ``x``.

        Аргумент ``x`` которое должно быть результатом шифрования ``encrypt`` используя
        публичный ключ.
        """
        return pow(x, self.d, self.n)


# In[72]:

def keys_to_RSA():
    private, public = make_keypair()
    return PublicKey(public[0],public[1]), PrivateKey(public[0], private)


# In[74]:

public_key, private_key = keys_to_RSA()


# In[77]:

print(public_key)
print(private_key)


# In[79]:

message = 10
encrypted_message = public_key.encrypt(message)
private_key.decrypt(encrypted_message)

It is clear that the return pow(x, self.d, self.n) method does not work for elliptic curves.
Found the following:
Modifications of existing
cryptosystems
• Most of the cryptosystems of modern cryptography can naturally
be "transferred" to elliptic curves
• Next, consider variants of some of the most common
cryptosystems
• In all descriptions, the parties are considered legitimate participants in the
information process
• In both cases, the elliptic curve is considered over the ring
of residues by composite modulo n
• Parameters b and a are not set by the user, but are "spontaneously added"
when the sender chooses a random number y
• For operations with curve points, you do not need to know the parameter b
• The parameter a is easily found using the extended Euclidean algorithm
for a given point (x, y) from the equation y
2 = x3 + ax
Encryption - C=e(M,y), y – case number, (M,y) – elliptic curve point, e - public key, С - ciphertext
Decryption: (M,y)=dC

Answer 1

# ECIES5.py
# 21st November 2015
# Mohit  Bhura 11CS30019
# Yash Shrivastava 13CS10054
# Souvik Sonar 15CS91S01
# Nadeem Shaik 11CS30033 

from random import randint
from math import *

#input : 3 integers - base, exp, modulus
# output : (base^exp)%modulus
def mod_pow(base, exp ,modulus):

    base%=modulus;
    result = 1;
    while ( exp > 0):
        if ( exp & 1 > 0 ):
            result = (result*base)%modulus
        base = (base*base)%modulus;
        exp/=2;
    return result;

# The jacobian function
def jacobi(a, n):
    t = 1
    while a != 0:
        while a % 2 == 0:
            a >>= 1
            if n % 8 == 3 or n % 8 == 5: t = -t
        if a < n:
            a, n = n, a
            if a % 4 == 3 and n % 4 == 3: t = -t
        a = (a - n) >> 1
        if n % 8 == 3 or n % 8 == 5: t = -t
    if n == 1: return t
    else: return 0

# calculates sqrt(a)mod(p) where p is a prime

def mod_sqrt(a, p):
    a = a % p

    if p % 8 == 3 or p % 8 == 7:
        return mod_pow(a, (p+1)/4, p)

    elif p % 8 == 5:
        x = mod_pow(a, (p+3)/8, p)
        c = (x*x) % p
        if a == c:
            return x
        return (x * mod_pow(2, (p-1)/4, p)) % p

    else:

        # find a quadratic non-residue d
        d = 2
        while jacobi(d, p) > -1:
            d += 1

        # set p-1 = 2^s * t with t odd
        t = p - 1
        s = 0
        while t % 2 == 0:
            t /= 2
            s += 1

        at = mod_pow(a, t, p)
        dt = mod_pow(d, t, p)

        m = 0
        for i in xrange(0, s):
            if mod_pow(at * pow(dt, m), pow(2, s-1-i), p) == (p-1):
                m = m + pow(2, i)

        return (pow(a, (t+1)/2) * pow(dt, m/2)) % p


#input : a point belonging to the elliptic curve
#return : a point 
def point_double(P):
    p1 = P;
    q1 = P;
    lam = 3*p1[0]*p1[0]+a;
    inv = mod_pow(2*p1[1],p-2,p);
    lam = lam*inv;

    xr = (lam*lam - p1[0] - q1[0])%p;
    yr = lam*(p1[0]-xr)-p1[1];
    yr = yr%p
    R = (xr,yr);
    return R;

#input : 2 points belonging to the elliptic curve
#return : a point 
def point_addition(P,Q):
    p1 = P;
    q1 = Q;
    if(p1 == q1):
        return point_double(P);
    lam = (q1[1]-p1[1]);
    inv = mod_pow(q1[0]-p1[0],p-2,p);
    lam = lam*inv;

    xr = lam*lam - p1[0] - q1[0];
    yr = lam*(p1[0]-xr)-p1[1];
    xr %= p;
    yr %= p;
    R = (xr,yr);
    return R;

#input : an integer, a point belonging to the elliptic curve
#return : a point 
def point_multiply(d,P):
    m = log(d,2)+1;
    d = bin(d)[2:]
    d = list(d)
    d.reverse()
    Q  = 0;
    d = map(int,d)
    for i in (d):
        if i :
            if Q == 0 :
                Q = P;
            else:
                Q = point_addition(P,Q);
        P = point_double(P);
    return Q


def point_compress(P):

    l = P;
    return [int(l[0]),int(l[1])%2];


# input : a tuple consisiting of the return of point_compress
# return : a tuple [x0/m,y0/m]
def point_decompress(x,i):

    z = (x**3 + a*x + b)%p;
    if mod_pow(z,(p-1)/2,p) == -1 :
        return "failure";
    y = mod_sqrt(z, p)
    if y%2 == i:
        return [x,y];
    else:
        return [x,p-y];


#encryption
def encrypt(x):

    encryption = [point_compress(l),(x*int(R[0]))%p];
    return encryption;

#decryption
def decrypt(encryption):

    y1 = encryption[0];
    y2 = encryption[1];
    alpha = point_decompress(y1[0],y1[1]);
    # S = E(int(alpha[0]),int(alpha[1]));
    S = (alpha[0], alpha[1]);
    # S = m*S;
    S = point_multiply(m, S);
    x0 = int(S[0])
    decryption = (y2*mod_pow(x0,p-2,p))%p;
    return decryption;


def main():

    encryption = [];
    arr = [];
    x = int(raw_input("Please enter your number : "));  
    while x > 0 :   
        arr.append(x%p);    
        encryption.append(encrypt(x%p));
        x/=p;
    print 'encryption : ', encryption;
    encryption.reverse();
    decryption = 0;
    for a,i in enumerate(encryption) :
        d = decrypt(i);
        decryption*=p;
        decryption+=d;
    print 'decryption : ',decryption;

a = 0;
b = 3;
x = 6917529027641089837;
p = 36*(x**4)+36*(x**3)+24*(x**2)+6*(x)+1;
print 'Elliptic Curve : y^2 = x^3 + ', a, 'x + ', b, ' over ';
print 'Prime : ',p;
n = 36*(x**4)+36*(x**3)+18*(x**2)+6*(x)+1;
P = (1,2);
print 'P (generator point for the elliptic curve, Public parameter) : ', P
print '<P> = n  (P is having a prime order) : ', n
m = randint(1,n);
print 'm (Private key) : ', m
k = randint(1,n);
print 'k (Secret Random Number) : ', k;
Q = point_multiply(m, P)
print 'Q ( = mP , Public parameter) : ',Q[0],Q[1];
R = point_multiply(k, Q)
print 'R (= kQ = kmP): ',R[0],R[1];
l = point_multiply(k, P)
print 'l ( = kP, used for point compression): ',l[0],l[1];
main();