ストリーム暗号を実装してみる【ChaCha20】

2023年3月30日 21:41

どうも、失恋した堕天使です
まあそんなことはいいので今回は暗号の話です←

今回はChaCha20ってアルゴリズムをC言語で作ってみようって感じですね

まずざっと暗号技術の基礎知識を説明します
まあ知ってることは飛ばして読んでもらって

暗号化したい文を平文、暗号を解くことを復号と言います
今回実装するChaCha20は共通鍵暗号といって暗号化に使う鍵(パスワード的な)と復号化に使う鍵が同じ暗号方式です
(逆に違うことってあるの?と思うかもしれませんが公開鍵暗号というのがあります、RSAとかが有名ですね)

共通鍵暗号は「鍵さえ安全に伝えられれば」安全な暗号です、じゃあその方法で本文を伝達すればいいのでは?って話ですけど、それを実現する公開鍵暗号は処理が大変なので鍵だけ公開鍵暗号で共有して本文は共通鍵暗号で暗号化するというハイブリッド暗号というのが使われます

共通鍵暗号の基本的な原理は以下の式で説明できます

$$
c=m\oplus s\\c\oplus s=m
$$

ここで$${c}$$は暗号、$${m}$$は平文、$${s}$$は鍵、$${\oplus}$$はxor演算子です
つまり、平文に鍵をxorしたら暗号化でき、その暗号にもう一度鍵をxorしたら復号化できるということです
(これは、xorに結合律$${(a\oplus b)\oplus c=a\oplus (b\oplus c)}$$が成り立つことによります、$${(m\oplus s)\oplus s=m\oplus (s\oplus s)=m\oplus 0=m}$$なので)

共通鍵暗号において強度や利便性を高めるために重要なのは鍵sの決め方です
ここで鍵sに完全な乱数(真の乱数と言い、ランダムな値のことです)を1度だけ使用する(つまり、周期的な値でなく、使いまわさない)と暗号文から平文を予測することが不可能になります、これをワンタイムパッド方式といいます

しかし現実的に真の乱数を生成することは難しいです
できたとしてそれを毎回平文と同じ量生成しなければならないのでコストはばか高いです
そこで疑似乱数というのが使われます

疑似乱数とは、種(シード)という値から計算によって生成された一見乱数のような値のことです、そのプログラムとかアルゴリズムとかを疑似乱数生成器と言ったりします
余談ですけど僕は学校の実験で線形合同法(LCGs)という疑似乱数生成器を作ったことがあります、ただこれは格子構造の規則性を持つのでそのまま暗号技術に使うことができません、どうやら線形帰還シフトレジスタやメルセンヌ・ツイスターといった疑似乱数生成器は鍵に使えるらしいです、今回は疑似乱数生成器は作らないので気にしなくてもいいです

鍵に真の乱数の代わりに疑似乱数を使った共通鍵暗号のことをストリーム暗号といいます
ここで秘密鍵(共通鍵暗号方式では当事者間で共有する情報のこと、共通鍵とも)は疑似乱数生成器の種になります

しかし、疑似乱数は周期を持つため同じ種を使いまわすことができません
それを解決するのが疑似ランダム関数(PRF)です

PRFでは疑似乱数を生成するために種の他にナンスという値も使用します
PRFには、ナンスを変えると生成される疑似乱数は大きく変わり、ナンスを公開しても鍵を予測できないという性質があります
これにより、1度種を共有したらナンスを変えることで種を繰り返して暗号化を行えるようになります、これによる暗号の1つがChaCha20です

ここから具体的なChaCha20のアルゴリズムを話します
ChaCha20の疑似ランダム関数では以下の4つの変数を使います(Bはバイトです)

32Bの秘密鍵k
12Bのナンスn
4Bのカウンタb
16Bの初期定数c

ここで秘密にする情報は秘密鍵kだけです
PRF(k,n,b,c)で64Bの疑似乱数になります(変数のサイズの総和と同じサイズです)
この情報から生成された疑似乱数とxorを取れば暗号化・復号化ができるので、ChaCha20たる部分はPRFのアルゴリズムです

ChaCha20では平文(復号なら暗号文)を64Bずつに分けて、そのグループの数だけPRFから乱数を生成しxorを取ります
末尾の余った乱数は要らない情報なので、ないものとして考えていいです
このときのPRFについてグループが変わる毎に順にカウンタを足していきます(他の情報は1度の暗号中で使いまわせます)
カウンタが4Bの(符号なし)整数なので、カウンタだけを変えることで2^32ビット(≒0.5GB)の平文を暗号化できます、これを超えるならナンスを変えればまた使用できます

PRFとなる関数は後でchar* ChaCha20_PRF(char* key,char* nonce,uint32_t count)として実装することにして、この部分だけを関数にします

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

void ChaCha20_QR(uint32_t*,uint32_t*,uint32_t*,uint32_t*) //PRF用
char* ChaCha20_PRF(char*,char*,uint32_t) // ChaCha20用

