LoginSignup
5
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@tibigame

ペアリングライブラリを使ってIDベース暗号を作ってみる

Last updated at Posted at 2017-03-20

ペアリングとは

$ペアリングeはG_1,G_2をFに移す写像で、$
$e(an, b)=e(a, nb)=e(a, b)^nのような便利な性質があるもの。$
とはいえ$G_1, G_2, F, e$とかを具体的に構成するにはどうしたものかと思ったら……

C++でmclライブラリというのがあるので使ってみる。
ペアリング暗号ライブラリmclを使ってみる
内部実装知らずに使っているので間違っていたら指摘してくれ。

準備

まずはgitから一通りダウンロードしてくる。
Visual Studio 2015でmcl.sln開いてビルドはReleaseで最適化の設定だけ変えてビルド。
警告は出るもトラブルなくビルド成功。
Debugの方は通らなかったが気にしない。
一旦ビルドすれば新規プロジェクトからライブラリ呼んで使えるようになる。
includeとライブラリの設定は以下を追加。

include

  • \mcl\include;
  • \cybozulib_ext\include;
  • \cybozulib\include;
  • \xbyak\xbyak

ライブラリ

  • \mcl\lib;
  • \cybozulib_ext\lib

実装

includeとデータ型のクラス

idbase.cpp
# include "stdafx.h"
# include <iostream>
# include <vector>
# include <string>
# include <sstream>
# include "util.h"
# include <random>
# include <mcl/bn256.hpp>
using namespace mcl::bn256;

class Message {
public:
	unsigned __int64 m[48];
	int length;
};

class CipherText {
public:
	G2 cipher1;
	Message cipher2;
};

Messageのクラスはunsigned __int64の配列でデータを持っている。
std::stringあたりから変換してくることも頑張ればできるだろうがこのままで。
CipherTextのクラスはMessageと同じデータ構造に加えてG2型の要素を1つ持っている。
util.hは後で書いていきます。

ベースとなるクラス作成

idbase.cpp
class Id_Base {
private:
	G2 P; // 初期点
	G2 P_pub; // 公開パラメータ
	Fr s; // シークレットとする乱数パラメータ
public:
	// セットアップ
	void init() {
		std::random_device rd1;
		int p_init = rd1(); // 楕円曲線上の初期点を定める乱数パラメータ
		BN::mapToG2(P, p_init);
		std::random_device rd;
		s.setRand(rd);
		G2::mul(P_pub, P, s); // P_pub = sP
	}
	// ユーザー秘密鍵の生成
	G1 create_user_private_key(const std::string& id)
	{
		G1 Ud;
		Fp t;
		t.setMsg(id);
		BN::mapToG1(Ud, t);
		return Ud;
	}
	// ユーザー公開鍵の生成
	Fp12 create_user_public_key(const std::string& id, G2 Pub)
	{
		Fp12 g_id;
		BN::pairing(g_id, create_user_private_key(id), Pub);
		return g_id;
	}
	G2 get_P_pub() {
		return P_pub;
	}
};

セットアップ

初期化では適当に$P, s$を決めて$P_{pub}=sP$を計算する。
$P_{pub}$は公開情報とするので$P_{pub}$を返す関数としてget_P_pub()を用意する。

ユーザーの秘密鍵生成

**ID:**std::stringから$G_1$の元$U_d$に移すハッシュ関数の役割を持つ。

ユーザーの公開鍵生成

秘密鍵$U_d$と公開情報$P_{pub}$とのペアリングを公開鍵とする。
$U_g=e(U_d, P_{pub})$

暗号化・復号化ロジックの記述

idbase.cpp
// 暗号化(ユーザー秘密鍵あり)
CipherText encrypt(Message M, G1 user_private_key, G2 Pub) {
	CipherText C;
	Fr r;
	std::random_device rm;
	r.setRand(rm); // 暗号文用に乱数を選ぶ
	G2::mul(C.cipher1, Pub, r); // cipher1 = rP
	Fp12 g_id, g_id_r, H2;
	BN::pairing(g_id, user_private_key, Pub);
	Fp12::pow(g_id_r, g_id, r); // g_id_r = g_id^r
	BN::mapToCyclotomic(H2, g_id_r);
	xor (C.cipher2.m, M.m, H2, M.length);
	C.cipher2.length = M.length;
	return C;
}
// 暗号化(ユーザー公開鍵あり)
CipherText encrypt_public(Message M, Fp12 user_public_key, G2 Pub) {
	CipherText C;
	Fr r;
	std::random_device rm;
	r.setRand(rm); // 暗号文用に乱数を選ぶ
	G2::mul(C.cipher1, Pub, r); // cipher1 = rP
	Fp12 g_id, g_id_r, H2;
	g_id = user_public_key;
	Fp12::pow(g_id_r, g_id, r); // g_id_r = g_id^r
	BN::mapToCyclotomic(H2, g_id_r);
	xor (C.cipher2.m, M.m, H2, M.length);
	C.cipher2.length = M.length;
	return C;
}
// 復号化
Message decrypt(CipherText C, G1 user_private_key) {
	Message M;
	Fp12 dID, H2;
	BN::pairing(dID, user_private_key, C.cipher1);
	BN::mapToCyclotomic(H2, dID);
	xor (M.m, C.cipher2.m, H2, C.cipher2.length);
	M.length = C.cipher2.length;
	return M;
}

暗号化

平文$M$、適当な乱数を$r$とする。
$C_1=rP_{pub}$
$C_2={\rm xor}(M, H_2((U_g)^r))$
$H_2はF上のハッシュ関数である。$

復号化

$M={\rm xor}(C_2, H_2(e(U_d, C_1)))$

複合が正しいことの計算

$Mの式にC_1、C_2とU_g=e(U_d, P_{pub})$を代入すると、
$M={\rm xor}({\rm xor}(M, H_2(e(U_d, P_{pub})^r), H_2(e(U_d, rP_{pub}))))$
ペアリングの関係ならば同じものをxorしていることになるので$M$に戻る。

xor関数の作成

Fp12型とxorを取らないといけないのだが、Fp12からstringが取れることがわかった。
stingは12個の多倍長整数の形をしているので、
unsigned __int64の配列に変換してxorを取ることにする。

util.h
# pragma once

# include <iostream>
# include <vector>
# include <string>
# include <sstream>

# include <mcl/bn256.hpp>
using namespace mcl::bn256;

unsigned __int64* xor(unsigned __int64* r, unsigned __int64* m, Fp12 fp12, int l);
util.cpp
# include "stdafx.h"
# include <iostream>
# include <iomanip>
# include "util.h"

// 文字列をスプリッターで分割する
std::vector<std::string> split(const std::string &str, char sep)
{
	std::vector<std::string> v;
	std::stringstream ss(str);
	std::string buffer;
	while (std::getline(ss, buffer, sep)) {
		v.push_back(buffer);
	}
	return v;
}

// 文字列をk文字*n個に分割する
std::vector<std::string> subs(const std::string &str, int k, int n)
{
	int l = static_cast<int>(str.size()); // 取得する場所のポインタ
	std::vector<std::string> r(n, std::string(k, '0')); // 0で初期化
	for (int i = 0; i < n; ++i) {
		l -= k; // 末尾からk文字ずつずらす
		if (l < 0) { // 文字列が足りない場合
			r[n - 1 - i].erase(-l, k);
			r[n - 1 - i] += str.substr(0, k + l);
			l = 0;
		}
		else { // 通常はk文字の部分文字列をそのまま代入
			r[n - 1 - i] = str.substr(l, k);
		}
	}
	return r;
}

constexpr int MAX_U64_LENGTH = 19; // u64で表現できる最大桁 18446744073709551615 _UI64_MAX
constexpr int NUMBER = 4; // str列1つ当たりに必要なu64の数
constexpr int FP12_STRNUM = 12; // FP12に含まれるstrの数

// メッセージとFp12オブジェクトとのxorを計算します
// メッセージには (最大4*12 = 48個)のuint64を取れます
unsigned __int64* xor(unsigned __int64* r, unsigned __int64* m, Fp12 fp12, int l = NUMBER*FP12_STRNUM) {
	// Fp12オブジェクトからstringを取り出す
	std::string fp12_str = fp12.getStr();
	std::vector<std::string>fp12_strs = split(fp12_str, ' ');
	std::vector<std::string>fp12_vec;

	for (int j = 0; j < FP12_STRNUM; ++j) {
		auto t = subs(fp12_strs[j], MAX_U64_LENGTH, NUMBER);
		for (int k = 0; k < NUMBER; ++k) {
			if (j * NUMBER + k == l) {
				return r;
			}
			r[j * NUMBER + k] = m[j * NUMBER + k] ^ std::stoull(t[k]); // 19桁ずつuint64に変換してxorを取る
		}
	}
	return r;
}

main関数

idbase

int main()
{
	bn256init();

	Id_Base id_Base;
	id_Base.init();

	std::string target_user = "ユーザーID";

	// 公開鍵で暗号化
	Message M1; // メッセージを用意
	M1.m[0] = (unsigned __int64)1245800458024;
	M1.m[1] = (unsigned __int64)100242425408752542;
	M1.m[2] = (unsigned __int64)25432899455857853;
	M1.m[3] = (unsigned __int64)8767694524;
	M1.m[4] = (unsigned __int64)996875400001242457;
	M1.length = 5;

	G2 P_pub1 = id_Base.get_P_pub(); // 公開情報なので入手可能
	Fp12 user_public_key = id_Base.create_user_public_key(target_user, P_pub1); // ユーザーの公開鍵を発行してもらう
	CipherText C1 = encrypt_public(M1, user_public_key, P_pub1); // encrypt_publicは引数以外の情報は不要なのでローカルで計算できる

	// 秘密鍵で暗号化
	Message M2; // メッセージを用意
	M2.m[0] = (unsigned __int64)5484588648;
	M2.m[1] = (unsigned __int64)86744073709551615;
	M2.m[2] = (unsigned __int64)412425422709551615;
	M2.m[3] = (unsigned __int64)1114073709551615;
	M2.m[4] = (unsigned __int64)42428479551615;
	M2.length = 5;

	G2 P_pub2 = id_Base.get_P_pub(); // 公開情報なので入手可能
	G1 user_private_key = id_Base.create_user_private_key(target_user); // ユーザーが秘密鍵を発行してもらう
	CipherText C2 = encrypt(M2, user_private_key, P_pub2); // encryptは引数以外の情報は不要なのでローカルで計算できる

	// 復号化 (秘密鍵を持っているユーザーだけが可能)
	Message R1, R2;
	R1 = decrypt(C1, user_private_key);
	R2 = decrypt(C2, user_private_key);

	// 検証
	std::cout << R1.m[0] << std::endl;
	std::cout << R1.m[1] << std::endl;
	std::cout << R1.m[2] << std::endl;
	std::cout << R1.m[3] << std::endl;
	std::cout << R1.m[4] << std::endl;

	std::cout << R2.m[0] << std::endl;
	std::cout << R2.m[1] << std::endl;
	std::cout << R2.m[2] << std::endl;
	std::cout << R2.m[3] << std::endl;
	std::cout << R2.m[4] << std::endl;

    return 0;
}

ちゃんと復号結果は一致する。
復号化で違う鍵を使うと結果が異なるのでうまくいってそう。

5
4
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?