【源码解析】Kyber(ML-KEM)源码解析

移动安全 3天前 admin

5 0 0

【源码解析】Kyber(ML-KEM)源码解析

上一篇文章，我们讲解完成了Dilithium的源码，那么，本篇文章呢，接着来顺道的看一下Kyber吧，有了前面Dilithium的基础，来看这个，就简单了很多，这次基于的代码呢，是标准的ML-KEM[1]。

注意，这里是一个KEM算法，也就是密钥封装机制(Key encapsulation mechanism)，具体这个的含义呢，我们有机会再来聊，现在，可以简单理解，最终，算法会传递一个秘密的信息。

环境搭建

这里，我们直接用标准的实现了，因为，偶然的机会，我翻到了pq-crystals给出的标准实现，所以呢，这里我们就看下标准的实现吧，上次为啥没写呢，因为上次，没找到，其实也是有的，这不就，又可以，再来多水一篇文章了嘛，等带着看看，具体实现的细节差异，好了，这是后话了，我们还是回归到本篇文章的主题上来。

这里，直接git clone源码就可以了，然后，具体环境和上一篇文章一致[3]，这里就不再啰嗦了，捎带，可以看下我之前写的文章。

项目结构

这里的项目结构，就比较清晰了，这里，代码都在ref这个文件夹下，而对于avx2这个里面，是针对于x86平台的汇编加速，本篇文章，我们就先不去描述了，然后针对于这个目录来说，就没有太多的信息了，这里，如果要运行，直接采用Clion打开ref这个文件夹就好了。

目录结构

.
├── Makefile
├── api.h
├── cbd.c
├── cbd.h
├── fips202.c
├── fips202.h
├── indcpa.c
├── indcpa.h
├── kem.c
├── kem.h
├── nistkat
│   ├── PQCgenKAT_kem.c
│   ├── rng.c
│   └── rng.h
├── ntt.c
├── ntt.h
├── params.h
├── poly.c
├── poly.h
├── polyvec.c
├── polyvec.h
├── randombytes.c
├── randombytes.h
├── reduce.c
├── reduce.h
├── symmetric-shake.c
├── symmetric.h
├── test
│   ├── cpucycles.c
│   ├── cpucycles.h
│   ├── speed_print.c
│   ├── speed_print.h
│   ├── test_kyber.c
│   ├── test_speed.c
│   └── test_vectors.c
├── verify.c
└── verify.h

这个目录，我们简单来看一下，test顾名思义，就是一些测试文件，主要是针对速度，向量，以及运行结果的测试的代码，然后nistkat，这个就是生成KAT的代码，不是重点，剩余的代码，就都是重点了，哈哈，不要怕，有了上一篇文章的铺垫呢，这一篇文章，就会好理解很多。

实现案例

这里，我们还是需要运行，因此，这里，还是简单写一个样例代码，这里其实，可以直接借鉴test/test_kyber.c的代码。

//
// Created by littleq
//

#include <stdio.h>
#include <string.h>
#include "../kem.h"

static void printArrayHex(const uint8_t m[], size_t length) {
  for (size_t i = 0; i < length; i++) {
    printf("%02X", m[i]);
  }
  printf("n");
}

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);
  printArrayHex(pk, CRYPTO_PUBLICKEYBYTES);

  //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 keysn");
    return 1;
  }

  return 0;
}

int main(void) {
  test_keys();
  return 0;
}

运行，也非常的简单，简单写一个Makefile就可以了。

examples/main: $(SOURCESKECCAK) $(HEADERSKECCAK) examples/main.c
  $(CC) $(NISTFLAGS) -DKYBER_K=2 -o $@ $(SOURCESKECCAK) nistkat/rng.c examples/main.c $(LDFLAGS) -lcrypto

参数设置

这里，对于ML-KEM来说，也是分了三个安全层级，，这三个也只是规模不同，具体如下表所示

	n	q	k	eta_1	eta_1	d_u	d_v	RBG strength
ML-KEM-512	256	3329	2	3	2	10	4	128
ML-KEM-768	256	3329	3	2	2	10	4	192
ML-KEM-1024	256	3329	4	2	2	11	5	256

参数不同，对应的密钥长度，密文长度也有不同，具体如下表所示

	Encapsulation Key	Decapsulation Key	ciphertext	shared secret key