/**
 * @brief 長さがsizeの文字列messageを、長さ32の鍵keyと長さ12のナンスnonceで暗号化・復号化します
 */
void ChaCha20(char* message,int size,char* key,char* nonce){
    for(uint32_t i=0;i<(size+63)/64;i++){
        char* rand=ChaCha20_PRF(key,nonce,i);
        for(int j=0;j<64;j++){
            if(i*64+j>=size)break;
            message[i*64+j]^=rand[j];
        }
        free(rand);
    }
}

引数をchar型にしているのはchar型が1Bだからなので、必ずしも文字列として読める必要はありません(流石にビット単位で送ることはないと思うのでバイト単位で情報をやり取りすることとします)
uint32_t型はstdint.hの32ビット(=4B)符号なし整数です

ここからはPRFのアルゴリズムについてです
PRFは受け取った引数を32ビット単位の整数として4*4の表(内部状態と言います)に配置し、それをかきまぜるという動作を繰り返します
内部状態は以下のような初期値で始めます

これに対し、1/4ラウンド関数(QR)という関数を8回使用してかき回します
これを10回繰り返した結果を初期値に加算すれば、疑似乱数が完成します
QRは4つの整数を引数とし、以下の順に実行します

なので、QRを合計80回行うことになります
QRは加算、xor、左ローテート(2進数で桁を左にn桁回転させる)だけで構成されます
ここでは以下の関数をQRとして使用します
(かきまぜた結果を返してまた格納するのは大変なので、引数はアドレス渡しにします)

void ChaCha20_QR(uint32_t* a,uint32_t* b,uint32_t* c,uint32_t* d){
    *a+=*b; *d^=*a; *d=(*d<<16)|(*d>>(32-16));
    *c+=*d; *b^=*c; *b=(*b<<12)|(*b>>(32-12));
    *a+=*b; *d^=*a; *d=(*d<<8)|(*d>>(32-8));
    *c+=*d; *b^=*c; *b=(*b<<7)|(*b>>(32-7));
}

PRFはこれを上の順に実行して最後に加算すればいいので、これを実装します

char* ChaCha20_PRF(char* key,char* nonce,uint32_t count){
    uint32_t table[4][4];
    table[0][0]=0xA914F587u;
    table[0][1]=0x90C074AFu;
    table[0][2]=0xB962785Cu;
    table[0][3]=0xD91ECC76u;
    table[3][0]=count;
    for(int i=0;i<2;i++){
        for(int j=0;j<4;j++){
            uint32_t block=0;
            for(int k=0;k<4;k++)block+=((uint32_t)key[i*4*4+j*4+k])<<(8*k);
            table[i+1][j]=block;
        }
    }
    for(int i=0;i<3;i++){
        uint32_t block=0;
        for(int j=0;j<4;j++)block+=((uint32_t)nonce[i*4+j])<<(8*j);
        table[3][i+1]=block;
    }
    uint32_t table_copy[4][4];
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++)table_copy[i][j]=table[i][j];
    }
    for(int i=0;i<10;i++){
        for(int j=0;j<4;j++)ChaCha20_QR(&(table[j][0]),&(table[j][1]),&(table[j][2]),&(table[j][3]));
        for(int j=0;j<4;j++)ChaCha20_QR(&(table[j][0]),&(table[(j+1)%4][1]),&(table[(j+2)%4][2]),&(table[(j+3)%4][3]));
    }
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++)table[i][j]+=table_copy[i][j];
    }
    char* char_table=(char*)malloc(sizeof(char)*4*4*4);
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            for(int k=0;k<4;k++)char_table[i*4*4+j*4+k]=(char)(table[i][j]>>(k*8));
        }
    }
    return char_table;
}

初期定数は関数中でてけとうな値を固定して設定してます
長くない?って思うかもしれませんが大体はchar型とuint32_t型の間の変換作業とかです、この部分だけ関数化してもよかったかも
最終的に返すchar型の乱数だけはスコープ外なのでメモリを動的に確保して返します

ということでChaCha20が完成したのでmain関数を作って試してみます

void printMessage(char* message,int size){
    printf("%s\n(",message);
    for(int i=0;i<size;i++){
        for(int j=0;j<8;j++)printf("%d",(message[i]>>j)&1);
        printf(" ");
    }
    printf(")\n");
}
int main(){
    char message[18]="this is a message";
    char key[33]="needa32Byteskeyformakethiscipher";
    char nonce[13]="nonceis96bit";
    printf("plaintext:\n");
    printMessage(message,17);
    ChaCha20(message,17,key,nonce);
    printf("\nencode:\n");
    printMessage(message,17);
    ChaCha20(message,17,key,nonce);
    printf("\ndecode:\n");
    printMessage(message,17);
}

こんな感じですね－
ということでChaCha20の実装でした
AESとかRSAとかも実装してみたいな－って思ってるので、その記事も出すかも
ではまた今度～

この記事が気に入ったらサポートをしてみませんか？