rsa.cpp

#include <iostream>
#include <stdlib.h>
#include <vector>
#include <ctime>
#include <cmath>

using namespace std;

#define PRIME_NUM_RANGE 10000

int gcd( int m, int n );
int lcm( int m, int n );
bool isPrimeNum( int num );
void listPrimeNum( void );
int extEuqlid( int a, int b );

vector<int> primeNumAry;

int main( void ) {

  srand( (unsigned int)time( NULL ) );

  listPrimeNum();
  int pNum = primeNumAry.size();

  // 異なる素数 p, q の用意
  int p, q;
  do {
    p = primeNumAry[ rand() % pNum ];
    q = primeNumAry[ rand() % pNum ];
  } while( p == q );

  // 公開鍵 n
  int n = p * q;

  // 最小公倍数 m
  int m = lcm( p - 1, q - 1 );

  // 公開鍵 e
  int e = 2;
  while( gcd( m, e ) != 1 ) e++;

  // 秘密鍵 d
  int d = extEuqlid( e, m );

  cout << "p (Prime number): " << p << endl;
  cout << "q (Prime number): " << q << endl;
  cout << "n (Public key)  : " << n << endl;
  cout << "m (LCM(p-1,q-1)): " << m << endl;
  cout << "e (Public key)  : " << e << endl;
  cout << "d (Secret key)  : " << d << endl;

  return 0;
}

/* 最大公約数を求める関数 */
int gcd( int m, int n ) {

  if( n == 0 ) {
    return m;
  } else {
    return gcd( n, m % n );
  }
}

/* 最小公倍数を求める関数 */
int lcm( int m, int n ) {

  return m * n /  gcd( m, n );
}

/* 素数判定の関数 */
bool isPrimeNum( int num ) {

  if( num <= 1 ) {
    return false;
  }

  int n = (int)sqrt( (double)num );

  for( int  i = 2; i <= n; i++ ){

    if( num % i == 0 ) {
      return false;
    }
  }
  return true;
}

/* 素数をリストアップする関数 */
void listPrimeNum( void ) {

  for( int i = 2; i <= PRIME_NUM_RANGE; i++ ) {
    if( isPrimeNum( i ) ) {
      primeNumAry.push_back( i );
    }
  }
}

/* 拡張ユーグリッド互除法 */
int extEuqlid( int a, int b ) {

  int x1 = 0, y1 = 1, r1 = b;
  int x2 = 1, y2 = 0, r2 = a;

  int d;

  while( true ) {

    int q = r1 / r2;
    int r = r1 % r2;
    int x = x1 - x2 * q;
    int y = y1 - y2 * q;

    if( r == 0 ) {
      d = x2;
      break;
    }

    x1 = x2; y1 = y2; r1 = r2;
    x2 =  x; y2 =  y; r2 =  r;
  }

  while( d <= 0 ) d += b;

  return d;
}