300_point_compression.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 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
  
# new ###############################################################################################

# convention _b for bytes objects

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 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 decompress_point(y_b):
    y_b = bytearray(y_b) # convert to bytearray because of bit manipulations
    x_sign = (y_b[31] & 0x80 == 0x80)  # extract x sign bit
    y_b[31] = y_b[31] & ~0x80          # clear x sign bit
    y = le_decode_to_number(y_b)
    x = recover_x(y, x_sign)
    if x is None:
        return None
    else:
        return affine_to_extended_homogeneous((x, y))

def recover_x(y, x_sign):
    x2 = ((y * y - 1) * pow(d * y * y + 1, -1, p)) % p
    x = pow(x2, (p + 3) // 8, p)
    x_final = None
    if ((x * x - x2) % p == 0):
        x_final = x
    elif ((x * x + x2) % p == 0):
        x_final = (x * pow(2, (p - 1) // 4, p)) % p
    else:
        return None
    if (x_final == 0) and (x_sign == 1):
        return None
    if (x_final & 1) != x_sign:
        x_final = p - x_final
    return x_final

# 
# test 1: compress/uncompress base point
#

G_2 = (Gx, Gy)
G_4 = affine_to_extended_homogeneous(G_2)
Gy_compressed_b = compress_point(G_4)
print("G, compressed  : " + Gy_compressed_b.hex())
G_uncompressed_4 = decompress_point(Gy_compressed_b)
G_uncompressed_2 = extended_homogeneous_to_affine(G_uncompressed_4)
print("G, uncompressed: " + str(G_uncompressed_2))
print()

# 
# test 2 compress/uncompress various points
#

G_2 = (Gx, Gy)
G_4 = affine_to_extended_homogeneous(G_2)
res0G_4 = point_multiplication(0, G_4)
res1G_4 = point_multiplication(1, G_4)
res2G_4 = point_multiplication(2, G_4)
res3G_4 = point_multiplication(3, G_4)
res4G_4 = point_multiplication(4, G_4)
res5G_4 = point_multiplication(5, G_4)
resKG_4 = point_multiplication(l - 1, G_4)
resLG_4 = point_multiplication(l, G_4)
resMG_4 = point_multiplication(l + 1, G_4)
resNG_4 = point_multiplication(l + 2, G_4)

res0G_Gy_compressed_b = compress_point(res0G_4)
res1G_Gy_compressed_b = compress_point(res1G_4)
res2G_Gy_compressed_b = compress_point(res2G_4)
res3G_Gy_compressed_b = compress_point(res3G_4)
res4G_Gy_compressed_b = compress_point(res4G_4)
res5G_Gy_compressed_b = compress_point(res5G_4)
resKG_Gy_compressed_b = compress_point(resKG_4)
resLG_Gy_compressed_b = compress_point(resLG_4)
resMG_Gy_compressed_b = compress_point(resMG_4)
resNG_Gy_compressed_b = compress_point(resNG_4)

res0G_Gy_uncompressed_4 = decompress_point(res0G_Gy_compressed_b)
res1G_Gy_uncompressed_4 = decompress_point(res1G_Gy_compressed_b)
res2G_Gy_uncompressed_4 = decompress_point(res2G_Gy_compressed_b)
res3G_Gy_uncompressed_4 = decompress_point(res3G_Gy_compressed_b)
res4G_Gy_uncompressed_4 = decompress_point(res4G_Gy_compressed_b)
res5G_Gy_uncompressed_4 = decompress_point(res5G_Gy_compressed_b)
resKG_Gy_uncompressed_4 = decompress_point(resKG_Gy_compressed_b)
resLG_Gy_uncompressed_4 = decompress_point(resLG_Gy_compressed_b)
resMG_Gy_uncompressed_4 = decompress_point(resMG_Gy_compressed_b)
resNG_Gy_uncompressed_4 = decompress_point(resNG_Gy_compressed_b)

res0G_Gy_uncompressed_2 = extended_homogeneous_to_affine(res0G_Gy_uncompressed_4)
res1G_Gy_uncompressed_2 = extended_homogeneous_to_affine(res1G_Gy_uncompressed_4)
res2G_Gy_uncompressed_2 = extended_homogeneous_to_affine(res2G_Gy_uncompressed_4)
res3G_Gy_uncompressed_2 = extended_homogeneous_to_affine(res3G_Gy_uncompressed_4)
res4G_Gy_uncompressed_2 = extended_homogeneous_to_affine(res4G_Gy_uncompressed_4)
res5G_Gy_uncompressed_2 = extended_homogeneous_to_affine(res5G_Gy_uncompressed_4)
resKG_Gy_uncompressed_2 = extended_homogeneous_to_affine(resKG_Gy_uncompressed_4)
resLG_Gy_uncompressed_2 = extended_homogeneous_to_affine(resLG_Gy_uncompressed_4)
resMG_Gy_uncompressed_2 = extended_homogeneous_to_affine(resMG_Gy_uncompressed_4)
resNG_Gy_uncompressed_2 = extended_homogeneous_to_affine(resNG_Gy_uncompressed_4)

print(res0G_Gy_compressed_b.hex())
print(res0G_Gy_uncompressed_2)
print()
print(res1G_Gy_compressed_b.hex())
print(res1G_Gy_uncompressed_2)
print()
print(res2G_Gy_compressed_b.hex())
print(res2G_Gy_uncompressed_2)
print()
print(res3G_Gy_compressed_b.hex())
print(res3G_Gy_uncompressed_2)
print()
print(res4G_Gy_compressed_b.hex())
print(res4G_Gy_uncompressed_2)
print()
print(res5G_Gy_compressed_b.hex())
print(res5G_Gy_uncompressed_2)
print()
print(resKG_Gy_compressed_b.hex())
print(resKG_Gy_uncompressed_2)
print()
print(resLG_Gy_compressed_b.hex())
print(resLG_Gy_uncompressed_2)
print()
print(resMG_Gy_compressed_b.hex())
print(resMG_Gy_uncompressed_2)
print()
print(resNG_Gy_compressed_b.hex())
print(resNG_Gy_uncompressed_2)
print()