Zenn
😸

【耐量子計算機暗号・PQC】CRYSTALS Kyber動かしてみた

2024/02/22に公開
Security
#
TLS
#
pqc
tech

そろそろPQCを理解したくなってきたので、ひとまずNIST標準化選出されたKEMアルゴリズムであるKyberを動かしてみる。

公式サイトのinstructionに従ってWLS2上にビルドする。

git clone https://github.com/pq-crystals/kyber.git
cd kyber/ref && make
cd ../avx2 && make

kyber/ref, kyber/avx2のそれぞれにいくつかの実行形式がビルドされる。avx2のほうは専用命令で高速化されていると思われるから、当面はrefを参照しよう。

実行形式として生成されるのは

  • test_kyber
  • test_kex
  • test_vectors
  • test_speed

で、それぞれに対して512, 512-90s, 768, 768-90s, 1024, 1024-90sのsuffixがついた6つのバイナリが生成される。いわゆるパラメータ違いのインスタンスであり、対応は以下の表のとおり。90sとなっているのはKyber内の計算で利用する共通鍵プリミティブがAESやSHAなどの”古い”インスタンスになっている。一方で90sがついてないものはSHAKEやSHA3といった新しいプリミティブを使っている。90sバージョンのほうが、CPUに存在する専用命令などを使えることから1.5~2倍程度高速

Kyber NIST
security level		 AES相当 古典
セキュリティ		 量子
セキュリティ
512 1 AES-128 128 64
768 3 AES-192 192 96
1024 5 AES-256 256 128

test_kyber

512のインスタンスを動かしてみる。

実行結果
~/prj/kyber/ref$ ./test_kyber512
CRYPTO_SECRETKEYBYTES:  1632
CRYPTO_PUBLICKEYBYTES:  800
CRYPTO_CIPHERTEXTBYTES: 768

・・・なんのこっちゃ。パラメータサイズが表示されるだけである。
ソースコードを見てみよう。

main

main in test_kyber.c
int main(void)
{
  unsigned int i;
  int r;

  for(i=0;i<NTESTS;i++) {
    r  = test_keys();
    r |= test_invalid_sk_a();
    r |= test_invalid_ciphertext();
    if(r)
      return 1;
  }

  printf("CRYPTO_SECRETKEYBYTES:  %d\n",CRYPTO_SECRETKEYBYTES);
  printf("CRYPTO_PUBLICKEYBYTES:  %d\n",CRYPTO_PUBLICKEYBYTES);
  printf("CRYPTO_CIPHERTEXTBYTES: %d\n",CRYPTO_CIPHERTEXTBYTES);

  return 0;
}

printしているのは単なるマクロの値であって、何の意味もなさそう。いちおう3つの関数test_keys(), test_invalid_sk_a(), test_invalid_ciphertext()がNTESTS=1000回動いているので、何らかの処理が走ってはいる。

test_keys

test_keys in test_kyber.c
static int test_keys(void)
{
  uint8_t pk[CRYPTO_PUBLICKEYBYTES];
  uint8_t sk[CRYPTO_SECRETKEYBYTES];
  uint8_t ct[CRYPTO_CIPHERTEXTBYTES];
  uint8_t key_a[CRYPTO_BYTES];
  uint8_t key_b[CRYPTO_BYTES];

  //Alice generates a public key
  crypto_kem_keypair(pk, sk);

  //Bob derives a secret key and creates a response
  crypto_kem_enc(ct, key_b, pk);

  //Alice uses Bobs response to get her shared key
  crypto_kem_dec(key_a, ct, sk);

  if(memcmp(key_a, key_b, CRYPTO_BYTES)) {
    printf("ERROR keys\n");
    return 1;
  }

  return 0;
}

アリス側で鍵ペアを生成し、ボブ側で公開鍵でセッション鍵を暗号化、アリス側で復号してセッション鍵の比較をしている。

test_invalid_sk_a

test_invalid_sk_a in test_kyber.c
static int test_invalid_sk_a(void)
{
  uint8_t pk[CRYPTO_PUBLICKEYBYTES];
  uint8_t sk[CRYPTO_SECRETKEYBYTES];
  uint8_t ct[CRYPTO_CIPHERTEXTBYTES];
  uint8_t key_a[CRYPTO_BYTES];
  uint8_t key_b[CRYPTO_BYTES];

  //Alice generates a public key
  crypto_kem_keypair(pk, sk);

  //Bob derives a secret key and creates a response
  crypto_kem_enc(ct, key_b, pk);

  //Replace secret key with random values
  randombytes(sk, CRYPTO_SECRETKEYBYTES);

  //Alice uses Bobs response to get her shared key
  crypto_kem_dec(key_a, ct, sk);

  if(!memcmp(key_a, key_b, CRYPTO_BYTES)) {
    printf("ERROR invalid sk\n");
    return 1;
  }

  return 0;
}

アリス側で鍵ペアを生成し、ボブ側で公開鍵でセッション鍵を暗号化、アリス側で秘密鍵を不正な値（ランダム値）に置き換えた後で復号している。当然鍵交換は成功せず、セッション鍵が一致しないことを検証している。

test_invalid_ciphertext

test_invalid_ciphertext in test_kyber.c
static int test_invalid_ciphertext(void)
{
  uint8_t pk[CRYPTO_PUBLICKEYBYTES];
  uint8_t sk[CRYPTO_SECRETKEYBYTES];
  uint8_t ct[CRYPTO_CIPHERTEXTBYTES];
  uint8_t key_a[CRYPTO_BYTES];
  uint8_t key_b[CRYPTO_BYTES];
  uint8_t b;
  size_t pos;

  do {
    randombytes(&b, sizeof(uint8_t));
  } while(!b);
  randombytes((uint8_t *)&pos, sizeof(size_t));

  //Alice generates a public key
  crypto_kem_keypair(pk, sk);

  //Bob derives a secret key and creates a response
  crypto_kem_enc(ct, key_b, pk);

  //Change some byte in the ciphertext (i.e., encapsulated key)
  ct[pos % CRYPTO_CIPHERTEXTBYTES] ^= b;

  //Alice uses Bobs response to get her shared key
  crypto_kem_dec(key_a, ct, sk);

  if(!memcmp(key_a, key_b, CRYPTO_BYTES)) {
    printf("ERROR invalid ciphertext\n");
    return 1;
  }

  return 0;
}

0でない乱数バイトbとposを生成。暗号文のposの位置にbを加えて暗号文を改ざんする。当然復号結果で鍵交換は成功しないので、key_aとkey_bが異なることを検証。1バイトの改ざんであるが、復号結果は改ざんされた場所以外も当然誤る。

test_kex

kyberを使った認証鍵交換をテストしているが、よくわからないので省略。

test_vectors

実行結果
~/prj/kyber/ref$ ./test_vectors512
934d60b35624d740b30a7f227af2ae7c678e4e04e13c5f509eade2b79aea77e2
3e2a2ea6c9c476fc4937b013c993a793d6c0ab9960695ba838f649da539ca3d0
Public Key: 5fc44b99d7584f38cd28360cc5625a905b96af12930ed5b5fe2a82fc5aa7dc4b829fe37635f13f5af2a6d3081dad878785698a0aa914374c4e43b89f094a7892aa149a38b49c06a068d829a8d249e753a375d097a0f162e6c3a4dfe8c79761410c605ed3899a3fc44378e14f28879e8f148077e6bc3bb2ae56178c491611bf6aaf5f9a9cb9b5659223007940bcd6f8a23280a56015330e8577259587b12606f4c937ea13606cb3bb046066ad294261e2b22022bcc74678a5520570d88e4ceb42692631e7e3711c4b2fd5347f0328598340cb3c65c8f55ac02716831094cb6eb90f175b173d9c650329aaf513633633bb2ce6858e7447abc41b6fb06da8782572c332b09660366926bf529ed8caaa6243ccdb152b36ba6e47c714145c86f5b3b61de84ef1470d03fa0135e35194fa1fb3bc860fa500d1299aee88ce56054376c1199c553dd90a8d6f9cc763c811d0c66da6f851abf1056635a34a68aa7815868f153a3a5c77fcc8b1eb1807fbf62a6fb43b355700e78230943a2ba1e11b181345b11b4d46266e7b359f074a500c8857d79ba60f64262d662ccd9c8489a4c19df67437db193f95b9765181d9152262b1166f97be53497f001cb1be79024d6a2289bcc704e1b1d821015366a3cc8a484e6bc2e1f1b889f19323e3101aa09ad9ea62ba4005039bbfb5998055f93fbf77b14433116d5958422654dada1127213f02b78717a5a0454271d5b0c02517a6c27a3c3610101d753c09a25571775477dc13b2e404db4965b9a9350330c73a8a3642d39af8a23839ab85c6355b12f279f849813c280d54c5913e99b6946a0aaf012c8cab025396b255f002d837c761d42a4aeb38c5f456aaf79e162700c6b4048eca6f9a7367f90238d67bcf8e6a0d8a553c071522f9d2394e28483d2048be2a8f9c8c8e39991a41273c7eacaefc6a308be870b45b41176412954a1a0fd83d362a5ab288663dec5456b6286d0b2cecb01922fb3d473802ea2b86639bce02450339261cffb114e1e725e90677826a1688f686b29a78779c9822315dafc55753e98c8ed3221f2b3220805c8a28983355207da36fb72f9bc85c0a13b9d041586fd583feb12afd5a402dd33b43543f5fa4eb436c8d
Secret Key: d6eccd635a4f19d80256bc9ca3c23deb783e2e16937ea151e136648db4cfa173c618552b57221ce3e43244d078f5c77a47b1a27b23bc7afc2b0a7991cf5a0a8e712cbd9c2f41250a6beb7cac3bc0e42bb446f3511f8a369b6082ba4477305ccaad9864bc3a4a15a6495644368028a4597ba78cb27a86e64333890f2783a8202a3fa018b100d1cbc49622e16a818a681d242a964ff8859b637b59a047f40cccd5d66770c08fb2b2c2eb538c6cd230b792448ee4acbebbc7ff57a798b296b596c858e85760f96e8eb0cac1380cfa20024d4aaa56c48031e4767fc544d982a72d135f56c24d5e157fdae24010c3b8a6c26a2f8713e82711f138906b020d8ef4a2676b1621fb38c9565512259c6d9ca54f64cf5f4b0860eb016caca6007db79e5890d9da874bf30bc53bba3de17ecf48c52dd028e92bb4edd75ec1b952fed596e1bb1507b3644f956ed4e8c352b61edc740fcee65cd907552562a31bb6898f0c17bcf894537b94d6c18f270a9b8b760a5be29ba4e61f9a0873459351174330c7a863b6d788c4895bb62058b8d5982fe525f88744bfa87f3bf223a967674d9601f22c022a149bdfc45bee5589a802996876471c36ab6fa31eec30b4324aa5a03cb29f93738e7519b1eb39b69b7092a9590fca8789978a61511df5ab7f38804255625151034e75244c7cf46a41e2a7447015c4109683714271fcb97fe8a1c2594f886161f5c36d022bc43c692ade56893b3341e63a01da870452fb7129cca4296a6fab49bc9e551ad40ab3067c679362c3e3c53191fa77e753ca69c092dad30032d665a237ce55f1044050c1000b8291c14b3fca500835711bc53df275996420892fac8a208683432c0854320d707985b35ba6aea0290f33108a29450edcc69613a00d1aa49a3304c5691eb4d6c3c0f32d4ab47e21184169b5a6e9fa89424cbfc49812304479d4411574320b45a10f21a352f412c4ae4305a09a801d8a6e211623c3207a3d893e98cc18709689f040561845cca42c154a2b04c912c39dc4831e14421fa2a9dbc322cc742aa78c8f1b7c3dac75bc596c8697d96d1af67365b621c6e7625fc44b99d7584f38cd28360cc5625a905b96af12930ed5b5fe2a82fc5aa7dc4b829fe37635f13f5af2a6d3081dad878785698a0aa914374c4e43b89f094a7892aa149a38b49c06a068d829a8d249e753a375d097a0f162e6c3a4dfe8c79761410c605ed3899a3fc44378e14f28879e8f148077e6bc3bb2ae56178c491611bf6aaf5f9a9cb9b5659223007940bcd6f8a23280a56015330e8577259587b12606f4c937ea13606cb3bb046066ad294261e2b22022bcc74678a5520570d88e4ceb42692631e7e3711c4b2fd5347f0328598340cb3c65c8f55ac02716831094cb6eb90f175b173d9c650329aaf513633633bb2ce6858e7447abc41b6fb06da8782572c332b09660366926bf529ed8caaa6243ccdb152b36ba6e47c714145c86f5b3b61de84ef1470d03fa0135e35194fa1fb3bc860fa500d1299aee88ce56054376c1199c553dd90a8d6f9cc763c811d0c66da6f851abf1056635a34a68aa7815868f153a3a5c77fcc8b1eb1807fbf62a6fb43b355700e78230943a2ba1e11b181345b11b4d46266e7b359f074a500c8857d79ba60f64262d662ccd9c8489a4c19df67437db193f95b9765181d9152262b1166f97be53497f001cb1be79024d6a2289bcc704e1b1d821015366a3cc8a484e6bc2e1f1b889f19323e3101aa09ad9ea62ba4005039bbfb5998055f93fbf77b14433116d5958422654dada1127213f02b78717a5a0454271d5b0c02517a6c27a3c3610101d753c09a25571775477dc13b2e404db4965b9a9350330c73a8a3642d39af8a23839ab85c6355b12f279f849813c280d54c5913e99b6946a0aaf012c8cab025396b255f002d837c761d42a4aeb38c5f456aaf79e162700c6b4048eca6f9a7367f90238d67bcf8e6a0d8a553c071522f9d2394e28483d2048be2a8f9c8c8e39991a41273c7eacaefc6a308be870b45b41176412954a1a0fd83d362a5ab288663dec5456b6286d0b2cecb01922fb3d473802ea2b86639bce02450339261cffb114e1e725e90677826a1688f686b29a78779c9822315dafc55753e98c8ed3221f2b3220805c8a28983355207da36fb72f9bc85c0a13b9d041586fd583feb12afd5a402dd33b43543f5fa4eb436c8d23497b31279a8b715f912f30a181666270913bbd72598eb9cd65a6da680f5c6b3e2a2ea6c9c476fc4937b013c993a793d6c0ab9960695ba838f649da539ca3d0
bac5ba881dd35c59719670004692d675b83c98db6a0e55800bafeb7e70491bf4
Ciphertext: c832cea277dcfb4aa23151db2b58c6ec0eb3ceb01b3d0b6aa130a2f94b451557d24a0edcf6525d3f4c3a60214a4772105b21bed1d4105e4567290ad64c14b32e5f4677d17612559bdbe05bdb4e19a4e6f80ceeafa298c95c42a570bee36d94a4d120e83cc524da06b9c56e8760fc5cc2c3a33c768d742ecbcd4742e240c2bbf5f29ba7c941da5ecb04d133c08f662bb84810ec6a0a90e8075f934449f6a24e4d8c84effb9d93c232286e911367558bd2b3ff3a4580c5e3b59790a550a63e3f945a6745bd3ee26a265f0734cecf87dd4b4f3d6fb076b6b20de643b36e9c84ec9d5103afed796672b24bc6ec980c9d1f73db634454aa977668dfccc988c5ff9f1c62554fa7b438722a2edb180eacd37c85d907f3f3a1ef8b3d94dca9fdf7522b8700e64cbd0b199a9892b4144db3131931501b7a1850432fbd3a954554cafeb8f1de1a9167652dd068c26c61d1d9a51d4e1dc5d7e8bb1d368b798831cbc4b051edc55b2b6236ca6ad0d59ed2b5b9ebdd7c1e816f8c2111db198fbeaf25b134fe9e57dd87479e9136572b181b307b346fec30be8c8e032094ec03cbfd2ee5d0f7b7055ee7346f2a4394399497d1dc9399f0577e8230e7ac067b9cabad993b6e0f5ac512c870fe76286fc4bd173b0341f627f695c6464649dc01e9422abd8471e988e028a03f5217c16b4169598152f0dcf9d78bd390bc9d6ae62a885ee291f145e1c6d37d432a129039854238b62bed00ab3dad389af8c5385ab613fa18f9b7463324d82e12dcccf45327f6201282586214dc5a1c4c12572fea4e47abe9c1023a9a1ece3fc46019e5e95a428551b1ddc108bfe68a117229ebae81f3829e70ce953e81a58986db1452e819518b1095c886d86e12395679e33227d724102b38211e812f95897265d40b62caa435438882069e33c0bdf886d14b6f26b61317581513ea625cdfef4d21344f9c10192e6f8c03fa354a067c289572d5062d4c9ad3048f54138211afa19feaf39ea444f3774a74a6a868e126b7a5c7b4e1dbb9cf1c949e2a072cff6c943c1b723cd6273c4bc4468991e4a4ceca6e1c4bcd42fa6fc7c73002
Shared Secret B: 8a627b20f82f8d9d72915148446d2aa1e2533cec93ecf99ff9d1c7c59c0a115b
Shared Secret A: 8a627b20f82f8d9d72915148446d2aa1e2533cec93ecf99ff9d1c7c59c0a115b

これが一番重要かもしれない。
公開鍵、秘密鍵、共有された鍵の例が表示される。決定的な乱数を用いており、テストベクタとして使える。

test_speed

ref以下はデフォルトではtest_speedはビルドされないので、make speedして生成する。

実行結果
~/prj/kyber/ref$ ./test_speed512
gen_a: 
median: 17006 cycles/ticks
average: 16105 cycles/ticks

poly_getnoise_eta1: 
median: 2109 cycles/ticks
average: 2104 cycles/ticks

poly_getnoise_eta2: 
median: 1102 cycles/ticks
average: 1104 cycles/ticks

NTT: 
median: 3812 cycles/ticks
average: 3817 cycles/ticks

INVNTT: 
median: 5509 cycles/ticks
average: 5540 cycles/ticks

polyvec_basemul_acc_montgomery: 
median: 4963 cycles/ticks
average: 4963 cycles/ticks

poly_tomsg: 
median: 353 cycles/ticks
average: 355 cycles/ticks

poly_frommsg: 
median: 172 cycles/ticks
average: 172 cycles/ticks

poly_compress: 
median: 298 cycles/ticks
average: 297 cycles/ticks

poly_decompress: 
median: 50 cycles/ticks
average: 50 cycles/ticks

polyvec_compress: 
median: 1013 cycles/ticks
average: 1013 cycles/ticks

