【耐量子計算機暗号・PQC】CRYSTALS Kyber動かしてみた
そろそろ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
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
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
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
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マイクロ秒程度なので、十分現実的な範囲ですね。実用上のネックとなるのはやはり速度よりも、鍵と暗号文サイズか。。。
あとがき
今回の話とは全然関係ないが、参考になりそうなリンク
Discussion