RSA暗号で遊んでみる

  • この記事では

RSA暗号C#で作って遊ぼうと思います

「桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つ」 RSA暗号 - Wikipedia


どういうことかというと
公開鍵が復号用の秘密鍵の積になってるけど、桁数が大きすぎて素因数分解できない = 秘密鍵がバレない、そんな暗号方式です。
暗号化のほか、ディジタル署名にも使われています。

  • まずはRSA暗号についてざっくりと解説

サルにもわかるRSA暗号: RSA暗号の世界はやわかり RSAがすごくわかりやすいので、先に読んでおきましょう。
登場人物

    • 暗号化対象のデータ m
    • 秘密鍵 p, q, d
    • 公開鍵 pq(秘密鍵pとqの積), e
    • 暗号化の式 c = m ^ e mod pq
    • 復号の式 m = c ^ d mod pq

p, q, eは勝手に決めます。ただしp, qは素数、eにp - 1とq - 1の最小公倍数Lと互いに素かつLより小さい数じゃなきゃダメです*1
それからdはp, q, eから求めます(やり方は後述)。


暗号化と復号の流れ
やること自体は簡単で、
暗号化
c = m ^ e mod pq を計算するだけ
復号

  1. p, q, eからdを求める
  2. m = c ^ d mod pq を計算

という感じです。
暗号化は公開鍵pqとeだけで行い、復号の際に秘密鍵p, q, dを使います。通信する相手に渡すのは公開鍵だけでいいので、他の人に復号される心配がありません。
もちろん公開鍵pqを素因数分解すれば秘密鍵p, qが求められますが、その素因数分解がほぼ不可能なぐらい困難なので、大丈夫らしいです。


具体例
m = 15, p = 3, q = 11, e = 7のとき
pq = 3 * 11 = 33
このときd = 3になるので、
暗号化: 15 ^ 7 mod 33 = 170859375 mod 33 = 27
復号: 27 ^ 3 mod 33 = 19683 mod 33 = 15
ちゃんと復号後のデータが元のデータ(m = 15)と一致してますね。


仕組み
こことか見てもらえばいいんじゃないかと思います。
サルにもわかるRSA暗号: RSA暗号の世界

ざっくり書くと、
暗号化/復号の式 m ^ k mod pq では、
k = n * (p-1とq-1の最小公倍数) + 1 (nは正の整数)
のときに
m = m ^ k mod pq
となる(つまり元に戻る)性質があります。
なので、
m ^ e mod pq
で暗号化したら
e * d = n * (p-1とq-1の最小公倍数) + 1 (nは正の整数)
となるようなdを選んでやれば
(m ^ e mod pq) ^ d mod pq = (m ^ k) mod pq = m
となって復号できるというわけです。


このときのdの選び方は、

  1. まずp-1, q-1の最小公倍数を求め、Lとおく
  2. L * n + e * d = 1 を満たす正の整数dを求める(これは拡張ユークリッドの互除法で求められる)

という流れでいけます(nは正の整数)。


注意するところ
暗号化の式 m ^ e mod pq を見ると簡単そうですが、
m = 97, e = 11, pq = 377とかでやると m ^ e の時点で
97 ^ 11 = 7153014030880804126753
とかになって普通にオーバーフローします。そこで、eを2のべき乗に分解して計算します。このへんのやり方は、はやわかり RSAの「暗号化と復号化の例」のところとか見てください。ソースコードでは、modPower()メソッドがこれをやっています。

  • C#で書くと

こんな感じ。素数のリストは素数表と素数メモなどでいっぱい公開されてるようです。
あ、それから今回のコードは鍵がlong型なので、せいぜい64ビットまでの値しか使えません。実際は512ビットくらいの数なら素因数分解できてしまうらしいので、そこらへんはご注意ください。

using System;

/// <summary>RSA暗号</summary>
public class Rsa
{
	/// <summary>データを暗号化する</summary>
	/// <param name="data">対象データ</param>
	/// <param name="pq">公開鍵pq</param>
	/// <param name="e">公開鍵e</param>
	/// <returns>暗号化されたデータ</returns>
	public static long[] Encrypt(long[] data, long pq, long e)
	{
		long[] result = new long[data.Length];
		// data[i] ^ e mod pqで暗号化
		for (int i = 0; i < result.Length; i++)
			result[i] = modPower(data[i], e, pq);

		return result;
	}

	/// <summary>データを復号する</summary>
	/// <param name="data">対象データ</param>
	/// <param name="p">秘密鍵p</param>
	/// <param name="q">秘密鍵q</param>
	/// <param name="e">公開鍵e</param>
	/// <returns>復号されたデータ</returns>
	public static long[] Decrypt(long[] data, long p, long q, long e)
	{
		// 秘密鍵dを求めて
		long d = getD(p, q, e);
		// 復号(やることは暗号化と同じ)
		return Encrypt(data, p * q, d);
	}

	/// <summary>nを法とする累乗を計算する(Pow(number, exp) % n)</summary>
	/// <param name="number">基数</param>
	/// <param name="exp">指数</param>
	/// <param name="n"></param>
	/// <returns>nを法とする累乗の値</returns>
	private static long modPower(long number, long exp, long n)
	{
		long result = 1;
		long powNumber = number;

		// expを2のべき乗に分解して計算
		// powNumberはnumber ^ 1, number ^ 2, number ^ 4, number ^ 8, number ^ 16, ...
		// のようにnumberの2のべき乗をとっていく
		// expの各ビットが2のべき乗の係数にあたるので、
		// ビットシフトしつつ最下位ビットの係数 > 0なら結果に乗じていく
		while (exp > 0) {
			if ((exp & 1) > 0)
				result = (result * powNumber) % n;
			powNumber = (powNumber * powNumber) % n;
			exp >>= 1;
		}

		return result;
	}

	/// <summary>最小公倍数を算出</summary>
	/// <param name="a">値1</param>
	/// <param name="b">値2</param>
	/// <returns>最小公倍数</returns>
	private static long getLcm(long a, long b)
	{
		long tmp;
		long m = a * b;
		while (a % b != 0) {
			tmp = b;
			b = a % b;
			a = tmp;
		}
		return m / b;
	}

	/// <summary>秘密鍵dを求める</summary>
	/// <param name="p">秘密鍵p</param>
	/// <param name="q">秘密鍵q</param>
	/// <param name="e">公開鍵e</param>
	/// <returns>秘密鍵d</returns>
	private static long getD(long p, long q, long e)
	{
		long lcm = getLcm(p - 1, q - 1);
		long x1 = 1, y1 = 0, z1 = lcm;
		long x2 = 0, y2 = 1, z2 = e;
		long x3, y3, z3;
		long a = 1;

		// 拡張ユークリッドの互除法
		// LCM(p - 1, q - 1) * n + e * d = 1
		// を満たすdを求める
		while (z2 > 0) {
			a = (long)(z1 / z2);
			x3 = x1 - a * x2;
			y3 = y1 - a * y2;
			z3 = z1 - a * z2;
			x1 = x2;
			y1 = y2;
			z1 = z2;
			x2 = x3;
			y2 = y3;
			z2 = z3;
		}

		return (x1 > y1) ? x1 : y1;
	}
}

class Program
{
	static void Main(string[] args)
	{
		long p = 12671;
		long q = 1009;
		long pq = p * q;
		long e = 11;
		long[] data = { 123, 342, 32, 78, 67 };

		Console.Write("元データ:\t");
		foreach (var a in data)
			Console.Write("{0} ", a);
		Console.WriteLine();

		long[] cipher = Rsa.Encrypt(data, pq, e);
		Console.Write("暗号化:\t\t");
		foreach (var a in cipher)
			Console.Write("{0} ", a);
		Console.WriteLine();

		long[] msg = Rsa.Decrypt(cipher, p, q, e);
		Console.Write("復号:\t\t");
		foreach (var a in msg)
			Console.Write("{0} ", a);
		Console.WriteLine();
	}
}


実行結果
f:id:ser1zw:20100801165627p:image
ちゃんと復号できたようです。

  • まとめ

RSA暗号C#で作って遊んでみました。アルゴリズムは単純だけど、仕組みを調べると結構おもしろいですね。

*1:11と65537がよく使われるらしい