stackprobe7s_memo

何処にも披露する見込みの無いものを書き落とす場所

16bitのRSAを実装してみる (C)

  • 昔実装した16bitのRSAが見事に間違っていたことに気付き、狼狽した勢いで書き直しました。
    • 実用性はありませんが、仕組みを理解するために作成
  • 仕様
    • 平文 ... 16ビットの符号なし整数 (或いは2バイトのデータ) とする。
      • 平文の最上位ビットを1にするなどして値の大きさを確保するらしいので、実質的には16ビット未満？

ソースコード

rsa.c

#include <stdio.h>

typedef unsigned __int8 uchar;
typedef unsigned __int32 uint;
typedef unsigned __int64 uint64;

#define SWAP(a, b) (a ^= b, b ^= a, a ^= b)

// VC ---->

#include <windows.h>
#include <wincrypt.h>

#pragma comment(lib, "ADVAPI32")

/*
	CSPRNG

	0 以上 2^16 未満の乱数を返す。
*/
static uint CRandom16(void)
{
	uchar v[2];

	{
		HCRYPTPROV hp;

		if(!CryptAcquireContext(&hp, 0, 0, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT))
			exit(1); // fatal

		if(!CryptGenRandom(hp, 2, v))
			exit(1); // fatal

		CryptReleaseContext(hp, 0);
	}

	return (uint)v[0] << 8 | v[1];
}

// <---- VC

/*
	ユークリッド互除法

	(x, y) の最大公約数を返す。
*/
static uint GCD(uint x, uint y)
{
	while(y)
	{
		x %= y;

		SWAP(x, y);
	}
	return x;
}

/*
	拡張ユークリッド互除法

	(x, y) の最大公約数を返す。

	(*a) * x + (*b) * y === GCD(x, y) (mod m) となるような (*a), (*b) をセットする。
*/
static uint ExtGCD(uint x, uint y, uint *a, uint *b, uint m)
{
	uint ret;

	if(y)
	{
		ret = ExtGCD(y, x % y, b, a, m);

		*b += m - ((uint64)(x / y) * (*a)) % m;
		*b %= m;
	}
	else
	{
		ret = x;

		*a = 1;
		*b = 0;
	}
	return ret;
}

/*
	(v ^ e) % m を返す。
*/
static uint ModPow(uint v, uint e, uint m)
{
	uint64 r;

	if(!e)
		return 1;

	r = ModPow(v, e / 2, m);
	r *= r;
	r %= m;

	if(e & 1)
	{
		r *= v;
		r %= m;
	}
	return r;
}

/*
	1 以上 2^16 未満の奇数について、素数でなければ真を返す。
*/
static int IsComposite(uint value)
{
	static uchar ops[0x1000];

#define op(p) (ops[(p) / 16] & 1 << (p) / 2 % 8)

	if(!ops[0])
	{
		uint c;
		uint d;

		ops[0] = 1;

		for(c = 3; c < 0x100; c += 2)
			if(!op(c))
				for(d = c * c / 2; d < 0x10000 / 2; d += c)
					ops[d / 8] |= 1 << d % 8;
	}
	return op(value);

#undef op
}

//
// ======================
// ==== ここから RSA ====
// ======================
//

/*
	鍵生成

	(*e) <--- 暗号鍵のext
	(*d) <--- 復号鍵のext
	(*m) <--- mod

	をそれぞれセットする。

	( (*e), (*m) ) を暗号鍵として使用する。
	( (*d), (*m) ) を復号鍵として使用する。
*/
static void GenKey(uint *e, uint *d, uint *m)
{
	uint p;
	uint q;
	uint tmp;

	do
	{
		while(p = CRandom16() | 1, IsComposite(p));
		while(q = CRandom16() | 1, p == q || IsComposite(q));
	}
	while(p * q < 0x10000);

	*m = p * q;

	p--;
	q--;

	p *= q / GCD(p, q);

	while(*e = CRandom16() | 1, IsComposite(*e) || ExtGCD(*e, p, d, &tmp, p) != 1);
}

/*
	暗号化

	p を平文 (e, m) を暗号鍵とする。
*/
static uint Enc(uint p, uint e, uint m)
{
	return ModPow(p, e, m);
}

/*
	復号

	c を暗号文 (d, m) を復号鍵とする。
*/
static uint Dec(uint c, uint d, uint m)
{
	return ModPow(c, d, m);
}

//
// ======================
// ==== ここまで RSA ====
// ======================
//