ML-KEM-512	800	1632	768	32
ML-KEM-768	1184	2400	1088	32
ML-KEM-1024	1568	3168	1568	32

这里，对应源码当中params.h这个文件，这里根据编译参数KYBER_K来确定具体的参数。

#ifndef PARAMS_H
#define PARAMS_H

#ifndef KYBER_K
#define KYBER_K 3  /* Change this for different security strengths */
#endif


/* Don't change parameters below this line */
#if   (KYBER_K == 2)
#define KYBER_NAMESPACE(s) pqcrystals_kyber512_ref_##s
#elif (KYBER_K == 3)
#define KYBER_NAMESPACE(s) pqcrystals_kyber768_ref_##s
#elif (KYBER_K == 4)
#define KYBER_NAMESPACE(s) pqcrystals_kyber1024_ref_##s
#else
#error "KYBER_K must be in {2,3,4}"
#endif

#define KYBER_N 256
#define KYBER_Q 3329

#define KYBER_SYMBYTES 32   /* size in bytes of hashes, and seeds */
#define KYBER_SSBYTES  32   /* size in bytes of shared key */

#define KYBER_POLYBYTES    384
#define KYBER_POLYVECBYTES  (KYBER_K * KYBER_POLYBYTES)

#if KYBER_K == 2
#define KYBER_ETA1 3
#define KYBER_POLYCOMPRESSEDBYTES    128
#define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 320)
#elif KYBER_K == 3
#define KYBER_ETA1 2
#define KYBER_POLYCOMPRESSEDBYTES    128
#define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 320)
#elif KYBER_K == 4
#define KYBER_ETA1 2
#define KYBER_POLYCOMPRESSEDBYTES    160
#define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 352)
#endif

#define KYBER_ETA2 2

#define KYBER_INDCPA_MSGBYTES       (KYBER_SYMBYTES)
#define KYBER_INDCPA_PUBLICKEYBYTES (KYBER_POLYVECBYTES + KYBER_SYMBYTES)
#define KYBER_INDCPA_SECRETKEYBYTES (KYBER_POLYVECBYTES)
#define KYBER_INDCPA_BYTES          (KYBER_POLYVECCOMPRESSEDBYTES + KYBER_POLYCOMPRESSEDBYTES)

#define KYBER_PUBLICKEYBYTES  (KYBER_INDCPA_PUBLICKEYBYTES)
/* 32 bytes of additional space to save H(pk) */
#define KYBER_SECRETKEYBYTES  (KYBER_INDCPA_SECRETKEYBYTES + KYBER_INDCPA_PUBLICKEYBYTES + 2*KYBER_SYMBYTES)
#define KYBER_CIPHERTEXTBYTES (KYBER_INDCPA_BYTES)

#endif

API

然后，我们，还是先来看一下，有哪些API。

#ifndef API_H
#define API_H

#include <stdint.h>

#define pqcrystals_kyber512_SECRETKEYBYTES 1632
#define pqcrystals_kyber512_PUBLICKEYBYTES 800
#define pqcrystals_kyber512_CIPHERTEXTBYTES 768
#define pqcrystals_kyber512_KEYPAIRCOINBYTES 64
#define pqcrystals_kyber512_ENCCOINBYTES 32
#define pqcrystals_kyber512_BYTES 32

#define pqcrystals_kyber512_ref_SECRETKEYBYTES pqcrystals_kyber512_SECRETKEYBYTES
#define pqcrystals_kyber512_ref_PUBLICKEYBYTES pqcrystals_kyber512_PUBLICKEYBYTES
#define pqcrystals_kyber512_ref_CIPHERTEXTBYTES pqcrystals_kyber512_CIPHERTEXTBYTES
#define pqcrystals_kyber512_ref_KEYPAIRCOINBYTES pqcrystals_kyber512_KEYPAIRCOINBYTES
#define pqcrystals_kyber512_ref_ENCCOINBYTES pqcrystals_kyber512_ENCCOINBYTES
#define pqcrystals_kyber512_ref_BYTES pqcrystals_kyber512_BYTES

int pqcrystals_kyber512_ref_keypair_derand(uint8_t *pk, uint8_t *sk, const uint8_t *coins);
int pqcrystals_kyber512_ref_keypair(uint8_t *pk, uint8_t *sk);
int pqcrystals_kyber512_ref_enc_derand(uint8_t *ct, uint8_t *ss, const uint8_t *pk, const uint8_t *coins);
int pqcrystals_kyber512_ref_enc(uint8_t *ct, uint8_t *ss, const uint8_t *pk);
int pqcrystals_kyber512_ref_dec(uint8_t *ss, const uint8_t *ct, const uint8_t *sk);

#define pqcrystals_kyber768_SECRETKEYBYTES 2400
#define pqcrystals_kyber768_PUBLICKEYBYTES 1184
#define pqcrystals_kyber768_CIPHERTEXTBYTES 1088
#define pqcrystals_kyber768_KEYPAIRCOINBYTES 64
#define pqcrystals_kyber768_ENCCOINBYTES 32
#define pqcrystals_kyber768_BYTES 32

#define pqcrystals_kyber768_ref_SECRETKEYBYTES pqcrystals_kyber768_SECRETKEYBYTES
#define pqcrystals_kyber768_ref_PUBLICKEYBYTES pqcrystals_kyber768_PUBLICKEYBYTES
#define pqcrystals_kyber768_ref_CIPHERTEXTBYTES pqcrystals_kyber768_CIPHERTEXTBYTES
#define pqcrystals_kyber768_ref_KEYPAIRCOINBYTES pqcrystals_kyber768_KEYPAIRCOINBYTES
#define pqcrystals_kyber768_ref_ENCCOINBYTES pqcrystals_kyber768_ENCCOINBYTES
#define pqcrystals_kyber768_ref_BYTES pqcrystals_kyber768_BYTES

int pqcrystals_kyber768_ref_keypair_derand(uint8_t *pk, uint8_t *sk, const uint8_t *coins);
int pqcrystals_kyber768_ref_keypair(uint8_t *pk, uint8_t *sk);
int pqcrystals_kyber768_ref_enc_derand(uint8_t *ct, uint8_t *ss, const uint8_t *pk, const uint8_t *coins);
int pqcrystals_kyber768_ref_enc(uint8_t *ct, uint8_t *ss, const uint8_t *pk);
int pqcrystals_kyber768_ref_dec(uint8_t *ss, const uint8_t *ct, const uint8_t *sk);

#define pqcrystals_kyber1024_SECRETKEYBYTES 3168
#define pqcrystals_kyber1024_PUBLICKEYBYTES 1568
#define pqcrystals_kyber1024_CIPHERTEXTBYTES 1568
#define pqcrystals_kyber1024_KEYPAIRCOINBYTES 64
#define pqcrystals_kyber1024_ENCCOINBYTES 32
#define pqcrystals_kyber1024_BYTES 32

#define pqcrystals_kyber1024_ref_SECRETKEYBYTES pqcrystals_kyber1024_SECRETKEYBYTES
#define pqcrystals_kyber1024_ref_PUBLICKEYBYTES pqcrystals_kyber1024_PUBLICKEYBYTES
#define pqcrystals_kyber1024_ref_CIPHERTEXTBYTES pqcrystals_kyber1024_CIPHERTEXTBYTES
#define pqcrystals_kyber1024_ref_KEYPAIRCOINBYTES pqcrystals_kyber1024_KEYPAIRCOINBYTES
#define pqcrystals_kyber1024_ref_ENCCOINBYTES pqcrystals_kyber1024_ENCCOINBYTES
#define pqcrystals_kyber1024_ref_BYTES pqcrystals_kyber1024_BYTES

int pqcrystals_kyber1024_ref_keypair_derand(uint8_t *pk, uint8_t *sk, const uint8_t *coins);
int pqcrystals_kyber1024_ref_keypair(uint8_t *pk, uint8_t *sk);
int pqcrystals_kyber1024_ref_enc_derand(uint8_t *ct, uint8_t *ss, const uint8_t *pk, const uint8_t *coins);
int pqcrystals_kyber1024_ref_enc(uint8_t *ct, uint8_t *ss, const uint8_t *pk);
int pqcrystals_kyber1024_ref_dec(uint8_t *ss, const uint8_t *ct, const uint8_t *sk);

#endif

这里，三个不同的安全分类，都在一个文件夹内，由于其他的都只是规模不同，这里本文后面以 ML-KEM-512为例来进行分析，为了简单起见，我们将省略具体的长度，不做特殊说明，都是指512。

crypto_kem_keypair_derand和crypto_kem_keypair用于生成密钥，这两个的区别是第一个需要自己传入初始的种子，第二个则利用randombytes函数来直接自动生成种子
crypto_kem_enc_derand和crypto_kem_enc这个用于加密，区别和上面是一样的，一个是需要自己传入种子，另一个则自动生成
crypto_kem_dec解密算法，解密获得共享的秘密信息

这里，我们先简单的看下，每个函数的作用，具体详细的分析，我们在后文中描述。

源码解析

和之前的文章一样，我们还是将源码分为几部分来进行描述，还是先来讲解一下里面用到的一些函数，因为本身Kyber也是基于模下的运算，其中核心也还是多项式的运算，只不过这里多项式的系数范围和Dilithium有些不同，这里多项式的运算还是在poly.c下，而对于Pack和Unpack函数，具体作用也相同，因此这两部分，不在本文过多描述了。

PRF函数

这里，用到了PRF函数，也就是伪随机数函数簇(Pseudorandom function family), 主要用来生成对应矩阵，以及进行秘密信息的生成，这里采用了shake, 其实也就是sha3的结构，具体用到的规模如下

#ifndef SYMMETRIC_H
#define SYMMETRIC_H

#include <stddef.h>
#include <stdint.h>
#include "params.h"

#include "fips202.h"

typedef keccak_state xof_state;

#define kyber_shake128_absorb KYBER_NAMESPACE(kyber_shake128_absorb)
void kyber_shake128_absorb(keccak_state *s,
                           const uint8_t seed[KYBER_SYMBYTES],
                           uint8_t x,
                           uint8_t y);

#define kyber_shake256_prf KYBER_NAMESPACE(kyber_shake256_prf)
void kyber_shake256_prf(uint8_t *out, size_t outlen, const uint8_t key[KYBER_SYMBYTES], uint8_t nonce);

#define kyber_shake256_rkprf KYBER_NAMESPACE(kyber_shake256_rkprf)
void kyber_shake256_rkprf(uint8_t out[KYBER_SSBYTES], const uint8_t key[KYBER_SYMBYTES], const uint8_t input[KYBER_CIPHERTEXTBYTES]);

#define XOF_BLOCKBYTES SHAKE128_RATE

#define hash_h(OUT, IN, INBYTES) sha3_256(OUT, IN, INBYTES)
#define hash_g(OUT, IN, INBYTES) sha3_512(OUT, IN, INBYTES)
#define xof_absorb(STATE, SEED, X, Y) kyber_shake128_absorb(STATE, SEED, X, Y)
#define xof_squeezeblocks(OUT, OUTBLOCKS, STATE) shake128_squeezeblocks(OUT, OUTBLOCKS, STATE)
#define prf(OUT, OUTBYTES, KEY, NONCE) kyber_shake256_prf(OUT, OUTBYTES, KEY, NONCE)
#define rkprf(OUT, KEY, INPUT) kyber_shake256_rkprf(OUT, KEY, INPUT)

#endif /* SYMMETRIC_H */

这里，并没有提供AES的实现，但是在之前，提交的代码当中有90s版本是有AES的实现的，这里，标准里面给的例子也没有提及AES, 在之前提交当中是可以用的，这个代码里面没支持，要注意下区别，这些函数，没有特别值得描述的，本身就是SHA3里面的海绵算法结构。

再有，其他的函数，就是矩阵派生函数等其他的辅助函数了，这里，其实用到的内容要比Dilithium少一些的，接下来，我们就来看一下API当中的函数。

密钥生成函数(crypto_kem_keypair)

int crypto_kem_keypair(uint8_t *pk, uint8_t *sk);

pk: 生成的公钥，长度为CRYPTO_PUBLICKEYBYTES
sk: 生成的私钥，长度为CRYPTO_SECRETKEYBYTES

/*************************************************
* Name:        crypto_kem_keypair
*
* Description: Generates public and private key
*              for CCA-secure Kyber key encapsulation mechanism
*
* Arguments:   - uint8_t *pk: pointer to output public key
*                (an already allocated array of KYBER_PUBLICKEYBYTES bytes)
*              - uint8_t *sk: pointer to output private key
*                (an already allocated array of KYBER_SECRETKEYBYTES bytes)
*
* Returns 0 (success)
**************************************************/
int crypto_kem_keypair(uint8_t *pk,
                       uint8_t *sk)
{
  uint8_t coins[2*KYBER_SYMBYTES];
  randombytes(coins, 2*KYBER_SYMBYTES);
  crypto_kem_keypair_derand(pk, sk, coins);
  return 0;
}

这里，文章开头已经说过了，这个就是通过randombytes生成的随机种子，传递给crypto_kem_keypair_derand函数，因此，我们来看一下

int crypto_kem_keypair_derand(uint8_t *pk,
                              uint8_t *sk,
                              const uint8_t *coins)
{
  indcpa_keypair_derand(pk, sk, coins);
  memcpy(sk+KYBER_INDCPA_SECRETKEYBYTES, pk, KYBER_PUBLICKEYBYTES);
  hash_h(sk+KYBER_SECRETKEYBYTES-2*KYBER_SYMBYTES, pk, KYBER_PUBLICKEYBYTES);
  /* Value z for pseudo-random output on reject */
  memcpy(sk+KYBER_SECRETKEYBYTES-KYBER_SYMBYTES, coins+KYBER_SYMBYTES, KYBER_SYMBYTES);
  return 0;
}

这里，有个核心是indcpa_keypair_derand, 生成公钥和私钥，但是最终的私钥是拼接而成，具体如下

这里，最后是一个随机数，用于后续的implicit rejection，因此，可以注意到，最开始传入的种子是两倍的原因，就在这里。那么接下来，我们简单来看一下 indcpa_keypair_derand 函数。

/*************************************************
* Name:        indcpa_keypair_derand
*
* Description: Generates public and private key for the CPA-secure
*              public-key encryption scheme underlying Kyber
*
* Arguments:   - uint8_t *pk: pointer to output public key
*                             (of length KYBER_INDCPA_PUBLICKEYBYTES bytes)
*              - uint8_t *sk: pointer to output private key
*                             (of length KYBER_INDCPA_SECRETKEYBYTES bytes)
*              - const uint8_t *coins: pointer to input randomness
*                             (of length KYBER_SYMBYTES bytes)
**************************************************/
void indcpa_keypair_derand(uint8_t pk[KYBER_INDCPA_PUBLICKEYBYTES],
                           uint8_t sk[KYBER_INDCPA_SECRETKEYBYTES],
                           const uint8_t coins[KYBER_SYMBYTES])
{
  unsigned int i;
  uint8_t buf[2*KYBER_SYMBYTES];
  const uint8_t *publicseed = buf;
  const uint8_t *noiseseed = buf+KYBER_SYMBYTES;
  uint8_t nonce = 0;
  polyvec a[KYBER_K], e, pkpv, skpv;

  memcpy(buf, coins, KYBER_SYMBYTES);
  buf[KYBER_SYMBYTES] = KYBER_K;
  hash_g(buf, buf, KYBER_SYMBYTES+1);

  gen_a(a, publicseed);

  for(i=0;i<KYBER_K;i++)
    poly_getnoise_eta1(&skpv.vec[i], noiseseed, nonce++);
  for(i=0;i<KYBER_K;i++)
    poly_getnoise_eta1(&e.vec[i], noiseseed, nonce++);

  polyvec_ntt(&skpv);
  polyvec_ntt(&e);

  // matrix-vector multiplication
  for(i=0;i<KYBER_K;i++) {
    polyvec_basemul_acc_montgomery(&pkpv.vec[i], &a[i], &skpv);
    poly_tomont(&pkpv.vec[i]);
  }

  polyvec_add(&pkpv, &pkpv, &e);
  polyvec_reduce(&pkpv);

  pack_sk(sk, &skpv);
  pack_pk(pk, &pkpv, publicseed);
}

我们，捎带着，回顾一下密钥生成算法的步骤吧

生成两个32字节的随机数，通过传入的种子+安全分类, 这里，也就是第25~27行代码的作用，注意这里其实和提交的有差异的，当时提交的时候，没有拼接这个，哎这都说出来差异了，不好再水一篇文章了，哈哈。
生成矩阵A, 也就是29行，这里生成的直接就是NTT表示
生成s和e, 这里采用的是中心二项分布的采样方式(centered binomial distribution), 并将其转换为NTT的表示
计算: , 这里运算是NTT表示下的结果
最终，输出公钥和私钥

这里，实际上，也是可以用最开始的种子直接生成私钥的，但是原因应该和Dilithium一样吧，我猜。

加密函数(crypto_kem_enc)

还是，先来看一下函数的签名

int crypto_kem_enc(uint8_t *ct, uint8_t *ss, const uint8_t *pk);

ct: 输出的密文，长度为CRYPTO_CIPHERTEXTBYTES
ss: 共享的密钥，这里是32字节
pk: 公钥（打包后）

/*************************************************
* Name:        crypto_kem_enc
*
* Description: Generates cipher text and shared
*              secret for given public key
*
* Arguments:   - uint8_t *ct: pointer to output cipher text
*                (an already allocated array of KYBER_CIPHERTEXTBYTES bytes)
*              - uint8_t *ss: pointer to output shared secret
*                (an already allocated array of KYBER_SSBYTES bytes)
*              - const uint8_t *pk: pointer to input public key
*                (an already allocated array of KYBER_PUBLICKEYBYTES bytes)
*
* Returns 0 (success)
**************************************************/
int crypto_kem_enc(uint8_t *ct,
                   uint8_t *ss,
                   const uint8_t *pk)
{
  uint8_t coins[KYBER_SYMBYTES];
  randombytes(coins, KYBER_SYMBYTES);
  crypto_kem_enc_derand(ct, ss, pk, coins);
  return 0;
}

这里，和之前的密钥生成一样，也需要一个种子，然后，我们直接来看crypto_kem_enc_derand

/*************************************************
* Name:        crypto_kem_enc_derand
*
* Description: Generates cipher text and shared
*              secret for given public key
*
* Arguments:   - uint8_t *ct: pointer to output cipher text
*                (an already allocated array of KYBER_CIPHERTEXTBYTES bytes)
*              - uint8_t *ss: pointer to output shared secret
*                (an already allocated array of KYBER_SSBYTES bytes)
*              - const uint8_t *pk: pointer to input public key
*                (an already allocated array of KYBER_PUBLICKEYBYTES bytes)
*              - const uint8_t *coins: pointer to input randomness
*                (an already allocated array filled with KYBER_SYMBYTES random bytes)
**
* Returns 0 (success)
**************************************************/
int crypto_kem_enc_derand(uint8_t *ct,
                          uint8_t *ss,
                          const uint8_t *pk,
                          const uint8_t *coins)
{
  uint8_t buf[2*KYBER_SYMBYTES];
  /* Will contain key, coins */
  uint8_t kr[2*KYBER_SYMBYTES];

  memcpy(buf, coins, KYBER_SYMBYTES);

  /* Multitarget countermeasure for coins + contributory KEM */
  hash_h(buf+KYBER_SYMBYTES, pk, KYBER_PUBLICKEYBYTES);
  hash_g(kr, buf, 2*KYBER_SYMBYTES);

  /* coins are in kr+KYBER_SYMBYTES */
  indcpa_enc(ct, buf, pk, kr+KYBER_SYMBYTES);

  memcpy(ss,kr,KYBER_SYMBYTES);
  return 0;
}

在加密之前，需要先扩展出来共享的秘密信息K, 也就是前面kr的生成过程（30~31），然后，我们来看后续的加密过程indcpa_enc函数。

/*************************************************
* Name:        indcpa_enc
*
* Description: Encryption function of the CPA-secure
*              public-key encryption scheme underlying Kyber.
*
* Arguments:   - uint8_t *c: pointer to output ciphertext
*                            (of length KYBER_INDCPA_BYTES bytes)
*              - const uint8_t *m: pointer to input message
*                                  (of length KYBER_INDCPA_MSGBYTES bytes)
*              - const uint8_t *pk: pointer to input public key
*                                   (of length KYBER_INDCPA_PUBLICKEYBYTES)
*              - const uint8_t *coins: pointer to input random coins used as seed
*                                      (of length KYBER_SYMBYTES) to deterministically
*                                      generate all randomness
**************************************************/
void indcpa_enc(uint8_t c[KYBER_INDCPA_BYTES],
                const uint8_t m[KYBER_INDCPA_MSGBYTES],
                const uint8_t pk[KYBER_INDCPA_PUBLICKEYBYTES],
                const uint8_t coins[KYBER_SYMBYTES])
{
  unsigned int i;
  uint8_t seed[KYBER_SYMBYTES];
  uint8_t nonce = 0;
  polyvec sp, pkpv, ep, at[KYBER_K], b;
  poly v, k, epp;

  unpack_pk(&pkpv, seed, pk);
  poly_frommsg(&k, m);
  gen_at(at, seed);

  for(i=0;i<KYBER_K;i++)
    poly_getnoise_eta1(sp.vec+i, coins, nonce++);
  for(i=0;i<KYBER_K;i++)
    poly_getnoise_eta2(ep.vec+i, coins, nonce++);
  poly_getnoise_eta2(&epp, coins, nonce++);

  polyvec_ntt(&sp);

  // matrix-vector multiplication
  for(i=0;i<KYBER_K;i++)
    polyvec_basemul_acc_montgomery(&b.vec[i], &at[i], &sp);

  polyvec_basemul_acc_montgomery(&v, &pkpv, &sp);

  polyvec_invntt_tomont(&b);
  poly_invntt_tomont(&v);

  polyvec_add(&b, &b, &ep);
  poly_add(&v, &v, &epp);
  poly_add(&v, &v, &k);
  polyvec_reduce(&b);
  poly_reduce(&v);

  pack_ciphertext(c, &b, &v);
}

这里，理解为加密过程就好了，只不过加密的内容是之前扩展出来的K。还是，简单的来回顾一下算法的过程

解包公钥，并计算矩阵A, 这里直接计算的A的转置，因为后面直接用的转置后的矩阵，这里，只需要采样的时候，控制下下标即可
生成采样方式依然是CBD, 具体对应32~36行
计算, 这里，便为加密后的内容
打包明文输出

好了，有关于加密算法，到这里，就讲完了，接下来，我们来看下解密算法，这个相对来说就简单多了。

解密算法(crypto_kem_dec)

int crypto_kem_dec(uint8_t *ss, const uint8_t *ct, const uint8_t *sk);

ss: 最后输出的共享信息
ct: 密文
sk: 打包后的私钥

/*************************************************
* Name:        crypto_kem_dec
*
* Description: Generates shared secret for given
*              cipher text and private key
*
* Arguments:   - uint8_t *ss: pointer to output shared secret
*                (an already allocated array of KYBER_SSBYTES bytes)
*              - const uint8_t *ct: pointer to input cipher text
*                (an already allocated array of KYBER_CIPHERTEXTBYTES bytes)
*              - const uint8_t *sk: pointer to input private key
*                (an already allocated array of KYBER_SECRETKEYBYTES bytes)
*
* Returns 0.
*
* On failure, ss will contain a pseudo-random value.
**************************************************/
int crypto_kem_dec(uint8_t *ss,
                   const uint8_t *ct,
                   const uint8_t *sk)
{
  int fail;
  uint8_t buf[2*KYBER_SYMBYTES];
  /* Will contain key, coins */
  uint8_t kr[2*KYBER_SYMBYTES];
  uint8_t cmp[KYBER_CIPHERTEXTBYTES+KYBER_SYMBYTES];
  const uint8_t *pk = sk+KYBER_INDCPA_SECRETKEYBYTES;

  indcpa_dec(buf, ct, sk);

  /* Multitarget countermeasure for coins + contributory KEM */
  memcpy(buf+KYBER_SYMBYTES, sk+KYBER_SECRETKEYBYTES-2*KYBER_SYMBYTES, KYBER_SYMBYTES);
  hash_g(kr, buf, 2*KYBER_SYMBYTES);

  /* coins are in kr+KYBER_SYMBYTES */
  indcpa_enc(cmp, buf, pk, kr+KYBER_SYMBYTES);

  fail = verify(ct, cmp, KYBER_CIPHERTEXTBYTES);

  /* Compute rejection key */
  rkprf(ss,sk+KYBER_SECRETKEYBYTES-KYBER_SYMBYTES,ct);

  /* Copy true key to return buffer if fail is false */
  cmov(ss,kr,KYBER_SYMBYTES,!fail);

  return 0;
}

这里，核心的解密函数在indcpa_dec, 我们可以通过解密后的sk，来通过和加密一样的派生过程得到kr, 最终得到秘密的信息，因此，接下来，我们就来看一下 indcpa_dec 这个函数。

