CRISTALS Kyber を Go で PKE

CRISTALS Kyber の本家の実装は C 言語ですが、本記事では Go 言語（以下 golang）の実装に Cloudflare 社の Go モジュール "CIRCL" に含まれる Kyber パッケージを使った具体的な PKE（Public Key Encryption、公開鍵暗号）の使い方を説明します。

動作確認:
- macOS v12.6.3 (Monteray)
- Go v1.20.2 (darwin/amd64)
- github.com/cloudflare/circl v1.3.2
あわせて読みたい:
- 2021-J-2: 量子コンピュータ開発の進展と次世代暗号 | ディスカッション・ペーパー・シリーズ | 論文 @ 日本銀行 (PDF)

CRISTALS Kyber とは

CRISTALS Kyber は、NIST 主催の PQC のコンペティションで「公開鍵暗号および鍵交換部門」で優勝した暗号アルゴリズムです。

PQC（Post-Quantum Cryptography）とは 2017 年から 6 年近くかけて開催された「量子コンピューター演算による解読にも耐性のある暗号アルゴリズム」のコンペです。詳しくは TS;DR をご覧ください。

Post-Quantum Cryptography - Selected Algorithms 2022 @ NIST

TL; DR _{^{（今北産業）}}

KYBER は NIST 主催のコンペ（PKE 部門）で優勝したアルゴリズム。
耐量子コンピューター暗号解読、つまり量子コンピューター演算（素因数分解など）にも耐性のある公開鍵暗号方式の暗号アルゴリズムである。
暗号化できるデータは 1 処理につき最大 32 バイト。
これはハイブリッド暗号を前提としており、本体データの暗号用途ではない。本体データは共通鍵暗号で暗号化し、暗号化に使われた鍵を公開鍵暗号方式で暗号化し相手に渡すためのもの（KEM）である。なお、本体データの暗号には AES-256 などの共通鍵暗号が一般的に使用される。
仕様が変わる可能性がある。
NIST のコンペで優勝したものの、これから数年かけて制定に向けての作業（脆弱性の精査や仕様固めなど）が行われるため、将来的に仕様が変わる可能性がある。実際に利用する際には関数をラッピングしてインターフェースを汎用にしておくと、仕様変更の際にも置き換えが楽になると思われる。

モジュールのインストール

go get github.com/cloudflare/circl

パッケージのインポート

import "github.com/cloudflare/circl/pke/kyber/kyber512"  // KYBER-512 を使う場合
import "github.com/cloudflare/circl/pke/kyber/kyber768"  // KYBER-768 を使う場合
import "github.com/cloudflare/circl/pke/kyber/kyber1024" // KYBER-1024 を使う場合

KYBER-1024を使う例

package main

import (
	"crypto/rand"
	"fmt"
	"log"

	"github.com/cloudflare/circl/pke/kyber/kyber1024"
)

func main() {
	// 公開鍵暗号の鍵ペアを生成（nil で crypto/rand.Reader を使う）
	pubKey, secKey, err := kyber1024.GenerateKey(nil)
	if err != nil {
		log.Fatal(err)
	}

	// 公開鍵の確認（1568 バイト長）
	var pubKeyRaw = make([]byte, kyber1024.PublicKeySize)
	pubKey.Pack(pubKeyRaw)
	fmt.Printf("PubKey: %x\n", pubKeyRaw)

	// 秘密鍵の確認（1536 バイト長）
	var secKeyRaw = make([]byte, kyber1024.PrivateKeySize)
	secKey.Pack(secKeyRaw)
	fmt.Printf("SecKey: %x\n", secKeyRaw)

	// 暗号化・復号時に渡される各メッセージのスライスは cap サイズが決められて
	// いる。そのため、一旦配列（固定長）で定義してから、渡すときにスライス（可
	// 変長）に変換する。
	var rawMsg [kyber1024.PlaintextSize]byte  // 暗号化される MSG（32 バイト）
	var encMsg [kyber1024.CiphertextSize]byte // 暗号化された MSG（1568 バイト）
	var decMsg [kyber1024.PlaintextSize]byte  // 復号された MSG（32 バイト）

	// 暗号化するメッセージ（Max 32 バイト、通常は共通鍵暗号の秘密鍵）
	_ = copy(rawMsg[:], "OurVeryStrongSharedSecretKey!")

	fmt.Println("RawMsg:", string(rawMsg[:]))

	// 暗号化に使うシード値に乱数を使う
	randSeed := GenerateRand32Byte()

	// 公開鍵で暗号化（メッセージの配列をスライスに変換して渡す）
	pubKey.EncryptTo(encMsg[:], rawMsg[:], randSeed)

	fmt.Printf("EncMsg: %x\n", encMsg)

	// 秘密鍵で復号
	secKey.DecryptTo(decMsg[:], encMsg[:])
	fmt.Println("DecMsg:", string(decMsg[:]))
    // Output:
    // PubKey: d3167a39b628afaa530930692de7cf5f5a3dc50338f021357f3440f17bb41578b7948c4fb02751143b845cd0928c01282554435f3bcf69257c4f341a3b18a4a868bab11438151964ea5505051aa0d9a1053b8c1cd0e57cb9129c35729c2eb14c472ac8137835bf536e564095d6b8c925f2c7c12ca25b74847c14928ff0a15b572b89d3397818614a4b7232674e81598aceabbc97d98fb2fb8c7da2c94821049649889784b800861784e7c3f653c1cd580fb81c24e8ac2b0b4946e37bb2839140a0db541ca08d7f348d71e7cab1f86b58d303f4058ffeb4cad350983793ba35286e5a88aaa1c91abb0365d2d9712f5440e97a9d7b513a23a2b91c499296045f4808b1b82a3c7a25be5598b23c39c5ec066dad9ccbaf7cca82652aa2d47bdbd48878aa395bc7a6f520cc409ccb43295440a9092555792047238c3128e2191bcbb24b505cae1f81237ea522eb29b914d41e06b7407b29530f0b36b9e741b7d276fe653fb5a4cd4e1ca4783c01f9bb9a20e06627b114c62c494af303ea19b6aa18483a5915bb2635152bbc85407fd3879e4192202bd6c538190876073868dc96864447d2e8691df8ce211aab09334590e864ce454a18e719fbf5c8da01399b90befaa68573d8a6753c43eac43b1dd466fe3164f382ac1b9b5c6c1a9205ac83f2652e993775d1e3776e7806a596311b1564be3061425a593d6c8de258b978d98d5a818a2072753e14b120cc93af995abbe8691ff3b72fa187a0f599c51b1d165107ea1b7eb39cb881800b32e6c653bacf0d265c5bbba82c210e29dc2d04d66d755a4c1e387168c4a18dbb27a4082d17d27c14706cce0963b73b4ca1dc31c286338648c13876b5e14241588ab913164977658fd1a4ce7db47c6e3c835359066ffc24583564d6f928f8323a80baac610cabf75854e3252a1e4134c1a57d857a0fdc19a3f1f193333c7494154fbc4888a4600642d41b4cc44e92311880b5b00f1433d9acb545935a8e9a429147b0d4b09cc08358c312a41ad5a7ae5516138267ec1061ff20cc58104e991b7a2117b225f2434c3644faaa042e4283c484564b4c3350fb40ebd60c1cb371dc6558209554b6c4b6d69120879a54ce4685339aa357c767f8217a9cd7c1d5e7067c35b17b515117842becb7235726560f455135924ee4d73f47396fc36370a2130d5d3b28a5e382e9032ea13770c787b1693c3d1b756e77a8a95a878ae7c604df2b2532a08faee4bb7991c91ff0770bec01c57926c2280ab62caf53c69036e2ae7391555eea3bd2e6019f748900c5a5365277aa8464d1e82ebef070479976efd35b3d61983bb5417c34842c33bec4c4a418e78c9d922cba993efb845142b465545c13e77ac3f014ab5a8a176bd1cd54410c121852542a10d809b3f51ac776e1b65756809c07ab43d768dae9044622864af0800fd837de39b1cf64761cf009d00940bb90ab4123a96fe923358608ccc9ab4904b6ec91aaf495084481773ab42885e9a8c8315b2c8587361c361c6b84df57114ff43f7ce902e9438decf63e60b847bed8ab13ac7a7fc601fab095813644c329644dac2250e0c0be87c608103ad7432eaf05685c9153a75a91909cbea0e98b588668c488859a60849fc1b3157b9866fc55d7d221530242f935526590b4f780080104496c582950d771634c75a5c83be52297eb316f76c966e4f7cdfbc71d6feb472d046a78b973d7f80aa75359b993c38f7718ca8b6aea25697e965ade83a47f6c1e43aa39449909a5c0725ee283934b6765331e4f5921c1a4374d3512199486cf00c3f513b6ddc005d6224201f761f7208b28c2c860ba14ab4a4b86963a75564f9502990d68b986853dd5d255afd06f706775db78a563d9c2b316ce2d0b017ff062eb4085fe4498df1a8acccacae050969010b4f43c9a0006548faa15f9e79e93780c751b509c4aa43c3131f0195de3ca4550b282cb3172b3ea33f6601963a47dbfb724db3a15f7083d3624ba564bc5ca73b90ec07f36ea74b3698158388489c256bfb1492ca79194215dd57805c2193e36baab48181e36a539fc37098a078d30060094a63e59f674da2c284dd19aec8a733d5ab6c994a62710867390cdb2672188da64caec633fbcb6ba3356caf8a0fe70582adc3a66b96c9f0ca26c303bb772bd8ca845dc8c4e2ade214bc9401f29285248f27ff655dfc74849507fe6065078ba99074e37702f
    // SecKey: 5345ba6ab342ed009edd713f43802d78f96b38bcc1e08a369fa79e0da0572ed536a49b4a50d80912e4ab937466d2a25f8bd0cbee899011e516ce38b982e9190d8a72e2865904c58aafc0421a892437ab40f7445d9295c947637e413cbaa26b4479b592bcd871ab2149e823515317b691f05e24b9014b702d52894e35c19b01572506a9c5aa67242f6b925f938900c9c50348b011db5021e5631e4c5f0c3a140f97c6ef05b224e30dabfa0ef0b562969c15d73a6397e66ee158515f48afe077a7a9995e67c107a86ab9a543614675a2037c216aa684a2a1b41743151a522d726902cee76bb36aa5c75b932fa77072772f334a1b8fa69a4ab56f2a702e480978ac9ccb3d263e4b166fe15b81852192ed95083a3126156c69790bbd172328e0ebb1d634ad94b88eed730ccd537fdc3784d4658d5120b92087805ad0639ef52998478f3fa016a8a47cb2088e3b58a2e17053e4d917da35a4bcfbaff3e72b33761ce1b741eda34aa1648e9f1a236fd74b71965fae56b6a4c0cf6ce99798bb15922ab7bd860c4d580cd7837944588d7ab73f6be0a23e71b98852176ea5750a29bd20b55974784cacf18dac335a138a1c91642445a95a0b5a84608c4af69640dff2646baccdb1997b3032371c152eb4dc50262c9451b8ae7791973374c029b31b942051d33477962726d36526bc3a04f110a97dd8672b274fb23a600e51abbae9a6385292dce1baa21b860d5bcd54a8a2a305a148255b9ce8c1034a6533016c6f8784077b69628148177217e1f25f2cd127771bb265f8a4e5017bda7073617693b0713cdc802174052040c91e7875505222b6ea56a195009fd3c67e82f25793ac5640e42aa786397e16279ecbb4451254101a5d496a8892f665d3bb54423666f39ca21d5607ad06abea828b97c2a5ed936f7ec2553447a91d3a0ce9b14596142fd5c9a69320616988ba70941769c76aa66a0230fb4e5ca000975acafcbbcc36e895b2c749d0c56b4d9532d62c21791797c693bd55991b63a97c1f84b8e8835f4e48a580778b8426b1e16c95a2508d49c5352387089511c9cdb80c300c84ff10714440a68c20199d788118688519a9381ecb8457c540dd031bbfd9ba2e71c18e62305541454732a21ef880f1a18353c8166c9c0647861424e47e500b79cf5072fc88af1c741610412b10621c2aa07a1926c4eeb19b05d59bd629451a709568b0c1eb5320b905acc0ac6ba4e3637f9a71b5f35f521c2afce225bc090cb21c2cbf65c919f9b4fdf345356454acd257223b249c5b55f2530d598b7948447dbb87cdb88a825eda3a8dc437fbac3d399125f999b6b81a406cc35563216c02986cca4575e1eccaa14bbd1a965dd7a2001702100010bc16067e001ca451f64fbda284339a119c85c18321494e047e221474f8389e15e60bf559a35ce14844e60fb8ca0be8cb6e8f6332ecd27fe616bcd9f12a50153538848922136c84468250d0172fc6cfaf3c220b68162a80abf091ce133ab004553bd309c31145c74276b99d90bbd2a78efc4044e46067cfc9afa2902d840c2d4af2c969c4563b539ba6951b10819f53ea895aa521a1f1862aa8347969b8e6c9496b613b13ab7930984eb2699ac0ba80f5a9b42eb2c81b21cd858bc018113748502a3c36c0ffe27839f6222e904e6aa88e40b63ee26ca746a0541e48c8fe493680239ab65b3e18a740213624a755936c2c861457c9d4bc2c020873e360595875b48c643e4797ba6a129e5ef58f1979162730bccb483a19849bae9712b320c24f65563143b6e54710cc7a91bfc2cf6826cd61da41dce173e73c9405dc8ab695548e9b46ffca998e056c3285176bec321d693063e30a02cbad54d1b91d6c742ab3b855cc4c58664d2619b7c42422cce9b02c80a74ec277e58979b6d998c5966ad04aab6ae23d53d0cc985b7e0ac4aad16751eb59b748c09f2ae1a476c4897f075460981414a3c0e078320bb21514b4b1d0c2a8c8769263f1c558962e680754243a57620c71a2521481a142dc32883f050b1b04c7c273cd09ab28804c7481d2baf9192fffd43fb7889ce0eacaf09686e83996ade8b29ad9a441751778fc1d8e4b80d693437c39713fa75090fc34be90bd7d21cd6281800ae6bf4402b5695b77c28021e608594ed28353e595917189c983143863be
    // RawMsg: OurVeryStrongSharedSecretKey!
    // EncMsg: b6ab9a0780cbfa3ee24d073765af5dd5053c9742f591d5d09fe285a9b1623530c4d90f286a54e6b58e88bfa94adaae9aca124bf889937a2bff583c0275b1fa812d9c4d5e1a1e716b2f0fa09014e5ae86ea5b5c888e054d9a3c939fc23a77f6893dff2abf80247cf2bf4ec52ecb812220a262e4d00e9b6731d14d02ffd13d6a177118f24a114cf2b645af4f380fcb8fa1082bf35d16b7624d9a0f8a78b2006267bd166b48843cde595b6014e4087a921c74dab85305982eb4f5b2575865dad7d1d0d09e43f9ee7bdc6585bd093fa1906a28306482f32bf47cc113ae63f546f5f321ca22f405de1232a9f96e9ed2502ee536f412b0a2bfd23f2c602eeada281d018eef1657ded5a339c0fec1630f0625c8416e7bd277edbb0e44c254f46830765c4a57e516b2442c33565a183a5278d71b7336fd5706a4d4f56d829135ca73a137b43290f0c26e5deffa0a19f429b3d349e37f76c4eaddccc7602d6e94de293fd667830c82fce8ba0a862013e76c94dc16b6f3fc4f9c022b75bdad18ef73ba7907370948aa9073dc2b5149b12568185c82ab17175a45d31ba1299894e260699a032eb88de203809ac078c0753c2adc94bf713dfdcd6b8c6e800d8d33923260d3c01d457825ad0ec8e8b1b5c3610eb44e76c25e6b738bce170cc75e585d64da4c59e371785e3bfc85e4d1f80189006db63a5c5ac194a7bb29e39525c9182148a9b157b731b9a8ec6a9189a6742e54bd2cc1c007e70e3364642fe7f7f542a046c9d4188c874a86e0969f1a90387001c24b429a3e025d1f9738f8e976f14b1632612b48b8646b87d2087695834dd5530176f3aef6690eca374447ca272a119420052ea3001c005dbfcc7621d8d9d5262bc91a292bd349205416604157c6539511bcd0a04343f1c4c9ea6fd3c918d2eda260e6174e1b0fbfefa5a497e09d51c7733cff5c46ed4f36f6b088d9b9c4e508a545c0634c7eff0f238c45463fd3a2923ad4056e561bf7b6ae41126c567b04b29fd914e001070393fc1eb09affacb7bd67a36dbd40aa4fca59a91ff4cebf47ca304bed58e00c08e79b143dc7dccd3b469446057bda76d52e77e9d6fd40564e0baacc828c736b0344de5b3fabce4b394574b180e235ffeb8730ecd60c54671f2d5e7110349ad45756ec70e1152c8ed5342d46f608cb49761cfacb51a67d706a2920e3098d3a1f3c075bc589ff29e2a7180ea619797c0398ff723c0cda5e696ac4811ca657ccaaf49055a2f8b86264511fe386d81650ed010924cb9b34fefb2a814f50e23f6c554ed78912d3aaf2bb83cb805b31b9aa0aaff724180ce2d0a9b0a2fbd5e965adee0398d16e01a82fbf5e7ff6570e6b9ad9a00542e4088f7fbd1ebf72c0822464780adaf80725a1292e2075cda80cad022249a86e5b971d93b3d1c8c7c5a0d5b862214e3371cb6e99657e3f892c47381431ccc761a764c41cbab9062c86c51efe79a5529da38c58e63f97cab852b3e3983344f28aa35631f7df84cee7a87766be760ac1cb961b5f441af215dd9f4d6374b2f791e473122f49c48f9e65d0a8daba6726970d5ef0cc36e2697c09bc898aeb5cff4346c05a7b4bc75515be51915bf9c9422ebce2e04f6e3143e42e8d1fec707d8b8773850a02ce8b6f10aabd90867ffe0ebab0755b1c80558fbe52bde135f9aac16eded8dfc48b3c138e78b053a647c55257493ebf5d8acecbe8f73312043916597885fb044e9cacc110de50403e6d548b7ac2955c60d45086c737674351c902ae709f07e3d3d2d024ce8c5d4014e1dfa0ccd8dc13786a7f6222c132b6725d51c42e9ef3c26770e6735c53e79ff3439958691ae4cdd8f2e1b56db37bd3c1ee883a6e93b9c007b29fc658ca50d27ca84bd38ec6f5131ba39f8b5b4ba4bf099ae1bc049128be604d24811bd01f28e4d7255894d25bbc30e6bd541c70d7304c6635e1699b6f9cc8e74be1fb466b58fbae4860433ace36da387eb5d3db73f9e054e9b703500dd2cd22e95af0528151129fd07e502f63caa32dd411c85b5ebde4f859409a2ea11ba90c50727e9cce87bd54dd4df844ea60e4d81d70229f669e69559287c12a692a5f7c69ab88f9f0bb15a5cbc9c3cb72ccc0b824a0266f1134801240bcf391a627ee869f7ac9013ae75086e1f003541734a2aa6aea8f21542578783f405adba7ddc6ad4f0a4c9397beb1db3ab1a327815e049225e882644a1d
    // DecMsg: OurVeryStrongSharedSecretKey!
}

// GenerateRand32Byte は 32 バイトの乱数を生成します。
// 32 バイトは AES-256 の秘密鍵と同じ長さであるため、この関数は AES-256 の
// 共通鍵暗号の鍵生成にも利用できます。
func GenerateRand32Byte() []byte {
	seed := make([]byte, kyber1024.EncryptionSeedSize)

	if _, err := rand.Read(seed); err != nil {
		log.Fatal(err)
	}

	return seed
}

オンラインで動作を見る @ GoPlayground

「公開鍵を生成できるということは DH 鍵共有で、お互いの公開鍵から共通秘密鍵を作れないものか」と思うかもしれません。

CRISTALS Kyber でも鍵交換の研究が進められています。例えば Signal プロトコルでは X3DH（Extended Triple Diffie-Hellman）をベースに Kyber と Curve25519 を利用した PQXDH（Post-Quantum Extended Diffie–Hellman) などでチャレンジしています。

ちなみに、DH 鍵共有（ディフィー・ヘルマン鍵共有もしくはディフィー・ヘルマン鍵交換）とは、相手の公開鍵と自分の秘密鍵でゴニョゴニョすると、お互いが同じ鍵を生成できる概念です（詳しくは、別記事を参照ください）。

TS; DR _{^{（KYBER に関するコマケーこと）}}

2017 年から行われていた¹、NIST による「Post-Quantum Cryptography」のアルゴリズム・コンペですが、2022/08/03 にとりあえずの最終選抜が終わりました²。2022/11/23 現在、2024 年の標準化（仕様の制定）に向けての作業が進められています。無事標準化されれば、NIST により 6 年以上かけて厳選されたアルゴリズムということになります。

Selected Algorithms 2022 | Post-Quantum Cryptography (PQC) @ NIST (csrc.nist.gov)

Post-Quantum Cryptography とは

Post-Quantum Cryptography は、日本語で「ポスト量子暗号」や「耐量子暗号」などと言われますが、注意点として「耐量子暗号」は「耐量子暗号・・・・」ではありません、「耐量子・・・暗号」です。

恐れずに一言で言うと「量子コンピューターの演算にも（理論上）耐性のある暗号アルゴリズム」です。Post-Quantum Cryptography を Quantum-Resistant Cryptography と呼ばれたりするのも、その為です。

Post とあるため「次世代量子暗号」とも勘違いされますが、「Post」+「Quantum Cryptography」と「Post-Quantum」+「Cryptography」の違いによる誤訳が多い気がします。どちらかと言うと「量子時代の・・・・・暗号」に近いニュアンスです。

NIST によると「Post-Quantum Cryptography」とは「量子コンピューターとクラシックコンピューターの両方に対して安全であり、既存の通信プロトコルとネットワークに大幅な変更を加えることなく展開可能であることを目的としています。」とあります。そして「Post-Quantum」とは「量子時代が来た後」を指しています。

これは、量子コンピューターを使った暗号化・復号、もしくは量子理論を利用した暗号技術である「量子暗号」の一般化よりも先に「量子演算」の一般化が 10 年前後には来る可能性が高いことから、「素因数分解は時間のかかるものではなくなる」時代が来ると言うことです。

この「素数に依存したアルゴリズムを頼れない時代」、つまり「来たる量子時代」に備えるという意味で「Post-Quantum」と呼ばれます。

逆に言えば「量子暗号」ではないので、量子コンピュータでない「一般人のコンピューターでも使える暗号」ということでもあります。

Post-Quantum Cryptography のアルゴリズム

さて、この PQC ですが、以下の 4 つのアルゴリズムが選定されました。

NIST Announces First Four Quantum-Resistant Cryptographic Algorithms @ NIST (www.nist.gov)
Selected Algorithms 2022 | Post-Quantum Cryptography @ csrc.nist.gov

「公開鍵暗号および鍵交換アルゴリズムPublic-key Encryption and Key-establishment Algorithms部門」では、CRYSTALS チームの Kyber アルゴリズムが優勝しました。

CRYSTALS-Kyber @ pq-crystals.org

また「電子署名Digital Signatureアルゴリズム部門」では、以下の 3 つのアルゴリズムが優勝しました。なんと、先の CRYSTALS チームは二冠です。

CRYSTALS-Dilithium @ pq-crystals.org
Falcon @ falcon-sign.info
Sphincs⁺ @ sphincs.org

Kyber でわかっていること（適宜更新）

CRISTALS-Kyber の由来
- スターウォーズのライトセーバーの中核に内蔵されたカイバー・クリスタルに由来する。³
ハイブリッド暗号を前提としている。
- Kyber でデータを暗号化する場合、データの長さは最大で 32 バイトと決められている。⁴
- つまり、RSA 暗号同様、長文データの暗号化用途には向かない。
- そのため、データの暗号化自体は任意の共通鍵暗号のアルゴリズムで行い、共通鍵を公開鍵暗号でやりとりする際に Kyber を使うことを目的としている（例えば AES-256 の 32 バイトの共通鍵を Kyber で暗号化し、交換するなど）。
セキュリティ強度
- Kyber-512 は AES-128、Kyber-768 は AES-192、Kyber-1024 は AES-256 程度の強度と推定される。⁵
CRISTALS チームの C 言語による公式実装
- Kyber | pq-crystals @ GitHub
CRISTALS-Kyber を採用している主な団体
- CloudFlare の暗号化ライブラリ CIRCL @ GitHub
- Amazon の AWS Key Management Service | JP @ aws.amazon.com
- IBM の IBM Public Cloud や IBM Key Protect | Blog @ ibm.com
- ドイツ政府の BSI では、メールソフトの「Thunderbird」および OpenPGP にアルゴリズムとして採用してはどうか働きかけている。⁶
CRISTALS-Kyber の仕様
- Specification document (Version 3.02) (PDF) @ pq-crystals.org
NIST PQC 標準化カンファレンスのプレゼン資料（スライド）
- CRYSTALS–Kyber(PDF) @ pq-crystals.org

Golang でも触ってみたい

量子コンピューターの素因数分解のポテンシャルにより、合成数（素数を何かの数値と掛けた値）に頼っている系のアルゴリズム（例えば RSA 暗号）の安全性が危ぶまれてから⁷、結構な月日が経ちました。

とは言え、スーパーコンピューター同様、パンピー一般人の私たちが「実用的な量子コンピューター」に日常的に触れるようになるのは、まだまだ先です_{^{（遠い未来とは言ってない）}}。

しかも、Alice と Bob のように暗号文でチチくり合う⁸相手もいなければ、暗号化しないといけないような個人の機密データを扱うこともありません。いや、あるにはあるのですが、ファイル名を変え、深い階層のフォルダに隠してあるので絶対にバレることはありません。

そんなエンジニアと言うよりは猿人に近いえんじん NEAR な私ですが、新しいことには興味があります。というのも、最近勉強を始めた Golang では、簡単に暗号化できます。そして、無駄に何でも暗号化するも、復号できずにキーkeyキーkeyと騒ぎ、すぐにググる検索猿人なのです。

そんな中、暗号化の勉強中に見つけた Post-Quantum Cryptography の情報にセンサーが反応し、「Go でも触ってみたい」と興味をソソられました。

本家の実装は C 言語ですが、本家が認識している言語実装では Rust、Python、Java、Typescript、Go、JavaScript があります。

調べたところ、Golang による keyber の実装と思われるものは複数あり、その中でも有力なのが Kyber-K2SO、DEDIS と CIRCL のモジュールと思われます。

Kyber-K2SO: 公式にも記載されているモジュール。フランスに拠点を置く symbolic.software 社が実装・メンテナンスしている。; モジュール: github.com/symbolicsoft/kyber-k2so @ GitHub
DEDIS: EPFL 校の教授のラボが実装・メンテナンスしているモジュール。; モジュール: go.dedis.ch/kyber/v3 @ GitHub
CIRCL: Cloudflare 社が実装・メンテナンスしているモジュール。; モジュール: github.com/cloudflare/circl @ GitHub

NIST による制定前なので仕様が変わる可能性はあるとは言え、「実運用で利用されている」「メンテナンスされている」「メンテナやコントリビューターが多い」という点と、セキュリティが重視される Cloudflare 社のサービス内容から、本記事では CIRCL モジュールの github.com/cloudflare/circl/pke/kyber パッケージを利用したいと思いました。

ところが、CIRCL は「再利用を目指した暗号化ライブラリ」（色々なモジュールのラッパー）であるため、Kyber は「その他大勢の 1 つ」です。

そのためか、Examples*() 系のテスト関数による具体的な使い方や、ドキュメントが整っていないのです。

「これから来る（と思っている）技術なのに、なぜにドキュメントしないのだろう」と悩んでいたところ、Crystal Kyber とか、妙にスターウォーズ臭がするなというところで脳裏にケノービの声が聞こえてきました。

「ルーク、ソースを使え。」

... ... まじかー。

ソースから使い方を探る

🐒 【余談】
_{Go 言語（以下 golang）を触っていて、最初に感じたのは他の言語以上に「ソースを確認する習慣」です。「ソースを確認」と言っても、これには Golang 自身の言語実装の仕方の確認も含まれます。Golang は、Delphi 言語のように、golang 自身も同じ golang で実装されています。つまり、PHP などと違い、C 言語や C++ 言語を知らなくても golang の構文が読めれば「Go がどのように作られているか探れる」のです。
Golang には「下位互換を維持する約束」というのがあり、同じ v1 系なら大抵の古いコードは最新版の Go v1.* でもビルドできます。しかし「セキュリティ関連を除く」という例外もあります。10 年選手の新参言語であるため進化（バージョンアップ）も早く、下位互換はあっても仕様が変わっていることも多く、従来の Go を知っている人でないとストレートにビルドできなかったりすることがあります。そのため、下手に古い記事に頼るよりは（わからないながらも）ソースを見た方が確実だったりすることが多々あります（特にネットワーク関連）。

その習慣からか「そんなん、ソースを読め」と、ドキュメントのない丸投げの古いコードも多く見受けられます。
とは言え、Golang は、強力なドキュメント化の機能（例えば「コメントからのドキュメント作成」や、Examples*() といった「使用例関数」を使うとドキュメント化される機能）を言語レベルで持っています。そのため、もっとドキュメントに力を注いて欲しいなぁと感じるライブラリも多いです。いやー、まじで他の言語よりも「デフォルトでドキュメント化が楽」なのですよ。知らんけど。}

さて、ソースを覗くと、Examples*() 関数は少ないとは言え、最低限のテストは行っています。そこから、暗号化と復号の方法を探っていきました。

func TestEncryptThenDecrypt(t *testing.T) {
	var seed [32]byte
	var coin [SeedSize]byte

	for i := 0; i < 32; i++ {
		seed[i] = byte(i)
		coin[i] = byte(i)
	}

	for i := 0; i < 100; i++ {
		seed[0] = byte(i)
		pk, sk := NewKeyFromSeed(seed[:])

		for j := 0; j < 100; j++ {
			var msg, msg2 [PlaintextSize]byte
			var ct [CiphertextSize]byte

			_, _ = rand.Read(msg[:])
			_, _ = rand.Read(coin[:])

			pk.EncryptTo(ct[:], msg[:], coin[:])
			sk.DecryptTo(msg2[:], ct[:])

			if msg != msg2 {
				t.Fatalf("%v %v %v", ct, msg, msg2)
			}
		}
	}
}

circl/pke/kyber/kyber1024/internal/cpapke_test.go @ GitHub より

上記から汲み取れるのは、以下の 3 つです。

NewKeyFromSeed() 関数で公開鍵（pk）と秘密鍵（sk）のオブジェクトが作成される
- その際の引数 seed は、通常はランダム値であるが、ここではテストのため固定値 seed とする
暗号化は、公開鍵（pk）のメソッド EncryptTo() を使う
- 処理結果は第一引数に渡したバイトのスライスにセットされる（参照渡し）
- 暗号化したいデータを第二引数で渡す
- 暗号化する際に第三引数のランダム値を利用する。ここではテストのため固定値 coin とする
復号は、秘密鍵（spk）のメソッド DecryptTo() を使う
- 処理結果は第一引数に渡したバイトのスライスにセットされる（参照渡し）
- 暗号化されたデータを第二引数で渡す

思ったより使い方は簡単そうでです。しかし、上記は internal ディレクトリ下にあるパッケージであるため、外部から利用できません。

そこで、一階層上のパッケージをみると、上記のラッパーがありました。さらに、コメントから「引数に nil を渡すと crypto/rand.Reader が使われる」とあります。

// GenerateKey generates a public/private key pair using entropy from rand.
// If rand is nil, crypto/rand.Reader will be used.
func GenerateKey(rand io.Reader) (*PublicKey, *PrivateKey, error) {
	var seed [KeySeedSize]byte
	if rand == nil {
		rand = cryptoRand.Reader
	}
	_, err := io.ReadFull(rand, seed[:])
	if err != nil {
		return nil, nil, err
	}
	pk, sk := internal.NewKeyFromSeed(seed[:])
	return (*PublicKey)(pk), (*PrivateKey)(sk), nil
}

circl/pke/kyber/kyber1024/kyber.go #L45-L56 @ GitHub より

以上を踏まえて、簡単に組んだ以下のプログラムをオンラインで実行してみましょう。

package main

import (
	"crypto/rand"
	"fmt"
	"log"

	"github.com/cloudflare/circl/pke/kyber/kyber1024"
)

func main() {
	// 公開鍵暗号の鍵ペアを生成（nil で crypto/rand.Reader を使う）
	pubKey, secKey, err := kyber1024.GenerateKey(nil)
	if err != nil {
		log.Fatal(err)
	}

	// 暗号化・復号時に渡される各メッセージのスライスは cap サイズが決められて
	// いる。そのため、一旦配列（固定長）で定義してから、渡すときにスライスに変
	// 換する。
	var rawMsg [kyber1024.PlaintextSize]byte  // 暗号化される MSG（32 バイト）
	var encMsg [kyber1024.CiphertextSize]byte // 暗号化された MSG（1568 バイト）
	var decMsg [kyber1024.PlaintextSize]byte  // 復号された MSG（32 バイト）

	// 暗号化するメッセージ （Max 32 バイト）
	_ = copy(rawMsg[:], "MyVeryStrongSecretKey!")
	fmt.Println("RawMsg:", string(rawMsg[:]))

	// 暗号化に使うシード値に乱数を使う
	randSeed := GenerateRand32Byte()

	// 公開鍵で暗号化 （メッセージの配列をスライスに変換して渡す）
	pubKey.EncryptTo(encMsg[:], rawMsg[:], randSeed)
	fmt.Printf("EncMsg: %x\n", encMsg)

	// 秘密鍵で復号
	secKey.DecryptTo(decMsg[:], encMsg[:])
	fmt.Println("DecMsg:", string(decMsg[:]))
    // Output:
    // RawMsg: MyStronSecretKey!
    // EncMsg: 7a1291e5e874f6a7ed9b9c81b0802cda0f8fbb9fa75e11541bc8fcb661eb32c2329822cb305a6bcc5806798017421d06b814713891d30a3adb51ca994321eac0b84314e8bde69213e6b56ea224116316495ad5633e4921f392971a5dbf825e1f10823ed8ef28b47c6d4832baa46d6d463e9b76e43c490e7a9aaddbdd001d19d9b641c9de5d0f8145b46722d575cbb47e903f2851b6c97252e8f1d47f9b45022495fadc8ebaebc712bf4f0c1de81759b630c3233fa3ab4f35115e27dcf19ce23cef1e4a11b8e7f484cdc6ae64035de52ca8b6070b945b1b06c0d38aa43ded4a2803ef4e7082efe5af96a2ac43aef435e096b2a457e2e418bfad0e0f5d6e9b2edbdedaa00fae336daa57b951284d493ee633c9ad2a85215d1800132e38f6d6ba3b387dbb33ce42a2a15c815463e22da4eb093b80fe2d42efb4c5139f521af5f8e7c956dadf1474c120ef879065ddd49b43506fee4e55a3d6ec95c8dce01fa6dcafa850ddb04271359e8e2a73081a20c65596dfef8f9c489f61d9be193a3fca7931dd9ca2362455dc5cdc576b3d214a64b3884d0b3a30ca9a896eebfad6cc906a855f61924ca202a4614f7f0616981df6a5210ee4fc709637e1483c5068bd06740bce5b930731c28ce136161a10a088441ff314163d40b6af8c3f0b0fafec0053a45d860c5934a633682c1d4b2417cbe7f84d254fce72493299523c85e2358e539ae92286c6aa5fabc17f5cf83dd163eddee910794589bd570ef91bbc287aeb3c6eb5610876defc83fa01ac3479f1b6c208ad7a3445ba05839a499bfe7a49003de026e7a244237e2d33be5040208e0cf224c42c455caba27093b9aa3faa16a10db4aff5d431cfea9477288c10d2c502a71636e5fc0e9390a9a5b1c2904cf644cc2eb59b60ba9ec9e3f930c697415e8a2507158254314804e63c9109a52efea25f7c4bee83b159434c578ae5f8a8e44e13563ec30d7949a884d2d3cd6f5f1e1b38ab06285845383abc3db7800200831c7a5ca200cde494c1e62b5f2b6aeb127fb3c1a318eada1050c46aa0f128bd92d8affd5f6cdf59ed96be67d5973e9e9e606bc179cde02ba5b27c406d3667eb84efe91f793e3c5e3a3f59910d73de281ced00fc6664c34f52d5ed672e576be231adeb4dcca601ad948923b1b684cbcb451a4167bc053b9fd7924effe28ce3e686da01d65fbfa4243deb47292c16c58af203aee48c33b42e234cb1869b06da312abbf6e0cf8257db229c6876b07f816b084b6b9116565edbf277c714676a302f5981d90945ddc2fb947724864645b67c319e555a137a8a6a47f15799fe8ded23f0289aeff6bf700bbb70e3aa8f64dae50c1bfd4dfe63eec92b21d4637c5ae26ad26c604affdcfc822dd83d0a8c9b1af5d3038cdee08d8f4ddaeb2cbc98342360227dd08f8e5ebe98854cf82b0f73e802847d1936853a855dceab2d83de90f77f1f86234f9496b61d43f0e5c81cf182c602c94830fcdf1687c1e43c1f034c243eb5ace86967a805bb55039b7c9779a4352bbb9726be93a45441ef11b68c8a4611de52cb99eebebdcda85dc2f08c62dd11895a28235563d704109357479f88d5773b0efa39bdd8517e025666e1542407ff1871a327ad918eca97e3fa524061ef06639ef2c5c2ba6e335c4ef4c08132e3c5abd62cbddf65906386ab9fd920b6db33a2a2b7afbe7151ea5cfc043b719a6bfabefcbf467aa5088c5691a541bd1a65b6fe6ace1417bf4cd5ea30e4134056db0cc353e059ad3ca1ddc79a0564b7e474b9dbd2852c7dc37d36ef275d92e982cdbca8eaf355c5353a67fce30c493d3fdfa6e83aab126ed5f80522f5c0768c2e6a65d1f9d2688fa126c87ebf44fed4a824cafef68742ecb95495d1555555f738d8ba5d53e6332a88391bed3ef339ea74eae64d7ddf9a38103724d25e7b0d8b6bc7e2947c958783b0dac2ac33cd69ece408fca91d28e38223b4c6a152cb461ab013fae3cb6222a5edbc19e7dc01b8876d23d3ef6896ff94d5cf3a37abbf07d15064ad7c9ab25d580d0b2519113fabb3b78e74b360e6e37abaddb6f196fd564624b7e73c33c923ea1028312d546c8b37aeed3e9b8849114f0afd6448c4830ef83721603f821a60eceecda3c070368c65a89add0d78f58236d0009b58d79a182127a4cf3212a0371240c62a126b60a96ec79748626208b7875f9133cc324a80c0a7575e95deab33
    // DecMsg: MyStronSecretKey!
}

// GenerateRand32Byte は 32 バイトの乱数を生成します。
// 32 バイトは AES-256 の秘密鍵と同じ長さであるため、AES-256 の共通鍵暗号の鍵としても利用できます。
func GenerateRand32Byte() []byte {
	seed := make([]byte, kyber1024.EncryptionSeedSize)

	if _, err := rand.Read(seed); err != nil {
		log.Fatal(err)
	}

	return seed
}

オンラインで動作を見る @ GoPlayground

動きました。

上記の Output: を見てもらうと分かるのですが、MyStronSecretKey!（17 文字）という短いメッセージの暗号化に、とんでもない長さになっています。

これは Kyber が "Public-key Encryption and Key-establishment Algorithms"（公開鍵暗号および鍵交換アルゴリズム）部門のアルゴリズムであることに注意します。つまり「共通鍵を公開鍵暗号で交換する際に使われる暗号」ということで、いわゆるハイブリッド暗号の 1 つです。32 バイト以上あるような本体データを暗号化するためのものではありません。

本体となるデータは、32 バイトのランダムな値を共通鍵として AES-256 で暗号化し、その共通鍵を相手の Kyber の公開鍵で暗号化して送るというのが王道な使い方でしょう。

そして、当然のように中間者攻撃（Alice と Bob の間に実は Charlie がいて、各々は Charlie と鍵交換していたパターン）の問題も健全です。

出典どころか文責すら明記しない記事が増えるなか、今後は AI のフェイク情報対策など、秘密鍵で署名といった身分を証明することや E2E でデータを暗号化するといったことが、より重要・身近になっていくことでしょう。

CRISTALS-Kyber の姉妹である、最新電子署名アルゴリズム CRISTALS-Dilithium といった CRISTALS 姉妹にお世話になる時代がくるのです。

そして、どんなに強いアルゴリズムを使ったとしても、結局のところ、秘密鍵が漏れるとダメだという本質に改めて気づき、さらに OS の再インストールなどで秘密鍵を一緒に削除しちゃったりなんかすると、パスワードの再発行のようなことはできない世界になってきたんだと気付かされるのです。とほほ。

Call for Proposals | Post-Quantum Cryptography @ NIST より ↩
History of PQC Standardization Selected Algorithm Updates (PDF) | Selected Algorithms 2022 @ NIST より ↩
Kyber @ Wikipedia より。論文内や公式サイトには言及が見つからないので「要出典」かもしれない。 ↩
32 バイト固定長のメッセージは Kyber.CPAPKE と呼ばれる。Algorithm Specifications And Supporting Documentation (PDF), P.4, 第1章 Written specification @ pq-crystals.org より。 ↩
Introduction @ pq-crystals.org より ↩
Integration von Post-Quanten Kryptografie in den E-Mail Client Thunderbird @ evergabe-online.de より ↩
RSA暗号と素因数分解問題の関係 @ Wikipedia より ↩
暗号の世界では「ユーザ A」と「ユーザ B」の代わりに「Alice」と「Bob」が良く使われます。 ↩