Light theme icon (depiction of a sun)
Dark theme icon (depiction of a moon)
โ€˜๐ŸŽฏ ํ† ์ด ํ”„๋กœ์ ํŠธโ€™ ์‹œ๋ฆฌ์ฆˆ

๐Ÿ” RSA ์•Œ๊ณ ๋ฆฌ์ฆ˜

  • 0
  • 2
0
2

๋ฌธ์ œ

๊ณต๊ฐœํ‚ค ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ค‘ Rivest, Shamir, Adleman์— ์˜ํ•ด ์„ค๊ณ„๋œ RSA ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ•˜๋ผ

๋กœ์ง

  1. 2๊ฐœ์˜ ์†Œ์ˆ˜ (p, q)๊ฐ€ ํ•„์š”ํ•˜๋‹ค
  2. n = p * q
  3. ฯ•(n) = (p-1) * (q-1)
  4. e = e์™€ ฯ•(n)์˜ ์„œ๋กœ์†Œ
  5. d = e*d mod ฯ•(n) = 1
  6. c = m^e mod n
  7. m = c^d mod n

์ฃผ์˜ ์‚ฌํ•ญ

  1. ์•”ํ˜ธํ™”ํ•˜๋Š” ํ‰๋ฌธ์€ n์˜ ์ž๋ฆฟ์ˆ˜๋ณด๋‹ค ์ž‘์€ ์ž๋ฆฟ์ˆ˜๋ฅผ ๊ฐ€์ ธ์•ผํ•œ๋‹ค. a. ํ‰๋ฌธ์ด '123456789'์ด๊ณ , n์ด '1234'์ด๋ฉด ํ‰๋ฌธ์„ '123', '456', 789'๋กœ ๋‚˜๋ˆ ์„œ ์•”ํ˜ธํ™”ํ•ด์•ผํ•œ๋‹ค.
  2. p์™€ q๋Š” ๋‹ค์Œ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•ด์•ผ ํ•œ๋‹ค. a. p์™€ q๋Š” ๊ฐ™์ง€ ์•Š๊ณ  ๊ฑฐ์˜ ๊ฐ™์€ ํฌ๊ธฐ์˜ ์ž๋ฆฟ์ˆ˜์•ผ์•ผ ํ•œ๋‹ค. b. p-1๊ณผ q-1์€ ์ปค๋‹ค๋ž€ ์†Œ์ธ์ˆ˜๋ฅผ ๊ฐ๊ฐ ๊ฐ€์ ธ์•ผ ํ•œ๋‹ค. c. p-1๊ณผ q-1์˜ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜๋Š” ์ž‘์€ ์ˆ˜์—ฌ์•ผ ํ•œ๋‹ค

๊ตฌํ˜„ํ•˜์ง€ ์•Š์•˜์ง€๋งŒ, TMI

  1. ์‹ค์ œ RSA์—์„œ ์‚ฌ์šฉํ•˜๋Š” p์™€ q๋Š” 100์ž๋ฆฌ ์ •๋„์˜ ์†Œ์ˆ˜๋กœ ๊ฑฐ์˜ ๊ฐ™์€ ํฌ๊ธฐ์˜ ์ž๋ฆฟ์ˆ˜๋ฅผ ๊ฐ€์ง€๋Š” ์ˆ˜๋ฅผ ์„ ํƒํ•œ๋‹ค.

์ฝ”๋“œ

rsa.h

#ifndef _RSA
#define _RSA

typedef struct key
{
    long pkey;  // ์ดˆ๊ธฐ 2๊ฐœ์˜ ์†Œ์ˆ˜ p์™€ q๊ฐ€ ๊ณฑํ•ด์„œ ๋‚˜์˜ค๋Š” n์ด ์ €์žฅ๋  ๋ณ€์ˆ˜
    long ekey;  // public-key
    long dkey;  // private-key
    int pkey_size;

} Key;

class Rsa
{
public:
    Rsa();
    virtual ~Rsa();

public:
    Key produce_keys();
    long endecrypt(const long msg, const long key, const long pkey);
    int sizeof_int(long data);

private:
    long produce_pkey(const long prime1, const long prime2);
    long produce_ekey(const long orla);
    long produce_dkey(const long ekey, const long orla);
    long produce_prime();
    long produce_orla(const long prime1, const long prime2);
    long produce_gcd(const long a, const long b);
    bool is_prime(const long digit);
};

#endif

main.cpp

#include "rsa.h"
#include <iostream>

using namespace std;

int main(void)
{
    Rsa rsa;
    Key key = rsa.produce_keys();
    cout << "=============================" << endl;
    cout << "=========== R S A ===========" << endl;
    cout << "=============================\n" << endl;

    cout << "=====================================" << endl;
    cout << "์•”ํ˜ธํ™” ํ›„ ์–ป์€ ํ‚ค๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค."<< endl;
    cout << "n ํ‚ค : " << key.pkey << endl;
    cout << "์•”ํ˜ธํ™” ํ‚ค (๊ณต๊ฐœํ‚ค) : " << key.ekey << endl;
    cout << "์•”ํ˜ธ ํ•ด๋… ํ‚ค (๊ฐœ์ธํ‚ค) : " << key.dkey << endl;
    cout << "=====================================\n" << endl;
    long msg;
    cout << "์•”ํ˜ธํ™”ํ•  ์ •๋ณด๋ฅผ ์ž…๋ ฅํ•˜์‹ญ์‹œ์˜ค (์ˆซ์ž, ๋„ˆ๋ฌด ํด ์ˆ˜ ์—†์Œ) : ";
    cin >> msg;
    cout << "\n=====================================" << endl;
    long msg_des = rsa.endecrypt(msg, key.ekey, key.pkey);
    cout << "์•”ํ˜ธํ™”๋œ ์ •๋ณด๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค : " << msg_des << endl;
    msg_des = rsa.endecrypt(msg_des, key.dkey, key.pkey);
    cout << "์•”ํ˜ธ ํ•ด๋…๋œ ๋ฉ”์‹œ์ง€๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค : " << msg_des << endl;
    cout << "=====================================" << endl;
    return 0;
}

rsa.cpp

#include "rsa.h"
#include <cstdlib>
#include <ctime>
#include <string>
#include <bitset>
#include <iostream>

using namespace std;

Rsa::Rsa()
{
}

Rsa::~Rsa()
{
}
/***********************************************************************
์•”ํ˜ธํ™” ๋ณตํ˜ธํ™”๋ฅผ ๋™์‹œ์— ์ง„ํ–‰ํ•˜๋Š” ๋ฉ”์†Œ๋“œ
c = m^e mod n
m = c^d mod n
๋ผ๋Š” ์‹์€ ๊ฐ™๊ณ  ๋ณ€์ˆ˜๋งŒ ๋งค๊ฐœ๊ฐ’๋งŒ ๋ฐ”๋€Œ๋ฉด ๋˜๋ฏ€๋กœ ํ•˜๋‚˜์˜ ๋ฉ”์†Œ๋“œ์—์„œ ์ฒ˜๋ฆฌํ•จ
***********************************************************************/
long Rsa::endecrypt(const long msg, const long key, const long pkey)
{
    long msg_des = 1;
    long root = msg;
    long index = key;
    //int n_size = sizeof_int(pkey);
    //int msg_size = sizeof_int(msg);
    //int size = msg_size / n_size;
    //if (msg_size % n_size)
    //  size = size + 1;

    while (index)
    {
        //cout << bitset<32>(index) << endl;
        if (index & 1) {
            msg_des = (msg_des * root) % pkey;
            //cout << "msg_des : " << msg_des << endl;
        }
        index >>= 1;
        //cout << "b root : " << root << endl;
        root = (root * root) % pkey;
        //cout << "a root : " << root << endl;
    }
    return msg_des;
}


/************************************
 p์™€ q๋ฅผ ์ƒ์„ฑํ•ด์„œ
 n, e, d ํ‚ค๋ฅผ ์ƒ์„ฑ
 * *********************************/
Key Rsa::produce_keys()
{
    long prime1 = produce_prime();  // p
    long prime2 = produce_prime();  // q
    while (prime2 == prime1)        // p์™€ q๋Š” n์„ ๋งŒ๋“ค๊ณ  ํ๊ธฐํ•ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์—
        prime2 = produce_prime();   // ๋”ฐ๋กœ ์ €์žฅํ•ด์„œ ๋ฉ”์†Œ๋“œ ๋ฐ–์œผ๋กœ ๋นผ์ง€ ์•Š์Œ

    Key key;
    long orla = produce_orla(prime1, prime2);   // ์˜ค์ผ๋Ÿฌ n ์ƒ์„ฑ
    key.pkey = produce_pkey(prime1, prime2);    // n ์ƒ์„ฑ
    key.ekey = produce_ekey(orla);              // e ์ƒ์„ฑ
    key.dkey = produce_dkey(key.ekey, orla);    // d ์ƒ์„ฑ
    return key;
}

/************************************
 N ํ‚ค ์ƒ์„ฑ
 p * q
 * *********************************/
long Rsa::produce_pkey(const long prime1, const long prime2)
{
    return prime1 * prime2;
}

/************************************
 ์˜ค์ผ๋Ÿฌ n ์ƒ์„ฑ
************************************/
long Rsa::produce_orla(const long prime1, const long prime2)
{
    return (prime1 - 1) * (prime2 - 1);
}

/************************************
 ์•”ํ˜ธํ™” ํ‚ค (๊ณต๊ฐœํ‚ค) e ์ƒ์„ฑ
 * *********************************/
long Rsa::produce_ekey(const long orla)
{
    long ekey;
    while (true)
    {
        ekey = rand() % orla;   // ๋žœ๋ค ์ˆ˜๋ฅผ ์˜ค์ผ๋Ÿฌ n์œผ๋กœ ๋‚˜๋จธ์ง€ ์—ฐ์‚ฐ
        if (ekey >= 2 && produce_gcd(ekey, orla) == 1)  // e-key์™€ ์˜ค์ผ๋Ÿฌ n์ด ์„œ๋กœ์†Œ์ธ์ง€ ํŒ๋ณ„
            break;
    }
    return ekey;
}

/************************************
 ๋ณตํ˜ธํ™” ํ‚ค (๊ฐœ์ธํ‚ค) d ์ƒ์„ฑ
 * *********************************/
long Rsa::produce_dkey(const long ekey, const long orla)
{
    long dkey = orla / ekey;
    while (true)
    {
        if (((dkey * ekey) % orla) == 1)
            break;
        else 
            ++dkey;
    }
    return dkey;
}

/************************************
 [100, 200] ๋ฒ”์œ„์—์„œ ์ž„์˜์˜ ์†Œ์ˆ˜ ์ƒ์„ฑ
 * *********************************/
long Rsa::produce_prime()
{
    long prime = 0;
    srand(time(0));
    while (true)
    {
        prime = rand() % 100 + 100;
        if (is_prime(prime))
            break;
    }
    return prime;
}

/************************************
 ๋‘ ์ˆซ์ž์˜ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜ ์ƒ์„ฑ        
 * *********************************/
long Rsa::produce_gcd(const long a, const long b)
{
    long dividend = a;
    long divisor = b;
    long residual = dividend % divisor;
    while (residual)
    {
        dividend = divisor;
        divisor = residual;
        residual = dividend % divisor;
    }
    return divisor;
}

/************************************
 ์†Œ์ˆ˜์ธ์ง€ ํŒ๋‹จ
 * *********************************/
bool Rsa::is_prime(const long digit)
{
    int tmp = 2;
    while (tmp < digit)
        if (!(digit % tmp++))
            break;

    if (tmp == digit)
        return true;
    return false;
}

/************************************
 ์ž…๋ ฅ๊ฐ’์˜ ์ž๋ฆฟ์ˆ˜ ํŒ๋‹จ
 * *********************************/
int Rsa::sizeof_int(long data)
{
    int pos = 1;
    
    if (data < 0)
        data *= (-1);

    for (int i = 0; ; i++, pos++) {
        if ((data /= 10) <= 0)
            break;
    }

    return pos;
}

๊ฒฐ๊ณผ

์ฐธ๊ณ ๋ฌธํ—Œ

GitHub, "RSA Encryption Decryption", https://github.com/cassvin/Rsa, (2020.06.05.)

0๋ถ„์ „
์ž‘์„ฑ๋œ ๋Œ“๊ธ€์ด ์—†์Šต๋‹ˆ๋‹ค. ์ฒซ ๋Œ“๊ธ€์„ ๋‹ฌ์•„๋ณด์„ธ์š”!
    ๋Œ“๊ธ€์„ ์ž‘์„ฑํ•˜๋ ค๋ฉด ๋กœ๊ทธ์ธ์ด ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค.