Python Curve25519 generate shared secret

---

overview

회사에서 과제를 하다가 파이썬으로 Curve25519 키 교환 연산을 해야할 일이 있었다.

개인키와 공개키를 모두 알고 있는 상태에서 shared secret(key)을 연산하는 파이썬 코드만 필요했다.

shared secret은 cocoa의 25519 Kit으로 계산되었는데, 이를 파이썬으로 구현해야했다.

그런데 인터넷에 있는 대부분의 예제 코드로는 shared secret을 온전하게 계산하기 힘들다.

예를 들어 이미 생성된 키를 이용해 shared secret을 계산하지 않고, 랜덤하게 키를 생성한 뒤 shared secret까지 랜덤하게 계산한다. 혹은 shared secret의 해시값만 반환하기도 한다.

덕분에 curve25519관련 파이썬 패키지들을 많이 찾아보았다...

그래서 파이썬을 이용해 Curve25519의 shared secret을 결정론적으로 계산하는 방법과 curve25519관련 패키지들을 정리한다.

---

curve25519

curve25519는 Daniel J. Bernstein이 고안한 elliptic-curve key-agreement(타원곡선 키 교환) 프로토콜이다. Bernstein의 original implemetation은 그가 고안한 qhasm라는 언어로 구현되어있다. 무려 2005년에 구현된 코드다.

http://cr.yp.to/ecdh/curve25519-20050915.tar.gz

관련 논문은 아래 링크에서 확인할 수 있다.

http://cr.yp.to/ecdh/curve25519-20060209.pdf

Alice와 Bob이 키 쌍(공개키, 개인키)을 생성하고, 공개키를 교환한 뒤에 두 당사자 모두 shared key를 계산할 수 있다.

조금 더 자세히 말해보자면, Alice는 $F(A_{private}, B_{public})$을 계산하고 BoB은 $F(B_{private}, A_{public})$을 계산한다. 그리고 서로 $B_{public}$과 $A_{public}$을 교환한다.

공격자가 $B_{public}$과 $A_{public}$을 알더라도 개인키를 이용해 계산한 shared secret은 알 수 없다.

---

curve25519-donna package

curve25519-donna는 http://code.google.com/p/curve25519-donna/에서 호스팅 중인Adam Langley의 코드를 구현한 python wrapper다.

또한 github에서 코드를 확인할 수 있다.

키 쌍을 생성하는 함수나 용법은 테스트 코드에서 확인할 수 있다.

• install

pip install curve25519-donna

# import curve25519

• Windows 에러

  윈도우에서 Visual Studio가 설치되어있지 않다면 아래와 같은 오류가 발생한다.

  error: Microsoft Visual C++ 14.0 is required. Get it with "Build Tools for Visual Studio": https://visualstudio.microsoft.com/downloads/

  내부에서 c 코드르 참조하기 때문에 컴파일러가 필요하다.

  Linux나 OS X는 그냥 설치가 가능하다.

---

curve25519-donna shared secret

궁금했던 것은 shared secret을 생성하는 부분이다.

curve25519-donna는 curve25519-donna/python-src/curve25519/keys.py에서 get_shared_key() 함수를 이용해 공유할 값을 계산한다.

def get_shared_key(self, public, hashfunc=None):
	if not isinstance(public, Public):
		raise ValueError("'public' must be an instance of Public")
	if hashfunc is None:
		hashfunc = _hash_shared
	shared = _curve25519.make_shared(self.private, public.public)
	return hashfunc(shared)

그런데 마지막 줄을 보면 shared가 아닌 해시값을 return한다.

따라서 shared secret이 필요한 경우 이 함수를 사용할 수 없다..

shared를 계산하는 make_shared()를 찾아보았다.

make_shared() 함수는 curve25519-donna/python-src/curve25519/curve25519module.c의 80번째 줄에서 pycurve25519_makeshared()라는 이름으로 매핑되어있다.

---

(이제부터 파이썬 코드가 아닌 c implementation으로 넘어가기 때문에 필요한 함수를 찾아도 쉽게 가져다 쓰기 힘들다. 그냥 궁금해서 찾아보았다.)

pycurve25519_makeshared() 함수는 다음과 같다. [참고]

