RSA暗号 C++

公開鍵暗号である RSA暗号をC++で実装してみました。

参考にさせてもらったのは、このページ（RSA暗号で遊んでみる - ser1zw's blog）の

C#で書かれた実装例です。ありがとうございます。

で、これをC++に移植しました↓

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <conio.h>
#include <cstring>
#include <iostream>
#define  P (__int64  )12671
#define  Q (__int64  )1009
#define  E (__int64  )6553
using namespace std;


class RSA
{
private:
	__int64   getl(__int64   p,__int64   q);
	__int64   getd(__int64   p,__int64   q,__int64   e);

public:
	__int64   Ec(__int64   ec, __int64   e, __int64   n);
	__int64   Dc(__int64   ec,__int64   p,__int64   q,__int64   e);
};


__int64   RSA::Ec(__int64   ee, __int64   e, __int64   n)
{
	__int64   result = 1;
	__int64   pown = ee;

	while (e > 0) {
		if((e & 1) > 0) result = (result * pown) % n;
		pown = (pown * pown) % n;
		e >>= 1;
	}

	return result;
}


__int64   RSA::getl(__int64   p,__int64   q)
{
	__int64   t;
	__int64   m = p*q;
	while (p % q != 0) {
		t = q;
		q = p % q;
		p = t;
	}
	return m / q;
}


__int64 RSA::getd(__int64   p,__int64   q,__int64   e)
{
	__int64   lcm = getl(p-1,q-1);
	int x1 = 1, y1 = 0, z1 = lcm;
	int x2 = 0, y2 = 1, z2 = e;
	int x3, y3, z3;
	int a = 1;

	while(z2 > 0) {
		a = (__int64  )(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;
}


__int64 RSA::Dc(__int64   ee,__int64   p,__int64   q,__int64   e)
{
	return Ec(ee,getd(p,q,e),p*q);
}

int main(void)
{
	int key = 13;//暗号化対象
	RSA rsa;
	cout << "key -> " << key << endl;
	cout << "暗号-> " << (key = rsa.Ec(key,E,P*Q)) << endl;
	cout << "復号-> " << rsa.Dc(key,P,Q,E) << endl;
	
	return 0;
}

ちょっと変数名が変わったり、新しい関数ができていたりしますが、

    __int64  RSA::Ec(
        __int64   ee,// 暗号化対象 
        __int64   e, // e
        __int64   n) // p * q

    __int64 RSA::Dc(
        __int64   ee,// 復号化対象
        __int64   p,//  p
        __int64   q,//  q
        __int64   e)//  e

という風になっています。

RSA暗号が理解できないと難しいですが、
　　　　pとqは大きな素数
　　　　eはp-1とq-1の最小公倍数とおたがいに素な数
だったと思います。

あと、このコードは Visual C++ でコンパイルしたので64bit 整数は __int64 となっています。
他の環境でコンパイルするときは、unsigned long long にしたほうがいいと思います。

また、変なところがあったら教えていただけると光栄です。