Здравствуйте, поставили задачу реализовать 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 < 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)
Понятно что, метод 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
