Namaran

Code daily. Without assist.

2026-08-30

ct_equal.c

int ct_equal(const unsigned char* a, const unsigned char* b, size_t n) {
}

長さ n の2つのバイト列 a と b が一致すれば 1、そうでなければ 0 を返す ct_equal を書いてください。パスワードやトークンのような秘密の値と比べるのに使うので、かかる時間が、2つの列のどこで食い違うかやバイトの値によって変わらないようにします。n が 0 なら 1 を返します。例では、バイト列を文字列リテラルで書きます。

入力例 1

ct_equal("pass", "pass", 4)

出力例 1

1

入力例 2

ct_equal("pass", "pasz", 4)

出力例 2

0

入力例 3

ct_equal("", "", 0)

出力例 3

1
Reference

Reference

int ct_equal(const unsigned char* a, const unsigned char* b, size_t n) {
    unsigned char diff = 0;
    for (size_t i = 0; i < n; i++)
        diff |= a[i] ^ b[i];
    return diff == 0;
}

見慣れた比較は、食い違うバイトを見つけた時点で return 0 します。この形では、先頭から一致したバイトが多いほど長く動くので、時間を測れば推測の先頭が何バイト当たったかが分かります。条件を満たすには、食い違いを見つけても抜けずに n バイトを最後まで読み、一致したかどうかは最後に一度だけ決めます。

a[i] ^ b[i] は、2つのバイトが同じなら 0、違えば違うビットだけが 1 の値になります。これを diff |= でためると、一度立ったビットはあとで 0 に戻らないので、どこか1か所でも違えば diff は最後まで 0 以外のままです。ループの中には値で向きが変わる分岐が無く、どのバイトでも同じ XOR と OR を1回ずつ実行します。"pass" と "pasz" では4バイト目の 's' ^ 'z' が 0 以外なので 0 を返し、n が 0 ならループに入らず diff は 0 のままなので 1 を返します。

掲載したのは参考実装で、唯一の正解ではありません。ためる演算を OR から足し算の += に変えると、unsigned char の和は 256 で 0 に戻るので、違うバイトがいくつかあっても一致と判定されることがあります。ためるのは、0 以外が一度入ったら 0 に戻らない OR にします。1

  1. C の規格はプログラムの実行時間について何も定めていないので、コンパイラが「diff が 0 以外になったら抜けてよい」と判断して書き換える余地は、理屈の上では残ります。暗号ライブラリが同じ処理を volatile やアセンブリで書き、コンパイラに手を出させないようにしているのはそのためです。