static PyObject *
pycurve25519_makeshared(PyObject *self, PyObject *args)
{
	const char *myprivate, *theirpublic;
	char shared_key[32];
	Py_ssize_t myprivatelen, theirpubliclen;
	if (!PyArg_ParseTuple(args, y"#"y"#:generate",
						  &myprivate, &myprivatelen, &theirpublic, &theirpubliclen))
		return NULL;
	if (myprivatelen != 32) {
		PyErr_SetString(PyExc_ValueError, "input must be 32-byte string");
		return NULL;
	}
	if (theirpubliclen != 32) {
		PyErr_SetString(PyExc_ValueError, "input must be 32-byte string");
		return NULL;
	}
	curve25519_donna(shared_key, myprivate, theirpublic);
	return PyBytes_FromStringAndSize((char *)shared_key, 32);
}

이 함수에서는 curve25519_donna() 함수를 호출해서 shared_key를 계산한다.

curve25519_donna() 함수는 curve25519-donna/curve25519-donna-c64.c에 구현되어있다.

---

(2021년 1월을 기준으로 여러 프로그래밍 언어의 curve25519관련 패키지(또는 모듈)를 많이 찾아보았는데, c implementation을 참조한다면 바로 이 코드로 수렴한다! 따라서 어떤 언어든 unit test를 해야 한다면 이 코드를 사용하면 아주 편리하다.)

• curve25519_donna()

int
curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) {
  limb bp[5], x[5], z[5], zmone[5];
  uint8_t e[32];
  int i;

  for (i = 0;i < 32;++i) e[i] = secret[i];
  e[0] &= 248;
  e[31] &= 127;
  e[31] |= 64;

  fexpand(bp, basepoint);
  cmult(x, z, e, bp);
  crecip(zmone, z);
  fmul(z, x, zmone);
  fcontract(mypublic, z);
  return 0;
}

아무튼 파이썬 수준에서 사용할 수 있는 함수는 get_shared_key()이고, 이 패키지에서는 온전한 shared secret을 계산할 수 없다.

---

donna25519 package

다행히 shared secret을 계산할 수 있는 파이썬 패키지를 찾을 수 있었다.

donna25519라는 패키지인데, 앞서 살펴본 Curve25519-donna의 wrapper 코드다.

코드는 github에서 볼 수 있다.

특히 PrivateKey().do_exchange(public)으로 shared secret을 생성한다.

do_exchange() 함수는 여기에 정의되어있다.

def do_exchange(self, public_key):
	if not isinstance(public_key, PublicKey):
		raise TypeError('"public_key" must be an instance of PublicKey.')

	shared = _curve25519.make_shared(self.private, public_key.public)
	return shared

---

Test Code

다음은 donna25519를 이용해 shared secret을 계산하는 테스트 코드다.

키 쌍 생성은 예제가 많아 생략했다.

#!/usr/bin/env python3

# `pip3 install donna25519`
from donna25519 import PublicKey
from donna25519 import PrivateKey


def gen_curve25519_secert():
	# shared_secret = ECDH(private, public)
	public_str = "44595b26ee2b7482661a7a3d3dbdc85cd78109a596b99e150800083c7326997e"
	private_str = "18560cc20d26d6cc891861247e26f459015dd55a7a3114e0837e8c56f7860642"

	print("[public]\n", public_str)
	print("[private]\n", private_str)

	public_key = bytes.fromhex(public_str)
	private_key = bytes.fromhex(private_str)

	assert(len(public_key)==0x20)
	assert(len(private_key)==0x20)

	public_key_obj = PublicKey(public_key)
	private_key_obj = PrivateKey(private_key)
	
	shared_secret = private_key_obj.do_exchange(public_key_obj)

	assert(len(shared_secret) == 0x20)

	print("[shared_secret]\n", shared_secret.hex())


def main():
	gen_curve25519_secert()


if __name__ == '__main__':
	main()

# EOF

---

참고

cocoadocs 25519: http://cocoadocs.org/docsets/25519/2.0.2/

D. J. Bernstein: http://cr.yp.to/djb.html

Curve25519 paper: http://cr.yp.to/ecdh/curve25519-20060209.pdf

curve25519-donna - google code archive: https://code.google.com/archive/p/curve25519-donna/

curve25519-donna - github: https://github.com/agl/curve25519-donna/tree/master

curve25519-donna

donna25519 패키지: https://pypi.org/project/donna25519/

donna25519 - github: https://github.com/Muterra/donna25519

---

Uploaded by Notion2Tistory v1.1.0