500_key_generation.py

# edwards25519 parameters
a = -1
d = 37095705934669439343138083508754565189542113879843219016388785533085940283555 
p = 2**255 - 19 # prime, order of Gallois field GF(p)
Gx = 15112221349535400772501151409588531511454012693041857206046113283949847762202
Gy = 46316835694926478169428394003475163141307993866256225615783033603165251855960
l = 2**252 + 27742317777372353535851937790883648493 # order of G, = order of subgroup generated by G 

# from previous chapters ############################################################################

def le_encode_to_bytes(number):
    return int.to_bytes(number, 32, "little")
  
def le_decode_to_number(bytes):
    return int.from_bytes(bytes, "little")

def extended_homogeneous_to_affine(Q):
    (X1, Y1, Z1, T1) = Q
    Z1_inv = pow(Z1, -1, p)
    x1 = (X1 * Z1_inv) % p
    y1 = (Y1 * Z1_inv) % p
    return (x1, y1)

def affine_to_extended_homogeneous(q):
    (x1, y1) = q
    X1 = x1
    Y1 = y1
    Z1 = 1
    T1 = (x1 * y1) % p
    return (X1, Y1, Z1, T1)

def add_extended_homogeneous(Q1, Q2):
    (X1, Y1, Z1, T1) = Q1
    (X2, Y2, Z2, T2) = Q2
    A = ((Y1 - X1) * (Y2 - X2)) % p
    B = ((Y1 + X1) * (Y2 + X2)) % p
    C = (T1 * 2 * d * T2) % p
    D = (Z1 * 2 * Z2) % p
    E = (B - A) % p
    F = (D - C) % p
    G = (D + C) % p
    H = (B + A) % p
    X3 = (E * F) % p
    Y3 = (G * H) % p
    T3 = (E * H) % p
    Z3 = (F * G) % p
    return (X3, Y3, Z3, T3)

def double_extended_homogeneous(Q):
    (X1, Y1, Z1, T1) = Q
    A = (X1 * X1) % p
    B = (Y1 * Y1) % p
    C = (2 * Z1 * Z1) % p
    H = (A + B) % p
    E = (H - (X1 + Y1) * (X1 + Y1)) % p
    G = (A - B) % p
    F = (C + G) % p
    X3 = (E * F) % p
    Y3 = (G * H) % p
    T3 = (E * H) % p
    Z3 = (F * G) % p
    return (X3, Y3, Z3, T3)
  
def point_multiplication(s, P):
    Q = (0, 1, 1, 0)                  # neutral element
    bits = bin(s)[2:]                 # bit encoding of s
    bitsPadded = bits.rjust(256, '0') # the bit representation of all scalars is extended with leading 0 to 256 bit 
    for b in bitsPadded:              # for each step, the same operations are done, no matter if the bit is 0 or 1
        if b == '0':
            P = add_extended_homogeneous(Q, P)
            Q = double_extended_homogeneous(Q)
        else:
            Q = add_extended_homogeneous(Q, P)
            P = double_extended_homogeneous(P)
    return Q

def compress_point(Q):
    (x, y) = extended_homogeneous_to_affine(Q)
    x_b = le_encode_to_bytes(x)
    y_b = bytearray(le_encode_to_bytes(y)) # convert to bytearray because of bit manipulations
    y_b[31] = y_b[31] | (0x80 if (x_b[0] & 1) else 0) # copy least signficant bit from y to most significant bit to y
    return bytes(y_b) 

def clamp(data_b): # data_b in little endian order
    a_b = bytearray(data_b)
    a_b[0] &= 248  # 0.  byte: set the three least significant bits to 0
    a_b[31] &= 127 # 31. byte: set the most significant bit to 0
    a_b[31] |= 64  #           ...and the second-most significant bit to 1
    return bytes(a_b) 


# new ###############################################################################################

import hashlib

def secret_expand(secret_key_b):
    if len(secret_key_b) != 32:
        raise Exception("Bad size of secret key")
    hash_b = hashlib.sha512(secret_key_b).digest()   
    a_b = clamp(hash_b[:32])
    a = le_decode_to_number(a_b)
    return (a, hash_b[32:])

def get_public_from_secret(secret_key_b):
    (a, dummy) = secret_expand(secret_key_b)
    G_2 = (Gx, Gy)
    G_4 = affine_to_extended_homogeneous(G_2)
    return compress_point(point_multiplication(a, G_4))

#
# test 1:
# secret key:   000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f 
# public key:   03a107bff3ce10be1d70dd18e74bc09967e4d6309ba50d5f1ddc8664125531b8
#
secret_key_b = bytes.fromhex('000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f')
public_key_b = get_public_from_secret(secret_key_b)
print(public_key_b.hex())

#
# test 2:
# secret key:   4b5c7dad2f986ed376686dddd3810ada00f1ef467b3eef25c3234bd1f938b2b0 
# public key:   c0b3fdec8b02bec26530e81176030da02ba74e21f9140ac3b2158c5e1b72608c
#
secret_key_b = bytes.fromhex('4b5c7dad2f986ed376686dddd3810ada00f1ef467b3eef25c3234bd1f938b2b0')
public_key_b = get_public_from_secret(secret_key_b)
print(public_key_b.hex())

#
# test 3:
# secret key:   random 
# public key:   ...
#
import os
secret_key_b = os.urandom(32)
public_key_b = get_public_from_secret(secret_key_b)
print(public_key_b.hex())