はじめに

2019年のBreaking Bitcoinで、Jonas Schnellが、"Bitcoin P2P Encryption"(Video,Slides,Transcript)という発表をしました。
その中に、"ChaCha20"と"Poly1305"というものについて触れられており、以前から気になっていたので仕様を読みつつJavascriptで実装していこうと思います。

仕様については、RFC-8439を参考にしていきます。

"ChaCha20"は共通鍵暗号（cipher）アルゴリズムで、主流のAESよりも（同じ環境化では）高速です。
"Poly1305"はメッセージ認証符号（authenticator）アルゴリズムで、高速で動き実装も簡単です。
これらを個別に作成し、２つを合わせたAEAD（認証付き暗号:Authenticated Encryption with Associated Data）を作成します。

ChaCha20

ChaCha20は、16個の符号なし32ビット数値（以下、ワード）が１つの状態（state）となります。

クォーターラウンド（Quarter Round）

4個のワードから以下の演算を行います。

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

１つの状態（state）は、16個のワードで構成されています。
そのうち4個を選んで上記演算を行う事をQUARTERROUND(x, y, z, w)と表します。
x,y,z,wは、状態における位置となります。

javascriptで実装してみます。
stateはワードの配列で配列長は16です。
これと、4個の位置（x,y,z,w）を引数とします。
演算後、同じ位置で数値を置き換えます。

function Qround(state, x, y, z, w) {
    let a = state[x]; let b = state[y]; let c = state[z]; let d = state[w];
    a = (a + b) & 0xffffffff; d = d ^ a; d = (d << 16) | (d >>> 16);
    c = (c + d) & 0xffffffff; b = b ^ c; b = (b << 12) | (b >>> 20);
    a = (a + b) & 0xffffffff; d = d ^ a; d = (d << 8) | (d >>> 24);
    c = (c + d) & 0xffffffff; b = b ^ c; b = (b << 7) | (b >>> 25);
    state[x] = a; state[y] = b; state[z] = c; state[w] = d;
}

javascriptは、ビット演算（^,<<,>>>）は、32ビットで演算してくれますが、加算（+）については、javascriptの整数で演算するので32ビット（& 0xffffffff）にする必要があります。

ブロック関数（Block Function）

入力（input）:
256ビットのキー（key）：8個の32ビット数値
32ビットのブロックカウント(block count)：1個の32ビット数値
96ビットのナンス（nonce）：3個の32ビット数値
出力（output）:
64バイト（64個のバイト）

初期化の状態（state）を作成します。16個のワードを以下のような順序で表します。

 0   1   2   3
 4   5   6   7
 8   9  10  11
12  13  14  15

0~3：定数（0x61707865,0x3320646e,0x79622d32,0x6b206574）
4~11：キー（それぞれ、リトリルエンディアンで設定）
12：ブロックカウント
13~15：ナンス（それぞれ、リトリルエンディアンで設定）

定数はSalsa20と同じで、次の文字列を4個のワードでリトルエンディアン表記したものとなっています。
expand 32-byte k→657870616e642033322d62797465206b

以下のようなイメージになります。

cccccccc  cccccccc  cccccccc  cccccccc
kkkkkkkk  kkkkkkkk  kkkkkkkk  kkkkkkkk
kkkkkkkk  kkkkkkkk  kkkkkkkk  kkkkkkkk
bbbbbbbb  nnnnnnnn  nnnnnnnn  nnnnnnnn

c=定数 k=キー b=ブロックカウント n=ナンス

ChaCha20は、「列ラウンド」（column rounds、縦方向）と
「対角ラウンド」（diagonal rounds、斜め方向）を交互に20ラウンド実行します。
各ラウンドは4つのクォーターラウンドを行い、次のように実行されます。

QUARTERROUND(0, 4, 8, 12)
QUARTERROUND(1, 5, 9, 13)
QUARTERROUND(2, 6, 10, 14)
QUARTERROUND(3, 7, 11, 15)
QUARTERROUND(0, 5, 10, 15)
QUARTERROUND(1, 6, 11, 12)
QUARTERROUND(2, 7, 8, 13)
QUARTERROUND(3, 4, 9, 14)

