Quote from: viljy on February 15, 2022, 01:15:39 PM

Quote from: indaxis on December 30, 2021, 11:57:18 AM

Однако любой софт это делает также быстро как и для вычисления десятки. Еще я встречал, что количество сложений не может быть более 256 (или 512 раз)
А значит всего скорее вычисление идет как то по бинарному моду НО КАК?

Кто нибудь может объяснить какое именно количество раз складываются точки и как это зависит от приват кея?

Спасибо!

Довольно один раз вычислить все точки от одного удвоения G до 255 удвоений и затем лишь складывать эти готовые точки в зависимости от приватника. А не вычислять все полностью каждый раз. Например для простоты маленькое число приватник: 100000000000001000000100000000000000001 здесь надо сложить 4 уже вычисленные точки, G+17G+24G+38G т.е. 3 сложения. Удвоений делать не нужно, если все уже посчитано давно. Поэтому быстро.

При использовании N = 2 в качестве основания степени максимальное количество слагаемых - 255 (не 256 !).
Если использовать N больше двойки, это количество будет уменьшаться. Например, для 3 - 162, для 16 - 64, для 1024 - 26,
для 1 048 576 = 2^20 - 13. В последнем случае база публичных ключей содержит 12 648 435 элементов и в памяти компьютера занимает 3 750 GB.
Для современного компьютера это не проблематично (в моём натыкано 8 модулей по 16 GB каждый).

Ради интереса "склепал" программку на Pyton-е. Сравнение по скорости стандартной библиотеки и "склёпанной" не в пользу последней. Sad

Использование словаря / разложение по степеням - неоптимальные варианты?
Хотя при больших N и относительно небольших числах в качестве ключей результат противоположный.

Программка (без защиты от кривых рук):

import math
import datetime
import binascii, ecdsa

# --------------------------- Разложение числа по степеням другого числа ---------------------------

def pow_num(a, b):
R = []
M = int(round((math.log(a) / math.log(b)), 0))
if b**M > a: M = M - 1
for i in range(M + 1):
k = M - i
p = a // (b ** k)
if p * b ** k > a:
R.append(0)
else:
R.append(p)
a = a - p * b ** k
R.reverse()
return R

# ----------------------------------- Сложение публичных ключей ------------------------------------

def EC_Add(P, Q):
if P == '0': return Q
if Q == '0': return P
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
px = int(P[2:66], 16)
py = int(P[66:], 16)
qx = int(Q[2:66], 16)
qy = int(Q[66:], 16)
if (px == qx) and (py == qy):
dydx = (3 * px**2) * pow(2 * py, p - 2, p)
else:
dydx = (qy - py) * pow(qx - px, p - 2, p)
x = (dydx**2 - px - qx) % p
y = (dydx * (px - x) - py) % p
return '04' + hex(x)[2:].zfill(64) + hex(y)[2:].zfill(64)

# ---------------------------- Публичный ключ из приватного (библиотека) ---------------------------

def U_pub(x):
hexPrv = hex(x)[2:].zfill(64)
sk = ecdsa.SigningKey.from_string(binascii.unhexlify(hexPrv.encode()), curve=ecdsa.SECP256k1)
vk = sk.get_verifying_key()
return '04' + binascii.hexlify(vk.to_string()).decode()

# --------------------------------------------------------------------------------------------------

# p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
Max = 115792089237316195423570985008687907852837564279074904382605163141518161494336
# P1 = '0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c 4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8'

N = int(input('Введите основание для разложения по степеням : '))

Pow = pow_num(Max, N)

N_p = len(Pow) # количество степеней (0 включительно)

D_N = dict()

for i in range(N_p - 1):
for k in range(N - 1):
D_N[str(k + 1).zfill(len(str(N))) + str(i).zfill(len(str(N_p)))] = U_pub((k + 1)*N**i)

N1 = Pow[-1]

for k in range(N1):
D_N[str(k + 1).zfill(len(str(N))) + str(N_p - 1).zfill(len(str(N_p)))] = U_pub((k + 1)*N**(N_p - 1))

print('Размер базы :', len(D_N))
print('Макс. к-во слагаемых :', N_p)

PK_0 = int(input('Введите приватный ключ: ("0" - завершение программы) '))
if PK_0 > Max: PK_0 = int(str(PK_0)[:77])

while PK_0 != 0:

MM = int(input('Введите число итераций : '))

PK = PK_0

date_1 = datetime.datetime.today()

for k in range(MM):
PK = PK_0 + k
Pow_key = pow_num(PK, N)
P = '0'
for m in range(len(Pow_key)):
if Pow_key[m] != 0:
Q = D_N[str(Pow_key[m]).zfill(len(str(N))) + str(m).zfill(len(str(N_p)))]
P = EC_Add(P, Q)

date_2 = datetime.datetime.today()
print('продолжительность :', date_2 - date_1)

print('Key =', PK, '; P =', P)

PK = PK_0

date_1 = datetime.datetime.today()

for k in range(MM):
PK = PK_0 + k
P = U_pub(PK)

date_2 = datetime.datetime.today()
print('продолжительность :', date_2 - date_1)

print('Key =', PK, '; P =', P)

PK_0 = int(input('Введите приватный ключ: ("0" - завершение программы) '))
if PK_0 > Max: PK_0 = int(str(PK_0)[:77])

P.S.
Претензии по качеству софта не принимаются - я не программист.