Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save johnzweng/863f412689ee383cc41ac7c709ca662c to your computer and use it in GitHub Desktop.
Save johnzweng/863f412689ee383cc41ac7c709ca662c to your computer and use it in GitHub Desktop.
The mystery of the generation points of the secpXXXk1 curves.. :)
# The mystery around secpxxxk1 generation points :)
# -------------------------------------------------
#
# The SEC 2 familiy of elliptic curves are defined in https://www.secg.org/sec2-v2.pdf
# and widely used in cryptography.
#
# The generation points G of these curves are defined in the standard paper without any nearer
# explanation how they were chosen. Interestingly the generation points (G) of all prime order
# koblitz curves of the SEC 2 family (secp160k1, secp192k1, secp224k1, secp256k1) share some
# unusual mysterious property.
#
# If the points are multiplied with the multiplicative inverse of 2 (effectively undoing
# a point doubling operation) one gets a point with an x coordinate, which surprisingly
# is only around 160 bit long (which is - except for the secp160k1 curve - unexepcted, as
# this value is much smaller than the order of the respective curve).
#
#
# What's even more interesting is that all these values share some common part:
#
# "8ce563f89a0ed9414f5aa28ad0d96d6795f9c6"
#
# secp160k1: 0x4_8ce563f89a0ed9414f5aa28ad0d96d6795f9c6_2
# secp192k1: 0x55412_3b7_8ce563f89a0ed9414f5aa28ad0d96d6795f9c6_6
# secp224k1: 0x_3b7_8ce563f89a0ed9414f5aa28ad0d96d6795f9c6_3
# secp256k1: 0x_3b7_8ce563f89a0ed9414f5aa28ad0d96d6795f9c6_3
#
# (I inserted the '_' for better visualization of the common parts.)
#
# Only the prefix and the last 3 bits got changed.
#
# I can recommend this short talk by Nadia Heninger about these open questions:
# https://youtu.be/NGLR2N4EK58
#
# Btw, NOTE: this does NOT mean that these are backdoors! It is assumed that the choice
# of the generator is irrelevant for security properties of schemes that only use
# one generator (like ECDSA or Schnorr signatures).
# To verify this yourself you can calculate these values in SageMath like this:
#
# secp160k1:
#
prime_p = ZZ('0xfffffffffffffffffffffffffffffffeffffac73')
a = 0
b = 7
secp160k1 = EllipticCurve( GF(prime_p), [a, b] )
order_n = secp160k1.order() # get order of the curve
# generator point G
G = secp160k1.point(('0x3b4c382ce37aa192a4019e763036f4f5dd4d7ebb' , '0x938cf935318fdced6bc28286531733c3f03c4fee'))
# calculate multiplicative inverse of 2:
Point_half_G_mod_n = G * ZZ( 1 / GF(order_n)(2) )
# print coordinates in hex:
'secp160k1: x: 0x%x, y: 0x%x' %( Point_half_G_mod_n.xy() )
#
# secp192k1:
#
prime_p = ZZ('0xfffffffffffffffffffffffffffffffffffffffeffffee37')
a = 0
b = 3
secp192k1 = EllipticCurve( GF(prime_p), [a, b] )
order_n = secp192k1.order() # get order of the curve
# generator point G
G = secp192k1.point(('0xdb4ff10ec057e9ae26b07d0280b7f4341da5d1b1eae06c7d' , '0x9b2f2f6d9c5628a7844163d015be86344082aa88d95e2f9d'))
# calculate multiplicative inverse of 2:
Point_half_G_mod_n = G * ZZ( 1 / GF(order_n)(2) )
# print coordinates in hex:
'secp192k1: x: 0x%x, y: 0x%x' %( Point_half_G_mod_n.xy() )
#
# secp224k1:
#
prime_p = ZZ('0xfffffffffffffffffffffffffffffffffffffffffffffffeffffe56d')
a = 0
b = 5
secp224k1 = EllipticCurve( GF(prime_p), [a, b] )
order_n = secp224k1.order() # get order of the curve
# generator point G
G = secp224k1.point(('0xa1455b334df099df30fc28a169a467e9e47075a90f7e650eb6b7a45c' , '0x7e089fed7fba344282cafbd6f7e319f7c0b0bd59e2ca4bdb556d61a5'))
# calculate multiplicative inverse of 2:
Point_half_G_mod_n = G * ZZ( 1 / GF(order_n)(2) )
# print coordinates in hex:
'secp224k1: x: 0x%x, y: 0x%x' %( Point_half_G_mod_n.xy() )
#
# secp256k1:
#
prime_p = ZZ('0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f')
a = 0
b = 7
secp256k1 = EllipticCurve( GF(prime_p), [a, b] )
order_n = secp256k1.order() # get order of the curve
# generator point G
G = secp256k1.point(('0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798' , '0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8'))
# calculate multiplicative inverse of 2:
Point_half_G_mod_n = G * ZZ( 1 / GF(order_n)(2) )
# print coordinates in hex:
'secp256k1: x: 0x%x, y: 0x%x' %( Point_half_G_mod_n.xy() )
#
# OUTPUT:
# -------
# 'secp160k1: x: 0x48ce563f89a0ed9414f5aa28ad0d96d6795f9c62, y: 0xbcda9d4acd74573f55010aef6c7b4b1ac4daa8ca'
# 'secp192k1: x: 0x554123b78ce563f89a0ed9414f5aa28ad0d96d6795f9c66, y: 0x90755fc93ea4b13027fc6c8f337d92c6d00090fad0e8b2c6'
# 'secp224k1: x: 0x3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63, y: 0xf7d94781b93cd62422e8a24472ffda23418d7c0e25ca89ed909f9ce4'
# 'secp256k1: x: 0x3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63, y: 0xc0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c'
#
#
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment