C言語でDH鍵交換とBaby-step Giant-step アルゴリズムの実装
はじめに
この記事では C 言語を使用して Diffie-Hellman 鍵共有と Baby-step Giant-step アルゴリズムを実装します。Diffie-Hellman 鍵共有は、2 人の当事者が安全に共通の秘密鍵を生成するためのプロトコルです。離散対数問題は、公開鍵暗号の基礎となる数学的問題です。
この記事は、以下を参考にしています。
数学的準備
DH 鍵共有のための数学的な準備としていくつか準備が必要です。
離散対数問題
離散対数問題は、与えられた整数
を満たす
指数関数
離散対数を解くためには、指数関数を効率的に計算する必要があります。
この計算は繰り返し二乗法を使用して効率的に行うことができ、計算量は
C 言語による繰り返し二乗法の実装例
// Result = (base^exp) % mod
int mod_pow(int base, int exp, int mod) {
unsigned long long result = 1;
unsigned long long b = base % mod;
while (exp) {
if (exp & 1) {
result = (result * b) % mod;
}
exp >>= 1;
b = (b * b) % mod;
}
return (int)result;
}
整数平方根
後に述べる Baby-step Giant-step アルゴリズムで使用するため、整数の平方根を計算するための関数を実装します。
C 言語による整数平方根の実装例
int isqrt(int n) {
if (n < 0) return -1; // Invalid input
if (n == 0 || n == 1) return n;
unsigned long long x = n;
unsigned long long y = (x + 1) / 2;
while (y < x) {
x = y;
y = (x + n / x) / 2;
}
return (int)x;
}
DH 鍵共有
数学的な準備が整ったところで、DH 鍵共有の手順と C 言語での実装例を示します。
DH 鍵共有の手順
Diffie-Hellman 鍵共有は、2 人が安全に共通の秘密鍵を生成するためのプロトコルです。まず、DH 鍵共有の手順を説明します。
- Alice と Bob は、大きな素数
p g - Alice と Bob はそれぞれ秘密鍵
a b - Alice は公開鍵
A = g^a \mod p - Bob は公開鍵
B = g^b \mod p - Alice は受け取った Bob の公開鍵
B K = B^a \mod p - Bob は受け取った Alice の公開鍵
A K = A^b \mod p - これにより、Alice と Bob は同じ共通鍵
K
この共有プロセスでは、離散対数問題の難しさに依存しており、第三者が
手計算による確認
上記の計算を手計算にて確認します。
まず、
Alice は Bob に
Alice と Bob は同じ共通鍵
C 言語による DH 鍵共有の実装
以下に、C 言語での実装例を示します。先ほどの繰り返し二乗法の関数 mod_pow を使用しています。
#include <stdio.h>
int main() {
int p = 1009;
int g = 11;
// private keys
int a = 123;
int b = 456;
// public keys
int A = mod_pow(g, a, p); // Alice public key
int B = mod_pow(g, b, p); // Bob public key
printf("Alice's public key: %d\n", A); // 510
printf("Bob's public key: %d\n", B); // 185
// Shared secret
int s1 = mod_pow(B, a, p);
int s2 = mod_pow(A, b, p);
printf("Shared secret (Alice): %d\n", s1); // 74
printf("Shared secret (Bob): %d\n", s2); // 74
return 0;
}
計算量は、公開鍵の計算が
離散対数の解法
離散対数問題は、与えられた整数
離散対数問題を解くためのより効率的なアルゴリズムとして、Baby-step Giant-step アルゴリズムがあります。このアルゴリズムは、計算量
Baby-step Giant-step アルゴリズム
Baby-step Giant-step アルゴリズムは、離散対数問題を解くための効率的な方法です。このアルゴリズムは、以下の手順で実行されます。
- 整数
q = \lceil \sqrt{p} \rceil -
i = 0, ... q-1 b = g^i \mod p -
g^{-q} \mod p -
j = 0, ... q-1 A \cdot (g^{-q})^j \mod p - 一致する場合、
x = i + j \cdot q
最後の
手計算による確認
上記を手計算にて確認します。
まず、
では、
では、Baby-step Giant-step アルゴリズムを使用して解を求めます。まず、
次に、Baby-step を計算します。Baby-step では、
| 0 | 1 |
| 1 | 5 |
| 2 | 2 |
| 3 | 10 |
| 4 | 8 |
次に、Giant-step を計算します。Giant-step では、
| Baby-step に存在するか | |||
|---|---|---|---|
| 0 | 1 | 16 | No |
| 1 | 15 | 10 | Yes (i=3) |
実際、
C 言語による Baby-step Giant-step アルゴリズムの実装
以下に、C 言語での実装例を示します。
// find x such that A = g^x mod p
int discrete_log(int g, int A, int p) {
int q = isqrt(p);
// Baby-step
HashMap *hashmap = newHashMap(q);
int b = 1;
insertToHashMap(hashmap, b, 0);
for (int i = 1; i <= q; i++) {
b = (b * g) % p;
insertToHashMap(hashmap, b, i);
}
// Giant-step
int g_inv = mod_pow(g, p-2, p);
int g_inv_q = mod_pow(g_inv, q, p);
int giant_step = A;
int result = -1;
for (int a=0; a<q; a++) {
int b;
if (getValueFromHashMap(hashmap, giant_step, &b) == HASHMAP_OK) {
result = a * q + b;
break;
}
giant_step = (giant_step * g_inv_q) % p;
}
freeHashMap(hashmap);
return result;
}
HashMap の実装
#ifndef HASHMAP_H
#define HASHMAP_H
#include <stddef.h>
typedef enum { HASHMAP_OK, HASHMAP_ERROR } HashMapStatus;
typedef struct Entry Entry;
struct Entry {
int key;
int value;
Entry *next;
};
typedef struct HashMap HashMap;
struct HashMap {
size_t size;
Entry **entries;
};
HashMap *newHashMap(int size);
HashMapStatus insertToHashMap(HashMap *hashmap, const int key, const int value);
HashMapStatus getValueFromHashMap(const HashMap *hashmap, const int key,
int *value);
void freeHashMap(HashMap *hashmap);
#endif
#include "hashmap.h"
#include <limits.h>
#include <stdlib.h>
HashMap *newHashMap(int size) {
HashMap *hashmap = malloc(sizeof(HashMap));
hashmap->size = size;
hashmap->entries = malloc(size * sizeof(Entry *));
for (size_t i = 0; i < size; i++) {
hashmap->entries[i] = NULL;
}
return hashmap;
}
int hash(int key, int size) {
unsigned int ukey = (unsigned int)key;
unsigned long long hash = ukey * 2654435761ULL;
return (int)(hash % size);
}
HashMapStatus insertToHashMap(HashMap *hashmap, const int key, const int value) {
int index = hash(key, hashmap->size);
Entry *node = hashmap->entries[index];
while (node) {
if (node->key == key) {
node->value = value;
return HASHMAP_OK;
}
node = node->next;
}
Entry *new_node = malloc(sizeof(Entry));
if (!new_node) return HASHMAP_ERROR;
new_node->key = key;
new_node->value = value;
new_node->next = hashmap->entries[index];
hashmap->entries[index] = new_node;
return HASHMAP_OK;
}
HashMapStatus getValueFromHashMap(const HashMap *hashmap, const int key,
int *value) {
int index = hash(key, hashmap->size);
Entry *node = hashmap->entries[index];
while (node) {
if (node->key == key) {
*value = node->value;
return HASHMAP_OK;
}
node = node->next;
}
return HASHMAP_ERROR;
}
void freeHashMap(HashMap *hashmap) {
for (size_t i = 0; i < hashmap->size; i++) {
Entry *node = hashmap->entries[i];
while (node) {
Entry *temp = node;
node = node->next;
free(temp);
}
}
free(hashmap->entries);
free(hashmap);
}
まとめ
この記事では、C 言語を使用して Diffie-Hellman 鍵共有と離散対数の解法を実装しました。Diffie-Hellman 鍵共有は、2 人の当事者が安全に共通の秘密鍵を生成するためのプロトコルです。離散対数問題は、公開鍵暗号の基礎となる数学的問題です。
今後は、有限体上の楕円曲線を使用した鍵共有や、より高度な離散対数の解法についても学んでいきたいと思います。
Discussion