Implementing Elliptic Curve Cryptography operation in Python on the Curve P-192
P-192 곡선 파라미터 선언
# define P-192 parameters
p = 2 ** 192 - 2 ** 64 - 1
a = -3
b = 0x64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1
n = 0xFFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831
gx = 0x188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012
gy = 0x07192B95FFC8DA78631011ED6B24CDD573F977A11E794811WeierStrass Form
def valid(P: Affine_Point) -> bool:
"""
Check if P is on the curve, i.e., it is a valid point or not
Return True: P is a valid point
False: P is not a valid point
"""
x, y = P
return y ** 2 % p == (x ** 3 + a * x + b) % pJacobian Projection 정의
from typing import Union
from collections import namedtuple
Affine_Point = namedtuple('Affine_Point', 'x y')
Jacobian_Point = namedtuple('Jacobian_Point', 'x y z')
def _to_jacobian(P: Affine_Point)-> Jacobian_Point:
if inf(P):
return JACOBIAN_INF
else:
return Jacobian_Point(P.x, P.y, 1)
def _to_affine(P: Jacobian_Point) -> Affine_Point:
if P.z == 0:
return INF
else:
inverse = pow(P.z, -1, p)
return Affine_Point(P.x * inverse**2 % p, P.y * inverse**3 % p)무한원점 정의
# INF = (p, p)
INF = Affine_Point(0, 0)
JACOBIAN_INF = Jacobian_Point(1, 1, 0)
def inf(P: Affine_Point) -> bool:
"""
Check if P is INF or not
Return True: P is INF
False: P is not INF
"""
return P is INF
def neg(P: Affine_Point) -> Affine_Point:
"""
Negate P (P is the affine point on the curve)
"""
return Affine_Point(P.x, -1 * P.y)덧셈 정의
def add(P1: Affine_Point, P2: Affine_Point) -> Affine_Point:
"""
add(P1, P2)
Point addition (P1 and P2 are the point on the curve P-192)
"""
return _to_affine(_jacobian_affine_addition(_to_jacobian(P1), P2))
def _jacobian_affine_addition(P1: Jacobian_Point, P2: Affine_Point) -> Jacobian_Point:
# case1 : check identity
if _is_identity_of_addition(P1):
return Jacobian_Point(P2.x, P2.y, 1)
elif _is_identity_of_addition(P2):
return P1
x1, y1, z1 = P1
x2, y2 = P2
t1 = z1 ** 2 % p
t2 = t1 * z1 % p
t1 = t1 * x2 % p
t2 = t2 * y2 % p
t1 = (t1 - x1) % p
t2 = (t2 - y1) % p
# case2 & case3 : check inverse & doubling
if t1 == 0:
return _jacobian_double((x2, y2, 1)) if t2 == 0 else JACOBIAN_INF
# case 4 : do addition
c_z = z1 * t1 % p
t3 = t1 ** 2 % p
t4 = t3 * t1 % p
t3 = t3 * x1 % p
t1 = 2 * t3 % p
c_x = t2 ** 2 % p
c_x = (c_x - t1 - t4) % p
t3 = t3 - c_x
t3 = t3 * t2 % p
t4 = t4 * y1 % p
c_y = (t3 - t4) % p
return Jacobian_Point(c_x, c_y, c_z)
def _is_identity_of_addition(P: Union[Affine_Point, Jacobian_Point]) -> bool:
"""
Determine whether the input point is the point at infinity or not.
For the jacobian projection, z-value of the point at infinity is 0.
:param P: a jacobian point OR an affine point
:return: true - if the input point is at infinity
"""
if type(P) is Affine_Point:
return inf(P)
elif type(P) is Jacobian_Point:
return P.z % p == 0더블링 정의
def dbl(P: Affine_Point)-> Affine_Point:
"""
dbl(P)
Point doubling (P is the point on the curve P-192)
"""
if inf(P):
return INF
return _to_affine(_jacobian_double(_to_jacobian(P)))
def _jacobian_double(P: Jacobian_Point)-> Jacobian_Point:
if _is_identity_of_addition(P):
return JACOBIAN_INF
x, y, z = P
t = (3 * x ** 2 + a * z ** 4) % p
c_x = (t ** 2 - 8 * x * y ** 2) % p
c_y = (t * (4 * x * y ** 2 - c_x) - 8 * y ** 4) % p
c_z = (2 * y * z) % p
return Jacobian_Point(c_x, c_y, c_z)Scala Multiplication 정의
def mul(k: int, P: Affine_Point) -> Affine_Point:
"""
mul(k, P)
Point multiplication (P is the point on the curve P-192, integer k >= 0 )
"""
Q = JACOBIAN_INF
k_binary = _to_binary(k)
for i in k_binary:
Q = _jacobian_double(Q)
if i == '1':
Q = _jacobian_affine_addition(Q, P)
return _to_affine(Q)
def _to_binary(num: int) -> list:
"""
return type is list, of which each element is character type
"""
return list(bin(num))[2:] # eliminate first two, ex) 0b00101001
더보기
"""
Implement ECC operations on the curve P-192
"""
######################### Define Projective ############################
from typing import Union
from collections import namedtuple
Affine_Point = namedtuple('Affine_Point', 'x y')
Jacobian_Point = namedtuple('Jacobian_Point', 'x y z')
# INF = (p, p)
INF = Affine_Point(0, 0)
JACOBIAN_INF = Jacobian_Point(1, 1, 0)
def _to_jacobian(P: Affine_Point)-> Jacobian_Point:
if inf(P):
return JACOBIAN_INF
else:
return Jacobian_Point(P.x, P.y, 1)
def _to_affine(P: Jacobian_Point) -> Affine_Point:
if P.z == 0:
return INF
else:
inverse = pow(P.z, -1, p)
return Affine_Point(P.x * inverse**2 % p, P.y * inverse**3 % p)
########################################################################
################## Define Basic properties of P-192 ####################
p = 2 ** 192 - 2 ** 64 - 1
a = -3
b = 0x64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1
n = 0xFFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831
gx = 0x188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012
gy = 0x07192B95FFC8DA78631011ED6B24CDD573F977A11E794811
def valid(P: Affine_Point) -> bool:
"""
Check if P is on the curve, i.e., it is a valid point or not
Return True: P is a valid point
False: P is not a valid point
"""
x, y = P
return y ** 2 % p == (x ** 3 + a * x + b) % p
def inf(P: Affine_Point) -> bool:
"""
Check if P is INF or not
Return True: P is INF
False: P is not INF
"""
return P is INF
def neg(P: Affine_Point) -> Affine_Point:
"""
Negate P (P is the affine point on the curve)
"""
return Affine_Point(P.x, -1 * P.y)
########################################################################
########################## Define add & dbl ############################
def add(P1: Affine_Point, P2: Affine_Point) -> Affine_Point:
"""
add(P1, P2)
Point addition (P1 and P2 are the point on the curve P-192)
"""
return _to_affine(_jacobian_affine_addition(_to_jacobian(P1), P2))
def _jacobian_affine_addition(P1: Jacobian_Point, P2: Affine_Point) -> Jacobian_Point:
# case1 : check identity
if _is_identity_of_addition(P1):
return Jacobian_Point(P2.x, P2.y, 1)
elif _is_identity_of_addition(P2):
return P1
x1, y1, z1 = P1
x2, y2 = P2
t1 = z1 ** 2 % p
t2 = t1 * z1 % p
t1 = t1 * x2 % p
t2 = t2 * y2 % p
t1 = (t1 - x1) % p
t2 = (t2 - y1) % p
# case2 & case3 : check inverse & doubling
if t1 == 0:
return _jacobian_double((x2, y2, 1)) if t2 == 0 else JACOBIAN_INF
# case 4 : do addition
c_z = z1 * t1 % p
t3 = t1 ** 2 % p
t4 = t3 * t1 % p
t3 = t3 * x1 % p
t1 = 2 * t3 % p
c_x = t2 ** 2 % p
c_x = (c_x - t1 - t4) % p
t3 = t3 - c_x
t3 = t3 * t2 % p
t4 = t4 * y1 % p
c_y = (t3 - t4) % p
return Jacobian_Point(c_x, c_y, c_z)
def _is_identity_of_addition(P: Union[Affine_Point, Jacobian_Point]) -> bool:
"""
Determine whether the input point is the point at infinity or not.
For the jacobian projection, z-value of the point at infinity is 0.
:param P: a jacobian point OR an affine point
:return: true - if the input point is at infinity
"""
if type(P) is Affine_Point:
return inf(P)
elif type(P) is Jacobian_Point:
return P.z % p == 0
def dbl(P: Affine_Point)-> Affine_Point:
"""
dbl(P)
Point doubling (P is the point on the curve P-192)
"""
if inf(P):
return INF
return _to_affine(_jacobian_double(_to_jacobian(P)))
def _jacobian_double(P: Jacobian_Point)-> Jacobian_Point:
if _is_identity_of_addition(P):
return JACOBIAN_INF
x, y, z = P
t = (3 * x ** 2 + a * z ** 4) % p
c_x = (t ** 2 - 8 * x * y ** 2) % p
c_y = (t * (4 * x * y ** 2 - c_x) - 8 * y ** 4) % p
c_z = (2 * y * z) % p
return Jacobian_Point(c_x, c_y, c_z)
########################################################################
######################## Define multiplication #########################
def mul(k: int, P: Affine_Point) -> Affine_Point:
"""
mul(k, P)
Point multiplication (P is the point on the curve P-192, integer k >= 0 )
"""
Q = JACOBIAN_INF
k_binary = _to_binary(k)
for i in k_binary:
Q = _jacobian_double(Q)
if i == '1':
Q = _jacobian_affine_addition(Q, P)
return _to_affine(Q)
def _to_binary(num: int) -> list:
"""
return type is list, of which each element is character type
"""
return list(bin(num))[2:] # eliminate first two, ex) 0b00101001
########################################################################
############################### testcase ###############################
if __name__ == "__main__":
G = Affine_Point(gx, gy)
# G = (gx, gy, 1) # for Jacobian
score = 0
# addition (1): Boundaries
# identity
if add(G, INF) == G:
score += 1
else:
print("Fail: add(G, INF) == G")
if add(INF, G) == G:
score += 1
else:
print("Fail: add(INF, G) == G")
# negate
if add(G, neg(G)) == INF:
score += 1
else:
print("Fail: add(G, neg(G)) == INF")
# same input -> doubling
if add(G, G) == dbl(G):
score += 1
else:
print("Fail: add(G, G) == dbl(G)")
# doubling (1) Boundaries
# inf
if dbl(INF) == INF:
score += 1
else:
print("Fail: dbl(INF) == INF")
# multiplication
# boundaries
# 0G
if mul(0, G) == INF:
score += 1
else:
print("Fail: mul(0, G) == INF")
# (n-1)G + G = INF
if add(mul(n - 1, G), G) == INF:
score += 1
else:
print("Fail: add(mul(n-1, G), G) == INF")
# nG=0
if mul(n, G) == INF:
score += 1
else:
print("Fail: mul(n, G) == INF")
# (n+1)G=1G
if mul(n + 1, G) == G:
score += 1
else:
print("Fail: mul(n+1, G) == G")
# random k
k = n - 2
Q = mul(k, G)
if not inf(Q) and not valid(Q):
print("Fail: Q is invalid")
else:
score += 1
if score == 10:
print("PASS")
else:
print("FAIL")
########################################################################'CS > Computer Security' 카테고리의 다른 글
| [컴퓨터 보안] 수업 필기 (0) | 2022.06.24 |
|---|---|
| RSA 파이썬 구현 (key pair generator) (0) | 2022.05.10 |