/*************************************************
* Name:        indcpa_dec
*
* Description: Decryption function of the CPA-secure
*              public-key encryption scheme underlying Kyber.
*
* Arguments:   - uint8_t *m: pointer to output decrypted message
*                            (of length KYBER_INDCPA_MSGBYTES)
*              - const uint8_t *c: pointer to input ciphertext
*                                  (of length KYBER_INDCPA_BYTES)
*              - const uint8_t *sk: pointer to input secret key
*                                   (of length KYBER_INDCPA_SECRETKEYBYTES)
**************************************************/
void indcpa_dec(uint8_t m[KYBER_INDCPA_MSGBYTES],
                const uint8_t c[KYBER_INDCPA_BYTES],
                const uint8_t sk[KYBER_INDCPA_SECRETKEYBYTES])
{
  polyvec b, skpv;
  poly v, mp;

  unpack_ciphertext(&b, &v, c);
  unpack_sk(&skpv, sk);

  polyvec_ntt(&b);
  polyvec_basemul_acc_montgomery(&mp, &skpv, &b);
  poly_invntt_tomont(&mp);

  poly_sub(&mp, &v, &mp);
  poly_reduce(&mp);

  poly_tomsg(m, &mp);
}

还是，先来回顾一下，具体的过程

首先，解包明文和私钥，也就是21~22行的作用
然后，计算
最后，将多项式，转换成为原始的消息，这样就结束了

注意，这里最后，还有一次加密的验证过程，也就是重新执行加密，看结果是否一样，如果不一样，我们最开始说道的那个种子，就用上了，也就是，无论如何，你都能拿到一个秘密信息。

总结

这里，本文主要是针对于ML-KEM算法进行了一个简单的原码分析，如果了解整体结构，理解整个代码，还是相对来说比较容易的，好了，本文到这里就结束了，溜了，源码分析，目前应该是暂时先没了，因为发布的最后一个是基于无状态哈希的，这个我是真的不熟悉（咳咳，paper都没看）, 这个估计一时半会不会来，当然看心情吧，万一哪时候，心情好，或者突然，我看懂了呢，哈哈哈哈，想法很美好，这次真的溜了

参考资料

https://github.com/pq-crystals/kyber
National Institute of Standards and Technology (2024) Module-Lattice-Based KeyEncapsulation Mechanism Standard. (Department of Commerce, Washington, D.C.), Federal Information Processing Standards Publication (FIPS) NIST FIPS 203. https://doi.org/10.6028/NIST.FIPS.203
https://mp.weixin.qq.com/s/SIn8iTfu6Sre6AGL_7ARew

原文始发于微信公众号（Coder小Q）：【源码解析】Kyber(ML-KEM)源码解析

版权声明：admin 发表于 2024年9月26日上午8:31。
转载请注明：【源码解析】Kyber(ML-KEM)源码解析 | CTF导航

Out of the Sandbox: WikiLoader Digs Sophisticated Evasion

admin

178

一道Android逆向题的取巧解题思路

admin

553

frida复现某app算法

admin

378

Egghunt_2.xls恶意宏文档分析【复活节彩蛋】

admin

422

勒索软件Retch和S.H.O概述

admin

「AVSS研报」iOS•Android•鸿蒙安全对抗能力初评报告-内核篇

admin

144

【源码解析】Kyber(ML-KEM)源码解析

【源码解析】Kyber(ML-KEM)源码解析

环境搭建

项目结构

目录结构

实现案例

参数设置

API

源码解析

PRF函数

密钥生成函数(crypto_kem_keypair)

加密函数(crypto_kem_enc)

解密算法(crypto_kem_dec)

总结

参考资料

JAVA安全之Velocity模板注入刨析

pixel5内核build、pixel6 LineageOS编译、motorola救砖

相关文章

相关文章

【源码解析】Kyber(ML-KEM)源码解析

【源码解析】Kyber(ML-KEM)源码解析

环境搭建

项目结构

目录结构

实现案例

参数设置

API

源码解析

PRF函数

密钥生成函数(crypto_kem_keypair)

加密函数(crypto_kem_enc)

解密算法(crypto_kem_dec)

总结

参考资料

JAVA安全之Velocity模板注入刨析

pixel5内核build、pixel6 LineageOS编译、motorola救砖

相关文章

广告位

相关文章