前半の4ラウンドは「列」ラウンド、後半の4ラウンドは「対角線」ラウンドです。
まずは、2回のラウンド（列ラウンドと対角ラウンド）を実装します。

function inner_block(state) {
    Qround(state, 0, 4, 8, 12);
    Qround(state, 1, 5, 9, 13);
    Qround(state, 2, 6, 10, 14);
    Qround(state, 3, 7, 11, 15);
    Qround(state, 0, 5, 10, 15);
    Qround(state, 1, 6, 11, 12);
    Qround(state, 2, 7, 8, 13);
    Qround(state, 3, 4, 9, 14);
}

20ラウンドなので、このinner_blockを10回繰り返します。
その後、元の入力ワードを出力ワードに加算し、
そのワードを1つずつリトルエンディアンでシリアル化します。

初期化（定数、キー、ブロックカウント、ナンス） ▶ 20ラウンド ▶ 加算 ▶ シリアル化
といった手順で実装していきます。

function chacha20_block(key, counter, nonce) {
    // 初期化
    // 定数
    let state = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574];
    // キー
    for (let i = 0; i < 8; i++) {
        state.push(key[i * 4] | (key[i * 4 + 1] << 8) |
            (key[i * 4 + 2] << 16) | (key[i * 4 + 3] << 24));
    }
    // ブロックカウント
    state.push(counter);
    // ナンス
    for (let i = 0; i < 3; i++) {
        state.push(nonce[i * 4] | (nonce[i * 4 + 1] << 8) |
            (nonce[i * 4 + 2] << 16) | (nonce[i * 4 + 3] << 24));
    }
    // 最後の加算用に状態コピー
    let ininitial_state = state.concat();
    // 20ラウンド
    for (let i = 0; i < 10; i++) {
        inner_block(state);
    }
    // 加算
    for (let i = 0; i < state.length; i++) {
        state[i] = (state[i] + ininitial_state[i]) & 0xffffffff;
    }
    // シリアル化
    let block = [];
    for (let i = 0; i < state.length; i++) {
        block.push(state[i] & 0x000000ff);
        block.push((state[i] & 0x0000ff00) >>> 8);
        block.push((state[i] & 0x00ff0000) >>> 16);
        block.push((state[i] & 0xff000000) >>> 24);
    }
    return block;
}

暗号化（Encryption）

キー、ブロックカウント、ナンスから、（ランダムな）64バイトのブロックを作成できるようになりました。
ChaCha20はストリーム暗号です。
同じキーとナンスを利用して、ブロックカウントを増やしていきながら、キーストリーム（keystream）ブロックを作成していきます。
平文（plaintext）と、このブロックのXOR（排他的論理和）をする事で暗号化します。
平文が（ブロックの大きさである）512ビットの倍数である必要はありません。
最後のブロックで余分な部分は破棄されます。

入力（input）:
256ビットのキー（key）
32ビットの初期カウンター（counter）
96ビットのノンス(nonce)
任意長の平文（plaintext）
出力（output）:
平文と同じ長さの暗号文（ciphertext）

function chacha20_encrypt(key, counter, nonce, plaintext) {
    let encrypted_message = [];
    for (let j = 0; j < Math.floor(plaintext.length / 64); j++) {
        let key_stream = chacha20_block(key, counter + j, nonce);
        for (let k = 0; k < 64; k++) {
            encrypted_message.push(plaintext[j * 64 + k] ^ key_stream[k]);
        }
    }
    if (plaintext.length % 64 != 0) {
        let j = Math.floor(plaintext.length / 64);
        let key_stream = chacha20_block(key, counter + j, nonce);
        for (let k = 0; k < plaintext.length % 64; k++) {
            encrypted_message.push(plaintext[j * 64 + k] ^ key_stream[k]);
        }
    }
    return encrypted_message;
}

※注意※
同じキーに関して、ナンスは毎回異なる値を使用してください。

復号化に関しては、暗号が単純なXORなので、暗号化されたデータをもう一度、暗号化すれば復号化されます。

Poly1305

Poly1305は、ワンタイム認証（one-time authenticator）です。
ワンタイムキー（one-time key）とメッセージ（message）から、128ビットのタグ（tag）を生成します。

入力（input）:
256ビットのワンタイムキー（one-time key）
任意長のメッセージ（message）
32ビットの初期カウンター（counter）
出力（output）:
128ビットのタグ(tag)

ワンタイムキーをrとsに分けます。
後半の128ビットをsとします。（リトルエンディアン）
前半の128ビットの数値（リトルエンディアン）に、0x0ffffffc0ffffffc0ffffffc0fffffffで論理和をとった値をrとします。
（22ビットを間引く事で、目的の値に収まるように調整されています。）

素数P（$2^{130}-5$、0x3fffffffffffffffffffffffffffffffb）を用意します。
（$2^{128}-1$よりもちょっと大きい素数での剰余する事で多項式評価を可能にしています。）

メッセージを16バイト毎に分割します。
任意長なので、最後は16バイトより少ない場合があります。
これらを、それぞれ数値（リトルエンディアン）にし最上位バイトの先のバイトに0x01を設定します。

アキュムレータ（accumulator）aを用意します。
作成した値を順にaに加算し、rを乗算し素数Pで剰余します。

最後に、aにsを加えます。
これをリトルエンディアンでバイト配列に戻し先頭の16バイトがタグとなります。

javascriptで実装します。
※：BigIntを使用している為、Chrome67以降、FireFox68以降でしか使えません。

function poly1305_mac(msg, key) {
    let mac = [];
    let r = 0n;
    let s = 0n;
    for (let i = 0; i < 16; i++) {
        r += BigInt(key[i]) << BigInt(i * 8);
        s += BigInt(key[i + 16]) << BigInt(i * 8);
    }
    r = r & BigInt("0x0ffffffc0ffffffc0ffffffc0fffffff");
    let a = 0n;
    let p = (1n << 130n) - 5n;
    for (let i = 1; i <= Math.ceil(msg.length / 16); i++) {
        let n = 1n;
        let len = 16;
        if (i == Math.ceil(msg.length / 16)) {
            len = msg.length - (i - 1) * 16;
        }
        for (let j = (16 * (i - 1) + len - 1); j >= 16 * (i - 1); j--) {
            n <<= 8n;
            n += BigInt(msg[j]);
        }
        a += n;
        a = (r * a) % p;
    }
    a += s;
    for (let i = 0; i < 16; i++) {
        let tmp = a & 255n;
        mac.push(parseInt(tmp.toString(10)));
        a >>= 8n;
    }
    return mac;
}

ChaCha20 & Poly1305

ChaCha20とPoly1305を組み合わせ、AEAD（認証付き暗号）を作成します。

ChaCha20を使用したPoly1305キーの生成

Poly1305は、256ビットのキーが必要となります。
これを、ChaCha20暗号で必要となるキーとナンスから生成します。
ChaCha20のブロック関数を使い、カウンターは0で生成します。
512ビットのブロックが取得出来るので、前半の256ビットをPoly1305のキーとします。

function poly1305_key_gen(key, nonce) {
    let counter = 0;
    let block = chacha20_block(key, counter, nonce);
    return block.slice(0, 32);
}

AEAD_CHACHA20_POLY1305

暗号化

入力（input）:
256ビットのキー（key）
96ビットのナンス（nonce）
任意長の平文（plaintext）
任意長の追加認証データ（aad:additional authenticated data）
出力（output）:
次の２つを連結したデータ
- ChaCha20で暗号化した、平文と同じ長さの暗号文（ciphertext）
- Poly1305で求めた、128ビットのタグ（tag）

平文を、カウンターを1として、キーとナンスでChaCha20の暗号化を行い暗号文を作成します。
キーとナンスで、poly1305のワンタイムキーを作成します。
追加認証データを16バイトの倍数長に調整したもの（足りない部分は0のバイトで埋める）、
暗号文を16バイトの倍数長に調整したもの（足りない部分は0のバイトで埋める）、
追加認証データの長さをリトルエンディアンで8バイトにしたもの、
暗号文の長さをリトルエンディアンで8バイトにしたもの、
これらを連結します。
このデータとワンタイムキーで、poly1305のタグを作成します。
暗号文とタグを連結させたデータを返します。

復号化

入力（input）:
256ビットのキー（key）
96ビットのナンス（nonce）
任意長の暗号化データ（aad:additional authenticated data）
任意長の暗号データ（enc）
出力（output）:
平文（plaintext）

暗号データの後ろ128ビットのタグの判定を行います。
キーとナンスで、poly1305のワンタイムキーを作成します。
追加認証データを16バイトの倍数長に調整したもの（足りない部分は0のバイトで埋める）、
暗号文を16バイトの倍数長に調整したもの（足りない部分は0のバイトで埋める）、
追加認証データの長さをリトルエンディアンで8バイトにしたもの、
暗号文の長さをリトルエンディアンで8バイトにしたもの、
これらを連結します。
このデータとワンタイムキーで、poly1305のタグを作成します。
これが、暗号データの後ろ128ビットと同じであるかを確認します。
（異なっていた場合は認証失敗です。）
タグを除いた暗号データを、カウンターを1として、キーとナンスでChaCha20の暗号化を行い平文を作成します。

function pad16(x) {
    let a = x.concat();
    while ((a.length % 16) != 0) {
        a.push(0);
    }
    return a;
}

function num_to_8_le_bytes(num) {
    let bs = [0, 0, 0, 0, 0, 0, 0, 0];
    let tmp = num;
    for (let i = 0; i < bs.length; i++) {
        bs[i] = tmp & 0xff;
        tmp >>= 8;
    }
    return bs;
}

function chacha20_aead_encrypt(key, nonce, plaintext, aad) {
    let otk = poly1305_key_gen(key, nonce);
    let ciphertext = chacha20_encrypt(key, 1, nonce, plaintext);
    let mac_data = pad16(aad);
    mac_data = mac_data.concat(pad16(ciphertext));
    mac_data = mac_data.concat(num_to_8_le_bytes(aad.length));
    mac_data = mac_data.concat(num_to_8_le_bytes(ciphertext.length));
    let tag = poly1305_mac(mac_data, otk);
    return ciphertext.concat(tag);
}

function chacha20_aead_decrypt(key, nonce, aad, enc) {
    let otk = poly1305_key_gen(key, nonce);
    let ciphertext = enc.slice(0, enc.length - 16);
    let tag = enc.slice(enc.length - 16);
    let mac_data = pad16(aad);
    mac_data = mac_data.concat(pad16(ciphertext));
    mac_data = mac_data.concat(num_to_8_le_bytes(aad.length));
    mac_data = mac_data.concat(num_to_8_le_bytes(ciphertext.length));
    let mac = poly1305_mac(mac_data, otk);
    for (let i = 0; i < mac.length; i++) {
        if (mac[i] != tag[i]) {
            throw error("unmatch tag");
        }
    }
    let plaintext = chacha20_encrypt(key, 1, nonce, ciphertext);
    return plaintext;
}

さいごに

案外簡単に実装できました。
（※：poly1305はBigIntを使ってしまったが・・・）
実際は共有鍵が必要となるので、ECDHなどのハンドシェイクが必要となります。
ソースコードは、RFCを元に作成していますが、もっと良いロジックがあるように思えます。

Githubにソースコードがあります。

参考（Reference）

ChaCha20 and Poly1305 for IETF Protocols（RFC-8439）
Bitcoin P2P Encryption（Breaking Bitcoin）
Video
Slides
Transcript
新しいTLSの暗号方式ChaCha20-Poly1305