polyvec_decompress: 
median: 767 cycles/ticks
average: 766 cycles/ticks

indcpa_keypair: 
median: 51704 cycles/ticks
average: 52170 cycles/ticks

indcpa_enc: 
median: 57299 cycles/ticks
average: 57867 cycles/ticks

indcpa_dec: 
median: 19458 cycles/ticks
average: 19513 cycles/ticks

kyber_keypair: 
median: 57365 cycles/ticks
average: 57663 cycles/ticks

kyber_encaps: 
median: 70954 cycles/ticks
average: 71139 cycles/ticks

kyber_decaps: 
median: 83236 cycles/ticks
average: 84264 cycles/ticks

kex_uake_initA: 
median: 128203 cycles/ticks
average: 130256 cycles/ticks

kex_uake_sharedB: 
median: 154199 cycles/ticks
average: 155527 cycles/ticks

kex_uake_sharedA: 
median: 84504 cycles/ticks
average: 86562 cycles/ticks

kex_ake_initA: 
median: 128576 cycles/ticks
average: 135611 cycles/ticks

kex_ake_sharedB: 
median: 224085 cycles/ticks
average: 228173 cycles/ticks

kex_ake_sharedA: 
median: 168058 cycles/ticks
average: 172708 cycles/ticks

いろいろ計測されている（デフォルトは1000回平均）が、重要なのはkyber_keypair, kyber_encaps, kyber_decapsだろう。512をi7-14700Kで計測した結果は以下（秒は3.4GHzで計算）

kyber_keypair kyber_encaps kyber_decaps
ref 57663 cycles
(16.9 us)		 71139 cycles
(20.9 us)		 84264 cycles
(24.7 us)
avx2 11423 cycles
(3.3 us)		 17072 cycles
(5.0 us)		 13613 cycles
(4.0 us)

鍵交換で5マイクロ秒程度なので、十分現実的な範囲ですね。実用上のネックとなるのはやはり速度よりも、鍵と暗号文サイズか。。。

あとがき

今回の話とは全然関係ないが、参考になりそうなリンク
https://qiita.com/kj1/items/8531feac2f3a56e6d6d9

Discussion