Как реализовать алгоритм 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 < 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 >= 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()

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

1. Главная
2. Вопросы и ответы
3. Вопросы и ответы по математике
4. Как реализовать алго...