ECC - BigNumber 구현 by C(더하기, 빼기 in Fp)

C언에에서 가장 큰 자료형은 long long으로 알고 있다 그렇다면 그것보다 큰 256비트는 어떻게 다루는가 이것이 bigNumber를 구현하는 이유이다

 

c를 아직 잘 사용 하지 못해서 c연습과 동시에 하고 있어 아직 미숙한 부분이 많다 

 

FINITE FIELD 

현대대수학 용어이다. 이 big number에서는 모든 연산에 modula 소수 P를 해줌으로 생각 하면 된다

 

소수 P

FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF

테스트 벡터의 소수 값이다

 

Big Number 구조체

 

Big Number  -  Add

덧셈 reduction

구조체를 보면 각각의 bigInt는 carry를 가지고 있다 이를 통해 8개의 32비트와 몇번의 reduction이 필요한지 알수 있다 따라서 더하기에서  마지막에 발생하는 carry를 결과값의 구조체 carry에 넣어주어 reduction의 bigint src가 들어가면 carry를 보고 판단하여 진행 할 수 있게 만들었다 또한 조건에서는 앞에 것만 결과값과 비교하지만 연속되는 0xffffffff를 만나게 되면 어느순간 carry가 발생하지 않게 된다 그래서 뒤에 것도 esle if로 넣어줘야 한다

reduction 시에 원래는 minus를 구현 후 사용을 한다 하지만 다르게 할 수 있지 않을까 생각을 해보았는데 ~prime +1로 됨을 찾았다 여기서 +1은 최하위 비트인 result.bigInt[0]에 더해주어야 함을 생각해야 한다

 

Big Number  -  Minus

사실 이 minus코드는 정말 못 짰다고 생각한다 그래도.. 짰으니까..

compare 함수가 쓰인다 x > y 인 경우 0을 반환하고 x < y 인 경우 1을 반환하고 x = y 인 경우 2을 반환한다 

compare로 결과를 나누어 0인 경우 reduction이 필요하지 않고 1인 경우 필요함을 알고 연산했다

0인 경우에도 배열 사이에서의 borrow관리는 필요하다 

지금 생각해보면 마지막에 구조체 carry를 -1로 주고 reduction을 진행하는게 더 좋은 방법이었을 것 같다

 

https://github.com/dlwotjr/ECC

GitHub - dlwotjr/ECC: Elliptic curve cryptography

전체 코드가 궁금하다면 방문해주세요