Golang: 양자 컴퓨터 이후의 암호기술 구현 패키지 sidh 분석

Photo by Michael Dziedzic on Unsplash

 

기존의 비대칭키 알고리즘들인 RSA나 Diffie-Hellman등은 소인수분해나 이산로그와 같은 수학적 개념을 기반으로 한다. 하지만 양자 컴퓨터는 이런 알고리즘을 쉽게 풀어낼 수 있다고 예상한다. 이러한 양자 컴퓨터 시대를 대비한 암호기술을 Post-Quantum Cryptography(PQC)라고 부른다

 

Golang의 sidh package는 양자 컴퓨터 이후의 암호알고리즘을 구현한 패키지라 보면 되겠다.

패키지 링크:  https://pkg.go.dev/github.com/cloudflare/circl/dh/sidh

 

sidh 패키지를 이용하여 서버와 클라이언트간에 secret key를 공유하는 두 방법을 코드를 이용하여 이해해 보자

GitHub 예제코드: https://github.com/nicewook/sidh-example

 

참고한 링크

Cloudflare 포스팅: https://blog.cloudflare.com/kemtls-post-quantum-tls-without-signatures/

권용민님 포스팅: https://snowmerak.pages.dev/posts/kemtls/

클라이언트와 서버가 서로 Public key만 공유하는 경우

GitHub Code: https://github.com/nicewook/sidh-example/blob/main/key-exchange-using-sidh/main.go

Go Playgraound: https://go.dev/play/p/p09rFI4G8W4

 

서버와 클라이언트가 각각 private key, public key를 생성한다. KeyVariation은 둘이 달라야 한다

	// Client generates key pair - KeyVariationA
	privClient := sidh.NewPrivateKey(sidh.Fp503, sidh.KeyVariantSidhA)
	pubClient := sidh.NewPublicKey(sidh.Fp503, sidh.KeyVariantSidhA)

	if err := privClient.Generate(rand.Reader); err != nil {
		log.Fatal(err)
	}
	privClient.GeneratePublicKey(pubClient)

	// Server generates key pair - KeyVariationB
	privServer := sidh.NewPrivateKey(sidh.Fp503, sidh.KeyVariantSidhB)
	pubServer := sidh.NewPublicKey(sidh.Fp503, sidh.KeyVariantSidhB)

	if err := privServer.Generate(rand.Reader); err != nil {
		log.Fatal(err)
	}
	privServer.GeneratePublicKey(pubServer)

 

서버와 클라이언트가 서로의 public key를 교환했다고 하자

MITM(Man In The Middle, 중간자)이 public key를 중간에 낚아챈다고 하여도 public key만으로는 아무것도 할 수 없다.

하지만 sidh 패키지의 PrivateKey 타입의 DeriveSecret 메서드는 통신하려는 상대의 public key로 shared secret, 즉 secret을 생성할 수 있으며 이 둘은 같다.

 

TL;DR: 서버와 클라이언트는 노출되어도 아무 상관없는 public key만을 교환해서 secret key를 공유하게 된 것이다.

	// Now, let's say, Client and Server shares their public key to each other
	// MITM can do nothing with the public key at all

	// Client makes shared secret key from the server's public key using client's private key
	clientSS := make([]byte, privClient.SharedSecretSize()) // Buffers storing shared secret
	privClient.DeriveSecret(clientSS, pubServer)

	// Server makes shared secret key from the client's public key using server's private key
	serverSS := make([]byte, privServer.SharedSecretSize()) // Buffers storing shared secret
	privServer.DeriveSecret(serverSS, pubClient)

 

아래와 같이 생성된 secret key가 똑같음을 확인 할 수 있다.

	// Let's check if server and client have the same secret key
	fmt.Printf("secret key of client: %x\n", clientSS)
	fmt.Printf("secret key of server: %x\n", serverSS)
	fmt.Printf("server and client have the same secret key: %t\n", bytes.Equal(serverSS, clientSS))

서버만 Public key를 공유하고 클라이언트는 Cipher Text를 회신하는 경우

GitHub Code: https://github.com/nicewook/sidh-example/blob/main/key-encapsulation-using-sike/main.go

Go Playgraound: https://go.dev/play/p/7xUcDBFQA4t

 

이번에는 서버만 public key와 private key를 생성하고, 그 중 public key를 클라이언트에게 전달한다고 가정해보자

	// Server generates key pair.
	privServer := sidh.NewPrivateKey(sidh.Fp503, sidh.KeyVariantSike)
	pubServer := sidh.NewPublicKey(sidh.Fp503, sidh.KeyVariantSike)

	if err := privServer.Generate(rand.Reader); err != nil {
		log.Fatal(err)
	}
	privServer.GeneratePublicKey(pubServer)

클라이언트는 *KEM object를 생성하며 이것으로 서버의 public key를 Encapsulation을 하면 shared secret(== secret key)과 ciphter text를  만들 수 있다. 

	// Assume server sends its public key to client.
	// Client generates "shared secret" and encapsulate "cipher text"
	// from server's public key with client's private key
	kemClient := sidh.NewSike503(rand.Reader)
	cipherText := make([]byte, kemClient.CiphertextSize())
	clientSS := make([]byte, kemClient.SharedSecretSize())

	if err := kemClient.Encapsulate(cipherText, clientSS, pubServer); err != nil {
		log.Fatal(err)
	}

shared secret은 절대 외부로 노출하면 안된다. 클라이언트는 cipher text만을 서버에게 전달한다. 서버는 *KEM object를 만들어서 자신의 public key/private key 쌍, 그리고 클라이언트에게서 받은 cipher text로 secret key를 생성한다.

	// Now, Client has "shared secret"
	// Assume client sends only "cipher text" to the server
	// - MITM has nothing to do with "cipher text"
	// Server can decapsulate "shared secret" from the "cipher text" with 
	// its private key and public key
	kemServer := sidh.NewSike503(rand.Reader)
	serverSS := make([]byte, kemServer.SharedSecretSize())
	if err := kemServer.Decapsulate(serverSS, privServer, pubServer, cipherText); err != nil {
		log.Fatal(err)
	}

이제 클라이언트와 서버가 각각 생성한 secret key를 확인해보면 같은 것을 알 수 있다. 

	// Let's check if server and client have the same secret key
	fmt.Printf("secret key of client: %x\n", clientSS)
	fmt.Printf("secret key of server: %x\n", serverSS)
	fmt.Printf("server and client have the same secret key: %t\n", bytes.Equal(serverSS, clientSS))