Как реализовать алгоритм RSA на эллиптических кривых EC? Здравствуйте, поставили задачу реализовать RSA криптографический алгоритм на эллиптических кривых, в сети нашел только информацию по ECDSA, и RSA решил попробовать что то собрать из них.# 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 >= 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)
Понятно что, метод return pow(x, self.d, self.n) для эллиптических кривых не работает.
Нашел следующее:
Модификации существующих
криптосистем
• Большинство криптосистем современной криптографии естественным
образом можно "переложить" на эллиптические кривые
• Далее рассмотрим варианты некоторых наиболее распространенных
криптосистем
• Во всех описаниях стороны считаются законными участниками
информационного процесса
• В обоих случаях эллиптическая кривая рассматривается над кольцом
вычетов по составному модулю n
• Параметры b и а не задаются пользователем, а "стихийно складываются"
при выборе отправителем сообщения случайного числа у
• Для операций с точками кривой знать параметр b не нужно
• Параметр а легко находится с помощью расширенного алгоритма Евклида
по заданной точке (х, у) из уравнения y
2 = x3 + ax
Шифрование - C=e(M,y), y – случ. число, (M,y) – точка элиптич.кривой, e - открытый ключ, С - шифротекст
Дешифрование: (M,y)=dC

Предыдущий
вопрос Следующий
вопрос