/*
	簡単なテスト
*/
static void DoTest(void)
{
	uint e;
	uint d;
	uint m;
	uint p;
	uint c;
	uint q;

	GenKey(&e, &d, &m);

	printf("暗号鍵 = %u (%u)\n", e, m);
	printf("復号鍵 = %u (%u)\n", d, m);

	p = CRandom16();

	printf("平文 = %u\n", p);

	c = Enc(p, e, m);

	printf("暗号文 = %u\n", c);

	q = Dec(c, d, m);

	printf("復号した平文 = %u\n", q);

	if(p == q)
		printf("■成功！\n");
	else
		printf("□失敗！\n");

	printf("\n");
}
int main()
{
	uint c;

	for(c = 0; c < 10; c++)
	{
		DoTest();
	}
}

実行結果 (出力例)

暗号鍵 = 40519 (850836101)
復号鍵 = 89955727 (850836101)
平文 = 31043
暗号文 = 175750552
復号した平文 = 31043
■成功！

暗号鍵 = 22447 (34618007)
復号鍵 = 9042127 (34618007)
平文 = 18870
暗号文 = 32960880
復号した平文 = 18870
■成功！

暗号鍵 = 20231 (861475339)
復号鍵 = 125032867 (861475339)
平文 = 1253
暗号文 = 221583236
復号した平文 = 1253
■成功！

暗号鍵 = 51713 (530318947)
復号鍵 = 124438833 (530318947)
平文 = 30961
暗号文 = 265166145
復号した平文 = 30961
■成功！

暗号鍵 = 15817 (1299805879)
復号鍵 = 394184833 (1299805879)
平文 = 25409
暗号文 = 254132619
復号した平文 = 25409
■成功！

暗号鍵 = 7933 (1367940043)
復号鍵 = 242017 (1367940043)
平文 = 38417
暗号文 = 226452582
復号した平文 = 38417
■成功！

暗号鍵 = 41911 (427479329)
復号鍵 = 207319555 (427479329)
平文 = 28550
暗号文 = 74597128
復号した平文 = 28550
■成功！

暗号鍵 = 5431 (847469081)
復号鍵 = 65065219 (847469081)
平文 = 52017
暗号文 = 774888864
復号した平文 = 52017
■成功！

暗号鍵 = 7309 (1558907309)
復号鍵 = 722680363 (1558907309)
平文 = 680
暗号文 = 1035114472
復号した平文 = 680
■成功！

暗号鍵 = 9221 (3715798837)
復号鍵 = 4029581 (3715798837)
平文 = 7644
暗号文 = 3582662490
復号した平文 = 7644
■成功！

平文と復号した平文が一致することしか見てないけど、ちゃんと実装できている。多分。...と思う。...と信じたい。

アルゴリズム (ほとんど自分用メモ)

鍵生成 (GenKey関数)

do
{
	while(p = CRandom16() | 1, IsComposite(p));           // p が奇素数になるまで繰り返す。
	while(q = CRandom16() | 1, p == q || IsComposite(q)); // q が p 以外の奇素数になるまで繰り返す。
}
while(p * q < 0x10000); // p * q (法n)が 16 bit に満たない場合はやり直す。
  • 異なる16ビットの奇素数を p, q とする。
*m = p * q;
  • m(法n)
p--;
q--;

p *= q / GCD(p, q);
  • (p - 1) * (q - 1) / GCD(p - 1, q - 1) を求め p にセットする。
    • 0 以上 m 未満の整数 x について x^p % m == 1 が成り立つ。⇒ 何でだっけ... ⇒ フェルマーの小定理？
    • なので (n ^ (p + 1)) % m == n も成り立つ。
    • なので e * d == (p の倍数 + 1) となるような e, d を求めれば (((x ^ e) % m) ^ d) % m == x という風に使える。
      • x が平文
      • (x ^ e) % m が暗号文
while(*e = CRandom16() | 1, IsComposite(*e) || ExtGCD(*e, p, d, &tmp, p) != 1);
  • p と互いに素な e を求める。
    • 素数から選ぶのは、素数の方が p と互いに素になりやすいから？
    • だいぶ前に 3 など小さい素数が使われると聞いた気がする。(うろ覚え)
      • 暗号鍵は総当たり攻撃への耐性を求められないため、計算量を少なくした方が良いため。
    • Wikipedia によると 65537 がよく使われるらしい。
      • 使われるということは 65537 は常に p と互いに素になるってこと？？？
  • GCD(e, p) == 1 なので、ExtGCD の第3引数 a の指す先には e * d == (p の倍数 + 1) となるような d がセットされる。
    • (*a) * x + (*b) * y == 1 (mod m) ということは ((*a) * x) % y == 1 なので
    • 本実装における ExtGCD は (*a), (*b) に m を法とする整数をセットしてくれるので、(*a) をそのまま d として使える。

暗号化 (Enc関数)

  • 暗号文 = 平文 ^ e mod m
    • 平文は 16 ビットの符号無し整数

復号 (Dec関数)

  • 平文 = 暗号文 ^ d mod m